第5章 存儲器管理2_chd

1、第五章 存儲管理（2）,概述分區(qū)存儲管理頁式存儲管理交換技術(shù)與覆蓋技術(shù)虛擬存儲,程序的裝入和鏈接,,對用戶程序的處理步驟,程序的裝入,1. 絕對裝入方式,程序中所使用的絕對地址，可在編譯或匯編時給出， 也可由程序員直接賦予。 但在由程序員直接給出絕對地址時， 不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉(zhuǎn)換為絕

2、對地址。,2. 可重定位裝入方式,作業(yè)裝入內(nèi)存時的情況,,在裝入時對目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為重定位。因地址變換是在裝入時一次完成的，以后不再改變，故稱為靜態(tài)重定位。,--------導(dǎo)致不允許程序運行時在內(nèi)存中移動位置,3. 動態(tài)運行時裝入方式,動態(tài)運行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行。因此， 裝入內(nèi)存后的所有地址都仍是相對地址

3、。,為使地址轉(zhuǎn)換不影響指令的執(zhí)行速度，需重定位寄存器的支持,程序的鏈接,圖 程序鏈接示意圖,1.靜態(tài)鏈接方式,兩個問題需解決：相對地址的修改、變換外部調(diào)用符號,,這種先進行鏈接所形成的一個完整的裝入模塊稱為可執(zhí)行文件通常不再拆開它，要運行時可直接裝入內(nèi)存若要修改或更新其中的某個目標(biāo)模塊，則要求重新打開裝入模塊,2. 裝入時動態(tài)鏈接,裝入目標(biāo)模塊時，邊裝入邊鏈接。裝入時動態(tài)鏈接方式有以下優(yōu)點： 便于修改和更新。 (2) 便于實現(xiàn)

4、對目標(biāo)模塊的共享。,3. 運行時動態(tài)鏈接,這種鏈接方式是將對某些模塊的鏈接推遲到執(zhí)行時才執(zhí)行，即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模塊并將之裝入內(nèi)存， 把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。,5.3 單用戶連續(xù)存儲管理,單用戶存儲管理,在單道環(huán)境下，不管是單用戶系統(tǒng)還是單道批處理系統(tǒng)，進程

5、（作業(yè)）執(zhí)行時除了系統(tǒng)占用一部分主存外，剩下的主存區(qū)域全部歸它占用。主存可以劃分為三部分： 系統(tǒng)區(qū)、用戶區(qū)、空閑區(qū)。用戶占用區(qū)是一個連續(xù)的存儲區(qū)所以又稱單一連續(xù)區(qū)存儲管理。單用戶系統(tǒng)在一段時間內(nèi)，只有一個進程在內(nèi)存，故內(nèi)存分配管理十分簡單，內(nèi)存利用率低。內(nèi)存分為兩個區(qū)域，一個供操作系統(tǒng)使用，一個供用戶使用,圖 單一連續(xù)區(qū)存儲分配示意圖,工作流程,單一連續(xù)區(qū)分配采用靜態(tài)分配和靜態(tài)重定位方式，亦即作業(yè)或進程一旦進入主存，就一直等

6、到它運行結(jié)束后才能釋放主存。如下圖所示的主存分配與回收法。并且由裝入程序檢查其絕對地址是否超越，即可達到保護系統(tǒng)的目的。,,工作流程(續(xù)),,,分時系統(tǒng)中可用對換方式讓多個用戶的作業(yè)輪流進入主存儲器執(zhí)行按時間片方式輪流地被換出和換入。,,由于單用戶連續(xù)存儲管理每次只允許一個作業(yè)進入主存儲器，因此不必考慮作業(yè)在主存的移動問題，可用靜態(tài)重定位硬件不必有地址轉(zhuǎn)換機構(gòu),單用戶系統(tǒng)缺點,不支持多道。主存利用率不高。程序的運行受主存容量限制

7、。,,存儲保護,自動地址修改　例如，存儲器的地址空間為１２Ｋ，而操作系統(tǒng)位于低址端的４Ｋ內(nèi)。對于這樣的系統(tǒng)，我們給用戶一個１３位的地址空間，并對其每個存儲器訪問自動加上４Ｋ。如果操作系統(tǒng)占用高址端的４Ｋ，則我們?nèi)∶恳粋€存儲訪問Ｒ，而實際上，其地址為（Ｒ?。恚铮洹。福耍?。從而實現(xiàn)了對操作系統(tǒng)的保護。,,存儲保護（續(xù)）,０頁、１頁尋址　通過對每個用戶生成的地址左端拼接上一位１來實現(xiàn)ＯＳ區(qū)與用戶區(qū)。把操作系統(tǒng)確定在０頁，而把用戶作業(yè)放在１頁。

8、界限寄存器　通過增加界限寄存器，劃分ＯＳ區(qū)與用戶區(qū)。,,分區(qū)存儲管理方案,系統(tǒng)把內(nèi)存用戶區(qū)劃分為若干分區(qū)，分區(qū)大小可以相等，也可以不等。一個進程占據(jù)一個分區(qū)固定分區(qū)可變分區(qū),5.4 固定分區(qū)存儲管理,預(yù)先把可分配的內(nèi)存空間分割成若干個連續(xù)區(qū)域，每一區(qū)域稱為分區(qū) 每個分區(qū)的大小可以相同也可以不同，分區(qū)大小固定不變，每個分區(qū)裝一個且只能裝一個作業(yè) 存儲分配：如果有一個空閑區(qū)，則分配給進程,分區(qū)4分區(qū)3分

