存儲管理之段頁式管理

1、第四章 存儲管理之段頁式管理,4.2 分區(qū)存儲管理4.3 頁式存儲管理4.4 段式存儲管理4.5 段頁式存儲管理4.6 交換技術與覆蓋技術4.7 虛擬存儲,4.3 頁式存儲管理,為什么要引進分頁技術?分區(qū)式存儲管理：程序要求連續(xù)存放，會產(chǎn)生碎片問題。大程序進入時需要移動已在主存中的信息。分頁式存儲管理允許把一個作業(yè)存放到若干不相鄰接的分區(qū)中免去移動信息充分利用主存空間,,1. 用戶程序劃分,把用戶程序按邏輯頁劃分成大

2、小相等的部分，稱為頁。從0開始編制頁號，頁內(nèi)地址是相對于0編址,邏輯地址,用戶程序的劃分是由系統(tǒng)自動完成的，對用戶是透明的。一般，一頁的大小為2的整數(shù)次冪，因此，地址的高位部分為頁號，低位部分為頁內(nèi)地址,,,0,11,12,31,頁號P,頁內(nèi)位移量W,編號0~1048575,相對地址0~4095,,,,,邏輯地址：一維,內(nèi)存空間：,按頁的大小劃分為大小相等的區(qū)域，稱為內(nèi)存塊（物理頁面，頁框）,內(nèi)存分配：,以頁為單位進行分配，并按作業(yè)的頁

3、數(shù)多少來分配。邏輯上相鄰的頁，物理上不一定相鄰,,4.3 .3管理,1.頁表：系統(tǒng)為每個進程建立一個頁表，頁表給出邏輯頁號和具體內(nèi)存塊號相應的關系 頁表放在內(nèi)存，屬于進程的現(xiàn)場信息2.空塊管理——位示圖3.內(nèi)存的分配與回收,,,,,,,,,,,0,31,0/1,0/1,0/1,0/1,0/1,0,1,7,……,空閑塊數(shù),,……,空塊管理——位示圖,計算一個作業(yè)所需要的總塊數(shù)N查位示圖，看看是否還有N個空閑塊如果有足夠的空

4、閑塊，則頁表長度設為N，可填入PCB中；申請頁表區(qū)，把頁表始址填入PCB依次分配N個空閑塊，將塊號和頁號填入頁表修改位示圖,4.3.4 硬件支持,1．系統(tǒng)設置一對寄存器： 頁表始址寄存器 頁表長度寄存器2．相聯(lián)存儲器——快表 快表表項： 頁號；內(nèi)存塊號；標識位；淘汰位,1. 基本的地址變換機構,圖 4-12 分頁系統(tǒng)的地址變換機構,p’,頁表,,,地址越界,L,比較,P>=L,,,,,p,p’,,

5、,,.,.,.,快表,,,,,,,,,,b,+,,,,頁號p 頁內(nèi)地址d,,,,,,P’,d,物理地址,,,,,,,,頁表地址寄存器,頁表長度寄存器,邏輯地址,快表地址映射機制,存在的問題,當讀/寫數(shù)據(jù)時，必須訪問兩次主存。第一次按頁號讀出頁表中相應欄內(nèi)容的塊號第二次根據(jù)計算出來的絕對地址進行讀/寫解決方法：利用高速緩存,假定訪問主存時間為100毫微秒，訪問相聯(lián)存儲器時間為20毫微秒，相聯(lián)存儲器為32個單元時快表命中率可達

6、90%，按邏輯地址存取的平均時間為：（100＋20）×90%＋(100+100+20)×(1-90%)＝130毫微秒 比兩次訪問主存的時間100毫微秒×2+20＝220毫微秒下降了四成多。,4.3.5 頁式管理的優(yōu)缺點,優(yōu)點：解決了碎片問題 便于管理缺點：不易實現(xiàn)共享 不便于動態(tài)連接思考：頁的共享？頁的保護？,4.3.3 兩級和多級頁表,邏輯

