第四章存儲(chǔ)器管理

1第四章存儲(chǔ)器管理

2第四章存儲(chǔ)器管理如何對(duì)存儲(chǔ)器進(jìn)行有效的管理，不僅影響到存儲(chǔ)器的利用率，而且還對(duì)系統(tǒng)性能有重大影響。存儲(chǔ)器：內(nèi)存（本章）外存（第六章）3主要內(nèi)容new存儲(chǔ)器的層次結(jié)構(gòu)4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁(yè)存儲(chǔ)管理方式4.4基本分段存儲(chǔ)管理方式4.5虛擬存儲(chǔ)器的基本概念4.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.7頁(yè)面置換算法4.8請(qǐng)求分段存儲(chǔ)管理方式4本章學(xué)習(xí)目標(biāo)了解存儲(chǔ)管理的研究對(duì)象和目的了解存儲(chǔ)管理的基本功能和有關(guān)的基本概念掌握分頁(yè)存儲(chǔ)管理和分段存儲(chǔ)管理的基本概念掌握請(qǐng)求分頁(yè)和請(qǐng)求分段存儲(chǔ)管理的基本原理New4.1存儲(chǔ)器的層次結(jié)構(gòu)1.多級(jí)存儲(chǔ)器結(jié)構(gòu)2.主存儲(chǔ)器與寄存器3.高速緩存與磁盤緩存51.多級(jí)存儲(chǔ)器結(jié)構(gòu)

寄存器高速緩存內(nèi)存磁盤緩存磁盤可移動(dòng)存儲(chǔ)器6三層由快到慢寄存器與主存（前四者）由操作系統(tǒng)直接管理，可快速訪問，稱為可執(zhí)行存儲(chǔ)器。后兩者需要通過(guò)I/O訪問2.主存儲(chǔ)器與寄存器1.主存儲(chǔ)器容量大小2.寄存器速度與CPU完全協(xié)調(diào)長(zhǎng)度以字為單位，幾十至幾百個(gè)73.高速緩存和磁盤緩存高速緩存局部性原理CPU與內(nèi)存之間磁盤緩存頻繁使用的磁盤數(shù)據(jù)暫存在內(nèi)存中的磁盤高速緩存中89預(yù)備知識(shí)地址空間的概念1．內(nèi)存空間(物理空間)

內(nèi)存是由若干個(gè)存儲(chǔ)單元組成的，每個(gè)存儲(chǔ)單元的編號(hào)稱為內(nèi)存地址(或物理地址)2．邏輯空間經(jīng)過(guò)匯編或編譯后形成目標(biāo)程序是以0為基址順序進(jìn)行編址的，目標(biāo)程序占據(jù)的地址空間稱為作業(yè)的邏輯地址空間。邏輯空間中的地址稱為邏輯地址，這是一個(gè)相對(duì)地址。104.1程序的裝入和鏈接為作業(yè)創(chuàng)建進(jìn)程需將其裝入內(nèi)存。要把程序裝入內(nèi)存，就要對(duì)程序進(jìn)行編譯和鏈接。1.編譯由編譯程序把源程序翻譯成若干個(gè)目標(biāo)模塊；2.鏈接由鏈接程序把目標(biāo)模塊以及相關(guān)的庫(kù)函數(shù)鏈接在一起，形成完整的裝入模塊；3.裝入由裝入程序把裝入模塊裝入內(nèi)存。114.1.1程序的裝入將一個(gè)裝入模塊裝入內(nèi)存時(shí)，有三種方式：絕對(duì)裝入方式可重定位裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式關(guān)鍵在于將邏輯地址轉(zhuǎn)換為物理地址的時(shí)機(jī)不同121.絕對(duì)裝入方式

AbsoluteLoadingMode若編譯時(shí)知道程序?qū)⒃趦?nèi)存的(起始)駐留地址，編譯程序?qū)a(chǎn)生絕對(duì)(物理)地址的目標(biāo)代碼。只適用單道程序環(huán)境。裝入模塊不需再地址轉(zhuǎn)換，直接裝入內(nèi)存。絕對(duì)地址，即可在編譯或匯編時(shí)給出，也可由程序員直接給出。通常在程序中采用符號(hào)地址，在編譯或匯編時(shí)，再將其轉(zhuǎn)換為絕對(duì)地址。132.可重定位裝入方式

RelocationLoadingMode多道程序環(huán)境下，各目標(biāo)模塊的起始地址均從0開始，程序中的其它地址都是相對(duì)于起始地址計(jì)算的，不是絕對(duì)的物理地址，編譯程序無(wú)法預(yù)知目標(biāo)模塊應(yīng)放于何處。裝入時(shí)，需根據(jù)內(nèi)存當(dāng)前的情況，將模塊裝入到內(nèi)存的適當(dāng)位置，存在一個(gè)邏輯地址空間到內(nèi)存物理地址空間的轉(zhuǎn)換過(guò)程（即重定位）。142.可重定位裝入方式

RelocationLoadingMode邏輯地址與實(shí)際裝入內(nèi)存的物理地址會(huì)不同。Load1,2500的作用是把2500單元中的數(shù)據(jù)送至寄存器1。在裝入時(shí)，指令的地址會(huì)由原來(lái)的1000，變?yōu)?1000，取數(shù)地址2500也會(huì)變?yōu)?2500。該例中，在裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)的地址修改過(guò)程稱為重定位。該地址變換是在裝入時(shí)一次完成的，不再改變，故稱為靜態(tài)重定位。153.動(dòng)態(tài)運(yùn)行時(shí)裝入方式

DynamicRun-timeLoading把程序裝入內(nèi)存后，并不立即把裝入模塊中的邏輯地址轉(zhuǎn)換為物理地址，仍是相對(duì)地址。邏輯地址到物理地址的轉(zhuǎn)換直到程序真正運(yùn)行時(shí)才進(jìn)行。不僅允許裝入模塊裝入到內(nèi)存中的任何位置，而且允許程序在運(yùn)行時(shí)在內(nèi)存中移動(dòng)。（動(dòng)態(tài)重定位分區(qū)分配）164.1.2程序的鏈接根據(jù)鏈接時(shí)間的不同，可分為：靜態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接關(guān)鍵在于進(jìn)行鏈接的時(shí)機(jī)171.靜態(tài)鏈接方式

StaticLinking在程序運(yùn)行之前把各目標(biāo)模塊及庫(kù)函數(shù)鏈接成一個(gè)完整的裝入模塊，以后不再拆開。裝配時(shí)需解決兩個(gè)問題：(1)對(duì)相對(duì)地址進(jìn)行修改。(2)變換外部符號(hào)。18模塊ABC在鏈接前其內(nèi)部地址均是相對(duì)于起始地址0而言的。鏈接成一個(gè)裝入模塊后，BC的首地址分別變成了L和L+M，這就需要修改BC中的相對(duì)地址，將其全部加上L或L+M；對(duì)于ABC各模塊中所使用的外部調(diào)用符號(hào)，也都需進(jìn)行變換，CALLB需變換為JSLL。192.裝入時(shí)動(dòng)態(tài)鏈接

Load-timeDynamicLinking編譯的目標(biāo)模塊在裝入內(nèi)存時(shí)，邊裝入邊鏈接。即在裝入一個(gè)目標(biāo)模塊時(shí)，若發(fā)生一個(gè)外部模塊調(diào)用，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存，還需修改目標(biāo)模塊中的相對(duì)地址。202.裝入時(shí)動(dòng)態(tài)鏈接

Load-timeDynamicLinking優(yōu)點(diǎn):VS靜態(tài)鏈接

1.便于修改和更新

各目標(biāo)模塊分開存放，便于修改或更新。靜態(tài)鏈接要修改或更新時(shí)，需重新打開裝入模塊，低效。

2.便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享

可將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊，實(shí)現(xiàn)多個(gè)應(yīng)用程序?qū)υ撃K的共享。靜態(tài)鏈接，每個(gè)應(yīng)用模塊都必須含有該目標(biāo)模塊的完整拷貝，無(wú)法共享。213.運(yùn)行時(shí)動(dòng)態(tài)鏈接

Run-timeDynamicLinking把對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)進(jìn)行。在執(zhí)行過(guò)程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到該模塊并鏈接到調(diào)用者模塊上。優(yōu)點(diǎn)：本次執(zhí)行不需要的模塊不鏈接。可加快裝入過(guò)程，而且節(jié)省內(nèi)存空間。224.1程序的裝入和鏈接小結(jié)程序的裝入絕對(duì)裝入方式可重定位裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式程序的鏈接靜態(tài)鏈接方式裝入時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接234.2連續(xù)分配方式

連續(xù)分配方式，指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。4.2.1單一連續(xù)分區(qū)分配4.2.2固定分區(qū)分配4.2.3動(dòng)態(tài)分區(qū)分配4.2.4動(dòng)態(tài)重定位分區(qū)分配4.2.5對(duì)換(Swapping)244.2.1單一連續(xù)分區(qū)分配1.內(nèi)存劃分