9、區(qū)2分區(qū)1操作系統(tǒng),,,,,,,,,,,,,,,,,多個等待隊列,單個等待隊列,,,,,,,,,,,,,,分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng),,,,,內(nèi)存分配管理,圖 4-3-3 固定分區(qū)使用表（教材上用標(biāo)志0代表未分配）,通過設(shè)置內(nèi)存分配表，內(nèi)存分配簡單,固定分區(qū)分配算法,5.4.2 地址轉(zhuǎn)換和存儲保護,作業(yè)執(zhí)行過程中不會改變存放區(qū)域，可采用靜態(tài)重定位方式存儲保護：一對寄存器，“下限寄存器”、“上限寄

10、存器”,5.4.3 如何提高主存空間的利用率,根據(jù)經(jīng)常出現(xiàn)作業(yè)的大小和數(shù)量來劃分分區(qū)，盡可能使每個分區(qū)被充分利用分區(qū)按大小排列按作業(yè)對主存空間的需求量排成多個作業(yè)隊列（防止小作業(yè)裝入大分區(qū)，減少閑置的主存空間量）,,,基本思想內(nèi)存不是預(yù)先劃分好的作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配 系統(tǒng)生成后，操作系統(tǒng)占用內(nèi)存的一部分，一般在物理內(nèi)存的開始處，比如，一個操作系統(tǒng)占20KB，裝入系統(tǒng)后占用0～20

11、KB的內(nèi)存空間，剩下的部分作為一個空閑區(qū)，當(dāng)一個用戶程序（作業(yè)、進程）調(diào)入內(nèi)存時，把這個空閑區(qū)的低地址部分的區(qū)域分配給它，如圖所示。,5.5 可變分區(qū)存儲管理方案,,當(dāng)有作業(yè)完成后釋放所占用的存儲區(qū)。 在系統(tǒng)運行的過程中，系統(tǒng)中形成多個空閑的不連續(xù)的存儲區(qū)。,,,,,分區(qū)存儲管理技術(shù)的實現(xiàn)：,1、地址映射2、動態(tài)存儲管理的機構(gòu)（數(shù)據(jù)結(jié)構(gòu)）3、分區(qū)的分配和回收4、三種基本的主存分配方法,1、 用基地址寄存器實現(xiàn)動態(tài)地址映射,在這

12、種存儲管理技術(shù)中，系現(xiàn)設(shè)置一個專用寄存器，稱為基地址寄存器，當(dāng)一個進程（或程序、作業(yè)）被調(diào)度運行時，系統(tǒng)首先從PCB中取出該進程的首地址裝入基地址寄存器中，在該進程運行的過程中實現(xiàn)動態(tài)地址映射。,2、分區(qū)分配機構(gòu),分區(qū)存儲管理使用的數(shù)據(jù)結(jié)構(gòu)主要是空閑區(qū)表、空閑區(qū)隊列兩種。其形式如圖所示。,,,,,,,,,0K,15K,38K,48K,68K,80K,110K,120K,空閑區(qū)表,已分配區(qū)表,,,,,,,,,0K,15K,38K,48K,

13、68K,80K,110K,120K,空閑區(qū)表,已分配區(qū)表,,85K,,98K,,,分區(qū)的分配與回收,一、分配算法介紹空閑區(qū)表數(shù)據(jù)結(jié)構(gòu)的分配算法。 注：1、分配算法中切割空閑區(qū)是從低地址開始的，例如，一個空閑區(qū)大小是100KB，首址是230KB，一申請者要求80KB，分配時將從230KB開始的80KB分配給申請者，剩下的部分仍作為一個空閑區(qū)，其首址是310KB，大小是20KB。2、門限值是切割空閑區(qū)后剩下的區(qū)域若小于門限值，

14、就不切割該空閑區(qū)，統(tǒng)統(tǒng)分給申請者。,分區(qū)分配操作,1) 分配內(nèi)存,圖 4-3-6 內(nèi)存分配流程,分區(qū)的分配與回收,二、回收算法 當(dāng)一個進程（或程序）釋放某內(nèi)存區(qū)時，要調(diào)用存儲區(qū)釋放算法release,它將首先檢查釋放區(qū)是否與空閑區(qū)表（隊列）中的其它空閑區(qū)相鄰，若相鄰則合并成一個空閑區(qū)，否則，將釋放為一個空閑區(qū)插入空閑區(qū)表（或隊列）中的適當(dāng)位置。 空閑釋放區(qū)與空閑區(qū)相鄰有四種情況。,分區(qū)的分配與回收,A、將r合并到f1，f1.

15、addr;f1.size+r.size=>f.sizeB、將r合并到f2, r.addr;r.size+r.size=>f2.sizeC、f1、r、f2 合并到f1, f1.addr; f1.size+r.size+f2.size=>f1.size 撤消f2空閑區(qū)D、r作為一個空閑區(qū)，并插入到空閑區(qū)表的適當(dāng)位置。,,,內(nèi)存分配 動態(tài)分配 四種分配算法：首次適應(yīng)算法、循環(huán)首次適應(yīng)、最佳適

