計(jì)算機(jī)操作系統(tǒng) 存儲(chǔ)器管理

1、v 編輯編輯編譯編譯鏈接鏈接裝入裝入運(yùn)行運(yùn)行v 圖圖4.14.1v 1 1、絕對(duì)裝入：、絕對(duì)裝入： 編譯后，裝入前已產(chǎn)生了絕對(duì)地址（內(nèi)存地址），裝編譯后，裝入前已產(chǎn)生了絕對(duì)地址（內(nèi)存地址），裝入時(shí)不再作地址重定位。入時(shí)不再作地址重定位。 絕對(duì)地址的產(chǎn)生：（絕對(duì)地址的產(chǎn)生：（1 1）由編譯器完成，（）由編譯器完成，（2 2）由程序）由程序員編程完成。員編程完成。 對(duì)（對(duì)（1 1）而言，編程用符號(hào)地址。）而言，編程用符號(hào)地址。v 2 2、可重定位裝入；、可重定位裝入； 靜態(tài)重定位：裝入時(shí)完成，主要工作是對(duì)相對(duì)地址中靜態(tài)重定位：裝入時(shí)完成，主要工作是對(duì)相對(duì)地址中的指令和數(shù)據(jù)地址的調(diào)整過程，例：圖的指

2、令和數(shù)據(jù)地址的調(diào)整過程，例：圖4 42 2 問題：?jiǎn)栴}： 如何知道哪些位置需調(diào)整？如何知道哪些位置需調(diào)整？ 鏈接時(shí)產(chǎn)生可裝入模塊的具體功能鏈接時(shí)產(chǎn)生可裝入模塊的具體功能? ?0100025005000LOAD 1, 2500LOAD 1, 250036536510000110001250015000作業(yè)地址空間作業(yè)地址空間內(nèi)存空間內(nèi)存空間圖圖4-2v 3.3.動(dòng)態(tài)運(yùn)行時(shí)裝入動(dòng)態(tài)運(yùn)行時(shí)裝入 在裝入后不能移動(dòng)，在裝入后不能移動(dòng)， 該情況一般在執(zhí)行時(shí)才完成相對(duì)該情況一般在執(zhí)行時(shí)才完成相對(duì)絕對(duì)地址的轉(zhuǎn)換絕對(duì)地址的轉(zhuǎn)換且有硬件的支持且有硬件的支持, ,能保證進(jìn)程的可移動(dòng)性。能保證進(jìn)程的可移動(dòng)性。v 1

3、1、靜態(tài)鏈接、靜態(tài)鏈接 a a對(duì)相對(duì)地址的修改對(duì)相對(duì)地址的修改 b b變換外部調(diào)用符號(hào)變換外部調(diào)用符號(hào)v 2 2、裝入時(shí)動(dòng)態(tài)鏈接、裝入時(shí)動(dòng)態(tài)鏈接 a.a.便于修改和更新便于修改和更新 b.b.便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享v 3 3、運(yùn)行時(shí)動(dòng)態(tài)鏈接、運(yùn)行時(shí)動(dòng)態(tài)鏈接模塊模塊A ACALL B;CALL B;RETURNRETURN模塊模塊B BCALL C;CALL C;RETURNRETURN模塊模塊C CRETURNRETURN0 0L-1L-10 0M-1M-10 0N-1N-1(a)(a)目標(biāo)模塊目標(biāo)模塊模塊模塊A AJSR L;JSR L;RETURNRETURN模塊

4、模塊B BJSR L+M;JSR L+M;RETURNRETURN模塊模塊C CRETURNRETURN0 0L-1L-1L LL+M-1L+M-1L+ML+ML+M+N-1L+M+N-1(b)(b)裝入模塊裝入模塊v 單一連續(xù)分配單一連續(xù)分配 用于單用戶，單任務(wù)中用于單用戶，單任務(wù)中v 分區(qū)式分配分區(qū)式分配 固定式固定式 可變式可變式 可重定位分區(qū)分配可重定位分區(qū)分配 v 特點(diǎn)：有特點(diǎn)：有n n個(gè)分區(qū)，則可同時(shí)裝入個(gè)分區(qū)，則可同時(shí)裝入n n個(gè)作業(yè)個(gè)作業(yè)/ /任務(wù)。任務(wù)。v 一、分區(qū)大?。阂?、分區(qū)大小： 相等相等: : 不相等：不相等利用率更高。不相等：不相等利用率更高。v 二、內(nèi)存分配：二、

