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

1、Module 10: Virtual MemoryBackground（背景）Demand Paging（請(qǐng)求頁(yè)式）Performance of Demand Paging（請(qǐng)求頁(yè)式的性能） Page Replacement（頁(yè)置換）Replacement Algorithms（頁(yè)置換算法）Allocation of Frames （頁(yè)框的分配）Thrashing（顛簸）Other Considerations（其他考慮）Demand Segmenation（請(qǐng)求段式）Applied Operating System ConceptsBackgroundVirtual memory separ

2、ation of user logical memory from physical memory.（虛擬內(nèi)存物理內(nèi)存和用戶邏輯內(nèi)存的區(qū)分）局部性原理(principle of locality) 時(shí)間局部性，空間局部性 Only part of the program needs to be in memory for execution （只有部分運(yùn)行的程序需要在內(nèi)存中）.Logical address space can therefore be much larger than physical address space（因此，邏輯地址空間能夠比物理地址空間大）.Need to al

3、low pages to be swapped in and out（必須允許頁(yè)面能夠被換入和換出）.Virtual memory can be implemented via（虛擬內(nèi)存能夠通過以下手段來執(zhí)行）:Demand paging （請(qǐng)求頁(yè)式）Demand segmentation（請(qǐng)求段式）Applied Operating System Concepts（1）虛擬存儲(chǔ)器的基本概念1.虛擬存儲(chǔ)器的引入 1)局部性原理 在一段時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)域內(nèi)。那么程序?yàn)槭裁磿?huì)出現(xiàn)局部性規(guī)律呢？原因可以歸結(jié)為以下幾點(diǎn)：程序在執(zhí)行時(shí)，除了少部

4、分的轉(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)。Applied Operating System Concepts局限性表現(xiàn)為： 時(shí)間局限性：如果程序中的某條指令一旦執(zhí)行，則不久的將來該指令可能再次被執(zhí)行；如果某個(gè)存儲(chǔ)單元被訪問，則不久以后該存儲(chǔ)單元可能再次被訪問。產(chǎn)生時(shí)間局限性的典型原因是在程序中存在著大量的循環(huán)操作。空間局限性：一旦程序訪問了某個(gè)存儲(chǔ)單

5、元，則在不久的將來，其附近的存儲(chǔ)單元也最有可能被訪問。 即程序在一段時(shí)間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)，其典型原因是程序是順序執(zhí)行的。Applied Operating System ConceptsBackground 虛擬存儲(chǔ)的基本原理 根據(jù)局部性原理，一個(gè)作業(yè)在運(yùn)行之前，沒有必要把全部作業(yè)裝入內(nèi)存，而僅將那些當(dāng)前要運(yùn)行的那部分頁(yè)面或段，先裝入內(nèi)存便可啟動(dòng)運(yùn)行，其余部分暫時(shí)留在磁盤上 程序在運(yùn)行時(shí)如果它所要訪問的頁(yè)（段）已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去；但如果程序所要訪問的頁(yè)（段）尚未調(diào)入內(nèi)存（稱為缺頁(yè)或缺段），此時(shí)程序應(yīng)利用OS所提供的請(qǐng)求調(diào)頁(yè)（段）功能，將它們調(diào)入內(nèi)存，以使進(jìn)程能繼

6、續(xù)執(zhí)行下去。如果內(nèi)存已滿，無法再裝入新的頁(yè)（段），則還須再利用頁(yè)（段）的置換功能，將內(nèi)存中暫時(shí)不用的頁(yè)（段）調(diào)出至磁盤上，騰出足夠的內(nèi)存空間后，再將所要訪問的頁(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ǔ)器。Applied Operating System ConceptsBackground 引入虛擬存儲(chǔ)技術(shù)的好處 可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序 可在內(nèi)存中容納更多程序并發(fā)執(zhí)行 不必影響編程時(shí)的程序結(jié)構(gòu)（與覆蓋

7、技術(shù)比較） 提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存(real memory)Applied Operating System ConceptsBackground 虛擬存儲(chǔ)技術(shù)的特征離散性：指在內(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)存容量。Applied Operating

