os04-1

1、第四章 存儲器管理,4.1 程序的裝入和鏈接 4.2 連續(xù)分配方式 4.3 基本分頁存儲管理方式 4.4 基本分段存儲管理方式 4.5 虛擬存儲器的基本概念 4.6 請求分頁存儲管理方式 4.7 頁面置換算法 4.8 請求分段存儲管理方式,第四章 存儲器管理,存儲器的層次結構,,,容量、價格,速度、價格,第四章 存儲器管理,存儲器管理的目的主存的分配和管理：當用戶需要內存時,系統(tǒng)為之分配相應的存儲

2、空間；不需要時，及時回收，以供其它用戶使用。提高主存儲器的利用率：不僅能使多道程序動態(tài)地共享主存，提高主存利用率，最好還能共享主存中某個區(qū)域的信息。,第四章 存儲器管理,存儲器管理的目的主存的分配和管理：當用戶需要內存時,系統(tǒng)為之分配相應的存儲空間；不需要時，及時回收，以供其它用戶使用。提高主存儲器的利用率：不僅能使多道程序動態(tài)地共享主存，提高主存利用率，最好還能共享主存中某個區(qū)域的信息。,第四章 存儲器管理,存儲器管理的目的

3、“擴充”主存容量：為用戶提供比主存物理空間大得多的地址空間，以至使用戶感覺他的作業(yè)是在這樣一個大的存儲器中運行。存儲保護：確保多道程序都在各自分配到存儲區(qū)域內操作，互不干擾，防止一道程序破壞其它作業(yè)或系統(tǒng)文件的信息。,第四章 存儲器管理,存儲器管理的目的“擴充”主存容量：為用戶提供比主存物理空間大得多的地址空間，以至使用戶感覺他的作業(yè)是在這樣一個大的存儲器中運行。存儲保護：確保多道程序都在各自分配到存儲區(qū)域內操作，互不干擾，防

4、止一道程序破壞其它作業(yè)或系統(tǒng)文件的信息。,第四章 存儲器管理,基本概念邏輯地址（相對地址，虛地址） ：用戶的程序經過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式，其首地址為0，其余指令中的地址都相對于首地址而編址。不能用邏輯地址在內存中讀取信息。物理地址（絕對地址，實地址）：內存中存儲單元的地址，可直接尋址。,第四章 存儲器管理,基本概念邏輯地址（相對地址，虛地址） ：用戶的程序經過匯編或編譯后形成目標代碼，目標代

5、碼通常采用相對地址的形式，其首地址為0，其余指令中的地址都相對于首地址而編址。不能用邏輯地址在內存中讀取信息。物理地址（絕對地址，實地址）：內存中存儲單元的地址，可直接尋址。,第四章 存儲器管理,基本概念地址空間程序用來訪問信息所用地址單元的集合邏輯（相對）地址的集合由編譯程序生成存儲空間主存中物理單元的集合物理（絕對）地址的集合由裝配程序等生成,第四章 存儲器管理,基本概念地址空間程序用來訪問信息所用地址單元

6、的集合邏輯（相對）地址的集合由編譯程序生成存儲空間主存中物理單元的集合物理（絕對）地址的集合由裝配程序等生成,地址映射,Load A 200 3456 。 。,1200,Load A data1data1 3456,源程序,,Load A 200 3456,0,100,200,編譯連接,邏輯地址空間,,,,BA=1000,地址空間 存儲空間,第四章 存儲器管理,基

7、本概念定位（存儲分配）：為具體的程序和數(shù)據(jù)等分配存儲單元或存儲區(qū)工作。映射：把邏輯地址轉換為相應的物理地址的過程。,第四章 存儲器管理,基本概念定位（存儲分配）：為具體的程序和數(shù)據(jù)等分配存儲單元或存儲區(qū)工作。映射：把邏輯地址轉換為相應的物理地址的過程。,4.1 程序的裝入和鏈接,對用戶程序的處理步驟,4.1 程序的裝入和鏈接,程序的裝入絕對裝入方式編譯程序產生絕對地址的目標代碼，即代碼的邏輯地址和物理地址相同裝入程序

