計算機操作系統(tǒng)-第四版-湯小丹-梁紅兵-哲鳳屏-第5章(2016-2017-1)

計算機操作系統(tǒng)-第四版-湯小丹-梁紅兵-哲鳳屏-第5章(2016-2017-1)第一頁，共50頁。5.1虛擬存儲器概述

前面所介紹的各種存儲器管理方式有一個共同的特點，即它們都要求將一個作業(yè)全部裝入內(nèi)存后方能運行，于是，出現(xiàn)了下面這樣兩種情況：

(1)有的作業(yè)很大，其所要求的內(nèi)存空間超過了內(nèi)存總?cè)萘?，作業(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無法運行。

(2)有大量作業(yè)要求運行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)

裝入內(nèi)存讓它們先運行，而將其它大量的作業(yè)留在外存上等待。

第二頁，共50頁。

1.常規(guī)存儲器管理方式的特征

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

第三頁，共50頁。

2．局部性原理

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

3.虛擬存儲器的基本工作情況基于局部性原理，應(yīng)用程序在運行之前，僅須將那些當前要運行的少數(shù)頁面或段先裝入內(nèi)存便可運行，其余部分暫留在盤上。程序在運行時，如果程序所要訪問的頁(段)尚未調(diào)入內(nèi)存，此時程序應(yīng)利用OS所提供的請求調(diào)頁(段)功能，將它們調(diào)入內(nèi)存，以使進程能繼續(xù)執(zhí)行下去。如果此時內(nèi)存已滿，則須再利用頁(段)的置換功能，將內(nèi)存中暫時不用的頁(段)調(diào)至盤上，再將要訪問的頁(段)調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。5.1.1常規(guī)存儲管理方式的特征和局部性原理第五頁，共50頁。5.1.2虛擬存儲器的定義和特征具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲系統(tǒng)。其邏輯容量是內(nèi)存容量和外存容量之和，其運行速度接近于內(nèi)存速度。1.虛擬存儲器的定義2.虛擬存儲器的特征1)多次性.一個作業(yè)被分成多次調(diào)入內(nèi)存運行2)對換性.作業(yè)的運行過程中進行換進、換出3)虛擬性.能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠大于實際內(nèi)存容量。第六頁，共50頁。

1.分頁請求系統(tǒng)在分頁系統(tǒng)的基礎(chǔ)上增加了請求調(diào)頁功能和頁面置換功能。它允許只裝入少數(shù)頁面的程序(及數(shù)據(jù))，便啟動運行。以后，再通過調(diào)頁功能及頁面置換功能，陸續(xù)地把即將要運行的頁面調(diào)入內(nèi)存，同時把暫不運行的頁面換出到外存上。置換時以頁面為單位。為了能實現(xiàn)請求調(diào)頁和置換功能，系統(tǒng)必須提供必要的硬件支持和相應(yīng)的軟件。

5.1.3虛擬存儲器的實現(xiàn)方法虛擬存儲器建立在離散分配存儲管理方式第七頁，共50頁。

2.請求分段系統(tǒng)在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段及分段置換功能后所形成的段式虛擬存儲系統(tǒng)。它允許只裝入少數(shù)段(而非所有的段)的用戶程序和數(shù)據(jù)，即可啟動運行。以后再通過調(diào)段功能和段的置換功能將暫不運行的段調(diào)出，同時調(diào)入即將運行的段。置換是以段為單位進行的。5.1.3虛擬存儲器的實現(xiàn)方法第八頁，共50頁。5.2請求分頁存儲管理方式

5.2.1請求分頁中的硬件支持

1.請求頁表機制在請求分頁系統(tǒng)中所需要的主要數(shù)據(jù)結(jié)構(gòu)是頁表。其基本作用仍然是將邏輯地址變換為物理地址。請求分頁系統(tǒng)建立在基本分頁基礎(chǔ)上，增加了請求調(diào)頁功能和頁面置換功能。請求分頁系統(tǒng)中的頁表第九頁，共50頁。