8、System ConceptsBackgroundpage0.Page nVirtual memoryMemorymapPhysicalmemoryApplied Operating System Concepts虛擬存儲(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)行，以后再通過調(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)段和分段置換功能所形成的段式虛擬

9、存儲(chǔ)系統(tǒng)。它允許只裝入若干段（而非全部段）的用戶程序和數(shù)據(jù)，就可以啟動(dòng)運(yùn)行，以后再通過調(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)。Applied Operating System ConceptsDemand PagingBring a page into memory only when it is needed（只有在一個(gè)頁(yè)需要的時(shí)候才把它換入內(nèi)存）.Less I/O needed（需要很少的I/O）Less memory needed （需要很少的內(nèi)存）Fa

10、ster response（快速響應(yīng)）More users（多用戶）Page is needed （需要頁(yè)） reference to it（查閱此頁(yè)）invalid reference（無效的訪問） abort（中止）not-in-memory（不在內(nèi)存） bring to memory（換入內(nèi)存）取頁(yè)-將哪部分裝入內(nèi)存置頁(yè)-將調(diào)入的頁(yè)放在什么地方淘汰-內(nèi)存不足時(shí)，將哪些頁(yè)換出內(nèi)存。Applied Operating System Concepts請(qǐng)求分頁(yè)存儲(chǔ)管理方式1.請(qǐng)求分頁(yè)中的硬件支持 它是在純分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)，它是目前常用的一

11、種虛擬存儲(chǔ)器的方式。1)請(qǐng)求分頁(yè)的頁(yè)表機(jī)制 它是在純分頁(yè)的頁(yè)表機(jī)制上形成的，由于只將應(yīng)用程序的一部分調(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 訪問字段A 修改位M 外存地址Applied Operating System Concepts其中各字段說明如下：狀態(tài)位（存在位P）：用于指示該頁(yè)是否已調(diào)入內(nèi)存，供程序訪問時(shí)參考。訪問字段A：用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問的次數(shù)，或最近已有多長(zhǎng)時(shí)間未被訪問，提供給置換算法選擇換出頁(yè)面時(shí)參考。修改位M：表示該頁(yè)在調(diào)入內(nèi)存后是否被修改過。由于

12、內(nèi)存中的每一頁(yè)都在外存上保留一份副本，因此，若未被修改，在置換該頁(yè)時(shí)就不需將該頁(yè)寫回到外存上，以減少系統(tǒng)的開銷和啟動(dòng)磁盤的次數(shù)；若已被修改，則必須將該頁(yè)重寫到外存上，以保證外存中所保留的始終是最新副本。外存地址：用于指出該頁(yè)在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)使用。Applied Operating System Concepts請(qǐng)求分頁(yè)中的硬件支持2）缺頁(yè)中斷機(jī)構(gòu) 在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪問的頁(yè)面不在內(nèi)存時(shí)，便要產(chǎn)生一缺頁(yè)中斷，請(qǐng)求OS將所缺頁(yè)調(diào)入內(nèi)存。與一般中斷的主要區(qū)別在于：缺頁(yè)中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)，而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信號(hào)。缺頁(yè)中斷返回

13、到該指令的開始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。Applied Operating System Concepts請(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)的地址變換過程。Applied Operating System Concepts 缺頁(yè)中斷處理 是 否 否 是 是 否 產(chǎn)生缺頁(yè)中 否 是 斷請(qǐng)求調(diào)頁(yè) 是開始（程序請(qǐng)求訪問一頁(yè))越界中斷CPU檢索

