操作系統(tǒng)課件前四章作業(yè)答案

1、第四章 存儲(chǔ)管理 第四章 存儲(chǔ)管理 4.1 存儲(chǔ)管理的基本概念存儲(chǔ)管理的基本概念 4.2 早期的存儲(chǔ)管理早期的存儲(chǔ)管理 4.3 分頁(yè)存儲(chǔ)管理分頁(yè)存儲(chǔ)管理 4.4 請(qǐng)求分頁(yè)存儲(chǔ)管理請(qǐng)求分頁(yè)存儲(chǔ)管理 4.5 分段存儲(chǔ)管理分段存儲(chǔ)管理 4.6 段頁(yè)式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理 4.7 WindowsNT虛擬內(nèi)存管理虛擬內(nèi)存管理 第四章 存儲(chǔ)管理 4.1 存儲(chǔ)管理的基本概念存儲(chǔ)管理的基本概念 4.1.1 存儲(chǔ)管理研究的四個(gè)問(wèn)題存儲(chǔ)管理研究的四個(gè)問(wèn)題 (1) 存儲(chǔ)分配問(wèn)題存儲(chǔ)分配問(wèn)題=存儲(chǔ)器被多個(gè)進(jìn)程共享的問(wèn)題。重點(diǎn)是研究如何對(duì)進(jìn)程分配存儲(chǔ)器空間的算法。處理器共享通過(guò)在時(shí)間上的劃分來(lái)實(shí)現(xiàn)，而存儲(chǔ)器共享通過(guò)在

2、空間上的劃分來(lái)實(shí)現(xiàn)。 (2) 裝配模塊的地址再定位問(wèn)題裝配模塊的地址再定位問(wèn)題。研究各種地址變換機(jī)構(gòu)， 以及靜態(tài)和動(dòng)態(tài)再定位方法。 (3) 存儲(chǔ)保護(hù)問(wèn)題存儲(chǔ)保護(hù)問(wèn)題。 研究保護(hù)各類程序、 數(shù)據(jù)區(qū)的方法。 (4) 存儲(chǔ)擴(kuò)充問(wèn)題存儲(chǔ)擴(kuò)充問(wèn)題。 主要研究虛擬存儲(chǔ)器問(wèn)題及其各種調(diào)度算法。 第四章 存儲(chǔ)管理 4.1.2 地址再定位地址再定位 1. 地址空間和存儲(chǔ)空間地址空間和存儲(chǔ)空間 裝配模塊 源程序 進(jìn)程編譯，鏈接加載符號(hào)指令變量類型高級(jí)語(yǔ)言結(jié)構(gòu)二進(jìn)制指令對(duì)存儲(chǔ)空間的引用字節(jié)大小以及排列方式變成順序結(jié)構(gòu)裝配模塊內(nèi)容+進(jìn)程環(huán)境Transform內(nèi)存管理：內(nèi)存管理：Transform：LASpace -

3、PASpace第四章 存儲(chǔ)管理 2. 地址定位發(fā)生的時(shí)態(tài)地址定位發(fā)生的時(shí)態(tài) 時(shí)間程序設(shè)計(jì)時(shí)或叫做編寫(xiě)程序時(shí)編譯或匯編時(shí)加載模塊產(chǎn)生時(shí)加載時(shí)運(yùn)行時(shí)第四章 存儲(chǔ)管理 2. 地址的靜態(tài)再定位，發(fā)生在地址的靜態(tài)再定位，發(fā)生在加載時(shí)加載時(shí) 80 KB50 KB030 KOSOS作業(yè)A地址空間作業(yè)A地址空間030 KB0110 KB主存主存80 KBLoaderLoaderTransform：LA - LA + Allocation Start Address 第四章 存儲(chǔ)管理 動(dòng)態(tài)地址再定位動(dòng)態(tài)地址再定位發(fā)生在發(fā)生在運(yùn)行時(shí)運(yùn)行時(shí) L 1，5001 2 3 4 5作業(yè)地址空間0100500600L 1，5

4、001 2 3 4 5010001100150016001000500處理機(jī)一側(cè) 存儲(chǔ)器一側(cè)+BR有效地址再定位寄存器600LR界限寄存器主存Transform：LA - LA + BR如果LA + BR BR+LR，則地址訪問(wèn)時(shí)安全的第四章 存儲(chǔ)管理 靜態(tài)再定位與動(dòng)態(tài)再定位的區(qū)別Load 1, 500123450100500Load 1, 150012345100011001500Start Address=1000靜態(tài)Load 1, 500123450100500Load 1, 50012345100011001500BR=1000動(dòng)態(tài)在加載時(shí)解析地址在運(yùn)行時(shí)解析地址第四章 存儲(chǔ)管理 Lo

5、ad 1, 500123450100500Load 1, 50012345100011001500BR=1000動(dòng)態(tài)Load 1, 50012345200021002500BR=2000第四章 存儲(chǔ)管理 程序能否在程序能否在內(nèi)存中移動(dòng)內(nèi)存中移動(dòng)程序在存儲(chǔ)程序在存儲(chǔ)空間中是否空間中是否連續(xù)存儲(chǔ)連續(xù)存儲(chǔ)是否有利于是否有利于程序共享程序共享執(zhí)行效率執(zhí)行效率應(yīng)用領(lǐng)應(yīng)用領(lǐng)域域靜態(tài)不能。除非再裝載一次，這對(duì)已經(jīng)開(kāi)始運(yùn)行的程序不可行需要不利于高。因?yàn)槲锢淼刂肥窃谘b載時(shí)得到解析的，因此執(zhí)行每條指令時(shí)，不需要再解析嵌入式控制器，DSP，Cray超級(jí)計(jì)算機(jī)動(dòng)態(tài)可以。只需修改寄存器BR的內(nèi)容即可不需要。為每個(gè)分散的

6、內(nèi)存區(qū)域增加一對(duì)寄存器利于低。因?yàn)槲锢淼刂肥窃谶\(yùn)行中邊解析邊執(zhí)行，但是可以通過(guò)硬件來(lái)加速PC，服務(wù)器靜態(tài)地址再定位與動(dòng)態(tài)地址在定位比較第四章 存儲(chǔ)管理 4.1.3 虛擬存儲(chǔ)器概念的引入虛擬存儲(chǔ)器概念的引入 虛擬存儲(chǔ)器的基本思想是把作業(yè)地址空間和實(shí)際主存的存儲(chǔ)空間， 視為兩個(gè)不同的概念。一個(gè)計(jì)算機(jī)系統(tǒng)為程序員提供了一個(gè)足夠大的地址空間，而完全不必考慮實(shí)際主存的大小。 由此，可以引出虛擬存儲(chǔ)器更一般的概念， 即把系統(tǒng)提供的這個(gè)地址空間，想象成有一個(gè)存儲(chǔ)器(虛存)與之對(duì)應(yīng)，正像存儲(chǔ)空間有一個(gè)主存與之對(duì)應(yīng)一樣。這就是說(shuō)，虛虛擬存儲(chǔ)器實(shí)際上是一個(gè)地址空間擬存儲(chǔ)器實(shí)際上是一個(gè)地址空間。 第四章 存儲(chǔ)管理

