Chapter9VirtualMemoryBackground（背景）DemandPaging（請求頁式）PerformanceofDemandPaging（請求頁式的性能）

PageReplacement（頁置換）ReplacementAlgorithms（頁置換算法）AllocationofFrames（頁框的分配）Thrashing（顛簸）OtherConsiderations（其他考慮）9.1Background為了在內存空間運行超過內存總容量的大作業或者同時運行大量作業解決的方法是從邏輯上擴充內存容量這就是虛擬存儲技術所要解決的主要問題9.1Background實現虛擬存儲器要解決:程序部分運行可以嗎?發現程序不在內存時,如何將其裝入后繼續運行?內存無空間時怎么辦?9.1BackgroundVirtualmemoryisatechniquethatallowstheexecutionofprocessesthatmaynotbecompletelyinmemory.（虛擬內存是一種允許進程部分裝入內存就可以執行的技術）principleoflocality局部性原理

:時間局部性，空間局部性Onlypartoftheprogramneedstobeinmemoryforexecution（只有運行的部分程序需要在內存中）.程序的局部性原理在一段時間內，程序的執行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區域內。程序在執行時，除了少部分的轉移和過程調用指令外，大多數仍是順序執行的。子程序調用將會使程序的執行由一部分內存區域轉至另一部分區域。但在大多數情況下，過程調用的深度都不超過5。程序中存在許多循環結構，循環體中的指令被多次執行。程序中還包括許多對數據結構的處理，如對連續的存儲空間——數組的訪問，往往局限于很小的范圍內。時間局部性：由于程序中存在著大量的循環操作某條指令一旦執行，則不久該指令可能再次被執行；某個存儲單元被訪問，則不久該存儲單元可能再次被訪問。空間局部性：由于程序的順序執行一旦程序訪問了某個存儲單元，則其附近的存儲單元也最有可能被訪問。即程序在一段時間內所訪問的地址，可能集中在一定的范圍內局部性表現9.1BackgroundLogicaladdressspacecanthereforebemuchlargerthanphysicaladdressspace（邏輯地址空間能夠比物理地址空間大）.Needtoallowpagestobeswappedinandout（必須允許頁面能夠被換入和換出）.VirtualMemoryThatisLargerThanPhysicalMemory9.1BackgroundVirtualmemorycanbeimplementedvia（虛擬內存能夠通過以下方法來實現）:Demandpaging（請求頁式）Demandsegmentation（請求段式）虛擬存儲器的特征離散性:在內存分配時采用離散的分配方式，是虛擬存儲器的最基本的特征。多次性:一個作業被分成多次調入內存運行，即在作業運行時沒有必要將其全部裝入，只須將當前要運行的那部分程序和數據裝入內存即可。是虛擬存儲器最重要的特征。對換性:作業運行過程中信息在內存和外存的對換區之間換進、換出。虛擬性:從邏輯上擴充內存容量，使用戶所看到的內存容量遠大于實際內存容量。在分頁系統的基礎上，增加了請求調頁功能、頁面置換功能所形成的虛擬存儲系統需解決:取頁--將哪部分裝入內存置頁--將調入的頁放在什么地方淘汰--內存不足時，將哪些頁換出內存9.2DemandPaging9.2DemandPagingBringapageintomemoryonlywhenitisneeded（只有在一個頁需要的時候才把它裝入內存）.LessI/Oneeded（需要很少的I/O）Lessmemoryneeded（需要很少的內存）Fasterresponse（快速響應）Moreusers（多用戶）HardwareSupportinvalidreference（無效的訪問）abort（中止）not-in-memory（不在內存）bringtomemory（換入內存）9.2.1Pagetablefordemandpaging在分頁的頁表機制上形成增加若干信息項，供程序(數據)在換進、換出時參考頁號物理塊號狀態位P訪問字段A修改位M外存地址狀態位（存在位P）：指示該頁是否已調入內存。訪問字段A：記錄本頁在一段時間內被訪問的次數，或最近已有多長時間未被訪問，提供給置換算法選擇換出頁面時參考。修改位M：表示該頁在調入內存后是否被修改過。外存地址：指出該頁在外存上的地址，供調入該頁時使用。9.2.1

