ch44.7虛擬存儲(chǔ)管理

1、CH4 存儲(chǔ)管理4.1 主存儲(chǔ)器 4.2 連續(xù)存儲(chǔ)空間管理 4.3 分頁式存儲(chǔ)管理 4.4 分段式存儲(chǔ)管理4.5 段頁式存儲(chǔ)管理4.6 交換技術(shù)和覆蓋技術(shù) 4.7 虛擬存儲(chǔ)管理 4.8 實(shí) 例 研 究：Intel Pentium存儲(chǔ)管理硬件設(shè)施14.7 虛擬存儲(chǔ)管理4.7.1 虛擬存儲(chǔ)管理的概述4.7.2 請(qǐng)求分頁虛擬存儲(chǔ)管理4.7.3 請(qǐng)求分段虛擬存儲(chǔ)管理4.7.4 請(qǐng)求段頁式虛擬存儲(chǔ)管理24.7.1虛擬存儲(chǔ)管理概述 1、問題的提出 程序大于內(nèi)存 當(dāng)要運(yùn)行的作業(yè)很多，而內(nèi)存空間不足的時(shí)，只能讓一部分作業(yè)先運(yùn)行，大量作業(yè)只能在外存中等待。 虛擬存貯管理策略考慮的出發(fā)點(diǎn)是基于程序局部性原理在一段

2、時(shí)間內(nèi)，一個(gè)程序的執(zhí)行往往呈現(xiàn)出高度的局部性，它對(duì)內(nèi)存的訪問是很不均勻的。32、局部性原理局部性原理：指程序在執(zhí)行過程中的一個(gè)較短時(shí)期內(nèi)，所執(zhí)行的指令地址和指令的操作數(shù)地址分別局限于一定區(qū)域。主要表現(xiàn)為：時(shí)間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，一個(gè)數(shù)據(jù)的一次訪問和下次訪問都集中在一個(gè)較短時(shí)期內(nèi)；原因是由于在程序中存在著大量的循環(huán)、子程序等程序結(jié)構(gòu)。 空間局部性：若某一存儲(chǔ)單元被訪問，那么與該存儲(chǔ)單元相鄰的單元可能也會(huì)很快被訪問。4虛擬存儲(chǔ)管理的主要技術(shù)是部分裝入和部分對(duì)換。 部分裝入：當(dāng)用戶作業(yè)被調(diào)度開始執(zhí)行時(shí)，不必將作業(yè)全部讀入主存，而是將當(dāng)前需要執(zhí)行的部分讀入主存，其他部分根據(jù)作業(yè)執(zhí)行的

3、需要逐步裝入主存。 部分對(duì)換：在程序執(zhí)行過程中，當(dāng)內(nèi)存空間緊張時(shí)，操作系統(tǒng)將暫不執(zhí)行的部分程序和數(shù)據(jù)調(diào)出，保存在外存上，從而騰出內(nèi)存空間存放將要裝入的程序和數(shù)據(jù)，或者留給系統(tǒng)再分配。 虛擬存儲(chǔ)管理的目的：把分開編址的二級(jí)存儲(chǔ)器內(nèi)存和輔存,變成面向用戶的，邏輯上可以統(tǒng)一編址的虛擬存儲(chǔ)器。3、虛擬存儲(chǔ)管理的基本思想54、虛擬存儲(chǔ)器的定義在具有層次結(jié)構(gòu)存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中，采用自動(dòng)實(shí)現(xiàn)部分裝入和部分對(duì)換功能，為用戶提供一個(gè)比物理主存容量大得多的，可尋址的一種“主存儲(chǔ)器”。虛擬存儲(chǔ)器的大小受限于計(jì)算機(jī)的地址結(jié)構(gòu)及可用的外存的容量?？?cè)萘坎怀^物理內(nèi)存和外存交換區(qū)容量之和。65、虛擬存儲(chǔ)器的特征 離散性

