昆明理工大學(xué)付湘瓊操作系統(tǒng)存儲(chǔ)器管理

1、1 計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng) 第四章第四章存儲(chǔ)器管理存儲(chǔ)器管理4.1 存儲(chǔ)器管理的若干概念1. 存儲(chǔ)器2. 地址變換3. 虛擬存儲(chǔ)器 一存儲(chǔ)器1存儲(chǔ)器 存儲(chǔ)器主存 （內(nèi)部存儲(chǔ)器，磁芯存 儲(chǔ)器）輔存 （外存）磁盤、磁鼓、 磁帶、 軟盤 主存 系統(tǒng)區(qū) （OS標(biāo)準(zhǔn)子程序） 用戶區(qū) （用戶程序、數(shù)據(jù)）2主存儲(chǔ)器的物理組織，多級(jí)存儲(chǔ)器高速緩存 主存外存 3存儲(chǔ)器管理的功能： (1) 主存空間分配和保護(hù)：主存儲(chǔ)器中允許同時(shí)容納各種軟件和多個(gè)用戶程序時(shí)，必須解決主存空間如何分配以及各存儲(chǔ)區(qū)內(nèi)的信息如何保護(hù)等問題。對(duì)不同的存儲(chǔ)管理方式，采用的主存空間分配策略是不同的。為了保護(hù)區(qū)域內(nèi)信息不被破壞，必須實(shí)現(xiàn)存

2、儲(chǔ)保護(hù)。存儲(chǔ)保護(hù)的工作必須由硬件和軟件配合來實(shí)現(xiàn)。 (2)主存空間的重定位 配合硬件做好地址轉(zhuǎn)換工作，把一組邏輯地址空間轉(zhuǎn)換成絕對(duì)地址空間，以保證處理器的正確執(zhí)行。 (3) 主存空間的共享 在多道程序設(shè)計(jì)的系統(tǒng)中，同時(shí)進(jìn)入主存儲(chǔ)器執(zhí)行的作業(yè)可能要調(diào)用同的程序。例如，調(diào)用編譯程序進(jìn)行編譯，把這個(gè)編譯程序存放在某個(gè)區(qū)域中，各作業(yè)要調(diào)用時(shí)就訪問這個(gè)區(qū)域，因此這個(gè)區(qū)域就是共享的。同樣也可實(shí)現(xiàn)公共數(shù)據(jù)的公享。 (4) 主存空間的擴(kuò)充 提供虛擬存儲(chǔ)器，使用戶編制程序時(shí)不必考慮主存儲(chǔ)器的實(shí)際容量，使計(jì)算機(jī)系統(tǒng)似乎有一個(gè)比實(shí)際主存儲(chǔ)器容量大得多的主存空間。 二地址變換 1.存儲(chǔ)空間 地址空間一個(gè)目標(biāo)程序所限定

3、的地址范圍 邏輯地址（相對(duì)地址）當(dāng)對(duì)源程序進(jìn)行編譯時(shí)，編譯后一個(gè)目標(biāo)程序所限定的地址范圍稱為該作業(yè)的邏輯地址空間。 物理地址（絕對(duì)地址）主存中一系列存儲(chǔ) 物理單元。 地址空間是邏輯地址的集合。存儲(chǔ)空間是物理地址的集合。一個(gè)是虛的概念，一個(gè)是實(shí)的物體。 2.重定位 當(dāng)一個(gè)地址裝入與其地址空間不一致的存儲(chǔ)空間中，就得要地址變換。也就是說將虛地址映射為內(nèi)存地址，把這種作法叫做地址重定位 (1) 靜態(tài)地址重定位 在裝入一個(gè)作業(yè)時(shí)，把作業(yè)中的指令地址全部轉(zhuǎn)換為絕對(duì)地址（地址轉(zhuǎn)換工作是在作業(yè)執(zhí)行前集中一次完成的）在作業(yè)執(zhí)行過程中就無須再進(jìn)行地址轉(zhuǎn)換工作。 靜態(tài)地址重定位優(yōu)點(diǎn) 它的主要優(yōu)點(diǎn)是，無需增加硬件地

4、址變換機(jī)構(gòu)，因而可在一般計(jì)算機(jī)上實(shí)現(xiàn)。 靜態(tài)地址重定位缺點(diǎn) 主要缺點(diǎn)有： 要求給每個(gè)作業(yè)分配一個(gè)連續(xù)的存儲(chǔ)空間，且在作業(yè)的整個(gè)執(zhí)行期間不能再移動(dòng)，因而也就不能實(shí)現(xiàn)重新分配主存。 用戶必須事先確定所需的存儲(chǔ)量，若所需的存儲(chǔ)量超過可用存儲(chǔ)空間時(shí)，用戶必須考慮覆蓋結(jié)構(gòu)。 用戶之間難以共享主存中的同一程序副本。 2動(dòng)態(tài)地址重定位： 動(dòng)態(tài)地址重地位是在程序執(zhí)行過程中，在cpu訪問內(nèi)存之前,將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址. 動(dòng)態(tài)重定位依靠硬件地址變換機(jī)構(gòu)完成。 Load A500 123455001000 Load A500 12345+虛擬空間 內(nèi)存空間 VR BR.

