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

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

(2)裝配模塊的地址再定位問(wèn)題。研究各種地址變換機(jī)構(gòu)，以及靜態(tài)和動(dòng)態(tài)再定位方法。

(3)存儲(chǔ)保護(hù)問(wèn)題。研究保護(hù)各類程序、數(shù)據(jù)區(qū)的方法。

(4)存儲(chǔ)擴(kuò)充問(wèn)題。主要研究虛擬存儲(chǔ)器問(wèn)題及其各種調(diào)度算法。4.1.2地址再定位1.地址空間和存儲(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)存管理：Transform：LASpace->PASpace2.地址定位發(fā)生的時(shí)態(tài)時(shí)間程序設(shè)計(jì)時(shí)或叫做編寫程序時(shí)編譯或匯編時(shí)加載模塊產(chǎn)生時(shí)加載時(shí)運(yùn)行時(shí)2.地址的靜態(tài)再定位，發(fā)生在加載時(shí)

LoaderLoaderTransform：LA->LA+AllocationStartAddress動(dòng)態(tài)地址再定位——發(fā)生在運(yùn)行時(shí)

Transform：LA->LA+[BR]如果LA+[BR]<[BR]+[LR]，則地址訪問(wèn)時(shí)安全的靜態(tài)再定位與動(dòng)態(tài)再定位的區(qū)別Load1,500123450100500…………Load1,150012345100011001500…………StartAddress=1000靜態(tài)Load1,500123450100500…………Load1,50012345100011001500…………[BR]=1000動(dòng)態(tài)在加載時(shí)解析地址在運(yùn)行時(shí)解析地址Load1,500123450100500…………Load1,50012345100011001500…………[BR]=1000動(dòng)態(tài)Load1,50012345200021002500…………[BR]=2000程序能否在內(nèi)存中移動(dòng)程序在存儲(chǔ)空間中是否連續(xù)存儲(chǔ)是否有利于程序共享執(zhí)行效率應(yīng)用領(lǐng)域靜態(tài)不能。除非再裝載一次，這對(duì)已經(jīng)開始運(yùn)行的程序不可行需要不利于高。因?yàn)槲锢淼刂肥窃谘b載時(shí)得到解析的，因此執(zhí)行每條指令時(shí)，不需要再解析嵌入式控制器，DSP，Cray超級(jí)計(jì)算機(jī)動(dòng)態(tài)可以。只需修改寄存器BR的內(nèi)容即可不需要。為每個(gè)分散的內(nèi)存區(qū)域增加一對(duì)<基址-限長(zhǎng)>寄存器利于低。因?yàn)槲锢淼刂肥窃谶\(yùn)行中邊解析邊執(zhí)行，但是可以通過(guò)硬件來(lái)加速PC，服務(wù)器靜態(tài)地址再定位與動(dòng)態(tài)地址在定位比較4.1.3虛擬存儲(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è)地址空間。

