蒲曉蓉_操作系統(tǒng)原理第3_3章_存儲管理

1、3.5 虛擬存儲管理技術(shù)虛擬存儲管理技術(shù) 簡單存儲：要求將一個(gè)進(jìn)程所需的程序和數(shù)據(jù)簡單存儲：要求將一個(gè)進(jìn)程所需的程序和數(shù)據(jù)全部裝入內(nèi)存方可執(zhí)行。全部裝入內(nèi)存方可執(zhí)行。 這樣的系統(tǒng)存在兩個(gè)很嚴(yán)重的問題。這樣的系統(tǒng)存在兩個(gè)很嚴(yán)重的問題。 其一，對于大進(jìn)程，如果其所需內(nèi)存空間超過了內(nèi)存其一，對于大進(jìn)程，如果其所需內(nèi)存空間超過了內(nèi)存的最大容量，則無法運(yùn)行。的最大容量，則無法運(yùn)行。 其二，對于多道程序系統(tǒng)，由于每一個(gè)進(jìn)程需要全部其二，對于多道程序系統(tǒng)，由于每一個(gè)進(jìn)程需要全部裝入內(nèi)存，使同時(shí)駐留內(nèi)存的進(jìn)程數(shù)量受到限制。雖裝入內(nèi)存，使同時(shí)駐留內(nèi)存的進(jìn)程數(shù)量受到限制。雖然也可以通過提高內(nèi)存容量來解決，但是代價(jià)

2、太高。然也可以通過提高內(nèi)存容量來解決，但是代價(jià)太高。 如果能將一部分價(jià)格較低的外存空間當(dāng)作內(nèi)存如果能將一部分價(jià)格較低的外存空間當(dāng)作內(nèi)存使用，從邏輯上擴(kuò)充內(nèi)存容量。那么，將獲得使用，從邏輯上擴(kuò)充內(nèi)存容量。那么，將獲得更高的性價(jià)比。更高的性價(jià)比。虛擬存儲技術(shù)的理論依據(jù)虛擬存儲技術(shù)的理論依據(jù) 程序執(zhí)行的局部性原理：程序的執(zhí)行總是呈現(xiàn)程序執(zhí)行的局部性原理：程序的執(zhí)行總是呈現(xiàn)局部性。即，在一個(gè)較短的時(shí)間段內(nèi)，程序的局部性。即，在一個(gè)較短的時(shí)間段內(nèi)，程序的執(zhí)行僅限于某個(gè)部分；相應(yīng)的，它所訪問的存執(zhí)行僅限于某個(gè)部分；相應(yīng)的，它所訪問的存儲空間也局限于某個(gè)區(qū)域。儲空間也局限于某個(gè)區(qū)域。 因此，只要保證進(jìn)程執(zhí)行

3、所需的部分程序和數(shù)因此，只要保證進(jìn)程執(zhí)行所需的部分程序和數(shù)據(jù)駐留在內(nèi)存，一段時(shí)間內(nèi)進(jìn)程都能順利執(zhí)行。據(jù)駐留在內(nèi)存，一段時(shí)間內(nèi)進(jìn)程都能順利執(zhí)行。實(shí)現(xiàn)虛擬存儲的一般過程實(shí)現(xiàn)虛擬存儲的一般過程 進(jìn)程運(yùn)行之前，僅需要將一部分頁面或段裝入進(jìn)程運(yùn)行之前，僅需要將一部分頁面或段裝入內(nèi)存，便可啟動(dòng)運(yùn)行，其余部分暫時(shí)保留在磁內(nèi)存，便可啟動(dòng)運(yùn)行，其余部分暫時(shí)保留在磁盤上。盤上。 進(jìn)程運(yùn)行時(shí)，如果它所需要訪問的頁面（段）進(jìn)程運(yùn)行時(shí)，如果它所需要訪問的頁面（段）已經(jīng)裝入內(nèi)存，則可以繼續(xù)執(zhí)行下去；已經(jīng)裝入內(nèi)存，則可以繼續(xù)執(zhí)行下去； 如果其所需要訪問的頁面（段）尚未裝入內(nèi)存，如果其所需要訪問的頁面（段）尚未裝入內(nèi)存，則發(fā)

4、生缺頁（段）中斷，進(jìn)程阻塞。則發(fā)生缺頁（段）中斷，進(jìn)程阻塞。 此時(shí)，系統(tǒng)將啟動(dòng)請求調(diào)頁（段）功能，將進(jìn)此時(shí)，系統(tǒng)將啟動(dòng)請求調(diào)頁（段）功能，將進(jìn)程所需的頁（段）裝入內(nèi)存。程所需的頁（段）裝入內(nèi)存。實(shí)現(xiàn)虛擬存儲的一般過程實(shí)現(xiàn)虛擬存儲的一般過程 如果當(dāng)前內(nèi)存已滿，無法裝入新的頁如果當(dāng)前內(nèi)存已滿，無法裝入新的頁（段），則還需要利用頁（段）置換功（段），則還需要利用頁（段）置換功能，將內(nèi)存中暫時(shí)不用的頁（段）交換能，將內(nèi)存中暫時(shí)不用的頁（段）交換到磁盤上，以騰出足夠的內(nèi)存空間。到磁盤上，以騰出足夠的內(nèi)存空間。 再將進(jìn)程所需的頁（段）裝入內(nèi)存，喚再將進(jìn)程所需的頁（段）裝入內(nèi)存，喚醒阻塞的進(jìn)程，使之重新參與

5、調(diào)度執(zhí)行。醒阻塞的進(jìn)程，使之重新參與調(diào)度執(zhí)行。 從外存裝入頁從外存裝入頁/段段更新頁更新頁/段表段表交換頁交換頁/段段內(nèi)存滿內(nèi)存滿？是是否否缺頁缺頁/段中斷段中斷頁頁/段段在內(nèi)存在內(nèi)存是是否否進(jìn)程執(zhí)行進(jìn)程執(zhí)行圖圖3.28 實(shí)現(xiàn)虛擬存儲的典型過程實(shí)現(xiàn)虛擬存儲的典型過程什么是虛擬存儲什么是虛擬存儲 通過系統(tǒng)提供的缺頁通過系統(tǒng)提供的缺頁/段中斷功能和交換技術(shù)，段中斷功能和交換技術(shù)，動(dòng)態(tài)裝入進(jìn)程的程序代碼和數(shù)據(jù)，使得一個(gè)大動(dòng)態(tài)裝入進(jìn)程的程序代碼和數(shù)據(jù)，使得一個(gè)大的用戶程序能在一個(gè)相對較小的內(nèi)存空間中運(yùn)的用戶程序能在一個(gè)相對較小的內(nèi)存空間中運(yùn)行，也使得有限的內(nèi)存能同時(shí)容納更多的進(jìn)程。行，也使得有限的內(nèi)存

6、能同時(shí)容納更多的進(jìn)程。 習(xí)慣上，人們把這種用戶感覺上的、由實(shí)際內(nèi)習(xí)慣上，人們把這種用戶感覺上的、由實(shí)際內(nèi)存和部分外存共同構(gòu)成的存儲空間稱為存和部分外存共同構(gòu)成的存儲空間稱為虛擬存虛擬存儲器儲器虛擬存儲技術(shù)的技術(shù)支持虛擬存儲技術(shù)的技術(shù)支持 首先，必須有相應(yīng)的硬件支持，用以實(shí)首先，必須有相應(yīng)的硬件支持，用以實(shí)現(xiàn)虛擬分頁或虛擬分段存儲管理。現(xiàn)虛擬分頁或虛擬分段存儲管理。 其次，操作系統(tǒng)必須提供相應(yīng)的軟件支其次，操作系統(tǒng)必須提供相應(yīng)的軟件支持，管理頁或段在內(nèi)存和外存之間的移持，管理頁或段在內(nèi)存和外存之間的移動(dòng)。動(dòng)。虛擬存儲的基本數(shù)據(jù)結(jié)構(gòu)虛擬存儲的基本數(shù)據(jù)結(jié)構(gòu) 由于虛擬存儲系統(tǒng)中，進(jìn)程的程序代碼和數(shù)據(jù)由

