計算機操作系統(tǒng)第5章

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

2、業(yè)留在外存上等待。3 3第五章 虛 擬 存 儲 器5.1.1 常規(guī)存儲管理方式的特征和局部性原理1. 常規(guī)存儲器管理方式的特征我們把前一章中所介紹的各種存儲器管理方式統(tǒng)稱為傳統(tǒng)存儲器管理方式，它們全都具有如下兩個共同的特征：(1) 一次性(2) 駐留性 4 4第五章 虛 擬 存 儲 器2. 局部性原理程序運行時存在的局部性現(xiàn)象，很早就已被人發(fā)現(xiàn)，但直到1968年，P.Denning才真正指出：程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，即在一較短的時間內，程序的執(zhí)行僅局限于某個部分，相應地，它所訪問的存儲空間也局限于某個區(qū)域。 5 5第五章 虛 擬 存 儲 器局限性又表現(xiàn)在下述兩個方面：(1) 時間局限性

3、。(2) 空間局限性。 6 6第五章 虛 擬 存 儲 器3. 虛擬存儲器的基本工作情況 基于局部性原理可知，應用程序在運行之前沒有必要將之全部裝入內存，而僅須將那些當前要運行的少數(shù)頁面或段先裝入內存便可運行，其余部分暫留在盤上。 7 7第五章 虛 擬 存 儲 器5.1.2 虛擬存儲器的定義和特征1. 虛擬存儲器的定義當用戶看到自己的程序能在系統(tǒng)中正常運行時，他會認為，該系統(tǒng)所具有的內存容量一定比自己的程序大，或者說，用戶所感覺到的內存容量會比實際內存容量大得多。但用戶所看到的大容量只是一種錯覺，是虛的，故人們把這樣的存儲器稱為虛擬存儲器。8 8第五章 虛 擬 存 儲 器2. 虛擬存儲器的特征與

4、傳統(tǒng)的存儲器管理方式比較，虛擬存儲器具有以下三個重要特征：(1) 多次性。(2) 對換性。(3) 虛擬性。 9 9第五章 虛 擬 存 儲 器5.1.3 虛擬存儲器的實現(xiàn)方法1. 分頁請求系統(tǒng)1) 硬件支持主要的硬件支持有：(1) 請求分頁的頁表機制。(2) 缺頁中斷機構。(3) 地址變換機構。2) 實現(xiàn)請求分頁的軟件10 10第五章 虛 擬 存 儲 器2. 請求分段系統(tǒng)1) 硬件支持主要的硬件支持有：(1) 請求分段的段表機制。(2) 缺頁中斷機構。(3) 地址變換機構。2) 軟件支持11 11第五章 虛 擬 存 儲 器5.2 請求分頁存儲管理方式5.2.1 請求分頁中的硬件支持為了實現(xiàn)請求分

5、頁，系統(tǒng)必須提供一定的硬件支持。計算機系統(tǒng)除了要求一定容量的內存和外存外，還需要有請求頁表機制、缺頁中斷機構以及地址變換機構。12 12第五章 虛 擬 存 儲 器1. 請求頁表機制在請求分頁系統(tǒng)中需要的主要數(shù)據(jù)結構是請求頁表，其基本作用仍然是將用戶地址空間中的邏輯地址映射為內存空間中的物理地址。為了滿足頁面換進換出的需要，在請求頁表中又增加了四個字段。這樣，在請求分頁系統(tǒng)中的每個頁表應含以下諸項：13 13第五章 虛 擬 存 儲 器2. 缺頁中斷機構(1) 在指令執(zhí)行期間產(chǎn)生和處理中斷信號。(2) 一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁中斷。14 14第五章 虛 擬 存 儲 器圖5-1 涉及6次缺

6、頁中斷的指令15 15第五章 虛 擬 存 儲 器3. 地址變換機構請求分頁系統(tǒng)中的地址變換機構是在分頁系統(tǒng)地址變換機構的基礎上，為實現(xiàn)虛擬存儲器，再增加了某些功能所形成的，如產(chǎn)生和處理缺頁中斷，以及從內存中換出一頁的功能等等。圖5-2示出了請求分頁系統(tǒng)中的地址變換過程。16 16第五章 虛 擬 存 儲 器圖5-2請求分頁中的地址變換過程17 17第五章 虛 擬 存 儲 器5.2.2 請求分頁中的內存分配1. 最小物理塊數(shù)的確定一個顯而易見的事實是，隨著為每個進程所分配的物理塊的減少，將使進程在執(zhí)行中的缺頁率上升，從而會降低進程的執(zhí)行速度。為使進程能有效地工作，應為它分配一定數(shù)目的物理塊，但這并