根據(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私有用戶地址空間（程序、數(shù)據(jù)）用戶棧進(jìn)程控制信息處理器狀態(tài)信息進(jìn)程標(biāo)識(shí)符共享地址空間Linux進(jìn)程的虛擬地址空間0x080480000xffffffffVAS=2^32=4GCPUMMUVAMemoryPACPUchip動(dòng)態(tài)地址再定位4.2早期的存儲(chǔ)管理4.2.1單一連續(xù)分配圖4.4單一連續(xù)分配特點(diǎn)：

單道處理系統(tǒng)

作業(yè)起始地址固定

內(nèi)存資源和處理器

沒(méi)有得到充分使用

作業(yè)需要的內(nèi)存>

物理內(nèi)存時(shí)，

作業(yè)無(wú)法運(yùn)行4.2.2分區(qū)分配特點(diǎn)：

分區(qū)大小固定，不能改變

當(dāng)存在一個(gè)分區(qū)：狀態(tài)=“未用”/\capacity>RequiredMemory

則分配給作業(yè)，否則作業(yè)不能運(yùn)行

內(nèi)存資源利用率低表4–1固定式分區(qū)舉例分區(qū)號(hào)分區(qū)容量作業(yè)容量剩余容量123458KB32KB32KB120KB520KB1KB9KB9KB33KB121KB7KB23KB23KB87KB399KB合計(jì)712KB173KB539KB2.可變式分區(qū)法圖4.6可變式分區(qū)的例子合并表4-2(a)已分配的分區(qū)狀態(tài)表分區(qū)號(hào)分區(qū)容量分區(qū)位置狀態(tài)123458KB32KB120KB321KB320KB384KB已分配已分配空項(xiàng)已分配空項(xiàng)分區(qū)號(hào)分區(qū)容量分區(qū)位置狀態(tài)1232KB520KB352KB504KB可用可用表4-2(b)未分配的分區(qū)狀態(tài)表判斷空白區(qū)是否可用判斷空白區(qū)大小是否滿足要求修改內(nèi)存分配狀態(tài)圖4.8可變式分區(qū)中釋放一個(gè)分區(qū)的流程可變式分區(qū)分配法分配分區(qū)的算法當(dāng)有多個(gè)空白區(qū)都可以滿足作業(yè)內(nèi)存需求時(shí)，究竟該選擇哪個(gè)分區(qū)予以分配？有如下幾種策略

最佳適應(yīng)算法（BestFit）min{xi|xi>RM}

其中xi是分區(qū)的容量，RM是作業(yè)請(qǐng)求內(nèi)存分配的大小

最差適應(yīng)算法（WorstFit）max{xi|xi>RM}

最先適應(yīng)算法（FirstFit）{xi|startaddressofxiismin/\xi>RM}3.可再定位式分區(qū)分配圖4.9可再定位式分區(qū)分配的靠攏過(guò)程圖4.10利用浮動(dòng)寄存器進(jìn)行地址變換圖4.11可再定位式分區(qū)分配算法流程沒(méi)有足夠空白區(qū)時(shí)再靠攏4.多重分區(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è)要求100KB存儲(chǔ)空間的作業(yè)，實(shí)際上由五個(gè)20KB的段組成時(shí)，則可以分配給該作業(yè)一個(gè)100KB的分區(qū)或者五個(gè)20KB的分區(qū)，或者兩個(gè)40KB的分區(qū)和一個(gè)20KB的分區(qū)等等。這種給一個(gè)作業(yè)分配一個(gè)以上分區(qū)的方法，稱為多重分區(qū)分配。采用這種方法時(shí)，作業(yè)可以在其執(zhí)行期間申請(qǐng)附加的分區(qū)。5.分區(qū)的保護(hù)措施圖4.12分區(qū)的界地址寄存器保護(hù)分區(qū)保護(hù)的特點(diǎn)：

在運(yùn)行過(guò)程中，每次訪問(wèn)存儲(chǔ)器

時(shí)進(jìn)行越界檢查

只需要一組寄存器組就可以6.分區(qū)分配方案的評(píng)價(jià)分區(qū)分配方案的主要優(yōu)點(diǎn)可歸納如下：

(1)實(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ù)段的共享。

分區(qū)分配的主要缺點(diǎn)有：

(1)主存仍不能充分利用，除了可再定位式分區(qū)法外，都存在著嚴(yán)重的碎片問(wèn)題。另外，即使不把存儲(chǔ)器分碎，整個(gè)空白區(qū)也可能因容納不下一個(gè)作業(yè)而造成浪費(fèi)。例如，有156KB的存儲(chǔ)空間可用，而某個(gè)作業(yè)序列是由100KB和60KB的作業(yè)組成的。如果分配了一個(gè)100KB的分區(qū)后，則剩下的56KB存儲(chǔ)空間就要浪費(fèi)掉。(2)不能實(shí)現(xiàn)對(duì)主存的擴(kuò)充。因此，作業(yè)的大小受到主存可用空間的限制。

(3)和單一連續(xù)分配一樣，要求一個(gè)作業(yè)在執(zhí)行之前必須全部裝入主存，因此在主存中可能包含從未使用過(guò)的信息。

(4)采用靠攏方法，雖然能解決碎片問(wèn)題，但有時(shí)需移動(dòng)大量信息，從而損失了處理機(jī)時(shí)間。

(5)除多重分區(qū)外，幾個(gè)共行作業(yè)之間不能共享存入主存的單一信息副本(如公用子程序、數(shù)據(jù)段等)?；仡?、可執(zhí)行文件（裝載模塊）三個(gè)地址空間Load1,500123450100…………500Load1,50012345…………磁盤空間邏輯(相對(duì))地址空間Load1,50012345x100+x…………500+x物理地址空間<磁碟號(hào),磁道號(hào),起始單元>所有地址從程序入口地址開始編號(hào)程序在內(nèi)存中占據(jù)的地址空間映射映射回顧2、靜態(tài)再定位和動(dòng)態(tài)在定位Load1,500123450100Jmp400……500Load1,500+x12345x100+xJmp400+x……500+x靜態(tài)定位發(fā)生在裝載時(shí)一旦裝載，程序不能再浮動(dòng)，否則會(huì)出現(xiàn)地址引用錯(cuò)亂400400+xLoad1,500123450100Jmp400……500Load1,50012345x100+xJmp400……500+x動(dòng)態(tài)定位發(fā)生在某條代碼執(zhí)行時(shí)，當(dāng)這條代碼引用了某個(gè)地址時(shí)，才進(jìn)行地址的定位400400+xJmp400得到邏輯地址400再定位寄存器x+400+x物理地址當(dāng)運(yùn)行這條指令時(shí)，才進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換4.3分頁(yè)存儲(chǔ)管理4.3.1分頁(yè)原理解決作業(yè)的內(nèi)存空間必須連續(xù)的問(wèn)題…………進(jìn)程地址空間(3K+10)B0kB1kB2kB3kBP0P1P2P3OSOS內(nèi)存地址空間B0B1B2B3B4B5B6B7B8B9PMTP0->B3P1->B4P2->B6P3->B810分頁(yè)管理的特點(diǎn)：1、頁(yè)面的大小是固定的，通常是2^k，如256B，1KB，4KB2、內(nèi)存塊的大小=頁(yè)面的大小3、連續(xù)頁(yè)所分配的塊不需要連續(xù)分頁(yè)管理的優(yōu)點(diǎn)：1、內(nèi)存碎片小。內(nèi)存碎片只能發(fā)生在分配給進(jìn)程地址空間的最后一頁(yè)的內(nèi)存塊中，而塊的大小通常很小，因此可以想象碎片也很小。2、不用浮動(dòng)程序的內(nèi)存空間就可以實(shí)現(xiàn)空閑空間的利用。因?yàn)橹灰獌?nèi)存中有空閑塊，無(wú)論這些塊是否相鄰，總可以進(jìn)行分配。當(dāng)然，付出的代價(jià)是需要建立一個(gè)PMT。分頁(yè)管理需要付出的代價(jià)1、維護(hù)大頁(yè)表需要一定的內(nèi)存空間。2、邏輯地址到物理地址的轉(zhuǎn)換更復(fù)雜?！纠印吭O(shè)某進(jìn)程地址空間大小為16MB。頁(yè)面大小為1KB。問(wèn)保存該進(jìn)程的頁(yè)表需要多大內(nèi)存空間？（1）16MB的程序可以劃分出：2^{24}/2^{10}=2^12個(gè)頁(yè)面（2）要編碼2^12個(gè)頁(yè)面，至少需要12bits（3）考慮到字節(jié)對(duì)齊，保存12bits需要2Bytes，也就是用2Bytes