7、于虛擬存儲系統(tǒng)中，進(jìn)程的程序代碼和數(shù)據(jù)只有一部分在內(nèi)存，另一部分保存在外存。只有一部分在內(nèi)存，另一部分保存在外存。 在頁在頁/段表項(xiàng)中增加一個(gè)段表項(xiàng)中增加一個(gè)“存在存在”字段，其值字段，其值為為0或或1。 增加一個(gè)增加一個(gè)“修改修改”字段，表明對應(yīng)頁字段，表明對應(yīng)頁/段自進(jìn)段自進(jìn)入內(nèi)存以來是否被修改過。只有被修改過的頁入內(nèi)存以來是否被修改過。只有被修改過的頁/段才需要保存到外存，若需要將未修改過的段才需要保存到外存，若需要將未修改過的頁頁/段換出內(nèi)存，只需要將新裝入的頁段換出內(nèi)存，只需要將新裝入的頁/段直接段直接覆蓋其存儲區(qū)域，而不必將其內(nèi)容保存到外存。覆蓋其存儲區(qū)域，而不必將其內(nèi)容保存到外存

8、。 圖圖3.29 虛擬分頁、分段及段頁式存儲系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)虛擬分頁、分段及段頁式存儲系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)頁號頁號頁框號頁框號存在存在修改修改其他控制其他控制(a) 虛擬存儲頁表項(xiàng)虛擬存儲頁表項(xiàng)段號段號段長段長存在存在修改修改其他控制其他控制(b) 虛擬存儲段表項(xiàng)虛擬存儲段表項(xiàng)段基址長段基址長(c) 虛擬存儲段頁式系統(tǒng)的段表項(xiàng)和頁表項(xiàng)虛擬存儲段頁式系統(tǒng)的段表項(xiàng)和頁表項(xiàng)段號段號其他控制其他控制頁表長度頁表長度頁表基址頁表基址段表項(xiàng)段表項(xiàng)頁號頁號頁框號頁框號存在存在修改修改其他控制其他控制頁表項(xiàng)頁表項(xiàng)虛擬存儲的好處虛擬存儲的好處 第一，可以運(yùn)行大程序，包括超過內(nèi)存第一，可以運(yùn)行大程序，包括超過內(nèi)存實(shí)際容量

9、的大程序。實(shí)際容量的大程序。 第二，可以在有限的物理內(nèi)存中運(yùn)行更第二，可以在有限的物理內(nèi)存中運(yùn)行更多的程序。多道程序系統(tǒng)的度不再受到多的程序。多道程序系統(tǒng)的度不再受到物理內(nèi)存空間的限制。物理內(nèi)存空間的限制。虛擬存儲的典型問題虛擬存儲的典型問題抖動(dòng)（抖動(dòng)（thrashing） 當(dāng)進(jìn)程要求裝入新的頁面或程序段時(shí)，如果當(dāng)當(dāng)進(jìn)程要求裝入新的頁面或程序段時(shí)，如果當(dāng)前沒有足夠的空閑空間，需要交換一些頁面或前沒有足夠的空閑空間，需要交換一些頁面或段到外存。如果被交換出去的頁面或段很快將段到外存。如果被交換出去的頁面或段很快將被進(jìn)程使用，則又需要將其換入內(nèi)存。被進(jìn)程使用，則又需要將其換入內(nèi)存。 如果系統(tǒng)花費(fèi)大

10、量的時(shí)間把程序和數(shù)據(jù)頻繁地如果系統(tǒng)花費(fèi)大量的時(shí)間把程序和數(shù)據(jù)頻繁地裝入和移出內(nèi)存而不是執(zhí)行用戶指令，那么，裝入和移出內(nèi)存而不是執(zhí)行用戶指令，那么，稱系統(tǒng)出現(xiàn)了稱系統(tǒng)出現(xiàn)了抖動(dòng)抖動(dòng)。出現(xiàn)抖動(dòng)現(xiàn)象時(shí)，系統(tǒng)顯。出現(xiàn)抖動(dòng)現(xiàn)象時(shí)，系統(tǒng)顯得非常繁忙，但是吞吐量很低，甚至產(chǎn)出為零。得非常繁忙，但是吞吐量很低，甚至產(chǎn)出為零。 根本原因：選擇的頁面或段不恰當(dāng)。根本原因：選擇的頁面或段不恰當(dāng)。虛擬存儲分頁技術(shù)虛擬存儲分頁技術(shù) 建立在簡單分頁存儲管理系統(tǒng)之上，是建立在簡單分頁存儲管理系統(tǒng)之上，是目前常用的一種虛擬存儲管理技術(shù)。目前常用的一種虛擬存儲管理技術(shù)。地址變換地址變換 基于簡單存儲分頁系統(tǒng)增加了某些功能，如產(chǎn)

11、基于簡單存儲分頁系統(tǒng)增加了某些功能，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出頁面等。生和處理缺頁中斷，以及從內(nèi)存中換出頁面等。 進(jìn)程執(zhí)行時(shí)，首先通過根據(jù)邏輯地址中的頁號，進(jìn)程執(zhí)行時(shí)，首先通過根據(jù)邏輯地址中的頁號，查找查找快表快表中是否存在對應(yīng)的頁表項(xiàng)。若快表中中是否存在對應(yīng)的頁表項(xiàng)。若快表中不存在該頁表項(xiàng)，則再查找不存在該頁表項(xiàng)，則再查找頁表頁表。檢查對應(yīng)的。檢查對應(yīng)的頁面是否在內(nèi)存中存在。若該頁面頁面是否在內(nèi)存中存在。若該頁面不在內(nèi)存不在內(nèi)存，啟動(dòng)啟動(dòng)缺頁中斷處理缺頁中斷處理例程，裝入需要的頁面，并例程，裝入需要的頁面，并更新頁表和快表。若該頁面已經(jīng)在內(nèi)存中，將更新頁表和快表。若該頁面已經(jīng)在內(nèi)

12、存中，將對應(yīng)的頁表項(xiàng)插入快表中，對應(yīng)的頁表項(xiàng)插入快表中，更新快表更新快表。若快表。若快表中存在該表項(xiàng)，則直接取出其中的中存在該表項(xiàng)，則直接取出其中的頁框號，加頁框號，加上頁內(nèi)偏移量，計(jì)算出物理地址上頁內(nèi)偏移量，計(jì)算出物理地址。 訪問頁表訪問頁表圖圖3.30 虛擬存儲分頁系統(tǒng)地址變換過程虛擬存儲分頁系統(tǒng)地址變換過程物理地址物理地址頁框號頁框號 偏移量偏移量更新快表更新快表頁號頁號 偏移量偏移量邏輯地址邏輯地址檢索快表檢索快表是是否否是是否否換出頁面換出頁面處理機(jī)處理中斷處理機(jī)處理中斷是是否否處理機(jī)從外存取該頁處理機(jī)從外存取該頁將該頁裝入內(nèi)存將該頁裝入內(nèi)存更新頁表更新頁表缺頁中斷處理缺頁中斷處理？