8、按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內存，不進行地址的修改只適用于單道程序環(huán)境,4.1 程序的裝入和鏈接,程序的裝入絕對裝入方式編譯程序產生絕對地址的目標代碼，即代碼的邏輯地址和物理地址相同裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內存，不進行地址的修改只適用于單道程序環(huán)境,4.1 程序的裝入和鏈接,程序的裝入絕對裝入方式編譯程序產生絕對地址的目標代碼，即代碼的邏輯地址和物理地址相同裝入程序按照裝入模塊中的地址，將

9、程序和數(shù)據(jù)裝入內存，不進行地址的修改只適用于單道程序環(huán)境,4.1 程序的裝入和鏈接,程序的裝入可重定位裝入方式目標模塊的起始地址從0開始，程序中其他地址相對于起始地址計算，裝入程序根據(jù)內存的當前情況，將裝入模塊裝入內存的適當位置。,作業(yè)裝入內存時的情況,4.1 程序的裝入和鏈接,程序的裝入可重定位裝入方式重定位：在裝入時對目標程序中指令和數(shù)據(jù)地址的修改過程?；蛘哒f：把作業(yè)地址空間中使用的邏輯地址變換成內存空間中的物理地址的過程

10、。又稱地址映射。地址變換在裝入時一次完成，以后不再改變，故稱為靜態(tài)重定位。,4.1 程序的裝入和鏈接,程序的裝入可重定位裝入方式重定位：在裝入時對目標程序中指令和數(shù)據(jù)地址的修改過程稱。或者說：把作業(yè)地址空間中使用的邏輯地址變換成內存空間中的物理地址的過程。又稱地址映射。地址變換在裝入時一次完成，以后不再改變，故稱為靜態(tài)重定位。,4.1 程序的裝入和鏈接,程序的裝入可重定位裝入方式優(yōu)點：無需增加硬件地址變換機構；實現(xiàn)簡單；適用

11、于多道程序環(huán)境。缺點：不允許程序運行時在內存中移動位置；程序在存儲空間中只能連續(xù)分配；多個用戶難以共享存于內存中的同一程序。,4.1 程序的裝入和鏈接,程序的裝入可重定位裝入方式優(yōu)點：無需增加硬件地址變換機構；實現(xiàn)簡單；適用于多道程序環(huán)境。缺點：不允許程序運行時在內存中移動位置；程序在存儲空間中只能連續(xù)分配；多個用戶難以共享存于內存中的同一程序。,4.1 程序的裝入和鏈接,程序的裝入動態(tài)運行時裝入方式裝入程序把裝入模塊裝入內

12、存后，不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序真正要執(zhí)行時才進行。裝入內存后的所有地址都仍是相對地址。允許程序在內存中移動；需要重定位寄存器的支持優(yōu)點：可對內存進行非連續(xù)分配；提供了實現(xiàn)虛存的基礎；有利于程序段的共享。,4.1 程序的裝入和鏈接,程序的裝入動態(tài)運行時裝入方式裝入程序把裝入模塊裝入內存后，不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序真正要執(zhí)行時才進行。

13、裝入內存后的所有地址都仍是相對地址。允許程序在內存中移動；需要重定位寄存器的支持優(yōu)點：可對內存進行非連續(xù)分配；提供了實現(xiàn)虛存的基礎；有利于程序段的共享。,4.1 程序的裝入和鏈接,程序的裝入動態(tài)運行時裝入方式裝入程序把裝入模塊裝入內存后，不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序真正要執(zhí)行時才進行。裝入內存后的所有地址都仍是相對地址。允許程序在內存中移動；需要重定位寄存器的支持優(yōu)點：可對

14、內存進行非連續(xù)分配；提供了實現(xiàn)虛存的基礎；有利于程序段的共享。,4.1 程序的裝入和鏈接,程序的裝入動態(tài)運行時裝入方式裝入程序把裝入模塊裝入內存后，不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序真正要執(zhí)行時才進行。裝入內存后的所有地址都仍是相對地址。允許程序在內存中移動；需要重定位寄存器的支持優(yōu)點：可對內存進行非連續(xù)分配；提供了實現(xiàn)虛存的基礎；有利于程序段的共享。,4.1 程序的裝入和鏈接,程序的裝

15、入動態(tài)運行時裝入方式裝入程序把裝入模塊裝入內存后，不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序真正要執(zhí)行時才進行。裝入內存后的所有地址都仍是相對地址。允許程序在內存中移動；需要重定位寄存器的支持優(yōu)點：可對內存進行非連續(xù)分配；提供了實現(xiàn)虛存的基礎；有利于程序段的共享。,4.1 程序的裝入和鏈接,程序的鏈接靜態(tài)鏈接方式在程序運行之前，先將各目標模塊以及所需的庫函數(shù)，鏈接成一個完整的裝配模塊。在將

