第二節(jié)存儲管理

1、第第二二節(jié)節(jié) 存儲器管理存儲器管理 2.1 2.1 存儲管理的功能存儲管理的功能 2.2 2.2 實(shí)存管理實(shí)存管理 2.3 2.3 虛擬存儲器管理虛擬存儲器管理 2.4 2.4 碎片與抖動問題碎片與抖動問題 本節(jié)的主要內(nèi)容如下：本節(jié)的主要內(nèi)容如下：(1)存儲管理的有關(guān)概念。存儲管理的有關(guān)概念。 (2)實(shí)存管理中講述了固定分區(qū)存儲管理、可變式實(shí)存管理中講述了固定分區(qū)存儲管理、可變式分區(qū)存儲管理、純分頁存儲管理三種存儲管理方分區(qū)存儲管理、純分頁存儲管理三種存儲管理方案的實(shí)現(xiàn)原理案的實(shí)現(xiàn)原理(3)虛存管理以請求式分頁存儲管理為重點(diǎn)虛存管理以請求式分頁存儲管理為重點(diǎn) (4)總結(jié)各種存儲管理方案中存在的

2、碎片和抖動問總結(jié)各種存儲管理方案中存在的碎片和抖動問題及解決方法題及解決方法圖圖2.1 多級存儲器體系示意圖多級存儲器體系示意圖2.1 存儲管理的功能存儲管理的功能 2.1.1 內(nèi)存的分配與回收內(nèi)存的分配與回收 2.1.2 地址重定位地址重定位2.1.3 存儲保護(hù)存儲保護(hù) 2.1.4 虛擬存儲器虛擬存儲器 2.1.1 內(nèi)存的分配與回收內(nèi)存的分配與回收 內(nèi)存分配按分配時(shí)機(jī)的不同，可分為兩種方式。內(nèi)存分配按分配時(shí)機(jī)的不同，可分為兩種方式。（1）靜態(tài)存儲分配：指內(nèi)存分配是在作業(yè)運(yùn)行之前各目）靜態(tài)存儲分配：指內(nèi)存分配是在作業(yè)運(yùn)行之前各目標(biāo)模塊連接后，把整個(gè)作業(yè)一次性全部裝入內(nèi)存，并在標(biāo)模塊連接后，把整

3、個(gè)作業(yè)一次性全部裝入內(nèi)存，并在作業(yè)的整個(gè)運(yùn)行過程中，不允許作業(yè)再申請其他內(nèi)存，作業(yè)的整個(gè)運(yùn)行過程中，不允許作業(yè)再申請其他內(nèi)存，或在內(nèi)存中移動位置。也就是說，內(nèi)存分配是在作業(yè)運(yùn)或在內(nèi)存中移動位置。也就是說，內(nèi)存分配是在作業(yè)運(yùn)行前一次性完成的。行前一次性完成的。（2）動態(tài)存儲分配：作業(yè)要求的基本內(nèi)存空間是在目標(biāo)）動態(tài)存儲分配：作業(yè)要求的基本內(nèi)存空間是在目標(biāo)模塊裝入內(nèi)存時(shí)分配的，但在作業(yè)運(yùn)行過程中，允許作模塊裝入內(nèi)存時(shí)分配的，但在作業(yè)運(yùn)行過程中，允許作業(yè)申請附加的內(nèi)存空間，或是在內(nèi)存中移動，即分配工業(yè)申請附加的內(nèi)存空間，或是在內(nèi)存中移動，即分配工作可以在作業(yè)運(yùn)行前及運(yùn)行過程中逐步完成。作可以在作業(yè)運(yùn)

4、行前及運(yùn)行過程中逐步完成。2.1.2 地址重定位地址重定位 1內(nèi)存空間（或物理空間）內(nèi)存空間（或物理空間）2邏輯空間邏輯空間3地址重定位地址重定位1內(nèi)存空間（或物理空間）內(nèi)存是由若干個(gè)存儲單元組成的，每個(gè)存儲單元內(nèi)存是由若干個(gè)存儲單元組成的，每個(gè)存儲單元有一個(gè)編號，這種編號可唯一標(biāo)識一個(gè)存儲單元，有一個(gè)編號，這種編號可唯一標(biāo)識一個(gè)存儲單元，稱為內(nèi)存地址（或物理地址）。稱為內(nèi)存地址（或物理地址）。2邏輯空間源程序經(jīng)過匯編或編譯后，形成目標(biāo)程序，每個(gè)源程序經(jīng)過匯編或編譯后，形成目標(biāo)程序，每個(gè)目標(biāo)程序都是以目標(biāo)程序都是以0為基址順序進(jìn)行編址的，原來為基址順序進(jìn)行編址的，原來用符號名訪問的單元用具體的

