操作系統(tǒng)課件：Chapter-04 Memory Management

MemoryManagementChapter44.1Basicmemorymanagement4.2Swapping4.3Virtualmemory4.4Pagereplacementalgorithms4.5Modelingpagereplacementalgorithms4.6Designissuesforpagingsystems4.7Implementationissues4.8Segmentation1MemoryManagement IdeallyprogrammerswantmemorythatislargefastnonvolatileMemoryhierarchy

smallamountoffast,expensivememory–cachesomemedium-speed,mediumpricemainmemorygigabytesofslow,cheapdiskstorageMemorymanagerhandlesthememoryhierarchy2內(nèi)存管理方案靜態(tài)內(nèi)存管理單道程序獨(dú)占存儲(chǔ)器固定分區(qū)多道程序共享存儲(chǔ)器動(dòng)態(tài)內(nèi)存管理基于交換技術(shù)的內(nèi)存管理基于虛擬存儲(chǔ)器的內(nèi)存管理3存儲(chǔ)管理的功能存儲(chǔ)分配和回收：分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。地址變換：可執(zhí)行文件生成中的鏈接技術(shù)程序加載(裝入)時(shí)的重定位技術(shù)進(jìn)程運(yùn)行時(shí)硬件和軟件的地址變換技術(shù)和機(jī)構(gòu)存儲(chǔ)共享和保護(hù)：代碼和數(shù)據(jù)共享地址空間訪問權(quán)限（讀、寫、執(zhí)行）存儲(chǔ)器擴(kuò)充：存儲(chǔ)器的邏輯組織和物理組織；由應(yīng)用程序控制：覆蓋；由OS控制：交換（整個(gè)進(jìn)程空間），虛擬存儲(chǔ)的請(qǐng)求調(diào)入和預(yù)調(diào)入（部分進(jìn)程空間）4邏輯地址、物理地址和地址映射5地址映射6BasicMemoryManagement

MonoprogrammingwithoutSwappingorPagingThreesimplewaysoforganizingmemory-anoperatingsystemwithoneuserprocess7MultiprogrammingwithFixedPartitionsFixedmemorypartitionsseparateinputqueuesforeachpartitionsingleinputqueue8ModelingMultiprogrammingCPUutilizationasafunctionofnumberofprocessesinmemoryDegreeofmultiprogramming9AnalysisofMultiprogrammingSystemPerformanceArrivalandworkrequirementsof4jobsCPUutilizationfor1–4jobswith80%I/OwaitSequenceofeventsasjobsarriveandfinishnotenumbersshowamoutofCPUtimejobsgetineachinterval10RelocationandProtectionCannotbesurewhereprogramwillbeloadedinmemoryaddresslocationsofvariables,coderoutinescannotbeabsolutemustkeepaprogramoutofotherprocesses’partitionsUsebaseandlimitvaluesaddresslocationsaddedtobasevaluetomaptophysicaladdraddresslocationslargerthanlimitvalueisanerror11動(dòng)態(tài)內(nèi)存管理設(shè)計(jì)思想為進(jìn)程動(dòng)態(tài)分配內(nèi)存，將進(jìn)程動(dòng)態(tài)調(diào)入內(nèi)存分類基于交換技術(shù)將進(jìn)程完整的調(diào)入內(nèi)存，運(yùn)行一段時(shí)間后，調(diào)出內(nèi)存?；谔摂M存儲(chǔ)器進(jìn)程只需要比程序空間小的內(nèi)存就可以正常運(yùn)行。12Swapping(1)Memoryallocationchangesas

