存儲(chǔ)管理及內(nèi)存的基本相關(guān)知識(shí)課件

第4章

存儲(chǔ)管理

本章學(xué)習(xí)目標(biāo)

4.1存儲(chǔ)管理的功能

4.2實(shí)存管理

4.3虛擬存儲(chǔ)器管理

4.4碎片與抖動(dòng)問(wèn)題

開(kāi)始第4章存儲(chǔ)管理本章學(xué)習(xí)目標(biāo)開(kāi)本章學(xué)習(xí)目標(biāo)

本章首先介紹了存儲(chǔ)管理的研究對(duì)象和目的，明確了存儲(chǔ)管理的基本功能和有關(guān)的基本概念；然后從實(shí)存和虛存兩個(gè)角度，分別介紹了常用的幾種存儲(chǔ)管理方案；最后對(duì)各種存儲(chǔ)管理方案存在的問(wèn)題，主要是碎片和抖動(dòng)問(wèn)題進(jìn)行了總結(jié)。

返回本章首頁(yè)本章學(xué)習(xí)目標(biāo)本章首先介紹了存儲(chǔ)管理的研究對(duì)象和目的，明確了本章的主要內(nèi)容如下：(1)存儲(chǔ)管理的目的和四大基本功能。

(2)實(shí)存管理中講述了固定分區(qū)存儲(chǔ)管理、可變式分區(qū)存儲(chǔ)管理、純分頁(yè)存儲(chǔ)管理三種存儲(chǔ)管理方案的實(shí)現(xiàn)原理(3)虛存管理以請(qǐng)求式分頁(yè)存儲(chǔ)管理為重點(diǎn)

(4)總結(jié)各種存儲(chǔ)管理方案中存在的碎片和抖動(dòng)問(wèn)題及解決方法下一頁(yè)本章的主要內(nèi)容如下：(1)存儲(chǔ)管理的目的和四大基本功能。下圖4.1多級(jí)存儲(chǔ)器體系示意圖圖4.1多級(jí)存儲(chǔ)器體系示意圖4.1存儲(chǔ)管理的功能4.1.1內(nèi)存的分配與回收

4.1.2地址重定位4.1.3存儲(chǔ)保護(hù)

4.1.4虛擬存儲(chǔ)器

返回本章首頁(yè)4.1存儲(chǔ)管理的功能4.1.1內(nèi)存的分配與回收返4.1.1內(nèi)存的分配與回收內(nèi)存分配按分配時(shí)機(jī)的不同，可分為兩種方式。（1）靜態(tài)存儲(chǔ)分配：指內(nèi)存分配是在作業(yè)運(yùn)行之前各目標(biāo)模塊連接后，把整個(gè)作業(yè)一次性全部裝入內(nèi)存，并在作業(yè)的整個(gè)運(yùn)行過(guò)程中，不允許作業(yè)再申請(qǐng)其他內(nèi)存，或在內(nèi)存中移動(dòng)位置。也就是說(shuō)，內(nèi)存分配是在作業(yè)運(yùn)行前一次性完成的。（2）動(dòng)態(tài)存儲(chǔ)分配：作業(yè)要求的基本內(nèi)存空間是在目標(biāo)模塊裝入內(nèi)存時(shí)分配的，但在作業(yè)運(yùn)行過(guò)程中，允許作業(yè)申請(qǐng)附加的內(nèi)存空間，或是在內(nèi)存中移動(dòng)，即分配工作可以在作業(yè)運(yùn)行前及運(yùn)行過(guò)程中逐步完成。返回本節(jié)4.1.1內(nèi)存的分配與回收內(nèi)存分配按分配時(shí)機(jī)的不同，可4.1.2地址重定位1．內(nèi)存空間（或物理空間）2．邏輯空間3．地址重定位下一頁(yè)4.1.2地址重定位1．內(nèi)存空間（或物理空間）下一頁(yè)1．內(nèi)存空間（或物理空間）內(nèi)存是由若干個(gè)存儲(chǔ)單元組成的，每個(gè)存儲(chǔ)單元有一個(gè)編號(hào)，這種編號(hào)可唯一標(biāo)識(shí)一個(gè)存儲(chǔ)單元，稱為內(nèi)存地址（或物理地址）。下一頁(yè)1．內(nèi)存空間（或物理空間）內(nèi)存是由若干個(gè)存儲(chǔ)單元組成的，每個(gè)2．邏輯空間源程序經(jīng)過(guò)匯編或編譯后，形成目標(biāo)程序，每個(gè)目標(biāo)程序都是以0為基址順序進(jìn)行編址的，原來(lái)用符號(hào)名訪問(wèn)的單元用具體的數(shù)據(jù)——單元號(hào)取代。這樣生成的目標(biāo)程序占據(jù)一定的地址空間，稱為作業(yè)的邏輯地址空間，簡(jiǎn)稱邏輯空間。在邏輯空間中每條指令的地址和指令中要訪問(wèn)的操作數(shù)地址統(tǒng)稱為邏輯地址。下一頁(yè)2．邏輯空間源程序經(jīng)過(guò)匯編或編譯后，形成目標(biāo)程序，每個(gè)目標(biāo)程圖4.2作業(yè)的名空間、邏輯地址空間和裝入后的物理空間下一頁(yè)圖4.2作業(yè)的名空間、邏輯地址空間和裝入后的物理空間下一3．地址重定位(1)靜態(tài)地址重定位靜態(tài)地址重定位是在程序執(zhí)行之前由操作系統(tǒng)的重定位裝入程序完成的。(2)動(dòng)態(tài)地址重定位

動(dòng)態(tài)地址重定位是在程序執(zhí)行期間進(jìn)行的。

下一頁(yè)3．地址重定位(1)靜態(tài)地址重定位下一頁(yè)（b）采用動(dòng)態(tài)重定位時(shí)內(nèi)存空間及地址重定位示意圖（a）采用靜態(tài)重定位后的內(nèi)存空間圖4.3靜態(tài)地址重定位和動(dòng)態(tài)地址重定位示意圖返回本節(jié)（b）采用動(dòng)態(tài)重定位時(shí)內(nèi)存空間及地址重定位示意圖（a）采用4.1.3存儲(chǔ)保護(hù)（1）上、下界存儲(chǔ)保護(hù)：上、下界保護(hù)是一種簡(jiǎn)單的存儲(chǔ)保護(hù)技術(shù)。系統(tǒng)可為每個(gè)作業(yè)設(shè)置一對(duì)上、下界寄存器，分別用來(lái)存放當(dāng)前運(yùn)行作業(yè)在內(nèi)存空間的上、下邊界地址，用它們來(lái)限制用戶程序的活動(dòng)范圍。

（2）基址—限長(zhǎng)存儲(chǔ)保護(hù)：上、下界保護(hù)的一個(gè)變種是采用基址—限長(zhǎng)存儲(chǔ)保護(hù)。

4.1.3存儲(chǔ)保護(hù)（1）上、下界存儲(chǔ)保護(hù)：上、下界保護(hù)圖4.4界限寄存器的兩種存儲(chǔ)保護(hù)方式返回本節(jié)圖4.4界限寄存器的兩種存儲(chǔ)保護(hù)方式返回本節(jié)4.1.4虛擬存儲(chǔ)器對(duì)內(nèi)存進(jìn)行邏輯上的擴(kuò)充，現(xiàn)在普遍采用虛擬存儲(chǔ)管理技術(shù)。

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

返回本節(jié)4.1.4虛擬存儲(chǔ)器對(duì)內(nèi)存進(jìn)行邏輯上的擴(kuò)充，現(xiàn)在普遍采4.2實(shí)存管理4.2.1固定分區(qū)存儲(chǔ)管理

4.2.2可變式分區(qū)存儲(chǔ)管理4.2.3純分頁(yè)存儲(chǔ)管理

