第五章存儲(chǔ)管理

第五章存儲(chǔ)管理存儲(chǔ)管理的目的：1、為用戶使用存儲(chǔ)器提供方便。使用戶使用計(jì)算機(jī)的過程不考慮存儲(chǔ)器的申請(qǐng)、分配、保存、回收等問題，體現(xiàn)在以下方面：（1）每個(gè)用戶均以獨(dú)立方式編成，而不必關(guān)心其程序在存儲(chǔ)空間上的物理位置；（2）為用戶提供充分大的內(nèi)存空間。2、充分發(fā)揮內(nèi)存的利用率：既要為用戶程序分配足夠大的內(nèi)存空間，又不至于浪費(fèi)。3、擴(kuò)充內(nèi)存容量的方法：物理擴(kuò)充與邏輯擴(kuò)充4、信息保護(hù)：市內(nèi)存中的數(shù)據(jù)不被非法修改。5.1存儲(chǔ)管理的功能一、虛擬存儲(chǔ)器基本思想：利用大容量的外存空間來邏輯擴(kuò)充內(nèi)存，使得產(chǎn)生一個(gè)不受實(shí)際內(nèi)存容量大小限制的邏輯的虛擬存儲(chǔ)器，以便充分發(fā)揮內(nèi)存利用率，使系統(tǒng)有效地支持多道程序的并發(fā)執(zhí)行以及解除對(duì)用戶作業(yè)大小的限制。

1、虛擬存儲(chǔ)器實(shí)現(xiàn)的可能性（1）現(xiàn)代計(jì)算機(jī)系統(tǒng)的物理存儲(chǔ)器分成內(nèi)存和外存。因內(nèi)存價(jià)格昂貴，不可能用大容量的內(nèi)存來存儲(chǔ)所有被訪問的或暫時(shí)不被訪問的程序和數(shù)據(jù)，而外存價(jià)格低，適于存儲(chǔ)大量的信息。（2）程序執(zhí)行的局部性原理（3）編譯、鏈接通常由用戶編寫的源程序，首先要有編譯程序編譯成可執(zhí)行代碼，然后，由鏈接程序把一個(gè)進(jìn)程的不同程序段連接起來以完成要求的功能。顯然，對(duì)于不同的程序段，應(yīng)具有不同的地址。

a、物理地址：物理存儲(chǔ)器中存儲(chǔ)單元的編號(hào)。優(yōu)點(diǎn)：速度快；缺點(diǎn)：影響并發(fā)執(zhí)行的進(jìn)程數(shù)；大進(jìn)程無法運(yùn)行。

b、編譯鏈接程序?qū)⒂脩暨M(jìn)程編譯鏈接到一個(gè)以0位始址的線性或多維地址空間。靜態(tài)鏈接：在程序執(zhí)行前由鏈接程序?qū)M(jìn)程所含目標(biāo)代碼進(jìn)行連接；動(dòng)態(tài)鏈接：在程序執(zhí)行過程中根據(jù)需要而進(jìn)行的連接。虛擬存儲(chǔ)器（P106第一行）：將進(jìn)程中的目標(biāo)代碼、數(shù)據(jù)等的虛擬地址組成的虛擬空間稱為虛擬存儲(chǔ)器。虛擬地址（邏輯地址）物理地址（4）地址變換：由邏輯地址向物理地址的轉(zhuǎn)換過程。二、地址變換(P106)

內(nèi)存空間（物理地址空間）：內(nèi)存地址的集合。虛擬空間的劃分：使編譯鏈接程序可以把不同的程序模塊連接到一個(gè)統(tǒng)一的虛擬空間。地址重定位：把虛擬空間中已鏈接和劃分好的內(nèi)容裝入內(nèi)存，并將虛擬地址映射為內(nèi)存地址的過程叫地址重定位或地址映射。1、靜態(tài)地址重定位（P107）(1)方法：是在虛擬空間中程序執(zhí)行之前由OS的重定位裝入程序完成地址映射工作。(2)特點(diǎn)：優(yōu)點(diǎn)：不需要硬件支持缺點(diǎn)：①使用靜態(tài)重定位法進(jìn)行地址變換無法實(shí)現(xiàn)虛擬存貯器，因靜態(tài)重定位將程序一旦裝入內(nèi)存之后不能再移動(dòng)，并且必須在程序執(zhí)行之前將有關(guān)部分全部裝入。②進(jìn)程必須占用連續(xù)的內(nèi)存空間，難實(shí)現(xiàn)數(shù)據(jù)共享。2、動(dòng)態(tài)地址重定位：（1）方法：在程序執(zhí)行過程中，在CPU訪問內(nèi)存之前，將要訪問的程序或數(shù)據(jù)地址變成內(nèi)存地址，動(dòng)態(tài)重定位依靠硬件地址變換機(jī)構(gòu)完成。（2）動(dòng)態(tài)地址重定位機(jī)構(gòu)基地址寄存器BR（始址）、虛地址寄存器

