第七章虛擬存儲器

第七章虛擬存儲器*計算機操作系統(tǒng)7.1

虛擬存儲器的基本概念7.2

請求分頁存儲器管理方式7.3

請求分段存儲器管理方式7.4

操作系統(tǒng)軟件*計算機操作系統(tǒng)7.1虛擬存儲器的基本概念實存管理有兩個明顯的特性：

一次性：作業(yè)一次全部入主存；

駐留性：作業(yè)進入主存后一直駐留直到完成。實存管理的不足：一、虛擬存儲器的定義

從用戶角度，將系統(tǒng)可提供的比實際大很多的內存容量，稱為虛擬存儲器。二、局部性原理1、程序訪問的局部性，總是局限在程序中某一個部分。2、局部性原理：描述了一個進程中程序和數(shù)據(jù)引用的集簇傾向。

虛存的4個特征三、虛存的2種實現(xiàn)方式請求分頁系統(tǒng)和請求分段系統(tǒng)。1、硬件支持：頁/段表擴充，缺頁/段中斷，地址變換2、操作系統(tǒng)必須有管理頁或段在主存和輔存之間移動的軟件。*計算機操作系統(tǒng)1、離散性：采用離散分配方式；2、多次性：一個作業(yè)分成多次調入主存運行；3、對換性：將得不到運行的程序、數(shù)據(jù)調至外存盤交換區(qū)；4、虛擬性：四、虛存的4個特征*計算機操作系統(tǒng)7.2請求分頁存儲器管理方式一、頁表機制

頁號，頁框號，狀態(tài)位P，訪問位A，修改位M，外存地址二、缺頁中斷機構與一般中斷的2點區(qū)別：

1、是在指令執(zhí)行期間，發(fā)現(xiàn)指令/數(shù)據(jù)不在主存時產(chǎn)生并處理；

2、一條指令在執(zhí)行期間，可能會產(chǎn)生多次缺頁中斷。要求系統(tǒng)能保存多次中斷的狀態(tài)。（例）地址變換*計算機操作系統(tǒng)3、多次缺頁中斷示例設：主存頁框大小為128字，有128*128的數(shù)組；VarA:array[1..128]ofarray[1..128]ofinteger;程序段：fori:=1to128forj:=1to128A[i][j]:=0;數(shù)組元素的存放格式為以行為主序，問：執(zhí)行時缺頁次數(shù)為多少？A[1,1]A[1,2]A[1,3]...A[1,128]...A[128,1]A[128,2]A[128,3]...A[128,128]...1頁1頁82、邏輯地址結構和頁表結構94、地址裝換過程：*計算機操作系統(tǒng)三、頁表組織方式頁面分配1、放置頁表需要大量的內存空間2、頁表也可以存儲在虛擬內存中3、當程序運行時，只需要訪問頁表的一部分。11舉例：兩極層次頁表四、兩級頁表

12五反向頁表：InvertedPageTable（1）、哈希表（2）、反向頁表包含的內容PagenumberProcessidentifierControlbitsChainpointer133、使用鏈接技術解決哈希沖突問題4、反向頁表中的第i項對應與第i幀。5、“反向”使用幀號而不是虛擬頁號來索引頁表項。1415六、轉移后備緩沖區(qū)（1）TLB提出的必要性每個虛存可能引起兩次物理內存訪問：OnetofetchthepagetableOnetofetchthedata為了克服這個問題，為頁表項使用一個特殊的高速緩存。CalledaTranslationLookasideBuffer(TLB)16給定一個虛擬地址，處理器首先檢查TLB如果所需要的頁表項在其中(TLBhit),檢索幀號并形成實地址。

如果沒有找到所需要的頁表項(TLBmiss),處理器用頁號檢索進程頁表，若“存在位”置位，更新TLB。如果“存在位”沒有，將產(chǎn)生一次頁錯誤，離開硬件作用范圍，調用操作系統(tǒng)。（2）實現(xiàn)過程或者TLB的用法1718（3）TLB的組織19（4）虛存機制與主存中高速緩存的交互20七、頁的大?。?）頁越小：內部碎片總量少頁越大：更有效的數(shù)據(jù)塊傳遞（2）頁尺寸對于也錯誤發(fā)生概率的影響。如下圖所示（3）頁尺寸的設計問題與物理主存大小和程序有關。主存變大，應用程序使用的地址空間增長。多線程應用/面向對象技術降低局部性。

