操作系統(tǒng)原理與實踐教程(第四版) 第6章 虛擬存儲器

6.1虛擬存儲器引入6.2虛擬存儲器的實現方法6.3虛擬存儲器的特征6.4請求分頁存儲管理技術

6.5頁面置換算法6.6“抖動”與工作集6.7請求分段存儲管理方式第5章虛擬存儲器第6章

虛擬存儲器6.1虛擬存儲器引入前面所介紹的幾種存儲管理方式有一個共同的特點，都要求將一個作業(yè)全部裝入內存之后才能運行，于是，就可能出現以下兩種情況：(1)有的作業(yè)很大，其要求的內存空間超過了內存總容量，從而導致作業(yè)不能全部被裝入內存，致使該作業(yè)無法運行。(2)有多個作業(yè)要求運行，其要求的內存空間超過了可用的內存空間，只能將少數作業(yè)裝入內存讓它們先運行，而將其它作業(yè)留在外存等待。6.1虛擬存儲器的引入1.傳統(tǒng)存儲管理方式的特征(1)一次性。前面介紹的幾種存儲管理方式有一個共同的特點，都要求將作業(yè)全部裝入內存之后才能運行，即作業(yè)在運行前需要一次性地全部裝入內存，正是這一特征導致了上述兩種情況的發(fā)生。另外，許多作業(yè)在每次運行時，并非要用到全部程序和數據，因此一次性地裝入全部程序和數據，對內存空間是一種極大的浪費。(2)駐留性。作業(yè)裝入內存直到運行結束，便一直駐留在內存中。盡管進程在運行中會因I/O等原因而長期處于阻塞狀態(tài)，或有的程序模塊在運行過一次后就不再需要，但它們都仍將繼續(xù)占用寶貴的內存資源。6.1虛擬存儲器的引入2.局部性原理早在1968年，Denning.P就曾指出：程序的執(zhí)行表現出局部性特征，即程序在執(zhí)行過程中的一個時間段內，程序的執(zhí)行僅局限于某個部分。相應地，它所執(zhí)行的指令地址或操作數地址也局限于一定的存儲區(qū)域中。(1)程序執(zhí)行時，只有少量分支轉移和過程被調用，在大部分情況下仍是順序執(zhí)行的指令。(2)程序中包含許多循環(huán)結構，由相對較少的指令組成，但是它們將多次執(zhí)行。在循環(huán)過程中，計算被限制在程序中很小的相鄰部分中。(3)程序中過程調用的深度限制在小范圍內，很少出現連續(xù)的過程調用，大多數情況下都不超過5。一段時間內，指令引用被局限在很少幾個過程中。(4)對于連續(xù)訪問數組之類的數據結構，往往是對存儲區(qū)域中相鄰位置的數據進行操作。(5)程序中有些部分是彼此互斥的，不是每次運行時都用到，如出錯處理程序。6.1虛擬存儲器的引入2.局部性原理局限性還表現在下述兩個方面；(1)時間局部性。如果程序中的某條指令正在執(zhí)行，則不久后，該指令可能會再次執(zhí)行。同樣，如果某數據被訪問過，則不久后，該數據可能會被再次訪問。時間局部性的產生原因是由于在程序中存在著大量的循環(huán)操作。(2)空間局部性。程序在運行過程中，一旦訪問了某個內存單元，則在不久后，其鄰近的存儲單元也將可能被訪問，即程序在一段時間內所訪問的內存地址，可能集中在一定的范圍之內?？臻g局部性的產生原因是由于程序的順序執(zhí)行。6.1虛擬存儲器的引入3.虛擬存儲器的概念虛擬存儲器是指在具有層次結構存儲器的計算機系統(tǒng)中，具有請求調入和交換功能，為用戶提供一個比實際物理內存容量大得多的可尋址的一種存儲器系統(tǒng)，它能從邏輯上對內存容量進行擴充。其邏輯容量由內存容量和外存容量之和決定，其運行速度接近于內存速度，而每位的成本卻又接近于外存。虛擬存儲器的容量主要受到兩方面的限制：(1)指令中表示地址的字長。一個虛擬存儲器的最大容量是由計算機的地址結構確定的。如：若CPU的有效地址長度為32位，則程序可以尋址的范圍就是0～232-1，即虛存容量為4GB。(2)外存的容量。虛擬存儲器的容量與主存的實際大小沒有直接關系，而是由主存與輔存的容量之和確定。虛擬存儲技術是一種性能非常優(yōu)越的存儲器管理技術，已被廣泛應用于大、中、小型機器和微型機中。6.2虛擬存儲器的實現方法虛擬存儲器的實現都必須建立在離散分配的存儲管理方式基礎上。虛擬存儲系統(tǒng)需要具有請求調頁(段)功能和頁面(分段)置換功能。如果程序執(zhí)行時發(fā)生缺頁或缺段，此時程序就可以利用系統(tǒng)提供的請求調頁(段)功能，將它們調入內存，以使程序能夠繼續(xù)執(zhí)行下去。如果內存已滿，無法裝入新調入的頁(段)，則必須利用一定的頁(段)置換功能，將內存中暫時不用的頁(段)換到外存中，以騰出足夠的空間來存放新調入的頁(段)，從而保證程序的順利執(zhí)行。虛擬存儲器根據地址空間結構的不同可以分為分頁虛擬存儲器和分段虛擬存儲器兩類，也可以把兩者結合起來，構成段頁式虛擬存儲器。6.3虛擬存儲器的特征(1)虛擬性。虛擬內存不是擴大實際的物理內存，而是從邏輯上擴充內存的容量。(2)多次性。多次性是指一個作業(yè)可被分成多次調入內存運行。(3)對換性。對換性是指允許在作業(yè)運行過程中進行換進和換出。虛擬性是以多次性和交換性為基礎的，或者說，只有系統(tǒng)允許作業(yè)分多次調入內存，并能將內存中暫時不運行的程序和數據交換到外存，系統(tǒng)才可能實現虛擬存儲器，而多次性和對換性，又必須建立在離散分配的基礎上。1)進程地址空間分為虛頁實現原理之所以稱虛頁，因為運行時不一定在主存2)運行前裝入部分頁3)運行時訪問的頁面不在內存,缺頁中斷,調入缺頁.4)缺頁中斷,調入新頁時,若內存無空閑塊,則淘汰某頁,把新頁調入.5)地址變換(重定位):類似簡單分頁系統(tǒng),但頁表要增加4項（增加請求調頁、頁面置換功能）6.4請求分頁存儲管理方式第6章虛擬存儲器6.4在簡單頁式存儲管理的基礎上，PMT中增加請求調頁和頁面置換功能。簡單分頁PMT請求頁式進程頁表(PMT)塊號頁號AM外存地址P塊號頁號淘汰此頁寫回外存