processescomeintomemoryleavememoryShadedregionsareunusedmemory13交換技術(shù)的動(dòng)態(tài)內(nèi)存管理問題：如果進(jìn)程內(nèi)存使用量增長(zhǎng)怎么辦？AllocatingspaceforgrowingdatasegmentAllocatingspaceforgrowingstack&datasegment14MemoryManagementwithBitMapsPartofmemorywith5processes,3holestickmarksshowallocationunitsshadedregionsarefreeCorrespondingbitmapSameinformationasalist15基于位圖的內(nèi)存管理內(nèi)存單位的劃分內(nèi)存分配與釋放的管理基本算法設(shè)計(jì)實(shí)踐：如何找出連續(xù)的‘0’位？16基于鏈表的內(nèi)存管理如果管理內(nèi)存鏈表？幾個(gè)鏈表合適？單向鏈表還是雙向鏈表？如何分配并釋放內(nèi)存？分配、釋放內(nèi)存時(shí)的鏈表管理首次適配算法下次適配算法最佳適配算法&最差適配算法快速適配算法——多鏈表管理17MemoryManagementwithLinkedListsFourneighborcombinationsfortheterminatingprocessX18交換技術(shù)的動(dòng)態(tài)內(nèi)存管理內(nèi)存空洞內(nèi)存緊縮(compaction)：將各個(gè)占用分區(qū)向內(nèi)存一端移動(dòng)。使各個(gè)空閑分區(qū)聚集在另一端，然后將各個(gè)空閑分區(qū)合并成為一個(gè)空閑分區(qū)。對(duì)占用分區(qū)進(jìn)行內(nèi)存數(shù)據(jù)搬移占用CPU時(shí)間如果對(duì)占用分區(qū)中的程序進(jìn)行"浮動(dòng)"，則其重定位需要硬件支持。緊縮時(shí)機(jī)：每個(gè)分區(qū)釋放后，或內(nèi)存分配找不到滿足條件的空閑分區(qū)時(shí)19靜態(tài)內(nèi)存分配方法與交換技術(shù)的比較管理方案單道獨(dú)占固定分區(qū)交換技術(shù)進(jìn)程大小小于內(nèi)存總量小于分區(qū)容量小于可用內(nèi)存量?jī)?nèi)存分配方式靜態(tài)靜態(tài)動(dòng)態(tài)多道程序不支持支持支持內(nèi)存空間分布連續(xù)連續(xù)連續(xù)內(nèi)存動(dòng)態(tài)變化不支持不支持不支持20虛擬存儲(chǔ)的動(dòng)態(tài)內(nèi)存管理設(shè)計(jì)目的保持容量大于內(nèi)存的程序能夠正常運(yùn)行。重要概念邏輯地址（虛）與物理地址（實(shí)）頁(yè)與頁(yè)框、段的概念重要處理步驟邏輯地址向物理地址的映射缺頁(yè)故障的處理：虛擬存儲(chǔ)的核心主要的實(shí)現(xiàn)方法分頁(yè)技術(shù)：一維虛擬存儲(chǔ)管理分段技術(shù)：二維虛擬存儲(chǔ)管理21從覆蓋塊到虛擬存儲(chǔ)覆蓋塊方法由程序員將程序手動(dòng)分割成多個(gè)片段（覆蓋塊）由系統(tǒng)根據(jù)程序運(yùn)行過程自動(dòng)依次調(diào)入下一個(gè)覆蓋塊優(yōu)點(diǎn)與缺點(diǎn)優(yōu)點(diǎn)：允許運(yùn)行比內(nèi)存容量大的程序缺點(diǎn)：覆蓋塊必須手動(dòng)設(shè)置，程序員負(fù)擔(dān)繁重虛擬存儲(chǔ)方法程序員基于邏輯地址空間編寫程序OS實(shí)現(xiàn)虛擬存儲(chǔ)的所有過程主要優(yōu)點(diǎn)降低編程負(fù)擔(dān)，提升OS的作用，促進(jìn)應(yīng)用的普及22邏輯空間與物理空間堆棧段數(shù)據(jù)段程序段進(jìn)程邏輯空間內(nèi)存物理空間進(jìn)程A進(jìn)程B進(jìn)程COS管理：分頁(yè)或者分段硬件支持：MMU映射23分頁(yè)技術(shù)設(shè)計(jì)思想 用固定大小的頁(yè)來描述邏輯地址空間，用相同大小的頁(yè)框來描述物理內(nèi)存空間，由操作系統(tǒng)實(shí)現(xiàn)從邏輯頁(yè)到物理頁(yè)框的映射，同時(shí)負(fù)責(zé)對(duì)所有頁(yè)的管理和進(jìn)程運(yùn)行的控制數(shù)據(jù)結(jié)構(gòu)頁(yè)與頁(yè)框的結(jié)構(gòu)：關(guān)鍵在于定義頁(yè)面大小頁(yè)表與頁(yè)表項(xiàng)：頁(yè)表是核心數(shù)據(jù)結(jié)構(gòu)，記錄映射關(guān)系與頁(yè)面屬性關(guān)鍵問題：如何實(shí)現(xiàn)邏輯地址（頁(yè)）向物理地址的映射（頁(yè)框）缺頁(yè)故障的產(chǎn)生與解決24VirtualMemory