7、地址空間(232~264)。頁表就變得非常大，要占用相當大的連續(xù)的內(nèi)存空間。 eg: 32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4 KB即212 B，則在每個進程頁表中的頁表項可達1兆個之多。解決辦法： 1、 采用離散分配方式。解決難以找到一塊連續(xù)的大內(nèi)存空間的問題； 2、只將當前需要的部分頁表項調(diào)入內(nèi)存， 其余的頁表項仍駐留在磁盤上，需要時再調(diào)入。,1. 兩級頁表(Two-Level Page Table),

8、邏輯地址結構可描述如下：,為了解決頁表需要連續(xù)存儲空間的問題，將頁表離散的放入內(nèi)存，然后建立一個頁表的頁表（連續(xù)存儲在外存中），用以標識頁表放在內(nèi)存中的位置。 同時邏輯地址也變成了如上的表示（一維）,圖 4-14 兩級頁表結構,圖 4-15 具有兩級頁表的地址變換機構,頁目錄地址,目錄位移,頁表位移,頁位移,虛擬地址,頁表地址,,,,,...,頁目錄（每進程一個）,,,,塊號,,...,頁表,代碼或數(shù)據(jù),,,,,..

9、.,內(nèi)存塊,,,,,,,,,,,,,,,二級頁表結構及地址映射,,+,,,,+,,4.4.1基本思想 一個程序的各個段離散存放 段式存儲管理 單個段的存儲基于可變分區(qū)存儲管理 實現(xiàn)，占據(jù)連續(xù)的內(nèi)存存儲空間 段頁式存儲管理 單個段的存儲基于頁式存儲管理實現(xiàn),,4.4分段式存儲管理,,0,116,N,,操作系統(tǒng),用戶程序劃分,按程序自身的邏輯關系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0

10、開始，每一段也從0開始編址，段內(nèi)地址是連續(xù)的,邏輯地址,內(nèi)存劃分 內(nèi)存空間被動態(tài)的劃分為若干個長度不相同的區(qū)域，這些區(qū)域被稱為物理段，每個物理段由起始地址和長度確定,內(nèi)存分配,以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機分割，需要多少分配多少），但各段之間可以不連續(xù)存放,4.4.2 管理,段表： 它記錄了段號，段的首（地）址和長度之間的關系 每一個程序設置一個段表，放在內(nèi)存 屬于進

11、程的現(xiàn)場信息,空閑塊管理：,記錄了空閑區(qū)起始地址和長度內(nèi)存的分配算法： 首先適配；最佳適配；最壞適配,4.4.3 硬件支持,系統(tǒng)設置一對寄存器段表始址寄存器：用于保存正在運行進程的段表的始址段表長度寄存器： 用于保存正在運行進程的段表的長度（例如上圖的段表長度為3）,Cl,,,,,,,,,Cb,+,,段號S 段內(nèi)地址d,,,,,,比較,比較,,b + d,,,,,,,,,,,段表,

12、,S>= Cl,,快表,,,,物理地址,,,,段表始址寄存器,段表長度寄存器,邏輯地址,,l,b,,,,,,.,.,.,,S,l,b,,,,,,地址越界,d>=1,d>=1,,地址映射及存儲保護機制,地址越界,地址越界,比較,L:為段長，注意與分頁的區(qū)別,介于內(nèi)存與寄存器之間的存儲機制，它又叫快表用途：保存正在運行進程的段表的子集（部分表項）特點：按內(nèi)容并行查找,相聯(lián)（聯(lián)想）存儲器（associative mem

13、ory） TLB（Translation lookaside buffers）,引入快表的作用： 為了提高地址映射速度,快表項目：段號；段始址；段長度；標識（狀態(tài)）位；訪問位（淘汰位）快表淘汰問題？（淘汰機制）,4.4.3 信息共享,圖 4-18 分頁系統(tǒng)中共享editor的示意圖,圖 4-19 分段系統(tǒng)中共享editor的示意圖,優(yōu)點： 便于動態(tài)申請內(nèi)存 管理和使用統(tǒng)一化

