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

1、第四章存儲器管理 第五章虛擬存儲器5.1 虛擬虛擬存儲器概述存儲器概述5.2請求分頁存儲管理方式請求分頁存儲管理方式5.3頁面置換算法頁面置換算法5.4“抖動抖動”與工作集與工作集5.5請求分段存儲管理方式請求分段存儲管理方式第四章存儲器管理 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)存讓它

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

3、ng.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ī)存儲管理方式的特征和局部性原理常規(guī)存儲管理方式的特征和局部性原理第四章存儲器管理 3.3.虛擬存儲器的基本工作情況虛擬存儲器的基本工作情況基于局部性原理，應(yīng)用程序在運

4、行之前，僅須將那些當(dā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ī)存儲管理方式的特征和局部性原理常規(guī)存儲管理方式的特征和局部性原理第四章存儲器管理 5.1.2虛擬存儲器的定義和特征虛擬存儲器的定義和特征 具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲系統(tǒng)。其邏輯容量是內(nèi)存容量

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

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

7、請求頁表機制在請求分頁系統(tǒng)中所需要的主要數(shù)據(jù)結(jié)構(gòu)是頁表。其基本作用仍然是將邏輯地址變換為物理地址。頁號 物理塊號 狀態(tài)位P 訪問字段A 修改位M 外存地址 請求分頁系統(tǒng)建立在基本分頁基礎(chǔ)上，增加了請求調(diào)頁功能和頁面置換功能。請求分頁系統(tǒng)中的頁表請求分頁系統(tǒng)中的頁表第四章存儲器管理 在請求分頁系統(tǒng)中，每當(dā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)生缺

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

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

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

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

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

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

14、處調(diào)入頁面從何處調(diào)入頁面請求分頁系統(tǒng)中的外存分為文件區(qū)和對換區(qū)。當(dāng)發(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ū)。第四章存儲器管理 3. 頁面調(diào)入過程頁面調(diào)入過程每當(dāng)程序所要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中

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

16、l)置換算法置換算法由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。 頁面置換算法是指選擇換出頁面的算法。不適當(dāng)?shù)乃惴赡軙?dǎo)致進程發(fā)生“抖動”。第四章存儲器管理 u例：例：假定系統(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)存。引用率70770170122010320304243230321201201770101頁框(物理塊）243

17、圖圖 5-3利用最佳頁面置換算法時的置換圖利用最佳頁面置換算法時的置換圖 1.1.最佳最佳(Optimal)置換算法置換算法第四章存儲器管理 2.2.先進先出先進先出(FIFO)頁面置換算法頁面置換算法該算法淘汰最先進入內(nèi)存的頁面。5.3.1最佳置換算法和先進先出置換算法最佳置換算法和先進先出置換算法引用率70770170122010323104430230321013201770201頁框230420423023012712701u例：頁面號引用串： 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. 進程運行時，先將7，0，1三個頁面裝入內(nèi)存。FIFO算法時進行了算法時進行了12次頁面置換次頁面置換第四章存儲器管理 1. LRU(Least Recently Used)置換算法置換算法選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t，當(dāng)須淘汰一個頁面時，選擇t值最大的頁面.5.3.2最近最久未使用和最少使用置換算法最近最久未使用和最少使用置換算法引用率70770170122010320304403230321132201770101頁框402432032102LRU頁面置換算法頁面置換算法 第四章存儲器管理

19、 2 2LRU置換算法的硬件支持置換算法的硬件支持 1) 寄存器移位寄存器，記錄某進程在內(nèi)存中各頁的使用情況。R=Rn-1Rn-2Rn-3 R2R1R0 5.3.2最近最久未使用置換算法和最少使用置換算法最近最久未使用置換算法和最少使用置換算法R 實 頁 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某進程具有某進程具有8個頁面時的個頁面時的LRU訪問情況訪問情況 第四章存儲器管理 2) 2) 棧?？衫靡粋€特殊的棧來保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。假定現(xiàn)有一進程所訪問的頁面號序列為：4，7，0，7，1，0，1，2，1，2，6.隨著進程的訪問，棧中頁面號的變化情況如圖所示。2 2LRU置換算法的硬件支持置換算法的硬件支持4474707407047170410174010741210742120741210742621076第四章存儲器管理 5.3.2最近最久未使用置換算法和最少使用置換算法最近最久未使用置換算法和最少使用置

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

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

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

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

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

26、的四個頁面的情況如下表：物理塊 虛頁號 裝入時間 最后一次訪問時間 訪問位 修改位 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ù)字均為十進制數(shù)，所有時間都是從進程開始運行時，從0開始計數(shù)的時鐘數(shù)。請問，如果系統(tǒng)采用下列置換算法，將選擇哪一頁進行換出？ (1) FIFO算法； (2) LRU算法； (3) 改進的Clock算法. 第四章存儲器管理 思考二思考二 在一個請求分頁系統(tǒng)中，假如一個作業(yè)的頁面走向為4，3，2，1，4，3，5，4，3，2，1，5，目前它還沒有任何頁裝入內(nèi)存，當(dāng)分配給該作業(yè)的物理塊數(shù)目

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

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

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

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

31、 2.缺段中斷機構(gòu)缺段中斷機構(gòu)在請求分段系統(tǒng)中，每當(dā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請求分段中的硬件支持請求分段中的硬件支持第四章存儲器管理 虛段S不在內(nèi)存阻塞請求進程內(nèi)存中有合適的空閑區(qū)嗎？從外存讀入段S修改段表及內(nèi)存空區(qū)鏈喚醒請求進程返回空區(qū)容量總和能否滿足？空區(qū)拼接，以形成一個合適的空區(qū)淘汰一個或幾個實段，以形成一個合適空區(qū)否否是是圖圖5-12請求分段系統(tǒng)中的中斷處理過程請求分段系統(tǒng)中的中斷處理過程 第四章存儲器管理 3. 3.地址變換機構(gòu)地址變換機構(gòu)因為被訪問的段并非全在內(nèi)存，所以在地址