計(jì)算機(jī)操作系統(tǒng)李翠霞o(jì)s45

1、第四章 存儲器管理主講：李翠霞主講：李翠霞辦公室：水環(huán)樓辦公室：水環(huán)樓306306電話：電話：0371-638872910371-63887291e-mail:e-mail:b頁表頁表地址越界地址越界l比較比較plpb. . .快表快表頁表始址+頁號頁號p p 頁內(nèi)地址頁內(nèi)地址wbw物理地址物理地址頁表地址寄存器頁表地址寄存器頁表長度寄存器頁表長度寄存器邏輯地址具有快表的地址映射機(jī)構(gòu)具有快表的地址映射機(jī)構(gòu) 解決頁表需要連續(xù)空間問題解決頁表需要連續(xù)空間問題- -對頁表進(jìn)行離散分配對頁表進(jìn)行離散分配如：以如：以4k4k為單位劃分頁面和內(nèi)存塊，若邏輯地址為為單位劃分頁面和內(nèi)存塊，若邏輯地址為3232

2、位，則用單級頁表時位，則用單級頁表時頁表的表項(xiàng)數(shù)：頁表的表項(xiàng)數(shù)：2 22020=1024=10241024=1m1024=1m； 每個表項(xiàng)占每個表項(xiàng)占4 4個字節(jié)個字節(jié)頁表長為：頁表長為：4m4m在內(nèi)存中難以找到在內(nèi)存中難以找到4m4m的連續(xù)空間的連續(xù)空間可類比為：頁表登記了各位同學(xué)的宿舍號，如果班里同學(xué)只有可類比為：頁表登記了各位同學(xué)的宿舍號，如果班里同學(xué)只有2020人，則一人，則一頁頁a4a4紙即可登記完畢。假如登記全院紙即可登記完畢。假如登記全院1 1萬名同學(xué)的宿舍號信息，此時可能萬名同學(xué)的宿舍號信息，此時可能需要一張很長的表格?？山梃b兩級頁表的策略，先將同學(xué)分成每需要一張很長的表格?？?/p>

3、借鑒兩級頁表的策略，先將同學(xué)分成每2020位一組，位一組，一張紙上一張紙上2020行，行，1 1萬名同學(xué)需要萬名同學(xué)需要50005000頁紙。這頁紙。這50005000頁紙可放在不同的若干檔頁紙可放在不同的若干檔案格中。又有一張登記表記下了每組所在的檔案盒號（外層頁表）。案格中。又有一張登記表記下了每組所在的檔案盒號（外層頁表）。兩級頁表兩級頁表012n1460121023114115012102314680121023012435671141151468第第0 0頁頁表頁頁表第第1 1頁頁表頁頁表第第n n頁頁表頁頁表兩級頁表兩級頁表.外部頁表寄存器外部頁表寄存器外部頁表外部頁表頁表頁表外部

4、頁號外部頁號外部頁內(nèi)地址外部頁內(nèi)地址頁內(nèi)地址頁內(nèi)地址p1p1p2p2d dd db b邏輯地址邏輯地址采用兩級時，指令所給出的地址分為三部分：采用兩級時，指令所給出的地址分為三部分： 外層頁號內(nèi)層頁號外層頁號內(nèi)層頁號 偏移地址。偏移地址。1010位位 1010位位 1212位位如上頁圖所示的兩級頁表結(jié)構(gòu)。假如邏輯地址空間為如上頁圖所示的兩級頁表結(jié)構(gòu)。假如邏輯地址空間為2 23232，請問，請問邏輯地址邏輯地址00401b21h00401b21h所對應(yīng)的物理地址為？所對應(yīng)的物理地址為？00073b21h00073b21h分析過程分析過程外層頁號內(nèi)層頁號外層頁號內(nèi)層頁號 偏移地址偏移地址 10位位

5、 10位位 12位位00401b21h可分割為可分割為0000 0000 01 00 0000 0001 1011 0010 0001得物理塊號得物理塊號1150000 0000 0000 0111 0011對應(yīng)的物理地址為：對應(yīng)的物理地址為：0000 0000 00 00 0111 0011 1011 0010 000100073b21h00073b21h假設(shè)：有主程序段假設(shè)：有主程序段mainmain、子程序段、子程序段x x，數(shù)據(jù)段，數(shù)據(jù)段d d及棧段及棧段s s等。等。則利用段表可實(shí)現(xiàn)地址映射（則利用段表可實(shí)現(xiàn)地址映射（p137 p137 圖圖4-174-17）：）：作業(yè)空間作業(yè)空間（