16、應(yīng)算法、最壞適應(yīng)算法,,首次適應(yīng)算法(First Fit: FF) 順序查找空閑區(qū)表，找到第一個滿足的就分割。 分配算法簡單，但可能把大的主存空間分割成許多小的空閑區(qū)，即碎片,分區(qū)管理算法 (可適應(yīng)于固定分區(qū)及可變分區(qū)),,改進：將空白區(qū)按存貯順序鏈成一個隊列，用一指針指向隊首分配時將找到的第一個滿足要求的空白區(qū)分配給它。分配時總是利用低地址部分空閑區(qū)，使高地址部分保持有較大的空閑區(qū),例：

17、,有四塊空白區(qū)(從低地址?高地址)，來了一個作業(yè)需分配19k內(nèi)存。,在高地址空白區(qū)中保持較大空白區(qū)(每次從10k開始分配尋找)。,解：,FF特點：,(ii) 循環(huán)首次適應(yīng)(Next fit: NF),將空白區(qū)組成環(huán)狀隊列，按循環(huán)順序?qū)ふ铱瞻讌^(qū)，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找。(與FF區(qū)別，頭指針從低地址開始向高地址循環(huán)移動),使得小空白區(qū)均勻分布，易于與其它空白區(qū)合并。,NF特點：,(iii) 最佳適應(yīng)算法(Best fi

18、t: BF),? 將空白區(qū)按大小排成隊列，尋找時總是以最小的空白區(qū)開始，找到第一個合適的分區(qū),例：,來一個19k的作業(yè),? 最佳地利用分區(qū)；,? 開銷比較大，并不是最好算法。,特點：,解：,(iv) 最壞適應(yīng)算法(Worst fit: WF),? 將空白區(qū)排序(按從大到小),? 找最大空白區(qū),如上例：,不會出現(xiàn)小的空白區(qū)。,特點：,例：設(shè)系統(tǒng)空白鏈表為,用戶先后申請7.5k，4k試用四種算法，求出分配塊。,先后申請7.5k，4k,后申請

19、4k，再排序從小到大,? 分配塊為d, f,先申請7.5k,WF: e,e,先排序：,5.5.2 地址轉(zhuǎn)換和存儲保護,采用動態(tài)重定位方式裝入作業(yè)硬件設(shè)專用控制寄存器：基址寄存器和限長寄存器（作業(yè)所占分區(qū)的最大地址）基址寄存器內(nèi)容<=絕對地址<=限長寄存器內(nèi)容（p49圖3-13）,可變式分區(qū)與固定式分區(qū)分配方案相比，一般來說其存儲空間的利用率高些，但是，由于存在著一些分散的，較小的空白區(qū)，仍然不能充分利用－稱之為存儲器的“

20、 零頭”。,(d) 碎片(零頭)問題：存在于已分配的分區(qū)之間的一些不能充分利用的空白區(qū),(i) 原因：請求?釋放?使存區(qū)分割,(ii) 碎片總和>nk，但不能裝入nk作業(yè),將碎片集中(緊湊或拼接) ––– 可重定位分配,可重定位分區(qū)分配法是利用分區(qū)的“ 拼接”(對空白區(qū)而言)或“ 緊湊”(作業(yè)程序而言)技術(shù)解決“ 零頭”。（移動：把作業(yè)從一個存儲區(qū)域移到另一個存儲區(qū)域的工作）,(iii) 解決的方法：,移動技術(shù)達到兩個目的

21、：1 集中分散的空閑區(qū)2 便于作業(yè)動態(tài)擴充主存,,,可重定位分區(qū)分配,(a) 概要：,移動內(nèi)存已分配區(qū)的信息，使得所有分配區(qū)靠在一起使空白區(qū)連成一片，采用浮動方法。,(b) 緊湊(重定位－動態(tài))進行主存的壓縮，就要將主存中用戶程序移動(浮動)，對作業(yè)中與地址有關(guān)的部分進行調(diào)整。,(c) 動態(tài)重定位可變分區(qū)分配算法：,例,,,采用動態(tài)重定位技術(shù)(當(dāng)一個作業(yè)裝入與其地址空間不一致的存儲空間時，可在每次訪問指令或數(shù)據(jù)時，通過重定位寄存器來

22、自動修改訪問存儲器的地址),因而，一個作業(yè)在主存中移動后，只需要改變重定位寄存器的內(nèi)容即可。,例: 圖(a)是作業(yè)拼接之前的執(zhí)行情況，這時重定位寄存器RR的值為64k，(b)是拼接后作業(yè)3執(zhí)行情況，作業(yè)3被移動到28k大字節(jié)開始的分區(qū)中。為保證在新的位置上仍能正確執(zhí)行，只需要將重點定位寄存器RR的值改為28k即可。,采取動態(tài)重定位后，由于目標(biāo)程序裝入主存后不需修改地址指針及所有與地址有關(guān)的項，因而程序可在主存中隨意浮動而不影響其正確執(zhí)

23、行。這樣，就可以方便地進行存儲器緊縮，較好地解決了碎片問題。,(d) 拼湊時機,(i) 出現(xiàn)相鄰空白區(qū)即拼接；(或某分區(qū)被釋放后即緊縮),(ii) 存貯不足(空白分區(qū)不夠大)時進行拼接,緊縮工作大，開銷大，但管理簡單,緊縮次數(shù)少，但管理(算法)較復(fù)雜。,前面已有框圖表示,移動技術(shù)注意問題：,增加開銷移動有條件,,改變作業(yè)裝入主存儲器的方式來減少移動的目的,(6) 覆蓋(overlay): 指一個作業(yè)的若干程序段(或數(shù)據(jù)段)或幾個作業(yè)的