5、地址重定位機(jī)構(gòu)需要一個(gè)或多個(gè)基地址寄存器BR和一個(gè)或多個(gè)程序虛地址寄存器VR。指令或數(shù)據(jù)的內(nèi)存地址MA與虛地址的關(guān)系為：MA=(BR)+(VR) 其中，(x)表示寄存器x中的內(nèi)容 最簡(jiǎn)單的辦法是利用一個(gè)重定位寄存器。該寄存器的值由調(diào)度程序根據(jù)作業(yè)分配到的存儲(chǔ)空間的起始地址來設(shè)定。在具有這種地址變換機(jī)構(gòu)的計(jì)算機(jī)系統(tǒng)中，當(dāng)作業(yè)執(zhí)行時(shí)，不是根據(jù)CPU給出的邏輯地址去訪問主存，而是將邏輯地址與重定位寄存器中的內(nèi)容相加后得到的地址作為訪問主存的地址。 動(dòng)態(tài)重定位的主要優(yōu)點(diǎn)有： 用戶作業(yè)不要求分配連續(xù)的存儲(chǔ)空間。 用戶作業(yè)在執(zhí)行過程中，可以動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間和在主存中移動(dòng)。 有利于程序段的共享。 動(dòng)態(tài)重定位

6、的主要缺點(diǎn)有： 需要附加的硬件支持。 實(shí)現(xiàn)存儲(chǔ)管理的軟件算法比較復(fù)雜。 三.虛擬存儲(chǔ)器 什么是虛擬存儲(chǔ)器？ 虛擬存儲(chǔ)器是一種存儲(chǔ)管理技術(shù)，用以完成用小的內(nèi)存實(shí)現(xiàn)在大的虛擬空間中程序的運(yùn)行工作。 為了給大作業(yè)用戶提供方便,使它們擺脫對(duì)主存和輔存的分配和管理問題,由操作系統(tǒng)把多級(jí)存儲(chǔ)器統(tǒng)一管理起來,實(shí)現(xiàn)自動(dòng)覆蓋。既一個(gè)大作業(yè)在執(zhí)行時(shí), 其一部分地址空間在主存,另一部分在輔存,當(dāng)訪問的信息不在主存時(shí).因此,從效果來看,這樣的系統(tǒng),好象用戶提供了存儲(chǔ)容量比實(shí)際主存大得多的存儲(chǔ)器,人們稱這個(gè)為虛擬存儲(chǔ)器。之所以稱它為虛擬存儲(chǔ)器,因?yàn)檫@樣的存儲(chǔ)器實(shí)際上并不存在而只是系統(tǒng)增加自動(dòng)覆蓋功能，給用戶造成的一種幻

7、覺,仿佛它有一個(gè)很大的主存供它使用。這是虛擬存儲(chǔ)器的最初概念。 這種想法的核心,實(shí)質(zhì)上也就是把作業(yè)的地址空間和實(shí)際主存的存儲(chǔ)空間似為兩個(gè)不同的概念.一個(gè)計(jì)算機(jī)系統(tǒng)算題人員提供了一個(gè)多大的地址空間,它就所在這個(gè)地址空間編制程序,而完全用不著考慮實(shí)際主存的大小.換句話說, 虛擬存儲(chǔ)器就是一個(gè)地址空間.一個(gè)虛存儲(chǔ)器的最大容量是由計(jì)算機(jī)的地址結(jié)構(gòu)確定的.若CPU給出的有效地址長(zhǎng)度為18位,可以尋址范圍為:0-256k;若地址的長(zhǎng)度為為20位,則尋址范圍為:1024k. 實(shí)際虛擬存儲(chǔ)器其一是要相當(dāng)容量的輔存,足以存放所有并列作業(yè)的地址空間.其二是要有一定的主存,因?yàn)樘幚頇C(jī)上運(yùn)行的作業(yè),必須有一定的信息在

8、主存中.其三是地址變換機(jī)構(gòu). 4.2 分區(qū)存儲(chǔ)管理 4.2.1 分區(qū)管理基本原理 1.固定分區(qū)法 固定分區(qū)把主存分成若干個(gè)固定大小的存儲(chǔ)區(qū)。區(qū)號(hào)分區(qū)長(zhǎng)度起始地址 狀態(tài)18K20K已分配232K28K已分配364K60K已分配4132K124K已分配OS20K28K60K124K256K進(jìn)程A（6K）進(jìn)程B（25K）進(jìn)程C（36K） 2.動(dòng)態(tài)分區(qū)法 因?yàn)楣潭ǚ謪^(qū)主存利用率不高，使用起來不靈活，所以出現(xiàn)了可變分區(qū)的管理技術(shù)。 動(dòng)態(tài)分區(qū)原則：存儲(chǔ)空間的劃分是在裝作業(yè)時(shí)進(jìn)行的。從可用的自由存儲(chǔ)空間內(nèi)，劃出一個(gè)大小正好等于作業(yè)大小的存儲(chǔ)區(qū)，并分配給這一作業(yè)。 進(jìn)程 A（8K）進(jìn)程 D（124K）進(jìn)程 B