(1)系統(tǒng)區(qū)僅提供給OS使用，通常為內(nèi)存中的低址部分

(2)用戶區(qū)單一分區(qū)，除系統(tǒng)區(qū)外的全部?jī)?nèi)存空間，只提供給用戶使用2.適用環(huán)境只適用于單用戶、單任務(wù)環(huán)境？254.2.2固定分區(qū)分配最早使用的一種可運(yùn)行多道程序的存儲(chǔ)管理方式。將內(nèi)存空間劃分為若干個(gè)固定大小的區(qū)域，在每個(gè)分區(qū)中可以裝入一道作業(yè)，當(dāng)內(nèi)存中劃分成幾個(gè)分區(qū)時(shí)，便允許幾道作業(yè)并發(fā)運(yùn)行；當(dāng)有一個(gè)空閑分區(qū)時(shí)，便可從外存的后備隊(duì)列中，選擇一個(gè)適當(dāng)大小的作業(yè)裝入該分區(qū)；當(dāng)該作業(yè)結(jié)束時(shí)，又可從后備隊(duì)列中找出另一個(gè)作業(yè)調(diào)入該分區(qū)。劃分分區(qū)內(nèi)存分配261.劃分分區(qū)的方法1.分區(qū)大小相等 使所有的內(nèi)存分區(qū)大小相等。適用于利用一臺(tái)計(jì)算機(jī)去控制多個(gè)相同對(duì)象的場(chǎng)合。缺乏靈活性。2.分區(qū)大小不等 將內(nèi)存區(qū)分為大小不等的多塊，靈活性稍好，可根據(jù)程序的大小為之分配適當(dāng)?shù)姆謪^(qū)。272.內(nèi)存分配把分區(qū)按大小排隊(duì)，并建立一個(gè)分區(qū)使用表。分區(qū)表中記錄各分區(qū)的起始地址、大小和狀態(tài)。分配內(nèi)存時(shí)，檢索分區(qū)表，如果存在大小合適且未分配的分區(qū)，就把其分配給相應(yīng)的程序，然后置“已分配”標(biāo)志；若未找到大小足夠的分區(qū)，則拒絕為之分配內(nèi)存。282.內(nèi)存分配分區(qū)大小固定，靈活性仍不足，會(huì)產(chǎn)生內(nèi)存碎片；在某些用于控制相同對(duì)象的場(chǎng)合仍有一定應(yīng)用。作業(yè)2：30K作業(yè)1：112K294.2.3動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。又稱為可變分區(qū)分配。示意圖30可變分區(qū)內(nèi)存使用示意圖314.2.3動(dòng)態(tài)分區(qū)分配三個(gè)問題分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配算法分區(qū)分配操作321.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)記錄內(nèi)存的使用情況，為分配提供依據(jù)。(1)空閑分區(qū)表 在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個(gè)空閑分區(qū)的情況。每個(gè)空閑分區(qū)占一個(gè)表目，表目中包括分區(qū)序號(hào)、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)項(xiàng)。331.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)(2)空閑分區(qū)鏈 每個(gè)分區(qū)的起始部分，設(shè)置用于鏈接各分區(qū)的前向指針；在分區(qū)尾部設(shè)置一后向指針。通過(guò)前、后向鏈接指針，可將所有的空閑分區(qū)鏈接成一個(gè)雙向鏈。前后向指針，大小，狀態(tài)342.分區(qū)分配算法按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。常用的三種分配算法：首次適應(yīng)算法循環(huán)適應(yīng)算法最佳適應(yīng)算法35(1)首次適應(yīng)算法空閑分區(qū)以地址遞增的次序鏈接。分配時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)；然后根據(jù)作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑鏈中。優(yōu)點(diǎn)：傾向于利用內(nèi)存中低址的空閑區(qū)，保留了高址部分的大空閑區(qū)，為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。 缺點(diǎn)：低址不斷被劃分，會(huì)產(chǎn)生大量的碎片；每次從低址開始查找，會(huì)增加查找可用空間的開銷。36(1)首次適應(yīng)算法圖中采用的空閑分區(qū)鏈按地址由小到大的順序?qū)臻e分區(qū)進(jìn)行組織，開始指向以40k為首址的空閑分區(qū)（其大小為46k，下一個(gè)空閑分區(qū)為始址為118k）。作業(yè)5大小為36k37(2)循環(huán)首次適應(yīng)算法分配時(shí)，不每次均從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直至找到第一個(gè)能滿足要求的空閑分區(qū)，并從中劃出一塊與請(qǐng)求的大小相等的內(nèi)存空間分配給作業(yè)。需設(shè)置一起始查尋指針，以指示下一次起始查尋的空閑分區(qū)，并采用循環(huán)查找方式。即如果最后一個(gè)(鏈尾)空閑分區(qū)，其大小仍不能滿足要求，應(yīng)返回到第一個(gè)空閑分區(qū)，比較其大小是否滿足要求。找到后，應(yīng)立即調(diào)整起始查尋指針。優(yōu)點(diǎn)：空閑分區(qū)分布均更均勻，減少了查找空閑分區(qū)的開銷，但會(huì)導(dǎo)致缺乏大的空閑分區(qū)。38(3)最佳適應(yīng)算法每次為作業(yè)分配內(nèi)存時(shí)，總是把既能滿足要求，又是最小的空閑分區(qū)分配給作業(yè)，避免了“大材小用”。為了加速尋找，要求將所有的空閑區(qū)，按其容量大小以遞增的順序形成一空閑區(qū)鏈。這樣，第一次找到的滿足要求的空閑區(qū)，必然是最優(yōu)的。特點(diǎn)：每次似乎是最佳的，然而在宏觀上卻不一定。每次分配后所切割下來(lái)的剩余部分總是最小的，在存儲(chǔ)器中會(huì)留下許多這樣難以利用的小空閑區(qū)。39(3)最佳適應(yīng)算法圖中采用的空閑分區(qū)鏈按容量由小到大的順序組織403.分區(qū)分配操作(分配－回收)1)分配內(nèi)存 若m.size-u.size<=size，說(shuō)明多余部分太小，可不再切割，將整個(gè)分區(qū)分配給請(qǐng)求者；否則，從該分區(qū)中劃分出與請(qǐng)求的大小相等的內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)鏈或空閑分區(qū)表中。最后，將分配區(qū)的首址返回給調(diào)用者。m.size空閑分區(qū)大小u.size用戶作業(yè)大小413.分區(qū)分配操作2)回收內(nèi)存當(dāng)一個(gè)進(jìn)程（或程序）釋放其所占內(nèi)存區(qū)時(shí)，系統(tǒng)將首先檢查回收區(qū)是否與其它空閑區(qū)相鄰，若相鄰則合并成一個(gè)空閑區(qū)，否則，將回收區(qū)插入空閑分區(qū)表（或空閑分區(qū)鏈）中的適當(dāng)位置。回收情況：A.只有前鄰空閑區(qū)B.只有后鄰空閑區(qū)C.既有前鄰空閑區(qū)又有后鄰空閑區(qū)D.沒有鄰接空閑區(qū)根據(jù)不同情況，A、B、C有不同的合并策略。42回收內(nèi)存示意圖A.將R合并到f1，f1.addr；f1.size+R.size->f1.size

B.將f2

合并到R

，R.addr；f2.size+R.size->f2.size

C.f1、R、f2合并到f1，f1.addr；f1.size+R.size+f2.size->f1.size；撤消f2空閑區(qū)表項(xiàng)D.R作為一個(gè)新空閑區(qū)，插入到空閑區(qū)表（鏈）的適當(dāng)位置。434.2.4動(dòng)態(tài)重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入2.動(dòng)態(tài)重定位的實(shí)現(xiàn)3.動(dòng)態(tài)重定位分區(qū)分配算法441.動(dòng)態(tài)重定位的引入為了充分利用內(nèi)存碎片，可利用“緊湊”操作把多個(gè)碎片處理為一個(gè)比較大的分區(qū)，以便利用。經(jīng)過(guò)緊湊后的某些用戶程序在內(nèi)存中的位置發(fā)生了變化，此時(shí)需對(duì)程序和數(shù)據(jù)的地址加以修改（變換），即需要進(jìn)行重定位。452.動(dòng)態(tài)重定位的實(shí)現(xiàn)采用動(dòng)態(tài)運(yùn)行時(shí)裝入方式，地址轉(zhuǎn)換推遲到程序指令真正要執(zhí)行時(shí)進(jìn)行。為避免影響速度，必須有硬件地址變換機(jī)構(gòu)的支持（重定位寄存器），用它來(lái)存放程序在內(nèi)存中的起始地址。程序在執(zhí)行時(shí)，真正訪問的內(nèi)存地址是相對(duì)地址與重定位寄存器中的地址相加而形成的。地址變換過(guò)程是在程序執(zhí)行期間，隨著對(duì)每條指令和數(shù)據(jù)的訪問而自動(dòng)進(jìn)行的，故稱為動(dòng)態(tài)重定位。當(dāng)系統(tǒng)對(duì)內(nèi)存進(jìn)行了“緊湊”，而使若干程序從內(nèi)存的某處移至另一處時(shí)，不需對(duì)程序做任何修改，只要用該程序的新起始地址，去置換原來(lái)的起始地址即可。462.動(dòng)態(tài)重定位的實(shí)現(xiàn)473.動(dòng)態(tài)重定位分區(qū)分配算法與動(dòng)態(tài)分區(qū)分配算法基本相同，差別僅在于：增加了緊湊功能，在找不到足夠大的空閑分區(qū)來(lái)滿足用戶需求時(shí)進(jìn)行緊湊。483.動(dòng)態(tài)重定位分區(qū)分配算法優(yōu)點(diǎn)：解決了動(dòng)態(tài)分區(qū)分配所引入的“內(nèi)存零頭”問題。消除內(nèi)存碎片，提高內(nèi)存利用率。缺點(diǎn)：提高硬件成本，緊湊時(shí)花費(fèi)CPU時(shí)間。49動(dòng)態(tài)重定位VS靜態(tài)重定位靜態(tài)重定位:當(dāng)用戶程序被裝入內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換。動(dòng)態(tài)重定位:在程序運(yùn)行過(guò)程中要訪問數(shù)據(jù)時(shí)再進(jìn)行地址變換。由地址變換機(jī)構(gòu)進(jìn)行的地址變換，硬件上需要重定位寄存器的支持。

