虛擬存儲(chǔ)管理

虛擬存儲(chǔ)管理引言

上一章介紹了實(shí)存儲(chǔ)管理技術(shù)，各種實(shí)存儲(chǔ)管理技術(shù)有一個(gè)共同的特點(diǎn)，即它們都要求把進(jìn)程全部裝入內(nèi)存才能運(yùn)行。在運(yùn)行過程中，往往可能出現(xiàn)兩種情況：要求運(yùn)行的進(jìn)程所需的內(nèi)存空間之和大于系統(tǒng)的內(nèi)存空間，只能有部分進(jìn)程能夠裝入內(nèi)存運(yùn)行，而其它進(jìn)程只有留在外存中等待；邏輯地址空間大于存儲(chǔ)空間的進(jìn)程無(wú)法在系統(tǒng)中運(yùn)行。為了解決以上問題，可有兩種解決方案：一是從物理上增加內(nèi)存容量。但這受到機(jī)器尋址能力的限制，不能無(wú)限擴(kuò)充，而且無(wú)疑會(huì)增加系統(tǒng)成本；二是從邏輯上擴(kuò)充內(nèi)存容量，這就是本章所要討論的“虛擬存儲(chǔ)”管理技術(shù)。第2頁(yè),共81頁(yè)，2024年2月25日，星期天8．1虛擬存儲(chǔ)器的基本概念

虛擬存儲(chǔ)管理要研究的問題是：

1.作業(yè)信息不全部裝入主存，能否保證作業(yè)的正確運(yùn)行？回答是肯定的,1968年P(guān).Denning研究了程序執(zhí)行時(shí)的局部性原理。

2.以CPU時(shí)間和外存空間換取昂貴內(nèi)存空間，如何進(jìn)行動(dòng)態(tài)調(diào)度？第3頁(yè),共81頁(yè)，2024年2月25日，星期天8．1虛擬存儲(chǔ)器的基本概念程序的局部性原理：

指程序在執(zhí)行過程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲(chǔ)區(qū)域中。具體地表現(xiàn)為時(shí)間局部性和空間局部性。第4頁(yè),共81頁(yè)，2024年2月25日，星期天8．1．1局部性原理

程序執(zhí)行呈現(xiàn)局部性規(guī)律的原因：程序執(zhí)行時(shí)，大多數(shù)情況下是順序執(zhí)行的。很少出現(xiàn)連續(xù)的過程調(diào)用，相反，程序中過程調(diào)用的深度限制在小范圍內(nèi)，一段時(shí)間內(nèi)，指令引用被局限在很少幾個(gè)過程中。程序中有許多循環(huán)語(yǔ)句，這些語(yǔ)句會(huì)重復(fù)多次執(zhí)行。程序中對(duì)數(shù)據(jù)結(jié)構(gòu)的操作，往往局限在很小的范圍內(nèi)。第5頁(yè),共81頁(yè)，2024年2月25日，星期天8．1．1局部性原理

局部性原理的表現(xiàn)形式：時(shí)間局限性：如果某條指令被執(zhí)行，則在不久的將來(lái)，該指令可能被再次執(zhí)行；如果某個(gè)數(shù)據(jù)結(jié)構(gòu)被訪問，則在不久的將來(lái)，該數(shù)據(jù)結(jié)構(gòu)可能再次被訪問。產(chǎn)生時(shí)間局限性的主要原因是程序中存在著大量的循環(huán)操作?？臻g局限性：一旦程序訪問了某個(gè)存儲(chǔ)單元，則在不久的將來(lái)，其附近的存儲(chǔ)單元也可能被訪問，即程序在一段時(shí)間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)。產(chǎn)生空間局限性的主要原因是程序的順序執(zhí)行。實(shí)現(xiàn)虛擬存儲(chǔ)器的理論基礎(chǔ)：局部性原理。第6頁(yè),共81頁(yè)，2024年2月25日，星期天8．1．2虛擬存儲(chǔ)器

實(shí)現(xiàn)方法：一個(gè)進(jìn)程在運(yùn)行之時(shí)，沒有必要全部裝入內(nèi)存，而只把當(dāng)前運(yùn)行所需要的頁(yè)（段）裝入內(nèi)存便可啟動(dòng)運(yùn)行，而其余部分則存放在磁盤上。程序在運(yùn)行時(shí)，如果所需要的頁(yè)（段）已經(jīng)調(diào)入內(nèi)存，便可以繼續(xù)執(zhí)行下去。如果所需要的頁(yè)（段）不在內(nèi)存，此時(shí)程序應(yīng)利用操作系統(tǒng)所提供的請(qǐng)求調(diào)頁(yè)（段）功能，將該頁(yè)（段）調(diào)入內(nèi)存，以使程序能夠運(yùn)行下去。如果此時(shí)分配給該程序的內(nèi)存已全部占用，不能裝入新的頁(yè)（段），則需要利用系統(tǒng)的置換功能，把內(nèi)存中暫時(shí)不用的頁(yè)（段）調(diào)出至磁盤上，騰出足夠的內(nèi)存空間，再將所要裝入的頁(yè)（段）調(diào)入內(nèi)存，使程序能夠繼續(xù)運(yùn)行下去。第7頁(yè),共81頁(yè)，2024年2月25日，星期天8．1．2虛擬存儲(chǔ)器

虛擬存儲(chǔ)器的定義：是指僅把進(jìn)程的一部分裝入內(nèi)存便可運(yùn)行的存儲(chǔ)器系統(tǒng)，它具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。虛擬存儲(chǔ)器的邏輯容量：虛擬存儲(chǔ)器的邏輯容量由系統(tǒng)的尋址能力和外存容量之和所決定。

第8頁(yè),共81頁(yè)，2024年2月25日，星期天8．1．2虛擬存儲(chǔ)器虛擬存儲(chǔ)管理主要采用以下技術(shù)實(shí)現(xiàn)：

?請(qǐng)求分頁(yè)虛擬存儲(chǔ)管理

?請(qǐng)求分段虛擬存儲(chǔ)管理

?請(qǐng)求段頁(yè)式虛擬存儲(chǔ)管理第9頁(yè),共81頁(yè)，2024年2月25日，星期天8．2請(qǐng)求分頁(yè)式存儲(chǔ)管理方式