14、 便于共享 便于動態(tài)鏈接缺點：產(chǎn)生碎片思考：與可變分區(qū)存儲管理方案的相同點與不同點？,4.4.4段頁式存儲管理,1。產(chǎn)生背景及基本思想 背景：結合了二者優(yōu)點 克服了二者的缺點,基本思想：,用戶程序劃分：按段式劃分（對用戶來講，按段的邏輯關系進行劃分；對系統(tǒng)講，按頁劃分每一段）邏輯地址：內(nèi)存劃分：按頁式存儲管理方案內(nèi)存分配：以頁為單位進行分配,段頁式存儲方式的 管理,1.

15、段表：記錄了每一段的頁表始址和頁表長度2.頁表：記錄了邏輯頁號與內(nèi)存塊號的對應關系（每一段有一個，一個程序可能有多個頁表）3.空塊管理：同頁式管理4.分配：同頁式管理,圖 4-21 利用段表和頁表實現(xiàn)地址映射,2. 地址變換過程,圖 4-22 段頁式系統(tǒng)中的地址變換機構,,4.5 虛擬存儲技術,計算機系統(tǒng)資源管理策略： 內(nèi)存比較昂貴，同時資源有限； 外存較大，價格便宜； 以CPU時間和外

16、存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉換技術,1. 常規(guī)存儲器管理方式的特征,一次性。作業(yè)在運行時全部一次裝入。 (2) 駐留性。作業(yè)裝入內(nèi)存后，直至作業(yè)結束才完全撤出。,4.5.1 概述,1、問題的提出 程序大于內(nèi)存 程序暫時不執(zhí)行或運行完是否還要占用內(nèi)存 虛擬存儲器的基本思想是：程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存的大小，操作系統(tǒng)把程序當前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需

17、要時在內(nèi)存和磁盤之間動態(tài)交換。 虛擬存儲器支持多道程序設計技術,2、程序局部性原理 在一段時間內(nèi)一個程序的執(zhí)行往往呈現(xiàn)出高度的局部性，表現(xiàn)在時間與空間兩方面時間局部性： 一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行空間局部性： 若某一存儲單元被使用，則在一定時間內(nèi)，與該存儲單元相鄰的單元可能被使用,3、虛擬存儲技術,虛存：把內(nèi)存與外存有機的結合起來使用，從而得到一個容量很大的“內(nèi)存”，這就是虛存

18、 實現(xiàn)思想：當進程運行時，先將一部分程序裝入內(nèi)存，另一部分暫時留在外存，當要執(zhí)行的指令不在內(nèi)存時，由系統(tǒng)自動完成將它們從外存調(diào)入內(nèi)存工作 目的： 提高內(nèi)存利用率。,4.5.3 虛擬存儲器的特征,多次性一個作業(yè)分多次調(diào)入內(nèi)存執(zhí)行 對換性進程運行期間允許程序和數(shù)據(jù)換進、換出。3. 虛擬性 從邏輯上對內(nèi)存進行擴充，允許運行比內(nèi)存大的程序,4.6虛擬頁式存儲管理(請求分頁式),1、基本工

19、作原理 在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面；當內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面,2、頁表表項（有可能在外存上，故如下）,頁號、駐留位、內(nèi)存塊號、外存地址、訪問位、修改位駐留位（中斷位）：表示該頁是在內(nèi)存還是在外存訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）修改位：查看此頁是否在內(nèi)存中被修改

