第四章 存儲(chǔ)管理

4.1

存儲(chǔ)器工作原理

4.2連續(xù)存儲(chǔ)空間管理4.3分頁(yè)式存儲(chǔ)管理4.4分段式存儲(chǔ)管理4.5虛擬存儲(chǔ)管理第四章存儲(chǔ)管理如何對(duì)存儲(chǔ)器加以有效的管理，不僅直接影響到存儲(chǔ)器的利用率，而且還對(duì)系統(tǒng)性能有重大影響。存儲(chǔ)器管理的主要對(duì)象是內(nèi)存。存儲(chǔ)管理的功能:分配和去配、抽象和映射、隔離與共享、存儲(chǔ)擴(kuò)充。4.1.1存儲(chǔ)器的層次寄存器高速緩存主存儲(chǔ)器磁盤(pán)緩存固定磁盤(pán)可移動(dòng)存儲(chǔ)介質(zhì)4.1

存儲(chǔ)器訪問(wèn)速度往上越高容量越往下越大如何將一個(gè)用戶源程序變成一個(gè)可在內(nèi)存中執(zhí)行的程序，通常要經(jīng)過(guò)3步驟：編譯:由編譯程序（Compiler）將用戶源代碼編譯成若個(gè)目標(biāo)模塊（ObjectModule）。鏈接:由鏈接程序（Linker）將編譯后形成的一組目標(biāo)模塊，以及它們所需要的庫(kù)函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊。裝入:由裝入程序（Loader）將裝入模塊裝入內(nèi)存。-程序的裝入和鏈接4.1.2地址轉(zhuǎn)換與存儲(chǔ)保護(hù)編輯―――編譯―――鏈接―――裝入―――運(yùn)行1.程序編譯源程序經(jīng)過(guò)編譯程序或匯編程序的處理來(lái)獲得多個(gè)目標(biāo)模塊處理時(shí)編譯程序負(fù)責(zé)記錄模塊內(nèi)引用的發(fā)生位置目標(biāo)模塊附有供引用使用的內(nèi)部符號(hào)表和外部符號(hào)表符號(hào)表給出了各個(gè)符號(hào)名及在本目標(biāo)模塊中的名字地址，在模塊被鏈接時(shí)進(jìn)行轉(zhuǎn)換2.程序鏈接1)靜態(tài)鏈接:在程序裝入之前，先將各目標(biāo)模塊及它們所需的庫(kù)函數(shù)，鏈接成一個(gè)完整的裝配模塊，以后不再拆開(kāi)。2)裝入時(shí)動(dòng)態(tài)鏈接:這是指將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式。a.便于修改和更新b.便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享3)運(yùn)行時(shí)動(dòng)態(tài)鏈接:這是指對(duì)某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該(目標(biāo))模塊時(shí)，才對(duì)它進(jìn)行的鏈接。模塊Aifx>1CALLB;elseCALLC;RETURN模塊BCALLC;RETURN模塊CRETURN0L-10M-10N-1(a)目標(biāo)模塊模塊Aifx>1JSRL;elseJSRL+M;RETURN模塊BJSRL+M;RETURN模塊CRETURN0L-1LL+M-1L+ML+M+N-1(b)裝入模塊三種裝入方式：絕對(duì)裝載方式、可重定位裝載方式、動(dòng)態(tài)運(yùn)行時(shí)轉(zhuǎn)載方式。1、絕對(duì)裝載：編譯后，裝入前已產(chǎn)生了絕對(duì)地址（內(nèi)存地址），裝載時(shí)不再作地址重定位。絕對(duì)地址的產(chǎn)生：（1）由編譯器完成，（2）由程序員編程完成。對(duì)（1）而言，編程用符號(hào)地址。

程序每次必須裝入同一內(nèi)存區(qū)；程序員必須事先了解內(nèi)存的使用情況，根據(jù)內(nèi)存情況確定程序的邏輯地址；程序的修改將引起整個(gè)程序中指令地址的變動(dòng)；程序所有的存儲(chǔ)引用（函數(shù)調(diào)用），在裝入之前都必須轉(zhuǎn)換為物理地址，這不利于存儲(chǔ)共享。3.程序轉(zhuǎn)載2、可重定位裝載方式

(靜態(tài)地址重定位)目標(biāo)模塊的起始地址通常是從0開(kāi)始的，程序中的其它地址也都是相對(duì)于起始地址計(jì)算的。由裝載程序?qū)⒀b載模塊裝入內(nèi)存后，裝載模塊中程序所訪問(wèn)的所有邏輯地址與實(shí)際裝載內(nèi)存的物理地址不同，必須進(jìn)行地址映射，將邏輯地址轉(zhuǎn)換為物理地址。靜態(tài)重定位技術(shù)：地址映射在程序裝載時(shí)進(jìn)行，以后不再更改程序地址。0100025005000LOAD1,2500LOAD1,1250036536510000110001250015000目標(biāo)模塊裝入內(nèi)存LOADj365符號(hào)地址相對(duì)地址絕對(duì)地址裝入模塊j3.動(dòng)態(tài)重定位在程序運(yùn)行時(shí)動(dòng)態(tài)進(jìn)行程序的地址轉(zhuǎn)換。硬件的支持，即重定位寄存器，用于保存程序的在內(nèi)存中的起始地址。能保證進(jìn)程的可移動(dòng)性，有效的提高內(nèi)存的使用效率。運(yùn)行時(shí)重定位有利于多道程序環(huán)境下，進(jìn)程的換進(jìn)/換出及實(shí)現(xiàn)緊湊技術(shù)。load1,2500365load1,25003650100250050002500500005000050100+5250055000作業(yè)J處理機(jī)一側(cè)存儲(chǔ)器一側(cè)重定位寄存器(分區(qū)首地址寄存器)相對(duì)地址4.2.1固定分區(qū)存儲(chǔ)管理4.2.2可變分區(qū)存儲(chǔ)管理

