實際操作系統(tǒng)講義請求

1、實際操作系統(tǒng)講義請求 實存管理 具有整體性、駐留性及連續(xù)性三種特性的 存儲器管理方法，叫實存管理。我們學習 過的無論是分區(qū)管理，分頁管理，或分段 管理，還是段頁式管理，都屬于實存管理。 實存管理的所謂整體性是指一個作業(yè)的全 部實體在執(zhí)行之前必須被整個地裝入內(nèi)存， 也就是說，如果一個作業(yè)的邏輯地址空間 大于內(nèi)存的用戶區(qū)時就不能執(zhí)行。 實際操作系統(tǒng)講義請求 駐留性是指作業(yè)一旦進入內(nèi)存便一直駐留 在內(nèi)存區(qū)直到運行完畢。 連續(xù)性，顧名思義，是指給作業(yè)分配的一 片連續(xù)的內(nèi)存空間。 整體性、駐留性及連續(xù)性這三種特性不利 于內(nèi)存空間的有效利用。 實際操作系統(tǒng)講義請求 虛擬存儲器 虛擬存儲器（Virtual

2、Memory），簡稱虛存， 是指對內(nèi)存的虛擬，一種實際并不存在的 內(nèi)存空間，包括一級存儲器概念和作業(yè)地 址空間概念。虛擬并不是無限的，取決于 機器的CPU地址結(jié)構(gòu)，虛存容量不能大于 外存容量。 實際操作系統(tǒng)講義請求 請求分頁管理請求分頁管理 請求分頁管理是動態(tài)分頁管理，是在靜態(tài)分頁管 理基礎(chǔ)上發(fā)展而來的。在簡單分頁管理中，如果 作業(yè)所要求的頁面數(shù)比內(nèi)存空閑的塊數(shù)多，則該 作業(yè)不能裝入運行。在虛擬存儲器技術(shù)的支持下， 可以進行請求分頁管理。 那么請求分頁管理的基本思想是什么？作業(yè)要訪 問的頁面不在內(nèi)存時，該如何處理？如何知道哪 些頁面在內(nèi)存，哪些不在？如何決定把作業(yè)的哪 些頁面留在內(nèi)存中呢？將虛

3、頁調(diào)入內(nèi)存時，沒有 空閑塊又怎么處理？ 在虛擬存儲系統(tǒng)中，將對邏輯空間和物理空間的 考慮截然分開，邏輯空間的容量由系統(tǒng)提供的有 效地址長度決定。 實際操作系統(tǒng)講義請求 請求分頁管理就能實現(xiàn)這種虛存空間，基本方法是在分頁管 理的基礎(chǔ)上，在作業(yè)開始執(zhí)行前，只裝入作業(yè)的一部分頁面 到內(nèi)存，其它的頁面在作業(yè)執(zhí)行過程中根據(jù)需要，動態(tài)地從 輔存裝入內(nèi)存。當內(nèi)存塊已經(jīng)占滿時，再根據(jù)某種策略交換 出部分頁面到輔存。 根據(jù)作業(yè)的執(zhí)行情況裝入作業(yè)的部分實體，顯然節(jié)省了內(nèi)存 空間。 請求分頁管理和分頁管理的數(shù)據(jù)結(jié)構(gòu)、地址映射和存儲保護、 存儲分配與回收等都類似，但請求分頁管理的實現(xiàn)過程復雜 很多，需要由硬件和軟件的

4、相互配合才能完成。 1. 請求調(diào)入及缺頁中斷處理請求調(diào)入及缺頁中斷處理 2. 淘汰算法淘汰算法 3. 抖動與工作集抖動與工作集 實際操作系統(tǒng)講義請求 請求分頁存儲管理鋪墊請求分頁存儲管理鋪墊 作業(yè)在運行期間的各個階段，多數(shù)作業(yè)只使用全作業(yè)在運行期間的各個階段，多數(shù)作業(yè)只使用全 部地址空間的一部分。例如用戶編制的出錯處理部地址空間的一部分。例如用戶編制的出錯處理 子程序，在作業(yè)正常運行情況下不會執(zhí)行這些程子程序，在作業(yè)正常運行情況下不會執(zhí)行這些程 序，沒有必要把它們調(diào)入內(nèi)存。即程序中往往會序，沒有必要把它們調(diào)入內(nèi)存。即程序中往往會 有一些彼此互斥的部分不是每次運行時都能執(zhí)行有一些彼此互斥的部分不

