第4章-存儲(chǔ)管理

1第四章諶衛(wèi)軍清華大學(xué)操作系統(tǒng)2第四章存儲(chǔ)管理單道程序存儲(chǔ)管理分區(qū)存儲(chǔ)管理頁式和段式存儲(chǔ)管理覆蓋技術(shù)與交換技術(shù)虛擬存儲(chǔ)技術(shù)3即使是簡(jiǎn)單的、老的存儲(chǔ)管理方案仍然有必要掌握。有些老的概念仍然有用使用何種存儲(chǔ)管理方案取決于硬件平臺(tái)有些方案需要硬件支持；手持設(shè)備和嵌入式系統(tǒng)等新的硬件平臺(tái)可能只有基本的硬件支持。4理想中的存儲(chǔ)器：更大、更快、更便宜的非易失性存儲(chǔ)器。實(shí)際中的存儲(chǔ)器：存儲(chǔ)器層次結(jié)構(gòu)（本圖摘自AndrewS.Tanenbaum：“ModernOperatingSystems”）實(shí)際中的存儲(chǔ)器：存儲(chǔ)管理？5我們主要考察內(nèi)存（MainMemory）的管理。64.1單道程序存儲(chǔ)管理內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。

每次把一個(gè)應(yīng)用程序裝入到用戶區(qū)運(yùn)行，

由它和操作系統(tǒng)來共享內(nèi)存。當(dāng)它運(yùn)行

結(jié)束后，操作系統(tǒng)再裝入一個(gè)新的程序

把它覆蓋；優(yōu)點(diǎn)：簡(jiǎn)單、開銷小，易于管理；適合于單用戶、單任務(wù)的OS。7BIOS（本圖摘自AndrewS.Tanenbaum：“ModernOperatingSystems”）三種實(shí)現(xiàn)方式單道程序存儲(chǔ)管理的缺點(diǎn)？？8每次只能運(yùn)行一個(gè)程序內(nèi)存資源的使用效率不高程序較小時(shí)，會(huì)浪費(fèi)大量的內(nèi)存空間OS的保護(hù)應(yīng)用程序的bug會(huì)破壞OS地址空間有限即為物理內(nèi)存的大小9如何實(shí)現(xiàn)多道存儲(chǔ)管理，即在內(nèi)存中同時(shí)有多個(gè)進(jìn)程運(yùn)行，有哪些問題需要考慮？10內(nèi)存空間的管理整個(gè)內(nèi)存區(qū)域如何劃分？用什么數(shù)據(jù)結(jié)構(gòu)來管理內(nèi)存？如何在有限的內(nèi)存空間中容納盡可能多的進(jìn)程？?jī)?nèi)存的分配新進(jìn)程到達(dá)時(shí)，如何給它分配內(nèi)存？?jī)?nèi)存的回收進(jìn)程運(yùn)行結(jié)束時(shí)，如何回收其內(nèi)存？11地址重定位程序員不知道當(dāng)他的程序被執(zhí)行時(shí)，將會(huì)被放在內(nèi)存的什么位置；當(dāng)一個(gè)程序正在執(zhí)行時(shí)，可能被交換到磁盤上，后來再返回內(nèi)存時(shí)，可能存放在不同的位置；對(duì)內(nèi)存的訪問必須轉(zhuǎn)換為實(shí)際的物理內(nèi)存地址。12內(nèi)存保護(hù)一個(gè)進(jìn)程不能未經(jīng)許可去訪問其他進(jìn)程或OS的內(nèi)存地址；內(nèi)存共享允許多個(gè)進(jìn)程訪問相同的一段內(nèi)存空間；最好允許每個(gè)進(jìn)程訪問一個(gè)程序的同一份拷貝，而不是每個(gè)進(jìn)程都有自己獨(dú)立的一份拷貝。13邏輯組織程序的編寫是以模塊為單位；每個(gè)模塊的保護(hù)級(jí)別可能是不同的（只讀、只可執(zhí)行、可讀寫等）；模塊的共享。物理組織分配給一個(gè)程序（包括其數(shù)據(jù)）的內(nèi)存空間可能不夠用；磁盤存儲(chǔ)器更便宜、容量更大、且永久保存。14Now，如何實(shí)現(xiàn)多道存儲(chǔ)管理？?jī)?nèi)存的分配；內(nèi)存的回收；內(nèi)存的管理（數(shù)據(jù)結(jié)構(gòu)）。154.2分區(qū)存儲(chǔ)管理內(nèi)存分為兩大區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。

又把用戶區(qū)劃分為若干分區(qū)(partition)，

分區(qū)大小可以相等，也可以不等。一個(gè)

進(jìn)程占用一個(gè)分區(qū)。特點(diǎn)：適合于多道程序系統(tǒng)和分時(shí)系統(tǒng)，

支持多個(gè)程序并發(fā)執(zhí)行；164.2.1固定分區(qū)存儲(chǔ)管理各個(gè)用戶分區(qū)的個(gè)數(shù)、位置和大小一旦確定以后，就固定不變。為了滿足不同程序的存儲(chǔ)需要，各分區(qū)的大小可相等，也可不等。分區(qū)大小相等：只適合于多個(gè)相同程序的并發(fā)執(zhí)

行（處理多個(gè)類型相同的對(duì)象）；分區(qū)大小不等：多個(gè)小分區(qū)、適量的中等分區(qū)、

少量的大分區(qū)；當(dāng)進(jìn)程到來時(shí)，根據(jù)它的大小，把它放置到相應(yīng)

的輸入隊(duì)列當(dāng)中，等待合適的空閑分區(qū)。兩種實(shí)

現(xiàn)方式：多個(gè)輸入隊(duì)列和單個(gè)輸入隊(duì)列。17多個(gè)輸入隊(duì)列分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)700K400K100K0200K800K對(duì)于每一個(gè)用戶分區(qū)，都有一個(gè)輸入隊(duì)列。當(dāng)一個(gè)新的進(jìn)程到來時(shí)，把它加入到某個(gè)輸入隊(duì)

列當(dāng)中，該輸入隊(duì)列所對(duì)應(yīng)的分區(qū)，是能夠裝下該進(jìn)程的最小分區(qū)。缺點(diǎn)：可能出現(xiàn)小分區(qū)的輸入隊(duì)列是滿的，而大分區(qū)的輸入隊(duì)列卻空著（如分區(qū)1和分區(qū)3的的情形），從而造成資源的浪費(fèi)。180K…18單個(gè)輸入隊(duì)列分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)700K400K100K0200K800K對(duì)于所有的用戶分區(qū)，只有一個(gè)統(tǒng)一的輸入隊(duì)列。當(dāng)一個(gè)新進(jìn)程到來時(shí)，把它加入到該輸入隊(duì)列當(dāng)中，然后當(dāng)某個(gè)分區(qū)空閑時(shí)：離隊(duì)首最近的、

能裝入該分區(qū)的

進(jìn)程被選中；搜索整個(gè)隊(duì)列，

選擇能裝入該分

區(qū)的最大進(jìn)程。19如何實(shí)現(xiàn)固定分區(qū)存儲(chǔ)管理？

數(shù)據(jù)結(jié)構(gòu)、分配、回收。20固定分區(qū)的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)：設(shè)置內(nèi)存分配表內(nèi)存分配：先放入輸入隊(duì)列，然后采用

最先匹配法、最佳匹配法

等算法。內(nèi)存回收：簡(jiǎn)單分區(qū)號(hào)起始地址長度狀態(tài)進(jìn)程名21固定分區(qū)的缺點(diǎn)：內(nèi)存利用率不高，內(nèi)碎片造成很大浪費(fèi)。

所謂內(nèi)碎片，即進(jìn)程所占用分區(qū)之內(nèi)的未

被利用的空間（再小的進(jìn)程都要占用一整個(gè)分區(qū)）。分區(qū)的總數(shù)固定，限制了并發(fā)執(zhí)行的程序