24、某些部分間共享某主存空間,(a) 目標(biāo)：用較小的存區(qū)滿足較大的存區(qū)要求,(b) 程序的分析：并不是作業(yè)的每一部分都是時時要用的,覆蓋技術(shù)的出發(fā)點：程序和數(shù)據(jù)并不需要全部裝入內(nèi)存，同一進程內(nèi)不會同時執(zhí)行的程序段可共享同一塊內(nèi)存區(qū),mainA 20k,A0, 30k,B0, 40k,B1, 30k,A2, 30k,A1, 60k,A4, 40k,A3, 20k,,,,,,,,例：,覆蓋技術(shù)是一種早期的內(nèi)存擴充技術(shù)，現(xiàn)已被淘汰。缺點：

25、 1、要求程序員提供程序結(jié)構(gòu)和覆蓋順序，對程序員不透明 2、以程序段為單位（段需要連續(xù)空間），且覆蓋交換是在進程內(nèi)的程序段之間進行，故不能實現(xiàn)虛擬存儲。覆蓋技術(shù)僅僅節(jié)約了內(nèi)存，有內(nèi)存需求下限，190k?110k,(c) 注意：,(i) 每次僅放入作業(yè)的一個部分,(ii) 覆蓋段程序員事先確定,(iii) 系統(tǒng)自動覆蓋－虛存,(iv) 可與其內(nèi)存分配方法結(jié)合使用,交換技術(shù),交換技術(shù)的出發(fā)點：某些進程處于等

26、待狀態(tài)（e.g, I/O），讓它們繼續(xù)駐留內(nèi)存，將會造成內(nèi)存的浪費。故，可將它們換出到外存。方法：選擇某進程，將其換出（即，將其程序或數(shù)據(jù)寫入外存交換區(qū)），再從外存交換區(qū)中將指定的作業(yè)或進程換入（將程序或數(shù)據(jù)讀到內(nèi)存），并讓其執(zhí)行。與覆蓋技術(shù)不同：①交換不要求程序員給出程序之間的覆蓋結(jié)構(gòu)。②交換是在進程間進行；覆蓋是在同一進程內(nèi)的程序段之間進行，并且只能覆蓋那些與自己無關(guān)的程序段。,可變分區(qū)存儲管理方案小結(jié),分區(qū)管理的缺點：

27、1、內(nèi)存利用率不高，存在嚴重的碎片2、由于要求連續(xù)存儲，并占有一個獨立分區(qū)，故進程的大小受分區(qū)大小的限制（固定分區(qū)），或受內(nèi)存可用空間的限制（可變分區(qū)）。覆蓋和交換技術(shù)只是對分區(qū)管理的有限改進。3、不利于程序段和數(shù)據(jù)的共享,問題的提出分區(qū)存儲管理的主要問題是碎片問題。 在采用分區(qū)存儲管理的系統(tǒng)中，會形成一些非常小的分區(qū)，最終這些非常小的分區(qū)不能被系統(tǒng)中的任何用戶（程序）利用而浪費。 造成這樣問題的主要原因是用

28、戶程序裝入內(nèi)存時是整體裝入的，為解決這個問題，提出了分頁存儲管理技術(shù)。,三、頁式存儲管理方案,基本原理,把程序的邏輯地址空間劃分為一些相等的片，稱為頁，邏輯頁把內(nèi)存物理空間也劃分為若干同樣大小的片，稱為頁面，塊，物理頁頁面的大小，由OS決定,頁面的大小是為2n ,通常為1KB，2KB，nKB等。。下圖假設(shè)頁面大小為1k,,某進程的虛擬空間,0k,1k,2k,518 mov eax, [2108],2k+60 115,0,2,

29、1,4,2,7,邏輯頁 物理頁,頁面變換表 PMT,,,,,,,,,,,,,2k,3k,4k,5k,6k,7k,2k+518 mov eax, [2108],7k+60 115,,,,inc eax,inc eax,………,………,………,………,………,………,………,………,………,………,………,………,(頁號) (頁面號),頁面映射表,（頁表）,塊號,作業(yè)2，0頁,,作業(yè)2，1頁,作業(yè)1，0頁,作業(yè)1，

30、1頁,作業(yè)2，2頁,2k,3k,4k,5k,6k,7k,操作,系統(tǒng),1k,0,作業(yè)3，0頁,,8k,9k,10k,,,,,,,作業(yè)1,作業(yè)2,作業(yè)3,0,2,1,4,2,7,0,5,1,6,0,8,,,,,,,,,,,,,作業(yè)3的頁表,內(nèi)存,作業(yè)2的頁表,作業(yè)1的頁表,靜態(tài)頁面管理,頁式管理兩個問題需解決：怎樣知道主存儲器中哪些塊已被占用；作業(yè)被分散存放后如何保證能正確執(zhí)行1、內(nèi)存頁面的分配與回收2、分配算法3、地址變換,5.6

31、.2 內(nèi)存頁面的分配與回收（位示圖）,,,假設(shè)主存可分配區(qū)域256塊塊號=字號×字長+位號字號=〔i/字長〕 位號=i mod 字長,,,分配算法,請求n個頁面,有n個空閑頁嗎,為該進程創(chuàng)建頁表將頁表始址、頁表長度置入請求表，置狀態(tài)=已分配,檢查存儲頁面表（位示圖），找出n個空閑頁，并將頁面號填入頁表,返回,,,,,,有,無,,無法分配,5.6.3 頁表和地址變換,,,,,絕對地址＝塊號×塊長＋頁內(nèi)地址