M修改位：該頁被寫過否0否,1是,淘汰此頁不寫回外存

A訪問字段：頁面訪問統(tǒng)計,在近期內被訪問的次數，或最近一次訪問到現在的時間間隔.為淘汰算法提供依據

外存地址:通常是外存物理塊號。

P狀態(tài)位:該頁在主存否0否1在地址變換查表時發(fā)現P=0,硬件缺頁中斷第6章虛擬存儲器6.46.4.1請求分頁中的硬件支持產生缺頁中斷請求調頁缺頁中斷處理保留CPU現場選擇一頁換出確定缺頁外存地址此頁修改過否？該頁寫回外存缺頁換入內存修改頁表NY程序請求訪問一頁CPU查快表訪問頁表頁在內存？形成物理地址修改訪問字段和修改位修改快表組織讀缺頁命令啟動I/O開始頁號≧頁表長度？越界中斷頁表項在快表中？YNYN內存滿否？NYNY6.4.2請求分頁中的內存分配1.最小物理塊數的確定

是指能保證進程正常運行所需的最小物理塊數。當系統(tǒng)為進程分配的物理塊數少于此值時，進程將無法運行。進程應獲得的最小物理塊數與計算機的硬件結構有關，取決于指令的格式、功能和尋址方式。為進程分配內存時，將涉及到三個問題：第一，最小物理塊數的確定；第二，物理塊的分配策略；第三，物理塊的分配算法。第6章虛擬存儲器6.42.內存分配策略