個(gè)數(shù)，不夠靈活。進(jìn)程的保護(hù)（應(yīng)用程序可能破壞OS和其他應(yīng)用程序）固定分區(qū)的優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開銷小。22地址空間的大小有限：不能超過物理內(nèi)存的大小。如何提高內(nèi)存的利用效率？如何確定分區(qū)的大??？分區(qū)太小怎么辦？分區(qū)太大怎么辦（內(nèi)碎片）？為此，人們又提出了可變分區(qū)（動(dòng)態(tài)分區(qū)）的存儲(chǔ)管理技術(shù)。234.2.2可變分區(qū)存儲(chǔ)管理分區(qū)不是預(yù)先劃分好的固定區(qū)域，而是動(dòng)態(tài)創(chuàng)建的。在裝入一個(gè)程序時(shí)，根據(jù)它的需求和內(nèi)存空間的使用情況來決定是否分配。具體來說，系統(tǒng)生成后，操作系統(tǒng)會(huì)占用內(nèi)存的一部分（一般在內(nèi)存地址低端），其余空間為一個(gè)完整的大空閑區(qū)。當(dāng)一個(gè)程序要求裝入內(nèi)存運(yùn)行時(shí)，系統(tǒng)從這個(gè)空閑區(qū)中劃分一塊分配給它，當(dāng)程序完成后釋放所占用的存儲(chǔ)區(qū)。隨著一系列的內(nèi)存分配和回收，原來的一整塊大空閑區(qū)就形成了若干占用區(qū)和空閑區(qū)相間的布局。24操作系統(tǒng)128K01024K128K空閑區(qū)896K操作系統(tǒng)128K01024K128K空閑區(qū)576K進(jìn)程1320K448K25操作系統(tǒng)128K01024K128K空閑區(qū)352K進(jìn)程1320K448K進(jìn)程2224K672K操作系統(tǒng)128K01024K128K空閑區(qū)64K進(jìn)程1320K448K進(jìn)程2224K672K進(jìn)程3288K960K空閑區(qū)224K250K？26操作系統(tǒng)128K01024K128K空閑區(qū)64K進(jìn)程1320K448K進(jìn)程4128K672K進(jìn)程3288K960K576K空閑區(qū)96K空閑區(qū)320K可變分區(qū)的特點(diǎn)：在可變分區(qū)當(dāng)中，分區(qū)的個(gè)

數(shù)、位置和大小都是隨進(jìn)程

的進(jìn)出而動(dòng)態(tài)變化的，非常

靈活，避免了在固定分區(qū)中

因分區(qū)大小不當(dāng)所造成的內(nèi)

碎片，提高了內(nèi)存利用率。有外碎片，即各個(gè)占用分區(qū)

之間難以利用的空閑分區(qū)

（通常是小空閑分區(qū)）；使得內(nèi)存的分配、回收和管

理更為復(fù)雜。27如何實(shí)現(xiàn)可變分區(qū)的存儲(chǔ)管理技術(shù)？?jī)?nèi)存管理的數(shù)據(jù)結(jié)構(gòu)；內(nèi)存的分配算法內(nèi)存的回收方法碎片問題4.2.3可變分區(qū)的實(shí)現(xiàn)281.分區(qū)鏈表系統(tǒng)維護(hù)一個(gè)有序的分區(qū)鏈表，來跟蹤記錄每一個(gè)內(nèi)存分區(qū)的情況，包括該分區(qū)的狀態(tài)（已分配或空閑）

起始地址、長度等信息。ABCDE058141820262932占05空53占86占144空182占206占263空293X空閑起始長度占用292.分區(qū)分配算法分區(qū)分配算法：當(dāng)一個(gè)新的進(jìn)程來到時(shí)，需為它尋找某個(gè)空閑分區(qū)，其大小必須大于或等于該進(jìn)程的要求。若是大于要求，則將該分區(qū)分割成兩個(gè)分區(qū)，其中一個(gè)分區(qū)為要求的大小并標(biāo)記為“占用”，而另一個(gè)分區(qū)為余下部分并標(biāo)記為“空閑”。分區(qū)的先后次序通常是從內(nèi)存低端到高端。分區(qū)分配算法主要有：最先匹配法、下次匹配法、最佳匹配法、最壞匹配法。30最先匹配法

(first-fit)：假設(shè)新進(jìn)程對(duì)內(nèi)存大小的要求為M，那么從分區(qū)鏈表的首結(jié)點(diǎn)開始，將每一個(gè)“空閑”結(jié)點(diǎn)的長度與M進(jìn)行比較，看是否大于或等于它，直到找到第一個(gè)符合要求的結(jié)點(diǎn)。然后把它所對(duì)應(yīng)的空閑分區(qū)分割為二個(gè)小分區(qū)，一個(gè)用于裝入該進(jìn)程，另一個(gè)仍然空閑。與之相對(duì)應(yīng)，把該結(jié)點(diǎn)也一分為二，并修改相應(yīng)內(nèi)容。查找的結(jié)點(diǎn)很少，因而速度快；算法的實(shí)質(zhì)是盡可能利用低地址部分的空閑區(qū)，而盡量地保證高地址部分的大空閑區(qū)，使其不被分割成小的區(qū)，這樣當(dāng)以后有大的進(jìn)程到來時(shí)，有足夠大的空閑區(qū)來滿足它。31下次匹配法

(next-fit)：與最先匹配法的思路是相似的，只不過每一次當(dāng)它找到一個(gè)合適的結(jié)點(diǎn)（分區(qū)）時(shí)，就把當(dāng)前的位置記錄下來。然后等下一次新進(jìn)程到來的時(shí)候，就從這個(gè)位置開始繼續(xù)往下找（到鏈表結(jié)尾時(shí)再回到開頭），直到找到符合要求的第一個(gè)分區(qū)。而不是象最先匹配法那樣，每次都是從鏈表的首結(jié)點(diǎn)開始找。查找的結(jié)點(diǎn)很少，因而速度快；該算法使空閑分區(qū)分布得更均勻，但較大的空閑分區(qū)不易保留。從性能上略遜于最先匹配法。32最佳匹配法

(best-fit)：將申請(qǐng)內(nèi)存的進(jìn)程裝入到與其大小最接近的空閑分區(qū)當(dāng)中。算法的性能最差，最大缺點(diǎn)是分割后剩余的空閑分區(qū)將會(huì)很小，直至無法使用，從而造成浪費(fèi)（與固定分區(qū)是不同的）。最壞匹配法(worst-fit)：每次分配時(shí)，總是將最大的空閑區(qū)切去一部分分配給請(qǐng)求者，其依據(jù)是當(dāng)一個(gè)很大的空閑區(qū)被切割了一部分后可能仍是一個(gè)較大的空閑區(qū)，從而避免了空閑區(qū)越分越小的問題。這種算法基本不留下小的空閑分區(qū)，但較大的空閑分區(qū)也不被保留。3316K16K16KWorstFit地址低端地址高端16K新進(jìn)程343.分區(qū)回收算法分區(qū)回收算法：當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束，釋放它所占用的分區(qū)后，需要將相鄰的幾個(gè)空閑分區(qū)合并為一個(gè)大的空閑分區(qū)。具體來說，可分以下四種情況：在分區(qū)回收后，可以很方便地更新分區(qū)鏈表。35占05占53占86(a)進(jìn)程A進(jìn)程X進(jìn)程B空空閑區(qū)50占35占68空(b)進(jìn)程A進(jìn)程X空閑區(qū)50占95空進(jìn)程A空閑區(qū)50空35占68空(d)空閑區(qū)進(jìn)程X空閑區(qū)140空空閑區(qū)(c)略…364.碎片問題經(jīng)過一段時(shí)間的分配與回收后，內(nèi)存中存在著很多

不連續(xù)的很小的空閑分區(qū)（外碎片）。當(dāng)一個(gè)新進(jìn)

程到來時(shí)，這些小的空閑區(qū)都不足以滿足分配要求，

但其總和滿足分配要求。這就是（外）碎片問題。內(nèi)存緊縮（Compaction）：把所有的進(jìn)程盡可能

地往地址低端移動(dòng)，相應(yīng)的，那些空閑的小分區(qū)就