7、不是最小物理塊數(shù)的概念。18 18第五章 虛 擬 存 儲 器2. 內存分配策略在請求分頁系統(tǒng)中，可采取兩種內存分配策略，即固定和可變分配策略。在進行置換時，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。1) 固定分配局部置換(Fixed Allocation，Local Replacement)2) 可變分配全局置換(Variable Allocation，Global Replacement)3) 可變分配局部置換(Variable Allocation，Local Replacement)19 19第五章 虛 擬 存 儲 器3. 物理塊分配算法在采用固定分配策略時

8、，如何將系統(tǒng)中可供分配的所有物理塊分配給各個進程，可采用下述幾種算法：(1) 平均分配算法，即將系統(tǒng)中所有可供分配的物理塊平均分配給各個進程。 (2) 按比例分配算法，即根據(jù)進程的大小按比例分配物理塊。如果系統(tǒng)中共有n個進程，每個進程的頁面數(shù)為Si，則系統(tǒng)中各進程頁面數(shù)的總和為：n1iiSS2020第五章 虛 擬 存 儲 器又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進程所能分到的物理塊數(shù)為bi可由下式計算：這里，bi應該取整，它必須大于最小物理塊數(shù)。mSSbii21 21第五章 虛 擬 存 儲 器(3) 考慮優(yōu)先權的分配算法。在實際應用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應為它分配較多

9、的內存空間。通常采取的方法是把內存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據(jù)各進程的優(yōu)先權進行分配，為高優(yōu)先進程適當?shù)卦黾悠湎鄳蓊~。在有的系統(tǒng)中，如重要的實時控制系統(tǒng)，則可能是完全按優(yōu)先權為各進程分配其物理塊的。2222第五章 虛 擬 存 儲 器5.2.3 頁面調入策略為使進程能夠正常運行，必須事先將要執(zhí)行的那部分程序和數(shù)據(jù)所在的頁面調入內存?，F(xiàn)在的問題是：(1) 系統(tǒng)應在何時調入所需頁面；(2) 系統(tǒng)應從何處調入這些頁面；(3) 是如何進行調入的。2323第五章 虛 擬 存 儲 器1. 何時調入頁面(1) 預調頁策略。(2) 請求調頁策略。 2424第五章

10、 虛 擬 存 儲 器2. 從何處調入頁面(1) 系統(tǒng)擁有足夠的對換區(qū)空間，這時可以全部從對換區(qū)調入所需頁面，以提高調頁速度。(2) 系統(tǒng)缺少足夠的對換區(qū)空間，這時凡是不會被修改的文件，都直接從文件區(qū)調入；而當換出這些頁面時，由于它們未被修改，則不必再將它們重寫到磁盤(換出)，以后再調入時，仍從文件區(qū)直接調入。但對于那些可能被修改的部分，在將它們換出時便須調到對換區(qū)，以后需要時再從對換區(qū)調入。(3) UNIX方式。 2525第五章 虛 擬 存 儲 器3. 頁面調入過程每當程序所要訪問的頁面未在內存時(存在位為“0”)，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后轉入缺

11、頁中斷處理程序。 2626第五章 虛 擬 存 儲 器4. 缺頁率假設一個進程的邏輯空間為n頁，系統(tǒng)為其分配的內存物理塊數(shù)為m(mn)。如果在進程的運行過程中，訪問頁面成功(即所訪問頁面在內存中)的次數(shù)為S，訪問頁面失敗(即所訪問頁面不在內存中，需要從外存調入)的次數(shù)為F，則該進程總的頁面訪問次數(shù)為A=S+F，那么該進程在其運行過程中的缺頁率即為AFf 2727第五章 虛 擬 存 儲 器事實上，在缺頁中斷處理時，當由于空間不足，需要置換部分頁面到外存時，選擇被置換頁面還需要考慮到置換的代價，如頁面是否被修改過。沒有修改過的頁面可以直接放棄，而修改過的頁面則必須進行保存，所以處理這兩種情況時的時間