7、根據(jù)地址空間結(jié)構(gòu)不同， 虛擬存儲(chǔ)器有兩種形式。 一種是單段式虛存單段式虛存， 它是一個(gè)連續(xù)的線性地址空間，其地址順序?yàn)椋?，1，2，n-1。其中n=2k, k為CPU給出的有效地址的長(zhǎng)度。另一種是多段式虛存多段式虛存，它是把地址空間分成若干段，而每一段Si是一個(gè)連續(xù)的線性地址空間。每個(gè)地址可用Si, W來(lái)表示，Si為段名或段號(hào)，W為段內(nèi)的相對(duì)地址。 VA = Bi + W第四章 存儲(chǔ)管理 私有用戶地址空間（程序、數(shù)據(jù)）用戶棧進(jìn)程控制信息處理器狀態(tài)信息進(jìn)程標(biāo)識(shí)符共享地址空間Linux進(jìn)程的虛擬地址空間0 x080480000 xffffffffVAS=232=4GCPUMMUVAMemoryPA

8、CPU chip動(dòng)態(tài)地址再定位第四章 存儲(chǔ)管理 4.2 早期的存儲(chǔ)管理早期的存儲(chǔ)管理 4.2.1 單一連續(xù)分配單一連續(xù)分配 作業(yè)操作系統(tǒng)未用32 KB64 KB160 KB分配給用戶作業(yè)的空間圖圖 4.4 單一連續(xù)分配單一連續(xù)分配 特點(diǎn)特點(diǎn)：p 單道處理系統(tǒng)p 作業(yè)起始地址固定p 內(nèi)存資源和處理器 沒(méi)有得到充分使用p 作業(yè)需要的內(nèi)存 物理內(nèi)存時(shí)， 作業(yè)無(wú)法運(yùn)行第四章 存儲(chǔ)管理 4.2.2 分區(qū)分配分區(qū)分配 (a)分區(qū)號(hào)12345容量8 KB32 KB32 KB120 KB520 KB位置312 KB320 KB352 KB384 KB504 KB狀態(tài)在使用在使用在使用未用未用(b)操作系統(tǒng)50

9、4 KB384 KB352 KB320 KB312 KB0520 KB120 KB32 KB32 KB8 KB312 KB特點(diǎn)：特點(diǎn)：p 分區(qū)大小固定，不能改變p 當(dāng)存在一個(gè)分區(qū)：狀態(tài)=“未用” / capacity Required Memory 則分配給作業(yè)，否則作業(yè)不能運(yùn)行p 內(nèi)存資源利用率低第四章 存儲(chǔ)管理 表 4 1 固定式分區(qū)舉例 分區(qū)號(hào)分區(qū)號(hào) 分區(qū)容量分區(qū)容量 作業(yè)容量作業(yè)容量 剩余容量剩余容量 123458KB32KB32KB120KB520KB1KB9KB9KB33KB121KB7KB23KB23KB87KB399KB合 計(jì) 712 KB 173 KB 539 KB 第四章

10、存儲(chǔ)管理 2. 可變式分區(qū)法可變式分區(qū)法（ b）（ c）作業(yè)6256 KB作業(yè)5128 KB作業(yè)424 KB作業(yè)3 (120 KB)作業(yè)2 (32 KB)作業(yè)1 (8 KB)OS1024 KB504 KB384 KB352 KB320 KB312 KB0作業(yè)6 (256 KB)作業(yè)5 (128 KB)作業(yè)4 (24 KB)888 KB632 KB376 KB（ a）作業(yè)3 (120 KB)作業(yè)2 (32 KB)作業(yè)1 (8 KB)OS1024 KB504 KB384 KB352 KB320 KB312 KB0作業(yè)1 (8 KB)OS0作業(yè)6 (256 KB)作業(yè)5 (128 KB)作業(yè)4 (2

11、4 KB)1624 KB504 KB352 KB320 KB312 KB888 KB632 KB376 KB圖 4.6 可變式分區(qū)的例子合并合并第四章 存儲(chǔ)管理 表 4 - 2(a) 已分配已分配的分區(qū)狀態(tài)表 分區(qū)號(hào) 分區(qū)容量 分區(qū)位置 狀 態(tài) 123458KB32KB-120KB-321KB320KB-384KB-已分配 已分配 空 項(xiàng) 已分配 空 項(xiàng) 分區(qū)號(hào) 分區(qū)容量 分區(qū)位置 狀 態(tài) 12-32KB520KB-352KB504KB-可用 可用-表 4 - 2(b) 未分配未分配的分區(qū)狀態(tài)表第四章 存儲(chǔ)管理 申請(qǐng)分配一個(gè)xKB大小的分區(qū)置空白區(qū)號(hào)f =1f 大于最后一個(gè)空白區(qū)號(hào)？空白區(qū)可用

12、？保存空白區(qū)的起始地址空白區(qū) f的大小xKB空白區(qū)的狀態(tài)=空項(xiàng)修改空白區(qū)的大小和起始地址在已分配表中找一個(gè)狀態(tài)=空項(xiàng)的分區(qū)號(hào) P置分區(qū)P的大小為 xKB置分區(qū)起始地址置分區(qū)狀態(tài)為已分配返回一個(gè)分區(qū)號(hào)此次無(wú)法分配f +1 fYYNN=判斷空白區(qū)是否可用判斷空白區(qū)是否可用判斷空白區(qū)大小判斷空白區(qū)大小是否滿足要求是否滿足要求修改內(nèi)存修改內(nèi)存分配狀態(tài)分配狀態(tài)第四章 存儲(chǔ)管理 請(qǐng)求釋放一個(gè)分區(qū) P保存分區(qū)P的大小和起始地址置分區(qū)的狀態(tài)為空項(xiàng)分區(qū)P有鄰接的空白區(qū)?修改新空白區(qū)的大小起始地址和狀態(tài)返回修改空白區(qū)的狀態(tài)修改新空白區(qū)的大小和起始地址在未分配表中找一空表目置新空白區(qū)大小和起始地址置空白區(qū)狀態(tài)為可用

13、在兩個(gè)空白區(qū)之間有一個(gè)空白區(qū)N圖 4.8 可變式分區(qū)中釋放一個(gè)分區(qū)的流程 第四章 存儲(chǔ)管理 可變式分區(qū)分配法分配分區(qū)的算法當(dāng)有多個(gè)空白區(qū)都可以滿足作業(yè)內(nèi)存需求時(shí)，究竟該選當(dāng)有多個(gè)空白區(qū)都可以滿足作業(yè)內(nèi)存需求時(shí)，究竟該選擇哪個(gè)分區(qū)予以分配？有如下幾種策略擇哪個(gè)分區(qū)予以分配？有如下幾種策略p 最佳適應(yīng)算法（Best Fit） min xi | xi RM 其中xi是分區(qū)的容量，RM是作業(yè)請(qǐng)求內(nèi)存分配的大小p 最差適應(yīng)算法（Worst Fit） max xi | xi RMp 最先適應(yīng)算法（First Fit） xi | start address of xi is min / xi RM第四章 存

