操作系統(tǒng)虛擬內(nèi)存 課件

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

PageReplacement（頁置換）ReplacementAlgorithms（頁置換算法）AllocationofFrames（頁框的分配）Thrashing（顛簸）OtherConsiderations（其他考慮）DemandSegmenation（請求段式）AppliedOperatingSystemConceptsModule10:VirtualMemoryBackBackgroundVirtualmemory–separationofuserlogicalmemoryfromphysicalmemory.（虛擬內(nèi)存—物理內(nèi)存和用戶邏輯內(nèi)存的區(qū)分）局部性原理(principleoflocality)

時間局部性，空間局部性O(shè)nlypartoftheprogramneedstobeinmemoryforexecution（只有部分運行的程序需要在內(nèi)存中）.Logicaladdressspacecanthereforebemuchlargerthanphysicaladdressspace（因此，邏輯地址空間能夠比物理地址空間大）.Needtoallowpagestobeswappedinandout（必須允許頁面能夠被換入和換出）.Virtualmemorycanbeimplementedvia（虛擬內(nèi)存能夠通過以下手段來執(zhí)行）:Demandpaging（請求頁式）Demandsegmentation（請求段式）AppliedOperatingSystemConceptsBackgroundVirtualmemory–sep（1）虛擬存儲器的基本概念1.虛擬存儲器的引入1)局部性原理 在一段時間內(nèi)，程序的執(zhí)行僅局限于某個部分；相應(yīng)地，它所訪問的存儲空間也局限于某個區(qū)域內(nèi)。那么程序為什么會出現(xiàn)局部性規(guī)律呢？原因可以歸結(jié)為以下幾點：程序在執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，大多數(shù)仍是順序執(zhí)行的。子程序調(diào)用將會使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不超過5。程序中存在許多循環(huán)結(jié)構(gòu)，循環(huán)體中的指令被多次執(zhí)行。程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對連續(xù)的存儲空間——數(shù)組的訪問，往往局限于很小的范圍內(nèi)。AppliedOperatingSystemConcepts（1）虛擬存儲器的基本概念1.虛擬存儲器的引入Applied局限性表現(xiàn)為：

時間局限性：如果程序中的某條指令一旦執(zhí)行，則不久的將來該指令可能再次被執(zhí)行；如果某個存儲單元被訪問，則不久以后該存儲單元可能再次被訪問。產(chǎn)生時間局限性的典型原因是在程序中存在著大量的循環(huán)操作?？臻g局限性：一旦程序訪問了某個存儲單元，則在不久的將來，其附近的存儲單元也最有可能被訪問。即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)，其典型原因是程序是順序執(zhí)行的。AppliedOperatingSystemConcepts局限性表現(xiàn)為：AppliedOperatingSystBackground虛擬存儲的基本原理根據(jù)局部性原理，一個作業(yè)在運行之前，沒有必要把全部作業(yè)裝入內(nèi)存，而僅將那些當前要運行的那部分頁面或段，先裝入內(nèi)存便可啟動運行，其余部分暫時留在磁盤上

程序在運行時如果它所要訪問的頁（段）已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去；但如果程序所要訪問的頁（段）尚未調(diào)入內(nèi)存（稱為缺頁或缺段），此時程序應(yīng)利用OS所提供的請求調(diào)頁（段）功能，將它們調(diào)入內(nèi)存，以使進程能繼續(xù)執(zhí)行下去。如果內(nèi)存已滿，無法再裝入新的頁（段），則還須再利用頁（段）的置換功能，將內(nèi)存中暫時不用的頁（段）調(diào)出至磁盤上，騰出足夠的內(nèi)存空間后，再將所要訪問的頁（段）調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。這樣，便可使一個大的用戶程序在較小的內(nèi)存空間中運行；也可使內(nèi)存中同時裝入更多的進程并發(fā)執(zhí)行。從用戶角度看，該系統(tǒng)所具有的內(nèi)存容量，將比實際內(nèi)存容量大得多，人們把這樣的存儲器稱為虛擬存儲器。AppliedOperatingSystemConceptsBackground虛擬存儲的基本原理ApplieBackground引入虛擬存儲技術(shù)的好處可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序可在內(nèi)存中容納更多程序并發(fā)執(zhí)行不必影響編程時的程序結(jié)構(gòu)（與覆蓋技術(shù)比較）提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存(realmemory)AppliedOperatingSystemConceptsBackground引入虛擬存儲技術(shù)的好處AppBackground虛擬存儲技術(shù)的特征離散性：指在內(nèi)存分配時采用離散的分配方式，它是虛擬存儲器的最基本的特征。多次性：指一個作業(yè)被分成多次調(diào)入內(nèi)存運行，即在作業(yè)運行時沒有必要將其全部裝入，只須將當前要運行的那部分程序和數(shù)據(jù)裝入內(nèi)存即可。多次性是虛擬存儲器最重要的特征。對換性：指允許在作業(yè)的運行過程中在內(nèi)存和外存的對換區(qū)之間換進、換出。虛擬性：指能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠大于實際內(nèi)存容量。AppliedOperatingSystemConceptsBackground虛擬存儲技術(shù)的特征ApplieBackgroundpage0...PagenVirtualmemoryMemorymapPhysicalmemoryAppliedOperatingSystemConceptsBackgroundpage0.PagenVirtualM虛擬存儲器實現(xiàn)方式1)請求分頁系統(tǒng)：在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能和頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。它允許只裝入若干頁（而非全部程序）的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再通過調(diào)頁功能和頁面置換功能，陸續(xù)把將要運行的頁面調(diào)入內(nèi)存，同時把暫不運行的頁面置換到外存上，置換時以頁面為單位。2)請求分段系統(tǒng)：在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段和分段置換功能所形成的段式虛擬存儲系統(tǒng)。它允許只裝入若干段（而非全部段）的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再通過調(diào)段功能和置換功能將不運行的段調(diào)出，同時調(diào)入將要運行的段，置換以段為單位。3)請求段頁式系統(tǒng)：它是在段頁式系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁和頁面置換功能所形成的段頁式虛擬存儲系統(tǒng)。AppliedOperatingSystemConcepts虛擬存儲器實現(xiàn)方式1)請求分頁系統(tǒng)：AppliedOperDemandPagingBringapageintomemoryonlywhenitisneeded（只有在一個頁需要的時候才把它換入內(nèi)存）.LessI/Oneeded（需要很少的I/O）Lessmemoryneeded（需要很少的內(nèi)存）Fasterresponse（快速響應(yīng)）Moreusers（多用戶）Pageisneeded（需要頁）referencetoit（查閱此頁）invalidreference（無效的訪問）abort（中止）not-in-memory（不在內(nèi)存）bringtomemory（換入內(nèi)存）取頁--將哪部分裝入內(nèi)存置頁--將調(diào)入的頁放在什么地方淘汰--內(nèi)存不足時，將哪些頁換出內(nèi)存。AppliedOperatingSystemConceptsDemandPagingBringapageinto請求分頁存儲管理方式1.請求分頁中的硬件支持它是在純分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲系統(tǒng)，它是目前常用的一種虛擬存儲器的方式。1)請求分頁的頁表機制它是在純分頁的頁表機制上形成的，由于只將應(yīng)用程序的一部分調(diào)入內(nèi)存，還有一部分仍在磁盤上，故需在頁表中再增加若干項，供程序(數(shù)據(jù))在換進、換出時參考。在請求分頁系統(tǒng)中的每個頁表項如圖所示。

頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址AppliedOperatingSystemConcepts請求分頁存儲管理方式1.請求分頁中的硬件支持頁號物理塊其中各字段說明如下：狀態(tài)位（存在位P）：用于指示該頁是否已調(diào)入內(nèi)存，供程序訪問時參考。訪問字段A：用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或最近已有多長時間未被訪問，提供給置換算法選擇換出頁面時參考。修改位M：表示該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不需將該頁寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。外存地址：用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時使用。AppliedOperatingSystemConcepts其中各字段說明如下：AppliedOperatingSy請求分頁中的硬件支持2）缺頁中斷機構(gòu) 在請求分頁系統(tǒng)中，每當所要訪問的頁面不在內(nèi)存時，便要產(chǎn)生一缺頁中斷，請求OS將所缺頁調(diào)入內(nèi)存。與一般中斷的主要區(qū)別在于：缺頁中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號，而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信號。缺頁中斷返回到該指令的開始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。AppliedOperatingSystemConcepts請求分頁中的硬件支持2）缺頁中斷機構(gòu)AppliedOper請求分頁中的硬件支持3)地址變換機構(gòu)

請求分頁系統(tǒng)中的地址變換機構(gòu)，是在分頁系統(tǒng)的地址變換機構(gòu)的基礎(chǔ)上，再為實現(xiàn)虛擬存儲器而增加了某些功能所形成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出一頁的功能等等，下圖給出了請求分頁系統(tǒng)的地址變換過程。AppliedOperatingSystemConcepts請求分頁中的硬件支持AppliedOperatingSy

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

地址變換結(jié)束保留CPU現(xiàn)場

從外存中找到缺頁

頁號>頁表長度？

內(nèi)存滿否？選擇一頁換出

該頁是否被修改？

將該頁寫回外存

將一頁從外存換入內(nèi)存

修改頁表

CPU從外存讀缺頁

啟動I/O硬件

AppliedOperatingSystemConcepts

Valid-InvalidBitWitheachpagetableentryavalid–invalidbitisassociated

(1in-memory,0

not-in-memory)（在每一個頁表的表項有一個有效-無效位相關(guān)聯(lián)，1表示在內(nèi)存，0表示不內(nèi)存）Initiallyvalid–invalidbutissetto0onallentries（在所有的表項，這個位被初始化為0）.Exampleofapagetablesnapshot（一個頁表映象的例子）.

Duringaddresstranslation,ifvalid–invalidbitinpagetableentryis0（在地址轉(zhuǎn)換中，如果頁表表項位的值是0）pagefault（缺頁）.1111000Frame#valid-invalidbitpagetableAppliedOperatingSystemConceptsValid-InvalidBitWitheachpagPageFaultIfthereiseverareferencetoapage,firstreferencewilltraptoOS（如果有對一個頁的訪問，第一個訪問要陷入OS）pagefault（缺頁）OSlooksatanothertabletodecide（OS查看另一個表來決定）:Invalidreference（無效引用）abort（終止）.Justnotinmemory（僅僅不在內(nèi)存）.Getemptyframe（得到空的頁框）.Swappageintoframe（把頁換入頁框）.Resettables,validationbit=1（重新設(shè)置頁表，把位設(shè)為1）.Restartinstruction（重啟指令）:LeastRecentlyUsed（最近未使用）blockmove（塊移動）

autoincrement/decrementlocation（區(qū)域自動增長/縮減）AppliedOperatingSystemConceptsPageFaultIfthereiseverarStepsinhandlingapagefaultLoadMiFreeframeOperatingsystemPagetable1reference6Restartinstruction5Resetpagetable3pageisonbackingstore2trapPhysicalmemory4bringinmissingpageAppliedOperatingSystemConceptsStepsinhandlingapagefaultWhathappensifthereisnofreeframe?1.wecheckaninternaltable(usuallykeptwiththeprocesscontrolblock)forthisprocess,todeterminewhetherthereferencewasavalidorinvalidmemoryaccess.2.ifthereferencewasinvalid,weterminatetheprocess.Ifitwasvalid,butwehavenotyetbroughtinthatpage,wenowageitin.3.wefindafreeframe(bytakingonefromthefree-framelist,forexample)4.wescheduleadiskoperationtoreadthedesiredpageintothenewlyallocatedframe.5whenthediskreadiscomplete,wemodifytheinternaltablekeptwiththeprocessandthepagetabletoindicatethatthepageisnowinmemory6.Werestarttheinstructionthatwasinterruptedbytheillegaladdresstrap.theprocesscannowaccessthepageasthoughithadalwaysbeeninmemoryAppliedOperatingSystemConceptsWhathappensifthereisnofrWhathappensifthereisnofreeframe?Pagereplacement–findsomepageinmemory,butnotreallyinuse,swapitout（頁置換—找到內(nèi)存中并沒有使用的一些頁，換出）.Algorithm（算法）Performance（性能）–wantanalgorithmwhichwillresultinminimumnumberofpagefaults（找出一個導(dǎo)致最小缺頁數(shù)的算法）.Samepagemaybebroughtintomemoryseveraltimes（同一個頁可能會被裝入內(nèi)存多次）.AppliedOperatingSystemConceptsWhathappensifthereisnofr調(diào)入策略、分配策略和清除策略