VR偏移）則：內(nèi)存地址MAMA=（BR）+（VR）（3）址映射過程：①設(shè)置基地址寄存器BR，虛地址寄存器VR②將程序段裝入內(nèi)存，將其占用的區(qū)域的首地址送BR；③在程序執(zhí)行過程中，將要訪問的虛地址送入VR中；④地址變換機(jī)構(gòu)把VR和BR的內(nèi)容相加，得訪問的物理地址（4）動(dòng)態(tài)重定位優(yōu)點(diǎn)：①可以對(duì)內(nèi)存進(jìn)行非連續(xù)分配②動(dòng)態(tài)重定位提供了實(shí)現(xiàn)虛擬存貯器的基礎(chǔ)③有利于程序段共享三、內(nèi)外存數(shù)據(jù)傳輸?shù)目刂?P108)（1）把即將執(zhí)行的程序和數(shù)據(jù)段調(diào)入內(nèi)存；（2）把處于等待狀態(tài)的程序、數(shù)據(jù)段調(diào)出內(nèi)存，為此目的，有兩種方法實(shí)現(xiàn)內(nèi)存與外存間的控制即覆蓋與交換。1、覆蓋（overlay）：由用戶程序自己控制內(nèi)外存之間的數(shù)據(jù)交換，它要求用戶清楚了解程序的結(jié)構(gòu)，并指定各程序段調(diào)入內(nèi)存的先后次序。2、交換（swapping）：包括換進(jìn)與換出，它是指由操作系統(tǒng)把那些在內(nèi)存中處于等待狀態(tài)的進(jìn)程換出內(nèi)存，以及把那些等待事件已經(jīng)發(fā)生，處于就緒態(tài)的進(jìn)程換入內(nèi)存，以及那些即將執(zhí)行的程序數(shù)據(jù)調(diào)入內(nèi)存。3、請(qǐng)求調(diào)入方式：在程序執(zhí)行時(shí)，如訪問的程序段或數(shù)據(jù)段不在內(nèi)存中，則操作系統(tǒng)自動(dòng)地從外存將有關(guān)程序、數(shù)據(jù)調(diào)入內(nèi)存。4、預(yù)調(diào)入方式：由OS預(yù)測(cè)在不遠(yuǎn)的將來會(huì)訪問到的那些程序、數(shù)據(jù)部分，并在他們被訪問之前由系統(tǒng)選擇適當(dāng)?shù)臅r(shí)機(jī)將它們調(diào)入內(nèi)存的方法。5、區(qū)分交換與覆蓋：（1）交換不需要程序員給出程序、數(shù)據(jù)段的交換方法、過程，而覆蓋要求明確給出程序段之間的覆蓋結(jié)構(gòu)（2）交換主要是在進(jìn)程之間進(jìn)行，而覆蓋主要是在一個(gè)進(jìn)程內(nèi)或一個(gè)作業(yè)內(nèi)進(jìn)行，同時(shí)覆蓋程序段與被覆蓋程序段是無關(guān)的。6、

區(qū)分請(qǐng)求式調(diào)入與預(yù)調(diào)入（1）二者一般是在一個(gè)進(jìn)程內(nèi)的不同程序段、數(shù)據(jù)段間進(jìn)行；（2）請(qǐng)求式調(diào)入命中率為100%，但程序執(zhí)行速度慢，預(yù)調(diào)方式命中率≤100%四、內(nèi)存分配與回收1、任務(wù)：存貯管理模塊為每一個(gè)并發(fā)執(zhí)行的進(jìn)程分配內(nèi)存空間，另外，當(dāng)進(jìn)程執(zhí)行結(jié)束后，存貯管理模塊又要及時(shí)回收該進(jìn)程所使用的內(nèi)存資源，以便給其他進(jìn)程分配本內(nèi)存。2、設(shè)計(jì)內(nèi)存分配和回收方法時(shí)，要考慮的策略及數(shù)據(jù)結(jié)構(gòu)如下：（1）分配結(jié)構(gòu)：空閑區(qū)表、空閑區(qū)隊(duì)列（鏈）（2）放置策略：選擇空閑區(qū)方法（3）交換策略（4）調(diào)入策略（5）回收策略五、內(nèi)存信息的共享和保護(hù)內(nèi)存信息共享內(nèi)存保護(hù)常用的內(nèi)存信息保護(hù)方式：1、