請(qǐng)求分頁(yè)式存儲(chǔ)管理是在分頁(yè)式存儲(chǔ)管理的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能而形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。它是目前常用的一種虛擬存儲(chǔ)器的方式。第10頁(yè),共81頁(yè)，2024年2月25日，星期天8．2請(qǐng)求分頁(yè)式存儲(chǔ)管理方式基本原理：在請(qǐng)求分頁(yè)式存儲(chǔ)管理系統(tǒng)中，進(jìn)程運(yùn)行之前將一部分頁(yè)面裝入內(nèi)存，另外一部分頁(yè)面則裝入外存。在進(jìn)程運(yùn)行過程中，如果所訪問的頁(yè)面不在內(nèi)存中，則發(fā)生缺頁(yè)中斷，進(jìn)入操作系統(tǒng)，由操作系統(tǒng)進(jìn)行頁(yè)面的動(dòng)態(tài)調(diào)度。系統(tǒng)需要解決下面三個(gè)問題：系統(tǒng)如何獲知進(jìn)程當(dāng)前所需頁(yè)面不在主存。當(dāng)發(fā)現(xiàn)缺頁(yè)時(shí)，如何把所缺頁(yè)面調(diào)入主存。當(dāng)主存中沒有空閑的頁(yè)框時(shí)，為了要接受一個(gè)新頁(yè)，需要把老的一頁(yè)淘汰出去，根據(jù)什么策略選擇欲淘汰的頁(yè)面。第11頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．1請(qǐng)求分頁(yè)式存儲(chǔ)管理的基本概念

其方法如下：找到被訪問頁(yè)面在外存中的地址；在內(nèi)存中找一個(gè)空閑塊，如果沒有，則按照淘汰算法選擇一個(gè)內(nèi)存塊，將此塊內(nèi)容寫回外存，修改頁(yè)表；讀入所需的頁(yè)面，修改頁(yè)表；重新啟動(dòng)進(jìn)程，執(zhí)行被中斷的指令。

第12頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．1請(qǐng)求分頁(yè)式存儲(chǔ)管理的基本概念

頁(yè)表機(jī)制：純分頁(yè)的頁(yè)表只有兩項(xiàng)：頁(yè)號(hào)和物理塊。而請(qǐng)求分頁(yè)存儲(chǔ)管理增加了調(diào)入功能和置換功能，故需在頁(yè)表中增加若干項(xiàng)，供程序在換進(jìn)換出時(shí)參考。下面所示是一請(qǐng)求分頁(yè)系統(tǒng)中的頁(yè)表：頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問字段A修改位M外存地址狀態(tài)位P：記錄該頁(yè)是否在內(nèi)存。P=0該頁(yè)在內(nèi)存；

P=1該頁(yè)不在內(nèi)存。訪問字段A：記錄該頁(yè)多長(zhǎng)時(shí)間沒有被訪問。修改位M：記錄該頁(yè)在內(nèi)存期間是否被修改過。

M=1該頁(yè)調(diào)入內(nèi)存后被修改過；

M=0該頁(yè)調(diào)入內(nèi)存后未被修改過。外存地址：該頁(yè)在外存上的地址第13頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．1請(qǐng)求分頁(yè)式存儲(chǔ)管理的基本概念

請(qǐng)求分頁(yè)存儲(chǔ)管理示意圖：物理地址空間頁(yè)面映射表存儲(chǔ)空間頁(yè)號(hào)塊號(hào)狀態(tài)作業(yè)10110430001作業(yè)20123作業(yè)30123410610329011011103212700412345678910111213第14頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．1請(qǐng)求分頁(yè)式存儲(chǔ)管理的基本概念

地址變換機(jī)構(gòu)：請(qǐng)求分頁(yè)系統(tǒng)中的地址變換機(jī)構(gòu)，是在分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上，為實(shí)現(xiàn)虛擬存儲(chǔ)器而增加了產(chǎn)生和處理缺頁(yè)中斷、頁(yè)面置換等功能而形成的。下圖給出了請(qǐng)求分頁(yè)系統(tǒng)的地址變換過程。第15頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．1請(qǐng)求分頁(yè)式存儲(chǔ)管理的基本概念

否否否是是產(chǎn)生缺頁(yè)中斷否是否是程序請(qǐng)求訪問一頁(yè)頁(yè)號(hào)>頁(yè)表長(zhǎng)度？越界中斷CPU檢索快表頁(yè)表項(xiàng)是否在快表中？訪問頁(yè)表頁(yè)是否在內(nèi)存中？修改快表修改訪問位和修改位保留CPU現(xiàn)場(chǎng)缺頁(yè)中斷處理從外存中找到該頁(yè)內(nèi)存滿否？選擇一頁(yè)換出該頁(yè)修改否？將該頁(yè)寫回外存CPU從外存讀缺頁(yè)啟動(dòng)I/O硬件形成物理地址地址變換結(jié)束將一頁(yè)從外存換入內(nèi)存修改頁(yè)表是第16頁(yè),共81頁(yè)，2024年2月25日，星期天查快表有登記無(wú)登記查頁(yè)表登記入快表發(fā)缺頁(yè)中斷在主存在輔存形成絕對(duì)地址繼續(xù)執(zhí)行指令重新執(zhí)行被中斷指令恢復(fù)現(xiàn)場(chǎng)調(diào)整頁(yè)表和主存分配表裝入所需頁(yè)面主存有空閑塊保護(hù)現(xiàn)場(chǎng)有選擇調(diào)出頁(yè)面該頁(yè)是否修改未修改已修改把該頁(yè)寫回輔存相應(yīng)位置操作系統(tǒng)硬件邏輯地址無(wú)第17頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．2頁(yè)面分配策略

內(nèi)存頁(yè)面分配策略：平均分配：將內(nèi)存中的所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。這是最簡(jiǎn)單的分配方式，它看起來(lái)很公平，但實(shí)際上很不公平，因?yàn)樗鼪]有考慮進(jìn)程的大小等因素。按進(jìn)程大小比例分配：系統(tǒng)按進(jìn)程的大小按比例分配物理塊。若m為可用物理塊總和，S為各進(jìn)程頁(yè)面總和，si為第i個(gè)進(jìn)程的頁(yè)面數(shù)，則為第i個(gè)進(jìn)程分配的頁(yè)面數(shù)為：按進(jìn)程優(yōu)先級(jí)比例分配：為照顧重要的、緊迫的進(jìn)程，使其能夠盡快的完成，可以為其分配較多的內(nèi)存物理塊。

