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

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

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

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

(4)存儲擴充問題。主要研究虛擬存儲器問題及其各種調(diào)度算法。4.1.2地址再定位1.地址空間和存儲空間

裝配模塊

源程序

進程編譯，鏈接加載符號指令變量類型高級語言結(jié)構(gòu)二進制指令對存儲空間的引用字節(jié)大小以及排列方式變成順序結(jié)構(gòu)裝配模塊內(nèi)容+進程環(huán)境Transform內(nèi)存管理：Transform：LASpace->PASpace2.地址定位發(fā)生的時態(tài)時間程序設(shè)計時或叫做編寫程序時編譯或匯編時加載模塊產(chǎn)生時加載時運行時2.地址的靜態(tài)再定位，發(fā)生在加載時

LoaderLoaderTransform：LA->LA+AllocationStartAddress動態(tài)地址再定位——發(fā)生在運行時

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

虛擬存儲器的基本思想是把作業(yè)地址空間和實際主存的存儲空間，視為兩個不同的概念。一個計算機系統(tǒng)為程序員提供了一個足夠大的地址空間，而完全不必考慮實際主存的大小。由此，可以引出虛擬存儲器更一般的概念，即把系統(tǒng)提供的這個地址空間，想象成有一個存儲器(虛存)與之對應(yīng)，正像存儲空間有一個主存與之對應(yīng)一樣。這就是說，虛擬存儲器實際上是一個地址空間。

根據(jù)地址空間結(jié)構(gòu)不同，虛擬存儲器有兩種形式。一種是單段式虛存，它是一個連續(xù)的線性地址空間，其地址順序為：0，1，2，…，n-1。其中n=2k,k為CPU給出的有效地址的長度。另一種是多段式虛存，它是把地址空間分成若干段，而每一段Si是一個連續(xù)的線性地址空間。每個地址可用［Si,W］來表示，Si為段名或段號，W為段內(nèi)的相對地址。VA=Bi+W私有用戶地址空間（程序、數(shù)據(jù)）用戶棧進程控制信息處理器狀態(tài)信息進程標識符共享地址空間Linux進程的虛擬地址空間0x080480000xffffffffVAS=2^32=4GCPUMMUVAMemoryPACPUchip動態(tài)地址再定位4.2早期的存儲管理4.2.1單一連續(xù)分配圖4.4單一連續(xù)分配特點：

單道處理系統(tǒng)

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

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

沒有得到充分使用

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

物理內(nèi)存時，

作業(yè)無法運行4.2.2分區(qū)分配特點：

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

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

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

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

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

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

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

最先適應(yīng)算法（FirstFit）{xi|startaddressofxiismin/\xi>RM}3.可再定位式分區(qū)分配圖4.9可再定位式分區(qū)分配的靠攏過程圖4.10利用浮動寄存器進行地址變換圖4.11可再定位式分區(qū)分配算法流程沒有足夠空白區(qū)時再靠攏4.多重分區(qū)分配

如果我們不想采用靠攏的辦法，又想使存儲器分區(qū)的碎片問題適當(dāng)?shù)氐玫浇鉀Q，那么可以采用多重分區(qū)分配方案。通常一個作業(yè)由一些相對獨立的程序段和數(shù)據(jù)段組成，如主程序、子程序、數(shù)據(jù)組等。這些程序段中的每一個在邏輯上必須是連續(xù)的，但是相應(yīng)的各分區(qū)卻不要求是連續(xù)的，只要有足夠的保護措施就可以了。例如一個要求100KB存儲空間的作業(yè)，實際上由五個20KB的段組成時，則可以分配給該作業(yè)一個100KB的分區(qū)或者五個20KB的分區(qū)，或者兩個40KB的分區(qū)和一個20KB的分區(qū)等等。這種給一個作業(yè)分配一個以上分區(qū)的方法，稱為多重分區(qū)分配。采用這種方法時，作業(yè)可以在其執(zhí)行期間申請附加的分區(qū)。5.分區(qū)的保護措施圖4.12分區(qū)的界地址寄存器保護分區(qū)保護的特點：

在運行過程中，每次訪問存儲器

時進行越界檢查

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

