第五章存儲管理

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

2、地支持多道程序的并發(fā)執(zhí)行以及解除對用戶作業(yè)大小的限制。 1、虛擬存儲器實現(xiàn)的可能性 （1）現(xiàn)代計算機系統(tǒng)的物理存儲器分成內(nèi)存和外存。 因內(nèi)存價格昂貴，不可能用大容量的內(nèi)存來存 儲所有被訪問的或暫時不被訪問的程序和數(shù)據(jù)，而 外存價格低，適于存儲大量的信息。 （2）程序執(zhí)行的局部性原理 （3）編譯、鏈接 通常由用戶編寫的源程序，首先要有編譯程序 編譯成可執(zhí)行代碼，然后，由鏈接程序把一個進程 的不同程序段連接起來以完成要求的功能。顯然， 對于不同的程序段，應(yīng)具有不同的地址。 a、物理地址：物理存儲器中存儲單元的編號。 優(yōu)點：速度快； 缺點：影響并發(fā)執(zhí)行的進程數(shù)； 大進程無法運行。 b、編譯鏈接程序?qū)?/p>

3、用戶進程編譯鏈接到一個以0位始 址的線性或多維地址空間。 靜態(tài)鏈接：在程序執(zhí)行前由鏈接程序?qū)M程所含目 標代碼進行連接； 動態(tài)鏈接：在程序執(zhí)行過程中根據(jù)需要而進行的連 接。 虛擬存儲器（P106第一行）：將進程中的目標代碼、 數(shù)據(jù)等的虛擬地址組成的虛擬空間稱為虛 擬存儲器。 虛擬地址（邏輯地址） 物理地址 （4）地址變換：由邏輯地址向物理地址的轉(zhuǎn)換過程。二、地址變換(P106) 內(nèi)存空間（物理地址空間）：內(nèi)存地址的集合。 虛擬空間的劃分：使編譯鏈接程序可以把不同的程序 模塊連接到一個統(tǒng)一的虛擬空間。 地址重定位：把虛擬空間中已鏈接和劃分好的內(nèi)容裝入 內(nèi)存，并將虛擬地址映射為內(nèi)存地址的過程叫 地

4、址重定位或地址映射。 1、靜態(tài)地址重定位（P107） (1)方法：是在虛擬空間中程序執(zhí)行之前由OS的重定位 裝入程序完成地址映射工作。 (2)特點： 優(yōu)點：不需要硬件支持 缺點： 使用靜態(tài)重定位法進行地址變換無法實現(xiàn)虛擬 存貯器，因靜態(tài)重定位將程序一旦裝入內(nèi)存之后不 能再移動，并且必須在程序執(zhí)行之前將有關(guān)部分全 部裝入。 進程必須占用連續(xù)的內(nèi)存空間，難實現(xiàn)數(shù)據(jù)共 享。 2、動態(tài)地址重定位： （1）方法：在程序執(zhí)行過程中，在CPU訪問內(nèi)存之前， 將要訪問的程序或數(shù)據(jù)地址變成內(nèi)存地址，動 態(tài)重定位依靠硬件地址變換機構(gòu)完成。 （2）動態(tài)地址重定位機構(gòu) 基地址寄存器BR（始址）、虛地址寄存器 VR偏移

5、） 則：內(nèi)存地址MA MA=（BR）+（VR） （3）址映射過程： 設(shè)置基地址寄存器BR，虛地址寄存器VR 將程序段裝入內(nèi)存，將其占用的區(qū)域的首地址送BR； 在程序執(zhí)行過程中，將要訪問的虛地址送入VR中； 地址變換機構(gòu)把VR和BR的內(nèi)容相加，得訪問的物 理地址 （4）動態(tài)重定位優(yōu)點： 可以對內(nèi)存進行非連續(xù)分配 動態(tài)重定位提供了實現(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)存，為此目 的，有兩種方法實現(xiàn)內(nèi)存與外存間的控制即覆蓋與 交換。 1、覆蓋（overlay ）：由用戶程序自己控制

6、內(nèi)外存之間 的數(shù)據(jù)交換，它要求用戶清楚了解程序的結(jié)構(gòu)，并指 定各程序段調(diào)入內(nèi)存的先后次序。 2、交換（swapping）：包括換進與換出，它是指由操作 系統(tǒng)把那些在內(nèi)存中處于等待狀態(tài)的進程換出內(nèi)存，以 及把那些等待事件已經(jīng)發(fā)生，處于就緒態(tài)的進程換入內(nèi) 存，以及那些即將執(zhí)行的程序數(shù)據(jù)調(diào)入內(nèi)存。 3、請求調(diào)入方式： 在程序執(zhí)行時，如訪問的程序段或數(shù)據(jù)段不在內(nèi)存 中，則操作系統(tǒng)自動地從外存將有關(guān)程序、數(shù)據(jù)調(diào)入 內(nèi)存。 4、預(yù)調(diào)入方式：由OS預(yù)測在不遠的將來會訪問到的那 些程序、數(shù)據(jù)部分，并在他們被訪問之前由系統(tǒng)選擇 適當?shù)臅r機將它們調(diào)入內(nèi)存的方法。 5、區(qū)分交換與覆蓋： （1）交換不需要程序員給出程