第18頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．2頁(yè)面分配策略

外存塊的分配策略：靜態(tài)分配：一個(gè)進(jìn)程在運(yùn)行前，將其所有頁(yè)面全部裝入外存。當(dāng)某一外存頁(yè)面被調(diào)入內(nèi)存時(shí)，所占用外存頁(yè)面并不釋放。這樣，當(dāng)該頁(yè)面以后被淘汰時(shí)，如果它在內(nèi)存中未被修改過，則不必寫回外存，因?yàn)橥獯嬷杏幸粋€(gè)和它完全相同的副本，這可以減少因頁(yè)面調(diào)度而引起的系統(tǒng)開銷，代價(jià)是犧牲一定的外存空間。動(dòng)態(tài)分配：一個(gè)進(jìn)程在運(yùn)行前，僅將未裝入內(nèi)存的那部分頁(yè)面裝入外存。當(dāng)某一外存頁(yè)面被調(diào)入內(nèi)存，釋放所占用的外存空間。這樣，當(dāng)該頁(yè)面以后被淘汰時(shí)，不管它在內(nèi)存中是否被修改過，都必須重新為其申請(qǐng)外存物理塊，將該頁(yè)重新寫回外存。這種方法的優(yōu)點(diǎn)是節(jié)省外存空間，但會(huì)增加由頁(yè)面調(diào)度而引起的系統(tǒng)開銷。第19頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．3頁(yè)面調(diào)入時(shí)機(jī)

請(qǐng)求調(diào)頁(yè)策略：發(fā)生缺頁(yè)時(shí)，調(diào)入內(nèi)存。根據(jù)局部性原理,一段時(shí)間后,缺頁(yè)中斷會(huì)下降到很低水平,程序進(jìn)入相對(duì)平穩(wěn)階段。

缺點(diǎn)：處理缺頁(yè)中斷和調(diào)頁(yè)的系統(tǒng)開銷較大，每次僅調(diào)一頁(yè),增加了磁盤I/O次數(shù)。預(yù)調(diào)頁(yè)策略：預(yù)計(jì)要訪問的頁(yè)，提前調(diào)入內(nèi)存。每次調(diào)入若干頁(yè)面,而不是僅調(diào)一頁(yè)。一次調(diào)入多頁(yè)能減少磁盤I/O啟動(dòng)次數(shù)。缺點(diǎn)：如果調(diào)入的一批頁(yè)面中多數(shù)未被使用,則效率就很低了，可見預(yù)調(diào)頁(yè)要建立在預(yù)測(cè)的基礎(chǔ)上第20頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法目標(biāo)：把未來(lái)不再使用的或短時(shí)間內(nèi)不再使用的頁(yè)調(diào)出。最佳置換算法OPT先進(jìn)先出置換算法FIFO最近最久未使用置換算法LRU時(shí)鐘置換算法第21頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

最佳置換算法（OPT，Optimal）：最佳置換算法置換那些以后永不再使用的或者在最長(zhǎng)的時(shí)間以后才會(huì)用到的頁(yè)面。顯然，這種算法的缺頁(yè)率最低。然而，該算法只是一種理論上的算法，因?yàn)楹茈y估計(jì)哪一個(gè)頁(yè)面是以后永遠(yuǎn)不再使用或在最長(zhǎng)時(shí)間以后才會(huì)用到的頁(yè)面，所以，這種算法是不能實(shí)現(xiàn)的。盡管如此，該算法仍然是有意義的，可以把它作為衡量其它算法優(yōu)劣的一個(gè)標(biāo)準(zhǔn)。第22頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

【例8-1】假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，頁(yè)面訪問序列為：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最佳置換算法，計(jì)算缺頁(yè)中斷次數(shù)和缺頁(yè)中斷率。解：頁(yè)面置換過程如下表所示：頁(yè)面訪問序列50120304230321201501501113333333322225555000004440000000000522222222221111111++++-+-+--+--+---+--缺頁(yè)中斷次數(shù)=9缺頁(yè)中斷率=9/20=45%

第23頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

先進(jìn)先出置換算法（FIFO，F(xiàn)irst-InFirst-Out）

：先進(jìn)先出置換算法總是置換最先進(jìn)入內(nèi)存的頁(yè)面。該算法實(shí)現(xiàn)簡(jiǎn)單，只須把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按照進(jìn)入內(nèi)存的先后順序排成一個(gè)隊(duì)列，當(dāng)一個(gè)頁(yè)面由外存調(diào)入內(nèi)存時(shí)排入隊(duì)尾，需要淘汰時(shí)取隊(duì)首的頁(yè)面。第24頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

【例8-2】假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，頁(yè)面訪問序列為：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用先進(jìn)先出置換算法，計(jì)算缺頁(yè)中斷次數(shù)和缺頁(yè)中斷率。解：頁(yè)面置換過程如下表所示：頁(yè)面訪問序列50120304230321201501501223042300012225015011230423330111250500123042223000125++++-++++++--++--+++缺頁(yè)中斷次數(shù)=15缺頁(yè)中斷率=15/20=75%

第25頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

Belady異?，F(xiàn)象：一般而言，分配給進(jìn)程的物理塊越多，運(yùn)行時(shí)的缺頁(yè)次數(shù)應(yīng)該越少。但是Belady在1969年發(fā)現(xiàn)了一個(gè)反例，使用FIFO算法時(shí)，四個(gè)物理塊時(shí)的缺頁(yè)次數(shù)比三個(gè)物理塊時(shí)的多，這種反常的現(xiàn)象稱為Belady異常。如下面兩表所示，一個(gè)進(jìn)程有5個(gè)頁(yè)面，頁(yè)面訪問序列如下：Belady異?，F(xiàn)象（3個(gè)物理塊的FIFO現(xiàn)象）

第26頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

Belady異?，F(xiàn)象（4個(gè)物理塊的FIFO現(xiàn)象）

由表中可見，3個(gè)物理塊時(shí)缺頁(yè)次數(shù)是9次，缺頁(yè)中斷率為9/12=75%；而4個(gè)物理塊時(shí)的缺頁(yè)次數(shù)是10次，缺頁(yè)中斷率為10/12≈83.3%。第27頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