9、（16K）進(jìn)程 C（64K）OS進(jìn)程A進(jìn)程B進(jìn)程C進(jìn)程DOS進(jìn)程A進(jìn)程B進(jìn)程COS進(jìn)程A進(jìn)程BOS進(jìn)程AOSA（8K）24K空閑區(qū)B（16K）C完成（64K）空閑區(qū)D（124K）OSA（8K）8K空閑區(qū)B（16K）E（50K）D（124K）14K空閑區(qū)F（16K）OSA（8K）8K空閑區(qū)空閑區(qū)16KE（50K）D（124K）空閑合并124+14=138K進(jìn)程E（50K）進(jìn)程F（16K）進(jìn)入內(nèi)存進(jìn)程B（16K）進(jìn)程D（124K）完成內(nèi)存分配變化過程 4.2.2分區(qū)的分配與回收固定式分區(qū)和可變式分區(qū)的存儲(chǔ)管理算法有如下三種： 最佳適應(yīng)算法(Best Fit) （1）含義 最佳適應(yīng)算法就是為一作業(yè)選

10、擇分區(qū)時(shí)總是尋找其大小最接近于作業(yè)所要求的存儲(chǔ)空間。換句話說，把作業(yè)放入這樣的分區(qū)后剩下的部分最小。（2）優(yōu)點(diǎn) 這種算法的優(yōu)點(diǎn)是：如果存儲(chǔ)空間中具有正好是所要求大小的空閑區(qū)，則必然被選中；如果不存在這樣的空閑區(qū)，也只對(duì)比要求稍大的空閑區(qū)劃分，而絕不會(huì)去劃分一個(gè)更大的空閑區(qū)。（3）實(shí)現(xiàn)方法 為了加快查找速度，應(yīng)將空閑區(qū)按其大小遞增的順序排列，組織成一空閑區(qū)鏈。 最壞適應(yīng)算法（Worst Fit）(1）含義 它在為作業(yè)選擇存儲(chǔ)空間時(shí)，總是尋找最大的空閑區(qū)。（2）實(shí)現(xiàn)方法 空閑區(qū)應(yīng)按其大小遞減的順序排列。分配時(shí)只看鏈頭空閑區(qū)是否滿足要求，決定是否分配。 首次適應(yīng)算法(First Fit) （1）含義

11、 最佳適應(yīng)和最壞適應(yīng)算法各有利弊。首次適應(yīng)算法是對(duì)它們進(jìn)行折衷考慮后設(shè)計(jì)出來的。（2）實(shí)現(xiàn)方法 將空閑區(qū)按其在存儲(chǔ)空間中的起始地址遞增的順序排列。為作業(yè)分配存儲(chǔ)空間時(shí)，從空閑區(qū)鏈的始端開始查找，選則第一個(gè)滿足要求的空閑區(qū)。 （1）分區(qū)分配的主要步驟有： 從未分配表中找到一個(gè)足以容納該作業(yè)的可用空閑區(qū)； 如這個(gè)空閑區(qū)比所要求的大，則將它分成兩部分：一部分成為已分配的分區(qū)，剩下部分仍為空閑區(qū)； 修改兩張表的有關(guān)信息，并回送一個(gè)所分配分區(qū)的序號(hào)或該區(qū)的首址。要求Xk大小分區(qū)取分區(qū)說明表第一項(xiàng)狀態(tài)位置正在使用取下一表項(xiàng)無法分配該分區(qū)空閑？分區(qū)長(zhǎng)度Xk?表結(jié)束？返回分區(qū)號(hào)否否否是是是固定分區(qū)分配算法最佳

12、分配算法例子 系統(tǒng)回收一個(gè)分區(qū)的主要步驟有： 檢查回收分區(qū)是否與空閑區(qū)鄰接，如鄰接則加以合并，使之成為一個(gè)連續(xù)的大空閑區(qū)。 修改兩張說明表?？芍囟ㄎ环謪^(qū)存儲(chǔ)管理 含義 采用動(dòng)態(tài)分配的可變分區(qū)管理，即分配時(shí)可以將主存重的空閑區(qū)拼接后再分配。 由于可變式分區(qū)存儲(chǔ)管理是根據(jù)作業(yè)的需求量劃分分區(qū)的，因此消除了固定式分區(qū)分配造成的內(nèi)零頭。但是，由于作業(yè)的多次請(qǐng)求和釋放，主存中經(jīng)?？赡艹霈F(xiàn)大量的不能充分利用的小空閑區(qū)。 采用拼接技術(shù)，把零頭集中起來形成一個(gè)大的空閑區(qū)。實(shí)現(xiàn)方法是移動(dòng)某些已分配區(qū)中的信息，移動(dòng)夠分配為止或者使所有的作業(yè)位于存儲(chǔ)器的一端，把空閑區(qū)全部留在另一端， 空閑區(qū)拼接的時(shí)機(jī)選擇 進(jìn)行拼接

13、的時(shí)機(jī)可選則為 （1）當(dāng)有作業(yè)完成釋放分區(qū)時(shí)，就立即拼接。這樣的拼接是比較頻繁的，要花費(fèi)較多的處理機(jī)時(shí)間。 （2）當(dāng)某一作業(yè)請(qǐng)求分配存儲(chǔ)空間時(shí)，若當(dāng)時(shí)主存沒有足夠大的空閑區(qū)，但所有空閑區(qū)的總和可以滿足該作業(yè)的要求，此時(shí)進(jìn)行拼接。這樣的拼接可節(jié)省處理機(jī)時(shí)間。 分配算法流程 45 頁(yè)式管理 4.5.1 頁(yè)式管理的基本原理 在分區(qū)存儲(chǔ)管理中，都要求把一個(gè)作業(yè)的地址空間裝入到連續(xù)的存儲(chǔ)空間內(nèi)，不是存在內(nèi)零頭，就是存在外零頭或?yàn)榻鉀Q外零頭花費(fèi)時(shí)間進(jìn)行“拼接”。如果我們能取消作業(yè)對(duì)連續(xù)性的要求，必然會(huì)進(jìn)一步提高主存的利用率，又無需為移動(dòng)信息付出代價(jià)。分頁(yè)管理就是在這個(gè)指導(dǎo)思想下設(shè)計(jì)出來的。 1. 分頁(yè)技術(shù)