固定分配局部置換為每個進程分配一定數目的物理塊，整個運行期間都不再改變。

可變分配全局置換

先為系統(tǒng)中的每個進程分配一定數目的物理塊，而OS自身也保持一定空閑物理塊隊列。當某進程發(fā)現缺頁時，由系統(tǒng)從空閑物理塊隊列中取出一個物理塊分配給該進程，并將欲調入的頁裝入其中。

第6章虛擬存儲器6.46.4.2請求分頁中的內存分配2.內存分配策略

可變分配局部置換

為每個進程分配一定數目的物理塊，當某進程發(fā)現缺頁時，只允許從該進程在內存的頁面中選出一頁換出，這樣就不會影響其它進程的運行。若進程運行過程中頻繁地發(fā)生缺頁中斷，則系統(tǒng)為該進程分配附加的物理塊，直至該進程的缺頁率減少到適當程度為止；反之，可適當減少分配給該進程的物理塊數。第6章虛擬存儲器6.46.4.2請求分頁中的內存分配并非一個進程分配幾個物理塊就可運行,太少可能造成系統(tǒng)抖動。在采用固定分配策略時，如何將系統(tǒng)中可供分配的所有物理塊分配給各進程?？刹捎靡韵聨追N算法：平均分配:將系統(tǒng)中所有可供分配的物理塊平均分配給各個進程。

內存塊平均分給各進程。小進程有利,長進程中斷率高。3.物理塊分配算法第6章虛擬存儲器6.46.4.2請求分頁中的內存分配2)根據進程大小按比例分配:根據進程的大小按比例分配物理塊。

如果系統(tǒng)中共有n個進程，每個進程的頁面數為Si，則系統(tǒng)中個進程頁面數的總和為：3.物理塊分配算法第6章虛擬存儲器6.46.4.2請求分頁中的內存分配再假定系統(tǒng)中可用的物理塊總數為m，則每個進程所能分到的物理塊數bi可由下式計算：3)考慮優(yōu)先權的分配算法:為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應為它們分配較多的內存空間。

通常將可供分配的所有物理塊分成兩部分：一部分按比例分配給各進程。另一部分則根據各進程的優(yōu)先權進行分配，可為高優(yōu)先級進程適當地增加其相應份額。在重要的實時系統(tǒng)中，則可能是完全按優(yōu)先權為各進程分配其物理塊。

3.物理塊分配算法第6章虛擬存儲器6.46.4.2請求分頁中的內存分配6.4.3頁面調入策略1）

預調頁策略：以預測為基礎需要調入某頁時，一次調入該頁以及相鄰的幾個頁。(通常用于進程首次調入內存,可同時調入幾頁)優(yōu)點：提高調頁的I/O效率。缺點：基于預測，若調入的頁在以后很少被訪問，則效率低。常用于程序裝入時的調頁。1.何時調入頁面第6章虛擬存儲器6.46.4.3頁面調入策略2）請求調頁策略：當發(fā)生缺頁時，只調入發(fā)生缺頁時所需的頁面。調入的頁一定會被訪問。優(yōu)點：容易實現。缺點：對外存I/O次數多，開銷較大1.何時調入頁面第6章虛擬存儲器6.46.4.3頁面調入策略通常對換區(qū)的I/O效率比文件區(qū)的高。關于調入頁面的來源，這里有三種做法：1）

從對換區(qū):進程裝入前，將其全部頁面復制到對換區(qū)，以后總是從對換區(qū)調入。執(zhí)行時調入速度快，要求對換區(qū)空間較大。2）

