計(jì)算機(jī)操作系統(tǒng)_第5章(2016-2017-1)

1、第四章存儲(chǔ)器管理 第五章虛擬存儲(chǔ)器5.1 虛擬虛擬存儲(chǔ)器概述存儲(chǔ)器概述5.2請(qǐng)求分頁(yè)存儲(chǔ)管理方式請(qǐng)求分頁(yè)存儲(chǔ)管理方式5.3頁(yè)面置換算法頁(yè)面置換算法5.4“抖動(dòng)抖動(dòng)”與工作集與工作集5.5請(qǐng)求分段存儲(chǔ)管理方式請(qǐng)求分段存儲(chǔ)管理方式第四章存儲(chǔ)器管理 5.1虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器概述 前面所介紹的各種存儲(chǔ)器管理方式有一個(gè)共同的特點(diǎn)，即它們都要求將一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行，于是，出現(xiàn)了下面這樣兩種情況：(1) 有的作業(yè)很大，其所要求的內(nèi)存空間超過(guò)了內(nèi)存總?cè)萘?，作業(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無(wú)法運(yùn)行。(2) 有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè) 裝入內(nèi)存讓它

2、們先運(yùn)行，而將其它大量的作業(yè)留在外存上等待。 第四章存儲(chǔ)器管理 1.1.常規(guī)存儲(chǔ)器管理方式的特征常規(guī)存儲(chǔ)器管理方式的特征(1) 一次性。常規(guī)存儲(chǔ)管理方式都要求將作業(yè)全部裝入內(nèi)存后方能運(yùn)行。然而，許多作業(yè)在每次運(yùn)行時(shí)，并非其全部程序和數(shù)據(jù)都要用到。5.1.1常規(guī)存儲(chǔ)管理方式的特征和局部性原理常規(guī)存儲(chǔ)管理方式的特征和局部性原理(2) 駐留性。作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。然而，有的程序模塊在運(yùn)行過(guò)一次后就不再需要(運(yùn)行)了。 問(wèn)題：一次性及駐留性在程序運(yùn)行時(shí)是否是必需的問(wèn)題：一次性及駐留性在程序運(yùn)行時(shí)是否是必需的? ? 第四章存儲(chǔ)器管理 2 2局部性原理局部性原理Denni

3、ng.P在1968指出：程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域。他提出了下述幾個(gè)論點(diǎn)：(1) 程序執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過(guò)程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的;(2)在過(guò)程調(diào)用中，程序?qū)?huì)在一段時(shí)間內(nèi)都局限在這些過(guò)程的范圍內(nèi)運(yùn)行； (3) 程序中存在許多循環(huán)結(jié)構(gòu)；(4) 程序中許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，往往都局限于很小的范圍內(nèi)。5.1.1常規(guī)存儲(chǔ)管理方式的特征和局部性原理常規(guī)存儲(chǔ)管理方式的特征和局部性原理第四章存儲(chǔ)器管理 3.3.虛擬存儲(chǔ)器的基本工作情況虛擬存儲(chǔ)器的基本工作情況基于局部性原理，應(yīng)用程序在運(yùn)

4、行之前，僅須將那些當(dāng)前要運(yùn)行的少數(shù)頁(yè)面或段先裝入內(nèi)存便可運(yùn)行，其余部分暫留在盤上。程序在運(yùn)行時(shí)，如果程序所要訪問(wèn)的頁(yè)(段)尚未調(diào)入內(nèi)存，此時(shí)程序應(yīng)利用OS所提供的請(qǐng)求調(diào)頁(yè)(段)功能，將它們調(diào)入內(nèi)存，以使進(jìn)程能繼續(xù)執(zhí)行下去。如果此時(shí)內(nèi)存已滿，則須再利用頁(yè)(段)的置換功能，將內(nèi)存中暫時(shí)不用的頁(yè)(段)調(diào)至盤上，再將要訪問(wèn)的頁(yè)(段)調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。5.1.1常規(guī)存儲(chǔ)管理方式的特征和局部性原理常規(guī)存儲(chǔ)管理方式的特征和局部性原理第四章存儲(chǔ)器管理 5.1.2虛擬存儲(chǔ)器的定義和特征虛擬存儲(chǔ)器的定義和特征 具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)系統(tǒng)。其邏輯容量是內(nèi)存容量