4、：系統(tǒng)內(nèi)存管理機(jī)構(gòu)分配給該作業(yè)的內(nèi)存空間不一定是連續(xù)的。 多次性：多次性是指一個(gè)作業(yè)被分成多次調(diào)入主存內(nèi)運(yùn)行。 對(duì)換性：在進(jìn)程運(yùn)行過程中，可以把那些暫時(shí)不運(yùn)行的程序和數(shù)據(jù)，從內(nèi)存調(diào)至外存的對(duì)換區(qū)，把當(dāng)前要運(yùn)行的程序和數(shù)據(jù)調(diào)入內(nèi)存?？梢?，對(duì)換有利于提高內(nèi)存的利用率。 虛擬性：操作系統(tǒng)通過把內(nèi)存和輔存從邏輯上結(jié)合起來，使用戶感覺到存儲(chǔ)容量遠(yuǎn)遠(yuǎn)大于實(shí)際的內(nèi)存容量，以實(shí)現(xiàn)擴(kuò)充內(nèi)存的目的。 7實(shí)現(xiàn)虛擬存儲(chǔ)器必須解決好以下有關(guān)問題：主存輔存統(tǒng)一管理問題邏輯地址到物理地址的轉(zhuǎn)換問題部分裝入和部分對(duì)換問題虛擬存儲(chǔ)管理主要采用以下存儲(chǔ)管理方法實(shí)現(xiàn)： 請(qǐng)求分頁虛擬存儲(chǔ)管理請(qǐng)求分段虛擬存儲(chǔ)管理請(qǐng)求段頁式虛擬存儲(chǔ)管理

5、84.7.2 請(qǐng)求分頁式存儲(chǔ)管理 動(dòng)態(tài)離散分配方式1. 基本思想等份主存、用戶邏輯地址空間 將程序的邏輯地址空間劃分成若干大小相等的區(qū)域，稱為頁或頁面。相應(yīng)地，將物理內(nèi)存劃分為與頁大小相等的區(qū)域，稱為塊或物理塊，并分別給頁和塊編以連續(xù)的序號(hào)0、1、2、3、主存分配原則 以塊為單位分配，作業(yè)以頁調(diào)入塊中，作業(yè)塊不一定是連續(xù)的，但不必全部裝入。9請(qǐng)求分頁式存儲(chǔ)管理基本思想部分裝入：在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入一個(gè)或零個(gè)頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁面；部分對(duì)換：當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁面，以便裝入新的頁面102. 數(shù)據(jù)結(jié)構(gòu)作業(yè)

6、表：整個(gè)系統(tǒng)有一個(gè)作業(yè)表，描述系統(tǒng)內(nèi)各個(gè)進(jìn)程頁表的起始位置和大小，用于地址轉(zhuǎn)換。物理頁面表（內(nèi)存塊表）：整個(gè)系統(tǒng)有一個(gè)物理頁面表，描述物理內(nèi)存空間的空閑和占用狀況。頁表：每個(gè)進(jìn)程有一個(gè)頁表，描述該進(jìn)程相應(yīng)頁在系統(tǒng)中的狀況。如是否在內(nèi)存？頁對(duì)應(yīng)的塊號(hào)？11標(biāo)志位（存在位）：用于指示該頁是在內(nèi)存還是在外存。訪問統(tǒng)計(jì)：在近期內(nèi)被訪問的次數(shù)，或最近一次訪問到現(xiàn)在的時(shí)間間隔。決定淘汰哪頁（由不同的算法決定）。修改位：表示該頁在調(diào)入內(nèi)存后是否被修改過。外存地址：用于指出該頁在外存上的地址。頁表表項(xiàng)：頁號(hào)物理塊號(hào)標(biāo)志位訪問字段修改位外存地址123 .請(qǐng)求分頁存儲(chǔ)管理系統(tǒng)頁面分配過程該頁修改過嗎？Y寫回輔存N