動(dòng)態(tài)重定位分區(qū)分配VS動(dòng)態(tài)分區(qū)分配 相對(duì)而言，前者具有緊湊功能，需要重定位寄存器支持504.2.5對(duì)換(Swapping)1.對(duì)換的引入把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或暫時(shí)不用的程序和數(shù)據(jù)，換出到外存，而把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，換入內(nèi)存，使其投入運(yùn)行(從而提高內(nèi)存利用率)。如果對(duì)換以整個(gè)進(jìn)程為單位，稱之為“整體對(duì)換”或“進(jìn)程對(duì)換”。目的是為了解決內(nèi)存緊張問題 如果對(duì)換以“頁(yè)”或“段”為單位，則稱之為“頁(yè)面對(duì)換”或“分段對(duì)換”。目的是為了支持虛擬存儲(chǔ)系統(tǒng)此小節(jié)僅介紹進(jìn)程對(duì)換。為了進(jìn)程對(duì)換，需三方面功能：對(duì)換空間的管理、進(jìn)程的換出及換入。512.對(duì)換空間的管理把外存分為文件區(qū)和對(duì)換區(qū)文件區(qū)：用于存放文件；為了提高空間的利用率，對(duì)其采用離散分配方式。對(duì)換區(qū)：用于存放從內(nèi)存換出的進(jìn)程；因?qū)Q操作頻繁，為提高進(jìn)程換入換出速度，對(duì)其采用連續(xù)分配方式。

(對(duì)換是在內(nèi)存與外存的對(duì)換區(qū)之間進(jìn)行）522.對(duì)換空間的管理為了對(duì)對(duì)換區(qū)中的空閑盤塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以記錄外存的使用情況。與內(nèi)存在動(dòng)態(tài)分區(qū)分配方式中所用的數(shù)據(jù)結(jié)構(gòu)相似，同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。對(duì)換空間的分配與回收，與動(dòng)態(tài)分區(qū)分配方式中的內(nèi)存分配與回收方法雷同。其分配算法可以是首次適應(yīng)算法、循環(huán)首次適應(yīng)算法或最佳適應(yīng)算法。533.進(jìn)程的換出和換入進(jìn)程換出：選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，將其程序和數(shù)據(jù)傳送到外存的對(duì)換區(qū)上，然后便可回收其所占用的內(nèi)存空間，并對(duì)其PCB作相應(yīng)修改。進(jìn)程換入：查找處于“就緒”狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程，將其換入。544.2連續(xù)分配方式小結(jié)單一連續(xù)分配方式固定分區(qū)分配分區(qū)使用表動(dòng)態(tài)分區(qū)分配首次適應(yīng)算法循環(huán)首次適應(yīng)算法最佳適應(yīng)算法動(dòng)態(tài)重定位分區(qū)分配“緊湊”動(dòng)態(tài)重定位的實(shí)現(xiàn)（重定位寄存器）對(duì)換

554.3基本分頁(yè)存儲(chǔ)管理方式引入： 連續(xù)分配方式會(huì)形成許多“碎片”，雖然可通過(guò)“緊湊”方法將碎片拼接成可用的大塊空間，但須為此付出較大開銷。

?

如果允許將一個(gè)進(jìn)程直接分散地分配到許多不相鄰接的分區(qū)中，就不必再進(jìn)行“緊湊”?；谶@一思想而產(chǎn)生了離散分配方式，相異于4.2所述連續(xù)分配方式。564.3基本分頁(yè)存儲(chǔ)管理方式分段存儲(chǔ)管理方式基本單位是段分頁(yè)存儲(chǔ)管理方式基本單位是頁(yè)基本的分頁(yè)存儲(chǔ)管理方式，要求把每個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行。（不具備頁(yè)面對(duì)換功能）4.3.1頁(yè)面和頁(yè)表4.3.2地址變換機(jī)構(gòu)4.3.3兩級(jí)和多級(jí)頁(yè)表574.3.1頁(yè)面與頁(yè)表1.頁(yè)面1)頁(yè)面和物理塊頁(yè)面：將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片物理塊：內(nèi)存物理空間分成與頁(yè)相同大小的若干個(gè)存儲(chǔ)塊分配內(nèi)存時(shí)，可將進(jìn)程中的若干頁(yè)(邏輯地址空間)分別裝入多個(gè)可以不相鄰接的塊(物理地址空間)中。 “頁(yè)內(nèi)碎片”581.頁(yè)面2)頁(yè)面大小頁(yè)面大小應(yīng)適中，且頁(yè)面大小應(yīng)為2的冪，一般為512B~8KB。頁(yè)面太小，減少了內(nèi)存碎片，有利于提高內(nèi)存利用率；但也會(huì)導(dǎo)致頁(yè)面過(guò)多，頁(yè)表過(guò)長(zhǎng)頁(yè)面太大，則會(huì)導(dǎo)致內(nèi)存碎片較多592.分頁(yè)存儲(chǔ)的地址結(jié)構(gòu)兩部分，前一部分為頁(yè)號(hào)P(220);后一部分為位移量W，即頁(yè)內(nèi)地址(212)。從邏輯地址獲得頁(yè)號(hào)p和頁(yè)內(nèi)偏移d p=INT(A/L) d=[A]MODL A——邏輯地址；L——頁(yè)大小602.地址結(jié)構(gòu)613.頁(yè)表各頁(yè)離散存儲(chǔ)在任一物理塊，系統(tǒng)需記錄各頁(yè)面對(duì)應(yīng)的物理塊。系統(tǒng)為每個(gè)進(jìn)程建立一張頁(yè)面映射表，簡(jiǎn)稱頁(yè)表。進(jìn)程的所有頁(yè)，依次在頁(yè)表中有一頁(yè)表項(xiàng)，其中記錄了其對(duì)應(yīng)的物理塊號(hào)。頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。查找頁(yè)表，即可找到每頁(yè)在內(nèi)存中的物理塊號(hào)。62頁(yè)表的作用