調(diào)入策略(fetchpolicy)(1)

請求調(diào)頁(demandpaging)(2)

預(yù)調(diào)頁(prepaging)分配策略(assignmentpolicy)清除策略(cleaningpolicy)¨

請求清除(demandcleaning)預(yù)清除(precleaning)

AppliedOperatingSystemConcepts調(diào)入策略、分配策略和清除策略調(diào)入策略(fetchpol頁面調(diào)入策略

為能使進程運行，必須事先將一部分要執(zhí)行的程序和數(shù)據(jù)調(diào)入內(nèi)存。1)調(diào)入頁面的時機預(yù)調(diào)頁策略：是一種主動的缺頁調(diào)入策略，即將那些預(yù)計在不久的將來會被訪問的程序或數(shù)據(jù)所在的頁面，預(yù)先調(diào)入內(nèi)存。由于預(yù)測的準確率不高（50%），所以這種策略主要用于進程的首次調(diào)入。有的系統(tǒng)將預(yù)調(diào)頁策略用于請求調(diào)頁，AppliedOperatingSystemConcepts頁面調(diào)入策略為能使進程運行，必須事先將一部分要執(zhí)行的程序頁面調(diào)入策略請求調(diào)頁策略：是指當進程在運行中發(fā)生缺頁時，就立即提出請求，由系統(tǒng)將缺頁調(diào)入內(nèi)存。目前的虛擬存儲器中，大多采用此策略。但這種策略在調(diào)頁時須花費較大的系統(tǒng)開銷，如需頻繁啟動磁盤I/O。AppliedOperatingSystemConcepts頁面調(diào)入策略AppliedOperatingSystem頁面調(diào)入策略2)從何處調(diào)入頁面在虛擬存儲系統(tǒng)中，外存（硬盤）常常被分成兩部分；文件區(qū)（用于存放文件）和對換區(qū)（用于存放對換頁面）。通常，對換區(qū)（連續(xù)分配）的磁盤I/O速度比文件區(qū)（離散分配）要高。每當進程發(fā)出缺頁請求時，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存呢？在UNIX系統(tǒng)中，對于從未運行過的頁面，都應(yīng)從硬盤文件區(qū)調(diào)入；對于曾經(jīng)運行過而又被換出的頁面，可以從對換區(qū)調(diào)入；對于共享頁面，該頁面可能已由其它進程調(diào)入內(nèi)存，此時就無須再從對換區(qū)調(diào)入。AppliedOperatingSystemConcepts頁面調(diào)入策略2)從何處調(diào)入頁面AppliedOperatiPerformanceofDemandPagingApagefaultcausethefollowingsequencetooccur:1.Traptotheoperatingsystem2.Savetheuserregistersandprocessstate3.Determinethattheinterruptwasapagefault4.Checkthatthepagereferencewaslegalanddeterminethelocationofthepageonthedisk5.Issueareadfromthedisktoafreeframe:a.Waitinaqueueforthisdeviceuntilthereadrequestisserviced.b.Waitforthedevicesseekand/orlatencytimec.Beginthetransferofthepagetoafreeframe6.Whilewaiting,allocatethecputosomeuser(cpuschedulingoperation)7.Interruptfromthedisk(I/Ocompleted)8.Savetheregistersandprocessstatefortheotheruser(ifstep6executed)9.Determinethattheinterruptwasfromthedisk10.Correctthepagetableandothertablestoshowthatthedesiredpageisnowinmemory11.Waitforthecputobeallocatedtothisprocessagain12Restoretheuserregisters,processstate,andnewpagetable,thenresumetheinterruptedinstruction.AppliedOperatingSystemConceptsPerformanceofDemandPagingA缺頁率假定作業(yè)Ji共有m頁，系統(tǒng)分配給它的主存塊為n塊，這里m>n。開始時，主存沒有裝入任何一頁的信息。如果作業(yè)Ji在運行中成功訪問的次數(shù)為S，不成功的訪問次數(shù)為F(產(chǎn)生缺頁中斷的次數(shù))，則作業(yè)執(zhí)行過程中總的訪問次數(shù)為A.A=S（成功訪問的次數(shù)）+F（不成功的訪問次數(shù)）作業(yè)Ji執(zhí)行過程中的缺頁率f=F/A。

AppliedOperatingSystemConcepts缺頁率AppliedOperatiPerformanceofDemandPagingPageFaultRate0p1.0（缺頁率0p1.0）ifp=0nopagefaults（如果p=0，沒有缺頁）ifp=1,everyreferenceisafault（每次訪問都缺頁）EffectiveAccessTime(EAT)（有效存取時間）

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

