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

1第四章諶衛(wèi)軍清華大學(xué)操作系統(tǒng)2第四章存儲(chǔ)管理單道程序存儲(chǔ)管理分區(qū)存儲(chǔ)管理頁(yè)式和段式存儲(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)來(lái)共享內(nèi)存。當(dāng)它運(yùn)行

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

把它覆蓋；優(yōu)點(diǎn)：簡(jiǎn)單、開(kāi)銷小，易于管理；適合于單用戶、單任務(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)行，有哪些問(wèn)題需要考慮？10內(nèi)存空間的管理整個(gè)內(nèi)存區(qū)域如何劃分？用什么數(shù)據(jù)結(jié)構(gòu)來(lái)管理內(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í)，可能被交換到磁盤(pán)上，后來(lái)再返回內(nèi)存時(shí)，可能存放在不同的位置；對(duì)內(nèi)存的訪問(wèn)必須轉(zhuǎn)換為實(shí)際的物理內(nèi)存地址。12內(nèi)存保護(hù)一個(gè)進(jìn)程不能未經(jīng)許可去訪問(wèn)其他進(jìn)程或OS的內(nèi)存地址；內(nèi)存共享允許多個(gè)進(jìn)程訪問(wèn)相同的一段內(nèi)存空間；最好允許每個(gè)進(jìn)程訪問(wèn)一個(gè)程序的同一份拷貝，而不是每個(gè)進(jìn)程都有自己獨(dú)立的一份拷貝。13邏輯組織程序的編寫(xiě)是以模塊為單位；每個(gè)模塊的保護(hù)級(jí)別可能是不同的（只讀、只可執(zhí)行、可讀寫(xiě)等）；模塊的共享。物理組織分配給一個(gè)程序（包括其數(shù)據(jù)）的內(nèi)存空間可能不夠用；磁盤(pán)存儲(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)程到來(lái)時(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)程到來(lái)時(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)程到來(lái)時(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)起始地址長(zhǎng)度狀態(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)，開(kāi)銷小。22地址空間的大小有限：不能超過(guò)物理內(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)存空間的使用情況來(lái)決定是否分配。具體來(lái)說(shuō)，系統(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)存分配和回收，原來(lá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)存的回收方法碎片問(wèn)題4.2.3可變分區(qū)的實(shí)現(xiàn)281.分區(qū)鏈表系統(tǒng)維護(hù)一個(gè)有序的分區(qū)鏈表，來(lái)跟蹤記錄每一個(gè)內(nèi)存分區(qū)的情況，包括該分區(qū)的狀態(tài)（已分配或空閑）

起始地址、長(zhǎng)度等信息。ABCDE058141820262932占05空53占86占144空182占206占263空293X空閑起始長(zhǎng)度占用292.分區(qū)分配算法分區(qū)分配算法：當(dāng)一個(gè)新的進(jìn)程來(lái)到時(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)開(kāi)始，將每一個(gè)“空閑”結(jié)點(diǎn)的長(zhǎng)度與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)程到來(lái)時(shí)，有足夠大的空閑區(qū)來(lái)滿足它。31下次匹配法

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

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

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

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

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

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

會(huì)往地址的高端移動(dòng)，從而形成一個(gè)大的空閑區(qū)。所有進(jìn)程的移動(dòng)需要大量的CPU時(shí)間；如何解決程序移動(dòng)后，地址的重定位問(wèn)題？374.2.5內(nèi)存中的程序執(zhí)行進(jìn)程執(zhí)行時(shí)的內(nèi)存分區(qū)布局棧動(dòng)態(tài)堆空間(malloc)數(shù)據(jù)代碼低地址高地址PCSP38變量的存儲(chǔ)與作用域/*全局變量，固定地址，其他源文件可見(jiàn)*/intglobal_static;/*靜態(tài)全局變量，固定地址，但只在本文件中可見(jiàn)*/staticintfile_static;/*函數(shù)參數(shù)：位于棧幀當(dāng)中，動(dòng)態(tài)創(chuàng)建，動(dòng)態(tài)釋放*/intfoo(intauto_param) //代碼{/*靜態(tài)局部變量，固定地址，只在本函數(shù)中可見(jiàn)*/staticintfunc_static;/*普通局部變量，位于棧幀當(dāng)中，只在本函數(shù)可見(jiàn)*/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)過(guò)匯編或編譯后形成目標(biāo)代碼，目

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

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

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

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