保存一個(gè)頁(yè)面編號(hào)（4）共需要2^12X2Bytes=2^{13}Bytes=8KB分頁(yè)管理的關(guān)鍵——地址轉(zhuǎn)換：LAddr->PAddr步驟：（1）把邏輯地址LAddr分解為形式：<PageNum,offset>

假定pagesize=1KB，那么：400=><0,400>1024=><1,0>2049=><2,1>PageNum=[LAddr/Pagesize]offset=LAddrmodPagesize分頁(yè)管理的關(guān)鍵——地址轉(zhuǎn)換步驟：（2）查PMT表，把PageNum映射到BlockNum。一般通過(guò)硬件實(shí)現(xiàn)。（3）通過(guò)BlockNum和offset構(gòu)造物理地址PAddr：PAddr=BlockNum*Blocksize+offset【例子】假定pagesize=blocksize=1KB。頁(yè)表如下。求邏輯地址2049轉(zhuǎn)換的物理地址？2049=><2,1>Page2對(duì)應(yīng)Block66*1kB+1=6145031526310PMT地址轉(zhuǎn)換的硬件實(shí)現(xiàn)上面的地址轉(zhuǎn)換需要使用算法除法和乘法，比較復(fù)雜。實(shí)際上采用二進(jìn)制表示頁(yè)號(hào)和塊號(hào)時(shí)，這個(gè)轉(zhuǎn)換很容易。【定理】對(duì)于一個(gè)

n位的邏輯地址，假如頁(yè)面的大小為2^{k}，則高(n-k)位表示該邏輯地址所在的頁(yè)號(hào)，低k

