操作系統(tǒng)第十章：虛擬存儲(chǔ)器

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

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

時(shí)間局部性，空間局部性O(shè)nlypartoftheprogramneedstobeinmemoryforexecution

（只有部分運(yùn)行的程序需要在內(nèi)存中）.Logicaladdressspacecanthereforebemuchlargerthanphysicaladdressspace（因此，邏輯地址空間能夠比物理地址空間大）.Needtoallowpagestobeswappedinandout（必須允許頁(yè)面能夠被換入和換出）.Virtualmemorycanbeimplementedvia（虛擬內(nèi)存能夠通過(guò)以下方法來(lái)實(shí)現(xiàn)）:Demandpaging（請(qǐng)求頁(yè)式）Demandsegmentation（請(qǐng)求段式）AppliedOperatingSystemConcepts問(wèn)題的提出為了在內(nèi)存空間運(yùn)行超過(guò)內(nèi)存總?cè)萘康拇笞鳂I(yè)，或者同時(shí)運(yùn)行大量作業(yè)，解決的方法是從邏輯上擴(kuò)充內(nèi)存容量，這就是虛擬存儲(chǔ)技術(shù)所要解決的主要問(wèn)題AppliedOperatingSystemConcepts程序、數(shù)據(jù)、堆棧的大小可以超過(guò)內(nèi)存的大小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需要時(shí)在內(nèi)存和磁盤之間動(dòng)態(tài)交換以CPU時(shí)間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)虛擬存儲(chǔ)器的基本思想AppliedOperatingSystemConcepts虛擬存儲(chǔ)器的基本概念局部性原理

在一段時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域內(nèi)。那么程序?yàn)槭裁磿?huì)出現(xiàn)局部性規(guī)律呢？原因可以歸結(jié)為以下幾點(diǎn)：程序在執(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)。AppliedOperatingSystemConcepts時(shí)間局部性：如果程序中的某條指令一旦執(zhí)行，則不久的將來(lái)該指令可能再次被執(zhí)行；如果某個(gè)存儲(chǔ)單元被訪問(wèn)，則不久以后該存儲(chǔ)單元可能再次被訪問(wèn)。產(chǎn)生時(shí)間局限性的典型原因是在程序中存在著大量的循環(huán)操作。空間局部性：一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元，則在不久的將來(lái)，其附近的存儲(chǔ)單元也最有可能被訪問(wèn)。即程序在一段時(shí)間內(nèi)所訪問(wèn)的地址，可能集中在一定的范圍內(nèi)，其典型原因是程序是順序執(zhí)行的。局部性表現(xiàn)AppliedOperatingSystemConcepts虛擬存儲(chǔ)的基本原理根據(jù)局部性原理，一個(gè)作業(yè)在運(yùn)行之前，沒(méi)有必要把全部作業(yè)裝入內(nèi)存，而僅將那些當(dāng)前要運(yùn)行的那部分頁(yè)面或段，先裝入內(nèi)存便可啟動(dòng)運(yùn)行，其余部分暫時(shí)留在磁盤上AppliedOperatingSystemConcepts程序在運(yùn)行時(shí)如果它所要訪問(wèn)的頁(yè)（段）已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去；如果程序所要訪問(wèn)的頁(yè)（段）尚未調(diào)入內(nèi)存（稱為缺頁(yè)或缺段），此時(shí)應(yīng)利用OS所提供的請(qǐng)求調(diào)頁(yè)（段）功能，將它們調(diào)入內(nèi)存，以使進(jìn)程能繼續(xù)執(zhí)行下去。虛擬存儲(chǔ)的基本原理AppliedOperatingSystemConcepts如果內(nèi)存已滿，無(wú)法再裝入新的頁(yè)（段），則還須再利用頁(yè)（段）的置換功能，將內(nèi)存中暫時(shí)不用的頁(yè)（段）調(diào)出至磁盤上，騰出足夠的內(nèi)存空間后，再將所要訪問(wèn)的頁(yè)（段）調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。這樣，便可使一個(gè)大的用戶程序在較小的內(nèi)存空間中運(yùn)行；也可使內(nèi)存中同時(shí)裝入更多的進(jìn)程并發(fā)執(zhí)行。從用戶角度看，該系統(tǒng)所具有的內(nèi)存容量，將比實(shí)際內(nèi)存容量大得多，人們把這樣的存儲(chǔ)器稱為虛擬存儲(chǔ)器。虛擬存儲(chǔ)的基本原理AppliedOperatingSystemConcepts虛擬存儲(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)存容量。AppliedOperatingSystemConcepts虛擬存儲(chǔ)器實(shí)現(xiàn)方式1)請(qǐng)求分頁(yè)系統(tǒng)：在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入若干頁(yè)（而非全部程序）的用戶程序和數(shù)據(jù)，就可以啟動(dòng)運(yùn)行，以后再通過(guò)調(diào)頁(yè)功能和頁(yè)面置換功能，陸續(xù)把將要運(yùn)行的頁(yè)面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁(yè)面置換到外存上，置換時(shí)以頁(yè)面為單位。2)請(qǐng)求分段系統(tǒng)：在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段和分段置換功能所形成的段式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入若干段（而非全部段）的用戶程序和數(shù)據(jù)，就可以啟動(dòng)運(yùn)行，以后再通過(guò)調(diào)段功能和置換功能將不運(yùn)行的段調(diào)出，同時(shí)調(diào)入將要運(yùn)行的段，置換以段為單位。3)請(qǐng)求段頁(yè)式系統(tǒng)：它是在段頁(yè)式系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能所形成的段頁(yè)式虛擬存儲(chǔ)系統(tǒng)。AppliedOperatingSystemConceptsDemandPagingBringapageintomemoryonlywhenitisneeded（只有在一個(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)存）AppliedOperatingSystemConcepts請(qǐng)求分頁(yè)存儲(chǔ)管理方式它是在純分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)，它是目前常用的一種虛擬存儲(chǔ)器的方式。取頁(yè)--將哪部分裝入內(nèi)存置頁(yè)--將調(diào)入的頁(yè)放在什么地方淘汰--內(nèi)存不足時(shí)，將哪些頁(yè)換出內(nèi)存。AppliedOperatingSystemConcepts請(qǐng)求分頁(yè)中的硬件支持1)請(qǐng)求分頁(yè)的頁(yè)表機(jī)制它是在純分頁(yè)的頁(yè)表機(jī)制上形成的，由于只將程序的一部分調(diào)入內(nèi)存，還有一部分仍在磁盤上，故需在頁(yè)表中再增加若干項(xiàng)，供程序(數(shù)據(jù))在換進(jìn)、換出時(shí)參考。在請(qǐng)求分頁(yè)系統(tǒng)中的每個(gè)頁(yè)表項(xiàng)如圖所示。頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問(wèn)字段A修改位M外存地址AppliedOperatingSystemConcepts狀態(tài)位（存在位P）：用于指示該頁(yè)是否已調(diào)入內(nèi)存，供程序訪問(wèn)時(shí)參考。訪問(wèn)字段A：用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)，或最近已有多長(zhǎng)時(shí)間未被訪問(wèn)，提供給置換算法選擇換出頁(yè)面時(shí)參考。修改位M：表示該頁(yè)在調(diào)入內(nèi)存后是否被修改過(guò)。由于內(nèi)存中的每一頁(yè)都在外存上保留一份副本，因此，若未被修改，在置換該頁(yè)時(shí)就不需將該頁(yè)寫回到外存上，以減少系統(tǒng)的開銷和啟動(dòng)磁盤的次數(shù)；若已被修改，則必須將該頁(yè)重寫到外存上，以保證外存中所保留的始終是最新副本。外存地址：用于指出該頁(yè)在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)使用。請(qǐng)求分頁(yè)中的硬件支持AppliedOperatingSystemConcepts請(qǐng)求分頁(yè)中的硬件支持2）缺頁(yè)中斷機(jī)構(gòu) 在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，便要產(chǎn)生一缺頁(yè)中斷，請(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è)中斷。AppliedOperatingSystemConcepts請(qǐng)求分頁(yè)中的硬件支持3)地址變換機(jī)構(gòu)

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