6、mainmain）=0=0（x x）=0=0（d d）=2=2（s s）=3=3030k20k015k010k030k40k20k80k15k 120k10k 150k段號段號段長段長基址基址0123(main)=030k(x)=120k(d)=215k(s)=310k內(nèi)存空間內(nèi)存空間040k80k120k150k3. 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)1k 6k600 4k500 8k 200 92008k82928692段號段號 段長段長 基址基址0123段表寄存器段表寄存器段表基址段表基址段表長度段表長度 段號段號s s 段內(nèi)偏移段內(nèi)偏移d d2100物理地址物理地址內(nèi)內(nèi)存存段表段表越界越界829

7、24.5.4 4.5.4 段頁式存儲管理方式段頁式存儲管理方式段表大小段表大小段表始址段表始址段號段號狀態(tài)狀態(tài) 頁表大小頁表大小頁表始址頁表始址頁號頁號狀態(tài)狀態(tài) 存儲塊存儲塊#操作系統(tǒng)操作系統(tǒng)主存主存段表寄存器段表寄存器0111213001112130414.5.4 4.5.4 段頁式存儲管理方式段頁式存儲管理方式段表大小段表大小段表始址段表始址段號段號狀態(tài)狀態(tài) 頁表大小頁表大小頁表始址頁表始址頁號頁號 存儲塊存儲塊#頁號頁號 存儲塊存儲塊#段表寄存器段表寄存器015112142010h300218213054031624372010h若某系統(tǒng)采用段頁式若某系統(tǒng)采用段頁式存儲管理方式，段表存儲

8、管理方式，段表和部分段的分頁情況和部分段的分頁情況如圖所示，頁面大小如圖所示，頁面大小為為1kb1kb。請問邏輯地。請問邏輯地址（址（2 2，25002500）對應(yīng)）對應(yīng)的物理地址是多少？的物理地址是多少？ 根據(jù)段號查得根據(jù)段號查得2 2號段號段的頁表地址為的頁表地址為2010h2010h，可到內(nèi)存可到內(nèi)存2010h2010h地址地址處讀得該段的頁表。處讀得該段的頁表。 int int（2500/10242500/1024）=2=22500 mod 1024=4522500 mod 1024=452 可得物理地址為：可得物理地址為：10241024* *4+452=4096+452=45484

9、+452=4096+452=4548本章主要內(nèi)容本章主要內(nèi)容4.1 4.1 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu)4.2 4.2 程序的裝入和鏈接程序的裝入和鏈接4.3 4.3 連續(xù)分配方式連續(xù)分配方式4.4 4.4 基本分頁存儲管理方式基本分頁存儲管理方式4.5 4.5 基本分段存儲管理方式基本分段存儲管理方式4.6 4.6 虛擬存儲器的基本概念虛擬存儲器的基本概念4.7 4.7 請求分頁存儲管理方式請求分頁存儲管理方式4.8 4.8 頁面置換算法頁面置換算法4.9 4.9 請求分段存儲管理方式請求分段存儲管理方式4.6 4.6 虛擬存儲器的基本概念虛擬存儲器的基本概念產(chǎn)生的原因：產(chǎn)生的原因：連續(xù)

10、分配、基本分頁和基本分段存儲管理方式都要求連續(xù)分配、基本分頁和基本分段存儲管理方式都要求將一個作業(yè)全部裝入內(nèi)存后方能運(yùn)行，于是，會出現(xiàn)：將一個作業(yè)全部裝入內(nèi)存后方能運(yùn)行，于是，會出現(xiàn)：1) 1) 作業(yè)很大，需求總?cè)萘砍^了內(nèi)存總?cè)萘?。會因不能全部裝入內(nèi)作業(yè)很大，需求總?cè)萘砍^了內(nèi)存總?cè)萘俊虿荒苋垦b入內(nèi)存而導(dǎo)致該作業(yè)無法運(yùn)行。存而導(dǎo)致該作業(yè)無法運(yùn)行。2) 2) 有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有作業(yè)，只有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存讓它們運(yùn)行，大量作業(yè)留在外存上等待。能將少數(shù)作業(yè)裝入內(nèi)存讓它們運(yùn)行，大量作業(yè)留在外存上等待。解決的辦

