存儲(chǔ)管理PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1存儲(chǔ)管理存儲(chǔ)管理操作系統(tǒng)的資源管理 (3) 主存管理 2第1頁/共61頁3操作系統(tǒng)的資源管理 (3) 主要內(nèi)容 第2頁/共61頁4分區(qū)存儲(chǔ)管理段式存儲(chǔ)管理操作系統(tǒng)的資源管理 (3) 主存管理的功能 頁式存儲(chǔ)管理段頁式存儲(chǔ)管理一個(gè)程序是一個(gè)連續(xù)、線性的地址結(jié)構(gòu)；確定線性地址空間中的指令地址或操作數(shù)地址只需要一個(gè)信息。 程序地址空間程序地址空間01 n-1 第3頁/共61頁5一個(gè)程序由若干個(gè)分段組成，每個(gè)分段是一個(gè)連續(xù)的地址區(qū)；確定任一線性地址空間中的指令地址或操作數(shù)地址需要兩個(gè)信息，一是該信息所在的分段，另一個(gè)是該信息在段內(nèi)的偏移量。code_addr4KB 10代碼分代碼分段段data

2、_addr3KB 10數(shù)據(jù)分?jǐn)?shù)據(jù)分段段stack_addr2KB 10棧段棧段11 操作系統(tǒng)的資源管理 (3) 主存管理的功能 第4頁/共61頁6 物理地址是計(jì)算機(jī)主存單元的真實(shí)地址，又稱為絕對(duì)地址或?qū)嵉刂贰?物理地址的集合所對(duì)應(yīng)的空間組成了主存空間。 用戶的程序地址(指令地址或操作數(shù)地址)均為邏輯地址。 用戶程序所有的邏輯地址集合對(duì)應(yīng)的空間。操作系統(tǒng)的資源管理 (3) 主存管理的功能 第5頁/共61頁7主存空間主存空間01m-1作業(yè)作業(yè)1地址空地址空間間01n-1作業(yè)作業(yè) i 地址空地址空間間01k-1 操作系統(tǒng)的資源管理 (3) 主存管理的功能 第6頁/共61頁8操作系統(tǒng)的資源管理 (3)

3、 主存管理的功能 第7頁/共61頁9什么是地址映射 將程序地址空間中使用的邏輯地址變換成主存中的物 理地址的過程，稱為地址映射。mov r1,5001230100500599作業(yè)地址空間作業(yè)地址空間mov r1,50012301000110015001599256k-1存儲(chǔ)空間存儲(chǔ)空間操作系統(tǒng)的資源管理 (3) 主存管理的功能 第8頁/共61頁10靜態(tài)地址映射 在作業(yè)裝入過程中隨即進(jìn)行的地址變換方式稱為靜態(tài) 地址映射。mov r1,500mov r1,500+m01005005990mm+100256k-1作業(yè)地址空間作業(yè)地址空間存儲(chǔ)空間存儲(chǔ)空間m+500重定位重定位裝入程序裝入程序12312

4、3操作系統(tǒng)的資源管理 (3) 主存管理的功能 第9頁/共61頁11動(dòng)態(tài)地址映射 在程序執(zhí)行期間，隨著每條指令和數(shù)據(jù)的訪問自動(dòng)地 連續(xù)地進(jìn)行地址映射，這種地址變換方式稱為動(dòng)態(tài)地 址映射。重定位寄存器重定位寄存器 1000 500邏輯地址+0 mov r1 , 500 1000256k-1存儲(chǔ)空間110015001600123mov r1,5000100500599作業(yè)地址空間123操作系統(tǒng)的資源管理 (3) 主存管理的功能 第10頁/共61頁12靜態(tài)地址映射與動(dòng)態(tài)地址映射的區(qū)別靜態(tài)地址映射 動(dòng)態(tài)地址映射 操作系統(tǒng)的資源管理 (3) 主存管理的功能 第11頁/共61頁13構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)制定策