16、這幾個目標模塊裝配成一個裝入模塊時，須解決以下兩個問題： (1) 對相對地址進行修改。 (2) 變換外部調用符號。,4.1 程序的裝入和鏈接,程序的鏈接靜態(tài)鏈接方式在程序運行之前，先將各目標模塊以及所需的庫函數(shù)，鏈接成一個完整的裝配模塊。在將這幾個目標模塊裝配成一個裝入模塊時，須解決以下兩個問題： (1) 對相對地址進行修改。 (2) 變換外部調用符號。,4.1 程序的裝入和鏈接,程序的鏈接裝入時

17、動態(tài)鏈接方式采用邊裝入邊鏈接的方式優(yōu)點：便于修改和更新；便于實現(xiàn)對目標模塊的共享。 缺點：程序每次要運行的模塊可能不相同，但無法知道本次要運行哪些模塊，故只能將所有可能要運行的模塊都全部裝入內存并鏈接。,4.1 程序的裝入和鏈接,程序的鏈接裝入時動態(tài)鏈接方式采用邊裝入邊鏈接的方式優(yōu)點：便于修改和更新；便于實現(xiàn)對目標模塊的共享。 缺點：程序每次要運行的模塊可能不相同，但無法知道本次要運行哪些模塊，故只能將所有可能要運行的模塊

18、都全部裝入內存并鏈接。,4.1 程序的裝入和鏈接,程序的鏈接裝入時動態(tài)鏈接方式采用邊裝入邊鏈接的方式優(yōu)點：便于修改和更新；便于實現(xiàn)對目標模塊的共享。 缺點：程序每次要運行的模塊可能不相同，但無法知道本次要運行哪些模塊，故只能將所有可能要運行的模塊都全部裝入內存并鏈接。,4.1 程序的裝入和鏈接,程序的鏈接運行時動態(tài)鏈接方式對某些目標模塊的鏈接，在程序執(zhí)行中需要該模塊時，才對它進行的鏈接。優(yōu)點：凡在執(zhí)行過程中未被用到的目標模

19、塊，都不會被調入內存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內存空間。,4.1 程序的裝入和鏈接,程序的鏈接運行時動態(tài)鏈接方式對某些目標模塊的鏈接，在程序執(zhí)行中需要該模塊時，才對它進行的鏈接。優(yōu)點：凡在執(zhí)行過程中未被用到的目標模塊，都不會被調入內存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內存空間。,4.2 連續(xù)分配方式,單一連續(xù)分配最簡單的一種存儲管理方式，但只能用于單用

20、戶、單任務的操作系統(tǒng)中。內存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內存空間， 提供給用戶使用。優(yōu)點：管理簡單，不要求專用的硬件支持；為防止破壞OS ，設置界限寄存器；易于實現(xiàn)。缺點：存儲器利用率低；信息不共享；CPU 利用率低，周轉時間長。,4.2 連續(xù)分配方式,單一連續(xù)分配最簡單的一種存儲管理方式，但只能用于單用戶、單任務的操作系統(tǒng)中。內存分為系統(tǒng)區(qū)和用戶區(qū)

21、兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內存空間， 提供給用戶使用。優(yōu)點：管理簡單，不要求專用的硬件支持；為防止破壞OS ，設置界限寄存器；易于實現(xiàn)。缺點：存儲器利用率低；信息不共享；CPU 利用率低，周轉時間長。,4.2 連續(xù)分配方式,單一連續(xù)分配最簡單的一種存儲管理方式，但只能用于單用戶、單任務的操作系統(tǒng)中。內存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內存的

22、低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內存空間， 提供給用戶使用。優(yōu)點：管理簡單，不要求專用的硬件支持；為防止破壞OS ，設置界限寄存器；易于實現(xiàn)。缺點：存儲器利用率低；信息不共享；CPU 利用率低，周轉時間長。,4.2 連續(xù)分配方式,單一連續(xù)分配最簡單的一種存儲管理方式，但只能用于單用戶、單任務的操作系統(tǒng)中。內存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內存空間，