13、命中？命中？內(nèi)存滿？內(nèi)存滿？頁在內(nèi)存？頁在內(nèi)存缺頁中斷處理過程缺頁中斷處理過程（1）操作系統(tǒng)接收到進(jìn)程產(chǎn)生的缺頁中斷信號，啟動(dòng)中）操作系統(tǒng)接收到進(jìn)程產(chǎn)生的缺頁中斷信號，啟動(dòng)中斷處理例程，保留處理機(jī)現(xiàn)場；斷處理例程，保留處理機(jī)現(xiàn)場；（2）操作系統(tǒng)通知處理機(jī)從外存讀取指定的頁面；）操作系統(tǒng)通知處理機(jī)從外存讀取指定的頁面；（3）處理機(jī)激活）處理機(jī)激活I(lǐng)/O設(shè)備；設(shè)備；（4） 檢查內(nèi)存有無足夠的空閑空間裝入該頁面？若有，檢查內(nèi)存有無足夠的空閑空間裝入該頁面？若有，轉(zhuǎn)（轉(zhuǎn)（6），否則，執(zhí)行（），否則，執(zhí)行（5）；）；（5） 利用頁面置換算法，選擇內(nèi)存中的某個(gè)頁面，換利用頁面置換算法，選擇內(nèi)存中的某個(gè)頁面

14、，換出內(nèi)存；出內(nèi)存；（6） 將指定頁面從外存裝入內(nèi)存；將指定頁面從外存裝入內(nèi)存；（7） 更新該進(jìn)程的頁表；更新該進(jìn)程的頁表；（8） 更新快表；更新快表；（9）計(jì)算物理地址。）計(jì)算物理地址。 虛擬存儲分段技術(shù)虛擬存儲分段技術(shù) 建立在簡單存儲分段系統(tǒng)基礎(chǔ)上，利用動(dòng)態(tài)分建立在簡單存儲分段系統(tǒng)基礎(chǔ)上，利用動(dòng)態(tài)分區(qū)技術(shù)分配存儲空間，并以段作為交換的單位。區(qū)技術(shù)分配存儲空間，并以段作為交換的單位。 進(jìn)程執(zhí)行之前，系統(tǒng)為之分配幾個(gè)必要的內(nèi)存進(jìn)程執(zhí)行之前，系統(tǒng)為之分配幾個(gè)必要的內(nèi)存分區(qū)，每一個(gè)分區(qū)中裝入一段。分區(qū)，每一個(gè)分區(qū)中裝入一段。 當(dāng)進(jìn)程執(zhí)行過程中，出現(xiàn)缺段中斷時(shí)，操作系當(dāng)進(jìn)程執(zhí)行過程中，出現(xiàn)缺段中斷時(shí)

15、，操作系統(tǒng)將為進(jìn)程裝入需要的程序段。統(tǒng)將為進(jìn)程裝入需要的程序段。虛擬存儲分段：數(shù)據(jù)結(jié)構(gòu)虛擬存儲分段：數(shù)據(jù)結(jié)構(gòu) 因此，需要修改段表，增加因此，需要修改段表，增加“存在存在”字字段和段和“修改修改”字段，分別標(biāo)明對應(yīng)段是字段，分別標(biāo)明對應(yīng)段是否存在于內(nèi)存，以及內(nèi)存中的段自裝入否存在于內(nèi)存，以及內(nèi)存中的段自裝入以來是否被修改過。以來是否被修改過。地址變換與存儲保護(hù)地址變換與存儲保護(hù) 在簡單分段系統(tǒng)的地址變換機(jī)構(gòu)基礎(chǔ)上形成的。在簡單分段系統(tǒng)的地址變換機(jī)構(gòu)基礎(chǔ)上形成的。 越界檢查越界檢查：可能產(chǎn)生一個(gè)地址越界中斷，進(jìn)入：可能產(chǎn)生一個(gè)地址越界中斷，進(jìn)入相應(yīng)的中斷處理例程執(zhí)行。一般地，當(dāng)?shù)刂吩较鄳?yīng)的中斷處理

16、例程執(zhí)行。一般地，當(dāng)?shù)刂吩浇缰袛嗵幚硗戤?，該進(jìn)程將異常結(jié)束。界中斷處理完畢，該進(jìn)程將異常結(jié)束。 操作合法性檢查操作合法性檢查：如果屬于非法操作，產(chǎn)生非：如果屬于非法操作，產(chǎn)生非法訪問中斷，這時(shí)也會讓進(jìn)程異常終止。法訪問中斷，這時(shí)也會讓進(jìn)程異常終止。 缺段處理缺段處理：執(zhí)行進(jìn)程被阻塞。并產(chǎn)生一個(gè)中斷：執(zhí)行進(jìn)程被阻塞。并產(chǎn)生一個(gè)中斷信號，處理機(jī)執(zhí)行缺段中斷處理例程。信號，處理機(jī)執(zhí)行缺段中斷處理例程。圖圖3.31 虛擬存儲分段系統(tǒng)地址變換過程虛擬存儲分段系統(tǒng)地址變換過程物理地址物理地址段基址段基址 偏移量偏移量更新快表更新快表否否非法訪問中斷非法訪問中斷是是是是否否是是越界中斷處理越界中斷處理訪問段

17、表訪問段表段號段號 偏移量偏移量邏輯地址邏輯地址檢索快表檢索快表否否是是缺段中斷處理缺段中斷處理否否更新段表更新段表？命中？命中？段在內(nèi)存？段在內(nèi)存？地址越界？地址越界？合法訪問？合法訪問圖圖3.31 虛擬存儲分段系統(tǒng)中的缺段中斷的處理過程虛擬存儲分段系統(tǒng)中的缺段中斷的處理過程換出一個(gè)或幾個(gè)段換出一個(gè)或幾個(gè)段形成一個(gè)合適空閑區(qū)形成一個(gè)合適空閑區(qū)返回返回修改段表、空閑分區(qū)表修改段表、空閑分區(qū)表從外存讀入段從外存讀入段s喚醒進(jìn)程喚醒進(jìn)程是是拼接外零頭，形成拼接外零頭，形成一個(gè)合適的空閑區(qū)一個(gè)合適的空閑區(qū)是是段段s不在內(nèi)存不在內(nèi)存阻塞執(zhí)行進(jìn)程阻塞執(zhí)行進(jìn)程內(nèi)存中有合內(nèi)存中有合適的空閑區(qū)適的空閑區(qū)嗎？嗎

18、？否否空閑區(qū)容量空閑區(qū)容量總和能否滿總和能否滿足？足？否否虛擬存儲段頁式技術(shù)虛擬存儲段頁式技術(shù) 虛擬存儲段頁式系統(tǒng)中，程序和數(shù)據(jù)通常以頁虛擬存儲段頁式系統(tǒng)中，程序和數(shù)據(jù)通常以頁面為單位被系統(tǒng)裝入和移出內(nèi)存。面為單位被系統(tǒng)裝入和移出內(nèi)存。 因此，一般不需要在段表項(xiàng)中增加因此，一般不需要在段表項(xiàng)中增加“存在存在”字字段和段和“修改修改”字段，而將它們放在頁表中。字段，而將它們放在頁表中。 段表中需要保留基于段的保護(hù)與存儲共享等目段表中需要保留基于段的保護(hù)與存儲共享等目的的存取控制信息，頁表中設(shè)置基于頁的控制的的存取控制信息，頁表中設(shè)置基于頁的控制信息。信息。 地址變換地址變換 首先，通過根據(jù)段號和

19、頁號，查找首先，通過根據(jù)段號和頁號，查找快表快表中是否中是否存在對應(yīng)的頁表項(xiàng)。存在對應(yīng)的頁表項(xiàng)。 若快表中不存在該頁表項(xiàng)，則再查找若快表中不存在該頁表項(xiàng)，則再查找段表段表。然。然后，檢索段號對應(yīng)的段表項(xiàng)，找到對應(yīng)段的頁后，檢索段號對應(yīng)的段表項(xiàng)，找到對應(yīng)段的頁表起始地址。表起始地址。 再根據(jù)頁號檢索該再根據(jù)頁號檢索該頁表頁表，檢查對應(yīng)頁面是否在，檢查對應(yīng)頁面是否在內(nèi)存。若該頁面內(nèi)存。若該頁面不在內(nèi)存不在內(nèi)存，啟動(dòng)，啟動(dòng)缺頁中斷缺頁中斷處理處理例程，裝入需要的頁面，并例程，裝入需要的頁面，并更新頁表和快表更新頁表和快表。若該頁面已經(jīng)在內(nèi)存中，將對應(yīng)的頁表項(xiàng)插入若該頁面已經(jīng)在內(nèi)存中，將對應(yīng)的頁表項(xiàng)插