4.2.3伙伴系統(tǒng)4.2.4主存不足的存儲(chǔ)管理技術(shù)4.2連續(xù)存儲(chǔ)管理4.2.1固定分區(qū)存儲(chǔ)管理分區(qū)管理：是一種簡(jiǎn)單使用的存貯管理方案，把內(nèi)存空間靜態(tài)的（動(dòng)態(tài)的）分割成若干大小可以不等的區(qū)域，每個(gè)作業(yè)分配一片連續(xù)的存儲(chǔ)空間，程序一次整體裝入固定式分區(qū)管理：將內(nèi)存空間靜態(tài)的分割成若干大小可以不等的區(qū)域，每個(gè)分區(qū)只能裝入一道作業(yè)，分區(qū)的個(gè)數(shù)是內(nèi)存中作業(yè)的最大道數(shù)操作系統(tǒng)區(qū)用戶分區(qū)1用戶分區(qū)2用戶分區(qū)3固定分區(qū)存儲(chǔ)管理(續(xù))劃分分區(qū)的方法：分區(qū)大小相等：將內(nèi)存分割成若干個(gè)大小相等的區(qū)（太大造成內(nèi)存的浪費(fèi)，太小不能裝入進(jìn)程運(yùn)行，缺乏靈活性）分區(qū)大小不等：一部分大的一部分小的，一部分適中的注意：一個(gè)分區(qū)分配了一個(gè)作業(yè)后剩余空間便不能再用，這稱為內(nèi)碎片；當(dāng)一個(gè)區(qū)域小于一個(gè)作業(yè)時(shí)便整塊被丟棄，稱為外碎片為了記住哪些分區(qū)是空閑分區(qū)，哪些分區(qū)是已分配分區(qū)，系統(tǒng)可設(shè)置如下主存分配表：分區(qū)號(hào)大小(KB)起址(KB)狀態(tài)1824已分配21632已分配33248已分配46480未分配5128144已分配操作系統(tǒng)作業(yè)A(7K)作業(yè)B(13K)作業(yè)C(23K)空閑分區(qū)作業(yè)D(80K)24K32K48K144K272K~~80K分區(qū)描述表內(nèi)存分配情況碎片固定分區(qū)存儲(chǔ)管理(續(xù))缺點(diǎn)：固定分區(qū)存儲(chǔ)管理限制了程序的大小,無(wú)法運(yùn)行超過(guò)分區(qū)大小的程序內(nèi)存空間利用率不高不便于程序動(dòng)態(tài)擴(kuò)充內(nèi)存限制了程序道數(shù)固定分區(qū)存儲(chǔ)管理適合于程序大小和出現(xiàn)頻率已知的情形4.2.2可變分區(qū)存儲(chǔ)管理按照作業(yè)的大小來(lái)劃分分區(qū)，劃分的時(shí)間、大小和位置都是動(dòng)態(tài)的。系統(tǒng)啟動(dòng)后用戶作業(yè)裝入內(nèi)存之前，整個(gè)用戶區(qū)是一個(gè)大的空閑分區(qū)，隨著作業(yè)的裝入和撤離，內(nèi)存空間被分成許多大小不一的分區(qū)，有的分區(qū)正被作業(yè)占用，有的分區(qū)是空閑的。當(dāng)一個(gè)新的作業(yè)要求裝入時(shí)，必須找到一個(gè)足夠大的空閑區(qū)，如果找到的空閑分區(qū)大于作業(yè)需要量，則把該空閑分區(qū)分成兩部分，一部分分配給作業(yè)，另一部分作為一個(gè)較小的空閑分區(qū)。當(dāng)一個(gè)作業(yè)運(yùn)行結(jié)束時(shí)，它歸還的分區(qū)如果與其它空閑分區(qū)相鄰，則還要進(jìn)行合并，形成一個(gè)大的空閑分區(qū)。一、分區(qū)組織1．空閑分區(qū)表：在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個(gè)空閑分區(qū)的情況。2．空閑分區(qū)鏈：為了實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接，設(shè)置前向指針和后向指針，通過(guò)前、后向鏈接指針將所有的空閑分區(qū)鏈接成一個(gè)雙向鏈。前向指針?lè)謪^(qū)信息N個(gè)字節(jié)可用后向指針系統(tǒng)區(qū)A(8K)B(16K)C(20K)D(28K)E(56K)F(2K)G(40K)..024K32K48K68K96K152K154K194K256kA、B、C、D、E、F、G任務(wù)陸續(xù)進(jìn)入內(nèi)存進(jìn)行執(zhí)行，T0時(shí)刻，A、C、E、G已經(jīng)完成，請(qǐng)畫(huà)出當(dāng)前時(shí)刻空閑分區(qū)表。如果此時(shí)有來(lái)了一個(gè)15K大小H任務(wù)，會(huì)分在哪個(gè)空閑分區(qū)里面。分區(qū)號(hào)大小(KB)起址(KB)狀態(tài)1824未分配22048未分配35696未分配440154未分配562194未分配空閑分區(qū)表1．最先適應(yīng)算法（首次適應(yīng)算法）。每次都從頭開(kāi)始，尋找第一個(gè)滿足需求的空閑分區(qū)。特點(diǎn)：找到第一個(gè)大小滿足的分區(qū)，劃分。有碎片（外零頭），低址內(nèi)存使用頻繁。2．下次首次適應(yīng)算法（循環(huán)首次適應(yīng)算法）。與1類(lèi)似，從上次找到的空閑分區(qū)的下一個(gè)開(kāi)始查找。特點(diǎn)：空閑分區(qū)分布均勻，提高了查找速度；缺乏大的空閑分區(qū)3．最佳適應(yīng)算法（最優(yōu)適應(yīng)算法）分區(qū)按大小遞增排序；分區(qū)釋放時(shí)需插入到適當(dāng)位置。特點(diǎn)：產(chǎn)生無(wú)法利用的小碎片。4.最壞適應(yīng)算法掃描整個(gè)空閑分區(qū)表或空閑分區(qū)鏈,總是挑選一個(gè)最大的空閑區(qū)分割給作業(yè)使用特點(diǎn)：分割剩余的空閑區(qū)不至于太小二、分區(qū)分配當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，需合并相鄰的空閑分區(qū)，形成大的分區(qū)，稱為合并技術(shù)。（1）上鄰空閑區(qū)：合并，改大?。?）下鄰空閑區(qū)：合并，改大小，首址。（3）上、下鄰空閑區(qū)：合并，改大小。（4）不鄰接，則建立一新表項(xiàng)。三、分區(qū)回收進(jìn)程1F1回收區(qū)進(jìn)程2進(jìn)程3進(jìn)程1進(jìn)程2回收區(qū)F2進(jìn)程3進(jìn)程1F1回收區(qū)F2進(jìn)程2內(nèi)存回收時(shí)的情況F1進(jìn)程1回收區(qū)進(jìn)程2F22.地址轉(zhuǎn)換與存儲(chǔ)保護(hù)可變分區(qū)方式采用動(dòng)態(tài)重定位裝入作業(yè),作業(yè)程序和數(shù)據(jù)的地址轉(zhuǎn)換由硬件完成.硬件設(shè)置兩個(gè)控制寄存器:基址寄存器和限長(zhǎng)寄存器.基址寄存器存放分配給作業(yè)使用的分區(qū)的起始地址,限長(zhǎng)寄存器存放作業(yè)占用的連續(xù)存儲(chǔ)空間的長(zhǎng)度當(dāng)作業(yè)占有CPU運(yùn)行時(shí),操作系統(tǒng)把作業(yè)所占分區(qū)的始址和長(zhǎng)度送入基址寄存器和限長(zhǎng)寄存器.隨著逐條指令的執(zhí)行和數(shù)據(jù)訪問(wèn)完成地址轉(zhuǎn)換當(dāng)邏輯地址小于限長(zhǎng)值時(shí)，可獲得絕對(duì)地址，大于時(shí)，不允許訪問(wèn)基址基址寄存器邏輯地址CPU絕對(duì)地址操作系統(tǒng)區(qū)空閑分區(qū)1用戶作業(yè)1空閑分區(qū)2限長(zhǎng)限長(zhǎng)寄存器<限長(zhǎng)越界中斷動(dòng)態(tài)分區(qū)特點(diǎn)系統(tǒng)初啟時(shí)，整個(gè)內(nèi)存只有一個(gè)自由塊需調(diào)入一個(gè)作業(yè)時(shí)，查找所有的自由塊直到找到一個(gè)滿足要求的并把它分給該作業(yè)當(dāng)自由塊較大以至滿足一個(gè)作業(yè)的需求后仍有剩余則將剩余量構(gòu)成一個(gè)新的自由塊交給系統(tǒng)當(dāng)一個(gè)作業(yè)運(yùn)行完畢并釋放了其所得到的空間時(shí)，要考慮它上下是否鄰接自由塊，若有合并它們?yōu)橐粋€(gè)較大的自由塊解決了內(nèi)碎片的問(wèn)題，但會(huì)產(chǎn)生很多較小的外碎片（相對(duì)的概念）固定分區(qū)和動(dòng)態(tài)分區(qū)方式都有不足之處。固定分區(qū)方式限制了活動(dòng)進(jìn)程的數(shù)目，當(dāng)進(jìn)程大小與空閑分區(qū)大小不匹配時(shí)，內(nèi)存空間利用率很低。動(dòng)態(tài)分區(qū)方式算法復(fù)雜，回收空閑分區(qū)時(shí)需要進(jìn)行分區(qū)合并等，系統(tǒng)開(kāi)銷(xiāo)較大。伙伴系統(tǒng)方式是對(duì)以上兩種內(nèi)存方式的一種折衷方案。伙伴系統(tǒng)規(guī)定，無(wú)論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪，k為整數(shù)，l≤k≤m，其中：21表示分配的最小分區(qū)的大小，2m表示分配的最大分區(qū)的大小，通常2m是整個(gè)可分配內(nèi)存的大小。4.2.4動(dòng)態(tài)分區(qū)的實(shí)例——伙伴系統(tǒng)當(dāng)需要為進(jìn)程分配一個(gè)長(zhǎng)度為n的存儲(chǔ)空間時(shí)，首先計(jì)算一個(gè)i值，使2i－1<n≤2i，然后在空閑分區(qū)大小為2i的空閑分區(qū)鏈表中查找。若找到，即把該空閑分區(qū)分配給進(jìn)程。否則，表明長(zhǎng)度為2i的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為2i＋1的空閑分區(qū)鏈表中尋找。若存在2i＋1的一個(gè)空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱為一對(duì)伙伴，其中的一個(gè)分區(qū)用于分配，而把另一個(gè)加入分區(qū)大小為2i的空閑分區(qū)鏈表中。若大小為2i＋1的空閑分區(qū)也不存在，則需要查找大小為2i＋2的空閑分區(qū)，若找到則對(duì)其進(jìn)行兩次分割：第一次，將其分割為大小為2i＋1的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為2i＋1的空閑分區(qū)鏈表中；第二次，將第一次用于分配的空閑區(qū)分割為2i的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為2i的空閑分區(qū)鏈表中。若仍然找不到，則繼續(xù)查找大小為2i＋3的空閑分區(qū)，以此類(lèi)推。由此可見(jiàn)，在最壞的情況下，可能需要對(duì)2k的空閑分區(qū)進(jìn)行k次分割才能得到所需分區(qū)。