11、法：解決的辦法：從物理上增加內(nèi)存容量從物理上增加內(nèi)存容量受機(jī)器自身的限制，增加系統(tǒng)成本受機(jī)器自身的限制，增加系統(tǒng)成本從邏輯上擴(kuò)充內(nèi)存容量從邏輯上擴(kuò)充內(nèi)存容量用用虛擬存儲器技術(shù)虛擬存儲器技術(shù)解決解決4.6 4.6 虛擬存儲器的基本概念虛擬存儲器的基本概念常規(guī)存儲管理方式的特征：常規(guī)存儲管理方式的特征：一次性一次性 作業(yè)在運(yùn)行前需一次性地全部裝入內(nèi)存。作業(yè)每次運(yùn)行作業(yè)在運(yùn)行前需一次性地全部裝入內(nèi)存。作業(yè)每次運(yùn)行時，并非全部程序和數(shù)據(jù)都要用到，如果全部裝入，造成了對內(nèi)時，并非全部程序和數(shù)據(jù)都要用到，如果全部裝入，造成了對內(nèi)存空間的浪費(fèi)。存空間的浪費(fèi)。駐留性駐留性 作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，

12、直至運(yùn)行結(jié)束。作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至運(yùn)行結(jié)束。盡管有的進(jìn)程會因等待盡管有的進(jìn)程會因等待i/oi/o而長期等待，或有的程序模塊在運(yùn)行而長期等待，或有的程序模塊在運(yùn)行過一次后就不再需要了，但它們都仍繼續(xù)占用寶貴的內(nèi)存資源。過一次后就不再需要了，但它們都仍繼續(xù)占用寶貴的內(nèi)存資源。一次性和駐留性是必需的嗎？一次性和駐留性是必需的嗎？一一. . 局部性原理局部性原理1. 1. 局部性原理：局部性原理： 指程序在執(zhí)行過程中的一個較短時間內(nèi)，所執(zhí)行的指指程序在執(zhí)行過程中的一個較短時間內(nèi)，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域?？梢粤畹刂泛椭噶畹牟僮鲾?shù)地址，分別局限于一定區(qū)域

13、?？梢员憩F(xiàn)為：表現(xiàn)為：1) 1) 時間局部性：一個數(shù)據(jù)結(jié)構(gòu)或指令在有限時間內(nèi)再次被時間局部性：一個數(shù)據(jù)結(jié)構(gòu)或指令在有限時間內(nèi)再次被訪問訪問. .2) 2) 空間局部性：一個區(qū)域再次被訪問空間局部性：一個區(qū)域再次被訪問. .4.6 4.6 虛擬存儲器的基本概念虛擬存儲器的基本概念19681968年，年，denning.pdenning.p提出了局部性原理，為虛擬存儲技術(shù)提出了局部性原理，為虛擬存儲技術(shù)的發(fā)展奠定了理論基礎(chǔ)。的發(fā)展奠定了理論基礎(chǔ)。2 2、局部性原理的具體體現(xiàn)、局部性原理的具體體現(xiàn)程序在執(zhí)行時，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)程序在執(zhí)行時，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)移和過程

14、調(diào)用指令。移和過程調(diào)用指令。過程調(diào)用的嵌套深度一般不超過過程調(diào)用的嵌套深度一般不超過5 5，因此執(zhí)行的范圍不超，因此執(zhí)行的范圍不超過這組嵌套的過程。過這組嵌套的過程。程序中存在相當(dāng)多的循環(huán)結(jié)構(gòu)，它們由少量指令組成，程序中存在相當(dāng)多的循環(huán)結(jié)構(gòu)，它們由少量指令組成，而被多次執(zhí)行。而被多次執(zhí)行。程序中存在相當(dāng)多對一定數(shù)據(jù)結(jié)構(gòu)的操作，如數(shù)組操作，程序中存在相當(dāng)多對一定數(shù)據(jù)結(jié)構(gòu)的操作，如數(shù)組操作，往往局限在較小范圍內(nèi)。往往局限在較小范圍內(nèi)。3. 3. 根據(jù)局部性原理根據(jù)局部性原理進(jìn)程地址空間進(jìn)程地址空間部分放于內(nèi)存部分放于內(nèi)存( (當(dāng)前使用的當(dāng)前使用的) ) 部分放于外存部分放于外存( (當(dāng)前暫不用的當(dāng)

15、前暫不用的) )內(nèi)內(nèi)外外交交換換4. 4. 虛擬存貯器定義虛擬存貯器定義: : 僅把作業(yè)一部分裝入內(nèi)存就可僅把作業(yè)一部分裝入內(nèi)存就可運(yùn)行的系統(tǒng)運(yùn)行的系統(tǒng)虛擬存貯器（虛擬存貯器（p143p143）：是指具有請求調(diào)入功能和）：是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)。種存儲器系統(tǒng)。交換單位交換單位: :頁或段頁或段4.6.2 4.6.2 虛擬存儲器的實(shí)現(xiàn)方法虛擬存儲器的實(shí)現(xiàn)方法1. 1.地址空間部分裝入：在程序裝入時，只將當(dāng)前需要執(zhí)地址空間部分裝入：在程序裝入時，只將當(dāng)前需要執(zhí)行的部分頁或段裝入到內(nèi)存，就可讓程序開始執(zhí)行

