存儲(chǔ)管理之段頁(yè)式管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33、三個(gè)頁(yè)面裝入內(nèi)存。 以后， 當(dāng)進(jìn)程要訪問(wèn)頁(yè)面2時(shí)， 將會(huì)產(chǎn)生缺頁(yè)中斷。此時(shí)OS根據(jù)最佳置換算法， 將選擇頁(yè)面7予以淘汰。,時(shí)刻,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,缺頁(yè)率σ =9/20=45%,2. 先進(jìn)先出(FIFO)頁(yè)面置換算法,圖 4-26 利用FIFO置換算法時(shí)的置換圖,時(shí)刻,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,缺頁(yè)率σ =15/20=75%,2. 先進(jìn)先出(FIFO)頁(yè)面置換算

36、法,時(shí)刻,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,缺頁(yè)率σ =12/20=60%,3. LRU(Least Recently Used)置換算法的描述,例：計(jì)算缺頁(yè)次數(shù),某程序在內(nèi)存中分配三個(gè)頁(yè)面，初始為空，頁(yè)面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5,FIFO 4 3 2 1 4 3 5 4 3 2 1 5頁(yè)1 4 3 2 1 4 3 5 5 5 2

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

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

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

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

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

43、被訪問(wèn)， 又未被修改， 是最佳淘汰頁(yè)。 2類(lèi)(A=0, M=1)： 表示該頁(yè)最近未被訪問(wèn)， 但已被修改， 并不是很好的淘汰頁(yè)。 3類(lèi)(A=1, M=0)： 最近已被訪問(wèn)， 但未被修改， 該頁(yè)有可能再被訪問(wèn)。 4類(lèi)(A=1, M=1): 最近已被訪問(wèn)且被修改， 該頁(yè)可能再被訪問(wèn)。,(1) 從指針?biāo)甘镜漠?dāng)前位置開(kāi)始， 掃描循環(huán)隊(duì)列， 尋找A=0且M=0的第一類(lèi)頁(yè)面， 將所遇到的第一個(gè)頁(yè)面作為

44、所選中的淘汰頁(yè)。 在第一次掃描期間不改變?cè)L問(wèn)位A。 (2) 如果第一步失敗，即查找一周后未遇到第一類(lèi)頁(yè)面， 則開(kāi)始第二輪掃描，尋找A=0且M=1的第二類(lèi)頁(yè)面，將所遇到的第一個(gè)這類(lèi)頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間，將所有掃描過(guò)的頁(yè)面的訪問(wèn)位都置0。,(3) 如果第二步也失敗，亦即未找到第二類(lèi)頁(yè)面，則將指針?lè)祷氐介_(kāi)始的位置，并將所有的訪問(wèn)位復(fù)0。 然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁(yè)。,

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

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

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

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

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

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