5、數(shù)據(jù)用符號名訪問的單元用具體的數(shù)據(jù)單元號取單元號取代。這樣生成的目標(biāo)程序占據(jù)一定的地址空間，代。這樣生成的目標(biāo)程序占據(jù)一定的地址空間，稱為作業(yè)的邏輯地址空間，簡稱邏輯空間。在邏稱為作業(yè)的邏輯地址空間，簡稱邏輯空間。在邏輯空間中每條指令的地址和指令中要訪問的操作輯空間中每條指令的地址和指令中要訪問的操作數(shù)地址統(tǒng)稱為邏輯地址。數(shù)地址統(tǒng)稱為邏輯地址。圖圖2.2 作業(yè)的名空間、邏輯地址空間和裝入后的物理空間作業(yè)的名空間、邏輯地址空間和裝入后的物理空間3地址重定位(1)靜態(tài)地址重定位靜態(tài)地址重定位靜態(tài)地址重定位是在程序執(zhí)行之前由操作系統(tǒng)的靜態(tài)地址重定位是在程序執(zhí)行之前由操作系統(tǒng)的重定位裝入程序完成的。重

6、定位裝入程序完成的。 (2)動態(tài)地址重定位動態(tài)地址重定位 動態(tài)地址重定位是在程序執(zhí)行期間進(jìn)行的。動態(tài)地址重定位是在程序執(zhí)行期間進(jìn)行的。 （b）采用動態(tài)重定位時(shí)內(nèi)存空間及地址重定位示意圖 （a）采用靜態(tài)重定位后的內(nèi)存空間 圖圖2.3 靜態(tài)地址重定位和動態(tài)地址重定位示意圖靜態(tài)地址重定位和動態(tài)地址重定位示意圖2.1.3 存儲保護(hù)存儲保護(hù) （1）上、下界存儲保護(hù)：上、下界保護(hù)是一種）上、下界存儲保護(hù)：上、下界保護(hù)是一種簡單的存儲保護(hù)技術(shù)。系統(tǒng)可為每個(gè)作業(yè)設(shè)置一簡單的存儲保護(hù)技術(shù)。系統(tǒng)可為每個(gè)作業(yè)設(shè)置一對上、下界寄存器，分別用來存放當(dāng)前運(yùn)行作業(yè)對上、下界寄存器，分別用來存放當(dāng)前運(yùn)行作業(yè)在內(nèi)存空間的上、下

7、邊界地址，用它們來限制用在內(nèi)存空間的上、下邊界地址，用它們來限制用戶程序的活動范圍。戶程序的活動范圍。 （2）基址）基址限長存儲保護(hù)：上、下界保護(hù)的一限長存儲保護(hù)：上、下界保護(hù)的一個(gè)變種是采用基址個(gè)變種是采用基址限長存儲保護(hù)。限長存儲保護(hù)。 圖圖2.4 界限寄存器的兩種存儲保護(hù)方式界限寄存器的兩種存儲保護(hù)方式2.1.4 虛擬存儲器虛擬存儲器 對內(nèi)存進(jìn)行邏輯上的擴(kuò)充，現(xiàn)在普遍采用虛擬存儲對內(nèi)存進(jìn)行邏輯上的擴(kuò)充，現(xiàn)在普遍采用虛擬存儲管理技術(shù)。管理技術(shù)。 虛擬存儲技術(shù)的基本思想是把有限的內(nèi)存空間與大虛擬存儲技術(shù)的基本思想是把有限的內(nèi)存空間與大容量的外存統(tǒng)一管理起來，構(gòu)成一個(gè)遠(yuǎn)大于實(shí)際內(nèi)存的、容量的外

8、存統(tǒng)一管理起來，構(gòu)成一個(gè)遠(yuǎn)大于實(shí)際內(nèi)存的、虛擬的存儲器。此時(shí)，外存是作為內(nèi)存的直接延伸，用虛擬的存儲器。此時(shí)，外存是作為內(nèi)存的直接延伸，用戶并不會感覺到內(nèi)、外存的區(qū)別，即把兩級存儲器當(dāng)作戶并不會感覺到內(nèi)、外存的區(qū)別，即把兩級存儲器當(dāng)作一級存儲器來看待。一個(gè)作業(yè)運(yùn)行時(shí)，其全部信息裝入一級存儲器來看待。一個(gè)作業(yè)運(yùn)行時(shí)，其全部信息裝入虛存，實(shí)際上可能只有當(dāng)前運(yùn)行的必需一部分信息存入虛存，實(shí)際上可能只有當(dāng)前運(yùn)行的必需一部分信息存入內(nèi)存，其他則存于外存，當(dāng)所訪問的信息不在內(nèi)存時(shí)，內(nèi)存，其他則存于外存，當(dāng)所訪問的信息不在內(nèi)存時(shí)，系統(tǒng)自動將其從外存調(diào)入內(nèi)存。系統(tǒng)自動將其從外存調(diào)入內(nèi)存。 2.2 實(shí)存管理實(shí)存