上下界保護(hù)法：方法：為每個(gè)進(jìn)程設(shè)置一對(duì)上下界寄存器，存貯被保護(hù)程序和數(shù)據(jù)段的起始地址和終止地址。程序執(zhí)行過程中，在對(duì)內(nèi)存進(jìn)行訪問操作時(shí)進(jìn)行地址合法性檢查，即檢查經(jīng)過重定位后的內(nèi)存地址是否在上下界寄存器所規(guī)定范圍內(nèi)。若在規(guī)定范圍內(nèi)，則訪問是合法的。否則是非法的，并產(chǎn)生訪地越界中斷。2、保護(hù)鍵法：方法：為每一個(gè)被保護(hù)存貯塊分配一個(gè)單獨(dú)的保護(hù)鍵。在程序狀態(tài)字中設(shè)置相應(yīng)的保護(hù)鍵開關(guān)字段，對(duì)不同進(jìn)程賦予不同的開關(guān)代碼，與保護(hù)的存貯塊中的保護(hù)鍵匹配，保護(hù)鍵可設(shè)置成對(duì)RW同時(shí)進(jìn)行保護(hù)或只對(duì)R、W進(jìn)行單獨(dú)保護(hù)的。如果開關(guān)字與保護(hù)鍵匹配或存貯塊未受到保護(hù)，則訪問該存貯塊是允許的，否則產(chǎn)生訪問出錯(cuò)中斷。3、界限寄存器與CPU的用戶態(tài)或核態(tài)工作方式相結(jié)合的保護(hù)方式，在這種方式下，用戶態(tài)進(jìn)程只能訪問那些在界限寄存器所規(guī)定范圍內(nèi)的內(nèi)存部分，而核心態(tài)進(jìn)程則可以訪問整個(gè)內(nèi)存區(qū)域。內(nèi)存空間：由若干存儲(chǔ)單元組成的，每個(gè)存貯單元有一編號(hào)，這一編號(hào)可唯一標(biāo)識(shí)一個(gè)存貯單元，稱內(nèi)存地址。邏輯空間：源程序經(jīng)過匯編或編譯后，形成目標(biāo)程序，每個(gè)目標(biāo)程序均以0為基址順序進(jìn)行編址，原來用符號(hào)名訪問的單元用數(shù)據(jù)——單元號(hào)取代，這樣生成的目標(biāo)程序占據(jù)一定的地址空間，稱為作業(yè)的邏輯地址空間。

5.2分區(qū)存貯管理一、分區(qū)管理的基本原理：給內(nèi)存中的每一個(gè)進(jìn)程劃分一塊適當(dāng)大小的存貯區(qū)，以連續(xù)存放各進(jìn)程的程序與數(shù)據(jù)，使各進(jìn)程得以并發(fā)執(zhí)行。1、固定分區(qū)法：（也稱靜態(tài)分區(qū)管理）（1）方法：將內(nèi)存區(qū)域固定地劃分為若干大小不等的區(qū)域，分區(qū)劃分的原則由系統(tǒng)操作員或OS決定。（2）數(shù)據(jù)結(jié)構(gòu)——PPT（partitiondescribetable)

分區(qū)說明表（3）特點(diǎn)每個(gè)分區(qū)在表中對(duì)應(yīng)一個(gè)表目（行），表目?jī)?nèi)容包括區(qū)號(hào)、大小、起始地址，使用狀態(tài)等。2、

動(dòng)態(tài)分區(qū)法：（可變分區(qū)管理）（1）方法：作業(yè)執(zhí)行前不建立分區(qū)，分區(qū)的建立是在作業(yè)的處理過程中進(jìn)行的，且其大小可隨作業(yè)或進(jìn)程對(duì)內(nèi)存的要求而改變，（2）數(shù)據(jù)結(jié)構(gòu)：（分區(qū)說明表）(P112)①可用表②自由表③請(qǐng)求表二、分區(qū)的分配與回收：1、

固定分區(qū)時(shí)的分配與回收、（1）分配：當(dāng)用戶程序要裝入執(zhí)行時(shí)，通過請(qǐng)求表提出內(nèi)存分配要求和所要求的內(nèi)存空間大小，存貯管理程序根據(jù)請(qǐng)求查詢分區(qū)說明表，從中找出一個(gè)滿足要求的空閑分區(qū)，并將其分配給申請(qǐng)者。分配算法如圖5.102、

動(dòng)態(tài)分區(qū)的分配與回收（1）動(dòng)態(tài)分配與回收要解決以下三個(gè)問題：①對(duì)于請(qǐng)求表中的要求內(nèi)存長(zhǎng)度，從可用分區(qū)表或自鏈中尋找出合適的空閑區(qū)進(jìn)行分配。②分配空閑區(qū)之后，更新可用表或自由鏈。③進(jìn)程或作業(yè)釋放內(nèi)存資源時(shí)，各相鄰的空閑區(qū)進(jìn)行鏈接合并，更新可用分區(qū)表或自由鏈。（2）常用的三種分配算法：

A、

最先適應(yīng)算法：（FFA）