實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射作業(yè)每頁(yè)1K內(nèi)存每塊1K634.3.2地址變換機(jī)構(gòu)功能：完成從邏輯地址（頁(yè)號(hào)+頁(yè)內(nèi)地址）到物理地址的轉(zhuǎn)換。(頁(yè)與物理塊的大小完全一致，故)頁(yè)內(nèi)地址和內(nèi)存物理塊中的物理地址是一一對(duì)應(yīng)的，無(wú)需再轉(zhuǎn)換頁(yè)號(hào)需轉(zhuǎn)換成內(nèi)存中的物理塊號(hào)，這也是地址變換機(jī)構(gòu)的實(shí)質(zhì)需做的工作。借助于頁(yè)表完成。兩種實(shí)現(xiàn)方法基本的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu)641.基本的地址變換機(jī)構(gòu)由于頁(yè)表項(xiàng)的總數(shù)很多，不可能均用寄存器來(lái)實(shí)現(xiàn)，頁(yè)表大多駐留在內(nèi)存中。需設(shè)置一個(gè)頁(yè)表寄存器PTR（TableRegister），存放頁(yè)表在內(nèi)存的始址和頁(yè)表的長(zhǎng)度。進(jìn)程未執(zhí)行時(shí)，這兩個(gè)數(shù)據(jù)存于進(jìn)程的PCB中；執(zhí)行時(shí)，才將它們裝入PTR。651.基本的地址變換機(jī)構(gòu)地址變換過(guò)程：1)分頁(yè)地址變換機(jī)構(gòu)自動(dòng)將有效地址分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，再以頁(yè)號(hào)為索引去檢索頁(yè)表。2)在檢索頁(yè)表前，將頁(yè)號(hào)與頁(yè)表長(zhǎng)度比較，如果越界則產(chǎn)生一越界中斷，本次訪問失敗3)如果未越界，則頁(yè)表始址+頁(yè)號(hào)*頁(yè)表項(xiàng)長(zhǎng)度得到該頁(yè)號(hào)在頁(yè)表中的位置，從中可得到該頁(yè)的物理塊號(hào)，將之裝入物理地址的物理塊號(hào)部分。4)最后再將有效地址中的頁(yè)內(nèi)地址送入物理地址寄存器的塊內(nèi)地址中。66分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)67分頁(yè)系統(tǒng)的地址變換實(shí)例邏輯地址為3BADH頁(yè)面大小為2KB頁(yè)表寄存器681.基本的地址變換機(jī)構(gòu)一個(gè)問題？頁(yè)表是存放在內(nèi)存中的，這使CPU每次要存取一個(gè)數(shù)據(jù)時(shí)，都要兩次訪問內(nèi)存。第一次是訪問內(nèi)存中的頁(yè)表，從中找到該頁(yè)的物理塊號(hào)，將此塊號(hào)與頁(yè)內(nèi)偏移量W拼接以形成物理地址；第二次訪問內(nèi)存時(shí)，才是從第一步所得地址中獲得所需數(shù)據(jù)(或向此地址中寫入數(shù)據(jù))。將使計(jì)算機(jī)的處理速度降低近1/2。？692.具有快表的地址變換機(jī)構(gòu)增設(shè)一個(gè)具有并行查尋能力的特殊高速緩沖寄存器，又稱為“聯(lián)想寄存器”(AssociativeMemory)或“快表”，用于存放當(dāng)前訪問的那些頁(yè)表項(xiàng)。（意味著這些頁(yè)表項(xiàng)不在存放在內(nèi)存中）702.具有快表的地址變換機(jī)構(gòu)地址變換過(guò)程：在CPU給出有效地址后，由地址變換機(jī)構(gòu)自動(dòng)地將頁(yè)號(hào)P送入高速緩沖存儲(chǔ)器（快表），將此頁(yè)號(hào)與其中的頁(yè)號(hào)進(jìn)行比較若有相匹配的頁(yè)號(hào)（在快表中），直接讀出其所對(duì)應(yīng)的物理塊號(hào)，并送物理地址寄存器中。若沒有匹配的，還需訪問內(nèi)存中的頁(yè)表。找到后，把對(duì)應(yīng)的物理塊號(hào)送地址寄存器；也將此頁(yè)表項(xiàng)存入快表中。但如果快表已滿，則將一個(gè)老的且已被認(rèn)為不再需要的頁(yè)表項(xiàng)換出。712.具有快表的地址變換機(jī)構(gòu)722.具有快表的地址變換機(jī)構(gòu)由于成本，快表不可能做的很大，一般只存放16~512個(gè)頁(yè)表項(xiàng)。但對(duì)于中小型作業(yè)來(lái)說(shuō)，已有可能把全部頁(yè)表項(xiàng)放在快表中，但對(duì)于大型作業(yè)，則只能將其一部分頁(yè)表項(xiàng)放入其中。從快表中能找到所需頁(yè)表項(xiàng)的機(jī)率，可達(dá)90%以上。73練習(xí)

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

=1.5*2=3(μs)■增加快表后的存取訪問時(shí)間

=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)75練習(xí)某存儲(chǔ)器的用戶編程空間共32個(gè)頁(yè)面，每頁(yè)為1KB，內(nèi)存為16KB。假定某時(shí)刻一用戶頁(yè)表中已調(diào)入內(nèi)存的頁(yè)面對(duì)應(yīng)的物理塊號(hào)如下表：頁(yè)號(hào)物理塊號(hào)051102437則邏輯地址0A5C（H）所對(duì)應(yīng)的物理地址為：125C76練習(xí)0A5C＝0000,1010,0101,1100頁(yè)號(hào)為2，對(duì)應(yīng)塊號(hào)為4，有：物理地址：0001，0010,0101,1100即：125C774.3.3兩級(jí)和多級(jí)頁(yè)表引入： 計(jì)算機(jī)支持的邏輯地址空間非常大(232~264)，每個(gè)進(jìn)程的頁(yè)表項(xiàng)也非常龐大，需占據(jù)大量的連續(xù)內(nèi)存空間，這顯然不現(xiàn)實(shí)。如何解決？

1.采用離散分配方式－－解決需大量連續(xù)內(nèi)存空間問題

(將頁(yè)表再次進(jìn)行分塊)

2.只將當(dāng)前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存－－使頁(yè)表需占用的內(nèi)存減少781.兩級(jí)頁(yè)表將頁(yè)表進(jìn)行分頁(yè)，并離散地將各個(gè)頁(yè)面分別存放在不同的物理塊中，同時(shí)為離散的頁(yè)表再建立一張頁(yè)表，稱為外層頁(yè)表，其每個(gè)表項(xiàng)記錄了頁(yè)表分頁(yè)的物理塊號(hào)。邏輯地址結(jié)構(gòu)如下：791.兩級(jí)頁(yè)表頁(yè)內(nèi)地址:12位，頁(yè)面大小為212，4KB外層頁(yè)內(nèi)地址:10位，每個(gè)頁(yè)表分頁(yè)中最多可包含210個(gè)頁(yè)表項(xiàng)（對(duì)應(yīng)210個(gè)物理塊）外層頁(yè)號(hào):10位，最多允許210個(gè)頁(yè)表分頁(yè)80兩級(jí)頁(yè)表示意圖外層頁(yè)表的每個(gè)表項(xiàng)存放的是某頁(yè)表分頁(yè)的在內(nèi)存中的物理塊號(hào)頁(yè)表(分頁(yè))的每個(gè)表項(xiàng)存放的是某頁(yè)在內(nèi)存中的物理塊號(hào)可利用兩級(jí)頁(yè)表，實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換這里只是物理塊號(hào)，并不是內(nèi)存單元的編號(hào)比如外層頁(yè)號(hào)為1,外層頁(yè)內(nèi)地址也為1,尋址81具有兩級(jí)頁(yè)表的地址變換外層頁(yè)表寄存器，用于存放外層頁(yè)表的始址d01.以邏輯地址中的外層頁(yè)號(hào)p1，作為外層頁(yè)表的索引，找到d0和p1對(duì)應(yīng)的表項(xiàng)，從中可知指定頁(yè)表分頁(yè)的始址d1(物理塊號(hào))；2.以外部頁(yè)內(nèi)地址p2，作為指定頁(yè)內(nèi)分頁(yè)的索引，找到d1和p2對(duì)應(yīng)的表項(xiàng)，從中可知該頁(yè)在內(nèi)存的物理塊號(hào)b3.物理塊號(hào)b與頁(yè)內(nèi)地址d，即構(gòu)成了要訪問的內(nèi)存的物理地址。d0d182如何減少頁(yè)表所占的內(nèi)存空間上述離散分配空間的辦法只解決了大頁(yè)表無(wú)需大片連續(xù)存儲(chǔ)空間的問題，并未減少頁(yè)表所占的內(nèi)存空間。如何減少？只把當(dāng)前需要的一些頁(yè)表項(xiàng)調(diào)入內(nèi)存，以后再根據(jù)需要陸續(xù)調(diào)入其它的。在采用兩級(jí)頁(yè)表的情況下，需把外層頁(yè)表全部調(diào)入內(nèi)存，對(duì)于頁(yè)表分頁(yè)只需調(diào)入需要使用的。 在外層頁(yè)表的表項(xiàng)中，需增設(shè)一個(gè)狀態(tài)位，表示相應(yīng)的頁(yè)表分頁(yè)是否已調(diào)入內(nèi)存。 （請(qǐng)求分頁(yè)存儲(chǔ)，虛擬存儲(chǔ)器中再作詳細(xì)介紹）832.多級(jí)頁(yè)表對(duì)于64位機(jī)器，若采用兩級(jí)頁(yè)表，頁(yè)內(nèi)地址12位，外部頁(yè)內(nèi)地址10位，這時(shí)外部頁(yè)號(hào)會(huì)達(dá)42位，每個(gè)表項(xiàng)占4個(gè)字節(jié)，就需要244B的連續(xù)內(nèi)存空間。顯然無(wú)法接受。采用多級(jí)頁(yè)表，將外層頁(yè)表再進(jìn)行分頁(yè)，將各分頁(yè)離散地裝入到不相鄰接的物理塊中，再利用第2級(jí)的外層頁(yè)表來(lái)映射它們之間的關(guān)系。844.3基本分頁(yè)存儲(chǔ)管理方式小結(jié)頁(yè)面、物理塊與頁(yè)表分頁(yè)地址結(jié)構(gòu)：頁(yè)號(hào)＋頁(yè)內(nèi)地址地址變換機(jī)構(gòu)基本的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu)兩級(jí)和多級(jí)頁(yè)表854.4基本分段存儲(chǔ)管理方式存儲(chǔ)管理方式從固定分區(qū)到動(dòng)態(tài)分區(qū)分配，進(jìn)而到分頁(yè)存儲(chǔ)管理方式主要是為了提高內(nèi)存的利用率。提出基本分段存儲(chǔ)管理方式主要是為了滿足用戶（程序員）在編程和使用上的多方面的要求。864.4基本分段存儲(chǔ)管理方式4.4.1分段存儲(chǔ)管理方式的引入4.4.2分段系統(tǒng)的基本原理4.4.3信息共享4.4.4段頁(yè)式存儲(chǔ)管理方式874.4.1分段存儲(chǔ)管理方式的引入為了滿足用戶和程序的如下需要：