20、入快表中，快表中，更新快表更新快表。 若快表中存在該表項(xiàng)，則直接取出其中的若快表中存在該表項(xiàng)，則直接取出其中的頁框頁框號，加上頁內(nèi)偏移量，計(jì)算出物理地址號，加上頁內(nèi)偏移量，計(jì)算出物理地址。 圖圖3.32 虛擬存儲分頁系統(tǒng)地址變換過程虛擬存儲分頁系統(tǒng)地址變換過程更新頁表更新頁表缺頁中斷處理缺頁中斷處理物理地址物理地址頁框號頁框號偏移量偏移量更新快表更新快表是是否否訪問段表訪問段表訪問頁表訪問頁表檢索快表檢索快表段號段號頁內(nèi)偏移量頁內(nèi)偏移量邏輯地址邏輯地址段內(nèi)頁號段內(nèi)頁號否否是是？命中？命中？頁在內(nèi)存？頁在內(nèi)存虛擬存儲系統(tǒng)的軟件策略虛擬存儲系統(tǒng)的軟件策略 現(xiàn)代操作系統(tǒng)幾乎都采用虛擬存儲管理系統(tǒng)現(xiàn)代

21、操作系統(tǒng)幾乎都采用虛擬存儲管理系統(tǒng) 一些特殊的操作系統(tǒng)和一些較老的操作系統(tǒng)沒一些特殊的操作系統(tǒng)和一些較老的操作系統(tǒng)沒有采用虛擬存儲技術(shù)。例如，有采用虛擬存儲技術(shù)。例如，MS DOS和早期和早期的的UNIX操作系統(tǒng)等。操作系統(tǒng)等。 大多采用分段與分頁相結(jié)合的段頁式管理系統(tǒng)。大多采用分段與分頁相結(jié)合的段頁式管理系統(tǒng)。 下面以分頁存儲管理為例，介紹虛擬存儲系統(tǒng)下面以分頁存儲管理為例，介紹虛擬存儲系統(tǒng)采用的軟件策略。采用的軟件策略。虛擬存儲系統(tǒng)的軟件策略虛擬存儲系統(tǒng)的軟件策略 駐 留 集 管 理駐 留 集 管 理 ( R e s i d e n t S e t Management) 放置策略放置策略

22、(Placement Policy) 獲取策略獲取策略(Fetch Policy) 置換策略置換策略(Replacement Policy) 清除策略清除策略(Cleaning Policy) 負(fù)載控制負(fù)載控制(Load Control)駐留集管理駐留集管理 進(jìn)程的進(jìn)程的駐留集駐留集指，虛擬存儲系統(tǒng)中，每指，虛擬存儲系統(tǒng)中，每個(gè)進(jìn)程駐留在內(nèi)存的頁面集合，或進(jìn)程個(gè)進(jìn)程駐留在內(nèi)存的頁面集合，或進(jìn)程分到的物理頁框集合。分到的物理頁框集合。 駐留集管理主要解決的問題是，系統(tǒng)應(yīng)駐留集管理主要解決的問題是，系統(tǒng)應(yīng)當(dāng)為每個(gè)活躍進(jìn)程分配當(dāng)為每個(gè)活躍進(jìn)程分配多少個(gè)頁框多少個(gè)頁框。影響頁框分配的主要因素影響頁框分

23、配的主要因素 分配給每個(gè)活躍進(jìn)程的頁框數(shù)分配給每個(gè)活躍進(jìn)程的頁框數(shù)越少越少，同，同時(shí)駐留內(nèi)存的活躍進(jìn)程數(shù)就時(shí)駐留內(nèi)存的活躍進(jìn)程數(shù)就越多越多，進(jìn)程，進(jìn)程調(diào)度程序能調(diào)度就緒進(jìn)程的調(diào)度程序能調(diào)度就緒進(jìn)程的概率就越大。概率就越大。然而，這將導(dǎo)致然而，這將導(dǎo)致進(jìn)程發(fā)生缺頁中斷的進(jìn)程發(fā)生缺頁中斷的概概率較大率較大； 為進(jìn)程分配過多的頁框，并不能顯著地為進(jìn)程分配過多的頁框，并不能顯著地降低其缺頁中斷率。降低其缺頁中斷率。 基本的駐留集管理策略基本的駐留集管理策略 固定分配策略固定分配策略(Fixed-Allocation Policy) 可變分配策略可變分配策略(Variable-Allocation Po

24、licy) 固定分配策略固定分配策略 為每個(gè)進(jìn)程分配為每個(gè)進(jìn)程分配固定數(shù)量固定數(shù)量的頁框。即，的頁框。即，每個(gè)活躍進(jìn)程的駐留集尺寸在運(yùn)行期間每個(gè)活躍進(jìn)程的駐留集尺寸在運(yùn)行期間固定不變固定不變。 為進(jìn)程分配為進(jìn)程分配多少個(gè)多少個(gè)頁框是合理的呢？頁框是合理的呢？ 可以由系統(tǒng)根據(jù)進(jìn)程的類型確定，也可可以由系統(tǒng)根據(jù)進(jìn)程的類型確定，也可以由編程人員或系統(tǒng)管理員指定。以由編程人員或系統(tǒng)管理員指定?？勺兎峙洳呗钥勺兎峙洳呗?為每個(gè)活躍進(jìn)程分配的頁框數(shù)在進(jìn)程的生命周為每個(gè)活躍進(jìn)程分配的頁框數(shù)在進(jìn)程的生命周期內(nèi)是期內(nèi)是可變的可變的。即，系統(tǒng)可以首先給進(jìn)程分配。即，系統(tǒng)可以首先給進(jìn)程分配一定數(shù)量的頁框。進(jìn)程運(yùn)行期

25、間，可以一定數(shù)量的頁框。進(jìn)程運(yùn)行期間，可以增加或增加或減少減少頁框。頁框。 系統(tǒng)可以根據(jù)進(jìn)程的系統(tǒng)可以根據(jù)進(jìn)程的缺頁率缺頁率調(diào)整進(jìn)程的駐留集調(diào)整進(jìn)程的駐留集。 當(dāng)進(jìn)程的缺頁率很高時(shí)，駐留集太小，需要當(dāng)進(jìn)程的缺頁率很高時(shí)，駐留集太小，需要增加增加頁框；頁框； 當(dāng)缺頁率一段時(shí)間內(nèi)都保持很低時(shí)，可以在不會當(dāng)缺頁率一段時(shí)間內(nèi)都保持很低時(shí)，可以在不會明顯增加進(jìn)程缺頁率的前提下，明顯增加進(jìn)程缺頁率的前提下，回收回收其一部分頁框，其一部分頁框，減小進(jìn)程的駐留集。減小進(jìn)程的駐留集?？勺兎峙淇勺兎峙?vs.固定分配固定分配 可變分配策略比固定分配策略更靈活，既可以可變分配策略比固定分配策略更靈活，既可以提高系統(tǒng)