23、 提供給用戶使用。優(yōu)點：管理簡單，不要求專用的硬件支持；為防止破壞OS ，設置界限寄存器；易于實現(xiàn)。缺點：存儲器利用率低；信息不共享；CPU 利用率低，周轉時間長。,4.2 連續(xù)分配方式,固定分區(qū)分配運行多道程序的存儲管理方式。內存用戶被劃分為若干個固定大小的區(qū)域，每個分區(qū)中只裝入一道作業(yè)。內存利用率低。允許幾道作業(yè)并發(fā)。劃分分區(qū)的方法： 分區(qū)大小相等；分區(qū)大小不等。,4.2 連續(xù)分配方式,固定分區(qū)分配運行多道程序

24、的存儲管理方式。內存用戶被劃分為若干個固定大小的區(qū)域，每個分區(qū)中只裝入一道作業(yè)。內存利用率低。允許幾道作業(yè)并發(fā)。劃分分區(qū)的方法： 分區(qū)大小相等；分區(qū)大小不等。,4.2 連續(xù)分配方式,固定分區(qū)分配運行多道程序的存儲管理方式。內存用戶被劃分為若干個固定大小的區(qū)域，每個分區(qū)中只裝入一道作業(yè)。內存利用率低。允許幾道作業(yè)并發(fā)。劃分分區(qū)的方法： 分區(qū)大小相等；分區(qū)大小不等。,4.2 連續(xù)分配方式,固定分區(qū)分配運行多道程序

25、的存儲管理方式。內存用戶被劃分為若干個固定大小的區(qū)域，每個分區(qū)中只裝入一道作業(yè)。內存利用率低。允許幾道作業(yè)并發(fā)。劃分分區(qū)的方法： 分區(qū)大小相等；分區(qū)大小不等。,4.2 連續(xù)分配方式,固定分區(qū)分配運行多道程序的存儲管理方式。內存用戶被劃分為若干個固定大小的區(qū)域，每個分區(qū)中只裝入一道作業(yè)。內存利用率低。允許幾道作業(yè)并發(fā)。劃分分區(qū)的方法： 分區(qū)大小相等；分區(qū)大小不等。,4.2 連續(xù)分配方式,固定分區(qū)分配內存分配分

26、區(qū)使用表：各表項包括每個分區(qū)的起始地址，大小和狀態(tài)。用戶程序需要裝入時，內存分配程序檢索該表，找出一個能滿足要求尚未分配的分區(qū)，分配給該程序，并將其表項中的狀態(tài)置為“已分配”。若未找到大小足夠的分區(qū)，則拒絕為用戶程序分配內存。,4.2 連續(xù)分配方式,固定分區(qū)分配內存分配分區(qū)使用表：各表項包括每個分區(qū)的起始地址，大小和狀態(tài)。用戶程序需要裝入時，內存分配程序檢索該表，找出一個能滿足要求尚未分配的分區(qū)，分配給該程序，并將其表項中的

27、狀態(tài)置為“已分配”。若未找到大小足夠的分區(qū)，則拒絕為用戶程序分配內存。,4.2 連續(xù)分配方式,固定分區(qū)分配內存分配分區(qū)使用表：各表項包括每個分區(qū)的起始地址，大小和狀態(tài)。用戶程序需要裝入時，內存分配程序檢索該表，找出一個能滿足要求尚未分配的分區(qū)，分配給該程序，并將其表項中的狀態(tài)置為“已分配”。若未找到大小足夠的分區(qū)，則拒絕為用戶程序分配內存。,4.2 連續(xù)分配方式,動態(tài)分區(qū)分配（可變分區(qū)分配）按作業(yè)的實際大小來劃分分區(qū)，且

28、分區(qū)個數(shù)也是隨機的,實現(xiàn)多個作業(yè)對內存的共享，進一步提高內存資源利用率分區(qū)分配中的數(shù)據(jù)結構空閑分區(qū)表，一個空閑分區(qū)占一個表目，表目包括：分區(qū)序號、分區(qū)始址、分區(qū)大小空閑分區(qū)鏈。,4.2 連續(xù)分配方式,動態(tài)分區(qū)分配（可變分區(qū)分配）按作業(yè)的實際大小來劃分分區(qū)，且分區(qū)個數(shù)也是隨機的,實現(xiàn)多個作業(yè)對內存的共享，進一步提高內存資源利用率分區(qū)分配中的數(shù)據(jù)結構空閑分區(qū)表，一個空閑分區(qū)占一個表目，表目包括：分區(qū)序號、分區(qū)始址、分區(qū)大小空