14、快表頁(yè)表項(xiàng)是否在快表中？訪問頁(yè)表頁(yè)是否在內(nèi)存中？修改快表修改訪問位和修改位形成物理地址 地址變換結(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硬件 Applied Operating System ConceptsValid-Invalid BitWith each page table entry a validinvalid bit is associated(1 in-memory, 0 not-in-memory)（在每一個(gè)頁(yè)表的表項(xiàng)有一個(gè)有效- 無效位相關(guān)聯(lián)

15、，1表示在內(nèi)存，0表示不內(nèi)存）Initially validinvalid but is set to 0 on all entries（在所有的表項(xiàng)，這個(gè)位被初始化為0）.Example of a page table snapshot（一個(gè)頁(yè)表映象的例子）.During address translation, if validinvalid bit in page table entry is 0（在地址轉(zhuǎn)換中，如果頁(yè)表表項(xiàng)位的值是0） page fault（缺頁(yè)）.1111000Frame #valid-invalid bitpage tableApplied Operating Sy

16、stem ConceptsPage FaultIf there is ever a reference to a page, first reference will trap to OS（如果有對(duì)一個(gè)頁(yè)的訪問，第一個(gè)訪問要陷入OS） page fault（缺頁(yè)）OS looks at another table to decide（OS查看另一個(gè)表來決定）:Invalid reference（無效引用） abort（終止）.Just not in memory（僅僅不在內(nèi)存）.Get empty frame（得到空的頁(yè)框）.Swap page into frame（把頁(yè)換入頁(yè)框）.Reset

17、 tables, validation bit = 1（重新設(shè)置頁(yè)表，把位設(shè)為1）.Restart instruction（重啟指令）: Least Recently Used （最近未使用）block move（塊移動(dòng)）auto increment/decrement location（區(qū)域自動(dòng)增長(zhǎng)/縮減）Applied Operating System ConceptsSteps in handling a page faultLoad M iFree frameOperatingsystemPagetable1reference6 Restart instruction5 Reset p

18、age table3 page is on backing store2 trapPhysical memory4 bring in missing pageApplied Operating System ConceptsWhat happens if there is no free frame?1.we check an internal table(usually kept with the process control block) for this process,to determine whether the reference was a valid or invalid

19、memory access.2.if the reference was invalid, we terminate the process. If it was valid,but we have not yet brought in that page,we now age it in.3.we find a free frame(by taking one from the free-frame list,for example)4.we schedule a disk operation to read the desired page into the newly allocated

20、 frame.5 when the disk read is complete, we modify the internal table kept with the process and the page table to indicate that the page is now in memory6. We restart the instruction that was interrupted by the illegal address trap.the process can now access the page as though it had always been in

21、memoryApplied Operating System ConceptsWhat happens if there is no free frame?Page replacement find some page in memory, but not really in use, swap it out（頁(yè)置換找到內(nèi)存中并沒有使用的一些頁(yè)，換出）.Algorithm（算法）Performance（性能） want an algorithm which will result in minimum number of page faults（找出一個(gè)導(dǎo)致最小缺頁(yè)數(shù)的算法）.Same pag

22、e may be brought into memory several times（同一個(gè)頁(yè)可能會(huì)被裝入內(nèi)存多次）.Applied Operating System Concepts調(diào)入策略、分配策略和清除策略 調(diào)入策略 (fetch policy)(1) 請(qǐng)求調(diào)頁(yè)(demand paging)(2) 預(yù)調(diào)頁(yè)(prepaging) 分配策略 (assignment policy)清除策略(cleaning policy) 請(qǐng)求清除(demand cleaning) 預(yù)清除(precleaning) Applied Operating System Concepts頁(yè)面調(diào)入策略 為能使進(jìn)程運(yùn)行

23、，必須事先將一部分要執(zhí)行的程序和數(shù)據(jù)調(diào)入內(nèi)存。1)調(diào)入頁(yè)面的時(shí)機(jī) 預(yù)調(diào)頁(yè)策略： 是一種主動(dòng)的缺頁(yè)調(diào)入策略，即將那些預(yù)計(jì)在不久的將來會(huì)被訪問的程序或數(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è)，Applied Operating System Concepts頁(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。Applied Operating System Conce

24、pts頁(yè)面調(diào)入策略2)從何處調(diào)入頁(yè)面 在虛擬存儲(chǔ)系統(tǒng)中，外存（硬盤）常常被分成兩部分；文件區(qū)（用于存放文件）和對(duì)換區(qū)（用于存放對(duì)換頁(yè)面）。通常，對(duì)換區(qū)（連續(xù)分配）的磁盤I/O速度比文件區(qū)（離散分配）要高。 每當(dāng)進(jìn)程發(fā)出缺頁(yè)請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁(yè)調(diào)入內(nèi)存呢？在UNIX系統(tǒng)中，對(duì)于從未運(yùn)行過的頁(yè)面，都應(yīng)從硬盤文件區(qū)調(diào)入；對(duì)于曾經(jīng)運(yùn)行過而又被換出的頁(yè)面，可以從對(duì)換區(qū)調(diào)入；對(duì)于共享頁(yè)面，該頁(yè)面可能已由其它進(jìn)程調(diào)入內(nèi)存，此時(shí)就無須再?gòu)膶?duì)換區(qū)調(diào)入。Applied Operating System ConceptsPerformance of Demand PagingA page fault caus

