os_第4章存儲器管理

1、第二章進(jìn)程管理 操作系統(tǒng)南昌大學(xué)信息管理系南昌大學(xué)信息管理系NanChang UniversityDepartment of information manager操作系統(tǒng)操作系統(tǒng)Operating System 第二章進(jìn)程管理 操作系統(tǒng)4.1 程序的裝入和鏈接程序的裝入和鏈接 一個(gè)用戶源程序要變?yōu)橐粋€(gè)可在內(nèi)存中執(zhí)行的程序，一般要經(jīng)過： 目標(biāo)模塊 （1）編譯（2）鏈接（3）裝入 裝入模塊 裝入內(nèi)存 第二章進(jìn)程管理 操作系統(tǒng) 4.1.1程序的裝入:（1）絕對裝入方式（2）可重定位裝入方式（3）動(dòng)態(tài)運(yùn)行時(shí)裝入方式第二章進(jìn)程管理 操作系統(tǒng)一、絕對裝入方式目標(biāo)中代碼中的地址就是絕對地址第二章進(jìn)程管理

2、操作系統(tǒng)絕對裝入方式只能將裝入模塊裝入到內(nèi)存中事先指定的位置。一般在程序中采用符號地址，在編譯或匯編時(shí)，將符號地址轉(zhuǎn)換為絕對地址。 絕對裝入程序按照裝入模塊中的地址，裝入時(shí)不用對程序和數(shù)據(jù)的地址進(jìn)行修改。只能用于單道程序環(huán)境。 第二章進(jìn)程管理 操作系統(tǒng)二、可重定位裝入方式 可重定位裝入方式，可將裝入模塊裝入到內(nèi)存中適當(dāng)?shù)奈恢?，因此可用于多道程序環(huán)境。目標(biāo)代碼中的地址是相對地址當(dāng)用戶程序被裝入內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時(shí)由軟件完成）第二章進(jìn)程管理 操作系統(tǒng) 11200 1200 LOAD 1200 400 JUMP 400 LOAD11200 104

3、00 JUMP10400 作業(yè)地址 空間相 內(nèi)容空間 0 10000 第二章進(jìn)程管理 操作系統(tǒng)原因: 當(dāng)程序裝入內(nèi)存時(shí), 操作系統(tǒng)要為該程序分配一個(gè)合適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致, 而CPU執(zhí)行指令時(shí)，是按物理地址進(jìn)行的，所以要進(jìn)行地址轉(zhuǎn)換第二章進(jìn)程管理 操作系統(tǒng) 重定位：重定位：在裝入時(shí)對目標(biāo)程序中的指令和數(shù)據(jù)地址的修改過程。 靜態(tài)重定位靜態(tài)重定位：地址變換只是在裝入時(shí)一次完成，以后不再改變。 靜態(tài)重定位不允許程序在運(yùn)行中在內(nèi)存中移動(dòng)位置。第二章進(jìn)程管理 操作系統(tǒng)靜態(tài)重定位的主要缺點(diǎn)：靜態(tài)重定位的主要缺點(diǎn)：1、只能連續(xù)存儲，在重定位后不能移動(dòng)，不利于內(nèi)存空間的有

4、效利用。2、各用戶進(jìn)程很難共享內(nèi)存中的同一程序的副本。第二章進(jìn)程管理 操作系統(tǒng)三、動(dòng)態(tài)運(yùn)行時(shí)裝入方式（動(dòng)態(tài)重定位） 動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不馬上把相對地址轉(zhuǎn)換為絕對地址，而是在程序要真正執(zhí)行時(shí)才進(jìn)行地址轉(zhuǎn)換。 第二章進(jìn)程管理 操作系統(tǒng)動(dòng)態(tài)重定位在程序運(yùn)行過程中要訪問數(shù)據(jù)時(shí)再進(jìn)行地址變換（即在逐條指令執(zhí)行時(shí)完成地址映射。一般為了提高效率，此工作由硬件地址映射機(jī)制來完成。硬件支持，軟硬件結(jié)合完成） 硬件上需要一對寄存器的支持第二章進(jìn)程管理 操作系統(tǒng)4.1.2 程序的鏈接程序的鏈接 一、靜態(tài)鏈接一、靜態(tài)鏈接 先進(jìn)行鏈接所形成的一個(gè)完整的裝入模塊，先進(jìn)行鏈接所形成的一個(gè)完整的

5、裝入模塊，又稱為可執(zhí)行文件。通常都不再拆開，要運(yùn)行時(shí)又稱為可執(zhí)行文件。通常都不再拆開，要運(yùn)行時(shí)可直接將它裝入內(nèi)存。這種事先進(jìn)行鏈接，以后可直接將它裝入內(nèi)存。這種事先進(jìn)行鏈接，以后不再拆開的鏈接方式，稱為靜態(tài)鏈接方式不再拆開的鏈接方式，稱為靜態(tài)鏈接方式 第二章進(jìn)程管理 操作系統(tǒng) C A LL B C A L LB ;Return; C A LLC ; Return; Return; 模 塊 C 模 塊 B 模 塊 A 模 塊 C 模 塊 B 模 塊 A 模 塊 B JS R “L+ M ” Return; M -1 0 0 L-1 0 0 N -1 模 塊 A JS R“L” L+ M M -1

6、 L L-1 0 模 塊 C Return; 第二章進(jìn)程管理 操作系統(tǒng) 編譯后得到三個(gè)目標(biāo)模塊，要將這幾個(gè)目標(biāo)模塊鏈接裝配成一個(gè)裝入模塊，要解決兩個(gè)問題。1、對相對地址進(jìn)行修改 2、變換外部調(diào)用符號(B,C都屬于外部調(diào)用號) 每個(gè)模塊中所用的外部調(diào)用符號,都變換為相對地址。第二章進(jìn)程管理 操作系統(tǒng)二、裝入時(shí)動(dòng)態(tài)鏈接 采用裝入時(shí)動(dòng)態(tài)鏈接方式把目標(biāo)模塊裝入內(nèi)存的同時(shí)，對相對地址進(jìn)行修改。優(yōu)點(diǎn)：1、便于軟件版本的修改和更新。2、便于實(shí)現(xiàn)目標(biāo)模塊共享。第二章進(jìn)程管理 操作系統(tǒng)三、運(yùn)行時(shí)動(dòng)態(tài)鏈接 該方式可將某些目標(biāo)模塊的鏈接，推遲到執(zhí)行時(shí)進(jìn)行。在執(zhí)行時(shí)，如果發(fā)現(xiàn)有一個(gè)被調(diào)用模塊不在內(nèi)存中，就由操作系統(tǒng)找

7、到這個(gè)模塊，把它裝入內(nèi)存，并鏈接到調(diào)用者模塊上。 第二章進(jìn)程管理 操作系統(tǒng)4.2 連續(xù)分配存儲管理連續(xù)分配存儲管理 連續(xù)分配是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。 連續(xù)分配有兩種： 1、單一連續(xù)分配方式 2 2、分區(qū)式分配方式，又可分為： 固定分區(qū)式 動(dòng)態(tài)分區(qū) 動(dòng)態(tài)重定位分區(qū)第二章進(jìn)程管理 操作系統(tǒng)4.2.1 單一連續(xù)分配單一連續(xù)分配 采用單一連續(xù)存儲管理時(shí)，內(nèi)存從概念上分為兩個(gè)連續(xù)區(qū)： （1）系統(tǒng)區(qū)。（2）用戶區(qū)。 第二章進(jìn)程管理 操作系統(tǒng) 作 業(yè) 實(shí) 際 占 用 區(qū) O S 空 閑 區(qū) 用 戶 區(qū) 系 統(tǒng) 區(qū) 第二章進(jìn)程管理 操作系統(tǒng)用戶程序位于RAM中的操作系統(tǒng)00 xFFF用戶程序