會(huì)往地址的高端移動(dòng)，從而形成一個(gè)大的空閑區(qū)。所有進(jìn)程的移動(dòng)需要大量的CPU時(shí)間；如何解決程序移動(dòng)后，地址的重定位問題？374.2.5內(nèi)存中的程序執(zhí)行進(jìn)程執(zhí)行時(shí)的內(nèi)存分區(qū)布局棧動(dòng)態(tài)堆空間(malloc)數(shù)據(jù)代碼低地址高地址PCSP38變量的存儲(chǔ)與作用域/*全局變量，固定地址，其他源文件可見*/intglobal_static;/*靜態(tài)全局變量，固定地址，但只在本文件中可見*/staticintfile_static;/*函數(shù)參數(shù)：位于棧幀當(dāng)中，動(dòng)態(tài)創(chuàng)建，動(dòng)態(tài)釋放*/intfoo(intauto_param) //代碼{/*靜態(tài)局部變量，固定地址，只在本函數(shù)中可見*/staticintfunc_static;/*普通局部變量，位于棧幀當(dāng)中，只在本函數(shù)可見*/intauto_i,auto_a[10];/*動(dòng)態(tài)申請(qǐng)的內(nèi)存空間，位于堆當(dāng)中*/double*auto_d=malloc(sizeof(double)*5);returnauto_i;}394.2.5重定位和存儲(chǔ)保護(hù)1.地址映射（重定位）1）物理地址也叫內(nèi)存地址、絕對(duì)地址，實(shí)地址；把內(nèi)存分成很多個(gè)大小相等的存儲(chǔ)單元，每個(gè)

單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱為物理地址；物理地址可以直接尋址；物理地址的集合稱為物理地址空間（內(nèi)存地址

空間），它是一個(gè)一維的線性空間。402）邏輯地址也叫相對(duì)地址，虛地址；用戶程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目

標(biāo)代碼通常采用相對(duì)地址的形式，其首地址為

0，其余指令中的地址都是相對(duì)首地址來編址；不能用邏輯地址在內(nèi)存中讀取信息。3）地址映射為了保證CPU執(zhí)行指令時(shí)可正確訪問存儲(chǔ)單元，

需要將用戶程序中的邏輯地址轉(zhuǎn)換為運(yùn)行時(shí)由

機(jī)器直接尋址的物理地址，這一過程稱為地址

映射。41intx,y;x=5;y=x+3;源程序編譯鏈接裝入分區(qū)0100200300......str5,[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]邏輯地址空間204xy1000......110012001300物理地址空間str5,[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]1204xy有無問題？42為了保證CPU執(zhí)行指令時(shí)可正確訪問存儲(chǔ)單元，在裝入程序時(shí)必須進(jìn)行地址映射，將程序中的邏輯地址轉(zhuǎn)換為物理地址。這主要有兩種方式：靜態(tài)地址映射（靜態(tài)重定位）：當(dāng)用戶程序

被裝入內(nèi)存時(shí)，直接對(duì)指令代碼進(jìn)行修改，

一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以

后不再轉(zhuǎn)換。在可執(zhí)行文件中，需列出各個(gè)需要重定位

的地址單元的位置。在裝入時(shí)，由一個(gè)裝

入程序（加載程序）來完成；實(shí)現(xiàn)簡(jiǎn)單，不需要硬件的支持；程序裝入內(nèi)存后不能移動(dòng)。43裝入分區(qū)0100200300......str5,[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]邏輯地址空間204xy1000......110012001300物理地址空間str5,[1200]

ldrR1,[1200]

addR2,R1,3

strR2,[1204]1204xy44動(dòng)態(tài)地址映射（動(dòng)態(tài)重定位）：當(dāng)用戶程序被裝

入內(nèi)存時(shí)，不對(duì)指令代碼做任何修改。而是在程

序運(yùn)行過程中，當(dāng)需要訪問內(nèi)存單元時(shí)再來進(jìn)行

地址轉(zhuǎn)換（即在逐條執(zhí)行指令時(shí)完成轉(zhuǎn)換）。為提高效率，此工作一般由硬件地址映射機(jī)

制來完成，通常的做法是設(shè)置一個(gè)基地址寄

存器（重定位寄存器），并把進(jìn)程所在分區(qū)的起始地址裝入到該寄存器當(dāng)中；在程序運(yùn)行過程中，當(dāng)需要訪問內(nèi)存單元時(shí),硬件就自動(dòng)地將其中的相對(duì)地址加上基地址

寄存器的內(nèi)容，形成實(shí)際的物理地址，然后按該地址去執(zhí)行。45裝入分區(qū)0100200300......str5,[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]邏輯地址空間204xy1000......110012001300物理地址空間str5,[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]1204xy+基地址寄存器相對(duì)地址10002001.基地址寄存器

在哪？2.何時(shí)填入1000？46為了防止一個(gè)用戶程序去訪問其他用戶程序的內(nèi)存分區(qū)，保護(hù)操作系統(tǒng)免受用戶程序的破壞，須進(jìn)行存儲(chǔ)保護(hù)。如何實(shí)現(xiàn)？能否與動(dòng)態(tài)地址映射集成在一起？2.存儲(chǔ)保護(hù)47最簡(jiǎn)單的做法：在基地址寄存器的基礎(chǔ)上，再增加一個(gè)限長寄存器，記錄分區(qū)的長度。這兩者在一起，就定義了進(jìn)程所在的分區(qū)（寄存器的值存放在哪？）進(jìn)程B進(jìn)程A操作系統(tǒng)100K100K基地址寄存器限長寄存器邏輯地址必須

小于限長寄存

器的值。硬件

保護(hù)這兩個(gè)寄

存器，用戶程

序不能修改。0100K200K300K48CPUMMU內(nèi)存磁盤控制器總線CPU組件存儲(chǔ)管

理單元CPU發(fā)送邏輯地址給MMUMMU發(fā)送物理地址給內(nèi)存動(dòng)態(tài)地址映射494.3頁式和段式存儲(chǔ)管理頁式存儲(chǔ)管理段式存儲(chǔ)管理頁式管理與段式管理的比較段頁式存儲(chǔ)管理504.3.1頁式存儲(chǔ)管理分區(qū)存儲(chǔ)管理方案的一個(gè)特性是連續(xù)性，這將會(huì)導(dǎo)致碎片問題（內(nèi)碎片和外碎片）。為有效地解決這些問題，人們又提出了頁式存儲(chǔ)管理方案，其基本出發(fā)點(diǎn)是打破存儲(chǔ)分配的連續(xù)性，使得一個(gè)程序的邏輯地址空間可以分布在若干個(gè)離散的內(nèi)存塊上，從而達(dá)到充分利用內(nèi)存，提高內(nèi)存利用率的目的。511.基本原理把物理內(nèi)存劃分為許多個(gè)固定大小的內(nèi)存塊，稱

為物理頁面，或頁框（pageframe）；把邏輯地址空間劃分為大小相同的塊，稱為邏輯

頁面，或簡(jiǎn)稱頁面（page）；頁面大小為2n，一般在512字節(jié)到8K字節(jié)之間；當(dāng)一個(gè)用戶程序裝入內(nèi)存時(shí)，以頁面為單位進(jìn)行分配。若要運(yùn)行一個(gè)大小為n個(gè)頁面的程序，需要有n個(gè)空閑的物理頁面把它裝入，這些頁面不必是連續(xù)的。生活中的例子…52進(jìn)程3第0頁進(jìn)程2第2頁進(jìn)程1第1頁進(jìn)程1第0頁進(jìn)程2第1頁進(jìn)程2第0頁操作系統(tǒng)操作系統(tǒng)0K1K2K3K4K5K6K7K8K9K10K0K1K2K進(jìn)程1地址空間進(jìn)程2地址空間0K1K2K3K0K1K進(jìn)程3地址空間內(nèi)存53用于存儲(chǔ)管理的數(shù)據(jù)結(jié)構(gòu)是什么？當(dāng)一個(gè)進(jìn)程到來時(shí)，如何給它分配內(nèi)存？當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束，釋放它所占用的內(nèi)存空間后，如何回收內(nèi)存？當(dāng)一個(gè)進(jìn)程被加載到內(nèi)存以后，它如何正確運(yùn)行（地址重定位）？頁式存儲(chǔ)管理要解決如下問題：542.數(shù)據(jù)結(jié)構(gòu)頁表：系統(tǒng)為每一個(gè)進(jìn)程都建立了一個(gè)頁表，頁表給出了邏輯頁面號(hào)和具體內(nèi)存塊號(hào)（物理頁面號(hào)）之間的對(duì)應(yīng)關(guān)系。邏輯頁號(hào)內(nèi)存塊號(hào)頁表01n-1如何實(shí)現(xiàn)頁表？55（本圖摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）

邏輯