5、內(nèi)存分配： 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 將分區(qū)按大小排序，并將其地址、分配標(biāo)識(shí)作記錄將分區(qū)按大小排序，并將其地址、分配標(biāo)識(shí)作記錄 例：例：dosdos的的MCBMCBv 三、特點(diǎn)：三、特點(diǎn)： 簡(jiǎn)單，有碎片（內(nèi)零頭）簡(jiǎn)單，有碎片（內(nèi)零頭）分區(qū)號(hào)分區(qū)號(hào) 大?。ù笮。↘)起址（起址（K）狀態(tài)狀態(tài)11220已分配已分配23232已分配已分配36464已分配已分配4128128已分配已分配操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)A A作業(yè)作業(yè)B B作業(yè)作業(yè)C C24K32K64K128K256K分配情況分配情況v 一、數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)1 1 空閑分區(qū)表空閑分區(qū)表2 2 空閑分區(qū)鏈空閑分區(qū)鏈前向指前向指針針N N個(gè)字節(jié)可用個(gè)字

6、節(jié)可用后向指后向指針針N+2N+2N+2N+20 0（分配（分配標(biāo)識(shí)）標(biāo)識(shí)）0 0v 二、分配算法二、分配算法1 1 首次適應(yīng)算法首次適應(yīng)算法FFFF。 要求：分區(qū)按低址要求：分區(qū)按低址高址鏈接高址鏈接 特點(diǎn)：找到第一個(gè)大小滿足的分區(qū)，劃分。有外零頭，特點(diǎn)：找到第一個(gè)大小滿足的分區(qū)，劃分。有外零頭，低址內(nèi)存使用頻繁。低址內(nèi)存使用頻繁。2 2 循環(huán)首次適應(yīng)算法。循環(huán)首次適應(yīng)算法。 從從1 1中上次找到的空閑分區(qū)的下一個(gè)開始查找。中上次找到的空閑分區(qū)的下一個(gè)開始查找。 特點(diǎn)：空閑分區(qū)分布均勻，提高了查找速度；缺乏大特點(diǎn)：空閑分區(qū)分布均勻，提高了查找速度；缺乏大的空閑分區(qū)。的空閑分區(qū)。3 3 最佳適

7、應(yīng)算法最佳適應(yīng)算法 分區(qū)按大小遞增排序；分區(qū)釋放時(shí)需插入到適當(dāng)位置。分區(qū)按大小遞增排序；分區(qū)釋放時(shí)需插入到適當(dāng)位置。v 三、分區(qū)分配三、分區(qū)分配1 1 分配：圖分配：圖4-64-62 2 回收：回收： （1 1）上鄰空閑區(qū)：合并，改大小）上鄰空閑區(qū)：合并，改大小 （2 2）下鄰空閑區(qū)：合并，改大小，首址。）下鄰空閑區(qū)：合并，改大小，首址。 （3 3）上、下鄰空閑區(qū)：合并，改大小。）上、下鄰空閑區(qū)：合并，改大小。 （4 4）不鄰接，則建立一新表項(xiàng)。）不鄰接，則建立一新表項(xiàng)。F1F1回收區(qū)回收區(qū)回收區(qū)回收區(qū)F2F2F1F1回收區(qū)回收區(qū)F2F24-7 4-7 內(nèi)存回收時(shí)的情況內(nèi)存回收時(shí)的情況v 1.

8、1.動(dòng)態(tài)重定位的引入動(dòng)態(tài)重定位的引入 連續(xù)式分配中，總量大于作業(yè)大小的多個(gè)小分連續(xù)式分配中，總量大于作業(yè)大小的多個(gè)小分區(qū)不能容納作業(yè)。區(qū)不能容納作業(yè)。 緊湊緊湊 通過作業(yè)移動(dòng)將原來分散的小分區(qū)拼接成一通過作業(yè)移動(dòng)將原來分散的小分區(qū)拼接成一個(gè)大分區(qū)。個(gè)大分區(qū)。 作業(yè)的移動(dòng)需重定位。是動(dòng)態(tài)（因作業(yè)已經(jīng)作業(yè)的移動(dòng)需重定位。是動(dòng)態(tài)（因作業(yè)已經(jīng)裝入）裝入）操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序1 110kb10kb用戶程序用戶程序3 330kb30kb用戶程序用戶程序6 614kb14kb用戶程序用戶程序9 926kb26kb操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序1 1用戶程序用戶程序3 3用戶程序用戶程序6 6用

9、戶程序用戶程序9 9load 1,2500load 1,2500365365load 1,load 1,250025003653650 0100100250025005000500025002500100001000010000100001010010100+ +12500125001500015000作業(yè)作業(yè)J J處理機(jī)一側(cè)處理機(jī)一側(cè)存儲(chǔ)器一側(cè)存儲(chǔ)器一側(cè)重定位寄存器重定位寄存器相對(duì)地址相對(duì)地址v 1 1 對(duì)換的引入對(duì)換的引入 將阻塞進(jìn)程，暫時(shí)不用的程序，數(shù)據(jù)換出。將阻塞進(jìn)程，暫時(shí)不用的程序，數(shù)據(jù)換出。 將具備運(yùn)行條件的進(jìn)程換入。將具備運(yùn)行條件的進(jìn)程換入。 類型：類型： 整體對(duì)換：進(jìn)程對(duì)換，解