EAT=(1–p)x1+p(10) =1+9P(inmsec)AppliedOperatingSystemConceptsDemandPagingExampleMemoryacPageReplacementPreventover-allocationofmemorybymodifyingfaultserviceroutinetoincludepagereplacement（通過修改缺頁服務(wù)例程，來包含頁置換，防止分配過多）.Usemodify(dirty)bittoreduceoverheadofpagetransfers–onlymodifiedpagesarewrittentodisk（修改（臟）位來防止頁面轉(zhuǎn)移過多—只有被修改的頁面才寫入磁盤）.Pagereplacementcompletesseparationbetweenlogicalmemoryandphysicalmemory–largevirtualmemorycanbeprovidedonasmallerphysicalmemory（頁置換完善了邏輯內(nèi)存和物理內(nèi)存的劃分—在一個較小的物理內(nèi)存基礎(chǔ)之上可以提供一個大的虛擬內(nèi)存.AppliedOperatingSystemConceptsPageReplacementPreventover-aReplacementAlgorithmsWantlowestfaultrate（需要一個最小的缺頁率）.Evaluatealgorithmbyrunningitonaparticularstringofmemoryreferences(referencestring)andcomputingthenumberofpagefaultsonthatstring（通過運行一個內(nèi)存訪問的特殊序列（訪問序列），計算這個序列的缺頁次數(shù)）.Inallourexamples,thereferencestringis（在所有的例子中，訪問序列是） 1,2,3,4,1,2,5,1,2,3,4,5.AppliedOperatingSystemConceptsReplacementAlgorithmsWanReplacementAlgorithms1.最佳算法(OPT,optimal)2.最近最久未使用算法(LRU,LeastRecentlyUsed)3.先進先出算法(FIFO)Belady現(xiàn)象4.輪轉(zhuǎn)算法(clock)最近未使用算法(NRU,NotRecentlyUsed)5.最不常用算法(LFU,LeastFrequentlyUsed)AppliedOperatingSystemConceptsReplacementAlgorithms1.最先進先出（FIFO）置換算法AppliedOperatingSystemConcepts先進先出（FIFO）置換算法AppliedOperati先進先出（FIFO）置換算法AppliedOperatingSystemConcepts先進先出（FIFO）置換算法AppliedOperatiFirst-In-First-Out(FIFO)AlgorithmReferencestring:1,2,3,4,1,2,5,1,2,3,4,53frames(3pagescanbeinmemoryatatimeperprocess)4frames

FIFOReplacement–Belady’sAnomaly（FIFO算法可能會產(chǎn)生Belady異常）moreframeslesspagefaults（頁就是更多的頁框相反會產(chǎn)生更多的缺頁）1231234125349pagefaults1231235124510pagefaults443AppliedOperatingSystemConceptsFirst-In-First-Out(FIFO)Algo頁面置換算法.最佳（Optimal）置換算法 它是一種理想化的算法，性能最好，但在實際上難于實現(xiàn)。即選擇那些永不使用的，或者是在最長時間內(nèi)不再被訪問的頁面置換出去。但是要確定哪一個頁面是未來最長時間內(nèi)不再被訪問的，目前來說是很難估計的，所以該算法通常用來評價其它算法。AppliedOperatingSystemConcepts頁面置換算法.最佳（Optimal）置換算法Applied頁面置換算法例：假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如下圖所示，進程運行時先將7，0，1三個頁面裝入內(nèi)存。當進程訪問頁面2時，產(chǎn)生缺頁中斷，此時OS根據(jù)最佳置換算法，頁面7將在第18次才被訪問，是三頁中將最久不被訪問的頁面，所以被淘汰。接著訪問頁面0時，發(fā)現(xiàn)已在內(nèi)存中，而不會產(chǎn)生缺頁中斷，以此類推。從圖可以看出，采用最佳置換算法，只發(fā)生了6次頁面置換。AppliedOperatingSystemConcepts頁面置換算法AppliedOperatingSystem最佳（Optimal）置換算法發(fā)生了6次面置換，9次缺頁中斷。AppliedOperatingSystemConcepts最佳（Optimal）置換算法發(fā)生了6次面置換，9次缺頁中斷OptimalAlgorithmReplacepagethatwillnotbeusedforlongestperiodoftime（被置換的頁將是之后最長時間不被使用的頁）.4framesexample 1,2,3,4,1,2,5,1,2,3,4,5

Howdoyouknowthis?（怎樣知道的）Usedformeasuringhowwellyouralgorithmperforms（用來衡量你的算法的效率）.12346pagefaults45AppliedOperatingSystemConceptsOptimalAlgorithmReplacepage最近最久未使用置換算法AppliedOperatingSystemConcepts最近最久未使用置換算法AppliedOperaLeastRecentlyUsed(LRU)AlgorithmReferencestring:1,2,3,4,1,2,5,1,2,3,4,5

Counterimplementation（計數(shù)器的實現(xiàn)）Everypageentryhasacounter;everytimepageisreferencedthroughthisentry,copytheclockintothecounter（每一個頁表項有一個計數(shù)器，每次頁通過這個表項被訪問，把記錄拷貝到計數(shù)器中）.Whenapageneedstobechanged,lookatthecounterstodeterminewhicharetochange（當一個頁需要改變是，查看計數(shù)器來覺得改變哪一個頁0.）12354435AppliedOperatingSystemConceptsLeastRecentlyUsed(LRU)AlgoLRUAlgorithm(Cont.)Stackimplementation–keepastackofpagenumbersinadoublelinkform（棧實現(xiàn)—在一個雙鏈表中保留一個記錄頁數(shù)目的棧）:Pagereferenced（被訪問的頁）:moveittothetop（移到棧頂）requires6pointerstobechanged（需要改變6個指針）Nosearchforreplacement（沒有為置換進行查找）AppliedOperatingSystemConceptsLRUAlgorithm(Cont.)Stackimp

LRU近似算法這種算法，只要在存儲分塊表（或頁表）中設(shè)一個“引用位”，當存儲分塊表中的某一頁被訪問時，該位由硬件自動置1，并由頁面管理軟件周期性把所有引用位置0。這樣，在一個時間周期T內(nèi)，某些被訪問過的頁面其引用位為1，而未被訪問過的頁面其引用位為0。因此，可根據(jù)引用位的狀態(tài)來判別各頁面最近的使用情況。當需要置換一頁面時，選擇其引用位為0的頁，如圖所示的算法。圖是這種近似算法的一個例子。

AppliedOperatingSystemConceptsLRU近似算法這種算法，只要在存儲分塊表（或頁表）中設(shè)一個