返回本章首頁(yè)4.2實(shí)存管理4.2.1固定分區(qū)存儲(chǔ)管理返回本章4.2.1固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理是實(shí)現(xiàn)多道程序設(shè)計(jì)的最簡(jiǎn)單的一種存儲(chǔ)管理技術(shù)。其基本思想是，在作業(yè)未進(jìn)入內(nèi)存之前，就由操作員或操作系統(tǒng)把內(nèi)存可用空間劃分成若干個(gè)固定大小的存儲(chǔ)區(qū)，除操作系統(tǒng)占用一個(gè)區(qū)域外，其余區(qū)域?yàn)橄到y(tǒng)中多個(gè)用戶共享，因?yàn)樵谙到y(tǒng)運(yùn)行期間，分區(qū)大小、數(shù)目都不變，所以固定式分區(qū)也稱為靜態(tài)分區(qū)。4.2.1固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理是實(shí)現(xiàn)多道程圖4.5固定式分區(qū)內(nèi)存分配示意圖（a）和（b）固定式分區(qū)說(shuō)明表返回本節(jié)圖4.5固定式分區(qū)內(nèi)存分配示意圖（a）和（b）固定式分區(qū)4.2.2可變式分區(qū)存儲(chǔ)管理1．空閑分區(qū)的組織形式

2．內(nèi)存的分配與回收

3．常用的分配算法

4．可變式分區(qū)的地址重定位

下一頁(yè)4.2.2可變式分區(qū)存儲(chǔ)管理1．空閑分區(qū)的組織形式下圖4.6可變式分區(qū)內(nèi)存使用情況示意圖下一頁(yè)圖4.6可變式分區(qū)內(nèi)存使用情況示意圖下一頁(yè)1．空閑分區(qū)的組織形式空閑分區(qū)鏈表的組織是這樣的：在每個(gè)空閑分區(qū)的起始部分開(kāi)辟出一個(gè)單元，存放一個(gè)鏈表指針和該分區(qū)的大小，鏈表指針指向下一個(gè)空閑分區(qū)。系統(tǒng)中用一個(gè)固定單元作為空閑分區(qū)鏈表的鏈表頭指針，指向第一塊空閑分區(qū)首地址，最后一塊空閑分區(qū)的鏈表指針存放鏈尾標(biāo)志。如圖4.7（a）所示。下一頁(yè)1．空閑分區(qū)的組織形式空閑分區(qū)鏈表的組織是這樣的：在每個(gè)空2．內(nèi)存的分配與回收當(dāng)某一個(gè)用戶作業(yè)完成釋放所占分區(qū)時(shí)，系統(tǒng)應(yīng)進(jìn)行回收。在可變式分區(qū)中，應(yīng)該檢查回收區(qū)與內(nèi)存中前后空閑區(qū)是否相鄰，若相鄰，則應(yīng)進(jìn)行合并，形成一個(gè)較大的空閑區(qū)，并對(duì)相應(yīng)的鏈表指針進(jìn)行修改；若不相鄰，應(yīng)將空閑區(qū)插入到空閑區(qū)鏈表的適當(dāng)位置。

下一頁(yè)2．內(nèi)存的分配與回收當(dāng)某一個(gè)用戶作業(yè)完成釋放所占分區(qū)時(shí)，系圖4.7首次適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)圖4.7首次適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)3．常用的分配算法（1）首次適應(yīng)算法

（2）最佳適應(yīng)算法

（3）最差適應(yīng)算法

下一頁(yè)3．常用的分配算法（1）首次適應(yīng)算法下一頁(yè)圖4.8最佳適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)圖4.8最佳適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)圖4.9最差適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)圖4.9最差適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)圖4.10內(nèi)存使用情況下一頁(yè)圖4.10內(nèi)存使用情況下一頁(yè)圖4.11用三種適應(yīng)算法處理同一作業(yè)序列下一頁(yè)圖4.11用三種適應(yīng)算法處理同一作業(yè)序列下一頁(yè)4．可變式分區(qū)的地址重定位可變式分區(qū)的地址重定位可采用靜態(tài)重定位，也可采用動(dòng)態(tài)重定位。如采用靜態(tài)重定位，因用戶作業(yè)進(jìn)入內(nèi)存后，程序的邏輯地址實(shí)現(xiàn)了重定位，不能在內(nèi)存中再進(jìn)行移動(dòng)，經(jīng)過(guò)一段時(shí)間的運(yùn)行，內(nèi)存中不能再分配利用的小碎片會(huì)越來(lái)越多。有時(shí)可能會(huì)出現(xiàn)這種情況，即當(dāng)一個(gè)作業(yè)申請(qǐng)一定數(shù)量的內(nèi)存時(shí)，雖然此時(shí)空閑區(qū)的總和大于新作業(yè)的內(nèi)存要求，但卻沒(méi)有單個(gè)的空閑區(qū)足以裝下該作業(yè)。采用動(dòng)態(tài)重定位的可變式分區(qū)管理技術(shù)，在執(zhí)行內(nèi)存分配時(shí)，如無(wú)足夠大空閑塊，應(yīng)考慮實(shí)現(xiàn)緊湊操作。其分配算法如圖4.12所示

。

下一頁(yè)4．可變式分區(qū)的地址重定位可變式分區(qū)的地址重定位可采用靜態(tài)圖4.12采用動(dòng)態(tài)重定位的可變式分區(qū)分配算法返回本節(jié)圖4.12采用動(dòng)態(tài)重定位的可變式分區(qū)分配算法返回本節(jié)4.2.3純分頁(yè)存儲(chǔ)管理1．純分頁(yè)存儲(chǔ)管理中存儲(chǔ)塊的分配與回收

2．純分頁(yè)存儲(chǔ)管理的地址重定位問(wèn)題3．聯(lián)想存儲(chǔ)器

4．存儲(chǔ)保護(hù)

下一頁(yè)4.2.3純分頁(yè)存儲(chǔ)管理1．純分頁(yè)存儲(chǔ)管理中存儲(chǔ)塊的分1．純分頁(yè)存儲(chǔ)管理中存儲(chǔ)塊的分配與回收通常有兩種記錄空閑存儲(chǔ)塊的方法：位圖法和鏈表法。（a）存儲(chǔ)塊使用情況（b）存儲(chǔ)塊使用情況的位圖表示圖4-13存儲(chǔ)塊的位圖管理法1．純分頁(yè)存儲(chǔ)管理中存儲(chǔ)塊的分配與回收通常有兩種記錄空閑存2．純分頁(yè)存儲(chǔ)管理的地址重定位問(wèn)題純分頁(yè)存儲(chǔ)管理中的地址重定位是非常重要的，要使不連續(xù)的、分散的用戶程序能正常運(yùn)行，須采用動(dòng)態(tài)地址重定位。此時(shí)，可采用重定位寄存器方式，如分頁(yè)太多，則重定位寄存器用得太多。通?？稍趦?nèi)存中為每個(gè)作業(yè)開(kāi)辟一塊特定區(qū)域，建立起作業(yè)的邏輯頁(yè)與存儲(chǔ)塊之間的對(duì)應(yīng)表格關(guān)系，這種表常稱為頁(yè)面映象表，簡(jiǎn)稱頁(yè)表。