10、決內(nèi)存緊張整體對(duì)換：進(jìn)程對(duì)換，解決內(nèi)存緊張 部分對(duì)換：頁(yè)面對(duì)換部分對(duì)換：頁(yè)面對(duì)換/ /分段對(duì)換：提供虛存支持分段對(duì)換：提供虛存支持v 2 2 對(duì)換空間的管理對(duì)換空間的管理 外存外存 對(duì)換區(qū)對(duì)換區(qū)比比文件區(qū)文件區(qū)側(cè)重于對(duì)換速度。側(cè)重于對(duì)換速度。 因此，對(duì)換區(qū)一般采用連續(xù)分配。采用數(shù)據(jù)結(jié)構(gòu)和因此，對(duì)換區(qū)一般采用連續(xù)分配。采用數(shù)據(jù)結(jié)構(gòu)和分配回收類似于可變化分區(qū)分配。分配回收類似于可變化分區(qū)分配。v 3 3 換出與換入換出與換入 一、換出一、換出 1 1選出被換出進(jìn)程：選出被換出進(jìn)程：因素：優(yōu)先級(jí)，駐留時(shí)間，進(jìn)程狀態(tài)因素：優(yōu)先級(jí)，駐留時(shí)間，進(jìn)程狀態(tài) 2 2換出過程：換出過程：對(duì)于共享段：計(jì)數(shù)減對(duì)于共享

11、段：計(jì)數(shù)減1 1， 是是0 0則換出，否則不換則換出，否則不換修改修改PCBPCB和和MCBMCB（或內(nèi)存分配表）（或內(nèi)存分配表） 二、換入：二、換入： 1 1選擇換入進(jìn)程：優(yōu)先級(jí)，換出時(shí)間等。選擇換入進(jìn)程：優(yōu)先級(jí)，換出時(shí)間等。 2 2申請(qǐng)內(nèi)存。申請(qǐng)內(nèi)存。 3 3換入換入v 連續(xù)分配引起連續(xù)分配引起: :碎片碎片v 碎片問題的解決：緊湊方式消耗系統(tǒng)開銷。碎片問題的解決：緊湊方式消耗系統(tǒng)開銷。v 離散分配離散分配 分頁(yè)、分段、段頁(yè)分頁(yè)、分段、段頁(yè)v 1.1.頁(yè)面頁(yè)面 頁(yè)面和物理塊：邏輯空間和內(nèi)存空間頁(yè)面和物理塊：邏輯空間和內(nèi)存空間 由機(jī)器的地址結(jié)構(gòu)決定由機(jī)器的地址結(jié)構(gòu)決定 頁(yè)太大，頁(yè)內(nèi)碎片大。頁(yè)

12、太大，頁(yè)內(nèi)碎片大。 頁(yè)太小：頁(yè)表可能很長(zhǎng)，換入頁(yè)太?。喉?yè)表可能很長(zhǎng)，換入/ /出效率低出效率低v 2.2.地址結(jié)構(gòu)地址結(jié)構(gòu)13 3112 1112 110 0 邏輯地址邏輯地址A A；頁(yè)大小；頁(yè)大小L(L(設(shè)為設(shè)為1024)1024)；頁(yè)內(nèi)偏移；頁(yè)內(nèi)偏移d dd=A mod Ld=A mod L如：如： A A2170B. 2170B. 則則P=2, d=122 P=2, d=122 頁(yè)號(hào)頁(yè)號(hào)P P 位移位移W W 0 0頁(yè)頁(yè)1 1頁(yè)頁(yè)2 2頁(yè)頁(yè)3 3頁(yè)頁(yè)4 4頁(yè)頁(yè)5 5頁(yè)頁(yè)n n頁(yè)頁(yè)0 02 21 13 32 26 63 38 84 49 95 50 01 12 23 34 45 56 67

13、 78 89 9用戶程序用戶程序頁(yè)表頁(yè)表頁(yè)號(hào)頁(yè)號(hào)塊號(hào)塊號(hào)內(nèi)存內(nèi)存v 完成：邏輯頁(yè)號(hào)完成：邏輯頁(yè)號(hào)物理塊號(hào)的映射，由頁(yè)表完成。物理塊號(hào)的映射，由頁(yè)表完成。v 一、基本地址變換機(jī)構(gòu)：一、基本地址變換機(jī)構(gòu)： 越界保護(hù)越界保護(hù) 每個(gè)進(jìn)程對(duì)應(yīng)一頁(yè)表，其信息（如長(zhǎng)度、始址）放在每個(gè)進(jìn)程對(duì)應(yīng)一頁(yè)表，其信息（如長(zhǎng)度、始址）放在PCBPCB中，執(zhí)行時(shí)將其首地址裝入中，執(zhí)行時(shí)將其首地址裝入頁(yè)表寄存器頁(yè)表寄存器。v 不具快表，則需兩次訪問內(nèi)存。不具快表，則需兩次訪問內(nèi)存。（ （1 1）訪頁(yè)表）訪頁(yè)表（ （2 2）得到絕對(duì)地址內(nèi)容）得到絕對(duì)地址內(nèi)容v 有快表，速度提高。有快表，速度提高。v 快表貴，不能太多?？毂碣F，