LRU近似算法

AppliedOperatingSystemConceptsLRU近似算法AppliedOperating

LRU近似算法舉例AppliedOperatingSystemConceptsLRU近似算法舉例AppliedOperatingLRUApproximationAlgorithmsReferencebit（訪問位）Witheachpageassociateabit,initially-=0（每個頁都與一個位相關(guān)聯(lián)，初始值位0）Whenpageisreferencedbitsetto1（當頁是訪問位是設(shè)位1）.Replacetheonewhichis0(ifoneexists).Wedonotknowtheorder,however（，如果存在的話置換位為0的頁。然而我們并不知道這個置換順序）.Secondchance（二次機會）Needreferencebit.（需要訪問位）Clockreplacement.（時鐘置換）Ifpagetobereplaced(inclockorder)hasreferencebit=1.Then（如果將要（以順時針）交換的訪問位是1，則）:setreferencebit0（把訪問位設(shè)位0）.leavepageinmemory（把頁留在內(nèi)存中）.replacenextpage(inclockorder),subjecttosamerules（以同樣的規(guī)則，替換下一個頁）.AppliedOperatingSystemConceptsLRUApproximationAlgorithmsReCountingAlgorithmsKeepacounterofthenumberofreferencesthathavebeenmadetoeachpage.（用一個計數(shù)器記錄對每一個頁的訪問次數(shù)。）LFUAlgorithm:replacespagewithsmallestcount（以最小的計數(shù)置換一個頁）.MFUAlgorithm:basedontheargumentthatthepagewiththesmallestcountwasprobablyjustbroughtinandhasyettobeused（以下面的觀點為基礎(chǔ)，最小計數(shù)的頁也許剛剛被換入和使用）.AppliedOperatingSystemConceptsCountingAlgorithmsKeepacounAllocationofFramesEachprocessneedsminimumnumberofpages（每個進程所需要的最少的頁的數(shù)目）.Example:IBM370–6pagestohandleSSMOVEinstruction:instructionis6bytes,mightspan2pages.2pagestohandlefrom.2pagestohandleto.Twomajorallocationschemes（兩個主要的分配策略）.fixedallocation（固定分配）priorityallocation（優(yōu)先分配）AppliedOperatingSystemConceptsAllocationofFramesEachproce頁面分配1)最少物理塊數(shù)在為進程分配物理塊時，首先應(yīng)該考慮的問題是：能保證進程能正常運行所需的最少物理塊數(shù)（稱為最小物理塊數(shù)）。若系統(tǒng)為某進程所分配的物理塊數(shù)少于此值時，進程將無法運行，這取決于指令的格式、功能和尋址方式。AppliedOperatingSystemConcepts頁面分配1)最少物理塊數(shù)AppliedOperating頁面分配2)頁面的分配和置換策略在請求分頁系統(tǒng)中，可采取兩種分配策略——固定和可變分配策略。在進行置換時，也可采取兩種策略——全局置換和局部置換。于是可組合成以下三種策略：固定分配局部置換策略：它基于進程的類型（交互型或批處理型等），或根據(jù)程序員、系統(tǒng)管理員的建議，為每個進程分配一固定頁數(shù)的內(nèi)存空間，在整個運行期間都不再改變。如果進程在運行中發(fā)現(xiàn)缺頁，則只能從該進程在內(nèi)存的固定頁面中選出一頁換出，然后再調(diào)入另一頁，保證分配給該進程的內(nèi)存空間不變。AppliedOperatingSystemConcepts頁面分配2)頁面的分配和置換策略AppliedOperat頁面分配可變分配全局置換策略：系統(tǒng)為每個進程分配一定數(shù)目的物理塊，而OS本身也保持一個空閑物理塊隊列。當某進程發(fā)現(xiàn)缺頁時，由系統(tǒng)從空閑物理塊隊列中，取出一物理塊分配給該進程，并將欲調(diào)入的缺頁裝入其中。當空閑物理塊隊列中的物理塊用完時，OS才能從內(nèi)存中選擇一頁調(diào)出，該頁可能是系統(tǒng)中任一進程的頁。AppliedOperatingSystemConcepts頁面分配可變分配全局置換策略：系統(tǒng)為每個進程分配一定數(shù)目的物頁面分配可變分配局部置換：根據(jù)進程的類型或程序員的要求，為每個進程分配一定數(shù)目的內(nèi)存空間，并且在進程運行期間可根據(jù)情況適當增加或減少所分配的物理塊數(shù)；但當某進程發(fā)生缺頁時，只允許從該進程在內(nèi)存的頁面中選出一頁換出，而不影響其它進程的運行。AppliedOperatingSystemConcepts頁面分配可變分配局部置換：根據(jù)進程的類型或程序員的要求，為每頁面分配頁面分配算法 在采用固定分配策略時，可采用以下幾種物理塊分配方法：平均分配算法：將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進程。按比例分配算法：這是根據(jù)進程的大小按比例分配物理塊。AppliedOperatingSystemConcepts頁面分配頁面分配算法AppliedOperatingS頁面分配