8、位于ROM中的操作系統(tǒng)ROM中的設(shè)備驅(qū)動(dòng)程序用戶程序位于RAM中的操作系統(tǒng)0基本輸入輸出系統(tǒng)BIOSMS-DOS00 xFFF第二章進(jìn)程管理 操作系統(tǒng)第二章進(jìn)程管理 操作系統(tǒng) 為了防止OS受到用戶的破壞，存儲保護(hù)可以通過硬件設(shè)置一個(gè)基址寄存器和界限寄存器來實(shí)現(xiàn)。 第二章進(jìn)程管理 操作系統(tǒng)主要優(yōu)點(diǎn): 管理簡單，只需要較少的軟件和硬件支持，便于用戶了解和使用。缺點(diǎn)：（1）若正在執(zhí)行的程序等待某個(gè)事件，這時(shí)處理器就會于處于空閑狀態(tài)，使處理器利用率不高。（2）由于可以進(jìn)入系統(tǒng)運(yùn)行的大多數(shù)用戶作業(yè)尺寸都不可能正好與整個(gè)內(nèi)存用戶作業(yè)區(qū)一致，因此造成主存空間的浪費(fèi)。 （3）計(jì)算機(jī)外圍設(shè)備均被單個(gè)用戶所占用。

9、因此利用率不高。程序和數(shù)據(jù)不可能被共享。 第二章進(jìn)程管理 操作系統(tǒng) 為了增加CPU的使用率，要引進(jìn)多道程序設(shè)計(jì)技術(shù)。 在多道程序環(huán)境下，必須使幾個(gè)作業(yè)同時(shí)駐留內(nèi)存。 如何組織存儲器才能達(dá)到多道程序的運(yùn)行呢？ 固定分區(qū)是最早使用的可運(yùn)行多道程序的存儲器管理方式。第二章進(jìn)程管理 操作系統(tǒng)4.2.2 固定分區(qū)分配固定分區(qū)分配 固定分區(qū)式分配就是把內(nèi)存空間分為若干個(gè)固定大小的區(qū)域。每一個(gè)作業(yè)占據(jù)一個(gè)連續(xù)的分區(qū)。 第二章進(jìn)程管理 操作系統(tǒng)一、劃分分區(qū)的方法 分區(qū)大小相等 分區(qū)大小不相等 分區(qū)一旦劃分結(jié)束，在整個(gè)執(zhí)行過程中每個(gè)分區(qū)的長度和內(nèi)存的總分區(qū)個(gè)數(shù)將保持不變。第二章進(jìn)程管理 操作系統(tǒng)二、內(nèi)存分配 系

10、統(tǒng)設(shè)有一張分區(qū)使用表，各表項(xiàng)包含有每個(gè)分區(qū)的起始地址、大小及狀態(tài)（是否已分配）。 第二章進(jìn)程管理 操作系統(tǒng)分區(qū)使用表分區(qū)號 大?。?K ）起址（ K ）狀態(tài)11220已分配23232已分配36464已分配4128128已分配操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C作業(yè)D20K32K64K128K256K第二章進(jìn)程管理 操作系統(tǒng) 采用固定分區(qū)時(shí)，把一個(gè)分區(qū)分配給某作業(yè)后，該作業(yè)就在此區(qū)域里運(yùn)行、工作，直至完成。 有沒有采用重定位？ 作業(yè)在裝入時(shí)必須進(jìn)行地址變換，因此固定分區(qū)方法實(shí)行的是“靜態(tài)重定位”。 第二章進(jìn)程管理 操作系統(tǒng)固定分區(qū)存儲管理的地址轉(zhuǎn)換和存儲保護(hù) B下限寄存器邏輯地址CPU絕對地址操作系統(tǒng)區(qū)用

11、戶分區(qū)1用戶分區(qū)2用戶分區(qū)3B+L2上限寄存器size，從分區(qū)中劃出u.size給請求者，其余的留在空閑分區(qū)鏈或空閑分區(qū)表中；將分配區(qū)的首址返回給調(diào)用者。 第二章進(jìn)程管理 操作系統(tǒng) 2 2、回收內(nèi)存 （1）回收區(qū)與插入點(diǎn)的前一個(gè)分區(qū)相鄰接F1回收區(qū)F序號分區(qū)大小分區(qū)始址狀態(tài)iF1.size addr1可用addr1第二章進(jìn)程管理 操作系統(tǒng) 2 2、回收內(nèi)存 （1）回收區(qū)與插入點(diǎn)的前一個(gè)分區(qū)相鄰接F1序號分區(qū)大小分區(qū)始址狀態(tài)iF.size+F1.sizeaddr1可用addr1第二章進(jìn)程管理 操作系統(tǒng)（2）回收區(qū)與插入點(diǎn)的后一分區(qū)相鄰接）回收區(qū)與插入點(diǎn)的后一分區(qū)相鄰接 回收區(qū)F F2序號分區(qū)大小

