第二節(jié)存儲(chǔ)管理

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

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

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

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

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

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

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

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

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

10、劃分成若干個(gè)固定大小的存儲(chǔ)區(qū)，除操作用空間劃分成若干個(gè)固定大小的存儲(chǔ)區(qū)，除操作系統(tǒng)占用一個(gè)區(qū)域外，其余區(qū)域?yàn)橄到y(tǒng)中多個(gè)用系統(tǒng)占用一個(gè)區(qū)域外，其余區(qū)域?yàn)橄到y(tǒng)中多個(gè)用戶(hù)共享，因?yàn)樵谙到y(tǒng)運(yùn)行期間，分區(qū)大小、數(shù)目戶(hù)共享，因?yàn)樵谙到y(tǒng)運(yùn)行期間，分區(qū)大小、數(shù)目都不變，所以固定式分區(qū)也稱(chēng)為靜態(tài)分區(qū)。都不變，所以固定式分區(qū)也稱(chēng)為靜態(tài)分區(qū)。圖圖2.6 固定式分區(qū)內(nèi)存分配示意圖（固定式分區(qū)內(nèi)存分配示意圖（a）和（）和（b）固定式分區(qū)說(shuō)明表固定式分區(qū)說(shuō)明表2.2.3 可變式分區(qū)存儲(chǔ)管理可變式分區(qū)存儲(chǔ)管理 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ū)的起始部分開(kāi)辟出一個(gè)單元，存放一個(gè)鏈表指針的起始部分開(kāi)辟出一個(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è)用戶(hù)作業(yè)完成釋放所占分區(qū)時(shí)，系統(tǒng)應(yīng)當(dāng)某一個(gè)用戶(hù)作業(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ū)，并對(duì)相應(yīng)的鏈表合并，形成一個(gè)較大的空閑區(qū)，并對(duì)相應(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)重定位，也可采用動(dòng)態(tài)重定位。如可重定位可采用靜態(tài)重定位，也可采用動(dòng)態(tài)重定位。如采用靜態(tài)重定位，因用戶(hù)作業(yè)進(jìn)入內(nèi)

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

15、位的可變式分區(qū)管理技術(shù)，在執(zhí)行內(nèi)存分配時(shí)，如無(wú)足夠大空閑塊，應(yīng)考慮實(shí)現(xiàn)緊湊操作。其分配時(shí)，如無(wú)足夠大空閑塊，應(yīng)考慮實(shí)現(xiàn)緊湊操作。其分配算法如圖配算法如圖2.13所示所示 。 圖圖2.13 采用動(dòng)態(tài)重定位的分配算法采用動(dòng)態(tài)重定位的分配算法2.2.5 覆蓋技術(shù)覆蓋技術(shù) 當(dāng)用戶(hù)作業(yè)大于地址空間大于主存可用空間時(shí)，當(dāng)用戶(hù)作業(yè)大于地址空間大于主存可用空間時(shí)，該作業(yè)就無(wú)法運(yùn)行，這樣限制了大程序的運(yùn)行。該作業(yè)就無(wú)法運(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原來(lái)需170K，現(xiàn)在需要110KB2.2.5 交換技術(shù)交換技術(shù) 交換技術(shù)同樣是解決內(nèi)存不足問(wèn)題。在分時(shí)、交換技術(shù)同樣是解決內(nèi)存不足問(wèn)題。在分時(shí)、實(shí)時(shí)系統(tǒng)及批處理系統(tǒng)中均有應(yīng)用。實(shí)時(shí)系統(tǒng)及批處理系統(tǒng)中均有應(yīng)用。 它的基本思想是：只允許一個(gè)或幾個(gè)用戶(hù)作它的基本思想是：只允許一個(gè)或幾個(gè)用戶(hù)作業(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 虛擬存儲(chǔ)器管理虛擬存儲(chǔ)器管理 2.3.1 虛擬存儲(chǔ)器的概念虛擬存儲(chǔ)器的概念 2.3.2 分頁(yè)存儲(chǔ)管理與動(dòng)態(tài)地址重定位分頁(yè)存儲(chǔ)管理與動(dòng)態(tài)地址重定位 2.3.3 現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動(dòng)態(tài)地址重定位現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動(dòng)態(tài)地址重定位 2.3.4 頁(yè)面置換算法頁(yè)面置換算法 2.3.5 請(qǐng)求式分頁(yè)存儲(chǔ)管理性能分析舉例請(qǐng)求式分頁(yè)存儲(chǔ)管理性能分析舉例 2.3.6 請(qǐng)求式分段存儲(chǔ)管理請(qǐng)求式分段存儲(chǔ)管理 2.3.1 虛擬存儲(chǔ)器的概念虛擬存儲(chǔ)器的概念 （1）程序

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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