最近最久未使用置換算法（LRU，LeastRecentlyUsed）：該算法的基本思想是：如果某一頁(yè)面被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁(yè)面很久沒有被訪問，那么最近也不會(huì)再次被訪問。因此，該算法為每一個(gè)頁(yè)面設(shè)置一個(gè)訪問字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問以來(lái)所經(jīng)歷的時(shí)間t，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中t值最大的，即最近最久未使用的頁(yè)面予以淘汰。LRU的實(shí)現(xiàn)：記時(shí)法：系統(tǒng)為每一頁(yè)面增設(shè)一個(gè)記時(shí)器。每當(dāng)一個(gè)頁(yè)面被訪問時(shí)，當(dāng)時(shí)的絕對(duì)時(shí)鐘內(nèi)容被拷貝到對(duì)應(yīng)的記時(shí)器中，這樣系統(tǒng)記錄了內(nèi)存所有頁(yè)面最后一次被訪問的時(shí)間。淘汰頁(yè)面時(shí)，選取記時(shí)器中值最小的頁(yè)面淘汰。第28頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

堆棧法：用一個(gè)棧保留頁(yè)號(hào)。每當(dāng)訪問一個(gè)頁(yè)面時(shí)，就把它從棧中取出放在棧頂上。這樣一來(lái)，棧頂總是放最新被訪問頁(yè)面的頁(yè)面號(hào)，而棧底放著最近最久未使用的頁(yè)面號(hào)。由于要從棧的中間移走一項(xiàng)，所以要用具有頭尾指針的雙向鏈連起來(lái)。注意：不是通常意義上的棧

第29頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

LRU的缺點(diǎn)：雖然LRU在理論上是可以實(shí)現(xiàn)的，但代價(jià)太高。為了實(shí)現(xiàn)LRU，需要在內(nèi)存維持一個(gè)包含所有頁(yè)的鏈表，最近使用的頁(yè)面在表頭，最近未使用的頁(yè)面在表尾。而每次訪問頁(yè)面時(shí)都需要對(duì)鏈表進(jìn)行更新。在鏈表中找到所需的頁(yè)，將它移動(dòng)到表頭是一個(gè)非常費(fèi)時(shí)的操作，即使使用硬件實(shí)現(xiàn)也是一樣。

第30頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

【例8-3】假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，頁(yè)面訪問序列為：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最近最久未使用置換算法，計(jì)算缺頁(yè)中斷次數(shù)和缺頁(yè)中斷率。解：頁(yè)面置換過程如下表所示：頁(yè)面訪問序列50120304230321201501501203042303212015015012030423032120150501223042203312015++++-+-++++--+-+-+--缺頁(yè)中斷次數(shù)=12缺頁(yè)中斷率=12/20=60%

第31頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

Clock置換算法（最近未使用算法

(NRU)）：最近最久未使用置換算法是一種比較合理的算法，但它經(jīng)常要在鏈表中移動(dòng)頁(yè)面，大大降低了系統(tǒng)效率。為了克服這個(gè)缺陷，把所有的頁(yè)面保存在一個(gè)類似時(shí)鐘表面的環(huán)形鏈表中，用一個(gè)表針指向可能淘汰的頁(yè)面，如下圖所示ABCDEFGHIJK設(shè)置一個(gè)訪問位:0表示最近未使用

1表示最近使用過第32頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

當(dāng)發(fā)生缺頁(yè)時(shí)，該算法首先檢查表針指向的頁(yè)面，如果其訪問位是0，則淘汰該頁(yè)，并把新的頁(yè)面插入到這個(gè)位置，然后把表針前移一個(gè)位置；如果訪問位是1則把其置0，暫不換出，并把表針前移一個(gè)位置，重復(fù)這個(gè)過程直到找到一個(gè)訪問位為0的頁(yè)為止。了解了這個(gè)算法的工作方式，我們就知道這種算法為什么被稱為Clock算法了。但因該算法只有一位訪問位，只能用它表示該頁(yè)是否使用過，而置換時(shí)將未使用過的頁(yè)面換出去，故又把該算法稱為最近未使用算法（NRU）。ABCDEFGHIJK第33頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法CLOCK算法執(zhí)行過程第34頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

改進(jìn)CLOCK置換算法事實(shí)上，時(shí)鐘算法不但希望淘汰最近未訪問的頁(yè)，而且還希望被挑選的頁(yè)在內(nèi)存駐留期間，其頁(yè)面內(nèi)的數(shù)據(jù)未被修改過。淘汰該頁(yè)時(shí)，由于該頁(yè)未被修改過，因此不必寫盤，從而減少了磁盤的I/O操作次數(shù)。為此，要為每頁(yè)增設(shè)兩個(gè)硬件位：訪問位和修改位：第35頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

訪問位A=0：該頁(yè)尚未被訪問過

=1：該頁(yè)已經(jīng)被訪問過修改位M=0：該頁(yè)尚未被修改過

=1：該頁(yè)已經(jīng)被修改過訪問位和修改位的組合有以下四種：1類（A=0，M=0）：表示該頁(yè)最近既未被訪問，又未被修改，是最佳淘汰頁(yè)；2類（A=0，M=1）：表示該頁(yè)最近未被訪問，但已被修改，并不是很好的淘汰頁(yè)；3類（A=1，M=0）：最近已被訪問，但未被修改，該頁(yè)有可能再次被訪問；4類（A=1，M=1）：最近已被訪問且被修改，該頁(yè)可能再次被訪問。第36頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．4頁(yè)面置換算法

改進(jìn)CLOCK算法執(zhí)行過程①?gòu)漠?dāng)前位置掃描循環(huán)隊(duì)列，尋找<1>類頁(yè)面,找到后立即置換

。②若步驟①失敗，開始第二輪掃描，尋找<2>類頁(yè)面找到后立即置換

。并將所經(jīng)過的頁(yè)面的訪問位置0。③若步驟②也失敗，重復(fù)步驟①，若仍失敗，再重復(fù)步驟②。第37頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析

