第七章虛擬存儲(chǔ)器

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

虛擬存儲(chǔ)器的基本概念7.2

請(qǐng)求分頁存儲(chǔ)器管理方式7.3

請(qǐng)求分段存儲(chǔ)器管理方式7.4

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

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

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

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

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

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

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

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

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

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

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

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

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

分段的共享與保護(hù)25SegmentTableEntries263、分段系統(tǒng)中的地址轉(zhuǎn)換*計(jì)算機(jī)操作系統(tǒng)

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

1、越界檢查：

2、存取控制檢查：

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

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

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

1、共享段只有當(dāng)所有共享進(jìn)程都不再需要時(shí)(Count=0)，才會(huì)被釋放；

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

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

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

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

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

307.4請(qǐng)求式段頁式管理

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

一、讀取策略

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

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

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

b、該頁隨后被訪問到時(shí)，它的使用位為1。指針不移動(dòng)。

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

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

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

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

比較FIFO與LRU得出何結(jié)論？

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

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

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

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

工作集：進(jìn)程在某段時(shí)間內(nèi)實(shí)際訪問頁的集合。

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

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

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

工作集的具體表述抖動(dòng)的產(chǎn)生和預(yù)防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,/