Paging(1)ThepositionandfunctionoftheMMU25Paging(2)Therelationbetween

virtualaddresses

andphysical

memoryaddres-

sesgivenby

pagetable26頁(yè)表的設(shè)計(jì)與管理頁(yè)表設(shè)計(jì)所需要考慮的問題頁(yè)表大小頁(yè)表太大則浪費(fèi)空間，尋頁(yè)速度過慢頁(yè)表太小則頁(yè)內(nèi)尋址過慢頁(yè)面大小（幾KB到幾十KB）頁(yè)面太大則頁(yè)內(nèi)尋址過慢，同時(shí)會(huì)產(chǎn)生內(nèi)零頭問題頁(yè)面太小則導(dǎo)致頁(yè)表過大，影響地址映射效率頁(yè)表的數(shù)據(jù)結(jié)構(gòu)定義單級(jí)頁(yè)表還是多級(jí)頁(yè)表？如何實(shí)現(xiàn)快速的地址映射——硬件支持和TLB機(jī)制如何良好解決缺頁(yè)故障——頁(yè)面替換算法如何保證數(shù)據(jù)的一致性——頁(yè)表項(xiàng)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)27頁(yè)表的設(shè)計(jì)原理與實(shí)現(xiàn)機(jī)制完全依賴硬件或者完全利用內(nèi)存空間浪費(fèi)大量寶貴硬件資源不具有廣泛適用性多級(jí)頁(yè)表一般選擇兩級(jí)頁(yè)表即可數(shù)據(jù)結(jié)構(gòu)復(fù)雜程度與實(shí)現(xiàn)效率的協(xié)調(diào)TLB機(jī)制：頁(yè)表的Cache結(jié)構(gòu)（關(guān)聯(lián)存儲(chǔ)器）硬件實(shí)現(xiàn)與軟件實(shí)現(xiàn)——較為有效的一種方法逆向頁(yè)表：將Frame映射為Page實(shí)現(xiàn)從物理地址向邏輯地址的映射缺頁(yè)故障的解決將非常低校28PageTables(1)InternaloperationofMMUwith164KBpages29PageTables(2)32bitaddresswith2pagetablefieldsTwo-levelpagetablesSecond-levelpagetablesTop-levelpagetable30PageTables(3)Typicalpagetableentry頁(yè)框號(hào)與“存在”位：標(biāo)識(shí)地址映射狀態(tài)和信息的數(shù)據(jù)域，非常重要“保護(hù)”位：規(guī)定當(dāng)前頁(yè)的讀取權(quán)限，保證數(shù)據(jù)安全“修改位”和“引用”位：記錄頁(yè)面內(nèi)容的狀態(tài)，用于頁(yè)面替換時(shí)的選擇禁止緩存位：為硬件設(shè)備寄存器的訪問提供支持問：對(duì)一個(gè)進(jìn)程而言，頁(yè)表會(huì)發(fā)生變化嗎？指令空間（Text）：一般來說會(huì)保持靜態(tài)數(shù)據(jù)空間（Data、Stack）：可能會(huì)發(fā)生變化31TLBs–TranslationLookasideBuffers現(xiàn)象：只有很少的頁(yè)表表項(xiàng)會(huì)被反復(fù)讀取，其它的幾乎很少使用在MMU中設(shè)置硬件設(shè)備：將虛擬地址直接映射到物理地址，而不必通過頁(yè)表，該設(shè)備為轉(zhuǎn)換檢測(cè)緩沖區(qū)，或稱之為關(guān)聯(lián)存儲(chǔ)器32TLBs–TranslationLookasideBuffersATLBtospeeduppaging關(guān)聯(lián)存儲(chǔ)器(TLB,TranslationLookasideBuffer)按內(nèi)容查找(associativemapping)，即邏輯頁(yè)號(hào)－>物理頁(yè)號(hào)33關(guān)聯(lián)存儲(chǔ)器TLB34關(guān)聯(lián)存儲(chǔ)器TLB35逆向頁(yè)表(invertedpagetable)逆向頁(yè)表不是依據(jù)進(jìn)程的邏輯頁(yè)號(hào)來組織，而是依據(jù)該進(jìn)程在內(nèi)存中的物理頁(yè)面號(hào)來組織（即：按物理頁(yè)面號(hào)排列）。每個(gè)進(jìn)程一個(gè)逆向頁(yè)表，通過哈希表(hashtable)查找可由邏輯頁(yè)號(hào)得到物理頁(yè)面號(hào)。虛擬地址中的邏輯頁(yè)號(hào)通過哈希表指向逆向頁(yè)表中的表項(xiàng)鏈頭（因?yàn)楣１砜赡苤赶蚨鄠€(gè)表項(xiàng)），得到物理頁(yè)面號(hào)。逆向頁(yè)表的大小只與物理內(nèi)存的大小相對(duì)關(guān)，與邏輯空間大小和進(jìn)程數(shù)無關(guān)。如PowerPC,IBMAS/400036InvertedPageTablesComparisonofatraditionalpagetablewithaninvertedpagetable37InvertedPageTablesinvertedpagetable(逆向頁(yè)表)38頁(yè)面置換算法功能：需要調(diào)入頁(yè)面時(shí)，選擇內(nèi)存中哪個(gè)物理頁(yè)面被置換。目標(biāo)：把未來不再使用的或短期內(nèi)較少使用的頁(yè)面調(diào)出，通常只能在局部性原理指導(dǎo)下依據(jù)過去的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行預(yù)測(cè)；頁(yè)面鎖定(framelocking)：用于描述必須常駐內(nèi)存的操作系統(tǒng)的關(guān)鍵部分或時(shí)間關(guān)鍵(time-critical)的應(yīng)用進(jìn)程。實(shí)現(xiàn)方法為在頁(yè)表中加上鎖定標(biāo)志位(lockbit)。39缺頁(yè)故障的解決方案缺頁(yè)故障的產(chǎn)生邏輯地址空間遠(yuǎn)大于物理地址空間造成缺頁(yè)故障分時(shí)系統(tǒng)中多進(jìn)程共享內(nèi)存，可用內(nèi)存小造成缺頁(yè)故障解決思想發(fā)現(xiàn)問題：通過頁(yè)表項(xiàng)中的“存在”位來發(fā)現(xiàn)缺頁(yè)故障分析問題：依據(jù)某種規(guī)則選擇一個(gè)頁(yè)框進(jìn)行替換問：如何選擇一個(gè)被替換的頁(yè)？替換過程中需要何種操作：頁(yè)寫回，頁(yè)替換40PageReplacementAlgorithmsPagefaultforceschoice