5、和外存容量之和，其運(yùn)行速度接近于內(nèi)存速度。1.1.虛擬存儲(chǔ)器的定義虛擬存儲(chǔ)器的定義2.2.虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器的特征1)多次性. 一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行2)對(duì)換性. 作業(yè)的運(yùn)行過(guò)程中進(jìn)行換進(jìn)、換出3)虛擬性. 能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。第四章存儲(chǔ)器管理 1.1.分頁(yè)請(qǐng)求系統(tǒng)分頁(yè)請(qǐng)求系統(tǒng)在分頁(yè)系統(tǒng)的基礎(chǔ)上增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能。它允許只裝入少數(shù)頁(yè)面的程序(及數(shù)據(jù))，便啟動(dòng)運(yùn)行。以后，再通過(guò)調(diào)頁(yè)功能及頁(yè)面置換功能，陸續(xù)地把即將要運(yùn)行的頁(yè)面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁(yè)面換出到外存上。置換時(shí)以頁(yè)面為單位。為了能實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)和置換功能，系

6、統(tǒng)必須提供必要的硬件支持和相應(yīng)的軟件。 5.1.3虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器建立在離散分配存儲(chǔ)管理方式第四章存儲(chǔ)器管理 2. 請(qǐng)求分段系統(tǒng)請(qǐng)求分段系統(tǒng)在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段及分段置換功能后所形成的段式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入少數(shù)段(而非所有的段)的用戶程序和數(shù)據(jù)，即可啟動(dòng)運(yùn)行。以后再通過(guò)調(diào)段功能和段的置換功能將暫不運(yùn)行的段調(diào)出，同時(shí)調(diào)入即將運(yùn)行的段。置換是以段為單位進(jìn)行的。5.1.3虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法第四章存儲(chǔ)器管理 5.2請(qǐng)求分頁(yè)存儲(chǔ)管理方式請(qǐng)求分頁(yè)存儲(chǔ)管理方式 5.2.1請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)中的硬件支持1.1.請(qǐng)求頁(yè)表機(jī)制

7、請(qǐng)求頁(yè)表機(jī)制在請(qǐng)求分頁(yè)系統(tǒng)中所需要的主要數(shù)據(jù)結(jié)構(gòu)是頁(yè)表。其基本作用仍然是將邏輯地址變換為物理地址。頁(yè)號(hào) 物理塊號(hào) 狀態(tài)位P 訪問(wèn)字段A 修改位M 外存地址 請(qǐng)求分頁(yè)系統(tǒng)建立在基本分頁(yè)基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能。請(qǐng)求分頁(yè)系統(tǒng)中的頁(yè)表請(qǐng)求分頁(yè)系統(tǒng)中的頁(yè)表第四章存儲(chǔ)器管理 在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，便產(chǎn)生一缺頁(yè)中斷，請(qǐng)求OS將所缺之頁(yè)調(diào)入內(nèi)存。缺頁(yè)中斷是一種特殊的中斷，主要表現(xiàn)在下面兩個(gè)方面：(1) 在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。(2)一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁(yè)中斷?；谶@些特征，系統(tǒng)中的硬件機(jī)構(gòu)應(yīng)能保存多次中斷時(shí)的狀態(tài)，并保證最后能返回到中斷前產(chǎn)生缺

8、頁(yè)中斷的指令處繼續(xù)執(zhí)行。5.2.1請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)中的硬件支持2.2.缺頁(yè)中斷機(jī)構(gòu)缺頁(yè)中斷機(jī)構(gòu)第四章存儲(chǔ)器管理 圖圖 5-2請(qǐng)求分頁(yè)中的地址變換過(guò)程請(qǐng)求分頁(yè)中的地址變換過(guò)程 缺頁(yè)中斷處理保留CPU現(xiàn)場(chǎng)從外存中找到缺頁(yè)內(nèi)存滿否？選擇一頁(yè)換出該頁(yè)被修改否？將該頁(yè)寫回外存OS命令CPU從外存讀缺頁(yè)啟動(dòng)I/O硬件將一頁(yè)從外存換入內(nèi)存修改頁(yè)表否是是否頁(yè)表項(xiàng)在快表中？CPU檢索快表訪問(wèn)頁(yè)表否頁(yè)在內(nèi)存？修改訪問(wèn)位和修改位形成物理地址地址變換結(jié)束否頁(yè)號(hào)頁(yè)表長(zhǎng)度?開(kāi)始程序請(qǐng)求訪問(wèn)一頁(yè)產(chǎn)生缺頁(yè)中斷請(qǐng)求調(diào)頁(yè)修改快表是越界中斷是是5.2.1請(qǐng)求分頁(yè)請(qǐng)求分頁(yè)中的硬件支持中的硬件支持3 3地址變換機(jī)構(gòu)地址變換