7、根據(jù)某種算法淘汰一頁調(diào)整頁表地址映射YN獲得邏輯地址：頁號(hào)、頁內(nèi)位移該頁在內(nèi)存？N有無空閑塊？Y調(diào)入頁面產(chǎn)生缺頁中斷啟動(dòng)待執(zhí)行指令執(zhí)行指令指令地址+1缺頁中斷處理過程 頁面淘汰134.缺頁中斷什么是缺頁中斷在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去。 缺頁中斷與與一般的中斷的區(qū)別 在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。當(dāng)所缺的頁面調(diào)入之后，重新執(zhí)行被中斷的指令。 一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。14缺頁率缺頁率f等于 缺頁次數(shù)F / 內(nèi)存總訪問次數(shù)A (

8、比率) 即 f = F / A15發(fā)缺頁中斷5.請(qǐng)求分頁地址轉(zhuǎn)換過程(1) 邏輯空間地址主存(用戶區(qū))CPU邏輯地址快表主存(系統(tǒng)區(qū)) 查頁表輔存缺頁中斷處理分解地址訪問MMU查快表命中不命中頁表命中調(diào)頁裝入、改表裝入快表運(yùn)行進(jìn)程映象物理地址頁框 頁內(nèi)地址頁號(hào) 頁內(nèi)地址16分頁式虛擬存儲(chǔ)系統(tǒng)的硬件支撐(1) 主存管理單元MMU完成邏輯地址到物理地址的轉(zhuǎn)換功能，它接受虛擬地址作為輸入，物理地址作為輸出，直接送到總線上，對(duì)主存單元進(jìn)行尋址。 17分頁式虛擬存儲(chǔ)系統(tǒng)的硬件支撐CPUMMU內(nèi)存CPU把邏輯地址送至MMUMMU把物理地址送至主存 MMU的位置、功能和16個(gè)4KB頁面情況下MMU的內(nèi)部操作

9、CPU送入的邏輯地址(8196) 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0MMU送出的物理地址0 010 11 001 12 110 13 000 14 100 15 011 16 000 07 000 08 101 19 000 0頁號(hào) 頁框號(hào) 在主存否18MMU主要功能(1)管理硬件頁表基址寄存器。(2)分解邏輯地址。(3)管理快表TLB。(4)訪問頁表。(5)發(fā)出缺頁中斷或越界中斷，并將控制權(quán)交給內(nèi)核存儲(chǔ)管理處理。(6)設(shè)置和檢查頁表中各個(gè)特征位。19 地址轉(zhuǎn)換過程(2)查快表有登記無登記查頁表登記入快表發(fā)

10、缺頁中斷在主存在輔存形成絕對(duì)地址繼續(xù)執(zhí)行指令重新執(zhí)行被中斷指令恢復(fù)現(xiàn)場調(diào)整頁表和主存分配表裝入所需頁面主存有空閑塊保護(hù)現(xiàn)場有選擇調(diào)出頁面該頁是否修改未修改已修改把該頁寫回輔存相應(yīng)位置操作系統(tǒng)硬件邏輯地址無206 .頁面的調(diào)入和分配策略請(qǐng)求調(diào)頁(demand paging)：只調(diào)入發(fā)生缺頁時(shí)所需的頁面。優(yōu)點(diǎn)：確保只有被訪問的頁調(diào)入主存，節(jié)省內(nèi)存。缺點(diǎn)：調(diào)入頁的開銷大，增加了對(duì)外存I/O次數(shù)預(yù)調(diào)頁(prepaging)：OS依據(jù)某種算法預(yù)測，預(yù)先將某頁或若干頁調(diào)入主存。優(yōu)點(diǎn)：提高調(diào)頁的I/O效率。缺點(diǎn)：基于預(yù)測，若調(diào)入的頁在以后很少被訪問，則效率低。常用于程序裝入時(shí)的調(diào)頁。（1）調(diào)入策略調(diào)入策略確