Pagetablefordemandpaging9.2.2Pagefault每當所要訪問的頁面不在內存時，便產生一缺頁中斷(pagefault)，請求OS將所缺頁調入內存。與一般中斷的主要區別在于：缺頁中斷機構在指令執行期間產生和處理中斷信號，而一般中斷在一條指令執行完后檢查和處理中斷信號。缺頁中斷返回到該指令的開始重新執行該指令，而一般中斷返回到該指令的下一條指令執行。一條指令在執行期間，可能產生多次缺頁中斷。9.2.3Addresstranslation在分頁系統地址變換機構的基礎上，增加了:產生和處理缺頁中斷頁面置換功能等StepsinHandlingaPageFaultStepsinhandlingapagefault查找頁表來確定此次地址訪問是否合法如果不合法,則中止該進程;否則如果是發生了缺頁,則需要將其調入內存找到一個空閑物理塊啟動磁盤,把該頁讀入內存讀磁盤結束后,修改頁表以指出該頁已在內存中重新開始執行剛才發生缺頁中斷的指令,這時它可以訪問剛才調入的頁Whathappensifthereisnofreeframe?Pagereplacement–findsomepageinmemory,butnotreallyinuse,swapitout（頁置換—找到內存中并沒有使用的某個頁，換出）.Algorithm（算法）Performance（性能）–wantanalgorithmwhichwillresultinminimumnumberofpagefaults（找出一個導致最小缺頁數的算法）.NeedForPageReplacementBasicPageReplacementFindthelocationofthedesiredpageondiskFindafreeframe:

-Ifthereisafreeframe,useit

-Ifthereisnofreeframe,useapagereplacement algorithmtoselectavictimframe

Bringthedesiredpageintothe(newly)freeframe;updatethepageandframetables

PageReplacement頁面調入策略為能使進程運行，事先需將一部分要執行的程序和數據調入內存調入頁面的時機

預調頁策略：主動的頁面調入策略，即把那些預計很快會被訪問的程序或數據所在的頁面，預先調入內存。預測的準確率不高（50%），主要用于進程的首次調入。也有的系統將預調頁策略用于請求調頁頁面調入策略(續)請求調頁策略：當進程在運行中發生缺頁時，由系統將缺頁調入內存。目前虛擬存儲器系統大多采用此策略。在調頁時須花費較大的系統開銷，如需頻繁啟動磁盤I/O。頁面調入策略(續)從何處調入頁面在虛擬存儲系統中，外存（硬盤）被分成兩部分:文件區和對換區。對換區（連續分配）的磁盤I/O速度比文件區（離散分配）要高。頁面調入策略(續)UNIX系統:對于從未運行過的頁面，都從硬盤文件區(可執行文件)調入對于被換出的頁面，從對換區調入；對于共享頁面，該頁面可能已由其它進程調入內存，此時就無須再從對換區調入。每個作業有一個頁表,還有一個與之對應的磁盤描述項:9.2.4PerformanceofDemandPaging發生缺頁時會導致以下步驟的發生:陷入OS保存該用戶寄存器和進程狀態確定該中斷是一個缺頁中斷檢查該頁面引用是合法的并確定該頁在磁盤上的位置將該頁從磁盤讀入一個空閑物理塊:在磁盤等待隊列中等待直到該請求被處理等待設備尋道延遲將該塊從磁盤傳送至內存為了提高CPU利用率，將CPU分派給其他進程使用9.2.4PerformanceofDemandPaging(Cont.)磁盤I/O完成，產生中斷保存正在執行進程的現場信息（如果第6步執行了）確定中斷來自于磁盤修改頁表以示所缺的頁已進入內存等待CPU再次分派給這個進程恢復該進程的現場信息，包括寄存器、進程狀態、頁表等，恢復執行9.2.4PerformanceofDemandPaging(Cont.)以上步驟并不是在任何情況下都會發生的這里主要的動作是：處理缺頁中斷從磁盤讀入所需的頁重新開始被中斷的進程其中最大的一部分時間開銷為從磁盤讀入所需的頁缺頁率假定作業Ji共有m頁，系統分配給它的主存塊為n塊，這里m>n。如果作業Ji執行過程中總的內存訪問次數為A,成功訪問的次數為S，不成功的訪問次數為F(產生缺頁中斷的次數),則:A=S+F缺頁率:f=F/A9.2.4PerformanceofDemandPagingPageFaultRate0p1.0（缺頁率0p1.0）ifp=0nopagefaults（如果p=0，沒有缺頁）ifp=1,everyreferenceisafault（每次訪問都缺頁）EffectiveAccessTime(EAT)（有效存取時間）