1)方便編程 用戶通常將作業(yè)按邏輯關(guān)系劃分為若干段。希望要訪問的邏輯地址是由段名和段內(nèi)偏移量決定。2)信息共享 實(shí)現(xiàn)共享是以信息的邏輯單位－段為基礎(chǔ)的。為實(shí)現(xiàn)段的共享，希望存儲(chǔ)管理能與用戶程序分段的組織方式相適應(yīng)。884.4.1分段存儲(chǔ)管理方式的引入3)信息保護(hù) 對(duì)信息的邏輯單位－段進(jìn)行保護(hù)4)動(dòng)態(tài)增長(zhǎng) 段在使用過(guò)程中可能會(huì)不斷增長(zhǎng)，唯有分段存儲(chǔ)可較好解決該問題5)動(dòng)態(tài)鏈接 動(dòng)態(tài)鏈接在運(yùn)行時(shí)，只將主程序?qū)?yīng)的目標(biāo)程序段裝入內(nèi)存。在需調(diào)用某些段時(shí)才將其裝入，需要以段作為存儲(chǔ)管理的單位。894.4.2分段系統(tǒng)的基本原理1.分段2.段表3.地址變換機(jī)構(gòu)901.分段作業(yè)的地址空間被劃分為若干個(gè)段，每個(gè)段用來(lái)定義一組邏輯信息，均從0開始編址，并采用一段連續(xù)的地址空間。段的長(zhǎng)度由相應(yīng)的邏輯信息組的長(zhǎng)度決定，因而各段長(zhǎng)度不等。邏輯地址由段號(hào)和段內(nèi)地址組成。912.段表進(jìn)程的多個(gè)段被離散的放入內(nèi)存不同位置。為了能將物理內(nèi)存與邏輯段地址對(duì)應(yīng)起來(lái)，需為每個(gè)進(jìn)程建立一張段映射表。每個(gè)段在表中占有一個(gè)表項(xiàng)，記錄了該段在內(nèi)存中的始址和段的長(zhǎng)度。進(jìn)程可通過(guò)查找段表，找到每個(gè)段對(duì)應(yīng)的內(nèi)存區(qū)，實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。92利用段表實(shí)現(xiàn)地址映射933.地址變換機(jī)構(gòu)段表寄存器存放段表始址和段表長(zhǎng)度SL。94與分頁(yè)系統(tǒng)一樣，當(dāng)段表放在內(nèi)存中時(shí)，每訪問一個(gè)數(shù)據(jù)，都須訪問兩次內(nèi)存。解決方法也類似，增設(shè)一個(gè)高速緩沖寄存器用于保存最近常用的段表項(xiàng)。954.分頁(yè)和分段的主要區(qū)別分頁(yè)是出于系統(tǒng)管理的需要，分段是出于用戶應(yīng)用的需要一條指令或一個(gè)操作數(shù)可能會(huì)跨越兩個(gè)頁(yè)的分界處，而不會(huì)跨越兩個(gè)段的分界處。頁(yè)大小是系統(tǒng)固定的，而段大小則通常不固定。邏輯地址表示：分頁(yè)是一維地址空間，各個(gè)模塊在鏈接時(shí)組織成同一個(gè)地址空間；只利用一個(gè)標(biāo)記符即可表示一個(gè)地址。分段是二維地址空間，各個(gè)模塊在鏈接時(shí)可以每個(gè)段組織成一個(gè)地址空間；標(biāo)識(shí)地址需給出段名和段內(nèi)地址。通常段比頁(yè)大，因而段表比頁(yè)表短，可以縮短查找時(shí)間，提高訪問速度。964.4.3信息共享分段系統(tǒng)的突出優(yōu)點(diǎn)，易于實(shí)現(xiàn)段的共享，即允許若干個(gè)進(jìn)程共享一個(gè)或多個(gè)分段。分頁(yè)系統(tǒng)也可實(shí)現(xiàn)程序和數(shù)據(jù)的共享，但不如分段系統(tǒng)來(lái)得方便。（舉例對(duì)比）可重入代碼：一種允許多個(gè)進(jìn)程同時(shí)訪問（可被共享）的代碼；不允許任何進(jìn)程對(duì)它進(jìn)行修改。974.4.3信息共享例：多用戶系統(tǒng)，可同時(shí)接納40個(gè)用戶，每個(gè)用戶均可執(zhí)行文本編輯程序。文本編輯程序有160KB代碼和40KB數(shù)據(jù)區(qū)，若代碼為非可重入的，需要8000KB內(nèi)存空間支持40個(gè)用戶。如果160KB程序代碼為可重入的，則不論在分頁(yè)還是在分段系統(tǒng)中該代碼均可被共享，此時(shí)所需內(nèi)存空間為160+40*40=1760KB。984.4.3信息共享分頁(yè)系統(tǒng)中：假定每個(gè)頁(yè)面大小為4KB，代碼需占用40個(gè)頁(yè)面，數(shù)據(jù)需占10頁(yè)面。每個(gè)用戶進(jìn)程的頁(yè)表中均需建立相應(yīng)的頁(yè)表項(xiàng)。如圖:99ed1ed2…ed40data1…data102122…6061…70…ed1ed2…ed40data1…data10data1…data10進(jìn)程1進(jìn)程2頁(yè)表頁(yè)表ed1ed2…ed40data1…data102122…6071…80主存分頁(yè)系統(tǒng)中共享editor，需建立比較復(fù)雜的頁(yè)表021226061707180100分段系統(tǒng)中共享editor示意editordata1editordata2段長(zhǎng)基址1608040240段長(zhǎng)基址1608040380editordata1…data2進(jìn)程2進(jìn)程1在分段系統(tǒng)中，實(shí)現(xiàn)共享只需在每個(gè)進(jìn)程的段表中為文本編輯程序代碼段設(shè)置一個(gè)段表項(xiàng)，比分頁(yè)系統(tǒng)簡(jiǎn)單的多。101略過(guò)：關(guān)于共享的進(jìn)一步說(shuō)明頁(yè)式地址是一維的，即每個(gè)邏輯地址是一個(gè)整數(shù)，由硬件將其分成：頁(yè)號(hào)|頁(yè)內(nèi)位移,故頁(yè)號(hào)是唯一的，程序段的共享必須用相同頁(yè)號(hào)。如：

call2148—〉call2|100段式地址是二維的，兩個(gè)數(shù)字。各進(jìn)程的段號(hào)未必一致，因此不同的進(jìn)程可用不同的段號(hào)共享同一段。如：