未被修改的頁面從文件區(qū)讀入，而被置換時不需調出；已被修改的頁面從對換區(qū)調入,節(jié)省對換區(qū)空間.被修改過的頁面淘汰時送入對換區(qū)2.從何處調入頁面第6章虛擬存儲器6.46.4.3頁面調入策略通常對換區(qū)的I/O效率比文件區(qū)的高。關于調入頁面的來源，這里有三種做法：2.從何處調入頁面3）

UNIX方式。未運行過的頁面都應從文件區(qū)調入。而對于曾經運行過但又被換出的頁面，應從對換區(qū)調入。又由于UNIX系統(tǒng)允許頁面共享，如果某進程所請求的頁面已經被其他進程調入內存，此時也無須從對換區(qū)調入。第6章虛擬存儲器6.46.4.3頁面調入策略

頁面未在內存時（存在位為“0”），程序向CPU發(fā)出一缺頁中斷申請。

轉入缺頁中斷處理程序調入新頁置換

修改快表訪問內存數據3.頁面調入過程整個頁面的調入過程對用戶是透明的。第6章虛擬存儲器6.46.4.3頁面調入策略

缺頁率：設一個進程的邏輯空間為n頁，系統(tǒng)為其分配的內存物理塊數為m(m≤n)。

如果在進程的運行過程中，訪問頁面成功（即所訪問的頁面在內存中）的次數為S。訪問頁面失?。此L問的頁面需從外存調入）的次數為F。

則總的頁面訪問數次為A=S+F，那么缺頁率為：4.缺頁率第6章虛擬存儲器6.46.4.3頁面調入策略

影響缺頁率的因素

頁面大小進程所分配物理塊的數據頁面置換算法程序固有特性4.缺頁率第6章虛擬存儲器6.46.4.3頁面調入策略

事實上，在缺頁中斷處理時，當由于空間不足，需要置換部分頁面到外存時，選擇置換頁面還需要考慮到置換的代價。

頁面未修改過，直接放棄。

頁面修改過，必須保存。4.缺頁率第6章虛擬存儲器6.4設被置換的頁面被修改的概率為β，其缺頁中斷處理時間為ta，被置換頁面沒有被修改的的缺頁中斷時間為tb。則缺頁中斷處理時間的計算公式是：

請求分頁系統(tǒng)的評價優(yōu)點：請求分頁存儲管理具有分頁存儲管理的全部優(yōu)點，特別是它有效地緩解了碎片的問題。提供了大容量的多個虛擬存儲器；作業(yè)地址空間不再受實際存儲容量的限制；更有效地利用主存；有利于運行多道程序；提高了系統(tǒng)效率，方便了用戶，特別是大作業(yè)用戶；第6章虛擬存儲器6.4缺點：要求有相應的硬件支持，從而增加了成本，如動態(tài)地址變換、快表、缺頁中斷的產生等都要求有相應的硬件支持。缺頁中斷增加了處理機時間的開銷，如頁表的建立與管理、缺頁中斷處理等；頁面淘汰算法如選擇不當，有可能產生抖動現象，為防止抖動，會增加系統(tǒng)的復雜性；雖然減少了碎片，但每個進程的最后一頁內總有一部分空間得不到利用；請求分頁系統(tǒng)的評價第6章虛擬存儲器6.4有一臺16位機，可訪問64K空間，給出的地址長度16位內存為32K。在具有虛擬存儲功能的系統(tǒng)中，允許進程的地址空間=64K（虛地址空間）64K地址空間不能全部裝入內存，部分裝入外存有一個64K的地址空間映象運行時由MMU（MemoryManagementUnit）進行地址變換頁面劃分為4K：64K的虛地址空間可分為0…15（16個頁面）物理空間分為8個塊討論：第6章虛擬存儲器6.4216043XXX5X7XXXX60K-64K…1556K-60K…1452K-56K…1348K-52K…1244K-48K…1140K-44K…1036K-40K…932K-36K…828K-32K…724K-28K…620K-24K…516K-20K…412K-16K…3