9、管理 2.2.1 單一連續(xù)分配單一連續(xù)分配2.2.2 固定分區(qū)存儲管理固定分區(qū)存儲管理 2.2.3 可變式分區(qū)存儲管理可變式分區(qū)存儲管理2.2.4 可重位分區(qū)分配可重位分區(qū)分配 2.2.5 覆蓋技術(shù)覆蓋技術(shù)2.2.6 交換技術(shù)交換技術(shù)2.2.1 單一連續(xù)分配單一連續(xù)分配操作系統(tǒng)區(qū)用戶區(qū)圖圖2.52.2.2 固定分區(qū)存儲管理固定分區(qū)存儲管理 固定分區(qū)存儲管理是實(shí)現(xiàn)多道程序設(shè)計(jì)的最簡單固定分區(qū)存儲管理是實(shí)現(xiàn)多道程序設(shè)計(jì)的最簡單的一種存儲管理技術(shù)。其基本思想是，在作業(yè)未的一種存儲管理技術(shù)。其基本思想是，在作業(yè)未進(jìn)入內(nèi)存之前，就由操作員或操作系統(tǒng)把內(nèi)存可進(jìn)入內(nèi)存之前，就由操作員或操作系統(tǒng)把內(nèi)存可用空間

10、劃分成若干個(gè)固定大小的存儲區(qū)，除操作用空間劃分成若干個(gè)固定大小的存儲區(qū)，除操作系統(tǒng)占用一個(gè)區(qū)域外，其余區(qū)域?yàn)橄到y(tǒng)中多個(gè)用系統(tǒng)占用一個(gè)區(qū)域外，其余區(qū)域?yàn)橄到y(tǒng)中多個(gè)用戶共享，因?yàn)樵谙到y(tǒng)運(yùn)行期間，分區(qū)大小、數(shù)目戶共享，因?yàn)樵谙到y(tǒng)運(yùn)行期間，分區(qū)大小、數(shù)目都不變，所以固定式分區(qū)也稱為靜態(tài)分區(qū)。都不變，所以固定式分區(qū)也稱為靜態(tài)分區(qū)。圖圖2.6 固定式分區(qū)內(nèi)存分配示意圖（固定式分區(qū)內(nèi)存分配示意圖（a）和（）和（b）固定式分區(qū)說明表固定式分區(qū)說明表2.2.3 可變式分區(qū)存儲管理可變式分區(qū)存儲管理 1空閑分區(qū)的組織形式空閑分區(qū)的組織形式 2內(nèi)存的分配與回收內(nèi)存的分配與回收 3常用的分配算法常用的分配算法 4可變

11、式分區(qū)的地址重定位可變式分區(qū)的地址重定位 圖圖2.7 可變式分區(qū)內(nèi)存使用情況示意圖可變式分區(qū)內(nèi)存使用情況示意圖1空閑分區(qū)的組織形式空閑分區(qū)的組織形式 空閑分區(qū)鏈表的組織是這樣的：在每個(gè)空閑分區(qū)空閑分區(qū)鏈表的組織是這樣的：在每個(gè)空閑分區(qū)的起始部分開辟出一個(gè)單元，存放一個(gè)鏈表指針的起始部分開辟出一個(gè)單元，存放一個(gè)鏈表指針和該分區(qū)的大小，鏈表指針指向下一個(gè)空閑分區(qū)。和該分區(qū)的大小，鏈表指針指向下一個(gè)空閑分區(qū)。系統(tǒng)中用一個(gè)固定單元作為空閑分區(qū)鏈表的鏈表系統(tǒng)中用一個(gè)固定單元作為空閑分區(qū)鏈表的鏈表頭指針，指向第一塊空閑分區(qū)首地址，最后一塊頭指針，指向第一塊空閑分區(qū)首地址，最后一塊空閑分區(qū)的鏈表指針存放鏈尾

12、標(biāo)志?？臻e分區(qū)的鏈表指針存放鏈尾標(biāo)志。2內(nèi)存的分配與回收內(nèi)存的分配與回收 當(dāng)某一個(gè)用戶作業(yè)完成釋放所占分區(qū)時(shí)，系統(tǒng)應(yīng)當(dāng)某一個(gè)用戶作業(yè)完成釋放所占分區(qū)時(shí)，系統(tǒng)應(yīng)進(jìn)行回收。在可變式分區(qū)中，應(yīng)該檢查回收區(qū)與進(jìn)行回收。在可變式分區(qū)中，應(yīng)該檢查回收區(qū)與內(nèi)存中前后空閑區(qū)是否相鄰，若相鄰，則應(yīng)進(jìn)行內(nèi)存中前后空閑區(qū)是否相鄰，若相鄰，則應(yīng)進(jìn)行合并，形成一個(gè)較大的空閑區(qū)，并對相應(yīng)的鏈表合并，形成一個(gè)較大的空閑區(qū)，并對相應(yīng)的鏈表指針進(jìn)行修改；若不相鄰，應(yīng)將空閑區(qū)插入到空指針進(jìn)行修改；若不相鄰，應(yīng)將空閑區(qū)插入到空閑區(qū)鏈表的適當(dāng)位置。閑區(qū)鏈表的適當(dāng)位置。 圖圖2.8 首次適應(yīng)算法的空閑分區(qū)鏈表組織形式首次適應(yīng)算法的空閑