12、也是不同的。假設被置換的頁面被修改的概率是，其缺頁中斷處理時間為ta，被置換頁面沒有被修改的缺頁中斷時間為tb，那么，缺頁中斷處理時間的計算公式為t=ta+(1)tb2828第五章 虛 擬 存 儲 器5.3 頁面置換算法在進程運行過程中，若其所要訪問的頁面不在內存，而需把它們調入內存，但內存已無空閑空間時，為了保證該進程能正常運行，系統(tǒng)必須從內存中調出一頁程序或數(shù)據(jù)送到磁盤的對換區(qū)中。但應將哪個頁面調出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法(Page-Replacement Algorithms)。置換算法的好壞將直接影響到系統(tǒng)的性能。2929第五章 虛 擬 存

13、儲 器5.3.1 最佳置換算法和先進先出置換算法1. 最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面將是以后永不使用的，或許是在最長(未來)時間內不再被訪問的頁面。采用最佳置換算法通?？杀ＷC獲得最低的缺頁率。但由于人們目前還無法預知，一個進程在內存的若干個頁面中，哪一個頁面是未來最長時間內不再被訪問的，因而該算法是無法實現(xiàn)的，但可以利用該算法去評價其它算法。 3030第五章 虛 擬 存 儲 器圖5-3利用最佳頁面置換算法時的置換圖31 31第五章 虛 擬 存 儲 器2. 先進先出(FIFO)頁面置換算法FIFO算法是最早出現(xiàn)的

14、置換算法。該算法總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單，只需把一個進程已調入內存的頁面按先后次序鏈接成一個隊列，并設置一個指針，稱為替換指針，使它總是指向最老的頁面。但該算法與進程實際運行的規(guī)律不相適應，因為在進程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。3232第五章 虛 擬 存 儲 器圖5-4 利用FIFO置換算法時的置換圖3333第五章 虛 擬 存 儲 器5.3.2 最近最久未使用和最少使用置換算法1. LRU(Least Recently Used)置換算法的描述FIFO置換

15、算法的性能之所以較差，是因為它所依據(jù)的條件是各個頁面調入內存的時間，而頁面調入的先后并不能反映頁面的使用情況。最近最久未使用(LRU)的頁面置換算法是根據(jù)頁面調入內存后的使用情況做出決策的。 3434第五章 虛 擬 存 儲 器圖5-5LRU頁面置換算法3535第五章 虛 擬 存 儲 器2. LRU置換算法的硬件支持1) 寄存器為了記錄某進程在內存中各頁的使用情況，須為每個在內存中的頁面配置一個移位寄存器，可表示為R=Rn-1Rn-2Rn-3 R2R1R03636第五章 虛 擬 存 儲 器當進程訪問某物理塊時，要將相應寄存器的Rn-1位置成1。此時，定時信號將每隔一定時間(例如100 ms)將寄

16、存器右移一位。如果我們把n位寄存器的數(shù)看作是一個整數(shù)，那么，具有最小數(shù)值的寄存器所對應的頁面，就是最近最久未使用的頁面。 3737第五章 虛 擬 存 儲 器圖5-6 某進程具有8個頁面時的LRU訪問情況3838第五章 虛 擬 存 儲 器2) 棧可利用一個特殊的棧保存當前使用的各個頁面的頁面號。每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。假定現(xiàn)有一進程，它分有五個物理塊，所訪問的頁面的頁面號序列為：4，7，0，7，1，0，1，2，1，2，63939第五章 虛 擬 存 儲 器圖5-7用棧保存當前使用頁

17、面時棧的變化情況4040第五章 虛 擬 存 儲 器3. 最少使用(Least Frequently Used，LFU)置換算法在采用LFU算法時，應為在內存中的每個頁面設置一個移位寄存器，用來記錄該頁面被訪問的頻率。該置換算法選擇在最近時期使用最少的頁面作為淘汰頁。 41 41第五章 虛 擬 存 儲 器5.3.3 Clock置換算法1. 簡單的Clock置換算法當利用簡單Clock算法時，只需為每頁設置一位訪問位，再將內存中的所有頁面都通過鏈接指針鏈接成一個循環(huán)隊列。 4242第五章 虛 擬 存 儲 器圖5-8簡單Clock置換算法的流程和示例4343第五章 虛 擬 存 儲 器2. 改進型Cl