7、序、數(shù)據(jù)段的交換方法、 過程，而覆蓋要求明確給出程序段之間的覆蓋結(jié)構(gòu) （2）交換主要是在進程之間進行，而覆蓋主要是在一 個進程內(nèi)或一個作業(yè)內(nèi)進行，同時覆蓋程序段與被覆 蓋程序段是無關(guān)的。 6、 區(qū)分請求式調(diào)入與預(yù)調(diào)入 （1）二者一般是在一個進程內(nèi)的不同程序段、數(shù)據(jù) 段間進行； （2）請求式調(diào)入命中率為100%，但程序執(zhí)行速度慢， 預(yù)調(diào)方式命中率100%四、內(nèi)存分配與回收 1、任務(wù)：存貯管理模塊為每一個并發(fā)執(zhí)行的進程分配 內(nèi)存空間，另外，當進程執(zhí)行結(jié)束后，存貯管理模塊 又要及時回收該進程所使用的內(nèi)存資源，以便給其他 進程分配本內(nèi)存。 2、設(shè)計內(nèi)存分配和回收方法時，要考慮的策略及數(shù)據(jù)結(jié) 構(gòu)如下：

8、（1）分配結(jié)構(gòu)：空閑區(qū)表、空閑區(qū)隊列（鏈） （2）放置策略：選擇空閑區(qū)方法 （3）交換策略 （4）調(diào)入策略 （5）回收策略五、內(nèi)存信息的共享和保護 內(nèi)存信息共享 內(nèi)存保護 常用的內(nèi)存信息保護方式： 1、 上下界保護法： 方法：為每個進程設(shè)置一對上下界寄存器，存貯被保護 程序和數(shù)據(jù)段的起始地址和終止地址。程序執(zhí)行 過程中，在對內(nèi)存進行訪問操作時進行地址合法 性檢查，即檢查經(jīng)過重定位后的內(nèi)存地址是否在 上下界寄存器所規(guī)定范圍內(nèi)。若在規(guī)定范圍內(nèi)， 則訪問是合法的。否則是非法的，并產(chǎn)生訪地越 界中斷。 2、保護鍵法： 方法：為每一個被保護存貯塊分配一個單獨的保護鍵。 在程序狀態(tài)字中設(shè)置相應(yīng)的保護鍵開關(guān)

9、字段，對 不同進程賦予不同的開關(guān)代碼，與保護的存貯塊 中的保護鍵匹配，保護鍵可設(shè)置成對RW同時進行 保護或只對R、W進行單獨保護的。如果開關(guān)字與 保護鍵匹配或存貯塊未受到保護，則訪問該存貯 塊是允許的，否則產(chǎn)生訪問出錯中斷。 3、界限寄存器與CPU的用戶態(tài)或核態(tài)工作方式相結(jié)合 的保護方式，在這種方式下，用戶態(tài)進程只能訪問 那些在界限寄存器所規(guī)定范圍內(nèi)的內(nèi)存部分，而核 心態(tài)進程則可以訪問整個內(nèi)存區(qū)域。 內(nèi)存空間：由若干存儲單元組成的，每個存貯單元 有一編號，這一編號可唯一標識一個存 貯單元，稱內(nèi)存地址。 邏輯空間：源程序經(jīng)過匯編或編譯后，形成目標程序， 每個目標程序均以0為基址順序進行編址， 原

10、來用符號名訪問的單元用數(shù)據(jù)單元 號取代，這樣生成的目標程序占據(jù)一定的 地址空間，稱為作業(yè)的邏輯地址空間。 5.2分區(qū)存貯管理 一、分區(qū)管理的基本原理： 給內(nèi)存中的每一個進程劃分一塊適當大小的存貯區(qū)，以連續(xù)存放各進程的程序與數(shù)據(jù)，使各進程得以并發(fā)執(zhí)行。 1、固定分區(qū)法：（也稱靜態(tài)分區(qū)管理） （1）方法：將內(nèi)存區(qū)域固定地劃分為若干大小不等的 區(qū)域，分區(qū)劃分的原則 由系統(tǒng)操作員或OS決定。 （2）數(shù)據(jù)結(jié)構(gòu)PPT（partition describe table) 分區(qū)說明表 （3）特點 每個分區(qū)在表中對應(yīng)一個表目（行），表目內(nèi)容 包括區(qū)號、大小、起始地址，使用狀態(tài)等。 2、 動態(tài)分區(qū)法：（可變分區(qū)管