26、的吞吐量，又能保證內(nèi)存的有效利用。提高系統(tǒng)的吞吐量，又能保證內(nèi)存的有效利用。 可變分配要求統(tǒng)計(jì)進(jìn)程的缺頁率，增加系統(tǒng)額可變分配要求統(tǒng)計(jì)進(jìn)程的缺頁率，增加系統(tǒng)額外開銷。而準(zhǔn)確判斷進(jìn)程缺頁率的高低，確定外開銷。而準(zhǔn)確判斷進(jìn)程缺頁率的高低，確定缺頁率的閾值是非常困難的。缺頁率的閾值是非常困難的。 可變分配策略不僅需要操作系統(tǒng)軟件專門的支可變分配策略不僅需要操作系統(tǒng)軟件專門的支持，而且，還需要處理機(jī)平臺提供的硬件支持持，而且，還需要處理機(jī)平臺提供的硬件支持頁面放置策略頁面放置策略 解決的問題：系統(tǒng)應(yīng)當(dāng)在內(nèi)存的解決的問題：系統(tǒng)應(yīng)當(dāng)在內(nèi)存的什么位置什么位置為活為活躍進(jìn)程分配頁框？躍進(jìn)程分配頁框？ 一般地，

27、對于一個(gè)分頁系統(tǒng)或段頁式系統(tǒng)，將一般地，對于一個(gè)分頁系統(tǒng)或段頁式系統(tǒng)，將進(jìn)程的一個(gè)頁面裝入哪一個(gè)頁框進(jìn)程的一個(gè)頁面裝入哪一個(gè)頁框無關(guān)緊要無關(guān)緊要。 對于分段系統(tǒng)，對于分段系統(tǒng)，需要考慮需要考慮將一個(gè)程序段裝入哪將一個(gè)程序段裝入哪一個(gè)合適的分區(qū)中，可采用的分配算法包括首一個(gè)合適的分區(qū)中，可采用的分配算法包括首次適應(yīng)法、下次適應(yīng)法、最佳適應(yīng)法或最差適次適應(yīng)法、下次適應(yīng)法、最佳適應(yīng)法或最差適應(yīng)法等。應(yīng)法等。頁面獲取策略頁面獲取策略 解決的問題：系統(tǒng)應(yīng)當(dāng)在解決的問題：系統(tǒng)應(yīng)當(dāng)在何時(shí)何時(shí)把一個(gè)頁把一個(gè)頁面裝入內(nèi)存？面裝入內(nèi)存？ 請求調(diào)頁請求調(diào)頁 (Demand Paging) 預(yù)調(diào)頁預(yù)調(diào)頁 (Prepa

28、ging)請求調(diào)頁請求調(diào)頁 僅當(dāng)進(jìn)程執(zhí)行過程中，通過檢查頁表發(fā)現(xiàn)相應(yīng)僅當(dāng)進(jìn)程執(zhí)行過程中，通過檢查頁表發(fā)現(xiàn)相應(yīng)頁面不在內(nèi)存時(shí)，才裝入該頁面。頁面不在內(nèi)存時(shí)，才裝入該頁面。 當(dāng)進(jìn)程剛開始執(zhí)行時(shí)，由于預(yù)先未裝入進(jìn)程的當(dāng)進(jìn)程剛開始執(zhí)行時(shí)，由于預(yù)先未裝入進(jìn)程的頁面，故需要頻繁地申請裝入頁面。執(zhí)行一段頁面，故需要頻繁地申請裝入頁面。執(zhí)行一段時(shí)間以后，進(jìn)程的缺頁率將下降。時(shí)間以后，進(jìn)程的缺頁率將下降。 采用請求調(diào)頁方式，一次裝入請求的一個(gè)頁面，采用請求調(diào)頁方式，一次裝入請求的一個(gè)頁面，磁盤磁盤I/O的啟動(dòng)頻率較高，系統(tǒng)的開銷較大。的啟動(dòng)頻率較高，系統(tǒng)的開銷較大。預(yù)調(diào)頁方式預(yù)調(diào)頁方式 當(dāng)進(jìn)程創(chuàng)建時(shí)，預(yù)先為進(jìn)程

29、裝入多個(gè)頁面。當(dāng)進(jìn)程創(chuàng)建時(shí)，預(yù)先為進(jìn)程裝入多個(gè)頁面。 缺頁中斷時(shí)，系統(tǒng)為進(jìn)程裝入指定的頁面以及缺頁中斷時(shí)，系統(tǒng)為進(jìn)程裝入指定的頁面以及與之相臨的多個(gè)頁面。與之相臨的多個(gè)頁面。 若局部性很差，預(yù)先裝入的很多頁面不會很快若局部性很差，預(yù)先裝入的很多頁面不會很快被引用，并會占用大量的內(nèi)存空間，反而降低被引用，并會占用大量的內(nèi)存空間，反而降低系統(tǒng)的效率系統(tǒng)的效率頁面置換策略頁面置換策略 當(dāng)發(fā)生缺頁中斷且無足夠的內(nèi)存空間時(shí)，需要當(dāng)發(fā)生缺頁中斷且無足夠的內(nèi)存空間時(shí)，需要置換已有的某些（個(gè)）頁面。置換已有的某些（個(gè)）頁面。 應(yīng)該解決的基本問題：應(yīng)該解決的基本問題： 當(dāng)系統(tǒng)欲把一個(gè)頁面裝入內(nèi)存時(shí)，應(yīng)當(dāng)在當(dāng)系統(tǒng)

30、欲把一個(gè)頁面裝入內(nèi)存時(shí)，應(yīng)當(dāng)在什么范圍什么范圍內(nèi)判斷已經(jīng)沒有空閑頁框供分配？內(nèi)判斷已經(jīng)沒有空閑頁框供分配？ 當(dāng)指定的范圍內(nèi)沒有空閑頁框時(shí)，應(yīng)當(dāng)從當(dāng)指定的范圍內(nèi)沒有空閑頁框時(shí)，應(yīng)當(dāng)從指定的范圍內(nèi)選擇指定的范圍內(nèi)選擇哪個(gè)頁面哪個(gè)頁面移出內(nèi)存？移出內(nèi)存？ 局部置換策略局部置換策略 可以采用可以采用局部置換局部置換或或全局置換全局置換策略。策略。 局部置換局部置換：系統(tǒng)在進(jìn)程：系統(tǒng)在進(jìn)程自身的駐留集中自身的駐留集中判斷當(dāng)前是否存在空閑頁框，并在其中判斷當(dāng)前是否存在空閑頁框，并在其中進(jìn)行置換。進(jìn)行置換。全局置換策略全局置換策略 在在整個(gè)內(nèi)存空間內(nèi)整個(gè)內(nèi)存空間內(nèi)判斷有無空閑頁框，判斷有無空閑頁框，并允許從

31、其它進(jìn)程的駐留集中選擇一個(gè)并允許從其它進(jìn)程的駐留集中選擇一個(gè)頁面換出內(nèi)存。頁面換出內(nèi)存。分配模式分配模式 vs. 置換模式置換模式 固定分配策略固定分配策略 局部置換策略局部置換策略 全局置換策略全局置換策略 可變分配策略可變分配策略 可變分配策略可變分配策略+局部置換策略局部置換策略 即可增加或減少分配給每個(gè)活躍進(jìn)程的頁即可增加或減少分配給每個(gè)活躍進(jìn)程的頁框數(shù)；當(dāng)進(jìn)程的頁框全部用完，而需要裝入一框數(shù)；當(dāng)進(jìn)程的頁框全部用完，而需要裝入一個(gè)新的頁面時(shí)，系統(tǒng)將在該進(jìn)程的當(dāng)前駐留集個(gè)新的頁面時(shí)，系統(tǒng)將在該進(jìn)程的當(dāng)前駐留集中選擇一個(gè)頁面換出內(nèi)存。中選擇一個(gè)頁面換出內(nèi)存。 頁面置換策略頁面置換策略 頁面