14、儲(chǔ)管理 3. 可再定位式分區(qū)分配可再定位式分區(qū)分配 圖 4.9 可再定位式分區(qū)分配的靠攏過(guò)程 作業(yè)7(256 KB)(a)(b)(c)作業(yè)6 (256 KB)作業(yè)5 (128 KB)作業(yè)4 (24 KB)作業(yè)1 (8 KB)OS作業(yè)7 (256 KB)作業(yè)6 (256 KB)作業(yè)5 (128 KB)作業(yè)4 (24 KB)作業(yè)1(8 KB)OS01024 KB504 KB352 KB320 KB312 KB888 KB652 KB376 KB作業(yè)6 (256 KB)作業(yè)5 (128 KB)作業(yè)4 (24 KB)作業(yè)1 (8 KB)OS第四章 存儲(chǔ)管理 圖 4.10 利用浮動(dòng)寄存器進(jìn)行地址變換 L

15、 1， 352 K + 980001557100352 KB352 KB + 50352 KB + 9800376 KB352 KB + 9800 -32 KB+L 1， 352 KB + 980001557100320KB320 KB + 50320 KB + 9800344 KB計(jì)算地址地址變換有效地址浮動(dòng)寄存器第四章 存儲(chǔ)管理 圖圖 4.11 可再定位式分區(qū)分配算法流程可再定位式分區(qū)分配算法流程 請(qǐng)求分配一個(gè)大小為xKB的分區(qū)有大于xKB的空白區(qū)嗎？空白區(qū)的總和xKB？執(zhí)行靠攏操作并修改狀態(tài)表分配一個(gè)分區(qū)并修改狀態(tài)表返回一個(gè)分區(qū)號(hào)此時(shí)無(wú)法分配YYNN沒(méi)有足夠空白區(qū)時(shí)再靠攏沒(méi)有足夠空白區(qū)時(shí)

16、再靠攏第四章 存儲(chǔ)管理 4. 多重分區(qū)分配多重分區(qū)分配 如果我們不想采用靠攏的辦法，又想使存儲(chǔ)器分區(qū)的碎片問(wèn)題適當(dāng)?shù)氐玫浇鉀Q，那么可以采用多重分區(qū)分配方案。通常一個(gè)作業(yè)由一些相對(duì)獨(dú)立的程序段和數(shù)據(jù)段組成，如主程序、子程序、數(shù)據(jù)組等。這些程序段中的每一個(gè)在邏輯上必須是連續(xù)的， 但是相應(yīng)的各分區(qū)卻不要求是連續(xù)的，只要有足夠的保護(hù)措施就可以了。例如一個(gè)要求 100 KB存儲(chǔ)空間的作業(yè)，實(shí)際上由五個(gè) 20 KB的段組成時(shí)，則可以分配給該作業(yè)一個(gè)100 KB的分區(qū)或者五個(gè)20 KB的分區(qū)，或者兩個(gè) 40 KB的分區(qū)和一個(gè) 20 KB的分區(qū)等等。這種給一個(gè)作業(yè)分配一個(gè)以上分區(qū)給一個(gè)作業(yè)分配一個(gè)以上分區(qū)的方

17、法，稱為多重分區(qū)分配的方法，稱為多重分區(qū)分配。采用這種方法時(shí)，作業(yè)可以在其執(zhí)行期間申請(qǐng)附加的分區(qū)。 第四章 存儲(chǔ)管理 5. 分區(qū)的保護(hù)措施分區(qū)的保護(hù)措施 作業(yè) 2的分區(qū)60 KB124 KB256 KB060 KB基址寄存器64 KB限長(zhǎng)寄存器作業(yè) 2的分區(qū)60 KB124 KB256 KB060 KB下界寄存器124 KB上界寄存器圖 4.12 分區(qū)的界地址寄存器保護(hù) 分區(qū)保護(hù)的特點(diǎn)：分區(qū)保護(hù)的特點(diǎn)： 在運(yùn)行過(guò)程中，每次訪問(wèn)存儲(chǔ)器 時(shí)進(jìn)行越界檢查 只需要一組一組寄存器組就可以第四章 存儲(chǔ)管理 6. 分區(qū)分配方案的評(píng)價(jià)分區(qū)分配方案的評(píng)價(jià) 分區(qū)分配方案的主要優(yōu)點(diǎn)可歸納如下： (1) 實(shí)現(xiàn)了主存的

18、共享實(shí)現(xiàn)了主存的共享，因而有助于多道程序設(shè)計(jì)，更有效地利用了處理機(jī)和I/O設(shè)備，從而使系統(tǒng)的吞吐量和作業(yè)周轉(zhuǎn)時(shí)間得到了相應(yīng)的改善。至于主存利用率，可變式分區(qū)比固定式分區(qū)高些， 可再定位式分區(qū)則更高些。 (2) 相對(duì)于后面介紹的存儲(chǔ)管理方式，本方案為實(shí)現(xiàn)分區(qū)分配所使用的表格、占用的存儲(chǔ)容量相對(duì)較少，算法也相對(duì)簡(jiǎn)單。 (3) 實(shí)現(xiàn)存儲(chǔ)保護(hù)的措施也比較簡(jiǎn)單。 (4) 多重分區(qū)分配方案能實(shí)現(xiàn)對(duì)子程序、 數(shù)據(jù)段的共享。 第四章 存儲(chǔ)管理 分區(qū)分配的主要缺點(diǎn)有： (1) 主存仍不能充分利用，除了可再定位式分區(qū)法外，都存在著嚴(yán)重的碎片問(wèn)題碎片問(wèn)題。另外，即使不把存儲(chǔ)器分碎，整個(gè)空白區(qū)也可能因容納不下一個(gè)作業(yè)

19、而造成浪費(fèi)空白區(qū)也可能因容納不下一個(gè)作業(yè)而造成浪費(fèi)。 例如，有 156 KB的存儲(chǔ)空間可用，而某個(gè)作業(yè)序列是由 100 KB和 60 KB的作業(yè)組成的。如果分配了一個(gè) 100 KB的分區(qū)后，則剩下的 56 KB存儲(chǔ)空間就要浪費(fèi)掉。 第四章 存儲(chǔ)管理 (2) 不能實(shí)現(xiàn)對(duì)主存的擴(kuò)充不能實(shí)現(xiàn)對(duì)主存的擴(kuò)充。 因此， 作業(yè)的大小受到主存可用空間的限制。 (3) 和單一連續(xù)分配一樣，要求一個(gè)作業(yè)在執(zhí)行之前必須全部全部裝入主存，因此在主存中可能包含從未使用過(guò)的信息。 (4) 采用靠攏方法，雖然能解決碎片問(wèn)題，但有時(shí)需移需移動(dòng)大量信息動(dòng)大量信息，從而損失了處理機(jī)時(shí)間。 (5) 除多重分區(qū)外，幾個(gè)共行作業(yè)之間不

20、能共享不能共享存入主存的單一信息副本(如公用子程序、數(shù)據(jù)段等)。 第四章 存儲(chǔ)管理 回顧回顧1、可執(zhí)行文件（裝載模塊）三個(gè)地址空間、可執(zhí)行文件（裝載模塊）三個(gè)地址空間Load 1, 500123450100500Load 1, 50012345磁盤空間邏輯(相對(duì))地址空間Load 1, 50012345x100+x500+x物理地址空間所有地址從程序入口地址開(kāi)始編號(hào)程序在內(nèi)存中占據(jù)的地址空間映射映射第四章 存儲(chǔ)管理 回顧回顧2、靜態(tài)再定位和動(dòng)態(tài)在定位、靜態(tài)再定位和動(dòng)態(tài)在定位Load 1, 500123450100Jmp 400500Load 1, 500+x12345x100+xJmp 400