頁面分配算法 考慮優(yōu)先權(quán)的分配算法：該方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例分配給各進程；另一部分則根據(jù)各進程的優(yōu)先權(quán)，適當?shù)卦黾悠湎鄳?yīng)份額后，分配給各進程。AppliedOperatingSystemConcepts頁面分配頁面分配算法AppliedOperatingSFixedAllocationEqualallocation（平均分配）–e.g.,if100framesand5processes,giveeach20pages（例：如果有100個頁框，和5個進程，則每個進程分給20個頁）.Proportionalallocation（按比率分配）–Allocateaccordingtothesizeofprocess（根據(jù)每個進程的大小來分配）.AppliedOperatingSystemConceptsFixedAllocationEqualallocatiPriorityAllocationUseaproportionalallocationschemeusingprioritiesratherthansize（根據(jù)優(yōu)先級而不是大小來使用比率分配策略）.IfprocessPigeneratesapagefault,（如果進程Pi產(chǎn)生一個缺頁）selectforreplacementoneofitsframes（選擇替換其中的一個頁框）.selectforreplacementaframefromaprocesswithlowerprioritynumber（從一個較低優(yōu)先級的進程中選擇一個頁面來替換）.AppliedOperatingSystemConceptsPriorityAllocationUseapropoGlobalvs.LocalAllocationGlobalreplacement（全局替換）–processselectsareplacementframefromthesetofallframes;oneprocesscantakeaframefromanother（進程在所有的頁中選擇一個替換頁面；一個進程可以從另一個進程中獲得頁面）.Localreplacement（局部替換）–eachprocessselectsfromonlyitsownsetofallocatedframes（每個進程只從屬于它自己的頁中選擇）.AppliedOperatingSystemConceptsGlobalvs.LocalAllocationGloThrashingIfaprocessdoesnothave“enough”pages,thefaultrateisveryhigh.Thisleadsto（如果一個進程沒有足夠的頁，那么缺頁率將很高，這將導(dǎo)致）:lowCPUutilization（CPU利用率低下）.operatingsystemthinksthatitneedstoincreasethedegreeofmultiprogramming（操作系統(tǒng)認為需要增加多道程序設(shè)計的道數(shù)）.anotherprocessaddedtothesystem（系統(tǒng)中將加入一個新的進程）.Thrashing（顛簸）aprocessisbusyswappingpagesinandout（一個進程的頁面經(jīng)常換入換出）.AppliedOperatingSystemConceptsThrashingIfaprocessdoesnotThrashingDiagramWhydoespagingwork?（為什么分頁工作）Localitymodel（位置模式）Processmigratesfromonelocalitytoanother（進程從一個位置移到另一個位置）.Localitiesmayoverlap（位置可能重疊）.Whydoesthrashingoccur?（為什么顛簸會發(fā)生）

sizeoflocality>totalmemorysizeAppliedOperatingSystemConceptsThrashingDiagramWhydoespagiWorking-SetModelworking-setwindowafixednumberofpagereferences

Example:10,000instructionWSSi(workingsetofProcessPi)=

totalnumberofpagesreferencedinthemostrecent(variesintime)iftoosmallwillnotencompassentirelocality.iftoolargewillencompassseverallocalities.if=willencompassentireprogram.D=WSSitotaldemandframesifD>mThrashingPolicyifD>m,thensuspendoneoftheprocesses.AppliedOperatingSystemConceptsWorking-SetModelworking-sFaultFrequencySchemeEstablish“acceptable”faultrate（設(shè)置可接受的缺頁率）.Ifactualratetoolow,processlosesframe（如果缺頁率太低，回收一些進程的頁框）.Ifactualratetoohigh,processgainsframe（如果缺頁率太高，就分給進程一些頁框）.AppliedOperatingSystemConceptsFaultFrequencySchemeEstOtherConsiderationsPrepaging（預(yù)先調(diào)頁）Pagesizeselection（頁面尺寸選擇）Fragmentation（碎片）tablesize（表大?。㊣/Ooverhead（I/O開銷）Locality（位置）AppliedOperatingSystemConceptsOtherConsiderationsPrepagingOtherConsideration(Cont.)Programstructure（程序結(jié)構(gòu)）ArrayA[1024,1024]ofintegerEachrowisstoredinonepageOneframeProgram1 forj:=1to1024do

fori:=1to1024do

A[i,j]:=0;

1024x1024pagefaultsProgram2 fori:=1to1024do

forj:=1to1024do

A[i,j]:=0;

1024pagefaultsI/Ointerlockandaddressing（I/O連接和地址）AppliedOperatingSystemConceptsOtherConsideration(Cont.)ProDemandSegmentationUsedwheninsufficienthardwaretoimplementdemandpaging（當請頁的硬件不充足時使用）.OS/2allocatesmemoryinsegments,whichitkeepstrackofthroughsegmentdescriptors（操作系統(tǒng)以段來分配內(nèi)存，它通過段描述符來進行跟蹤）Segmentdescriptorcontainsavalidbittoindicatewhetherthesegmentiscurrentlyinmemory（段描述符有一個有效位來說明段是否以在內(nèi)存）.Ifsegmentisinmainmemory,accesscontinues（如果段已在主存中，繼續(xù)存取）,Ifnotinmemory,segmentfault（如果不在內(nèi)存中，缺段中斷）.AppliedOperatingSystemConceptsDemandSegmentationUsedwheni請求分段存儲管理方式請求分段系統(tǒng)在分段系統(tǒng)的基礎(chǔ)上實現(xiàn)的虛擬存儲器，是以分段為單位進行換入、換出的。在程序運行之前只要先調(diào)入若干個分段（不必調(diào)入所有的分段），便可啟動運行。當所訪問的段不在內(nèi)存時可請求OS將所缺的段調(diào)入內(nèi)存。為實現(xiàn)請求分段存儲管理方式，同樣需要一定的硬件支持和相應(yīng)的軟件，有段表機制、缺段中斷機構(gòu)以及地址變換機構(gòu)。1.請求分段中的硬件支持1)段表機制在請求分段式管理中在段表中增加若干項，以供程序在調(diào)進、調(diào)出時參考。請求分段的段表項如下：段段段的存取訪問修改存在增補外存名長基址方式字段A位M位P位起址AppliedOperatingSystemConcepts請求分段存儲管理方式請求分段系統(tǒng)在分段系統(tǒng)的基礎(chǔ)上實現(xiàn)的1.請求分段中的硬件支持在段表項中，除了段名(號)、段長、段在內(nèi)存的起始地址外，還增加了以下幾項：存取方式：用于標識本分段的存取屬性是只執(zhí)行、只讀，還是允許讀／寫。訪問字段A：用于記錄該段被訪問的頻繁程度。修改位M：用于表示該段進入內(nèi)存后，是否已被修改過。存在位P：說明本段是否已調(diào)入內(nèi)存。增補位：用于表示本段在運行過程中，是否進行過動態(tài)增長。外存起址：指示本段在外存中的起始地址，即起始盤塊號。AppliedOperatingSystemConcepts1.請求分段中的硬件支持在段表項中，除了段名(號)、段長1.請求分段中的硬件支持2)缺段中斷機構(gòu)在請求分段系統(tǒng)中，采用的是請求調(diào)段策略。即當進程所要訪問的段未調(diào)入內(nèi)存時，便由缺段中斷機構(gòu)產(chǎn)生一缺段中斷信號，由缺斷中斷處理程序?qū)⑺璧亩握{(diào)入內(nèi)存。缺段中斷的處理過程如下圖：AppliedOperatingSystemConcepts1.請求分段中的硬件支持AppliedOperating

2)缺段中斷機構(gòu)