請(qǐng)求分頁(yè)式存儲(chǔ)管理系統(tǒng)的性能優(yōu)越，較好地解決了存儲(chǔ)擴(kuò)充問題。因此，它是目前最常用的存儲(chǔ)管理方式。但進(jìn)程在運(yùn)行時(shí)所產(chǎn)生的缺頁(yè)中斷，會(huì)影響程序的運(yùn)行速度及系統(tǒng)性能。而缺頁(yè)率的高低又與分配給進(jìn)程的物理塊數(shù)直接相關(guān)。因此，本節(jié)所要介紹的主要內(nèi)容是分析:

1.缺頁(yè)率對(duì)系統(tǒng)性能的影響程度

2.為每個(gè)進(jìn)程分配多少物理塊數(shù)目，才能把缺頁(yè)率保持在一個(gè)合理的水平上。第38頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析

缺頁(yè)率對(duì)有效訪問時(shí)間的影響

：有效訪問時(shí)間：設(shè)p為缺頁(yè)率，t為存儲(chǔ)器訪問時(shí)間，則有效訪問時(shí)間為：

有效訪問時(shí)間=（1－p）×t+p×缺頁(yè)中斷時(shí)間缺頁(yè)中斷時(shí)間的組成：缺頁(yè)中斷時(shí)間主要由三部分組成：缺頁(yè)中斷服務(wù)時(shí)間；將所缺的頁(yè)讀入的時(shí)間；進(jìn)程重新執(zhí)行時(shí)間。第39頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析

缺頁(yè)中斷率對(duì)訪問時(shí)間的影響：其中缺頁(yè)中斷服務(wù)時(shí)間和進(jìn)程重新執(zhí)行時(shí)間之和可以不超過1ms,而將一磁盤塊讀入內(nèi)存的時(shí)間大概是24ms。所以缺頁(yè)中斷時(shí)間約為25ms。如果存儲(chǔ)器的平均訪問時(shí)間為100ns，于是可得：有效訪問時(shí)間=（1－p）×0.1+p×25000=0.1+24999.9p

如果希望在缺頁(yè)時(shí)，僅使有效訪問時(shí)間延長(zhǎng)不超過10%，則可計(jì)算出缺頁(yè)率p0.1×(1+10%)

0.1+24999.9p即第40頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析

由此可知，要求在2500000次的訪問中，才發(fā)生一次缺頁(yè)，即請(qǐng)求分頁(yè)式存儲(chǔ)管理應(yīng)保持非常低的缺頁(yè)率，否則將使程序的執(zhí)行速度受到嚴(yán)重影響。此外，提高磁盤I/O速度，對(duì)改善請(qǐng)求分頁(yè)系統(tǒng)的性能至關(guān)重要。為此，應(yīng)選用高速磁盤和高速磁盤接口。第41頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析例：現(xiàn)有一請(qǐng)求調(diào)頁(yè)系統(tǒng)，頁(yè)表保存在寄存器中。若有一個(gè)被替換的頁(yè)未被修改過，則處理一個(gè)缺頁(yè)中斷需要8ms；若被替換的頁(yè)被修改過，則處理一個(gè)缺頁(yè)中斷需要20ms。內(nèi)存存取時(shí)間為1s,訪問頁(yè)表的時(shí)間可以忽略不計(jì)。假設(shè)70%被替換的頁(yè)被修改過，為保證有效存取時(shí)間不超過2s，則可接受的最大缺頁(yè)率是多少？p*(0.7*20+0.3*8)+(1-p)*0.001<=0.002P<=1/163990.00006第42頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析“抖動(dòng)”問題在虛存中，頁(yè)面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁(yè)面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動(dòng)原因：頁(yè)面淘汰算法不合理分配給進(jìn)程的物理頁(yè)面數(shù)太少第43頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析駐留集

虛擬頁(yè)式存儲(chǔ)管理中給進(jìn)程分配的物理塊的集合；駐留集大小即是這個(gè)集合的元素個(gè)數(shù)駐留集大小與系統(tǒng)效率每個(gè)進(jìn)程的駐留集越小，則同時(shí)駐留內(nèi)存的進(jìn)程就越多，CPU利用率越高進(jìn)程的駐留集太小的話，則缺頁(yè)率高，使調(diào)頁(yè)的開銷增大進(jìn)程的駐留集大小達(dá)到一定數(shù)目之后，再給它分配更多頁(yè)面，缺頁(yè)率不再明顯下降第44頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析

拐點(diǎn)物理塊數(shù)n缺頁(yè)率第45頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析

工作集：

1968年由Denning提出，引入工作集的目的是依據(jù)進(jìn)程在過去的一段時(shí)間內(nèi)訪問的頁(yè)面來(lái)調(diào)整駐留集大小工作集定義：工作集就是進(jìn)程在某段時(shí)間段Δ里實(shí)際要訪問的頁(yè)面的集合。第46頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析工作集（WorkingSet）模型

基本思想：根據(jù)程序的局部性原理，一般情況下，進(jìn)程在一段時(shí)間內(nèi)總是集中訪問一些頁(yè)面，這些頁(yè)面稱為活躍頁(yè)面，如果分配給一個(gè)進(jìn)程的物理頁(yè)面數(shù)太少了，使該進(jìn)程所需的活躍頁(yè)面不能全部裝入內(nèi)存，則進(jìn)程在運(yùn)行過程中將頻繁發(fā)生中斷抖動(dòng)

進(jìn)程要有效地運(yùn)行，其工作集必須在內(nèi)存中第47頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析

工作集：工作集就是進(jìn)程在某段時(shí)間段Δ里實(shí)際要訪問的頁(yè)面的集合。具體地說，運(yùn)行進(jìn)程在時(shí)間t－Δ到t這個(gè)時(shí)間段內(nèi)所訪問的頁(yè)面的集合稱為該進(jìn)程在時(shí)間t的工作集，記為，變量Δ稱為工作集“窗口尺寸”（WindowsSize）。通常還把工作集中所包含的頁(yè)面數(shù)稱為“工作集尺寸”，記為例：

26157775162341234443434441327||t1||t2ws(t1,△)={1,2,5,6,7}ws(t2,△)={3,4}第48頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析△大小確定如果△過大，甚至把作業(yè)地址空間全包括在內(nèi)，就成了實(shí)存管理;如果△過小，則會(huì)引起頻繁缺頁(yè),降低了系統(tǒng)的效率。第49頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析工作集大小的變化