9、機(jī)構(gòu)1111月月1111日日第四章存儲(chǔ)器管理 1 1最小物理塊數(shù)的確定最小物理塊數(shù)的確定最小物理塊數(shù)是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無(wú)法運(yùn)行。進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。5.2.2請(qǐng)求分頁(yè)中的內(nèi)存分配請(qǐng)求分頁(yè)中的內(nèi)存分配第四章存儲(chǔ)器管理 2.2.內(nèi)存分配策略內(nèi)存分配策略 1)固定分配局部置換(Fixed Allocation，Local Replacement) 基于進(jìn)程的類型，或根據(jù)程序員、程序管理員的建議，為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，在整個(gè)運(yùn)行期間都不再改變。如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)

10、缺頁(yè)，則從該進(jìn)程在內(nèi)存的n個(gè)頁(yè)面中選出一個(gè)頁(yè)換出，然后再調(diào)入一頁(yè)。5.2.2請(qǐng)求分頁(yè)中的內(nèi)存分配請(qǐng)求分頁(yè)中的內(nèi)存分配第四章存儲(chǔ)器管理 2)可變分配全局置換(Variable Allocation，Global Replacement)2.2.內(nèi)存分配策略內(nèi)存分配策略 先為系統(tǒng)中的每個(gè)進(jìn)程分配一定數(shù)目的物理塊，而OS自身也保持一個(gè)空閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)時(shí)，由系統(tǒng)從空閑物理塊隊(duì)列中取出一個(gè)物理塊分配給該進(jìn)程，并將欲調(diào)入的(缺)頁(yè)裝入其中。這樣，凡產(chǎn)生缺頁(yè)(中斷)的進(jìn)程，都將獲得新的物理塊。當(dāng)空閑物理塊用完時(shí)，OS才能從內(nèi)存中選擇一頁(yè)調(diào)出，被選擇調(diào)出的頁(yè)可能試系統(tǒng)中的任何一頁(yè)。5.2.2請(qǐng)

11、求分頁(yè)中的內(nèi)存分配請(qǐng)求分頁(yè)中的內(nèi)存分配第四章存儲(chǔ)器管理 3)3)可變分配局部置換可變分配局部置換(Variable Allocation，Local Replacement)5.2.2請(qǐng)求分頁(yè)中的內(nèi)存分配請(qǐng)求分頁(yè)中的內(nèi)存分配先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，但當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)時(shí)，只允許從該進(jìn)程在內(nèi)存的頁(yè)面中選出一頁(yè)換出，這樣就不會(huì)影響其它進(jìn)程的運(yùn)行。如果進(jìn)程在運(yùn)行中頻繁地發(fā)生缺頁(yè)中斷，則系統(tǒng)須再為該進(jìn)程分配若干附加的物理塊，直至該進(jìn)程的缺頁(yè)率減少到適當(dāng)程度為止；反之，若一個(gè)進(jìn)程在運(yùn)行過(guò)程中的缺頁(yè)率特別低，則此時(shí)可適當(dāng)減少分配給該進(jìn)程的物理塊數(shù)。 2.2.內(nèi)存分配策略內(nèi)存分配策略第四章存儲(chǔ)器管理

12、 3.3.物理塊分配算法物理塊分配算法1) 平均分配算法將系統(tǒng)中所有可供分配的物理塊平均分配給各個(gè)進(jìn)程。5.2.2請(qǐng)求分頁(yè)中的內(nèi)存分配請(qǐng)求分頁(yè)中的內(nèi)存分配2) 按比例分配算法 根據(jù)進(jìn)程的大小按比例分配物理塊的算法。系統(tǒng)中共有n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁(yè)面數(shù)為Si ,可用的物理塊總數(shù)為m，則每個(gè)進(jìn)程所能分到的物理塊數(shù)為bi 。niiSS1mSSbii第四章存儲(chǔ)器管理 3) 考慮優(yōu)先權(quán)的分配算法考慮優(yōu)先權(quán)的分配算法在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先