callac1|100進(jìn)程1：ac1=2；進(jìn)程2：ac1=41024.4.4段頁(yè)式存儲(chǔ)管理方式分頁(yè)系統(tǒng)能有效地提高內(nèi)存利用率，而分段系統(tǒng)則能很好地滿足用戶需要。？段頁(yè)式系統(tǒng)1031.基本原理將分段和分頁(yè)原理結(jié)合，先將用戶程序分成若干個(gè)段，再把每個(gè)段分成若干個(gè)頁(yè)，并為每一個(gè)段賦予一個(gè)段名。段頁(yè)式系統(tǒng)中，地址結(jié)構(gòu)由段號(hào)、段內(nèi)頁(yè)號(hào)及頁(yè)內(nèi)地址三部分組成。頁(yè)104利用段表和頁(yè)表實(shí)現(xiàn)地址映射每個(gè)作業(yè)一張段表，每段一張頁(yè)表。先查段表，再查該段的頁(yè)表，才能找到物理塊號(hào)。再將其與頁(yè)內(nèi)地址組合1052.地址變換過(guò)程1.利用段表始址d0和段號(hào)s來(lái)求出該段所對(duì)應(yīng)的段表項(xiàng)在段表中的位置，從中得到該段的頁(yè)表始址d1；2.利用頁(yè)表始址d1和段內(nèi)頁(yè)號(hào)P獲得對(duì)應(yīng)頁(yè)的頁(yè)表項(xiàng)位置，從中讀出該頁(yè)所在的物理塊號(hào)P’；3.利用塊號(hào)P’和頁(yè)內(nèi)地址d來(lái)構(gòu)成物理地址。1062.地址變換過(guò)程1.利用段表始址和段號(hào)來(lái)求出該段所對(duì)應(yīng)的段表項(xiàng)在段表中的位置，從中得到該段的頁(yè)表始址；2.利用頁(yè)表始址和段內(nèi)頁(yè)號(hào)P獲得對(duì)應(yīng)頁(yè)的頁(yè)表項(xiàng)位置，從中讀出該頁(yè)所在的物理塊號(hào)b；3.利用塊號(hào)b和頁(yè)內(nèi)地址來(lái)構(gòu)成物理地址。1072.地址變換過(guò)程段頁(yè)式系統(tǒng)中，訪問數(shù)據(jù)需三次訪問內(nèi)存。 第一次訪問內(nèi)存中的段表，取得頁(yè)表始址；第二次訪問內(nèi)存的頁(yè)表，取得該頁(yè)的物理塊號(hào)，并與頁(yè)內(nèi)地址一起組成實(shí)際的物理地址；第三次從物理地址中取出指令或數(shù)據(jù)。為了避免每次均需三次訪問，可在地址變換機(jī)構(gòu)中增設(shè)一個(gè)高速緩沖寄存器，將常用的段表和頁(yè)表存儲(chǔ)在高速緩沖中。1084.4基本分段存儲(chǔ)管理方式小結(jié)分段存儲(chǔ)管理方式的引入方便用戶分段系統(tǒng)的基本原理分段系統(tǒng)的地址變換過(guò)程段表始址+段號(hào)->段的基址與段內(nèi)地址結(jié)合->物理地址信息共享分頁(yè)系統(tǒng)與分段系統(tǒng)的比較段頁(yè)式存儲(chǔ)管理方式段表始址+段號(hào)->頁(yè)表始址與頁(yè)號(hào)結(jié)合->頁(yè)面對(duì)應(yīng)的物理塊號(hào)與頁(yè)內(nèi)地址結(jié)合->物理地址1094.5虛擬存儲(chǔ)器的基本概念連續(xù)分配方式、基本分頁(yè)、基本分段存儲(chǔ)管理方式均需將一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行，這將導(dǎo)致大作業(yè)無(wú)法運(yùn)行。解決方法：物理上增加內(nèi)存容量有一定限制從邏輯上擴(kuò)充內(nèi)存容量此即虛擬存儲(chǔ)器所要解決的主要問題1104.5虛擬存儲(chǔ)器的基本概念4.5.1虛擬存儲(chǔ)器的引入4.5.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法4.5.3虛擬存儲(chǔ)器的特征1114.5.1虛擬存儲(chǔ)器的引入1.常規(guī)存儲(chǔ)器管理方式的特征一次性：作業(yè)運(yùn)行前需一次性全部裝入內(nèi)存這可能導(dǎo)致大作業(yè)無(wú)法裝入并非全部程序和數(shù)據(jù)都需用到，一次裝入，浪費(fèi)內(nèi)存駐留性：一旦裝入便一直駐留內(nèi)存直至作業(yè)結(jié)束不再運(yùn)行的程序模塊仍將占用寶貴的內(nèi)存資源一次性及駐留性是否是必需的？1124.5.1虛擬存儲(chǔ)器的引入2.局部性原理程序執(zhí)行時(shí)的特點(diǎn)：程序執(zhí)行時(shí)，除少部分轉(zhuǎn)移和過(guò)程調(diào)用指令外，大多仍是順序執(zhí)行的。過(guò)程調(diào)用雖可導(dǎo)致程序由一區(qū)域轉(zhuǎn)至另一區(qū)域，但調(diào)用深度大多不超過(guò)5。程序在一段時(shí)間內(nèi)都局部于這些過(guò)程的范圍內(nèi)執(zhí)行。程序中存在循環(huán)結(jié)構(gòu)，它們將多次執(zhí)行程序中對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，往往局限于較小的范圍內(nèi)1134.5.1虛擬存儲(chǔ)器的引入2.局部性原理局部性的表現(xiàn)：空間局限性。一段時(shí)間內(nèi)所訪問的地址可能集中于一定的范圍之內(nèi)。（程序的順序執(zhí)行）時(shí)間局限性。某條指令或數(shù)據(jù)可能被再次執(zhí)行或訪問。（循環(huán)操作）根據(jù)局部性原理，程序在運(yùn)行之前沒有必要一次性全部裝入，也沒必要長(zhǎng)期駐留內(nèi)存。1144.5.1虛擬存儲(chǔ)器的引入引入虛擬存儲(chǔ)器基于局部性原理，程序可僅將需運(yùn)行的部分頁(yè)或段裝入內(nèi)存便可開始執(zhí)行。執(zhí)行中，如果訪問的頁(yè)段已調(diào)入內(nèi)存便可繼續(xù)；否則，應(yīng)利用OS提供的請(qǐng)求調(diào)頁(yè)(段)功能將它們調(diào)入內(nèi)存。若此時(shí)內(nèi)存已滿，應(yīng)利用頁(yè)(段)置換功能，將暫時(shí)不用的調(diào)出，騰出地方調(diào)入需要的頁(yè)(段)。這樣，便可使一個(gè)大的程序在較小的空間中運(yùn)行;也可使內(nèi)存中同時(shí)裝入更多的進(jìn)程并發(fā)執(zhí)行。1154.5.1虛擬存儲(chǔ)器的引入3.虛擬存儲(chǔ)器定義具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)系統(tǒng)。實(shí)質(zhì)：以時(shí)間換空間，但時(shí)間犧牲不大。虛擬大小由內(nèi)存容量和外存容量之和決定。1164.5.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器是建立在離散分配的存儲(chǔ)管理方式基礎(chǔ)上的。為什么？虛擬存儲(chǔ)器請(qǐng)求調(diào)入頁(yè)面轉(zhuǎn)換若采用連續(xù)分配方式，一次性將全部數(shù)據(jù)調(diào)入，無(wú)需虛擬存儲(chǔ)。實(shí)現(xiàn)的兩種方式:請(qǐng)求分頁(yè)請(qǐng)求分段1171.分頁(yè)請(qǐng)求系統(tǒng)在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能。只裝入部分頁(yè)面即可運(yùn)行，可通過(guò)調(diào)頁(yè)和頁(yè)面置換功能，調(diào)入需要的頁(yè)面，同時(shí)將暫不需要的換出。以頁(yè)為單位置換需硬件：請(qǐng)求分頁(yè)的頁(yè)表機(jī)制缺頁(yè)中斷機(jī)構(gòu)地址變換機(jī)構(gòu)需軟件：實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)的軟件實(shí)現(xiàn)頁(yè)面置換的軟件1182.請(qǐng)求分段系統(tǒng)在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段及分段置換功能。只裝入部分段即可運(yùn)行，可通過(guò)調(diào)段和段置換功能，調(diào)入需要的段，同時(shí)將暫不需要的調(diào)出。以段為單位置換需硬件：請(qǐng)求分段的段表結(jié)構(gòu)缺段中斷機(jī)構(gòu)地址變換機(jī)構(gòu)需軟件：請(qǐng)求調(diào)段和置換軟件1194.5.3虛擬存儲(chǔ)器的特征1.離散性：離散分配內(nèi)存2.多次性：多次裝入3.對(duì)換性：允許作業(yè)運(yùn)行中進(jìn)行換進(jìn)換出4.虛擬性：從邏輯上擴(kuò)充內(nèi)存虛擬性以多次性和對(duì)換性為基礎(chǔ)，而多次性和對(duì)換性又必須建立在離散分配的基礎(chǔ)上。最本質(zhì)的特征是離散性，在此基礎(chǔ)上又形成了多次性和對(duì)換性，所表現(xiàn)出來(lái)的最重要的特征是