地址空間頁表物理內(nèi)存物理頁面號(hào)56物理頁面表：在系統(tǒng)中設(shè)立一張物理頁面表，用來描述內(nèi)存空間當(dāng)中，各個(gè)物理頁面的分配使用狀況。具體實(shí)現(xiàn)：位示圖，空閑頁面鏈表。0310/10/10/10/10/1017……空閑頁數(shù)……位示圖內(nèi)存中共有

256個(gè)物理

頁面，可以

用字長為32

位的8個(gè)字

來構(gòu)成位示

圖。573.內(nèi)存的分配與回收內(nèi)存的分配與回收算法與物理頁面表的具體實(shí)現(xiàn)方法有關(guān)。這里以位示圖為例。內(nèi)存的分配：計(jì)算一個(gè)進(jìn)程所需要的頁面數(shù)N，并查看位示圖，看是否還有N個(gè)空閑頁面；若有，則申請(qǐng)一個(gè)頁表，其長度為N，并把頁表的起始地址填入PCB；分配N個(gè)空閑的物理頁面，將其編號(hào)填入頁表；修改位示圖（0→1，空閑頁面數(shù)－N）58內(nèi)存的回收：當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束，釋放它所占用的內(nèi)存空間后，需要對(duì)這些物理頁面進(jìn)行回收。對(duì)于每一個(gè)物理頁面，根據(jù)它的編號(hào)計(jì)算出它在位示圖當(dāng)中的相應(yīng)位置，并將相應(yīng)位的值從1改成0；修改位示圖中的空閑頁面數(shù)：加上N。594.地址映射為什么要進(jìn)行地址映射？一個(gè)進(jìn)程的各個(gè)連續(xù)的邏輯頁面，被分散地

裝入到內(nèi)存的各個(gè)物理頁面當(dāng)中，在這種情

形下，怎樣才能保證程序能夠正確地運(yùn)行？能否采用靜態(tài)地址映射方法？能否采用動(dòng)態(tài)地址映射方法？如何實(shí)現(xiàn)？60對(duì)于給定的邏輯地址，找到邏輯頁面號(hào)和頁內(nèi)偏移地址；查找頁表，找到相應(yīng)的物理頁面號(hào)；計(jì)算最終的物理地址。61邏輯地址的劃分把邏輯地址劃分為兩部分：邏輯頁面號(hào)和頁內(nèi)偏移地址。這種劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶是透明的。由于頁面的大小一般為2的整數(shù)次冪，因此，地址的高位部分即為頁號(hào)，低位部分即為頁內(nèi)偏移地址。例如，頁面大小為4KB。頁號(hào)頁內(nèi)地址62邏輯地址為十六進(jìn)制的形式63邏輯地址為十進(jìn)制的形式計(jì)算方法： 頁號(hào)＝虛地址/頁大小 位移量＝虛地址%頁大小例如：假設(shè)頁面大小為2KB，計(jì)算邏輯地址7145和3412的邏輯頁面號(hào)和頁內(nèi)偏移地址。頁號(hào)：3412/2048＝1頁內(nèi)偏移：3412%2048＝1364頁號(hào)：7145/2048＝3頁內(nèi)偏移：7145%2048＝1001Why?64頁表保存在內(nèi)存當(dāng)中（用戶/內(nèi)核空間?）;設(shè)置一個(gè)頁表基地址寄存器（tablebaseregister，PTBR），用來指向頁表的起始地址；設(shè)置一個(gè)頁表長度寄存器（tablelengthregister，PTLR），用來指示頁表的大小。頁表的具體實(shí)現(xiàn)硬件寄存器位于什么地方？其內(nèi)容何時(shí)更新？誰更新？如何更新？65頁式地址映射疊加1.需訪問幾次內(nèi)存？2.頁表頁表？66頁式地址映射舉例頁號(hào)頁內(nèi)偏移量67在現(xiàn)有的方案中，每一次訪問內(nèi)存（數(shù)據(jù)/指令）時(shí)，都要做兩次訪問內(nèi)存的工作。這樣，降低了存取速度，將會(huì)影響整個(gè)系統(tǒng)的使用效率。為縮短頁表的查找時(shí)間，可以采用一種特殊的快速查找硬件：TLB(TranslationLookasideBuffer)或稱associativememory,用來存放那些最常用的頁表項(xiàng)。如何加快頁表的查詢速度？68帶有TLB的頁式地址映射（本圖摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）先后為什么管用？695.優(yōu)缺點(diǎn)優(yōu)點(diǎn)：沒有外碎片，內(nèi)碎片的大小不超過頁面的大小；一個(gè)程序不必連續(xù)存放；便于管理；缺點(diǎn)：程序必須全部裝入內(nèi)存；系統(tǒng)必須為每個(gè)進(jìn)程維護(hù)一張頁表。704.3.2段式存儲(chǔ)管理 Why段式存儲(chǔ)管理？頁式存儲(chǔ)管理（和分區(qū)存儲(chǔ)管理）只有一個(gè)邏輯地址空間，即一維的線性連續(xù)空間，從0到某個(gè)最大的邏輯地址。但是從程序員或系統(tǒng)管理的角度來說，一個(gè)程序是由一組模塊（片段）所組成的，每個(gè)片段是一個(gè)邏輯單元，如：主程序、全局變量、棧、庫函數(shù)等。71存儲(chǔ)保護(hù)：代碼段：一條條指令組成，只讀，可執(zhí)行，無需寫回磁盤；數(shù)據(jù)段：全局變量，可修改，可讀寫，需寫回磁盤；棧：行參、局部變量、CPU寄存器、返回地址，可讀寫，是否可執(zhí)行？存儲(chǔ)共享：在多個(gè)進(jìn)程之間，共享代碼和數(shù)據(jù)。721.基本原理對(duì)于程序當(dāng)中的每一個(gè)邏輯單元，設(shè)立一個(gè)完全獨(dú)立的地址空間，稱為“段”。在每個(gè)段的內(nèi)部，是一維的線性連續(xù)地址，從0一直到某個(gè)最大的地址。每個(gè)段的大小一般是不相等的，它所包含的內(nèi)容也是不一樣的；對(duì)于物理內(nèi)存來說，采用可變分區(qū)（動(dòng)態(tài)分區(qū)）的管理方法；當(dāng)一個(gè)程序需要裝入內(nèi)存時(shí)，以段為單位進(jìn)行分配，把每一個(gè)段裝入到一個(gè)內(nèi)存分區(qū)當(dāng)中，這些內(nèi)存分區(qū)不必是連續(xù)的。731423物理內(nèi)存空間用戶空間1324子函數(shù)主函數(shù)棧符號(hào)表0n742.具體實(shí)現(xiàn)在段式存儲(chǔ)管理中，用戶空間的地址為二元地址：(段號(hào)，段內(nèi)偏移)。實(shí)現(xiàn)方式：(1)地址高端為段號(hào)、低端為偏移；(2)指令中顯式地給出段號(hào)和段內(nèi)偏移。段表：系統(tǒng)為每一個(gè)進(jìn)程都建立了一個(gè)段表，它給出了進(jìn)程當(dāng)中的每一個(gè)段與它所對(duì)應(yīng)的內(nèi)存分區(qū)之間的映射關(guān)系。75所對(duì)應(yīng)內(nèi)存分區(qū)的起始地址段長度1400100063004004300400段號(hào)012段表比較頁表76段表的具體實(shí)現(xiàn)：段表保存在內(nèi)存當(dāng)中；設(shè)置一個(gè)段表基地址寄存器（Segment-tablebaseregister，STBR），用來指向內(nèi)存當(dāng)中段表的起始地址；設(shè)置一個(gè)段表長度寄存器（Segment-tablelengthregister，STLR），用來指示段表的大小，即程序當(dāng)中的段的個(gè)數(shù)；77段式地址映射PhysicalAddress與頁式地址映射的區(qū)別？78段式地址映射舉例79邏輯地址32位：16位段號(hào)＋16位段內(nèi)偏移;整數(shù)為32位；地址以16進(jìn)制描述。段式存儲(chǔ)管理舉例16位16位段號(hào) 段內(nèi)偏移80段基地址長度保護(hù)01000018C0只讀1119003FF只讀211D001FF讀－寫300禁止訪問411F001000讀－寫500禁止訪問600禁止訪問713000FFF讀－寫mainSin240pushX[10108]360mov4(sp),r2244callSin364pushr2248…366…488ret段表代碼段8182X在哪？（Sin函數(shù)的參數(shù)）棧指針的當(dāng)前地址是70FF0，物理地址是多少？第一條指令在哪？PushX指令：將SP減4，然后存儲(chǔ)X的值，那么X被存儲(chǔ)在什么地方？CallSin指令：(1)當(dāng)前PC值入棧；(2)在PC內(nèi)裝入目標(biāo)PC值。哪個(gè)值被壓入棧了？新的棧指針的值是多少？新的PC值是多少？“mov4+(sp),r2”的功能是什么？833.優(yōu)缺點(diǎn)優(yōu)點(diǎn)：程序通過分段來劃分多個(gè)模塊，每個(gè)模塊可以分別編寫和編譯，可以針對(duì)不同類型的段采取不同的保護(hù)，可以按段為單位來進(jìn)行共享；一個(gè)程序不必連續(xù)存放，沒有內(nèi)碎片。缺點(diǎn)：程序必須全部裝入內(nèi)存、外碎片等。84854.3.3頁式管理與段式管理的比較分頁與分段的出發(fā)點(diǎn)不同頁式：為減少碎片，提高內(nèi)存的使用效率，因此把內(nèi)存劃分為許多個(gè)固定大小的物理頁面。相應(yīng)的，把邏輯地址空間也劃分為大小相同的邏輯頁面；段式：為了實(shí)現(xiàn)程序當(dāng)中的各個(gè)邏輯單元的獨(dú)立性，便于它們的共享、保護(hù)和修改，從而為每一個(gè)邏輯單元設(shè)立一個(gè)單獨(dú)的“段”。相應(yīng)的，在物理內(nèi)存的分配和回收上，采用可變分區(qū)的存儲(chǔ)管理方法。86程序員對(duì)所采用的存儲(chǔ)管理技術(shù)的關(guān)注：頁式：對(duì)于程序員而言，頁式存儲(chǔ)管理完全是透明的，不必關(guān)心。對(duì)邏輯地址空間的分頁，是由系統(tǒng)自動(dòng)完成的。程序員甚至不知道分頁的發(fā)生。段式：程序員知道各個(gè)邏輯單元的存在，因此可以對(duì)它們進(jìn)行不同的處理。87從邏輯地址的表示來看：頁式：邏輯地址是一維的線性連續(xù)地址，各模塊在鏈接時(shí)必須組織成同一個(gè)地址空間；段式：邏輯地址是二維的，即段號(hào)和段內(nèi)的偏移地址，各個(gè)模塊在鏈接時(shí)可以為每個(gè)段組織一個(gè)地址空間。從退化形式來看：頁式：如果頁面比較大，能裝下整個(gè)程序，那么就退化為一種的方法；段式：如果段的個(gè)數(shù)為1，那么就退化為一種