5、略分配策略在眾多個(gè)請(qǐng)求者中選擇一個(gè)請(qǐng)求者的原則放置策略在可用資源中選擇一個(gè)空閑區(qū)的原則調(diào)入策略決定信息裝入主存的時(shí)機(jī) 預(yù)調(diào)策略：預(yù)先將信息調(diào)入主存 請(qǐng)調(diào)策略：當(dāng)需要信息時(shí)，將信息調(diào)入主存淘汰策略在主存中沒有可用的空閑區(qū)(對(duì)某一作業(yè)而言)時(shí)，決定哪些信息從主存中移走，即確定淘汰已占用的內(nèi)存區(qū)的原則。實(shí)施主存分配與回收操作系統(tǒng)的資源管理 (3) 主存管理的功能 第12頁/共61頁14實(shí)現(xiàn)方法程序的全部代碼和數(shù)據(jù)存放在輔存中；將程序當(dāng)前執(zhí)行所涉及的那部分程序代碼放入主存中；程序執(zhí)行時(shí)，當(dāng)所需信息不在主存，由操作系統(tǒng)和硬件相配合來完成主存從輔存中調(diào)入信息，程序繼續(xù)執(zhí)行。什么是虛擬存儲(chǔ)器 由操作系統(tǒng)和硬

6、件配合完成主存和輔存之間信息的動(dòng)態(tài) 調(diào)度。計(jì)算機(jī)系統(tǒng)為用戶提供一個(gè)其存儲(chǔ)容量比實(shí)際主 存大得多的存儲(chǔ)器，這個(gè)存儲(chǔ)器稱為虛擬存儲(chǔ)器。局部性特征局部性特征操作系統(tǒng)的資源管理 (3) 主存管理的功能 第13頁/共61頁15虛擬存儲(chǔ)器的核心邏輯地址與物理地址分開存儲(chǔ)空間與虛地址空間分開提供地址變換機(jī)構(gòu)實(shí)現(xiàn)虛擬存儲(chǔ)器的物質(zhì)基礎(chǔ)有相當(dāng)容量的輔存 足以存放應(yīng)用程序的虛地址空間有一定容量的主存 存放進(jìn)入主存的多進(jìn)程的信息地址變換機(jī)構(gòu) 操作系統(tǒng)的資源管理 (3) 主存管理的功能 第14頁/共61頁16什么是存儲(chǔ)保護(hù) 在多用戶環(huán)境中，主存儲(chǔ)器按區(qū)分配給各用戶程序使 用。為了互不影響，必須由硬件(軟件配合)保證各用

7、戶 程序只能在給定的存儲(chǔ)區(qū)域內(nèi)活動(dòng)，這種措施叫做存 儲(chǔ)保護(hù)。操作系統(tǒng)的資源管理 (3) 主存管理的功能 第15頁/共61頁17界地址保護(hù)上下界防護(hù) 例：作業(yè)大小為4KB，主存首址為20KB。 mov r1 , 500 123020KB256KB 1存儲(chǔ)空存儲(chǔ)空間間24KB下界寄存器下界寄存器 20KB上 界 寄 存上 界 寄 存器器 24KB設(shè)置上下界寄存器內(nèi)容 ？判斷是否越界 ？ 若 20KBD24KB 允許訪問； 否則發(fā)生越界中斷操作系統(tǒng)的資源管理 (3) 主存管理的功能 第16頁/共61頁18基地址、限長(zhǎng)防護(hù) 例：作業(yè)大小為4KB，主存首址為20KB。設(shè)置基址、限長(zhǎng)寄存器內(nèi)容 ？判斷是否

8、越界 ？ 若 邏輯地址 4KB 允許訪問； 否則發(fā)生越界中斷 mov r1 , 500 123020KB256KB 1存儲(chǔ)空存儲(chǔ)空間間24KB基址寄存器基址寄存器 20KB限 長(zhǎng) 寄 存限 長(zhǎng) 寄 存器器 4KB操作系統(tǒng)的資源管理 (3) 主存管理的功能 第17頁/共61頁19 在處理作業(yè)的過程中，建立分區(qū)，依請(qǐng)求的大小分配分區(qū)。操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第18頁/共61頁20作業(yè)作業(yè)1申請(qǐng)申請(qǐng) 32KB 0 256KB 1主存主存2 0 KBos20KB 0 5 2 KB256KB 1主存主存os作業(yè)1作業(yè)作業(yè)2申請(qǐng)申請(qǐng) 14KB20KB 0 5 2 KB66KB256KB