32、,頁式地址變換,二、虛地址結(jié)構(gòu)(程序字) 虛地址是用戶程序中的邏輯地址，它包括頁號和頁內(nèi)地址（頁內(nèi)位移）。 區(qū)分頁號和頁內(nèi)地址的依椐是頁的大小，頁內(nèi)地址占虛地址的低位部分，頁號占虛地址的高位部分。虛地址共占用32位，假定頁面大小4kb，地址空間最多允許1M頁,,,0,11,12,31,頁號P,頁內(nèi)位移量W,編號0~1048575,相對地址0~4095,,,,,,機器代碼內(nèi)，每個有效地址都可劃分為2部分：,頁號,頁內(nèi)地

33、址,,地址寄存器位數(shù),,與頁面大小有關(guān),例如，有效地址：41014101= 4096+5= 4K+5若頁面1k，則頁號=4，頁內(nèi)地址為50001000000000101但這個頁號是邏輯上的。對應(yīng)內(nèi)存哪個塊，還需查頁表。,,頁號,,,靜態(tài)分頁存儲管理地址變換過程,2500 = 0000100111000100,,,,,,,2,0 9 C 4H,頁式地址映射,1. 虛地址（邏輯地址

34、、程序地址）以十六進制、八進制、二進制的形式給出將虛地址轉(zhuǎn)換成二進制的數(shù)；按頁的大小分離出頁號和位移量（低位部分是位移量，高位部分是頁號）；根據(jù)題意產(chǎn)生頁表；將位移量直接復(fù)制到內(nèi)存地址寄存器的低位部分；以頁號查頁表，得到對應(yīng)頁裝入內(nèi)存的塊號，并將塊號轉(zhuǎn)換成二進制數(shù)填入地址寄存器的高位部分，從而形成內(nèi)存地址。,頁式地址變換 二、虛地址結(jié)構(gòu),頁式地址變換 三、頁式地址映射,例1：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，

35、頁大小為2KB，依次裝入內(nèi)存的第7、9、A、5塊，試將虛地址0AFEH，1ADDH轉(zhuǎn)換成內(nèi)存地址。虛地址0AFEH0000 1010 1111 1110P＝1 W＝010 1111 1110MR＝0100 1010 1111 1110 ＝4AFEH,頁式地址變換 三、頁式地址映射,虛地址1ADDH0001 1010 1101 1101P＝3W＝010 1101 1101MR＝0010 1010 1101 1101＝

36、2ADDH,頁式地址變換 三、頁式地址映射,2、虛地址以十進制數(shù)給出 頁號＝虛地址％頁大小 位移量＝虛地址 mod 頁大小根據(jù)題意產(chǎn)生頁表；以頁號查頁表，得到對應(yīng)頁裝入內(nèi)存的塊號內(nèi)存地址＝塊號×頁大小＋位移量,頁式地址變換 三、頁式地址映射,例2：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。,頁式地址變換 三

37、、頁式地址映射,虛地址 3412P＝3412 ％ 2048 ＝1W＝ 3412 mod 2048 ＝ 1364MR=9*2048+1364=19796虛地址3412的內(nèi)存地址是：19796,頁式地址變換 三、頁式地址映射,虛地址 7145P＝7145 ％ 2048 ＝3W＝7145 mod 2048 ＝1001MR=5*2048+1001=11241虛地址7145的內(nèi)存地址是：11241,系統(tǒng)內(nèi)有很多進程，每個進

38、程都有頁表。到底查哪個頁表？看頁表地址寄存器。每個進程的頁表始址放到請求表中，進程被調(diào)度運行時，其頁表始址存到頁表地址寄存器中。,分頁管理中，指令執(zhí)行速度比分區(qū)管理慢,因為每執(zhí)行一條指令都要2次訪問內(nèi)存：一，查頁表，把頁號變成塊號；二，按實際地址，取所要的數(shù)據(jù)或指令。從而降低了速度。而分區(qū)管理中，只需要一次高速緩沖存儲器（快表）：設(shè)置一個小容量的高速緩沖存儲器，可根據(jù)指定的特征對每個單元進行并行查找，因而插座速度快，但造價高。它

39、始終存放正在執(zhí)行的進程當(dāng)前常用的部分頁表，也叫快表。雙管齊下：一方面，在高速緩沖存儲器中的小頁表中查；同時在該進程的總的頁表中查。,例：設(shè)訪問主存時間為200ns,訪問高速緩存的時間為40ns，命中率為90％，則平均存取時間為多少？,查頁表兩次訪存：平均為200＋200＝400ns,查塊表(200+40)×90％＋(200+200)×10％＝256ns,解：,方法1：,方法2：,快表能提高系統(tǒng)的性能,,整個系統(tǒng)只

40、有一個高速緩沖存儲器，只有占用處理器者才能使用它。當(dāng)讓出處理器時，應(yīng)把該作業(yè)的快表保護到它的進程控制塊中。,5.6.4 頁的共享和保護,,動態(tài)頁面管理,和分區(qū)管理相比，靜態(tài)頁面管理的優(yōu)點：解決了碎片問題，每個進程浪費的空間小于1個頁面靜態(tài)頁面管理的不足：由于要求將進程的程序和數(shù)據(jù)全部裝入才能運行，故進程的大小受到內(nèi)存可用頁面數(shù)的限制。,動態(tài)頁式管理,請求頁式管理,預(yù)調(diào)入頁式管理,,前面所介紹的各種存儲器管理方式，出現(xiàn)了下面

