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

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

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

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

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

5、 10位位 12位位00401b21h可分割為可分割為0000 0000 01 00 0000 0001 1011 0010 0001得物理塊號(hào)得物理塊號(hào)1150000 0000 0000 0111 0011對(duì)應(yīng)的物理地址為：對(duì)應(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段號(hào)段號(hào)段長(zhǎng)段長(zhǎng)基址基址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段號(hào)段號(hào) 段長(zhǎng)段長(zhǎng) 基址基址0123段表寄存器段表寄存器段表基址段表基址段表長(zhǎng)度段表長(zhǎng)度 段號(hào)段號(hào)s s 段內(nèi)偏移段內(nèi)偏移d d2100物理地址物理地址內(nèi)內(nèi)存存段表段表越界越界829

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

8、管理方式，段表和部分段的分頁(yè)情況和部分段的分頁(yè)情況如圖所示，頁(yè)面大小如圖所示，頁(yè)面大小為為1kb1kb。請(qǐng)問邏輯地。請(qǐng)問邏輯地址（址（2 2，25002500）對(duì)應(yīng)）對(duì)應(yīng)的物理地址是多少？的物理地址是多少？ 根據(jù)段號(hào)查得根據(jù)段號(hào)查得2 2號(hào)段號(hào)段的頁(yè)表地址為的頁(yè)表地址為2010h2010h，可到內(nèi)存可到內(nèi)存2010h2010h地址地址處讀得該段的頁(yè)表。處讀得該段的頁(yè)表。 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 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)4.2 4.2 程序的裝入和鏈接程序的裝入和鏈接4.3 4.3 連續(xù)分配方式連續(xù)分配方式4.4 4.4 基本分頁(yè)存儲(chǔ)管理方式基本分頁(yè)存儲(chǔ)管理方式4.5 4.5 基本分段存儲(chǔ)管理方式基本分段存儲(chǔ)管理方式4.6 4.6 虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念4.7 4.7 請(qǐng)求分頁(yè)存儲(chǔ)管理方式請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.8 4.8 頁(yè)面置換算法頁(yè)面置換算法4.9 4.9 請(qǐng)求分段存儲(chǔ)管理方式請(qǐng)求分段存儲(chǔ)管理方式4.6 4.6 虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念產(chǎn)生的原因：產(chǎn)生的原因：連續(xù)

10、分配、基本分頁(yè)和基本分段存儲(chǔ)管理方式都要求連續(xù)分配、基本分頁(yè)和基本分段存儲(chǔ)管理方式都要求將一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行，于是，會(huì)出現(xiàn)：將一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行，于是，會(huì)出現(xiàn)：1) 1) 作業(yè)很大，需求總?cè)萘砍^了內(nèi)存總?cè)萘俊?huì)因不能全部裝入內(nèi)作業(yè)很大，需求總?cè)萘砍^了內(nèi)存總?cè)萘?。?huì)因不能全部裝入內(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)存容量用用虛擬存儲(chǔ)器技術(shù)虛擬存儲(chǔ)器技術(shù)解決解決4.6 4.6 虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念常規(guī)存儲(chǔ)管理方式的特征：常規(guī)存儲(chǔ)管理方式的特征：一次性一次性 作業(yè)在運(yùn)行前需一次性地全部裝入內(nèi)存。作業(yè)每次運(yùn)行作業(yè)在運(yùn)行前需一次性地全部裝入內(nèi)存。作業(yè)每次運(yùn)行時(shí)，并非全部程序和數(shù)據(jù)都要用到，如果全部裝入，造成了對(duì)內(nèi)時(shí)，并非全部程序和數(shù)據(jù)都要用到，如果全部裝入，造成了對(duì)內(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)程會(huì)因等待盡管有的進(jìn)程會(huì)因等待i/oi/o而長(zhǎng)期等待，或有的程序模塊在運(yùn)行而長(zhǎng)期等待，或有的程序模塊在運(yùn)行過一次后就不再需要了，但它們都仍繼續(xù)占用寶貴的內(nèi)存資源。過一次后就不再需要了，但它們都仍繼續(xù)占用寶貴的內(nèi)存資源。一次性和駐留性是必需的嗎？一次性和駐留性是必需的嗎？一一. . 局部性原理局部性原理1. 1. 局部性原理：局部性原理： 指程序在執(zhí)行過程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行的指指程序在執(zhí)行過程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域?？梢粤畹刂泛椭噶畹牟僮鲾?shù)地址，分別局限于一定區(qū)域