20、過,3、缺頁中斷（Page Fault）,在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，使作業(yè)繼續(xù)運行下去如果內(nèi)存中有空閑塊，則分配一頁，將新調(diào)入頁裝入內(nèi)存，并修改頁表中相應頁表項目的駐留位及相應的內(nèi)存塊號若此時內(nèi)存中沒有空閑塊，則要淘汰某頁，若該頁在內(nèi)存期間被修改過，則要將其寫回外存,與一般中斷機制的區(qū)別;(1)指令

21、執(zhí)行期間產(chǎn)生和處理中斷信號。 因為在執(zhí)行期間發(fā)現(xiàn)缺少某頁。（2）一條指令期間可能需要多次中斷才能完成任務。 因為一條指令需要的數(shù)據(jù)或指令可能跨越多個頁面。,3. 地址變換機構,圖 4-24 請求分頁中的地址變換過程,4.6.2 內(nèi)存分配策略和分配算法,1. 最小物理塊數(shù)的確定,保證進程正常運行所需的最小物理塊數(shù)。當系統(tǒng)為進程分配的物理塊數(shù)少于此值時，進程將無法運行。 （1）若是單地址指令且采用直接尋址方式，則所需

22、的最少物理塊數(shù)為2。一塊是用于存放指令的頁面，另一塊則是用于存放數(shù)據(jù)的頁面。 （2）如果該機器允許間接尋址時，則至少要求有三個物理塊。 （3） 對于某些功能較強的機器， 其指令長度可能是兩個或多于兩個字節(jié)，因而其指令本身有可能跨兩個頁面，且源地址和目標地址所涉及的區(qū)域也都可能跨兩個頁面。,2. 物理塊的分配策略,1) 固定分配局部置換(Fixed Allocation, Local Replacement) 為某

23、個進程分配固定頁面數(shù)，其間不能改變。需要置換時候只能置換自己的。 2) 可變分配全局置換(Variable Allocation,lobalReplacement) 先為進程一定的內(nèi)存頁面，如果在需要責從空閑塊中選擇相應的頁面分配給它。 3) 可變分配局部置換(Variable Allocation, Local Replacemen 初始分配同上，但是如果發(fā)生缺頁，必須置換自己

24、的頁面。如果缺頁率過高，os再為其分配一定的頁面數(shù)目。,3. 物理塊分配算法,1) 平均分配算法 這是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進程。 例如，當系統(tǒng)中有100個物理塊，有5個進程在運行時，每個進程可分得20個物理塊。這種方式貌似公平，但實際上是不公平的，因為它未考慮到各進程本身的大小。如有一個進程其大小為200頁，只分配給它20個塊，這樣，它必然會有很高的缺頁率；而另一個進程只有10頁，卻有10個物理

25、塊閑置未用。,2) 按比例分配算法 這是根據(jù)進程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個進程，每個進程的頁面數(shù)為Si，則系統(tǒng)中各進程頁面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進程所能分到的物理塊數(shù)為bi，將有：b應該取整，它必須大于最小物理塊數(shù)。,3) 考慮優(yōu)先權的分配算法 在實際應用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成， 應為它分配較多的內(nèi)存空間。通常采取的方法是把

26、內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據(jù)各進程的優(yōu)先權，適當?shù)卦黾悠湎鄳蓊~后，分配給各進程。在有的系統(tǒng)中，如重要的實時控制系統(tǒng)，則可能是完全按優(yōu)先權來為各進程分配其物理塊的。,4.6.3 調(diào)頁策略,1. 何時調(diào)入頁面,預調(diào)頁策略 一次調(diào)入進程的多個相鄰的多個頁面，這樣可以降低每次缺頁都要進行調(diào)入的開銷?？梢圆捎妙A測機制進行處理。 2) 請求調(diào)頁策略 發(fā)生缺頁時

27、才將缺頁調(diào)入內(nèi)存中。在目前的虛擬存儲中基本采用此種方法進行。,2. 從何處調(diào)入頁面,外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。對換區(qū)是采用連續(xù)分配方式，故對換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當發(fā)生缺頁請求時，系統(tǒng)應從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況： (1) 系統(tǒng)擁有足夠的對換區(qū)空間，這時可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。為此，在進程運行前， 便須將與該進程有關的文件，從