位表示該邏輯地址的頁(yè)面偏移量。nkn-koffsetPageNum邏輯地址低位高位地址轉(zhuǎn)換過(guò)程：offsetPageNum邏輯地址PMT：PageNum->BlockNum查表offsetBlockNum物理地址【例子】用24位表示一個(gè)邏輯地址，pagesize=4KB。求地址0000,0000,0010,0000,1001,0000的頁(yè)號(hào)和頁(yè)內(nèi)偏移地址?！窘獯稹恳?yàn)?KB=2^{12}B，因此表示2^{12}個(gè)頁(yè)內(nèi)偏移地址需要12位。0000,0000,0010,0000,1001,0000PageNum=2Offset=144剩下的問(wèn)題：如何高效的查頁(yè)表？1、頁(yè)表保存在內(nèi)存中還是寄存器中？2、頁(yè)表要不要與進(jìn)程關(guān)聯(lián)？頁(yè)表地址寄存器頁(yè)表與進(jìn)程的關(guān)系：1、頁(yè)表的生命周期：頁(yè)表隨著進(jìn)程程序和數(shù)據(jù)的裝載而建立，隨著進(jìn)程的消亡而消亡。因此LifeCycle(PMT)<=LifeCycle(Process)2、在進(jìn)程的不同生命周期中，頁(yè)表的內(nèi)容可能不同。3、進(jìn)程需要保存頁(yè)表的起始位置，否則進(jìn)程在執(zhí)行時(shí)就無(wú)法通過(guò)查PMT表來(lái)進(jìn)行物理地址的解析（定位）。4、頁(yè)表起始地址通常保存在進(jìn)程的PCB中。當(dāng)該進(jìn)程被調(diào)度執(zhí)行時(shí)，取出頁(yè)表起始地址，放入PMTAR寄存器，加快頁(yè)表訪問(wèn)速度。頁(yè)表訪問(wèn)的加速1、高速頁(yè)面變換寄存器2、聯(lián)想存儲(chǔ)器（快表）

3.聯(lián)想存儲(chǔ)器圖4.17利用聯(lián)想存儲(chǔ)器加速查表快表：容量較小的存儲(chǔ)器，保存最近常用的頁(yè)面映射。PMT的一個(gè)高速緩存表。最后一個(gè)問(wèn)題：頁(yè)面管理的整個(gè)流程——進(jìn)程內(nèi)存分配算法如何記錄進(jìn)程內(nèi)存分配狀態(tài)？進(jìn)程表：記錄進(jìn)程的頁(yè)表長(zhǎng)度和頁(yè)表起始地址

PMT：進(jìn)程頁(yè)面的分配狀態(tài)MBT：內(nèi)存塊的分配狀態(tài)在頁(yè)面分配過(guò)程中，算法需要改變這三個(gè)表的狀態(tài)圖4.19分頁(yè)存儲(chǔ)分配算法流程創(chuàng)建PMT實(shí)際分配4.3.4分頁(yè)存儲(chǔ)管理方案的評(píng)價(jià)(1)采用動(dòng)態(tài)地址變換會(huì)增加計(jì)算機(jī)成本和降低處理機(jī)的速度。

(2)各種表格要占用一定容量的主存空間，而且還要花費(fèi)一部分處理機(jī)時(shí)間用來(lái)建立和管理這些表格。

(3)雖然說(shuō)碎片消除了，但每個(gè)作業(yè)的最后一頁(yè)一般都有不能充分利用的空白區(qū)。