21、+x500+x靜態(tài)定位發(fā)生在裝載時(shí)發(fā)生在裝載時(shí)一旦裝載，程序不能一旦裝載，程序不能再浮動(dòng)，否則會(huì)出現(xiàn)再浮動(dòng)，否則會(huì)出現(xiàn)地址引用錯(cuò)亂地址引用錯(cuò)亂400400+x第四章 存儲(chǔ)管理 Load 1, 500123450100Jmp 400500Load 1, 50012345x100+xJmp 400500+x動(dòng)態(tài)定位發(fā)生在某條代碼執(zhí)行時(shí)，發(fā)生在某條代碼執(zhí)行時(shí)，當(dāng)這條代碼引用了當(dāng)這條代碼引用了某個(gè)地址時(shí)，才進(jìn)行某個(gè)地址時(shí)，才進(jìn)行地址的定位地址的定位400400+xJmp 400得到邏輯地址400再定位寄存器 x+400+x物理地址當(dāng)運(yùn)行這條指令時(shí)，才進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換第四章 存儲(chǔ)管理 4.3

22、 分頁(yè)存儲(chǔ)管理分頁(yè)存儲(chǔ)管理 4.3.1 分頁(yè)原理分頁(yè)原理 解決作業(yè)的內(nèi)存空間必須連續(xù)的問(wèn)題解決作業(yè)的內(nèi)存空間必須連續(xù)的問(wèn)題進(jìn)程地址空間(3K+10)B0kB1kB2kB3kBP0P1P2P3OSOS內(nèi)存地址空間B0B1B2B3B4B5B6B7B8B9 PMTP0 - B3P1 - B4P2 - B6P3 - B810第四章 存儲(chǔ)管理 分頁(yè)管理的特點(diǎn)分頁(yè)管理的特點(diǎn)：1、頁(yè)面的大小是固定的，通常是2k，如256B，1KB，4KB2、內(nèi)存塊的大小 = 頁(yè)面的大小3、連續(xù)頁(yè)所分配的塊不需要連續(xù)分頁(yè)管理的優(yōu)點(diǎn)分頁(yè)管理的優(yōu)點(diǎn)：1、內(nèi)存碎片小內(nèi)存碎片小。內(nèi)存碎片只能發(fā)生在分配給進(jìn)程地址空間的最后一頁(yè)的內(nèi)存塊

23、中，而塊的大小通常很小，因此可以想象碎片也很小。2、不用浮動(dòng)程序的內(nèi)存空間就可以實(shí)現(xiàn)空閑空間的利用不用浮動(dòng)程序的內(nèi)存空間就可以實(shí)現(xiàn)空閑空間的利用。因?yàn)橹灰獌?nèi)存中有空閑塊，無(wú)論這些塊是否相鄰，總可以進(jìn)行分配。當(dāng)然，付出的代價(jià)是需要建立一個(gè)PMT。第四章 存儲(chǔ)管理 分頁(yè)管理需要付出的代價(jià)分頁(yè)管理需要付出的代價(jià)1、維護(hù)大頁(yè)表需要一定的內(nèi)存空間。2、邏輯地址到物理地址的轉(zhuǎn)換更復(fù)雜。【例子】設(shè)某進(jìn)程地址空間大小為16MB。頁(yè)面大小為1KB。問(wèn)保存該進(jìn)程的頁(yè)表需要多大內(nèi)存空間？（1）16MB的程序可以劃分出：224/ 210 = 212個(gè)頁(yè)面（2）要編碼212個(gè)頁(yè)面，至少需要12 bits（3）考慮到字節(jié)

24、對(duì)齊，保存12 bits需要2 Bytes，也就是用2Bytes 保存一個(gè)頁(yè)面編號(hào)（4）共需要212 X 2 Bytes=213 Bytes = 8KB第四章 存儲(chǔ)管理 分頁(yè)管理的關(guān)鍵分頁(yè)管理的關(guān)鍵 地址轉(zhuǎn)換：地址轉(zhuǎn)換：LAddr - PAddr步驟：（1）把邏輯地址LAddr分解為形式： 假定 pagesize=1KB，那么： 400 = 1024 = 2049 = PageNum = LAddr / Pagesizeoffset = LAddr mod Pagesize第四章 存儲(chǔ)管理 分頁(yè)管理的關(guān)鍵分頁(yè)管理的關(guān)鍵 地址轉(zhuǎn)換地址轉(zhuǎn)換步驟：（2）查PMT表，把PageNum映射到BlockN

25、um。一般通過(guò)硬件實(shí)現(xiàn)。（3）通過(guò)BlockNum和offset構(gòu)造物理地址PAddr： PAddr= BlockNum* Blocksize + offset 【例子】假定pagesize=blocksize=1KB。頁(yè)表如下。求邏輯地址2049轉(zhuǎn)換的物理地址？(1) 2049 = (2) Page 2 對(duì)應(yīng) Block 6(3) 6*1kB + 1= 6145031526310PMT第四章 存儲(chǔ)管理 地址轉(zhuǎn)換的硬件實(shí)現(xiàn)地址轉(zhuǎn)換的硬件實(shí)現(xiàn)上面的地址轉(zhuǎn)換需要使用算法除法和乘法，比較復(fù)雜。實(shí)際上采用二進(jìn)制表示頁(yè)號(hào)和塊號(hào)時(shí)，這個(gè)轉(zhuǎn)換很容易。【定理】對(duì)于一個(gè) n 位的邏輯地址，假如頁(yè)面的大小為2k，

26、則高 (n-k) 位表示該邏輯地址所在的頁(yè)號(hào)，低 k 位表示該邏輯地址的頁(yè)面偏移量。nkn-koffsetPageNum邏輯地址邏輯地址低位高位第四章 存儲(chǔ)管理 地址轉(zhuǎn)換過(guò)程：offsetPageNum邏輯地址邏輯地址PMT： PageNum - BlockNum查表查表offsetBlockNum物理地址物理地址第四章 存儲(chǔ)管理 【例子】用24位表示一個(gè)邏輯地址，pagesize = 4KB。求地址0000,0000,0010,0000,1001,0000的頁(yè)號(hào)和頁(yè)內(nèi)偏移地址。【解答】因?yàn)?KB=212B，因此表示212個(gè)頁(yè)內(nèi)偏移地址需要12位。0000,0000,0010, 0000,10