16、。行的部分頁或段裝入到內(nèi)存，就可讓程序開始執(zhí)行。2. 2.執(zhí)行中，如果需執(zhí)行的指令或訪問的數(shù)據(jù)尚未在內(nèi)存執(zhí)行中，如果需執(zhí)行的指令或訪問的數(shù)據(jù)尚未在內(nèi)存（稱為缺頁或缺段），硬件產(chǎn)生缺頁或缺段中斷。（稱為缺頁或缺段），硬件產(chǎn)生缺頁或缺段中斷。3. 3. 中斷處理程序，將相應(yīng)的頁或段調(diào)入到內(nèi)存，然后繼續(xù)中斷處理程序，將相應(yīng)的頁或段調(diào)入到內(nèi)存，然后繼續(xù)執(zhí)行程序；如果內(nèi)存無空閑空間，系統(tǒng)將內(nèi)存中暫時不執(zhí)行程序；如果內(nèi)存無空閑空間，系統(tǒng)將內(nèi)存中暫時不使用的頁或段調(diào)出保存在外存交換區(qū)，從而騰出空間存使用的頁或段調(diào)出保存在外存交換區(qū)，從而騰出空間存放將要調(diào)入的頁或段。放將要調(diào)入的頁或段。4. 4. 以上以上2

17、 2、3 3兩條功能稱之：兩條功能稱之：缺頁中斷處理（用于請求頁式管理）缺頁中斷處理（用于請求頁式管理）缺段中斷處理（用于請求段式管理）缺段中斷處理（用于請求段式管理）三三. . 引入虛擬存儲技術(shù)的好處引入虛擬存儲技術(shù)的好處3. 3. 并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行. .1. 1. 運(yùn)行大程序：可在較小的可用內(nèi)存中執(zhí)行較大運(yùn)行大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序的用戶程序. .2. 2. 大的用戶地址空間：提供給用戶可用的虛擬內(nèi)大的用戶地址空間：提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存存空間通常大于物理內(nèi)存. .4.6.3 4.6.3 虛

18、擬存儲技術(shù)的特征虛擬存儲技術(shù)的特征3. 3. 虛擬性：提供大范圍的虛擬地址空間虛擬性：提供大范圍的虛擬地址空間( (通過通過物理內(nèi)存和快速外存相結(jié)合物理內(nèi)存和快速外存相結(jié)合). ).1. 1. 作業(yè)裝入的多次性作業(yè)裝入的多次性: : 不再一次性裝入不再一次性裝入2. 2. 對換性對換性: :注意注意: : 總?cè)萘坎怀^物理內(nèi)存和外存交換區(qū)容量之和總?cè)萘坎怀^物理內(nèi)存和外存交換區(qū)容量之和本章主要內(nèi)容本章主要內(nèi)容4.1 4.1 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu)4.2 4.2 程序的裝入和鏈接程序的裝入和鏈接4.3 4.3 連續(xù)分配方式連續(xù)分配方式4.4 4.4 基本分頁存儲管理方式基本分頁存儲管理

19、方式4.5 4.5 基本分段存儲管理方式基本分段存儲管理方式4.6 4.6 虛擬存儲器的基本概念虛擬存儲器的基本概念4.7 4.7 請求分頁存儲管理方式請求分頁存儲管理方式4.8 4.8 頁面置換算法頁面置換算法4.9 4.9 請求分段存儲管理方式請求分段存儲管理方式1) 1) 進(jìn)程地址空間分為進(jìn)程地址空間分為虛頁虛頁一一. . 實(shí)現(xiàn)原理實(shí)現(xiàn)原理之所以稱虛頁，因?yàn)檫\(yùn)行時之所以稱虛頁，因?yàn)檫\(yùn)行時不一定在主存不一定在主存2) 2) 運(yùn)行前裝入部分頁運(yùn)行前裝入部分頁 3) 3) 運(yùn)行時訪問的頁面不在內(nèi)存運(yùn)行時訪問的頁面不在內(nèi)存, , 缺頁中斷缺頁中斷, ,調(diào)入缺頁調(diào)入缺頁 . .4) 4) 缺頁中斷