①可用分區(qū)表或自由鏈的組織：按起始地址遞增的次序?qū)⒖捎梅謪^(qū)或自由鏈排列起來。②分配：從頭搜索可用分區(qū)表或自由鏈，一旦找到大于或等于所要求內(nèi)存長(zhǎng)度的分區(qū)，則結(jié)束搜索。然后從所找到的分區(qū)中劃出所要求的內(nèi)存長(zhǎng)度分配給用戶進(jìn)程，并把余下的部分（進(jìn)行合并后）留在可用表中。③特點(diǎn)：內(nèi)存利用率低，易產(chǎn)生碎片算法實(shí)現(xiàn)簡(jiǎn)單，速度快。

B、最佳適應(yīng)算法：①可用分區(qū)組織：按空閑分區(qū)的從小到大次序組織可用分區(qū)表或自由鏈。②分配：當(dāng)用戶作業(yè)或進(jìn)程申請(qǐng)一個(gè)空閑分區(qū)時(shí)，存貯管理程序從表頭開始查找，當(dāng)找到第一個(gè)滿足要求的時(shí)，停止查找，如果該分區(qū)長(zhǎng)度大于請(qǐng)

求表中的請(qǐng)求長(zhǎng)度，則將減去請(qǐng)求長(zhǎng)度后的剩余空閑區(qū)部分留在可用表中③特點(diǎn)：優(yōu)點(diǎn)：自由分區(qū)表或可用鏈中尾部的空閑區(qū)容量大，便于大服務(wù)業(yè)運(yùn)行。缺點(diǎn)：更容易形成碎片。

C、最壞適應(yīng)算法：（MF）①空閑分區(qū)組織：按空閑分區(qū)容量從大到小次序組織可用表或自由鍵。②分配：當(dāng)用戶作業(yè)或進(jìn)程請(qǐng)求一個(gè)空閑區(qū)時(shí)，先檢查可用分區(qū)表或自由鏈的第一個(gè)空閑區(qū)的大小是否大于或等于所要求內(nèi)存長(zhǎng)度，若第一個(gè)的長(zhǎng)度小于分配請(qǐng)求，則分配失敗，否則從空閑區(qū)可用分區(qū)表或自由鏈中分配相應(yīng)的存貯空間給用戶，然后修改和調(diào)整空閑區(qū)可用表或自由鍵。③特點(diǎn)：優(yōu)——不易產(chǎn)生碎片

缺——大作業(yè)往往無法運(yùn)行。3、動(dòng)態(tài)分區(qū)時(shí)的回收與拼接可用分區(qū)拼接(P114)圖5.12(四種情形)

4、幾種分配算法的比較：從查找速度，釋放速度、空閑區(qū)利用三方面進(jìn)行比較（1）最先適應(yīng)算法：搜索速度，回收速度快，同時(shí)盡可能地利用了低地址空閑，保證了高地址端有較大的空閑區(qū)來放置要求內(nèi)存較多的進(jìn)程作業(yè)。（2）最佳適應(yīng)算法：找到的空閑區(qū)最佳（3）最壞適應(yīng)算法：克服了碎片問題，但大作業(yè)往往無法運(yùn)行。三、有關(guān)分區(qū)管理其他問題的討論：1、關(guān)于虛存的討論：在分區(qū)管理中，每個(gè)用戶進(jìn)程所需內(nèi)存容量是受分區(qū)大小限制的2、關(guān)于內(nèi)存擴(kuò)充所謂內(nèi)存擴(kuò)充，是指通過覆蓋或交換技術(shù)來擴(kuò)充內(nèi)存。3、關(guān)于地址變換和內(nèi)存保護(hù)。地址變換分：靜態(tài)地址重定位動(dòng)態(tài)地址重定位內(nèi)存保護(hù)4、

分區(qū)存貯管理的主要優(yōu)缺點(diǎn)：（1）優(yōu)點(diǎn)：①實(shí)現(xiàn)了多個(gè)服務(wù)業(yè)或進(jìn)程對(duì)內(nèi)存的共享，有助于多道程序設(shè)計(jì)，從而提高了系統(tǒng)資源的利用率②該方法要求的硬件支持少，管理算法簡(jiǎn)單（2）缺點(diǎn)：①內(nèi)存利用率仍然不高②作業(yè)或進(jìn)程的大小受分區(qū)大小控制，除非配合采用覆蓋和交換技術(shù)。③難以實(shí)現(xiàn)各分區(qū)間的信息共享。

5.3覆蓋與交換技術(shù)

一、覆蓋技術(shù)1、

概念：所謂覆蓋，指一內(nèi)存區(qū)可以被不同的程序段重復(fù)使用，當(dāng)某一程序段不再需要時(shí)，另一程序段可以占用它的位置，把可以在其上進(jìn)行覆蓋的內(nèi)存區(qū)域稱為“覆蓋區(qū)”，而可以相互覆蓋的程序?yàn)椤案采w”。2、基本思想：①程序的執(zhí)行具有局部性特征程序在CPU上執(zhí)行，在一個(gè)絕對(duì)時(shí)刻，CPU只能執(zhí)行一條指令，在一個(gè)相對(duì)較短的時(shí)間段內(nèi)，又只有一個(gè)和諧段被執(zhí)行。②程序的劃分：

