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

1、會(huì)計(jì)學(xué)1存儲(chǔ)管理存儲(chǔ)管理操作系統(tǒng)的資源管理 (3) 主存管理 2第1頁(yè)/共61頁(yè)3操作系統(tǒng)的資源管理 (3) 主要內(nèi)容 第2頁(yè)/共61頁(yè)4分區(qū)存儲(chǔ)管理段式存儲(chǔ)管理操作系統(tǒng)的資源管理 (3) 主存管理的功能 頁(yè)式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理一個(gè)程序是一個(gè)連續(xù)、線性的地址結(jié)構(gòu)；確定線性地址空間中的指令地址或操作數(shù)地址只需要一個(gè)信息。 程序地址空間程序地址空間01 n-1 第3頁(yè)/共61頁(yè)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頁(yè)/共61頁(yè)6 物理地址是計(jì)算機(jī)主存單元的真實(shí)地址，又稱為絕對(duì)地址或?qū)嵉刂贰?物理地址的集合所對(duì)應(yīng)的空間組成了主存空間。 用戶的程序地址(指令地址或操作數(shù)地址)均為邏輯地址。 用戶程序所有的邏輯地址集合對(duì)應(yīng)的空間。操作系統(tǒng)的資源管理 (3) 主存管理的功能 第5頁(yè)/共61頁(yè)7主存空間主存空間01m-1作業(yè)作業(yè)1地址空地址空間間01n-1作業(yè)作業(yè) i 地址空地址空間間01k-1 操作系統(tǒng)的資源管理 (3) 主存管理的功能 第6頁(yè)/共61頁(yè)8操作系統(tǒng)的資源管理 (3)