41、這樣兩種情況：（1）有的作業(yè)很大，其所要求的內(nèi)存空間超過了內(nèi)存總?cè)萘?，作業(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無法運行。（2）有大量作業(yè)要求運行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存讓它們先運行，而將其它大量的作業(yè)留在外存上等待。,5.6.5 什么是虛擬存儲器,1．常規(guī)存儲器管理方式的特征 ：（1）一次性。 作業(yè)在運行前需一次性地全部裝入內(nèi)存，如果一次性地裝入其全部程序，也是一種對內(nèi)存空間的浪費。 （

42、2）駐留性。 作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運行結(jié)束。盡管運行中的進程會因I／O而長期等待，仍將繼續(xù)占用寶貴的內(nèi)存資源。,2．局部性原理 （1）程序執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的。 （2）過程調(diào)用將會使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過5層。這就是說，程序?qū)谝欢螘r間內(nèi)都局限在這些過程的范圍內(nèi)運行。,（3）程

43、序中存在許多循環(huán)結(jié)構(gòu)，這些雖然只由少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行。（4）程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對數(shù)組進行操作，它們往往都局限于很小的范圍內(nèi)。,局限性又表現(xiàn)在下述兩個方面： （1）時間局限性。 產(chǎn)生時間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。 （2）空間局限性。 一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)

44、。,,互斥性：在程序的一次運行中，執(zhí)行了這部分程序就不會執(zhí)行那部分，如：錯誤處理程序,提出問題：,能否不把程序全部裝入主存?允許用戶的邏輯地址空間大于主存的絕對地址空間容量由地址結(jié)構(gòu)和輔助存儲器的容量決定,3．虛擬存儲器定義 基于局部性原理，應(yīng)用程序在運行之前，沒有必要全部裝入內(nèi)存，僅須將那些當(dāng)前要運行的部分頁面或段先裝入內(nèi)存便可運行，其余部分暫留在盤上。 所謂虛擬存儲器：是指具有請求調(diào)入功能和置換功能，能從邏

45、輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)，其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。,,某進程的虛擬空間,0k,1k,2k,518 mov eax, [2108],2k+60 115,0,2,1,4,2,,邏輯頁 物理頁,頁面變換表 PMT,,,,,,,,,,,,,2k,3k,4k,5k,6k,7k,2k+518 mov eax, [2108],,,inc e

46、ax,inc eax,………,………,………,………,………,………,………,………,………,………,(頁號) (頁面號),頁面映射表,（頁表）,塊號,頁式虛擬存儲管理,該進程只獲得2個頁面，邏輯第2頁不在內(nèi)存,請求分頁存儲管理,請求式分頁存儲管理與靜態(tài)分頁存儲管理相比： 。請求式分頁管理的地址重定位，可能會出現(xiàn)

47、 的情況，此時，系統(tǒng)必須解決以下幾個問題：（1）只裝入部分代碼，能否正確運行？（2）當(dāng)程序要訪問的某虛頁不在內(nèi)存時，如何 這種缺頁情況？（3）發(fā)現(xiàn)后應(yīng)如何 ？（缺頁中斷）（4）當(dāng)需要把外存上的某個頁面調(diào)入內(nèi)存時，此時內(nèi)存中沒有空閑頁應(yīng)怎么辦？ 哪個頁面？（頁面置換算法）,不同之處在于地址重定位問題,所需頁面不在主存,發(fā)現(xiàn),處理

48、,淘汰,為了幫助操作系統(tǒng)對要置換出內(nèi)存的頁面進行選擇，對頁表進行改造，以反映該頁最近的使用情況。一般來說，一個頁表的表目通?？砂ㄈ缦碌臄?shù)據(jù)內(nèi)容：,,,為了保證程序能夠正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁存放在磁盤上，以便將所需要的頁調(diào)入內(nèi)存，該過程稱為頁面調(diào)度。通常，把選擇換出頁面的算法稱為頁面調(diào)度算法（置換算法）。頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩

49、潰。這種現(xiàn)象稱為顛簸或抖動,2. 頁面調(diào)度,1最佳（Optimal）置換算法,調(diào)入一個新頁而必須淘汰一個舊頁時，所淘汰的頁應(yīng)該是以后不再訪問的頁，或距現(xiàn)在最長時間以后才會訪問的頁。僅僅是一個理論算法而已。因為在實際應(yīng)用中，我們無法判斷哪一頁是以后不再訪問的頁或距離現(xiàn)在最長時間以后再訪問的頁。,Optimal算法,系統(tǒng)為某個進程分配了3個物理塊，假設(shè)進程按照以下頁號的順序來訪問頁面;7,0,1,2,0,3,0,4,2,3,0,3,2,1

50、,2,0,1,7,0,1,3個物理塊,7,0,1,2,0,3,0,4,2,3,0,3 2,1,2,0,1,7,0,1,共發(fā)生幾次缺頁中斷？,6次。這是最理想的情況，置換的次數(shù)最少,2先進先出頁面置換算法（FIFO),基于程序總是按線性順序來訪問物理空間這一假設(shè)。算法總是淘汰最先調(diào)入主存的那一頁，或者說在主存中駐留時間最長的那一頁。,先進先出算法,系統(tǒng)為某個進程分配了3個物理塊，假設(shè)進程按照以下頁號的順序來訪問頁面;7,0,1,2,0