的方法。固定分區(qū)可變分區(qū)884.3.4段頁式存儲(chǔ)管理段式存儲(chǔ)和頁式存儲(chǔ)各有特點(diǎn)：段式存儲(chǔ)管理為用戶提供了一個(gè)二維的邏輯地址空間，可以滿足程序和信息的邏輯分段要求，反映了程序的邏輯結(jié)構(gòu)，有利于段的共享、保護(hù)和動(dòng)態(tài)增長；頁式存儲(chǔ)管理的特征是等分內(nèi)存，它有效地克服了碎片問題，提高了內(nèi)存的利用率。為了保持頁式在存儲(chǔ)管理上的優(yōu)點(diǎn)和段式在邏輯上的優(yōu)點(diǎn)，人們又提出了段頁式存儲(chǔ)管理技術(shù)。89基本思想：先把程序劃分為段，然后在段內(nèi)分頁。邏輯地址：段號(hào)段內(nèi)地址頁號(hào)頁內(nèi)地址內(nèi)存劃分：按頁式存儲(chǔ)管理方案內(nèi)存分配：以頁面為單位進(jìn)行分配90具體實(shí)現(xiàn)：段表：記錄了每一段的頁表起始地址和頁表長度，而不是該段所在內(nèi)存分區(qū)的起始地址。頁表：記錄了邏輯頁面號(hào)與物理頁面號(hào)之間的對(duì)應(yīng)關(guān)系。（每一段有一個(gè)，一個(gè)程序可能有多個(gè)頁表）需要的硬件支持：段表基地址寄存器

（STBR）和段表長度寄存器（STLR）。91段頁式地址映射（本圖摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）覆蓋（overlay）和交換技術(shù)（swaping）分區(qū)存儲(chǔ)管理頁式段頁式段頁式都是將整個(gè)程序全部裝入內(nèi)存。這樣在多道程序的環(huán)境下可能出現(xiàn)內(nèi)存不夠用的情況。1.程序太大，超過了空閑的內(nèi)存容量，使用覆蓋技術(shù)。只需把需要的指令和數(shù)據(jù)保存在內(nèi)存，其他的在外存。2.若程序的個(gè)數(shù)太多，他們的總和超過了內(nèi)存容量，使用交換技術(shù)，把暫時(shí)不能執(zhí)行的程序送到外存。3.如果箱子啊有限容量的內(nèi)存裝入盡可能多的程序，而且每個(gè)程序又8K

E4K

F10K

C10K

B8K

D12K作業(yè)X的調(diào)用結(jié)構(gòu)作業(yè)X的常駐區(qū)

A（8K）覆蓋區(qū)0（10K）覆蓋區(qū)1（12K）BCDEF覆蓋技術(shù)（續(xù)1）

A請(qǐng)計(jì)算采用覆蓋技術(shù)后，作業(yè)X的運(yùn)行節(jié)省了多少內(nèi)存空間？覆蓋技術(shù)的缺點(diǎn)：1.需要程序員手工的把大程序劃分成功能模塊并確定其覆蓋關(guān)系，即哪些模塊存在調(diào)用關(guān)系。2.覆蓋模塊從外存裝入內(nèi)存，以時(shí)間延長來換取空間。交換技術(shù)如果有多個(gè)進(jìn)程并發(fā)運(yùn)行，可以將一些暫時(shí)不能運(yùn)行的進(jìn)程送到外存，從而使新進(jìn)程可以裝入。交換的單位是進(jìn)程的整個(gè)內(nèi)存空間。交換技術(shù)多用于多道程序系統(tǒng)或者分時(shí)系統(tǒng)，和分區(qū)存儲(chǔ)管理一起使用。交換技術(shù)的原理換出：把整個(gè)進(jìn)程的地址空間保存到外存的一個(gè)交換區(qū)。換入：將外存中某個(gè)進(jìn)程的地址空間讀入到內(nèi)存。交換技術(shù)的幾個(gè)問題交換時(shí)機(jī)：何時(shí)交換？?jī)?nèi)存不足，或有不足危險(xiǎn)。外存中交換區(qū)的大?。罕仨氉銐虼?，能存放所有用戶進(jìn)程的所有內(nèi)存影響的復(fù)制件。程序換入時(shí)的重定位：靜態(tài)地址映射必須放在原來的位置動(dòng)態(tài)地址映射無需。