28、文件區(qū)拷貝到對換區(qū)。,(2) 系統(tǒng)缺少足夠的對換區(qū)空間，這時凡是不會被修改的文件，都直接從文件區(qū)調(diào)入；而當換出這些頁面時，由于它們未被修改而不必再將它們換出，以后再調(diào)入時，仍從文件區(qū)直接調(diào)入。但對于那些可能被修改的部分，在將它們換出時，便須調(diào)到對換區(qū)，以后需要時，再從對換區(qū)調(diào)入。 (3) UNIX方式。由于與進程有關的文件都放在文件區(qū)，故凡是未運行過的頁面，都應從文件區(qū)調(diào)入。而對于曾經(jīng)運行過但又被換出的頁面，由于是被放在

29、對換區(qū)，因此在下次調(diào)入時，應從對換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁面共享，因此， 某進程所請求的頁面有可能已被其它進程調(diào)入內(nèi)存，此時也就無須再從對換區(qū)調(diào)入。,3. 頁面調(diào)入過程 (1)向CPU發(fā)出缺頁中斷，保留CPU環(huán)境，分析中斷原因后， 轉入缺頁中斷處理程序。 (2)查找頁表，得到該頁在外存的物理塊后， 如果此時內(nèi)存能容納新頁，則啟動磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。 （3）如果內(nèi)存已滿，

30、則須先按照某種置換算法從內(nèi)存中選出一頁準備換出；,（4）檢查該頁是否被修改。 a.如果該頁未被修改過，可不必將該頁寫回磁盤； b.如果此頁已被修改， 則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存。 (5)修改頁表中的相應表項，置其存在位為“1”，并將此頁表項寫入快表中。 (6)在缺頁調(diào)入內(nèi)存后，利用修改后的頁表， 去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。,4.7

31、頁面淘汰算法,1、最佳頁面淘汰算法（OPT） 淘汰以后不再需要的或最遠的將來才會用到的頁面（理論上可行，實際上不可行） 2、最近最久未使用（LRU） 在最近的一段時間之內(nèi)一直沒有被訪問的頁面，我們可以認為該頁面在將來可能頁不會被訪問，所以淘汰掉。 即淘汰沒有使用的時間最長的頁。,3、先進先出頁面淘汰算法（FIFO） 選擇在內(nèi)存中駐留時間最長的頁并淘汰之 4、第二次機會

32、淘汰算法 (NUR) 按照先進先出算法選擇某一頁面，檢查其訪問位，如果為0，則淘汰該頁，如果為1，則給第二次機會，并將訪問位置0。 該算法要求在訪問某頁面時將其訪問位置1,1、OPT頁面置換算法 假定系統(tǒng)為某進程分配了三個物理塊， 并考慮有以下的頁面號引用串： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 進程運行時， 先將7，0，1

33、三個頁面裝入內(nèi)存。 以后， 當進程要訪問頁面2時， 將會產(chǎn)生缺頁中斷。此時OS根據(jù)最佳置換算法， 將選擇頁面7予以淘汰。,時刻,P,M,F,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,0,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,7,0,7,1,0,7,2,1,0,f,f,f,f,v,2,1,0,2,3,0,2,3,0,v,2,3,4,2,3,4,

34、2,f,V,V,f,3,4,2,3,0,f,2,3,0,v,2,3,0,v,2,1,0,f,2,1,0,v,2,1,0,V,2,1,0,v,7,1,0,f,7,1,0,v,7,1,0,v,缺頁率σ =9/20=45%,2. 先進先出(FIFO)頁面置換算法,圖 4-26 利用FIFO置換算法時的置換圖,時刻,P,M,F,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,0,7,0,1,2,