27、01,0000PageNum = 2Offset =144第四章 存儲(chǔ)管理 剩下的問(wèn)題：如何高效的查頁(yè)表？剩下的問(wèn)題：如何高效的查頁(yè)表？1、頁(yè)表保存在內(nèi)存中還是寄存器中？2、頁(yè)表要不要與進(jìn)程關(guān)聯(lián)？ 2 4 7作業(yè)2（0 頁(yè)）作業(yè)2（1 頁(yè)）作業(yè)2（2 頁(yè)）34160長(zhǎng)度PMT 起始地址0頁(yè)1頁(yè)2頁(yè)0 KB4 KB8 KB12 KB作業(yè)2的地址空間04 KB4160操作系統(tǒng)用塊 2塊 4塊 7PMTAR4 字節(jié)頁(yè)表地址寄存器頁(yè)表地址寄存器第四章 存儲(chǔ)管理 頁(yè)表與進(jìn)程的關(guān)系：1、頁(yè)表的生命周期頁(yè)表的生命周期：頁(yè)表隨著進(jìn)程程序和數(shù)據(jù)的裝載而建立，隨著進(jìn)程的消亡而消亡。因此 LifeCycle(PMT

28、) Block2.請(qǐng)求I/O通道完成磁盤文件到內(nèi)存塊的 數(shù)據(jù)傳輸3. 調(diào)度其它就緒進(jìn)程并執(zhí)行等待當(dāng)頁(yè)面裝載完畢時(shí)，產(chǎn)生一個(gè)中斷，OS在處理這個(gè)中斷時(shí)，發(fā)現(xiàn)P正在等待這個(gè)事件的發(fā)生，于是將P從Block -Ready。如果P被調(diào)度，則從Ready- Run，這樣得以繼續(xù)運(yùn)行下去。第四章 存儲(chǔ)管理 這里一個(gè)遺留問(wèn)題是：如何建立磁盤文件塊與頁(yè)面之間的關(guān)系？表 4-3 (b)輔助頁(yè)表 虛頁(yè)號(hào)輔存地址保護(hù)信息第四章 存儲(chǔ)管理 4、當(dāng)把新頁(yè)載入內(nèi)存，而內(nèi)存不夠用時(shí)，需要換出一部分頁(yè)面，這時(shí)，被換出的頁(yè)面是被簡(jiǎn)單的覆蓋還是需要回寫(xiě)磁盤？Page n內(nèi)存塊Page mPage n磁盤塊回寫(xiě)輔助頁(yè)表第四章 存儲(chǔ)

29、管理 表 4-3 (a) 擴(kuò)充后的PMT表 虛頁(yè)號(hào) 主存塊號(hào) 改變位 引進(jìn)位 狀態(tài)位 輔存地址 標(biāo)識(shí)該頁(yè)面是否被修改過(guò)標(biāo)識(shí)該頁(yè)面是否被映射到內(nèi)存該頁(yè)面在外存介質(zhì)中的物理位置第四章 存儲(chǔ)管理 5、當(dāng)把新頁(yè)載入內(nèi)存，而內(nèi)存不夠用時(shí)，需要換出的頁(yè)面是在分配給當(dāng)前進(jìn)程中挑選，還是在整個(gè)內(nèi)存中挑選？OSOS進(jìn)程1.P0B0B1B2B3B4B5B6B7B8B9進(jìn)程1.P1進(jìn)程1.P2進(jìn)程2.P0進(jìn)程2.P1進(jìn)程2.P2進(jìn)程2.P3進(jìn)程3.P0進(jìn)程2.P4請(qǐng)求分配置換范圍置換范圍局部置換局部置換全局置換全局置換第四章 存儲(chǔ)管理 6、置換策略問(wèn)題 FIFO, LRU 例例 1 設(shè)頁(yè)面走向?yàn)镻=4, 3, 2,

30、 1, 4, 3, 5, 4, 3, 2, 1, 5，主存容量M=3，置換算法采用FIFO，則缺頁(yè)中斷次數(shù)及缺頁(yè)率按表 4 - 4 給出。 表4-4 FIFO性能分析例(M=3) 第四章 存儲(chǔ)管理 例例 3 設(shè)頁(yè)面走向如上，M=3，置換算法為L(zhǎng)RU，則系統(tǒng)模型如表 4-6 所示。在表 4-6 中，由于采用LRU算法，M中各列按訪問(wèn)的時(shí)間順序排列，最近被訪問(wèn)的頁(yè)面在最前。由表 4-6 算出缺頁(yè)中斷次數(shù)F=10， 缺頁(yè)率f=10/12=83%。 表4-6 LRU性能分析例(M=3) 第四章 存儲(chǔ)管理 內(nèi)存大小與缺頁(yè)中斷次數(shù)的關(guān)系內(nèi)存大小與缺頁(yè)中斷次數(shù)的關(guān)系圖 4.26 存儲(chǔ)容量與缺頁(yè)中斷次數(shù)的關(guān)系