下一頁(yè)2．純分頁(yè)存儲(chǔ)管理的地址重定位問(wèn)題純分頁(yè)存儲(chǔ)管理中的地址重圖4.14純分頁(yè)存儲(chǔ)管理示意圖下一頁(yè)圖4.14純分頁(yè)存儲(chǔ)管理示意圖下一頁(yè)3．聯(lián)想存儲(chǔ)器從上面介紹的地址變換過(guò)程可以看出：如果把頁(yè)表全部放在內(nèi)存，那么存取一個(gè)數(shù)據(jù)時(shí)，至少要訪問(wèn)二次內(nèi)存。一次是訪問(wèn)頁(yè)表，形成實(shí)際內(nèi)存地址；另一次是根據(jù)形成的內(nèi)存地址存取數(shù)據(jù)。顯然，這比通常執(zhí)行指令的速度要慢得多，使計(jì)算機(jī)的運(yùn)行速度幾乎降低一半。應(yīng)用聯(lián)想存儲(chǔ)器和頁(yè)表相結(jié)合的方式，可有效地提高系統(tǒng)動(dòng)態(tài)地址轉(zhuǎn)換的速度，是一種行之有效的方法。下一頁(yè)3．聯(lián)想存儲(chǔ)器從上面介紹的地址變換過(guò)程可以看出：如果把頁(yè)表圖4.15純分頁(yè)存儲(chǔ)管理地址重定位實(shí)現(xiàn)過(guò)程下一頁(yè)圖4.15純分頁(yè)存儲(chǔ)管理地址重定位實(shí)現(xiàn)過(guò)程下一頁(yè)圖4.16采用快表和頁(yè)表相結(jié)合的分頁(yè)地址變換過(guò)程示意圖下一頁(yè)圖4.16采用快表和頁(yè)表相結(jié)合的分頁(yè)地址變換過(guò)程示意圖下4．存儲(chǔ)保護(hù)四種保護(hù)方式：①禁止做任何操作，②只能執(zhí)行，③只能讀，④能讀/寫，當(dāng)要訪問(wèn)某頁(yè)時(shí)，先判斷該頁(yè)的存取控制和存儲(chǔ)保護(hù)信息是否允許。添加了存取控制信息的頁(yè)表表目如下圖所示：

返回本節(jié)4．存儲(chǔ)保護(hù)四種保護(hù)方式：①禁止做任何操作，②只能執(zhí)行，③4.3虛擬存儲(chǔ)器管理4.3.1虛擬存儲(chǔ)器的概念

4.3.2請(qǐng)求式分頁(yè)存儲(chǔ)管理與動(dòng)態(tài)地址重定位

4.3.3現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動(dòng)態(tài)地址重定位

4.3.4頁(yè)面置換算法

4.3.5請(qǐng)求式分頁(yè)存儲(chǔ)管理性能分析舉例

4.3.6請(qǐng)求式分段存儲(chǔ)管理

返回本章首頁(yè)4.3虛擬存儲(chǔ)器管理4.3.1虛擬存儲(chǔ)器的概念返4.3.1虛擬存儲(chǔ)器的概念（1）程序中往往會(huì)有一些彼此互斥的部分。（2）在一個(gè)完整的程序中，會(huì)有一些諸如出錯(cuò)處理這樣的子程序，在作業(yè)正常運(yùn)行情況下不會(huì)執(zhí)行這些程序，沒(méi)有必要把它們調(diào)入內(nèi)存?；诔绦蚓植啃栽砗蜕鲜銮闆r，就沒(méi)有必要把一個(gè)作業(yè)一次性全部裝入內(nèi)存再開(kāi)始運(yùn)行。而是可以把程序當(dāng)前執(zhí)行所涉及的信息放入內(nèi)存中，其余部分可根據(jù)需要臨時(shí)調(diào)入，由操作系統(tǒng)和硬件相配合來(lái)完成主存和輔存之間信息的動(dòng)態(tài)調(diào)度。這樣的計(jì)算機(jī)系統(tǒng)好像為用戶提供了一個(gè)存儲(chǔ)容量比實(shí)際主存大得多的存儲(chǔ)器，就稱為虛擬存儲(chǔ)器。

返回本節(jié)4.3.1虛擬存儲(chǔ)器的概念（1）程序中往往會(huì)有一些彼此4.3.2請(qǐng)求式分頁(yè)存儲(chǔ)管理與動(dòng)態(tài)地址重定位請(qǐng)求式分頁(yè)存儲(chǔ)管理與純分頁(yè)存儲(chǔ)管理在內(nèi)存塊的分配與回收，存儲(chǔ)保護(hù)某方面都十分相似，不同之處在于地址重定位問(wèn)題。在請(qǐng)求式分頁(yè)存儲(chǔ)管理的地址重定位時(shí)，可能會(huì)出現(xiàn)所需頁(yè)面不在主存的情況，此時(shí)，系統(tǒng)必須解決以下兩個(gè)問(wèn)題：（1）當(dāng)程序要訪問(wèn)的某頁(yè)不在內(nèi)存時(shí)，如何發(fā)現(xiàn)這種缺頁(yè)情況？發(fā)現(xiàn)后應(yīng)如何處理？（2）當(dāng)需要把外存上的某個(gè)頁(yè)面調(diào)入內(nèi)存時(shí)，此時(shí)內(nèi)存中沒(méi)有空閑塊應(yīng)怎么辦？下一頁(yè)4.3.2請(qǐng)求式分頁(yè)存儲(chǔ)管理與動(dòng)態(tài)地址重定位請(qǐng)求式分頁(yè)如圖4.17所示是請(qǐng)求式分頁(yè)存儲(chǔ)管理的存儲(chǔ)映像下一頁(yè)如圖4.17所示是請(qǐng)求式分頁(yè)存儲(chǔ)管理的存儲(chǔ)映像下一頁(yè)為了幫助操作系統(tǒng)對(duì)要置換出內(nèi)存的頁(yè)面進(jìn)行選擇，在頁(yè)表中還可以增加一個(gè)引用位，以反映該頁(yè)最近的使用情況。一般來(lái)說(shuō)，一個(gè)頁(yè)表的表目通常可包括如下的數(shù)據(jù)內(nèi)容：下一頁(yè)為了幫助操作系統(tǒng)對(duì)要置換出內(nèi)存的頁(yè)面進(jìn)行選擇，在頁(yè)表中還可以請(qǐng)求式分頁(yè)存儲(chǔ)管理中的地址重定位和缺頁(yè)中斷處理過(guò)程如圖4.18所示。返回本節(jié)請(qǐng)求式分頁(yè)存儲(chǔ)管理中的地址重定位和缺頁(yè)中斷處理過(guò)程如圖4.14.3.3現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動(dòng)態(tài)地址重定位（1）如何合理地組織管理相當(dāng)大的頁(yè)表？在WindowsNT中，為解決第一個(gè)問(wèn)題，對(duì)頁(yè)表本身進(jìn)行了改進(jìn)，將龐大的頁(yè)表本身也采取分頁(yè)措施，采用了兩級(jí)頁(yè)表結(jié)構(gòu)。即把頁(yè)表本身按固定大小分成一個(gè)個(gè)小頁(yè)表，每個(gè)小頁(yè)表由210=1024個(gè)頁(yè)表表目構(gòu)成，每個(gè)表目占4字節(jié)，所以每個(gè)小頁(yè)表剛好占一個(gè)頁(yè)面（頁(yè)面大小為212=4kb）。一共有210=1k個(gè)小頁(yè)表。為了對(duì)這1k個(gè)小頁(yè)表進(jìn)行管理和索引查找，設(shè)置了一個(gè)頁(yè)表目錄，也稱之為頂級(jí)頁(yè)表或一級(jí)頁(yè)表，該頁(yè)目錄包含有1k個(gè)表目項(xiàng)，分別指出每個(gè)次級(jí)小頁(yè)表所在的物理塊號(hào)和其他有關(guān)狀態(tài)信息。這樣，每個(gè)作業(yè)有一個(gè)頁(yè)目錄（一級(jí)頁(yè)表），它的每個(gè)表目指向一個(gè)二級(jí)頁(yè)表。頁(yè)目錄本身也剛好是一個(gè)頁(yè)面大?。?10=1k，每個(gè)表目4個(gè)字節(jié)）。下一頁(yè)4.3.3現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動(dòng)態(tài)地址重定位（1）如何圖4.19WindowsNT兩級(jí)頁(yè)表地址變換示意圖下一頁(yè)圖4.19WindowsNT兩級(jí)頁(yè)表地址變換示意圖下一（2）面對(duì)大的頁(yè)表，地址的映射怎樣才能比較快地實(shí)現(xiàn)？（1）使用快表：即利用前面我們已介紹的高速緩沖存儲(chǔ)器來(lái)存放經(jīng)常使用的頁(yè)表表目，以提高頁(yè)表的查詢速度。（2）使用高速緩沖存儲(chǔ)器：在微處理器和主存之間設(shè)置32kb或64kb的高速緩沖存儲(chǔ)器，大部分的指令和數(shù)據(jù)取自高速緩存（命中率為98%），所以存取數(shù)據(jù)和指令速度相當(dāng)高，達(dá)到與處理器速度完全相匹配。返回本節(jié)（2）面對(duì)大的頁(yè)表，地址的映射怎樣才能比較快地實(shí)現(xiàn)？（1）4.3.4頁(yè)面置換算法1．最優(yōu)算法（OPT算法）2．先進(jìn)先出算法（FIFO算法）3．最久未使用頁(yè)面置換算法（LRU算法）4．LRU近似算法下一頁(yè)4.3.4頁(yè)面置換算法1．最優(yōu)算法（OPT算法）下一頁(yè)1．最優(yōu)算法（OPT算法）最理想的頁(yè)面置換算法是：從內(nèi)存中移出以后不再使用的頁(yè)面；如無(wú)這樣的頁(yè)面，則選擇以后最長(zhǎng)時(shí)間內(nèi)不需要訪問(wèn)的頁(yè)。這就是最優(yōu)算法的思想。這種算法本身不是一種實(shí)際的方法，因?yàn)轫?yè)面訪問(wèn)的順序是很難預(yù)知的。但是，可把它作為一種評(píng)價(jià)標(biāo)準(zhǔn)，比較其他實(shí)用方法的優(yōu)劣，所以，最優(yōu)算法只具有理論上的意義。下一頁(yè)1．最優(yōu)算法（OPT算法）最理想的頁(yè)面置換算法是：從內(nèi)存中移2．先進(jìn)先出算法（FIFO算法）這種算法的基本思想是：總是先淘汰那些駐留在內(nèi)存時(shí)間最長(zhǎng)的頁(yè)面，即先進(jìn)入內(nèi)存的頁(yè)面先被置換掉。理由是：最先進(jìn)入內(nèi)存的頁(yè)面不再被訪問(wèn)的可能性最大。