13、分區(qū)鏈表組織形式3常用的分配算法常用的分配算法 （1）首次適應(yīng)算法）首次適應(yīng)算法 （2）最佳適應(yīng)算法）最佳適應(yīng)算法 （3）最差適應(yīng)算法）最差適應(yīng)算法 圖圖2.9 最佳適應(yīng)算法的空閑分區(qū)鏈表組織形式最佳適應(yīng)算法的空閑分區(qū)鏈表組織形式圖圖2.10 最差適應(yīng)算法的空閑分區(qū)鏈表組織形式最差適應(yīng)算法的空閑分區(qū)鏈表組織形式圖圖2.11 內(nèi)存使用情況內(nèi)存使用情況 圖圖2.12 用三種適應(yīng)算法處理同一作業(yè)序列用三種適應(yīng)算法處理同一作業(yè)序列2.2.4 可重定位分區(qū)分配可重定位分區(qū)分配 可重定位可采用靜態(tài)重定位，也可采用動態(tài)重定位。如可重定位可采用靜態(tài)重定位，也可采用動態(tài)重定位。如采用靜態(tài)重定位，因用戶作業(yè)進(jìn)入內(nèi)

14、存后，程序的邏輯采用靜態(tài)重定位，因用戶作業(yè)進(jìn)入內(nèi)存后，程序的邏輯地址實(shí)現(xiàn)了重定位，不能在內(nèi)存中再進(jìn)行移動，經(jīng)過一地址實(shí)現(xiàn)了重定位，不能在內(nèi)存中再進(jìn)行移動，經(jīng)過一段時(shí)間的運(yùn)行，內(nèi)存中不能再分配利用的小碎片會越來段時(shí)間的運(yùn)行，內(nèi)存中不能再分配利用的小碎片會越來越多。有時(shí)可能會出現(xiàn)這種情況，即當(dāng)一個(gè)作業(yè)申請一越多。有時(shí)可能會出現(xiàn)這種情況，即當(dāng)一個(gè)作業(yè)申請一定數(shù)量的內(nèi)存時(shí)，雖然此時(shí)空閑區(qū)的總和大于新作業(yè)的定數(shù)量的內(nèi)存時(shí)，雖然此時(shí)空閑區(qū)的總和大于新作業(yè)的內(nèi)存要求，但卻沒有單個(gè)的空閑區(qū)足以裝下該作業(yè)。內(nèi)存要求，但卻沒有單個(gè)的空閑區(qū)足以裝下該作業(yè)。采用動態(tài)重定位的可變式分區(qū)管理技術(shù)，在執(zhí)行內(nèi)存分采用動態(tài)重定

15、位的可變式分區(qū)管理技術(shù)，在執(zhí)行內(nèi)存分配時(shí)，如無足夠大空閑塊，應(yīng)考慮實(shí)現(xiàn)緊湊操作。其分配時(shí)，如無足夠大空閑塊，應(yīng)考慮實(shí)現(xiàn)緊湊操作。其分配算法如圖配算法如圖2.13所示所示 。 圖圖2.13 采用動態(tài)重定位的分配算法采用動態(tài)重定位的分配算法2.2.5 覆蓋技術(shù)覆蓋技術(shù) 當(dāng)用戶作業(yè)大于地址空間大于主存可用空間時(shí)，當(dāng)用戶作業(yè)大于地址空間大于主存可用空間時(shí)，該作業(yè)就無法運(yùn)行，這樣限制了大程序的運(yùn)行。該作業(yè)就無法運(yùn)行，這樣限制了大程序的運(yùn)行。但我們知道一個(gè)大程序往往有多個(gè)模塊構(gòu)成，而但我們知道一個(gè)大程序往往有多個(gè)模塊構(gòu)成，而且不每時(shí)每刻都要在內(nèi)存中，這樣幾個(gè)模塊在不且不每時(shí)每刻都要在內(nèi)存中，這樣幾個(gè)模塊在

16、不同時(shí)間內(nèi)裝入內(nèi)存時(shí)可以用同一塊內(nèi)容，即可以同時(shí)間內(nèi)裝入內(nèi)存時(shí)可以用同一塊內(nèi)容，即可以進(jìn)行覆蓋運(yùn)行。具體情況如圖進(jìn)行覆蓋運(yùn)行。具體情況如圖2.14A(20KB)B(50KB)C(20KB)D(40KB)E(20KB)F(20KB)20KB50KB40KB圖 2.14原來需170K，現(xiàn)在需要110KB2.2.5 交換技術(shù)交換技術(shù) 交換技術(shù)同樣是解決內(nèi)存不足問題。在分時(shí)、交換技術(shù)同樣是解決內(nèi)存不足問題。在分時(shí)、實(shí)時(shí)系統(tǒng)及批處理系統(tǒng)中均有應(yīng)用。實(shí)時(shí)系統(tǒng)及批處理系統(tǒng)中均有應(yīng)用。 它的基本思想是：只允許一個(gè)或幾個(gè)用戶作它的基本思想是：只允許一個(gè)或幾個(gè)用戶作業(yè)保留在內(nèi)存中。當(dāng)內(nèi)存不夠時(shí)，以整個(gè)作業(yè)為業(yè)保留