31、 016KB 32KB 48KB 64KB 80KB 96KB 112KB100020003000400050006000700080009000MF24 KB932132 KB512648 KB245664 KB129580 KB69696 KB441112 KB329128 KB271160 KB144192 KB62缺頁(yè)次數(shù)F主存大小M第四章 存儲(chǔ)管理 不同置換策略與內(nèi)存大小的關(guān)系不同置換策略與內(nèi)存大小的關(guān)系表4-4 FIFO性能分析例(M=3,4) 第四章 存儲(chǔ)管理 表4-6 LRU性能分析例(M=3，4) 第四章 存儲(chǔ)管理 由表 4-6， 表 4-7 可得如下事實(shí)： 設(shè)G(P, M,

32、 t)表示當(dāng)頁(yè)面走向?yàn)镻，主存容量為M，在時(shí)刻t的頁(yè)面集合，對(duì)于LRU算法，存在如下關(guān)系，即 ), 1,(),(tMPGtMPG成立。即對(duì)于任何時(shí)刻t(t=1, 2, , 12),G(P, M, t)所選中的頁(yè)號(hào)必定包含在G(P, M+1, t)之中。這種關(guān)系說(shuō)明了增加主存容量不會(huì)增加缺頁(yè)中斷次數(shù)，然而對(duì)FIFO算法， 此關(guān)系并不成立。 第四章 存儲(chǔ)管理 執(zhí)行一條指令形成有效地址計(jì)算頁(yè)號(hào)該頁(yè)在實(shí)存嗎？缺頁(yè)中斷入口有空閑的實(shí)頁(yè)碼？出頁(yè)修改PMT MBTC=1？復(fù)制到輔存取出保存的頁(yè)號(hào)入頁(yè)找出磁盤地址修改PMT MBT表重新執(zhí)行被中斷的指令取下一條指令取數(shù)據(jù)完成該指令硬件軟件YNNYYN圖 4.2

33、1缺頁(yè)中斷的發(fā)生及其處理 第四章 存儲(chǔ)管理 4.4.4 請(qǐng)求分頁(yè)存儲(chǔ)管理方案的評(píng)價(jià)請(qǐng)求分頁(yè)存儲(chǔ)管理方案的評(píng)價(jià) (1) 它提供了大容量的多個(gè)虛擬存儲(chǔ)器， 作業(yè)地址空間不再受實(shí)存容量的限制； (2) 更有效地利用了主存，一個(gè)作業(yè)的地址空間不必全部同時(shí)都裝入主存， 只裝入其必要部分，其它部分根據(jù)請(qǐng)求裝入， 或者根本就不裝入(如錯(cuò)誤處理程序等)； (3) 更加有利于多道程序的運(yùn)行， 從而提高了系統(tǒng)效率； (4) 方便了用戶，特別是大作業(yè)用戶。 第四章 存儲(chǔ)管理 但請(qǐng)求分頁(yè)還存在以下缺點(diǎn)： (1) 為處理缺頁(yè)中斷，增加了處理機(jī)時(shí)間的開(kāi)銷， 即請(qǐng)求分頁(yè)系統(tǒng)是用時(shí)間的代價(jià)換取了空間的擴(kuò)大； (2) 可能因作

34、業(yè)地址空間過(guò)大或多道程序道數(shù)過(guò)多以及其它原因而造成系統(tǒng)抖動(dòng)； (3) 為防止系統(tǒng)抖動(dòng)所采取的各種措施會(huì)增加系統(tǒng)的復(fù)雜性。 第四章 存儲(chǔ)管理 作業(yè)：P1352,3,13,21,22第四章 存儲(chǔ)管理 4.5 分段存儲(chǔ)管理分段存儲(chǔ)管理 細(xì)分用戶程序的方案分頁(yè)（分頁(yè)（paging）分段分段采用分段技術(shù)，可以把程序和其相關(guān)的數(shù)據(jù)劃分到幾個(gè)段段中。值得注意的是：分段分段是程序設(shè)計(jì)語(yǔ)言提供給程序員的一種組織是程序設(shè)計(jì)語(yǔ)言提供給程序員的一種組織程序和數(shù)據(jù)的手段程序和數(shù)據(jù)的手段。在FORTRAN等語(yǔ)言中有對(duì)段的支持，但在C語(yǔ)言中沒(méi)有段的概念。第四章 存儲(chǔ)管理 大小是否固定大小是否固定是否對(duì)程序員是否對(duì)程序員透明

35、透明是否需要連續(xù)是否需要連續(xù)存儲(chǔ)存儲(chǔ)表示邏輯地址表示邏輯地址的方法的方法分頁(yè)分頁(yè)是是不需要分段分段否否不需要分頁(yè)與分段的比較分頁(yè)與分段的比較第四章 存儲(chǔ)管理 4.5 分段存儲(chǔ)管理分段存儲(chǔ)管理 4.5.1 分段原理分段原理 OSXAMAIN實(shí)存空間346038004000L 1，A |6ST ,B|MAIN=00160X=3A=5B=6C:虛存空間34000100060160E0400034010060ERR/W001346038000123456SMT容量存取權(quán)限狀態(tài)始址圖 4.27 分段管理概念圖第四章 存儲(chǔ)管理 邏輯地址到物理地址的映射：LA - PAoffsetSegmentNum（1）

36、LA:mn（2）查段表，得到對(duì)應(yīng)段號(hào)的內(nèi)存起始地址start（3）PA = start + offset第四章 存儲(chǔ)管理 【例子】在上圖中，指令L 1，A | 6中引用了地址 A | 6中的數(shù)據(jù)。在那樣的段表下，求邏輯地址 A | 6的物理地址。1、數(shù)組段A的段號(hào)為5, 地址 A | 6的偏移量是62、在SMT中，對(duì)應(yīng)A的起始地址為38003、因此，邏輯地址 A | 6對(duì)應(yīng)的物理地址為3800+6=3806第四章 存儲(chǔ)管理 圖 4.28 段式地址變換過(guò)程請(qǐng)求訪問(wèn)S段中的B單元段S在實(shí)存嗎?BS段容量在訪問(wèn)權(quán)限之內(nèi)?置訪問(wèn)位為1。若為寫(xiě)訪問(wèn)，則置改變位為1求段的始址L，加上段內(nèi)地址B，便得實(shí)存地

37、址A=L+B返回訪問(wèn)地址S段號(hào)B段內(nèi)地址缺段中斷越界中斷保護(hù)中斷NNN由處理機(jī)產(chǎn)生由分段管理機(jī)構(gòu)實(shí) 現(xiàn)第四章 存儲(chǔ)管理 4.5.3 分段存儲(chǔ)管理方案的評(píng)價(jià)分段存儲(chǔ)管理方案的評(píng)價(jià) 分段管理的優(yōu)點(diǎn)如下：(1) 消除了碎片。 (2) 提供了大容量的虛存。 (3) 允許動(dòng)態(tài)增加段的長(zhǎng)度。因?yàn)?(4) 便于動(dòng)態(tài)裝入和鏈接。 (5) 便于共享。當(dāng)兩個(gè)或兩個(gè)以上的作業(yè)要使用同一子程序時(shí)，在實(shí)存上就要有兩個(gè)或兩個(gè)以上的程序副本，這樣一來(lái)，實(shí)存的地址空間就可能被這些共用的子程序或標(biāo)準(zhǔn)應(yīng)用程序所塞滿。 (6) 便于實(shí)現(xiàn)存儲(chǔ)保護(hù)。 第四章 存儲(chǔ)管理 圖 4.29 兩個(gè)作業(yè)對(duì)SQRT的共享 第四章 存儲(chǔ)管理 分段存儲(chǔ)

38、管理的缺點(diǎn)有： (1) 進(jìn)行地址變換和實(shí)現(xiàn)靠攏操作要花費(fèi)處理機(jī)時(shí)間，為管理各分段， 要設(shè)立若干表格，提供附加的存儲(chǔ)空間； (2) 在輔存上管理可變長(zhǎng)度的段比較困難； (3) 段的最大長(zhǎng)度受到實(shí)存容量的限制； (4) 會(huì)出現(xiàn)系統(tǒng)抖動(dòng)現(xiàn)象。 第四章 存儲(chǔ)管理 4.6 段頁(yè)式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理 4.6.1 段頁(yè)式存儲(chǔ)管理的實(shí)現(xiàn)段頁(yè)式存儲(chǔ)管理的實(shí)現(xiàn) 在段頁(yè)存儲(chǔ)管理系統(tǒng)中，處理機(jī)給出的有效地址被劃分為三部分：段號(hào)、 頁(yè)號(hào)和頁(yè)內(nèi)地址。在某計(jì)算機(jī)系統(tǒng)中，24 位有效地址的劃分是： 段號(hào)S 頁(yè)號(hào)P 頁(yè)內(nèi)地址W 0 7 8 15 16 19 20 31 第四章 存儲(chǔ)管理 處理機(jī)給出的有效地址長(zhǎng)度確定了作業(yè)地

39、址空間的范圍。 換言之，它確定了虛存的容量。一個(gè)具體的地址結(jié)構(gòu)，確定了一個(gè)作業(yè)最多能有幾段， 每段最多能有幾頁(yè)以及每頁(yè)的大小。 上述的 24 位有效地址確定了虛存的容量為 16 MB。 8 位的段號(hào)確定了一個(gè)作業(yè)地址空間最多有 256 個(gè)段，段號(hào)為 0255， 每個(gè)段最多為 16 頁(yè)，頁(yè)號(hào)為015，每頁(yè)的大小為4 KB。 第四章 存儲(chǔ)管理 現(xiàn)在假定有一個(gè)作業(yè)，它有三段：第 0 段段長(zhǎng)為 15 KB， 占 4頁(yè)(最后一頁(yè)有 1 KB未用)；第 1 段為 8 KB，占2 頁(yè)；第 2 段為 10 KB，占 3 頁(yè)(最后2 KB未用)。該作業(yè)的地址空間如圖 4.30 所示。 04 KB8 KB12 K