32、置換算法：在指定的置換范圍內(nèi)，頁面置換算法：在指定的置換范圍內(nèi)，決定將哪一個(gè)頁面換出內(nèi)存。決定將哪一個(gè)頁面換出內(nèi)存。 置換算法的好壞將直接影響系統(tǒng)的性能，置換算法的好壞將直接影響系統(tǒng)的性能，不適當(dāng)?shù)闹脫Q算法可能導(dǎo)致系統(tǒng)出現(xiàn)不適當(dāng)?shù)闹脫Q算法可能導(dǎo)致系統(tǒng)出現(xiàn)“抖動(dòng)抖動(dòng)”現(xiàn)象?，F(xiàn)象。 常用的頁面置換算法：最佳置換算法、常用的頁面置換算法：最佳置換算法、最近最少使用算法、先進(jìn)先出算法和時(shí)最近最少使用算法、先進(jìn)先出算法和時(shí)鐘算法等鐘算法等最佳置換算法最佳置換算法(Optimal Algorithm，OPT) 基本思想：被置換的頁面是將來不再訪問，或基本思想：被置換的頁面是將來不再訪問，或在最遠(yuǎn)的將來才被

33、訪問的頁面。在最遠(yuǎn)的將來才被訪問的頁面。 若采用若采用固定分配策略，最佳置換算法可以保證固定分配策略，最佳置換算法可以保證系統(tǒng)的缺頁率最低。系統(tǒng)的缺頁率最低。 但是，無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干頁面中，但是，無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干頁面中，哪一個(gè)頁面是將來不再訪問的，甚至最長時(shí)間哪一個(gè)頁面是將來不再訪問的，甚至最長時(shí)間內(nèi)將不再被訪問的，因而該算法是無法實(shí)現(xiàn)的。內(nèi)將不再被訪問的，因而該算法是無法實(shí)現(xiàn)的。 該算法可以用于該算法可以用于評價(jià)其它置換算法評價(jià)其它置換算法的性能。的性能。示例示例 假設(shè)假設(shè)系統(tǒng)分配給某進(jìn)程系統(tǒng)分配給某進(jìn)程3個(gè)頁框，且進(jìn)個(gè)頁框，且進(jìn)程開始運(yùn)行時(shí)，這程開始運(yùn)行時(shí)，這3個(gè)頁

34、框是空的。個(gè)頁框是空的。 考慮下列頁面號引用序列：考慮下列頁面號引用序列： 2、3、2、1、5、2、4、5、3、2、5、222323231235235435435435235235235頁面引用序列頁面引用序列 2 3 2 1 5 2 4 5 3 2 5 2 F F F F F F 12次頁面引用次頁面引用 6次缺頁中斷（次缺頁中斷（F和和F） 3次頁面置換（次頁面置換（F）圖圖3.33 采用采用OPT置換算法的缺頁中斷與頁面置換過程置換算法的缺頁中斷與頁面置換過程 據(jù)局部性原理，如果一個(gè)頁面最近被訪問過，據(jù)局部性原理，如果一個(gè)頁面最近被訪問過，那么，它將在不久的將來再次被訪問。那么，它將在不

35、久的將來再次被訪問。 如果一個(gè)頁面已經(jīng)很長時(shí)間未被訪問過，則在如果一個(gè)頁面已經(jīng)很長時(shí)間未被訪問過，則在很久的將來，它將不會被訪問。很久的將來，它將不會被訪問。 因此，可以根據(jù)頁面的使用歷史，判斷其將來因此，可以根據(jù)頁面的使用歷史，判斷其將來的行為。的行為。最近最少使用置換算法最近最少使用置換算法(Least Recently Used Algorithm，LRU) LRU根據(jù)頁面裝入內(nèi)存以后的使用情況，選擇根據(jù)頁面裝入內(nèi)存以后的使用情況，選擇淘汰最近最久未被使用的一個(gè)頁面。淘汰最近最久未被使用的一個(gè)頁面。 該算法的性能接近該算法的性能接近OPT算法，但實(shí)現(xiàn)較困難。算法，但實(shí)現(xiàn)較困難。 一種方法

36、：為每一個(gè)頁面增加一個(gè)訪問字段，一種方法：為每一個(gè)頁面增加一個(gè)訪問字段，用以標(biāo)注該頁最后一次被訪問的時(shí)間。需要選用以標(biāo)注該頁最后一次被訪問的時(shí)間。需要選擇淘汰頁面時(shí)，比較置換范圍內(nèi)的所有頁面的擇淘汰頁面時(shí)，比較置換范圍內(nèi)的所有頁面的最后訪問時(shí)間，選擇訪問時(shí)間最遠(yuǎn)的哪個(gè)頁面。最后訪問時(shí)間，選擇訪問時(shí)間最遠(yuǎn)的哪個(gè)頁面。 實(shí)現(xiàn)該方法的開銷非常大，不易實(shí)現(xiàn)。實(shí)現(xiàn)該方法的開銷非常大，不易實(shí)現(xiàn)。LRU置換算法的實(shí)現(xiàn)置換算法的實(shí)現(xiàn) 另一種方法：將訪問頁面組織在一個(gè)堆另一種方法：將訪問頁面組織在一個(gè)堆棧中，最近訪問的頁面位于棧頂，棧底棧中，最近訪問的頁面位于棧頂，棧底的頁面即是最久未被訪問的。的頁面即是最久未

37、被訪問的。 實(shí)踐證明，該方法的實(shí)現(xiàn)仍然很困難，實(shí)踐證明，該方法的實(shí)現(xiàn)仍然很困難，系統(tǒng)付出的代價(jià)也非常大。系統(tǒng)付出的代價(jià)也非常大。 22323231251251254254354352352352頁面引用序列頁面引用序列 2 3 2 1 5 2 4 5 3 2 5 2 F F F F F F F 12次頁面引用次頁面引用 7次缺頁中斷（次缺頁中斷（F和和F） 4次頁面置換（次頁面置換（F）圖圖3.34 采用采用LRU置換算法的缺頁中斷與頁面置換過程置換算法的缺頁中斷與頁面置換過程先進(jìn)先出置換算法先進(jìn)先出置換算法(First-in First-out Algorithm，F(xiàn)IFO) 淘汰最先進(jìn)入內(nèi)

38、存的頁面，即選擇在內(nèi)淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。存中駐留時(shí)間最久的頁面予以淘汰。 實(shí)現(xiàn)時(shí)，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的實(shí)現(xiàn)時(shí)，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)頁面按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，使它總是指向最老的頁面。置一個(gè)指針，使它總是指向最老的頁面。22323231531521524524324324354352頁面引用序列頁面引用序列 2 3 2 1 5 2 4 5 3 2 5 2 F F F F F F F F F12次頁面引用次頁面引用 9次缺頁中斷（次缺頁中斷（F和和F） 6次頁面置換（次頁面置換（F）圖圖3

39、.35 采用采用FIFO置換算法的缺頁中斷與頁面置換過程置換算法的缺頁中斷與頁面置換過程先進(jìn)先出置換算法先進(jìn)先出置換算法(First-in First-out Algorithm，F(xiàn)IFO) 該算法與進(jìn)程實(shí)際的運(yùn)行規(guī)律不相適應(yīng)，該算法與進(jìn)程實(shí)際的運(yùn)行規(guī)律不相適應(yīng)，進(jìn)程中的某些程序代碼或數(shù)據(jù)可能需要進(jìn)程中的某些程序代碼或數(shù)據(jù)可能需要高頻使用，該算法將導(dǎo)致這種類型的頁高頻使用，該算法將導(dǎo)致這種類型的頁面被反復(fù)地?fù)Q進(jìn)換出，從而降低系統(tǒng)性面被反復(fù)地?fù)Q進(jìn)換出，從而降低系統(tǒng)性能。能。Clock時(shí)鐘置換算法時(shí)鐘置換算法 內(nèi)存中的每個(gè)頁面配置一個(gè)內(nèi)存中的每個(gè)頁面配置一個(gè)使用位使用位（U位）；位）； 當(dāng)頁面裝入