缺頁(yè)中斷處理是

否 是是否

產(chǎn)生缺頁(yè)中否是斷請(qǐng)求調(diào)頁(yè)

開始（程序請(qǐng)求訪問(wèn)一頁(yè))越界中斷CPU檢索快表頁(yè)表項(xiàng)是否在快表中？訪問(wèn)頁(yè)表頁(yè)是否在內(nèi)存中？修改快表修改訪問(wèn)位和修改位形成物理地址

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

從外存中找到缺頁(yè)

頁(yè)號(hào)>頁(yè)表長(zhǎng)度？

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

該頁(yè)是否被修改？

將該頁(yè)寫回外存

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

修改頁(yè)表

CPU從外存讀缺頁(yè)

啟動(dòng)I/O硬件

AppliedOperatingSystemConceptsStepsinhandlingapagefaultLoadM

0FreeframeOperatingsystemPagetable1reference6Restartinstruction5Resetpagetable3pageisonbackingstore2trapPhysicalmemory4bringinmissingpageAppliedOperatingSystemConceptsStepsinhandlingapagefault1.wecheckaninternaltable(usuallykeptwiththeprocesscontrolblock)forthisprocess,todeterminewhetherthereferencewasavalidorinvalidmemoryaccess.2.ifthereferencewasinvalid,weterminatetheprocess.Ifitwasvalid,butwehavenotyetbroughtinthatpage,wenowpageitin.3.wefindafreeframe(bytakingonefromthefree-framelist,forexample)4.wescheduleadiskoperationtoreadthedesiredpageintothenewlyallocatedframe.5whenthediskreadiscomplete,wemodifytheinternaltablekeptwiththeprocessandthepagetabletoindicatethatthepageisnowinmemory6.Werestarttheinstructionthatwasinterruptedbytheillegaladdresstrap.theprocesscannowaccessthepageasthoughithadalwaysbeeninmemoryAppliedOperatingSystemConceptsWhathappensifthereisnofreeframe?Pagereplacement–findsomepageinmemory,butnotreallyinuse,swapitout（頁(yè)置換—找到內(nèi)存中并沒(méi)有使用的某個(gè)頁(yè)，換出）.Algorithm（算法）Performance（性能）–wantanalgorithmwhichwillresultinminimumnumberofpagefaults（找出一個(gè)導(dǎo)致最小缺頁(yè)數(shù)的算法）.AppliedOperatingSystemConcepts頁(yè)面調(diào)入策略

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