40、B15 KB16 KB0 段1 段04 KB8 KB04 KB8 KB10 KB2 段圖 4.30 段頁(yè)式管理的作業(yè)地址空間例 第四章 存儲(chǔ)管理 程序的分段，可由程序員或編譯程序按信息的邏輯結(jié)構(gòu)來(lái)劃分，而分頁(yè)與程序員無(wú)關(guān)，它是由操作系統(tǒng)自動(dòng)完成的。這就是說(shuō)，程序員所使用的編址方式或編譯程序給出的目標(biāo)程序其地址形式仍是二維的，即(S，W)，其中S為段號(hào)，W為段內(nèi)地址。而段內(nèi)地址W則由地址變換機(jī)構(gòu)把W的高 4 位解釋為頁(yè)號(hào)P， 把低 12 位解釋為頁(yè)內(nèi)地址W。 對(duì)主存而言，和分頁(yè)管理一樣，劃分為許多和頁(yè)面大小相等的存儲(chǔ)塊(也稱為實(shí)頁(yè))。因此，一個(gè)段可裝入不連續(xù)的存儲(chǔ)塊一個(gè)段可裝入不連續(xù)的存儲(chǔ)塊中，

41、于是就用不著再用靠攏的辦法來(lái)消除碎片了。通常把超出頁(yè)面大小的碎片稱為外碎片(或大碎片)，而小于頁(yè)面大小的碎片稱為內(nèi)碎片(或小碎片)。 第四章 存儲(chǔ)管理 圖 4.31 地址變換中所用表格的關(guān)系 段表長(zhǎng)度段表地址0L0110L300000000控制寄存器 1狀態(tài)頁(yè)表長(zhǎng)度 頁(yè)表地址段號(hào)0123頁(yè)號(hào)狀態(tài) 實(shí)存頁(yè)號(hào)01230123L0L3段表頁(yè)表實(shí)存OS第四章 存儲(chǔ)管理 圖 4.32 段頁(yè)式系統(tǒng)地址變換過(guò)程 控制寄存器 1（S，P）主存塊號(hào)SPW不匹配S塊號(hào)（S，P，W）PW聯(lián)想存儲(chǔ)器虛地址主存中的存儲(chǔ)塊段表頁(yè)表（頁(yè)面）第四章 存儲(chǔ)管理 4.6.2 段頁(yè)式存儲(chǔ)管理的評(píng)價(jià)段頁(yè)式存儲(chǔ)管理的評(píng)價(jià) 段頁(yè)存儲(chǔ)管理

42、方案保留了分段存儲(chǔ)管理和請(qǐng)求分頁(yè)存儲(chǔ)管理的全部?jī)?yōu)點(diǎn)。其主要優(yōu)點(diǎn)是它提供了大量的虛存空間，能有效地利用主存，為組織多道程序運(yùn)行提供了方便。 當(dāng)然，段頁(yè)存儲(chǔ)管理也有缺點(diǎn)，主要缺點(diǎn)是增加了硬件成本、系統(tǒng)的復(fù)雜性和管理上的開(kāi)銷；頁(yè)面使用不充分(和請(qǐng)求分頁(yè)一樣，存在著內(nèi)碎片)； 各種表格(如SMT、 PMT等)占用主存空間； 存在著系統(tǒng)發(fā)生抖動(dòng)的危險(xiǎn)。 第四章 存儲(chǔ)管理 4.7 Windows NT虛擬內(nèi)存管理虛擬內(nèi)存管理 4.7.1 進(jìn)程的虛擬地址空間進(jìn)程的虛擬地址空間 圖圖 4.33 虛擬地址空間虛擬地址空間 非頁(yè)交換區(qū)頁(yè)交換區(qū)直接映射地址頁(yè)面交換區(qū)FFFFFFFFhC0000000h8000000

43、0h00000000h系統(tǒng)存儲(chǔ)區(qū)(2 GB)用戶存儲(chǔ)區(qū)(2 GB)第四章 存儲(chǔ)管理 4.7.2 虛擬存儲(chǔ)的實(shí)現(xiàn)虛擬存儲(chǔ)的實(shí)現(xiàn) 圖圖 4.34 二級(jí)頁(yè)表地址變換結(jié)構(gòu)二級(jí)頁(yè)表地址變換結(jié)構(gòu) 頁(yè)表地址頁(yè)幀地址代碼或數(shù)據(jù)頁(yè)目錄(每進(jìn)程一個(gè))頁(yè)表頁(yè)幀表目錄位移頁(yè)表位移頁(yè)位移3121110頁(yè)目錄地址虛擬地址第四章 存儲(chǔ)管理 圖 4.35 地址變換過(guò)程舉例 0030020080044000626代碼或數(shù)據(jù)00C00800400000800400000800400000C02000168#00440#00626#0016831110控制寄存器頁(yè)目錄頁(yè)表頁(yè)幀虛擬地址第四章 存儲(chǔ)管理 我們計(jì)算一下，分頁(yè)管理和分級(jí)頁(yè)

44、管理下，頁(yè)表所占內(nèi)存大小。p 在分頁(yè)管理下，一個(gè)進(jìn)程的虛擬空間共需要 232/ 212 = 220=1M個(gè)頁(yè)表項(xiàng)，假定用一個(gè)word（即4 Bytes）保存一個(gè)頁(yè)表項(xiàng)，那么共需4MB來(lái)保存一個(gè)頁(yè)表。p 在分級(jí)頁(yè)管理下，一個(gè)進(jìn)程的虛擬空間被分為一個(gè)頁(yè)目錄，其中包含1K個(gè)頁(yè)目錄項(xiàng)，每個(gè)頁(yè)目錄項(xiàng)包括1K個(gè)頁(yè)表。這樣保存頁(yè)目錄需要1K*4B=4KB，保存頁(yè)表需要1K*1K*4B=4MB所以共需4KB+4MB。p 盡管分級(jí)頁(yè)管理保存頁(yè)目錄和頁(yè)表的內(nèi)存大于分頁(yè)管理的頁(yè)表內(nèi)存，但是搜索效率得到了提高：O(1K) + O(1K) O(1M)第四章 存儲(chǔ)管理 采用兩級(jí)頁(yè)表的缺點(diǎn)是降低了訪問(wèn)主存的速度。 因?yàn)槊窟M(jìn)

45、行一次地址變換要有三次訪問(wèn)主存：查頁(yè)目錄訪問(wèn)一次，查頁(yè)表訪問(wèn)一次，到主存中存取目標(biāo)數(shù)據(jù)又訪問(wèn)一次。但實(shí)際上Windows NT的訪問(wèn)主存速度并不慢， 相對(duì)來(lái)說(shuō)還比較快，這主要是因?yàn)樗扇×巳缦聝蓚€(gè)措施： (1) 使用快表，即使用聯(lián)想存儲(chǔ)器加快了查表速度， 在Windows NT中稱其為變換查找緩沖區(qū)TLB。 (2) 使用高速緩沖存儲(chǔ)器cache，在處理機(jī)和主存間設(shè)置了 32 KB或 64 KB的高速緩沖存儲(chǔ)器，大部分的指令和數(shù)據(jù)取自高速緩存(命中率達(dá)98%)，所以存取數(shù)據(jù)和指令速度相當(dāng)快，與處理機(jī)的速度完全匹配。 第四章 存儲(chǔ)管理 2. 頁(yè)面調(diào)度頁(yè)面調(diào)度 頁(yè)面調(diào)度策略包括取頁(yè)、置頁(yè)和淘汰策略。