14、不能太多。 例：有一頁(yè)式系統(tǒng)，其頁(yè)表存放在主存中：例：有一頁(yè)式系統(tǒng)，其頁(yè)表存放在主存中： 如果對(duì)主存的一次存取需要如果對(duì)主存的一次存取需要1.5 1.5 s,s,試問實(shí)試問實(shí)現(xiàn)一次頁(yè)面訪問的存取時(shí)間是多少現(xiàn)一次頁(yè)面訪問的存取時(shí)間是多少? ? 如果系統(tǒng)加有快表如果系統(tǒng)加有快表, ,平均命中率為平均命中率為85%,85%,當(dāng)頁(yè)表當(dāng)頁(yè)表項(xiàng)在快表中時(shí)項(xiàng)在快表中時(shí), ,其查找時(shí)間忽略為其查找時(shí)間忽略為0, 0, 試試問此時(shí)問此時(shí)的存取時(shí)間是多少的存取時(shí)間是多少? ?答：若頁(yè)表存放在主存中，則要實(shí)現(xiàn)一次頁(yè)面訪問需兩次訪問答：若頁(yè)表存放在主存中，則要實(shí)現(xiàn)一次頁(yè)面訪問需兩次訪問主存：一次是訪問頁(yè)表，確定所存取

15、頁(yè)面的物理地址（稱為主存：一次是訪問頁(yè)表，確定所存取頁(yè)面的物理地址（稱為定位）。第二次才根據(jù)該地址存取頁(yè)面數(shù)據(jù)。定位）。第二次才根據(jù)該地址存取頁(yè)面數(shù)據(jù)。 頁(yè)表在主存的存取訪問時(shí)間頁(yè)表在主存的存取訪問時(shí)間 =1.5=1.5* *2=3(s)2=3(s) 增加快表后的存取訪問時(shí)間增加快表后的存取訪問時(shí)間 =0.85=0.85* *1.5+(1-0.85)1.5+(1-0.85)* *2 2* *1.5=1.725(s)1.5=1.725(s)v 頁(yè)表可能很大，將其離散存放在不同頁(yè)塊中。頁(yè)表可能很大，將其離散存放在不同頁(yè)塊中。v 建一建一“外外部部頁(yè)表頁(yè)表”來管理這些離散頁(yè)表塊。來管理這些離散頁(yè)表塊

16、。 相當(dāng)于單級(jí)相當(dāng)于單級(jí)頁(yè)表中頁(yè)表中的頁(yè)表寄存器，一般應(yīng)常駐內(nèi)存。的頁(yè)表寄存器，一般應(yīng)常駐內(nèi)存。每項(xiàng)記錄頁(yè)表始址，且增加存在位。每項(xiàng)記錄頁(yè)表始址，且增加存在位。v 6464位機(jī)器頁(yè)表一般位機(jī)器頁(yè)表一般33級(jí)，最外層頁(yè)表常駐。級(jí)，最外層頁(yè)表常駐。 v某虛擬存儲(chǔ)器的用戶編程空間共某虛擬存儲(chǔ)器的用戶編程空間共3232個(gè)頁(yè)面，每頁(yè)為個(gè)頁(yè)面，每頁(yè)為1KB1KB，內(nèi)存為，內(nèi)存為16KB16KB。假定某時(shí)刻一用戶頁(yè)表中已調(diào)入。假定某時(shí)刻一用戶頁(yè)表中已調(diào)入內(nèi)存的頁(yè)面對(duì)應(yīng)的物理塊號(hào)如下表：內(nèi)存的頁(yè)面對(duì)應(yīng)的物理塊號(hào)如下表：頁(yè)號(hào)頁(yè)號(hào)物理塊號(hào)物理塊號(hào)0 05 51 110102 24 43 37 7則邏輯地址則邏輯地

17、址0A5C0A5C（H H）所對(duì)應(yīng)的物理地址為）所對(duì)應(yīng)的物理地址為 ：125C125Cv 0A5C0A5C0000,100000,1010,0101,110010,0101,1100v 頁(yè)號(hào)為頁(yè)號(hào)為2 2，對(duì)應(yīng)塊號(hào)為，對(duì)應(yīng)塊號(hào)為4 4，有：，有：v 物理地址：物理地址：00010001，000010,0101,110010,0101,1100v 即：即：125C125Cv 即多重定位分區(qū)管理即多重定位分區(qū)管理 v 4.4.14.4.1引入引入 每個(gè)段可有其邏輯意義及功能，使得便于每個(gè)段可有其邏輯意義及功能，使得便于 （1 1）方便編程；）方便編程； （2 2）分段共享；）分段共享； （3 3）