51、,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,3個物理塊,7,0,1,2,0,3,0,4,2,3,0,3 2,1,2,0,1,7,0,1,總共發(fā)生幾次缺頁中斷？,12次。可以看出這種算法性能不佳,,,FIFO實現(xiàn)技術(shù),系統(tǒng)中設(shè)置一張具有m個元素的頁號表，它是Ｍ個數(shù)：P[0]， P[1]， …， P[m-1] 組成的數(shù)組，每個P[i] (i =0，1，…m-1) 存儲一個在主存中的頁面的頁號。用指針k指示當(dāng)

52、前調(diào)入新頁時應(yīng)淘汰的那一頁在頁號表中的位置。每當(dāng)調(diào)入一個新頁后，執(zhí)行P[k] := 新頁的頁號;k := （k+1）mod m;,FIFO另一個實現(xiàn)算法,引入指針鏈成隊列，只要把進入主存的頁面按時間的先后次序鏈接，新進入的頁面從隊尾入隊，淘汰總是從隊列頭進行。,缺頁中斷率,假定作業(yè)p共計n頁，系統(tǒng)分配給它的物理塊只有m塊（１≤m≤n）。如果作業(yè)p在運行中成功的訪問次數(shù)為s（訪問的地址都在內(nèi)存中）， 不成功的訪問次數(shù)為F（訪問的地址在

53、外存），則總的訪問次數(shù)Ａ為：A = S + F 則缺頁中斷率為：f = F / A,影響缺頁中斷率的因素,稱f為缺頁中斷率。影響缺頁中斷率f的因素有： (1)主存頁框數(shù)。 (2)頁面大小。 (3)頁面替換算法。 (4)程序特性。,3最近最久未使用置換算法LRU,被換出頁面是在最近一段時間里最久未被訪問的那頁。根據(jù)程序局部性原理，那些剛被使用過的頁面，可能馬上還要被使用，而在較長時間里未被使用的頁

54、面，可能不會馬上使用到。,3個物理塊,7,0,1,2,0,3,0,4,2,3,0,3,1,2,0,1,7,0,1,LRU算法,2,置換,置換,置換,置換,共發(fā)生9次置換,LRU算法實現(xiàn)：頁面淘汰隊列(1),隊列中存放當(dāng)前在主存中的頁號，每當(dāng)訪問一頁時就調(diào)整一次，使隊列尾總指向最近訪問的頁，隊列頭就是最近最少用的頁（書上采用此方法）。發(fā)生缺頁中斷時總淘汰隊列頭所指示的頁；執(zhí)行一次頁面訪問后，需要從隊列中把該頁調(diào)整到隊列尾。,LRU算法實

55、現(xiàn)：頁面淘汰隊列(2),訪問頁號 頁面淘汰序列 被淘汰頁面 4 4 3 4 3 0 4 3 0 4 3 0 4 1 0 4 1 3 1

56、 0 4 1 2 4 1 2 0 3 1 2 3 4 2 1 3 2,LRU算法實現(xiàn)：標(biāo)志位法,每頁設(shè)置一個引用標(biāo)志位R，訪問某頁時，由硬件將頁標(biāo)志位R置1，隔一

57、定時間t將所有頁的標(biāo)志R均清0。發(fā)生缺頁中斷時，從標(biāo)志位R為0的頁中挑選一頁淘汰。挑選到要淘汰的頁后，也將所有頁的標(biāo)志位R清0。,LRU算法實現(xiàn)：多位寄存器法,例如，r寄存器共有四位，頁面P0、P1、P2在T1、T2、T3時刻的r寄存器內(nèi)容如下： 頁面 時刻 T1 T2

58、 T3 P0 1000 0100 1010 P1 1000 1100 0110 P2 0000 1000 0100 訪問就高位置1,每隔一定時間將寄存器右移一位！,LRU算法實現(xiàn)：多位計數(shù)器法,每個頁面設(shè)置一個多

59、位計數(shù)器，又叫最不常用頁面替換算法LFU。每當(dāng)訪問一頁時，就使它對應(yīng)的計數(shù)器加１。當(dāng)發(fā)生缺頁中斷時，可選擇計數(shù)值最小的對應(yīng)頁面淘汰，并將所有計數(shù)器全部清０。,LRU算法實現(xiàn)：多位計時器法,為每個頁面設(shè)置一個多位計時器，每當(dāng)頁面被訪問時，系統(tǒng)的絕對時間記入計時器。比較各頁面的計時器的值，選最小值的未使用的頁面淘汰，因為，它是最“老”的未使用的頁面。,書上實現(xiàn)方法：,為頁表增加引用位，記錄該頁面自上次被訪問以來所經(jīng)歷的時間，每訪問一次都

60、應(yīng)重新計時。淘汰時選擇計時值最大的一個。并把所有的引用位置0，重新計時.該法必須對每一頁的訪問情況時時刻刻加以記錄和更新，實現(xiàn)起來困難，且開銷大。,最近最不經(jīng)常使用調(diào)度算法（LFU）,該算法是基于過去一段時間里被訪問次數(shù)多的頁可能是經(jīng)常需要用的頁，所以應(yīng)調(diào)出被訪問次數(shù)少的頁設(shè)計數(shù)器，每訪問一頁就將該頁對應(yīng)的計數(shù)器加1,隔一定周期把所有計數(shù)器清0.關(guān)鍵是選擇一個合適的周期T,4)第二次機會頁面替換算法(1),改進FIFO算法，把F