預(yù)調(diào)頁(yè)策略：是一種主動(dòng)的缺頁(yè)調(diào)入策略，即將那些預(yù)計(jì)在不久的將來(lái)會(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è)，AppliedOperatingSystemConcepts頁(yè)面調(diào)入策略請(qǐng)求調(diào)頁(yè)策略：是指當(dāng)進(jìn)程在運(yùn)行中發(fā)生缺頁(yè)時(shí)，就立即提出請(qǐng)求，由系統(tǒng)將缺頁(yè)調(diào)入內(nèi)存。目前的虛擬存儲(chǔ)器中，大多采用此策略。但這種策略在調(diào)頁(yè)時(shí)須花費(fèi)較大的系統(tǒng)開銷，如需頻繁啟動(dòng)磁盤I/O。AppliedOperatingSystemConcepts頁(yè)面調(diào)入策略2)從何處調(diào)入頁(yè)面在虛擬存儲(chǔ)系統(tǒng)中，外存（硬盤）常常被分成兩部分；文件區(qū)（用于存放文件）和對(duì)換區(qū)（用于存放對(duì)換頁(yè)面）。通常，對(duì)換區(qū)（連續(xù)分配）的磁盤I/O速度比文件區(qū)（離散分配）要高。在UNIX系統(tǒng)中，對(duì)于從未運(yùn)行過(guò)的頁(yè)面，都應(yīng)從硬盤文件區(qū)調(diào)入；對(duì)于曾經(jīng)運(yùn)行過(guò)而又被換出的頁(yè)面，可以從對(duì)換區(qū)調(diào)入；對(duì)于共享頁(yè)面，該頁(yè)面可能已由其它進(jìn)程調(diào)入內(nèi)存，此時(shí)就無(wú)須再?gòu)膶?duì)換區(qū)調(diào)入。AppliedOperatingSystemConceptsPerformanceofDemandPagingApagefaultcausethefollowingsequencetooccur:1.Traptotheoperatingsystem2.Savetheuserregistersandprocessstate3.Determinethattheinterruptwasapagefault4.Checkthatthepagereferencewaslegalanddeterminethelocationofthepageonthedisk5.Issueareadfromthedisktoafreeframe:a.Waitinaqueueforthisdeviceuntilthereadrequestisserviced.b.Waitforthedevicesseekand/orlatencytimec.Beginthetransferofthepagetoafreeframe6.Whilewaiting,allocatethecputosomeotheruser(cpuschedulingoperation)

AppliedOperatingSystemConceptsPerformanceofDemandPaging7.Interruptfromthedisk(I/Ocompleted)8.Savetheregistersandprocessstatefortheotheruser(ifstep6executed)9.Determinethattheinterruptwasfromthedisk10.Correctthepagetableandothertablestoshowthatthedesiredpageisnowinmemory11.Waitforthecputobeallocatedtothisprocessagain12.Restoretheuserregisters,processstate,andnewpagetable,thenresumetheinterruptedinstruction.AppliedOperatingSystemConceptsPerformanceofDemandPaging以上步驟并不是在任何情況下都會(huì)發(fā)生的這里主要的動(dòng)作是：處理缺頁(yè)中斷從磁盤讀入所需的頁(yè)重新開始被中斷的進(jìn)程其中最大的一部分時(shí)間為從磁盤讀入所需的頁(yè)AppliedOperatingSystemConcepts假定作業(yè)Ji共有m頁(yè)，系統(tǒng)分配給它的主存塊為n塊，這里m>n。開始時(shí)，主存沒(méi)有裝入任何一頁(yè)的信息。如果作業(yè)Ji在運(yùn)行中成功訪問(wèn)的次數(shù)為S，不成功的訪問(wèn)次數(shù)為F(產(chǎn)生缺頁(yè)中斷的次數(shù))，則作業(yè)執(zhí)行過(guò)程中總的訪問(wèn)次數(shù)為A.A=S（成功訪問(wèn)的次數(shù)）+F（不成功的訪問(wèn)次數(shù)）作業(yè)Ji執(zhí)行過(guò)程中的缺頁(yè)率f=F/A。