20、缺頁中斷, ,調(diào)入新頁時調(diào)入新頁時, ,若內(nèi)存無空閑塊若內(nèi)存無空閑塊, ,則淘汰某頁則淘汰某頁, ,把新頁把新頁調(diào)入調(diào)入. .5) 5) 地址變換地址變換( (重定位重定位): ): 類似簡單分頁系統(tǒng)類似簡單分頁系統(tǒng) , ,但頁表要增加但頁表要增加4 4項(xiàng)（增加請求調(diào)頁、頁面置換功能）項(xiàng)（增加請求調(diào)頁、頁面置換功能）4.7 4.7 請求分頁存儲管理方式請求分頁存儲管理方式在簡單頁式存儲管理的基礎(chǔ)上，在簡單頁式存儲管理的基礎(chǔ)上，pmtpmt中增加中增加請求調(diào)頁和請求調(diào)頁和頁面置換頁面置換功能。功能。簡單分頁簡單分頁pmtpmt請求頁式進(jìn)程頁表請求頁式進(jìn)程頁表(pmt)(pmt)塊號塊號頁號頁號a

21、 amm外存地址外存地址p p塊號塊號頁號頁號淘汰此頁寫回外存淘汰此頁寫回外存 m m修改位：該頁被寫過否修改位：該頁被寫過否0 0 否否, ,1 1 是是, ,淘汰此頁不寫回外存淘汰此頁不寫回外存 a a訪問字段：頁面訪問統(tǒng)計(jì)訪問字段：頁面訪問統(tǒng)計(jì), , 在在近期內(nèi)近期內(nèi)被訪問的被訪問的次數(shù)次數(shù)，或最近，或最近一次訪問到現(xiàn)在的一次訪問到現(xiàn)在的時間間隔時間間隔. .為淘汰算法提供依據(jù)為淘汰算法提供依據(jù) 外存地址外存地址 : :通常是物理塊號。通常是物理塊號。 p p狀態(tài)位狀態(tài)位: : 該頁在主存否該頁在主存否0 0 否否1 1 在在地址變換查表時發(fā)現(xiàn)地址變換查表時發(fā)現(xiàn)p=0, p=0, 硬硬件

22、缺頁中斷件缺頁中斷cpucpummummu內(nèi)內(nèi)存存磁盤磁盤控制器控制器總線總線( mmu )( mmu )處理機(jī)卡上的處理機(jī)卡上的存儲管理單元存儲管理單元邏輯地址邏輯地址物理地址物理地址二二. . 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu): : （mmummu） 硬件支持硬件支持：頁表機(jī)制、缺頁中斷機(jī)構(gòu)、地址變換機(jī)構(gòu)：頁表機(jī)制、缺頁中斷機(jī)構(gòu)、地址變換機(jī)構(gòu) 軟件支持軟件支持：缺頁中斷處理程序。：缺頁中斷處理程序。cpucpu給出的虛地址（邏輯地址）送給給出的虛地址（邏輯地址）送給mmummu部件，經(jīng)部件，經(jīng)mmummu解析出虛頁號，例如解析出虛頁號，例如k k，查頁表的第，查頁表的第k k個表項(xiàng)，用該表項(xiàng)所對個

23、表項(xiàng)，用該表項(xiàng)所對應(yīng)的塊號去構(gòu)造物理地址，應(yīng)的塊號去構(gòu)造物理地址，mmummu把構(gòu)造的物理地址送地址總把構(gòu)造的物理地址送地址總線。線。mmummu部件是地址變換機(jī)構(gòu)。部件是地址變換機(jī)構(gòu)。v 有一臺有一臺1616位機(jī)，可訪問位機(jī)，可訪問64k64k空間，給出的地址長度空間，給出的地址長度1616位位v 內(nèi)存為內(nèi)存為32k32k。v 在具有虛擬存儲功能的系統(tǒng)中，允許進(jìn)程的地址空間在具有虛擬存儲功能的系統(tǒng)中，允許進(jìn)程的地址空間=64k=64k（虛地址空間）（虛地址空間）v 64k64k地址空間不能全部裝入內(nèi)存，部分裝入地址空間不能全部裝入內(nèi)存，部分裝入v 外存有一個外存有一個64k64k的地址空間映

24、象的地址空間映象v 運(yùn)行時由運(yùn)行時由mmummu進(jìn)行地址變換進(jìn)行地址變換v 頁面劃分為頁面劃分為4k4k： 64k64k的虛地址空間可分為的虛地址空間可分為015015（1616個頁面）個頁面） 物理空間分為物理空間分為8 8個頁框（塊）個頁框（塊）討論討論mmummu：216043xxx5x7xxxx60k-64k1556k-60k1452k-56k1348k-52k1244k-48k1140k-44k1036k-40k932k-36k828k-32k724k-28k620k-24k516k-20k412k-16k3 8k-12k2 4k-8k1 0k-4k0虛地址空間虛地址空間 虛頁虛頁2