虛擬性.1204.5虛擬存儲(chǔ)器小結(jié)虛擬存儲(chǔ)器的引入大作業(yè)小內(nèi)存運(yùn)行局部性原理 具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上擴(kuò)充內(nèi)存虛擬存儲(chǔ)器的實(shí)現(xiàn)方法分頁(yè)請(qǐng)求系統(tǒng) 請(qǐng)求分段系統(tǒng)虛擬存儲(chǔ)器的特征離散性 多次性 對(duì)換性 虛擬性1214.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式建立在基本分頁(yè)基礎(chǔ)上，為了支持虛擬存儲(chǔ)器功能，而增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能。每次調(diào)入和換出的基本單位是固定長(zhǎng)度的頁(yè)。1224.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.6.1請(qǐng)求分頁(yè)中的硬件支持4.6.2內(nèi)存分配策略和分配算法4.6.3調(diào)頁(yè)策略1234.6.1請(qǐng)求分頁(yè)中的硬件支持1.頁(yè)表機(jī)制由于應(yīng)用程序只是一部分調(diào)入內(nèi)存即只有部分頁(yè)位于內(nèi)存中，須在頁(yè)表中增加若干項(xiàng)，供程序（數(shù)據(jù)）換進(jìn)換出時(shí)參考。頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問字段A修改位M外存地址P:是否已調(diào)入內(nèi)存A:一段時(shí)間內(nèi)使用的次數(shù)或多久未使用M:調(diào)入內(nèi)存后是否修改過(guò)1244.6.1請(qǐng)求分頁(yè)中的硬件支持2.缺頁(yè)中斷機(jī)構(gòu)當(dāng)訪問的頁(yè)不在內(nèi)存中時(shí)便產(chǎn)生缺頁(yè)中斷，請(qǐng)求OS將其調(diào)入。缺頁(yè)中斷具有一般中斷的入棧、轉(zhuǎn)中斷處理、出棧等過(guò)程，但又其特殊性：在指令執(zhí)行期間產(chǎn)生和處理中斷。發(fā)現(xiàn)訪問的頁(yè)不在內(nèi)存即產(chǎn)生；通常是在等到指令執(zhí)行完畢后。一條指令在執(zhí)行期間，可能要產(chǎn)生多次中斷。（如圖）125涉及6次缺頁(yè)中斷的指令頁(yè)面6543211264.6.1請(qǐng)求分頁(yè)中的硬件支持3.地址變換機(jī)構(gòu)大致步驟：1)在地址變換時(shí)，首先檢索快表，試圖從中找到要訪問的頁(yè)。如找到，修改其訪問位；對(duì)于“寫”指令，還要設(shè)置修改位的值。如未找到，則轉(zhuǎn)3。2)利用頁(yè)表項(xiàng)中的物理塊號(hào)和頁(yè)內(nèi)地址，形成物理地址，結(jié)束。3)查找頁(yè)表，找到頁(yè)表項(xiàng)后，判斷其狀態(tài)位P，查看該頁(yè)是否在內(nèi)存中。如果在，則將該頁(yè)寫入快表（若快表已滿，則應(yīng)該先調(diào)出某個(gè)或某些頁(yè)表項(xiàng)）。如果不在，則產(chǎn)生缺頁(yè)中斷，由OS從外存將該頁(yè)調(diào)入內(nèi)存。返回1。參圖4-241271284.6.2內(nèi)存分配策略和分配算法三個(gè)問題最小物理塊數(shù)的確定物理塊的分配策略物理塊的分配算法1291.最小物理塊數(shù)的確定最小物理塊數(shù)是指保證進(jìn)程正常運(yùn)行所需的最少物理塊數(shù)。與計(jì)算機(jī)的硬件機(jī)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。單地址指令且采用直接尋址方式，最少物理塊數(shù)為2(指令頁(yè)面數(shù)據(jù)頁(yè)面)單地址指令且采用間接尋址方式，3多字節(jié)指令，6（幻燈片125頁(yè)）1302.物理塊的分配策略1)固定分配局部置換2)可變分配全局置換3)可變分配局部置換1312.物理塊的分配策略1)固定分配局部置換每個(gè)進(jìn)程分配固定數(shù)目的物理塊數(shù)，在整個(gè)運(yùn)行期間都不改變?nèi)绻表?yè)，則只能從該進(jìn)程在內(nèi)存的頁(yè)面中選中一頁(yè)，進(jìn)行換出操作，然后再調(diào)入一頁(yè)。特點(diǎn)：為每個(gè)進(jìn)程分配多少頁(yè)是合適的值難以確定。此外，在對(duì)換時(shí)會(huì)浪費(fèi)比較多的時(shí)間。1322.物理塊的分配策略2)可變分配全局置換每個(gè)進(jìn)程預(yù)先分配一定數(shù)目的物理塊，同時(shí)OS也保持一個(gè)空閑物理塊隊(duì)列。（進(jìn)程的塊數(shù)運(yùn)行時(shí)可能會(huì)有變化）當(dāng)缺頁(yè)時(shí)，首先將對(duì)OS所占有的空閑塊進(jìn)行分配，從而增加各進(jìn)程的物理塊數(shù)。當(dāng)OS的空閑塊全部用完，將引起換出操作。（換出的頁(yè)可能是任一進(jìn)程的中的一頁(yè)）1332.物理塊的分配策略3)可變分配局部置換思路：先為進(jìn)程分配部分物理塊運(yùn)行；系統(tǒng)根據(jù)缺頁(yè)率動(dòng)態(tài)調(diào)整各進(jìn)程占有的物理塊數(shù)目，使其保持在一個(gè)比較低的缺頁(yè)率狀態(tài)下（輕微缺頁(yè)時(shí)，僅允許從進(jìn)程自身的頁(yè)面中選一頁(yè)換出再換入需要的；只有頻繁缺頁(yè)時(shí)，系統(tǒng)才為其分配附加的物理塊）。特點(diǎn)：使大部分進(jìn)程可以達(dá)到比較近似的性能。1343.物理塊的分配算法

－－針對(duì)固定分配策略平均分配算法將物理塊平均分配給各進(jìn)程未考慮進(jìn)程本身的大?。?yè)數(shù)有多有少）按比例分配算法根據(jù)進(jìn)程大小按比例分配物理塊

m為物理塊總數(shù),S代表各進(jìn)程頁(yè)數(shù)之和

b取整，且應(yīng)大于最小物理塊數(shù)考慮優(yōu)先權(quán)的分配算法物理塊分為兩部分：一部分按比例分配；一部分根據(jù)各進(jìn)程優(yōu)先權(quán)分配1354.6.3調(diào)頁(yè)策略1.何時(shí)調(diào)入頁(yè)面2.從何處調(diào)入頁(yè)面3.頁(yè)面調(diào)入過(guò)程1361.何時(shí)調(diào)入頁(yè)面根據(jù)將進(jìn)程運(yùn)行時(shí)所缺頁(yè)面調(diào)入內(nèi)存的時(shí)機(jī)預(yù)調(diào)頁(yè)策略將那些預(yù)計(jì)在不久之后便會(huì)被訪問的頁(yè)面預(yù)先調(diào)入內(nèi)存預(yù)測(cè)成功率僅約50%請(qǐng)求調(diào)頁(yè)策略在運(yùn)行中，發(fā)現(xiàn)要訪問的頁(yè)面不在內(nèi)存中，便提出請(qǐng)求，由OS將其調(diào)入每次僅能調(diào)入一頁(yè)，增加了磁盤的啟動(dòng)頻率，系統(tǒng)開銷較大1372.從何處調(diào)入頁(yè)面請(qǐng)求分頁(yè)系統(tǒng)中外存分兩個(gè)部分：文件區(qū)和對(duì)換區(qū)。一般應(yīng)當(dāng)盡量使用對(duì)換區(qū)來(lái)調(diào)入頁(yè)面。對(duì)于不同情況，采用不同的策略：系統(tǒng)有足夠的對(duì)換空間全部由對(duì)換區(qū)調(diào)入，事先需將有數(shù)據(jù)從文件區(qū)拷貝到對(duì)換區(qū)系統(tǒng)對(duì)換空間不足凡是不會(huì)被修改的文件都直接從文件區(qū)調(diào)入，換出時(shí)不必再改動(dòng)文件區(qū)；對(duì)于需修改的部分，換出時(shí)便調(diào)到對(duì)換區(qū)，需要時(shí)再?gòu)膶?duì)換區(qū)調(diào)入。UNIX的調(diào)入方式未運(yùn)行過(guò)的頁(yè)面均從文件區(qū)調(diào)入；對(duì)于曾經(jīng)運(yùn)行過(guò)但又被換出的頁(yè)面放在對(duì)換區(qū)，以后從對(duì)換區(qū)調(diào)入。1383.頁(yè)面調(diào)入過(guò)程

進(jìn)程需要的頁(yè)面不在內(nèi)存，引起缺頁(yè)中斷 中斷處理程序保留現(xiàn)場(chǎng)環(huán)境，轉(zhuǎn)入缺頁(yè)中斷處理程序

中斷處理程序如何調(diào)入頁(yè)面？

1.中斷處理程序查找頁(yè)表，得到對(duì)應(yīng)的外存物理塊號(hào)。如果內(nèi)存有空閑，則啟動(dòng)磁盤操作，將所缺的頁(yè)面讀入，并修改頁(yè)表。否則，即內(nèi)存無(wú)空閑時(shí)，轉(zhuǎn)2。

2.執(zhí)行置換算法，選出要換出的頁(yè)面（如果該頁(yè)修改過(guò)，應(yīng)將其寫入磁盤）然后將所缺頁(yè)調(diào)入內(nèi)存，修改相應(yīng)表項(xiàng)，將其狀態(tài)位設(shè)為"1"，并放入快表。

3.利用修改后的頁(yè)表，形成物理地址，訪問內(nèi)存數(shù)據(jù)。1394.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式小結(jié)請(qǐng)求分頁(yè)中的硬件支持頁(yè)表機(jī)制 缺頁(yè)中斷機(jī)構(gòu) 地址變換機(jī)構(gòu)內(nèi)存分配策略和分配算法最小物理塊的確定物理塊的分配策略固定分配局部置換可變分配全局置換可變分配局部置換物理塊分配算法平均分配按比例分配考慮優(yōu)先權(quán)的分配調(diào)頁(yè)策略何時(shí)調(diào)入（預(yù)調(diào)、請(qǐng)求）從何處調(diào)入（對(duì)換區(qū)）頁(yè)面調(diào)入過(guò)程（內(nèi)存是否有空閑）1404.7頁(yè)面置換算法請(qǐng)求分頁(yè)存儲(chǔ)管理方式，若訪問的頁(yè)面不在內(nèi)存，且內(nèi)存已無(wú)空閑空間時(shí)，需首先從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，然后調(diào)入。需根據(jù)一定的算法來(lái)確定將哪個(gè)頁(yè)面調(diào)出，此算法即頁(yè)面置換算法，用來(lái)選擇需調(diào)出的頁(yè)面。理論目標(biāo)：減少對(duì)換量，具有較低的頁(yè)面更換頻率。應(yīng)優(yōu)先將那些以后不再訪問或較長(zhǎng)時(shí)間內(nèi)不再訪問的頁(yè)面調(diào)出。1414.7頁(yè)面置換算法4.7.1最佳置換算法和先進(jìn)先出置換算法4.7.2最近最久未使用(LRU)置換算法4.7.3Clock置換算法4.7.4其它置換算法 具體7種1424.7.1最佳置換算法和先進(jìn)先出