缺頁(yè)率AppliedOperatingSystemConceptsPerformanceofDemandPagingPageFaultRate0p1.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])AppliedOperatingSystemConceptsDemandPagingExampleMemoryaccesstime=1microsecond（存取內(nèi)存的時(shí)間）50%ofthetimethepagethatisbeingreplacedhasbeenmodifiedandthereforeneedstobeswappedout（50%的時(shí)間，所置換的頁(yè)被修改，因此需要被換出）.SwapPageTime=10msec（交換頁(yè)的時(shí)間）EAT=(1–p)x1+p(10)=1+9P(inmsec)AppliedOperatingSystemConceptsPageReplacementPreventover-allocationofmemorybymodifyingfaultserviceroutinetoincludepagereplacement（通過(guò)修改缺頁(yè)服務(wù)例程，來(lái)包含頁(yè)置換）.Usemodify(dirty)bittoreduceoverheadofpagetransfers–onlymodifiedpagesarewrittentodisk（使用修改（臟）位來(lái)防止頁(yè)面?zhèn)鬏斶^(guò)多—只有被修改的頁(yè)面才寫入磁盤）.Pagereplacementcompletesseparationbetweenlogicalmemoryandphysicalmemory–largevirtualmemorycanbeprovidedonasmallerphysicalmemory（頁(yè)置換完善了邏輯內(nèi)存和物理內(nèi)存的劃分—在一個(gè)較小的物理內(nèi)存基礎(chǔ)之上可以提供一個(gè)大的虛擬內(nèi)存.AppliedOperatingSystemConceptsReplacementAlgorithmsWantlowestfaultrate（需要一個(gè)最小的缺頁(yè)率）.Evaluatealgorithmbyrunningitonaparticularstringofmemoryreferences(referencestring)andcomputingthenumberofpagefaultsonthatstring（通過(guò)運(yùn)行一個(gè)內(nèi)存訪問(wèn)的特殊序列（訪問(wèn)序列），計(jì)算這個(gè)序列的缺頁(yè)次數(shù)）.AppliedOperatingSystemConceptsReplacementAlgorithms在進(jìn)程運(yùn)行過(guò)程中，如果發(fā)生缺頁(yè)，此時(shí)內(nèi)存中又無(wú)空閑塊時(shí)，為了保證進(jìn)程能正常運(yùn)行就必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送磁盤的對(duì)換區(qū)。但將哪個(gè)頁(yè)面調(diào)出，則須根據(jù)一定的頁(yè)面置換算法來(lái)確定。置換算法的好壞將直接影響系統(tǒng)的性能，不適當(dāng)?shù)乃惴赡軙?huì)導(dǎo)致進(jìn)程發(fā)生“抖動(dòng)”（Thrashing)。即剛被換出的頁(yè)很快又被訪問(wèn)，需重新調(diào)入，導(dǎo)致系統(tǒng)頻繁地更換頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行中把大部分時(shí)間花費(fèi)在完成頁(yè)面置換的工作上，我們稱該進(jìn)程發(fā)生了“抖動(dòng)”（顛簸）。AppliedOperatingSystemConceptsReplacementAlgorithms從理論上講，應(yīng)將那些以后不再被訪問(wèn)的頁(yè)面換出，或把那些在較長(zhǎng)時(shí)間內(nèi)不會(huì)再被訪問(wèn)的頁(yè)面換出。目前,存在多種置換算法,都是試圖更接近理論上的目標(biāo)。AppliedOperatingSystemConceptsReplacementAlgorithms1.最佳算法(OPT,optimal)2.最近最久未使用算法(LRU,LeastRecentlyUsed)3.先進(jìn)先出算法(FIFO)Belady現(xiàn)象4.LRU的近似算法AppliedOperatingSystemConcepts頁(yè)面置換算法.最佳（Optimal）置換算法 它是一種理想化的算法，性能最好，但在實(shí)際上難于實(shí)現(xiàn)。即選擇那些永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面置換出去。但是要確定哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，目前來(lái)說(shuō)是很難估計(jì)的，所以該算法通常用來(lái)評(píng)價(jià)其它算法。AppliedOperatingSystemConcepts頁(yè)面置換算法最佳置換算法舉例例：假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁(yè)面號(hào)引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如下頁(yè)圖所示，進(jìn)程運(yùn)行時(shí)先將7，0，1三個(gè)頁(yè)面裝入內(nèi)存。當(dāng)進(jìn)程訪問(wèn)頁(yè)面2時(shí)，產(chǎn)生缺頁(yè)中斷，此時(shí)OS根據(jù)最佳置換算法，頁(yè)面7將在第18次才被訪問(wèn)，是三頁(yè)中將最久不被訪問(wèn)的頁(yè)面，所以被淘汰。接著訪問(wèn)頁(yè)面0時(shí)，發(fā)現(xiàn)已在內(nèi)存中，而不會(huì)產(chǎn)生缺頁(yè)中斷，以此類推。從圖可以看出，采用最佳置換算法，只發(fā)生了6次頁(yè)面置換。AppliedOperatingSystemConcepts最佳（Optimal）置換算法發(fā)生了6次面置換，9次缺頁(yè)中斷。AppliedOperatingSystemConcepts

