Module10:VirtualMemoryBackground（背景）DemandPaging（請求頁式）PerformanceofDemandPaging（請求頁式的性能）

PageReplacement（頁置換）ReplacementAlgorithms（頁置換算法）AllocationofFrames（頁框的分配）Thrashing（顛簸）OtherConsiderations（其他考慮）DemandSegmenation（請求段式）Background為了在內存空間運行超過內存總容量的大作業或者同時運行大量作業解決的方法是從邏輯上擴充內存容量這就是虛擬存儲技術所要解決的主要問題實現虛擬存儲器要解決:程序部分運行可以嗎?發現程序不在內存時,如何將其裝入后繼續運行?內存無空間時怎么辦?虛擬存儲器的引入局部性原理 在一段時間內，程序的執行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區域內。那么程序為什么會出現局部性規律呢？原因可以歸結為以下幾點：程序在執行時，除了少部分的轉移和過程調用指令外，大多數仍是順序執行的。子程序調用將會使程序的執行由一部分內存區域轉至另一部分區域。程序中存在許多循環結構，循環體中的指令被多次執行。程序中還包括許多對數據結構的處理，如對連續的存儲空間——數組的訪問，往往局限于很小的范圍內。Background局部性表現為：

時間局部限性：如果程序中的某條指令一旦執行，則不久的將來該指令可能再次被執行；如果某個存儲單元被訪問，則不久以后該存儲單元可能再次被訪問。產生時間局限性的典型原因是在程序中存在著大量的循環操作。空間局部限性：一旦程序訪問了某個存儲單元，則在不久的將來，其附近的存儲單元也最有可能被訪問。即程序在一段時間內所訪問的地址，可能集中在一定的范圍內，其典型原因是程序是順序執行的。BackgroundBackgroundVirtualmemoryisatechniquethatallowstheexecutionofprocessesthatmaynotbecompletelyinmemory.（虛擬內存是一種允許進程部分裝入內存就可以執行的技術）principleoflocality局部性原理

:時間局部性，空間局部性Onlypartoftheprogramneedstobeinmemoryforexecution（只有運行的部分程序需要在內存中）.Logicaladdressspacecanthereforebemuchlargerthanphysicaladdressspace（邏輯地址空間能夠比物理地址空間大）.Needtoallowpagestobeswappedinandout（必須允許頁面能夠被換入和換出）.VirtualMemoryThatisLargerThanPhysicalMemoryVirtualmemorycanbeimplementedvia（虛擬內存能夠通過以下手段來執行）:Demandpaging（請求頁式）Demandsegmentation（請求段式）虛擬存儲器的特征離散性:在內存分配時采用離散的分配方式，是虛擬存儲器的最基本的特征。多次性:一個作業被分成多次調入內存運行，即在作業運行時沒有必要將其全部裝入，只須將當前要運行的那部分程序和數據裝入內存即可。是虛擬存儲器最重要的特征。對換性:作業運行過程中信息在內存和外存的對換區之間換進、換出。虛擬性:從邏輯上擴充內存容量，使用戶所看到的內存容量遠大于實際內存容量。Background虛擬存儲的基本原理

在程序裝入時裝入當前需要執行的部分頁或段讀入到內存

在程序執行過程中根據缺頁或缺段將相應的頁或段調入到內存

內存中暫時不使用的頁或段調出保存在外存上引入虛擬存儲技術的好處

可在較小的可用內存中執行較大的用戶程序可在內存中容納更多程序并發執行不必影響編程時的程序結構（與覆蓋技術比較）

提供給用戶可用的虛擬內存空間通常大于物理內存(realmemory)DemandPaging在簡單頁式存儲管理的基礎上，增加請求調頁和頁面置換功能形成虛擬存儲系統需解決:取頁--將哪部分裝入內存置頁--將調入的頁放在什么地方淘汰--內存不足時，將哪些頁換出內存DemandPagingBringapageintomemoryonlywhenitisneeded（只有在一個頁需要的時候才把它換入內存）.LessI/Oneeded（需要很少的I/O）Lessmemoryneeded（需要很少的內存）Fasterresponse（快速響應）Moreusers（多用戶）Pageisneeded（需要頁）referencetoit（查閱此頁）invalidreference（無效的訪問）abort（中止）not-in-memory（不在內存）bringtomemory（換入內存）

對進程頁表的修改

缺頁中斷的特殊性

請求分頁中的硬件支持