11、理） （1）方法：作業(yè)執(zhí)行前不建立分區(qū)，分區(qū)的建立是 在作業(yè)的處理過程中進行的，且其大小可隨作業(yè) 或進程對內(nèi)存的要求而改變， （2）數(shù)據(jù)結(jié)構(gòu)：（分區(qū)說明表）(P112) 可用表 自由表 請求表二、分區(qū)的分配與回收： 1、 固定分區(qū)時的分配與回收、 （1）分配：當用戶程序要裝入執(zhí)行時，通過請求表提 出內(nèi)存分配要求和所要求的內(nèi)存空間大小，存貯管 理程序根據(jù)請求查詢分區(qū)說明表，從中找出一個滿 足要求的空閑分區(qū)，并將其分配給申請者。 分配算法如圖5.10 2、 動態(tài)分區(qū)的分配與回收 （1）動態(tài)分配與回收要解決以下三個問題： 對于請求表中的要求內(nèi)存長度，從可用分區(qū)表或 自鏈中尋找出合適的空閑區(qū)進行分配。

12、 分配空閑區(qū)之后，更新可用表或自由鏈。 進程或作業(yè)釋放內(nèi)存資源時，各相鄰的空閑區(qū)進 行鏈接合并，更新可用分區(qū)表或自由鏈。 （2）常用的三種分配算法： A、 最先適應(yīng)算法：（FFA） 可用分區(qū)表或自由鏈的組織：按起始地址遞增的 次序?qū)⒖捎梅謪^(qū)或自由鏈排列起來。 分配：從頭搜索可用分區(qū)表或自由鏈，一旦找到 大于或等于所要求內(nèi)存長度的分區(qū)，則結(jié)束搜索。 然后從所找到的分區(qū)中劃出所要求的內(nèi)存長度分 配給用戶進程，并把余下的部分（進行合并后） 留在可用表中。 特點：內(nèi)存利用率低，易產(chǎn)生碎片 算法實現(xiàn)簡單，速度快。 B、最佳適應(yīng)算法： 可用分區(qū)組織：按空閑分區(qū)的從小到大次序組織 可用分區(qū)表或自由鏈 。 分

13、配：當用戶作業(yè)或進程申請一個空閑分區(qū)時， 存貯管理程序從表頭開始查找，當找到第一個滿 足要求的時，停止查找，如果該分區(qū)長度大于請 求表中的請求長度，則將減去請求長度后的剩余 空閑區(qū)部分留在可用表中 特點： 優(yōu)點：自由分區(qū)表或可用鏈中尾部的空閑區(qū)容量 大，便于大服務(wù)業(yè)運行。 缺點：更容易形成碎片。 C、最壞適應(yīng)算法：（MF） 空閑分區(qū)組織：按空閑分區(qū)容量從大到小次序組 織可用表或自由鍵。 分配：當用戶作業(yè)或進程請求一個空閑區(qū)時，先 檢查可用分區(qū)表或自由鏈的第一個空閑區(qū)的大小 是否大于或等于所要求內(nèi)存長度，若第一個的長 度小于分配請求，則分配失敗，否則從空閑區(qū)可 用分區(qū)表或自由鏈中分配相應(yīng)的存貯空

14、間給用戶， 然后修改和調(diào)整空閑區(qū)可用表或自由鍵。 特點：優(yōu)不易產(chǎn)生碎片 缺大作業(yè)往往無法運行。 3、動態(tài)分區(qū)時的回收與拼接 可用分區(qū)拼接(P114) 圖5.12(四種情形) 4、幾種分配算法的比較： 從查找速度，釋放速度、空閑區(qū)利用三方面進行比較（1）最先適應(yīng)算法：搜索速度，回收速度快，同時盡可 能地利用了低地址空閑，保證了高地址端有較大的空 閑區(qū)來放置要求內(nèi)存較多的進程作業(yè)。（2）最佳適應(yīng)算法：找到的空閑區(qū)最佳（3）最壞適應(yīng)算法：克服了碎片問題，但大作業(yè)往往無 法運行。三、有關(guān)分區(qū)管理其他問題的討論： 1、關(guān)于虛存的討論： 在分區(qū)管理中，每個用戶進程所需內(nèi)存容量是受分 區(qū)大小限制的 2、關(guān)于