(4)存儲(chǔ)擴(kuò)充問(wèn)題仍未得到解決。單一連續(xù)分配只適用于單道作業(yè)處理固定分區(qū)法為了讓多個(gè)作業(yè)共享內(nèi)存可變分區(qū)法限制了作業(yè)的個(gè)數(shù)內(nèi)存浪費(fèi)嚴(yán)重已分配分區(qū)狀態(tài)表未分配分區(qū)狀態(tài)表可再定位式分區(qū)法程序一旦裝載，不可再移動(dòng)碎片過(guò)多通過(guò)重新定位程序，把碎片連成整片內(nèi)存由于程序在裝載后重新移動(dòng)了位置，因此在裝載時(shí)解析邏輯地址已不可能，因此必須依賴動(dòng)態(tài)再定位技術(shù)的輔助分頁(yè)存儲(chǔ)管理程序可在裝載后重新定位和移動(dòng)程序必須連續(xù)程序可以不連續(xù)存儲(chǔ)BestfitWorstfitFirstfit非連續(xù)存儲(chǔ)PMT，PMTAR的支持動(dòng)態(tài)地址變換機(jī)構(gòu)硬件聯(lián)想存儲(chǔ)器進(jìn)程結(jié)構(gòu)（地址空間）與分頁(yè)存儲(chǔ)管理的關(guān)系程序段數(shù)據(jù)段堆棧內(nèi)核代碼，數(shù)據(jù)PCB，內(nèi)核棧等0x080480000x00000000程序PMT進(jìn)程P1虛擬地址空間0xFFFFFFFF程序私有地址空間程序間共享地址空間PMTAR程序段數(shù)據(jù)段堆棧內(nèi)核代碼，數(shù)據(jù)PCB，內(nèi)核棧等進(jìn)程P2虛擬地址空間物理內(nèi)存PMT4.4請(qǐng)求分頁(yè)存儲(chǔ)管理4.4.1請(qǐng)求分頁(yè)原理前面的內(nèi)存管理方法都是以程序和數(shù)據(jù)的完全裝載為前提的，但是有時(shí)物理內(nèi)存不足以滿足多個(gè)進(jìn)程的完全裝載，這時(shí)就要通過(guò)把頁(yè)面換入和換出物理內(nèi)存內(nèi)存來(lái)實(shí)現(xiàn)。這樣從用戶來(lái)看，就好像內(nèi)存能夠存放比它的物理大小大得多的程序，這就是存儲(chǔ)器的擴(kuò)充。解決存儲(chǔ)器擴(kuò)充問(wèn)題請(qǐng)求分頁(yè)機(jī)制（DemandPaging）預(yù)取分頁(yè)機(jī)制（Prepaging）為實(shí)現(xiàn)請(qǐng)求分頁(yè)機(jī)制，我們需要先解決幾個(gè)問(wèn)題：

能不能先把部分頁(yè)面載入內(nèi)存，讓程序運(yùn)行起來(lái)？

在程序運(yùn)行時(shí)，如何判斷某條指令或數(shù)據(jù)所在的頁(yè)沒(méi)有

被載入內(nèi)存？

當(dāng)某條指令或數(shù)據(jù)所在的頁(yè)沒(méi)有被載入內(nèi)存時(shí)，采用什么機(jī)制

把該頁(yè)載入內(nèi)存？

當(dāng)把新頁(yè)載入內(nèi)存，而內(nèi)存不夠用時(shí)，需要換出一部分頁(yè)面，

這時(shí)，被換出的頁(yè)面是被簡(jiǎn)單的覆蓋還是需要回寫磁盤？當(dāng)把新頁(yè)載入內(nèi)存，而內(nèi)存不夠用時(shí)，需要換出的頁(yè)面是在分配給當(dāng)前進(jìn)程中挑選，還是在整個(gè)內(nèi)存中挑選？

挑選被換出頁(yè)面的策略是什么？

1、能不能先把部分頁(yè)面載入內(nèi)存，讓程序運(yùn)行起來(lái)？——程序的“局部性”原理使得上述問(wèn)題的回答是肯定的局部性空間局部性：程序在不久的將來(lái)需要訪問(wèn)的內(nèi)存單元與當(dāng)前正在訪問(wèn)的內(nèi)存單元具有簇聚性時(shí)間局部性：程序當(dāng)前正在訪問(wèn)的內(nèi)存單元在不久的將來(lái)又會(huì)被重復(fù)訪問(wèn)到。局部性原理指示：一旦一個(gè)頁(yè)面被載入內(nèi)存，程序的執(zhí)行在很大程度上會(huì)一直訪問(wèn)該頁(yè)，從而使得程序執(zhí)行會(huì)持續(xù)一段時(shí)間，不會(huì)產(chǎn)生頻繁缺頁(yè)的狀況。2、在程序運(yùn)行時(shí)，如何判斷某條指令或數(shù)據(jù)所在的頁(yè)沒(méi)有

被載入內(nèi)存？方案一、維護(hù)部分頁(yè)表，該頁(yè)表中只包括那些已被映射到內(nèi)存中

的頁(yè)號(hào)方案二、維護(hù)全部頁(yè)表，通過(guò)增加一個(gè)標(biāo)志位來(lái)指示該頁(yè)