它是在純分頁系統的基礎上，增加了請求調頁功能、頁面置換功能所形成的頁式虛擬存儲系統，它是目前常用的一種虛擬存儲器的方式。1)請求分頁的頁表機制它是在純分頁的頁表機制上形成的，由于只將應用程序的一部分調入內存，還有一部分仍在磁盤上，故需在頁表中再增加若干項，供程序(數據)在換進、換出時參考。在請求分頁系統中的每個頁表項如圖所示。頁號物理塊號狀態位P訪問字段A修改位M外存地址DemandPaging其中各字段說明如下：狀態位（存在位P）：用于指示該頁是否已調入內存，供程序訪問時參考。訪問字段A：用于記錄本頁在一段時間內被訪問的次數，或最近已有多長時間未被訪問，提供給置換算法選擇換出頁面時參考。修改位M：表示該頁在調入內存后是否被修改過。由于內存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不需將該頁寫回到外存上，以減少系統的開銷和啟動磁盤的次數；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。外存地址：用于指出該頁在外存上的地址，通常是物理塊號，供調入該頁時使用。DemandPaging2）缺頁中斷機構

在請求分頁系統中，每當所要訪問的頁面不在內存時，便要產生一缺頁中斷，請求OS將所缺頁調入內存。與一般中斷的主要區別在于：缺頁中斷在指令執行期間產生和處理中斷信號，而一般中斷在一條指令執行完后檢查和處理中斷信號。缺頁中斷返回到該指令的開始重新執行該指令，而一般中斷返回到該指令的下一條指令執行。一條指令在執行期間，可能產生多次缺頁中斷。DemandPaging3)地址變換機構

請求分頁系統中的地址變換機構，是在分頁系統的地址變換機構的基礎上，再為實現虛擬存儲器而增加了某些功能所形成的，如產生和處理缺頁中斷，以及從內存中換出一頁的功能等等，下圖給出了請求分頁系統的地址變換過程。DemandPaging

缺頁中斷處理是否否 是是否產生缺頁中否是斷請求調頁是開始（程序請求訪問一頁)越界中斷CPU檢索快表頁表項是否在快表中？訪問頁表頁是否在內存中？修改快表修改訪問位和修改位形成物理地址

地址變換結束保留CPU現場

從外存中找到缺頁

頁號>頁表長度？

內存滿否？選擇一頁換出

該頁是否被修改？

將該頁寫回外存

將一頁從外存換入內存

修改頁表

CPU從外存讀缺頁

啟動I/O硬件

StepsinHandlingaPageFaultStepsinhandlingapagefault查找頁表來確定此次地址訪問是否合法如果不合法,則中止該進程;否則如果是發生了缺頁,則需要將其調入內存找到一個空閑物理塊啟動磁盤,把該頁讀入內存讀磁盤結束后,修改頁表以指出該頁已在內存中重新開始執行剛才發生缺頁中斷的指令,這時它可以訪問剛才調入的頁Valid-InvalidBitWitheachpagetableentryavalid–invalidbitisassociated

(1in-memory,0

not-in-memory)（在每一個頁表的表項有一個有效-無效位相關聯，1表示在內存，0表示不內存）Initiallyvalid–invalidbutissetto0onallentries（在所有的表項，這個位被初始化為0）.Exampleofapagetablesnapshot（一個頁表映象的例子）.Duringaddresstranslation,ifvalid–invalidbitinpagetableentryis0（在地址轉換中，如果頁表表項位的值是0）pagefault（缺頁）.1111000Frame#valid-invalidbitpagetablePageFaultIfthereiseverareferencetoapage,firstreferencewilltraptoOS（如果有對一個頁的訪問，第一個訪問要陷入OS）pagefault（缺頁）OSlooksatanothertabletodecide（OS查看另一個表來決定）:Invalidreference（無效引用）abort（終止）.Justnotinmemory（僅僅不在內存）.Getemptyframe（得到空的頁框）.Swappageintoframe（把頁換入頁框）.Resettables,validationbit=1（重新設置頁表，把位設為1）.Restartinstruction（重啟指令）Whathappensifthereisnofreeframe?Pagereplacement–findsomepageinmemory,butnotreallyinuse,swapitout（頁置換—找到內存中并沒有使用的一些頁，換出）.Algorithm（算法）Performance（性能）–wantanalgorithmwhichwillresultinminimumnumberofpagefaults（找出一個導致最小缺頁數的算法）.Samepagemaybebroughtintomemoryseveraltimes（同一個頁可能會被裝入內存多次）.NeedForPageReplacementBasicPageReplacementFindthelocationofthedesiredpageondiskFindafreeframe:

-Ifthereisafreeframe,useit

-Ifthereisnofreeframe,useapagereplacement algorithmtoselectavictimframe

Bringthedesiredpageintothe(newly)freeframe;updatethepageandframetables

PageReplacement調入策略、分配策略分配策略(assignmentpolicy)調入策略(fetchpolicy)(1)

請求調頁(demandpaging)(2)

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

EAT=(1–p)xmemoryaccess +p(pagefaultoverhead +[swappageout] +[swappagein] +[restartoverhead])DemandPagingExampleMemoryaccesstime=1microsecond（存取內存的時間）50%ofthetimethepagethatisbeingreplacedhasbeenmodifiedandthereforeneedstobeswappedout（50%的時間，所置換的頁被修改，因此需要被換出）.SwapPageTime=10msec

（交換頁的時間）

EAT=(1–p)x1+p(10) =1+9P(inmsec)Copy-on-WriteCopy-on-Write(COW)allowsbothparentandchildprocessestoinitiallysharethesamepagesinmemory

Ifeitherprocessmodifiesasharedpage,onlythenisthepagecopiedCOWallowsmoreefficientprocesscreationasonlymodifiedpagesarecopiedFreepagesareallocatedfromapoolofzeroed-outpagesBeforeProcess1ModifiesPageCAfterProcess1ModifiesPageCReplacementAlgorithms在進程運行過程中，如果發生缺頁,而內存中又無空閑塊時，怎么辦?將內存中的某一頁換到磁盤的對換區將哪個頁面調出?根據頁面置換算法來確定置換算法的好壞將直接影響系統的性能，不適當的算法可能會導致進程發生“抖動”（Thrashing)。抖動:剛被換出的頁很快又被訪問，需重新調入，導致系統頻繁地交換頁面，以致大部分CPU時間花費在完成頁面置換的工作上。PageReplacement如果沒有空閑幀，需要兩個頁面傳輸，一個換出，一個換入。可以通過修改位來降低額外開銷。Usemodify(dirty)bittoreduceoverheadofpagetransfers–onlymodifiedpagesarewrittentodisk（修改（臟）位來防止頁面轉移過多—只有被修改的頁面才寫入磁盤）.Pagereplacementcompletesseparationbetweenlogicalmemoryandphysicalmemory–largevirtualmemorycanbeprovidedonasmallerphysicalmemory（頁置換實現了邏輯內存和物理內存的劃分—在一個較小的物理內存基礎之上可以提供一個大的虛擬內存.ReplacementAlgorithms選擇哪些幀進行置換？從理論上講，應將那些以后不再被訪問的頁面換出，或把那些在較長時間內不會再被訪問的頁面換出。存在多種置換算法,都是試圖更接近理論上的目標ReplacementAlgorithmsWantlowestfaultrate（需要一個最小的缺頁率）.Evaluatealgorithmbyrunningitonaparticularstringofmemoryreferences(referencestring)andcomputingthenumberofpagefaultsonthatstring（通過運行一個內存訪問的特殊序列（訪問序列），計算這個序列的缺頁次數）.Inallourexamples,thereferencestringis（在所有的例子中，訪問序列是） 1,2,3,4,1,2,5,1,2,3,4,5.ReplacementAlgorithms1.先進先出算法(FIFO)

Belady現象2.最佳算法(OPT,optimal)3.最近最久未使用算法(LRU,LeastRecentlyUsed)4.LRU近似算法(clock)First-In-First-Out(FIFO)AlgorithmReferencestring:1,2,3,4,1,2,5,1,2,3,4,53frames(3pagescanbeinmemoryatatimeperprocess)4frames

FIFOReplacement–Belady’sAnomaly（FIFO算法可能會產生Belady異常）moreframeslesspagefaults（頁就是更多的頁框相反會產生更多的缺頁）1231234125349pagefaults1231235124510pagefaults443先進先出（FIFO）置換算法Pagefault:15Pagereplacement:12GraphofPageFaultsVersusTheNumberofFramesFirst-In-First-Out(FIFO)AlgorithmFIFOIllustratingBelady’sAnomalyOptimalAlgorithmReplacepagethatwillnotbeusedforlongestperiodoftime（被置換的頁將是之后最長時間不被使用的頁）.4framesexample 1,2,3,4,1,2,5,1,2,3,4,5