12、分區(qū)始址狀態(tài)iF2.sizeaddr2可用addraddr2第二章進(jìn)程管理 操作系統(tǒng)（3）回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰）回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接接F1回收區(qū)F序號分區(qū)大小分區(qū)始址狀態(tài)iF1.sizeadd1可用i+1F2.sizeadd2可用F2add1add2第二章進(jìn)程管理 操作系統(tǒng)（4）回收區(qū)既不與）回收區(qū)既不與F1鄰接，也不與鄰接，也不與F2鄰接。鄰接。回收區(qū)F序號分區(qū)大小分區(qū)始址狀態(tài)addr第二章進(jìn)程管理 操作系統(tǒng)分區(qū)回收算法：分區(qū)回收算法：(補(bǔ)充）補(bǔ)充）回收分區(qū)R,首址為baddrF上鄰一個(gè)空白區(qū)f1?將f 放入自由主存隊(duì)列從自由主存隊(duì)列中摘下f1NYYN合并釋

13、放分區(qū)f和空白分區(qū)f1成為一個(gè)大的空白區(qū)fF下鄰一個(gè)空白區(qū)f2?從自由主存隊(duì)列中摘下f2合并釋放分區(qū)f和空白分區(qū)f2成為一個(gè)大的空白區(qū)f返回第二章進(jìn)程管理 操作系統(tǒng)碎片問題： 經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個(gè)都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片第二章進(jìn)程管理 操作系統(tǒng)地址轉(zhuǎn)換與存儲保護(hù) 基址基址寄存器邏輯地址CPU絕對地址操作系統(tǒng)區(qū)空閑分區(qū)1用戶作業(yè)1空閑分區(qū)2限長限長寄存器 + 第二章進(jìn)程管理 操作系統(tǒng) 由上可知，在分頁系統(tǒng)環(huán)境下，程序員編制的程序，以及由編譯程序給出的目標(biāo)程序，其地址空間是連續(xù)的，程序地址空間的分頁是由系統(tǒng)自

14、動(dòng)完成的，而不是程序員或編譯程序的事。 第二章進(jìn)程管理 操作系統(tǒng)頁表全部放在內(nèi)存頁表全部放在內(nèi)存 第一次訪問內(nèi)存第一次訪問內(nèi)存 根據(jù)頁號訪問頁表根據(jù)頁號訪問頁表 讀出塊號形成絕對地址讀出塊號形成絕對地址 根據(jù)絕對地址取數(shù)據(jù)根據(jù)絕對地址取數(shù)據(jù) 第二次訪問內(nèi)存第二次訪問內(nèi)存 取一個(gè)數(shù)據(jù)至少取一個(gè)數(shù)據(jù)至少要訪問二次內(nèi)存要訪問二次內(nèi)存 第二章進(jìn)程管理 操作系統(tǒng)2、具有快表的地址變換機(jī)構(gòu)、具有快表的地址變換機(jī)構(gòu) 為了提高查表速度，在地址變換機(jī)為了提高查表速度，在地址變換機(jī)構(gòu)中加入一個(gè)高速小容量的聯(lián)想存儲器，構(gòu)中加入一個(gè)高速小容量的聯(lián)想存儲器，該存儲器具有并行查尋能力，構(gòu)成快表。該存儲器具有并行查尋能力，

15、構(gòu)成快表。第二章進(jìn)程管理 操作系統(tǒng)越界中斷 頁內(nèi)地址d 頁表長度 頁表始址 頁號P 頁號 快表快表 塊號 頁號 塊號 物理地址物理地址 輸入寄存器 d b b + b 聯(lián)想存儲器存放正在運(yùn)行作業(yè)的當(dāng)前最常用的頁號和它的相應(yīng)塊號。 當(dāng)CPU給出有效地址(p,d)，地址變換機(jī)構(gòu)自動(dòng)把頁號P送入輸入寄存器，然后立即和快表中的所有頁號比較。第二章進(jìn)程管理 操作系統(tǒng) 分頁存儲管理中的優(yōu)缺點(diǎn)分頁存儲管理中的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 分頁存儲分配有效地解決了存儲器的分頁存儲分配有效地解決了存儲器的零頭問題，能同時(shí)為更多的作業(yè)提供存儲零頭問題，能同時(shí)為更多的作業(yè)提供存儲空間，也就能在更高的程度上進(jìn)行多道程空間，也

16、就能在更高的程度上進(jìn)行多道程序設(shè)計(jì)，提高了存儲器和處理機(jī)的利用率。序設(shè)計(jì)，提高了存儲器和處理機(jī)的利用率。 第二章進(jìn)程管理 操作系統(tǒng)缺點(diǎn)：缺點(diǎn)： （1）采用了動(dòng)態(tài)地址變換機(jī)構(gòu)，降低了）采用了動(dòng)態(tài)地址變換機(jī)構(gòu)，降低了CPU的速度。的速度。 （2）必須用一部分存儲空間來存放各種）必須用一部分存儲空間來存放各種表格，要花費(fèi)一定的處理機(jī)時(shí)間來建立和管表格，要花費(fèi)一定的處理機(jī)時(shí)間來建立和管理這些表。理這些表。第二章進(jìn)程管理 操作系統(tǒng) （3）解決了分區(qū)間的零頭，又出現(xiàn)了塊內(nèi)的零頭。 （4）要求運(yùn)行的作業(yè)，必須全部裝入內(nèi)存。 （5）和分區(qū)分配方案一樣，作業(yè)的地址空間受到主存實(shí)際容量的限制。第二章進(jìn)程管理 操作

17、系統(tǒng) 一個(gè)具有一個(gè)具有32位的邏輯地址空間的分頁系統(tǒng)：位的邏輯地址空間的分頁系統(tǒng)： 頁面大小為頁面大小為4KB=212B 每個(gè)進(jìn)程的頁表項(xiàng)可達(dá)每個(gè)進(jìn)程的頁表項(xiàng)可達(dá)220個(gè)個(gè)連續(xù)存放連續(xù)存放第二章進(jìn)程管理 操作系統(tǒng)解決方法：解決方法：（1）采用離散分配方式來解決難以找到一塊連）采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題。續(xù)的大內(nèi)存空間的問題。（2）只將當(dāng)前需要的部分頁表項(xiàng)調(diào)入內(nèi)存，其）只將當(dāng)前需要的部分頁表項(xiàng)調(diào)入內(nèi)存，其余的頁表仍駐留在磁盤上，需要時(shí)再調(diào)入。余的頁表仍駐留在磁盤上，需要時(shí)再調(diào)入。第二章進(jìn)程管理 操作系統(tǒng)4.3.3 兩級和多級頁表兩級和多級頁表 1、兩級頁表、兩級頁表

18、 將頁表分頁，并離散地將各頁面分別存放在不將頁表分頁，并離散地將各頁面分別存放在不同的物理塊，為離散分配的頁面再建立一張同的物理塊，為離散分配的頁面再建立一張頁表頁表。外層頁表外層頁表外層頁表的每個(gè)頁表項(xiàng)中記外層頁表的每個(gè)頁表項(xiàng)中記錄了頁表頁面的物理塊號。錄了頁表頁面的物理塊號。第二章進(jìn)程管理 操作系統(tǒng) 以以32位的邏輯地址空間的系統(tǒng)為例，頁位的邏輯地址空間的系統(tǒng)為例，頁面大小為面大小為4 KB：外層頁號外層頁號P1外層頁內(nèi)地址外層頁內(nèi)地址P2頁內(nèi)地址頁內(nèi)地址d3122 2112 11010位，可包含1024個(gè)頁表分頁10位，最多允許1024個(gè)頁面12位第二章進(jìn)程管理 操作系統(tǒng)10111078

19、17421461141151468 01141468外部頁表第0頁頁表第1頁頁表第n頁頁表0n某頁表分頁的始址進(jìn)程的某頁在內(nèi)存中的物理塊號第二章進(jìn)程管理 操作系統(tǒng)P1P2d外部頁號外部頁號外部頁內(nèi)地址外部頁內(nèi)地址頁內(nèi)地址頁內(nèi)地址邏輯地址邏輯地址外部頁表寄存器外部頁表寄存器+bd外部頁表外部頁表頁表頁表物理地址頁表分頁的始址采用離散分配的方式并沒有減少頁表所占的內(nèi)存空間第二章進(jìn)程管理 操作系統(tǒng)2.多級頁表以64位的邏輯地址空間的系統(tǒng)為例，頁面大小為4 KB,余下42位用于外層頁號,則在外層頁表中可能有4096G個(gè)頁表項(xiàng),要占用16384GB的連續(xù)內(nèi)存空間.在64位OS中,把直接尋址的存儲器空間減

20、少到45位長度,這樣可利用三級頁表結(jié)構(gòu)來實(shí)現(xiàn)分頁存儲管理.第二章進(jìn)程管理 操作系統(tǒng)分頁式存儲空間的分配和去配 分頁式存儲管理把主存的可分配區(qū)按頁面大小可分成若干塊，主存分配以塊為單位?？捎靡粡堉鞔娣峙浔韥碛涗浺逊峙涞膲K和尚未分配的塊以及當(dāng)前有多少空閑塊。 例如主存的可分配區(qū)有256塊 用字長16位的16個(gè)字來構(gòu)成主存分配表，表格的每一位與一個(gè)物理塊對應(yīng)，用0/1表示對應(yīng)塊為空閑/已占用，用另一字節(jié)記錄當(dāng)前空閑塊數(shù) 第二章進(jìn)程管理 操作系統(tǒng)位示圖 0/10/10/10/10/10/10/10/1 0/10/10/10/10/10/10/10/10/10/1 0/10/10/10/10/10/10

21、/10/10/10/1 0/10/10/10/10/10/10/10/10/10/1 0/10/10/10/10/10/10/10/10/10/1 0/10/1 空閑塊數(shù)空閑塊數(shù)第二章進(jìn)程管理 操作系統(tǒng)頁的共享和保護(hù) 實(shí)現(xiàn)數(shù)據(jù)共享時(shí)，可允許不同的作業(yè)對共享的數(shù)據(jù)頁用不同的頁號，只要讓各自頁表中的有關(guān)表目指向共享的數(shù)據(jù)信息塊就行了 。對共享程序必須規(guī)定一個(gè)統(tǒng)一的頁號 。實(shí)現(xiàn)信息共享必須解決共享信息的保護(hù)問題。通常的辦法是在頁表中增加一些標(biāo)志位，用來指出該頁的信息可讀/寫；只讀；只可執(zhí)行；不可訪問等，指令執(zhí)行時(shí)進(jìn)行核對。例如，要想向只塊寫入信息則指令停止，產(chǎn)生中斷。第二章進(jìn)程管理 操作系統(tǒng)4.4

22、基本基本分段存儲管理方式分段存儲管理方式 前面介紹的各種存儲管理方案，為用戶提供的是一個(gè)線性地址空間，這對于模塊化程序和變化的數(shù)據(jù)結(jié)構(gòu)的處理，以及不同作業(yè)之間對某些公用子程序或數(shù)據(jù)塊的共享等問題的解決，都存在著較大的困難；另外，程序人員在編程和使用上也有多方面的要求，由此又引入了分段存儲管理方式。 第二章進(jìn)程管理 操作系統(tǒng)1、方便編程： 編程人員希望把作業(yè)按照邏輯關(guān)系，分成若干段，每個(gè)段有自己的名字和長度。 2、分段共享 ： 一般是以信息的邏輯單位為基礎(chǔ)來實(shí)現(xiàn)程序和數(shù)據(jù)的共享的。 3、分段保護(hù)： 以信息的邏輯單位為基礎(chǔ)對內(nèi)存中信息采取保護(hù)措施 。 4、動(dòng)態(tài)鏈接 5、動(dòng)態(tài)增長4.4.1 分段存儲

23、管理方式的引入第二章進(jìn)程管理 操作系統(tǒng)4.4.2 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理 1 1、分段、分段 一個(gè)段定義為一組邏輯信息分段Main分段X分段A第二章進(jìn)程管理 操作系統(tǒng)作業(yè)的地址空間是二維的。作業(yè)的地址空間是二維的。邏輯地址是由段名和段內(nèi)地址構(gòu)成。邏輯地址是由段名和段內(nèi)地址構(gòu)成。 段號段內(nèi)地址 分段管理就是管理由若干分段組成的作業(yè)，且按分段來進(jìn)行存儲分配，即為每個(gè)段分配一個(gè)連續(xù)的分區(qū)，而各個(gè)段可以離散地放入內(nèi)存中不同的分區(qū)中。 第二章進(jìn)程管理 操作系統(tǒng)2、段表段號 段長 基址 邏輯段到物理內(nèi)存區(qū)的映射系統(tǒng)調(diào)度到某個(gè)作業(yè)時(shí)，就為它建立一張段表第二章進(jìn)程管理 操作系統(tǒng)B0SA0NY0L

24、X0PM0K邏輯段號邏輯段號作業(yè)的地址空間作業(yè)的地址空間10003200500060008000PKSLN主存主存K 3200P 1500L 6000N 8000S 5000長度長度 段地址段地址操作系統(tǒng)操作系統(tǒng)第二章進(jìn)程管理 操作系統(tǒng)3、地址變換機(jī)構(gòu)、地址變換機(jī)構(gòu)動(dòng)態(tài)重定位技術(shù)動(dòng)態(tài)重定位技術(shù)實(shí)現(xiàn)把二維地址結(jié)構(gòu)變換成一個(gè)線性的地址結(jié)構(gòu)實(shí)現(xiàn)把二維地址結(jié)構(gòu)變換成一個(gè)線性的地址結(jié)構(gòu)第二章進(jìn)程管理 操作系統(tǒng)段表始址段表始址 段表長度段表長度1100段號S位移量W越界中斷越界中斷+01K6K1500K4K2300K8K3200K9200K4段號段長基址+4196123454196段表寄存器由硬件自動(dòng)完成

25、由硬件自動(dòng)完成第二章進(jìn)程管理 操作系統(tǒng) （1）頁是信息的物理單位，分頁活動(dòng)用戶是看不見的，僅僅用于對內(nèi)存的管理，引進(jìn)分頁是為了消除內(nèi)存的外零頭，提高內(nèi)存的利用率。 段是信息的邏輯單位，分段活動(dòng)用戶是可見的，分段的目的是為了更好地滿足用戶的需要。 分頁和分段的主要區(qū)別分頁和分段的主要區(qū)別 第二章進(jìn)程管理 操作系統(tǒng) （2）頁的大小是固定的，并且由系統(tǒng)確定，由硬件實(shí)現(xiàn)把邏輯地址劃分為頁號和頁內(nèi)地址，一個(gè)系統(tǒng)只能有一種大小的頁面。 段的長度卻不固定，可以在用戶編程時(shí)確定，也可以在編譯程序?qū)υ闯绦蜻M(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分。 第二章進(jìn)程管理 操作系統(tǒng) （3）分頁的地址空間是一維的，程序員只要用一個(gè)

26、記憶符即可表示一個(gè)地址。 分段的作業(yè)地址空間是二維的，程序員在標(biāo)識一個(gè)地址時(shí)，既要給出段名，又要給出段內(nèi)地址。 LOAD 1，A 第二章進(jìn)程管理 操作系統(tǒng)4.4.3 信息信息共享共享 可重入代碼，又稱為可重入代碼，又稱為“純代碼純代碼”，是一種允許多個(gè)進(jìn)程同時(shí)訪問的代碼。是一種允許多個(gè)進(jìn)程同時(shí)訪問的代碼。 可重入代碼是一種不允許任何進(jìn)程可重入代碼是一種不允許任何進(jìn)程對其進(jìn)行修改的代碼。對其進(jìn)行修改的代碼。 第二章進(jìn)程管理 操作系統(tǒng) 例：有一個(gè)可同時(shí)例：有一個(gè)可同時(shí)接納接納40個(gè)用個(gè)用 戶的多用戶戶的多用戶系統(tǒng)，他們都執(zhí)行一個(gè)系統(tǒng)，他們都執(zhí)行一個(gè)文本文本 編輯程序（編輯程序（Text Edito

27、r），文本），文本 編輯程編輯程序含有序含有160KB的代碼和的代碼和40K的數(shù)據(jù)區(qū)。的數(shù)據(jù)區(qū)。 40個(gè)用戶同時(shí)執(zhí)行。個(gè)用戶同時(shí)執(zhí)行。 需要需要(160+40)40=8M的內(nèi)存空間的內(nèi)存空間 。第二章進(jìn)程管理 操作系統(tǒng) 如果如果160K代碼是可重代碼是可重入的，那么代碼就能被共入的，那么代碼就能被共享。內(nèi)存只要保留一份文享。內(nèi)存只要保留一份文本編輯程序的副本，這時(shí)本編輯程序的副本，這時(shí)需要的內(nèi)存空間就是：需要的內(nèi)存空間就是： (160+4040)=1760KB。 第二章進(jìn)程管理 操作系統(tǒng) 在分頁系統(tǒng)中，假定頁面大小為在分頁系統(tǒng)中，假定頁面大小為4KB，160KB的的代碼占用代碼占用160/4=

28、40個(gè)頁面，數(shù)據(jù)區(qū)占個(gè)頁面，數(shù)據(jù)區(qū)占40/4=10個(gè)頁面。個(gè)頁面。 為實(shí)現(xiàn)代碼的共享，每個(gè)進(jìn)程都要在頁表中建為實(shí)現(xiàn)代碼的共享，每個(gè)進(jìn)程都要在頁表中建立立40個(gè)頁表項(xiàng)，物理塊號都是從個(gè)頁表項(xiàng)，物理塊號都是從21#60#，還要為，還要為數(shù)據(jù)區(qū)建立數(shù)據(jù)區(qū)建立10個(gè)頁表項(xiàng)，物理塊號分別的個(gè)頁表項(xiàng)，物理塊號分別的61# 70#，71# 80#，81# 90#， 要把共享的程序安排到所有共享它的作業(yè)地址空要把共享的程序安排到所有共享它的作業(yè)地址空間中相同頁號的頁中。間中相同頁號的頁中。 第二章進(jìn)程管理 操作系統(tǒng)ed1ed2ed40data1data102122607180ed1ed2ed40data1da

29、ta10進(jìn)程進(jìn)程1進(jìn)程進(jìn)程22122606170頁表頁表頁表頁表ed1ed2ed40data1data10 data1data10主存主存021226061707180分分 頁頁 共共 享享第二章進(jìn)程管理 操作系統(tǒng)240280380420editordata1進(jìn)程進(jìn)程1進(jìn)程進(jìn)程2段表段表editordata1 data2 主存主存080 editordata2段長段長基址基址1608040240段長段長基址基址1608040380段表段表分 段 共 享第二章進(jìn)程管理 操作系統(tǒng)4.4.4 段頁式存儲管理段頁式存儲管理 為了獲得分段在邏輯上的優(yōu)點(diǎn)和分頁在管理存儲空間方面的優(yōu)點(diǎn)，兼用分段和分頁方法，

30、即采用段頁存儲管理。 第二章進(jìn)程管理 操作系統(tǒng)1 1、基本原理、基本原理 段頁式系統(tǒng)的基本原理是分段和分頁段頁式系統(tǒng)的基本原理是分段和分頁原理的組合。原理的組合。 在這個(gè)系統(tǒng)中，先把用戶程序分為若在這個(gè)系統(tǒng)中，先把用戶程序分為若干段，每個(gè)分段又被分成若干個(gè)固定大小干段，每個(gè)分段又被分成若干個(gè)固定大小的頁，每個(gè)段有一個(gè)段名。的頁，每個(gè)段有一個(gè)段名。第二章進(jìn)程管理 操作系統(tǒng) 假定頁面大小為假定頁面大小為4K。一作業(yè)分成三段。一作業(yè)分成三段。 第一段第一段7k，占有，占有2頁；頁； 第二段第二段4k，占，占1頁；頁； 第三段第三段3k，占，占1頁。頁。 0104k8k004k04k0頁內(nèi)零頭第二章進(jìn)

31、程管理 操作系統(tǒng) 段號(s) 段內(nèi)頁號頁內(nèi)地址 在段頁式系統(tǒng)中，地址空間由段、段內(nèi)的頁和頁內(nèi)的相對地址構(gòu)成。 段頁式存儲管理中，程序的分段可以由程序員或編譯程序根據(jù)信息的邏輯結(jié)構(gòu)來劃分。而分頁和程序員無關(guān)，是由系統(tǒng)自動(dòng)進(jìn)行的。 第二章進(jìn)程管理 操作系統(tǒng) 段頁式存儲管理中，地址結(jié)構(gòu)是幾維的？段頁式存儲管理中，地址結(jié)構(gòu)是幾維的？二維的二維的第二章進(jìn)程管理 操作系統(tǒng)2 2、地址變換過程、地址變換過程 為了實(shí)現(xiàn)動(dòng)態(tài)地址變換，段頁式系統(tǒng)必須為每個(gè)作業(yè)建立一張段表，并為每個(gè)分段建立一張頁表。 第二章進(jìn)程管理 操作系統(tǒng)第二章進(jìn)程管理 操作系統(tǒng) 進(jìn)行地址變換時(shí)： 段號S與段表長度TL比較； 利用段表始址和段號

32、來求出該段對應(yīng)的段表項(xiàng)在段表中的位置，從中得到該段的頁表始址，并利用邏輯地址中的段內(nèi)頁號P來獲得對應(yīng)頁的頁表項(xiàng)位置，從中讀出該頁所在的的物理塊號b，再用塊號b和頁內(nèi)地址構(gòu)成物理地址。 第二章進(jìn)程管理 操作系統(tǒng) 頁 表 始 址 頁 表 長 度 物 理 地 址 塊 內(nèi) 地 址 塊 號b 頁 表 段 表 頁 內(nèi) 地 址W 頁 號P 段 號S 段 表 長 度 段 表 始 址 b 2 1 0 + 3 2 1 0 + 3 第二章進(jìn)程管理 操作系統(tǒng) 段表和頁表全放在主存的話，訪問內(nèi)存中的一條指令或數(shù)據(jù)，至少需要訪問主存三次。 第一次是訪問段表，以段號為索引找到頁表所在位置。 第二次是訪問頁表，以頁號為索引找

33、到該頁所在的存儲塊號。 第三次是以形成的物理地址訪問內(nèi)存單元。第二章進(jìn)程管理 操作系統(tǒng) 采用聯(lián)想存儲器來加速查表過程。 在快表中保存著當(dāng)前最常用的一些段的段號、頁號及相應(yīng)的主存塊號。 每次訪問時(shí)，同時(shí)利用段號和頁號去檢索快表，若找到匹配的表項(xiàng)，便可從中得到相應(yīng)頁的物理塊號，與頁內(nèi)地址一起形成物理地址；若找不到匹配的表項(xiàng)，仍然要訪問三次內(nèi)存。W P S 主存塊號(S,P)第二章進(jìn)程管理 操作系統(tǒng) W P S 主存塊號(S,P)第二章進(jìn)程管理 操作系統(tǒng)4.5虛擬存儲器的基本概念虛擬存儲器的基本概念4.5.1 虛擬存儲器的引入虛擬存儲器的引入第二章進(jìn)程管理 操作系統(tǒng) 前面討論的各種存儲管理方法雖前面

34、討論的各種存儲管理方法雖各有特長，但有一些共同的特點(diǎn)各有特長，但有一些共同的特點(diǎn): : 首先是首先是“一次性分配一次性分配”。 其次是其次是“駐留性駐留性”。 作業(yè)全部信作業(yè)全部信息，必須一息，必須一次性裝入內(nèi)次性裝入內(nèi)存存 作業(yè)信息一作業(yè)信息一旦裝入內(nèi)存旦裝入內(nèi)存便一直駐留便一直駐留到作業(yè)運(yùn)行到作業(yè)運(yùn)行結(jié)束結(jié)束 一方面使大作業(yè)的運(yùn)行受到限制，另一方面又影響了多道程序的實(shí)現(xiàn)。 第二章進(jìn)程管理 操作系統(tǒng)2、局部性原理、局部性原理 程序的局部性規(guī)律，程序往往會不程序的局部性規(guī)律，程序往往會不均勻地高度局部化地訪問內(nèi)存。均勻地高度局部化地訪問內(nèi)存。 第二章進(jìn)程管理 操作系統(tǒng) （1）程序在執(zhí)行時(shí)，在大

35、多數(shù)情況下仍是順序執(zhí)行的。 這種特性使得程序的執(zhí)行在一段時(shí)間內(nèi)被限制在作業(yè)的某一局部范圍。 P.Denning還有以下一些論點(diǎn)： （2）過程調(diào)用將會使程序的執(zhí)行軌跡由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不超過5。 在一段時(shí)間內(nèi)，程序?qū)痪窒抻谶@些過程的范圍內(nèi)運(yùn)行。第二章進(jìn)程管理 操作系統(tǒng) （3）程序中存在許多循環(huán)結(jié)構(gòu)，它們可以）程序中存在許多循環(huán)結(jié)構(gòu)，它們可以多次重復(fù)執(zhí)行。多次重復(fù)執(zhí)行。 for i:=1 to n ai:=ai+1;（4）程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，）程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，它們往往都局限于很小的范圍內(nèi)。它們往往都局限于很小的范