8K-12K…24K-8K…10K-4K…0虛地址空間}虛頁28K-32K…724K-28K…620K-24K…516K-20K…412K-16K…38K-12K…24K-8K……10K-4K……0物理地址空間物理塊（虛擬存儲器）第5章虛擬存儲器6.401234567891011121314010100111101000110010111X0X0X01011X01111X0X0X0X015110000000000100001000000000010110頁表VAMA0CPU執(zhí)行

loadR1，8196（2004H）CPU給出虛地址8196送VA，分離出P|W：2|4因存在位為1，故2頁在內存中，其物理塊號為6塊號6送MA的高四位，W送MA的低12位，形成物理地址：24580（6004H）6004H送地址總線讀取數據到寄存器R1。第6章虛擬存儲器6.40缺頁中斷機構：在請求分頁系統(tǒng)中，每當所要訪問的頁面不在內存時，便產生一缺頁中斷，請求OS將所缺之頁調入內存。缺頁中斷同樣需要經歷保護CPU環(huán)境、分析中斷原因、轉入缺頁中斷處理程序進行處理、恢復CPU環(huán)境等幾步。但缺頁與一般中斷相比，有著明顯的區(qū)別，主要表現在：（1）在指令執(zhí)行期間產生和處理中斷信號。（2）一條指令在執(zhí)行期間，可能產生多次中斷。如圖所示例子。123466頁面COPYATOBB:A:指令指令COPYATOB本身跨了兩頁，A和B分別各是一個數據塊，也都跨了兩頁。該指令的執(zhí)行可能產生6次缺頁中斷。第5章虛擬存儲器6.4產生缺頁中斷請求調頁缺頁中斷處理保留CPU現場選擇一頁換出確定缺頁外存地址此頁修改過否？該頁寫回外存缺頁換入內存修改頁表NY程序請求訪問一頁CPU查快表訪問頁表頁在內存？形成物理地址修改訪問字段和修改位修改快表組織讀缺頁命令啟動I/O開始頁號≧頁表長度？越界中斷頁表項在快表中？YNYN內存滿否？NYNY6.5頁面置換算法功能：需要調入頁面時，選擇內存中哪個物理頁面被置換。稱為replacementpolicy。目標： ①把未來不再使用的調出 ②短期內較少使用的頁面調出（根據局部性原理，依據過去的統(tǒng)計數據預測）頁面鎖定(framelocking)：

必須常駐內存的操作系統(tǒng)的關鍵部分，不允許調出，頁表項中加上鎖定標志位(lockbit)。第6章虛擬存儲器6.5最佳置換算法(OPT,optimal)先進先出頁面置換算法(FIFO)最近最久未使用置換算法(LRU,LeastRecentlyUsed)Clock置換算法(clock)其他置換算法最少使用置換算法 (LFU,LeastFrequentlyUsed)

頁面緩沖算法6.5頁面置換算法第6章虛擬存儲器6.51.最佳置換算法(OPT,optimal)選擇被置換頁面： “未來不再使用的” 或“在最長（未來）時間內不再訪問的”這是一種理想情況，實際中是無法預知的，因而不能實現?？捎米髂乘惴ㄐ阅茉u價的依據。Example1:假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1第6章虛擬存儲器6.56.5.1最佳置換算法和先進先出置換算法利用最佳置換算法時的置換圖70120304230321201701770701201201203203243243243203203203201201201201701701√√√√√√缺頁中斷9次，頁面置換6次頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1√√√第6章虛擬存儲器6.5√√17012.先進先出算法(FIFO)FIFO算法是最早出現的置換算法。該算法總是淘汰最先進入內存的頁面，即選擇進入內存中駐留時間最長的頁面進行淘汰。可以把一個進程已調入內存的頁面按先后次序鏈接成一個隊列，并設置一個指針，稱為替換指針，使它總是指向最老的頁面。