25、8k-32k724k-28k620k-24k516k-20k412k-16k3 8k-12k 24k-8k1 0k-4k0物理地址空間物理地址空間頁框（塊）頁框（塊）（虛擬存貯器）（虛擬存貯器）01234567891011121314010100111100000110010111000000000000101100001111000000000000000015110000000000100001000000000010110頁表頁表vama0cpu執(zhí)行執(zhí)行l(wèi)oad r1， 8196（2004h）cpu給出虛地址給出虛地址8196送送va，分離出分離出 p | w：2 | 42頁在頁在6塊中

26、塊中塊號塊號6送送ma的高三位，的高三位，w送送ma的低的低12位，形成物理位，形成物理地址：地址：24580（ 6004h）6004h送地址總線送地址總線存在位為存在位為0，mmu引起缺引起缺頁中斷。頁中斷。地址變換與中斷處理流程地址變換與中斷處理流程, , 見見: ( p146: ( p146圖圖4-25)4-25) 地址變換機(jī)構(gòu)產(chǎn)生缺頁中斷，然后調(diào)地址變換機(jī)構(gòu)產(chǎn)生缺頁中斷，然后調(diào)用內(nèi)存管理提供的中斷處理例程。用內(nèi)存管理提供的中斷處理例程。缺頁中斷機(jī)構(gòu)：缺頁中斷機(jī)構(gòu)：在請求分頁系統(tǒng)中，每當(dāng)所要訪問的在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時，便產(chǎn)生一缺頁中斷，頁面不在內(nèi)存時，便產(chǎn)生一缺

27、頁中斷，請求請求osos將所缺之頁調(diào)入內(nèi)存。缺頁將所缺之頁調(diào)入內(nèi)存。缺頁中斷同樣需要經(jīng)歷保護(hù)中斷同樣需要經(jīng)歷保護(hù)cpucpu環(huán)境、分環(huán)境、分析中斷原因、轉(zhuǎn)入缺頁中斷處理程序析中斷原因、轉(zhuǎn)入缺頁中斷處理程序進(jìn)行處理、恢復(fù)進(jìn)行處理、恢復(fù)cpucpu環(huán)境等幾步。但環(huán)境等幾步。但缺頁與一般中斷相比，有著明顯的區(qū)缺頁與一般中斷相比，有著明顯的區(qū)別，主要表現(xiàn)在：別，主要表現(xiàn)在：（1 1）在指令執(zhí)行期間產(chǎn)生和處理中）在指令執(zhí)行期間產(chǎn)生和處理中斷信號。斷信號。（2 2）一條指令在執(zhí)行期間，可能產(chǎn)）一條指令在執(zhí)行期間，可能產(chǎn)生多次中斷。如圖所示例子。生多次中斷。如圖所示例子。123456頁面頁面copy ato

28、 bb:a:指令指令指令指令copy a to bcopy a to b本身跨了兩頁，本身跨了兩頁，a a和和b b分別各是一個數(shù)據(jù)塊，也都跨了兩分別各是一個數(shù)據(jù)塊，也都跨了兩頁。該指令的執(zhí)行可能產(chǎn)生頁。該指令的執(zhí)行可能產(chǎn)生6 6次缺頁中次缺頁中斷。斷。產(chǎn)生缺頁中產(chǎn)生缺頁中斷請求調(diào)頁斷請求調(diào)頁 缺頁中斷處理缺頁中斷處理保留保留cpucpu現(xiàn)場現(xiàn)場選擇一頁換出選擇一頁換出確定缺頁外存地址確定缺頁外存地址此頁修改過否？此頁修改過否？該頁寫回外存該頁寫回外存缺頁換入內(nèi)存缺頁換入內(nèi)存修改頁表修改頁表n ny y程序請求訪問一頁程序請求訪問一頁cpucpu查快表查快表訪問頁表訪問頁表頁在內(nèi)存？頁在內(nèi)存？

29、形成物理地址形成物理地址修改訪問字段和修改位修改訪問字段和修改位修改快表修改快表組織讀缺頁命令組織讀缺頁命令啟動啟動i/oi/o開始開始頁號頁號頁表長度？頁表長度？越界中斷越界中斷頁表項(xiàng)在快表中？頁表項(xiàng)在快表中？y yn ny yn n內(nèi)存滿否？內(nèi)存滿否？n ny yn ny y4.7.2 4.7.2 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法1. 1. 最小物理塊數(shù)的確定最小物理塊數(shù)的確定 是指能保證進(jìn)程正常運(yùn)行所需的最是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時，進(jìn)程將無小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時，進(jìn)程將無法運(yùn)行。進(jìn)程應(yīng)獲得的最小物