(1)實現(xiàn)了主存的共享，因而有助于多道程序設(shè)計，更有效地利用了處理機和I/O設(shè)備，從而使系統(tǒng)的吞吐量和作業(yè)周轉(zhuǎn)時間得到了相應(yīng)的改善。至于主存利用率，可變式分區(qū)比固定式分區(qū)高些，可再定位式分區(qū)則更高些。

(2)相對于后面介紹的存儲管理方式，本方案為實現(xiàn)分區(qū)分配所使用的表格、占用的存儲容量相對較少，算法也相對簡單。

(3)實現(xiàn)存儲保護的措施也比較簡單。

(4)多重分區(qū)分配方案能實現(xiàn)對子程序、數(shù)據(jù)段的共享。

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

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

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

(4)采用靠攏方法，雖然能解決碎片問題，但有時需移動大量信息，從而損失了處理機時間。

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

保存一個頁面編號（4）共需要2^12X2Bytes=2^{13}Bytes=8KB分頁管理的關(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分頁管理的關(guān)鍵——地址轉(zhuǎn)換步驟：（2）查PMT表，把PageNum映射到BlockNum。一般通過硬件實現(xiàn)。（3）通過BlockNum和offset構(gòu)造物理地址PAddr：PAddr=BlockNum*Blocksize+offset【例子】假定pagesize=blocksize=1KB。頁表如下。求邏輯地址2049轉(zhuǎn)換的物理地址？2049=><2,1>Page2對應(yīng)Block66*1kB+1=6145031526310PMT地址轉(zhuǎn)換的硬件實現(xiàn)上面的地址轉(zhuǎn)換需要使用算法除法和乘法，比較復(fù)雜。實際上采用二進制表示頁號和塊號時，這個轉(zhuǎn)換很容易?！径ɡ怼繉τ谝粋€

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

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

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

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

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

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

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

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

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

被載入內(nèi)存？

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

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

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

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

挑選被換出頁面的策略是什么？

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

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

的頁號方案二、維護全部頁表，通過增加一個標志位來指示該頁

是否已被映射3、當(dāng)某條指令或數(shù)據(jù)所在的頁沒有被載入內(nèi)存時，采用什么機制把該頁載入內(nèi)存？進程P缺頁中斷Block操作系統(tǒng)把進程P的狀態(tài)從Run->Block請求I/O通道完成磁盤文件到內(nèi)存塊的

數(shù)據(jù)傳輸3.調(diào)度其它就緒進程并執(zhí)行等待當(dāng)頁面裝載完畢時，產(chǎn)生一個中斷，OS在處理這個中斷時，發(fā)現(xiàn)P正在等待這個事件的發(fā)生，于是將P從Block->Ready。如果P被調(diào)度，則從Ready->Run，這樣得以繼續(xù)運行下去。這里一個遺留問題是：如何建立磁盤文件塊與頁面之間的關(guān)系？表4-3(b)輔助頁表虛頁號輔存地址保護信息4、當(dāng)把新頁載入內(nèi)存，而內(nèi)存不夠用時，需要換出一部分頁面，這時，被換出的頁面是被簡單的覆蓋還是需要回寫磁盤？Pagen內(nèi)存塊PagemPagen磁盤塊回寫輔助頁表表4-3(a)擴充后的PMT表虛頁號主存塊號改變位引進位狀態(tài)位輔存地址標識該頁面是否被修改過標識該頁面是否被映射到內(nèi)存該頁面在外存介質(zhì)中的物理位置5、當(dāng)把新頁載入內(nèi)存，而內(nèi)存不夠用時，需要換出的頁面是在分配給當(dāng)前進程中挑選，還是在整個內(nèi)存中挑選？OSOS進程1.P0B0B1B2B3B4B5B6B7B8B9進程1.P1進程1.P2進程2.P0進程2.P1進程2.P2進程2.P3進程3.P0進程2.P4請求分配置換范圍局部置換全局置換6、置換策略問題——FIFO,LRU

例1

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

例3

設(shè)頁面走向如上，M=3，置換算法為LRU，則系統(tǒng)模型如表4-6所示。在表4-6中，由于采用LRU算法，M中各列按訪問的時間順序排列，最近被訪問的頁面在最前。由表4-6算出缺頁中斷次數(shù)F=10，缺頁率f=10/12=83%。表4-6LRU性能分析例(M=3)內(nèi)存大小與缺頁中斷次數(shù)的關(guān)系圖4.26存儲容量與缺頁中斷次數(shù)的關(guān)系不同置換策略與內(nèi)存大小的關(guān)系表4-4FIFO性能分析例(M=3,4)表4-6LRU性能分析例(M=3，4)

由表4-6，表4-7可得如下事實：設(shè)G(P,M,t)表示當(dāng)頁面走向為P，主存容量為M，在時刻t的頁面集合，對于LRU算法，存在如下關(guān)系，即成立。即對于任何時刻t(t=1,2,…,12),G(P,M,t)所選中的頁號必定包含在G(P,M+1,t)之中。這種關(guān)系說明了增加主存容量不會增加缺頁中斷次數(shù)，然而對FIFO算法，此關(guān)系并不成立。圖4.21缺頁中斷的發(fā)生及其處理4.4.4請求分頁存儲管理方案的評價(1)它提供了大容量的多個虛擬存儲器，作業(yè)地址空間不再受實存容量的限制；

(2)更有效地利用了主存，一個作業(yè)的地址空間不必全部同時都裝入主存，只裝入其必要部分，其它部分根據(jù)請求裝入，或者根本就不裝入(如錯誤處理程序等)；

(3)更加有利于多道程序的運行，從而提高了系統(tǒng)效率；

(4)方便了用戶，特別是大作業(yè)用戶。

但請求分頁還存在以下缺點：

(1)為處理缺頁中斷，增加了處理機時間的開銷，即請求分頁系統(tǒng)是用時間的代價換取了空間的擴大；

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

(3)為防止系統(tǒng)抖動所采取的各種措施會增加系統(tǒng)的復(fù)雜性。作業(yè)：P1352,3,13,21,224.5分段存儲管理細分用戶程序的方案分頁（paging）分段采用分段技術(shù)，可以把程序和其相關(guān)的數(shù)據(jù)劃分到幾個段中。值得注意的是：分段是程序設(shè)計語言提供給程序員的一種組織程序和數(shù)據(jù)的手段。在FORTRAN等語言中有對段的支持，但在C語言中沒有段的概念。大小是否固定是否對程序員透明是否需要連續(xù)存儲表示邏輯地址的方法分頁是是不需要<頁號，頁內(nèi)偏移>分段否否不需要<段號，段內(nèi)偏移>分頁與分段的比較4.5分段存儲管理4.5.1分段原理圖4.27分段管理概念圖邏輯地址到物理地址的映射：LA->PAoffsetSegmentNum（1）LA:mn（2）查段表，得到對應(yīng)段號的內(nèi)存起始地址start（3）PA=start+offset【例子】在上圖中，指令L1，[A]|6中引用了地址[A]|6中的數(shù)據(jù)。在那樣的段表下，求邏輯地址[A]|6的物理地址。1、數(shù)組段A的段號為5,地址[A]|6的偏移量是62、在SMT中，對應(yīng)A的起始地址為38003、因此，邏輯地址[A]|6對應(yīng)的物理地址為3800+6=3806圖4.28段式地址變換過程4.5.3分段存儲管理方案的評價分段管理的優(yōu)點如下：消除了碎片。(2)提供了大容量的虛存。(3)允許動態(tài)增加段的長度。因為(4)便于動態(tài)裝入和鏈接。(5)便于共享。當(dāng)兩個或兩個以上的作業(yè)要使用同一子程序時，在實存上就要有兩個或兩個以上的程序副本，這樣一來，實存的地址空間就可能被這些共用的子程序或標準應(yīng)用程序所塞滿。

(6)便于實現(xiàn)存儲保護。圖4.29兩個作業(yè)對SQRT的共享

分段存儲管理的缺點有：

(1)進行地址變換和實現(xiàn)靠攏操作要花費處理機時間，為管理各分段，要設(shè)立若干表格，提供附加的存儲空間；

(2)在輔存上管理可變長度的段比較困難；

(3)段的最大長度受到實存容量的限制；

(4)會出現(xiàn)系統(tǒng)抖動現(xiàn)象。4.6段頁式存儲管理4.6.1段頁式存儲管理的實現(xiàn)

在段頁存儲管理系統(tǒng)中，處理機給出的有效地址被劃分為三部分：段號、頁號和頁內(nèi)地址。在某計算機系統(tǒng)中，24位有效地址的劃分是：段號S頁號P頁內(nèi)地址W0781516192031

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

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

程序的分段，可由程序員或編譯程序按信息的邏輯結(jié)構(gòu)來劃分，而分頁與程序員無關(guān)，它是由操作系統(tǒng)自動完成的。這就是說，程序員所使用的編址方式或編譯程序給出的目標程序其地址形式仍是二維的，即(S，W′)，其中S為段號，W′為段內(nèi)地址。而段內(nèi)地址W′則由地址變換機構(gòu)把W′的高4位解釋為頁號P，把低12位解釋為頁內(nèi)地址W。對主存而言，和分頁管理一樣，劃分為許多和頁面大小相等的存儲塊(也稱為實頁)。因此，一個段可裝入不連續(xù)的存儲塊中，于是就用不著再用靠攏的辦法來消除碎片了。通常把超出頁面大小的碎片稱為外碎片(或大碎片)，而小于頁面大小的碎片稱為內(nèi)碎片(或小碎片)。圖4.31地址變換中所用表格的關(guān)系圖4.32段頁式系統(tǒng)地址變換過程4.6.2段頁式存儲管理的評價段頁存儲管理方案保留了分段存儲管理和請求分頁存儲管理的全部優(yōu)點。其主要優(yōu)點是它提供了大量的虛存空間，能有效地利用主存，為組織多道程序運行提供了方便。當(dāng)然，段頁存儲管理也有缺點，主要缺點是增加了硬件成本、系統(tǒng)的復(fù)雜性和管理上的開銷；頁面使用不充分(和請求分頁一樣，存在著內(nèi)碎片)；各種表格(如SMT、PMT等)占用主存空間；存在著系統(tǒng)發(fā)生抖動的危險。4.7WindowsNT虛擬內(nèi)存管理4.7.1進程的虛擬地址空間圖4.33虛擬地址空間4.7.2虛擬存儲的實現(xiàn)圖4.34二級頁表地址變換結(jié)構(gòu)圖4.35地址變換過程舉例我們計算一下，分頁管理和分級頁管理下，頁表所占內(nèi)存大小。在分頁管理下，一個進程的虛擬空間共需要2^{32}/2^{12}=2^{20}=1M個頁表項，假定用一個word（即4Bytes）保存一個頁表項，那么共需4MB來保存一個頁表。

在分級頁管理下，一個進程的虛擬空間被分為一個頁目錄，其中包含1K個頁目錄項，每個頁目錄項包括1K個頁表。這樣保存頁目錄需要1K*4B=4KB，保存頁表需要1K*1K*4B=4MB所以共需4KB+4MB。

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

采用兩級頁表的缺點是降低了訪問主存的速度。因為每進行一次地址變換要有三次訪問主存：查頁目錄訪問一次，查頁表訪問一次，到主存中存取目標數(shù)據(jù)又訪問一次。但實際上WindowsNT的訪問主存速度并不慢，相對來說還比較快，這主要是因為它采取了如下兩個措施：

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

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

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

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

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

范圍是1,0,-1,…,-(n-1)，即[1-n,1]2、如果最多允許m（m<n）個進程同時進入互斥段，信號量初值

為m，變化范圍是：m,m-1,…,0,-1,…,-(n-m)思考：在第（2）問中，當(dāng)信號量值是-(n-m)時，這些進程分別處于什么狀態(tài)？第三章作業(yè)：T24為描述讀者的動作，需要編寫三個程序：實現(xiàn)登記操作Checkin()實現(xiàn)進入閱覽室之后的閱讀操作Read()實現(xiàn)讀者離開時的注銷動作Checkout()。如果閱覽室最多允許n個讀者進入的話，那么就會為每一個讀者i創(chuàng)建一個進程Pi，每個進程按照Pi：Checkin();Read();Checkout()的次序依次順序三個程序執(zhí)行。這里存在的并發(fā)問題主要有：最多只能允許n個讀者（即n個進程）進入閱覽室（即關(guān)鍵區(qū)）每個讀者在進行Checkin和Checkout時對于登記表關(guān)鍵區(qū)必須互斥。為此，我們有如下算法：SemaphoreSn:=100;//最多只允許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