40、內(nèi)存時(shí)，或被引用時(shí)，其當(dāng)頁面裝入內(nèi)存時(shí)，或被引用時(shí)，其U位將被設(shè)位將被設(shè)置為置為1； 系統(tǒng)將置換范圍內(nèi)的所有頁面組成一系統(tǒng)將置換范圍內(nèi)的所有頁面組成一 個(gè)循環(huán)隊(duì)個(gè)循環(huán)隊(duì)列，并為其設(shè)置一個(gè)列，并為其設(shè)置一個(gè)掃描指針掃描指針； 未進(jìn)行頁面置換時(shí)，掃描指針總是指向上一次進(jìn)未進(jìn)行頁面置換時(shí)，掃描指針總是指向上一次進(jìn)行頁面置換時(shí)被置換頁面所在位置的下一個(gè)位置。行頁面置換時(shí)被置換頁面所在位置的下一個(gè)位置。時(shí)鐘置換算法（續(xù)）時(shí)鐘置換算法（續(xù)） 當(dāng)需要進(jìn)行頁面置換時(shí)，系統(tǒng)將移動(dòng)掃描指針，搜索置換當(dāng)需要進(jìn)行頁面置換時(shí)，系統(tǒng)將移動(dòng)掃描指針，搜索置換范圍內(nèi)的各個(gè)頁面，以便找到一個(gè)范圍內(nèi)的各個(gè)頁面，以便找到一個(gè)U位為

41、位為0的頁面：的頁面： 如果當(dāng)前掃描指針?biāo)赶虻捻撁娴娜绻?dāng)前掃描指針?biāo)赶虻捻撁娴腢位為位為1，那么系統(tǒng)將把該頁面，那么系統(tǒng)將把該頁面的的U位設(shè)置為位設(shè)置為0，同時(shí)把掃描指針移到下一個(gè)位置，繼續(xù)搜索；，同時(shí)把掃描指針移到下一個(gè)位置，繼續(xù)搜索； 如果當(dāng)前掃描指針?biāo)赶虻捻撁娴娜绻?dāng)前掃描指針?biāo)赶虻捻撁娴腢位為位為0，那么系統(tǒng)將把該頁面，那么系統(tǒng)將把該頁面作為被置換頁面，同時(shí)把掃描指針移到下一個(gè)位置，停止搜索。作為被置換頁面，同時(shí)把掃描指針移到下一個(gè)位置，停止搜索。頁頁6U = 1頁頁123U = 1頁頁30U = 0頁頁616U = 0頁頁77U = 1頁頁24U = 1頁頁110U = 1

42、頁頁16U = 0頁頁76U = 0.01234567n-1(b) 用用77號頁面替換號頁面替換23號頁面以后的情況號頁面以后的情況頁頁6U = 1頁頁123U = 1頁頁30U = 1頁頁616U = 1頁頁23U = 0頁頁24U = 1頁頁110U = 1頁頁16U = 0頁頁76U = 0.01234567n-1(a) 當(dāng)前頁面循環(huán)隊(duì)列情況當(dāng)前頁面循環(huán)隊(duì)列情況2*2*3*2*3*2*3*1*5*315*2*15*2*4*5*2*4*3*243*2*43*25*3*2*5*頁面引用序列頁面引用序列 2 3 2 1 5 2 4 5 3 2 5 2F F F F F F F F 12次頁面引

43、用次頁面引用 8次缺頁中斷（次缺頁中斷（F和和F） 5次頁面置換次頁面置換（F）圖圖3.37 采用采用Clock置換算法的缺頁中斷與頁面置換過程置換算法的缺頁中斷與頁面置換過程時(shí)鐘置換算法的改進(jìn)時(shí)鐘置換算法的改進(jìn) 系統(tǒng)把一個(gè)頁面移出內(nèi)存時(shí)，如果該頁面駐留內(nèi)存期間沒有系統(tǒng)把一個(gè)頁面移出內(nèi)存時(shí)，如果該頁面駐留內(nèi)存期間沒有被修改過，那么不必把它寫回輔存，否則系統(tǒng)必須把它寫回被修改過，那么不必把它寫回輔存，否則系統(tǒng)必須把它寫回輔存。這表明，換出未修改過的頁面比換出被修改過的頁面輔存。這表明，換出未修改過的頁面比換出被修改過的頁面開銷小。開銷小。 顯然，我們可以依據(jù)上述結(jié)論改進(jìn)顯然，我們可以依據(jù)上述結(jié)論

44、改進(jìn)CLOCK算法。改進(jìn)后的算法。改進(jìn)后的CLOCK算法將在置換范圍內(nèi)算法將在置換范圍內(nèi)首選首選在最近沒有被使用過、在在最近沒有被使用過、在駐留內(nèi)存期間沒有被修改過的頁面作為被置換頁面。駐留內(nèi)存期間沒有被修改過的頁面作為被置換頁面。時(shí)鐘置換算法的改進(jìn)時(shí)鐘置換算法的改進(jìn)(續(xù)續(xù)1) 為了改進(jìn)為了改進(jìn)CLOCK算法，系統(tǒng)將為內(nèi)存的每個(gè)頁面配置一個(gè)算法，系統(tǒng)將為內(nèi)存的每個(gè)頁面配置一個(gè)修改位修改位（簡稱為（簡稱為M位）。位）。 改進(jìn)后的改進(jìn)后的CLOCK算法在置換范圍內(nèi)選擇被置換頁面時(shí)將同算法在置換范圍內(nèi)選擇被置換頁面時(shí)將同時(shí)考慮時(shí)考慮U位和位和M位。位。 一個(gè)頁面的一個(gè)頁面的U位與位與M位共有四種組合

45、：位共有四種組合： U=0，M=0：最近沒有被使用過，駐留內(nèi)存期間也沒有被修改過；：最近沒有被使用過，駐留內(nèi)存期間也沒有被修改過； U=1，M=0：最近被使用過，但駐留內(nèi)存期間沒有被修改過；：最近被使用過，但駐留內(nèi)存期間沒有被修改過； U=0，M=1：最近沒有被使用過，但駐留內(nèi)存期間被修改過；：最近沒有被使用過，但駐留內(nèi)存期間被修改過； U=1，M=1：最近被使用過，駐留內(nèi)存期間也被修改過；：最近被使用過，駐留內(nèi)存期間也被修改過；時(shí)鐘置換算法的改進(jìn)時(shí)鐘置換算法的改進(jìn)(續(xù)續(xù)2) 改進(jìn)后的改進(jìn)后的 CLOCK 算法將按下列步驟選擇被置換頁面：算法將按下列步驟選擇被置換頁面：1、從掃描指針的當(dāng)前位置

46、開始，搜索、從掃描指針的當(dāng)前位置開始，搜索 U=0且且 M=0 的頁的頁面。此次搜索不會修改置換范圍內(nèi)的任何一個(gè)頁面的面。此次搜索不會修改置換范圍內(nèi)的任何一個(gè)頁面的U位。位。若找到第一個(gè)若找到第一個(gè)U=0且且M=0的頁面，則把該頁面選作被置的頁面，則把該頁面選作被置換頁面，終止算法。換頁面，終止算法。2、如果第一步?jīng)]有成功，、如果第一步?jīng)]有成功， 那么掃描指針將回到原位。那么掃描指針將回到原位。 再再次搜索次搜索U=0但但M=1的頁面。如果遇到的頁面。如果遇到U位為位為1的頁面，將的頁面，將其其U位修改為位修改為0。倘若找到第一個(gè)。倘若找到第一個(gè)U=0但但M=1的頁面，將的頁面，將該頁面選作被