29、閑分區(qū)鏈。,,4.2 連續(xù)分配方式,動態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法首次適應算法（First Fit）把主存中所有空閑區(qū)按其物理地址遞增的次序排列。在為作業(yè)分配存儲空間時，從低址空閑區(qū)開始查找,直到找到第一個能滿足要求的空閑區(qū)后，從中劃出與請求的大小相等的存儲空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑鏈中；優(yōu)先利用內存中低址部分的空閑分區(qū)，保留了高址部分的大空閑區(qū)；低址部分不斷被分割，形成很多難以利用的碎片。,4.2

30、 連續(xù)分配方式,動態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法首次適應算法（First Fit）把主存中所有空閑區(qū)按其物理地址遞增的次序排列。在為作業(yè)分配存儲空間時，從低址空閑區(qū)開始查找,直到找到第一個能滿足要求的空閑區(qū)后，從中劃出與請求的大小相等的存儲空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑鏈中；優(yōu)先利用內存中低址部分的空閑分區(qū)，保留了高址部分的大空閑區(qū)；低址部分不斷被分割，形成很多難以利用的碎片。,4.2 連續(xù)分配方式,動態(tài)分

31、區(qū)分配（可變分區(qū)分配）分區(qū)分配算法首次適應算法（First Fit）把主存中所有空閑區(qū)按其物理地址遞增的次序排列。在為作業(yè)分配存儲空間時，從低址空閑區(qū)開始查找,直到找到第一個能滿足要求的空閑區(qū)后，從中劃出與請求的大小相等的存儲空間分配給作業(yè)，余下的空閑區(qū)仍留在空閑鏈中；優(yōu)先利用內存中低址部分的空閑分區(qū)，保留了高址部分的大空閑區(qū)；低址部分不斷被分割，形成很多難以利用的碎片。,4.2 連續(xù)分配方式,動態(tài)分區(qū)分配（可變分區(qū)分配）

32、分區(qū)分配算法循環(huán)首次適應算法該算法是首次適應算法的變形，在為作業(yè)分配存儲空間時，是從上次所分配的空閑區(qū)的下一個空閑區(qū)開始查找，直到找到第一個能滿足要求的空閑區(qū)，從中劃出一塊與請求的大小相等的 一塊存儲區(qū)分配給作業(yè)。若到最后一個空閑區(qū)的大小仍不能滿足要求時，應再從第一個空閑區(qū)開始查找；需設置查詢指針；使空閑分區(qū)分布均勻，但是缺乏大的空閑區(qū)；,4.2 連續(xù)分配方式,動態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法循環(huán)首次適應算法該

33、算法是首次適應算法的變形，在為作業(yè)分配存儲空間時，是從上次所分配的空閑區(qū)的下一個空閑區(qū)開始查找，直到找到第一個能滿足要求的空閑區(qū)，從中劃出一塊與請求的大小相等的 一塊存儲區(qū)分配給作業(yè)。若到最后一個空閑區(qū)的大小仍不能滿足要求時，應再從第一個空閑區(qū)開始查找；需設置查詢指針；使空閑分區(qū)分布均勻，但是缺乏大的空閑區(qū)；,4.2 連續(xù)分配方式,動態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法循環(huán)首次適應算法該算法是首次適應算法的變形，在為作業(yè)分

34、配存儲空間時，是從上次所分配的空閑區(qū)的下一個空閑區(qū)開始查找，直到找到第一個能滿足要求的空閑區(qū)，從中劃出一塊與請求的大小相等的 一塊存儲區(qū)分配給作業(yè)。若到最后一個空閑區(qū)的大小仍不能滿足要求時，應再從第一個空閑區(qū)開始查找；需設置查詢指針；使空閑分區(qū)分布均勻，但是缺乏大的空閑區(qū)；,4.2 連續(xù)分配方式,動態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法最佳適應算法“最佳”的含義是指每次為作業(yè)分配主存時，總是把既能滿足要求，又是最小的空閑區(qū)分