與一次分配可能要進(jìn)行多次分割一樣，一次回收也可能要進(jìn)行多次合并，如回收大小為2i的空閑分區(qū)時(shí)，若事先已存在2i的空閑分區(qū)時(shí)，則應(yīng)將其與伙伴分區(qū)合并為大小為

2i＋1的空閑分區(qū)，若事先已存在2i＋1的空閑分區(qū)時(shí)，又應(yīng)繼續(xù)與其伙伴分區(qū)合并為大小為2i＋2的空閑分區(qū)，依此類(lèi)推。在伙伴系統(tǒng)中，其分配和回收的時(shí)間性能取決于查找空閑分區(qū)的位置和分割、合并空閑分區(qū)所花費(fèi)的時(shí)間。與前面所述的多種方法相比較，由于該算法在回收空閑分區(qū)時(shí)，需要對(duì)空閑分區(qū)進(jìn)行合并，所以其時(shí)間性能比前面所述的分類(lèi)搜索算法差，但比順序搜索算法好，而其空間性能則遠(yuǎn)優(yōu)于前面所述的分類(lèi)搜索法，比順序搜索法略差。當(dāng)一個(gè)新的作業(yè)要求裝入,沒(méi)有一個(gè)空閑分區(qū)能夠滿足要求,但所有空閑分區(qū)之和能夠滿足要求時(shí),可以移動(dòng)內(nèi)存作業(yè),合并這些小的空閑分區(qū),使之滿足新來(lái)的作業(yè)。作業(yè)移動(dòng)后,要及時(shí)修改它們的基址。操作系統(tǒng)作業(yè)1空閑區(qū)作業(yè)2空閑區(qū)作業(yè)3空閑區(qū)操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)操作系統(tǒng)作業(yè)1作業(yè)2作業(yè)3空閑區(qū)作業(yè)44.2.3主存不足的存儲(chǔ)管理技術(shù)-移動(dòng)技術(shù)

對(duì)換的引入將阻塞進(jìn)程，暫時(shí)不用的程序、數(shù)據(jù)換出。將具備運(yùn)行條件的進(jìn)程換入。類(lèi)型：整體對(duì)換：進(jìn)程對(duì)換，解決內(nèi)存緊張部分對(duì)換：頁(yè)面對(duì)換/分段對(duì)換：提供虛存支持對(duì)換空間管理外存對(duì)換區(qū)比文件區(qū)側(cè)重于對(duì)換速度。因此，對(duì)換區(qū)一般采用連續(xù)分配。采用數(shù)據(jù)結(jié)構(gòu)和分配回收類(lèi)似于動(dòng)態(tài)分區(qū)分配。4.2.3主存不足的存儲(chǔ)管理技術(shù)-對(duì)換技術(shù)連續(xù)分配引起:碎片離散分配方式分頁(yè)存儲(chǔ)管理將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的頁(yè)面，把內(nèi)存空間分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)塊，稱為頁(yè)框，在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干個(gè)頁(yè)分別裝入到多個(gè)可以不相鄰接的頁(yè)框中。分段存儲(chǔ)管理作業(yè)的地址空間被劃分為若干個(gè)段，每個(gè)段定義了一組邏輯信息。每個(gè)段都有自己的名字。每個(gè)段都從0開(kāi)始編址，并采用一段連續(xù)的地址空間。段的長(zhǎng)度由相應(yīng)的邏輯信息組的長(zhǎng)度決定，因而各段長(zhǎng)度不等。段頁(yè)存儲(chǔ)管理是分段和分頁(yè)原理的結(jié)合，即先將用戶程序分成若干個(gè)段，再把每個(gè)段分成若干個(gè)頁(yè)，并為每一個(gè)段賦予一個(gè)段名。4.3.1分頁(yè)式存儲(chǔ)管理的基本原理4.3.2快表4.3.3分頁(yè)式存儲(chǔ)空間的分配和去配4.3.4分頁(yè)式存儲(chǔ)空間的頁(yè)面共享和保護(hù)4.3.5多級(jí)頁(yè)表4.3分頁(yè)存儲(chǔ)管理4.3.1分頁(yè)式存儲(chǔ)管理的基本原理將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的區(qū)，稱為頁(yè)面或頁(yè)，相應(yīng)地，也把內(nèi)存空間分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)塊，稱為頁(yè)框，在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干個(gè)頁(yè)分別裝入到多個(gè)可以不相鄰接的頁(yè)框中。對(duì)頁(yè)框和頁(yè)面都加以編號(hào)，從0開(kāi)始，如第0號(hào)、第1號(hào)等由于進(jìn)程的最后一頁(yè)經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁(yè)內(nèi)碎片”或稱為“內(nèi)零頭”。1.頁(yè)面頁(yè)面和頁(yè)框：邏輯空間和內(nèi)存空間由機(jī)器的地址結(jié)構(gòu)決定頁(yè)太大，頁(yè)內(nèi)碎片大。頁(yè)太?。喉?yè)表可能很長(zhǎng)，換入/出效率低2.地址結(jié)構(gòu)