15、內(nèi)存擴充 所謂內(nèi)存擴充，是指通過覆蓋或交換技術(shù)來擴 充內(nèi)存。 3、關(guān)于地址變換和內(nèi)存保護。 地址變換分：靜態(tài)地址重定位 動態(tài)地址重定位 內(nèi)存保護 4、 分區(qū)存貯管理的主要優(yōu)缺點： （1）優(yōu)點： 實現(xiàn)了多個服務(wù)業(yè)或進程對內(nèi)存的共享，有助于多 道程序設(shè)計，從而提高了系統(tǒng)資源的利用率 該方法要求的硬件支持少，管理算法簡單 （2）缺點： 內(nèi)存利用率仍然不高 作業(yè)或進程的大小受分區(qū)大小控制，除非配合采用 覆蓋和交換技術(shù)。 難以實現(xiàn)各分區(qū)間的信息共享。 5.3 覆蓋與交換技術(shù)一、覆蓋技術(shù) 1、 概念： 所謂覆蓋，指一內(nèi)存區(qū)可以被不同的程序段重復使用，當某一程序段不再需要時，另一程序段可以占用它的位置，把可

16、以在其上進行覆蓋的內(nèi)存區(qū)域稱為“覆蓋區(qū)”，而可以相互覆蓋的程序為“覆蓋”。 2、基本思想： 程序的執(zhí)行具有局部性特征 程序在CPU上執(zhí)行，在一個絕對時刻，CPU只能執(zhí) 行一條指令，在一個相對較短的時間段內(nèi)，又只有一 個和諧段被執(zhí)行。 程序的劃分： 由于程序的執(zhí)行具有局部性特征，因此在程序執(zhí) 行前沒有必要將程序全部加載到內(nèi)存，而且只裝入一 個或若干個程序段。為此，需將程序進行劃分，將那 些不會同時執(zhí)行的程序段共享同一內(nèi)存區(qū) 程序段的執(zhí)行與覆蓋： 當內(nèi)存中的程序段執(zhí)行結(jié)束，再將外存中它的 后鍵程序段加載內(nèi)存，原來的程序段被覆蓋。 3、覆蓋的實現(xiàn)要求： （1）要求程序員提供一個清楚的覆蓋結(jié)構(gòu)，搞清楚

17、程 序應(yīng)分為多少段，每段的前起后鍵各是什么。 （2）要求程序員清楚了解程序所屬進程的虛擬空間以 及各程序段所在虛擬空間位置。 （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)存擴充技術(shù)。 2、引入交換原因：多道程序系統(tǒng)中，同時執(zhí)行好幾個 作業(yè)或進程，但是同時存在于內(nèi)存中的作業(yè)或進程， 有的處于執(zhí)行狀態(tài)或變緒狀態(tài)，而有的則于等待狀態(tài) ，一般來說，等待較長，如果讓處于等待狀態(tài)的進程 繼續(xù)駐留內(nèi)存，將會造成存儲空間浪費，因此，應(yīng)把

18、 處于等待態(tài)進程換出內(nèi)存。 3、交換與覆蓋區(qū)別： 交換不需要程序員給出程序段之間的覆蓋結(jié)構(gòu)，而 覆蓋要求明確給是等程序段之間的覆蓋結(jié)構(gòu)。 交換是進程之間或作業(yè)之間進行，而覆蓋主要在同 一作業(yè)內(nèi)來進程內(nèi)進行內(nèi)。同時覆蓋程度段與被覆 蓋程序段之間是無關(guān)的。5.4 分頁管理 分區(qū)管理的缺陷：系統(tǒng)對于每個存儲要求，都分配一片連續(xù)的內(nèi)存空間，導致碎片的產(chǎn)生和內(nèi)存利用率不高。一、實現(xiàn)原理 1、作業(yè)（進程）空間的劃分： （1）系統(tǒng)將作業(yè)（進程）地址空間分成一些大小 相等的塊，每一塊稱為一個頁，叫邏輯頁。長 度為1KB-4KB. （2）例：如作業(yè)被分成L頁，編號為1,2,3,L-1，每一 個自然數(shù)叫頁號或邏輯

19、頁號，其邏輯地址由頁號和頁內(nèi)偏移地址確定；表示成序偶（p,d）即： 2、內(nèi)存空間的劃分：將內(nèi)存空間分成大小可與邏輯頁相 等的若干塊，每塊叫內(nèi)存塊（物理頁）。設(shè)內(nèi)存總?cè)萘?為2S，頁長為2r，則內(nèi)存頁數(shù)目為2 s-r=m，從低地址開 始編號為0,1,2,m-1，其中每一個整數(shù)叫物理頁號。 物理地址=塊號x頁長+偏移 3、作業(yè)空間與內(nèi)存空間的關(guān)系 （1）頁表:當作業(yè)（進程）運行時，先將其各邏輯頁加 載道內(nèi)存的物理頁中，作業(yè)（進程）的所有邏輯頁號 是連續(xù)的，而該進程獲得的物理頁號是不連續(xù)的，為 此需要建立一個數(shù)據(jù)結(jié)構(gòu)頁表，反映邏輯頁與物 力頁間的對應(yīng)關(guān)系。pd邏輯地址=px頁長+d邏輯頁號 物理頁號