25、e the following sequence to occur: 1. Trap to the operating system 2.Save the user registers and process state 3.Determine that the interrupt was a page fault 4. Check that the page reference was legal and determine the location of the page on the disk 5.Issue a read from the disk to a free frame: a

26、.Wait in a queue for this device until the read request is serviced. b. Wait for the devices seek and/or latency time c. Begin the transfer of the page to a free frame 6. While waiting,allocate the cpu to some user(cpu scheduling operation) 7.Interrupt from the disk(I/O completed) 8.Save the registe

27、rs and process state for the other user(if step 6 executed) 9.Determine that the interrupt was from the disk10. Correct the page table and other tables to show that the desired page is now in memory11.Wait for the cpu to be allocated to this process again12 Restore the user registers,process state,a

28、nd new page table,then resume the interrupted instruction.Applied Operating System Concepts 缺頁(yè)率假定作業(yè)Ji共有m頁(yè)，系統(tǒng)分配給它的主存塊為n塊，這里mn。開始時(shí)，主存沒有裝入任何一頁(yè)的信息。如果作業(yè)Ji在運(yùn)行中成功訪問的次數(shù)為S，不成功的訪問次數(shù)為F(產(chǎn)生缺頁(yè)中斷的次數(shù))，則作業(yè)執(zhí)行過程中總的訪問次數(shù)為A.A=S（成功訪問的次數(shù)）+F（不成功的訪問次數(shù)）作業(yè)Ji執(zhí)行過程中的缺頁(yè)率f=F/A。 Applied Operating System ConceptsPerformance of Demand

29、 PagingPage Fault Rate 0 p 1.0（缺頁(yè)率0 p 1.0）if p = 0 no page faults （如果p = 0 ，沒有缺頁(yè)）if p = 1, every reference is a fault（每次訪問都缺頁(yè)）Effective Access Time (EAT)（有效存取時(shí)間）EAT = (1 p) x memory access+ p (page fault overhead+ swap page out + swap page in+ restart overhead)Applied Operating System ConceptsDemand

30、 Paging ExampleMemory access time = 1 microsecond （存取內(nèi)存的時(shí)間）50% of the time the page that is being replaced has been modified and therefore needs to be swapped out（ 50%的時(shí)間，所置換的頁(yè)被修改，因此需要被換出）.Swap Page Time = 10 msec （交換頁(yè)的時(shí)間）EAT = (1 p) x 1 + p (10) = 1 + 9P (in msec)Applied Operating System ConceptsPa

31、ge ReplacementPrevent over-allocation of memory by modifying fault service routine to include page replacement（通過修改缺頁(yè)服務(wù)例程，來包含頁(yè)置換，防止分配過多）.Use modify (dirty) bit to reduce overhead of page transfers only modified pages are written to disk（修改（臟）位來防止頁(yè)面轉(zhuǎn)移過多只有被修改的頁(yè)面才寫入磁盤）.Page replacement completes separa

32、tion between logical memory and physical memory large virtual memory can be provided on a smaller physical memory（頁(yè)置換完善了邏輯內(nèi)存和物理內(nèi)存的劃分在一個(gè)較小的物理內(nèi)存基礎(chǔ)之上可以提供一個(gè)大的虛擬內(nèi)存.Applied Operating System ConceptsReplacement AlgorithmsWant lowest fault rate（需要一個(gè)最小的缺頁(yè)率）.Evaluate algorithm by running it on a particular st