Howdoyouknowthis?（怎樣知道的）Usedformeasuringhowwellyouralgorithmperforms（用來衡量你的算法的效率）.12346pagefaults45最佳（Optimal）置換算法Pagefault:9Pagereplacement:6LeastRecentlyUsed(LRU)Algorithm使用離過去最近的情況作為不遠將來的近似，可以選擇最近最少使用的頁進行置換。LRU選擇最長時間沒有使用的頁。LeastRecentlyUsed(LRU)AlgorithmReferencestring:1,2,3,4,1,2,5,1,2,3,4,5

12354435Pagefault:12Pagereplacement:9Counterimplementation（計數器的實現）Everypageentryhasacounter;everytimepageisreferencedthroughthisentry,copytheclockintothecounter（每一個頁表項有一個計數器，每次頁通過這個表項被訪問，把記錄拷貝到計數器中）.Whenapageneedstobechanged,lookatthecounterstodeterminewhicharetochange（當一個頁需要置換時，查看計數器來決定置換哪一個頁.）特點：每次內存訪問時需增加一次寫內存（寫頁表中某一頁的時間域）頁面替換時需檢索頁表以找到時間域最小的頁面。LRUAlgorithm(Cont.)Stackimplementation–keepastackofpagenumbersinadoublelinkform（棧實現—在一個雙鏈表中保留一個記錄頁數目的棧）:Pagereferenced（被訪問的頁）:moveittothetop（移到棧頂）requires6pointerstobechanged（需要改變6個指針）Nosearchforreplacement（沒有為置換進行查找）UseOfAStacktoRecordTheMostRecentPageReferencesLRUApproximationAlgorithms（1）Referencebit（訪問位）Witheachpageassociateabit,initially-=0（每個頁都與一個位相關聯，初始值位0）Whenpageisreferencedbitsetto1（當頁是訪問頁時設位1）.Replacetheonewhichis0(ifoneexists).Wedonotknowtheorder,however（，如果存在的話置換位為0的頁。然而我們并不知道這個置換順序）.LRUApproximationAlgorithms（2）Secondchance（二次機會）Needreferencebit.（需要訪問位）Clockreplacement.（時鐘置換）Ifpagetobereplaced(inclockorder)hasreferencebit=1.Then（如果將要（以順時針）交換某頁的訪問位是1，則）:setreferencebit0（把訪問位設位0）.leavepageinmemory（把頁留在內存中）.replacenextpage(inclockorder),subjecttosamerules（以同樣的規則，替換下一個頁）.如果所有頁的訪問位都為1，則此算法退化為FIFO算法Second-Chance(clock)ReplacementAlgorithmEnhancedSecondchanceAlgorithm不僅考慮頁面的使用情況，還考慮置換代價選擇淘汰頁面時，既要是未被訪問的，還要是未被修改的頁面。實現：設置兩位訪問位（A），修改位（M）

啟動一個進程時，A、M置0A被定期清零內存中的所有頁面被分成為四類:第0類：無訪問，無修改(A=0,M=0)第1類：無訪問，有修改(A=0,M=1)第2類：有訪問，無修改(A=1,M=0)第3類：有訪問，有修改(A=1,M=1)EnhancedSecondchanceAlgorithmOS首先尋找第0類頁面，將找到的第一個頁面淘汰；若沒找到，則找第1類頁面，將找到的第一個頁面淘汰，并將掃描過的頁面的A位全部置為0；若沒找到，則指針回到開始位置，將所有的A位置為0。然后重復第一步。CountingAlgorithmsKeepacounterofthenumberofreferencesthathavebeenmadetoeachpage.（用一個計數器記錄對每一個頁的訪問次數。）LFUAlgorithm:replacespagewithsmallestcount（最少使用算法：置換計數器值最小的一個頁，即訪問次數最少的頁）.MFUAlgorithm:basedontheargumentthatthepagewiththesmallestcountwasprobablyjustbroughtinandhasyettobeused（最常使用算法，認為：最小計數的頁也許剛剛被換入和使用，所以置換計數器值最大的頁）.AllocationofFramesEachprocessneedsminimumnumberofpages（每個進程所需要的最少的頁的數目）.保證進程正常運行所需的最小物理塊數若系統為某進程所分配的物理塊數少于此值時，進程將無法正常運行(頻繁發生缺頁)這個數目取決于指令的格式、功能和尋址方式。Example:IBM370–6pagestohandleSSMOVEinstruction:instructionis6bytes,mightspan2pages.2pagestohandlefrom.2pagestohandleto.Twomajorallocationschemes（兩個主要的分配策略）.fixedallocation（固定分配）priorityallocation（優先分配）FixedAllocationEqualallocation（平均分配）–e.g.,if100framesand5processes,giveeach20pages（例：如果有100個頁框，和5個進程，則每個進程分給20個頁）.Proportionalallocation（按比率分配）–Allocateaccordingtothesizeofprocess（根據每個進程的大小來分配）.PriorityAllocationUseaproportionalallocationschemeusingprioritiesratherthansize（根據優先級而不是大小來使用比率分配策略）.IfprocessPigeneratesapagefault,（如果進程Pi產生一個缺頁）selectforreplacementoneofitsframes（選擇替換其中的一個頁框）.selectforreplacementaframefromaprocesswithlowerprioritynumber（從一個較低優先級的進程中選擇一個頁面來替換）.Globalvs.LocalAllocationGlobalreplacement（全局替換）–processselectsareplacementframefromthesetofallframes;oneprocesscantakeaframefromanother（進程在所有的頁中選擇一個替換頁面；一個進程可以從另一個進程中獲得頁面）.Localreplacement（局部替換）–