是否已被映射3、當(dāng)某條指令或數(shù)據(jù)所在的頁(yè)沒(méi)有被載入內(nèi)存時(shí)，采用什么機(jī)制把該頁(yè)載入內(nèi)存？進(jìn)程P缺頁(yè)中斷Block操作系統(tǒng)把進(jìn)程P的狀態(tài)從Run->Block請(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)行下去。這里一個(gè)遺留問(wèn)題是：如何建立磁盤文件塊與頁(yè)面之間的關(guān)系？表4-3(b)輔助頁(yè)表虛頁(yè)號(hào)輔存地址保護(hù)信息4、當(dāng)把新頁(yè)載入內(nèi)存，而內(nèi)存不夠用時(shí)，需要換出一部分頁(yè)面，這時(shí)，被換出的頁(yè)面是被簡(jiǎn)單的覆蓋還是需要回寫磁盤？Pagen內(nèi)存塊PagemPagen磁盤塊回寫輔助頁(yè)表表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ì)中的物理位置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)求分配置換范圍局部置換全局置換6、置換策略問(wèn)題——FIFO,LRU

例1

設(shè)頁(yè)面走向?yàn)镻=4,3,2,1,4,3,5,4,3,2,1,5，主存容量M=3，置換算法采用FIFO，則缺頁(yè)中斷次數(shù)及缺頁(yè)率按表4-4給出。表4-4FIFO性能分析例(M=3)

例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-6LRU性能分析例(M=3)內(nèi)存大小與缺頁(yè)中斷次數(shù)的關(guān)系圖4.26存儲(chǔ)容量與缺頁(yè)中斷次數(shù)的關(guān)系不同置換策略與內(nèi)存大小的關(guān)系表4-4FIFO性能分析例(M=3,4)表4-6LRU性能分析例(M=3，4)

由表4-6，表4-7可得如下事實(shí)：設(shè)G(P,M,t)表示當(dāng)頁(yè)面走向?yàn)镻，主存容量為M，在時(shí)刻t的頁(yè)面集合，對(duì)于LRU算法，存在如下關(guān)系，即成立。即對(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)系并不成立。圖4.21缺頁(yè)中斷的發(fā)生及其處理4.4.4請(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è)用戶。

但請(qǐng)求分頁(yè)還存在以下缺點(diǎn)：

(1)為處理缺頁(yè)中斷，增加了處理機(jī)時(shí)間的開銷，即請(qǐng)求分頁(yè)系統(tǒng)是用時(shí)間的代價(jià)換取了空間的擴(kuò)大；

(2)可能因作業(yè)地址空間過(guò)大或多道程序道數(shù)過(guò)多以及其它原因而造成系統(tǒng)抖動(dòng)；