33、ring of memory references (reference string) and computing the number of page faults on that string（通過運(yùn)行一個(gè)內(nèi)存訪問的特殊序列（訪問序列），計(jì)算這個(gè)序列的缺頁(yè)次數(shù)）.In all our examples, the reference string is （在所有的例子中，訪問序列是）1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.Applied Operating System ConceptsReplacement Algorithms1.最佳算法(OPT, opt

34、imal)2.最近最久未使用算法(LRU,Least Recently Used)3.先進(jìn)先出算法(FIFO) Belady現(xiàn)象4.輪轉(zhuǎn)算法(clock) 最近未使用算法(NRU, Not Recently Used)5.最不常用算法(LFU, Least Frequently Used)Applied Operating System Concepts 先進(jìn)先出（FIFO）置換算法Applied Operating System Concepts 先進(jìn)先出（FIFO）置換算法Applied Operating System ConceptsFirst-In-First-Out (FIFO)

35、AlgorithmReference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 53 frames (3 pages can be in memory at a time per process)4 framesFIFO Replacement Beladys Anomaly（FIFO算法可能會(huì)產(chǎn)生Belady異常）more frames less page faults（頁(yè)就是更多的頁(yè)框相反會(huì)產(chǎn)生更多的缺頁(yè)）1231234125349 page faults1231235124510 page faults443Applied Operating Sy

36、stem Concepts頁(yè)面置換算法 .最佳（Optimal）置換算法 它是一種理想化的算法，性能最好，但在實(shí)際上難于實(shí)現(xiàn)。即選擇那些永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁(yè)面置換出去。但是要確定哪一個(gè)頁(yè)面是未來最長(zhǎng)時(shí)間內(nèi)不再被訪問的，目前來說是很難估計(jì)的，所以該算法通常用來評(píng)價(jià)其它算法。Applied Operating System Concepts頁(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。如下圖所示，進(jìn)程運(yùn)行時(shí)先將7，0，1三個(gè)頁(yè)面裝入內(nèi)存。當(dāng)進(jìn)程訪問頁(yè)面2時(shí)，產(chǎn)生缺

37、頁(yè)中斷，此時(shí)OS根據(jù)最佳置換算法，頁(yè)面7將在第18次才被訪問，是三頁(yè)中將最久不被訪問的頁(yè)面，所以被淘汰。接著訪問頁(yè)面0時(shí)，發(fā)現(xiàn)已在內(nèi)存中，而不會(huì)產(chǎn)生缺頁(yè)中斷，以此類推。從圖可以看出，采用最佳置換算法，只發(fā)生了6次頁(yè)面置換。Applied Operating System Concepts最佳（Optimal）置換算法發(fā)生了6次面置換，9次缺頁(yè)中斷。Applied Operating System ConceptsOptimal AlgorithmReplace page that will not be used for longest period of time（被置換的頁(yè)將是之后最長(zhǎng)時(shí)間

38、不被使用的頁(yè)）.4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5How do you know this?（怎樣知道的）Used for measuring how well your algorithm performs（用來衡量你的算法的效率）.12346 page faults45Applied Operating System Concepts 最近最久未使用置換算法Applied Operating System ConceptsLeast Recently Used (LRU) AlgorithmReference string

39、: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5Counter implementation（計(jì)數(shù)器的實(shí)現(xiàn)）Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter（每一個(gè)頁(yè)表項(xiàng) 有一個(gè)計(jì)數(shù)器，每次頁(yè)通過這個(gè)表項(xiàng)被訪問，把記錄拷貝到計(jì)數(shù)器中）.When a page needs to be changed, look at the counters to determine which are to c

40、hange（當(dāng)一個(gè)頁(yè)需要改變是，查看計(jì)數(shù)器來覺得改變哪一個(gè)頁(yè)0.）12354435Applied Operating System ConceptsLRU Algorithm (Cont.)Stack implementation keep a stack of page numbers in a double link form（棧實(shí)現(xiàn)在一個(gè)雙鏈表中保留一個(gè)記錄頁(yè)數(shù)目的棧）:Page referenced（被訪問的頁(yè)）:move it to the top（移到棧頂）requires 6 pointers to be changed（需要改變6個(gè)指針）No search for replac

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

42、rating System Concepts LRU近似算法舉例Applied Operating System ConceptsLRU Approximation AlgorithmsReference bit（訪問位）With each page associate a bit, initially -= 0（每個(gè)頁(yè)都與一個(gè)位相關(guān)聯(lián)，初始值位0）When page is referenced bit set to 1（當(dāng)頁(yè)是訪問位是設(shè)位1）.Replace the one which is 0 (if one exists). We do not know the order, howev

43、er（，如果存在的話置換位為0的頁(yè)。然而我們并不知道這個(gè)置換順序）.Second chance（二次機(jī)會(huì)）Need reference bit.（需要訪問位）Clock replacement.（時(shí)鐘置換）If page to be replaced (in clock order) has reference bit = 1. Then（如果將要（以順時(shí)針）交換的訪問位是1，則）:set reference bit 0（把訪問位設(shè)位0）.leave page in memory（把頁(yè)留在內(nèi)存中）.replace next page (in clock order), subject to s

44、ame rules（以同樣的規(guī)則，替換下一個(gè)頁(yè)）.Applied Operating System ConceptsCounting AlgorithmsKeep a counter of the number of references that have been made to each page.（用一個(gè)計(jì)數(shù)器記錄對(duì)每一個(gè)頁(yè)的訪問次數(shù)。）LFU Algorithm: replaces page with smallest count（以最小的計(jì)數(shù)置換一個(gè)頁(yè)）.MFU Algorithm: based on the argument that the page with the smal

45、lest count was probably just brought in and has yet to be used（以下面的觀點(diǎn)為基礎(chǔ)，最小計(jì)數(shù)的頁(yè)也許剛剛被換入和使用）.Applied Operating System ConceptsAllocation of FramesEach process needs minimum number of pages（每個(gè)進(jìn)程所需要的最少的頁(yè)的數(shù)目）.Example: IBM 370 6 pages to handle SS MOVE instruction:instruction is 6 bytes, might span 2 page

46、s.2 pages to handle from.2 pages to handle to.Two major allocation schemes（兩個(gè)主要的分配策略）.fixed allocation（固定分配）priority allocation（優(yōu)先分配）Applied Operating System Concepts頁(yè)面分配1)最少物理塊數(shù) 在為進(jìn)程分配物理塊時(shí)，首先應(yīng)該考慮的問題是：能保證進(jìn)程能正常運(yùn)行所需的最少物理塊數(shù)（稱為最小物理塊數(shù)）。若系統(tǒng)為某進(jìn)程所分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無法運(yùn)行，這取決于指令的格式、功能和尋址方式。Applied Operating Syst