13、權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。5.2.2請(qǐng)求分頁(yè)中的內(nèi)存分配請(qǐng)求分頁(yè)中的內(nèi)存分配3.3.物理塊分配算法物理塊分配算法第四章存儲(chǔ)器管理 5.2.3頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略1) 預(yù)調(diào)頁(yè)策略預(yù)調(diào)頁(yè)策略采用一種以預(yù)測(cè)為基礎(chǔ)的預(yù)調(diào)頁(yè)策略，將那些預(yù)計(jì)在不久之后便會(huì)被訪問(wèn)的頁(yè)面預(yù)先調(diào)入內(nèi)存。這種策略主要用于進(jìn)程的首次調(diào)入時(shí)，由程序員指出應(yīng)該先調(diào)入哪些頁(yè)。 2) 請(qǐng)求調(diào)頁(yè)策略請(qǐng)求調(diào)頁(yè)策略 當(dāng)進(jìn)程在運(yùn)行中需要訪問(wèn)某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁(yè)面不在內(nèi)存，便立即提出請(qǐng)求，由OS將其所需頁(yè)面調(diào)入內(nèi)存。每次僅調(diào)入一頁(yè)，目前虛擬存儲(chǔ)器大多采用此策略。1.何時(shí)調(diào)入頁(yè)面何時(shí)調(diào)入頁(yè)面第四章存儲(chǔ)器管理 2從何

14、處調(diào)入頁(yè)面從何處調(diào)入頁(yè)面請(qǐng)求分頁(yè)系統(tǒng)中的外存分為文件區(qū)和對(duì)換區(qū)。當(dāng)發(fā)生缺頁(yè)請(qǐng)求時(shí)，有三種情況將缺頁(yè)調(diào)入內(nèi)存： (1) 系統(tǒng)擁有足夠的對(duì)換區(qū)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)速度。(2)系統(tǒng)缺少足夠的對(duì)換區(qū)空間，凡不會(huì)被修改的文件都直接從文件區(qū)調(diào)入。對(duì)于那些可能被修改的部分，將它們換出時(shí)須調(diào)到對(duì)換區(qū)。 (3) UNIX方式。與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過(guò)的頁(yè)面，都應(yīng)從文件區(qū)調(diào)入；對(duì)于曾經(jīng)運(yùn)行過(guò)但又被換出的頁(yè)面，放在對(duì)換區(qū)。第四章存儲(chǔ)器管理 3. 頁(yè)面調(diào)入過(guò)程頁(yè)面調(diào)入過(guò)程每當(dāng)程序所要訪問(wèn)的頁(yè)面未在內(nèi)存時(shí)，便向CPU發(fā)出一缺頁(yè)中斷，中斷處理程序首先保留CPU環(huán)境，分析中