(3)為防止系統(tǒng)抖動(dòng)所采取的各種措施會(huì)增加系統(tǒng)的復(fù)雜性。作業(yè)：P1352,3,13,21,224.5分段存儲(chǔ)管理細(xì)分用戶程序的方案分頁(yè)（paging）分段采用分段技術(shù)，可以把程序和其相關(guān)的數(shù)據(jù)劃分到幾個(gè)段中。值得注意的是：分段是程序設(shè)計(jì)語(yǔ)言提供給程序員的一種組織程序和數(shù)據(jù)的手段。在FORTRAN等語(yǔ)言中有對(duì)段的支持，但在C語(yǔ)言中沒(méi)有段的概念。大小是否固定是否對(duì)程序員透明是否需要連續(xù)存儲(chǔ)表示邏輯地址的方法分頁(yè)是是不需要<頁(yè)號(hào)，頁(yè)內(nèi)偏移>分段否否不需要<段號(hào)，段內(nèi)偏移>分頁(yè)與分段的比較4.5分段存儲(chǔ)管理4.5.1分段原理圖4.27分段管理概念圖邏輯地址到物理地址的映射：LA->PAoffsetSegmentNum（1）LA:mn（2）查段表，得到對(duì)應(yīng)段號(hào)的內(nèi)存起始地址start（3）PA=start+offset【例子】在上圖中，指令L1，[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圖4.28段式地址變換過(guò)程4.5.3分段存儲(chǔ)管理方案的評(píng)價(jià)分段管理的優(yōu)點(diǎn)如下：消除了碎片。(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ù)。圖4.29兩個(gè)作業(yè)對(duì)SQRT的共享

分段存儲(chǔ)管理的缺點(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)象。4.6段頁(yè)式存儲(chǔ)管理4.6.1段頁(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)地址W0781516192031

處理機(jī)給出的有效地址長(zhǎng)度確定了作業(yè)地址空間的范圍。換言之，它確定了虛存的容量。一個(gè)具體的地址結(jié)構(gòu)，確定了一個(gè)作業(yè)最多能有幾段，每段最多能有幾頁(yè)以及每頁(yè)的大小。上述的24位有效地址確定了虛存的容量為16MB。8位的段號(hào)確定了一個(gè)作業(yè)地址空間最多有256個(gè)段，段號(hào)為0～255，每個(gè)段最多為16頁(yè)，頁(yè)號(hào)為0～15，每頁(yè)的大小為4KB。

現(xiàn)在假定有一個(gè)作業(yè)，它有三段：第0段段長(zhǎng)為15KB，占4頁(yè)(最后一頁(yè)有1KB未用)；第1段為8KB，占2頁(yè)；第2段為10KB，占3頁(yè)(最后2KB未用)。該作業(yè)的地址空間如圖4.30所示。圖4.30段頁(yè)式管理的作業(yè)地址空間例

程序的分段，可由程序員或編譯程序按信息的邏輯結(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ǔ)塊中，于是就用不著再用靠攏的辦法來(lái)消除碎片了。通常把超出頁(yè)面大小的碎片稱為外碎片(或大碎片)，而小于頁(yè)面大小的碎片稱為內(nèi)碎片(或小碎片)。圖4.31地址變換中所用表格的關(guān)系圖4.32段頁(yè)式系統(tǒng)地址變換過(guò)程4.6.2段頁(yè)式存儲(chǔ)管理的評(píng)價(jià)段頁(yè)存儲(chǔ)管理方案保留了分段存儲(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ù)雜性和管理上的開銷；頁(yè)面使用不充分(和請(qǐng)求分頁(yè)一樣，存在著內(nèi)碎片)；各種表格(如SMT、PMT等)占用主存空間；存在著系統(tǒng)發(fā)生抖動(dòng)的危險(xiǎn)。4.7WindowsNT虛擬內(nèi)存管理4.7.1進(jìn)程的虛擬地址空間圖4.33虛擬地址空間4.7.2虛擬存儲(chǔ)的實(shí)現(xiàn)圖4.34二級(jí)頁(yè)表地址變換結(jié)構(gòu)圖4.35地址變換過(guò)程舉例我們計(jì)算一下，分頁(yè)管理和分級(jí)頁(yè)管理下，頁(yè)表所占內(nèi)存大小。在分頁(yè)管理下，一個(gè)進(jìn)程的虛擬空間共需要2^{32}/2^{12}=2^{20}=1M個(gè)頁(yè)表項(xiàng)，假定用一個(gè)word（即4Bytes）保存一個(gè)頁(yè)表項(xiàng)，那么共需4MB來(lái)保存一個(gè)頁(yè)表。

在分級(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。

盡管分級(jí)頁(yè)管理保存頁(yè)目錄和頁(yè)表的內(nèi)存大于分頁(yè)管理的頁(yè)表內(nèi)存，但是搜索效率得到了提高：O(1K)+O(1K)<<O(1M)

采用兩級(jí)頁(yè)表的缺點(diǎn)是降低了訪問(wèn)主存的速度。因?yàn)槊窟M(jìn)行一次地址變換要有三次訪問(wèn)主存：查頁(yè)目錄訪問(wèn)一次，查頁(yè)表訪問(wèn)一次，到主存中存取目標(biāo)數(shù)據(jù)又訪問(wèn)一次。但實(shí)際上WindowsNT的訪問(wèn)主存速度并不慢，相對(duì)來(lái)說(shuō)還比較快，這主要是因?yàn)樗扇×巳缦聝蓚€(gè)措施：

(1)使用快表，即使用聯(lián)想存儲(chǔ)器加快了查表速度，在WindowsNT中稱其為變換查找緩沖區(qū)TLB。

(2)使用高速緩沖存儲(chǔ)器cache，在處理機(jī)和主存間設(shè)置了32KB或64KB的高速緩沖存儲(chǔ)器，大部分的指令和數(shù)據(jù)取自高速緩存(命中率達(dá)98%)，所以存取數(shù)據(jù)和指令速度相當(dāng)快，與處理機(jī)的速度完全匹配。

2.頁(yè)面調(diào)度頁(yè)面調(diào)度策略包括取頁(yè)、置頁(yè)和淘汰策略。