46、 Windows NT的取頁(yè)策略分為兩種，一種是按進(jìn)程需要的“請(qǐng)求取頁(yè)”，另一種是提前取頁(yè)。前一種方法是在請(qǐng)求分頁(yè)存儲(chǔ)管理中普遍采用的方法，而后一種是Windows NT所獨(dú)有的，采取集群方法把一些頁(yè)面提前裝入主存。集群方法提前取頁(yè)的意思是，當(dāng)一個(gè)線程在發(fā)生缺頁(yè)時(shí)，不僅把它需要的那一頁(yè)裝入主存，而且還把該頁(yè)附近的一些頁(yè)也一起裝入。這樣做的主要依據(jù)就是程序行為的局部性。因此采取提前裝入取頁(yè)會(huì)減少缺頁(yè)次數(shù)，尤其在一個(gè)線程開(kāi)始執(zhí)行時(shí)，請(qǐng)求取頁(yè)會(huì)造成頻繁缺頁(yè)，降低系統(tǒng)的性能。 第四章 存儲(chǔ)管理 置頁(yè)策略是指把虛頁(yè)放入主存的哪個(gè)頁(yè)幀， 這個(gè)問(wèn)題在線性存儲(chǔ)結(jié)構(gòu)中比較簡(jiǎn)單，只要找到一個(gè)未分配的頁(yè)幀即可。 置

47、換(淘汰)策略，是為每個(gè)進(jìn)程分配一個(gè)固定數(shù)量的頁(yè)面(但可動(dòng)態(tài)調(diào)整這個(gè)數(shù)量)，當(dāng)發(fā)生缺頁(yè)中斷時(shí)，從本進(jìn)程從本進(jìn)程的范圍內(nèi)的范圍內(nèi)進(jìn)行替換。在Windows NT中采用了局部置換策略了局部置換策略。Windows NT采用先進(jìn)先出(FIFO)頁(yè)面置換算法， 即把在主存中駐留時(shí)間最長(zhǎng)的頁(yè)面淘汰出去，采用這種方法的出發(fā)點(diǎn)是算法實(shí)現(xiàn)簡(jiǎn)單。 第四章 存儲(chǔ)管理 第一章作業(yè)：T6ABCI/O30A:10101050B:30201020C:40第一種情況：第一種情況：A，B，C共用一個(gè)共用一個(gè)I/O10T=190ms第四章 存儲(chǔ)管理 第一章作業(yè)：T6ABCI/O130A:10101050B:302020C:40

48、第二種情況：第二種情況：A，B，C擁有不同擁有不同I/OI/O2T=180ms第四章 存儲(chǔ)管理 ABCI/O130A:10101050B:302020C:40假如考慮調(diào)度器調(diào)度時(shí)間假如考慮調(diào)度器調(diào)度時(shí)間I/O2T=msSched10第四章 存儲(chǔ)管理 ABCI/O130A:10101050B:302020C:40假如考慮調(diào)度器調(diào)度時(shí)間假如考慮調(diào)度器調(diào)度時(shí)間I/O2T=msSched10問(wèn)題：1、調(diào)度程序的執(zhí)行通常發(fā)生在什么時(shí)刻？調(diào)度程序的執(zhí)行是怎樣觸發(fā)的？2、下圖中，在什么時(shí)段系統(tǒng)狀態(tài)是：第四章 存儲(chǔ)管理 第二章補(bǔ)充題：給定一組作業(yè)給定一組作業(yè)J1, J2, , Jn，其執(zhí)行時(shí)間依次為，其執(zhí)行時(shí)

49、間依次為R1,R2,Rn。假定。假定這些作業(yè)同時(shí)到達(dá)，并且在同一臺(tái)處理機(jī)上按單道方式執(zhí)行。這些作業(yè)同時(shí)到達(dá)，并且在同一臺(tái)處理機(jī)上按單道方式執(zhí)行。試證明：按最短作業(yè)優(yōu)先算法調(diào)度時(shí)，其平均周轉(zhuǎn)時(shí)間最短。試證明：按最短作業(yè)優(yōu)先算法調(diào)度時(shí)，其平均周轉(zhuǎn)時(shí)間最短。假定按照J(rèn)1,J2,Jn的順序來(lái)調(diào)度，則周轉(zhuǎn)時(shí)間為：T1=R1T2=T1+R2=R1+R2T3=T2+R3=R1+R2+R3Tn=Tn-1+Rn=R1+R2+Rn-1+Rn總周轉(zhuǎn)時(shí)間：T= Sigma_i=1,nTi = nR1+(n-1)R2+(n-2)R3+2Rn-1+Rn = niiRin1) 1(平均周轉(zhuǎn)時(shí)間：niiRinn1) 1(1第

50、四章 存儲(chǔ)管理 第三章作業(yè)：T12LOCK：while(w = =1) skip;w:=1;UNLOCK:w:=0;要點(diǎn)：1、從進(jìn)程調(diào)度和狀態(tài)變化方面來(lái)說(shuō)明。2、與P，V操作進(jìn)行對(duì)比Critical regionP1 P2 CPULOCKP1 P2 第四章 存儲(chǔ)管理 第三章作業(yè)：T12LOCK：while(w = =1) skip;w:=1;UNLOCK:w:=0;要點(diǎn)：1、從進(jìn)程調(diào)度和狀態(tài)變化方面來(lái)說(shuō)明。2、與P，V操作進(jìn)行對(duì)比Critical regionP1 P2 CPULOCKP1 P2 第四章 存儲(chǔ)管理 第三章作業(yè)：T231、如果每次只允許一個(gè)進(jìn)程進(jìn)入互斥段，信號(hào)量初值為1，變化 范

51、圍是1,0,-1, -(n-1)，即1-n, 12、如果最多允許m（mn）個(gè)進(jìn)程同時(shí)進(jìn)入互斥段，信號(hào)量初值 為m，變化范圍是：m, m-1, , 0, -1, , -(n-m)思考：在第（2）問(wèn)中，當(dāng)信號(hào)量值是-(n-m)時(shí)，這些進(jìn)程分別處于什么狀態(tài)？第四章 存儲(chǔ)管理 第三章作業(yè)：T24為描述讀者的動(dòng)作，需要編寫(xiě)三個(gè)程序：p實(shí)現(xiàn)登記操作Checkin()p實(shí)現(xiàn)進(jìn)入閱覽室之后的閱讀操作Read()p實(shí)現(xiàn)讀者離開(kāi)時(shí)的注銷動(dòng)作Checkout()。如果閱覽室最多允許n個(gè)讀者進(jìn)入的話，那么就會(huì)為每一個(gè)讀者i創(chuàng)建一個(gè)進(jìn)程Pi，每個(gè)進(jìn)程按照Pi：Checkin();Read();Checkout()的次序依次順序三個(gè)程序執(zhí)行。這里存在的并發(fā)問(wèn)題主要有：p最多只能允許n個(gè)讀者（即n個(gè)進(jìn)程）進(jìn)入閱覽室（即關(guān)鍵區(qū)）p每個(gè)讀者在進(jìn)行Checkin和Checkout時(shí)對(duì)于登記表關(guān)鍵區(qū)必須互斥。為此，我們有如下算法：