【正文】 間存放將要裝入的程序以及將要調(diào)入的頁或段。只需程序的一部分在內(nèi)存就可執(zhí)行　請求分頁存儲(chǔ)管理方式n在實(shí)存頁式管理的基礎(chǔ)上建立的一種管理機(jī)制。其基本思想是作業(yè)運(yùn)行的過程中，頁面只有需要時(shí)才請求被換入內(nèi)存，而暫不運(yùn)行的頁面置換到外存，從而減少對換時(shí)間和所需內(nèi)存數(shù)量，增加多道程序的道數(shù)。換入和換出是以頁面為基本單位。 需要解決的問題系統(tǒng)需要解決下面三個(gè)問題：n系統(tǒng)如何獲知進(jìn)程當(dāng)前所需頁面不在主存。n當(dāng)發(fā)現(xiàn)缺頁時(shí)，如何把所缺頁面調(diào)入主存。n當(dāng)主存中沒有空閑的頁框時(shí)，為了要接受一個(gè)新頁，需要 把老的一頁淘汰出去，根據(jù)什么策略選擇欲淘汰的頁面?！≌埱蠓猪撝械挠布С謓為了實(shí)現(xiàn)請求分頁，系統(tǒng)需要提供一定的硬件支持：n1頁表機(jī)制n2缺頁中斷機(jī)構(gòu)n3地址變換機(jī)構(gòu) n狀態(tài)位 P:用于指示該頁是否已調(diào)入內(nèi)存， 供程序訪問時(shí)參考 ；n訪問字段 A:用于記錄本頁在一段時(shí)間內(nèi) 被訪問的次數(shù) ，或記錄本頁最近已有多長時(shí)間未被訪問，供選擇 換出頁面時(shí)參考 ；n修改位 M:表示該頁在調(diào)入內(nèi)存后是否被修改過，供 置換頁面時(shí)參考；n外存地址 :用于指示該頁 在外存上的地址 ， 供調(diào)入頁時(shí)使用。頁號 物理塊號 狀態(tài)位 P 訪問字段 A 修改位 M 外存地址查頁表時(shí)，當(dāng)存在位指示該頁不在主存時(shí)，則引起一個(gè)缺頁中斷發(fā)生，相應(yīng)的中斷處理程序把控制轉(zhuǎn)向缺頁中斷子程序。執(zhí)行此子程序，即把所缺頁面裝入主存。 如果內(nèi)存中有空閑塊，則分配一頁， 若此時(shí)內(nèi)存中沒有空閑塊，則要淘汰某頁。 然后處理機(jī)重新執(zhí)行缺頁時(shí)打斷的指令。這時(shí)，就將順利形成物理地址。它與一般的中斷相比，主要區(qū)別表現(xiàn)在： 1)在指令執(zhí)行期間 產(chǎn)生和處理中斷信號； 2)一條指令在執(zhí)行期間，可能產(chǎn)生 多次缺頁中斷 (為什么？ )B:A:指令TO BCopy A頁面654321按 邏輯地址查快表該頁在快表中有 登記 ?形成物理地址繼續(xù)執(zhí)行指令是發(fā)缺頁 中斷查頁表否該頁在 主存中形成物理地址將該頁 登記入快表是保護(hù)現(xiàn)場主存有空閑塊 ?裝入所 需要的頁調(diào)整頁表和主存分配表恢復(fù)現(xiàn)場重啟被中斷的指令是選擇調(diào)出的頁該頁被 修改 ?將該頁寫回輔存 相應(yīng)位置否否 是缺頁 中斷處理流程硬件處理操作系統(tǒng)處理圖：請求式分頁存儲(chǔ)管理示意圖　 3．地址變換機(jī)構(gòu) 存儲(chǔ)保護(hù)檢查：頁號 頁表長度？是，越界中斷；否則 2； 查快表：找到，修改訪問位，對于寫操作置修改位，并形成物理地址訪問； 若未找到，查頁表狀態(tài)位：在主存，將表目寫入快表；否則，缺頁中斷。內(nèi)存分配策略和分配算法n虛存請求分頁管理在為進(jìn)程分配內(nèi)存時(shí)，必須考慮三個(gè)問題： n第一，確定保證進(jìn)程正常運(yùn)行所需要的最小的物理塊數(shù)； n第二，物理塊的分配策略； n第三，確定采用何種分配算法來進(jìn)行頁面分配1．最小物理塊數(shù)的確定n保證進(jìn)程正常運(yùn)行所需最小的物理塊數(shù)，與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，其值取決于指令的格式、功能和尋址方式。n采用直接尋址：最小物理塊數(shù)為 2；（存放指令的頁和存放數(shù)據(jù)的頁） n采用間接尋址：最小物理塊數(shù)為 3；　 2．物理塊的分配策略1)固定分配局部置換n根據(jù)進(jìn)程的類型，為每個(gè)進(jìn)程分配固定數(shù)目N的內(nèi)存頁框，整個(gè)運(yùn)行期間不再改變。 n采用該策略時(shí)，如果進(jìn)程運(yùn)行過程中出現(xiàn)缺頁，則只能從該進(jìn)程的 N個(gè)頁面中選出一頁換出，然后再調(diào)入一頁。 n這種策略的難點(diǎn)在于，為每個(gè)進(jìn)程分配的頁框數(shù) N難以確定。太少會(huì)造成頻繁的缺頁中斷，降低系統(tǒng)吞吐量，太多則使內(nèi)存中駐留的進(jìn)程數(shù)減少，可能造成 CPU空閑或其它資源空閑，在實(shí)現(xiàn)進(jìn)程交換時(shí)會(huì)花費(fèi)更多的時(shí)間。2)可變分配全局置換n先為系統(tǒng)中的每個(gè)進(jìn)程分配一定數(shù)目的內(nèi)存頁框，操作系統(tǒng)自身也保持一個(gè)空閑物理塊隊(duì)列； n當(dāng)某進(jìn)程發(fā)生缺頁中斷時(shí)，由系統(tǒng)從空閑物理塊隊(duì)列中取出一塊分配給該進(jìn)程； n當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，操作系統(tǒng)從整個(gè)內(nèi)存空間選擇一頁調(diào)出，該頁可能是系統(tǒng)中任一進(jìn)程的頁面。 n這種策略實(shí)現(xiàn)容易，但可能使整個(gè)系統(tǒng)產(chǎn)生抖動(dòng)現(xiàn)象。3)可變分配局部置換n先為每個(gè)進(jìn)程分配一定數(shù)目的內(nèi)存頁框，但當(dāng)進(jìn)程缺頁時(shí)，只允許從該進(jìn)程的頁面中選出一頁換出，而不影響其它進(jìn)程的運(yùn)行。 n若進(jìn)程缺頁中斷頻繁，則系統(tǒng)須為該進(jìn)程追加分配若干物理塊，直至進(jìn)程的缺頁率減低到適當(dāng)程度為止，反之，若一個(gè)進(jìn)程的缺頁率特別低，則可在不引起其缺頁率明顯增加的情況下，適當(dāng)減少分配給該進(jìn)程的物理塊。3．物理塊分配算法n1)平均分配算法n　　這是將系統(tǒng)中所有可供分配的物理塊平均分配給各個(gè)進(jìn)程。2)按比例分配算法n　　這是根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有 n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)為 Si，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為： n　　又假定系統(tǒng)中可用的物理塊總數(shù)為 m，則每個(gè)進(jìn)程所能分到的物理塊數(shù)為 bi，將有： 3)考慮優(yōu)先權(quán)的分配算法n　　在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(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)來為各進(jìn)程分配其物理塊的?！≌{(diào)頁策略1．調(diào)入頁面的時(shí)機(jī)1)預(yù)調(diào)頁策略如果進(jìn)程的許多頁是存放在外存的一個(gè)連續(xù)區(qū)域中，則一次調(diào)入若干個(gè)相鄰的頁，會(huì)比一次調(diào)入一頁更高效些。但如果調(diào)入的一批頁面中的大多數(shù)都未被訪問，則又是低效的?？刹捎靡环N以預(yù)測為基礎(chǔ)的預(yù)調(diào)頁策略，將那些預(yù)計(jì)在不久之后便會(huì)被訪問的頁面預(yù)先調(diào)入內(nèi)存。1．調(diào)入頁面的時(shí)機(jī)n2)請求調(diào)頁策略n當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，便立即提出請求，由 OS將其所需頁面調(diào)入內(nèi)存。由請求調(diào)頁策略所確定調(diào)入的頁，是一定會(huì)被訪問的，再加之請求調(diào)頁策略比較易于實(shí)現(xiàn)，故在目前的虛擬存儲(chǔ)器中大多采用此策略?！?2．確定從何處調(diào)入頁面n在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。通常，由于對換區(qū)是采用連續(xù)分配方式，而文件區(qū)是采用離散分配方式，故對換區(qū)的磁盤 I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁請求時(shí)，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況：n　　 2．確定從何處調(diào)入頁面n第一種，若系統(tǒng)擁有足夠的對換區(qū)空間，則可全部從對換區(qū)調(diào)入所需頁面。 n第二種，如果系統(tǒng)缺少足夠的對換區(qū)空間，對于不被修改的文件，則直接從文件區(qū)調(diào)入；對于可能被修改的文件，則從交換區(qū)調(diào)入，換出時(shí)也換出到交換區(qū)； n第三種， UNIX系統(tǒng)中，凡未運(yùn)行過的頁面都從文件區(qū)調(diào)入；對曾經(jīng)運(yùn)行過而又被換出的頁面，則從交換區(qū)調(diào)入； 3．頁面調(diào)入過程每當(dāng)程序所要訪問的頁面未在內(nèi)存時(shí)，便向 CPU發(fā)出一缺頁中斷，中斷處理程序首先保留 CPU環(huán)境，分析中斷原因后轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后，如果此時(shí)內(nèi)存能容納新頁，則啟動(dòng)磁盤 I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出；然后再把所缺的頁調(diào)入內(nèi)存，并修改頁表中的相應(yīng)表項(xiàng)，置其存在位為 “1”，并將此頁表項(xiàng)寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個(gè)頁面的調(diào)入過程對用戶是透明的。 　頁面置換算法當(dāng)要放一頁面到全滿的主存塊時(shí)，系統(tǒng)需淘汰一頁。用來選取 淘汰哪一頁的規(guī)則，叫置換算法。n最佳置換算法 n先進(jìn)先出置換算法 n最近最久未用置換算法nClock置換算法 最佳置換算法是由 Belady于 1966年提出的一種理論上的算法。 其所選擇的被淘汰頁面，將是以后永不使用的， 或許是在最長 (未來 )時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法， 通?？杀ＷC獲得最低的缺頁率。n假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊， 并考慮有以下的頁面號引用串： ?n7， 0， 1， 2， 0， 3， 0， 4， 2， 3， 0，3， 2， 1， 2， 0， 1， 7， 0， 1?n進(jìn)程運(yùn)行時(shí)， 先將 7， 0， 1三個(gè)頁面裝入內(nèi)存。 以后， 當(dāng)進(jìn)程要訪問頁面 2時(shí)， 將會(huì)產(chǎn)生缺頁中斷。此時(shí) OS根據(jù)最佳置換算法， 將選擇頁面 7予以淘汰。 引用率7 07 70170122010 32030 42432 3 0 3 2 12012 0 1 77010 1頁框 (物理塊）203％％＝缺頁率為＝ 45100209 2．先進(jìn)先出 (FIFO)頁面置換算法n這種算法的基本思想是：總是先淘汰那些駐留在內(nèi)存時(shí)間最長的頁面，即先進(jìn)入內(nèi)存的頁面先被置換掉。理由是：最先進(jìn)入內(nèi)存的頁面不再被訪問的可能性最大 。n這里，我們?nèi)杂蒙厦娴睦?，但采用FIFO算法進(jìn)行頁面置換 2. 先進(jìn)先出 (FIFO)頁面置換算法引用率7 07 70170122010 32310 44302 3 0 3 2 10132 0 1 77020 1頁框230420423023012712701％％＝缺頁率為＝ 751002022 采用 FIFO算法還會(huì)產(chǎn)生一種奇怪現(xiàn)象，直觀上，分配給作業(yè)的 物理塊越多 ，進(jìn)程執(zhí)行時(shí)發(fā)生的 缺頁率就越小 ，但對 FIFO算法這個(gè)結(jié)論并不是絕對的。在某些情況下，當(dāng)分配的 物理塊數(shù)增多反而導(dǎo)致更多的缺頁中斷 ，這種現(xiàn)象稱為 FIFO異?，F(xiàn)象 或稱 Belady現(xiàn)象 。（根本原因就是沒有考慮程序執(zhí)行的動(dòng)態(tài)特征）某進(jìn)程共有 5頁 ,依次訪問頁面的序列為:1,2,3,4,1,2,5,1,2,3,4,5。當(dāng)系統(tǒng)為該進(jìn)程分配的物理塊數(shù) M=3時(shí) ,缺頁中斷次數(shù)為 9次 ,其缺頁中斷率為 9/12=75%。但是如果為進(jìn)程分配的物理塊數(shù) M=4時(shí) ,缺頁中斷次數(shù)為 10次 ,其缺頁中斷率為10/12=%。1 2 3 4 1 2 5 5 5 3 4 41 2 3 4 1 2 2 2 5 3 31 2 3 4 1 1 1 2 5 51 2 3 4 4 4 5 1 2 3 4 51 2 3 3 3 4 5 1 2 3 41 2 2 2 3 4 5 1 2 31 1 1 2 3 4 5 1 21 2 3 4 1 2 5 1 2 3 4 5+ + + + + + + + ++ + + + + + + + + +(“+”表示產(chǎn)生一次缺頁中斷 )　最近最久未使用置換算法n當(dāng)需要淘汰某一頁時(shí)，算法選擇離當(dāng)前時(shí)間 最近 的一段時(shí)間內(nèi) 最久沒有使用過的頁先淘汰。其理由是， 如果 某頁被訪問了，則它可能馬上還要被訪問， 反之 如果該頁很長時(shí)間未被訪問，則它在最近一段時(shí)間內(nèi)也不會(huì)被訪問。最近最久未使用置換算法引用率7 07 70170122010 32030 44032 3 0 3 2 11322 0 1 77010 1頁框402432032102％％＝缺頁率為＝ 6010020222． LRU置換算法的硬件支持nLRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁面各有多少時(shí)間未被進(jìn)程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類硬件之一的支持：寄存器或棧。1)寄存器n為了記錄頁面 自上次被訪問以來所經(jīng)過的時(shí)間 ,需要在頁表中增加一個(gè) 移位寄存器,進(jìn)程訪問某物理塊時(shí)，要將相應(yīng)寄存器的最高位置成 1。每隔一定時(shí)間 將寄存器右移一位。具有最小數(shù)值的寄存器所對應(yīng)的頁面，就是最近最久未使用的頁面。某進(jìn)程具有 8個(gè)頁面時(shí)的 LRU訪問情況1)寄存器 R 實(shí) 頁 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 2)棧n可利用一個(gè)特殊的棧來保存當(dāng)前使用的各個(gè)頁面的頁面號。每當(dāng)進(jìn)程訪問某頁面時(shí)，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。假定現(xiàn)有一進(jìn)程所訪問的頁面的頁面號序列為：4， 7， 0， 7， 1， 0， 1， 2， 1， 2， 62)棧用棧保存當(dāng)前使用頁面時(shí)棧的變化情況　 Clock置換算法要實(shí)現(xiàn) LRU算法，需要付出 很大的系統(tǒng)開銷 。在實(shí)際系統(tǒng)中，經(jīng)常采用 LRU的近似算法。 Clock算法就是用得較多的一種 LRU近似算法1．簡單的 Clock置換算法n這種算法，只要在頁表中設(shè)一個(gè) “引用位 ”，當(dāng)頁表中的某一頁被訪問時(shí)，該位由硬件自動(dòng)置 1，并由頁面管理軟件周期性把所有引用位置 0。這樣，在一個(gè)時(shí)間周期 T內(nèi)，某些被訪問過的頁面其引用位為 1，而未被訪問過的頁面其引用位為 0。n根據(jù)引用位的狀態(tài)來判別各頁面最近的使用情況。當(dāng)需要置換一頁面時(shí)，選擇其引用位為 0的頁，如下圖所示的算法。1．簡單的 Clock置換算法 簡單 Clock置換算法的流程和示例 入口查尋指針前進(jìn)一步，指向下一個(gè)表目頁面訪問位＝ 0?選擇該頁面淘汰是返回置頁面訪問位＝ “ 0”否塊號 頁號 訪問位 指針012 4 034 2 156 5 07 1 1替