該算法性能較差。較早調入的頁往往是經常被訪問的頁，這些頁在FIFO算法下被反復調入和調出，可能產生Belady（貝萊迪）異常。第6章虛擬存儲器6.52.先進先出算法(FIFO)Belady（貝萊迪）異常：在分頁式虛擬存儲器管理中，發(fā)生缺頁時的置換算法采用FIFO（先進先出）算法時，如果對一個進程未分配它所要求的全部頁面，有時就會出現分配的物理塊數目增多，但缺頁率反而提高的異?，F象。即替換策略不符合隨著物理塊數量的增大，缺頁率一定減少的規(guī)律。Belady異常的原因：

FIFO算法的置換特征與進程訪問內存的動態(tài)特征是矛盾的，即被置換的頁面并不是進程不會訪問的。第6章虛擬存儲器6.5利用FIFO置換算法時的置換圖70120304230321201701770701201201231230430420423023023023013012012012712702√√√√√缺頁中斷16次，頁面置換12次701√√√√√√頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1√√√√第6章虛擬存儲器6.5√√√√√6.5.2最近最久未使用和最少使用置換算法一個特殊的棧：把被訪問的頁面移到棧頂，于是棧底的是最久未使用頁面。每個頁面設立移位寄存器：被訪問時左邊最高位置1，周期右移并且最高位補0，于是寄存器數值最小的是最久未使用頁面。選擇內存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。但由于需要記錄頁面使用時間的先后關系，硬件開銷太大。硬件機構如：第6章虛擬存儲器6.51LRU(LeastRecentlyUsed)置換算法的描述利用LRU置換算法時的置換圖70120304230321201701770701201201203203403402432032032032132132102102107107√√√√√缺頁中斷12次，頁面置換9次107√√√√頁面引用序列為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1√√√第6章虛擬存儲器6.5√√√6.6頁面緩沖算法在請求分頁系統(tǒng)中，由于進程在運行時經常會發(fā)生頁面換進換出的情況，所以一個十分明顯的事實就是，頁面換進換出所付出的開銷將對系統(tǒng)性能產生重大的影響。在此，我們首先對影響頁面換進換出效率的若干因素進行分析。6.6.1影響頁面換進換出效率的若干因素1.頁面置換算法。2.寫回磁盤的頻率。3.讀入內存的頻率。6.6.2頁面緩沖算法PBAPBA算法的主要特點是：①顯著地降低了頁面換進、換出的頻率，使磁盤I/O的操作次數大為減少，因而減少了頁面換進、換出的開銷；②正是由于換入換出的開銷大幅度減小，才能使其采用一種較簡單的置換策略，如先進先出（FIFO）算法，它不需要特殊硬件的支持，實現起來非常簡單。1.空閑頁面鏈表2.修改頁面鏈表6.7訪問內存的有效時間（1）被訪問頁在內存中，且其對應的頁表項在快表中。顯然，此時不存在缺頁中斷情況，內存的有效訪問時間（EAT）分為查找快表的時間（λ）和訪問實際物理地址所需的時間（t）:EAT=λ+t（2）被訪問頁在內存中，且其對應的頁表項不在快表中。顯然，此時也不存在缺頁中斷情況，但需要兩次訪問內存，一次讀取頁表，一次讀取數據，另外還需要更新快表。所以，這種情況內存的有效訪問時間可分為查找快表的時間、查找頁表的時間、修改快表的時間和訪問實際物理地址的時間：EAT=λ+t+λ+t=2*（λ+t）（3）被訪問頁不在內存中。因為被訪問頁不在內存中，需要進行缺頁中斷處理，所以這種情況的內存的有效訪問時間可分為查找快表的時間、查找頁表的時間、處理缺頁中斷的時間、更新快表的時間和訪問實際物理地址的時間：假設缺頁中斷處理時間為ε,則EAT=λ+t+ε+λ+t=ε+2*（λ+t）6.8工作集理論和抖動問題從主存中剛剛移走某頁面后，根據請求馬上又調入該頁。這種反復進行入頁和出頁的現象稱為“抖動”，也叫系統(tǒng)顛簸。它會浪費大量的處理機時間，應盡可能避免。產生抖動的直接原因是頁面置換算法選取不當。第5章虛擬存儲器6.86.8“抖動”與工作集請求分頁系統(tǒng)能有效地減少內存碎片，提高處理機的利用率和吞吐量，是目前最常用的一種系統(tǒng)。但如果在系統(tǒng)中運行的進程太多，進程在運行中頻繁地發(fā)生缺頁情況，又會對系統(tǒng)的性能產生很大的影響。6.86.8.1多道程序度與“抖動”第5章虛擬存儲器6.8抖動與工作集1.多道程序度與處理機的利用率100%CPU飽和度利用率0N1NmaxN2N3L/S