11、定在外存中的頁面調(diào)入時(shí)機(jī)。在虛擬頁式管理中有兩種常用策略。21（2）頁面分配策略系統(tǒng)為進(jìn)程分配主存,需考慮因素: 分給進(jìn)程的空間越小,同一時(shí)間處于主存的進(jìn)程就越多，至少有一個(gè)進(jìn)程處于就緒態(tài)的可能性就越大如果進(jìn)程只有小部分在主存里,即使局部性很好,缺頁中斷率還會(huì)相當(dāng)因程序的局部性原理，分給進(jìn)程的主存超過一定限度后，再增加主存空間,不會(huì)明顯降低進(jìn)程的缺頁中斷率。22頁面分配策略：固定分配進(jìn)程保持頁框數(shù)固定不變,稱固定分配;進(jìn)程創(chuàng)建時(shí),根據(jù)進(jìn)程類型和程序員的要求決定頁框數(shù),只要有一個(gè)缺頁中斷產(chǎn)生,進(jìn)程就會(huì)有一頁被替換。23頁面分配策略：可變分配進(jìn)程分得的頁框數(shù)可變, 稱可變分配;進(jìn)程執(zhí)行的某階段缺頁

12、率較高,說明目前局部性較差，系統(tǒng)可多分些頁框以降低缺頁率，反之說明進(jìn)程目前的局部性較好,可減少分給進(jìn)程的頁框數(shù)24頁面替換策略：局部替換和全局替換頁面替換需要采用一定的算法來實(shí)現(xiàn)算法如果頁面替換算法的作用范圍是整個(gè)系統(tǒng)，稱全局頁面替換算法,它可以在運(yùn)行進(jìn)程間動(dòng)態(tài)地分配頁框。解決：從那個(gè)進(jìn)程選擇頁面？缺頁中斷率是否上升？如果頁面替換算法的作用范圍局限于本進(jìn)程，稱為局部頁面替換算法,它實(shí)際上需要為每個(gè)進(jìn)程分配固定的頁框。 25固定分配和局部替換策略配合使用(1)進(jìn)程分得的頁框數(shù)不變，發(fā)生缺頁中斷，只能從進(jìn)程的頁面中選頁替換，保證進(jìn)程的頁框總數(shù)不變。策略難點(diǎn)：應(yīng)給每個(gè)進(jìn)程分配多少頁框?給少了,缺頁中

13、斷率高;給多了,使主存中能同時(shí)執(zhí)行的進(jìn)程數(shù)減少，進(jìn)而造成處理器和其它設(shè)備空閑。26固定分配和局部替換策略配合使用(2) 采用固定分配算法，系統(tǒng)把頁 框分配給進(jìn)程，采用：平均分配，按比例分配, 優(yōu)先權(quán)分配。27可變分配和全局替換策略配合使用先每個(gè)進(jìn)程分配一定數(shù)目頁框,os保留若干空閑頁框,進(jìn)程發(fā)生缺頁中斷時(shí)，從系統(tǒng)空閑頁框中選一個(gè)給進(jìn)程,這樣產(chǎn)生缺頁中斷進(jìn)程的主存空間會(huì)逐漸增大,有助于減少系統(tǒng)的缺頁中斷次數(shù)。系統(tǒng)擁有的空閑頁框耗盡時(shí) ，會(huì)從主存中選擇一頁淘汰，該頁可以是主存中任一進(jìn)程的頁面，這樣又會(huì)使那個(gè)進(jìn)程的頁框數(shù)減少，缺頁中斷率上升。28可變分配和局部替換配合使用其實(shí)現(xiàn)要點(diǎn)如下:(1)新進(jìn)程