61、IFO與頁表中的”引用位”結(jié)合起來使用： ?檢查FIFO中的隊首頁面(最早進入主存的頁面)，如果它的”引用位”是0，這個頁面既老又沒有用，選擇該頁面淘汰;,第二次機會頁面替換算法(2),?如果”引用位”是1，說明它進入主存較早，但最近仍在使用。把它的”引用位”清0，并把這個頁面移到隊尾，把它看作是一個新調(diào)入的頁。 ?算法含義：最先進入主存的頁面，如果最近還在被使用的話，仍然有機會作為像一個新調(diào)入頁面一樣留在主存中。,5）時鐘頁面

62、替換算法ClockPolicy(1),算法實現(xiàn)要點(1)：? 一個頁面首次裝入主存，其“引用位”置1 。主存中的任何頁面被訪問時， ”引用位”置1。淘汰頁面時，從指針當(dāng)前指向的頁面開始掃描循環(huán)隊列，把遇到的”引用位”是1的頁面的”引用位”清0，跳過這個頁面; 把所遇到的”引用位”是0的頁面淘汰掉，指針推進一步。,時鐘頁面替換算法(Clock Policy)(2),算法實現(xiàn)要點(2)：掃描循環(huán)隊列時，如果遇到的所有頁面的”引用

63、位”為1，指針就會繞整個循環(huán)隊列一圈，把碰到的所有頁面的”引用位”清0;指針停在起始位置，并淘汰掉這一頁，然后，指針推進一步。,時鐘頁面替換算法的一個例子,,一個例子，計算缺頁中斷次數(shù)和被淘汰頁面(1),假設(shè)采用固定分配策略，進程分得三個頁框，執(zhí)行中按下列次序引用5個獨立的頁面: 2 3 2 1 5 2 4 5 3 2 5 2。,一個例子，計算缺頁中斷次數(shù)和被淘汰頁面(2),性能比較 OPT F

64、(1) F(2) F(4)LRU F(3) F(1) F(2) F(4)CLOCK F(2) F(3) F(1) F(5) F(4) FIFO F(2) F(3) F(1) F(5) F(2) F(4),2 3 2 1 5 2 4 5 3 2 5 2,影響缺頁中斷率的因素,1．分配的內(nèi)存頁面數(shù)2．頁面的大小3．頁面置換算法性能4．程序設(shè)計的質(zhì)量,例：1024*1024

65、數(shù)組，每元素1字節(jié)，OS每頁1k，即每行1頁,for(i=1;i<=1024;i++) for(j=1;j<=1024;j++)a[i,j]=0;,for(j=1;j<=1024;j++) for(i=1;i<=1024;i++)a[i,j]=0;,【例1】主存塊數(shù)m=3，置換算法采用FIFO算法，缺頁中斷次數(shù)及缺頁率如下圖所示。在下圖中，P行表示頁面走向，M行表示在主存中的頁面號，其中帶有

66、+的表示新調(diào)入頁面，在M行的各列按調(diào)入的順序排列，帶有圓圈的數(shù)字表示下一時刻將被淘汰頁面，F(xiàn)行表示是否引起缺頁中斷，帶√號的表示引起缺頁中斷。從下圖可以看出，缺頁中斷頁數(shù)為9次，缺頁率f=9/12=75%。,FIFO算法性能分析（m=3）,【例2】設(shè)m=4，仍采用FIFO算法，缺頁中斷次數(shù)及缺頁率如圖4.24所示?？梢运愠觯诜峙浣o該作業(yè)的內(nèi)存塊數(shù)增加到4時，缺頁中斷由圖4.23的9次反而增加到了10次，缺頁率由75%增加到10/12=

67、83%，這就是FIFO算法的一種異?，F(xiàn)象。隨著分配的主存塊數(shù)的增加，缺頁中斷次數(shù)不但沒有降低，反而增加了。這與該算法不考慮程序的動態(tài)特征有關(guān)。,FIFO算法性能分析（m=4）,【例3】設(shè)m=3，采用LRU算法，缺頁中斷次數(shù)及缺頁率如圖所示。,LRU算法性能分析（m=3）,,,,【例4】設(shè)m=4，其余同例3，則缺頁中斷次數(shù)及缺頁率如圖4.26所示。,LRU算法性能分析（m=4）,6請求分頁虛擬存儲管理的幾個設(shè)計問題,(1)頁面大小

68、.從頁表大小考慮 .從主存利用率考慮 .從讀寫一個頁面所需時間考慮,最佳頁面尺寸(1),假定S表示用戶作業(yè)程序的字節(jié)數(shù)平均長度，P表示以字節(jié)為單位的頁面長度，且有S>>P，頁表項需要e個字節(jié)。作業(yè)的頁表長度為S/P，占用了Se/P個字節(jié)的頁表空間，作業(yè)的最后一頁，浪費的主存平均為P/2字節(jié)。對一個作業(yè)而言： 浪費的存儲字=頁表使用的主存空間+內(nèi)部碎片=Se/P+P/2,最佳頁面尺寸(2),頁面較小時