31 1211 0邏輯地址A；頁(yè)大小L(設(shè)為4096)；頁(yè)內(nèi)偏移d P=(int)A/Ld=AmodL如：A＝8210B.則P=2,d=18分頁(yè)存儲(chǔ)管理頁(yè)號(hào)P頁(yè)內(nèi)位移d3、頁(yè)表0頁(yè)1頁(yè)2頁(yè)3頁(yè)4頁(yè)5頁(yè)n頁(yè)02132638495n0123456789用戶程序頁(yè)表頁(yè)面號(hào)頁(yè)框號(hào)內(nèi)存地址轉(zhuǎn)換由頁(yè)表完成邏輯頁(yè)號(hào)—物理頁(yè)框號(hào)的映射。一、基本地址變換機(jī)構(gòu)： 越界保護(hù)每個(gè)進(jìn)程對(duì)應(yīng)一頁(yè)表，其信息（如長(zhǎng)度、始址）放在PCB中，執(zhí)行時(shí)將其首地址裝入頁(yè)表寄存器。二、地址轉(zhuǎn)換的過(guò)程進(jìn)程運(yùn)行前系統(tǒng)把頁(yè)表基址存入頁(yè)表基址寄存器運(yùn)行時(shí)硬件自動(dòng)將邏輯地址分成兩部分，頁(yè)號(hào)P和頁(yè)內(nèi)位移d找到頁(yè)表基址后，按頁(yè)號(hào)P作為索引查頁(yè)表，得到頁(yè)框號(hào)，根據(jù)公式完成地址轉(zhuǎn)換物理地址=頁(yè)框號(hào)×塊長(zhǎng)+頁(yè)內(nèi)位移分頁(yè)系統(tǒng)地址轉(zhuǎn)換頁(yè)表始址頁(yè)表長(zhǎng)度＋頁(yè)號(hào)(3)頁(yè)內(nèi)地址(342)頁(yè)表寄存器邏輯地址(12630)＜越界中斷5頁(yè)框號(hào)頁(yè)表頁(yè)號(hào)0123物理地址68155頁(yè)號(hào)012368154.3.2快表由于頁(yè)表放在內(nèi)存中，這樣，CPU每存取一個(gè)數(shù)據(jù)時(shí)，需要兩次訪問(wèn)內(nèi)存一次訪問(wèn)頁(yè)表取得物理塊號(hào)以形成物理地址第二次根據(jù)物理地址存取數(shù)據(jù),速度降低了一倍為了提高速度,在存儲(chǔ)管理部件中增設(shè)一個(gè)專用的高速緩沖存儲(chǔ)器,用來(lái)存放最近訪問(wèn)過(guò)的部分頁(yè)表,這種相聯(lián)存儲(chǔ)器稱為快表；快表昂貴，不易過(guò)多。如Intel80486的快表為32個(gè)單元具有快表的分頁(yè)系統(tǒng)地址轉(zhuǎn)換頁(yè)表始址頁(yè)表長(zhǎng)度＋頁(yè)號(hào)(2)頁(yè)內(nèi)地址(342)頁(yè)表寄存器邏輯地址＜越界中斷5頁(yè)框號(hào)頁(yè)表頁(yè)號(hào)0123物理地址6815相聯(lián)存儲(chǔ)器快表501268頁(yè)框號(hào)頁(yè)號(hào)有了快表,根據(jù)頁(yè)號(hào)查找對(duì)應(yīng)的物理塊號(hào)時(shí)：首先查找快表，若找到則將物理塊號(hào)和頁(yè)內(nèi)地址（也是塊內(nèi)地址）拼接形成物理地址若在快表中未找到物理塊號(hào)，則再查找內(nèi)存頁(yè)表，獲取物理塊號(hào)，一方面形成物理地址，另一方面將該表項(xiàng)抄到快表中，以備下次再次訪問(wèn)該頁(yè)面有的系統(tǒng)查快表和查內(nèi)存頁(yè)表是同時(shí)進(jìn)行的，一旦從快表中找到了對(duì)應(yīng)項(xiàng)，則立即停止對(duì)內(nèi)存頁(yè)表的查找當(dāng)快表已滿且要登記新頁(yè)時(shí)，需要淘汰舊快表項(xiàng)，最簡(jiǎn)單的策略是“先進(jìn)先出”

例：有一分頁(yè)式系統(tǒng)，其頁(yè)表存放在主存中：①如果對(duì)主存的一次存取需要10ns,試問(wèn)實(shí)現(xiàn)一次頁(yè)面訪問(wèn)的存取時(shí)間是多少?②如果系統(tǒng)加有快表,平均命中率為85%,當(dāng)頁(yè)表項(xiàng)在快表中時(shí),其查找時(shí)間為2ns,試問(wèn)此時(shí)的存取時(shí)間是多少?答：若頁(yè)表存放在主存中，則要實(shí)現(xiàn)一次頁(yè)面訪問(wèn)需兩次訪問(wèn)主存：一次是訪問(wèn)頁(yè)表，確定所存取頁(yè)面的物理地址（稱為定位）。第二次才根據(jù)該地址存取頁(yè)面數(shù)據(jù)?！鲰?yè)表在主存的存取訪問(wèn)時(shí)間

=10*2=20(ns)■增加快表后的存取訪問(wèn)時(shí)間

=0.85*12+(1-0.85)*（2+10*2）=13.4(ns)4.3.3分頁(yè)式存儲(chǔ)空間的分配和去配位示圖由一些二進(jìn)制位組成,每一位對(duì)應(yīng)一個(gè)內(nèi)存物理塊,位值表示所對(duì)應(yīng)的物理塊是否已分配出去.分配和回收物理塊時(shí)只需修改位值即可鏈表方法1111100011111111110011111100011100000001111111111100000011111111111000000114.3.4分頁(yè)式存儲(chǔ)空間的共享與保護(hù)分頁(yè)存儲(chǔ)管理在實(shí)現(xiàn)共享時(shí),必須區(qū)分?jǐn)?shù)據(jù)共享和程序共享,實(shí)現(xiàn)數(shù)據(jù)共享時(shí),允許不同的作業(yè)對(duì)共享的數(shù)據(jù)頁(yè)使用不同的頁(yè)號(hào),只要讓各自頁(yè)表中的有關(guān)表目指向共享的數(shù)據(jù)信息塊就行了實(shí)現(xiàn)程序共享時(shí),由于頁(yè)式存儲(chǔ)結(jié)構(gòu)要求邏輯地址空間是連續(xù)的,所以程序運(yùn)行前它們的頁(yè)號(hào)就確定了.對(duì)共享的程序必須規(guī)定一個(gè)統(tǒng)一的頁(yè)號(hào).當(dāng)共享程序的作業(yè)數(shù)增多時(shí),要規(guī)定一個(gè)統(tǒng)一的頁(yè)號(hào)是困難的實(shí)現(xiàn)信息保護(hù)的辦法是在頁(yè)表中增加一些標(biāo)志位,用來(lái)指出該頁(yè)的信息可讀/寫(xiě)\只讀\只可執(zhí)行\(zhòng)不可訪問(wèn)等4.3.5

多級(jí)頁(yè)表現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁(yè)表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。例如，對(duì)于一個(gè)具有32位邏輯地址空間的分頁(yè)系統(tǒng)，規(guī)定頁(yè)面大小為4KB，則在每個(gè)進(jìn)程頁(yè)表中的頁(yè)表項(xiàng)可達(dá)1兆個(gè)之多，又因?yàn)槊總€(gè)頁(yè)表項(xiàng)占用4個(gè)字節(jié)，故每個(gè)進(jìn)程僅僅其頁(yè)表就要占用4MB的內(nèi)存空間，而且還要求是連續(xù)的。多級(jí)頁(yè)表（續(xù)）多級(jí)頁(yè)表實(shí)現(xiàn)方法