14、裝入主存時(shí)，根據(jù)應(yīng)用類型、程序要求，分配給一定數(shù)目頁框,可用請(qǐng)頁式或預(yù)調(diào)式完成這個(gè)分配。(2)產(chǎn)生缺頁中斷時(shí),從該進(jìn)程駐留集中選一個(gè)頁面替換。(3)不時(shí)重新評(píng)價(jià)進(jìn)程的分配，增加或減少分配給進(jìn)程的頁框以改善系統(tǒng)性能。297 .頁面置換算法最佳置換算法（OPT, Belady算法） 算法：淘汰那些以后永不使用，或者是在最長時(shí)間內(nèi)不再被訪問的頁。無法實(shí)現(xiàn)的，只能作為其它置換算法的衡量標(biāo)準(zhǔn)。 先進(jìn)先出算法（FIFO） 算法：每次淘汰最先進(jìn)入主存的頁 優(yōu)點(diǎn)：簡單，易于實(shí)現(xiàn) 缺點(diǎn)：效率不高，可能產(chǎn)生“抖動(dòng)”現(xiàn)象30例1：計(jì)算缺頁次數(shù) 某程序在內(nèi)存中分配三個(gè)頁面，初始為空，頁面走向?yàn)?，3，2，1，4，3，

15、5，4，3，2，1，531共缺頁中斷7次,缺頁率=7/12=58%32 共缺頁中斷9次，缺頁率=9/12=75%33例2：計(jì)算缺頁次數(shù)用FIFO算法計(jì)算某程序在內(nèi)存中分配m頁初始為空，頁面走向?yàn)?，2，3，4，1，2，5，1，2，3，4，5。當(dāng)m=3，m=4時(shí)缺頁中斷分別為多少？34如果在內(nèi)存中分配3個(gè)頁面，則缺頁情況如下：12次訪問中有缺頁9次；35如果在內(nèi)存中分配4個(gè)頁面，則缺頁情況如下：12次訪問中有缺頁10次；36例2：計(jì)算缺頁次數(shù)m=3時(shí)，缺頁中斷9次m=4時(shí)，缺頁中斷10次注：FIFO頁面淘汰算法會(huì)產(chǎn)生異?，F(xiàn)象，即：當(dāng)分配給進(jìn)程的物理頁面數(shù)增加時(shí)，缺頁次數(shù)反而增加。37抖動(dòng)現(xiàn)象：采