9、1主存主存os作業(yè)1作業(yè)2作業(yè)作業(yè)3申請(qǐng)申請(qǐng) 64KB2 0 KB 0 52KB66KB130KB256KB 1主存主存os作業(yè)1作業(yè)2作業(yè)3作業(yè)作業(yè)4申請(qǐng)申請(qǐng) 100KB2 0 KB 0 52KB66KB130KB230KB256KB 1主存主存os作業(yè)1作業(yè)2作業(yè)3作業(yè)4作業(yè)作業(yè)5申請(qǐng)申請(qǐng) 50KB操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第19頁/共61頁21作業(yè)作業(yè)2 完成完成 作業(yè)作業(yè)4 完成完成 20KB 0 52KB66KB130KB230KB256KB 1主存主存作 業(yè)1作 業(yè)2作 業(yè)3作 業(yè)4os20KB 0 52KB66KB1 3 0 KB230KB256KB 1主存主存作

10、 業(yè)1作 業(yè)3作 業(yè)4os20KB 0 52KB6 6 KB130KB230KB256KB 1主存主存os作 業(yè)1作 業(yè)3操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第20頁/共61頁22 等待隊(duì)列頭指針 空閑區(qū)隊(duì)列頭指針 主存分配程序入口地址M_RIBflag： 為 0 空閑區(qū) 為 1 已分配區(qū) size： 分區(qū)大小 next：空閑區(qū)自由主存隊(duì)列中的勾鏈字 已分配區(qū)此項(xiàng)為零 分配標(biāo)志 flag 大小 size 勾鏈字 nextPD操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第21頁/共61頁232 0 KB 0 5 2 KB6 6 KB130KB230KB256KB 1主存主存os作業(yè)1作業(yè)3作

11、業(yè)45 2 KBm_rib 空閑區(qū)隊(duì)列空閑區(qū)隊(duì)列230KB01 4 KB02 6 KB 操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第22頁/共61頁24 選擇空閑區(qū)的策略，稱為放置策略。 常用的放置策略 首次匹配(首次適應(yīng)算法) 最佳匹配(最佳適應(yīng)算法) 操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第23頁/共61頁25首次適應(yīng)算法是將輸入的作業(yè)放置到主存里第一個(gè)足 夠裝入它的地址最低的空閑區(qū)中。 作 業(yè)作 業(yè)A 18KB首次適應(yīng)算法的例空閑區(qū)隊(duì)列結(jié)構(gòu) 空閑區(qū)地址由低到高排序 盡可能地利用存儲(chǔ)器中低 地址的空閑區(qū)，而盡量保 存高地址的空閑區(qū)。 在使在使用用在使用在使用在使用在使用30KB5KB4

12、6KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第24頁/共61頁26最佳適應(yīng)算法是將輸入的作業(yè)放置到主存中與它所需 大小最接近的空閑區(qū)中。 作 業(yè)作 業(yè)A 18KB最佳適應(yīng)算法的例空閑區(qū)隊(duì)列結(jié)構(gòu) 空閑區(qū)大小由小到大排序最佳適應(yīng)算法的特點(diǎn) 盡可能地利用存儲(chǔ)器中小的 空閑區(qū)，而盡量保存大的空 閑區(qū)。 在使在使用用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第25頁/共61頁27作業(yè)A要求18

13、KB；作業(yè)B要求25KB；作業(yè)C要求30KB。 用首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法來處理 該作業(yè)序列，看哪種算法合適。 操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第26頁/共61頁28首次適應(yīng)算法、最佳適應(yīng)算法隊(duì)列結(jié)構(gòu) 在使在使用用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os(a) 首次適應(yīng)算法的空閑區(qū)隊(duì)首次適應(yīng)算法的空閑區(qū)隊(duì)列列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB (a) 最佳適應(yīng)算法的空閑區(qū)隊(duì)最佳適應(yīng)算法的空閑區(qū)隊(duì)列列160KB 0 5