whichpagemustberemovedmakeroomforincomingpageModifiedpagemustfirstbesavedunmodifiedjustoverwrittenBetternottochooseanoftenusedpagewillprobablyneedtobebroughtbackinsoon41OptimalPageReplacementAlgorithmReplacepageneededatthefarthestpointinfutureOptimalbutunrealizableEstimateby…loggingpageuseonpreviousrunsofprocessalthoughthisisimpractical先決條件：必須知道一個(gè)頁(yè)面的下一次訪問時(shí)間選擇“未來不再使用的”或“在離當(dāng)前最遠(yuǎn)位置上出現(xiàn)的”頁(yè)面被置換。這是一種理想情況，是實(shí)際執(zhí)行中無法預(yù)知的，因而不能實(shí)現(xiàn)?？捎米餍阅茉u(píng)價(jià)的依據(jù)。42NotRecentlyUsedPageReplacementAlgorithmEachpagehasReferencebit,Modifiedbitbitsaresetwhenpageisreferenced,modifiedPagesareclassifiednotreferenced,notmodifiednotreferenced,modifiedreferenced,notmodifiedreferenced,modifiedNRUremovespageatrandomfromlowestnumberednonemptyclass43NotRecentlyUsedPageReplacementAlgorithm實(shí)現(xiàn)過程先決條件：頁(yè)表項(xiàng)中存在R位和M位,依據(jù)RM位內(nèi)容，共分為四類每一個(gè)時(shí)鐘周期，均將R位清零發(fā)生頁(yè)面故障時(shí)，對(duì)現(xiàn)有頁(yè)面進(jìn)行分類，選擇替換頁(yè)優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：簡(jiǎn)單、易實(shí)現(xiàn)，一般情況下能夠保證性能缺點(diǎn)：判據(jù)簡(jiǎn)單，全局性不強(qiáng)問:四類頁(yè)面的替換優(yōu)先級(jí)？存在多個(gè)同類頁(yè)面怎么辦？“最近”是什么含義？R位是如何變化的？44FIFOPageReplacementAlgorithmMaintainalinkedlistofallpages