進(jìn)程開始執(zhí)行后，隨著訪問新頁(yè)面逐步建立較穩(wěn)定的工作集。當(dāng)內(nèi)存訪問的局部性區(qū)域的位置大致穩(wěn)定時(shí)，工作集大小也大致穩(wěn)定；局部性區(qū)域的位置改變時(shí)，工作集快速擴(kuò)張和收縮過渡到下一個(gè)穩(wěn)定值。第50頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析利用工作集來(lái)進(jìn)行駐留集調(diào)整的策略：記錄一個(gè)進(jìn)程的工作集變化定期刪除駐留集中不在工作集中的頁(yè)面總是讓駐留集包含工作集（不能包含時(shí)則增大駐留集）第51頁(yè),共81頁(yè)，2024年2月25日，星期天8．2．5請(qǐng)求分頁(yè)系統(tǒng)的性能分析影響缺頁(yè)次數(shù)的因素(1)分配給進(jìn)程的物理塊數(shù) 一個(gè)程序運(yùn)行時(shí)遇到缺頁(yè)中斷的次數(shù)，是和分配給該道程序的物理塊數(shù)成反比的，但當(dāng)主存容量達(dá)到某個(gè)值時(shí)，缺頁(yè)次數(shù)減少不再明顯。多數(shù)程序都有一個(gè)確定值——拐點(diǎn)(2)頁(yè)面本身的大小 頁(yè)面大，頁(yè)表小，省空間且查找快；缺頁(yè)次數(shù)相對(duì)也少；一次換頁(yè)的時(shí)間長(zhǎng)，頁(yè)內(nèi)碎片空間浪費(fèi)的可能性較大。頁(yè)面小則相反.(3)頁(yè)面置換算法(頁(yè)面淘汰算法)

選擇最合適的置換算法。(4)程序的編制方法 盡可能使編出的程序具有高度的局部性，則執(zhí)行時(shí)可經(jīng)常集中在幾個(gè)頁(yè)面上進(jìn)行訪問，減少缺頁(yè)率.第52頁(yè),共81頁(yè)，2024年2月25日，星期天8．3請(qǐng)求分段式存儲(chǔ)管理方式

請(qǐng)求分段存儲(chǔ)管理系統(tǒng)是在分段存儲(chǔ)管理系統(tǒng)的基礎(chǔ)上實(shí)現(xiàn)的虛擬存儲(chǔ)器。它以段為單位進(jìn)行換入換出。在程序運(yùn)行之前不必調(diào)入所有的段，而只調(diào)入若干個(gè)段，便可啟動(dòng)運(yùn)行。當(dāng)所訪問的段不在內(nèi)存時(shí)可請(qǐng)求操作系統(tǒng)將所缺的段調(diào)入內(nèi)存。為實(shí)現(xiàn)請(qǐng)求分段存儲(chǔ)管理，與請(qǐng)求分頁(yè)存儲(chǔ)管理類似，需要硬件的支持和相應(yīng)的軟件。第53頁(yè),共81頁(yè)，2024年2月25日，星期天8．3．1請(qǐng)求分段存儲(chǔ)管理的基本概念

基本原理：在請(qǐng)求分段式存儲(chǔ)管理系統(tǒng)中，進(jìn)程運(yùn)行之前一部分段裝入內(nèi)存，另外一部分段則裝入外存。在進(jìn)程運(yùn)行過程中，如果所訪問的段不在內(nèi)存中，則發(fā)生缺段中斷，進(jìn)入操作系統(tǒng)，由操作系統(tǒng)進(jìn)行段的動(dòng)態(tài)調(diào)度。段表機(jī)制：請(qǐng)求分段的段表是在純分段的段表機(jī)制的基礎(chǔ)上形成的。需在段表中增加若干項(xiàng)，供程序在換進(jìn)換出時(shí)參考。下面所示是一請(qǐng)求分段系統(tǒng)中的段表：段名段長(zhǎng)段基址存取方式訪問字段修改位存在位增補(bǔ)位外存地址第54頁(yè),共81頁(yè)，2024年2月25日，星期天8．3．1請(qǐng)求分段存儲(chǔ)管理的基本概念

存取方式：用于標(biāo)識(shí)本段的存取屬性，存取屬性包括只執(zhí)行、只讀還是讀/寫；訪問字段：用于記錄該段在一段時(shí)間內(nèi)被訪問的次數(shù)，或最近已有多長(zhǎng)時(shí)間未被訪問，供置換算法選擇段時(shí)參考；修改位：表示該段在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一段都在外存上保留一個(gè)副本，因此，若未被修改，在置換該段時(shí)就不需將該段寫回到磁盤上，以減少系統(tǒng)的開銷和啟動(dòng)磁盤的次數(shù)；若已被修改，則必須將該段重寫回磁盤上，以保證磁盤上所保留的始終是最新副本；第55頁(yè),共81頁(yè)，2024年2月25日，星期天8．3．1請(qǐng)求分段存儲(chǔ)管理的基本概念

存在位：說明本段是否已調(diào)入內(nèi)存；增補(bǔ)位：用于表示本段在運(yùn)行過程中，是否進(jìn)行過動(dòng)態(tài)增長(zhǎng)；外存地址：用于指出該段在外存上的起始地址，通常是起始物理塊號(hào)，供調(diào)入該段時(shí)使用。第56頁(yè),共81頁(yè)，2024年2月25日，星期天8．3．1請(qǐng)求分段存儲(chǔ)管理的基本概念

請(qǐng)求分段存儲(chǔ)管理系統(tǒng)的示意圖：200K存儲(chǔ)空間030K90K150K(MAIN)=020K（X）=18K（S）=310K作業(yè)空間10K0（S）=312K0（D）=28K0（X）=120K0（MAIN）=0狀態(tài)段表基址段長(zhǎng)段號(hào)20K030K8K190K12K2150K10K3200K0010第57頁(yè),共81頁(yè)，2024年2月25日，星期天8．3．1請(qǐng)求分段存儲(chǔ)管理的基本概念