14、KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB 操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第27頁/共61頁29首次適應(yīng)算法 作業(yè)A要求18KB，作業(yè)B要求25KB，作業(yè)C要求30KB 首次適應(yīng)算法對(duì)該作業(yè)序列是不合適的 在使在使用用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os(a) 首次適應(yīng)算法的空閑區(qū)隊(duì)首次適應(yīng)算法的空閑區(qū)隊(duì)列列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB 操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第2

15、8頁/共61頁30最佳適應(yīng)算法 在使在使用用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os(a) 最佳適應(yīng)算法的空閑區(qū)隊(duì)最佳適應(yīng)算法的空閑區(qū)隊(duì)列列160KB 0 5KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB 操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 作業(yè)A要求18KB，作業(yè)B要求25KB，作業(yè)C要求30KB 最佳適應(yīng)算法對(duì)該作業(yè)序列是合適的 第29頁/共61頁31在已分配區(qū)之間存在著的一些沒有被充分利用的空閑區(qū) 如何解決碎片問題？如何解決碎片問題？ 所謂拼接技術(shù)是指移動(dòng)存儲(chǔ)器

16、中某些已分配區(qū)中的信息，使本來分散的空閑區(qū)連成一個(gè)大的空閑區(qū)。 20KB 54KB58KB135 KB254KB256KB 1主主存存138KB作業(yè)2 0os作業(yè)3作 業(yè)拼接前20KB 0 5 4 KB1 3 1 KB2 4 7 KB256KB 1主主存存os作 業(yè)作業(yè)2作業(yè)3拼接后操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第30頁/共61頁32 程序的地址空間被等分成 大小相等的片，稱為頁面， 又稱為虛頁。主存被等分成大小相等的片，稱為主存塊，又稱為實(shí)頁。02 KB4KB254KB256KB 102KB4KB6KB0頁1頁2頁3頁主存主存作業(yè)地址空間作業(yè)地址空間操作系統(tǒng)的資源管理 (3) 頁

17、式地址變換 第31頁/共61頁33 為了實(shí)現(xiàn)從地址空間到物理主存的映象，系統(tǒng)建立的 記錄頁與內(nèi)存塊之間對(duì)應(yīng)關(guān)系的地址變換的機(jī)構(gòu)稱為 頁面映像表，簡(jiǎn)稱頁表。高速緩沖存儲(chǔ)器 地址變換速度快，但成本較高主存區(qū)域 地址變換速度比硬件慢，成本較低操作系統(tǒng)的資源管理 (3) 頁式地址變換 第32頁/共61頁3401KB01KB2KB3KB 1主存主存作業(yè)作業(yè)2地址空間地址空間2KB3KB4KB5KB6 KB7 KB8 KB9 KB10KB 101KB2KB 1作業(yè)作業(yè)1地址空地址空間間01KB 1作業(yè)作業(yè)3地址空間地址空間0516頁頁號(hào)號(hào)塊塊號(hào)號(hào)02140827作業(yè)作業(yè)1頁表頁表作業(yè)作業(yè)2頁表頁表作業(yè)作業(yè)

18、3頁表頁表osos操作系統(tǒng)的資源管理 (3) 頁式地址變換 第33頁/共61頁35 記錄頁與塊之間對(duì)應(yīng)關(guān)系的。 當(dāng)CPU給出的虛地址長(zhǎng)度為16位，頁面大小為1KB時(shí)，在分頁系統(tǒng)中地址結(jié)構(gòu)的格式如下： p w15 10 9 0頁號(hào)頁號(hào)P頁內(nèi)位移頁內(nèi)位移Wmov r1 ,250012301KB2KB3KB 1作業(yè)作業(yè)2地址空間地址空間操作系統(tǒng)的資源管理 (3) 頁式地址變換 第34頁/共61頁361頁式地址變換的例 作業(yè)2地址空間中，設(shè)100號(hào)單元處有如下指令： mov r1,2500。當(dāng)這條指令執(zhí)行時(shí)，如何進(jìn)行正確的 地址變換。2500 21024 + 452 p=2 w=45200001001