由于程序的執(zhí)行具有局部性特征，因此在程序執(zhí)行前沒有必要將程序全部加載到內(nèi)存，而且只裝入一個(gè)或若干個(gè)程序段。為此，需將程序進(jìn)行劃分，將那些不會(huì)同時(shí)執(zhí)行的程序段共享同一內(nèi)存區(qū)①程序段的執(zhí)行與覆蓋：當(dāng)內(nèi)存中的程序段執(zhí)行結(jié)束，再將外存中它的后鍵程序段加載內(nèi)存，原來的程序段被覆蓋。3、覆蓋的實(shí)現(xiàn)要求：（1）要求程序員提供一個(gè)清楚的覆蓋結(jié)構(gòu)，搞清楚程序應(yīng)分為多少段，每段的前起后鍵各是什么。（2）要求程序員清楚了解程序所屬進(jìn)程的虛擬空間以及各程序段所在虛擬空間位置。（3）要求程序員了解系統(tǒng)和內(nèi)存的內(nèi)部結(jié)構(gòu)和地址劃分情況4、例（備課本）二、交換技術(shù)：1、概念：交換是指先將內(nèi)存某部分的程序或數(shù)據(jù)寫入外存交換區(qū)，再從外存交換區(qū)中調(diào)入指定的程序或數(shù)據(jù)到內(nèi)存中來，并讓其執(zhí)行的一種內(nèi)存擴(kuò)充技術(shù)。2、引入交換原因：多道程序系統(tǒng)中，同時(shí)執(zhí)行好幾個(gè)作業(yè)或進(jìn)程，但是同時(shí)存在于內(nèi)存中的作業(yè)或進(jìn)程，有的處于執(zhí)行狀態(tài)或變緒狀態(tài)，而有的則于等待狀態(tài)，一般來說，等待較長(zhǎng)，如果讓處于等待狀態(tài)的進(jìn)程繼續(xù)駐留內(nèi)存，將會(huì)造成存儲(chǔ)空間浪費(fèi)，因此，應(yīng)把處于等待態(tài)進(jìn)程換出內(nèi)存。3、交換與覆蓋區(qū)別：①交換不需要程序員給出程序段之間的覆蓋結(jié)構(gòu)，而覆蓋要求明確給是等程序段之間的覆蓋結(jié)構(gòu)。②交換是進(jìn)程之間或作業(yè)之間進(jìn)行，而覆蓋主要在同一作業(yè)內(nèi)來進(jìn)程內(nèi)進(jìn)行內(nèi)。同時(shí)覆蓋程度段與被覆蓋程序段之間是無關(guān)的。

5.4分頁管理分區(qū)管理的缺陷：系統(tǒng)對(duì)于每個(gè)存儲(chǔ)要求，都分配一片連續(xù)的內(nèi)存空間，導(dǎo)致碎片的產(chǎn)生和內(nèi)存利用率不高。一、實(shí)現(xiàn)原理1、作業(yè)（進(jìn)程）空間的劃分：（1）系統(tǒng)將作業(yè)（進(jìn)程）地址空間分成一些大小相等的塊，每一塊稱為一個(gè)頁，叫邏輯頁。長(zhǎng)度為1KB-4KB.（2）例：如作業(yè)被分成L頁，編號(hào)為1,2,3,…,L-1，每一個(gè)自然數(shù)叫頁號(hào)或邏輯頁號(hào)，其邏輯地址由頁號(hào)和頁內(nèi)偏移地址確定；表示成序偶（p,d）即：

2、內(nèi)存空間的劃分：將內(nèi)存空間分成大小可與邏輯頁相等的若干塊，每塊叫內(nèi)存塊（物理頁）。設(shè)內(nèi)存總?cè)萘繛?S，頁長(zhǎng)為2r，則內(nèi)存頁數(shù)目為2s-r=m，從低地址開始編號(hào)為0,1,2,…,m-1，其中每一個(gè)整數(shù)叫物理頁號(hào)。物理地址=塊號(hào)x頁長(zhǎng)+偏移3、作業(yè)空間與內(nèi)存空間的關(guān)系（1）頁表:當(dāng)作業(yè)（進(jìn)程）運(yùn)行時(shí)，先將其各邏輯頁加載道內(nèi)存的物理頁中，作業(yè)（進(jìn)程）的所有邏輯頁號(hào)是連續(xù)的，而該進(jìn)程獲得的物理頁號(hào)是不連續(xù)的，為此需要建立一個(gè)數(shù)據(jù)結(jié)構(gòu)——頁表，反映邏輯頁與物力頁間的對(duì)應(yīng)關(guān)系。pd邏輯地址=px頁長(zhǎng)+d邏輯頁號(hào)物理頁號(hào)（2）頁表控制寄存器：包括頁表基地址和頁表長(zhǎng)度，有的系統(tǒng)建立一個(gè)總頁表。二、地址映射（1）指令本身得到邏輯地址，分離出邏輯頁號(hào)L和頁內(nèi)地址b；（2）將L與長(zhǎng)度寄存器值m比較，若0<=L<=m，則從始址寄存器取得頁表始址，找到與L相應(yīng)的物理頁號(hào)L；若L不滿足0<=L<=m，則發(fā)出越界訪問錯(cuò)誤信息；（3）由物理頁號(hào)L與b進(jìn)行地址合成，得到邏輯地址所指示的物理單元；（4）進(jìn)行操作，取指令；（5）轉(zhuǎn)（1）。三、快表進(jìn)程標(biāo)志頁表始址長(zhǎng)度（1）目的：提高地址映射速度；（2）設(shè)快表的方法：設(shè)置一組寄存器，用以存儲(chǔ)當(dāng)前進(jìn)程的頁表的一部分，這樣有效地避免地址映射過程中頻繁地訪問內(nèi)存中的頁表。（3）快表的組成：