18、ock置換算法在將一個頁面換出時，如果該頁已被修改過，便須將該頁重新寫回到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。換而言之，對于修改過的頁面，在換出時所付出的開銷比未修改過的頁面大，或者說，置換代價大。在改進型Clock算法中，除須考慮頁面的使用情況外，還須再增加一個因素置換代價。 4444第五章 虛 擬 存 儲 器5.3.4 頁面緩沖算法(Page Buffering Algorithm，PBA)1. 影響頁面換進換出效率的若干因素(1) 頁面置換算法。(2) 寫回磁盤的頻率。(3) 讀入內存的頻率。 4545第五章 虛 擬 存 儲 器2. 頁面緩沖算法PBAPBA算法的主要特點是

19、： 顯著地降低了頁面換進、換出的頻率，使磁盤I/O的操作次數(shù)大為減少，因而減少了頁面換進、換出的開銷； 正是由于換入換出的開銷大幅度減小，才能使其采用一種較簡單的置換策略，如先進先出(FIFO)算法，它不需要特殊硬件的支持，實現(xiàn)起來非常簡單。 1) 空閑頁面鏈表2) 修改頁面鏈表4646第五章 虛 擬 存 儲 器5.3.5 訪問內存的有效時間與基本分頁存儲管理方式不同，在請求分頁管理方式中，內存有效訪問時間不僅要考慮訪問頁表和訪問實際物理地址數(shù)據(jù)的時間，還必須要考慮到缺頁中斷的處理時間。 4747第五章 虛 擬 存 儲 器5.4 5.4 “抖動”與工作集 由于請求分頁式虛擬存儲器系統(tǒng)的性能優(yōu)越

20、，在正常運行情況下，它能有效地減少內存碎片，提高處理機的利用率和吞吐量，故是目前最常用的一種系統(tǒng)。但如果在系統(tǒng)中運行的進程太多，進程在運行中會頻繁地發(fā)生缺頁情況，這又會對系統(tǒng)的性能產(chǎn)生很大的影響，故還須對請求分頁系統(tǒng)的性能做簡單的分析。4848第五章 虛 擬 存 儲 器5.4.1 多道程序度與“抖動”1. 多道程序度與處理機的利用率 由于虛擬存儲器系統(tǒng)能從邏輯上擴大內存，這時，只需裝入一個進程的部分程序和數(shù)據(jù)便可開始運行，故人們希望在系統(tǒng)中能運行更多的進程，即增加多道程序度，以提高處理機的利用率。但處理機的實際利用率卻如圖5-9中的實線所示。 4949第五章 虛 擬 存 儲 器圖5-9 處理機

21、的利用率5050第五章 虛 擬 存 儲 器2. 產(chǎn)生“抖動”的原因發(fā)生“抖動”的根本原因是，同時在系統(tǒng)中運行的進程太多，由此分配給每一個進程的物理塊太少，不能滿足進程正常運行的基本要求，致使每個進程在運行時，頻繁地出現(xiàn)缺頁，必須請求系統(tǒng)將所缺之頁調入內存。這會使得在系統(tǒng)中排隊等待頁面調進/調出的進程數(shù)目增加。顯然，對磁盤的有效訪問時間也隨之急劇增加，造成每個進程的大部分時間都用于頁面的換進/換出，而幾乎不能再去做任何有效的工作，從而導致發(fā)生處理機的利用率急劇下降并趨于0的情況。我們稱此時的進程是處于“抖動”狀態(tài)。51 51第五章 虛 擬 存 儲 器5.4.2 工作集1. 工作集的基本概念進程發(fā)

22、生缺頁率的時間間隔與進程所獲得的物理塊數(shù)有關。圖5-10示出了缺頁率與物理塊數(shù)之間的關系。 5252第五章 虛 擬 存 儲 器圖5-10 缺頁率與物理塊數(shù)之間的關系5353第五章 虛 擬 存 儲 器2. 工作集的定義所謂工作集，是指在某段時間間隔里，進程實際所要訪問頁面的集合。Denning指出，雖然程序只需要少量的幾頁在內存便可運行，但為了較少地產(chǎn)生缺頁，應將程序的全部工作集裝入內存中。然而我們無法事先預知程序在不同時刻將訪問哪些頁面，故仍只有像置換算法那樣，用程序的過去某段時間內的行為作為程序在將來某段時間內行為的近似。 5454第五章 虛 擬 存 儲 器圖5-11 窗口為3、4、5時進程