在請求分頁系統(tǒng)中，每當所要訪問的頁面不在內(nèi)存時，便產(chǎn)生一缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存。缺頁中斷是一種特殊的中斷，主要表現(xiàn)在下面兩個方面：(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號。(2)一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁中斷?；谶@些特征，系統(tǒng)中的硬件機構(gòu)應(yīng)能保存多次中斷時的狀態(tài)，并保證最后能返回到中斷前產(chǎn)生缺頁中斷的指令處繼續(xù)執(zhí)行。5.2.1請求分頁中的硬件支持2.缺頁中斷機構(gòu)第十頁，共50頁。圖

5-2請求分頁中的地址變換過程

5.2.1請求分頁中的硬件支持3．地址變換機構(gòu)11月11日第十一頁，共50頁。

1．最小物理塊數(shù)的確定最小物理塊數(shù)是指能保證進程正常運行所需的最小物理塊數(shù)。當系統(tǒng)為進程分配的物理塊數(shù)少于此值時，進程將無法運行。進程應(yīng)獲得的最少物理塊數(shù)與計算機的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。5.2.2請求分頁中的內(nèi)存分配第十二頁，共50頁。

2.內(nèi)存分配策略1)固定分配局部置換(FixedAllocation，LocalReplacement)基于進程的類型，或根據(jù)程序員、程序管理員的建議，為每個進程分配一定數(shù)目的物理塊，在整個運行期間都不再改變。如果進程在運行中發(fā)現(xiàn)缺頁，則從該進程在內(nèi)存的n個頁面中選出一個頁換出，然后再調(diào)入一頁。5.2.2請求分頁中的內(nèi)存分配第十三頁，共50頁。2)可變分配全局置換(VariableAllocation，GlobalReplacement)

2.內(nèi)存分配策略先為系統(tǒng)中的每個進程分配一定數(shù)目的物理塊，而OS自身也保持一個空閑物理塊隊列。當某進程發(fā)現(xiàn)缺頁時，由系統(tǒng)從空閑物理塊隊列中取出一個物理塊分配給該進程，并將欲調(diào)入的(缺)頁裝入其中。這樣，凡產(chǎn)生缺頁(中斷)的進程，都將獲得新的物理塊。當空閑物理塊用完時，OS才能從內(nèi)存中選擇一頁調(diào)出，被選擇調(diào)出的頁可能試系統(tǒng)中的任何一頁。5.2.2請求分頁中的內(nèi)存分配第十四頁，共50頁。

3)可變分配局部置換(VariableAllocation，LocalReplacement)5.2.2請求分頁中的內(nèi)存分配先為每個進程分配一定數(shù)目的物理塊，但當某進程發(fā)現(xiàn)缺頁時，只允許從該進程在內(nèi)存的頁面中選出一頁換出，這樣就不會影響其它進程的運行。如果進程在運行中頻繁地發(fā)生缺頁中斷，則系統(tǒng)須再為該進程分配若干附加的物理塊，直至該進程的缺頁率減少到適當程度為止；反之，若一個進程在運行過程中的缺頁率特別低，則此時可適當減少分配給該進程的物理塊數(shù)。

2.內(nèi)存分配策略第十五頁，共50頁。

3.物理塊分配算法

1)平均分配算法將系統(tǒng)中所有可供分配的物理塊平均分配給各個進程。5.2.2請求分頁中的內(nèi)存分配2)按比例分配算法根據(jù)進程的大小按比例分配物理塊的算法。系統(tǒng)中共有n個進程，每個進程的頁面數(shù)為Si,可用的物理塊總數(shù)為m，則每個進程所能分到的物理塊數(shù)為bi。第十六頁，共50頁。

3)考慮優(yōu)先權(quán)的分配算法在實際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據(jù)各進程的優(yōu)先權(quán)，適當?shù)卦黾悠湎鄳?yīng)份額后，分配給各進程。5.2.2請求分頁中的內(nèi)存分配3.物理塊分配算法第十七頁，共50頁。5.2.3頁面調(diào)入策略1)預(yù)調(diào)頁策略采用一種以預(yù)測為基礎(chǔ)的預(yù)調(diào)頁策略，將那些預(yù)計在不久之后便會被訪問的頁面預(yù)先調(diào)入內(nèi)存。這種策略主要用于進程的首次調(diào)入時，由程序員指出應(yīng)該先調(diào)入哪些頁。