35、配給作業(yè)，以免由于“大材小用”而浪費主存。為了加速查找，該算法要求將所有的空閑區(qū)按其大小遞增次序排列；第一個找到能滿足要求的空閑區(qū)一定使最佳的；每次分割的剩余部分都是最小的，因此在存儲器中會留下很多難以利用的小碎片,4.2 連續(xù)分配方式,動態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配算法最佳適應算法“最佳”的含義是指每次為作業(yè)分配主存時，總是把既能滿足要求，又是最小的空閑區(qū)分配給作業(yè)，以免由于“大材小用”而浪費主存。為了加速查找，該算法

36、要求將所有的空閑區(qū)按其大小遞增次序排列；第一個找到能滿足要求的空閑區(qū)一定使最佳的；每次分割的剩余部分都是最小的，因此在存儲器中會留下很多難以利用的小碎片,4.2 連續(xù)分配方式,動態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配操作分配內存 系統(tǒng)利用某種分配算法，從空閑分區(qū)表（鏈）中找到所需大小的分區(qū)。 分配流程見下圖。,4.2 連續(xù)分配方式,動態(tài)分區(qū)分配（可變分區(qū)分配）分區(qū)分配操作回收內存 系統(tǒng)根據(jù)回收區(qū)的首地址，從空

37、閑區(qū)鏈中找到插入點后，會有四種情況出現(xiàn)：（1）回收區(qū)前是空閑分區(qū)（2）回收區(qū)后是空閑分區(qū)（3）回收區(qū)前、后都是空閑分區(qū)（4）回收區(qū)前、后都不是空閑分區(qū),4.2 連續(xù)分配方式,可重定位分區(qū)分配動態(tài)重定位的引入碎片問題 經過一段時間的分配回收后，內存中存在很多很小的空閑塊。它們每一個都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為“碎片”或“零頭”。碎片問題的解決——“拼接”或“緊湊” 移動內存

38、中作業(yè)的位置，以把原來多個分散的小分區(qū)拼接成一個大分區(qū),4.2 連續(xù)分配方式,可重定位分區(qū)分配動態(tài)重定位的引入碎片問題 經過一段時間的分配回收后，內存中存在很多很小的空閑塊。它們每一個都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為“碎片”或“零頭”。碎片問題的解決——“拼接”或“緊湊” 移動內存中作業(yè)的位置，以把原來多個分散的小分區(qū)拼接成一個大分區(qū)。,4.2 連續(xù)分配方式,可重定位分區(qū)分配動態(tài)

39、重定位的實現(xiàn)每次“緊湊”后必須對移動了的程序或數(shù)據(jù)進行重定位地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問自動進行的，稱為動態(tài)重定位。硬件地址變換機構的支持——重定位寄存器內存地址＝相對地址＋重定位寄存器中的地址移動程序時只需修改重定位寄存器中的地址,4.2 連續(xù)分配方式,可重定位分區(qū)分配動態(tài)重定位的實現(xiàn)每次“緊湊”后必須對移動了的程序或數(shù)據(jù)進行重定位地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問自

40、動進行的，稱為動態(tài)重定位。硬件地址變換機構的支持——重定位寄存器內存地址＝相對地址＋重定位寄存器中的地址移動程序時只需修改重定位寄存器中的地址,4.2 連續(xù)分配方式,可重定位分區(qū)分配動態(tài)重定位的實現(xiàn)每次“緊湊”后必須對移動了的程序或數(shù)據(jù)進行重定位地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問自動進行的，稱為動態(tài)重定位。硬件地址變換機構的支持——重定位寄存器內存地址＝相對地址＋重定位寄存器中的地址移動程序時只

41、需修改重定位寄存器中的地址,4.2 連續(xù)分配方式,可重定位分區(qū)分配動態(tài)重定位的實現(xiàn)每次“緊湊”后必須對移動了的程序或數(shù)據(jù)進行重定位地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問自動進行的，稱為動態(tài)重定位。硬件地址變換機構的支持——重定位寄存器內存地址＝相對地址＋重定位寄存器中的地址移動程序時只需修改重定位寄存器中的地址,4.2 連續(xù)分配方式,可重定位分區(qū)分配動態(tài)重定位的實現(xiàn)每次“緊湊”后必須對移動了的程序或

42、數(shù)據(jù)進行重定位地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問自動進行的，稱為動態(tài)重定位。硬件地址變換機構的支持——重定位寄存器內存地址＝相對地址＋重定位寄存器中的地址移動程序時只需修改重定位寄存器中的地址,4.2 連續(xù)分配方式,可重定位分區(qū)分配動態(tài)重定位分區(qū)分配算法 與動態(tài)分區(qū)分配算法基本相同，增加了緊湊的功能。見下圖。,4.2 連續(xù)分配方式,對換(Swapping)對換的引入所謂“對換”， 是