36、圍內(nèi)。第二章進(jìn)程管理 操作系統(tǒng)（1）時(shí)間局限性時(shí)間局限性 時(shí)間局限性時(shí)間局限性是指最近被訪問的存儲位置，很可能不久的將來還要被訪問。 支持這種現(xiàn)象的是： (a) 循環(huán)； (b) 子程序； (c) 棧； (d) 用于計(jì)數(shù)和總計(jì)的變量。 第二章進(jìn)程管理 操作系統(tǒng)（2）空間局限性空間局限性 空間局限性空間局限性是指存儲訪問有集成一組的傾向，以致一旦某個(gè)位置被訪問到，很有可能它附近的位置也要被訪問。 支持這種現(xiàn)象的是： a、數(shù)組遍歷； b、代碼的順序執(zhí)行； c、程序員傾向于將相關(guān)的變量定義相互靠近存放。 第二章進(jìn)程管理 操作系統(tǒng) 基于局部性原理，作業(yè)沒有必要全部裝入內(nèi)存。 如果計(jì)算機(jī)系統(tǒng)把輔助存儲器當(dāng)

37、做主存儲器的擴(kuò)充，當(dāng)作業(yè)運(yùn)行時(shí)，不是將其全部信息裝入內(nèi)存，而是將必須部分先裝入內(nèi)存，其它部分仍存于輔存中。作業(yè)運(yùn)行過程中隨時(shí)把需要但又不在內(nèi)存的信息裝入內(nèi)存，把暫時(shí)不用的信息淘汰出去，以確保作業(yè)的正確運(yùn)行。 好象這個(gè)計(jì)算機(jī)系統(tǒng)向他們提供了一個(gè)容量很大的主存第二章進(jìn)程管理 操作系統(tǒng)3、虛擬存儲器的定義虛擬存儲器的定義 所謂虛擬存儲器是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲器系統(tǒng)。 虛擬存儲器的大小受計(jì)算機(jī)系統(tǒng)地址結(jié)構(gòu)和可用外存數(shù)量的限制，與實(shí)際內(nèi)存單元的數(shù)量無關(guān)。第二章進(jìn)程管理 操作系統(tǒng)4.5.2 虛擬存儲器的實(shí)現(xiàn)方式虛擬存儲器的實(shí)現(xiàn)方式 離散分配存儲管理方式是實(shí)現(xiàn)