47、em Concepts頁(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)存空間不變。Applied Operating System Concepts頁(yè)面分配可變分配全局置換策略：系統(tǒng)為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，而

48、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è)。Applied Operating System Concepts頁(yè)面分配可變分配局部置換：根據(jù)進(jìn)程的類型或程序員的要求，為每個(gè)進(jìn)程分配一定數(shù)目的內(nèi)存空間，并且在進(jìn)程運(yùn)行期間可根據(jù)情況適當(dāng)增加或減少所分配的物理塊數(shù)；但當(dāng)某進(jìn)程發(fā)生缺頁(yè)時(shí)，只允許從該進(jìn)程在內(nèi)存的頁(yè)面中選出一頁(yè)換出，而不影響其它進(jìn)程的運(yùn)行。Applied Operating System Concepts頁(yè)面

49、分配 頁(yè)面分配算法在采用固定分配策略時(shí)，可采用以下幾種物理塊分配方法：平均分配算法：將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。按比例分配算法：這是根據(jù)進(jìn)程的大小按比例分配物理塊。Applied Operating System Concepts頁(yè)面分配 頁(yè)面分配算法考慮優(yōu)先權(quán)的分配算法：該方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。Applied Operating System ConceptsFixed AllocationEqual allocation（平均分配） e.g., if

50、100 frames and 5 processes, give each 20 pages（例：如果有100個(gè)頁(yè)框，和5個(gè)進(jìn)程，則每個(gè)進(jìn)程分給20個(gè)頁(yè)）.Proportional allocation（按比率分配） Allocate according to the size of process（根據(jù)每個(gè)進(jìn)程的大小來分配）.Applied Operating System ConceptsPriority AllocationUse a proportional allocation scheme using priorities rather than size（根據(jù)優(yōu)先級(jí)而不是大小來使