16、用FIFO算法時(shí)，如果對(duì)一個(gè)進(jìn)程未分配它所要求的全部頁面，有時(shí)就會(huì)出現(xiàn)分配的頁面數(shù)增多，缺頁率反而提高的異?，F(xiàn)象。異?，F(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動(dòng)態(tài)特征是矛盾的，即被置換的頁面并不是進(jìn)程不會(huì)訪問的。抖動(dòng)現(xiàn)象38最近最久未使用（LRU）算法 算法：選擇淘汰內(nèi)存中那些在最近一段時(shí)間里最久未使用的頁面置換。但由于需要記錄頁面使用時(shí)間的先后關(guān)系，硬件開銷太大。硬件機(jī)構(gòu)如：一個(gè)特殊的棧：把被訪問的頁面移到棧頂，于是棧底的是最久未使用頁面。每個(gè)頁面設(shè)立移位寄存器：被訪問時(shí)左邊最高位置1，定期右移并且最高位補(bǔ)0，于是寄存器數(shù)值最小的是最久未使用頁面。39 缺頁中斷10次，缺頁率=10

17、/12=83%40第二次機(jī)會(huì)頁面替換算法改進(jìn)FIFO算法,把FIFO與頁表中的”引用位”結(jié)合起來使用：檢查FIFO中的隊(duì)首頁面(最早進(jìn)入主存的頁面),如果它的”引用位”是0,這個(gè)頁面既老又沒有用，選擇該頁面淘汰; 如果”引用位”是1,說明它進(jìn)入主存較早，但最近仍在使用。把它的”引用位”清0,并把這個(gè)頁面移到隊(duì)尾，把它看作是一個(gè)新調(diào)入的頁。算法含義：最先進(jìn)入主存的頁面，如果最近還在被使用的話,仍然有機(jī)會(huì)作為像一個(gè)新調(diào)入頁面一樣留在主存中。41時(shí)鐘頁面替換算法(1) 算法實(shí)現(xiàn)要點(diǎn)(1)： 一個(gè)頁面首次裝入主存，其“引用位”置0 。主存中的任何頁面被訪問時(shí), ”引用位”置1。淘汰頁面時(shí),從指針當(dāng)前指

18、向的頁面開始掃描循環(huán)隊(duì)列，把遷到的”引用位”是1的頁面的”引用位”清0,跳過這個(gè)頁面; 把所遷到的”引用位”是0的頁面淘汰掉,指針推進(jìn)一步。42時(shí)鐘頁面替換算法(2) 算法實(shí)現(xiàn)要點(diǎn)(2)：掃描循環(huán)隊(duì)列時(shí)，如果遷到的所有頁面的”引用位”為1，指針就會(huì)繞整個(gè)循環(huán)隊(duì)列一圈，把碰到的所有頁面的”引用位”清0;指針停在起始位置，并淘汰掉這一頁,然后，指針推進(jìn)一步。43時(shí)鐘頁面替換算法的一個(gè)例子 一個(gè)頁替換前的緩沖區(qū)狀態(tài)下一頁替換后的緩沖區(qū)狀態(tài)Page9 use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page

19、67Use=1Page33Use=1Page222Use=0下一個(gè)幀指針n012345678Page9 use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=1Page727Use=1Page13Use=0Page67Use=1Page33Use=1Page222Use=0n012345678第1頁框44時(shí)鐘頁面替換改進(jìn)算法(1)把”引用位”和”修改位”結(jié)合起來使用，共組合成四種情況：(1)最近沒有被引用,沒有被修改(r=0,m=0)(2)最近被引用,沒有被修改(r=1,m=0)(3)最近沒有被引用,但被修改(r=0,m=1)(4)最近被引用過,也被修

20、改過(r=1,m=1)45時(shí)鐘頁面替換改進(jìn)算法(2)步1：選擇最佳淘汰頁面，從指針當(dāng)前位置開始,掃描循環(huán)隊(duì)列。掃描過程中不改變”引用位”，把遇到的第一個(gè)r=0,m=0的頁面作為淘汰頁面。步2：如果步1失敗，再次從原位置開始，查找r=0且m=1的頁面，把把遇到的第一個(gè)這樣的頁面作為淘汰頁面，而在掃描過程中把指針?biāo)鶔哌^的頁面的”引用位”r置0。46時(shí)鐘頁面替換改進(jìn)算法(3)步3：如果步2失敗，指針再次回到了起始位置，由于此時(shí)所有頁面的”引用位”r均己為0，再轉(zhuǎn)向步1操作，必要時(shí)再做步2操作，這次一定可以挑出一個(gè)可淘汰的頁面。478. 影響缺頁次數(shù)的因素(1) 分配給進(jìn)程的物理頁面數(shù)(2) 頁面大小

21、(3) 程序的編制方法(4) 頁面淘汰算法489.請(qǐng)求頁式存儲(chǔ)管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：作業(yè)的程序和數(shù)據(jù)可按頁分散存放在內(nèi)存中，減少移動(dòng)開銷，有效解決了碎片問題;既有利于改進(jìn)主存利用率，又有利于多道程序運(yùn)行。缺點(diǎn)：要有硬件支持，要進(jìn)行缺頁中斷處理，機(jī)器成本增加，系統(tǒng)開銷加大。 4910. 性能問題 顛簸（抖動(dòng)） 在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動(dòng).原因：頁面淘汰算法不合理分配給進(jìn)程的物理頁面數(shù)太少50工作集模型和工作集置換算法 進(jìn)程工作集指“在某一段時(shí)間間隔內(nèi)進(jìn)程運(yùn)行所需訪問的頁面集合”