WindowsNT的取頁(yè)策略分為兩種，一種是按進(jìn)程需要的“請(qǐng)求取頁(yè)”，另一種是提前取頁(yè)。前一種方法是在請(qǐng)求分頁(yè)存儲(chǔ)管理中普遍采用的方法，而后一種是WindowsNT所獨(dú)有的，采取集群方法把一些頁(yè)面提前裝入主存。集群方法提前取頁(yè)的意思是，當(dāng)一個(gè)線程在發(fā)生缺頁(yè)時(shí)，不僅把它需要的那一頁(yè)裝入主存，而且還把該頁(yè)附近的一些頁(yè)也一起裝入。這樣做的主要依據(jù)就是程序行為的局部性。因此采取提前裝入取頁(yè)會(huì)減少缺頁(yè)次數(shù)，尤其在一個(gè)線程開始執(zhí)行時(shí)，請(qǐng)求取頁(yè)會(huì)造成頻繁缺頁(yè)，降低系統(tǒng)的性能。

置頁(yè)策略是指把虛頁(yè)放入主存的哪個(gè)頁(yè)幀，這個(gè)問(wèn)題在線性存儲(chǔ)結(jié)構(gòu)中比較簡(jiǎn)單，只要找到一個(gè)未分配的頁(yè)幀即可。置換(淘汰)策略，是為每個(gè)進(jìn)程分配一個(gè)固定數(shù)量的頁(yè)面(但可動(dòng)態(tài)調(diào)整這個(gè)數(shù)量)，當(dāng)發(fā)生缺頁(yè)中斷時(shí)，從本進(jìn)程的范圍內(nèi)進(jìn)行替換。在WindowsNT中采用了局部置換策略。WindowsNT采用先進(jìn)先出(FIFO)頁(yè)面置換算法，即把在主存中駐留時(shí)間最長(zhǎng)的頁(yè)面淘汰出去，采用這種方法的出發(fā)點(diǎn)是算法實(shí)現(xiàn)簡(jiǎn)單。第一章作業(yè)：T6ABCI/O30A:10101050B:30201020C:40第一種情況：A，B，C共用一個(gè)I/O10T=190ms第一章作業(yè)：T6ABCI/O130A:10101050B:302020C:40第二種情況：A，B，C擁有不同I/OI/O2T=180msABCI/O130A:10101050B:302020C:40假如考慮調(diào)度器調(diào)度時(shí)間I/O2T=msSched10ABCI/O130A:10101050B:302020C:40假如考慮調(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)是：<Exit,Block,Block>第二章補(bǔ)充題：給定一組作業(yè)J1,J2,…,Jn，其執(zhí)行時(shí)間依次為R1,R2,…,Rn。假定這些作業(yè)同時(shí)到達(dá)，并且在同一臺(tái)處理機(jī)上按單道方式執(zhí)行。試證明：按最短作業(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+R3……Tn=Tn-1+Rn=R1+R2+…+Rn-1+Rn總周轉(zhuǎn)時(shí)間：T=Sigma_{i=1,…,n}Ti=nR1+(n-1)R2+(n-2)R3+…+2Rn-1+Rn=平均周轉(zhuǎn)時(shí)間：第三章作業(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ì)比CriticalregionP1P2CPULOCKP1P2第三章作業(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ì)比CriticalregionP1P2CPULOCKP1P2>第三章作業(yè)：T231、如果每次只允許一個(gè)進(jìn)程進(jìn)入互斥段，信號(hào)量初值為1，變化

范圍是1,0,-1,…,-(n-1)，即[1-n,1]2、如果最多允許m（m<n）個(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)？第三章作業(yè)：T24為描述讀者的動(dòng)作，需要編寫三個(gè)程序：實(shí)現(xiàn)登記操作Checkin()實(shí)現(xiàn)進(jìn)入閱覽室之后的閱讀操作Read()實(shí)現(xiàn)讀者離開時(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)題主要有：最多只能允許n個(gè)讀者（即n個(gè)進(jìn)程）進(jìn)入閱覽室（即關(guān)鍵區(qū)）每個(gè)讀者在進(jìn)行Checkin和Checkout時(shí)對(duì)于登記表關(guān)鍵區(qū)必須互斥。為此，我們有如下算法：SemaphoreSn:=100;//最多只允許n個(gè)讀者進(jìn)入閱覽室SemphoreS:=0;//Checkin之間，Checkout之間以及//Checkin和Checkout之間互斥Algorithm：foreachreaderintendingtoenterreading-roomcreateaprocess{P(Sn);P(S);Checkin();V(S);Read();P(S);Checkout();V(S);V(Sn);}//foreachreaderproc