下一頁(yè)2．先進(jìn)先出算法（FIFO算法）這種算法的基本思想是：總是先圖4.20先進(jìn)先出算法存儲(chǔ)分塊表構(gòu)造下一頁(yè)圖4.20先進(jìn)先出算法存儲(chǔ)分塊表構(gòu)造下一頁(yè)3．最久未使用頁(yè)面置換算法（LRU算法）這種算法的基本思想是，如果某一頁(yè)被訪問(wèn)了，那么它很可能馬上又被訪問(wèn)；反之，如果某一頁(yè)很長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)，那么最近也不太可能會(huì)被訪問(wèn)。這種算法考慮了程序設(shè)計(jì)的局部性原理。其實(shí)質(zhì)是，當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間最久未使用的頁(yè)面予以淘汰。實(shí)現(xiàn)這種算法可通過(guò)周期性地對(duì)“引用位”進(jìn)行檢查，并利用它來(lái)記錄一頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t，淘汰時(shí)選擇t最大的頁(yè)面。

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

下一頁(yè)4．LRU近似算法這種算法，只要在存儲(chǔ)分塊表（或頁(yè)表）中設(shè)一圖4.21LRU近似算法下一頁(yè)圖4.21LRU近似算法下一頁(yè)圖4.22LRU近似算法舉例返回本節(jié)圖4.22LRU近似算法舉例返回本節(jié)4.3.5請(qǐng)求式分頁(yè)存儲(chǔ)管理性能分析舉例1．程序設(shè)計(jì)的質(zhì)量2．頁(yè)面的大小3．分配的內(nèi)存塊數(shù)4．頁(yè)面置換算法性能下一頁(yè)4.3.5請(qǐng)求式分頁(yè)存儲(chǔ)管理性能分析舉例1．程序設(shè)計(jì)的【例1】主存塊數(shù)m=3，置換算法采用FIFO算法，缺頁(yè)中斷次數(shù)及缺頁(yè)率如圖4.23所示。在圖4.23中，P行表示頁(yè)面走向，M行表示在主存中的頁(yè)面號(hào)，其中帶有+的表示新調(diào)入頁(yè)面，在M行的各列按調(diào)入的順序排列，帶有圓圈的數(shù)字表示下一時(shí)刻將被淘汰頁(yè)面，F(xiàn)行表示是否引起缺頁(yè)中斷，帶√號(hào)的表示引起缺頁(yè)中斷。從圖4.23可以看出，缺頁(yè)中斷頁(yè)數(shù)為9次，缺頁(yè)率f=9/12=75%。下一頁(yè)【例1】主存塊數(shù)m=3，置換算法采用FIFO算法，缺頁(yè)中斷次圖4.23FIFO算法性能分析（m=3）下一頁(yè)圖4.23FIFO算法性能分析（m=3）下一頁(yè)【例2】設(shè)m=4，仍采用FIFO算法，缺頁(yè)中斷次數(shù)及缺頁(yè)率如圖4.24所示?？梢运愠觯诜峙浣o該作業(yè)的內(nèi)存塊數(shù)增加到4時(shí)，缺頁(yè)中斷由圖4.23的9次反而增加到了10次，缺頁(yè)率由75%增加到10/12=83%，這就是FIFO算法的一種異?，F(xiàn)象。隨著分配的主存塊數(shù)的增加，缺頁(yè)中斷次數(shù)不但沒(méi)有降低，反而增加了。這與該算法定全不考慮程序的動(dòng)態(tài)特征有關(guān)。下一頁(yè)【例2】設(shè)m=4，仍采用FIFO算法，缺頁(yè)中斷次數(shù)及缺頁(yè)率如圖4.24FIFO算法性能分析（m=4）下一頁(yè)圖4.24FIFO算法性能分析（m=4）下一頁(yè)【例3】設(shè)m=3，采用LRU算法，缺頁(yè)中斷次數(shù)及缺頁(yè)率如圖4.25所示。圖4.25LRU算法性能分析（m=3）下一頁(yè)【例3】設(shè)m=3，采用LRU算法，缺頁(yè)中斷次數(shù)及缺頁(yè)率如圖4【例4】設(shè)m=4，其余同例3，則缺頁(yè)中斷次數(shù)及缺頁(yè)率如圖4.26所示。

圖4.26LRU算法性能分析（m=4）返回本節(jié)【例4】設(shè)m=4，其余同例3，則缺頁(yè)中斷次數(shù)及缺頁(yè)率如圖4.4.3.6請(qǐng)求式分段存儲(chǔ)管理為了能實(shí)現(xiàn)虛擬存儲(chǔ)，段式邏輯地址空間中的程序段在運(yùn)行時(shí)并不全部裝入內(nèi)存，而是如同請(qǐng)求式分頁(yè)存儲(chǔ)管理，首先調(diào)入一個(gè)或若干個(gè)程序段運(yùn)行，在運(yùn)行過(guò)程中調(diào)用到哪段時(shí)，就根據(jù)該段長(zhǎng)度在內(nèi)存分配一個(gè)連續(xù)的分區(qū)給它使用。若內(nèi)存中沒(méi)有足夠大的空閑分區(qū)，則考慮進(jìn)行段的緊湊或?qū)⒛扯位蚰承┒翁蕴鋈?。相?yīng)于請(qǐng)求式分頁(yè)存儲(chǔ)管理，這種存儲(chǔ)管理技術(shù)稱為請(qǐng)求式分段存儲(chǔ)管理。下一頁(yè)4.3.6請(qǐng)求式分段存儲(chǔ)管理為了能實(shí)現(xiàn)虛擬存儲(chǔ)，段式邏圖4.27分段的邏輯地址空間下一頁(yè)圖4.27分段的邏輯地址空間下一頁(yè)請(qǐng)求式分段存儲(chǔ)管理的地址變換1．程序的邏輯地址結(jié)構(gòu)

2．段表

3．請(qǐng)求式分段動(dòng)態(tài)地址變換過(guò)程

4．請(qǐng)求式分段存儲(chǔ)管理的優(yōu)、缺點(diǎn)