14、的實(shí)現(xiàn)原理 等分主存： 把主存的存儲(chǔ)空間劃分成大小相等的片，稱為存儲(chǔ)塊，或稱為頁(yè)架（Page Frame） 用戶邏輯地址空間的分頁(yè)： 把用戶的邏輯地址空間（虛地址空間）劃分成若干個(gè)與存儲(chǔ)塊大小相等的片，稱之為頁(yè)面或頁(yè)（Page）。并給各頁(yè)從零開始依次編以連續(xù)的頁(yè)號(hào)0，1，2，。 邏輯地址的表示： 用戶的邏輯地址一般是從基地址“0”開始連續(xù)編址，即是相對(duì)地址。在分頁(yè)系統(tǒng)中，每個(gè)虛擬地址（相對(duì)地址）用一個(gè)數(shù)對(duì)（p,d）來表示。其中p是頁(yè)號(hào)，d是該虛擬地址在頁(yè)面號(hào)為p的頁(yè)中的相對(duì)地址，稱為頁(yè)內(nèi)地址（位移量）。 主存分配原則： 系統(tǒng)以存儲(chǔ)塊為單位把主存分給作業(yè)或進(jìn)程，并且分給一個(gè)作業(yè)的各存儲(chǔ)塊不一定是

15、相鄰和連續(xù)的。 頁(yè)表 在分頁(yè)系統(tǒng)中，作業(yè)的一頁(yè)可以分配到主存空間中任何一個(gè)可用的存儲(chǔ)塊。但是，系統(tǒng)怎么知道作業(yè)的哪一頁(yè)分配到哪一存儲(chǔ)塊內(nèi)？為此，系統(tǒng)建立了一張頁(yè)面映象表，簡(jiǎn)稱頁(yè)表。用一張頁(yè)表來描述每頁(yè)的頁(yè)號(hào)與所在塊的塊號(hào)的映射。 為了便于管理和保護(hù)，系統(tǒng)為每個(gè)裝入主存的作業(yè)建立一張相應(yīng)的頁(yè)表，它的起始地址及大小保存在該作業(yè)的PCB中。一旦這個(gè)作業(yè)被調(diào)度執(zhí)行，把它的頁(yè)表始址及大小裝入特定的頁(yè)表寄存器中。頁(yè)號(hào)塊號(hào)存取控制021328 4.5.2 簡(jiǎn)單分頁(yè)管理 在作業(yè)或進(jìn)程開始執(zhí)行之前，把該作業(yè)或進(jìn)程的程序段和數(shù)據(jù)全部裝入主存的各個(gè)空閑塊中，并通過頁(yè)表和硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)虛擬地址到主存物理地址的地

