第5章 存儲(chǔ)器管理2_chd

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

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

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

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

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

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

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

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

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

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

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

12、種存儲(chǔ)管理技術(shù)中，系現(xiàn)設(shè)置一個(gè)專用寄存器，稱為基地址寄存器，當(dāng)一個(gè)進(jìn)程（或程序、作業(yè)）被調(diào)度運(yùn)行時(shí)，系統(tǒng)首先從PCB中取出該進(jìn)程的首地址裝入基地址寄存器中，在該進(jìn)程運(yùn)行的過(guò)程中實(shí)現(xiàn)動(dòng)態(tài)地址映射。,2、分區(qū)分配機(jī)構(gòu),分區(qū)存儲(chǔ)管理使用的數(shù)據(jù)結(jié)構(gòu)主要是空閑區(qū)表、空閑區(qū)隊(duì)列兩種。其形式如圖所示。,,,,,,,,,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ū)是從低地址開始的，例如，一個(gè)空閑區(qū)大小是100KB，首址是230KB，一申請(qǐng)者要求80KB，分配時(shí)將從230KB開始的80KB分配給申請(qǐng)者，剩下的部分仍作為一個(gè)空閑區(qū)，其首址是310KB，大小是20KB。2、門限值是切割空閑區(qū)后剩下的區(qū)域若小于門限值，

14、就不切割該空閑區(qū)，統(tǒng)統(tǒng)分給申請(qǐng)者。,分區(qū)分配操作,1) 分配內(nèi)存,圖 4-3-6 內(nèi)存分配流程,分區(qū)的分配與回收,二、回收算法 當(dāng)一個(gè)進(jìn)程（或程序）釋放某內(nèi)存區(qū)時(shí)，要調(diào)用存儲(chǔ)區(qū)釋放算法release,它將首先檢查釋放區(qū)是否與空閑區(qū)表（隊(duì)列）中的其它空閑區(qū)相鄰，若相鄰則合并成一個(gè)空閑區(qū)，否則，將釋放為一個(gè)空閑區(qū)插入空閑區(qū)表（或隊(duì)列）中的適當(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作為一個(gè)空閑區(qū)，并插入到空閑區(qū)表的適當(dāng)位置。,,,內(nèi)存分配 動(dòng)態(tài)分配 四種分配算法：首次適應(yīng)算法、循環(huán)首次適應(yīng)、最佳適

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35、頁(yè)大小為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,頁(yè)式地址變換 三、頁(yè)式地址映射,虛地址1ADDH0001 1010 1101 1101P＝3W＝010 1101 1101MR＝0010 1010 1101 1101＝

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

55、現(xiàn)：頁(yè)面淘汰隊(duì)列(2),訪問(wèn)頁(yè)號(hào) 頁(yè)面淘汰序列 被淘汰頁(yè)面 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算法實(shí)現(xiàn)：標(biāo)志位法,每頁(yè)設(shè)置一個(gè)引用標(biāo)志位R，訪問(wèn)某頁(yè)時(shí)，由硬件將頁(yè)標(biāo)志位R置1，隔一

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

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

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

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

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

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

63、位”為1，指針就會(huì)繞整個(gè)循環(huán)隊(duì)列一圈，把碰到的所有頁(yè)面的”引用位”清0;指針停在起始位置，并淘汰掉這一頁(yè)，然后，指針推進(jìn)一步。,時(shí)鐘頁(yè)面替換算法的一個(gè)例子,,一個(gè)例子，計(jì)算缺頁(yè)中斷次數(shù)和被淘汰頁(yè)面(1),假設(shè)采用固定分配策略，進(jìn)程分得三個(gè)頁(yè)框，執(zhí)行中按下列次序引用5個(gè)獨(dú)立的頁(yè)面: 2 3 2 1 5 2 4 5 3 2 5 2。,一個(gè)例子，計(jì)算缺頁(yè)中斷次數(shù)和被淘汰頁(yè)面(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,影響缺頁(yè)中斷率的因素,1．分配的內(nèi)存頁(yè)面數(shù)2．頁(yè)面的大小3．頁(yè)面置換算法性能4．程序設(shè)計(jì)的質(zhì)量,例：1024*1024

65、數(shù)組，每元素1字節(jié)，OS每頁(yè)1k，即每行1頁(yè),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算法，缺頁(yè)中斷次數(shù)及缺頁(yè)率如下圖所示。在下圖中，P行表示頁(yè)面走向，M行表示在主存中的頁(yè)面號(hào)，其中帶有

66、+的表示新調(diào)入頁(yè)面，在M行的各列按調(diào)入的順序排列，帶有圓圈的數(shù)字表示下一時(shí)刻將被淘汰頁(yè)面，F(xiàn)行表示是否引起缺頁(yè)中斷，帶√號(hào)的表示引起缺頁(yè)中斷。從下圖可以看出，缺頁(yè)中斷頁(yè)數(shù)為9次，缺頁(yè)率f=9/12=75%。,FIFO算法性能分析（m=3）,【例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=

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

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