a、一個(gè)快表通常含8-16個(gè)寄存器。

b、每個(gè)寄存器組存儲(chǔ)頁表的一個(gè)表目，包括邏輯頁號(hào)、物理頁號(hào)、訪問值和狀態(tài)四項(xiàng)，前兩項(xiàng)由頁表直接取得，狀態(tài)項(xiàng)表示該表目是否空表目，訪問值表示該頁表當(dāng)前被訪問的頻率獲該表目建立的次序，的便于置換快表的表目。四、引入快表之后的地址映射過程：（1）指令產(chǎn)生邏輯地址L,b；（2）由邏輯頁號(hào)l查頁表的物理頁頁號(hào)l；

如找不到，則：

a、由邏輯頁號(hào)l和頁表長(zhǎng)度寄存器中的內(nèi)容m比較，判斷是否滿足0<=l<=m，如不滿足則產(chǎn)生越界錯(cuò)誤；

b、如滿足0<=l<=m，由邏輯頁號(hào)l和頁表首址寄存器內(nèi)容查頁表的物理頁號(hào)L，將邏輯頁號(hào)l和物理頁號(hào)L一起置于快表中，若此時(shí)快表已滿，則淘汰一個(gè)；

c、轉(zhuǎn)步驟(2)。（3）由物理頁號(hào)L和頁內(nèi)地址b合成的物理地址。五、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)分配：1、內(nèi)存分塊（頁）表MBT

整個(gè)系統(tǒng)一個(gè)，用于記錄所有內(nèi)存快的使用情況，表目數(shù)等于內(nèi)存塊總數(shù)，各內(nèi)存塊按序?qū)?yīng)一個(gè)表目，表目號(hào)即塊號(hào)。

2、頁表PMT

每個(gè)用戶進(jìn)程一個(gè)，用以記錄進(jìn)程實(shí)體的地址空間與內(nèi)存空間之間的對(duì)應(yīng)關(guān)系，地址空間中的各內(nèi)存塊號(hào)狀態(tài)

占用者名

……

……

……頁按序?qū)?yīng)表目中的一個(gè)表目，表目號(hào)等于邏輯頁號(hào)，表長(zhǎng)等于邏輯頁總數(shù)。3、計(jì)數(shù)變量freeblocks：記錄當(dāng)前空閑塊數(shù)目。4、存儲(chǔ)塊分頁算法（略）六、關(guān)于碎片一個(gè)作業(yè)占有的各塊除最后一塊外均不存在碎片，最后一塊存在碎片，小于塊長(zhǎng)。

5.5分段管理與段頁式管理

一、分段管理（一）分段的引入1、分頁管理的優(yōu)點(diǎn)：實(shí)現(xiàn)了內(nèi)存分配的非連續(xù)性，解決了碎片問題，從而大大提高了內(nèi)存利用率。

缺點(diǎn)：對(duì)作業(yè)或進(jìn)城實(shí)體的分頁不是按其內(nèi)部的邏輯結(jié)構(gòu)和關(guān)系；一頁中的內(nèi)容通常不是完整的程序和數(shù)據(jù)邏輯段，導(dǎo)致一個(gè)邏輯段可能被分成若干頁，不通邏輯段也可能在同一個(gè)頁內(nèi)，這使程序段或數(shù)據(jù)段的共享、保護(hù)變得困難。

2、引入：為了解決頁式存儲(chǔ)管理中共享數(shù)據(jù)和程序段的困難，引入一種以作業(yè)（進(jìn)程）邏輯段為單位分配內(nèi)存的方法，這就是分段管理。（二）實(shí)現(xiàn)原理：1、思想：把作業(yè)（進(jìn)程）按內(nèi)容或過程（函數(shù)）關(guān)系分成段，每段叫做邏輯段，每段有其段名，在分配內(nèi)存時(shí)，以邏輯段為單位分配。2、實(shí)現(xiàn)：（1）內(nèi)存空間的劃分：內(nèi)存空間被動(dòng)態(tài)地分成若干長(zhǎng)度不等的區(qū)域，每個(gè)區(qū)域等于相應(yīng)程序段長(zhǎng)度，叫物理段。物理地址：每個(gè)物理段中存儲(chǔ)單元地址由兩個(gè)值決定，即段首址和段內(nèi)偏移。物理地址=段首址+段內(nèi)偏移=（2）進(jìn)程空間的劃分：