（1）把整個(gè)頁(yè)表進(jìn)行分頁(yè)，分成一張張小頁(yè)表(稱為頁(yè)表頁(yè)或頁(yè)目錄表)，小頁(yè)表的大小與頁(yè)框相同，為進(jìn)行索引查找，為這些小頁(yè)表建一張頁(yè)目錄表，其表項(xiàng)指出小頁(yè)表所在頁(yè)框號(hào)及相關(guān)信息（2）系統(tǒng)為每個(gè)進(jìn)程建一張頁(yè)目錄表，它的每個(gè)表項(xiàng)對(duì)應(yīng)一個(gè)頁(yè)表頁(yè)，而頁(yè)表頁(yè)的每個(gè)表項(xiàng)給出了頁(yè)面和頁(yè)框的對(duì)應(yīng)關(guān)系,頁(yè)目錄表是一級(jí)頁(yè)表，頁(yè)表頁(yè)是二級(jí)頁(yè)表（3）邏輯地址結(jié)構(gòu)有三部分組成：頁(yè)目錄、頁(yè)表頁(yè)和位移

B

offset目錄位移頁(yè)表頁(yè)位移

頁(yè)內(nèi)位移BF進(jìn)程一級(jí)頁(yè)表進(jìn)程二級(jí)頁(yè)表物理地址邏輯地址頁(yè)目錄表控制寄存器4.4.1程序分段結(jié)構(gòu)4.4.2分段式存儲(chǔ)管理的基本原理4.4.3段的共享和保護(hù)4.4.4分段和分頁(yè)的比較4.4分段式存儲(chǔ)管理基于模塊化的程序設(shè)計(jì)，通常將一個(gè)大任務(wù)分成若干個(gè)相對(duì)獨(dú)立的子任務(wù)，對(duì)應(yīng)于子任務(wù)編寫(xiě)子程序，稱為段。各個(gè)子程序可以獨(dú)立的編輯、編譯、鏈接和執(zhí)行各個(gè)子程序由實(shí)現(xiàn)的功能決定，長(zhǎng)度各不相同。執(zhí)行時(shí)，根據(jù)實(shí)際需要將各個(gè)子程序鏈接成一個(gè)大程序。4.4.1

程序分段結(jié)構(gòu)-分段存儲(chǔ)管理的引入4.4.2分段式存儲(chǔ)管理的基本原理

段號(hào)

段內(nèi)偏移量在分段存儲(chǔ)管理方式中，作業(yè)的地址空間被劃分為若干個(gè)段，每個(gè)段定義了一組邏輯信息。每個(gè)段都有自己的名字。每個(gè)段都從0開(kāi)始編址，并采用一段連續(xù)的地址空間。段的長(zhǎng)度由相應(yīng)的邏輯信息組的長(zhǎng)度決定，因而各段長(zhǎng)度不等。整個(gè)作業(yè)的地址空間，由于是分成多個(gè)段，因而是二維的，亦即，其邏輯地址由段號(hào)（段名）和段內(nèi)地址所組成。分段地址中的地址具有如下結(jié)構(gòu)：作業(yè)空間（MAIN)=0030k（X)=1020k（D)=2015k（S)=3010k內(nèi)存空間30k40k20k80k15k120k10k150k段長(zhǎng)段首址段號(hào)0123段表段表：為每個(gè)分段分配一個(gè)連續(xù)的分區(qū)，而進(jìn)程中的各個(gè)段可以離散地移入內(nèi)存中不同的分區(qū)中。段表始址段表長(zhǎng)度＋段號(hào)（2)100段表寄存器邏輯地址＜越界中斷122980物理地址分段系統(tǒng)地址變換機(jī)構(gòu)＋30k40k20k80k15k120k10k150k段長(zhǎng)段首址段號(hào)0123段表例題對(duì)以下段表,請(qǐng)將邏輯地址(0,137),(1,4000),(2,3600),(5,230)轉(zhuǎn)換成物理地址.段號(hào)起始地址段長(zhǎng)050K10KB160K3KB2120K5KB370K8KB4150K4KB4.4.3