inordertheycameintomemoryPageatbeginningoflistreplacedDisadvantagepageinmemorythelongestmaybeoftenused基于前提假設(shè)，存在時(shí)間越長(zhǎng)的，保留價(jià)值越低性能較差。較早調(diào)入的頁(yè)可能經(jīng)常被訪問，這些頁(yè)在FIFO算法下被反復(fù)調(diào)入和調(diào)出。并且有Belady現(xiàn)象。45SecondChancePageReplacementAlgorithmOperationofasecondchancepagessortedinFIFOorderPagelistiffaultoccursattime20,AhasRbitset

(numbersabovepagesareloadingtimes)46TheClockPageReplacementAlgorithm47LeastRecentlyUsed(LRU)AssumepagesusedrecentlywillusedagainsoonthrowoutpagethathasbeenunusedforlongesttimeMustkeepalinkedlistofpagesmostrecentlyusedatfront,leastatrearupdatethislisteverymemoryreference!!Alternativelykeepcounterineachpagetableentrychoosepagewithlowestvaluecounterperiodicallyzerothecounter48最久未使用算法（LRU）設(shè)計(jì)思想 基于內(nèi)存訪問的局部性原理，通過記錄所有頁(yè)面的被訪問時(shí)間，替換未被訪問時(shí)間最長(zhǎng)的頁(yè)面實(shí)現(xiàn)過程為每一個(gè)頁(yè)面分配一個(gè)計(jì)數(shù)器，訪問一次既被加1發(fā)生頁(yè)面故障時(shí)，替換計(jì)數(shù)器值最小的頁(yè)面實(shí)現(xiàn)機(jī)制：軟件方法很慢，硬件方法很貴優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：保證公平和穩(wěn)定缺點(diǎn)：難以基于軟件實(shí)現(xiàn)49SimulatingLRUinSoftware(1)LRUusingamatrix–pagesreferencedinorder0,1,2,3,2,1,0,3,2,350SimulatingLRUinSoftware(2)TheagingalgorithmsimulatesLRUinsoftwareNote6pagesfor5clockticks,(a)–(e)51工作集策略問題是分給每個(gè)進(jìn)程多少物理頁(yè)面，以及如何動(dòng)態(tài)調(diào)整各進(jìn)程的物理頁(yè)面數(shù)。常駐集指虛擬頁(yè)式管理中給進(jìn)程分配的物理頁(yè)面數(shù)目工作集是一個(gè)進(jìn)程執(zhí)行過程中所訪問頁(yè)面的集合，可用一個(gè)二元函數(shù)W(t,)表示t是執(zhí)行時(shí)刻；是一個(gè)虛擬時(shí)間段，稱為窗口大小(windowsize)，它采用"虛擬時(shí)間"單位(即阻塞時(shí)不計(jì)時(shí))，大致可以用執(zhí)行的指令數(shù)目，或處理器執(zhí)行時(shí)間來計(jì)算；工作集是在[t-,t]時(shí)間段內(nèi)所訪問的頁(yè)面的集合；|W(t,)|指工作集大小即頁(yè)面數(shù)目；52工作集策略常駐集與缺頁(yè)率的關(guān)系：每個(gè)進(jìn)程的常駐集越小，則同時(shí)駐留內(nèi)存的進(jìn)程就越多，可以提高并行度和處理器利用率；另一方面，進(jìn)程的缺頁(yè)率上升，使調(diào)頁(yè)的開銷增大。進(jìn)程的常駐集達(dá)到某個(gè)數(shù)目之后，再給它分配更多頁(yè)面，缺頁(yè)率不再明顯下降。該數(shù)目是"缺頁(yè)率－常駐集大小"曲線上的拐點(diǎn)(curve)。置換范圍(replacementscope)：被置換的頁(yè)面局限在本進(jìn)程（局部），或允許在其他進(jìn)程（全局）。53工作集策略引入工作集的目的是依據(jù)進(jìn)程在過去的一段時(shí)間內(nèi)訪問的頁(yè)面來調(diào)整常駐集大小。這里要討論的內(nèi)容是常駐集大小的動(dòng)態(tài)調(diào)整策略。工作集大小的變化：進(jìn)程開始執(zhí)行后，隨著訪問新頁(yè)面逐步建立較穩(wěn)定的工作集。當(dāng)內(nèi)存訪問的局部性區(qū)域的位置大致穩(wěn)定時(shí)，工作集大小也大致穩(wěn)定；局部性區(qū)域的位置改變時(shí)，工作集快速擴(kuò)張和收縮過渡到下一個(gè)穩(wěn)定值。54工作集策略工作集為一個(gè)時(shí)間間隔內(nèi)一個(gè)進(jìn)程所訪問的所有頁(yè)面組成的集合，隨單調(diào)遞增：W(t,)W(t,+a)，其中a>0工作集的作用：工作集穩(wěn)定，則系統(tǒng)顛簸程度低利用工作集進(jìn)行常駐集調(diào)整的策略：記錄一個(gè)進(jìn)程的工作集變化；定期從常駐集中刪除不在工作集中的頁(yè)面；總是讓常駐集包含工作集；困難：工作集的過去變化未必能夠預(yù)示工作集的將來大小或組成頁(yè)面的變化；記錄工作集變化要求開銷太大；對(duì)工作集窗口大小的取值難以優(yōu)化，而且通常該值是不斷變化的；55TheWorkingSetPageReplacementAlgorithm(1)Theworkingsetisthesetofpagesusedbythekmostrecentmemoryreferencesw(k,t)isthesizeoftheworkingsetattime,t56TheWorkingSetPageReplacementAlgorithm(2)Theworkingsetalgorithm57TheWSClockPageReplacementAlgorithmOperationoftheWSClockalgorithm(a)and(b)giveanexampleofwhathappenswhenR=1.(c)and(d)giveanexampleofR=0.58ReviewofPageReplacementAlgorithms59FIFO：Belady現(xiàn)象Belady現(xiàn)象：采用FIFO算法時(shí)，如果對(duì)一個(gè)進(jìn)程未分配它所要求的全部頁(yè)面，有時(shí)就會(huì)出現(xiàn)分配的頁(yè)面數(shù)增多，缺頁(yè)率反而提高的異常現(xiàn)象。Belady現(xiàn)象的描述：一個(gè)進(jìn)程P要訪問M個(gè)頁(yè)，OS分配N個(gè)內(nèi)存頁(yè)面給進(jìn)程P；對(duì)一個(gè)訪問序列S，發(fā)生缺頁(yè)次數(shù)為PE（S,N）。當(dāng)N增大時(shí)，PE(S,N)時(shí)而增大，時(shí)而減小。Belady現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動(dòng)態(tài)特征是矛盾的，即被置換的頁(yè)面并不是進(jìn)程不會(huì)訪問的。60FIFO：Belady現(xiàn)象的例子進(jìn)程P有5頁(yè)，程序訪問頁(yè)的順序?yàn)椋?,2,3,4,1,2,5,1,2,3,4,5；如果在內(nèi)存中分配3個(gè)頁(yè)面，則缺頁(yè)情況如下：12次訪問中有缺頁(yè)9次；61FIFO：Belady現(xiàn)象的例子如果在內(nèi)存中分配4個(gè)頁(yè)面，則缺頁(yè)情況如下：12次訪問中有缺頁(yè)10次；62ModelingPageReplacementAlgorithms