覆蓋和交換技術(shù)的比較覆蓋只能發(fā)生在互相沒有調(diào)用關(guān)系的模塊之間。交換是以進(jìn)程為單位，無需用戶給出各個(gè)模塊之間的邏輯覆蓋結(jié)構(gòu)。即：交換發(fā)生在進(jìn)城之間，而覆蓋發(fā)生在同一個(gè)進(jìn)程內(nèi)部。虛擬存儲(chǔ)技術(shù)覆蓋和交換都是擴(kuò)充內(nèi)存的方法，但是都有缺點(diǎn)覆蓋：需將整個(gè)程序劃分模塊，并確定覆蓋關(guān)系。增加程序員的負(fù)擔(dān)。交換：以進(jìn)程為單位交換，需要把進(jìn)程的整個(gè)地址空間都換進(jìn)換出，增加了處理器的開銷，浪費(fèi)cpu時(shí)間。系統(tǒng)設(shè)計(jì)者不希望這種開銷。有沒有一種技術(shù)，即可解決程序員的煩惱，又解決系統(tǒng)設(shè)計(jì)者的煩惱。虛擬存儲(chǔ)技術(shù)。虛擬存儲(chǔ)技術(shù)像覆蓋技術(shù)那樣，把程序的一部分放入內(nèi)存，但它想做的更好，將這個(gè)過程由系統(tǒng)自動(dòng)完成。另一方面像交換技術(shù)那樣，實(shí)現(xiàn)進(jìn)程在內(nèi)存與外存間的交換，但是它想做的更好，部分而不是整個(gè)地址空間。1014.5虛擬存儲(chǔ)技術(shù)4.5.1程序的局部性原理局部性原理(principleoflocality)：程序在執(zhí)行過程中的一個(gè)較短時(shí)期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。表現(xiàn)為：時(shí)間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，一個(gè)數(shù)據(jù)的一次訪問和下次訪問都集中在一個(gè)較短時(shí)期內(nèi)；空間局部性：當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問的數(shù)據(jù)和鄰近的幾個(gè)數(shù)據(jù)都集中在一個(gè)較小區(qū)域內(nèi)。forexample…102局部性原理的具體表現(xiàn)：程序在執(zhí)行時(shí)，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)移和過程調(diào)用指令；程序中存在相當(dāng)多的循環(huán)結(jié)構(gòu)，它們由少量指令組成，而被多次執(zhí)行；程序中存在很多對(duì)一定數(shù)據(jù)結(jié)構(gòu)的操作，如數(shù)組操作，往往局限在較小范圍內(nèi)。103程序的局部性原理表明，從理論上來說，虛擬存儲(chǔ)技術(shù)是能夠?qū)崿F(xiàn)的，而且在實(shí)現(xiàn)了以后應(yīng)該是能夠取得一個(gè)滿意的效果的。成功案例：TLB、Cache。1044.5.2虛擬頁式存儲(chǔ)管理大部分虛擬存儲(chǔ)系統(tǒng)都采用虛擬頁式存儲(chǔ)管理技術(shù)，即在頁式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求調(diào)頁和頁面置換功能?；舅悸罚寒?dāng)一個(gè)用戶程序要調(diào)入內(nèi)存運(yùn)行時(shí)，不是將該程序的所有頁面都裝入內(nèi)存，而是只裝入部分的頁面（0個(gè)或多個(gè)），就可啟動(dòng)程序運(yùn)行。在運(yùn)行的過程中，如果發(fā)現(xiàn)要執(zhí)行的指令或要訪問數(shù)據(jù)不在內(nèi)存，則發(fā)出缺頁中斷請(qǐng)求，系統(tǒng)在處理這個(gè)中斷時(shí)，將外存中相應(yīng)的頁面調(diào)入內(nèi)存，使得該程序能繼續(xù)運(yùn)行。105當(dāng)內(nèi)存空間不夠用時(shí)，需要把頁面保存在磁盤上（backingstore，后備存儲(chǔ)）；內(nèi)存物理頁面稱為pageframe，磁盤上的頁面稱為后備頁面（backingframe）；目的：提供一種錯(cuò)覺，內(nèi)存的容量好像和磁盤容量一樣大，且速度和內(nèi)存一樣快（理想狀態(tài)）。106MMU磁盤邏輯地址空間物理地址空間107虛擬頁式管理需要解決以下問題：如何發(fā)現(xiàn)執(zhí)行的代碼或訪問的數(shù)據(jù)不在內(nèi)存；代碼或數(shù)據(jù)什么時(shí)候調(diào)入內(nèi)存，調(diào)入策略；當(dāng)一些頁調(diào)入內(nèi)存時(shí)，內(nèi)存沒有空閑內(nèi)存時(shí)，將淘汰哪些頁，淘汰策略。1081.頁表表項(xiàng)每個(gè)頁表項(xiàng)包含以下信息：邏輯頁號(hào)、物理頁號(hào)、駐留位、保護(hù)位、修改位、訪問位。物理頁號(hào)駐留位保護(hù)位修改位訪問位邏輯頁號(hào)i109駐留位（有效位）：表示該頁是在內(nèi)存還是在外存。如果該位等于1，表示該頁位于內(nèi)存當(dāng)中，即該頁表項(xiàng)是有效的，可以使用；如果該位等于0，表示該頁當(dāng)前還在外存當(dāng)中，如果訪問該頁表項(xiàng)，將導(dǎo)致缺頁中斷；保護(hù)位：表示允許對(duì)該頁做何種類型的訪問，如只讀、可讀寫、可執(zhí)行等；修改位：表明此頁在內(nèi)存中是否被修改過。當(dāng)系統(tǒng)回收該物理頁面時(shí)，根據(jù)此位來決定是否把它的內(nèi)容寫回外存；訪問位：如果該頁面被訪問過（包括讀操作或?qū)懖僮鳎?，則設(shè)置此位。用于頁面置換算法。110XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K邏輯地址空間物理地址空間物理頁面頁表16位的邏輯地址，邏輯地址空間64K。物理內(nèi)存只有