段的共享和保護(hù)段的共享是通過(guò)不同作業(yè)段表中的項(xiàng)指向同一個(gè)段基址來(lái)實(shí)現(xiàn)的于是，幾道作業(yè)共享的程序就可放在一個(gè)段中，只要讓各道作業(yè)的共享部分有相同的基址/限長(zhǎng)值就可以了必須對(duì)共享段的信息進(jìn)行存取控制和保護(hù)ed1ed2…ed40data1_1…data1_10021122……40604161……5070…ed1ed2…ed40data1_1…data1_10data2_1…data2_10進(jìn)程1進(jìn)程2頁(yè)表頁(yè)表ed1ed2…ed40data2_1…data2_10主存分頁(yè)系統(tǒng)中共享editor021122……40604161……分段系統(tǒng)中共享editoreditordata1editordata2段長(zhǎng)基址1608040240段長(zhǎng)基址1608040380editordata1…data2在分段系統(tǒng)中，實(shí)現(xiàn)共享則容易得多，只需在每個(gè)進(jìn)程的段表中為文本編輯程序設(shè)置一個(gè)段表項(xiàng)。進(jìn)程1進(jìn)程2段表4.4.4分段和分頁(yè)的比較分段是信息的邏輯單位，由源程序的邏輯結(jié)構(gòu)所決定,用戶可見(jiàn)；分頁(yè)是信息的物理單位，與源程序的邏輯結(jié)構(gòu)無(wú)關(guān)，用戶不可見(jiàn)。段長(zhǎng)可根據(jù)用戶需要來(lái)規(guī)定，段起始地址可從任何主存地址開(kāi)始；頁(yè)長(zhǎng)由系統(tǒng)確定，頁(yè)面只能以頁(yè)大小的整倍數(shù)地址開(kāi)始。分段方式中,源程序(段號(hào),段內(nèi)位移)經(jīng)連結(jié)裝配后地址仍保持二維結(jié)構(gòu);分頁(yè)方式中,源程序(頁(yè)號(hào),頁(yè)內(nèi)位移)經(jīng)連結(jié)裝配后地址變成了一維結(jié)構(gòu)思考在分頁(yè)存儲(chǔ)管理中,其邏輯地址空間是__維的.在分段存儲(chǔ)管理中,其邏輯地址空間是__維的.在沒(méi)有快表的情況下,分頁(yè)系統(tǒng)每訪問(wèn)一次數(shù)據(jù),要訪問(wèn)__次內(nèi)存;分段系統(tǒng)每訪問(wèn)一次數(shù)據(jù),要訪問(wèn)__次內(nèi)存.在分頁(yè)系統(tǒng)中為實(shí)現(xiàn)地址變換而設(shè)置了頁(yè)表寄存器,其中存放了__和__.程序未運(yùn)行時(shí),這些信息保存在__中.頁(yè)表中的基本數(shù)據(jù)項(xiàng)是__,段表中的基本數(shù)據(jù)項(xiàng)是__和__.把邏輯地址分成頁(yè)號(hào)和頁(yè)內(nèi)地址是由__進(jìn)行的,所以分頁(yè)系統(tǒng)的作業(yè)地址空間是__維的.把邏輯地址分成段號(hào)和段內(nèi)地址是由__進(jìn)行的,所以分段系統(tǒng)的作業(yè)地址空間是__維的.思考頁(yè)表寄存器的值為下面哪些頁(yè)表有錯(cuò)（）5頁(yè)框號(hào)頁(yè)號(hào)01236815501236815頁(yè)表始址頁(yè)表長(zhǎng)度464K5頁(yè)框號(hào)頁(yè)號(hào)01276815503468155頁(yè)框號(hào)頁(yè)號(hào)01268501268ABC4.5.1虛擬存儲(chǔ)器概念4.5.2請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理4.5.4請(qǐng)求段頁(yè)式虛擬存儲(chǔ)管理4.5虛擬存儲(chǔ)管理4.5.1虛擬存儲(chǔ)器概念前面介紹的連續(xù)的（分區(qū)）、離散的（分頁(yè)和分段）管理均是將程序一次性全部裝入內(nèi)存后才能運(yùn)行，在下面情況下：（1）一個(gè)特別大的作業(yè)，不能夠一次裝入內(nèi)存（2）有大量作業(yè)在外存上等待運(yùn)行，而又沒(méi)有足夠大的內(nèi)存容納這些作業(yè)，只能將少量作業(yè)裝入內(nèi)存運(yùn)行，大量的作業(yè)在外存上等待解決辦法：（1）可以從物理上擴(kuò)大內(nèi)存（2）邏輯上擴(kuò)充內(nèi)存，即虛擬內(nèi)存技術(shù)局部性原理C++程序示例局部性原理程序執(zhí)行的局部性是指在一段時(shí)間內(nèi)，程序訪問(wèn)的存儲(chǔ)空間僅限于某個(gè)區(qū)域（這稱為空間局部性），或者最近訪問(wèn)過(guò)的程序代碼和數(shù)據(jù)很快會(huì)再被訪問(wèn)（這稱為時(shí)間局部性）。第一，程序中只有少量分支和過(guò)程調(diào)用，大都是順序執(zhí)行的指令。第二，程序包含若干循環(huán)，是由相對(duì)較少的指令組成，在循環(huán)過(guò)程中，計(jì)算被限制在程序中很小的相鄰部分中。第三，很少出現(xiàn)連續(xù)的過(guò)程調(diào)用，相反，程序中過(guò)程調(diào)用的深度限制在小范圍內(nèi)，一段時(shí)間內(nèi)，指令引用被局限在很少幾個(gè)過(guò)程中。第四，對(duì)于連續(xù)訪問(wèn)數(shù)組之類(lèi)的數(shù)據(jù)結(jié)構(gòu)，往往是對(duì)存儲(chǔ)區(qū)域中相鄰位置的數(shù)據(jù)的操作。第五，程序中有些部分是彼此互斥的，不是每次運(yùn)行時(shí)都用到的，如出錯(cuò)處理程序。虛擬存儲(chǔ)系統(tǒng)思想基于局部性原理，程序在運(yùn)行之前，沒(méi)有必要全部裝入內(nèi)存，將將要運(yùn)行的少數(shù)先裝內(nèi)存便可開(kāi)始運(yùn)行,其余部分留在磁盤(pán)上。運(yùn)行時(shí)，要訪問(wèn)的如果已調(diào)入內(nèi)存，繼續(xù)運(yùn)行；如果未調(diào)入，通過(guò)操作系統(tǒng)“部分裝入”，再運(yùn)行。如果內(nèi)存已滿，用“部分替換”功能，將內(nèi)存中暫時(shí)不用的部分調(diào)到磁盤(pán)上，把要訪問(wèn)的調(diào)入。大的用戶程序在較小的內(nèi)存空間運(yùn)行。更多的作業(yè)并發(fā)執(zhí)行。用戶角度看,系統(tǒng)所具有的內(nèi)存容量,將比實(shí)際內(nèi)存容量大得多。虛擬存儲(chǔ)器的定義在具有層次結(jié)構(gòu)存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中，采用自動(dòng)實(shí)現(xiàn)部分裝入和部分對(duì)換功能，為用戶提供一個(gè)比物理內(nèi)存容量大得多的，可尋址的“內(nèi)存儲(chǔ)器”。虛擬存儲(chǔ)器的容量取決于計(jì)算機(jī)的地址結(jié)構(gòu)和可用的物理內(nèi)存和外存的容量之和。邏輯地址空間處理器虛擬地址存儲(chǔ)管理部件物理地址主存輔存物理地址空間虛擬存儲(chǔ)管理的概念（續(xù)）實(shí)現(xiàn)虛擬存儲(chǔ)器必須解決好以下有關(guān)問(wèn)題：主存輔存統(tǒng)一管理問(wèn)題邏輯地址到物理地址的轉(zhuǎn)換問(wèn)題部分裝入和部分對(duì)換問(wèn)題虛擬存儲(chǔ)器的實(shí)現(xiàn)方法主要有：請(qǐng)求分頁(yè)式虛擬存儲(chǔ)管理請(qǐng)求段頁(yè)式虛擬存儲(chǔ)管理4.5.2請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理1.請(qǐng)求分頁(yè)式虛擬存儲(chǔ)的硬件支撐2.請(qǐng)求分頁(yè)虛擬存儲(chǔ)的基本原理3.交換區(qū)4.頁(yè)面裝入策略和清除策略5.頁(yè)面分配策略6.缺頁(yè)中斷率7.頁(yè)面替換策略8.請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理的幾個(gè)設(shè)計(jì)問(wèn)題1.請(qǐng)求分頁(yè)式虛擬存儲(chǔ)管理的硬件支撐

存儲(chǔ)管理部件--MMU①管理硬件頁(yè)表寄存器：負(fù)責(zé)裝入將要占用處理器的進(jìn)程的頁(yè)表②分解邏輯地址為頁(yè)號(hào)和頁(yè)內(nèi)地址③管理快表：查找快表、裝入表目和清除表目④訪問(wèn)頁(yè)表⑤當(dāng)要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)發(fā)出缺頁(yè)中斷，頁(yè)面訪問(wèn)越界時(shí)發(fā)出越界中斷⑥管理特征位：設(shè)置和檢查頁(yè)表中的狀態(tài)位、訪問(wèn)字段、修改位、保護(hù)權(quán)限等2.請(qǐng)求分頁(yè)系統(tǒng)的基本原理在進(jìn)程開(kāi)始運(yùn)行之前，不是裝入全部頁(yè)面，而是裝入一個(gè)或幾個(gè)頁(yè)面，進(jìn)程運(yùn)行過(guò)程中，訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，再裝入所需頁(yè)面；若內(nèi)存空間已滿，而又需要裝入新的頁(yè)面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁(yè)面，以便裝入新的頁(yè)面怎樣才能發(fā)現(xiàn)頁(yè)面不在內(nèi)存中呢?怎樣處理這種情況呢?采用的辦法是：擴(kuò)充頁(yè)表的內(nèi)容，增加駐留標(biāo)志位和頁(yè)面輔存的地址等信息頁(yè)號(hào)頁(yè)框號(hào)駐留位P引用位U修改位M外存地址是否已調(diào)入內(nèi)存被訪問(wèn)次數(shù)或多長(zhǎng)時(shí)間未被訪問(wèn)，供選擇換出頁(yè)面時(shí)參考是否被修改過(guò),頁(yè)面置換時(shí)參考外存上的地址,調(diào)入時(shí)參考頁(yè)表機(jī)制邏輯地址空間主存(用戶區(qū))CPU邏輯地址快表主存(系統(tǒng)區(qū))運(yùn)行進(jìn)程頁(yè)表輔存缺頁(yè)中斷處理①分解地址③⑤訪問(wèn)MMU②查快表③命中④不命中⑤頁(yè)表命中⑦發(fā)缺頁(yè)中斷⑧調(diào)頁(yè)⑨裝入、改表④查頁(yè)表運(yùn)行進(jìn)程頁(yè)表基址⑥裝入快表運(yùn)行進(jìn)程映象進(jìn)程切換時(shí)裝入物理地址頁(yè)框頁(yè)內(nèi)地址頁(yè)號(hào)頁(yè)內(nèi)地址請(qǐng)求分頁(yè)的地址變換過(guò)程查快表有登記無(wú)登記查頁(yè)表登記入快表發(fā)缺頁(yè)中斷在主存在輔存形成絕對(duì)地址繼續(xù)執(zhí)行指令重新執(zhí)行被中斷指令恢復(fù)現(xiàn)場(chǎng)調(diào)整頁(yè)表和主存分配表裝入所需頁(yè)面主存有空閑塊保護(hù)現(xiàn)場(chǎng)有選擇調(diào)出頁(yè)面該頁(yè)是否修改未修改已修改把該頁(yè)寫(xiě)回輔存相應(yīng)位置操作系統(tǒng)-缺頁(yè)中斷處理程序硬件MMU邏輯地址無(wú)①②③④3.交換區(qū)