38、虛擬存儲器的基礎(chǔ)。 第二章進(jìn)程管理 操作系統(tǒng)1 1、分頁請求系統(tǒng)、分頁請求系統(tǒng) 是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的頁式虛調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。擬存儲系統(tǒng)。 第二章進(jìn)程管理 操作系統(tǒng)硬件支持：硬件支持： (1) (1) 請求分頁的頁表機(jī)制。請求分頁的頁表機(jī)制。 (2) (2) 缺頁中斷機(jī)構(gòu)。缺頁中斷機(jī)構(gòu)。 (3) (3) 地址變換機(jī)構(gòu)。地址變換機(jī)構(gòu)。 軟件支持：軟件支持： (1) (1) 實(shí)現(xiàn)請求調(diào)頁的軟件。實(shí)現(xiàn)請求調(diào)頁的軟件。 (2) (2) 實(shí)現(xiàn)頁面置換的軟件。實(shí)現(xiàn)頁面置換的軟件。 第二章進(jìn)程管理 操作系統(tǒng)

39、2 2、請求分段系統(tǒng)、請求分段系統(tǒng) 這是在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段及分段置換功能后，所形成的段式虛擬存儲系統(tǒng)。 第二章進(jìn)程管理 操作系統(tǒng)為了實(shí)現(xiàn)請求分段，系統(tǒng)要提供硬件支持： (1) 請求分段的段表機(jī)制。 (2) 缺段中斷機(jī)構(gòu)。 (3) 地址變換機(jī)構(gòu)。 同樣地，請求調(diào)段和段的置換功能的實(shí)現(xiàn)也需要得到OS的支持。 第二章進(jìn)程管理 操作系統(tǒng)4.5.3 虛擬存儲器的特征虛擬存儲器的特征 離散性是虛擬存儲器最基本的特性，虛擬性是它的最重要特征，另外虛擬存儲器還具有多次性和對換性。 第二章進(jìn)程管理 操作系統(tǒng)1、離散性 離散性是指在內(nèi)存分配時(shí)采用離散分配方式。2、多次性 作業(yè)分多次裝入內(nèi)存 3、對