15、斷原因后轉(zhuǎn)入缺頁(yè)中斷處理程序。在缺頁(yè)調(diào)入內(nèi)存后，利用修改后的頁(yè)表，形成所要訪問(wèn)數(shù)據(jù)的物理地址，再去訪問(wèn)內(nèi)存數(shù)據(jù)。整個(gè)頁(yè)面的調(diào)入過(guò)程對(duì)用戶是透明的。 5.2.3頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略第四章存儲(chǔ)器管理 5.2.3頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略4. 缺頁(yè)率缺頁(yè)率 假設(shè)一個(gè)進(jìn)程的邏輯空間為n頁(yè)，系統(tǒng)為其分配的內(nèi)存物理塊數(shù)為m(mn)。如果在進(jìn)程的運(yùn)行過(guò)程中，訪問(wèn)頁(yè)面成功的次數(shù)為S，訪問(wèn)頁(yè)面失敗的次數(shù)為F。則該進(jìn)程在運(yùn)行過(guò)程中的缺頁(yè)率為：f = F/(S+F)第四章存儲(chǔ)器管理 5.3頁(yè)面置換算法頁(yè)面置換算法 5.3.1最佳置換算法和先進(jìn)先出置換算法最佳置換算法和先進(jìn)先出置換算法1.1.最佳最佳(Optima

16、l)置換算法置換算法由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的，或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。 頁(yè)面置換算法是指選擇換出頁(yè)面的算法。不適當(dāng)?shù)乃惴赡軙?huì)導(dǎo)致進(jìn)程發(fā)生“抖動(dòng)”。第四章存儲(chǔ)器管理 u例：例：假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，考慮有以下的頁(yè)面號(hào)引用串： 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1進(jìn)程運(yùn)行時(shí)，先將7，0，1三個(gè)頁(yè)面裝入內(nèi)存。引用率70770170122010320304243230321201201770101頁(yè)框(物理塊）243

17、圖圖 5-3利用最佳頁(yè)面置換算法時(shí)的置換圖利用最佳頁(yè)面置換算法時(shí)的置換圖 1.1.最佳最佳(Optimal)置換算法置換算法第四章存儲(chǔ)器管理 2.2.先進(jìn)先出先進(jìn)先出(FIFO)頁(yè)面置換算法頁(yè)面置換算法該算法淘汰最先進(jìn)入內(nèi)存的頁(yè)面。5.3.1最佳置換算法和先進(jìn)先出置換算法最佳置換算法和先進(jìn)先出置換算法引用率70770170122010323104430230321013201770201頁(yè)框230420423023012712701u例：頁(yè)面號(hào)引用串： 7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7

18、，0 0，1.1. 進(jìn)程運(yùn)行時(shí)，先將7，0，1三個(gè)頁(yè)面裝入內(nèi)存。FIFO算法時(shí)進(jìn)行了算法時(shí)進(jìn)行了12次頁(yè)面置換次頁(yè)面置換第四章存儲(chǔ)器管理 1. LRU(Least Recently Used)置換算法置換算法選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇t值最大的頁(yè)面.5.3.2最近最久未使用和最少使用置換算法最近最久未使用和最少使用置換算法引用率70770170122010320304403230321132201770101頁(yè)框402432032102LRU頁(yè)面置換算法頁(yè)面置換算法 第四章存儲(chǔ)器管理

19、 2 2LRU置換算法的硬件支持置換算法的硬件支持 1) 寄存器移位寄存器，記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況。R=Rn-1Rn-2Rn-3 R2R1R0 5.3.2最近最久未使用置換算法和最少使用置換算法最近最久未使用置換算法和最少使用置換算法R 實(shí) 頁(yè) R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 圖圖5-

20、6某進(jìn)程具有某進(jìn)程具有8個(gè)頁(yè)面時(shí)的個(gè)頁(yè)面時(shí)的LRU訪問(wèn)情況訪問(wèn)情況 第四章存儲(chǔ)器管理 2) 2) 棧棧可利用一個(gè)特殊的棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問(wèn)某頁(yè)面時(shí)，便將該頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。假定現(xiàn)有一進(jìn)程所訪問(wèn)的頁(yè)面號(hào)序列為：4，7，0，7，1，0，1，2，1，2，6.隨著進(jìn)程的訪問(wèn)，棧中頁(yè)面號(hào)的變化情況如圖所示。2 2LRU置換算法的硬件支持置換算法的硬件支持4474707407047170410174010741210742120741210742621076第四章存儲(chǔ)器管理 5.3.2最近最久未使用置換算法和最少使用置換算法最近最久未使用置換算法和最少使用置

21、換算法3. 最少使用最少使用(Least Frequently Used, LFU)置換算法置換算法該置換算法選擇在最近時(shí)期使用最少的頁(yè)面作為淘汰頁(yè)。在采用LFU算法時(shí)，應(yīng)為在內(nèi)存中的每個(gè)頁(yè)面設(shè)置一個(gè)移位寄存器，用來(lái)記錄該頁(yè)面被訪問(wèn)的頻率。第四章存儲(chǔ)器管理 1 1簡(jiǎn)單的簡(jiǎn)單的Clock置換算法置換算法又稱為最近未用(Not Recently Used，NRU)算法，該算法為每頁(yè)設(shè)置一位訪問(wèn)位，再將內(nèi)存中的所有頁(yè)面都通過(guò)鏈接指針鏈接成一個(gè)循環(huán)隊(duì)列。當(dāng)某頁(yè)被訪問(wèn)時(shí)，其訪問(wèn)位被置1。5.3.3Clock置換算法置換算法 置換算法在選擇一頁(yè)淘汰時(shí)，只需檢查頁(yè)的訪問(wèn)位。如果是0，就選擇該頁(yè)換出；若為1，