20、（2）頁表控制寄存器：包括頁表基地址和頁表長度，有 的系統(tǒng)建立一個總頁表。二、地址映射 （1）指令本身得到邏輯地址，分離出邏輯頁號L和頁內(nèi) 地址b； （2）將L與長度寄存器值m比較，若0=L=m，則從 始址寄存器取得頁表始址，找到與L相應(yīng)的物理頁號L；若L不滿足0=L=m，則發(fā)出越界訪問錯誤信息； （3）由物理頁號L與b進行地址合成，得到邏輯地址所指示的物理單元； （4）進行操作，取指令； （5）轉(zhuǎn)（1）。三、快表進程標志頁表始址長度 （1）目的：提高地址映射速度； （2）設(shè)快表的方法：設(shè)置一組寄存器，用以存儲當前 進程的頁表的一部分，這樣有效地避免地址映射過 程中頻繁地訪問內(nèi)存中的頁表。 （

21、3）快表的組成： a、一個快表通常含8-16個寄存器。 b、每個寄存器組存儲頁表的一個表目，包括邏輯 頁號、物理頁號、訪問值和狀態(tài)四項，前兩項由 頁表直接取得，狀態(tài)項表示該表目是否空表目， 訪問值表示該頁表當前被訪問的頻率獲該表目建 立的次序，的便于置換快表的表目。 四、引入快表之后的地址映射過程： （1）指令產(chǎn)生邏輯地址L,b； （2）由邏輯頁號l查頁表的物理頁頁號l； 如找不到，則： a、由邏輯頁號l和頁表長度寄存器中的內(nèi)容m比較， 判斷是否滿足0=l=m，如不滿足則產(chǎn)生越界錯誤； b、如滿足0=l=m，由邏輯頁號l和頁表首址寄存器 內(nèi)容查頁表的物理頁號L，將邏輯頁號l和物理頁號 L一起置

22、于快表中，若此時快表已滿，則淘汰一個； c、轉(zhuǎn)步驟(2)。 （3）由物理頁號L和頁內(nèi)地址b合成的物理地址。 五、數(shù)據(jù)結(jié)構(gòu)、存儲分配： 1、內(nèi)存分塊（頁）表MBT 整個系統(tǒng)一個，用于記錄所有內(nèi)存快的使用情 況，表目數(shù)等于內(nèi)存塊總數(shù)，各內(nèi)存塊按序?qū)?yīng)一 個表目，表目號即塊號。 2、頁表PMT 每個用戶進程一個， 用以記錄進程實體的地址 空間與內(nèi)存空間之間的對應(yīng)關(guān)系， 地址空間中的各 內(nèi)存塊號 狀態(tài) 占用者名 頁按序?qū)?yīng)表目中的一個表目，表目號等于邏輯頁 號，表長等于邏輯頁總數(shù)。 3、計數(shù)變量freeblocks：記錄當前空閑塊數(shù)目。 4、存儲塊分頁算法（略）六、關(guān)于碎片 一個作業(yè)占有的各塊除最后一

23、塊外均不存在碎 片，最后一塊存在碎片，小于塊長。 5.5分段管理與段頁式管理 一、分段管理 （一）分段的引入 1、分頁管理的優(yōu)點：實現(xiàn)了內(nèi)存分配的非連續(xù)性， 解決了碎片問題，從而大大提高了內(nèi)存利用率。 缺點：對作業(yè)或進城實體的分頁不是按其內(nèi)部 的邏輯結(jié)構(gòu)和關(guān)系；一頁中的內(nèi)容通常不是完 整的程序和數(shù)據(jù)邏輯段，導致一個邏輯段可能 被分成若干頁，不通邏輯段也可能在同一個頁 內(nèi)，這使程序段或數(shù)據(jù)段的共享、保護變得困 難。 2、引入：為了解決頁式存儲管理中共享數(shù)據(jù)和程序段 的困難，引入一種以作業(yè)（進程）邏輯段為單位分 配內(nèi)存的方法，這就是分段管理。（二）實現(xiàn)原理： 1、思想：把作業(yè)（進程）按內(nèi)容或過程（

24、函數(shù)）關(guān)系 分成段，每段叫做邏輯段，每段有其段名，在分配內(nèi) 存時，以邏輯段為單位分配。 2、實現(xiàn)： （1）內(nèi)存空間的劃分：內(nèi)存空間被動態(tài)地分成若干長 度不等的區(qū)域，每個區(qū)域等于相應(yīng)程序段長度，叫 物理段。 物理地址：每個物理段中存儲單元地址由兩個值決 定，即段首址和段內(nèi)偏移。 物理地址=段首址+段內(nèi)偏移 = （2）進程空間的劃分： 進程空間被靜態(tài)地劃分成長度不等的區(qū)域，每個 區(qū)域為一個邏輯段，它是具有一定功能和結(jié)構(gòu)的相對 獨立的程序單位。 邏輯地址：源程序經(jīng)過編譯后的地址，由段號和段內(nèi) 偏移量組成。 段名：每個邏輯段有一個符號名稱，用以標志該段。段首址段內(nèi)偏移 段號：將一個作業(yè)（進程）的所有邏