操作系統(tǒng)在磁盤(pán)上定義一個(gè)交換區(qū)用來(lái)保存臨時(shí)換出的頁(yè)面，交換區(qū)是物理內(nèi)存的擴(kuò)展，它和內(nèi)存一起組成虛擬存儲(chǔ)空間，文件系統(tǒng)不能占用交換區(qū)空間。

交換區(qū)管理重點(diǎn)是維護(hù)交換區(qū)映射表，該表用來(lái)記錄所有被換出內(nèi)存的頁(yè)面在交換區(qū)中的位置，以便在需要時(shí)再次換入內(nèi)存。當(dāng)頁(yè)面第二次被換出內(nèi)存時(shí)，僅當(dāng)頁(yè)面修改過(guò)（臟頁(yè)）才寫(xiě)入交換區(qū)，否則因已有副本就直接將它丟棄。4.頁(yè)面裝入策略和清除策略頁(yè)裝入策略：請(qǐng)頁(yè)式調(diào)入：在需要訪問(wèn)程序和數(shù)據(jù)時(shí),才把所在頁(yè)面裝入主存優(yōu)點(diǎn)是確保只有被訪問(wèn)的頁(yè)才調(diào)入內(nèi)存，節(jié)省了主存空間缺點(diǎn)是處理缺頁(yè)中斷和調(diào)頁(yè)的系統(tǒng)開(kāi)銷(xiāo)較大，每次僅調(diào)一頁(yè),增加了磁盤(pán)I/O次數(shù)預(yù)調(diào)式調(diào)入：由系統(tǒng)預(yù)測(cè)進(jìn)程將要使用的頁(yè)面,使用前預(yù)先調(diào)入主存,每次調(diào)入若干頁(yè)面,而不是僅調(diào)一頁(yè)優(yōu)點(diǎn)是減少磁盤(pán)I/O啟動(dòng)次數(shù)，節(jié)省尋道和收索時(shí)間缺點(diǎn)是可能所調(diào)入頁(yè)面大多未使用，效率低。頁(yè)面清除策略請(qǐng)頁(yè)式清除僅當(dāng)一頁(yè)選中被替換,且之前它又被修改過(guò),才把這個(gè)頁(yè)面寫(xiě)回輔存預(yù)約式清除對(duì)所有更改過(guò)的頁(yè)面,在需要之前就把它們都寫(xiě)回外存4.頁(yè)面裝入策略和清除策略(續(xù))5.頁(yè)面分配策略系統(tǒng)為進(jìn)程分配主存,需考慮因素:①分給進(jìn)程的空間越小,同一時(shí)間處于內(nèi)存的進(jìn)程就越多，至少有一個(gè)進(jìn)程處于就緒態(tài)的可能性就越大②如果進(jìn)程只有小部分在主存里,即使局部性很好,缺頁(yè)中斷率還會(huì)增加③分給進(jìn)程的內(nèi)存超過(guò)一定限度后，再增加內(nèi)存空間,不會(huì)明顯降低進(jìn)程的缺頁(yè)中斷率假設(shè)固定分配，運(yùn)行FORTRAN程序，共有0.25×106次頁(yè)面引用，頁(yè)面大小為256個(gè)字。分給進(jìn)程的頁(yè)框數(shù)分別為6、8、10、12和14FIFO所產(chǎn)生的缺頁(yè)中斷基本上是Opt的2倍，Clock則比較接近于LRU0510152025354030068101214分配的頁(yè)數(shù)每千次訪問(wèn)的缺頁(yè)中斷數(shù)

FIFO

CLOCK

LRU