22、則重新將它置0，暫不換出，給予該頁(yè)第二次駐留內(nèi)存的機(jī)會(huì)，再按照FIFO算法檢查下一個(gè)頁(yè)面。11.16第四章存儲(chǔ)器管理 圖圖5-8簡(jiǎn)單簡(jiǎn)單Clock置換算法的流程和示例置換算法的流程和示例 入口查尋指針前進(jìn)一步，指向下一個(gè)表目頁(yè)面訪問(wèn)位0?選擇該頁(yè)面淘汰是返回置頁(yè)面訪問(wèn)位“0”否塊號(hào)頁(yè)號(hào)訪問(wèn)位指針0124034215650711替換指針第四章存儲(chǔ)器管理 2.2.改進(jìn)型改進(jìn)型ClockClock置換算法置換算法在改進(jìn)型Clock算法中，須考慮頁(yè)面的使用情況、置換置換代價(jià)代價(jià)。在選擇頁(yè)面換出時(shí)，既要是未使用過(guò)的頁(yè)面，又要是未被修改過(guò)的頁(yè)面。由訪問(wèn)位A和修改位M組合成下面四種類型的頁(yè)面： 1類(A=0

23、, M=0) 該頁(yè)最近既未被訪問(wèn)，又未被修改過(guò)。 2類(A=0, M=1) 該頁(yè)最近既未被訪問(wèn)，但已被修改。3類(A=1, M=0) 4類(A=1, M=1)5.3.3Clock置換算法置換算法第四章存儲(chǔ)器管理 該算法須同時(shí)檢查訪問(wèn)位與修改位，以確定該頁(yè)是四類頁(yè)面中的哪一種。其執(zhí)行過(guò)程可分成以下三步：(1) 從指針?biāo)甘镜漠?dāng)前位置開(kāi)始，掃描循環(huán)隊(duì)列，尋找A=0且M=0的第一類頁(yè)面。在第一次掃描期間不改變?cè)L問(wèn)位A。2.2.改進(jìn)型改進(jìn)型Clock置換算法置換算法(2)如果第一步失敗，則開(kāi)始第二輪掃描尋找A=0且M=1的第二類頁(yè)面。在第二輪，將所有掃描過(guò)的頁(yè)面的訪問(wèn)位都置0。(3)如果第二步失敗，將

24、所有的訪問(wèn)位復(fù)0。然后重復(fù)第一步，必要時(shí)再重復(fù)第二步。5.3.3Clock置換算法置換算法第四章存儲(chǔ)器管理 5.3.4 頁(yè)面緩沖算法頁(yè)面緩沖算法(Page Buffering Algorithm, PBA)1.1.影響頁(yè)面換進(jìn)換出效率的若干因素影響頁(yè)面換進(jìn)換出效率的若干因素(1) 頁(yè)面置換算法 。影響頁(yè)面換進(jìn)換出效率最重要的因素(2) 寫回磁盤的頻率。對(duì)于已經(jīng)被修改過(guò)的頁(yè)面，在將其換出時(shí)，應(yīng)寫回磁盤。減少已修改頁(yè)面換出的開(kāi)銷。(3) 讀入內(nèi)存的頻率。減少將頁(yè)面從磁盤讀入內(nèi)存的頻率，減少頁(yè)面換進(jìn)的開(kāi)銷。第四章存儲(chǔ)器管理 l VAX/VMS操作系統(tǒng)中所使用的PBA：采用可變分配和局部置換方式，置換

25、算法采用FIFO。PBA算法的實(shí)現(xiàn)需要內(nèi)存中設(shè)置的兩個(gè)鏈表：空閑頁(yè)面鏈表、修改頁(yè)面鏈表。該算法規(guī)定將一個(gè)被淘汰的頁(yè)放入兩個(gè)鏈表中的一個(gè)，即如果頁(yè)面未被修改，就將它直接放入空閑鏈表中；否則，便放入修改頁(yè)面鏈表中。l 須注意，這時(shí)頁(yè)面在內(nèi)存中并不做物理上的移動(dòng)，而只是將頁(yè)表中的表項(xiàng)移到上述兩個(gè)鏈表之一中。l 采用PBA算法時(shí)，被換出的頁(yè)面仍留在內(nèi)存的空閑塊中，所有的空閑塊形成一個(gè)空閑頁(yè)面緩沖池。5.3.4 頁(yè)面緩沖算法頁(yè)面緩沖算法(Page Buffering Algorithm, PBA)第四章存儲(chǔ)器管理 思考一思考一 在一采取局部置換策略的請(qǐng)求分頁(yè)系統(tǒng)中，分配給某個(gè)作業(yè)的內(nèi)存塊數(shù)為4，其中存放