下一頁(yè)請(qǐng)求式分段存儲(chǔ)管理的地址變換1．程序的邏輯地址結(jié)構(gòu)下一頁(yè)1．程序的邏輯地址結(jié)構(gòu)請(qǐng)求式分段存儲(chǔ)管理的邏輯地址結(jié)構(gòu)由段號(hào)s和段內(nèi)位移量d組成，如下圖所示。下一頁(yè)1．程序的邏輯地址結(jié)構(gòu)請(qǐng)求式分段存儲(chǔ)管理的邏輯地址結(jié)構(gòu)由段2．段表類似于請(qǐng)求式分頁(yè)存儲(chǔ)管理的頁(yè)表，為了實(shí)現(xiàn)動(dòng)態(tài)地址變換和存儲(chǔ)保護(hù)，系統(tǒng)要為每一個(gè)作業(yè)建立一張段表。段表中的每一個(gè)表目對(duì)應(yīng)著作業(yè)地址空間的一個(gè)程序段，其一般格式為：

下一頁(yè)2．段表類似于請(qǐng)求式分頁(yè)存儲(chǔ)管理的頁(yè)表，為了實(shí)現(xiàn)動(dòng)態(tài)地址變3．請(qǐng)求式分段動(dòng)態(tài)地址變換過(guò)程圖4.28請(qǐng)求式分段動(dòng)態(tài)地址下一頁(yè)3．請(qǐng)求式分段動(dòng)態(tài)地址變換過(guò)程圖4.28請(qǐng)求式分段動(dòng)態(tài)請(qǐng)求式分段存儲(chǔ)管理的地址變換（1）可提供大容量的虛存

（2）允許動(dòng)態(tài)增加段的長(zhǎng)度

（3）便于段的動(dòng)態(tài)鏈接

（4）便于實(shí)現(xiàn)程序段的共享

（5）便于實(shí)現(xiàn)存儲(chǔ)保護(hù)

返回本節(jié)請(qǐng)求式分段存儲(chǔ)管理的地址變換（1）可提供大容量的虛存返回4.4碎片與抖動(dòng)問(wèn)題1、碎片問(wèn)題

解決碎片問(wèn)題的比較好的方法是采用分頁(yè)技術(shù)，在純分頁(yè)存儲(chǔ)管理系統(tǒng)中，因存儲(chǔ)區(qū)劃分成固定大小的塊，而用戶作業(yè)也劃分成與塊相等的若干頁(yè)，每個(gè)作業(yè)調(diào)入內(nèi)存時(shí)，除最后一個(gè)頁(yè)面可能有頁(yè)內(nèi)碎片出現(xiàn)外，其余頁(yè)不存在碎片問(wèn)題，一般來(lái)說(shuō)，平均每個(gè)作業(yè)可能有半頁(yè)的內(nèi)碎片。返回本章首頁(yè)4.4碎片與抖動(dòng)問(wèn)題1、碎片問(wèn)題返回本章首頁(yè)2、抖動(dòng)現(xiàn)象

避免抖動(dòng)現(xiàn)象最根本的方法是控制多道程序的道數(shù)，使得每個(gè)用戶作業(yè)都有足夠的內(nèi)存空間可供使用。但作業(yè)的個(gè)數(shù)又不能太少，否則，會(huì)影響處理機(jī)的利用率。最好是使處理機(jī)利用率較高，又不致于使系統(tǒng)發(fā)生抖動(dòng)，這是一個(gè)很難解決的問(wèn)題，牽扯到程序的局部性問(wèn)題，并需借助于工作集模型。返回本節(jié)2、抖動(dòng)現(xiàn)象返回本節(jié)THANKYOUVERYMUCH！本章到此結(jié)束，謝謝您的光臨！返回本章首頁(yè)結(jié)束放映THANKYOUVERYMUCH！本章到此結(jié)束，返回第4章

存儲(chǔ)管理

本章學(xué)習(xí)目標(biāo)

4.1存儲(chǔ)管理的功能

4.2實(shí)存管理

4.3虛擬存儲(chǔ)器管理

4.4碎片與抖動(dòng)問(wèn)題

開(kāi)始第4章存儲(chǔ)管理本章學(xué)習(xí)目標(biāo)開(kāi)本章學(xué)習(xí)目標(biāo)

本章首先介紹了存儲(chǔ)管理的研究對(duì)象和目的，明確了存儲(chǔ)管理的基本功能和有關(guān)的基本概念；然后從實(shí)存和虛存兩個(gè)角度，分別介紹了常用的幾種存儲(chǔ)管理方案；最后對(duì)各種存儲(chǔ)管理方案存在的問(wèn)題，主要是碎片和抖動(dòng)問(wèn)題進(jìn)行了總結(jié)。

返回本章首頁(yè)本章學(xué)習(xí)目標(biāo)本章首先介紹了存儲(chǔ)管理的研究對(duì)象和目的，明確了本章的主要內(nèi)容如下：(1)存儲(chǔ)管理的目的和四大基本功能。

(2)實(shí)存管理中講述了固定分區(qū)存儲(chǔ)管理、可變式分區(qū)存儲(chǔ)管理、純分頁(yè)存儲(chǔ)管理三種存儲(chǔ)管理方案的實(shí)現(xiàn)原理(3)虛存管理以請(qǐng)求式分頁(yè)存儲(chǔ)管理為重點(diǎn)

(4)總結(jié)各種存儲(chǔ)管理方案中存在的碎片和抖動(dòng)問(wèn)題及解決方法下一頁(yè)本章的主要內(nèi)容如下：(1)存儲(chǔ)管理的目的和四大基本功能。下圖4.1多級(jí)存儲(chǔ)器體系示意圖圖4.1多級(jí)存儲(chǔ)器體系示意圖4.1存儲(chǔ)管理的功能4.1.1內(nèi)存的分配與回收

4.1.2地址重定位4.1.3存儲(chǔ)保護(hù)

4.1.4虛擬存儲(chǔ)器

返回本章首頁(yè)4.1存儲(chǔ)管理的功能4.1.1內(nèi)存的分配與回收返4.1.1內(nèi)存的分配與回收內(nèi)存分配按分配時(shí)機(jī)的不同，可分為兩種方式。（1）靜態(tài)存儲(chǔ)分配：指內(nèi)存分配是在作業(yè)運(yùn)行之前各目標(biāo)模塊連接后，把整個(gè)作業(yè)一次性全部裝入內(nèi)存，并在作業(yè)的整個(gè)運(yùn)行過(guò)程中，不允許作業(yè)再申請(qǐng)其他內(nèi)存，或在內(nèi)存中移動(dòng)位置。也就是說(shuō)，內(nèi)存分配是在作業(yè)運(yùn)行前一次性完成的。（2）動(dòng)態(tài)存儲(chǔ)分配：作業(yè)要求的基本內(nèi)存空間是在目標(biāo)模塊裝入內(nèi)存時(shí)分配的，但在作業(yè)運(yùn)行過(guò)程中，允許作業(yè)申請(qǐng)附加的內(nèi)存空間，或是在內(nèi)存中移動(dòng)，即分配工作可以在作業(yè)運(yùn)行前及運(yùn)行過(guò)程中逐步完成。返回本節(jié)4.1.1內(nèi)存的分配與回收內(nèi)存分配按分配時(shí)機(jī)的不同，可4.1.2地址重定位1．內(nèi)存空間（或物理空間）2．邏輯空間3．地址重定位下一頁(yè)4.1.2地址重定位1．內(nèi)存空間（或物理空間）下一頁(yè)1．內(nèi)存空間（或物理空間）內(nèi)存是由若干個(gè)存儲(chǔ)單元組成的，每個(gè)存儲(chǔ)單元有一個(gè)編號(hào)，這種編號(hào)可唯一標(biāo)識(shí)一個(gè)存儲(chǔ)單元，稱為內(nèi)存地址（或物理地址）。下一頁(yè)1．內(nèi)存空間（或物理空間）內(nèi)存是由若干個(gè)存儲(chǔ)單元組成的，每個(gè)2．邏輯空間源程序經(jīng)過(guò)匯編或編譯后，形成目標(biāo)程序，每個(gè)目標(biāo)程序都是以0為基址順序進(jìn)行編址的，原來(lái)用符號(hào)名訪問(wèn)的單元用具體的數(shù)據(jù)——單元號(hào)取代。這樣生成的目標(biāo)程序占據(jù)一定的地址空間，稱為作業(yè)的邏輯地址空間，簡(jiǎn)稱邏輯空間。在邏輯空間中每條指令的地址和指令中要訪問(wèn)的操作數(shù)地址統(tǒng)稱為邏輯地址。下一頁(yè)2．邏輯空間源程序經(jīng)過(guò)匯編或編譯后，形成目標(biāo)程序，每個(gè)目標(biāo)程圖4.2作業(yè)的名空間、邏輯地址空間和裝入后的物理空間下一頁(yè)圖4.2作業(yè)的名空間、邏輯地址空間和裝入后的物理空間下一3．地址重定位(1)靜態(tài)地址重定位靜態(tài)地址重定位是在程序執(zhí)行之前由操作系統(tǒng)的重定位裝入程序完成的。(2)動(dòng)態(tài)地址重定位