OPT頁(yè)面分配策略固定分配：固定分配使進(jìn)程在生命周期中保持固定數(shù)目的物理塊，每個(gè)進(jìn)程物理塊的分配方式主要有：平均分配按比例分配考慮優(yōu)先權(quán)的分配可變分配不時(shí)重新評(píng)價(jià)進(jìn)程的缺頁(yè)率，增加或減少進(jìn)程的頁(yè)框數(shù)，以改善系統(tǒng)的總性能。頁(yè)面替換策略局部替換：局部替換在進(jìn)程發(fā)生缺頁(yè)時(shí)僅從該進(jìn)程的物理塊中淘汰頁(yè)面,以調(diào)入所缺頁(yè)面全局替換：全局替換則在進(jìn)程發(fā)生缺頁(yè)時(shí)可從系統(tǒng)中任一進(jìn)程的物理塊中淘汰頁(yè)面頁(yè)面分配和替換常用的組合策略有三種:固定分配局部置換、可變分配全局置換和可變分配局部置換6.缺頁(yè)中斷率頁(yè)面替換主存空間已經(jīng)用完，而又要裝入新頁(yè)時(shí)，必須把主存的一些頁(yè)面調(diào)出去，叫頁(yè)面替換頁(yè)面淘汰算法確定被淘汰頁(yè)的算法“抖動(dòng)”(Thrashing)(“顛簸”)現(xiàn)象是淘汰算法不好而產(chǎn)生的一種現(xiàn)象。剛淘汰的頁(yè)面又立即要用，又將其調(diào)入，然后再淘汰、再調(diào)入。浪費(fèi)大量CPU的時(shí)間假定作業(yè)p共計(jì)n頁(yè)，系統(tǒng)分配給它的主存塊只有m塊（１≤m≤n）。如果作業(yè)p在運(yùn)行中成功的訪問(wèn)次數(shù)為S，不成功的訪問(wèn)次數(shù)（缺頁(yè)次數(shù)）為F，則總的訪問(wèn)次數(shù)Ａ為：A=S+F，又定義：f=F/A稱f為缺頁(yè)中斷率6.缺頁(yè)中斷率影響缺頁(yè)中斷率f的因素有：(1)主存頁(yè)框數(shù)(2)頁(yè)面大小(3)頁(yè)面替換算法(4)程序特性程序要將128×128的數(shù)組置“0”。分給的主存只一塊，頁(yè)面尺寸為每頁(yè)128個(gè)字，數(shù)組中的元素每行存放在一頁(yè)中。intA[128][128];for(intj=0;j<128;j++)for(inti=0;i<128;i++)A[i][j]:=0總共產(chǎn)生（128*128－1）次缺頁(yè)中斷intA[128][128];for(inti=0;i<128;i++)for(intj=0;j<128;j++)A[i][j]:=0總共產(chǎn)生（128－1）次缺頁(yè)中斷請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理（續(xù)）幾種頁(yè)面替換策略:最佳頁(yè)面算法(OPT、Belady算法)先進(jìn)先出頁(yè)面淘汰算法(FIFO)最近最久未使用頁(yè)面淘汰算法(LRU)Clock置換算法最佳頁(yè)面替換算法(OPT)其所選擇的被淘汰頁(yè)面，將是以后永不使用的，或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳頁(yè)面置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。假定系統(tǒng)為某進(jìn)程分配了三個(gè)頁(yè)框（物理塊），并考慮有以下的頁(yè)面號(hào)引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1；70770170122010320304243230321201201770101203共缺頁(yè)中斷9次，缺頁(yè)中斷率為9/20=45%;頁(yè)面替換6次總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面.頁(yè)面按先后次序鏈接成一個(gè)隊(duì)列設(shè)置一個(gè)替換指針,指向最老的頁(yè)面先進(jìn)先出（FIFO）頁(yè)面替換算法70770170122010323104230230321013201771201023430420423012702701共缺頁(yè)中斷15次，缺頁(yè)中斷率為15/20=75%;頁(yè)面替換12次最近最少使用LRU替換算法訪問(wèn)字段，上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t選擇t值最大的頁(yè)面淘汰用“最近的過(guò)去”作為“最近的將來(lái)”的近似70770170122010320304230321132201710201032403402432107共缺頁(yè)中斷12次，缺頁(yè)中斷率為12/20=60%;頁(yè)面替換9次1）引用位法方法：每頁(yè)設(shè)置一個(gè)引用標(biāo)志位R，訪問(wèn)某頁(yè)時(shí)，由硬件將頁(yè)標(biāo)志位R置1，隔一定時(shí)間t將所有頁(yè)的標(biāo)志R均清0發(fā)生缺頁(yè)中斷處理：從標(biāo)志位R為0的頁(yè)中挑選一頁(yè)淘汰。并將所有頁(yè)的標(biāo)志位R清0主要問(wèn)題：時(shí)間間隔t的選擇，t太大則標(biāo)志位R均為1，t太小則標(biāo)志位R均為0LRU算法的硬件支持2）計(jì)數(shù)器法方法：每個(gè)頁(yè)面設(shè)置一個(gè)多位計(jì)數(shù)器，每當(dāng)訪問(wèn)一頁(yè)時(shí)，就使它對(duì)應(yīng)的計(jì)數(shù)器加1。又叫最不常用頁(yè)面替換算法LFU。發(fā)生缺頁(yè)中斷處理：選擇計(jì)數(shù)值最小的對(duì)應(yīng)頁(yè)面淘汰，并將所有計(jì)數(shù)器全部清0。LRU算法的硬件支持3）計(jì)時(shí)法方法：為每個(gè)頁(yè)面設(shè)置一個(gè)多位計(jì)時(shí)器，每當(dāng)頁(yè)面被訪問(wèn)時(shí)，系統(tǒng)的絕對(duì)時(shí)間記入計(jì)時(shí)器缺頁(yè)中斷處理：比較各頁(yè)面的計(jì)時(shí)器的值，選最小值的未使用的頁(yè)面淘汰，因?yàn)椋亲睢袄稀钡奈词褂玫捻?yè)面。時(shí)鐘頁(yè)面替換算法一個(gè)頁(yè)面首次裝入主存，其“引用位”置1。主存中的任何頁(yè)面被訪問(wèn)時(shí),“引用位”置1。淘汰頁(yè)面時(shí),從指針當(dāng)前指向的頁(yè)面開(kāi)始掃描循環(huán)隊(duì)列，把遇到的“引用位”是1的頁(yè)面的“引用位”清0,跳過(guò)這個(gè)頁(yè)面;把所遇到的“引用位”是0的頁(yè)面淘汰掉,指針推進(jìn)一步。掃描循環(huán)隊(duì)列時(shí)，如果遇到的所有頁(yè)面的“引用位”為1，指針就會(huì)繞整個(gè)循環(huán)隊(duì)列一圈，把碰到的所有頁(yè)面的“引用位”清0;指針停在起始位置，并淘汰掉這一頁(yè),然后，指針推進(jìn)一步。P9U1P19U1P1U0P45U1P191U1P556U0P13U0P67U1P33U1P222U0

：：下幀指針n012345678一個(gè)頁(yè)替換前的緩沖區(qū)狀態(tài)P9U1P19U1P1U0P45U0P191U0P727U1P13U0P67U1P33U1P222U0n012345678替換一頁(yè)后的緩沖區(qū)狀態(tài)頁(yè)框號(hào)

：：時(shí)鐘頁(yè)面替換算法的改進(jìn)算法把”引用位”和”修改位”結(jié)合起來(lái)使用，共組合成四種情況：(1)最近沒(méi)有被引用,沒(méi)有被修改(r=0,m=0)(2)最近被引用,沒(méi)有被修改(r=1,m=0)(3)最近沒(méi)有被引用,但被修改(r=0,m=1)(4)最近被引用過(guò),也被修改過(guò)(r=1,m=1)步1：選擇最佳淘汰頁(yè)面，從指針當(dāng)前位置開(kāi)始,掃描循環(huán)隊(duì)列。掃描過(guò)程中不改變“引用位”，把找到的第一個(gè)r=0,m=0的頁(yè)面作為淘汰頁(yè)面。步2：如果步1失敗，再次從原位置開(kāi)始，查找r=0且m=1的頁(yè)面，把找到的第一個(gè)這樣的頁(yè)面作為淘汰頁(yè)面，而在掃描過(guò)程中把指針?biāo)鶔哌^(guò)的頁(yè)面的“引用位”r置0。步3：如果步2失敗，指針再次回到了起始位置，由于此時(shí)所有頁(yè)面的“引用位”r均己為0，再轉(zhuǎn)向步1操作，必要時(shí)再做步2操作，這次一定可以挑出一個(gè)可淘汰的頁(yè)面。時(shí)鐘頁(yè)面替換算法的改進(jìn)算法工作集模型用于模擬實(shí)現(xiàn)局部最佳頁(yè)面替換算法使用滑動(dòng)窗口，但不向前查看引用串，而是向后看通過(guò)考察最近主存需求來(lái)估計(jì)進(jìn)程將需要的頁(yè)框數(shù)

進(jìn)程工作集

在某一段時(shí)間間隔內(nèi)進(jìn)程運(yùn)行所需訪問(wèn)的頁(yè)面集合W(t,△)表示在時(shí)刻t-△到時(shí)刻t自己所訪問(wèn)的頁(yè)面集合，它就是進(jìn)程在時(shí)刻t的工作集。變量△稱為“工作集窗口尺寸”，工作集所包含的頁(yè)面數(shù)稱為“工作集尺寸”工作集替換示例頁(yè)面引用串與上例相同，△=3。當(dāng)系統(tǒng)有空閑頁(yè)框供分配，并在時(shí)刻t=0時(shí)，初始工作集為（p1，p4，p5），其中，p1在時(shí)刻t=0被引用，p4在時(shí)刻t=-1被引用，而p5在時(shí)刻t=-2時(shí)刻被引用。第一次缺頁(yè)中斷發(fā)生在時(shí)刻t=1，頁(yè)面p3被裝入一個(gè)空閑頁(yè)框，另外3個(gè)