Belady'sAnomalyFIFOwith3pageframesFIFOwith4pageframesP'sshowwhichpagereferencesshowpagefaults63棧式算法訪問字符串：每個(gè)進(jìn)程的內(nèi)存訪問都可以用一個(gè)有序的頁(yè)號(hào)列表來表示，該列表即為referencestring刻畫分頁(yè)系統(tǒng)的三部分：執(zhí)行進(jìn)程的訪問字符串，頁(yè)面置換算法，內(nèi)存中可用的頁(yè)幀數(shù)（m）。距離字符串：頁(yè)面訪問用與訪問頁(yè)面所在的棧頂?shù)木嚯x標(biāo)識(shí)64StackAlgorithmsStateofmemoryarray,M,aftereachiteminreferencestringisprocessedMethod:1.每次訪問一個(gè)頁(yè)面時(shí)，將其移到頂部；2.如要訪問的頁(yè)面已在M中，所有它上面的頁(yè)面都向下移一個(gè)位置；3.在被訪問的頁(yè)面下面的頁(yè)面不移動(dòng)。65TheDistanceStringProbabilitydensityfunctionsfortwohypotheticaldistancestrings66TheDistanceStringComputationofpagefaultratefromdistancestringtheCvectortheFvector67DesignIssuesforPagingSystems