35、0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,7,0,7,1,0,7,2,1,0,f,f,f,f,v,2,1,0,3,2,1,0,3,2,f,4,0,3,2,4,0,3,f,f,f,f,2,4,0,3,2,f,0,3,2,v,0,3,2,v,1,0,3,f,2,1,0,f,2,1,0,v,2,1,0,v,7,2,1,f,0,7,2,f,1,0,7,f,缺頁率σ =15/20=75%,2. 先進先出(FIFO)頁面置換算

36、法,時刻,P,M,F,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,0,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,7,0,7,1,0,7,2,1,0,f,f,f,f,v,2,1,0,2,3,0,2,3,0,v,4,3,0,4,2,0,4,f,f,f,f,2,3,0,2,3,f,0,2,3,v,0,2,3,v,1,2,3,f,1,2,3,v,1,2,0

37、,f,1,2,0,v,1,7,0,f,1,7,0,v,1,7,0,v,缺頁率σ =12/20=60%,3. LRU(Least Recently Used)置換算法的描述,例：計算缺頁次數(shù),某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5,FIFO 4 3 2 1 4 3 5 4 3 2 1 5頁1 4 3 2 1 4 3 5 5 5 2

38、 1 1頁2 4 3 2 1 4 3 3 3 5 2 2頁3 4 3 2 1 4 4 4 3 5 5 x x x x x x x ? ? x x ?共缺頁中斷9次,LRU 4 3 2 1 4 3 5 4 3 2 1 5頁1 4 3 2 1 4 3 5 4

39、3 2 1 5頁2 4 3 2 1 4 3 5 4 3 2 1頁3 4 3 2 1 4 3 5 4 3 2 x x x x x x x ? ? x x x共缺頁中斷10次,OPT 4 3 2 1 4 3 5 4 3 2 1 5頁1 4 3 2 1 1 1

40、 5 5 5 2 1 1頁2 4 3 3 3 3 3 3 3 5 5 5頁3 4 4 4 4 4 4 4 4 4 4 x x x x ? ? x ? ? x x ? 共缺頁中斷7次,最佳頁面算法（OPT）,LRU置換算法的硬件支持,1) 寄存器 為了記錄某進程在內(nèi)存中各頁的使用情況，

41、須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為,R=Rn-1Rn-2Rn-3 … R2R1R0,進程訪問某物理塊時，要將相應的寄存器r位置為1。定時信號將每隔一段時間將寄存器右移1位，將n位寄存器看作一個整數(shù)，那么，具有最小數(shù)值的寄存器所對應的頁面，就是最近最久未使用頁面。 如下圖所示：,圖 4-28 某進程具有8個頁面時的LRU訪問情況,2) 棧,圖 4-29 用棧保存當前使用頁面時棧的變化情況,保存當前使用的各個頁面的頁

42、面號，當進程訪問某個頁面時，便將該頁面的頁面號從棧中取出，將其壓入棧頂。因此棧頂永遠是最近使用的頁面，而棧底則是最近最久沒有被訪問的頁面。,4 、 Clock置換算法 （NUR）,1. 簡單的Clock置換算法,圖 4-30 簡單Clock置換算法的流程和示例,注：頁面被訪問時，其訪問位被置為1,2. 改進型Clock置換算法,由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 表示該頁最近既未

43、被訪問， 又未被修改， 是最佳淘汰頁。 2類(A=0, M=1)： 表示該頁最近未被訪問， 但已被修改， 并不是很好的淘汰頁。 3類(A=1, M=0)： 最近已被訪問， 但未被修改， 該頁有可能再被訪問。 4類(A=1, M=1): 最近已被訪問且被修改， 該頁可能再被訪問。,(1) 從指針所指示的當前位置開始， 掃描循環(huán)隊列， 尋找A=0且M=0的第一類頁面， 將所遇到的第一個頁面作為

