操作系統(tǒng)課件CCH09virtual memory

Chapter9VirtualMemoryBackground（背景）DemandPaging（請(qǐng)求頁式）PerformanceofDemandPaging（請(qǐng)求頁式的性能）

PageReplacement（頁置換）ReplacementAlgorithms（頁置換算法）AllocationofFrames（頁框的分配）Thrashing（顛簸）OtherConsiderations（其他考慮）9.1Background為了在內(nèi)存空間運(yùn)行超過內(nèi)存總?cè)萘康拇笞鳂I(yè)或者同時(shí)運(yùn)行大量作業(yè)解決的方法是從邏輯上擴(kuò)充內(nèi)存容量這就是虛擬存儲(chǔ)技術(shù)所要解決的主要問題9.1Background實(shí)現(xiàn)虛擬存儲(chǔ)器要解決:程序部分運(yùn)行可以嗎?發(fā)現(xiàn)程序不在內(nèi)存時(shí),如何將其裝入后繼續(xù)運(yùn)行?內(nèi)存無空間時(shí)怎么辦?9.1BackgroundVirtualmemoryisatechniquethatallowstheexecutionofprocessesthatmaynotbecompletelyinmemory.（虛擬內(nèi)存是一種允許進(jìn)程部分裝入內(nèi)存就可以執(zhí)行的技術(shù)）principleoflocality局部性原理

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

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

-Ifthereisafreeframe,useit

-Ifthereisnofreeframe,useapagereplacement algorithmtoselectavictimframe

Bringthedesiredpageintothe(newly)freeframe;updatethepageandframetables

PageReplacement頁面調(diào)入策略為能使進(jìn)程運(yùn)行，事先需將一部分要執(zhí)行的程序和數(shù)據(jù)調(diào)入內(nèi)存調(diào)入頁面的時(shí)機(jī)

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

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

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

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

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

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

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

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