LocalversusGlobalAllocationPolicies(1)OriginalconfigurationLocalpagereplacementGlobalpagereplacement68LocalversusGlobalAllocationPolicies(2)使用全局算法為每個(gè)進(jìn)程分配多少頁(yè)幀監(jiān)視由老化算法指出的工作集大小定期確定進(jìn)程運(yùn)行的數(shù)目并為它們分配等額的頁(yè)幀改進(jìn)：按照進(jìn)程大小的比例為它們分配頁(yè)幀使用PFF(PageFaultFrequency)算法管理頁(yè)幀分配69LoadControlDespitegooddesigns,systemmaystillthrashWhenPFFalgorithmindicatessomeprocessesneedmorememorybutnoprocessesneedlessSolution:

Reducenumberofprocessescompetingformemoryswaponeormoretodisk,divideuppagestheyheldreconsiderdegreeofmultiprogramming70缺頁(yè)率(pagefaultrate)缺頁(yè)率的影響因素頁(yè)面大小：頁(yè)面很?。?gt;每個(gè)進(jìn)程的內(nèi)存頁(yè)較多，通過調(diào)頁(yè)很快適應(yīng)局部性原理的要求，缺頁(yè)率低；頁(yè)面很大－>進(jìn)程使用的大部分地址空間都在內(nèi)存，缺頁(yè)率低；頁(yè)面中等大?。?gt;局部性區(qū)域只占每頁(yè)的較小部分，缺頁(yè)率高(不能很快適應(yīng)，也不能大部分在內(nèi)存)。分配給進(jìn)程的頁(yè)面數(shù)目：數(shù)目越多－>缺頁(yè)率越低。頁(yè)面數(shù)目的下限，應(yīng)該是一條指令及其操作數(shù)可能涉及的頁(yè)面數(shù)目的上限，以保證每條指令都能被執(zhí)行。缺頁(yè)率表示“缺頁(yè)次數(shù)/內(nèi)存訪問次數(shù)”(比率)或“缺頁(yè)的平均時(shí)間間隔的倒數(shù)”；71缺頁(yè)率(pagefaultrate)發(fā)展趨勢(shì)：采用多種頁(yè)面大小內(nèi)存增大－>應(yīng)用程序增大，而局部性下降（面向?qū)ο蠹夹g(shù)和多線程使數(shù)據(jù)和指令流分散）－>TLB命中率下降，成為性能瓶頸－>增加TLB容量，則成本上升；增加頁(yè)面大小，則缺頁(yè)率上升；采用多種頁(yè)面大小針對(duì)不同規(guī)模的數(shù)據(jù)結(jié)構(gòu)采用不同的頁(yè)面大小。代碼段是大規(guī)模的每個(gè)線程的棧是小規(guī)模的處理器的例子有R4000,DECAlpha和SUNSuperSPARC。其中R4000支持7種頁(yè)面大小，從4KB到16MB72PageSize(1)SmallpagesizeAdvantageslessinternalfragmentationbetterfitforvariousdatastructures,codesectionslessunusedprograminmemoryDisadvantagesprogramsneedmanypages,largerpagetables73PageSize(2)OverheadduetopagetableandinternalfragmentationWheres=averageprocesssizeinbytesp=pagesizeinbytese=pageentrypagetablespaceinternalfragmentationOptimizedwhen

