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

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

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

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

-Ifthereisafreeframe,useit

-Ifthereisnofreeframe,useapagereplacement algorithmtoselectavictimframe

Bringthedesiredpageintothe(newly)freeframe;updatethepageandframetables

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

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

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

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

LRUApproximationAlgorithms(2)Second-Chance(clock)ReplacementAlgorithmEnhancedSecondchanceAlgorithm不僅考慮頁(yè)面的使用情況，還考慮置換代價(jià)選擇淘汰頁(yè)面時(shí)，既要是未被訪問(wèn)的，還要是未被修改的頁(yè)面。實(shí)現(xiàn)：設(shè)置兩位訪問(wèn)位（A），修改位（M）啟動(dòng)一個(gè)進(jìn)程時(shí)，A、M置0A被定期清零EnhancedSecondchanceAlgorithm內(nèi)存中的所有頁(yè)面被分成為四類:第0類：無(wú)訪問(wèn)，無(wú)修改(A=0,M=0)第1類：無(wú)訪問(wèn)，有修改(A=0,M=1)第2類：有訪問(wèn)，無(wú)修改(A=1,M=0)第3類：有訪問(wèn)，有修改(A=1,M=1)EnhancedSecondchanceAlgorithm算法首先尋找第0類頁(yè)面，將找到的第一個(gè)頁(yè)面淘汰若沒(méi)找到，則找第1類頁(yè)面，將找到的第一個(gè)頁(yè)面淘汰，并將掃描過(guò)的頁(yè)面的A位全部置為0；若沒(méi)找到，則指針回到開始位置，將所有的A位置為0。然后重復(fù)第一步。Counting-BasedAlgorithmsKeepacounterofthenumberofreferencesthathavebeenmadetoeachpage.（用一個(gè)計(jì)數(shù)器記錄對(duì)每一個(gè)頁(yè)的訪問(wèn)次數(shù)。）LFUAlgorithm:replacespagewithsmallestcount（最少使用算法：置換計(jì)數(shù)器值最小的一個(gè)頁(yè)，即訪問(wèn)次數(shù)最少的頁(yè)）.MFUAlgorithm:basedontheargumentthatthepagewiththesmallestcountwasprobablyjustbroughtinandhasyettobeused（最常使用算法，認(rèn)為：最小計(jì)數(shù)的頁(yè)也許剛剛被換入和使用，所以置換計(jì)數(shù)器值最大的頁(yè)）.9.2.6AllocationofFrames分配和置換策略分配策略固定分配可變分配置換策略全局置換局部置換Globalvs.LocalAllocationGlobalreplacement（全局替換）–processselectsareplacementframefromthesetofallframes;oneprocesscantakeaframefromanother（發(fā)生缺頁(yè)時(shí)在內(nèi)存中所有的頁(yè)中選擇一個(gè)替換頁(yè)面；一個(gè)進(jìn)程可以從另一個(gè)進(jìn)程中獲得頁(yè)面）.Localreplacement（局部替換）–eachprocessselectsfromonlyitsownsetofallocatedframes（發(fā)生缺頁(yè)時(shí),進(jìn)程只能從屬于它自己的頁(yè)中選擇一頁(yè)換出去）.相對(duì)而言，全局替換會(huì)帶來(lái)較高的系統(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ā)生缺頁(yè)，只能從該進(jìn)程已在內(nèi)存的頁(yè)面中選一頁(yè)換出，然后再調(diào)入另一頁(yè)，保證分配給該進(jìn)程的內(nèi)存空間不變。9.2.6AllocationofFrames可變分配&全局置換策略：系統(tǒng)為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，OS本身也保持一個(gè)空閑物理塊隊(duì)列當(dāng)某進(jìn)程發(fā)生缺頁(yè)時(shí)，系統(tǒng)從空閑物理塊隊(duì)列中，取出一物理塊分配給該進(jìn)程，并將欲調(diào)入的缺頁(yè)裝入其中。當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，OS才從內(nèi)存中選擇一頁(yè)調(diào)出，該頁(yè)可能是任一進(jìn)程的頁(yè)。9.2.6AllocationofFrames可變分配&局部置換：為每個(gè)進(jìn)程分配一定數(shù)目的內(nèi)存空間，并且在進(jìn)程運(yùn)行期間可根據(jù)情況（缺頁(yè)率）適當(dāng)增加或減少所分配的物理塊數(shù)當(dāng)某進(jìn)程發(fā)生缺頁(yè)時(shí)，只允許從該進(jìn)程已在內(nèi)存的頁(yè)面中選出一頁(yè)換出，而不影響其它進(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í)而不是大小來(lái)按比率分配的策略）.IfprocessPigeneratesapagefault,（如果進(jìn)程Pi產(chǎn)生一個(gè)缺頁(yè)）selectforreplacementoneofitsframes（選擇替換其中的一個(gè)頁(yè)框）.selectforreplacementaframefromaprocesswithlowerprioritynumber（從一個(gè)較低優(yōu)先級(jí)的進(jìn)程中選擇一個(gè)頁(yè)面來(lái)替換）.ThrashingIfaprocessdoesnothave“enough”pages,thefaultrateisveryhigh.Thisleadsto（如果一個(gè)進(jìn)程沒(méi)有足夠的頁(yè)，那么缺頁(yè)率將很高，這將導(dǎo)致）:lowCPUutilization（CPU利用率低下）.operatingsystemthinksthatitneedstoincreasethedegreeofmultiprogramming（OS認(rèn)為需要增加多道程序設(shè)計(jì)的道數(shù)）.anotherprocessaddedtothesystem（系統(tǒng)中將加入一個(gè)新的進(jìn)程）.Thrashing（顛簸）aprocessisbusyswappingpagesinandout（一個(gè)進(jìn)程的頁(yè)面經(jīng)常換入換出）.ThrashingDiagramThrashingSolution采用局部置換：若一個(gè)進(jìn)程開始顛簸，則它只能采用局部置換，這樣不會(huì)使其它進(jìn)程也發(fā)生顛簸給進(jìn)程提供足夠的物理塊：根據(jù)進(jìn)程執(zhí)行的局部模型，來(lái)確定進(jìn)程真正需要多少物理塊ThrashingSolutionLocalitymodel（局部模型）一個(gè)locality是一個(gè)進(jìn)程目前的活躍頁(yè)面的集合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頁(yè)全部裝入內(nèi)存之后，不再發(fā)生缺頁(yè)Workingset工作集理論是在1968年由Denning提出來(lái)的。它正是基于局部的假設(shè)。Denning認(rèn)為，程序在運(yùn)行時(shí)對(duì)頁(yè)面的訪問(wèn)是不均勻的，即往往在某段時(shí)間內(nèi)的訪問(wèn)僅局限于較少的若干個(gè)頁(yè)面，如果能夠預(yù)知程序在某段時(shí)間內(nèi)要訪問(wèn)哪些頁(yè)面，并能將它們提前調(diào)入內(nèi)存，將會(huì)大大地降低缺頁(yè)率，從而減少置換工作，提高CPU的利用率。

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

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