40、換性運(yùn)行時(shí)換進(jìn)換出 4、虛擬性邏輯上擴(kuò)充內(nèi)存容量 最基本特性第二章進(jìn)程管理 操作系統(tǒng)4.6 請求分頁存儲管理方式請求分頁存儲管理方式 請求分頁存儲管理方式是建立在純分頁基礎(chǔ)上的，換進(jìn)換出的基本單位是固定長的頁面，因而實(shí)現(xiàn)起來比較容易。 第二章進(jìn)程管理 操作系統(tǒng)4.6.1 請求分頁中的硬件支持請求分頁中的硬件支持 一、頁表機(jī)制一、頁表機(jī)制 頁表的作用是實(shí)現(xiàn)從用戶地址空間中的邏輯地址到內(nèi)存空間的物理地址的轉(zhuǎn)換。第二章進(jìn)程管理 操作系統(tǒng) 請求頁式管理中對地址空間分頁，內(nèi)存分請求頁式管理中對地址空間分頁，內(nèi)存分塊與基本分頁管理一樣，但對虛頁的管理是不塊與基本分頁管理一樣，但對虛頁的管理是不同的。同的。

41、 要訪問的頁面不在內(nèi)存中，如何發(fā)現(xiàn)和處要訪問的頁面不在內(nèi)存中，如何發(fā)現(xiàn)和處理這種情況？理這種情況？這是請求分頁存儲這是請求分頁存儲管理要解決的兩個(gè)管理要解決的兩個(gè)基本問題基本問題第二章進(jìn)程管理 操作系統(tǒng) 在純分頁系統(tǒng)中，頁表的內(nèi)容為：在純分頁系統(tǒng)中，頁表的內(nèi)容為：頁號物理塊號針對第一個(gè)問題，擴(kuò)充頁表：針對第一個(gè)問題，擴(kuò)充頁表：頁號物理塊號狀態(tài)位P外存地址第二章進(jìn)程管理 操作系統(tǒng)針對第二個(gè)問題： 由地址變換機(jī)構(gòu)產(chǎn)生一個(gè)缺頁中斷信號，OS進(jìn)行中斷處理后，根據(jù)該頁的外存地址把它從外存調(diào)入內(nèi)存。 引進(jìn)修改位和訪問字段。第二章進(jìn)程管理 操作系統(tǒng)請求分頁系統(tǒng)中，頁表項(xiàng)如下：請求分頁系統(tǒng)中，頁表項(xiàng)如下： 頁

42、號頁號物理塊號物理塊號狀態(tài)位狀態(tài)位P訪問字段訪問字段A 修改位修改位M外存地址外存地址(1)(1)狀態(tài)位（存在位）狀態(tài)位（存在位）P。 (2)(2)訪問字段訪問字段A。(3)(3)修改位修改位M。(4)(4)外存地址。外存地址。第二章進(jìn)程管理 操作系統(tǒng) 在虛擬存儲系統(tǒng)中，當(dāng)一個(gè)作業(yè)被編譯或在虛擬存儲系統(tǒng)中，當(dāng)一個(gè)作業(yè)被編譯或經(jīng)鏈接裝配后得到的地址空間，通常存在磁盤經(jīng)鏈接裝配后得到的地址空間，通常存在磁盤上。上。頁號物理塊號 保護(hù)信息外頁外頁面表面表 當(dāng)一個(gè)作業(yè)被調(diào)度到而裝入內(nèi)存時(shí)，系統(tǒng)當(dāng)一個(gè)作業(yè)被調(diào)度到而裝入內(nèi)存時(shí)，系統(tǒng)為它在內(nèi)存建立一張頁表。為它在內(nèi)存建立一張頁表。第二章進(jìn)程管理 操作系統(tǒng)2

43、 2、缺頁中斷機(jī)構(gòu)、缺頁中斷機(jī)構(gòu) 在請求分頁系統(tǒng)中，當(dāng)要訪問的頁面不在內(nèi)存時(shí)，硬件發(fā)一個(gè)缺頁中斷，轉(zhuǎn)交OS處理。第二章進(jìn)程管理 操作系統(tǒng)(1)在指令執(zhí)行期間產(chǎn)生和處理中斷信號。 (2)一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。 它跟一般的中斷有著明顯的區(qū)別：它跟一般的中斷有著明顯的區(qū)別：第二章進(jìn)程管理 操作系統(tǒng)3 3、地址變換機(jī)構(gòu)、地址變換機(jī)構(gòu) 請求分頁系統(tǒng)中的地址變換機(jī)構(gòu)是以分頁系統(tǒng)請求分頁系統(tǒng)中的地址變換機(jī)構(gòu)是以分頁系統(tǒng)的地址變換機(jī)構(gòu)為基礎(chǔ)的，還增加了產(chǎn)生缺頁中斷、的地址變換機(jī)構(gòu)為基礎(chǔ)的，還增加了產(chǎn)生缺頁中斷、處理缺頁中斷，置換等功能。處理缺頁中斷，置換等功能。 第二章進(jìn)程管理 操作系統(tǒng)

44、在進(jìn)行地址變換時(shí)，首先去檢索快表；在進(jìn)行地址變換時(shí)，首先去檢索快表； 如果快表中沒有這一頁的頁表項(xiàng)，再到內(nèi)存中找如果快表中沒有這一頁的頁表項(xiàng)，再到內(nèi)存中找頁表，根據(jù)狀態(tài)位頁表，根據(jù)狀態(tài)位P來判斷該頁是否在內(nèi)存中。來判斷該頁是否在內(nèi)存中。 （1）在內(nèi)存，將該頁的頁表寫入快表；快表滿時(shí)，）在內(nèi)存，將該頁的頁表寫入快表；快表滿時(shí)，調(diào)出某頁表項(xiàng)，再寫入該頁的頁表項(xiàng)；調(diào)出某頁表項(xiàng)，再寫入該頁的頁表項(xiàng)； （2）不在內(nèi)存，產(chǎn)生缺頁中斷，請求）不在內(nèi)存，產(chǎn)生缺頁中斷，請求OS從外存從外存中把該頁調(diào)入內(nèi)存。中把該頁調(diào)入內(nèi)存。 第二章進(jìn)程管理 操作系統(tǒng) 這里僅僅給出一個(gè)很粗略的框圖，具體的過程是很復(fù)雜的。因?yàn)樽鳂I(yè)