51、用比率分配策略）.If process Pi generates a page fault,（如果進(jìn)程Pi產(chǎn)生一個(gè)缺頁(yè)）select for replacement one of its frames（選擇替換其中的一個(gè)頁(yè)框）.select for replacement a frame from a process with lower priority number（從一個(gè)較低優(yōu)先級(jí)的進(jìn)程中選擇一個(gè)頁(yè)面來替換）.Applied Operating System ConceptsGlobal vs. Local AllocationGlobal replacement（全局替換） proce

52、ss selects a replacement frame from the set of all frames; one process can take a frame from another（進(jìn)程在所有的頁(yè)中選擇一個(gè)替換頁(yè)面；一個(gè)進(jìn)程可以從另一個(gè)進(jìn)程中獲得頁(yè)面）.Local replacement （局部替換） each process selects from only its own set of allocated frames（每個(gè)進(jìn)程只從屬于它自己的頁(yè)中選擇）.Applied Operating System ConceptsThrashingIf a process do

53、es not have “enough” pages, the fault rate is very high. This leads to（如果一個(gè)進(jìn)程沒有足夠的頁(yè)，那么缺頁(yè)率將很高，這將導(dǎo)致）:low CPU utilization（CPU利用率低下）.operating system thinks that it needs to increase the degree of multiprogramming（操作系統(tǒng)認(rèn)為需要增加多道程序設(shè)計(jì)的道數(shù)）.another process added to the system（系統(tǒng)中將加入一個(gè)新的進(jìn)程）.Thrashing（顛簸） a pro

54、cess is busy swapping pages in and out（一個(gè)進(jìn)程的頁(yè)面經(jīng)常換入換出）.Applied Operating System ConceptsThrashing DiagramWhy does paging work?（為什么分頁(yè)工作）Locality model（位置模式）Process migrates from one locality to another（進(jìn)程從一個(gè)位置移到另一個(gè)位置）.Localities may overlap（位置可能重疊）.Why does thrashing occur?（為什么顛簸會(huì)發(fā)生） size of locality

55、total memory sizeApplied Operating System ConceptsWorking-Set Model working-set window a fixed number of page references Example: 10,000 instructionWSSi (working set of Process Pi) =total number of pages referenced in the most recent (varies in time)if too small will not encompass entire locality.if

56、 too large will encompass several localities.if = will encompass entire program.D = WSSi total demand frames if D m ThrashingPolicy if D m, then suspend one of the processes.Applied Operating System ConceptsFault Frequency SchemeEstablish “acceptable” fault rate（設(shè)置可接受的缺頁(yè)率）.If actual rate too low, pr

57、ocess loses frame（如果缺頁(yè)率太低，回收一些進(jìn)程的頁(yè)框）.If actual rate too high, process gains frame（如果缺頁(yè)率太高，就分給進(jìn)程一些頁(yè)框）.Applied Operating System ConceptsOther ConsiderationsPrepaging （預(yù)先調(diào)頁(yè)）Page size selection（頁(yè)面尺寸選擇）Fragmentation（碎片）table size （表大小）I/O overhead（I/O開銷）Locality（位置）Applied Operating System ConceptsOther

58、Consideration (Cont.)Program structure（程序結(jié)構(gòu)）Array A1024, 1024 of integerEach row is stored in one pageOne frame Program 1 for j := 1 to 1024 dofor i := 1 to 1024 doAi,j := 0;1024 x 1024 page faults Program 2 for i := 1 to 1024 dofor j := 1 to 1024 doAi,j := 0;1024 page faultsI/O interlock and addres

59、sing（I/O連接和地址）Applied Operating System ConceptsDemand SegmentationUsed when insufficient hardware to implement demand paging（當(dāng)請(qǐng)頁(yè)的硬件不充足時(shí)使用）.OS/2 allocates memory in segments, which it keeps track of through segment descriptors（操作系統(tǒng)以段來分配內(nèi)存，它通過段描述符來進(jìn)行跟蹤）Segment descriptor contains a valid bit to indica

60、te whether the segment is currently in memory（段描述符有一個(gè)有效位來說明段是否以在內(nèi)存）.If segment is in main memory, access continues（如果段已在主存中，繼續(xù)存?。?If not in memory, segment fault（如果不在內(nèi)存中，缺段中斷）.Applied Operating System Concepts請(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)所訪問