22、。實(shí)現(xiàn)思想： 工作集模型用來對(duì)局部最佳頁面替換算法進(jìn)行模擬實(shí)現(xiàn)，不向前查看頁面引用串，而是基于程序局部性原理向后看，在任何給定時(shí)刻，一個(gè)進(jìn)程不久的將來所需主存頁框數(shù)，可通過考查其過去最近的時(shí)間內(nèi)的主存需求做出估計(jì)。51 工作集（Working Set）模型 基本思想：根據(jù)程序的局部性原理，一般情況下，進(jìn)程在一段時(shí)間內(nèi)總是集中訪問一些頁面，這些頁面稱為活躍頁面，如果分配給一個(gè)進(jìn)程的物理頁面數(shù)太少了，使該進(jìn)程所需的活躍頁面不能全部裝入內(nèi)存，則進(jìn)程在運(yùn)行過程中將頻繁發(fā)生中斷。如果能為進(jìn)程提供與活躍頁面數(shù)相等的物理頁面數(shù)，則可減少缺頁中斷次數(shù)。52工作集： 對(duì)于給定的訪問序列選取定長的區(qū)間，稱為工作集

23、窗口，落在工作集窗口中的頁面集合稱為工作集。進(jìn)程工作集指“在某一段時(shí)間間隔內(nèi)進(jìn)程運(yùn)行所需訪問的頁面集合”。內(nèi)容取決于頁的三個(gè)因素： 訪頁序列特性 時(shí)刻Ti 窗口長度()53例： 261234443434441327 | |t1 | |t2 ws(t1)=1,2,5,6,7 ws(t2)=3,45412 請(qǐng)求分頁虛擬存儲(chǔ)管理的幾個(gè)設(shè)計(jì)問題頁面大小 .從頁表大小考慮 .從主存利用率考慮 .從讀寫一個(gè)頁面所需時(shí)間考慮 .最佳頁面尺寸頁面 5512 請(qǐng)求分頁虛擬存儲(chǔ)管理的幾個(gè)設(shè)計(jì)問題 (1)最佳頁面尺寸假定S表示用戶作業(yè)程序的字節(jié)數(shù)平均長度，P表示以字節(jié)為單位的頁面長度，且有SP，頁表項(xiàng)需要e個(gè)字節(jié)。

24、作業(yè)的頁表長度為S/P，占用了Se/P個(gè)字節(jié)的頁表空間，作業(yè)的最后一頁，浪費(fèi)的主存平均為P/2字節(jié)。對(duì)一個(gè)作業(yè)而言： 浪費(fèi)的存儲(chǔ)字=頁表使用的主存空間+內(nèi)部碎片=Se/P+P/256最佳頁面尺寸頁面較小時(shí)頁表占用空間多(因Se/P較大)，頁面較大時(shí)內(nèi)部碎片浪費(fèi)多(因P/2較大)?，F(xiàn)對(duì)P求一階導(dǎo)數(shù)并令其為0，得到 -Se/P2+1/2=0 那么，可以得出最優(yōu)頁面尺寸 P=根號(hào)（2Se） 時(shí)，浪費(fèi)的存儲(chǔ)字節(jié)最少，稱P為最佳 頁面尺寸。57(2)頁面交換區(qū)替換算法要挑選頁面淘汰出主存，但被淘汰出去的頁面可能很快使用，又要被重新裝入主存。操作系統(tǒng)必須保存被淘汰的頁面,例如UNIX/Linux使用交換區(qū)