地址變換機(jī)構(gòu)：請(qǐng)求分段系統(tǒng)中的地址變換機(jī)構(gòu)，是在分段系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上形成的。由于被訪問的段并非全在內(nèi)存，所以在地址變換時(shí)，若發(fā)現(xiàn)所要訪問的段不在內(nèi)存時(shí)，必須先將所缺的段調(diào)入內(nèi)存，在修改了段表之后，才能利用段表進(jìn)行地址變換。下圖給出了請(qǐng)求分段系統(tǒng)的地址變換過程。第58頁(yè),共81頁(yè)，2024年2月25日，星期天8．3．1請(qǐng)求分段存儲(chǔ)管理的基本概念

是訪問（s，w）w

段表長(zhǎng)？否越界中斷處理符合存取方式？保護(hù)中斷處理否是段s在主存？缺段中斷處理否是修改訪問字段，如果寫訪問，置修改位=1形成訪問內(nèi)存地址：（A）=內(nèi)存始址+偏移量w返回第59頁(yè),共81頁(yè)，2024年2月25日，星期天8．3．2分段共享與保護(hù)

分段共享：在系統(tǒng)中配置一張共享段表，所有共享段都在共享段表中占有一個(gè)表項(xiàng)。共享段表除具有段表中的表項(xiàng)外，還記錄有共享此段的每個(gè)進(jìn)程的情況，其中包括：共享進(jìn)程數(shù)count：記錄共享該段的進(jìn)程數(shù)，只有當(dāng)count為0時(shí)，才由系統(tǒng)回收該段所占存儲(chǔ)區(qū)；存取控制字段：記錄不同進(jìn)程的不同存取權(quán)限。如對(duì)于擁有該段的進(jìn)程，則允許讀和寫，而對(duì)于其它進(jìn)程，則可能只允許讀，或者只允許執(zhí)行。段名段長(zhǎng)段基址狀態(tài)外存始址共享進(jìn)程計(jì)數(shù)count狀態(tài)進(jìn)程名進(jìn)程號(hào)段號(hào)存取控制……第60頁(yè),共81頁(yè)，2024年2月25日，星期天8．3．2分段共享與保護(hù)

分段保護(hù)：由于進(jìn)程的每個(gè)段在邏輯上是獨(dú)立的，因而比較容易實(shí)現(xiàn)信息保護(hù)。常用的分段保護(hù)方法有越界檢查和存取控制檢查等。越界檢查：在進(jìn)行存儲(chǔ)訪問時(shí)，首先將邏輯地址空間的段號(hào)與段表長(zhǎng)度進(jìn)行比較，如果段號(hào)等于或大于段表長(zhǎng)度，將發(fā)出地址越界中斷信號(hào)；其次，還要檢查段內(nèi)地址是否等于或大于段長(zhǎng)，若是等于或大于段長(zhǎng)，將產(chǎn)生地址越界中斷信號(hào)，從而保證了每個(gè)進(jìn)程只能在自己的地址空間內(nèi)運(yùn)行。存取控制檢查：在段表的每個(gè)表項(xiàng)中，都設(shè)置了一個(gè)“存取控制”字段，用于規(guī)定該段的訪問方式。通常有只讀、只執(zhí)行和讀/寫等三種。第61頁(yè),共81頁(yè)，2024年2月25日，星期天練習(xí)：一個(gè)程序的段表如下表，其中存在位為0表示段在內(nèi)存，存取控制字段中W表示可寫，R表示可讀，E表示可執(zhí)行。對(duì)下面的5條指令，在執(zhí)行時(shí)會(huì)產(chǎn)生什么樣的結(jié)果？（0表示在內(nèi)存中，1表示在外存）STORER1,[0,70]STORER1,[1,20]LOADR1,[3,20]LOADR1,[3,100]JMP[2,100]段號(hào)存在位內(nèi)存始址段長(zhǎng)存取控制01500100W10100030R203000200E30800080R41500040R缺段中斷只讀，保護(hù)性中斷合法，形成物理地址8020，將該單元內(nèi)容讀入寄存器R1中越界中斷合法，跳到3100處繼續(xù)執(zhí)行答：第62頁(yè),共81頁(yè)，2024年2月25日，星期天8．4Linux存儲(chǔ)管理

Linux操作系統(tǒng)采用虛擬存儲(chǔ)管理機(jī)制，即置換和請(qǐng)求分頁(yè)存儲(chǔ)管理技術(shù)。盡管Linux的存儲(chǔ)管理的基本原理與前面所論述的存儲(chǔ)管理方法是相同的，但它也有自己獨(dú)特的特點(diǎn)?？傮w而言，Linux的存儲(chǔ)管理方案非常復(fù)雜。下面就其存儲(chǔ)管理的主要特征進(jìn)行簡(jiǎn)單的論述。第63頁(yè),共81頁(yè)，2024年2月25日，星期天8．4．1Linux的內(nèi)存空間在x86平臺(tái)的Linux系統(tǒng)中，地址碼采用32位，因此每個(gè)進(jìn)程的虛存空間可以達(dá)到4GB。Linux內(nèi)核將這4GB的空間分為兩部分：最高地址的1GB是系統(tǒng)空間，供內(nèi)核本身使用；而較低地址的3GB空間是用戶空間。系統(tǒng)空間由所有進(jìn)程共享，而用戶空間理論上雖然可以達(dá)到3GB，但實(shí)際的用戶空間要受到物理存儲(chǔ)器（包括內(nèi)存和磁盤的交換空間）和用戶競(jìng)爭(zhēng)存儲(chǔ)器的限制。第64頁(yè),共81頁(yè)，2024年2月25日，星期天8．4．2Linux的頁(yè)表機(jī)制頁(yè)表：在Linux系統(tǒng)中，頁(yè)的大小為4KB，因此每個(gè)進(jìn)程的虛存空間要有1M個(gè)頁(yè)面。如果采用一級(jí)頁(yè)表描述這種映射關(guān)系，每個(gè)進(jìn)程的頁(yè)表就要有1M個(gè)表項(xiàng)。顯然，用大量的內(nèi)存資源來(lái)存放頁(yè)表的方法是不可取的，所以，Linux采用三級(jí)頁(yè)表的方式。頁(yè)目錄（PGD）：第一級(jí)頁(yè)表為頁(yè)目錄，每個(gè)活動(dòng)進(jìn)程有一個(gè)頁(yè)目錄。頁(yè)目錄的大小為一頁(yè)的尺寸，頁(yè)目錄的每一項(xiàng)指向頁(yè)中間目錄中的一頁(yè)。每個(gè)活動(dòng)進(jìn)程的頁(yè)目錄都必須在內(nèi)存中。頁(yè)中間目錄（PMD）：第二級(jí)頁(yè)表為頁(yè)中間目錄。頁(yè)中間目錄可以有多個(gè)頁(yè)，頁(yè)中間目錄的每一項(xiàng)指向頁(yè)表中的一頁(yè)。頁(yè)表（PT）：第三級(jí)目錄為頁(yè)表。頁(yè)表也可以有多個(gè)頁(yè)，頁(yè)表中的每一項(xiàng)指向該進(jìn)程的一個(gè)虛擬頁(yè)。