5、是每次運行時都能執(zhí)行 到。到。 程序的局部性。程序的局部性。順序執(zhí)行的指令和線性結(jié)構(gòu)的數(shù) 據(jù)(如數(shù)組)。它們通常被限定在某一連續(xù)區(qū)域。一 旦某一位置被訪問后，那么它附近的位置很快也 會被訪問。 實際操作系統(tǒng)講義請求 基于上述情況，就沒有必要把一個作業(yè)一次性全 部裝入內(nèi)存再開始運行。而是可以把程序當前執(zhí) 行所涉及的信息放入內(nèi)存中，其余部分可根據(jù)需 要臨時調(diào)入，由操作系統(tǒng)和硬件相配合來完成主 存和輔存之間信息的動態(tài)調(diào)度。這樣的計算機系 統(tǒng)好像為用戶提供了一個存儲容量比實際主存大 得多的存儲器，就稱為虛擬存儲器。 實際操作系統(tǒng)講義請求 虛擬存儲器的概念 P61 虛擬存儲技術(shù)的基本思想是利用大容量的外

6、存來擴 充內(nèi)存，產(chǎn)生一個比有限的實際內(nèi)存空間大得多的、 邏輯的虛擬內(nèi)存空間，以有效地支持多道程序設(shè)計 的實現(xiàn)和大型程序運行的需要，增強系統(tǒng)的處理能 力。 請求分頁系統(tǒng)支持虛擬存儲技術(shù) 實際操作系統(tǒng)講義請求 請求分頁存儲管理請求分頁存儲管理 名詞名詞 作業(yè)的邏輯地址空間劃分的頁，稱為 虛頁虛頁 主存稱為實存實存 實存中的塊稱為實頁實頁 實際操作系統(tǒng)講義請求 請求分頁存儲管理請求分頁存儲管理基本原理 請求分頁系統(tǒng)對地址空間和內(nèi)存空間的管理采 用與分頁存儲管理系統(tǒng)相同的方式，但是它只 將作業(yè)的部分頁面裝入內(nèi)存，便可開始運行作 業(yè)，作業(yè)的其他部分被存放在輔助存儲器上。 實際操作系統(tǒng)講義請求 請求分頁存

7、儲管理必須解決的問題請求分頁存儲管理必須解決的問題 一個作業(yè)不全部裝入，該作業(yè)能否開始運 行，并運行一段時間？ 當程序要訪問的某頁不在內(nèi)存時，如何發(fā) 現(xiàn)這種缺頁情況？發(fā)現(xiàn)后應(yīng)如何處理？ 缺頁時，所需的頁面從何處裝入？裝入到 何處？若此時實存中沒有空閑塊應(yīng)怎么辦？ 實際操作系統(tǒng)講義請求 一個作業(yè)不全部裝入，該作業(yè)能否開始運行， 并運行一段時間？ 作業(yè)在運行期間的各個階段，多數(shù)作業(yè)只使用全部地址作業(yè)在運行期間的各個階段，多數(shù)作業(yè)只使用全部地址 空間的一部分。例如用戶編制的出錯處理子程序，在作空間的一部分。例如用戶編制的出錯處理子程序，在作 業(yè)正常運行情況下不會執(zhí)行這些程序，沒有必要把它們業(yè)正常運行

8、情況下不會執(zhí)行這些程序，沒有必要把它們 調(diào)入內(nèi)存。即程序中往往會有一些彼此互斥的部分不是調(diào)入內(nèi)存。即程序中往往會有一些彼此互斥的部分不是 每次運行時都能執(zhí)行到。每次運行時都能執(zhí)行到。 程序的局部性。程序的局部性。順序執(zhí)行的指令和線性結(jié)構(gòu)的數(shù)據(jù)(如數(shù) 組)。它們通常被限定在某一連續(xù)區(qū)域。一旦某一位置被 訪問后，那么它附近的位置很快也會被訪問。 因此，沒有必要把一個作業(yè)一次性全部裝入內(nèi)存再開始 運行。而是可以把程序當前執(zhí)行所涉及的信息放入內(nèi)存 中，其余部分可根據(jù)需要臨時調(diào)入，由操作系統(tǒng)和硬件 相配合來完成主存和輔存之間信息的動態(tài)調(diào)度。 實際操作系統(tǒng)講義請求 當程序要訪問的某頁不在內(nèi)存時，如何發(fā)現(xiàn)當

9、程序要訪問的某頁不在內(nèi)存時，如何發(fā)現(xiàn) 這種缺頁情況？發(fā)現(xiàn)后應(yīng)如何處理？這種缺頁情況？發(fā)現(xiàn)后應(yīng)如何處理？ 地址變換機構(gòu)檢測到虛頁的狀態(tài)為1，由硬件產(chǎn)生缺頁中斷，轉(zhuǎn)去中斷處理 實際操作系統(tǒng)講義請求 所需的頁面從何處裝入？ 在請求分頁管理系統(tǒng)中，當一個作業(yè)完成編譯 鏈接后，所形成的裝配模塊通常以文件形式存入作 為輔存的磁盤上，當該頁需要裝入實存時，就從磁 盤上調(diào)進來。為此，需建立一個作業(yè)的輔助頁表， 也稱為外頁表。 虛頁號輔存地址 實際操作系統(tǒng)講義請求 新調(diào)入的頁面裝入何處？新調(diào)入的頁面裝入何處？ 實存中有空閑實頁，直接將其裝入。實存中有空閑實頁，直接將其裝入。 空閑已滿，則必須淘汰（頁面置換算法）