16、址映射。1主存的分配與回收 所需的表格 為了實(shí)現(xiàn)分頁(yè)存儲(chǔ)管理，在軟件方面應(yīng)建立如下表格，并由操作系統(tǒng)實(shí)施管理。 (1）頁(yè)表（PMT）。每個(gè)作業(yè)一張表，用于該作業(yè)的地址變換，該作業(yè)有多少頁(yè)面就有多少表目。 （2）存儲(chǔ)分塊表（MBT）。 整個(gè)系統(tǒng)一張表。該表中每一表目對(duì)應(yīng)一個(gè)存儲(chǔ)塊，記錄了該塊的狀態(tài)：已分配或空閑。 2.分配算法 當(dāng)進(jìn)程或作業(yè)要求分配主存塊時(shí)，首先檢查是否有足夠的空閑塊，如果沒有，則本次無法分配。如果有則首先分配設(shè)置頁(yè)表，將分到的主存快號(hào)添入頁(yè)表中。3.地址變換 地址變換過程 （1）當(dāng)調(diào)度一個(gè)作業(yè)執(zhí)行時(shí)，首先將頁(yè)表始址及大小裝入頁(yè)表寄存器。 （2）作業(yè)執(zhí)行過程中CPU產(chǎn)生的每一個(gè)邏

17、輯地址，由硬件地址變換機(jī)構(gòu)自動(dòng)將其分成兩部分：一部分為頁(yè)號(hào)，另一部分是頁(yè)內(nèi)位移量。 （3）這個(gè)頁(yè)號(hào)先與頁(yè)表寄存器中的當(dāng)前頁(yè)表大小進(jìn)行比較。如果頁(yè)號(hào)太大，表示訪問越界，系統(tǒng)產(chǎn)生相應(yīng)的中斷。如果頁(yè)訪問是合法的，則由頁(yè)表始址和頁(yè)號(hào)計(jì)算出所對(duì)應(yīng)的物理塊號(hào)； （4）取出其存取控制字段，作存取控制驗(yàn)證，若合法則將物理塊號(hào)與邏輯地址中的位移量拼接，形成最終訪問的物理地址。否則，產(chǎn)生相應(yīng)訪問非法中斷。地址變換例子 例如，設(shè)一個(gè)3頁(yè)長(zhǎng)的進(jìn)程具有頁(yè)號(hào)0、1、2,分到的主存快號(hào)為2、3、8。假設(shè)頁(yè)的大小為1K,指令LOAD 1,2500的虛地址為100。下面我們以該例子來說明地址變換過程。 （1）指令地址100轉(zhuǎn)換

18、 由虛地址100可知，指令LOAD 1,2500在第0頁(yè)的100單元中。由于第0頁(yè)在主存的第二塊中，因此，該指令在主存的地址為2048+100=2148。 （2）指令地址2500轉(zhuǎn)換 當(dāng)CPU執(zhí)行到第2148單元的指令時(shí)，地址變換機(jī)構(gòu)首先將2500轉(zhuǎn)換為頁(yè)號(hào)與頁(yè)內(nèi)地址兩部分，即P=2,W=452。由頁(yè)表，可知第二頁(yè)所對(duì)應(yīng)的主存快為8。將塊號(hào)8與頁(yè)內(nèi)地址452相連，得到待訪問的主存物理地址為8644。4. 超高速緩存 聯(lián)想存儲(chǔ)器 為了提高地址變換速度，且不增加太多的硬件投資，通過在地址變換機(jī)構(gòu)中增設(shè)一組數(shù)量不多的寄存器，把它作為超高速緩沖寄存器來使用，存放當(dāng)前訪問的那些頁(yè)的頁(yè)號(hào)和塊號(hào)。 地址轉(zhuǎn)換

19、過程 （1）當(dāng)運(yùn)行進(jìn)程要訪問邏輯地址v時(shí)，硬件自動(dòng)將邏輯地址v截成頁(yè)號(hào)p和頁(yè)內(nèi)地址d。 （2）地址轉(zhuǎn)換機(jī)構(gòu)首先以頁(yè)號(hào)p和高速緩沖器中各表目相比較。 （3）若該頁(yè)不在高速緩沖器中，則訪問存儲(chǔ)器中的頁(yè)表。如果相符，則它送出相應(yīng)的塊號(hào)與頁(yè)內(nèi)地址一起形成物理地址，并按此地址訪主存。 超高速緩存（找到） 超高速緩存（未找到） 4.5.3 請(qǐng)求分頁(yè)管理 請(qǐng)求分頁(yè)存儲(chǔ)管理是在簡(jiǎn)單分頁(yè)管理基礎(chǔ)上發(fā)展起來的。請(qǐng)求頁(yè)式管理在作業(yè)或進(jìn)程開始執(zhí)行之前，只把當(dāng)前需要的一部分頁(yè)面裝入主存，其它部分在作業(yè)執(zhí)行過程中需要時(shí)，再?gòu)妮o存上調(diào)入主存 1.頁(yè)表的擴(kuò)充 頁(yè)表增加信息 通常頁(yè)表表目應(yīng)增加如下信息： （1）中斷位：表示該頁(yè)

20、是否在主存。中斷位為0表示該頁(yè)在主存；為1表示不在主存。 （2）修改位：該位為0時(shí)，表示該頁(yè)面中的數(shù)據(jù)未被修改過。該位為1時(shí)，表示該頁(yè)面中的信息已被修改過。 （3）訪問位：表示該頁(yè)面在最近期間是否被訪問過。該位為0時(shí)，表示該頁(yè)面未被訪問過。為1時(shí)，表示該頁(yè)面最近被訪問過。該位主要用于頁(yè)面置換策略中。 （4）輔存地址：指出該頁(yè)面在輔存上的存放地址。擴(kuò)充后的頁(yè)表如圖所示： 頁(yè)號(hào)塊號(hào)存取控制改變位引用位中斷位 輔存地址2.地址變換 請(qǐng)求分頁(yè)的地址變換初始過程十分類似于簡(jiǎn)單分頁(yè)系統(tǒng)的地址變換，其全部工作：存儲(chǔ)空間的分配，頁(yè)面的置換等都是在指令執(zhí)行過程中完成的，更準(zhǔn)確地說，是在CPU訪問內(nèi)存的過程中完成