26、的四個(gè)頁(yè)面的情況如下表：物理塊 虛頁(yè)號(hào) 裝入時(shí)間 最后一次訪問(wèn)時(shí)間 訪問(wèn)位 修改位 0 2 60 157 0 1 1 1 160 161 1 0 2 0 26 158 0 0 3 3 20 163 1 1 表中的所有數(shù)字均為十進(jìn)制數(shù)，所有時(shí)間都是從進(jìn)程開(kāi)始運(yùn)行時(shí)，從0開(kāi)始計(jì)數(shù)的時(shí)鐘數(shù)。請(qǐng)問(wèn)，如果系統(tǒng)采用下列置換算法，將選擇哪一頁(yè)進(jìn)行換出？ (1) FIFO算法； (2) LRU算法； (3) 改進(jìn)的Clock算法. 第四章存儲(chǔ)器管理 思考二思考二 在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，假如一個(gè)作業(yè)的頁(yè)面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5，目前它還沒(méi)有任何頁(yè)裝入內(nèi)存，當(dāng)分配給該作業(yè)的物理塊數(shù)目

27、M分別為3和4時(shí)，請(qǐng)分別計(jì)算采用LRU和FIFO頁(yè)面淘汰算法時(shí)，訪問(wèn)過(guò)程中所發(fā)生的缺頁(yè)次數(shù)和缺頁(yè)率，并比較所得的結(jié)果。第四章存儲(chǔ)器管理 思考三思考三 某虛擬存儲(chǔ)器的用戶空間共有32個(gè)頁(yè)面，每頁(yè)1KB，主存16KB。假定某時(shí)刻系統(tǒng)為用戶的第0、1、2、3頁(yè)分配的物理塊號(hào)為5、10、4、7，而該用戶作業(yè)的長(zhǎng)度為6頁(yè)，試將十六進(jìn)制的虛擬地址0A5C、103C、1A5C轉(zhuǎn)換成物理地址。第四章存儲(chǔ)器管理 5.4“抖動(dòng)抖動(dòng)”與工作集與工作集5.4.1 多道程序度與多道程序度與“抖動(dòng)抖動(dòng)”u“抖動(dòng)”系統(tǒng)中運(yùn)行的進(jìn)程太多，由此分配給每一個(gè)進(jìn)程的物理塊太少，不能滿足進(jìn)程正常運(yùn)行的基本要求，致使每個(gè)進(jìn)程在運(yùn)行時(shí)頻

28、繁地出現(xiàn)缺頁(yè)。第四章存儲(chǔ)器管理 工作集是指在某段時(shí)間間隔內(nèi)，進(jìn)程要訪問(wèn)的頁(yè)面集合。經(jīng)常被使用的頁(yè)面需要在工作集中，而長(zhǎng)期不被使用的頁(yè)面要從工作集中被丟棄。 5.4.2 工作集工作集 工作集模型的原理是：操作系統(tǒng)跟蹤每個(gè)進(jìn)程的工作集，并為進(jìn)程分配大于其工作集的物理塊。如果還有空閑物理塊，則可以再調(diào)一個(gè)進(jìn)程到內(nèi)存以增加多道程序數(shù)。如果所有工作集之和增加以至于超過(guò)了可用物理塊的總數(shù)，那么操作系統(tǒng)會(huì)暫停一個(gè)進(jìn)程，將其頁(yè)面調(diào)出并且將其物理塊分配給其他進(jìn)程，防止出現(xiàn)抖動(dòng)現(xiàn)象。 第四章存儲(chǔ)器管理 5.4.3 “抖動(dòng)抖動(dòng)”的預(yù)防方法的預(yù)防方法1. 采用局部置換策略采用局部置換策略 頁(yè)面分配采用可變分配方式，置