內(nèi)存中有合適的空閑區(qū)？拼接后形成合適大小的空閑區(qū)淘汰一個或幾個段以形成合適大小的空閑區(qū)虛段不在內(nèi)存中阻塞請求的進程從外存讀入段修改段表和內(nèi)存空閑鏈喚醒請求進程返回空閑區(qū)大小總和能否滿足？NNAppliedOperatingSystemConcepts

2)缺段中斷機構(gòu)內(nèi)存中有合適的空閑區(qū)？拼接后形成合3)地址變換機構(gòu)3)地址變換機構(gòu) 請求分段系統(tǒng)中的地址變換機構(gòu)，是在分段系統(tǒng)地址變換機構(gòu)的基礎(chǔ)上形成的。由于被訪問的段并非全在內(nèi)存，所以在地址變換時，若發(fā)現(xiàn)所要訪問的段不在內(nèi)存時，必須先將所缺的段調(diào)入內(nèi)存，并修改了段表之后，才能再利用段表進行地址變換。為此，在地址變換機制中又增加了某些功能，如缺段中斷的請求及其處理等。AppliedOperatingSystemConcepts3)地址變換機構(gòu)3)地址變換機構(gòu)AppliedOperat啟動要處理指令

計算有效地址

訪問地址v=(s,p,d)S≤段表長嗎？段連接了嗎？段在主存嗎？P≤頁表長嗎？訪問類型合法嗎？頁在主存嗎？

缺頁中斷處理執(zhí)行下一條指令

訪問該地址完成指令形成主存地址出錯處理

越界中斷處理

連接中斷處理缺段中斷處理允許動態(tài)增長嗎？出錯處理NNNNNNNAppliedOperatingSystemConcepts啟動要處理指令計算有效地址訪問地址v=(s,p分段共享與保護

在系統(tǒng)中，用共享段表來記錄了每一個共享段的段號和段長、內(nèi)存始址、存在位等信息，并記錄共享此分段的每個進程的情況。共享段表如下圖所示。AppliedOperatingSystemConcepts分段共享與保護在系統(tǒng)中，用共享段表來記錄了每一個共享段的2.分段共享與保護其中：共享進程計數(shù)器COUNT：記錄有多少個進程需要共享該分段。存取控制字段：說明不同的進程對該分段不同的存取權(quán)限。段號：對于同一個共享段，不同的進程可以使用不同的段號去共享該段。段名段長內(nèi)存起址狀態(tài)外存起址共享進程計數(shù)器COUNT狀態(tài)進程名進程號段號存取控制AppliedOperatingSystemConcepts2.分段共享與保護其中：段名段長存儲共享共享段：被連接或被釋放一次則對引用計數(shù)加1或減1，計數(shù)減至0則可將該共享段刪除；目的在于進程間的信息交流。通過引用計數(shù)(referencecount)來描述存儲區(qū)的共享，引用計數(shù)表示共享它的進程的數(shù)目；具體的存儲共享方式有兩種：AppliedOperatingSystemConcepts存儲共享共享段：被連接或被釋放一次則對引用計數(shù)加1或減1，計存儲共享共享頁面：在物理頁面表中有引用計數(shù)。只能共享不被修改的頁面。這對用戶應(yīng)用是透明的，完全由操作系統(tǒng)控制，目的在于減少系統(tǒng)內(nèi)的物理頁面總數(shù)?？捎糜谘b入同一個程序而創(chuàng)建的幾個進程，或是父進程通過fork()創(chuàng)建子進程；寫時復(fù)制(copyonwrite)：如果一個進程要改寫共享頁面，則先把該頁面復(fù)制一份，讓該進程訪問復(fù)制后的頁面，而讓其他進程訪問復(fù)制前的頁面。AppliedOperatingSystemConcepts存儲共享共享頁面：在物理頁面表中有引用計數(shù)。只能共享不被修改共享段的分配與回收1）共享段的分配對第一個請求使用共享段的進程，為共享段分配物理區(qū)，填寫該進程的段表，填寫共享段表對非第一個請求共享段的進程，填寫該進程的段表，填寫共享段表2）共享段的回收AppliedOperatingSystemConcepts共享段的分配與回收1）共享段的分配AppliedOpera存儲保護存儲保護的目的：保護系統(tǒng)程序區(qū)不被用戶侵犯（有意或無意的）不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)（系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）1.存儲保護由于存儲保護檢查是針對每個存儲訪問操作進行的，必須由相應(yīng)的處理器硬件機構(gòu)支持。AppliedOperatingSystemConcepts存儲保護存儲保護的目的：1.存儲保護由于存儲保護檢查是針對存儲保護類型界限保護（上界寄存器/下界寄存器或基址寄存器/限長寄存器）：所有訪問地址必須在上下界之間；每個進程都有自己獨立的進程空間，如果一個進程在運行時所產(chǎn)生的地址在其地址空間之外，則發(fā)生地址越界。當程序要訪問某個內(nèi)存單元時，由硬件檢查是否允許，如果允許則執(zhí)行，否則產(chǎn)生地址越界中斷，由操作系統(tǒng)進行相應(yīng)處理。AppliedOperatingSystemConcepts存儲保護類型AppliedOperatingSystem訪問方式保護（保護鍵）：通過保護鍵匹配來判斷存儲訪問方式是否合法。對于允許多個進程共享的存儲區(qū)域，每個進程都有自己的訪問權(quán)限。如果一個進程對共享區(qū)域的訪問違反了權(quán)限規(guī)定，則發(fā)生操作越權(quán)(即讀寫保護)。對每個內(nèi)存區(qū)域指定一個鍵值和若干禁止的訪問方式，進程中也指定鍵值，如果訪問時鍵值不匹配而且是被禁止的訪問方式，則出錯；AppliedOperatingSystemConcepts訪問方式保護（保護鍵）：通過保護鍵匹配來判斷存儲訪問方式是否環(huán)保護：處理器狀態(tài)分為多個環(huán)(ring)，分別具有不同的存儲訪問特權(quán)級別(privilege)，通常是級別高的在內(nèi)環(huán)，編號?。ㄈ?環(huán)）級別最高；可訪問同環(huán)或更低級別環(huán)的數(shù)據(jù)；可調(diào)用同環(huán)或更高級別環(huán)的服務(wù)。AppliedOperatingSystemConceptsAppliedOperatingSystemConce對同環(huán)或更高級別環(huán)服務(wù)的調(diào)用AppliedOperatingSystemConcepts對同環(huán)或更高級別環(huán)服務(wù)的調(diào)用AppliedOperatin存儲分配的安全性考慮把一個頁面分配給進程之前，先要清除頁面中的數(shù)據(jù)（如全部填充為0），以免該進程讀取前一進程遺留在頁面中的數(shù)據(jù)；AppliedOperatingSystemConcepts存儲分配的安全性考慮把一個頁面分配給進程之前，先要清除頁面中10.310.410.910.1010.11AppliedOperatingSystemConceptsAppliedOperatingSystemConce本本章小結(jié)章小結(jié)方法功能單一連續(xù)區(qū)分區(qū)式頁式段式段頁式固定分區(qū)可變分區(qū)靜態(tài)動態(tài)適用環(huán)境單道多道多道多道多道虛擬空間一維一維一維二維二維重定位方式靜態(tài)靜態(tài)動態(tài)動態(tài)動態(tài)動態(tài)AppliedOperatingSystemConcepts本本章小結(jié)章小結(jié)方法單一分區(qū)式頁式段式段頁式固定可變靜態(tài)方法功能單一連續(xù)區(qū)分區(qū)式頁式段式段頁式固定分區(qū)可變分區(qū)靜態(tài)動態(tài)分配方式靜態(tài)分配連續(xù)區(qū)靜態(tài)動態(tài)分配連續(xù)區(qū)靜態(tài)或動態(tài)頁為單位非連續(xù)動態(tài)分配段為單位非連續(xù)動態(tài)分配頁為單位非連續(xù)釋放執(zhí)行完成后全部釋放執(zhí)行完分區(qū)成后全釋放部釋放執(zhí)行淘汰與完成執(zhí)行完后釋放后釋放