25、輯段從0開始編 號，這個自然數(shù)叫段號。 （3）進程空間與內(nèi)存空間的對應(yīng)關(guān)系： 進程的一個邏輯段與內(nèi)存中的一個物理段相 對應(yīng)，一個進程的多個邏輯段可存于內(nèi)存中若干 部相連的物理段中。 （4）所需表目 A、段表：用于記錄一個進程各段在內(nèi)存的起始地址 和長度，從而反映邏輯空間與物理空間的關(guān)系。 邏輯段號 內(nèi)存始址 長度 B、段表控制寄存器（一個系統(tǒng)一個該表） 物理段始址寄存器 段長度寄存器 C、進程表：用于記錄個進程段表始址及長度，位于 OS空間。 D、空閑表：用于記錄內(nèi)存中空閑的物理區(qū)域，便于進 行內(nèi)存分配。 進程標識 段表始址 表長度 始址 長度 E、一組聯(lián)想寄存器快表 用于保存正在運行的進程段

26、表的一部分（投影）。 （5） 地址映射： 指令產(chǎn)生邏輯地址（段號S、段內(nèi)偏移量lad）； 由段號查快表得到段首址、段長； 若找不到，則： a、由段號S與段表長度寄存器內(nèi)容l進行比較，是否 滿足0=S=l，如不滿足則越界； b、由段號及段表首址寄存器內(nèi)容查內(nèi)存中的段表， 得到段號S對應(yīng)的物理段始址和長度，將首址和 長度寫入快表（可能存在淘汰） c、轉(zhuǎn) 由段內(nèi)地址lad和長度leng比較，是否滿足 0=lad=leng，如不滿足則越界。 由段首址與段內(nèi)地址相加得物理地址。 （三） 分段與分頁的共享： 1、分段的共享： 為了實現(xiàn)不同進程對內(nèi)存中同一物理段的共享， 方法是通過它的段表來實現(xiàn)，一兩個進程

27、共享一段為 例：設(shè)甲進程的段號Si，乙進程的段號為Sj，若Si、 Sj對應(yīng)同一個物理段的始址和長度，則甲乙兩進程實 現(xiàn)對該物理段的共享。 2、分頁的共享： 與分段的共享相同，即讓一個進程的一個邏輯頁 號Pi與另一個進程的邏輯頁號Pj對應(yīng)同一個物理頁號 PP，則實現(xiàn)了兩個進程對PP的共享。二、段頁式管理 （一）基本原理： 1、思想：用分段向用戶提供二維的編程空間，以方 便用戶編程，利用分頁來管理內(nèi)存空間，以提高 內(nèi)存的利用率。 2、實現(xiàn)： （1）內(nèi)存空間的劃分： 內(nèi)存空間被靜態(tài)地劃分成若干長度相等的區(qū)域，內(nèi)存空間被靜態(tài)地劃分成若干長度相等的區(qū)域， 每個區(qū)域長為每個區(qū)域長為 2i，稱為一個物理頁面

28、。，稱為一個物理頁面。 （2 2）進程空間的劃分：）進程空間的劃分： 與段頁式存儲管理相同，進程空間被靜態(tài)地劃分與段頁式存儲管理相同，進程空間被靜態(tài)地劃分 為長度不等的區(qū)域為長度不等的區(qū)域邏輯段，與頁式存儲相同，在邏輯段，與頁式存儲相同，在 進行進程存儲管理時，每段空間被靜態(tài)地分成若干長進行進程存儲管理時，每段空間被靜態(tài)地分成若干長 度若干長度為度若干長度為2i的區(qū)域，每個區(qū)域稱為一個邏輯頁面。的區(qū)域，每個區(qū)域稱為一個邏輯頁面。 邏輯地址：邏輯地址： （3 3）內(nèi)存空間與進程空間之間的對應(yīng)關(guān)系：）內(nèi)存空間與進程空間之間的對應(yīng)關(guān)系： 段號 邏輯頁號 頁內(nèi)地址 進程空間的一個邏輯頁面對應(yīng)內(nèi)存空間的

29、一個物進程空間的一個邏輯頁面對應(yīng)內(nèi)存空間的一個物 理頁面，同一段的邏輯頁面是連續(xù)的，而對應(yīng)的物理理頁面，同一段的邏輯頁面是連續(xù)的，而對應(yīng)的物理 頁面是不連續(xù)的。（如圖所示：備課本）頁面是不連續(xù)的。（如圖所示：備課本） （4 4）所需表目：）所需表目： A、段表：每個進程一個，用于記錄進程各段的頁表、段表：每個進程一個，用于記錄進程各段的頁表 始址和頁表長度；始址和頁表長度； B、頁表：此表每個段一個，用于記錄段中各邏輯頁、頁表：此表每個段一個，用于記錄段中各邏輯頁 與物理頁號之間的對應(yīng)關(guān)系；與物理頁號之間的對應(yīng)關(guān)系； C、進程表：用于記錄各進程段表的首址及長度，、進程表：用于記錄各進程段表的首