先進(jìn)先出（FIFO）置換算法AppliedOperatingSystemConcepts先進(jìn)先出（FIFO）置換算法AppliedOperatingSystemConcepts

最近最久未使用置換算法AppliedOperatingSystemConceptsLeastRecentlyUsed(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è)面。5435AppliedOperatingSystemConceptsLRUAlgorithm(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è)指針AppliedOperatingSystemConcepts

LRU近似算法這種算法，只要在頁(yè)表中設(shè)一個(gè)“引用位”，當(dāng)某一頁(yè)被訪問(wèn)時(shí)，該位由硬件自動(dòng)置1，并由頁(yè)面管理軟件周期性把所有引用位置0。這樣，在一個(gè)時(shí)間周期T內(nèi)，某些被訪問(wèn)過(guò)的頁(yè)面其引用位為1，而未被訪問(wèn)過(guò)的頁(yè)面其引用位為0。因此，可根據(jù)引用位的狀態(tài)來(lái)判別各頁(yè)面最近的使用情況。當(dāng)需要置換一頁(yè)面時(shí)，選擇其引用位為0的頁(yè)AppliedOperatingSystemConcepts

LRU近似算法

AppliedOperatingSystemConceptsLRUApproximationAlgorithmsSecondchance（二次機(jī)會(huì)）其基本算法是FIFONeedreferencebit.（頁(yè)表中每一項(xiàng)設(shè)置訪問(wèn)位）實(shí)現(xiàn)：FIFO的循環(huán)隊(duì)列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算法AppliedOperatingSystemConceptsEnhancedSecondchanceAlgorithm不僅考慮頁(yè)面的使用情況，還考慮置換代價(jià)

選擇淘汰頁(yè)面時(shí)，既要是未被訪問(wèn)的，還要是未被修改的頁(yè)面。實(shí)現(xiàn)：設(shè)置兩位訪問(wèn)位（A），修改位（M）

啟動(dòng)一個(gè)進(jìn)程時(shí)，A、M置0

A被定期清零AppliedOperatingSystemConceptsEnhancedSecondchanceAlgorithm發(fā)生缺頁(yè)中斷時(shí)，操作系統(tǒng)檢查A，M：

第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)OS首先尋找第0類頁(yè)面，將找到的第一個(gè)頁(yè)面淘汰；若沒(méi)找到，則找第1類頁(yè)面，將找到的第一個(gè)頁(yè)面淘汰，并將掃描過(guò)的頁(yè)面的A位置為0；若沒(méi)找到，則指針回到開始位置，將所有的A位置為0。然后重復(fù)第一步。AppliedOperatingSystemConceptsCounting-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è)）.AppliedOperatingSystemConceptsAllocationofFramesEachprocessneedsminimumnumberofpages（每個(gè)進(jìn)程所需要的最少的頁(yè)的數(shù)目）.Twomajorallocationschemes（兩個(gè)主要的分配策略）.AppliedOperatingSystemConcepts頁(yè)面分配1)最少物理塊數(shù)在為進(jìn)程分配物理塊時(shí)，首先應(yīng)該考慮的問(wèn)題是：能保證進(jìn)程正常運(yùn)行所需的最少物理塊數(shù)（稱為最小物理塊數(shù)）。若系統(tǒng)為某進(jìn)程所分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無(wú)法運(yùn)行，這取決于指令的格式、功能和尋址方式。AppliedOperatingSystemConcepts頁(yè)面分配2)頁(yè)面的分配和置換策略在請(qǐng)求分頁(yè)系統(tǒng)中，可采取兩種分配策略——固定和可變分配策略。在進(jìn)行置換時(shí)，也可采取兩種策略——全局置換和局部置換。于是可組合成以下三種策略：固定分配&局部置換策略：它基于進(jìn)程的類型（交互型或批處理型等），或根據(jù)程序員、系統(tǒng)管理員的建議，為每個(gè)進(jìn)程分配一固定頁(yè)數(shù)的內(nèi)存空間，在整個(gè)運(yùn)行期間都不再改變。如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁(yè)，則只能從該進(jìn)程在內(nèi)存的固定頁(yè)面中選出一頁(yè)換出，然后再調(diào)入另一頁(yè)，保證分配給該進(jìn)程的內(nèi)存空間不變。AppliedOperatingSystemConcepts頁(yè)面分配可變分配&全局置換策略：系統(tǒng)為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，而OS本身也保持一個(gè)空閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)時(shí)，由系統(tǒng)從空閑物理塊隊(duì)列中，取出一物理塊分配給該進(jìn)程，并將欲調(diào)入的缺頁(yè)裝入其中。當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，OS才從內(nèi)存中選擇一頁(yè)調(diào)出，該頁(yè)可能是系統(tǒng)中任一進(jìn)程的頁(yè)。AppliedOperatingSystemConcepts頁(yè)面分配可變分配&局部置換：根據(jù)進(jìn)程的類型或程序員的要求，為每個(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)行AppliedOperatingSystemConcepts頁(yè)面分配