17、在內(nèi)存中。當(dāng)內(nèi)存不夠時(shí)，以整個(gè)作業(yè)為單位進(jìn)行內(nèi)外存交換。單位進(jìn)行內(nèi)外存交換。 * 缺點(diǎn)是作業(yè)較大時(shí)花費(fèi)的代價(jià)較大。缺點(diǎn)是作業(yè)較大時(shí)花費(fèi)的代價(jià)較大。2.3 虛擬存儲器管理虛擬存儲器管理 2.3.1 虛擬存儲器的概念虛擬存儲器的概念 2.3.2 分頁存儲管理與動態(tài)地址重定位分頁存儲管理與動態(tài)地址重定位 2.3.3 現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動態(tài)地址重定位現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動態(tài)地址重定位 2.3.4 頁面置換算法頁面置換算法 2.3.5 請求式分頁存儲管理性能分析舉例請求式分頁存儲管理性能分析舉例 2.3.6 請求式分段存儲管理請求式分段存儲管理 2.3.1 虛擬存儲器的概念虛擬存儲器的概念 （1）程序

18、中往往會有一些彼此互斥的部分。）程序中往往會有一些彼此互斥的部分。 （2）在一個(gè)完整的程序中，會有一些諸如出錯(cuò)處理這樣）在一個(gè)完整的程序中，會有一些諸如出錯(cuò)處理這樣的子程序，在作業(yè)正常運(yùn)行情況下不會執(zhí)行這些程序，的子程序，在作業(yè)正常運(yùn)行情況下不會執(zhí)行這些程序，沒有必要把它們調(diào)入內(nèi)存。沒有必要把它們調(diào)入內(nèi)存?；诔绦蚓植啃栽砗蜕鲜銮闆r，就沒有必要把一個(gè)作基于程序局部性原理和上述情況，就沒有必要把一個(gè)作業(yè)一次性全部裝入內(nèi)存再開始運(yùn)行。而是可以把程序當(dāng)業(yè)一次性全部裝入內(nèi)存再開始運(yùn)行。而是可以把程序當(dāng)前執(zhí)行所涉及的信息放入內(nèi)存中，其余部分可根據(jù)需要前執(zhí)行所涉及的信息放入內(nèi)存中，其余部分可根據(jù)需要臨時(shí)

19、調(diào)入，由操作系統(tǒng)和硬件相配合來完成主存和輔存臨時(shí)調(diào)入，由操作系統(tǒng)和硬件相配合來完成主存和輔存之間信息的動態(tài)調(diào)度。這樣的計(jì)算機(jī)系統(tǒng)好像為用戶提之間信息的動態(tài)調(diào)度。這樣的計(jì)算機(jī)系統(tǒng)好像為用戶提供了一個(gè)存儲容量比實(shí)際主存大得多的存儲器，就稱為供了一個(gè)存儲容量比實(shí)際主存大得多的存儲器，就稱為虛擬存儲器。虛擬存儲器。 2.3.2 分頁存儲管理分頁存儲管理1）什么是分頁2）頁面、頁架號及其大小3）分頁系統(tǒng)中地址的構(gòu)成2-4KBp dp：頁號d：頁內(nèi)地址1、基本概念）頁表和頁表地址寄存器頁表地址寄存器n頁表頁號頁架號 狀態(tài)2分頁存儲管理的地址重定位問題分頁存儲管理的地址重定位問題 分頁存儲管理中的地址重定位

20、是非常重要的，要分頁存儲管理中的地址重定位是非常重要的，要使不連續(xù)的、分散的用戶程序能正常運(yùn)行，須采使不連續(xù)的、分散的用戶程序能正常運(yùn)行，須采用動態(tài)地址重定位。此時(shí)，可采用重定位寄存器用動態(tài)地址重定位。此時(shí)，可采用重定位寄存器方式，如分頁太多，則重定位寄存器用得太多。方式，如分頁太多，則重定位寄存器用得太多。通?？稍趦?nèi)存中為每個(gè)作業(yè)開辟一塊特定區(qū)域，通?？稍趦?nèi)存中為每個(gè)作業(yè)開辟一塊特定區(qū)域，建立起作業(yè)的邏輯頁與存儲塊之間的對應(yīng)表格關(guān)建立起作業(yè)的邏輯頁與存儲塊之間的對應(yīng)表格關(guān)系，這種表常稱為頁面映象表，簡稱頁表。系，這種表常稱為頁面映象表，簡稱頁表。 圖圖.1 分頁存儲管理示意圖分頁存儲管理示意

21、圖地址轉(zhuǎn)換過程地址轉(zhuǎn)換過程 從上面介紹的地址變換過程可以看出：如果把頁從上面介紹的地址變換過程可以看出：如果把頁表全部放在內(nèi)存，那么存取一個(gè)數(shù)據(jù)時(shí)，至少要表全部放在內(nèi)存，那么存取一個(gè)數(shù)據(jù)時(shí)，至少要訪問二次內(nèi)存。一次是訪問頁表，形成實(shí)際內(nèi)存訪問二次內(nèi)存。一次是訪問頁表，形成實(shí)際內(nèi)存地址；另一次是根據(jù)形成的內(nèi)存地址存取數(shù)據(jù)。地址；另一次是根據(jù)形成的內(nèi)存地址存取數(shù)據(jù)。顯然，這比通常執(zhí)行指令的速度要慢得多，使計(jì)顯然，這比通常執(zhí)行指令的速度要慢得多，使計(jì)算機(jī)的運(yùn)行速度幾乎降低一半。算機(jī)的運(yùn)行速度幾乎降低一半。圖圖.1 分頁存儲管理地址重定位實(shí)現(xiàn)過程分頁存儲管理地址重定位實(shí)現(xiàn)過程圖圖.1 采用快表和頁表相