23、的工作集5555第五章 虛 擬 存 儲 器5.4.3 “抖動”的預防方法1. 采取局部置換策略在頁面分配和置換策略中，如果采取的是可變分配方式，則為了預防發(fā)生“抖動”，可采取局部置換策略。 5656第五章 虛 擬 存 儲 器2. 把工作集算法融入到處理機調度中當調度程序發(fā)現(xiàn)處理機利用率低下時，它將試圖從外存調入一個新作業(yè)進入內存，來改善處理機的利用率。 5757第五章 虛 擬 存 儲 器3. 利用“L=S”準則調節(jié)缺頁率Denning于1980年提出了“L=S”的準則來調節(jié)多道程序度，其中L是缺頁之間的平均時間，S是平均缺頁服務時間，即用于置換一個頁面所需的時間。如果是L遠比S大，說明很少發(fā)生

24、缺頁，磁盤的能力尚未得到充分的利用；反之，如果是L比S小，則說明頻繁發(fā)生缺頁，缺頁的速度已超過磁盤的處理能力。只有當L與S接近時，磁盤和處理機都可達到它們的最大利用率。理論和實踐都已證明，利用“L=S”準則，對于調節(jié)缺頁率是十分有效的。5858第五章 虛 擬 存 儲 器4. 選擇暫停的進程當多道程序度偏高時，已影響到處理機的利用率，為了防止發(fā)生“抖動”，系統(tǒng)必須減少多道程序的數(shù)目。 5959第五章 虛 擬 存 儲 器 5.5 請求分段存儲管理方式5.5.1 請求分段中的硬件支持為了實現(xiàn)請求分段式存儲管理，應在系統(tǒng)中配置多種硬件機構，以支持快速地完成請求分段功能。與請求分頁系統(tǒng)相似，在請求分段系

25、統(tǒng)中所需的硬件支持有段表機制、缺段中斷機構，以及地址變換機構。6060第五章 虛 擬 存 儲 器1. 請求段表機制在請求分段式管理中所需的主要數(shù)據(jù)結構是請求段表。在該表中除了具有請求分頁機制中有的訪問字段A、修改位M、存在位P和外存始址四個字段外，還增加了存取方式字段和增補位。這些字段供程序在調進、調出時參考。下面給出請求分段的段表項。61 61第五章 虛 擬 存 儲 器2. 缺段中斷機構在請求分段系統(tǒng)中采用的是請求調段策略。每當發(fā)現(xiàn)運行進程所要訪問的段尚未調入內存時，便由缺段中斷機構產(chǎn)生一缺段中斷信號，進入OS后，由缺段中斷處理程序將所需的段調入內存。與缺頁中斷機構類似，缺段中斷機構同樣需要

26、在一條指令的執(zhí)行期間產(chǎn)生和處理中斷，以及在一條指令執(zhí)行期間，可能產(chǎn)生多次缺段中斷。但由于分段是信息的邏輯單位，因而不可能出現(xiàn)一條指令被分割在兩個分段中，和一組信息被分割在兩個分段中的情況。缺段中斷的處理過程如圖5-12所示。 6262第五章 虛 擬 存 儲 器圖5-12 請求分段系統(tǒng)中的中斷處理過程6363第五章 虛 擬 存 儲 器3. 地址變換機構請求分段系統(tǒng)中的地址變換機構是在分段系統(tǒng)地址變換機構的基礎上形成的。因為被訪問的段并非全在內存，所以在地址變換時，若發(fā)現(xiàn)所要訪問的段不在內存，必須先將所缺的段調入內存，并修改段表，然后才能再利用段表進行地址變換。為此，在地址變換機構中又增加了某些功

27、能，如缺段中斷的請求及處理等。圖5-13示出了請求分段系統(tǒng)的地址變換過程。6464第五章 虛 擬 存 儲 器圖5-13 請求分段系統(tǒng)的地址變換過程6565第五章 虛 擬 存 儲 器5.5.2 分段的共享與保護1. 共享段表(1) 共享進程計數(shù)count。(2) 存取控制字段。(3) 段號。 6666第五章 虛 擬 存 儲 器圖5-14 共享段表項6767第五章 虛 擬 存 儲 器2. 共享段的分配與回收1) 共享段的分配2) 共享段的回收6868第五章 虛 擬 存 儲 器3. 分段保護在分段系統(tǒng)中，由于每個分段在邏輯上是相對獨立的，因而比較容易實現(xiàn)信息保護。目前，常采用以下幾種措施來確保信息的安全。1) 越界檢查2) 存取控制檢查3) 環(huán)保護機構6969第五章 虛 擬 存 儲 器圖5-15 環(huán)保護機構7070第五章 虛 擬 存 儲 器1、虛擬存儲器