32K。頁面大小為4K。151413121110987654321076543210駐留位為0駐留位為1MOVREG,[0]MOVREG,[32780][32786]缺頁中斷1112.缺頁中斷在地址映射過程中，如果所要訪問的邏輯頁面p不在內(nèi)存，則產(chǎn)生缺頁中斷(pagefault)。中斷處理過程：如果在內(nèi)存中有空閑的物理頁面，則分配一頁，設(shè)為f，然后轉(zhuǎn)第4步；否則轉(zhuǎn)第2步；采用某種頁面置換算法，選擇一個(gè)將被替換的物理頁面f，它所對(duì)應(yīng)的邏輯頁面為p。如果該頁在內(nèi)存期間被修改過，則需把它寫回外存；對(duì)p所對(duì)應(yīng)的頁表項(xiàng)進(jìn)行修改，把駐留位置為0；將需要訪問的頁面p裝入到物理頁面f當(dāng)中（進(jìn)程被阻塞），并修改p所對(duì)應(yīng)的頁表項(xiàng)的內(nèi)容，把駐留位置為1，把物理頁面號(hào)設(shè)置為f；重新運(yùn)行被中斷的指令（PC不變）。112有空閑頁面嗎？分配一個(gè)空閑頁面修改相應(yīng)的頁表項(xiàng)重新運(yùn)行被中斷的指令有無否用置換算法選擇一頁把它寫回外存該頁被修改過？是缺頁中斷調(diào)入所需頁面缺頁中斷的流程圖113XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K11194501328K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K邏輯地址空間物理地址空間頁表151413121110987654321076543210MOVREG,[32780](32K+12)缺頁中斷置換算法選中物理頁面1把物理頁面1的內(nèi)容寫回外存調(diào)入所需頁面修改相應(yīng)頁表項(xiàng)的內(nèi)容8X1114用戶進(jìn)程感覺不到缺頁中斷的發(fā)生（就像進(jìn)程切換一樣）。addr1,r2,r3mov+(sp),(r2)faultallocpagereadfromdisksetmappingOSUsrprogramresume1154.5.3頁面置換算法功能：當(dāng)缺頁中斷發(fā)生，需要調(diào)入新的頁面而內(nèi)存已滿時(shí)，選擇內(nèi)存當(dāng)中哪個(gè)物理頁面被置換。目標(biāo)：盡可能地減少頁面的換進(jìn)換出次數(shù)（即缺頁中斷的次數(shù)）。具體來說，把未來不再使用的或短期內(nèi)較少使用的頁面換出。116最優(yōu)頁面置換算法(OPT,optimal)最近最久未使用算法(LRU,LeastRecentlyUsed)最不常用算法(LFU,LeastFrequentlyUsed)先進(jìn)先出算法(FIFO)時(shí)鐘頁面置換算法(Clock)1171.最優(yōu)頁面置換算法基本思路：當(dāng)一個(gè)缺頁中斷發(fā)生時(shí)，對(duì)于保存在內(nèi)存當(dāng)中的每一個(gè)邏輯頁面，計(jì)算在它的下一次訪問之前，還需等待多長時(shí)間，從中選擇等待時(shí)間最長的那個(gè)，作為被置換的頁面。這只是一種理想情況，在實(shí)際系統(tǒng)中是無法實(shí)現(xiàn)的，因?yàn)椴僮飨到y(tǒng)無從知道每一個(gè)頁面要等待多長時(shí)間以后才會(huì)再次被訪問?？捎米髌渌惴ǖ男阅茉u(píng)價(jià)的依據(jù)（在一個(gè)模擬器上運(yùn)行某個(gè)程序，并記錄每次的頁面訪問情況，在第二遍運(yùn)行時(shí)即可使用最優(yōu)算法）。118OPT123412512345頁0111111111114頁122222222222頁23333333333頁3444455555缺頁XXXXXX進(jìn)程總共有5個(gè)邏輯頁面，在它的運(yùn)行過程中，對(duì)邏輯頁面的訪問順序是：1,2,3,4,1,2,5,1,2,3,4,5。如果在內(nèi)存中給它分配4個(gè)物理頁面，則缺頁情況如下：12次訪問中有缺頁6次。541192.最近最久未使用算法最近最久未使用算法(LeastRecentlyUsed,LRU);基本思路：當(dāng)一個(gè)缺頁中斷發(fā)生時(shí)，選擇最近最久未使用的那個(gè)頁面，并淘汰之。它是對(duì)最優(yōu)頁面置換算法的一個(gè)近似，其依據(jù)是程序的局部性原理，即在最近一小段時(shí)間內(nèi)，如果某些頁面被頻繁地訪問，那么在將來的一小段時(shí)間內(nèi)，它們還可能會(huì)再一次被頻繁地訪問。反之，如果在過去某些頁面長時(shí)間未被訪問，那么在將來它們還可能會(huì)長時(shí)間地得不到訪問。120如何實(shí)現(xiàn)LRU算法？可能的實(shí)現(xiàn)方法是：系統(tǒng)維護(hù)一個(gè)頁面鏈表，最近剛剛使用過的頁面作為首結(jié)點(diǎn)，最久未使用的頁面作為尾結(jié)點(diǎn)。每一次訪問內(nèi)存時(shí)，找到相應(yīng)的頁面，把它從鏈表中摘下來，再移動(dòng)到鏈表之首。每次缺頁中斷發(fā)生時(shí)，淘汰鏈表末尾的頁面。設(shè)置一個(gè)活動(dòng)頁面棧，當(dāng)訪問某頁時(shí)，將此頁號(hào)壓入棧頂，然后，考察棧內(nèi)是否有與此頁面相同的頁號(hào)，若有則抽出。當(dāng)需要淘汰一個(gè)頁面時(shí)，總是選擇棧底的頁面，它就是最久未使用的。在每次內(nèi)存訪問時(shí)，給相應(yīng)頁面打上時(shí)間戳，然后在缺頁中斷時(shí)，選擇最老的頁面淘汰出去。121LRU123412512345缺頁鏈?zhǔn)?X鏈?zhǔn)譞21鏈尾鏈?zhǔn)譞312X312鏈?zhǔn)?4231X2415134254211452X2513X3124X4235進(jìn)程總共有5個(gè)邏輯頁面，在它的運(yùn)行過程中，對(duì)邏輯頁面的訪問順序是：1,2,3,4,1,2,5,1,2,3,4,5。如果在內(nèi)存中給它分配4個(gè)物理頁面，則缺頁情況如下：12次訪問中有缺頁8次。1221,2,3,4,1,2,5,1,2,3,4,5111221233123442341134122412554251145122512331234423455123完美的LRU算法并不實(shí)用：在每次內(nèi)存訪問時(shí)，都需要去更新該頁面訪問時(shí)間（時(shí)間戳法）或調(diào)整各個(gè)頁面的先后順序（鏈表法和棧法），開銷很大；缺乏硬件支持?？尚械淖龇ǎ簩?duì)LRU算法的近似；在硬件的支持下，使用某種簡(jiǎn)單而快速的方法來尋找比較老（而非最老）的頁面。 1243.最不常用算法最不常用算法（LeastFrequentlyUsed,LFU）;基本思路：當(dāng)一個(gè)缺頁中斷發(fā)生時(shí)，選擇訪問次數(shù)最少的那個(gè)頁面，并淘汰之。實(shí)現(xiàn)方法：對(duì)每個(gè)頁面設(shè)置一個(gè)訪問計(jì)數(shù)器，每當(dāng)一個(gè)頁面被訪問時(shí)，該頁面的訪問計(jì)數(shù)器加1。在發(fā)生缺頁中斷時(shí)，淘汰計(jì)數(shù)值最小的那個(gè)頁面。LRU和LFU的區(qū)別：LRU考察的是多久未訪問,時(shí)間越短越好；而LFU考察的是訪問的次數(shù)或頻度，訪問次數(shù)越多越好。1254.先進(jìn)先出算法先進(jìn)先出算法（First-InFirst-Out,FIFO）；基本思路：選擇在內(nèi)存中駐留時(shí)間最長的頁面并淘汰之。具體來說，系統(tǒng)維護(hù)著一個(gè)鏈表，記錄了所有位于內(nèi)存當(dāng)中的邏輯頁面。從鏈表的排列順序來看，鏈?zhǔn)醉撁娴鸟v留時(shí)間最長，鏈尾頁面的駐留時(shí)間最短。當(dāng)發(fā)生一個(gè)缺頁中斷時(shí)，把鏈?zhǔn)醉撁嫣蕴鼍?，并把新的頁面添加到鏈表的末尾。性能較差，調(diào)出的頁面有可能是經(jīng)常要訪問的頁面，并且有Belady現(xiàn)象。126Belady現(xiàn)象：在采用FIFO算法時(shí)，有時(shí)會(huì)出現(xiàn)分配的物理頁面數(shù)增加，缺頁率反而提高的異?，F(xiàn)象；Belady現(xiàn)象的原因：FIFO算法的置換特征與置換算法的目標(biāo)是不一致的（即替換較少使用的頁面），因此，被它置換出去的頁面并不一定是進(jìn)程不會(huì)訪問的（如1,2,3,1,1,4）。127FIFO123412512345缺頁進(jìn)程總共有5個(gè)邏輯頁面，在它的運(yùn)行過程中，對(duì)邏輯頁面的訪問順序是：1,2,3,4,1,2,5,1,2,3,4,5。如果在內(nèi)存中給它分配3個(gè)物理頁面，則缺頁情況如下：12次訪問中有缺頁9次。鏈?zhǔn)?X鏈?zhǔn)譞12鏈尾鏈?zhǔn)譞132X243X314X421X152152152X235X543543128FIFO123412512345缺頁如果在內(nèi)存中給這個(gè)進(jìn)程分配4個(gè)物理頁面：鏈?zhǔn)?X鏈?zhǔn)譞12鏈尾鏈?zhǔn)譞132結(jié)論：在12次頁面訪問中，總共缺頁10次（Belady現(xiàn)象）。X243鏈?zhǔn)?2431X35422431X4153X5214X1325X2431X35421295.時(shí)鐘頁面置換算法時(shí)鐘頁面置換算法(Clock)；基本思路（FIFO+跳過訪問過的頁面）：需要用到頁表項(xiàng)當(dāng)中的訪問位。如果一個(gè)頁面被訪問（讀/寫），硬件自動(dòng)將其訪問位置為1，OS則負(fù)責(zé)定期清0；把各個(gè)頁面組織成環(huán)形鏈表（類似鐘表面），把指針指向最老的頁面（最先進(jìn)來）；當(dāng)發(fā)生一個(gè)缺頁中斷時(shí)，考察指針?biāo)赶虻淖罾享撁?，若它的訪問位為0，立即淘汰；若訪問位為1，則把該位置為0，然后指針往下移動(dòng)一格。如此下去，直到找到被淘汰的頁面，然后把指針移動(dòng)到它的下一格。130001100110001頁面訪問位頁面置換前000000110001頁面置換后M131什么時(shí)候LRU等價(jià)于FIFO，舉例？LRU的性能比較好，但是開銷大。FIFO開銷小但是性能差Clock比較折中，不像LRU那樣動(dòng)態(tài)調(diào)整順序，只是設(shè)置一個(gè)訪問位，所以開銷少，并且訪問位是硬件實(shí)現(xiàn)。LRU、FIFO和Clock的比較1324.5.4工作集模型前面介紹的各種頁面置換算法，都是基于一個(gè)前提,即程序的局部性原理。但是此原理是否成立？若局部性原理不成立，則各種頁面置換算法就沒有區(qū)別。例如：若進(jìn)程對(duì)邏輯頁面的訪問順序是1、2、3、4、5、6、7、8、9…，即單調(diào)遞增，則在物理頁面數(shù)有限的前提下，不管采用何種置換算法，每次的頁面訪問都必然導(dǎo)致缺頁中斷。如果局部性原理是成立的，那么如何來證明它的存在，如何來對(duì)它進(jìn)行定量地分析？133工作集：一個(gè)進(jìn)程當(dāng)前正在使用的邏輯頁面集合，可以用一個(gè)二元函數(shù)W(t,)來表示：t是當(dāng)前的執(zhí)行時(shí)刻；稱為工作集窗口（working-setwindow），即一個(gè)定長的頁面訪問窗口；W(t,)＝在當(dāng)前時(shí)刻t之前的窗口當(dāng)中的所有頁面所組成的集合（隨著t的變化，該集合也在不斷地變化）；|W(t,)|指工作集的大小，即頁面數(shù)目。1.工作集134261577775162341234443434441327