EAT=(1–p)xmemoryaccess +p(pagefaultoverhead +[swappageout] +[swappagein]+[restartoverhead])9.2.5ReplacementAlgorithms在進程運行過程中，如果發生缺頁,而內存中又無空閑塊時，怎么辦?將內存中的某一頁換到磁盤的對換區將哪個頁面調出?根據頁面置換算法來確定9.2.5ReplacementAlgorithms置換算法的好壞將直接影響系統的性能，不適當的算法可能會導致進程發生“抖動”（Thrashing)。抖動:剛被換出的頁很快又被訪問，需重新調入，導致系統頻繁地交換頁面，以致大部分CPU時間花費在完成頁面置換的工作上。9.2.5ReplacementAlgorithmsGoal:WantlowestfaultrateEvaluatealgorithmbyrunningitonaparticularstringofmemoryreferences(referencestring)andcomputingthenumberofpagefaultsonthatstring（通過運行一個內存訪問的特殊序列（訪問序列），計算這個序列的缺頁次數）.9.2.5ReplacementAlgorithms從理論上講，應將那些以后不再被訪問的頁面換出，或把那些在較長時間內不會再被訪問的頁面換出。存在多種置換算法,都是試圖更接近理論上的目標9.2.5ReplacementAlgorithms最佳算法(OPT:optimal)先進先出算法(FIFO)BeLady現象最近最久未使用算法(LRU:LeastRecentlyUsed)LRU的近似算法9.2.5ReplacementAlgorithms最佳（Optimal）置換算法選擇那些永不使用的，或者是在最長時間內不再被訪問的頁面置換出去。要確定哪一個頁面是未來最長時間內不再被訪問的，很難是一種理想化的算法，性能最好，但在實際上難于實現。通常用來評價其它算法。最佳（Optimal）置換算法Pagefault:9Pagereplacement:6先進先出（FIFO）置換算法Pagefault:15Pagereplacement:12GraphofPageFaultsVersusTheNumberofFramesFIFOIllustratingBelady’sAnomaly先進先出（FIFO）置換算法LeastRecentlyUsed(LRU)AlgorithmPagefault:12Pagereplacement:9LeastRecentlyUsed(LRU)AlgorithmCounterimplementation（計數器實現）Everypageentryhasacounter;everytimepageisreferencedthroughthisentry,copytheclockintothecounter（每一個頁表項有一個時間域，給CPU增加一個計數器，每次訪問內存，該計數器值加1。如果某一頁被訪問，則把計數器值拷貝到該頁的時間域中）.Whenapageneedstobechanged,lookatthecounterstodeterminewhicharetochange（當需要進行頁面置換時，查看頁表中每一頁的時間域，選擇該值最小的頁面換出去.）特點：每次內存訪問時需增加一次寫內存（寫頁表中某一頁的時間域）頁面替換時需檢索頁表以找到時間域最小的頁面。LRUAlgorithm(Cont.)Stackimplementation–keepastackofpagenumbersinadoublelinkform（棧實現—用一個雙向鏈表實現一個記錄頁號的棧）:Pagereferenced（被訪問的頁移到棧頂）棧底的頁是最近最少被訪問的Nosearchforreplacement（不用為置換進行查找）每次把一個頁號從棧中移動到棧頂，需修改幾個指針UseOfAStacktoRecordTheMostRecentPageReferences

LRUApproximationAlgorithms(1)在頁表中設一個“引用位”，當某一頁被訪問時，該位由硬件自動置1由頁面管理軟件周期性把所有引用位置0在一個周期T內，某些被訪問過的頁面其引用位為1，而未被訪問過的頁面其引用位為0。當需要置換一頁面時，選擇其引用位為0的頁LRUApproximationAlgorithms(2)Secondchance其基本算法是FIFO實現：FIFO的循環隊列Needreferencebit.（頁表中每一項設置訪問位）Ifpagetobereplacedhasreferencebit=1.Then（如果某頁的訪問位是1，則）:setreferencebit0（把訪問位設為0）.leavepageinmemory（把頁留在內存中）.replacenextpagesubjecttosamerules（以同樣的規則，處理下一個頁）.如果所有頁的訪問位都為1，則此算法退化為FIFO算法