抖動6.86.8.1多道程序度與“抖動”第5章虛擬存儲器6.8抖動與工作集1.多道程序度與處理機的利用率100%CPU飽和度利用率0N1NmaxN2N3L/S

抖動在橫軸的開始部分，隨著進程數目的增加，處理機的利用率急劇增加；到達N1時，增速明顯減慢；到達Nmax時，處理機的利用率達到最大，之后開始緩慢下降；到達N2時，處理機的利用率下降加快之所以出現利用率趨于0的情況，是因為系統(tǒng)中出現了“抖動”。第5章虛擬存儲器6.8L是缺頁之間的平均時間，S是平均缺頁服務時間6.8抖動與工作集2.產生“抖動”的原因同時在系統(tǒng)中運行的進程太多，由此分配給每一個進程的物理塊太少，不能滿足進程正常運行的基本要求，致使每個進程在運行時，頻繁地出現缺頁，造成每個進程的大部分時間都用于頁面的換進/換出，而幾乎不能再去做任何有效的工作，從而導致發(fā)生處理機的利用率急劇下降并趨于0的情況。第5章虛擬存儲器6.86.8抖動與工作集6.8.2工作集進程發(fā)生缺頁率的時間間隔與進程所獲得的物理塊數有關從圖中可以看出，缺頁率隨著所分配物理塊數的增加明顯地減少，當物理塊數超過某個數目時，再為進程增加一個物理塊，對缺頁率的改善已不明顯。已無必要再為它分配更多的物理塊。當為某進程所分配的物理塊數低于某個數目時，每減少一塊，對缺頁率的影響都變得十分明顯。應為進程分配更多的物理塊缺頁率上限下限0n物理塊數缺頁率與物理塊數之間的關系第5章虛擬存儲器6.86.8抖動與工作集6.8.2工作集是指在某段時間間隔Δ里，進程實際所要訪問頁面的集合。24151823241718241817171524172418242424152415241524181524181524181524231815231815242318152424231824231815242318151724231724231817242318151817241817242318172423241817241817241817231824182417182417171824171824171824171817182417182415171517181517182424151724151724151718172415172415172415241724171524171518241718241718241715引用頁面序列窗口大小345第5章虛擬存儲器6.86.8抖動與工作集6.8.3“抖動”的預防方法1．采取局部置換策略當某進程發(fā)生缺頁時，只能在分配給自己的內存空間內進行置換，不允許從其它進程去獲得新的物理塊，即使“抖動”也不影響其它進程。2．把工作集算法融入到處理機調度中從外存調入作業(yè)時，先檢查每個進程在內存的駐留頁面是否足夠多。如果已經足夠多，新作業(yè)的調入不會導致缺頁率的增加；反之，如果某些進程的頁面不足，應首先為那些缺頁率居高的作業(yè)增加新的物理塊。第5章虛擬存儲器6.86.8抖動與工作集6.8.3“抖動”的預防方法3.利用“L=S”準則調節(jié)缺頁率利用“L=S”準則調節(jié)多道程序度，L是缺頁之間的平均時間，S是平均缺頁服務時間，即用于置換一個頁面所需的時間。L<S，頻繁發(fā)生缺頁；L>S，很少缺頁；L與S接近，磁盤和處理機都可達到它們的最大利用率。4．選擇暫停的進程掛起某些暫停的進程。第5章虛擬存儲器6.86.9請求分段存儲管理方式在簡單段式存儲管理的基礎上，SMT增加5項:1.請求段表機制1)地址空間分為若干虛段,運行前裝入部分段.2)當訪問的段不在內存時產生“缺段中斷”,把缺的段調入內存.3)如果內存無空閑空間,則置換出暫不用的某個段.很類似虛擬頁式。學習中注意二者差異段號段長內存首址存取權限AMP增補位外存始址基本段式SMT增加的表項第5章虛擬存儲器外存始址增補位PMA存取權限內存首址段長段號基本段式SMT增加的表項1)存取權限:如讀R，寫W，執(zhí)行X2)A訪問字段:段訪問統(tǒng)計,在近期內被訪問的次數， 或近一次訪問到現在的時間間隔.為淘汰算法提供依據。3)M修改位:該段是否被修改過。4)P存在位(狀態(tài)位):該段在主存否。5)增補位:該段動態(tài)增長過否。6)外存始址:該段外存起始盤塊號。第5章虛擬存儲器

