第四章 存儲管理

4.1

存儲器工作原理

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

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

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

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

4.2.3伙伴系統(tǒng)4.2.4主存不足的存儲管理技術(shù)4.2連續(xù)存儲管理4.2.1固定分區(qū)存儲管理分區(qū)管理：是一種簡單使用的存貯管理方案，把內(nèi)存空間靜態(tài)的（動態(tài)的）分割成若干大小可以不等的區(qū)域，每個(gè)作業(yè)分配一片連續(xù)的存儲空間，程序一次整體裝入固定式分區(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ū)存儲管理(續(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ū)號大小(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ū)存儲管理(續(xù))缺點(diǎn)：固定分區(qū)存儲管理限制了程序的大小,無法運(yùn)行超過分區(qū)大小的程序內(nèi)存空間利用率不高不便于程序動態(tài)擴(kuò)充內(nèi)存限制了程序道數(shù)固定分區(qū)存儲管理適合于程序大小和出現(xiàn)頻率已知的情形4.2.2可變分區(qū)存儲管理按照作業(yè)的大小來劃分分區(qū)，劃分的時(shí)間、大小和位置都是動態(tài)的。系統(tǒ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)對空閑分區(qū)的分配和鏈接，設(shè)置前向指針和后向指針，通過前、后向鏈接指針將所有的空閑分區(qū)鏈接成一個(gè)雙向鏈。前向指針分區(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)完成，請畫出當(dāng)前時(shí)刻空閑分區(qū)表。如果此時(shí)有來了一個(gè)15K大小H任務(wù)，會分在哪個(gè)空閑分區(qū)里面。分區(qū)號大小(KB)起址(KB)狀態(tài)1824未分配22048未分配35696未分配440154未分配562194未分配空閑分區(qū)表1．最先適應(yīng)算法（首次適應(yīng)算法）。每次都從頭開始，尋找第一個(gè)滿足需求的空閑分區(qū)。特點(diǎn)：找到第一個(gè)大小滿足的分區(qū)，劃分。有碎片（外零頭），低址內(nèi)存使用頻繁。2．下次首次適應(yīng)算法（循環(huán)首次適應(yīng)算法）。與1類似，從上次找到的空閑分區(qū)的下一個(gè)開始查找。特點(diǎn)：空閑分區(qū)分布均勻，提高了查找速度；缺乏大的空閑分區(qū)3．最佳適應(yīng)算法（最優(yōu)適應(yīng)算法）分區(qū)按大小遞增排序；分區(qū)釋放時(shí)需插入到適當(dāng)位置。特點(diǎn)：產(chǎn)生無法利用的小碎片。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)換與存儲保護(hù)可變分區(qū)方式采用動態(tài)重定位裝入作業(yè),作業(yè)程序和數(shù)據(jù)的地址轉(zhuǎn)換由硬件完成.硬件設(shè)置兩個(gè)控制寄存器:基址寄存器和限長寄存器.基址寄存器存放分配給作業(yè)使用的分區(qū)的起始地址,限長寄存器存放作業(yè)占用的連續(xù)存儲空間的長度當(dāng)作業(yè)占有CPU運(yùn)行時(shí),操作系統(tǒng)把作業(yè)所占分區(qū)的始址和長度送入基址寄存器和限長寄存器.隨著逐條指令的執(zhí)行和數(shù)據(jù)訪問完成地址轉(zhuǎn)換當(dāng)邏輯地址小于限長值時(shí)，可獲得絕對地址，大于時(shí)，不允許訪問基址基址寄存器邏輯地址CPU絕對地址操作系統(tǒng)區(qū)空閑分區(qū)1用戶作業(yè)1空閑分區(qū)2限長限長寄存器<限長越界中斷動態(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)碎片的問題，但會產(chǎn)生很多較小的外碎片（相對的概念）固定分區(qū)和動態(tài)分區(qū)方式都有不足之處。固定分區(qū)方式限制了活動進(jìn)程的數(shù)目，當(dāng)進(jìn)程大小與空閑分區(qū)大小不匹配時(shí)，內(nèi)存空間利用率很低。動態(tài)分區(qū)方式算法復(fù)雜，回收空閑分區(qū)時(shí)需要進(jìn)行分區(qū)合并等，系統(tǒng)開銷較大。伙伴系統(tǒng)方式是對以上兩種內(nèi)存方式的一種折衷方案?；锇橄到y(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪，k為整數(shù)，l≤k≤m，其中：21表示分配的最小分區(qū)的大小，2m表示分配的最大分區(qū)的大小，通常2m是整個(gè)可分配內(nèi)存的大小。4.2.4動態(tài)分區(qū)的實(shí)例——伙伴系統(tǒng)當(dāng)需要為進(jìn)程分配一個(gè)長度為n的存儲空間時(shí)，首先計(jì)算一個(gè)i值，使2i－1<n≤2i，然后在空閑分區(qū)大小為2i的空閑分區(qū)鏈表中查找。若找到，即把該空閑分區(qū)分配給進(jìn)程。否則，表明長度為2i的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為2i＋1的空閑分區(qū)鏈表中尋找。若存在2i＋1的一個(gè)空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱為一對伙伴，其中的一個(gè)分區(qū)用于分配，而把另一個(gè)加入分區(qū)大小為2i的空閑分區(qū)鏈表中。若大小為2i＋1的空閑分區(qū)也不存在，則需要查找大小為2i＋2的空閑分區(qū)，若找到則對其進(jìn)行兩次分割：第一次，將其分割為大小為2i＋1的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為2i＋1的空閑分區(qū)鏈表中；第二次，將第一次用于分配的空閑區(qū)分割為2i的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為2i的空閑分區(qū)鏈表中。若仍然找不到，則繼續(xù)查找大小為2i＋3的空閑分區(qū)，以此類推。由此可見，在最壞的情況下，可能需要對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ū)，依此類推。在伙伴系統(tǒng)中，其分配和回收的時(shí)間性能取決于查找空閑分區(qū)的位置和分割、合并空閑分區(qū)所花費(fèi)的時(shí)間。與前面所述的多種方法相比較，由于該算法在回收空閑分區(qū)時(shí)，需要對空閑分區(qū)進(jìn)行合并，所以其時(shí)間性能比前面所述的分類搜索算法差，但比順序搜索算法好，而其空間性能則遠(yuǎn)優(yōu)于前面所述的分類搜索法，比順序搜索法略差。當(dāng)一個(gè)新的作業(yè)要求裝入,沒有一個(gè)空閑分區(qū)能夠滿足要求,但所有空閑分區(qū)之和能夠滿足要求時(shí),可以移動內(nèi)存作業(yè),合并這些小的空閑分區(qū),使之滿足新來的作業(yè)。作業(yè)移動后,要及時(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主存不足的存儲管理技術(shù)-移動技術(shù)

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

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

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

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

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

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

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

B

offset目錄位移頁表頁位移

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

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

段號

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

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

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

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

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

FIFO

CLOCK

LRU

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

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

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

進(jìn)程工作集

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