21、的。 3.缺頁(yè)中斷處理 當(dāng)中斷位為1時(shí)，表示該頁(yè)不在主存，則必須確定它在輔存中的存放地址。并把它從輔存中調(diào)入主存。缺頁(yè)中斷的處理過程如圖： 4. 提取頁(yè)面策略 這是一個(gè)何時(shí)把頁(yè)面裝入主存的問題。 兩種策略 （1）請(qǐng)求式提取:僅當(dāng)需要時(shí)才提取頁(yè)面的策略； （2）預(yù)先調(diào)頁(yè):把事先提取頁(yè)面的策略。任何預(yù)先調(diào)頁(yè)策略都是以預(yù)測(cè)為基礎(chǔ)的。如果能裝入合適的不久要訪問的頁(yè)面，則可減少缺頁(yè)中斷。在很長(zhǎng)一段時(shí)間內(nèi)（甚至本次運(yùn)行）都不被存取，這樣的預(yù)先調(diào)頁(yè)是失敗的。因?yàn)轭A(yù)先調(diào)頁(yè)的成功率約為50，因此，大多數(shù)系統(tǒng)采用純請(qǐng)求式提取頁(yè)面策略。 4.5.4請(qǐng)求頁(yè)式管理中的置換算法 （頁(yè)式淘汰算法） 1.先進(jìn)先出（FIFO）

22、算法 FIFO：總是淘汰最先進(jìn)入主存儲(chǔ)器的那一頁(yè)。 FIFO算法容易實(shí)現(xiàn)，但是它所依據(jù)的理由不是普遍成立的。哪些在內(nèi)存中駐留很久的頁(yè)，往往是被經(jīng)常訪問的頁(yè)，結(jié)果這些常用的頁(yè)都被淘汰調(diào)，而可能又需要立即調(diào)回內(nèi)存。 采用FIFO算法還會(huì)產(chǎn)生一種奇怪現(xiàn)象，直觀上，分配給的作業(yè)的實(shí)頁(yè)越多，進(jìn)程執(zhí)行時(shí)發(fā)生的缺頁(yè)中斷率就越小，但對(duì)FIFO算法這個(gè)結(jié)論并不是絕對(duì)的。在某些情況下，當(dāng)分配的頁(yè)面多反而導(dǎo)致更多的缺頁(yè)中斷，這種現(xiàn)象稱為FIFO異?，F(xiàn)象或稱Belady現(xiàn)象。 創(chuàng)建進(jìn)程式時(shí)往往只向內(nèi)存裝入了第0頁(yè)。 當(dāng)需要淘汰某一頁(yè)時(shí)，選擇在最近一段時(shí)間里最久沒有被使用過的頁(yè)淘汰。 A.近似算法(LFU)：當(dāng)需要淘汰

23、時(shí)，應(yīng)淘汰被訪問次數(shù)最少的頁(yè)。一種簡(jiǎn)單的方法是為每一頁(yè)設(shè)置一個(gè)計(jì)數(shù)器，每當(dāng)訪問一頁(yè)時(shí)，就把該頁(yè)對(duì)應(yīng)的計(jì)數(shù)器加一，隔一個(gè)周期T，把左右計(jì)數(shù)器清0。當(dāng)發(fā)生缺頁(yè)中斷時(shí)，選擇計(jì)數(shù)值最小的頁(yè)，可把它淘汰，同時(shí)把所有計(jì)數(shù)器清0。1.最近最久未使用頁(yè)面置換算法（LRU） B.最近沒有使用的頁(yè)面淘汰算法NUR 需要淘汰某一頁(yè)時(shí)，從那些最近一個(gè)時(shí)期內(nèi)未被訪問的頁(yè)中任選一頁(yè)淘汰。 實(shí)現(xiàn)方法：在頁(yè)內(nèi)增設(shè)一個(gè)訪問位，當(dāng)這一頁(yè)被訪問時(shí)，硬件把它置成“1”，而沒有被訪問過的頁(yè)，訪問位為“0”。因此，在產(chǎn)生缺頁(yè)中斷時(shí)，可從那些訪問位為0的頁(yè)中選一頁(yè)進(jìn)行淘汰。 抖動(dòng)和工作集 1. 局部性概念 局部性含義 (1)時(shí)間局部性：是