頁(yè)面分配算法 在采用固定分配策略時(shí)，可采用以下幾種物理塊分配方法：平均分配算法：將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。按比例分配算法：這是根據(jù)進(jìn)程的大小按比例分配物理塊。AppliedOperatingSystemConcepts頁(yè)面分配

考慮優(yōu)先權(quán)的分配算法：該方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。AppliedOperatingSystemConceptsPriorityAllocationUseaproportionalallocationschemeusingprioritiesratherthansize（根據(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)替換）.AppliedOperatingSystemConceptsGlobalvs.LocalAllocationGlobalreplacement（全局替換）–processselectsareplacementframefromthesetofallframes;oneprocesscantakeaframefromanother（進(jìn)程在所有的頁(yè)中選擇一個(gè)替換頁(yè)面；一個(gè)進(jìn)程可以從另一個(gè)進(jìn)程中獲得頁(yè)面）.Localreplacement（局部替換）–eachprocessselectsfromonlyitsownsetofallocatedframes（每個(gè)進(jìn)程只從屬于它自己的頁(yè)中選擇）.相對(duì)而言，全局替換會(huì)帶來(lái)較高的系統(tǒng)吞吐率AppliedOperatingSystemConceptsThrashingIfaprocessdoesnothave“enough”pages,thefaultrateisveryhigh.Thisleadsto（如果一個(gè)進(jìn)程沒(méi)有足夠的頁(yè)，那么缺頁(yè)率將很高，這將導(dǎo)致）:lowCPUutilization（CPU利用率低下）.operatingsystemthinksthatitneedstoincreasethedegreeofmultiprogramming（操作系統(tǒng)認(rèn)為需要增加多道程序設(shè)計(jì)的道數(shù)）.anotherprocessaddedtothesystem（系統(tǒng)中將加入一個(gè)新的進(jìn)程）.Thrashing（顛簸）