如果窗口的長度為10，那么：

W(t1,)={1,2,5,6,7}W(t2,)={3,4}一個(gè)例子頁面訪問順序：t1t2135工作集大小的變化：進(jìn)程開始執(zhí)行后，隨著訪問新頁面逐步建立較穩(wěn)定的工作集。當(dāng)內(nèi)存訪問的局部性區(qū)域的位置大致穩(wěn)定時(shí)，工作集大小也大致穩(wěn)定；局部性區(qū)域的位置改變時(shí)，工作集快速擴(kuò)張和收縮過渡到下一個(gè)穩(wěn)定值。1362.駐留集駐留集是指在當(dāng)前時(shí)刻，進(jìn)程實(shí)際駐留在內(nèi)存當(dāng)中的頁面集合。工作集是進(jìn)程在運(yùn)行過程中固有的性質(zhì)，而駐留集取決于系統(tǒng)分配給進(jìn)程的物理頁面數(shù)目，以及所采用的頁面置換算法；如果一個(gè)進(jìn)程的整個(gè)工作集都在內(nèi)存當(dāng)中，即駐留集工作集，那么進(jìn)程將很順利地運(yùn)行，而不會(huì)造成太多的缺頁中斷（直到工作集發(fā)生劇烈變動(dòng)，從而過渡到另一個(gè)狀態(tài)）；當(dāng)進(jìn)程駐留集的大小達(dá)到某個(gè)數(shù)目之后，再給它分配更多的物理頁面，缺頁率也不會(huì)明顯下降。1373.抖動(dòng)問題(thrashing)如果分配給一個(gè)進(jìn)程的物理頁面太少，不能包含整個(gè)工作集，即駐留集工作集，則進(jìn)程將會(huì)造成很多缺頁中斷，需要頻繁地在內(nèi)存與外存之間替換頁面，從而使進(jìn)程的運(yùn)行速度變得很慢，這種狀態(tài)稱為“抖動(dòng)”(進(jìn)程總被阻塞，I/O繁忙)。138例題： 請(qǐng)求分頁管理系統(tǒng)中，假設(shè)某進(jìn)程的頁表內(nèi)容如下表所示。頁號(hào)頁框(PageFrame)號(hào)有效位0101H11—02254H1139

頁面大小為4KB，一次內(nèi)存的訪問時(shí)間是100ns，一次快表（TLB）的訪問時(shí)間是10ns，處理一次缺頁的平均時(shí)間為108ns（已含更新TLB和頁表的時(shí)間），進(jìn)程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略。假設(shè)①TLB初始為空；②地址轉(zhuǎn)換時(shí)先訪問TLB，若TLB未命中，再訪問頁表（忽略訪問頁表之后的TLB更新時(shí)間）；③有效位為0表示頁面不在內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。140

設(shè)有虛地址訪問序列2362H、1565H、25A5H，請(qǐng)問：（1）依次訪問上述三個(gè)虛地址，各需多少時(shí)間？給出計(jì)算過程。（2）基于上述訪問序列，虛地址1565H的物理地址是多少？請(qǐng)說明理由。141（1）根據(jù)頁式管理的工作原理，應(yīng)先考慮頁面大小，以便將頁號(hào)和頁內(nèi)位移分解出來。頁面大小為4KB，即212，則得到頁內(nèi)位移占虛地址的低12位，頁號(hào)占剩余高位。可得三個(gè)虛地址的頁號(hào)P如下：1422362H：P=2，訪問快表10ns，因初始為空，訪問頁表100ns得到頁框號(hào)，合成物理地址后訪問主存100ns，共計(jì)10ns+100ns+100ns=210ns。1565H：P=1，訪問快表10ns，落空，訪問頁表100ns落空，進(jìn)行缺頁中斷處理108ns，合成物理地址后訪問主存100ns，10ns+100ns+108ns+10ns+100ns14325A5H：P=2，訪問快表，因第一次訪問已將該頁號(hào)放入快表，因此花費(fèi)10ns便可合成物理地址，訪問主存100ns，共計(jì)10ns+100ns=110ns。144（2）當(dāng)訪問虛地址1565H時(shí)，產(chǎn)生缺頁中斷，合法駐留集為2，必須從頁表中淘汰一個(gè)頁面，根據(jù)題目的置換算法，應(yīng)淘汰0號(hào)頁面，因此1565H的對(duì)應(yīng)頁框號(hào)為101H。由此可得1565H的物理地址為101565H。1454.5.5虛擬頁式的設(shè)計(jì)問題1.頁面的分配策略如何來確定駐留集的大?。抗潭ǚ峙渑c可變分配。固定分配策略：駐留集大小固定。例如：各進(jìn)程平均分配，或根據(jù)程序大小按比例分配等。采用局部頁面置換的方式，當(dāng)發(fā)生一個(gè)缺頁中斷時(shí)，被置換的頁面局限在本進(jìn)程內(nèi)部。缺點(diǎn)：分配的物理頁面數(shù)難以確定。進(jìn)程在運(yùn)行過程中，工作集的大小可能會(huì)不斷地變化，若分配的頁面數(shù)太少，則發(fā)生抖動(dòng)；若分配的頁面數(shù)太多，則浪費(fèi)內(nèi)存資源。146可變分配策略：駐留集大小可變。例如：每個(gè)進(jìn)程在剛開始運(yùn)行的時(shí)候，先根據(jù)程序大小給它分配一定數(shù)目的物理頁面，然后在進(jìn)程運(yùn)行過程中，再動(dòng)態(tài)地調(diào)整駐留集的大小?？刹捎萌猪撁嬷脫Q的方式，當(dāng)發(fā)生一個(gè)缺頁中斷時(shí)，被置換的頁面可以是在其它進(jìn)程當(dāng)中，各個(gè)并發(fā)進(jìn)程競(jìng)爭(zhēng)地使用物理頁面。優(yōu)缺點(diǎn)：性能較好，但增加了系統(tǒng)開銷。具體實(shí)現(xiàn)：可以使用缺頁率算法(PFF,pagefaultfrequency)來動(dòng)態(tài)調(diào)整駐留集的大小。147缺頁率缺頁率表示“缺頁次數(shù)/內(nèi)存訪問次數(shù)”(比率)或“缺頁的平均時(shí)間間隔的倒數(shù)”。影響缺頁率的因素：頁面置換算法分配給進(jìn)程的物理頁面數(shù)目頁面本身的大小程序的編制方法148若進(jìn)程的缺頁率過高，則分配更多的物理頁面；若進(jìn)

程的缺頁率過低，則減少它的物理頁面數(shù)，力圖使每

個(gè)進(jìn)程的缺頁率保持在一個(gè)合理的范圍內(nèi)。缺頁率算法149程序的編寫方法對(duì)缺頁率的影響：例子：頁面大小為4K，分配給每個(gè)進(jìn)程的物理頁面數(shù)為1。在一個(gè)進(jìn)程中，定義了如下的二維數(shù)組intA[1024][1024]，該數(shù)組按行存放在內(nèi)存，每一行放在一個(gè)頁面中。程序編制方法1：for(j=0;j<1024;j++)for(i=0;i<1024;i++)A[i][j]=0;程序編制方法2：for(i=0;i<1024;i++)for(j=0;j<1024;j++)A[i][j]=0;150a0,0a0,1a0,2……..a0,10231a1,0a1,1a1,2……..a1,10232…………….…………….a1023,0a1023,1

…..a1023,10231024訪問頁面的序列為：解法1：1，2，3，………1024，1，2，………，共1024組共發(fā)生了1024×1024次缺頁中斷解法2：1，1，1，………，2，2，………，3，3，…….共發(fā)生了1024次缺頁中斷1512.頁面大小頁面大小的選擇需要平衡各種相互競(jìng)爭(zhēng)