LRUApproximationAlgorithms(2)Second-Chance(clock)ReplacementAlgorithmEnhancedSecondchanceAlgorithm不僅考慮頁面的使用情況，還考慮置換代價選擇淘汰頁面時，既要是未被訪問的，還要是未被修改的頁面。實現：設置兩位訪問位（A），修改位（M）啟動一個進程時，A、M置0A被定期清零EnhancedSecondchanceAlgorithm內存中的所有頁面被分成為四類:第0類：無訪問，無修改(A=0,M=0)第1類：無訪問，有修改(A=0,M=1)第2類：有訪問，無修改(A=1,M=0)第3類：有訪問，有修改(A=1,M=1)EnhancedSecondchanceAlgorithm算法首先尋找第0類頁面，將找到的第一個頁面淘汰若沒找到，則找第1類頁面，將找到的第一個頁面淘汰，并將掃描過的頁面的A位全部置為0；若沒找到，則指針回到開始位置，將所有的A位置為0。然后重復第一步。Counting-BasedAlgorithmsKeepacounterofthenumberofreferencesthathavebeenmadetoeachpage.（用一個計數器記錄對每一個頁的訪問次數。）LFUAlgorithm:replacespagewithsmallestcount（最少使用算法：置換計數器值最小的一個頁，即訪問次數最少的頁）.MFUAlgorithm:basedontheargumentthatthepagewiththesmallestcountwasprobablyjustbroughtinandhasyettobeused（最常使用算法，認為：最小計數的頁也許剛剛被換入和使用，所以置換計數器值最大的頁）.9.2.6AllocationofFrames分配和置換策略分配策略固定分配可變分配置換策略全局置換局部置換Globalvs.LocalAllocationGlobalreplacement（全局替換）–processselectsareplacementframefromthesetofallframes;oneprocesscantakeaframefromanother（發生缺頁時在內存中所有的頁中選擇一個替換頁面；一個進程可以從另一個進程中獲得頁面）.Localreplacement（局部替換）–eachprocessselectsfromonlyitsownsetofallocatedframes（發生缺頁時,進程只能從屬于它自己的頁中選擇一頁換出去）.相對而言，全局替換會帶來較高的系統吞吐率9.2.6AllocationofFrames固定分配&局部置換策略：基于進程的類型（交互型或批處理型等），或根據程序員、系統管理員的建議，為每個進程分配固定數目的物理塊，在整個運行期間都不再改變如果進程在運行中發生缺頁，只能從該進程已在內存的頁面中選一頁換出，然后再調入另一頁，保證分配給該進程的內存空間不變。9.2.6AllocationofFrames可變分配&全局置換策略：系統為每個進程分配一定數目的物理塊，OS本身也保持一個空閑物理塊隊列當某進程發生缺頁時，系統從空閑物理塊隊列中，取出一物理塊分配給該進程，并將欲調入的缺頁裝入其中。當空閑物理塊隊列中的物理塊用完時，OS才從內存中選擇一頁調出，該頁可能是任一進程的頁。9.2.6AllocationofFrames可變分配&局部置換：為每個進程分配一定數目的內存空間，并且在進程運行期間可根據情況（缺頁率）適當增加或減少所分配的物理塊數當某進程發生缺頁時，只允許從該進程已在內存的頁面中選出一頁換出，而不影響其它進程的運行9.2.6AllocationofFrames

在采用固定分配策略時，可采用以下幾種物理塊分配方法：平均分配：將系統中所有可供分配的物理塊，平均分配給各個進程按比例分配：這是根據進程的大小按比例分配物理塊根據進程優先級分配PriorityAllocationUseaproportionalallocationschemeusingprioritiesratherthansize（根據優先級而不是大小來按比率分配的策略）.IfprocessPigeneratesapagefault,（如果進程Pi產生一個缺頁）selectforreplacementoneofitsframes（選擇替換其中的一個頁框）.selectforreplacementaframefromaprocesswithlowerprioritynumber（從一個較低優先級的進程中選擇一個頁面來替換）.ThrashingIfaprocessdoesnothave“enough”pages,thefaultrateisveryhigh.Thisleadsto（如果一個進程沒有足夠的頁，那么缺頁率將很高，這將導致）:lowCPUutilization（CPU利用率低下）.operatingsystemthinksthatitneedstoincreasethedegreeofmultiprogramming（OS認為需要增加多道程序設計的道數）.anotherprocessaddedtothesystem（系統中將加入一個新的進程）.Thrashing（顛簸）aprocessisbusyswappingpagesinandout（一個進程的頁面經常換入換出）.ThrashingDiagramThrashingSolution采用局部置換：若一個進程開始顛簸，則它只能采用局部置換，這樣不會使其它進程也發生顛簸給進程提供足夠的物理塊：根據進程執行的局部模型，來確定進程真正需要多少物理塊ThrashingSolutionLocalitymodel（局部模型）一個locality是一個進程目前的活躍頁面的集合Locality取決于程序的結構和它的數據結構Processmigratesfromonelocalitytoanother（進程從一個局部移到另一個局部）.Localitiesmayoverlap（局部可能重疊）.Whydoesthrashingoccur?（為什么顛簸會發生）