aprocessisbusyswappingpagesinandout（一個(gè)進(jìn)程的頁(yè)面經(jīng)常換入換出）.AppliedOperatingSystemConceptsThrashingDiagramAppliedOperatingSystemConceptsThrashingSolutionLocalitymodel（局部模型）一個(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è)AppliedOperatingSystemConcepts工作集理論工作集理論是在1968年由Denning提出來(lái)的。他認(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的利用率。AppliedOperatingSystemConcepts工作集理論基本思想：根據(jù)程序的局部性原理，一般情況下，進(jìn)程在一段時(shí)間內(nèi)總是集中訪問(wèn)一些頁(yè)面，這些頁(yè)面稱為活躍頁(yè)面，如果分配給一個(gè)進(jìn)程的物理頁(yè)面數(shù)太少了，使該進(jìn)程所需的活躍頁(yè)面不能全部裝入內(nèi)存，則進(jìn)程在運(yùn)行過(guò)程中將頻繁發(fā)生中斷如果能為進(jìn)程提供與活躍頁(yè)面數(shù)相等的物理頁(yè)面數(shù)，則可減少缺頁(yè)中斷次數(shù)AppliedOperatingSystemConcepts工作集窗口（Δ）

：是指對(duì)于給定的訪問(wèn)序列選取的定長(zhǎng)的區(qū)間，落在工作集窗口中的頁(yè)面集合稱為工作集例：Δ=1026157775162341234443434441327

|

|t1||t2

ws(t1)={1,2,5,6,7}ws(t2)={3,4}工作集理論AppliedOperatingSystemConcepts正確選擇工作集窗口（Δ）的大小，對(duì)存儲(chǔ)器的有效利用和系統(tǒng)吞吐量的提高，都將產(chǎn)生重要的影響。在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)確定，并且根據(jù)主存的負(fù)荷和進(jìn)程的缺頁(yè)情況動(dòng)態(tài)地調(diào)整其工作集。工作集理論AppliedOperatingSystemConcepts其具體的作法是：一個(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è)換出去。在主存負(fù)荷不太大時(shí)，虛存管理程序允許進(jìn)程擁有盡可能多的頁(yè)面；負(fù)荷發(fā)生變化時(shí)，如空閑頁(yè)面不多了，虛存管理程序就使用“自動(dòng)調(diào)整工作集”的技術(shù)來(lái)增加主存中可用的自由頁(yè)面。方法是檢查主存中的每個(gè)進(jìn)程，將它當(dāng)前工作集大小與其最小工作集進(jìn)行比較。如果大于最小值，則從它們的工作集中移去一些頁(yè)面作為主存自由頁(yè)面，可為其它進(jìn)程所使用。若主存自由頁(yè)面仍然太少，則不斷進(jìn)行檢查，直到每個(gè)進(jìn)程的工作集都達(dá)到最小值為止。AppliedOperatingSystemConceptsFaultFrequencySchemeEstablish“acceptable”faultrate（設(shè)置可接受的缺頁(yè)率）.Ifactualratetoolow,processlosesframe（如果缺頁(yè)率太低，回收一些進(jìn)程的頁(yè)框）.Ifactualratetoohigh,processgainsframe（如果缺頁(yè)率太高，就分給進(jìn)程一些頁(yè)框）.AppliedOperatingSystemConceptsOtherConsiderationsPagesizeselection（頁(yè)面尺寸選擇）Fragmentation：頁(yè)面大，則內(nèi)碎片大小Pagetablesize：頁(yè)面小，則頁(yè)表占用的空間大。大I/Ooverhead：磁盤I/O時(shí)間中傳輸時(shí)間和數(shù)據(jù)量有關(guān)系，但它占的比例很小，而尋道時(shí)間和旋轉(zhuǎn)延遲時(shí)間占了很大的比例。所以頁(yè)面尺寸比較大的情況有利于減少磁盤I/O時(shí)間。大減少I/O及內(nèi)存的占用：要求頁(yè)面尺寸小小減少缺頁(yè)率：要求頁(yè)面尺寸大大總的趨勢(shì)：頁(yè)面尺寸越來(lái)越大，這是由于CPU速度和內(nèi)存容量的增長(zhǎng)超過(guò)了磁盤速度的加快AppliedOperatingSystemConceptsPrepaging（預(yù)調(diào)頁(yè)）純請(qǐng)求分頁(yè)系統(tǒng)，當(dāng)一個(gè)進(jìn)程開始執(zhí)行時(shí)，需將其要用到的若干頁(yè)調(diào)入內(nèi)存，所以會(huì)連續(xù)發(fā)生多次缺頁(yè)中斷；一個(gè)被換出的進(jìn)程在重啟之前，需從磁盤上將其多個(gè)頁(yè)面調(diào)入內(nèi)存，于是會(huì)連續(xù)發(fā)生多次缺頁(yè)中斷。解決：預(yù)調(diào)頁(yè)。如，一個(gè)被換出的進(jìn)程在重啟之前，一次性地將其所需有頁(yè)面全部調(diào)入內(nèi)存；一個(gè)進(jìn)程處于阻塞狀態(tài)時(shí)，系統(tǒng)記住它的工作集，則當(dāng)它恢復(fù)執(zhí)行時(shí)，系統(tǒng)自動(dòng)地將它的工作集全部調(diào)入內(nèi)存。AppliedOperatingSystemConceptsOtherConsideration(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;

1024pagefaultAppliedOperatingSystemConceptsSolaris2的虛存管理維持一個(gè)空閑物理塊鏈表，最大值和最小值指明表中空閑塊的上限和下限值內(nèi)核以每秒4次的頻率檢查表中的空閑塊數(shù)。如果低于下限值，啟動(dòng)pageout進(jìn)程（相當(dāng)于second-chance算法，又叫two-handed-clock算法）。Pageout：第一遍掃描內(nèi)存中的所有頁(yè)面，并置其訪問(wèn)位為0，稍后進(jìn)行第二遍掃描，檢查內(nèi)存中的所有頁(yè)面，如果某一頁(yè)的訪問(wèn)位仍然為0，則把它加入空閑塊鏈。Pageout如此循環(huán)執(zhí)行，直到空閑塊數(shù)達(dá)到最大值。如果不能達(dá)到最大值，則內(nèi)核從內(nèi)存換出進(jìn)程，把該進(jìn)程的所有物理塊作為空閑塊。AppliedOperatingSystemConceptsWindowsNT的虛存管理采用請(qǐng)求頁(yè)面調(diào)度加上簇的策略在處理缺頁(yè)中斷時(shí),不僅調(diào)入出錯(cuò)頁(yè),而且還調(diào)入其周圍的頁(yè)虛存管理程序維護(hù)一個(gè)空閑物理塊鏈表,它有一個(gè)相關(guān)閾值當(dāng)空閑物理塊數(shù)低于其閾值,則采用自動(dòng)工作集修整,以使該值在閾值以上自動(dòng)工作集修整:計(jì)算分配給每個(gè)進(jìn)程的物理塊數(shù),如果大于其最小工作集,則減少其物理塊數(shù)直到最小工作集.一個(gè)進(jìn)程創(chuàng)建時(shí),會(huì)分配一個(gè)工作集的最大值和最小值如果一個(gè)缺頁(yè)進(jìn)程現(xiàn)有物理塊數(shù)低于其工作集最大值,則虛存管理程序?yàn)槠浞峙湟粋€(gè)空閑物理塊;如果一個(gè)缺頁(yè)進(jìn)程現(xiàn)有物理塊數(shù)已達(dá)到其工作集最大值,則采用局部置換策略AppliedOperatingSystemConcepts請(qǐng)求分段存儲(chǔ)管理方式