淘汰與執(zhí)行完成后釋放淘汰與執(zhí)行完成后釋放保護越界保護或沒有越界保護與保護鍵越界保護與控制保護同左同左本章小結(jié)AppliedOperatingSystemConcepts方法單一分區(qū)式頁式固定可變靜態(tài)動態(tài)分配靜態(tài)分配連方法功能單一連續(xù)區(qū)分區(qū)式頁式段式段頁式固定分區(qū)可變分區(qū)靜態(tài)動態(tài)內(nèi)存擴充覆蓋與交換技術(shù)同左同左同左同左共享不能不能較難方便方便硬件支持保護用寄存器保護用同左寄存器加重定位機構(gòu)地址變換機構(gòu)中斷機構(gòu)保護機構(gòu)段式地址變換機構(gòu)，保護與中斷動態(tài)連接機構(gòu)同左外存、內(nèi)存統(tǒng)一管理的虛存本章小結(jié)AppliedOperatingSystemConcepts方法單一分區(qū)式頁式固定可變靜態(tài)動態(tài)內(nèi)存擴充覆蓋與Module10:VirtualMemoryBackground（背景）DemandPaging（請求頁式）PerformanceofDemandPaging（請求頁式的性能）

PageReplacement（頁置換）ReplacementAlgorithms（頁置換算法）AllocationofFrames（頁框的分配）Thrashing（顛簸）OtherConsiderations（其他考慮）DemandSegmenation（請求段式）AppliedOperatingSystemConceptsModule10:VirtualMemoryBackBackgroundVirtualmemory–separationofuserlogicalmemoryfromphysicalmemory.（虛擬內(nèi)存—物理內(nèi)存和用戶邏輯內(nèi)存的區(qū)分）局部性原理(principleoflocality)

時間局部性，空間局部性O(shè)nlypartoftheprogramneedstobeinmemoryforexecution（只有部分運行的程序需要在內(nèi)存中）.Logicaladdressspacecanthereforebemuchlargerthanphysicaladdressspace（因此，邏輯地址空間能夠比物理地址空間大）.Needtoallowpagestobeswappedinandout（必須允許頁面能夠被換入和換出）.Virtualmemorycanbeimplementedvia（虛擬內(nèi)存能夠通過以下手段來執(zhí)行）:Demandpaging（請求頁式）Demandsegmentation（請求段式）AppliedOperatingSystemConceptsBackgroundVirtualmemory–sep（1）虛擬存儲器的基本概念1.虛擬存儲器的引入1)局部性原理 在一段時間內(nèi)，程序的執(zhí)行僅局限于某個部分；相應(yīng)地，它所訪問的存儲空間也局限于某個區(qū)域內(nèi)。那么程序為什么會出現(xiàn)局部性規(guī)律呢？原因可以歸結(jié)為以下幾點：程序在執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，大多數(shù)仍是順序執(zhí)行的。子程序調(diào)用將會使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不超過5。程序中存在許多循環(huán)結(jié)構(gòu)，循環(huán)體中的指令被多次執(zhí)行。程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理