10、實存中的某一頁?？臻e已滿，則必須淘汰（頁面置換算法）實存中的某一頁。 被淘汰的頁，以后可能還要用，是否需要寫回輔存，被淘汰的頁，以后可能還要用，是否需要寫回輔存， 這取決于該頁進入實存后是否被修改，如未被修改，因輔這取決于該頁進入實存后是否被修改，如未被修改，因輔 存上已有副本則不必寫回輔存。否則，要重新寫回輔存。存上已有副本則不必寫回輔存。否則，要重新寫回輔存。 因此頁表中還可以增加一個因此頁表中還可以增加一個“修改位修改位”，以反映該頁是否，以反映該頁是否 已被修改過。已被修改過。 為了便于系統(tǒng)管理頁面置換，增加為了便于系統(tǒng)管理頁面置換，增加“引用位引用位”，表示該，表示該 頁最近是否被訪

11、問過。頁最近是否被訪問過。 實際操作系統(tǒng)講義請求 虛頁號 主存塊號 改變位 引用位 狀態(tài)位 輔存地址 0/1 1該頁已被 修改過 0該頁未被 修改 0/1 1最近已被 訪問過 主存塊號 0/1 0在內(nèi)存 1不在內(nèi)存 輔助頁表 虛頁號輔存地址保護信息 擴充后的PMT表 實際操作系統(tǒng)講義請求 圖 缺頁中斷的發(fā)生及其處理 執(zhí)行一條指令 形成有效地址 計算頁號 該頁在 實存嗎？ 缺頁中 斷入口 有空閑的 實頁碼？ 出頁 修改PMT MBT C=1？復制到輔存 取出保存的頁號 入頁 找出磁盤地址 修改PMT MBT表 重新執(zhí)行被 中斷的指令 取下一條指令 取數(shù)據(jù)完 成該指令 硬件 軟件 Y N N Y

12、Y N 抖動/ 系統(tǒng)顛簸 實際操作系統(tǒng)講義請求 q抖動抖動/系統(tǒng)顛簸系統(tǒng)顛簸 出頁：將某一頁從實存移到輔存出頁：將某一頁從實存移到輔存 入頁：將某一頁從輔存調(diào)入實存入頁：將某一頁從輔存調(diào)入實存 這種反復進行入頁和出頁的現(xiàn)象稱為這種反復進行入頁和出頁的現(xiàn)象稱為“抖動抖動/系統(tǒng)顛簸系統(tǒng)顛簸” 實際操作系統(tǒng)講義請求 先進先出算法先進先出算法(FIFO) 淘汰駐留主存時間最長的頁面淘汰駐留主存時間最長的頁面 最近最久未用置換算法最近最久未用置換算法(LRU) 淘汰在最近一段時間最久未用的頁面淘汰在最近一段時間最久未用的頁面 最近最不常用算法 最近未使用算法 頁面置換算法/淘汰算法 實際操作系統(tǒng)講義請求

13、 1. 先進先出算法（FIFO算法） 這種算法的基本思想是：總是先淘汰那些駐留 在內(nèi)存時間最長的頁面，即先進入內(nèi)存的頁面先被 置換掉。 理由是：最先進入內(nèi)存的頁面不再被訪問的可能 性最大。 實際操作系統(tǒng)講義請求 2最近最久未使用頁面置換算法（ Least Recently Used/ LRU算法） 這種算法的基本思想是，如果某一頁被訪問了，那么它 很可能馬上又被訪問；反之，如果某一頁很長時間沒有被 訪問，那么最近也不太可能會被訪問。這種算法考慮了程 序設(shè)計的局部性原理。其實質(zhì)是，當需要置換一頁時，選 擇在最近一段時間最久未使用的頁面予以淘汰。 實現(xiàn)這種算法可通過周期性地對“引用位”進行檢查，

14、并利用它來記錄一頁面自上次被訪問以來所經(jīng)歷的時間t， 淘汰時選擇t最大的頁面。 不太實用 實際操作系統(tǒng)講義請求 性能分析性能分析 為了盡可能地減少缺頁中斷的次數(shù)，應(yīng)從 程序設(shè)計的質(zhì)量 頁面的大小 主存的容量 頁面置換算法 等幾方面來考慮。 實際操作系統(tǒng)講義請求 程序設(shè)計的質(zhì)量(主要指程序的局部化程度) 程序的局部化程度包括時間局部化和空間局部化 時間局部化是指一旦某個位置-數(shù)據(jù)或指令-被訪 問了，它常常很快又要再次被訪問。這可通過循環(huán)、經(jīng) 常用到的變量和子程序等程序結(jié)構(gòu)來實現(xiàn)。 空間局部化是指一旦某個位置被訪問到，那么它附近的 位置很快也要用到。這可以盡量采用順序的指令列、線 形的數(shù)據(jù)結(jié)構(gòu)來實