2)請求調(diào)頁策略當進程在運行中需要訪問某部分程序和數(shù)據(jù)時，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，便立即提出請求，由OS將其所需頁面調(diào)入內(nèi)存。每次僅調(diào)入一頁，目前虛擬存儲器大多采用此策略。1.何時調(diào)入頁面第十八頁，共50頁。

2．從何處調(diào)入頁面請求分頁系統(tǒng)中的外存分為文件區(qū)和對換區(qū)。當發(fā)生缺頁請求時，有三種情況將缺頁調(diào)入內(nèi)存：

(1)系統(tǒng)擁有足夠的對換區(qū)空間，這時可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。(2)系統(tǒng)缺少足夠的對換區(qū)空間，凡不會被修改的文件都直接從文件區(qū)調(diào)入。對于那些可能被修改的部分，將它們換出時須調(diào)到對換區(qū)。(3)UNIX方式。與進程有關(guān)的文件都放在文件區(qū)，故凡是未運行過的頁面，都應(yīng)從文件區(qū)調(diào)入；對于曾經(jīng)運行過但又被換出的頁面，放在對換區(qū)。第十九頁，共50頁。

3.頁面調(diào)入過程每當程序所要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后轉(zhuǎn)入缺頁中斷處理程序。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個頁面的調(diào)入過程對用戶是透明的。

5.2.3頁面調(diào)入策略第二十頁，共50頁。5.2.3頁面調(diào)入策略4.缺頁率假設(shè)一個進程的邏輯空間為n頁，系統(tǒng)為其分配的內(nèi)存物理塊數(shù)為m(m≤n)。如果在進程的運行過程中，訪問頁面成功的次數(shù)為S，訪問頁面失敗的次數(shù)為F。則該進程在運行過程中的缺頁率為：f=F/(S+F)第二十一頁，共50頁。5.3頁面置換算法

5.3.1最佳置換算法和先進先出置換算法

1.最佳(Optimal)置換算法由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。頁面置換算法是指選擇換出頁面的算法。不適當?shù)乃惴赡軙е逻M程發(fā)生“抖動”。第二十二頁，共50頁。例：假定系統(tǒng)為某進程分配了三個物理塊，考慮有以下的頁面號引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1進程運行時，先將7，0，1三個頁面裝入內(nèi)存。圖

5-3利用最佳頁面置換算法時的置換圖

1.最佳(Optimal)置換算法第二十三頁，共50頁。

2.先進先出(FIFO)頁面置換算法該算法淘汰最先進入內(nèi)存的頁面。5.3.1最佳置換算法和先進先出置換算法例：頁面號引用串：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1.進程運行時，先將7，0，1三個頁面裝入內(nèi)存。FIFO算法時進行了12次頁面置換第二十四頁，共50頁。

1.LRU(LeastRecentlyUsed)置換算法

選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t，當須淘汰一個頁面時，選擇t值最大的頁面.5.3.2最近最久未使用和最少使用置換算法LRU頁面置換算法

第二十五頁，共50頁。

2．LRU置換算法的硬件支持

1)寄存器移位寄存器，記錄某進程在內(nèi)存中各頁的使用情況。R?=?Rn-1Rn-2Rn-3…R2R1R0

5.3.2最近最久未使用和最少使用置換算法圖5-6某進程具有8個頁面時的LRU訪問情況

第二十六頁，共50頁。

2)?？衫靡粋€特殊的棧來保存當前使用的各個頁面的頁面號。每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。假定現(xiàn)有一進程所訪問的頁面號序列為：4，7，0，7，1，0，1，2，1，2，6.隨著進程的訪問，棧中頁面號的變化情況如圖所示。2．LRU置換算法的硬件支持第二十七頁，共50頁。5.3.2最近最久未使用和最少使用置換算法

3.最少使用(LeastFrequentlyUsed,LFU)置換算法該置換算法選擇在最近時期使用最少的頁面作為淘汰頁。在采用LFU算法時，應(yīng)為在內(nèi)存中的每個頁面設(shè)置一個移位寄存器，用來記錄該頁面被訪問的頻率。第二十八頁，共50頁。