19、11000100 000010 0111000100mov r1 ,250012301KB2KB3KB 1作業(yè)作業(yè)2地址空間地址空間操作系統(tǒng)的資源管理 (3) 頁式地址變換 第35頁/共61頁37頁式地址變換過程頁表始址寄存頁表始址寄存器器mov r1 ,250012301KB2KB3KB 1作業(yè)作業(yè)2地址空間地址空間+021427頁頁表表 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 015 10 9 0頁號(hào)頁號(hào)P頁內(nèi)位移頁內(nèi)位移W250001 KB主存主存2KB3KB4KB5 KB6 KB7 KB8 KB9KB10KB 1ososmov r1 , 2500123第第1頁頁頁號(hào)

20、頁號(hào)P頁內(nèi)位移頁內(nèi)位移W 15 10 9 00 0 0 1 1 10 1 1 1 0 0 0 1 0 071024+452=7620操作系統(tǒng)的資源管理 (3) 頁式地址變換 第36頁/共61頁38頁式地址變換步驟CPU給出操作數(shù)地址(為2500) ；由分頁機(jī)構(gòu)自動(dòng)地把邏輯地址分為兩部分，得到頁 號(hào)p和頁內(nèi)相對(duì)位移w (p =2， w =452)；根據(jù)頁表始址寄存器指示的頁表始地址，以頁號(hào)為 索引，找到第2頁所對(duì)應(yīng)的塊號(hào)(為7) ；將塊號(hào)b和頁內(nèi)位移量w拼接在一起，就形成了訪問 主存的物理地址 (71024+452=7620)操作系統(tǒng)的資源管理 (3) 頁式地址變換 第37頁/共61頁39什么是

21、聯(lián)想存儲(chǔ)器 高速、小容量半導(dǎo)體存儲(chǔ)部件，又稱緩沖存儲(chǔ)器快表 在緩沖存儲(chǔ)器中存放正在運(yùn)行的進(jìn)程當(dāng)前用到的頁號(hào) 和對(duì)應(yīng)的塊號(hào)，又稱為快表。操作系統(tǒng)的資源管理 (3) 頁式地址變換 第38頁/共61頁40利用快表進(jìn)行地址映射 a + P w 僅在聯(lián)想映像不匹配時(shí)進(jìn)行僅在聯(lián)想映像不匹配時(shí)進(jìn)行頁號(hào)頁號(hào) b w首首先先選選擇擇聯(lián)想存儲(chǔ)器聯(lián)想存儲(chǔ)器所有頁表在主存中所有頁表在主存中物理地址物理地址pbba+pa操作系統(tǒng)的資源管理 (3) 頁式地址變換 第39頁/共61頁41 頁號(hào)頁號(hào) 主存塊號(hào)主存塊號(hào) 中斷位中斷位 輔存地址輔存地址中斷位I 標(biāo)識(shí)該頁是否在主存 若i=1，表示此頁不在主存；若i=0，表示該頁在

22、主存輔存地址 該頁面在輔存的位置操作系統(tǒng)的資源管理 (3) 請(qǐng)求頁面的機(jī)制 裝入一個(gè)作業(yè)的全部頁面才能投入運(yùn)行裝入一個(gè)作業(yè)的部分頁面即可投入運(yùn)行 第40頁/共61頁42作業(yè)2在請(qǐng)求分頁系統(tǒng)中的存儲(chǔ)映像01 KB2 KB4KB 1作業(yè)作業(yè)2地址空地址空間間mov r1,2120add r1,3410006251 006802 3 KB01KB主存主存2KB3KB4KB5KB6KB7KB8KB9KB10KB 102142作業(yè)作業(yè)2頁頁表表osos作業(yè)2 第 1頁作業(yè)2 第 0頁3頁號(hào)頁號(hào) 輔存地址輔存地址 中斷位中斷位 塊號(hào)塊號(hào) 0011地址地址地址地址操作系統(tǒng)的資源管理 (3) 請(qǐng)求頁面的機(jī)制