置換算法1.最佳置換算法 理論上的算法，其所選擇的被淘汰頁(yè)將是以后永不使用，或者是最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁(yè)。 無(wú)法預(yù)知頁(yè)面被訪問的次序，無(wú)法實(shí)現(xiàn)，但可用來(lái)評(píng)價(jià)其它算法。1431.最佳置換算法每次選擇最長(zhǎng)時(shí)間內(nèi)不再訪問的頁(yè)面調(diào)出內(nèi)存“向后看”缺頁(yè)次數(shù)為6，缺頁(yè)率6/12＝50%1442.先進(jìn)先出(FIFO)頁(yè)面置換算法最早出現(xiàn)的置換算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)替換指針（總是指向最老的頁(yè)面）該算法不能保證經(jīng)常使用的頁(yè)面不被淘汰，會(huì)導(dǎo)致缺頁(yè)率較高。1452.先進(jìn)先出(FIFO)頁(yè)面置換算法每次選擇最早進(jìn)入的頁(yè)面調(diào)出內(nèi)存缺頁(yè)次數(shù)為9，缺頁(yè)率9/12＝75%1464.7.2最近最久未使用(LRU)

置換算法1.算法描述LeastRecentlyUsed根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策，利用“最近的過(guò)去”作為“最近的將來(lái)”的近似，選擇最近最久未使用的頁(yè)面予以淘汰。為每個(gè)頁(yè)面設(shè)置一個(gè)訪問字段，記錄一個(gè)頁(yè)面自上次被訪問以來(lái)所經(jīng)歷的時(shí)間t。1471.LRU算法描述每次選擇最近最久未使用的頁(yè)面調(diào)出內(nèi)存“向前看”缺頁(yè)次數(shù)為7，缺頁(yè)率7/12＝58.3%1482.LRU置換算法的硬件支持LRU算法為了記錄哪一頁(yè)是最近最久未使用的頁(yè)面，需要以下兩類硬件之一支持寄存器棧1491)寄存器為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)n位移位寄存器，R=Rn-1Rn-2Rn-3…R2R1R0定時(shí)將所有寄存器右移一位（其值將會(huì)減?。划?dāng)進(jìn)程訪問某頁(yè)時(shí)，便將該頁(yè)相應(yīng)寄存器的最高位Rn-1置1（其值將會(huì)增大）。最久未訪問的頁(yè)面對(duì)應(yīng)的寄存器的值肯定最小，據(jù)此可找到要淘汰的頁(yè)面。1501)寄存器1512)棧利用一個(gè)特殊的棧來(lái)記錄頁(yè)面的使用次序當(dāng)進(jìn)程訪問某頁(yè)時(shí)，將其從棧中移出壓入“棧頂”；換出時(shí)，將“棧底”換出。這樣可以保證：棧頂總是最新被訪問頁(yè)面的頁(yè)號(hào)，而棧底則是最近最久未使用頁(yè)面的頁(yè)號(hào)。1522)棧進(jìn)程訪問頁(yè)面的序列為：

4,7,0,7,1,0,1,2,1,2,6棧的變化情況訪問6時(shí)缺頁(yè)將棧底換出1534.7.3Clock置換算法LRU算法較好，但硬件要求較高，在實(shí)際應(yīng)用中多采用其近似算法，Clock算法是其中一種。1.簡(jiǎn)單的Clock置換算法2.改進(jìn)型Clock置換算法1541.簡(jiǎn)單的Clock置換算法內(nèi)存中所有頁(yè)面通過(guò)鏈接指針形成一個(gè)循環(huán)隊(duì)列每頁(yè)有一個(gè)使用訪問位(usebit)，若該頁(yè)被訪問則置其usebit=1。缺頁(yè)置換時(shí)采用一個(gè)指針，從當(dāng)前指針位置開始按地址依次檢查各頁(yè)：尋找usebit=0的頁(yè)面作為被置換頁(yè)指針經(jīng)過(guò)的userbit=1的頁(yè)都修改userbit=0,暫不換出最后指針停留在被置換頁(yè)的下一個(gè)頁(yè)。1551.簡(jiǎn)單的Clock置換算法1562.改進(jìn)型Clock置換算法該算法中，除考慮頁(yè)面的最近使用情況外，還須再增加一個(gè)因素－－置換代價(jià)。在頁(yè)面換出時(shí)，如果該頁(yè)修改過(guò)，便須將它重新寫回磁盤，相對(duì)于未修改過(guò)的頁(yè)面，其置換代價(jià)就高。1572.改進(jìn)型Clock置換算法選擇頁(yè)面時(shí)，盡量選擇既未使用又沒有修改的頁(yè)面。頁(yè)面（訪問位A，修改位M）有四種不同情形：1類(A=0,M=0）既未訪問，又沒有修改，最佳淘汰頁(yè)2類(A=0,M=1）最近未訪問，但已被修改，效率低的淘汰頁(yè)3類(A=1,M=0）被訪問，但沒有修改，可能再次被訪問4類(A=1,M=1）既被訪問，又有修改 淘汰頁(yè)優(yōu)先選擇前兩類，實(shí)在沒有才考慮后兩類1582.改進(jìn)型Clock置換算法執(zhí)行過(guò)程：（1）指針從當(dāng)前位置開始，開始第一輪掃描循環(huán)隊(duì)列，尋找未訪問且沒有修改過(guò)的頁(yè)面（第1類頁(yè)面），找到則可換出。（2）如果找不到，則開始第二輪掃描，尋找未訪問但修改過(guò)的頁(yè)面（第2類頁(yè)面），并且每經(jīng)過(guò)一個(gè)頁(yè)面時(shí)，將其訪問位A設(shè)置為0（未訪問）。如果找到一個(gè)第2類頁(yè)面，則可換出。（3）如果仍舊未找到合適的換出頁(yè)面，則此時(shí)指針回到初始位置，且所有頁(yè)面其訪問位A置為0。再轉(zhuǎn)回（1）繼續(xù)工作，這時(shí)肯定可以經(jīng)由前兩步找到換出頁(yè)面?？捎行p少磁盤I/O操作，但算法本身開銷有所增大1594.7.4其它置換算法1.最少使用(LFU:LeastFrequentlyUsed)置換算法2.頁(yè)面緩沖算法(PBA:PageBufferingAlgorithm)1601.最少使用置換算法LFU目的：選擇到當(dāng)前時(shí)間為止被訪問次數(shù)最少的頁(yè)面被置換；實(shí)現(xiàn)方法1：每頁(yè)設(shè)置訪問計(jì)數(shù)器，每當(dāng)頁(yè)面被訪問時(shí)，該頁(yè)面的訪問計(jì)數(shù)器加1；發(fā)生缺頁(yè)中斷時(shí)，淘汰計(jì)數(shù)值最小的頁(yè)面；因頁(yè)面訪問次數(shù)可能極多，要求計(jì)數(shù)器容量極大，此法不可行。實(shí)現(xiàn)方法2：類似于LRU算法，每個(gè)頁(yè)面設(shè)立n位移位寄存器：被訪問時(shí)左邊最高位置1，定期右移并且最高位補(bǔ)0，這樣，在最近一段時(shí)間內(nèi)時(shí)用最少的頁(yè)面將是ΣRi最小的頁(yè)。1612.頁(yè)面緩沖算法PBA對(duì)FIFO算法的發(fā)展，通過(guò)被置換頁(yè)面的緩沖，有機(jī)會(huì)找回剛被置換的頁(yè)面；被置換頁(yè)面的選擇和處理：由操作系統(tǒng)中專門的頁(yè)面置換進(jìn)程，用FIFO算法選擇被置換頁(yè)，把被置換的頁(yè)面放入內(nèi)存中的兩個(gè)鏈表（空閑頁(yè)面鏈表和已修改頁(yè)面鏈表）之一：如果頁(yè)面未被修改，就將其歸入到空閑頁(yè)面鏈表的末尾否則將其歸入到已修改頁(yè)面鏈表。1622.頁(yè)面緩沖算法這種算法被換出的頁(yè)面，鏈接在空閑頁(yè)面鏈表和已修改頁(yè)面鏈表中，仍留在內(nèi)存中。當(dāng)進(jìn)程再訪問時(shí)，只需花