進(jìn)程空間被靜態(tài)地劃分成長(zhǎng)度不等的區(qū)域，每個(gè)區(qū)域?yàn)橐粋€(gè)邏輯段，它是具有一定功能和結(jié)構(gòu)的相對(duì)獨(dú)立的程序單位。

邏輯地址：源程序經(jīng)過編譯后的地址，由段號(hào)和段內(nèi)偏移量組成。

段名：每個(gè)邏輯段有一個(gè)符號(hào)名稱，用以標(biāo)志該段。段首址段內(nèi)偏移段號(hào)：將一個(gè)作業(yè)（進(jìn)程）的所有邏輯段從0開始編號(hào)，這個(gè)自然數(shù)叫段號(hào)。（3）進(jìn)程空間與內(nèi)存空間的對(duì)應(yīng)關(guān)系：

進(jìn)程的一個(gè)邏輯段與內(nèi)存中的一個(gè)物理段相對(duì)應(yīng)，一個(gè)進(jìn)程的多個(gè)邏輯段可存于內(nèi)存中若干部相連的物理段中。（4）所需表目

A、段表：用于記錄一個(gè)進(jìn)程各段在內(nèi)存的起始地址和長(zhǎng)度，從而反映邏輯空間與物理空間的關(guān)系。

邏輯段號(hào)

內(nèi)存始址

長(zhǎng)度

B、段表控制寄存器（一個(gè)系統(tǒng)一個(gè)該表）

①物理段始址寄存器

②段長(zhǎng)度寄存器

C、進(jìn)程表：用于記錄個(gè)進(jìn)程段表始址及長(zhǎng)度，位于

OS空間。

D、空閑表：用于記錄內(nèi)存中空閑的物理區(qū)域，便于進(jìn)行內(nèi)存分配。

進(jìn)程標(biāo)識(shí)

段表始址

表長(zhǎng)度始址

長(zhǎng)度

E、一組聯(lián)想寄存器——快表

用于保存正在運(yùn)行的進(jìn)程段表的一部分（投影）。（5）

地址映射：①指令產(chǎn)生邏輯地址（段號(hào)S、段內(nèi)偏移量lad）；②由段號(hào)查快表得到段首址、段長(zhǎng)；

若找不到，則：

a、由段號(hào)S與段表長(zhǎng)度寄存器內(nèi)容l進(jìn)行比較，是否滿足0<=S<=l，如不滿足則越界；

b、由段號(hào)及段表首址寄存器內(nèi)容查內(nèi)存中的段表，得到段號(hào)S對(duì)應(yīng)的物理段始址和長(zhǎng)度，將首址和長(zhǎng)度寫入快表（可能存在淘汰）

c、轉(zhuǎn)②③由段內(nèi)地址lad和長(zhǎng)度leng比較，是否滿足

0<=lad<=leng，如不滿足則越界。④由段首址與段內(nèi)地址相加得物理地址。（三）

分段與分頁的共享：1、分段的共享：

為了實(shí)現(xiàn)不同進(jìn)程對(duì)內(nèi)存中同一物理段的共享，方法是通過它的段表來實(shí)現(xiàn)，一兩個(gè)進(jìn)程共享一段為例：設(shè)甲進(jìn)程的段號(hào)Si，乙進(jìn)程的段號(hào)為Sj，若Si、

Sj對(duì)應(yīng)同一個(gè)物理段的始址和長(zhǎng)度，則甲乙兩進(jìn)程實(shí)現(xiàn)對(duì)該物理段的共享。2、分頁的共享：與分段的共享相同，即讓一個(gè)進(jìn)程的一個(gè)邏輯頁號(hào)Pi與另一個(gè)進(jìn)程的邏輯頁號(hào)Pj對(duì)應(yīng)同一個(gè)物理頁號(hào)

PP，則實(shí)現(xiàn)了兩個(gè)進(jìn)程對(duì)PP的共享。二、段頁式管理（一）基本原理：1、思想：用分段向用戶提供二維的編程空間，以方便用戶編程，利用分頁來管理內(nèi)存空間，以提高內(nèi)存的利用率。2、實(shí)現(xiàn)：（1）內(nèi)存空間的劃分：

內(nèi)存空間被靜態(tài)地劃分成若干長(zhǎng)度相等的區(qū)域，每個(gè)區(qū)域長(zhǎng)為2i，稱為一個(gè)物理頁面。