18、分段保護(hù)；）分段保護(hù)； （4 4）動(dòng)態(tài)鏈接；）動(dòng)態(tài)鏈接； （5 5）動(dòng)態(tài)增長(zhǎng)；（如數(shù)據(jù)段的增長(zhǎng)）動(dòng)態(tài)增長(zhǎng)；（如數(shù)據(jù)段的增長(zhǎng)）v 分段分段 對(duì)用戶而言，分段是對(duì)用戶而言，分段是2 2維的。維的。 段號(hào)段號(hào)+ +段內(nèi)地址。段內(nèi)地址。v 段表：段表： 邏輯段邏輯段mapmap物理段物理段v 地址變換機(jī)構(gòu)：地址變換機(jī)構(gòu)：圖圖4 41616，4 41717v 分頁(yè)與分段：分頁(yè)與分段：（ （1 1）頁(yè)是信息的物理單位，段是邏輯單位）頁(yè)是信息的物理單位，段是邏輯單位（ （2 2）頁(yè)長(zhǎng)度固定，段長(zhǎng)度不固定（由用戶指定）頁(yè)長(zhǎng)度固定，段長(zhǎng)度不固定（由用戶指定）（ （3 3）一維與二維）一維與二維 v 段式系統(tǒng)易于

19、共享段式系統(tǒng)易于共享 例：圖例：圖4-184-18及及4-194-19 分頁(yè)與分段共享比較分頁(yè)與分段共享比較 可重入碼（純代碼）可重入碼（純代碼） 各個(gè)進(jìn)程應(yīng)保留局部數(shù)據(jù)區(qū)各個(gè)進(jìn)程應(yīng)保留局部數(shù)據(jù)區(qū)ed1ed2ed40data1data102122606170ed1ed2ed40data1data10data1data10進(jìn)程進(jìn)程1進(jìn)程進(jìn)程2頁(yè)表頁(yè)表頁(yè)表頁(yè)表ed1ed2ed40data1data102122607180主存分頁(yè)系統(tǒng)中共享分頁(yè)系統(tǒng)中共享editoreditordata1editordata2段長(zhǎng)段長(zhǎng)基址基址1608040240段長(zhǎng)段長(zhǎng)基址基址1608040380editordata

20、1data2v 分頁(yè)優(yōu)點(diǎn)：提高內(nèi)存利用率分頁(yè)優(yōu)點(diǎn)：提高內(nèi)存利用率v 分段優(yōu)點(diǎn)：方便用戶，易于共享，保護(hù)，動(dòng)態(tài)鏈接。分段優(yōu)點(diǎn)：方便用戶，易于共享，保護(hù)，動(dòng)態(tài)鏈接。v 一、段頁(yè)式系統(tǒng)基本原理一、段頁(yè)式系統(tǒng)基本原理 圖圖4-20 4-20 圖圖4-214-21 段號(hào)段號(hào)+ +段內(nèi)頁(yè)號(hào)段內(nèi)頁(yè)號(hào)+ +頁(yè)內(nèi)地址頁(yè)內(nèi)地址 注意：注意： 對(duì)用戶而言，仍然是二維編址。對(duì)用戶而言，仍然是二維編址。 對(duì)系統(tǒng)而言，則是三維編址對(duì)系統(tǒng)而言，則是三維編址 v 二、地址變換二、地址變換 圖圖4-224-22 三次訪內(nèi)存操作，為提高速度，在地址變換機(jī)構(gòu)三次訪內(nèi)存操作，為提高速度，在地址變換機(jī)構(gòu)中增設(shè)一高速緩沖寄存器（中增設(shè)一

21、高速緩沖寄存器（CacheCache）v 4.5.1 4.5.1 引入引入.1 1.常規(guī)存儲(chǔ)管理的特征：常規(guī)存儲(chǔ)管理的特征： 一次性（指全部裝入）、一次性（指全部裝入）、 駐留性（指駐留在內(nèi)存不換出）駐留性（指駐留在內(nèi)存不換出）、2 2 局部性原理、局部性原理 時(shí)間局部性：如循環(huán)執(zhí)行時(shí)間局部性：如循環(huán)執(zhí)行 空間局部性：如順序執(zhí)行?？臻g局部性：如順序執(zhí)行。、3 3 虛擬存貯器、虛擬存貯器 具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)系統(tǒng)。存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)系統(tǒng)。 實(shí)質(zhì)：以時(shí)間換空間，但時(shí)間犧牲不大。實(shí)質(zhì)：以時(shí)間換空間，但時(shí)間犧