TLB大小的確定：不能像主存增長那么快。解決方法：使用大小不等的多種頁尺寸。2122ExamplePageSizes237.3請求式分段存儲管理段的大小不相等，并且是動態(tài)的。優(yōu)點：1、簡化不斷增長的數(shù)據(jù)結構處理。2、允許程序獨立地改變或者重新編譯。3、有助于進程間的共享。4、有助于保護。*計算機操作系統(tǒng)請求分段中的硬件支持一、段表機制

段名，段長，內存起址，狀態(tài)位，存取方式，訪問位，修改位，增補位，外存起址二、缺段中斷

在一條指令的執(zhí)行期間，產(chǎn)生并處理中斷，且可能產(chǎn)生多次缺段中斷。三、地址變換機構

分段的共享與保護25SegmentTableEntries263、分段系統(tǒng)中的地址轉換*計算機操作系統(tǒng)

共享方式：每個共享進程段表中，在相應共享段表目中，指向共享段在內存的起址即可。系統(tǒng)實現(xiàn)：一、設置共享段表/現(xiàn)行分段表二、建立共享段分配、回收操作過程三、完善分段保護機制，有3種常用措施：

1、越界檢查：

2、存取控制檢查：

3、環(huán)保護機構：類似于軟件的層次結構，每層有不同的優(yōu)先數(shù)，0環(huán)為操作系統(tǒng)。2個訪問規(guī)則：

A、一個程序可以訪問同環(huán)或低優(yōu)先權環(huán)中數(shù)據(jù)；

B、一個程序可以調用同環(huán)或高優(yōu)先權環(huán)中的服務；分段的共享與保護*計算機操作系統(tǒng)共享段表說明：

1、共享段只有當所有共享進程都不再需要時(Count=0)，才會被釋放；

2、對同一個共享段，不同進程可以使用不同的段號來共享該段。段名段長內存起址狀態(tài)外存起址

共享進程計數(shù)Count狀態(tài)進程名進程號段號存取控制......

*計算機操作系統(tǒng)共享段的分配、回收分配：

第一個請求使用共享段的進程申請內存分區(qū)，調入，修改共享段表相應內容；以后其它進程使用該共享段時，首先在本進程段表中填入該共享段的物理地址；然后在共享段表中增加一表目，填入進程名，存取控制等信息，并完成Count+1?；厥眨?/p>

執(zhí)行Count-1，取消共享段表中的表目

307.4請求式段頁式管理

CombinedPagingandSegmentation1、基本概念分頁對程序員是透明的，消除外部碎片，有效使用主存Pagingistransparenttotheprogrammer分段對程序員是可見的。處理不斷增長的數(shù)據(jù)結構能力，支持共享和保護。Segmentationisvisibletotheprogrammer用戶地址空間被程序員劃分為多個段，每個段劃分為多個固定大小的頁。Eachsegmentisbrokenintofixed-sizepages311、CombinedSegmentationandPaging322、段頁式系統(tǒng)中的地址轉換333、保護與共享7.4操作系統(tǒng)軟件

一、讀取策略

1、讀策略確定一頁合適取入主存請求式分頁：只有當訪問到某一頁的一個單元時才將該頁取入主存。預約式分頁：讀取的頁并不是頁錯誤請求的頁。適應于：進程第一次啟動和發(fā)生頁錯誤時。與交換的區(qū)別：交換以作業(yè)為單位。二、放置策略決定進程塊駐留在主存什么位置。分段：最佳適配，首次適配。分頁：如何放置沒有關系。非一致存儲訪問多處理器：機器中分布的共享內存可以被機器的任何處理器訪問。訪問特定物理單元所需要的時間隨著處理器和內存之間的距離而變化。依賴于駐留集的位置與使用數(shù)據(jù)處理器間的距離。因此，希望把頁分配到能夠提供最佳性能的內存。三、替換策略

