1、會計學(xué)1存儲管理存儲管理操作系統(tǒng)的資源管理 (3) 主存管理 2第1頁/共61頁3操作系統(tǒng)的資源管理 (3) 主要內(nèi)容 第2頁/共61頁4分區(qū)存儲管理段式存儲管理操作系統(tǒng)的資源管理 (3) 主存管理的功能 頁式存儲管理段頁式存儲管理一個程序是一個連續(xù)、線性的地址結(jié)構(gòu)；確定線性地址空間中的指令地址或操作數(shù)地址只需要一個信息。 程序地址空間程序地址空間01 n-1 第3頁/共61頁5一個程序由若干個分段組成，每個分段是一個連續(xù)的地址區(qū)；確定任一線性地址空間中的指令地址或操作數(shù)地址需要兩個信息，一是該信息所在的分段，另一個是該信息在段內(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ī)主存單元的真實(shí)地址，又稱為絕對地址或?qū)嵉刂贰?物理地址的集合所對應(yīng)的空間組成了主存空間。 用戶的程序地址(指令地址或操作數(shù)地址)均為邏輯地址。 用戶程序所有的邏輯地址集合對應(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存儲空間存儲空間操作系統(tǒng)的資源管理 (3) 主存管理的功能 第8頁/共61頁10靜態(tài)地址映射 在作業(yè)裝入過程中隨即進(jìn)行的地址變換方式稱為靜態(tài) 地址映射。mov r1,500mov r1,500+m01005005990mm+100256k-1作業(yè)地址空間作業(yè)地址空間存儲空間存儲空間m+500重定位重定位裝入程序裝入程序12312

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

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

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

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

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

9、1主存主存os作業(yè)1作業(yè)2作業(yè)作業(yè)3申請申請 64KB2 0 KB 0 52KB66KB130KB256KB 1主存主存os作業(yè)1作業(yè)2作業(yè)3作業(yè)作業(yè)4申請申請 100KB2 0 KB 0 52KB66KB130KB230KB256KB 1主存主存os作業(yè)1作業(yè)2作業(yè)3作業(yè)4作業(yè)作業(yè)5申請申請 50KB操作系統(tǒng)的資源管理 (3) 分區(qū)存儲管理 第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ū)存儲管理 第20頁/共61頁22 等待隊列頭指針 空閑區(qū)隊列頭指針 主存分配程序入口地址M_RIBflag： 為 0 空閑區(qū) 為 1 已分配區(qū) size： 分區(qū)大小 next：空閑區(qū)自由主存隊列中的勾鏈字 已分配區(qū)此項為零 分配標(biāo)志 flag 大小 size 勾鏈字 nextPD操作系統(tǒng)的資源管理 (3) 分區(qū)存儲管理 第21頁/共61頁232 0 KB 0 5 2 KB6 6 KB130KB230KB256KB 1主存主存os作業(yè)1作業(yè)3作

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

12、6KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os操作系統(tǒng)的資源管理 (3) 分區(qū)存儲管理 第24頁/共61頁26最佳適應(yīng)算法是將輸入的作業(yè)放置到主存中與它所需 大小最接近的空閑區(qū)中。 作 業(yè)作 業(yè)A 18KB最佳適應(yīng)算法的例空閑區(qū)隊列結(jié)構(gòu) 空閑區(qū)大小由小到大排序最佳適應(yīng)算法的特點(diǎn) 盡可能地利用存儲器中小的 空閑區(qū)，而盡量保存大的空 閑區(qū)。 在使在使用用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os操作系統(tǒng)的資源管理 (3) 分區(qū)存儲管理 第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ū)存儲管理 第26頁/共61頁28首次適應(yīng)算法、最佳適應(yīng)算法隊列結(jié)構(gòu) 在使在使用用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os(a) 首次適應(yīng)算法的空閑區(qū)隊首次適應(yīng)算法的空閑區(qū)隊列列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB (a) 最佳適應(yīng)算法的空閑區(qū)隊最佳適應(yīng)算法的空閑區(qū)隊列列160KB 0 5

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

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

16、中某些已分配區(qū)中的信息，使本來分散的空閑區(qū)連成一個大的空閑區(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ū)存儲管理 第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)存塊之間對應(yīng)關(guān)系的地址變換的機(jī)構(gòu)稱為 頁面映像表，簡稱頁表。高速緩沖存儲器 地址變換速度快，但成本較高主存區(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頁頁號號塊塊號號02140827作業(yè)作業(yè)1頁表頁表作業(yè)作業(yè)2頁表頁表作業(yè)作業(yè)

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

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

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

22、主存輔存地址 該頁面在輔存的位置操作系統(tǒng)的資源管理 (3) 請求頁面的機(jī)制 裝入一個作業(yè)的全部頁面才能投入運(yùn)行裝入一個作業(yè)的部分頁面即可投入運(yùn)行 第40頁/共61頁42作業(yè)2在請求分頁系統(tǒng)中的存儲映像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頁號頁號 輔存地址輔存地址 中斷位中斷位 塊號塊號 0011地址地址地址地址操作系統(tǒng)的資源管理 (3) 請求頁面的機(jī)制

23、第41頁/共61頁43缺頁處理的例 作業(yè)2的主存塊數(shù)為 m2=3，討論程序執(zhí)行 “mov r1，2120”指令時的情況。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) 請求頁面的機(jī)制 第42頁/共61頁44缺頁處理 啟動要處理的指令啟動要處理的指令給出虛地址給出虛地址 得到頁號得到頁號該頁在主

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

25、修改 為“0” 該頁未被修改；為“1” 該頁已被修改 頁頁 號號 主存塊號主存塊號 中斷位中斷位 輔存地址輔存地址 引用位引用位 改變位改變位操作系統(tǒng)的資源管理 (3) 淘汰機(jī)制與策略 第44頁/共61頁46顛簸 顛簸(thrashing)，又稱為“抖動”。 簡單地說，導(dǎo)致系統(tǒng)效率急劇下降的主存和輔存之間的 頻繁頁面置換現(xiàn)像稱為“抖動”。缺頁中斷率假定程序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)入一新頁而必須先淘汰一舊頁時，所淘汰的那一頁應(yīng)是以 后不再要用的，或者是在最長的時間以后才會用到的那頁。 先進(jìn)先出淘汰算法(FIFO算法) 什么是先進(jìn)先出淘汰算法 總是選擇在主存中居留時間最長(即最早進(jìn)入主存)的一頁淘汰。先進(jìn)先出淘汰算法的實(shí)現(xiàn)建立一個頁面進(jìn)入主存的先后次序表；建立一個替換指針，指向最早進(jìn)入主存的頁面；當(dāng)需要置換一頁時，選擇替換指向的那一頁，然后調(diào)整替換指 針的內(nèi)容。操作系統(tǒng)的資源管理 (3) 淘汰機(jī)制與策略 第46頁/共61頁48頁號表 頁面進(jìn)入主存的先后次序： 2451 替換指針 指向最老的一頁頁號 2

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

28、引用位考察頁面的使用情況；當(dāng)訪問頁面時，將引用位置1，并記時；當(dāng)要淘汰一頁時，選擇時間最長的一頁淘汰。 要精確實(shí)現(xiàn)很困難硬件方法：采用計數(shù)器軟件方法：采用頁號棧操作系統(tǒng)的資源管理 (3) 淘汰機(jī)制與策略 第49頁/共61頁51用頁號棧實(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近似算法 (使用引用位)框圖 入口入口讀出替換指針指向的塊號讀出替換指針指向的

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