25、臨時(shí)保存頁面，系統(tǒng)初始化時(shí),保留一定盤空間作交換區(qū)。58(3)寫時(shí)復(fù)制寫時(shí)復(fù)制(copy-on-write)是存儲(chǔ)管理節(jié)省物理主存(頁框)的一種頁面級(jí)優(yōu)化技術(shù),已被UNIX和Windows等采用，能減少主存頁面內(nèi)容的復(fù)制操作,減少相同內(nèi)容頁面在主存的副本數(shù)目。59寫時(shí)復(fù)制(2)原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進(jìn)程地址空間物理地址空間原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進(jìn)程地址空間物理地址空間原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進(jìn)程地址空間原始數(shù)據(jù)原始數(shù)據(jù)原始數(shù)據(jù)進(jìn)程地址空間頁面2副本 頁面1頁面2頁面3頁面1頁面2頁面3604.7.3 請(qǐng)求分段式存儲(chǔ)管理 動(dòng)態(tài)離散分配方式1. 基本思想用戶程序劃分 按程序自身的邏輯關(guān)系，將程

26、序的邏輯地址空間劃分成若干段，每個(gè)段都是獨(dú)立的邏輯單位，有完整和相對(duì)獨(dú)立的意義。 一個(gè)程序由若干段組成，每個(gè)段的大小可以不同。 每個(gè)程序段都有一個(gè)段名，且有一個(gè)段號(hào)。段號(hào)從0開始，每一段也從0開始編址，段內(nèi)地址是連續(xù)的。 61 內(nèi)存分配 主存以段為單位分配內(nèi)存，每一個(gè)段在內(nèi)存中占據(jù)連續(xù)空間，一個(gè)進(jìn)程的各段所分到的主存分區(qū)可以是不連續(xù)的。部分裝入：在作業(yè)運(yùn)行之前，不需要把作業(yè)的整個(gè)地址空間全部裝入主存，而只要將作業(yè)當(dāng)前需要的一段或幾段裝入主存即可開始運(yùn)行。部分對(duì)換：在執(zhí)行過程中，當(dāng)所需要的段不在主存時(shí)再將它調(diào)入。請(qǐng)求分段式存儲(chǔ)管理62特征位：00不在內(nèi)存，01在內(nèi)存，11共享段；存取權(quán)限：00可

27、執(zhí)行，01可讀，11可寫；擴(kuò)充位：0固定長，1可擴(kuò)充；標(biāo)志位：00未修改，01已修改，11不可移動(dòng)；外存地址：本段在外存上的起始地址。2. 對(duì)進(jìn)程段表的修改段號(hào)段長基址特征位存取權(quán)限擴(kuò)充位標(biāo)志位外存地址633. 缺段中斷如果訪問的段不在主存中，系統(tǒng)將產(chǎn)生一個(gè)缺段中斷，請(qǐng)求操作系統(tǒng)將所缺的段調(diào)入主存。缺段中斷的特殊性缺段中斷在指令執(zhí)行期間產(chǎn)生和進(jìn)行處理。一條指令的執(zhí)行可能產(chǎn)生多次缺段中斷。64需調(diào)入新段S內(nèi)存中有空閑區(qū)S的段長是否合并空閑區(qū)，形成長度大于S段長的空閑區(qū)為段S分配內(nèi)存空閑區(qū)，調(diào)段S至內(nèi)存修改段表返回內(nèi)存中空閑區(qū)總和大于S段長是按一定的算法淘汰段，形成大于S的空閑區(qū)缺段中斷處理過程654. 地址轉(zhuǎn)換過程S段在內(nèi)存否是B 段長？越界中斷允許本次訪問？YNNY修改訪問字段，置訪問位和狀態(tài)分段保護(hù)中斷查快表或段表，段S的始址+段內(nèi)位移D形成物理地址67越界中斷處理 進(jìn)程在執(zhí)行過程中，有時(shí)需要擴(kuò)大分段，如數(shù)據(jù)段。由于要訪問的地址超出原有的段長，所以發(fā)越界中斷。操作系統(tǒng)處理中斷時(shí) ，首先判斷該段的“擴(kuò)充位”，如可擴(kuò)充，則增加段的長度；否則按出錯(cuò)處理。68