22、牲不大。 虛擬大小由虛擬大小由_決定。決定。v 需要?jiǎng)討B(tài)重定位需要?jiǎng)討B(tài)重定位v 一、請(qǐng)求分頁(yè)系統(tǒng)一、請(qǐng)求分頁(yè)系統(tǒng) 以頁(yè)為單位轉(zhuǎn)換以頁(yè)為單位轉(zhuǎn)換 需硬件：需硬件：（1 1）請(qǐng)求分頁(yè)的頁(yè)表機(jī)制）請(qǐng)求分頁(yè)的頁(yè)表機(jī)制（2 2）缺頁(yè)中斷）缺頁(yè)中斷（3 3）地址變換機(jī)構(gòu)）地址變換機(jī)構(gòu) 需實(shí)現(xiàn)請(qǐng)求分頁(yè)機(jī)制的軟件（置換軟件等）需實(shí)現(xiàn)請(qǐng)求分頁(yè)機(jī)制的軟件（置換軟件等）v 二、請(qǐng)求分段系統(tǒng)二、請(qǐng)求分段系統(tǒng) 以段為單位轉(zhuǎn)換以段為單位轉(zhuǎn)換: :（1 1）請(qǐng)求分段的段表結(jié)構(gòu)）請(qǐng)求分段的段表結(jié)構(gòu)（2 2）缺段中斷）缺段中斷（3 3）地址變換機(jī)構(gòu)）地址變換機(jī)構(gòu) 需實(shí)現(xiàn)請(qǐng)求分段機(jī)制的軟件（置換軟件等）需實(shí)現(xiàn)請(qǐng)求分段機(jī)制的軟件（

23、置換軟件等）v 1 1離散性：部分裝入離散性：部分裝入（若連續(xù)則不可能提供虛存），無(wú)法支持大（若連續(xù)則不可能提供虛存），無(wú)法支持大作業(yè)小內(nèi)存運(yùn)行作業(yè)小內(nèi)存運(yùn)行v 2 2多次性：局部裝入，多次裝入。多次性：局部裝入，多次裝入。v 3 3對(duì)換性：對(duì)換性：v 4 4虛擬性虛擬性. .v4.6.1 4.6.1 請(qǐng)求分頁(yè)中的數(shù)據(jù)結(jié)構(gòu)及硬件支持請(qǐng)求分頁(yè)中的數(shù)據(jù)結(jié)構(gòu)及硬件支持一、頁(yè)表機(jī)制一、頁(yè)表機(jī)制頁(yè)表項(xiàng)：頁(yè)表項(xiàng)：二、缺頁(yè)中斷機(jī)構(gòu)：可在指令執(zhí)行期間產(chǎn)生（如圖二、缺頁(yè)中斷機(jī)構(gòu)：可在指令執(zhí)行期間產(chǎn)生（如圖4-234-23）轉(zhuǎn)入缺頁(yè)中斷處理程序。轉(zhuǎn)入缺頁(yè)中斷處理程序。三、地址變換機(jī)構(gòu)三、地址變換機(jī)構(gòu)比較簡(jiǎn)單分頁(yè)機(jī)

24、制，增加了中斷處理，比較簡(jiǎn)單分頁(yè)機(jī)制，增加了中斷處理，圖圖4.244.24頁(yè)號(hào)頁(yè)號(hào)物理塊物理塊號(hào)號(hào)狀態(tài)位狀態(tài)位P P訪問字訪問字段段A A修改位修改位M M外存地外存地址址v一、最小物理塊數(shù)一、最小物理塊數(shù)不同的作業(yè)要求不同。不同的作業(yè)要求不同。如：允許間接尋址：則如：允許間接尋址：則至少要求至少要求3 3個(gè)物理塊。個(gè)物理塊。MovMov A, B A, B v 二、頁(yè)面分配和置換策略。二、頁(yè)面分配和置換策略。1 1 固定分配局部置換。固定分配局部置換。 缺點(diǎn)：難以確定固定分配的頁(yè)數(shù)缺點(diǎn)：難以確定固定分配的頁(yè)數(shù).(.(少：置換少：置換率高率高 多：浪費(fèi)多：浪費(fèi)) ).2 2.可變分配全局置換可

25、變分配全局置換.3 3.可變分配局部置換可變分配局部置換 根據(jù)進(jìn)程的缺頁(yè)率進(jìn)行頁(yè)面數(shù)調(diào)整，進(jìn)程之根據(jù)進(jìn)程的缺頁(yè)率進(jìn)行頁(yè)面數(shù)調(diào)整，進(jìn)程之間相互不會(huì)影響。間相互不會(huì)影響。v 1 1平均分配算法平均分配算法v 2 2按進(jìn)程大小比例分配算法：按進(jìn)程大小比例分配算法：v 3 3考慮優(yōu)先權(quán)分配算法考慮優(yōu)先權(quán)分配算法 mssbiiniiss1v 1.1.調(diào)入時(shí)機(jī)：調(diào)入時(shí)機(jī)： 預(yù)調(diào)：（根據(jù)空間局部性）預(yù)調(diào)：（根據(jù)空間局部性） 目前：成功率目前：成功率5050 請(qǐng)求調(diào)：較費(fèi)系統(tǒng)開銷請(qǐng)求調(diào)：較費(fèi)系統(tǒng)開銷 各有優(yōu)劣各有優(yōu)劣v 2 2從何處調(diào)頁(yè)：從何處調(diào)頁(yè)： 對(duì)換區(qū)：修改過的頁(yè)被換出時(shí)入對(duì)換區(qū)，對(duì)換區(qū)：修改過的頁(yè)被換