eachprocessselectsfromonlyitsownsetofallocatedframes（每個進程只從屬于它自己的頁中選擇）.相對而言，全局替換會帶來較高的系統吞吐率固定分配&局部置換策略：基于進程的類型（交互型或批處理型等），或根據程序員、系統管理員的建議，為每個進程分配固定數目的物理塊，在整個運行期間都不再改變如果進程在運行中發生缺頁，只能從該進程已在內存的頁面中選一頁換出，然后再調入另一頁，保證分配給該進程的內存空間不變。可變分配&全局置換策略：系統為每個進程分配一定數目的物理塊，OS本身也保持一個空閑物理塊隊列當某進程發生缺頁時，系統從空閑物理塊隊列中，取出一物理塊分配給該進程，并將欲調入的缺頁裝入其中。當空閑物理塊隊列中的物理塊用完時，OS才從內存中選擇一頁調出，該頁可能是任一進程的頁。可變分配&局部置換：根據進程的類型或程序員的要求，為每個進程分配一定數目的內存空間，并且在進程運行期間可根據情況（缺頁率）適當增加或減少所分配的物理塊數當某進程發生缺頁時，只允許從該進程已在內存的頁面中選出一頁換出，而不影響其它進程的運行ThrashingIfaprocessdoesnothave“enough”pages,thefaultrateisveryhigh.Thisleadsto（如果一個進程沒有足夠的頁，那么缺頁率將很高，這將導致）:lowCPUutilization（CPU利用率低下）.operatingsystemthinksthatitneedstoincreasethedegreeofmultiprogramming（操作系統認為需要增加多道程序設計的道數）.anotherprocessaddedtothesystem（系統中將加入一個新的進程）.Thrashing（顛簸）

aprocessisbusyswappingpagesinandout（一個進程的頁面經常換入換出）.ThrashingDiagramThrashingSolutionWhydoespagingwork?Localitymodel（局部模型）一個locality是一個進程目前的活躍頁面的集合Locality取決于程序的結構和它的數據結構Processmigratesfromonelocalitytoanother（進程從一個位置移到另一個位置）.Localitiesmayoverlap（位置可能重疊）.Whydoesthrashingoccur?（為什么顛簸會發生）

sizeoflocality>totalmemorysize給每個進程分配的最小物理塊數不能少于locality的大小。這樣，就可以使進程在把它的locality頁全部裝入內存之后，不再發生缺頁Workingset工作集理論是在1968年由Denning提出來的。它正是基于局部的假設。Denning認為，程序在運行時對頁面的訪問是不均勻的，即往往在某段時間內的訪問僅局限于較少的若干個頁面，如果能夠預知程序在某段時間內要訪問哪些頁面，并能將它們提前調入內存，將會大大地降低缺頁率，從而減少置換工作，提高CPU的利用率。基本思想：根據程序的局部性原理，進程在一段時間內總是集中訪問一些頁面(活躍頁面).如果分配給一個進程的物理塊數太少了，使該進程的活躍頁面不能全部裝入內存，則進程在運行過程中將頻繁發生缺頁如果能為進程提供與活躍頁面數相等的物理塊數，則可減少缺頁中斷次數Workingset具體實現：OS跟蹤每個進程的工作集，并為其分配大于其工作集的物理塊數。如果還有空閑物理塊，則可啟動另外的進程。如果所有進程的工作集之和超過了可用物理塊的總數，則OS會選擇暫停一個進程，該進程被換出，所釋放的物理塊可分配給其他進程。Working-SetModelworking-setwindowafixednumberofpagereferences工作集窗口（Δ）是指對于給定的訪問序列選取定長的區間，落在工作集窗口中的頁面集合稱為工作集正確選擇工作集窗口（Δ）的大小，對存儲器的有效利用和系統吞吐量的提高，都將產生重要的影響。WSSi(workingsetofProcessPi)=

