【正文】 60?！恫僮飨到y(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有最近最久未使用頁面置換算法（ LRU）。 該方法的著眼點(diǎn)是在要進(jìn)行頁面淘汰時(shí)，檢查這些對(duì)象的被訪問時(shí)間，總是把 最長時(shí)間未被訪問過的頁面 淘汰出去。 LRU算法需要叫多的硬件支持，系統(tǒng)花費(fèi)大，故常使用近似算法（ P132）， 最近沒有使用頁面淘汰算法 是常用的近似算法。該算法所需的頁表及算法流程如下圖：制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有查詢指針前進(jìn)一步，指向下一個(gè)表目選擇該頁面淘汰置頁面訪問位為 0入口返回頁面訪問位 =0？ 是否訪問位頁號(hào) 頁面號(hào)0 6 01 13 12 32 1返回周期性的將訪問位改為 0制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有存儲(chǔ)保護(hù)地址越界保護(hù)： 由頁表控制寄存器中頁表的長度與虛地址相比較來完成。如：在讀取頁表的時(shí)候， 將虛地址中的頁號(hào)與頁表長度比較，若頁號(hào)大于頁表長度 ，則訪問越界。存取控制保護(hù)： 在 頁表中增加一個(gè)保護(hù)位 ，說明對(duì)該頁的 “ 讀、寫 ” 的控制，當(dāng)要訪問訪問某個(gè)頁面時(shí)，系統(tǒng)會(huì)自動(dòng)檢查所做的操作是否滿足該頁在頁表所記錄的存取控制的要求。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有頁式管理的優(yōu)缺點(diǎn)頁式管理有如下優(yōu)點(diǎn)：（ 1）它不要求進(jìn)程的在內(nèi)存中連續(xù)存放，因此 有效地解決了外部碎片。（ 2） 實(shí)現(xiàn)了虛擬存儲(chǔ)方式，提高了內(nèi)存的利用 率，有利于組織多道程序執(zhí)行。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有缺點(diǎn)： （ 1）需要相應(yīng)的硬件支持，增加了機(jī)器成本。 （ 2）實(shí)現(xiàn)動(dòng)態(tài)頁式管理需要增加系統(tǒng)開銷，如 缺頁中斷等。 （ 3）雖然消除了外部碎片，但是 進(jìn)程中的最后 一頁中總有一部分空間得不到利用 ，形成 內(nèi)部碎片 。 （ 4）在內(nèi)外存信息交換時(shí)的淘汰算法的選擇不 當(dāng)時(shí)，產(chǎn)生 抖動(dòng)現(xiàn)象 （即整個(gè)系統(tǒng)內(nèi)外存 之間的頁面交換頻繁， CPU的利用率顯著 降低）。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有 段式與段頁式存儲(chǔ)管理 段式存儲(chǔ)管理基本思想 分區(qū)存儲(chǔ)管理與分頁存儲(chǔ)管理不易實(shí)現(xiàn)作業(yè)與進(jìn)程之間的 程序共享 。而段式存儲(chǔ)管理則可以有效地解決程序共享的問題。 在該管理方式中， 系統(tǒng)將程序按照內(nèi)容或過程分成段 ，每段有自己的名字，用戶程序的地址空間是二維的。 系統(tǒng)以段為單位來分配內(nèi)存 ，然后通過地址映射機(jī)構(gòu)將虛擬地址轉(zhuǎn)換成實(shí)際的物理地址。 多個(gè)進(jìn)程可以通過段名來實(shí)現(xiàn)子程序的共享 。 每段內(nèi)部，是 連續(xù)順序 存儲(chǔ)的。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有段式存儲(chǔ)管理的虛存空間 段式管理的虛存空間是二維的，它是由 “ 段號(hào) ”與 “ 段內(nèi)地址 ” 組成。不同分段中的 “ 段號(hào) ” 是沒有順序關(guān)系的（即段與段之間的地址不是連續(xù)的），而且 段的大小是不等 （頁的大小相同） 的。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有段式存儲(chǔ)管理用到的數(shù)據(jù)結(jié)構(gòu) 非共享段表 與頁式存儲(chǔ)管理類似，系統(tǒng) 為每個(gè)作業(yè)或進(jìn)程 建立一張段 表，保存非共享段的信息。以便實(shí)現(xiàn)動(dòng)態(tài)地址變換和缺段 中斷處理，段表的結(jié)構(gòu)如下圖所示：段號(hào) 起始地址 長度 存取方式 內(nèi)存內(nèi)外 訪問位 0 2067 89 只讀 內(nèi) 1 1 6532 1000 讀 /寫 外 0 2 7780 567 讀 /寫 內(nèi) 1制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有共享段表系統(tǒng)中所有的共享段信息組成了 共享段表 ，共享段表具有如下表項(xiàng) :段號(hào) 段長 內(nèi)存始址 外存始址 進(jìn)程號(hào) 存取控制共享記數(shù)器制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有共享段分配的過程如下： （ 1） 第一個(gè)進(jìn)程 請(qǐng)求共享段時(shí)，為該共享段分配內(nèi)存， 將該段的信息填入進(jìn)程的 非共享段表 中。同時(shí) 在 共享段表中增加一表項(xiàng) ，填入有關(guān)數(shù)據(jù)，置共享 計(jì)數(shù)器為 1。 （ 2） 其它 進(jìn)程請(qǐng)求共享段時(shí)， 該進(jìn)程的非共享段表增 加一表項(xiàng) ，填入該共享段的物理地址。同時(shí)在共 享段表中， 填上調(diào)用進(jìn)程名等信息 。 將共享計(jì)數(shù) 器 +1。 當(dāng)某個(gè)進(jìn)程不再需要共享段時(shí)，將該共享段的共享 計(jì)數(shù)器 減一 ，只有當(dāng)某個(gè)共享段的共享計(jì)數(shù)器為 0時(shí)， 系統(tǒng)才能回收共享段的內(nèi)存。 制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有段式系統(tǒng)中共享段的示意圖如下： 進(jìn)程 1的非 共享段表…… 段 1 段 2 段 n 進(jìn)程 1的程序地址空間 進(jìn)程 2的非 共享段表…… 段 1 段 2 段 n進(jìn)程 2的程序地址空間 操作系統(tǒng) 共享段 1．．．．．． 共享段 2 內(nèi)存制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有缺段中斷機(jī)制 當(dāng)進(jìn)程所需的段還未調(diào)入內(nèi)存時(shí)，便由缺段中斷機(jī)構(gòu)產(chǎn)生 中斷信號(hào)。由系統(tǒng)調(diào)用缺斷處理程序?qū)⑺瓒握{(diào)入內(nèi)存。缺段處理過程如下：修改段表及空閑區(qū)鏈按照合適的算法淘汰一個(gè)或幾個(gè)段來相成一個(gè)合適的空區(qū)合并空閑區(qū)，以形成一個(gè)合適的空閑區(qū)為新段分配內(nèi)存區(qū)內(nèi)存中有合適的空閑區(qū)嗎？否是是請(qǐng)求新段 返回空閑區(qū)容量總和能否滿足？空閑區(qū)管理，同動(dòng)態(tài)分區(qū)管理方式類似制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有段式管理的地址變換地址變換可以使用如下流程來描述：否越界中斷處理修改訪問位 ，若是寫操作，則置訪問位為 “1”形成物理地址：該段內(nèi)存起始地址 +段內(nèi)地址掃描非共享段表，比較段內(nèi)地址是否小于段長是 返回訪問虛地址（段號(hào)，段內(nèi)地址）是否符合存取方式該段是否在內(nèi)存中是是存取控制保護(hù)中斷處理缺段中斷處理否否制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有段的保護(hù)地址越界保護(hù)： 利用段表中的段長項(xiàng)與虛地址中的段內(nèi)地址進(jìn)行比較，若段內(nèi)地址大于段長，系統(tǒng)就會(huì)產(chǎn)生保護(hù)中斷。 存取控制保護(hù)與頁式管理類似。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有段式管理的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： （ 1）便于 程序模塊化處理 。在分段中，每個(gè)程序模塊構(gòu) 成各自獨(dú)立的分段，并采用段的保護(hù)措施，模塊之 間不受干擾，因此模塊化程序的處理比較好解決。 （ 2）便于子程序的 共享 。 （ 3）段長可以根據(jù)需要?jiǎng)討B(tài)增長，對(duì)那些需要不斷吸收 新數(shù)據(jù)的段來說，非常有用。 （ 4）便于 動(dòng)態(tài)鏈接 。由于分段的地址空間是二維的，而 且分段是獨(dú)立的程序模塊，因此可以 在程序執(zhí)行過 程中調(diào)入相應(yīng)的段進(jìn)行動(dòng)態(tài)鏈接 。而分頁管理中， 作業(yè)則必須在執(zhí)行之前鏈接好，以便實(shí)現(xiàn)線性的地 址空間。 （ 5）實(shí)現(xiàn)了虛擬存儲(chǔ)管理，而且內(nèi)外存交換的是一段完 整的 有意義的信息（程序功能模塊） 。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有缺點(diǎn)： （ 1）需要更多的硬件支持，提高了機(jī)器成本（雖然在現(xiàn)在的硬件環(huán)境下已經(jīng)不是問題了）。 （ 2）為了滿足分段的動(dòng)態(tài)增長和碎片的拼接， 給系統(tǒng)帶來了一定的難度和開銷。 （ 3）分段的最大尺寸受內(nèi)存可用空間的限制。 （ 4）在內(nèi)外存信息交換時(shí)的淘汰算法的選擇不 當(dāng)時(shí)，產(chǎn)生抖動(dòng)現(xiàn)象。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有段頁式存儲(chǔ)管理 段式存儲(chǔ)管理與頁式存儲(chǔ)管理各有優(yōu)缺點(diǎn)，如 頁式管理能較好地解決系統(tǒng)碎片問題 ，而 段式存儲(chǔ)管理能很好地實(shí)現(xiàn)程序共享 ，因此，將頁式管理與段式管理的思想結(jié)合起來進(jìn)行內(nèi)存的管理應(yīng)該是更具優(yōu)勢(shì)的。段頁式存儲(chǔ)管理就是基于這種思想提出來的。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有基本思想 在段頁式存儲(chǔ)管理中， 一個(gè)程序首先被劃分成若干段，每段賦予不同的段號(hào)，然后，對(duì)每段又劃分成固定大小的頁 ， 如下圖 所示。因此程序的虛地址空間由三個(gè)部分組成： 段號(hào) 、 頁號(hào) 與 頁內(nèi)位移量 。 內(nèi)存可用區(qū)也被劃分成若干個(gè)大小相等的頁面（同頁式管理相同） 。且 每段的信息可以在內(nèi)存中分開存放（同純段式的區(qū)別） ，因此，分段的大小不受內(nèi)存區(qū)的限制，可以利用動(dòng)態(tài)頁面請(qǐng)求的方式實(shí)現(xiàn)虛擬存儲(chǔ)。制 作 者 ： 郭 平 、 王 在 模 、 何 靜 媛重慶大學(xué)計(jì)算機(jī)學(xué)院 《操作系統(tǒng)》教程 精品課程系列 計(jì)算機(jī)學(xué)院版權(quán)所有 0頁 1頁 2頁 3頁 作業(yè)