15、現(xiàn)。 局部化程度隨程序而異，一般來說，總希望編制 的程序具有較高的局部化程度。這樣，程序執(zhí)行 時可經(jīng)常集中在幾個頁面上進行訪問，以減少缺 頁中斷的次數(shù)。 實際操作系統(tǒng)講義請求 頁面的大小 頁面大小應(yīng)根據(jù)實際情況實際情況來確定，它和計算機的性能 以及用戶的要求都有關(guān)系。 頁面大，頁表小，占用空間小，缺頁中斷次數(shù)少，但換 頁時間長，頁內(nèi)碎片也大，浪費空間 頁面小時，正好相反 實際操作系統(tǒng)講義請求 主存的容量 一個作業(yè)的執(zhí)行所產(chǎn)生缺頁的次數(shù)是存放頁面的實際存 儲容量的函數(shù)。當存儲容量達到某一程度時，缺頁中斷 的次數(shù)的減少就不明顯了。 試驗分析表明：對所有程序來說，要使之有效地工作， 它在主存中的頁面

16、數(shù)不低于它的總頁面數(shù)的一半。 實際操作系統(tǒng)講義請求 圖 存儲容量與缺頁中斷次數(shù)的關(guān)系 0 16KB32KB48KB64KB80KB96KB112KB 1000 2000 3000 4000 5000 6000 7000 8000 9000 MF 24 KB9321 32 KB5126 48 KB2456 64 KB1295 80 KB696 96 KB441 112 KB329 128 KB271 160 KB144 192 KB62 缺頁次數(shù) F 主存大小 M 實際操作系統(tǒng)講義請求 4頁面置換算法性能 三個參數(shù)： 頁面走向：每個作業(yè)的虛頁調(diào)入實存的順序，稱為頁面軌跡， 或頁面走向，用P表示。

17、 主存容量：是指分配給作業(yè)的主存塊數(shù)，M表示。 置換算法：包括FIFO，LRU等 實際操作系統(tǒng)講義請求 例例 1 設(shè)頁面走向為P=4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5，主存容量 M=3，置換算法采用FIFO，求訪問過程中發(fā)生缺頁中斷的 次數(shù)和缺頁率？假設(shè)開始時，主存未裝入任何塊 。 表1 FIFO性能分析例(M=3) 缺頁中斷次數(shù)F=9 缺頁率f=9/12=75% P行表示頁面走向，M行表示在主存中的頁面號，其中帶有+ +的表示新調(diào)入 頁面，在M行的各列按調(diào)入的順序排列，帶有圓圈的數(shù)字表示下一時刻 將被淘汰頁面，F(xiàn)行表示是否引起缺頁中斷，帶+號的表示引起缺頁中斷

18、。 實際操作系統(tǒng)講義請求 例例 2 設(shè)M=4，其余同例 1。則缺頁中斷次數(shù)和缺頁率？ 表2 FIFO性能分析例(M=4) 缺頁中斷次數(shù)F=10 缺頁率f=10/12=83% 實際操作系統(tǒng)講義請求 由表1，表2得出：對于FIFO算法，內(nèi)存增加，缺頁率反而增加！ 異?，F(xiàn)象異常現(xiàn)象 （Belady異常）異常） 實際操作系統(tǒng)講義請求 例例 3 設(shè)頁面走向如上，M=3，置換算法為LRU，則缺頁中斷 次數(shù)和 缺頁率？ 由于采用LRU算法，M中各列按訪問的時間順序排列， 最近被訪問的頁面在最前。 表3LRU性能分析例(M=3) 缺頁中斷次數(shù)F=10， 缺頁率f=10/12=83%。 實際操作系統(tǒng)講義請求 例例 4 設(shè)M=4，其余同例 3，則缺頁中斷次數(shù)和 缺頁率？ 表4LRU性能分析例(M=4) 實際操作系統(tǒng)講義請求 3 4 實際操作系統(tǒng)講義請求 由表 3， 表 4 可得如下事實： 設(shè)G(P, M, t)表示當頁面走向為P，主存容量為M，在時刻 t的頁面集合，對于LRU算法，存在如下關(guān)系，即 ), 1,(),(tMPGtMPG 成立。即對于任何時刻t(t=1, 2, , 12),G(P, M, t)所選中的頁 號必定包含在G(P, M+1,