43、指把內存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)，調出到外存上，以便騰出足夠的內存空間，再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)，調入內存。對換分類整體對換、進程對換部分對換：頁面對換、分段對換,4.2 連續(xù)分配方式,對換(Swapping)對換的引入所謂“對換”， 是指把內存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)，調出到外存上，以便騰出足夠的內存空間，再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)，調入

44、內存。對換分類整體對換、進程對換部分對換：頁面對換、分段對換,4.2 連續(xù)分配方式,對換(Swapping)OS必須實現(xiàn)三方面的功能：對換空間的管理、進程的換出、進程的換入對換空間的管理連續(xù)分配方式空閑分區(qū)表或空閑分區(qū)鏈對換空間的分配與回收，與動態(tài)分區(qū)方式時的內存分配與回收方法雷同,4.2 連續(xù)分配方式,對換(Swapping)OS必須實現(xiàn)三方面的功能：對換空間的管理、進程的換出、進程的換入對換空間的管理連

45、續(xù)分配方式空閑分區(qū)表或空閑分區(qū)鏈對換空間的分配與回收，與動態(tài)分區(qū)方式時的內存分配與回收方法雷同,4.2 連續(xù)分配方式,對換(Swapping)進程的換出與換入換出過程選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，換出后收回內存空間，修改進程的PCB相關信息換入過程找出“就緒”狀態(tài)并已經換出的進程，將其中換出時間最久的進程作為換入進程，將其換入直到已無可換入的進程和無可換出的進程,4.2 連續(xù)分配方式,對換(Sw

46、apping)進程的換出與換入換出過程選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，換出后收回內存空間，修改進程的PCB相關信息換入過程找出“就緒”狀態(tài)并已經換出的進程，將其中換出時間最久的進程作為換入進程，將其換入直到已無可換入的進程和無可換出的進程,4.2 連續(xù)分配方式,對換(Swapping)進程的換出與換入換出過程選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，換出后收回內存空間，修改進程的PCB相關

47、信息換入過程找出“就緒”狀態(tài)并已經換出的進程，將其中換出時間最久的進程作為換入進程，將其換入直到已無可換入的進程和無可換出的進程,4.3 基本分頁存儲管理方式,連續(xù)分配方式的缺點：形成許多“碎片”；“緊湊”開銷大。離散分配方式：無須“緊湊”，將一個用戶程序離散地分配到內存中的多個不相連接的區(qū)域中。分頁存儲管理方式－離散的基本單位是“頁”分段存儲管理方式－離散的基本單位是“段”段頁式存儲管理方式在分頁存儲管理方式中，如

48、果不具備頁面對換功能，就是基本分頁存儲管理方式，即不支持虛擬存儲器的功能,4.3 基本分頁存儲管理方式,連續(xù)分配方式的缺點：形成許多“碎片”；“緊湊”開銷大。離散分配方式：無須“緊湊”，將一個用戶程序離散地分配到內存中的多個不相連接的區(qū)域中。分頁存儲管理方式－離散的基本單位是“頁”分段存儲管理方式－離散的基本單位是“段”段頁式存儲管理方式在分頁存儲管理方式中，如果不具備頁面對換功能，就是基本分頁存儲管理方式，即不支持虛擬存儲

49、器的功能,4.3 基本分頁存儲管理方式,連續(xù)分配方式的缺點：形成許多“碎片”；“緊湊”開銷大。離散分配方式：無須“緊湊”，將一個用戶程序離散地分配到內存中的多個不相連接的區(qū)域中。分頁存儲管理方式－離散的基本單位是“頁”分段存儲管理方式－離散的基本單位是“段”段頁式存儲管理方式在分頁存儲管理方式中，如果不具備頁面對換功能，就是基本分頁存儲管理方式，即不支持虛擬存儲器的功能,4.3 基本分頁存儲管理方式,頁面與頁表頁面頁面