動(dòng)態(tài)地址重定位是在程序執(zhí)行期間進(jìn)行的。

下一頁(yè)3．地址重定位(1)靜態(tài)地址重定位下一頁(yè)（b）采用動(dòng)態(tài)重定位時(shí)內(nèi)存空間及地址重定位示意圖（a）采用靜態(tài)重定位后的內(nèi)存空間圖4.3靜態(tài)地址重定位和動(dòng)態(tài)地址重定位示意圖返回本節(jié)（b）采用動(dòng)態(tài)重定位時(shí)內(nèi)存空間及地址重定位示意圖（a）采用4.1.3存儲(chǔ)保護(hù)（1）上、下界存儲(chǔ)保護(hù)：上、下界保護(hù)是一種簡(jiǎn)單的存儲(chǔ)保護(hù)技術(shù)。系統(tǒng)可為每個(gè)作業(yè)設(shè)置一對(duì)上、下界寄存器，分別用來(lái)存放當(dāng)前運(yùn)行作業(yè)在內(nèi)存空間的上、下邊界地址，用它們來(lái)限制用戶程序的活動(dòng)范圍。

（2）基址—限長(zhǎng)存儲(chǔ)保護(hù)：上、下界保護(hù)的一個(gè)變種是采用基址—限長(zhǎng)存儲(chǔ)保護(hù)。

4.1.3存儲(chǔ)保護(hù)（1）上、下界存儲(chǔ)保護(hù)：上、下界保護(hù)圖4.4界限寄存器的兩種存儲(chǔ)保護(hù)方式返回本節(jié)圖4.4界限寄存器的兩種存儲(chǔ)保護(hù)方式返回本節(jié)4.1.4虛擬存儲(chǔ)器對(duì)內(nèi)存進(jìn)行邏輯上的擴(kuò)充，現(xiàn)在普遍采用虛擬存儲(chǔ)管理技術(shù)。

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

返回本節(jié)4.1.4虛擬存儲(chǔ)器對(duì)內(nèi)存進(jìn)行邏輯上的擴(kuò)充，現(xiàn)在普遍采4.2實(shí)存管理4.2.1固定分區(qū)存儲(chǔ)管理

4.2.2可變式分區(qū)存儲(chǔ)管理4.2.3純分頁(yè)存儲(chǔ)管理

返回本章首頁(yè)4.2實(shí)存管理4.2.1固定分區(qū)存儲(chǔ)管理返回本章4.2.1固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理是實(shí)現(xiàn)多道程序設(shè)計(jì)的最簡(jiǎn)單的一種存儲(chǔ)管理技術(shù)。其基本思想是，在作業(yè)未進(jìn)入內(nèi)存之前，就由操作員或操作系統(tǒng)把內(nèi)存可用空間劃分成若干個(gè)固定大小的存儲(chǔ)區(qū)，除操作系統(tǒng)占用一個(gè)區(qū)域外，其余區(qū)域?yàn)橄到y(tǒng)中多個(gè)用戶共享，因?yàn)樵谙到y(tǒng)運(yùn)行期間，分區(qū)大小、數(shù)目都不變，所以固定式分區(qū)也稱為靜態(tài)分區(qū)。4.2.1固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理是實(shí)現(xiàn)多道程圖4.5固定式分區(qū)內(nèi)存分配示意圖（a）和（b）固定式分區(qū)說(shuō)明表返回本節(jié)圖4.5固定式分區(qū)內(nèi)存分配示意圖（a）和（b）固定式分區(qū)4.2.2可變式分區(qū)存儲(chǔ)管理1．空閑分區(qū)的組織形式

2．內(nèi)存的分配與回收

3．常用的分配算法

4．可變式分區(qū)的地址重定位

下一頁(yè)4.2.2可變式分區(qū)存儲(chǔ)管理1．空閑分區(qū)的組織形式下圖4.6可變式分區(qū)內(nèi)存使用情況示意圖下一頁(yè)圖4.6可變式分區(qū)內(nèi)存使用情況示意圖下一頁(yè)1．空閑分區(qū)的組織形式空閑分區(qū)鏈表的組織是這樣的：在每個(gè)空閑分區(qū)的起始部分開(kāi)辟出一個(gè)單元，存放一個(gè)鏈表指針和該分區(qū)的大小，鏈表指針指向下一個(gè)空閑分區(qū)。系統(tǒng)中用一個(gè)固定單元作為空閑分區(qū)鏈表的鏈表頭指針，指向第一塊空閑分區(qū)首地址，最后一塊空閑分區(qū)的鏈表指針存放鏈尾標(biāo)志。如圖4.7（a）所示。下一頁(yè)1．空閑分區(qū)的組織形式空閑分區(qū)鏈表的組織是這樣的：在每個(gè)空2．內(nèi)存的分配與回收當(dāng)某一個(gè)用戶作業(yè)完成釋放所占分區(qū)時(shí)，系統(tǒng)應(yīng)進(jìn)行回收。在可變式分區(qū)中，應(yīng)該檢查回收區(qū)與內(nèi)存中前后空閑區(qū)是否相鄰，若相鄰，則應(yīng)進(jìn)行合并，形成一個(gè)較大的空閑區(qū)，并對(duì)相應(yīng)的鏈表指針進(jìn)行修改；若不相鄰，應(yīng)將空閑區(qū)插入到空閑區(qū)鏈表的適當(dāng)位置。

下一頁(yè)2．內(nèi)存的分配與回收當(dāng)某一個(gè)用戶作業(yè)完成釋放所占分區(qū)時(shí)，系圖4.7首次適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)圖4.7首次適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)3．常用的分配算法（1）首次適應(yīng)算法

（2）最佳適應(yīng)算法

（3）最差適應(yīng)算法

下一頁(yè)3．常用的分配算法（1）首次適應(yīng)算法下一頁(yè)圖4.8最佳適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)圖4.8最佳適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)圖4.9最差適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)圖4.9最差適應(yīng)算法的空閑分區(qū)鏈表組織形式下一頁(yè)圖4.10內(nèi)存使用情況下一頁(yè)圖4.10內(nèi)存使用情況下一頁(yè)圖4.11用三種適應(yīng)算法處理同一作業(yè)序列下一頁(yè)圖4.11用三種適應(yīng)算法處理同一作業(yè)序列下一頁(yè)4．可變式分區(qū)的地址重定位可變式分區(qū)的地址重定位可采用靜態(tài)重定位，也可采用動(dòng)態(tài)重定位。如采用靜態(tài)重定位，因用戶作業(yè)進(jìn)入內(nèi)存后，程序的邏輯地址實(shí)現(xiàn)了重定位，不能在內(nèi)存中再進(jìn)行移動(dòng)，經(jīng)過(guò)一段時(shí)間的運(yùn)行，內(nèi)存中不能再分配利用的小碎片會(huì)越來(lái)越多。有時(shí)可能會(huì)出現(xiàn)這種情況，即當(dāng)一個(gè)作業(yè)申請(qǐng)一定數(shù)量的內(nèi)存時(shí)，雖然此時(shí)空閑區(qū)的總和大于新作業(yè)的內(nèi)存要求，但卻沒(méi)有單個(gè)的空閑區(qū)足以裝下該作業(yè)。采用動(dòng)態(tài)重定位的可變式分區(qū)管理技術(shù)，在執(zhí)行內(nèi)存分配時(shí)，如無(wú)足夠大空閑塊，應(yīng)考慮實(shí)現(xiàn)緊湊操作。其分配算法如圖4.12所示