內存分配:在虛擬段式管理中是按段對物理內存進行分配，可采用動態(tài)分區(qū)算法。2.缺段中斷處理:(參看圖5-12)1)當指令給出訪問地址:S|W,地址變換機構首先檢查SMT的存在位.2)當存在位表示該段不在內存,則產生缺段中斷請求：①CPU響應中斷,進入中斷處理，把缺的段調入內存,修改SMT和內存空閑區(qū)鏈表.②若內存無合適空閑區(qū),則拼接或置換某段，形成合適的空閑區(qū)，調入新段，修改SMT和內存空閑鏈表.第5章虛擬存儲器6.9圖5-12缺段中斷處理流程第5章虛擬存儲器6.93.地址變換機構:(參看圖5-13)訪問S|WW≦段長？N分段越界中斷處理Y符合存取方式？N分段保護中斷處理Y段S在內存否？N缺段中斷處理Y修改訪問字段A，如果是寫訪問，則置修改位M=1返回形成物理地址：段始址+W是否出錯？E、R、W查P=1？同于基本段式地址變換機構第5章虛擬存儲器6.9

1．共享段表為了實現分段共享，可在系統(tǒng)中配置一張共享段表，所有各共享段都在共享段表中占有一表項。表項中記錄了共享段的段號、段長、內存始址、存在位等信息，并記錄了共享此分段的每個進程的情況。共享段表如圖所示。其中各項說明如下。6.9.2分段的共享與保護第5章虛擬存儲器6.9共享進程計數count。記錄有多少個進程需要共享該分段。存取控制字段。不同進程對該段的存取權限段號。對于一個共享段，不同的進程可以各用不同的段號去共享該段。

圖5-14共享段表項

第5章虛擬存儲器6.9段名段長內存始址狀態(tài)外存始址共享進程計數進程狀態(tài)進程名進程號段號存取控制權限……S2301002H1452就緒P1320R阻塞P2561RWN23501A2CH0693就緒P8682X阻塞P9971R阻塞P32003RD4602B00H12002就緒P201334RW阻塞P32002R共享段表示例第5章虛擬存儲器6.9

2．共享段的分配與回收

1)共享段的分配

對第一個請求使用該共享段的進程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調入該區(qū)，同時將該區(qū)的始址填入請求進程的段表的相應項中，還須在共享段表中增加一表項，填寫有關數據，把count置為1；之后，當又有其它進程需要調用該共享段時，由于該共享段已被調入內存，故此時無