3、 主存管理的功能 第7頁(yè)/共61頁(yè)9什么是地址映射 將程序地址空間中使用的邏輯地址變換成主存中的物 理地址的過(guò)程，稱為地址映射。mov r1,5001230100500599作業(yè)地址空間作業(yè)地址空間mov r1,50012301000110015001599256k-1存儲(chǔ)空間存儲(chǔ)空間操作系統(tǒng)的資源管理 (3) 主存管理的功能 第8頁(yè)/共61頁(yè)10靜態(tài)地址映射 在作業(yè)裝入過(guò)程中隨即進(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頁(yè)/共61頁(yè)11動(dòng)態(tài)地址映射 在程序執(zhí)行期間，隨著每條指令和數(shù)據(jù)的訪問(wèn)自動(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頁(yè)/共61頁(yè)12靜態(tài)地址映射與動(dòng)態(tài)地址映射的區(qū)別靜態(tài)地址映射 動(dòng)態(tài)地址映射 操作系統(tǒng)的資源管理 (3) 主存管理的功能 第11頁(yè)/共61頁(yè)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)入主存淘汰策略在主存中沒(méi)有可用的空閑區(qū)(對(duì)某一作業(yè)而言)時(shí)，決定哪些信息從主存中移走，即確定淘汰已占用的內(nèi)存區(qū)的原則。實(shí)施主存分配與回收操作系統(tǒng)的資源管理 (3) 主存管理的功能 第12頁(yè)/共61頁(yè)14實(shí)現(xiàn)方法程序的全部代碼和數(shù)據(jù)存放在輔存中；將程序當(dāng)前執(zhí)行所涉及的那部分程序代碼放入主存中；程序執(zhí)行時(shí)，當(dāng)所需信息不在主存，由操作系統(tǒng)和硬件相配合來(lái)完成主存從輔存中調(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頁(yè)/共61頁(yè)15虛擬存儲(chǔ)器的核心邏輯地址與物理地址分開(kāi)存儲(chǔ)空間與虛地址空間分開(kāi)提供地址變換機(jī)構(gòu)實(shí)現(xiàn)虛擬存儲(chǔ)器的物質(zhì)基礎(chǔ)有相當(dāng)容量的輔存 足以存放應(yīng)用程序的虛地址空間有一定容量的主存 存放進(jìn)入主存的多進(jìn)程的信息地址變換機(jī)構(gòu) 操作系統(tǒng)的資源管理 (3) 主存管理的功能 第14頁(yè)/共61頁(yè)16什么是存儲(chǔ)保護(hù) 在多用戶環(huán)境中，主存儲(chǔ)器按區(qū)分配給各用戶程序使 用。為了互不影響，必須由硬件(軟件配合)保證各用

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

8、越界 ？ 若 邏輯地址 4KB 允許訪問(wèn)； 否則發(fā)生越界中斷 mov r1 , 500 123020KB256KB 1存儲(chǔ)空存儲(chǔ)空間間24KB基址寄存器基址寄存器 20KB限 長(zhǎng) 寄 存限 長(zhǎng) 寄 存器器 4KB操作系統(tǒng)的資源管理 (3) 主存管理的功能 第17頁(yè)/共61頁(yè)19 在處理作業(yè)的過(guò)程中，建立分區(qū)，依請(qǐng)求的大小分配分區(qū)。操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第18頁(yè)/共61頁(yè)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頁(yè)/共61頁(yè)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頁(yè)/共61頁(yè)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頁(yè)/共61頁(yè)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頁(yè)/共61頁(yè)24 選擇空閑區(qū)的策略，稱為放置策略。 常用的放置策略 首次匹配(首次適應(yīng)算法) 最佳匹配(最佳適應(yīng)算法) 操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第23頁(yè)/共61頁(yè)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頁(yè)/共61頁(yè)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頁(yè)/共61頁(yè)27作業(yè)A要求18

13、KB；作業(yè)B要求25KB；作業(yè)C要求30KB。 用首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法來(lái)處理 該作業(yè)序列，看哪種算法合適。 操作系統(tǒng)的資源管理 (3) 分區(qū)存儲(chǔ)管理 第26頁(yè)/共61頁(yè)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頁(yè)/共61頁(yè)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頁(yè)/共61頁(yè)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頁(yè)/共61頁(yè)31在已分配區(qū)之間存在著的一些沒(méi)有被充分利用的空閑區(qū) 如何解決碎片問(wèn)題？如何解決碎片問(wèn)題？ 所謂拼接技術(shù)是指移動(dòng)存儲(chǔ)器

16、中某些已分配區(qū)中的信息，使本來(lái)分散的空閑區(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頁(yè)/共61頁(yè)32 程序的地址空間被等分成 大小相等的片，稱為頁(yè)面， 又稱為虛頁(yè)。主存被等分成大小相等的片，稱為主存塊，又稱為實(shí)頁(yè)。02 KB4KB254KB256KB 102KB4KB6KB0頁(yè)1頁(yè)2頁(yè)3頁(yè)主存主存作業(yè)地址空間作業(yè)地址空間操作系統(tǒng)的資源管理 (3) 頁(yè)

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

18、3頁(yè)表頁(yè)表osos操作系統(tǒng)的資源管理 (3) 頁(yè)式地址變換 第33頁(yè)/共61頁(yè)35 記錄頁(yè)與塊之間對(duì)應(yīng)關(guān)系的。 當(dāng)CPU給出的虛地址長(zhǎng)度為16位，頁(yè)面大小為1KB時(shí)，在分頁(yè)系統(tǒng)中地址結(jié)構(gòu)的格式如下： p w15 10 9 0頁(yè)號(hào)頁(yè)號(hào)P頁(yè)內(nèi)位移頁(yè)內(nèi)位移Wmov r1 ,250012301KB2KB3KB 1作業(yè)作業(yè)2地址空間地址空間操作系統(tǒng)的資源管理 (3) 頁(yè)式地址變換 第34頁(yè)/共61頁(yè)361頁(yè)式地址變換的例 作業(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) 頁(yè)式地址變換 第35頁(yè)/共61頁(yè)37頁(yè)式地址變換過(guò)程頁(yè)表始址寄存頁(yè)表始址寄存器器mov r1 ,250012301KB2KB3KB 1作業(yè)作業(yè)2地址空間地址空間+021427頁(yè)頁(yè)表表 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 015 10 9 0頁(yè)號(hào)頁(yè)號(hào)P頁(yè)內(nèi)位移頁(yè)內(nèi)位移W250001 KB主存主存2KB3KB4KB5 KB6 KB7 KB8 KB9KB10KB 1ososmov r1 , 2500123第第1頁(yè)頁(yè)頁(yè)號(hào)

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

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

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

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

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

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

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

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

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

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