。

下一頁(yè)4．可變式分區(qū)的地址重定位可變式分區(qū)的地址重定位可采用靜態(tài)圖4.12采用動(dòng)態(tài)重定位的可變式分區(qū)分配算法返回本節(jié)圖4.12采用動(dòng)態(tài)重定位的可變式分區(qū)分配算法返回本節(jié)4.2.3純分頁(yè)存儲(chǔ)管理1．純分頁(yè)存儲(chǔ)管理中存儲(chǔ)塊的分配與回收

2．純分頁(yè)存儲(chǔ)管理的地址重定位問(wèn)題3．聯(lián)想存儲(chǔ)器

4．存儲(chǔ)保護(hù)

下一頁(yè)4.2.3純分頁(yè)存儲(chǔ)管理1．純分頁(yè)存儲(chǔ)管理中存儲(chǔ)塊的分1．純分頁(yè)存儲(chǔ)管理中存儲(chǔ)塊的分配與回收通常有兩種記錄空閑存儲(chǔ)塊的方法：位圖法和鏈表法。（a）存儲(chǔ)塊使用情況（b）存儲(chǔ)塊使用情況的位圖表示圖4-13存儲(chǔ)塊的位圖管理法1．純分頁(yè)存儲(chǔ)管理中存儲(chǔ)塊的分配與回收通常有兩種記錄空閑存2．純分頁(yè)存儲(chǔ)管理的地址重定位問(wèn)題純分頁(yè)存儲(chǔ)管理中的地址重定位是非常重要的，要使不連續(xù)的、分散的用戶程序能正常運(yùn)行，須采用動(dòng)態(tài)地址重定位。此時(shí)，可采用重定位寄存器方式，如分頁(yè)太多，則重定位寄存器用得太多。通?？稍趦?nèi)存中為每個(gè)作業(yè)開(kāi)辟一塊特定區(qū)域，建立起作業(yè)的邏輯頁(yè)與存儲(chǔ)塊之間的對(duì)應(yīng)表格關(guān)系，這種表常稱為頁(yè)面映象表，簡(jiǎn)稱頁(yè)表。

下一頁(yè)2．純分頁(yè)存儲(chǔ)管理的地址重定位問(wèn)題純分頁(yè)存儲(chǔ)管理中的地址重圖4.14純分頁(yè)存儲(chǔ)管理示意圖下一頁(yè)圖4.14純分頁(yè)存儲(chǔ)管理示意圖下一頁(yè)3．聯(lián)想存儲(chǔ)器從上面介紹的地址變換過(guò)程可以看出：如果把頁(yè)表全部放在內(nèi)存，那么存取一個(gè)數(shù)據(jù)時(shí)，至少要訪問(wèn)二次內(nèi)存。一次是訪問(wèn)頁(yè)表，形成實(shí)際內(nèi)存地址；另一次是根據(jù)形成的內(nèi)存地址存取數(shù)據(jù)。顯然，這比通常執(zhí)行指令的速度要慢得多，使計(jì)算機(jī)的運(yùn)行速度幾乎降低一半。應(yīng)用聯(lián)想存儲(chǔ)器和頁(yè)表相結(jié)合的方式，可有效地提高系統(tǒng)動(dòng)態(tài)地址轉(zhuǎn)換的速度，是一種行之有效的方法。下一頁(yè)3．聯(lián)想存儲(chǔ)器從上面介紹的地址變換過(guò)程可以看出：如果把頁(yè)表圖4.15純分頁(yè)存儲(chǔ)管理地址重定位實(shí)現(xiàn)過(guò)程下一頁(yè)圖4.15純分頁(yè)存儲(chǔ)管理地址重定位實(shí)現(xiàn)過(guò)程下一頁(yè)圖4.16采用快表和頁(yè)表相結(jié)合的分頁(yè)地址變換過(guò)程示意圖下一頁(yè)圖4.16采用快表和頁(yè)表相結(jié)合的分頁(yè)地址變換過(guò)程示意圖下4．存儲(chǔ)保護(hù)四種保護(hù)方式：①禁止做任何操作，②只能執(zhí)行，③只能讀，④能讀/寫，當(dāng)要訪問(wèn)某頁(yè)時(shí)，先判斷該頁(yè)的存取控制和存儲(chǔ)保護(hù)信息是否允許。添加了存取控制信息的頁(yè)表表目如下圖所示：

返回本節(jié)4．存儲(chǔ)保護(hù)四種保護(hù)方式：①禁止做任何操作，②只能執(zhí)行，③4.3虛擬存儲(chǔ)器管理4.3.1虛擬存儲(chǔ)器的概念

4.3.2請(qǐng)求式分頁(yè)存儲(chǔ)管理與動(dòng)態(tài)地址重定位

4.3.3現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動(dòng)態(tài)地址重定位

4.3.4頁(yè)面置換算法

4.3.5請(qǐng)求式分頁(yè)存儲(chǔ)管理性能分析舉例

4.3.6請(qǐng)求式分段存儲(chǔ)管理

返回本章首頁(yè)4.3虛擬存儲(chǔ)器管理4.3.1虛擬存儲(chǔ)器的概念返4.3.1虛擬存儲(chǔ)器的概念（1）程序中往往會(huì)有一些彼此互斥的部分。（2）在一個(gè)完整的程序中，會(huì)有一些諸如出錯(cuò)處理這樣的子程序，在作業(yè)正常運(yùn)行情況下不會(huì)執(zhí)行這些程序，沒(méi)有必要把它們調(diào)入內(nèi)存?；诔绦蚓植啃栽砗蜕鲜銮闆r，就沒(méi)有必要把一個(gè)作業(yè)一次性全部裝入內(nèi)存再開(kāi)始運(yùn)行。而是可以把程序當(dāng)前執(zhí)行所涉及的信息放入內(nèi)存中，其余部分可根據(jù)需要臨時(shí)調(diào)入，由操作系統(tǒng)和硬件相配合來(lái)完成主存和輔存之間信息的動(dòng)態(tài)調(diào)度。這樣的計(jì)算機(jī)系統(tǒng)好像為用戶提供了一個(gè)存儲(chǔ)容量比實(shí)際主存大得多的存儲(chǔ)器，就稱為虛擬存儲(chǔ)器。