26、出時(shí)入對(duì)換區(qū)， 快快 文件區(qū)：文件區(qū)：稍慢稍慢 對(duì)共享頁(yè)，應(yīng)判斷其是否在內(nèi)存區(qū)。對(duì)共享頁(yè)，應(yīng)判斷其是否在內(nèi)存區(qū)。v 3.3.頁(yè)面調(diào)入過程頁(yè)面調(diào)入過程v 目的：減少對(duì)換量，提高系統(tǒng)性能目的：減少對(duì)換量，提高系統(tǒng)性能 v 4.7.1 4.7.1 最佳置換算法和先進(jìn)先出算法最佳置換算法和先進(jìn)先出算法 一、最佳置換算法（理論上的）一、最佳置換算法（理論上的）v 目的：減少對(duì)換量，提高系統(tǒng)性能目的：減少對(duì)換量，提高系統(tǒng)性能 v 4.7.1 4.7.1 最佳置換算法和先進(jìn)先出算法最佳置換算法和先進(jìn)先出算法 二、二、FIFOFIFOv 一、算法描述一、算法描述 將將“最近的過去最近的過去”，作為，作為“最近

27、的將來最近的將來”。圖圖4-274-27v 二、二、LRULRU算法的硬件支持：（用來記錄誰(shuí)最近最久未訪問）算法的硬件支持：（用來記錄誰(shuí)最近最久未訪問）1 1 位移寄存器：（定時(shí)右移）位移寄存器：（定時(shí)右移）R=RR=Rn-1n-1R R0 0圖圖4-284-28v 2 2棧：棧： 當(dāng)進(jìn)程訪問某頁(yè)時(shí)，將其移出壓入當(dāng)進(jìn)程訪問某頁(yè)時(shí)，將其移出壓入“棧頂棧頂”，“棧底棧底”換出。換出。圖圖4-294-29v 一、簡(jiǎn)單算法：一、簡(jiǎn)單算法： 設(shè)一訪問位：設(shè)一訪問位：圖圖4-304-30 循環(huán)掃描，每次掃描時(shí)將訪問位復(fù)位。循環(huán)掃描，每次掃描時(shí)將訪問位復(fù)位。v 二、改進(jìn)：二、改進(jìn)：A=0; M=0A=0;

28、M=0v 一、最少使用（是頻率）一、最少使用（是頻率） 與與LRULRU類似（記錄訪問次數(shù)），設(shè)置一個(gè)訪問計(jì)數(shù)器。類似（記錄訪問次數(shù)），設(shè)置一個(gè)訪問計(jì)數(shù)器。v 二、頁(yè)面緩沖算法：二、頁(yè)面緩沖算法： 特點(diǎn)：淘汰的頁(yè)只是修改標(biāo)志；若頁(yè)被修改過，則在特點(diǎn)：淘汰的頁(yè)只是修改標(biāo)志；若頁(yè)被修改過，則在欲復(fù)蓋它時(shí)回寫，否則成批回寫。欲復(fù)蓋它時(shí)回寫，否則成批回寫。 在欲重訪問該頁(yè)時(shí)，若頁(yè)換出則只需修改標(biāo)志。在欲重訪問該頁(yè)時(shí)，若頁(yè)換出則只需修改標(biāo)志。v 補(bǔ)充：補(bǔ)充：8038680386的頁(yè)描述的頁(yè)描述。v 段表：段表：v 段名段名 段長(zhǎng)段長(zhǎng) 段基址段基址 存取方式存取方式 訪問字段訪問字段A A 修改字段修改字

29、段M M 存在位存在位P P 增補(bǔ)位增補(bǔ)位 外存起址外存起址v 二、缺段中斷機(jī)構(gòu)：二、缺段中斷機(jī)構(gòu)： 段不定長(zhǎng)，處理起來比缺頁(yè)中斷復(fù)雜。段不定長(zhǎng)，處理起來比缺頁(yè)中斷復(fù)雜。圖圖4.314.31v 三、地址變換機(jī)構(gòu)三、地址變換機(jī)構(gòu) 圖圖4.324.32v 一、共享段表：（整個(gè)系統(tǒng)一張）一、共享段表：（整個(gè)系統(tǒng)一張） 圖圖4.334.33.1 1.共享進(jìn)程計(jì)數(shù)。共享進(jìn)程計(jì)數(shù)。.2 2.存取控制字段。存取控制字段。.3 3.段號(hào)：不同的進(jìn)程可以使用不同的段號(hào)去共享段號(hào)：不同的進(jìn)程可以使用不同的段號(hào)去共享段。段。段名段名段長(zhǎng)段長(zhǎng)內(nèi)存地內(nèi)存地址址狀態(tài)狀態(tài)外存地外存地址址共享進(jìn)程計(jì)數(shù)共享進(jìn)程計(jì)數(shù)狀態(tài)狀態(tài)進(jìn)程