29、換采用局部置換策略。當(dāng)某進(jìn)程發(fā)生缺頁(yè)時(shí)，只能在分配給自己的內(nèi)存空間內(nèi)進(jìn)行置換，不允許從其他進(jìn)程去獲得新的物理塊。2. 把工作集算法融入到處理機(jī)調(diào)度中把工作集算法融入到處理機(jī)調(diào)度中 當(dāng)調(diào)度程序試圖從外存調(diào)入一個(gè)新作業(yè)到內(nèi)存，必須先檢查每個(gè)進(jìn)程在內(nèi)存的駐留頁(yè)面是否足夠多。如果足夠多，此時(shí)便可以從外村調(diào)入新作業(yè)。第四章存儲(chǔ)器管理 5.4.3 “抖動(dòng)抖動(dòng)”的預(yù)防方法的預(yù)防方法3. 利用利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁(yè)率準(zhǔn)則調(diào)節(jié)缺頁(yè)率4. 選擇暫停的進(jìn)程選擇暫停的進(jìn)程 L是缺頁(yè)之間的平均時(shí)間，S是平均缺頁(yè)服務(wù)，即用于置換一個(gè)頁(yè)面所需的時(shí)間。當(dāng)L遠(yuǎn)比S大，說(shuō)明很少發(fā)生缺頁(yè)；反之，如果L比S小，則說(shuō)明頻繁發(fā)生缺頁(yè)

30、，缺頁(yè)的速度已超過(guò)磁盤的處理能力。當(dāng)L與S接近時(shí)，磁盤和處理機(jī)都達(dá)到它們的最大利用率。 當(dāng)多道程序度偏高時(shí)，為了防止發(fā)生“抖動(dòng)”，系統(tǒng)必須減少多道程序的數(shù)目。因此暫停某些當(dāng)前活動(dòng)的進(jìn)程。第四章存儲(chǔ)器管理 5.5請(qǐng)求分段存儲(chǔ)管理方式請(qǐng)求分段存儲(chǔ)管理方式 1 1請(qǐng)求段表機(jī)制請(qǐng)求段表機(jī)制在請(qǐng)求分段式管理中所需的主要數(shù)據(jù)結(jié)構(gòu)是請(qǐng)求段表。段名 段長(zhǎng) 段的 基址 存取 方式 訪問(wèn) 字段 A 修改 位 M 存在 位 P 增補(bǔ)位 外存 始址 程序運(yùn)行之前，只需先調(diào)入調(diào)入少數(shù)幾個(gè)分段便可啟動(dòng)。當(dāng)所訪問(wèn)的段不再內(nèi)存中，可請(qǐng)求OS將所缺的段調(diào)入內(nèi)存。5.5.1請(qǐng)求分段中的硬件支持請(qǐng)求分段中的硬件支持第四章存儲(chǔ)器管理

31、 2.缺段中斷機(jī)構(gòu)缺段中斷機(jī)構(gòu)在請(qǐng)求分段系統(tǒng)中，每當(dāng)發(fā)現(xiàn)運(yùn)行進(jìn)程所要訪問(wèn)的段尚未調(diào)入內(nèi)存時(shí)，便由缺段中斷機(jī)構(gòu)產(chǎn)生一缺段中斷信號(hào)，進(jìn)入OS后由缺段中斷處理程序?qū)⑺璧亩握{(diào)入內(nèi)存。缺段中斷機(jī)構(gòu)與缺頁(yè)中斷機(jī)構(gòu)類似，它同樣需要在一條指令的執(zhí)行期間，產(chǎn)生和處理中斷，以及在一條指令執(zhí)行期間，可能產(chǎn)生多次缺段中斷。缺段中斷的處理過(guò)程如圖所示。由于段不是定長(zhǎng)的，這使對(duì)缺段中斷的處理要比對(duì)缺頁(yè)中斷的處理復(fù)雜。 5.5.1請(qǐng)求分段中的硬件支持請(qǐng)求分段中的硬件支持第四章存儲(chǔ)器管理 虛段S不在內(nèi)存阻塞請(qǐng)求進(jìn)程內(nèi)存中有合適的空閑區(qū)嗎？從外存讀入段S修改段表及內(nèi)存空區(qū)鏈喚醒請(qǐng)求進(jìn)程返回空區(qū)容量總和能否滿足？空區(qū)拼接，以形成一個(gè)合適的空區(qū)淘汰一個(gè)或幾個(gè)實(shí)段，以形成一個(gè)合適空區(qū)否否是是圖圖5-12請(qǐng)求分段系統(tǒng)中的中斷處理過(guò)程請(qǐng)求分段系統(tǒng)中的中斷處理過(guò)程 第四章存儲(chǔ)器管理 3. 3.地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)因?yàn)楸辉L問(wèn)的段并非全在內(nèi)存，所以在地址