74SeparateInstructionandDataSpacesOneaddressspaceSeparateIandDspaces75SharedPagesTwoprocessessharingsameprogramsharingitspagetable76CleaningPolicyNeedforabackgroundprocess,pagingdaemonperiodicallyinspectsstateofmemoryWhentoofewframesarefreeselectspagestoevictusingareplacementalgorithmItcanusesamecircularlist(clock)asregularpagereplacementalgorithmbutwithdiffptr77ImplementationIssues

OperatingSystemInvolvementwithPagingFourtimeswhenOSinvolvedwithpagingProcesscreationdetermineprogramsizecreatepagetableProcessexecutionMMUresetfornewprocessTLBflushedPagefaulttimedeterminevirtualaddresscausingfaultswaptargetpageout,neededpageinProcessterminationtimereleasepagetable,pages78PageFaultHandling(1)HardwaretrapstokernelGeneralregisterssavedOSdetermineswhichvirtualpageneededOSchecksvalidityofaddress,seekspageframeIfselectedframeisdirty,writeittodisk79PageFaultHandling(2)OSbringsschedulesnewpageinfromdiskPagetablesupdatedFaultinginstructionbackeduptowhenitbeganFaultingprocessscheduledRegistersrestoredProgramcontinues80InstructionBackupAninstructioncausingapagefault81LockingPagesinMemoryVirtualmemoryandI/OoccasionallyinteractProcissuescallforreadfromdeviceintobufferwhilewaitingforI/O,anotherprocessesstartsuphasapagefaultbufferforthefirstprocmaybechosentobepagedoutNeedtospecifysomepageslockedexemptedfrombeingtargetpages82BackingStore(a)Pagingtostaticswaparea(b)Backinguppagesdynamically83SeparationofPolicyandMechanismPagefaulthandlingwithanexternalpager84分段頁(yè)式管理是把內(nèi)存視為一維線性空間；而段式管理是把內(nèi)存視為二維空間，與進(jìn)程邏輯相一致。將程序的地址空間劃分為若干個(gè)段(segment)，程序加載時(shí)，分配其所需的所有段（內(nèi)存分區(qū)），這些段不必連續(xù)；物理內(nèi)存的管理采用動(dòng)態(tài)分區(qū)。需要CPU的硬件支持。85分段程序通過分段(segmentation)劃分為多個(gè)模塊，如代碼段、數(shù)據(jù)段、共享段?？梢苑謩e編寫和編譯可以針對(duì)不同類型的段采取不同的保護(hù)可以按段為單位來進(jìn)行共享，包括通過動(dòng)態(tài)鏈接進(jìn)行代碼共享優(yōu)點(diǎn)：沒有內(nèi)碎片，外碎片可以通過內(nèi)存緊縮來消除。便于改變進(jìn)程占用空間的大小。缺點(diǎn)：進(jìn)程全部裝入內(nèi)存。86段表進(jìn)程段表：描述組成進(jìn)程地址空間的各段，可以是指向系統(tǒng)段表中表項(xiàng)的索引。每段有段基址(baseaddress)和段長(zhǎng)度系統(tǒng)段表：系統(tǒng)內(nèi)所有占用段空閑段表：內(nèi)存中所有空閑段，可以結(jié)合到系統(tǒng)段表中87分段的地址變換88段式地址變換舉例89頁(yè)式管理和段式管理的比較分頁(yè)是出于系統(tǒng)管理的需要，分段是出于用戶應(yīng)用的需要。一條指令或一個(gè)操作數(shù)可能會(huì)跨越兩個(gè)頁(yè)的分界處，而不會(huì)跨越兩個(gè)段的分界處。頁(yè)大