23、第41頁/共61頁43缺頁處理的例 作業(yè)2的主存塊數(shù)為 m2=3，討論程序執(zhí)行 “mov r1，2120”指令時(shí)的情況。CPU產(chǎn)生的虛地址為2120分頁機(jī)構(gòu)得 p=2，w=72查頁表。該頁中斷位i=1發(fā)生缺頁中斷 ！ 如主存中有空白塊，且nm 則直接調(diào)入如主存中無空白塊，或n m ，則需淘汰該作業(yè)在主存中的一頁01 KB2 KB4KB 1作業(yè)作業(yè)2地址空地址空間間mov r1,2120add r1,3410006251 006802 3 KB操作系統(tǒng)的資源管理 (3) 請(qǐng)求頁面的機(jī)制 第42頁/共61頁44缺頁處理 啟動(dòng)要處理的指令啟動(dòng)要處理的指令給出虛地址給出虛地址 得到頁號(hào)得到頁號(hào)該頁在主

24、存該頁在主存?有空閑塊有空閑塊? 缺頁中斷缺頁中斷執(zhí) 行 完 該 指執(zhí) 行 完 該 指令令 準(zhǔn)備執(zhí)行下條指令準(zhǔn)備執(zhí)行下條指令選一頁淘汰選一頁淘汰 從外存讀入所需的頁從外存讀入所需的頁 調(diào)整存儲(chǔ)分配表和頁表調(diào)整存儲(chǔ)分配表和頁表 重新啟動(dòng)被中斷的指令重新啟動(dòng)被中斷的指令 調(diào)整存儲(chǔ)分配表和頁調(diào)整存儲(chǔ)分配表和頁表表要重寫入要重寫入?該頁寫入外存該頁寫入外存YNNY硬件硬件軟件軟件YN操作系統(tǒng)的資源管理 (3) 請(qǐng)求頁面的機(jī)制 第43頁/共61頁45 用來選擇淘汰哪一頁的規(guī)則叫做置換策略，或稱淘汰算法。引用位 標(biāo)識(shí)該頁最近是否被訪問 為“0” 該頁沒有被訪問；為“1” 該頁已被訪問改變位 表示該頁是否被

25、修改 為“0” 該頁未被修改；為“1” 該頁已被修改 頁頁 號(hào)號(hào) 主存塊號(hào)主存塊號(hào) 中斷位中斷位 輔存地址輔存地址 引用位引用位 改變位改變位操作系統(tǒng)的資源管理 (3) 淘汰機(jī)制與策略 第44頁/共61頁46顛簸 顛簸(thrashing)，又稱為“抖動(dòng)”。 簡(jiǎn)單地說，導(dǎo)致系統(tǒng)效率急劇下降的主存和輔存之間的 頻繁頁面置換現(xiàn)像稱為“抖動(dòng)”。缺頁中斷率假定程序p共有n頁，系統(tǒng)分配m塊，有 1mn； 若程序p在運(yùn)行中：成功的訪問次數(shù)為s，不成功的訪 問次數(shù)為f；缺頁中斷率： f=f/ (s+ f) f= f (r，m，p)； r：置換算法； p：程序特征； m：系統(tǒng)分配的塊數(shù)操作系統(tǒng)的資源管理 (3

26、) 淘汰機(jī)制與策略 第45頁/共61頁47最佳算法(OPT算法) 當(dāng)要調(diào)入一新頁而必須先淘汰一舊頁時(shí)，所淘汰的那一頁應(yīng)是以 后不再要用的，或者是在最長(zhǎng)的時(shí)間以后才會(huì)用到的那頁。 先進(jìn)先出淘汰算法(FIFO算法) 什么是先進(jìn)先出淘汰算法 總是選擇在主存中居留時(shí)間最長(zhǎng)(即最早進(jìn)入主存)的一頁淘汰。先進(jìn)先出淘汰算法的實(shí)現(xiàn)建立一個(gè)頁面進(jìn)入主存的先后次序表；建立一個(gè)替換指針，指向最早進(jìn)入主存的頁面；當(dāng)需要置換一頁時(shí)，選擇替換指向的那一頁，然后調(diào)整替換指 針的內(nèi)容。操作系統(tǒng)的資源管理 (3) 淘汰機(jī)制與策略 第46頁/共61頁48頁號(hào)表 頁面進(jìn)入主存的先后次序： 2451 替換指針 指向最老的一頁頁號(hào) 2