22、結(jié)合的分頁地址變換過程示意圖采用快表和頁表相結(jié)合的分頁地址變換過程示意圖4存儲保護(hù)存儲保護(hù) 四種保護(hù)方式：四種保護(hù)方式：禁止做任何操作，禁止做任何操作，只能執(zhí)行，只能執(zhí)行，只能讀，只能讀，能讀能讀/寫，當(dāng)要訪問某頁時(shí)，先判斷寫，當(dāng)要訪問某頁時(shí)，先判斷該頁的存取控制和存儲保護(hù)信息是否允許。該頁的存取控制和存儲保護(hù)信息是否允許。添加了存取控制信息的頁表表目如下圖所示：添加了存取控制信息的頁表表目如下圖所示： 狀態(tài)、分頁式存儲分配方法的特點(diǎn)：、分頁式存儲分配方法的特點(diǎn)：、優(yōu)點(diǎn)：、優(yōu)點(diǎn)：）較好地解決了片問題）較好地解決了片問題）作業(yè)地址空間不受內(nèi)存的限制）作業(yè)地址空間不受內(nèi)存的限制、缺點(diǎn)：、缺點(diǎn)：）硬

23、件支持）硬件支持）要進(jìn)行頁表管理）要進(jìn)行頁表管理2.3.3 現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動態(tài)地址重定位現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動態(tài)地址重定位 （1）如何合理地組織管理相當(dāng)大的頁表？）如何合理地組織管理相當(dāng)大的頁表？在在Windows NT中，為解決第一個(gè)問題，對頁表本身進(jìn)行了改中，為解決第一個(gè)問題，對頁表本身進(jìn)行了改進(jìn)，將龐大的頁表本身也采取分頁措施，采用了兩級頁表結(jié)構(gòu)。進(jìn)，將龐大的頁表本身也采取分頁措施，采用了兩級頁表結(jié)構(gòu)。即把頁表本身按固定大小分成一個(gè)個(gè)小頁表，每個(gè)小頁表由即把頁表本身按固定大小分成一個(gè)個(gè)小頁表，每個(gè)小頁表由210=1024個(gè)頁表表目構(gòu)成，每個(gè)表目占個(gè)頁表表目構(gòu)成，每個(gè)表目占4字節(jié)，所

24、以每個(gè)小頁字節(jié)，所以每個(gè)小頁表剛好占一個(gè)頁面（頁面大小為表剛好占一個(gè)頁面（頁面大小為212=4kb）。一共有）。一共有210=1k個(gè)個(gè)小頁表。為了對這小頁表。為了對這1k個(gè)小頁表進(jìn)行管理和索引查找，設(shè)置了個(gè)小頁表進(jìn)行管理和索引查找，設(shè)置了一個(gè)頁表目錄，也稱之為頂級頁表或一級頁表，該頁目錄包含一個(gè)頁表目錄，也稱之為頂級頁表或一級頁表，該頁目錄包含有有1k個(gè)表目項(xiàng)，分別指出每個(gè)次級小頁表所在的物理塊號和個(gè)表目項(xiàng)，分別指出每個(gè)次級小頁表所在的物理塊號和其他有關(guān)狀態(tài)信息。這樣，每個(gè)作業(yè)有一個(gè)頁目錄（一級頁其他有關(guān)狀態(tài)信息。這樣，每個(gè)作業(yè)有一個(gè)頁目錄（一級頁表），它的每個(gè)表目指向一個(gè)二級頁表。頁目錄本身

25、也剛好是表），它的每個(gè)表目指向一個(gè)二級頁表。頁目錄本身也剛好是一個(gè)頁面大?。ㄒ粋€(gè)頁面大?。?10=1k，每個(gè)表目，每個(gè)表目4個(gè)字節(jié)）。個(gè)字節(jié)）。圖圖.20 Windows NT兩級頁表地址變換示意圖兩級頁表地址變換示意圖（2）面對大的頁表，地址的映射怎樣才能比較）面對大的頁表，地址的映射怎樣才能比較快地實(shí)現(xiàn)？快地實(shí)現(xiàn)？ （1）使用快表：即利用前面我們已介紹的高速）使用快表：即利用前面我們已介紹的高速緩沖存儲器來存放經(jīng)常使用的頁表表目，以提高緩沖存儲器來存放經(jīng)常使用的頁表表目，以提高頁表的查詢速度。頁表的查詢速度。（2）使用高速緩沖存儲器：在微處理器和主存）使用高速緩沖存儲器：在微處理器和主存之