30、理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取法運(yùn)行。進(jìn)程應(yīng)獲得的最小物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。決于指令的格式、功能和尋址方式。為進(jìn)程分配內(nèi)存時，將涉及到三個問題：為進(jìn)程分配內(nèi)存時，將涉及到三個問題：第一，最小物理塊數(shù)的確定；第一，最小物理塊數(shù)的確定；第二，物理塊的分配策略；第二，物理塊的分配策略；第三，物理塊的分配算法。第三，物理塊的分配算法。4.7.2 4.7.2 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法2. 2. 物理塊的分配策略物理塊的分配策略 固定分配局部置換固定分配局部置換 為每個進(jìn)程分配一定數(shù)目的物理塊，整個運(yùn)行期為每個進(jìn)程分配一定數(shù)目的物理塊，整個

31、運(yùn)行期間都不再改變。間都不再改變。 可變分配全局置換可變分配全局置換 先為系統(tǒng)中的每個進(jìn)程分配一定數(shù)目的物理塊，先為系統(tǒng)中的每個進(jìn)程分配一定數(shù)目的物理塊，而而osos自身也保持一定空閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁時，由系統(tǒng)從空自身也保持一定空閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁時，由系統(tǒng)從空閑物理塊隊(duì)列中取出一個物理塊分配給該進(jìn)程，并將欲調(diào)入的頁裝入其中。閑物理塊隊(duì)列中取出一個物理塊分配給該進(jìn)程，并將欲調(diào)入的頁裝入其中。 可變分配局部置換可變分配局部置換 為每個進(jìn)程分配一定數(shù)目的物理塊，當(dāng)某進(jìn)程發(fā)為每個進(jìn)程分配一定數(shù)目的物理塊，當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁時，只允許從該進(jìn)程在內(nèi)存的頁面中選出一頁換出，這樣就不會

32、影現(xiàn)缺頁時，只允許從該進(jìn)程在內(nèi)存的頁面中選出一頁換出，這樣就不會影響其它進(jìn)程的運(yùn)行。若進(jìn)程運(yùn)行過程中頻繁地發(fā)生缺頁中斷，則系統(tǒng)為該響其它進(jìn)程的運(yùn)行。若進(jìn)程運(yùn)行過程中頻繁地發(fā)生缺頁中斷，則系統(tǒng)為該進(jìn)程分配附加的物理塊，直至該進(jìn)程的缺頁率減少到適當(dāng)程度為止；反之，進(jìn)程分配附加的物理塊，直至該進(jìn)程的缺頁率減少到適當(dāng)程度為止；反之，可適當(dāng)減少分配給該進(jìn)程的物理塊數(shù)?？蛇m當(dāng)減少分配給該進(jìn)程的物理塊數(shù)。4.7.2 4.7.2 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法并非一個進(jìn)程分配幾個物理塊就可運(yùn)行并非一個進(jìn)程分配幾個物理塊就可運(yùn)行, , 太少可能造成系統(tǒng)抖動太少可能造成系統(tǒng)抖動. .在采在采用固定分

33、配策略時，如何將系統(tǒng)中可供分配的所有物理塊分配給各進(jìn)用固定分配策略時，如何將系統(tǒng)中可供分配的所有物理塊分配給各進(jìn)程?？刹捎靡韵聨追N算法：程。可采用以下幾種算法：1. 1. 平均分配平均分配: : 內(nèi)存塊平均分給各進(jìn)程。小進(jìn)程有利內(nèi)存塊平均分給各進(jìn)程。小進(jìn)程有利, ,長進(jìn)程中斷率高。長進(jìn)程中斷率高。2. 2. 根據(jù)進(jìn)程大小按比例分配。根據(jù)進(jìn)程大小按比例分配。3. 3. 按優(yōu)先權(quán)分配。按優(yōu)先權(quán)分配。3. 3. 物理塊分配算法物理塊分配算法4.7.3 4.7.3 調(diào)頁策略調(diào)頁策略2. 2. 預(yù)調(diào)頁：在發(fā)生缺頁需要調(diào)入某頁時，一次調(diào)入該頁以預(yù)調(diào)頁：在發(fā)生缺頁需要調(diào)入某頁時，一次調(diào)入該頁以及相鄰的幾個頁