27、 4 5 16 當(dāng)要調(diào)入第6頁時(shí)：置換第2頁將第2頁改為6替換指針指向第4頁 操作系統(tǒng)的資源管理 (3) 淘汰機(jī)制與策略 第47頁/共61頁49在存儲(chǔ)分塊表中建立次序表 頁面進(jìn)入主存的先后次序： 4512 當(dāng)要調(diào)入第6頁時(shí)： 如何處理 ? 512 67102345642516 74 2替換指針替換指針塊號(hào)塊號(hào) 頁號(hào)頁號(hào) 指針指針710234566251 274 6替換指針替換指針 塊號(hào)塊號(hào) 頁號(hào)頁號(hào) 指針指針操作系統(tǒng)的資源管理 (3) 淘汰機(jī)制與策略 第48頁/共61頁50最久未使用淘汰算法(LRU算法)什么是最久未使用淘汰算法 總是選擇最長(zhǎng)時(shí)間未被使用的那一頁淘汰。最久未使用淘汰算法的實(shí)現(xiàn)用

28、引用位考察頁面的使用情況；當(dāng)訪問頁面時(shí)，將引用位置1，并記時(shí)；當(dāng)要淘汰一頁時(shí)，選擇時(shí)間最長(zhǎng)的一頁淘汰。 要精確實(shí)現(xiàn)很困難硬件方法：采用計(jì)數(shù)器軟件方法：采用頁號(hào)棧操作系統(tǒng)的資源管理 (3) 淘汰機(jī)制與策略 第49頁/共61頁51用頁號(hào)棧實(shí)現(xiàn)LRU算法 頁面訪問軌跡：451 2 5 64512訪問第訪問第5頁頁 訪問第訪問第6頁頁 淘汰第淘汰第4頁頁 41251256訪問4、5、1、2頁后棧的內(nèi)容 訪問第5頁后，調(diào)整棧的內(nèi)容 訪問第6頁后，棧的內(nèi)容 操作系統(tǒng)的資源管理 (3) 淘汰機(jī)制與策略 第50頁/共61頁52LRU近似算法 (使用引用位)框圖 入口入口讀出替換指針指向的塊號(hào)讀出替換指針指向的

29、塊號(hào)移動(dòng)指針指向下一個(gè)存儲(chǔ)塊移動(dòng)指針指向下一個(gè)存儲(chǔ)塊 引用位為引用位為0 ?選擇該頁淘汰，記錄該頁的頁號(hào)選擇該頁淘汰，記錄該頁的頁號(hào)、塊號(hào)、塊號(hào)將該頁所在的將該頁所在的塊號(hào)送到塊號(hào)送到替換指針替換指針返回返回置引用位為置引用位為0YN操作系統(tǒng)的資源管理 (3) 淘汰機(jī)制與策略 第51頁/共61頁53LRU近似算法舉例7102345642514172 4替換指針替換指針 塊號(hào)塊號(hào) 頁號(hào)頁號(hào) 引用位引用位 指針指針60017102345642564072 7替換指針替換指針 塊號(hào)塊號(hào) 頁號(hào)頁號(hào) 引用位引用位 指針指針6011當(dāng)要調(diào)入第當(dāng)要調(diào)入第6頁時(shí)，如何處理頁時(shí)，如何處理 ?操作系統(tǒng)的資源管理 (3) 淘汰機(jī)制與策略 第52頁/共61頁54 分段是程序中自然劃分的一組邏輯意義完整的信息集合。 分段的例：代碼分段、數(shù)據(jù)分段、棧段頁。 由若干個(gè)邏輯分段組成，每個(gè)分段有自己的名字，對(duì)于一個(gè)分段而 言，它是一個(gè)連續(xù)的地址區(qū)。c