24、指某個(gè)位置最近被訪問了，那么往往很快又要被再次訪問。 (2)空間局部性：是指一旦某個(gè)位置被訪問了，那么它附近的位置也將被訪問。 2. 抖動(dòng)(或稱顛簸) 抖動(dòng)： 如果一個(gè)進(jìn)程花費(fèi)多于執(zhí)行時(shí)間的時(shí)間來完成頁(yè)面替換工作，我們稱該進(jìn)程是顛簸的。 4.5.5 存儲(chǔ)保護(hù) 一種是地址越界保護(hù)，另一種存取控制保護(hù)。 地址越界保護(hù)可由地址變換機(jī)構(gòu)中的控制寄存器的值頁(yè)表長(zhǎng)度和所要訪問的虛地址通過比較完成。 存取控制保護(hù)是通過頁(yè)表控制對(duì)內(nèi)存信息的操作方式提供保護(hù)。它的實(shí)現(xiàn)則是在頁(yè)表增加相應(yīng)的保護(hù)位即可。 頁(yè)式管理的優(yōu)缺點(diǎn) 優(yōu)點(diǎn) (1) 由于它不要求作業(yè)或進(jìn)程的程序段和數(shù)據(jù)在主存中連續(xù)存放，從而有效的解決了碎片問題。

25、 (2) 請(qǐng)求分頁(yè)管理提供了虛擬存儲(chǔ)器。提高了主存的利用率，更加有利于多道程序的運(yùn)行和方便用戶，特別是大作業(yè)用戶。 缺點(diǎn) （1）要求有相應(yīng)的硬件支持。 （2）為處理缺頁(yè)中斷，增加了處理機(jī)時(shí)間的開銷。 （3）為防止系統(tǒng)抖動(dòng)所采取的各種措施會(huì)增加系統(tǒng)的復(fù)雜性。 （4）每個(gè)作業(yè)或進(jìn)程的最后一頁(yè)內(nèi)總有一部分空間得不到利用。 4.6 段式與段頁(yè)式管理1.作業(yè)的邏輯地址空間：分段情況下要求每個(gè)作業(yè)的地址空間按照程序的自然邏輯關(guān)系分成若干段，每個(gè)段有自己的段名。子程序子程序數(shù)組數(shù)組子程子程序序主程序主程序數(shù)組數(shù)組主程序主程序作業(yè)A02K00.5k 03000200 2. 段式存儲(chǔ)管理的地址結(jié)構(gòu)段號(hào)段號(hào)段內(nèi)地

26、址段內(nèi)地址a:虛擬地址段號(hào)段號(hào) 始址始址 長(zhǎng)度長(zhǎng)度存取方式存取方式內(nèi)外內(nèi)外 訪問位訪問位b:段表段表每個(gè)作業(yè)一個(gè)，這個(gè)段表實(shí)施段保護(hù)，提供虛存。存取方式讀/寫、只讀、執(zhí)行。段號(hào)其他頁(yè)表長(zhǎng)度起始地址051024171029291036段表長(zhǎng)度 起始地址段表地址寄存器頁(yè)號(hào)其他頁(yè)面11221932148510頁(yè)號(hào) 其他 頁(yè)面12933.段地址變換 4.段的共享與保護(hù) 段的共享是比較容易實(shí)現(xiàn)的，只要用戶使用相同的段名，在新的段表中填入已在主存中的段的起始地址，并置以適當(dāng)?shù)淖x寫控制權(quán)，就可做到共享一個(gè)邏輯上完整的段的信息。 段號(hào)段號(hào) 標(biāo)志標(biāo)志始址始址. 0執(zhí)行執(zhí)行 218 1讀讀/寫寫 365 2只讀只

27、讀 542 共享共享 主存主存 共享共享 數(shù)據(jù)數(shù)據(jù)段號(hào)段號(hào) 標(biāo)志標(biāo)志始址始址. 0 執(zhí)行執(zhí)行 218 1只讀只讀 542 2讀讀/寫寫 103段的共享 分段存儲(chǔ)管理系統(tǒng)的保護(hù)可采用如下幾種措施: (1)在段表中設(shè)置一個(gè)段長(zhǎng)值，以指明該段的長(zhǎng)度。當(dāng)存儲(chǔ)訪問時(shí)，段地址的位移量與段長(zhǎng)相比較，如超過段長(zhǎng)，便發(fā)出越界中斷信號(hào)。 (2) 建立存取控制,在段表的每個(gè)表目中，還增加存取方式項(xiàng)。 (3) 采用存儲(chǔ)保護(hù)鍵。 在一個(gè)段式存儲(chǔ)管理系統(tǒng)中，通過在段表中施加段長(zhǎng)、存取控制、設(shè)置存儲(chǔ)保護(hù)鍵等，可提供一個(gè)多級(jí)的存儲(chǔ)保護(hù)體系。 分段與分頁(yè)的區(qū)別與聯(lián)系 分段與分頁(yè)的區(qū)別 （1）分頁(yè)的作業(yè)地址空間是單一的線性地址空