sizeoflocality>totalmemorysize解決：給每個進程分配的最小物理塊數不能少于locality的大小。這樣，就可以使進程在把它的locality頁全部裝入內存之后，不再發生缺頁Workingset工作集理論是在1968年由Denning提出來的。它正是基于局部的假設。Denning認為，程序在運行時對頁面的訪問是不均勻的，即往往在某段時間內的訪問僅局限于較少的若干個頁面，如果能夠預知程序在某段時間內要訪問哪些頁面，并能將它們提前調入內存，將會大大地降低缺頁率，從而減少置換工作，提高CPU的利用率。

Workingset基本思想：根據程序的局部性原理，進程在一段時間內總是集中訪問一些頁面(活躍頁面).如果分配給一個進程的物理塊數太少了，使該進程的活躍頁面不能全部裝入內存，則進程在運行過程中將頻繁發生缺頁如果能為進程提供與活躍頁面數相等的物理塊數，則可減少缺頁中斷次數Workingset具體實現：OS跟蹤每個進程的工作集，并為其分配大于其工作集的物理塊數。如果還有空閑物理塊，則可啟動另外的進程。如果所有進程的工作集之和超過了可用物理塊的總數，則OS會選擇暫停一個進程，該進程被換出，所釋放的物理塊可分配給其他進程。工作集窗口（Δ）

：是指對于給定的訪問序列選取定長的區間，落在工作集窗口中的頁面集合稱為工作集正確選擇工作集窗口（Δ）的大小，對存儲器的有效利用和系統吞吐量的提高，都將產生重要的影響。Workingset在WindowsNT中，虛擬存儲管理程序（VirtualMemoryManager)為每一個進程分配一定數量的物理塊，并且這個數目可以進行動態的調整。那么這個數量如何確定？又如何進行動態的調整呢？這個數目就是由每個進程的工作集來確定系統根據主存的負荷和進程的缺頁情況動態地調整進程工作集工作集應用例WindowsNT的虛存管理一個進程在創建時就指定了一個最小工作集和最大工作集，進程運行中所擁有的物理塊數應介于二者之間虛存管理程序維持一個空閑物理塊鏈表如果一個發生缺頁的進程所擁有的物理塊數低于其最大工作集，則虛存管理程序從空閑物理塊鏈表中取一空閑物理塊分配給該進程；否則，該進程只能按FIFO策略從它自己的內存頁面中選擇一個換出去。WindowsNT的虛存管理在主存負荷不太大時，虛存管理程序允許進程擁有盡可能多的頁面；負荷發生變化時，如空閑物理塊不多了，虛存管理程序就使用“自動調整工作集”的技術來增加主存中可用的自由物理塊。檢查主存中的每個進程，將它當前工作集大小與其最小工作集進行比較。如果大于最小值，則從它的工作集中移去一些頁面作為主存自由頁面，可為其它進程所使用。若主存自由頁面仍然太少，則不斷進行檢查，直到每個進程的工作集都達到最小值為止。FaultFrequencyScheme工作集理論可用于預調頁，用于防止顛簸，但不夠靈活一種更加直接的防止顛簸的方法是控制缺頁頻率（FaultFrequency）：顛簸具有較高的缺頁率，所以通過控制缺頁頻率，可以有效地防止顛簸的發生。FaultFrequencySchemeEstablish“acceptable”faultrate（設置可接受的缺頁率）.Ifactualratetoolow,processlosesframe（如果缺頁率太低，回收一些進程的頁框）.Ifactualratetoohigh,processgainsframe（如果缺頁率太高，就分給進程一些頁框）.OtherIssues--PrepagingPrepagingToreducethelargenumberofpagefaultsthatoccursatprocessstartupPrepageallorsomeofthepagesaprocesswillneed,beforetheyarereferencedButifprepagedpagesareunused,I/OandmemorywaswastedOtherIssues–PagesizePagesizeselection（頁面尺寸選擇）Fragmentation：頁面大，則內碎片大Pagetablesize：頁面小，則頁表占用的空間大I/Ooverhead：磁盤I/O時間中傳輸時間和數據量有關系，但它占的比例很小，而尋道時間和旋轉延遲時間占了很大的比例。所以頁面尺寸比較大會有利于減少磁盤I/O時間。減少內存的占用：要求頁面尺寸小減少缺頁率：要求頁面尺寸大總的趨勢：頁面尺寸越來越大，這是由于CPU速度和內存容量的增長超過了磁盤速度的加快OtherIssues–TLBReachTLBReach-Theamountofmemoryaccessiblefromthe