“抖動”(Thrashing)：剛剛被換出的頁很快又被訪問，需再次調入。使進程花費大部分時間進行頁面的置換，稱進程發(fā)生了“抖動”。1、幀鎖定2、基本算法（1）最佳算法OPT選擇替換下次訪問距當前時間最長的那些頁。最少的頁錯誤不可能實現(xiàn)，作為一種標準來衡量其他算法。（2）最近最少使用LRU替換主存中上次使用距當前最遠的頁。（3）先進先出FIFO替換主存中時間最長的頁。三種算法比較：LRU效果好，但需要大量的開銷（時間標簽，維護訪問頁的棧）FIFO實現(xiàn)簡單但性能差。OPT只能作為衡量依據(jù)。（4）時鐘策略

a、某一頁首次裝入主存中的某一幀時，使用位為1，指針下移。

b、該頁隨后被訪問到時，它的使用位為1。指針不移動。

c、替換時，查找使用位為0的幀，若找到，發(fā)生頁面替換后，指針下移，每遇到使用位為1的幀重新置0，指針后移。

d、若所有位為1，把所有位置0，并且指針停留下最初位置，替換該幀的頁，替換后，指針后移。*計算機操作系統(tǒng)

為避免抖動的發(fā)生，應選擇合適的置換算法。一、最佳置換算法二、先進先出置換算法（FIFO）（例）三、最近最久未使用置換算法(LeastRecentlyUsed)

思想：記錄頁面上次被訪問的時間，選擇最近最久未使用的頁面淘汰。（例）

比較FIFO與LRU得出何結論？

頁面置換算法（續(xù)1）404142434、ComparisonofPlacementAlgorithms四、駐留集管理駐留集：進程執(zhí)行中的任何時候在主存中那部分集合。固定分配：為一個進程分配固定數(shù)目的幀?？勺兎峙洌悍峙浣o一個進程的頁幀在進程的生命周期中不斷發(fā)生變化。*計算機操作系統(tǒng)分配算法分配：固定/可變；置換：局部/全局。

1、固定分配，局部置換；

2、可變分配，全局置換；先分配一定數(shù)額，OS保留一個空閑頁框隊列。進程缺頁時，申請新頁框：有，追加分配；無，全局置換。

3、可變分配，局部置換；先分配一定數(shù)額，OS保留一個空閑頁框隊列。進程缺頁時，申請新頁框：有，追加分配；無，局部置換。*計算機操作系統(tǒng)進程缺頁率高，不僅會使其運行進度減慢，而且增加了CPU開銷和通道及外設的負擔。1968年，Denning根據(jù)程序的局部性理論(進程對頁的訪問不是均勻的，而是集中的。進程訪問頁面集合的變化，從一個時間段到另一個時間段是緩慢過渡的)，提出了工作集理論(屬LRU算法的發(fā)展)。

工作集：進程在某段時間內實際訪問頁的集合。

五、工作集/駐留集(WorkingSet)具體表述*計算機操作系統(tǒng)

設進程在t-到t時間段內訪問頁的工作集記為：W(t,)（為工作集窗口尺寸）則：|W(t,)|為工作集中包含的頁面數(shù)工作集W是二元函數(shù)：

1、W是t的函數(shù)，隨時間不同，工作集不同；2、W是的非降函數(shù)。若過大，甚至將整個作業(yè)地址空間包含在內，則失去虛存意義；過小，會導致頻繁缺頁。

工作集的具體表述抖動的產(chǎn)生和預防WorkingSetTheworkingsetwithparameterforaprocessatvirtualtimet,W(t，),isthesetofpagesofthatprocessthathavebeenreferencedinthelastvirtualtimeunits0,1,0,1,0,2,3,4,1,3,/……/4,2,5,3,4,5,3,4,2,0,/……/1,0,1,1,1,2,1,1,0,2,/……/1,1,2,1,2,0,0,1,2,/