1．簡單的Clock置換算法又稱為最近未用(NotRecentlyUsed，NRU)算法，該算法為每頁設(shè)置一位訪問位，再將內(nèi)存中的所有頁面都通過鏈接指針鏈接成一個循環(huán)隊列。5.3.3

Clock置換算法置換算法在選擇一頁淘汰時，只需檢查頁的訪問位。如果是0，就選擇該頁換出；若為1，則重新將它置0，暫不換出，給予該頁第二次駐留內(nèi)存的機會，再按照FIFO算法檢查下一個頁面。11.16第二十九頁，共50頁。圖5-8簡單Clock置換算法的流程和示例

第三十頁，共50頁。

2.改進型Clock置換算法在改進型Clock算法中，須考慮頁面的使用情況、置換代價。在選擇頁面換出時，既要是未使用過的頁面，又要是未被修改過的頁面。由訪問位A和修改位M組合成下面四種類型的頁面：

1類(A=0,M=0)該頁最近既未被訪問，又未被修改過。

2類(A=0,M=1)

該頁最近既未被訪問，但已被修改。3類(A=1,M=0)4類(A=1,M=1)5.3.3

Clock置換算法第三十一頁，共50頁。該算法須同時檢查訪問位與修改位，以確定該頁是四類頁面中的哪一種。其執(zhí)行過程可分成以下三步：(1)從指針所指示的當前位置開始，掃描循環(huán)隊列，尋找A=0且M=0的第一類頁面。在第一次掃描期間不改變訪問位A。2.改進型Clock置換算法(2)如果第一步失敗，則開始第二輪掃描尋找A=0且M=1的第二類頁面。在第二輪，將所有掃描過的頁面的訪問位都置0。(3)如果第二步失敗，將所有的訪問位復(fù)0。然后重復(fù)第一步，必要時再重復(fù)第二步。5.3.3

Clock置換算法第三十二頁，共50頁。

5.3.4頁面緩沖算法(PageBufferingAlgorithm,PBA)1.影響頁面換進換出效率的若干因素(1)頁面置換算法。影響頁面換進換出效率最重要的因素(2)寫回磁盤的頻率。對于已經(jīng)被修改過的頁面，在將其換出時，應(yīng)寫回磁盤。減少已修改頁面換出的開銷。(3)讀入內(nèi)存的頻率。減少將頁面從磁盤讀入內(nèi)存的頻率，減少頁面換進的開銷。第三十三頁，共50頁。VAX/VMS操作系統(tǒng)中所使用的PBA：采用可變分配和局部置換方式，置換算法采用FIFO。PBA算法的實現(xiàn)需要內(nèi)存中設(shè)置的兩個鏈表：空閑頁面鏈表、修改頁面鏈表。該算法規(guī)定將一個被淘汰的頁放入兩個鏈表中的一個，即如果頁面未被修改，就將它直接放入空閑鏈表中；否則，便放入修改頁面鏈表中。須注意，這時頁面在內(nèi)存中并不做物理上的移動，而只是將頁表中的表項移到上述兩個鏈表之一中。采用PBA算法時，被換出的頁面仍留在內(nèi)存的空閑塊中，所有的空閑塊形成一個空閑頁面緩沖池。5.3.4頁面緩沖算法(PageBufferingAlgorithm,PBA)第三十四頁，共50頁。思考一在一采取局部置換策略的請求分頁系統(tǒng)中，分配給某個作業(yè)的內(nèi)存塊數(shù)為4，其中存放的四個頁面的情況如下表：物理塊虛頁號裝入時間最后一次訪問時間訪問位修改位0260157011116016110202615800332016311表中的所有數(shù)字均為十進制數(shù)，所有時間都是從進程開始運行時，從0開始計數(shù)的時鐘數(shù)。請問，如果系統(tǒng)采用下列置換算法，將選擇哪一頁進行換出？