45、的副本是以文件形式存于外存上，因而要求頁面?zhèn)鬏敃r(shí)，必然要涉及到文件系統(tǒng)，此外，還得調(diào)用輸入輸出進(jìn)程。在多道程序環(huán)境下，一個(gè)作業(yè)在等待傳輸頁時(shí)，它處于被阻塞的狀態(tài)。此時(shí)，由系統(tǒng)調(diào)度另一作業(yè)運(yùn)行。當(dāng)頁面?zhèn)鬏斖瓿珊螅虐言缺蛔枞哪莻€(gè)作業(yè)重新置成就緒狀態(tài)，但要等到再次調(diào)度到它時(shí)，才能恢復(fù)到原先中斷的地方繼續(xù)運(yùn)行下去。 第二章進(jìn)程管理 操作系統(tǒng)4.6.2 內(nèi)存內(nèi)存分配策略和分配算法分配策略和分配算法 在為進(jìn)程分配物理塊時(shí)，又要解決三個(gè)問題：1、保證進(jìn)程正常運(yùn)行而需要的最少物理塊數(shù)；2、進(jìn)行分配時(shí)，物理塊數(shù)目是固定的還是可變的；3、是采取平均分配算法還是根據(jù)進(jìn)程的大小按比例分配物理塊。第二章進(jìn)程管理

46、操作系統(tǒng)1、最小物理塊數(shù)的確定 最小的物理塊數(shù)，是指保證進(jìn)程正常運(yùn)行所需的最少物理塊數(shù)。 最少物理塊數(shù)與指令的格式、功能和尋址方式有關(guān)，也就是說與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)。 第二章進(jìn)程管理 操作系統(tǒng)2 2、頁面分配頁面分配和和置換策略置換策略 1)、固定分配局部置換（Fixed Allocation, Local Replacement） 采取固定和采取固定和可變分配策可變分配策略略 采取全局置采取全局置換和局部置換和局部置換策略換策略 第二章進(jìn)程管理 操作系統(tǒng)2)、可變分配全局置換空閑物理塊隊(duì)列3)、可變分配局部置換要求保持要求保持適當(dāng)?shù)娜边m當(dāng)?shù)娜表撀薯撀?第二章進(jìn)程管理 操作系統(tǒng)3 3、物理塊

47、分配算法、物理塊分配算法 在固定分配策略中，系統(tǒng)在為各個(gè)進(jìn)程分配物理塊時(shí)，可采?。?1)、平均分配算法 第二章進(jìn)程管理 操作系統(tǒng) 系統(tǒng)中多進(jìn)程頁面數(shù)的總和為：niSiS1 每個(gè)進(jìn)程所能分到的物理塊數(shù)bi=Si/S m，m為可用的物理總數(shù)。 3)、考慮優(yōu)先權(quán)的分配算法 2)、按比例分配算法 ，Si為某個(gè)進(jìn)程的頁面數(shù)。 第二章進(jìn)程管理 操作系統(tǒng)4.6.3 調(diào)頁策略調(diào)頁策略1 1、何時(shí)調(diào)入頁面、何時(shí)調(diào)入頁面1、預(yù)調(diào)頁策略2、請求調(diào)頁策略用于首次調(diào)用于首次調(diào)入入第二章進(jìn)程管理 操作系統(tǒng)2 2、從何處調(diào)入頁面、從何處調(diào)入頁面 (1)(1)系統(tǒng)擁有足夠的對換區(qū)空間。系統(tǒng)擁有足夠的對換區(qū)空間。 當(dāng)缺頁時(shí)，全

48、部從對換區(qū)把所需的頁當(dāng)缺頁時(shí)，全部從對換區(qū)把所需的頁面調(diào)入內(nèi)存，使調(diào)頁速度提高面調(diào)入內(nèi)存，使調(diào)頁速度提高。 第二章進(jìn)程管理 操作系統(tǒng)剛開始時(shí)，都放在文件區(qū) 文件區(qū)對換區(qū)不改改外存可能被修改 不會被修改內(nèi)存(2)(2)系統(tǒng)缺少足夠的對換區(qū)空間。系統(tǒng)缺少足夠的對換區(qū)空間。 第二章進(jìn)程管理 操作系統(tǒng)文件區(qū)對換區(qū)第一次內(nèi)存外存(3) UNIX方式方式 與進(jìn)程有關(guān)的文件都放在文件區(qū)。沒有運(yùn)行過的頁面，從文件區(qū)調(diào)入內(nèi)存；已經(jīng)運(yùn)行過又被換出的頁面，放在對換區(qū)，下次調(diào)入時(shí)，從對換區(qū)調(diào)入。第二章進(jìn)程管理 操作系統(tǒng)外存物理塊號內(nèi)存空：調(diào)入內(nèi)存不空：換出一頁修改位為1，重新寫入外存修改位為0，不必寫入外存將缺頁調(diào)入

49、內(nèi)存修改頁表，寫入快表物理地址訪問數(shù)據(jù)3、頁面調(diào)入過程、頁面調(diào)入過程 第二章進(jìn)程管理 操作系統(tǒng)4.7 頁面置換算法頁面置換算法把選擇換出頁面的算法稱為頁面置換算法。第二章進(jìn)程管理 操作系統(tǒng) 剛被換出的頁很快又被訪問，需要重新調(diào)入，為此又需再選出一頁調(diào)出；而剛被換出的頁，很快又要被訪問，又需把它調(diào)入，如此頻繁地更換頁面，以致一個(gè)進(jìn)程在運(yùn)行中，把大部分時(shí)間花費(fèi)在完成頁面的置換工作上，我們稱該進(jìn)程發(fā)生了“抖動(dòng)”。 抖動(dòng)抖動(dòng)第二章進(jìn)程管理 操作系統(tǒng)4.7.1最佳置換算法和先進(jìn)先出算法最佳置換算法和先進(jìn)先出算法1 1、最佳置換算法、最佳置換算法 最佳置換算法是由Relady在1966年提出的，這種算法選

50、擇的被淘汰頁面，將是永不使用的，或在最長時(shí)間內(nèi)不再被訪問的頁面。第二章進(jìn)程管理 操作系統(tǒng) 假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁面號引用串。 1 2 3 4 5 6 7 8 9 1011121314151617181920217 0 1 2 0 3 0 4 2 3 0 3122 0 1 1 7101702070170304238 91000214500231112130102141516171807011920210673020 采用最佳置換算法，只發(fā)生了6次頁面置換，發(fā)生了9次缺頁中斷。缺頁率=9/21第二章進(jìn)程管理 操作系統(tǒng)2、先進(jìn)先出頁面置換算法（、先進(jìn)先出頁面置換算法（FI

51、FO） 這是最早出現(xiàn)的置換算法，這種算法總是淘汰最先進(jìn)入內(nèi)存的頁面，選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。第二章進(jìn)程管理 操作系統(tǒng) 我們來看看采用FIFO算法進(jìn)行頁面置換時(shí)的情況。 0 717002170031020 4 51230 60230 74300 84200 94230 100230 11-130130 140120 15-187120 197020 207010 21一共發(fā)生了12次頁面置換，比最佳置換算法多了1倍。缺頁率15/21=3/4，15次頁面中斷。 1 2 3 4 5 6 7 8 9 1011121314151617181920217 0 1 2 0 3 0 4 2 3

52、 0 3122 0 1 1 710第二章進(jìn)程管理 操作系統(tǒng) FIFO是根據(jù)各個(gè)頁面調(diào)入內(nèi)存的時(shí)間來選擇被淘汰頁面，但頁面調(diào)入的先后并不能反映頁面的使用情況。 FIFO算法只是在按線性順序訪問地址空間才是理想的。 未考慮到程序的動(dòng)態(tài)特性。 可能引起異常。第二章進(jìn)程管理 操作系統(tǒng)4.7.2 最近最久未使用最近最久未使用LRU置換算法置換算法 1、LRU（Least Recently Used）算法的描述）算法的描述 這種算法依據(jù)的原理是程序執(zhí)行時(shí)所具有的局這種算法依據(jù)的原理是程序執(zhí)行時(shí)所具有的局部性，即那些剛被使用過的頁面可能馬上再次被使部性，即那些剛被使用過的頁面可能馬上再次被使用，而那些最近未