47、置換頁面，終止算法。該頁面選作被置換頁面，終止算法。3、如果第二步也沒有成功，、如果第二步也沒有成功， 那么掃描指針將再次回到原那么掃描指針將再次回到原位，且置換范圍內(nèi)的所有頁面的位，且置換范圍內(nèi)的所有頁面的U位均為位均為0。此時(shí)，算法。此時(shí)，算法將返回第一步繼續(xù)執(zhí)行。將返回第一步繼續(xù)執(zhí)行。頁頁10U=1 M=0頁頁565U=1 M=1頁頁20U=1 M=0頁頁16U=1 M=1頁頁19U=0 M=0頁頁566U=1 M=0 頁頁110 U=1 M=1頁頁111U=0 M=1頁頁112U=0 M=1.01234567n-1圖圖3.38 改進(jìn)型改進(jìn)型clock算法：頁面置換之前的情形算法：頁面置

48、換之前的情形頁面清除策略頁面清除策略 頁面清除是指，將由頁面置換算法選擇頁面清除是指，將由頁面置換算法選擇的被修改的置換頁面的被修改的置換頁面保存到外存保存到外存。 頁面清除策略需要決定系統(tǒng)頁面清除策略需要決定系統(tǒng)何時(shí)何時(shí)把一個(gè)把一個(gè)被置換頁面寫回外存。被置換頁面寫回外存。 最直接的頁面清除時(shí)機(jī)是，只有當(dāng)一個(gè)最直接的頁面清除時(shí)機(jī)是，只有當(dāng)一個(gè)頁被選中作為置換頁時(shí)，才被寫回外存，頁被選中作為置換頁時(shí)，才被寫回外存，稱之為稱之為請求清除策略請求清除策略。 若被選中的置換頁面自進(jìn)入內(nèi)存以來被修改過，若被選中的置換頁面自進(jìn)入內(nèi)存以來被修改過，則需要首先將該頁面內(nèi)容寫回外存保存起來，則需要首先將該頁面內(nèi)

49、容寫回外存保存起來，然后，裝入進(jìn)程需要的新頁內(nèi)容。然后，裝入進(jìn)程需要的新頁內(nèi)容。 可見，采用請求清除策略時(shí)，寫出一個(gè)被修改可見，采用請求清除策略時(shí)，寫出一個(gè)被修改過的頁面與讀入一個(gè)新頁的操作是過的頁面與讀入一個(gè)新頁的操作是成對出現(xiàn)成對出現(xiàn)的，的，而且，寫出操作先于讀入操作。而且，寫出操作先于讀入操作。 所以，當(dāng)正在執(zhí)行的進(jìn)程發(fā)生缺頁中斷時(shí)，需所以，當(dāng)正在執(zhí)行的進(jìn)程發(fā)生缺頁中斷時(shí)，需要阻塞等待一個(gè)頁面的寫出和另一個(gè)頁面的讀要阻塞等待一個(gè)頁面的寫出和另一個(gè)頁面的讀入，這可能降低處理機(jī)的使用效率。入，這可能降低處理機(jī)的使用效率。 一種有效的頁面清除策略是結(jié)合一種有效的頁面清除策略是結(jié)合頁緩沖頁緩沖（

50、Page Buffering）技術(shù)。）技術(shù)。 當(dāng)發(fā)生缺頁中斷時(shí)，不必首先寫出置換當(dāng)發(fā)生缺頁中斷時(shí)，不必首先寫出置換頁，然后讀入新頁。而是，將被選中的頁，然后讀入新頁。而是，將被選中的置換頁置換頁暫時(shí)保留暫時(shí)保留在內(nèi)存的一個(gè)緩沖區(qū)，在內(nèi)存的一個(gè)緩沖區(qū)，在以后某個(gè)合適的時(shí)候?qū)⑦@些被置換頁在以后某個(gè)合適的時(shí)候?qū)⑦@些被置換頁批量寫出批量寫出到外存。到外存。 減少磁盤減少磁盤I/O的次數(shù)，提高處理機(jī)的效率。的次數(shù)，提高處理機(jī)的效率。頁緩沖技術(shù)的實(shí)現(xiàn)頁緩沖技術(shù)的實(shí)現(xiàn) 需要兩個(gè)鏈表：需要兩個(gè)鏈表：未修改頁鏈表未修改頁鏈表和和修改頁鏈表修改頁鏈表。 當(dāng)選中一個(gè)被修改過的頁作為置換頁時(shí)，不需當(dāng)選中一個(gè)被修改過的

51、頁作為置換頁時(shí)，不需要立即、真正地將其寫出到外存，而是首先將要立即、真正地將其寫出到外存，而是首先將其插入到其插入到修改鏈表修改鏈表中緩沖存儲。修改鏈表中的中緩沖存儲。修改鏈表中的頁可以周期性地批量寫出到外存，并移到未修頁可以周期性地批量寫出到外存，并移到未修改表中。改表中。 未修改表未修改表鏈接被選中的未修改置換頁，當(dāng)其中鏈接被選中的未修改置換頁，當(dāng)其中某頁所占用的頁框被新頁占用時(shí)，新頁的內(nèi)容某頁所占用的頁框被新頁占用時(shí)，新頁的內(nèi)容覆蓋置換頁的內(nèi)容，置換頁被真正從內(nèi)存清除。覆蓋置換頁的內(nèi)容，置換頁被真正從內(nèi)存清除。 采用頁緩沖技術(shù)，當(dāng)需要讀入一個(gè)新頁時(shí)，首采用頁緩沖技術(shù)，當(dāng)需要讀入一個(gè)新頁時(shí)

52、，首先檢查先檢查未修改頁鏈表未修改頁鏈表，若該表非空，便可按照，若該表非空，便可按照FIFO方法，將該鏈表頭指向的第一個(gè)頁面占方法，將該鏈表頭指向的第一個(gè)頁面占用的頁框分配給新頁。用的頁框分配給新頁。 如果未修改表為空，檢查修改頁鏈表，將該表如果未修改表為空，檢查修改頁鏈表，將該表中的頁面內(nèi)容批量寫出到外存，并將這些頁移中的頁面內(nèi)容批量寫出到外存，并將這些頁移到未修改表中，按照上述方法重新分配其占用到未修改表中，按照上述方法重新分配其占用的頁框。的頁框。 顯然，采用頁緩沖技術(shù)不僅可以減少寫出頁面顯然，采用頁緩沖技術(shù)不僅可以減少寫出頁面的系統(tǒng)開銷，而且可以減少讀入頁面的開銷。的系統(tǒng)開銷，而且可以

53、減少讀入頁面的開銷。因?yàn)?，?dāng)進(jìn)程再次訪問頁面緩沖區(qū)的頁面時(shí)，因?yàn)椋?dāng)進(jìn)程再次訪問頁面緩沖區(qū)的頁面時(shí)，只需要將對應(yīng)頁面從緩沖區(qū)返回到該進(jìn)程的駐只需要將對應(yīng)頁面從緩沖區(qū)返回到該進(jìn)程的駐留集中，而無須從外存讀入。留集中，而無須從外存讀入。負(fù)載控制負(fù)載控制 多道程序系統(tǒng)允許多個(gè)進(jìn)程同時(shí)駐留內(nèi)多道程序系統(tǒng)允許多個(gè)進(jìn)程同時(shí)駐留內(nèi)存，以提高系統(tǒng)吞吐量和資源利用率。存，以提高系統(tǒng)吞吐量和資源利用率。 然而，如果同時(shí)駐留內(nèi)存的進(jìn)程數(shù)量然而，如果同時(shí)駐留內(nèi)存的進(jìn)程數(shù)量太太多多，每個(gè)進(jìn)程都競爭各自需要的資源，每個(gè)進(jìn)程都競爭各自需要的資源，反而會反而會降低系統(tǒng)效率降低系統(tǒng)效率。負(fù)載控制負(fù)載控制 如果內(nèi)存中如果內(nèi)存中進(jìn)程太多，進(jìn)程太多，將導(dǎo)致每個(gè)進(jìn)程的駐留將導(dǎo)致每個(gè)進(jìn)程的駐留集