44、所選中的淘汰頁。 在第一次掃描期間不改變訪問位A。 (2) 如果第一步失敗，即查找一周后未遇到第一類頁面， 則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。,(3) 如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復0。 然后重復第一步，如果仍失敗，必要時再重復第二步，此時就一定能找到被淘汰的頁。,

45、4.7.4 其它置換算法,最少使用(LFU： Least Frequently Used)置換算法2. 頁面緩沖算法(PBA： Page Buffering Algorithm) ,,4.8 虛擬段式存儲管理（請求分段式）,1、段表機制 增加：存在位（在/不在內(nèi)存，是否可共享），存取方式位（讀，寫，執(zhí)行），修改位（是否修改過，能否移動），增補位（固定長/可擴充 ）， 訪問字段a:紀錄該段被訪問的頻繁度； 外

46、存始址：本段在外存中的起始地址，即起始盤塊號。,2、越界中斷處理 進程在執(zhí)行過程中，有時需要擴大分段，如數(shù)據(jù)段。由于要訪問的地址超出原有的段長，所以發(fā)越界中斷。操作系統(tǒng)處理中斷時 ，首先判斷該段的“擴充位”，如可擴充，則增加段的長度；否則按出錯處理,3、缺段中斷處理 檢查內(nèi)存中是否有足夠的空閑空間 ①若有，則裝入該段，修改有關數(shù)據(jù)結構，中斷返回 ②若沒有，檢查內(nèi)存中空閑區(qū)的總和是否滿足要求，是則應采

47、用緊縮技術，轉① ；否則，淘汰一（些）段，轉①,2. 缺段中斷機構,圖 4-31 請求分段系統(tǒng)中的中斷處理過程,分段式虛擬存儲管理,3. 地址變換機構,圖 4-32 請求分段系統(tǒng)的地址變換過程,4.8.2 分段的共享與保護,1. 共享段表,圖 4-33 共享段表項,另外單獨設置一個共享段表，所有共享段都在里面有一個表項。記錄項目如下：,共享進程計數(shù)：記錄有多少個進程在使用該段?？刂拼嫒∽侄危涸O置使用該段的權限，“寫”、“讀”等段號：

48、允許不同的進程使用不同的段號來訪問相同的段。,2. 共享段的分配與回收,1) 共享段的分配 在為共享段分配內(nèi)存時，對第一個請求使用該共享段的進程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時將該區(qū)的始址填入請求進程的段表的相應項中，還須在共享段表中增加一表項，填寫有關數(shù)據(jù)，把count置為1；之后，當又有其它進程需要調(diào)用該共享段時，由于該共享段已被調(diào)入內(nèi)存，故此時無須再為該段分配內(nèi)存，而只需在調(diào)用進程的段表中，

49、增加一表項，填寫該共享段的物理地址；在共享段的段表中，填上調(diào)用進程的進程名、存取控制等，再執(zhí)行count∶=count+1操作，以表明有兩個進程共享該段。,2) 共享段的回收 當共享此段的某進程不再需要該段時，應將該段釋放， 包括撤在該進程段表中共享段所對應的表項，以及執(zhí)行count∶=count-1操作。若結果為0，則須由系統(tǒng)回收該共享段的物理內(nèi)存，以及取消在共享段表中該段所對應的表項， 表明此時已沒有進程使用該段

50、；否則(減1結果不為0)， 則只是取消調(diào)用者進程在共享段表中的有關記錄。,3. 分段保護,越界檢查 ：檢查段號與段表長度，段內(nèi)地址與段長的比較。2) 存取控制檢查 ：設定存取權限只讀 (2) 只執(zhí)行 (3) 讀/寫 3) 環(huán)保護機構 劃分程序優(yōu)先級，內(nèi)環(huán)優(yōu)先級高，外環(huán)優(yōu)先級第，編號由內(nèi)向外編號。調(diào)用和訪問方式如下圖所示:,圖 4-34 環(huán)保護機構,,,2、分區(qū)式存儲管理 a. 固定式分區(qū)管理；