（2）進(jìn)程空間的劃分：與段頁式存儲(chǔ)管理相同，進(jìn)程空間被靜態(tài)地劃分為長(zhǎng)度不等的區(qū)域——邏輯段，與頁式存儲(chǔ)相同，在進(jìn)行進(jìn)程存儲(chǔ)管理時(shí)，每段空間被靜態(tài)地分成若干長(zhǎng)度若干長(zhǎng)度為2i的區(qū)域，每個(gè)區(qū)域稱為一個(gè)邏輯頁面。邏輯地址：

（3）內(nèi)存空間與進(jìn)程空間之間的對(duì)應(yīng)關(guān)系：段號(hào)

邏輯頁號(hào)

頁內(nèi)地址進(jìn)程空間的一個(gè)邏輯頁面對(duì)應(yīng)內(nèi)存空間的一個(gè)物理頁面，同一段的邏輯頁面是連續(xù)的，而對(duì)應(yīng)的物理頁面是不連續(xù)的。（如圖所示：備課本）（4）所需表目：

A、段表：每個(gè)進(jìn)程一個(gè)，用于記錄進(jìn)程各段的頁表始址和頁表長(zhǎng)度；B、頁表：此表每個(gè)段一個(gè)，用于記錄段中各邏輯頁與物理頁號(hào)之間的對(duì)應(yīng)關(guān)系；C、進(jìn)程表：用于記錄各進(jìn)程段表的首址及長(zhǎng)度，一個(gè)系統(tǒng)。D、空閑表：用于記錄內(nèi)存頁中空閑頁情況。（5）所需寄存器：

A、段表首址寄存器B、段表長(zhǎng)度寄存器C、快表（6）地址映射

A、由指令產(chǎn)生邏輯地址，包括段號(hào)s、邏輯頁號(hào)lp、頁內(nèi)偏移lad；B、由段號(hào)s和邏輯頁號(hào)查快表得物理頁號(hào)，如果找不到：

a、由段號(hào)和頁表長(zhǎng)度寄存器中的內(nèi)容l進(jìn)行比較，判斷是否滿足0<=s<=l，如果不滿足則越界，產(chǎn)生中斷；b、由段號(hào)和段表始址寄存器內(nèi)容查段表得頁表首址和頁表長(zhǎng)度；c、由邏輯頁號(hào)lp與頁表長(zhǎng)度l’相比較，判斷0<=lp<=l’,如不滿足則越界，產(chǎn)生中斷；d、由邏輯頁號(hào)與頁表首址查對(duì)應(yīng)的物理頁號(hào)；e、將段號(hào)、邏輯頁號(hào)和物理頁號(hào)合在一起送入快表；

f、轉(zhuǎn)b；C、由物理頁號(hào)和頁內(nèi)地址合成為物理地址。（二）特點(diǎn)1、優(yōu)點(diǎn)：（1）方便用戶、使用戶對(duì)進(jìn)程在內(nèi)存中的映射可見；（2）內(nèi)存利用率高，克服了碎片問題。2、缺點(diǎn)：方法復(fù)雜，軟件、硬件開銷大。

動(dòng)態(tài)頁式存儲(chǔ)管理（P122）(虛擬頁式存儲(chǔ)管理)一、類型：1、請(qǐng)求頁式存儲(chǔ)管理：進(jìn)程執(zhí)行前只讓程序、數(shù)據(jù)的一部分內(nèi)容進(jìn)入內(nèi)存，其他部分則在執(zhí)行過程中動(dòng)態(tài)調(diào)入，當(dāng)訪問某條指令時(shí)發(fā)現(xiàn)它在外存而不在內(nèi)存，則發(fā)生缺頁中斷，系統(tǒng)將外存中相應(yīng)的頁面調(diào)入內(nèi)存。2、預(yù)調(diào)入方式：在缺頁中斷發(fā)生之前，事先調(diào)入處于外存中的還未被訪問的頁面。二、問題：為了實(shí)現(xiàn)虛擬存儲(chǔ)管理，需要解決以下問題：1、頁表的改進(jìn)2、置換算法的選擇：當(dāng)內(nèi)存中無空閑頁面時(shí)，把調(diào)入的頁放在什么地方。三、請(qǐng)求頁式管理中的置換算法1、隨機(jī)淘汰算法2、輪轉(zhuǎn)法和FIFO

特點(diǎn)：內(nèi)存利用率不高；缺頁中斷率高，有時(shí)甚至產(chǎn)生Belady現(xiàn)象。

頁號(hào)

頁面號(hào)

中段位外存地址改變位（1）Belady現(xiàn)象：是一種異?，F(xiàn)象，由于缺頁中斷發(fā)生時(shí)，置換算法的不合理及程序執(zhí)行順序的隨機(jī)性，呆滯給進(jìn)程分配的內(nèi)存頁面越多，而缺頁中斷不但不降低反而升高的現(xiàn)象。例1、例2、（見備課本）3、最近最久未使用頁面淘汰算法（P126