28、間，而分段作業(yè)的地址空間是二維的。 （2）頁(yè)是信息的物理單位，大小固定。段是信息的邏輯單位，其長(zhǎng)度不定。 （3）分頁(yè)管理是單段式虛擬存儲(chǔ)系統(tǒng)，而分段存儲(chǔ)管理實(shí)現(xiàn)多段式虛擬存儲(chǔ)系統(tǒng)。 段式管理的主要優(yōu)點(diǎn) （1）便于程序模塊化處理和便于處理變換的數(shù)據(jù)結(jié)構(gòu)。（2）便于動(dòng)態(tài)連接。（3）便于共享分段。（4）可以實(shí)現(xiàn)虛擬存儲(chǔ)器，使作業(yè)的地址空間不受主存容量的限制。 段式管理的主要缺點(diǎn) （1）和分頁(yè)管理一樣，處理機(jī)要為地址變換花費(fèi)時(shí)間；要為表格提供附加的存儲(chǔ)空間；這使操作系統(tǒng)復(fù)雜化。（2）為滿足分段的動(dòng)態(tài)增長(zhǎng)和減少外零頭，要采用拼接手段。（3）分段的最大尺寸受到主存可用空間的限制。 4.6.4 段頁(yè)式管理的

29、基本思想 分段結(jié)構(gòu)具有邏輯上清晰的優(yōu)點(diǎn)，但它的一個(gè)致命弱點(diǎn)是每個(gè)段必須占據(jù)主存儲(chǔ)器的連續(xù)區(qū)域，于是，要裝入一個(gè)分段時(shí)可能要移動(dòng)已在主存儲(chǔ)器中的信息，為了克服這個(gè)缺點(diǎn)，可兼用分段和分頁(yè)的方法，構(gòu)成段頁(yè)式存儲(chǔ)管理。 每個(gè)作業(yè)仍按邏輯分段，但對(duì)每一段不是按單一的連續(xù)整體存放到存儲(chǔ)器中，而是把每個(gè)段再分成若干個(gè)頁(yè)面，每一段不必占據(jù)連續(xù)的主存空間，可把它按頁(yè)存放在不連續(xù)的主存塊中。 4.6.5 段頁(yè)式管理的實(shí)現(xiàn)原理 1 虛地址的構(gòu)成 一個(gè)進(jìn)程中所包含的具有獨(dú)立邏輯功能的程序和數(shù)據(jù)仍被劃分為段，并有各自的段號(hào)S。把段劃成若干個(gè)頁(yè)，和頁(yè)式系統(tǒng)一樣。段號(hào)頁(yè)號(hào) 頁(yè)內(nèi)地址 2 段表和頁(yè)表 在段頁(yè)式系統(tǒng)中,每個(gè)分段

30、又被分成若干個(gè)固定大小的頁(yè)面，那么每個(gè)段又必須建立一張頁(yè)表把段中的虛頁(yè)變換成內(nèi)存中的實(shí)際頁(yè)面。顯然，與頁(yè)式管理時(shí)相同，頁(yè)表中也要有相應(yīng)的實(shí)現(xiàn)缺頁(yè)中斷處理和頁(yè)面保護(hù)等功能表項(xiàng)。 每個(gè)段有一個(gè)頁(yè)表，段表中應(yīng)有專項(xiàng)指出該段所對(duì)應(yīng)頁(yè)表的頁(yè)表始址和頁(yè)表長(zhǎng)度。 段表、頁(yè)表、段表地址寄存器。為了進(jìn)行地址轉(zhuǎn)換，系統(tǒng)為每個(gè)作業(yè)建立一個(gè)段表，并且要為該作業(yè)段表中的每一個(gè)段建立一個(gè)頁(yè)表。系統(tǒng)中有一個(gè)段表地址寄存器來指出作業(yè)的段表起始地址和段表長(zhǎng)度。 3.動(dòng)態(tài)地址變換過程 關(guān)鍵問題仍是如何將二維虛地址映射成一維實(shí)地址，為了實(shí)現(xiàn)動(dòng)態(tài)地址變換。 段頁(yè)式系統(tǒng)必須為每個(gè)作業(yè)建立一張段表，段表表目中的地址部分指出該段的頁(yè)表在主存的始址。 為每個(gè)段建立一張頁(yè)表，每個(gè)表目指示該頁(yè)所在主存的頁(yè)面號(hào)。 每個(gè)作業(yè)有一個(gè)段表地址寄存器，指示它的段表所在位置和段表長(zhǎng)度。 設(shè)置快速聯(lián)想寄存器，存放當(dāng)前最常用的段號(hào)S，頁(yè)號(hào)P和對(duì)應(yīng)的內(nèi)存頁(yè)面與其它控制用欄目。 查找方法:如果所訪問的段或頁(yè)在快速聯(lián)想寄存器中，則系統(tǒng)不再訪問內(nèi)存中的段表、頁(yè)表。把快速聯(lián)想寄存器中的值與頁(yè)內(nèi)相對(duì)地址D拼接起來得到內(nèi)存地址。若快速聯(lián)想寄存器中沒有，才去通過段表、頁(yè)表進(jìn)行內(nèi)存地址查找。慢速地址轉(zhuǎn)換過程 若運(yùn)行進(jìn)程