(1)FIFO算法；(2)LRU算法；(3)改進的Clock算法.第三十五頁，共50頁。思考二在一個請求分頁系統(tǒng)中，假如一個作業(yè)的頁面走向為4，3，2，1，4，3，5，4，3，2，1，5，目前它還沒有任何頁裝入內(nèi)存，當分配給該作業(yè)的物理塊數(shù)目M分別為3和4時，請分別計算采用LRU和FIFO頁面淘汰算法時，訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率，并比較所得的結(jié)果。第三十六頁，共50頁。第三十七頁，共50頁。5.4“抖動”與工作集5.4.1多道程序度與“抖動”

“抖動”：系統(tǒng)中運行的進程太多，由此分配給每一個進程的物理塊太少，不能滿足進程正常運行的基本要求，致使每個進程在運行時頻繁地出現(xiàn)缺頁。第三十八頁，共50頁。工作集是指在某段時間間隔Δ內(nèi)，進程要訪問的頁面集合。經(jīng)常被使用的頁面需要在工作集中，而長期不被使用的頁面要從工作集中被丟棄。

5.4.2工作集

工作集模型的原理是：操作系統(tǒng)跟蹤每個進程的工作集，并為進程分配大于其工作集的物理塊。如果還有空閑物理塊，則可以再調(diào)一個進程到內(nèi)存以增加多道程序數(shù)。如果所有工作集之和增加以至于超過了可用物理塊的總數(shù)，那么操作系統(tǒng)會暫停一個進程，將其頁面調(diào)出并且將其物理塊分配給其他進程，防止出現(xiàn)抖動現(xiàn)象。

第三十九頁，共50頁。5.4.3“抖動”的預(yù)防方法

1.采用局部置換策略頁面分配采用可變分配方式，置換采用局部置換策略。當某進程發(fā)生缺頁時，只能在分配給自己的內(nèi)存空間內(nèi)進行置換，不允許從其他進程去獲得新的物理塊。2.把工作集算法融入到處理機調(diào)度中當調(diào)度程序試圖從外存調(diào)入一個新作業(yè)到內(nèi)存，必須先檢查每個進程在內(nèi)存的駐留頁面是否足夠多。如果足夠多，此時便可以從外存調(diào)入新作業(yè)。第四十頁，共50頁。5.4.3“抖動”的預(yù)防方法

3.利用“L=S”準則調(diào)節(jié)缺頁率4.選擇暫停的進程L是缺頁之間的平均時間，S是平均缺頁服務(wù)時間，即用于置換一個頁面所需的時間。當L遠比S大，說明很少發(fā)生缺頁；反之，如果L比S小，則說明頻繁發(fā)生缺頁，缺頁的速度已超過磁盤的處理能力。當L與S接近時，磁盤和處理機都達到它們的最大利用率。當多道程序度偏高時，為了防止發(fā)生“抖動”，系統(tǒng)必須減少多道程序的數(shù)目。因此暫停某些當前活動的進程。第四十一頁，共50頁。5.5請求分段存儲管理方式

1．請求段表機制在請求分段式管理中所需的主要數(shù)據(jù)結(jié)構(gòu)是請求段表。程序運行之前，只需先調(diào)入調(diào)入少數(shù)幾個分段便可啟動。當所訪問的段不再內(nèi)存中，可請求OS將所缺的段調(diào)入內(nèi)存。5.5.1請求分段中的硬件支持11.23？第四十二頁，共50頁。

2.缺段中斷機構(gòu)在請求分段系統(tǒng)中，每當發(fā)現(xiàn)運行進程所要訪問的段尚未調(diào)入內(nèi)存時，便由缺段中斷機構(gòu)產(chǎn)生一缺段中斷信號，進入OS后由缺段中斷處理程序?qū)⑺璧亩握{(diào)入內(nèi)存。缺段中斷機構(gòu)與缺頁中斷機構(gòu)類似，它同樣需要在一條指令的執(zhí)行期間，產(chǎn)生和處理中斷，以及在一條指令執(zhí)行期間，可能產(chǎn)生多次缺段中斷。缺段中斷的處理過程如圖所示。由于段不是定長的，這使對缺段中斷的處理要比對缺頁中斷的處理復(fù)雜。

5.5.1請求