【正文】 1．簡單的 Clock置換算法 簡單 Clock置換算法的流程和示例 入口查尋指針前進一步，指向下一個表目頁面訪問位＝ 0?選擇該頁面淘汰是返回置頁面訪問位＝ “ 0”否塊號 頁號 訪問位 指針012 4 034 2 156 5 07 1 1替換。n根據(jù)引用位的狀態(tài)來判別各頁面最近的使用情況。 Clock算法就是用得較多的一種 LRU近似算法1．簡單的 Clock置換算法n這種算法，只要在頁表中設一個 “引用位 ”，當頁表中的某一頁被訪問時，該位由硬件自動置 1，并由頁面管理軟件周期性把所有引用位置 0。棧用棧保存當前使用頁面時棧的變化情況　 Clock置換算法要實現(xiàn) LRU算法，需要付出 很大的系統(tǒng)開銷 。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。棧n可利用一個特殊的棧來保存當前使用的各個頁面的頁面號。1)具有最小數(shù)值的寄存器所對應的頁面，就是最近最久未使用的頁面。每隔一定時間 1)為了了解一個進程在內(nèi)存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類硬件之一的支持：寄存器或棧。其理由是， 如果 某頁被訪問了，則它可能馬上還要被訪問， 反之 如果該頁很長時間未被訪問，則它在最近一段時間內(nèi)也不會被訪問。但是如果為進程分配的物理塊數(shù) M=4時 ,缺頁中斷次數(shù)為 10次 ,其缺頁中斷率為10/12=%。（根本原因就是沒有考慮程序執(zhí)行的動態(tài)特征）某進程共有 5頁 ,依次訪問頁面的序列為:1,2,3,4,1,2,5,1,2,3,4,5。n這里，我們?nèi)杂蒙厦娴睦?，但采用FIFO算法進行頁面置換 2. 先進先出 (FIFO)頁面置換算法引用率7 07 70170122010 32310 44302 3 0 3 2 10132 0 1 77020 1頁框230420423023012712701％％＝缺頁率為＝ 751002022 采用 FIFO算法還會產(chǎn)生一種奇怪現(xiàn)象，直觀上，分配給作業(yè)的 物理塊越多 ，進程執(zhí)行時發(fā)生的 缺頁率就越小 ，但對 FIFO算法這個結(jié)論并不是絕對的。引用率7 07 70170122010 32030 42432 3 0 3 2 12012 0 1 77010 1頁框 (物理塊）203％％＝缺頁率為＝ 45100209 2．先進先出 (FIFO)頁面置換算法n這種算法的基本思想是：總是先淘汰那些駐留在內(nèi)存時間最長的頁面，即先進入內(nèi)存的頁面先被置換掉。將選擇頁面 7予以淘汰。將會產(chǎn)生缺頁中斷。以后， 先將 7， 0， 1三個頁面裝入內(nèi)存。假定系統(tǒng)為某進程分配了三個物理塊， 采用最佳置換算法， 通?？杀ＷC獲得最低的缺頁率。最佳置換算法是由 Belady于 1966年提出的一種理論上的算法。用來選取 淘汰哪一頁的規(guī)則，叫置換算法。 在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。該程序通過查找頁表，得到該頁在外存的物理塊后，如果此時內(nèi)存能容納新頁，則啟動磁盤 I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。n第三種， UNIX系統(tǒng)中，凡未運行過的頁面都從文件區(qū)調(diào)入；對曾經(jīng)運行過而又被換出的頁面，則從交換區(qū)調(diào)入； 通常，由于對換區(qū)是采用連續(xù)分配方式，而文件區(qū)是采用離散分配方式，故對換區(qū)的磁盤 I/O速度比文件區(qū)的高。由請求調(diào)頁策略所確定調(diào)入的頁，是一定會被訪問的，再加之請求調(diào)頁策略比較易于實現(xiàn)，故在目前的虛擬存儲器中大多采用此策略。1．調(diào)入頁面的時機n2)但如果調(diào)入的一批頁面中的大多數(shù)都未被訪問，則又是低效的。　調(diào)頁策略1．調(diào)入頁面的時機1)通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據(jù)各進程的優(yōu)先權，適當?shù)卦黾悠湎鄳蓊~后，分配給各進程。3)如果系統(tǒng)中共有 n個進程，每個進程的頁面數(shù)為 Si，則系統(tǒng)中各進程頁面數(shù)的總和為： 2)3．物理塊分配算法n1) 3) 當某進程發(fā)生缺頁中斷時，由系統(tǒng)從空閑物理塊隊列中取出一塊分配給該進程； n2)n這種策略的難點在于，為每個進程分配的頁框數(shù) N難以確定。n采用該策略時，如果進程運行過程中出現(xiàn)缺頁，則只能從該進程的 N個頁面中選出一頁換出，然后再調(diào)入一頁。固定分配局部置換n根據(jù)進程的類型，為每個進程分配固定數(shù)目N的內(nèi)存頁框，整個運行期間不再改變。n采用直接尋址：最小物理塊數(shù)為 2；（存放指令的頁和存放數(shù)據(jù)的頁） 第二，物理塊的分配策略； n內(nèi)存分配策略和分配算法n虛存請求分頁管理在為進程分配內(nèi)存時，必須考慮三個問題： 若未找到，查頁表狀態(tài)位：在主存，將表目寫入快表；否則，缺頁中斷。它與一般的中斷相比，主要區(qū)別表現(xiàn)在： 1)在指令執(zhí)行期間 產(chǎn)生和處理中斷信號； 2)一條指令在執(zhí)行期間，可能產(chǎn)生 多次缺頁中斷 (為什么？ )B:A:指令TO BCopy A頁面654321按 邏輯地址查快表該頁在快表中有 登記 ?形成物理地址繼續(xù)執(zhí)行指令是發(fā)缺頁 中斷查頁表否該頁在 主存中形成物理地址將該頁 登記入快表是保護現(xiàn)場主存有空閑塊 ?裝入所 需要的頁調(diào)整頁表和主存分配表恢復現(xiàn)場重啟被中斷的指令是選擇調(diào)出的頁該頁被 修改 ?將該頁寫回輔存 相應位置否否 是缺頁 中斷處理流程硬件處理操作系統(tǒng)處理圖：請求式分頁存儲管理示意圖　 3．地址變換機構 存儲保護檢查：頁號 頁表長度？是，越界中斷；否則 2； 然后處理機重新執(zhí)行缺頁時打斷的指令。 如果內(nèi)存中有空閑塊，則分配一頁， 頁號 物理塊號 狀態(tài)位 P 訪問字段 A 修改位 M 外存地址查頁表時，當存在位指示該頁不在主存時，則引起一個缺頁中斷發(fā)生，相應的中斷處理程序把控制轉(zhuǎn)向缺頁中斷子程序?！≌埱蠓猪撝械挠布С謓為了實現(xiàn)請求分頁，系統(tǒng)需要提供一定的硬件支持：n1頁表機制n2缺頁中斷機構n3地址變換機構 n當發(fā)現(xiàn)缺頁時，如何把所缺頁面調(diào)入主存。換入和換出是以頁面為基本單位。只需程序的一部分在內(nèi)存就可執(zhí)行　請求分頁存儲管理方式n在實存頁式管理的基礎上建立的一種管理機制。 n主存＋輔存 =總的虛擬存儲容量，但是虛擬存儲器的最大容量受限于系統(tǒng)的有效地址長度 ,每個作業(yè)不是全部一次性地裝入內(nèi)存，將當前不運行的程序、數(shù)據(jù)調(diào)至外存盤交換區(qū)；虛擬性：、虛擬性： 虛存是從邏輯上擴充內(nèi)存容量，使用戶編程所用到的地址空間遠大于實際內(nèi)存容量。一個作業(yè)分成多次調(diào)入主存運行； 　虛擬存儲器的特征多次性：、多次性：n(3)n(2)一般需要下列支持：n(1)置換是以段為單位進行的。它允許只裝入少數(shù)段 (而非所有的段 )的用戶程序和數(shù)據(jù)，即可啟動運行。實現(xiàn)請求分頁的軟件這里包括有用于實現(xiàn)請求調(diào)頁的軟件和實現(xiàn)頁面置換的軟件。地址變換機構 。請求分頁的頁表機制 ；② 1．分頁請求系統(tǒng)1)以后，再通過調(diào)頁功能及頁面置換功能，陸續(xù)地把即將要運行的頁面調(diào)入內(nèi)存，同時把暫不運行的頁面換出到外存上。n易于開發(fā)： 與覆蓋技術比較，不必影響編程時的程序結(jié)構　虛擬存儲器的實現(xiàn)方法n1．分頁請求系統(tǒng)n　　這是在分頁系統(tǒng)的基礎上，增加了 請求調(diào)頁 功能和 頁面置換 功能所形成的頁式虛擬存儲系統(tǒng)。memory)引入虛擬存儲技術的好處n大程序： 可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序； 3．虛擬存儲器的定義n對用戶：指令地址部分所限定的比實存大得多的地址實間。3．虛擬存儲器的定義虛擬存儲器 是指具有 請求調(diào)入功能 和 置換功能 ，能從邏輯上對內(nèi)存進行擴充的一種存儲器系統(tǒng)。② 空間的局限性 ，一旦程序訪問了某個存儲單元，在不久以后，其附近的存儲單元也被訪問，即程序在一段時間內(nèi)所訪問的地址可能集中在一定的范圍內(nèi)。2．局部性原理① 時間的局限性 ，如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；某個數(shù)據(jù)被訪問，則不久以后該數(shù)據(jù)可能被再次訪問。2．局部性原理局部性原理 ：程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，即在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區(qū)域。 駐留性。 要求將作業(yè)全部裝入內(nèi)存后方能運行，即作業(yè)在運行前需一次性地全部裝入內(nèi)存。n目的：提高內(nèi)存利用率。n實現(xiàn)思想：當進程運行時，先將一部分程序裝入內(nèi)存，另一部分暫時留在外存，當要執(zhí)行的指令不在內(nèi)存時，由系統(tǒng)自動完成將它們從外存調(diào)入內(nèi)存工作?！√摂M存儲器的引入n虛存：把內(nèi)存與外存有機的結(jié)合起來使用，從而得到一個容量很大的 “內(nèi)存 ”，這就是虛存。有大量作業(yè)要求運行 ，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè) 有的作業(yè)很大 ，其所要求的內(nèi)存空間超過了內(nèi)存總?cè)萘?，作業(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無法運行。 n因此，任何共享的信息可以單獨作一個段，同樣段中所有內(nèi)容就可以用相同的方式進行使用，從而規(guī)定相同的使用權限； n1) 每一段在邏輯上是相對完整的一組信息，分段技術中共享信息是在段一級出現(xiàn)的。、為什么分段技術比分頁技術更容易實現(xiàn)程序或數(shù)據(jù)的共享？ 1727n（ 4）非法訪問，產(chǎn)生中斷 n（ 3） n（ 2） n（ 1） n（ 5） 3， 400n（ 1） 0， 430 （ 2） 1， 1000100219合法（ 0） /非法（ 1） 長度 基址 nnn（ 3） 物理地址 1024=108MODnn物理地址 1024=20MODn4n答 n71n58n36n13nn系統(tǒng)頁表： （ 2） 8300（請詳細寫出第一、二小題的運算過程） 連續(xù)空間分配與不連續(xù)空間分配方式都屬于實存管理技術。n如：不存在外碎片、段可動態(tài)增長、便于共享和控制存取訪問。段頁式存儲管理的優(yōu)缺點 段頁式 地址變換段表控制寄存器段表長度 起始地址 段 號 (s) 頁號 (p) 頁內(nèi)地址 (w) 物理地址段號 頁表始址……頁號 b……b邏輯地址段表 S段的頁表地址越界++2．地址變換過程在段頁式系統(tǒng)中，為了獲取一條指令或數(shù)據(jù)，需三次訪問內(nèi)存。進行地址變換時，首先利用段號 S，將它與段表長 TL進行比較。 每個段有一個頁表，段表中應有專項指出該段所對應頁表的 頁表始址 和 頁表長度 。內(nèi)存分配：以頁為單位進行分配段號段內(nèi)地址頁號 頁內(nèi)地址作業(yè)的地址空間 一個程序首先被劃分成若干程序段，每一段給予不同的分段標識符然后，對每一分段又分成若干個固定大小的頁面。邏輯地址：用戶程序劃分：按段式劃分（對用戶來講，按段的邏輯關系進行劃分；對系統(tǒng)講，按頁劃分每一段）結(jié)合了段式與頁式二者優(yōu)點 克服了二者的缺點　 1．基本原理在段頁式存儲管理中每個作業(yè)仍按 邏輯分段 ，但對每一段不是按單一的連續(xù)整體存放到存儲器中，而是把 每個段 再分成 若干個頁面 ，每一段不必占據(jù)連續(xù)的主存空間，可把它按頁 存放在不連續(xù) 的主存塊中。１）指出這兩種變換各屬于何種存儲管理；２）計算出這兩種變換所對應的物理地址。 例 : 在一個分頁式存儲管理系統(tǒng)中 ,某作業(yè)的頁表如下所示。為使各個進程所執(zhí)行的代碼完全相同，絕對 不允許 可重入代碼 在執(zhí)行中有任何改變 。又稱為 “純代碼 ”為實現(xiàn)某段代碼的共享 ,在分段式存儲管理系統(tǒng)中 ,各個進程對共享段使用相同的段名 ,并置以適當?shù)?讀 /寫控制權 ,即可做到共享一個邏輯上完事的主存段信息。112n5500n4430n2段內(nèi)位移n095n試求表所示中的邏輯地址所對應的物理地址？n90n4100500n2210段長n0內(nèi)存起始地址 段表n段號 n并從該位置中獲得該段存放在內(nèi)存中的 起始地址 ，然后，檢查 段內(nèi)位移 是否超過該段的段長 ，若超過則同樣產(chǎn)生越界中斷；若未越界，則將該段在內(nèi)存中的 起始地址 與邏輯地址的段內(nèi)位移相加 即得到要訪問的物理地址。...0S工作區(qū)段 [B]主程序段 [M]....