30、名進(jìn)程名進(jìn)程號(hào)進(jìn)程號(hào)段號(hào)段號(hào)存取控存取控制制v 二、共享段的分配與回收二、共享段的分配與回收.1 1.分配：分配： 第一次訪問：分配內(nèi)存，（第一次訪問：分配內(nèi)存，（1 1）增加共享段表；）增加共享段表；（2 2）修改進(jìn)程段表。）修改進(jìn)程段表。 第二次訪問：（第二次訪問：（1 1）修改共享段表；（）修改共享段表；（2 2）修改進(jìn)）修改進(jìn)程段表。程段表。.2 2.回收：回收： （1 1）count=0 count=0 （2 2）count0count0三、分段保護(hù)三、分段保護(hù).1 1.越界檢查越界檢查 段號(hào)越界檢查。段號(hào)越界檢查。 段內(nèi)偏移越界檢查。段內(nèi)偏移越界檢查。.2 2.存取控制檢查。存取控

31、制檢查。 R R；R/WR/W；E E.3 3.環(huán)保護(hù)機(jī)構(gòu)環(huán)保護(hù)機(jī)構(gòu) （1 1）內(nèi)環(huán)可訪問外環(huán)數(shù)據(jù)；）內(nèi)環(huán)可訪問外環(huán)數(shù)據(jù)； （2 2）外環(huán)可請(qǐng)求內(nèi)環(huán)服務(wù)。）外環(huán)可請(qǐng)求內(nèi)環(huán)服務(wù)。v實(shí)現(xiàn)實(shí)現(xiàn)LRULRU算法和算法和FIFOFIFO算法算法v要求要求 給出任意的輸入流、計(jì)算失效率。給出任意的輸入流、計(jì)算失效率。 輸入流長(zhǎng)度、輸入流長(zhǎng)度、cachecache尺寸可定制。尺寸可定制。 測(cè)試：測(cè)試： CacheCache5 5， 從從0 09 9可數(shù)字的任意排序，長(zhǎng)度為可數(shù)字的任意排序，長(zhǎng)度為3030。 例如：例如：12568,36536,56892,70495,36745,8734512568,3653

32、6,56892,70495,36745,87345v 虛地址：程序中的地址，如虛地址：程序中的地址，如 MOVE REG, 2000MOVE REG, 2000v 內(nèi)存管理單元（內(nèi)存管理單元（MMUMMU）：完成地址轉(zhuǎn)換（圖）：完成地址轉(zhuǎn)換（圖4.14.1）v 虛擬地址空間：二維：虛擬地址空間：二維：16k16k* *4G=64T4G=64T（LDT 8K LDT 8K GDT 8KGDT 8K）v 線性地址空間線性地址空間: : 一維：一維：4G4Gv 物理地址空間物理地址空間: : 一維：一維：4G4G選擇子偏移量：段機(jī)制313101500頁(yè)機(jī)制310線性地址物理地址v 段基地址段基地址v

33、 段界限段界限v 段屬性段屬性v 以上三者存儲(chǔ)在段描述符表中以上三者存儲(chǔ)在段描述符表中G G：粒度位，：粒度位，0 0時(shí)，段長(zhǎng)表示段格式的字節(jié)長(zhǎng)度，即一個(gè)段最長(zhǎng)可達(dá)時(shí)，段長(zhǎng)表示段格式的字節(jié)長(zhǎng)度，即一個(gè)段最長(zhǎng)可達(dá)1M1M字節(jié)；字節(jié)；1 1時(shí)，段長(zhǎng)表示段格式以時(shí)，段長(zhǎng)表示段格式以4K4K字節(jié)為一頁(yè)的頁(yè)目錄數(shù)，即一個(gè)字節(jié)為一頁(yè)的頁(yè)目錄數(shù)，即一個(gè)段最長(zhǎng)可達(dá)段最長(zhǎng)可達(dá)1M1M* *4K=4G4K=4GD D：表示缺省操作數(shù)的大小，：表示缺省操作數(shù)的大小，=0=0操作數(shù)為操作數(shù)為1616位。位。1 1為為3232位位v P:P:存在位。描述段是否在內(nèi)存存在位。描述段是否在內(nèi)存v S:S:表示該段是系統(tǒng)段（表示該段是系統(tǒng)段（0 0）還是用戶段（）還是用戶段（1 1）v DPL:DPL:該段的特權(quán)級(jí)該段的特權(quán)級(jí)v 類型：數(shù)據(jù)段還是代碼段類型：數(shù)據(jù)段還是代碼段v A:A:該段是否被訪問該段是否被訪問v 3 3位位: :為為0 0表示數(shù)據(jù)段，表示數(shù)據(jù)段，1 1表示代碼段表示代碼段v W:W:為為0 0表示不可寫，為表示不可寫，為1 1表示可寫表示可寫v R:R:該段可讀否該段可