30、址及長度， 一一 個系統(tǒng)。個系統(tǒng)。 D、空閑表：用于記錄內(nèi)存頁中空閑頁情況。、空閑表：用于記錄內(nèi)存頁中空閑頁情況。 （5 5）所需寄存器：）所需寄存器： A、段表首址寄存器、段表首址寄存器 B、段表長度寄存器、段表長度寄存器 C、快表、快表 （6 6）地址映射）地址映射 A、由指令產(chǎn)生邏輯地址，包括段號、由指令產(chǎn)生邏輯地址，包括段號s、邏輯頁號、邏輯頁號lp、 頁內(nèi)偏移頁內(nèi)偏移lad； B、由段號、由段號s和邏輯頁號查快表得物理頁號，如果找不和邏輯頁號查快表得物理頁號，如果找不 到：到： a、由段號和頁表長度寄存器中的內(nèi)容、由段號和頁表長度寄存器中的內(nèi)容l進行比較，進行比較， 判斷是否滿足判斷

31、是否滿足0=s=l，如果不滿足則越界，產(chǎn)生，如果不滿足則越界，產(chǎn)生 中斷；中斷； b、由段號和段表始址寄存器內(nèi)容查段表得頁表首、由段號和段表始址寄存器內(nèi)容查段表得頁表首 址和頁表長度；址和頁表長度； c、由邏輯頁號、由邏輯頁號lp與頁表長度與頁表長度l相比較，判斷相比較，判斷 0=lp=l,如不滿足則越界，產(chǎn)生中斷；如不滿足則越界，產(chǎn)生中斷； d、由邏輯頁號與頁表首址查對應(yīng)的物理頁號；、由邏輯頁號與頁表首址查對應(yīng)的物理頁號； e、將段號、邏輯頁號和物理頁號合在一起送入快、將段號、邏輯頁號和物理頁號合在一起送入快 表；表； f、轉(zhuǎn)、轉(zhuǎn)b； C、由物理頁號和頁內(nèi)地址合成為物理地址。、由物理頁號和頁

32、內(nèi)地址合成為物理地址。 （二）特點（二）特點 1、優(yōu)點：、優(yōu)點： （1）方便用戶、使用戶對進程在內(nèi)存中的映射可見；）方便用戶、使用戶對進程在內(nèi)存中的映射可見； （2）內(nèi)存利用率高，克服了碎片問題。）內(nèi)存利用率高，克服了碎片問題。 2、缺點：方法復雜，軟件、硬件開銷大。、缺點：方法復雜，軟件、硬件開銷大。 動態(tài)頁式存儲管理（動態(tài)頁式存儲管理（P122） (虛擬頁式存儲管理虛擬頁式存儲管理)一、類型：一、類型： 1、請求頁式存儲管理：、請求頁式存儲管理： 進程執(zhí)行前只讓程序、數(shù)據(jù)的一部分內(nèi)容進入內(nèi)進程執(zhí)行前只讓程序、數(shù)據(jù)的一部分內(nèi)容進入內(nèi) 存，其他部分則在執(zhí)行過程中動態(tài)調(diào)入，當訪問某條存，其他部分

33、則在執(zhí)行過程中動態(tài)調(diào)入，當訪問某條 指令時發(fā)現(xiàn)它在外存而不在內(nèi)存，則發(fā)生缺頁中斷，指令時發(fā)現(xiàn)它在外存而不在內(nèi)存，則發(fā)生缺頁中斷， 系統(tǒng)將外存中相應(yīng)的頁面調(diào)入內(nèi)存。系統(tǒng)將外存中相應(yīng)的頁面調(diào)入內(nèi)存。 2、預(yù)調(diào)入方式：、預(yù)調(diào)入方式： 在缺頁中斷發(fā)生之前，事先調(diào)入處于外存中的還在缺頁中斷發(fā)生之前，事先調(diào)入處于外存中的還 未被訪問的頁面。未被訪問的頁面。二、問題：二、問題： 為了實現(xiàn)虛擬存儲管理，需要解決以下問題：為了實現(xiàn)虛擬存儲管理，需要解決以下問題： 1、頁表的改進、頁表的改進 2、置換算法的選擇：當內(nèi)存中無空閑頁面時，把調(diào)入的、置換算法的選擇：當內(nèi)存中無空閑頁面時，把調(diào)入的 頁放在什么地方。頁放在