totalnumberofpagesreferencedinthemostrecent(variesintime)iftoosmallwillnotencompassentirelocality.iftoolargewillencompassseverallocalities.if=willencompassentireprogram.D=WSSitotaldemandframesifD>mThrashingPolicyifD>m,thensuspendoneoftheprocesses.在WindowsNT中，虛擬存儲管理程序（VirtualMemoryManager)為每一個進程分配一定數量的物理塊，并且這個數目可以進行動態的調整。那么這個數量如何確定？又如何進行動態的調整呢？這個數目就是由每個進程的工作集來確定系統根據主存的負荷和進程的缺頁情況動態地調整進程工作集工作集應用例WindowsNT的虛存管理一個進程在創建時就指定了一個最小工作集和最大工作集，進程運行中所擁有的物理塊數應介于二者之間虛存管理程序維持一個空閑物理塊鏈表。如果一個發生缺頁的進程所擁有的物理塊數低于其最大工作集，則虛存管理程序從空閑物理塊鏈表中取一空閑物理塊分配給該進程；否則，該進程只能按FIFO策略從它自己的內存頁面中選擇一個換出去。WindowsNT的虛存管理在主存負荷不太大時，虛存管理程序允許進程擁有盡可能多的頁面；負荷發生變化時，如空閑物理塊不多了，虛存管理程序就使用“自動調整工作集”的技術來增加主存中可用的自由物理塊。檢查主存中的每個進程，將它當前工作集大小與其最小工作集進行比較。如果大于最小值，則從它的工作集中移去一些頁面作為主存自由頁面，可為其它進程所使用。若主存自由頁面仍然太少，則不斷進行檢查，直到每個進程的工作集都達到最小值為止。FaultFrequencyScheme工作集理論可用于預調頁，用于防止顛簸，但不夠靈活一種更加直接的防止顛簸的方法是控制缺頁頻率（FaultFrequency）：顛簸具有較高的缺頁率，所以通過控制缺頁頻率，可以有效地防止顛簸的發生。FaultFrequencySchemeEstablish“acceptable”faultrate（設置可接受的缺頁率）.Ifactualratetoolow,processlosesframe（如果缺頁率太低，回收一些進程的頁框）.Ifactualratetoohigh,processgainsframe（如果缺頁率太高，就分給進程一些頁框）.OtherConsiderationsPrepaging（預先調頁）ToreducethelargenumberofpagefaultsthatoccursatprocessstartupPrepageallorsomeofthepagesaprocesswillneed,beforetheyarereferencedButifprepagedpagesareunused,I/OandmemorywaswastedAssumespagesareprepagedandα

ofthepagesisusedIscostofs*α

savepagesfaults>or<thanthecostofprepagings*(1-α)unnecessarypages?α

nearzeroprepagingloses

OtherConsiderationsPagesizeselection（頁面尺寸選擇）Fragmentation（碎片）頁面大，則內碎片大tablesize（表大小）頁面小，則頁表占用的空間大I/Ooverhead（I/O開銷）磁盤I/O時間中傳輸時間和數據量有關系，但它占的比例很小，而尋道時間和旋轉延遲時間占了很大的比例。所以頁面尺寸比較大會有利于減少磁盤I/O時間。減少I/O及內存的占用：要求頁面尺寸小減少缺頁率：要求頁面尺寸大總的趨勢：頁面尺寸越來越大，這是由于CPU速度和內存容量的增長超過了磁盤速度的加快OtherConsideration(Cont.)Programstructure（程序結構）ArrayA[1024,1024]ofintegerEachrowisstoredinonepageOneframeProgram1 forj:=1to1