53、被使用的頁一般來說不會馬上被用，而那些最近未被使用的頁一般來說不會馬上被使用到。使用到。選擇淘汰的頁面是最近最久未使用第二章進(jìn)程管理 操作系統(tǒng) 我們用“最近的過去”來直接推斷“最近的將來”。 7070717012 0 3402302 132 0 1 1 7 0 1120023043024 243032213012017發(fā)生了9次頁面置換。 標(biāo)明訪問時(shí)標(biāo)明訪問時(shí)間間 第二章進(jìn)程管理 操作系統(tǒng) LRU算法是與每個(gè)頁面最后使用的算法是與每個(gè)頁面最后使用的時(shí)間有關(guān)的。當(dāng)要淘汰一個(gè)頁面時(shí)，時(shí)間有關(guān)的。當(dāng)要淘汰一個(gè)頁面時(shí)， LRU算法選擇過去一段時(shí)間里最久未被算法選擇過去一段時(shí)間里最久未被使用的頁面。使用

54、的頁面。第二章進(jìn)程管理 操作系統(tǒng)2、LRU算法的硬件支持算法的硬件支持為了實(shí)現(xiàn)LRU算法必須解決： （1）一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁面各有多久時(shí)間未被進(jìn)程訪問； （2）如何快速地知道哪一頁是最近最久未使用的頁面。 第二章進(jìn)程管理 操作系統(tǒng)1 1、寄存器、寄存器 為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，表示為：表示為： R=Rn-1Rn-2Rn-3R1R2R0 當(dāng)進(jìn)程訪問某物理塊時(shí)，要將相應(yīng)的寄存器的當(dāng)進(jìn)程訪問某物理塊時(shí)，要將相應(yīng)的寄存器的Rn-1位置為位置為1。 定時(shí)信號將每隔一定時(shí)間將寄存器右移一次，定時(shí)信號將每隔一定時(shí)間將寄存器右移一次，把把n位寄存器

55、的數(shù)看作是一個(gè)無符號的整數(shù)，最近位寄存器的數(shù)看作是一個(gè)無符號的整數(shù)，最近最久未使用的頁面就對應(yīng)著具有最小數(shù)值的寄存器最久未使用的頁面就對應(yīng)著具有最小數(shù)值的寄存器 。用于記錄某進(jìn)程在內(nèi)存中各頁的使用情況。用于記錄某進(jìn)程在內(nèi)存中各頁的使用情況。第二章進(jìn)程管理 操作系統(tǒng)2、棧 LRU置換算法可用堆棧的方法來實(shí)現(xiàn)。 棧中存放當(dāng)前內(nèi)存中的頁面號，每當(dāng)訪問一頁時(shí)就調(diào)整一次堆棧，總是使最近訪問的那頁的頁面號保持在棧頂，然后根據(jù)當(dāng)前被訪問時(shí)間的近遠(yuǎn)，依次排列，棧底總是最近最久未使用的那頁的頁面號。 淘汰淘汰第二章進(jìn)程管理 操作系統(tǒng)1121231234214312431234215621237651241256

56、125612561265126313276327缺頁中斷假設(shè)，作業(yè)固定占用4塊主存 例如，某作業(yè)按下列頁號訪問：例如，某作業(yè)按下列頁號訪問： 第二章進(jìn)程管理 操作系統(tǒng)4.7.3 CLock置換算法置換算法 CLock算法就是用得較多的一種LRU近似算法。 第二章進(jìn)程管理 操作系統(tǒng)1 1、簡單的、簡單的CLock置換算法置換算法 這種算法的實(shí)質(zhì)是：當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間內(nèi)最久未用的頁予以淘汰，因此稱為最近未用的算法NRU（Not Recently Used）。第二章進(jìn)程管理 操作系統(tǒng) 這種近似算法，要求為每一頁設(shè)置一位訪問位，再將內(nèi)存中的所有頁面都通過指針按FIFO鏈成一個(gè)循環(huán)隊(duì)列

57、。 當(dāng)某頁被訪問時(shí)，訪問位由硬件自動(dòng)置“1”。我們可以根據(jù)訪問位的狀態(tài)來判斷各個(gè)頁面最近使用的情況。如果是“0”，就選擇該頁換出；若為1，則重新將它置為0，再按照FIFO算法檢查下一個(gè)頁面。 第二章進(jìn)程管理 操作系統(tǒng)塊號頁號訪問位指針0124034215650711替換替換指針指針總是指向最近總是指向最近被替換的頁所被替換的頁所在的存儲塊，在的存儲塊，缺頁時(shí)從其后缺頁時(shí)從其后一塊開始。一塊開始。第二章進(jìn)程管理 操作系統(tǒng)2、改進(jìn)型CLock置換算法 1類 （A=0，M=0），最近既未被訪問，又未被修改，是最佳淘汰頁。 2類 （A=0，M=1），最近未被訪問，但已被修改，不是很好的淘汰頁。 3類

58、（A=1，M=0），最近已被訪問，但未被修改，可能再被訪問。 既要考慮到頁既要考慮到頁面的使用情況，面的使用情況，還要考慮置換還要考慮置換代價(jià)代價(jià) 4類 （A=1，M=1），最近已被訪問且被修改，可能再被訪問。 第二章進(jìn)程管理 操作系統(tǒng)改進(jìn)型改進(jìn)型CLock算法，執(zhí)行過程可分為以下三步：算法，執(zhí)行過程可分為以下三步： （1）從指針的當(dāng)前位置開始，掃描按先進(jìn)先出循環(huán)隊(duì)列，尋找A=0且M=0的第一類頁面，將符合條件的第一個(gè)頁面作為淘汰頁，在第一次掃描期間A不改變。 第二章進(jìn)程管理 操作系統(tǒng)（2）第一步失敗，開始第二輪掃描，尋找A=0且M=1的第二類頁面，將符合條件的第一個(gè)頁面作為淘汰頁。將所有經(jīng)過

59、的頁面的訪問位置0。（3）第二步也失敗，把指針返回到開始的位置，把所有的訪問位A置為0，然后重復(fù)第一步，如還是失敗，重復(fù)第二步，就一定能找到被淘汰的頁。第二章進(jìn)程管理 操作系統(tǒng)4.7.4 其它置換算法其它置換算法1、最少使用（Least Frequently Used）置換算法（LFU ）既可實(shí)現(xiàn)LRU，也可實(shí)現(xiàn)LFU 為內(nèi)存中的每個(gè)頁面為內(nèi)存中的每個(gè)頁面設(shè)置一個(gè)移位寄存器，用設(shè)置一個(gè)移位寄存器，用來記錄頁面被訪問的頻率，來記錄頁面被訪問的頻率，淘汰頁是最少使用或是訪淘汰頁是最少使用或是訪問次數(shù)最少的頁面。問次數(shù)最少的頁面。 ri最小的頁就是最近一段時(shí)間使用最少的頁面。最小的頁就是最近一段時(shí)間

60、使用最少的頁面。第二章進(jìn)程管理 操作系統(tǒng)2、頁面緩沖算法（Page Buffering Algorithm） PBA 淘汰頁面未修改修改過空閑頁面鏈表末尾已修改頁面的鏈表中末尾采用可變分配和局部置換方式，采用可變分配和局部置換方式，采用采用FIFO置換算法置換算法 第二章進(jìn)程管理 操作系統(tǒng)請求分頁系統(tǒng)的性能分析請求分頁系統(tǒng)的性能分析 請求分頁系統(tǒng)中，程序在運(yùn)行中產(chǎn)生的缺頁情況，會影響程序的運(yùn)行速度及系統(tǒng)性能。缺頁率的高低又將直接與每個(gè)進(jìn)程所占用的物理塊數(shù)目有關(guān)。因此，應(yīng)該把缺頁率保持在一個(gè)合理的水平上。第二章進(jìn)程管理 操作系統(tǒng) 請求分頁管理是實(shí)現(xiàn)單段式虛擬存儲器的一種具體方案，它允許作業(yè)的部分