26、間設(shè)置之間設(shè)置32kb或或64kb的高速緩沖存儲器，大部分的高速緩沖存儲器，大部分的指令和數(shù)據(jù)取自高速緩存（命中率為的指令和數(shù)據(jù)取自高速緩存（命中率為98%），），所以存取數(shù)據(jù)和指令速度相當(dāng)高，達(dá)到與處理器所以存取數(shù)據(jù)和指令速度相當(dāng)高，達(dá)到與處理器速度完全相匹配。速度完全相匹配。2.3.4 頁面置換算法頁面置換算法 1最優(yōu)算法（最優(yōu)算法（OPT算法）算法）2先進(jìn)先出算法（先進(jìn)先出算法（FIFO算法）算法）3最久未使用頁面置換算法（最久未使用頁面置換算法（LRU算法）算法）4LRU近似算法近似算法1最優(yōu)算法（最優(yōu)算法（OPT算法）算法）最理想的頁面置換算法是：從內(nèi)存中移出以后不最理想的頁面置換算

27、法是：從內(nèi)存中移出以后不再使用的頁面；如無這樣的頁面，則選擇以后最再使用的頁面；如無這樣的頁面，則選擇以后最長時(shí)間內(nèi)不需要訪問的頁。這就是最優(yōu)算法的思長時(shí)間內(nèi)不需要訪問的頁。這就是最優(yōu)算法的思想。想。這種算法本身不是一種實(shí)際的方法，因?yàn)轫撁嬖L這種算法本身不是一種實(shí)際的方法，因?yàn)轫撁嬖L問的順序是很難預(yù)知的。但是，可把它作為一種問的順序是很難預(yù)知的。但是，可把它作為一種評價(jià)標(biāo)準(zhǔn)，比較其他實(shí)用方法的優(yōu)劣，所以，最評價(jià)標(biāo)準(zhǔn)，比較其他實(shí)用方法的優(yōu)劣，所以，最優(yōu)算法只具有理論上的意義。優(yōu)算法只具有理論上的意義。2先進(jìn)先出算法（先進(jìn)先出算法（FIFO算法）算法）這種算法的基本思想是：總是先淘汰那些駐留在這種

28、算法的基本思想是：總是先淘汰那些駐留在內(nèi)存時(shí)間最長的頁面，即先進(jìn)入內(nèi)存的頁面先被內(nèi)存時(shí)間最長的頁面，即先進(jìn)入內(nèi)存的頁面先被置換掉。理由是：最先進(jìn)入內(nèi)存的頁面不再被訪置換掉。理由是：最先進(jìn)入內(nèi)存的頁面不再被訪問的可能性最大。問的可能性最大。 3最久未使用頁面置換算法（最久未使用頁面置換算法（LRU算法）算法）這種算法的基本思想是，如果某一頁被訪問了，那么它這種算法的基本思想是，如果某一頁被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁很長時(shí)間沒有很可能馬上又被訪問；反之，如果某一頁很長時(shí)間沒有被訪問，那么最近也不太可能會被訪問。這種算法考慮被訪問，那么最近也不太可能會被訪問。這種算法考慮了程

29、序設(shè)計(jì)的局部性原理。其實(shí)質(zhì)是，當(dāng)需要置換一頁了程序設(shè)計(jì)的局部性原理。其實(shí)質(zhì)是，當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間最久未使用的頁面予以淘汰。時(shí)，選擇在最近一段時(shí)間最久未使用的頁面予以淘汰。實(shí)現(xiàn)這種算法可通過周期性地對實(shí)現(xiàn)這種算法可通過周期性地對“引用位引用位”進(jìn)行檢查，進(jìn)行檢查，并利用它來記錄一頁面自上次被訪問以來所經(jīng)歷的時(shí)間并利用它來記錄一頁面自上次被訪問以來所經(jīng)歷的時(shí)間t，淘汰時(shí)選擇淘汰時(shí)選擇t最大的頁面。最大的頁面。 4LRU近似算法近似算法這種算法，只要在存儲分塊表（或頁表）中設(shè)一個(gè)這種算法，只要在存儲分塊表（或頁表）中設(shè)一個(gè)“引引用位用位”，當(dāng)存儲分塊表中的某一頁被訪問時(shí)，該位由硬，

30、當(dāng)存儲分塊表中的某一頁被訪問時(shí)，該位由硬件自動置件自動置1，并由頁面管理軟件周期性把所有引用位置，并由頁面管理軟件周期性把所有引用位置0。這樣，在一個(gè)時(shí)間周期這樣，在一個(gè)時(shí)間周期T內(nèi)，某些被訪問過的頁面其引用內(nèi)，某些被訪問過的頁面其引用位為位為1，而未被訪問過的頁面其引用位為，而未被訪問過的頁面其引用位為0。因此，可根。因此，可根據(jù)引用位的狀態(tài)來判別各頁面最近的使用情況。當(dāng)需要據(jù)引用位的狀態(tài)來判別各頁面最近的使用情況。當(dāng)需要置換一頁面時(shí)，選擇其引用位為置換一頁面時(shí)，選擇其引用位為0的頁，如圖的頁，如圖4.21所示的所示的算法算法 。圖圖4.22是這種近似算法的一個(gè)例子。是這種近似算法的一個(gè)例子