映射。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有無(wú)問(wèn)題？42為了保證CPU執(zhí)行指令時(shí)可正確訪問(wèn)存儲(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è)裝

入程序（加載程序）來(lái)完成；實(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)行過(guò)程中，當(dāng)需要訪問(wèn)內(nèi)存單元時(shí)再來(lái)進(jìn)行

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

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

存器（重定位寄存器），并把進(jìn)程所在分區(qū)的起始地址裝入到該寄存器當(dāng)中；在程序運(yùn)行過(guò)程中，當(dāng)需要訪問(wèn)內(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è)用戶程序去訪問(wèn)其他用戶程序的內(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è)限長(zhǎng)寄存器，記錄分區(qū)的長(zhǎng)度。這兩者在一起，就定義了進(jìn)程所在的分區(qū)（寄存器的值存放在哪？）進(jìn)程B進(jìn)程A操作系統(tǒng)100K100K基地址寄存器限長(zhǎng)寄存器邏輯地址必須

小于限長(zhǎng)寄存

器的值。硬件

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

存器，用戶程

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

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

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

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

邏輯

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

256個(gè)物理

頁(yè)面，可以

用字長(zhǎng)為32

位的8個(gè)字

來(lái)構(gòu)成位示

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

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

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

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

（STBR）和段表長(zhǎng)度寄存器（STLR）。91段頁(yè)式地址映射（本圖摘自Silberschatz,GalvinandGagne：“OperatingSystemConcepts”）覆蓋（overlay）和交換技術(shù)（swaping）分區(qū)存儲(chǔ)管理頁(yè)式段頁(yè)式段頁(yè)式都是將整個(gè)程序全部裝入內(nèi)存。這樣在多道程序的環(huán)境下可能出現(xiàn)內(nèi)存不夠用的情況。1.程序太大，超過(guò)了空閑的內(nèi)存容量，使用覆蓋技術(shù)。只需把需要的指令和數(shù)據(jù)保存在內(nèi)存，其他的在外存。2.若程序的個(gè)數(shù)太多，他們的總和超過(guò)了內(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í)間延長(zhǎng)來(lái)?yè)Q取空間。交換技術(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ù)的原理?yè)Q出：把整個(gè)進(jìn)程的地址空間保存到外存的一個(gè)交換區(qū)。換入：將外存中某個(gè)進(jìn)程的地址空間讀入到內(nèi)存。交換技術(shù)的幾個(gè)問(wèn)題交換時(shí)機(jī)：何時(shí)交換？?jī)?nèi)存不足，或有不足危險(xiǎn)。外存中交換區(qū)的大?。罕仨氉銐虼?，能存放所有用戶進(jìn)程的所有內(nèi)存影響的復(fù)制件。程序換入時(shí)的重定位：靜態(tài)地址映射必須放在原來(lái)的位置動(dòng)態(tài)地址映射無(wú)需。

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

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

如果窗口的長(zhǎng)度為10，那么：

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

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

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

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

個(gè)進(jìn)程的缺頁(yè)率保持在一個(gè)合理的范圍內(nèi)。缺頁(yè)率算法149程序的編寫(xiě)方法對(duì)缺頁(yè)率的影響：例子：頁(yè)面大小為4K，分配給每個(gè)進(jìn)程的物理頁(yè)面數(shù)為1。在一個(gè)進(jìn)程中，定義了如下的二維數(shù)組intA[1024][1024]，該數(shù)組按行存放在內(nèi)存，每一行放在一個(gè)頁(yè)面中。程序編制方法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訪問(wèn)頁(yè)面的序列為：解法1：1，2，3，………1024，1，2，………，共1024組共發(fā)生了1024×1024次缺頁(yè)中斷解法2：1，1，1，………，2，2，………，3，3，…….共發(fā)生了1024次缺頁(yè)中斷1512.頁(yè)面大小頁(yè)面大小的選擇需要平衡各種相互競(jìng)爭(zhēng)