34、什么地方。三、請求頁式管理中的置換算法三、請求頁式管理中的置換算法 1、隨機淘汰算法、隨機淘汰算法 2、輪轉(zhuǎn)法和、輪轉(zhuǎn)法和FIFO 特點：內(nèi)存利用率不高；特點：內(nèi)存利用率不高； 缺頁中斷率高，有時甚至產(chǎn)生缺頁中斷率高，有時甚至產(chǎn)生Belady現(xiàn)象?，F(xiàn)象。 頁號 頁面號 中段位外存地址改變位 （1）Belady現(xiàn)象：現(xiàn)象： 是一種異?，F(xiàn)象，由于缺頁中斷發(fā)生時，置是一種異?，F(xiàn)象，由于缺頁中斷發(fā)生時，置 換算法的不合理及程序執(zhí)行順序的隨機性，呆滯給換算法的不合理及程序執(zhí)行順序的隨機性，呆滯給 進程分配的內(nèi)存頁面越多，而缺頁中斷不但不降低進程分配的內(nèi)存頁面越多，而缺頁中斷不但不降低 反而升高的現(xiàn)象。反

35、而升高的現(xiàn)象。 例例1、 例例2、 （見備課本）（見備課本） 3、最近最久未使用頁面淘汰算法（、最近最久未使用頁面淘汰算法（P126） LRU （1）基本思想：當需要淘汰一頁時，選擇離當前時間最）基本思想：當需要淘汰一頁時，選擇離當前時間最 近的一段時間內(nèi)最久沒有使用過的頁面先淘汰。近的一段時間內(nèi)最久沒有使用過的頁面先淘汰。 （2）特點：因要記錄每個內(nèi)存頁面的訪問情況，系統(tǒng)開）特點：因要記錄每個內(nèi)存頁面的訪問情況，系統(tǒng)開 銷較大。銷較大。 （3）比較常用的近似算法：）比較常用的近似算法： A、最不經(jīng)常使用的頁面淘汰算法、最不經(jīng)常使用的頁面淘汰算法-LFU a、思想：當需要淘汰一頁時，首先淘汰到

36、當前為、思想：當需要淘汰一頁時，首先淘汰到當前為 止，被訪問次數(shù)最少的一頁；止，被訪問次數(shù)最少的一頁； b、實現(xiàn)方法：為每個內(nèi)存頁增設(shè)一個訪問計數(shù)器。、實現(xiàn)方法：為每個內(nèi)存頁增設(shè)一個訪問計數(shù)器。 B、最近沒有使用頁面淘汰算法、最近沒有使用頁面淘汰算法-NUR a、思想：選擇最近一個時期內(nèi)未被訪問的頁面進、思想：選擇最近一個時期內(nèi)未被訪問的頁面進 行淘汰。行淘汰。 b、實現(xiàn)：為每個內(nèi)存頁增設(shè)一個訪問位即可實現(xiàn)。、實現(xiàn)：為每個內(nèi)存頁增設(shè)一個訪問位即可實現(xiàn)。 當某頁被訪問時，訪問位置為當某頁被訪問時，訪問位置為1，否則置為，否則置為0。 且系統(tǒng)周期性地對所有訪問位清且系統(tǒng)周期性地對所有訪問位清0。

37、4、理想型淘汰算法（、理想型淘汰算法（OPT） 淘汰在訪問串中將來再也不會出現(xiàn)的或離當前最遠淘汰在訪問串中將來再也不會出現(xiàn)的或離當前最遠 的位置上出現(xiàn)的頁。的位置上出現(xiàn)的頁。四、存儲保護（四、存儲保護（P127） 法法1：地址越界保護，通過地址變換機構(gòu)中的控制寄存器：地址越界保護，通過地址變換機構(gòu)中的控制寄存器 的值的值頁表長度和要訪問的虛地址相比較來完成。頁表長度和要訪問的虛地址相比較來完成。 法法2：存取控制保護，通過在頁表中增加相應(yīng)的保護位實：存取控制保護，通過在頁表中增加相應(yīng)的保護位實 現(xiàn)?，F(xiàn)。五、頁式存儲管理的優(yōu)缺點五、頁式存儲管理的優(yōu)缺點(P127) 1、優(yōu)點、優(yōu)點 （1）由于他不要求作業(yè)或進程的程序段、數(shù)據(jù)段在內(nèi)）由于他不要求作業(yè)或進程的程序段、數(shù)據(jù)段在內(nèi) 存中連續(xù)存放，從而有效地解決了碎片問題。存中連續(xù)存放，從而有效地解決了碎片問題。 （2）動態(tài)頁式存儲管理提供了內(nèi)存和外存統(tǒng)一管理的虛）動態(tài)頁式存儲管理提供了內(nèi)存和外存統(tǒng)一管理的虛 存實現(xiàn)方法，使用戶可以利用的存儲空間大大增加，存實現(xiàn)方法，使用戶可以利用的存儲空間大大增加，