31、。 【例【例1】主存塊數(shù)】主存塊數(shù)m=3，置換算法采用，置換算法采用FIFO算法，缺頁中算法，缺頁中斷次數(shù)及缺頁率如圖斷次數(shù)及缺頁率如圖2.21所示。所示。在圖在圖2.21中，中，P行表示頁面走向，行表示頁面走向，M行表示在主存中的頁行表示在主存中的頁面號，其中帶有面號，其中帶有+的表示新調(diào)入頁面，在的表示新調(diào)入頁面，在M行的各列按調(diào)行的各列按調(diào)入的順序排列，帶有圓圈的數(shù)字表示下一時(shí)刻將被淘汰入的順序排列，帶有圓圈的數(shù)字表示下一時(shí)刻將被淘汰頁面，頁面，F(xiàn)行表示是否引起缺頁中斷，帶行表示是否引起缺頁中斷，帶號的表示引起缺號的表示引起缺頁中斷。從圖頁中斷。從圖2.21可以看出，缺頁中斷頁數(shù)為可以看

32、出，缺頁中斷頁數(shù)為9次，缺頁次，缺頁率率f=9/12=75%。圖圖4.23 FIFO算法性能分析（算法性能分析（m=3）【例【例2】設(shè)】設(shè)m=4，仍采用，仍采用FIFO算法，缺頁中斷次算法，缺頁中斷次數(shù)及缺頁率如圖數(shù)及缺頁率如圖2.22所示?？梢运愠?，在分配給所示?？梢运愠?，在分配給該作業(yè)的內(nèi)存塊數(shù)增加到該作業(yè)的內(nèi)存塊數(shù)增加到4時(shí)，缺頁中斷由圖時(shí)，缺頁中斷由圖2.21的的9次反而增加到了次反而增加到了10次，缺頁率由次，缺頁率由75%增加增加到到10/12=83%，這就是，這就是FIFO算法的一種異?，F(xiàn)象。算法的一種異?，F(xiàn)象。隨著分配的主存塊數(shù)的增加，缺頁中斷次數(shù)不但隨著分配的主存塊數(shù)的增加，

33、缺頁中斷次數(shù)不但沒有降低，反而增加了。這與該算法定全不考慮沒有降低，反而增加了。這與該算法定全不考慮程序的動態(tài)特征有關(guān)。程序的動態(tài)特征有關(guān)。圖圖2.22 FIFO算法性能分析（算法性能分析（m=4）【例【例3】設(shè)】設(shè)m=3，采用，采用LRU算法，缺頁中斷次數(shù)算法，缺頁中斷次數(shù)及缺頁率如圖及缺頁率如圖2.23所示。所示。圖圖2.23 LRU算法性能分析（算法性能分析（m=3）【例例4】設(shè)設(shè)m=4，其余同例，其余同例3，則缺頁中斷次數(shù)及，則缺頁中斷次數(shù)及缺頁率如圖缺頁率如圖2.24所示。所示。 圖圖2.24 LRU算法性能分析（算法性能分析（m=4）2.3.6 分段存儲管理分段存儲管理 考慮到程往

34、往是有幾個(gè)模塊構(gòu)成，每個(gè)模塊可以稱為考慮到程往往是有幾個(gè)模塊構(gòu)成，每個(gè)模塊可以稱為段。整個(gè)程序在運(yùn)行時(shí)并不全部裝入內(nèi)存，而是如同分段。整個(gè)程序在運(yùn)行時(shí)并不全部裝入內(nèi)存，而是如同分頁存儲管理，首先調(diào)入一個(gè)或若干個(gè)程序段運(yùn)行，在運(yùn)頁存儲管理，首先調(diào)入一個(gè)或若干個(gè)程序段運(yùn)行，在運(yùn)行過程中調(diào)用到哪段時(shí)，就根據(jù)該段長度在內(nèi)存分配一行過程中調(diào)用到哪段時(shí)，就根據(jù)該段長度在內(nèi)存分配一個(gè)連續(xù)的分區(qū)給它使用。若內(nèi)存中沒有足夠大的空閑分個(gè)連續(xù)的分區(qū)給它使用。若內(nèi)存中沒有足夠大的空閑分區(qū)，則考慮進(jìn)行段的緊湊或?qū)⒛扯位蚰承┒翁蕴鋈?。區(qū)，則考慮進(jìn)行段的緊湊或?qū)⒛扯位蚰承┒翁蕴鋈?。相?yīng)于分頁存儲管理，這種存儲管理技術(shù)稱為分段存儲相應(yīng)于分頁存儲管理，這種存儲管理技術(shù)稱為分段存儲管理。管理。圖圖2.25 分段的邏輯地址空間分段的邏輯地址空間分段存儲管理分段存儲管理 1程序的邏輯地址結(jié)構(gòu)程序的邏輯地址結(jié)構(gòu) 2段表段表 3請求式分段動態(tài)地址變換過程請求式分段動態(tài)地址變換過程 4請求式分段存儲管理的優(yōu)、缺點(diǎn)請求式分段存儲管理