50、和物理塊頁（頁面）——把每個作業(yè)(進程)邏輯地址空間劃分成若干大小相等的片.第0頁、第1頁 (物理)塊或頁框(frame)——把內存空間分成與頁面相同大小的若干個存儲塊。 0＃塊、1＃塊 頁內碎片——由于進程的最后一頁經常裝不滿一塊而形成了不可利用的碎片。,4.3 基本分頁存儲管理方式,頁面與頁表頁面頁面大小太小，可使內存碎片減小，有利于提高內存利用率；會使每個進程占用較多的頁面，從而導致進程的頁表過長，占用大量

51、內存； 此外，還會降低頁面換進換出的效率。較大，可以減少頁表的長度，提高頁面換進換出的速度，但卻又會使頁內碎片增大。頁面的大小應選擇得適中，且頁面大小應是2的冪，通常為512 B~8 KB。,4.3 基本分頁存儲管理方式,頁面與頁表地址結構,31,12,11,0,220＝1M(頁)每頁大小為：212＝4KB,4.3 基本分頁存儲管理方式,頁面與頁表地址結構,對某特定機器，其地址結構是一定的。地址為A，頁面的大小為L，則頁號

52、P和頁內地址d可按下式求得：,例：系統(tǒng)頁面大小為１KB，設A＝2170B，則P=2,d=122,4.3 基本分頁存儲管理方式,頁面與頁表頁表（頁面映象表）頁表的作用是實現(xiàn)從頁號到物理塊號的地址映射由頁號和塊號組成，指出邏輯地址中頁號與主存中物理塊號的對應關系 頁號---作業(yè)地址空間的頁序號 塊號---內存空間的頁面序號,頁表的作用,4.3 基本分頁存儲管理方式,地址變換機構借助于頁表，實現(xiàn)從邏輯地址到

53、物理地址的轉換基本的地址變換機構頁表駐留在內存中進程未執(zhí)行時，頁表的始址和頁表長度存放在PCB中進程執(zhí)行時，頁表的始址和頁表長度裝入頁表寄存器,圖 4-12 分頁系統(tǒng)的地址變換機構,例：一個三頁長的進程，每頁長1K。 頁號頁框號（塊號）              

54、 0   2               1 3                2 8

55、 指令：100 LOAD 1，2500的地址變換過程為：根據(jù)控制寄存器找到頁表的始址和長度，該指令地址=2*1024+100 = 2148執(zhí)行： 2500 = 2048+452 P=2 W=452 B= 82500單元的物理地址=1024*8+452 = 8644,4.3 基本分頁存儲管理方式,地址變換機構具有快表的地址變換機構頁表駐留在內存中的缺點：每存取一個數(shù)據(jù)都要兩次訪問內存。聯(lián)想

56、寄存器（快表）：存放當前訪問的若干個頁表項具有快表的地址變換機構見下圖。,4.3 基本分頁存儲管理方式,二級頁表CPU具有32位地址時 ,使用232邏輯地址空間的分頁系統(tǒng),規(guī)定頁面4KB時,每個進程頁表的表項有1M(220)個,若表項占用1個字節(jié),則每個進程需要占用1MB連續(xù)內存空間存放頁表解決辦法：把將頁表進行分頁,分成一張張小頁表(稱為頁表頁) ,小頁表的大小與頁框相同，為進行索引查找,應該為這些小頁表建一張頁目錄表為離散

57、分配的頁表再建一張頁表，稱為：外層頁表或頁目錄表,4.3 基本分頁存儲管理方式,二級頁表,邏輯地址結構可描述如下：,外層頁表頁表,,兩級頁表,,1011,,1078,,0,1,2,,,1742,n,第,0,頁頁表,,1,,4,,6,,…,,0,1,2,…,1023,第,1,頁頁表,,114,,115,,,0,1,…,1023,外部頁表,,,,,,,,,0,1,2,3,4,5,6,7,,…,,,,,,…,114,115,1468,,,

58、,,,第,n,頁頁表,,1468,,,,,0,1,2,…,1023,,,,,,,,,,,,,,內存空間,兩級頁表結構,具有兩級頁表的地址變換機構,外部頁號,,P,1,,P,2,外部頁內地址,頁內地址,,d,邏輯地址,,＋,,,,外部頁表寄存器,,,,,外部頁表,,＋,,,,,,,,,,,d,,b,頁表,頁表,物理地址,,,,,,…,,,,,,,,…,,二級頁表地址變換需三次訪問主存：一次訪問頁目錄、一次訪問頁表頁、一次訪問指令或數(shù)據(jù)，訪