請(qǐng)求分段系統(tǒng)在分段系統(tǒng)的基礎(chǔ)上實(shí)現(xiàn)的虛擬存儲(chǔ)器，是以分段為單位進(jìn)行換入、換出的。在程序運(yùn)行之前只要先調(diào)入若干個(gè)分段（不必調(diào)入所有的分段），便可啟動(dòng)運(yùn)行。當(dāng)所訪問(wèn)的段不在內(nèi)存時(shí)可請(qǐng)求OS將所缺的段調(diào)入內(nèi)存。為實(shí)現(xiàn)請(qǐng)求分段存儲(chǔ)管理方式，同樣需要一定的硬件支持和相應(yīng)的軟件，有段表機(jī)制、缺段中斷機(jī)構(gòu)以及地址變換機(jī)構(gòu)。1.請(qǐng)求分段中的硬件支持1)段表機(jī)制在請(qǐng)求分段式管理中在段表中增加若干項(xiàng)，以供程序在調(diào)進(jìn)、調(diào)出時(shí)參考。請(qǐng)求分段的段表項(xiàng)如下：段段段的存取訪問(wèn)修改存在增補(bǔ)外存名長(zhǎng)基址方式字段A位M位P位起址AppliedOperatingSystemConcepts請(qǐng)求分段中的硬件支持在段表項(xiàng)中，除了段名(號(hào))、段長(zhǎng)、段在內(nèi)存的起始地址外，還增加了以下幾項(xiàng)：存取方式：用于標(biāo)識(shí)本分段的存取屬性是只執(zhí)行、只讀，還是允許讀／寫。訪問(wèn)字段A：用于記錄該段被訪問(wèn)的頻繁程度。修改位M：用于表示該段進(jìn)入內(nèi)存后，是否已被修改過(guò)。存在位P：說(shuō)明本段是否已調(diào)入內(nèi)存。增補(bǔ)位：用于表示本段在運(yùn)行過(guò)程中，是否進(jìn)行過(guò)動(dòng)態(tài)增長(zhǎng)。外存起址：指示本段在外存中的起始地址，即起始盤塊號(hào)。AppliedOperatingSystemConcepts請(qǐng)求分段中的硬件支持2)缺段中斷機(jī)構(gòu)在請(qǐng)求分段系統(tǒng)中，采用的是請(qǐng)求調(diào)段策略。即當(dāng)進(jìn)程所要訪問(wèn)的段未調(diào)入內(nèi)存時(shí)，便由缺段中斷機(jī)構(gòu)產(chǎn)生一缺段中斷信號(hào)，由缺斷中斷處理程序?qū)⑺璧亩握{(diào)入內(nèi)存。缺段中斷的處理過(guò)程如下圖：AppliedOperatingSystemConcepts缺段中斷處理

內(nèi)存中有合適的空閑區(qū)？拼接后形成合適大小的空閑區(qū)淘汰一個(gè)或幾個(gè)段以形成合適大小的空閑區(qū)虛段不在內(nèi)存中阻塞請(qǐng)求的進(jìn)程從外存讀入段修改段表和內(nèi)存空閑鏈喚醒請(qǐng)求進(jìn)程返回空閑區(qū)大小總和能否滿足？NNAppliedOperatingSystemConcepts請(qǐng)求分段中的硬件支持3)地址變換機(jī)構(gòu) 請(qǐng)求分段系統(tǒng)中的地址變換機(jī)構(gòu)，是在分段系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上形成的。由于被訪問(wèn)的段并非全在內(nèi)存，所以在地址變換時(shí)，若發(fā)現(xiàn)所要訪問(wèn)的段不在內(nèi)存時(shí)，必須先將所缺的段調(diào)入內(nèi)存，并修改了段表之后，才能再利用段表進(jìn)行地址變換。為此，在地址變換機(jī)制中又增加了某些功能，如缺段中斷的請(qǐng)求及其處理等。AppliedOperatingSystemConcepts存儲(chǔ)共享共享頁(yè)面：在物理頁(yè)面表中有引用計(jì)數(shù)。只能共享不被修改的頁(yè)面。這對(duì)用戶應(yīng)用是透明的，完全由操作系統(tǒng)控制，目的在于減少系統(tǒng)內(nèi)的物理頁(yè)面總數(shù)?？捎糜谘b入同一個(gè)程序而創(chuàng)建的幾個(gè)進(jìn)程，或是父進(jìn)程通過(guò)fork()創(chuàng)建子進(jìn)程；寫時(shí)復(fù)制(copyonwrite)：如果一個(gè)進(jìn)程要改寫共享頁(yè)面，則先把該頁(yè)面復(fù)制一份，讓該進(jìn)程訪問(wèn)復(fù)制后的頁(yè)面，而讓其他進(jìn)程訪問(wèn)復(fù)制前的頁(yè)面。AppliedOperatin