返回本節(jié)4.3.1虛擬存儲(chǔ)器的概念（1）程序中往往會(huì)有一些彼此4.3.2請(qǐng)求式分頁(yè)存儲(chǔ)管理與動(dòng)態(tài)地址重定位請(qǐng)求式分頁(yè)存儲(chǔ)管理與純分頁(yè)存儲(chǔ)管理在內(nèi)存塊的分配與回收，存儲(chǔ)保護(hù)某方面都十分相似，不同之處在于地址重定位問(wèn)題。在請(qǐng)求式分頁(yè)存儲(chǔ)管理的地址重定位時(shí)，可能會(huì)出現(xiàn)所需頁(yè)面不在主存的情況，此時(shí)，系統(tǒng)必須解決以下兩個(gè)問(wèn)題：（1）當(dāng)程序要訪問(wèn)的某頁(yè)不在內(nèi)存時(shí)，如何發(fā)現(xiàn)這種缺頁(yè)情況？發(fā)現(xiàn)后應(yīng)如何處理？（2）當(dāng)需要把外存上的某個(gè)頁(yè)面調(diào)入內(nèi)存時(shí)，此時(shí)內(nèi)存中沒(méi)有空閑塊應(yīng)怎么辦？下一頁(yè)4.3.2請(qǐng)求式分頁(yè)存儲(chǔ)管理與動(dòng)態(tài)地址重定位請(qǐng)求式分頁(yè)如圖4.17所示是請(qǐng)求式分頁(yè)存儲(chǔ)管理的存儲(chǔ)映像下一頁(yè)如圖4.17所示是請(qǐng)求式分頁(yè)存儲(chǔ)管理的存儲(chǔ)映像下一頁(yè)為了幫助操作系統(tǒng)對(duì)要置換出內(nèi)存的頁(yè)面進(jìn)行選擇，在頁(yè)表中還可以增加一個(gè)引用位，以反映該頁(yè)最近的使用情況。一般來(lái)說(shuō)，一個(gè)頁(yè)表的表目通?？砂ㄈ缦碌臄?shù)據(jù)內(nèi)容：下一頁(yè)為了幫助操作系統(tǒng)對(duì)要置換出內(nèi)存的頁(yè)面進(jìn)行選擇，在頁(yè)表中還可以請(qǐng)求式分頁(yè)存儲(chǔ)管理中的地址重定位和缺頁(yè)中斷處理過(guò)程如圖4.18所示。返回本節(jié)請(qǐng)求式分頁(yè)存儲(chǔ)管理中的地址重定位和缺頁(yè)中斷處理過(guò)程如圖4.14.3.3現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動(dòng)態(tài)地址重定位（1）如何合理地組織管理相當(dāng)大的頁(yè)表？在WindowsNT中，為解決第一個(gè)問(wèn)題，對(duì)頁(yè)表本身進(jìn)行了改進(jìn)，將龐大的頁(yè)表本身也采取分頁(yè)措施，采用了兩級(jí)頁(yè)表結(jié)構(gòu)。即把頁(yè)表本身按固定大小分成一個(gè)個(gè)小頁(yè)表，每個(gè)小頁(yè)表由210=1024個(gè)頁(yè)表表目構(gòu)成，每個(gè)表目占4字節(jié)，所以每個(gè)小頁(yè)表剛好占一個(gè)頁(yè)面（頁(yè)面大小為212=4kb）。一共有210=1k個(gè)小頁(yè)表。為了對(duì)這1k個(gè)小頁(yè)表進(jìn)行管理和索引查找，設(shè)置了一個(gè)頁(yè)表目錄，也稱之為頂級(jí)頁(yè)表或一級(jí)頁(yè)表，該頁(yè)目錄包含有1k個(gè)表目項(xiàng)，分別指出每個(gè)次級(jí)小頁(yè)表所在的物理塊號(hào)和其他有關(guān)狀態(tài)信息。這樣，每個(gè)作業(yè)有一個(gè)頁(yè)目錄（一級(jí)頁(yè)表），它的每個(gè)表目指向一個(gè)二級(jí)頁(yè)表。頁(yè)目錄本身也剛好是一個(gè)頁(yè)面大?。?10=1k，每個(gè)表目4個(gè)字節(jié)）。下一頁(yè)4.3.3現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動(dòng)態(tài)地址重定位（1）如何圖4.19WindowsNT兩級(jí)頁(yè)表地址變換示意圖下一頁(yè)圖4.19WindowsNT兩級(jí)頁(yè)表地址變換示意圖下一（2）面對(duì)大的頁(yè)表，地址的映射怎樣才能比較快地實(shí)現(xiàn)？（1）使用快表：即利用前面我們已介紹的高速緩沖存儲(chǔ)器來(lái)存放經(jīng)常使用的頁(yè)表表目，以提高頁(yè)表的查詢速度。（2）使用高速緩沖存儲(chǔ)器：在微處理器和主存之間設(shè)置32kb或64kb的高速緩沖存儲(chǔ)器，大部分的指令和數(shù)據(jù)取自高速緩存（命中率為98%），所以存取數(shù)據(jù)和指令速度相當(dāng)高，達(dá)到與處理器速度完全相匹配。返回本節(jié)（2）面對(duì)大的頁(yè)表，地址的映射怎樣才能比較快地實(shí)現(xiàn)？（1）4.3.4頁(yè)面置換算法1．最優(yōu)算法（OPT算法）2．先進(jìn)先出算法（FIFO算法）3．最久未使用頁(yè)面置換算法（LRU算法）4．LRU近似算法下一頁(yè)4.3.4頁(yè)面置換算法1．最優(yōu)算法（OPT算法）下一頁(yè)1．最優(yōu)算法（OPT算法）最理想的頁(yè)面置換算法是：從內(nèi)存中移出以后不再使用的頁(yè)面；如無(wú)這樣的頁(yè)面，則選擇以后最長(zhǎng)時(shí)間內(nèi)不需要訪問(wèn)的頁(yè)。這就是最優(yōu)算法的思想。這種算法本身不是一種實(shí)際的方法，因?yàn)轫?yè)面訪問(wèn)的順序是很難預(yù)知的。但是，可把它作為一種評(píng)價(jià)標(biāo)準(zhǔn)，比較其他實(shí)用方法的優(yōu)劣，所以，最優(yōu)算法只具有理論上的意義。下一頁(yè)1．最優(yōu)算法（OPT算法）最理想的頁(yè)面置換算法是：從內(nèi)存中移2．先進(jìn)先出算法（FIFO算法）這種算法的基本思想是：總是先淘汰那些駐留在內(nèi)存時(shí)間最長(zhǎng)的頁(yè)面，即先進(jìn)入內(nèi)存的頁(yè)面先被置換掉。理由是：最先進(jìn)入內(nèi)存的頁(yè)面不再被訪問(wèn)的可能性最大。

下一頁(yè)2．先進(jìn)先出算法（FIFO算法）這種算法的基本思想是：總是先圖4.20先進(jìn)先出算法存儲(chǔ)分塊表構(gòu)造下一頁(yè)圖4.20先進(jìn)先出算法存儲(chǔ)分塊表構(gòu)造下一頁(yè)3．最久未使用頁(yè)面置換算法（LRU算法）這種算法的基本思想是，如果某一頁(yè)被訪問(wèn)了，那么它很可能馬上又被訪問(wèn)；反之，如果某一頁(yè)很長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)，那么最近也不太可能會(huì)被訪問(wèn)。這種算法考慮了程序設(shè)計(jì)的局部性原理。其實(shí)質(zhì)是，當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間最久未使用的頁(yè)面予以淘汰。實(shí)現(xiàn)這種算法可通過(guò)周期性地對(duì)“引用位”進(jìn)行檢查，并利用它來(lái)記錄一頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t，淘汰時(shí)選擇t最大的頁(yè)面。

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

下一頁(yè)4．LRU近似算法這種算法，只要在存儲(chǔ)分塊表（或頁(yè)表）中設(shè)一圖4.21LRU近似算法下一頁(yè)圖4.21LRU近似算法下一頁(yè)圖4.22LRU近似算法舉例返回本節(jié)圖4.22LRU近似算法舉例返回本節(jié)4.3.5請(qǐng)求式分頁(yè)存儲(chǔ)管理性能分析舉例1．程序設(shè)計(jì)的質(zhì)量2．頁(yè)面的大小3．分配的內(nèi)存塊數(shù)4．頁(yè)面置換算法性能下一頁(yè)4.3.5請(qǐng)求式分頁(yè)存儲(chǔ)管理性能分析舉例1．程序設(shè)計(jì)的【例1】主存塊數(shù)m=3，置換算法采用FIFO算法，缺頁(yè)中斷次數(shù)及缺頁(yè)率如圖4.23所示。在圖4.23中，P行表示頁(yè)面走向，M行表示在主存中的頁(yè)面號(hào)，其中帶有+的表示新調(diào)入頁(yè)面，在M行的各列按調(diào)入的順序排列，帶有圓圈的數(shù)字表示下一時(shí)刻將