13、?？梢员憩F(xiàn)為：表現(xiàn)為：1) 1) 時(shí)間局部性：一個(gè)數(shù)據(jù)結(jié)構(gòu)或指令在有限時(shí)間內(nèi)再次被時(shí)間局部性：一個(gè)數(shù)據(jù)結(jié)構(gòu)或指令在有限時(shí)間內(nèi)再次被訪問訪問. .2) 2) 空間局部性：一個(gè)區(qū)域再次被訪問空間局部性：一個(gè)區(qū)域再次被訪問. .4.6 4.6 虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念19681968年，年，denning.pdenning.p提出了局部性原理，為虛擬存儲(chǔ)技術(shù)提出了局部性原理，為虛擬存儲(chǔ)技術(shù)的發(fā)展奠定了理論基礎(chǔ)。的發(fā)展奠定了理論基礎(chǔ)。2 2、局部性原理的具體體現(xiàn)、局部性原理的具體體現(xiàn)程序在執(zhí)行時(shí)，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)程序在執(zhí)行時(shí)，大部分是順序執(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)多對(duì)一定數(shù)據(jù)結(jié)構(gòu)的操作，如數(shù)組操作，程序中存在相當(dāng)多對(duì)一定數(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）：是指具有請(qǐng)求調(diào)入功能和）：是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。種存儲(chǔ)器系統(tǒng)。交換單位交換單位: :頁(yè)或段頁(yè)或段4.6.2 4.6.2 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法1. 1.地址空間部分裝入：在程序裝入時(shí)，只將當(dāng)前需要執(zhí)地址空間部分裝入：在程序裝入時(shí)，只將當(dāng)前需要執(zhí)行的部分頁(yè)或段裝入到內(nèi)存，就可讓程序開始執(zhí)行

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

17、 2、3 3兩條功能稱之：兩條功能稱之：缺頁(yè)中斷處理（用于請(qǐng)求頁(yè)式管理）缺頁(yè)中斷處理（用于請(qǐng)求頁(yè)式管理）缺段中斷處理（用于請(qǐng)求段式管理）缺段中斷處理（用于請(qǐng)求段式管理）三三. . 引入虛擬存儲(chǔ)技術(shù)的好處引入虛擬存儲(chǔ)技術(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、擬存儲(chǔ)技術(shù)的特征虛擬存儲(chǔ)技術(shù)的特征3. 3. 虛擬性：提供大范圍的虛擬地址空間虛擬性：提供大范圍的虛擬地址空間( (通過通過物理內(nèi)存和快速外存相結(jié)合物理內(nèi)存和快速外存相結(jié)合). ).1. 1. 作業(yè)裝入的多次性作業(yè)裝入的多次性: : 不再一次性裝入不再一次性裝入2. 2. 對(duì)換性對(duì)換性: :注意注意: : 總?cè)萘坎怀^物理內(nèi)存和外存交換區(qū)容量之和總?cè)萘坎怀^物理內(nèi)存和外存交換區(qū)容量之和本章主要內(nèi)容本章主要內(nèi)容4.1 4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)4.2 4.2 程序的裝入和鏈接程序的裝入和鏈接4.3 4.3 連續(xù)分配方式連續(xù)分配方式4.4 4.4 基本分頁(yè)存儲(chǔ)管理方式基本分頁(yè)存儲(chǔ)管理

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

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

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

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

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

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

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

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

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

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

29、形成物理地址形成物理地址修改訪問字段和修改位修改訪問字段和修改位修改快表修改快表組織讀缺頁(yè)命令組織讀缺頁(yè)命令啟動(dòng)啟動(dòng)i/oi/o開始開始頁(yè)號(hào)頁(yè)號(hào)頁(yè)表長(zhǎng)度？頁(yè)表長(zhǎng)度？越界中斷越界中斷頁(yè)表項(xiàng)在快表中？頁(yè)表項(xiàng)在快表中？y yn ny yn n內(nèi)存滿否？?jī)?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ù)少于此值時(shí)，進(jìn)程將無小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(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)存時(shí)，將涉及到三個(gè)問題：為進(jìn)程分配內(nèi)存時(shí)，將涉及到三個(gè)問題：第一，最小物理塊數(shù)的確定；第一，最小物理塊數(shù)的確定；第二，物理塊的分配策略；第二，物理塊的分配策略；第三，物理塊的分配算法。第三，物理塊的分配算法。4.7.2 4.7.2 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法2. 2. 物理塊的分配策略物理塊的分配策略 固定分配局部置換固定分配局部置換 為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，整個(gè)運(yùn)行期為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，整個(gè)

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

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

33、配策略時(shí)，如何將系統(tǒng)中可供分配的所有物理塊分配給各進(jìn)用固定分配策略時(shí)，如何將系統(tǒng)中可供分配的所有物理塊分配給各進(jìn)程?？刹捎靡韵聨追N算法：程?？刹捎靡韵聨追N算法：1. 1. 平均分配平均分配: : 內(nèi)存塊平均分給各進(jìn)程。小進(jìn)程有利內(nèi)存塊平均分給各進(jìn)程。小進(jìn)程有利, ,長(zhǎng)進(jìn)程中斷率高。長(zhǎng)進(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)頁(yè)策略調(diào)頁(yè)策略2. 2. 預(yù)調(diào)頁(yè)：在發(fā)生缺頁(yè)需要調(diào)入某頁(yè)時(shí)，一次調(diào)入該頁(yè)以預(yù)調(diào)頁(yè)：在發(fā)生缺頁(yè)需要調(diào)入某頁(yè)時(shí)，一次調(diào)入該頁(yè)以及相鄰的幾個(gè)頁(yè)

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

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

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

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