34、。及相鄰的幾個頁。( (通常用于進(jìn)程首次調(diào)入內(nèi)存通常用于進(jìn)程首次調(diào)入內(nèi)存, , 可同時調(diào)入可同時調(diào)入幾頁幾頁) )優(yōu)點(diǎn)：提高調(diào)頁的優(yōu)點(diǎn)：提高調(diào)頁的i/oi/o效率。效率。缺點(diǎn)：基于預(yù)測，若調(diào)入的頁在以后很少被訪問，則效率缺點(diǎn)：基于預(yù)測，若調(diào)入的頁在以后很少被訪問，則效率低。常用于程序裝入時的調(diào)頁。低。常用于程序裝入時的調(diào)頁。1. 1.請求調(diào)頁：只調(diào)入發(fā)生缺頁時所需的頁面。請求調(diào)頁：只調(diào)入發(fā)生缺頁時所需的頁面。優(yōu)點(diǎn)：容易實(shí)現(xiàn)。優(yōu)點(diǎn)：容易實(shí)現(xiàn)。缺點(diǎn)：對外存缺點(diǎn)：對外存i/oi/o次數(shù)多，開銷較大次數(shù)多，開銷較大調(diào)入頁面的時機(jī)：調(diào)入頁面的時機(jī)：4.7.3 4.7.3 調(diào)頁策略調(diào)頁策略通常對換區(qū)的通常

35、對換區(qū)的i/oi/o效率比文件區(qū)的高。關(guān)于調(diào)入頁面的來源，效率比文件區(qū)的高。關(guān)于調(diào)入頁面的來源，這里有三種做法：這里有三種做法：1. 1. 從對換區(qū)從對換區(qū): : 進(jìn)程裝入前，將其全部頁面復(fù)制到對換區(qū)，以進(jìn)程裝入前，將其全部頁面復(fù)制到對換區(qū)，以后總是從對換區(qū)調(diào)入。執(zhí)行時調(diào)入速度快，要求對換區(qū)后總是從對換區(qū)調(diào)入。執(zhí)行時調(diào)入速度快，要求對換區(qū)空間較大。空間較大。2. 2. 未被修改的頁面從文件區(qū)讀入，而被置換時不需調(diào)出；未被修改的頁面從文件區(qū)讀入，而被置換時不需調(diào)出；已已被修改的頁面從交換區(qū)調(diào)入被修改的頁面從交換區(qū)調(diào)入, ,節(jié)省交換區(qū)空間節(jié)省交換區(qū)空間. .被修改過的頁面淘汰時送入對換區(qū)被修改過的

36、頁面淘汰時送入對換區(qū)確定從何處調(diào)入頁面：確定從何處調(diào)入頁面：3. unix3. unix方式。未運(yùn)行過的頁面都應(yīng)從文件區(qū)調(diào)入。而對于方式。未運(yùn)行過的頁面都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運(yùn)行過但又被換出的頁面，應(yīng)從對換區(qū)調(diào)入。又由曾經(jīng)運(yùn)行過但又被換出的頁面，應(yīng)從對換區(qū)調(diào)入。又由于于unixunix系統(tǒng)允許頁面共享，如果某進(jìn)程所請求的頁面已系統(tǒng)允許頁面共享，如果某進(jìn)程所請求的頁面已經(jīng)被其他進(jìn)程調(diào)入內(nèi)存，此時也無須從對換區(qū)調(diào)入。經(jīng)被其他進(jìn)程調(diào)入內(nèi)存，此時也無須從對換區(qū)調(diào)入。補(bǔ)充：抖動補(bǔ)充：抖動從主存中剛剛移走某頁面后，根據(jù)請求馬上又調(diào)入該頁。這從主存中剛剛移走某頁面后，根據(jù)請求馬上又調(diào)入該頁。這種反復(fù)進(jìn)

37、行入頁和出頁的現(xiàn)象稱為種反復(fù)進(jìn)行入頁和出頁的現(xiàn)象稱為“抖動抖動”，也叫系統(tǒng)顛簸。，也叫系統(tǒng)顛簸。它會浪費(fèi)大量的處理機(jī)時間，應(yīng)盡可能避免。產(chǎn)生抖動的直它會浪費(fèi)大量的處理機(jī)時間，應(yīng)盡可能避免。產(chǎn)生抖動的直接原因是頁面置換算法選取不當(dāng)。接原因是頁面置換算法選取不當(dāng)。利用利用lrulru置換算法時的置換圖置換算法時的置換圖70120304230321201701707107210021302032403240324032302230123213021102710071共產(chǎn)生缺頁中共產(chǎn)生缺頁中斷斷12次次107頁面引用序列為：頁面引用序列為：7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1請求分頁系統(tǒng)的評價請求分頁系統(tǒng)的評價優(yōu)點(diǎn)：優(yōu)點(diǎn)：