第65頁(yè),共81頁(yè)，2024年2月25日，星期天8．4．2Linux的頁(yè)表機(jī)制頁(yè)目錄（PGD）：第一級(jí)頁(yè)表為頁(yè)目錄，每個(gè)活動(dòng)進(jìn)程有一個(gè)頁(yè)目錄。頁(yè)目錄的大小為一頁(yè)的尺寸，頁(yè)目錄的每一項(xiàng)指向頁(yè)中間目錄中的一頁(yè)。每個(gè)活動(dòng)進(jìn)程的頁(yè)目錄都必須在內(nèi)存中。頁(yè)中間目錄（PMD）：第二級(jí)頁(yè)表為頁(yè)中間目錄。頁(yè)中間目錄可以有多個(gè)頁(yè)，頁(yè)中間目錄的每一項(xiàng)指向頁(yè)表中的一頁(yè)。第66頁(yè),共81頁(yè)，2024年2月25日，星期天8．4．2Linux的頁(yè)表機(jī)制地址轉(zhuǎn)換：Linux虛擬內(nèi)存的地址轉(zhuǎn)換分為四步，如下圖所示：PMD寄存器PGD下標(biāo)PMD下標(biāo)PT下標(biāo)頁(yè)內(nèi)偏移量虛擬地址PGD……PT…物理頁(yè)面…PGD基地址++++第67頁(yè),共81頁(yè)，2024年2月25日，星期天8．4．2Linux的頁(yè)表機(jī)制把虛擬地址中的最高位段與寄存器中的PGD基地址相加，在PGD中找到相應(yīng)的表項(xiàng)，該表項(xiàng)指向相應(yīng)的PMD基地址；把虛擬地址中的第二個(gè)位段與PMD的基地址相加，在PMD中找到相應(yīng)的表項(xiàng)，該表項(xiàng)指向相應(yīng)的PT基地址；把虛擬地址中的第三個(gè)位段與PT的基地址相加，在PT中找到相應(yīng)的表項(xiàng)，該表項(xiàng)指向相應(yīng)的物理頁(yè)面；把虛擬地址中的最低位段與物理頁(yè)面的基地址相加，得到相應(yīng)的物理地址。第68頁(yè),共81頁(yè)，2024年2月25日，星期天8．4．3Linux內(nèi)存頁(yè)的分配為了提高往內(nèi)存中讀入頁(yè)和從內(nèi)存中寫出頁(yè)的效率，Linux采用了一種機(jī)制，即把連續(xù)的頁(yè)映射到連續(xù)的物理塊中?；谶@個(gè)目的，它采用了一種伙伴系統(tǒng)。內(nèi)核維護(hù)一系列大小固定的連續(xù)物理塊組，一組可以包含1、2、4、8、16或32個(gè)物理塊。當(dāng)一頁(yè)在內(nèi)存中被分配或被釋放時(shí)，可用的組使用伙伴算法被分割或合并。第69頁(yè),共81頁(yè)，2024年2月25日，星期天8．4．4Linux內(nèi)存頁(yè)的置換算法

Linux的頁(yè)面置換算法采用最近最少使用置換算法（NRU）。在簡(jiǎn)單的最近最少使用置換算法中，內(nèi)存中的每一頁(yè)都有一個(gè)訪問位和一個(gè)修改位。在Linux系統(tǒng)中，用一個(gè)8位的age變量取代了訪問位。每當(dāng)一頁(yè)被訪問時(shí)，age變量增1。在后臺(tái)，Linux周期性地掃描全局頁(yè)池，并將所有大于0的age變量減1。age的值為0的頁(yè)在較長(zhǎng)一段時(shí)間內(nèi)未被訪問過，是用于置換的最佳候選頁(yè)。age的值越大，該頁(yè)最近被使用的頻率越高，從而越不適合于被置換。第70頁(yè),共81頁(yè)，2024年2月25日，星期天8．5Windows存儲(chǔ)管理

Windows有一個(gè)非常成功的虛擬存儲(chǔ)系統(tǒng)。有大量的Win32函數(shù)和六個(gè)內(nèi)核線程在進(jìn)行存儲(chǔ)管理。它采用的是頁(yè)式虛擬存儲(chǔ)管理。第71頁(yè),共81頁(yè)，2024年2月25日，星期天8．5．1Windows的虛擬地址空間在Windows中，每一個(gè)用戶進(jìn)程都有自己的虛擬地址空間。虛擬地址的長(zhǎng)度是32位，因此每個(gè)進(jìn)程有4GB（232B）的虛擬地址空間。低2GB為用戶地址空間，用于進(jìn)程代碼和數(shù)據(jù)；高2GB為核心地址空間，它處于保護(hù)模式。其中的用戶地址空間可被用戶態(tài)和核心態(tài)線程存取，并且對(duì)每個(gè)進(jìn)程都是不同的；而核心地址空間只能被核心態(tài)線程存取，并且對(duì)每個(gè)線程都是相同的。這兩個(gè)地址空間的布局如圖12．6所示。虛擬地址空間采用分頁(yè)存儲(chǔ)管理，每一頁(yè)的大小是固定的（Pentium是4KB）。第72頁(yè),共81頁(yè)，2024年2月25日，星期天8．5．1Windows的虛擬地址空間2GB04GB非頁(yè)池頁(yè)池用戶頁(yè)表?xiàng)?、?shù)據(jù)等HAL+操作系統(tǒng)用戶地址空間第73頁(yè),共81頁(yè)，2024年2月25日，星期天8．5．2頁(yè)面狀態(tài)