操作系統(tǒng)二版-OS--第三章-課件

1、第三章 存儲(chǔ)管理 (Memory Management) 存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，所以存儲(chǔ)器的管理是操作系統(tǒng)最主要的功能之一。當(dāng)程序的指令和數(shù)據(jù)當(dāng)以文件的形式存放在磁盤上時(shí)，是不能被CPU訪問(wèn)的，只有當(dāng)被調(diào)入內(nèi)存（RAM）里才能被CPU直接訪問(wèn)，程序才能夠被執(zhí)行。雖然目前的RAM芯片的集成度在不斷地提高，從原來(lái)的幾百到現(xiàn)在的幾百兆甚至上千兆，價(jià)格也在不斷地降低，但是軟件系統(tǒng)需要的內(nèi)存容量也在不斷地增加，所以內(nèi)存的容量仍然是計(jì)算機(jī)硬件中最關(guān)鍵的、且又是最緊張的“瓶頸”資源。如何對(duì)存儲(chǔ)器進(jìn)行有效的管理，不僅直接影響到它的利用率，而且還對(duì)系統(tǒng)的性能有重大影響。存儲(chǔ)管理的主要對(duì)象是內(nèi)存。 教

2、學(xué)要求熟悉存儲(chǔ)管理目的和功能，掌握地址重定位的概念。熟悉單一連續(xù)分配、固定分區(qū)分配、動(dòng)態(tài)分區(qū)分配實(shí)現(xiàn)原理；掌握可變分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)和分配回收算法，熟悉可變分區(qū)零頭和拼接技術(shù) 。熟練掌握分頁(yè)存儲(chǔ)管理原理，熟練掌握分頁(yè)存儲(chǔ)管理基本的地址變換機(jī)構(gòu)和具有快表的地址變換機(jī)構(gòu)。掌握分段存儲(chǔ)管理原理和分段地址變換機(jī)構(gòu)，掌握分頁(yè)和分段比較，熟悉分頁(yè)和分段的共享，掌握段頁(yè)式存儲(chǔ)管理原理和地址變換機(jī)構(gòu)。教學(xué)要求-1掌握虛擬存儲(chǔ)器的理論基礎(chǔ)和定義，熟悉虛擬存儲(chǔ)器實(shí)現(xiàn)方式和特征。掌握請(qǐng)求分頁(yè)的頁(yè)表機(jī)制、缺頁(yè)中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)，熟悉頁(yè)面的分配和置換策略、頁(yè)面的分配的算法。熟練掌握最佳置換算法、先進(jìn)先出（FIFO）

3、置換算法、最近最久未使用置換算法LRU，熟悉Clock置換算法和頁(yè)面緩沖算法；熟悉有效訪問(wèn)時(shí)間計(jì)算，了解工作集概念。掌握請(qǐng)求分段的段表機(jī)制、缺段中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)，熟悉分段的共享和保護(hù)。存儲(chǔ)管理目錄31 存儲(chǔ)管理概述311存儲(chǔ)層次結(jié)構(gòu)312存儲(chǔ)管理的功能313 地址重定位32 存儲(chǔ)器的連續(xù)分配321單一連續(xù)分配322固定分區(qū)分配323可變（動(dòng)態(tài)）分區(qū)分配33存儲(chǔ)器的離散分配331純分頁(yè)存儲(chǔ)管理332 分段存儲(chǔ)管理333 段頁(yè)式存儲(chǔ)管理存儲(chǔ)管理目錄-134虛擬存儲(chǔ)器管理技術(shù)341虛擬存儲(chǔ)器的基本概念342請(qǐng)求分頁(yè)存儲(chǔ)管理343請(qǐng)求分段存儲(chǔ)管理35 Windows2000內(nèi)存的管理351Int

4、el x86/Pentium系列CPU對(duì)內(nèi)存管理的硬件支持機(jī)制352 Windows2000地址空間的劃分353 Windows2000用戶空間內(nèi)存分配和使用354頁(yè)面調(diào)度策略355物理內(nèi)存管理35. 6 Windows 2000高速緩沖管理存儲(chǔ)管理目錄-236 實(shí)驗(yàn)與習(xí)題361實(shí)驗(yàn)一：在Windows2000下評(píng)價(jià)內(nèi)存和緩存使用362 實(shí)驗(yàn)2：Windows 2000 內(nèi)存管理API函數(shù)的使用363 選擇題364 問(wèn)答題31 存儲(chǔ)管理概述311存儲(chǔ)層次結(jié)構(gòu) 存儲(chǔ)器是處理器處理的信息的來(lái)源與歸宿，占據(jù)著重要地位。但任何一種存儲(chǔ)設(shè)備都無(wú)法在速度與容量?jī)蓚€(gè)方面同時(shí)滿足用戶的需求。為解決速度和容量之

5、間的矛盾，馮諾依曼計(jì)算機(jī)系統(tǒng)中，采用了三級(jí)或更多級(jí)的存儲(chǔ)器來(lái)組成存儲(chǔ)層次結(jié)構(gòu)，高一級(jí)為CPU寄存器和高速緩存器，中間是主存(可執(zhí)行的存儲(chǔ)器)，最低一級(jí)為輔存。通過(guò)采用特殊的存儲(chǔ)技術(shù)，主存與輔存兩級(jí)可以進(jìn)一步優(yōu)化成多級(jí)。在存儲(chǔ)層次結(jié)構(gòu)中，高層的存儲(chǔ)器往往是速度很快、但成本高使容量有限，而接近底部的存儲(chǔ)器容量很大、成本低，相對(duì)訪問(wèn)速度則慢。各種存儲(chǔ)設(shè)備組成存儲(chǔ)層次結(jié)構(gòu)，如圖51所示。 存儲(chǔ)層次結(jié)構(gòu)圖高速緩存器主存輔存10MB12時(shí)鐘1GB14時(shí)鐘絕對(duì)地址2150(=2000+150)內(nèi)容修改：內(nèi)容100變成2100(=100+2000)。動(dòng)態(tài)重定位 動(dòng)態(tài)重定位是指在程序執(zhí)行過(guò)程中進(jìn)行地址重定位，即

6、在每次訪問(wèn)內(nèi)存單元前才進(jìn)行地址變換。動(dòng)態(tài)重定位可使裝配模塊不加任何修改就裝入內(nèi)存，但是它需要硬件重定位寄存器的支持。下圖給出了動(dòng)態(tài)重定位的示意圖。程序的目標(biāo)模塊在裝入內(nèi)存時(shí)，與地址有關(guān)的指令都無(wú)須進(jìn)行修改，如在圖3-4中LOAD 1，2500這條指令中仍保持相對(duì)地址2500。當(dāng)該指令被操作系統(tǒng)取到中央處理器指令寄存器上執(zhí)行時(shí)，操作系統(tǒng)首先把該模塊裝入的實(shí)際起始地址減去目標(biāo)模塊的相對(duì)基地址（圖3-4中該模塊的基地址為0），然后將其差值10000裝入重定位寄存器。 動(dòng)態(tài)重定位的示意圖LOAD 1，25003650：10025002600程序的地址空間LOAD 1，25003651000010100

7、12500物理地址內(nèi)存的地址空間重定位寄存重定位寄存器中央處理器CPU指令寄存器LOAD 1,25002500(邏輯地址)MMU(存儲(chǔ)管理部件)CPU芯片+10000動(dòng)態(tài)重定位-1當(dāng)CPU執(zhí)行該指令時(shí)，地址變換硬件邏輯自動(dòng)將指令中的邏輯地址2500與重定位寄存器中的值相加，再根據(jù)和值作為內(nèi)存的絕對(duì)地址去訪問(wèn)該單元的數(shù)據(jù)，讀入的數(shù)據(jù)送到寄存器1。完成地址變換硬件是屬于存儲(chǔ)管理部件 MMU，目前它已集成到中央處理器CPU中。 由此可見(jiàn)，動(dòng)態(tài)重定位是在指令執(zhí)行過(guò)程中動(dòng)態(tài)進(jìn)行，它由硬件完成，這樣可以帶來(lái)兩個(gè)好處：目標(biāo)程序裝入內(nèi)存時(shí)無(wú)需任何修改，所以裝入之后再移動(dòng)也不會(huì)影響其正確運(yùn)行，這便于存儲(chǔ)器用緊縮

8、來(lái)解決存儲(chǔ)器的碎片問(wèn)題。一個(gè)程序由若干個(gè)相對(duì)獨(dú)立的目標(biāo)模塊組成時(shí)，每個(gè)目標(biāo)模塊各裝入一個(gè)存儲(chǔ)區(qū)域，這些存儲(chǔ)區(qū)域可以不相領(lǐng)接，只要各個(gè)模塊有自己對(duì)應(yīng)的重定位寄存器就可以了。3.鏈接 靜態(tài)鏈接(static-linking)是在生成可執(zhí)行文件時(shí)進(jìn)行的。在目標(biāo)模塊中記錄符號(hào)地址(symbolic address)，而在可執(zhí)行文件中改寫為指令直接使用的數(shù)字地址。 有一個(gè)程序P（如圖所示），它既可以被其它程序調(diào)用（通過(guò)用符號(hào)定義的入口點(diǎn)如P, e, d），也可以調(diào)用別的程序模塊。前一種情況稱為內(nèi)部定義符號(hào)，后者稱為外部調(diào)用符號(hào)。一個(gè)源程序經(jīng)編譯或匯編后生成的可重定位目標(biāo)模塊必須明顯地給出這些內(nèi)部符號(hào)和外

9、部符號(hào)，以供連接裝入程序使用。每個(gè)可重定位目標(biāo)段相關(guān)聯(lián)的除重定位表（又稱重定位詞典）或指示字外，還應(yīng)有一張內(nèi)部定義符號(hào)表和外部調(diào)用符號(hào)表。鏈接例-1鏈接例-2CALL SUB1ADD TIME內(nèi)部定義符號(hào)：P, e, d。外部調(diào)用符號(hào)：SUB1, TIME。Ped內(nèi)部定義符號(hào)表符號(hào)名地址PedSUB1TIMEPeCALL*ADD*d.外部調(diào)用符號(hào)表重定位詞典.代碼和數(shù)據(jù)區(qū)鏈接例-3動(dòng)態(tài)鏈接動(dòng)態(tài)鏈接(dynamic-linking)在裝入或運(yùn)行時(shí)進(jìn)行鏈接。通常被鏈接的共享代碼稱為動(dòng)態(tài)鏈接庫(kù)(DLL, Dynamic-Link Library)或共享庫(kù)(shared library)。優(yōu)點(diǎn)：共享：

10、多個(gè)進(jìn)程可以共用一個(gè)DLL，節(jié)省內(nèi)存，減少文件交換。部分裝入：一個(gè)進(jìn)程可以將多種操作分散在不同的DLL中實(shí)現(xiàn)，而只將當(dāng)前操作相應(yīng)的DLL裝入內(nèi)存。便于局部代碼修改：即便于代碼升級(jí)和代碼重用；只要函數(shù)的接口參數(shù)（輸入和輸出）不變，則修改函數(shù)及其DLL，無(wú)需對(duì)可執(zhí)行文件重新編譯或鏈接。便于運(yùn)行環(huán)境適應(yīng)：調(diào)用不同的DLL，就可以適應(yīng)多種使用環(huán)境和提供不同功能。如：不同的顯示卡只需廠商為其提供特定的DLL，而OS和應(yīng)用程序不必修改。缺點(diǎn)：鏈接開(kāi)銷：增加了程序執(zhí)行時(shí)的鏈接開(kāi)銷；管理開(kāi)銷：程序由多個(gè)文件組成，增加管理復(fù)雜度。32 存儲(chǔ)器的連續(xù)分配 321單一連續(xù)分配 這是一種最簡(jiǎn)單的存儲(chǔ)管理方式，但只能用

11、于單用戶、單任務(wù)的操作系統(tǒng)，如在8位和16位微機(jī)上CP/M和MS-DOS操作系統(tǒng)。它將內(nèi)存分為兩個(gè)區(qū)： 系統(tǒng)區(qū)：僅供操作系統(tǒng)使用，通常設(shè)置在內(nèi)存的低段； 用戶區(qū)：指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間，提供給用戶使用。 這種存儲(chǔ)分配方式由于用在單用戶、單任務(wù)的操作系統(tǒng)中。單一連續(xù)分配-1系統(tǒng)區(qū)操作系統(tǒng)用戶區(qū)用戶程序 0下限上限基址長(zhǎng)度單一連續(xù)區(qū)存儲(chǔ)管理322固定分區(qū)(Fixed Partitioning)分配 分區(qū)存儲(chǔ)管理是能夠滿足多道程序運(yùn)行的最簡(jiǎn)單的存儲(chǔ)器管理方案，其基本思想是將內(nèi)存劃分成若干個(gè)連續(xù)的區(qū)域，稱為分區(qū)。每個(gè)分區(qū)只能儲(chǔ)存一個(gè)程序，而且程序也只能在它所駐留的分區(qū)中運(yùn)行。分區(qū)存儲(chǔ)管理根據(jù)分區(qū)

12、個(gè)數(shù)及分區(qū)大小的可變性分為固定式分區(qū)和可變式分區(qū)兩種。 固定分區(qū)是在作業(yè)裝入之前，內(nèi)存就被劃分成若干個(gè)分區(qū)。劃分工作可以由系統(tǒng)管理員完成，也可以由操作系統(tǒng)實(shí)現(xiàn)。然而一旦劃分完成，在系統(tǒng)運(yùn)行期間不再重新劃分，即分區(qū)的個(gè)數(shù)不可變，分區(qū)的大小不可變，所以，固定式分區(qū)又稱為靜態(tài)分區(qū)。 這種分區(qū)方式一般將內(nèi)存的用戶區(qū)域劃分成大小不等的分區(qū)，以適應(yīng)不同大小的作業(yè)的需要。系統(tǒng)有一張分區(qū)說(shuō)明表，每個(gè)表目說(shuō)明一個(gè)分區(qū)的大小、起始地址和是否已分配的使用標(biāo)志。分區(qū)說(shuō)明表和內(nèi)存分配圖如下所示。 固定分區(qū)分配-1區(qū)號(hào) 大小 起址 標(biāo)志 1 16KB20K已分配 2 32KB36K已分配 3 64KB68K已分配 4 1

13、24KB 132K 未分配 (a) 分區(qū)說(shuō)明表 固定式分區(qū)實(shí)現(xiàn)技術(shù)簡(jiǎn)單，但是內(nèi)存的利用率不高，適用于作業(yè)的大小和多少事先都比較清楚的系統(tǒng)中。它用于60年代的IBM-360的MFT操作系統(tǒng)中。0k： 20k： 36k： 68k： 132k： 256k： 內(nèi)存分配圖 操作系統(tǒng)作業(yè)A（16k）作業(yè)B（26k）作業(yè)C（56k）第1分區(qū)（16kb）第2分區(qū)（32kb） （已分配）第3分區(qū)（64kb） （已分配）4分區(qū)（124kb ） （未分配） 固定分區(qū)分配-2由于每個(gè)分區(qū)的大小是固定的，所以每個(gè)提出運(yùn)行的作業(yè)必須說(shuō)明所需的最大內(nèi)存容量。在調(diào)度作業(yè)時(shí)，存儲(chǔ)管理程序根據(jù)作業(yè)所需的內(nèi)存容量，在分區(qū)說(shuō)明表中找

14、出一個(gè)足夠大的空閑分區(qū)分配給它，然后用重定位裝入程序?qū)⒋俗鳂I(yè)裝入。如果找不到，則通知作業(yè)調(diào)度模塊，選擇另外一個(gè)作業(yè)。圖3-6（b）說(shuō)明了某一時(shí)刻，作業(yè)A、B、C分別被分配到1，2，3三個(gè)分區(qū)中，第四個(gè)分區(qū)尚未分配，操作系統(tǒng)則永久占據(jù)內(nèi)存低地址區(qū)20KB的空間。當(dāng)一個(gè)作業(yè)結(jié)束時(shí)，系統(tǒng)又調(diào)用存儲(chǔ)管理程序查到分區(qū)說(shuō)明表，把所占分區(qū)的使用標(biāo)志修改為未分配狀態(tài)即可。 固定分區(qū)分配-3采用這種技術(shù)，雖然可以使多個(gè)作業(yè)共駐內(nèi)存，但是一個(gè)作業(yè)的大小不可能正好等于某個(gè)分區(qū)的大小，所以每個(gè)被分配的分區(qū)總有一部分被浪費(fèi)，我們把這部分被浪費(fèi)的存儲(chǔ)區(qū)稱為內(nèi)零頭或內(nèi)碎片。有時(shí)這種分配方式浪費(fèi)相當(dāng)嚴(yán)重，如圖3-6（b）中第

15、3分區(qū)未分配的部分還有8KB，加上第4分區(qū)的124KB共計(jì)132KB，而且這132KB的內(nèi)存空間在物理上是一個(gè)連續(xù)的區(qū)域，這時(shí)如果有一個(gè)大小為130KB的作業(yè)申請(qǐng)內(nèi)存，卻被拒絕，因?yàn)榉謪^(qū)的大小是預(yù)先劃分好的，分區(qū)說(shuō)明表中指出只有第4分區(qū)未分配（大小為124K），且不能改變分區(qū)的大小。Multiprogramming with Fixed PartitionsFixed memory partitionsseparate input queues for each partitionsingle input queue323可變（動(dòng)態(tài)） (Dynamic Partitioning)分區(qū)分配 1.

16、 可變分區(qū)概述可變分區(qū)是指在作業(yè)裝入內(nèi)存時(shí)，從可用的內(nèi)存中劃出一塊連續(xù)的區(qū)域分配給它，且分區(qū)大小正好等于該作業(yè)的大小。可變分區(qū)中分區(qū)的大小和分區(qū)的個(gè)數(shù)都是可變的，而且是根據(jù)作業(yè)的大小和多少動(dòng)態(tài)地劃分，因此又稱為動(dòng)態(tài)分區(qū)。這種存儲(chǔ)管理技術(shù)是固定式分區(qū)的改進(jìn)，既可以獲得較大的靈活性，又能提高內(nèi)存的利用率。系統(tǒng)初始化后，內(nèi)存被劃分成兩塊，一塊用于常駐的操作系統(tǒng)，另一塊則是完整的空閑區(qū)（用戶區(qū)）。對(duì)于調(diào)入的若干個(gè)作業(yè)，劃分幾個(gè)大小不等的分區(qū)給它們，隨著作業(yè)的調(diào)入和撤除，相應(yīng)的分區(qū)被劃分和釋放，原來(lái)整塊的存儲(chǔ)區(qū)形成空閑區(qū)和已分配區(qū)相間的局面。圖3-7（c）給出了可變式分區(qū)的示例，512KB內(nèi)存中除20K

17、B操作系統(tǒng)外，裝入作業(yè)2、3、4、6四個(gè)，有空閑區(qū)1、2、3三個(gè)。 可變式分區(qū)數(shù)據(jù)結(jié)構(gòu)圖表 序號(hào)P大小起址狀態(tài) 132k20k空閑 256k260k空閑 3 116k396k空閑 4空表目 5空表目 （a）空閑分區(qū)表前向指針 N+2 00后向指針 N+2 00N個(gè)字可用空閑區(qū)（56k）作業(yè)6（80k）空閑區(qū)（116k）空閑區(qū)（32k）作業(yè)2（64k）作業(yè)3（48k）作業(yè)4（96k）操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K返回可變分區(qū)概述-1可變式分區(qū)的分配和釋放的基本思想是：在分配時(shí)，首先找到一個(gè)足夠大的空閑分區(qū)，即這個(gè)空閑區(qū)的大小比作業(yè)要求的要大，系統(tǒng)

18、則將這個(gè)空閑分區(qū)分成兩部分：一部分成為已分配的分區(qū)，剩余的部分仍作為空閑區(qū)。在回收撤除作業(yè)所占領(lǐng)的分區(qū)時(shí)，要檢查回收的分區(qū)是否與前后空閑的分區(qū)相領(lǐng)接，若是，則加以合并，使之成為一個(gè)連續(xù)的大空間。 Example Dynamic PartitioningOperating SystemProcess 1320 KProcess 2Process 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3288 K64 KProcess 412

19、8 K96 KExample Dynamic Partitioning-1Operating System320 KProcess 3288 K64 KProcess 4128 K96 KOperating SystemProcess 3288 K64 KProcess 4128 K96 KProcess 2224 k96 K動(dòng)態(tài)/可變式分區(qū)分配-12. 可變式分區(qū)的數(shù)據(jù)結(jié)構(gòu) 空閑區(qū)表形式 空閑分區(qū)表為每個(gè)尚未分配的分區(qū)設(shè)置一個(gè)表項(xiàng)，包括分區(qū)的序號(hào)、大小、始址和狀態(tài)。空閑區(qū)鏈形式 為了實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接，在每個(gè)分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息（如分區(qū)的大小和狀態(tài)位），以及

20、用于鏈接其它分區(qū)的前向指針；在分區(qū)尾部，則設(shè)置了一個(gè)后向指針，為了檢索方便也設(shè)置了控制分區(qū)分配的信息。然后，通過(guò)前、后向指針將所有的分區(qū)鏈接成一個(gè)雙向鏈表。3. 可變分區(qū)分配算法 (Partitioning Placement Algorithm)(1)最佳適應(yīng)算法BF（Best Fit）：它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按大小從小到大進(jìn)行排序，自表頭開(kāi)始查找到第一個(gè)滿足要求的自由分區(qū)分配。該算法保留大的空閑區(qū)，但造成許多小的空閑區(qū)。(2)首次適應(yīng)算法FF（First Fit）：從空閑分區(qū)表

21、的第一個(gè)表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時(shí)間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進(jìn)行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)?？勺兎謪^(qū)分配算法-1(3)循環(huán)首次適應(yīng)算法NF(Next Fit)：該算法是首次適應(yīng)算法的變種，它把空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)按地址遞增構(gòu)成一個(gè)循環(huán)鏈。在分配內(nèi)存空間時(shí)，不再每次從表頭（鏈?zhǔn)祝╅_(kāi)始查找，而是從上次找到的空閑區(qū)的下一個(gè)空閑區(qū)開(kāi)始查找，直到找到第一個(gè)能滿足要求的的空閑區(qū)為止，并從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)

22、。該算法能使內(nèi)存中的空閑區(qū)分布得比較均勻。(4)最壞適應(yīng)法：從所有未分配的分區(qū)中挑選最大的且大于和等于作業(yè)大小的分區(qū)分給要求的作業(yè)；空閑分區(qū)按大小由大到小排序。該算法使小的空閑區(qū)減少，但造成大的空閑區(qū)不夠大。例：分配一個(gè)16KB分區(qū)采用空閑分區(qū)表結(jié)構(gòu)和首次適應(yīng)分配算法 空閑分區(qū)表數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表中的空閑分區(qū)要按地址從低到高連續(xù)排序，最后一個(gè)空閑分區(qū)中 m_size為0表示以上表目空白?？臻e分區(qū)表起始地址為coremap分配和釋放的基本思想是：在分配時(shí)，首先找到一個(gè)足夠大的空閑分區(qū)，即這個(gè)空閑區(qū)的大小比作業(yè)要求的要大，系統(tǒng)則將這個(gè)空閑分區(qū)分成兩部分：一部分成為已分配的分區(qū)，剩余的部分仍作為空閑

23、區(qū)。在回收撤除作業(yè)所占領(lǐng)的分區(qū)時(shí)，要檢查回收的分區(qū)是否與前后空閑的分區(qū)相領(lǐng)接，若是，則加以合并，使之成為一個(gè)連續(xù)的大空間。m_addrm_size.m_addrm_size=0.m_addrm_sizem_addrm_sizem_addrm_sizem_addrm_sizeCoremap采用首次適應(yīng)算法的可變分區(qū)的分配流程圖 申請(qǐng)分配一個(gè)u.size大小的分區(qū)從頭開(kāi)始查表是否檢索完畢？本次無(wú)法分配m.sizeu.size m.size-u.sizesize？從該分區(qū)中劃出u.size大小的分區(qū)繼續(xù)檢索下一個(gè)表項(xiàng)將該表目以上的所有表目下移一格將該分區(qū)分配給申請(qǐng)者修改有關(guān)的數(shù)據(jù)結(jié)構(gòu) 返 回YNN4

24、. 可變分區(qū)回收算法 當(dāng)一個(gè)作業(yè)運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)釋放區(qū)的首地址，從空閑區(qū)說(shuō)明表中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)下列四種情況（如圖3-9所示，其中F1，F(xiàn)2表示回收區(qū)的前、后空閑區(qū)）：(1)當(dāng)回收區(qū)既不與F1領(lǐng)接，又不與F2領(lǐng)接時(shí)（如圖3-9（a），應(yīng)為回收區(qū)單獨(dú)建立一項(xiàng)新表目，填寫回收區(qū)的起址和大小，并根據(jù)其起址，插入到空閑區(qū)說(shuō)明表的適當(dāng)位置。(2)當(dāng)回收區(qū)只與插入點(diǎn)的前一個(gè)分區(qū)F1相領(lǐng)接時(shí)（如圖3-9（b），應(yīng)將回收區(qū)與插入點(diǎn)的前一個(gè)分區(qū)合并，不再為回收區(qū)分配新的表目，而只需修改F1分區(qū)表目的大小即可。 可變分區(qū)回收算法 -1(3)當(dāng)回收區(qū)只與插入點(diǎn)的后一個(gè)分區(qū)F2相領(lǐng)接時(shí)（如圖

25、3-9（c），將把兩個(gè)空閑區(qū)合并，修改F2分區(qū)的表目，把回收區(qū)的起址作為新空閑區(qū)的起址，大小為兩個(gè)分區(qū)之和。(4)當(dāng)回收區(qū)與插入點(diǎn)的前、后兩個(gè)分區(qū)（F1和F2）都相領(lǐng)接時(shí)（如圖3-9（d），合并三個(gè)分區(qū)，用F1表目的起址作為新空閑區(qū)的起址，修改其大小為三塊分區(qū)之和，最后取消F2的表目。圖3-7（c）內(nèi)存分配圖中作業(yè)3、2、4、6分別回收時(shí)相當(dāng)于圖3-9（a）、（b）、（c）、（d）內(nèi)存回收時(shí)的情況。 可變分區(qū)回收算法 -2 作業(yè)Y回收區(qū) 作業(yè)X F1 F1 回收區(qū) 作業(yè)Y F2 F1 回收區(qū) F2 作業(yè)Y 回收區(qū) F2 作業(yè)X 作業(yè)Y A B C D可變分區(qū)回收算法 -3對(duì)于前圖所示的可變式分

26、區(qū)內(nèi)存分配圖，下列四種情況分別如下圖所示： 作業(yè)4回收區(qū) 作業(yè)2空閑區(qū)1 空閑區(qū)1 回收區(qū) 作業(yè)3 空閑區(qū)2 回收區(qū)空閑區(qū)3 回收區(qū) 空閑區(qū)2 作業(yè)3 作業(yè)6 A B C D作業(yè)3回收 作業(yè)2回收 作業(yè)4回收 作業(yè)6回收可變分區(qū)回收算法 -4作業(yè)3回收前后序號(hào)P大小起址狀態(tài) 132k20k空閑 256k260k空閑 3 116k396k空閑 4空表目 5空表目 （a）空閑分區(qū)表序號(hào)P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 48k 116k 空閑 3 56k 260k 空閑 4 116k 396k 空閑 5 空表目 空閑分區(qū)表空閑區(qū)2（56k）作業(yè)6（80k）空閑區(qū)3（116k）空閑區(qū)

27、1（32k）作業(yè)2（64k）作業(yè)3（48k） 回收區(qū)作業(yè)4（96k）操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K空閑區(qū)3（56k）作業(yè)6（80k）空閑區(qū)4（116k）空閑區(qū)1（32k） 作業(yè)2（64k）空閑區(qū)2（48k）作業(yè)4（96k）操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K 回收前 回收后空閑區(qū)2（56k）作業(yè)6（80k）空閑區(qū)3（116k）作業(yè)3 （48k）作業(yè)4（96k）操作系統(tǒng)(20K)020K116K164K260K316K396K512K空閑區(qū)2（56k）作業(yè)6（80k）空閑區(qū)3（116k）空閑區(qū)1（32k

28、）作業(yè)2（64k） 回收區(qū)作業(yè)3（48k） 作業(yè)4（96k）操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K 回收前 回收后可變分區(qū)回收算法 -5作業(yè)2回收前后序號(hào)P大小起址狀態(tài) 132k20k空閑 256k260k空閑 3 116k396k空閑 4空表目 5空表目 （a）空閑分區(qū)表序號(hào)P 大小 起址 狀態(tài) 1 96k 20k 空閑 2 56k 260k 空閑 3 116k 396k 空閑 4 空表目 5 空表目 空閑分區(qū)表空閑區(qū)1（96k）可變分區(qū)回收算法 -6作業(yè)4回收前后序號(hào)P大小起址狀態(tài) 132k20k空閑 256k260k空閑 3 116k396k空閑

29、 4空表目 5空表目 （a）空閑分區(qū)表序號(hào)P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 152k 164k 空閑 3 116k 396k 空閑 4 空表目 5 空表目 空閑分區(qū)表空閑區(qū)2（56k）作業(yè)6（80k）空閑區(qū)3（116k）空閑區(qū)1（32k）作業(yè)2（64k）作業(yè)3（48k） 作業(yè)4（96k） 回收區(qū)操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K空閑區(qū)2（152k）作業(yè)6（80k）空閑區(qū)3（116k）空閑區(qū)1（32k）作業(yè)2（64k）作業(yè)3 （48k）操作系統(tǒng)(20K)020K52K116K164K316K396K512K 回收前 回收后可變分區(qū)回

30、收算法 -7作業(yè)6回收前后序號(hào)P大小起址狀態(tài) 132k20k空閑 256k260k空閑 3 116k396k空閑 4空表目 5空表目 （a）空閑分區(qū)表序號(hào)P 大小 起址 狀態(tài) 1 32k 20k 空閑 2 252k 260k 空閑 3 空表目 4 空表目 5 空表目 空閑分區(qū)表作業(yè)6（80k）空閑區(qū)4（116k）空閑區(qū)2（56k）作業(yè)6-80k回收區(qū)空閑區(qū)3（116k）空閑區(qū)1（32k）作業(yè)2（64k）作業(yè)3（48k） 作業(yè)4（96k）操作系統(tǒng)(20K)020K52K116K164K260K316K396K512K空閑區(qū)2（252k）空閑區(qū)1（32k）作業(yè)2（64k）作業(yè)3 （48k）作業(yè)4（

31、96k）操作系統(tǒng)(20K)020K52K116K164K260K512K 回收前 回收后可變分區(qū)回收算法 -8后空閑區(qū)不 D不 A鄰 B鄰 C前空閑區(qū)不鄰不鄰表目加一/ /減一后空閑區(qū)首址/-size撤消后空閑區(qū)大小/+size撤消前空閑區(qū)首址/前空閑區(qū)大小/+size/+size+后空閑區(qū)大小5. 可變分區(qū)零頭和拼接技術(shù) 可變分區(qū)也有零頭問(wèn)題。在系統(tǒng)不斷地分配和回收中，必定會(huì)出現(xiàn)一些不連續(xù)的小的空閑區(qū)，稱為外零頭或外碎片。雖然可能所有零頭的總和超過(guò)某一個(gè)作業(yè)的要求，但是由于不連續(xù)而無(wú)法分配。解決零頭的方法是拼接或緊湊（Compaction），即向一個(gè)地址方向（例如向低地址端）移動(dòng)已分配的作業(yè)

32、，使那些零散的小空閑區(qū)在另一方向連成一片。分區(qū)的拼接技術(shù)，一方面是要求能夠?qū)ψ鳂I(yè)進(jìn)行重定位，另一方面系統(tǒng)在拼接時(shí)要耗費(fèi)較多的時(shí)間。采用拼接技術(shù)的可變分區(qū)又稱可重定位分區(qū)。 動(dòng)態(tài)重定位分區(qū)分配例 20k28k88k132k182ko.s作業(yè)1(8k)(16k)作業(yè)3(24k)(24k)作業(yè)(20k)作業(yè)4(50k)(74k)64k112k256k(a)初始狀態(tài)20k202ko.s1324作業(yè)5(80k)(54k)122k(c)分配作業(yè)5之后(b)移動(dòng)之后(即浮動(dòng))20k28k72ko.s1(8k)3(24k)2(20k)4(50k)(134k)52k122k256k作業(yè)580k6. 分區(qū)的存儲(chǔ)保

33、護(hù) 分區(qū)的存儲(chǔ)保護(hù)是用戶程序只能訪問(wèn)自己的用戶分區(qū)，不能訪問(wèn)系統(tǒng)分區(qū)和其它程序的分區(qū)。分區(qū)存儲(chǔ)保護(hù)常用方法是界地址法或界限寄存器。系統(tǒng)設(shè)置一對(duì)上、下界寄存器，每當(dāng)選中某個(gè)作業(yè)運(yùn)行時(shí)，先將它的界地址裝入這對(duì)寄存器中，作業(yè)運(yùn)行時(shí)形成的每一個(gè)訪問(wèn)存儲(chǔ)器的地址都要同這兩個(gè)寄存器的內(nèi)容進(jìn)行比較，若超過(guò)這個(gè)指定范圍，就產(chǎn)生越界中斷。系統(tǒng)也可以設(shè)置一對(duì)基址、限長(zhǎng)寄存器，此時(shí)基址寄存器還起著重定位寄存器的作用，運(yùn)行進(jìn)程所在分區(qū)的始址和大小分別裝入基址和限長(zhǎng)寄存器。界限寄存器用硬件實(shí)現(xiàn)，它是存儲(chǔ)管理部件 MMU的一部分，采用基址、限長(zhǎng)寄存器的地址變換和存儲(chǔ)保護(hù)的存儲(chǔ)管理部件 MMU見(jiàn)圖310所示。 分區(qū)的存儲(chǔ)保

34、護(hù) -1界限寄存器重定位寄存器(基址)+CPU=1地址越界地址越界lbSlbSegmentation Hardware5共享 段是信息的邏輯單位,因此分段系統(tǒng)的一個(gè)突出的優(yōu)點(diǎn)是易于實(shí)現(xiàn)段的共享。即允許若干個(gè)進(jìn)程共享一個(gè)或多個(gè)段，而且對(duì)段的保護(hù)也十分簡(jiǎn)單。在分頁(yè)系統(tǒng)中，雖然也能實(shí)現(xiàn)程序和數(shù)據(jù)的共享，但遠(yuǎn)不如分段系統(tǒng)來(lái)得方便。分段系統(tǒng)中，每個(gè)進(jìn)程的段表中設(shè)置一個(gè)段表項(xiàng)。圖是分段系統(tǒng)中共享 editor編輯程序的示意圖。在實(shí)現(xiàn)段共享時(shí)，需要用到可重入代碼(Reentrant Code)又稱為“純代碼”(Pure Code)。它是一種允許多個(gè)進(jìn)程同時(shí)訪問(wèn)的代碼，是一種不允許任何進(jìn)程對(duì)其進(jìn)行修改的代碼。

35、但在每個(gè)進(jìn)程中，配以局部數(shù)據(jù)區(qū)，將在執(zhí)行中可能改變的部分，拷貝到該數(shù)據(jù)區(qū)，這樣，程序在執(zhí)行時(shí)，只對(duì)該數(shù)據(jù)區(qū)(屬于該進(jìn)程私有)中的內(nèi)容進(jìn)行修改，而不去改變共享的代碼，這時(shí)的可共享代碼即成為可重入代碼。共享-1 段 表段長(zhǎng) 基址 160 80 40 240 editor DATA1 editor DATA2段長(zhǎng) 基址160 8040 380 editorDATA1 DATA2進(jìn)程1進(jìn)程2 802402803804206分頁(yè)和分段的主要區(qū)別 分頁(yè)和分段的主要區(qū)別-1 333 段頁(yè)式存儲(chǔ)管理 分頁(yè)和分段存儲(chǔ)管理方式都各有其優(yōu)缺點(diǎn)。如果對(duì)兩種存儲(chǔ)管理方式“各取所長(zhǎng)”后，則可以形成一種新的存儲(chǔ)管理方式的系

36、統(tǒng)段頁(yè)式系統(tǒng)。它以分頁(yè)的方式管理內(nèi)存，具有分頁(yè)系統(tǒng)能有效地提高內(nèi)存利用率的優(yōu)點(diǎn)；又以分段的方式管理用戶的邏輯地址空間，具有分段系統(tǒng)能很好地滿足用戶需要的長(zhǎng)處，顯然是一種比較有效的存儲(chǔ)管理方式。 1基本原理 段頁(yè)式系統(tǒng)的基本原理是將內(nèi)存空間劃分成相同大小相同的若干個(gè)塊，將用戶程序先按邏輯完整性分為若干個(gè)段，并為每個(gè)段賦予一個(gè)段名，再把每個(gè)段劃分成若干個(gè)與塊大小相同的頁(yè)，將進(jìn)程中的若干頁(yè)離散裝入不相鄰接的塊中。圖3-20中示出了一個(gè)作業(yè)地址空間結(jié)構(gòu)，該作業(yè)有四個(gè)段，頁(yè)面大小為4K，四個(gè)段的頁(yè)面數(shù)分別為4、2、2、2，總頁(yè)面數(shù)為10頁(yè)，此時(shí)每一頁(yè)都屬于邏輯上完整的一個(gè)段。在段頁(yè)式系統(tǒng)中，其地址結(jié)構(gòu)由

37、段號(hào)、段內(nèi)頁(yè)號(hào)和頁(yè)內(nèi)地址三部分組成，作業(yè)地址空間的結(jié)構(gòu)如圖3-21所示。 基本原理-1 在段頁(yè)式系統(tǒng)中，為了實(shí)現(xiàn)從邏輯地址到物理地址的變換，系統(tǒng)中必需同時(shí)配置段表和頁(yè)表。由于將段中的頁(yè)進(jìn)行離散地分配，段表中的內(nèi)容不再是段的內(nèi)存始址和段長(zhǎng)，而是頁(yè)表始址和頁(yè)表長(zhǎng)度。下圖說(shuō)明了利用段表和頁(yè)表進(jìn)行地址映射的過(guò)程。 段號(hào)（S） 段內(nèi)頁(yè)號(hào)（P） 頁(yè)內(nèi)地址（W）段頁(yè)式系統(tǒng)的作業(yè)地址空間 段表、頁(yè)表的作用段表大小段表始址2地址變換過(guò)程在段頁(yè)式系統(tǒng)中，有一個(gè)段表寄存器，存放段表始址和段長(zhǎng)TL。在進(jìn)行地址變換時(shí)，系統(tǒng)將邏輯地址截成段號(hào)S、段內(nèi)頁(yè)號(hào)P與頁(yè)內(nèi)地址W，先用段號(hào)S與段長(zhǎng)TL進(jìn)行比較。若 STL，表示段號(hào)太

38、大，訪問(wèn)越界，于是產(chǎn)生越界中斷信號(hào)；若STL，表示未越界，于是利用段表始址和段號(hào)求出該段對(duì)應(yīng)的段表項(xiàng)在段表中的位置，從中得到該段的頁(yè)表始址，并利用邏輯地址中的段內(nèi)頁(yè)號(hào)P來(lái)獲得對(duì)應(yīng)頁(yè)的頁(yè)表項(xiàng)在頁(yè)表中位置，從中讀出該頁(yè)所在的物理塊號(hào)b，再用塊號(hào) b和頁(yè)內(nèi)地址W拼成物理地址。圖3-23說(shuō)明了段頁(yè)式系統(tǒng)中的地址變換機(jī)構(gòu) 。地址變換過(guò)程-1在段頁(yè)式系統(tǒng)中，為了獲得一條指令或數(shù)據(jù)，需三次訪問(wèn)內(nèi)存：第一次訪問(wèn)內(nèi)存中的段表，從中取得頁(yè)表始址；第二次訪問(wèn)內(nèi)存中的頁(yè)表，從中取出該頁(yè)所在的物理塊號(hào)，并將該塊號(hào)與頁(yè)內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；第三次訪問(wèn)才是真正根據(jù)所得的物理地址取出指令或數(shù)據(jù)。顯然，這使訪問(wèn)內(nèi)

39、存的次數(shù)增加了近兩倍。為了提高執(zhí)行的速度，在地址變換機(jī)構(gòu)中增設(shè)一高速緩沖寄存器。每次訪問(wèn)它時(shí)，都同時(shí)利用段號(hào)和頁(yè)號(hào)去檢索高速緩存。段頁(yè)式系統(tǒng)的地址變換機(jī)構(gòu)圖 + 段 表0123 頁(yè) 表0123段表始址 段表長(zhǎng)度 +段號(hào)（S）段內(nèi)頁(yè)號(hào)（P）頁(yè)內(nèi)地址（W）塊 號(hào)b 塊內(nèi)地址越界中斷段表寄存器CPU邏輯地址物理地址 b頁(yè)表始址34虛擬存儲(chǔ)器管理技術(shù) 前面所介紹的各種存儲(chǔ)器管理方式，有一個(gè)共同的特點(diǎn)，即要求將一個(gè)作業(yè)全部裝入內(nèi)存才能運(yùn)行。如果有的作業(yè)很大，其所要求的內(nèi)存空間超過(guò)了內(nèi)存總?cè)萘?，作業(yè)就不能全部被裝入內(nèi)存，致使該作業(yè)無(wú)法運(yùn)行；有時(shí)大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將

40、少數(shù)作業(yè)裝入內(nèi)存讓它們先運(yùn)行，而將其它大量的作業(yè)留在外存上等待。顯而易見(jiàn)的一種解決方法，是從物理上增加內(nèi)存容量，但這往往會(huì)受到機(jī)器自身的限制，而且無(wú)疑要增加系統(tǒng)成本，因此這種方法是受到一定限制的；另一種方法是從邏輯上擴(kuò)充內(nèi)存容量，這正是虛擬存儲(chǔ)技術(shù)所要解決的主要問(wèn)題。 341虛擬存儲(chǔ)器的基本概念 1局部性原理(principle of locality)實(shí)際上有許多作業(yè)在每次運(yùn)行時(shí)，并非用到其全部程序，那么是否可以僅把作業(yè)的一部分裝入內(nèi)存就能運(yùn)行呢？回答是可以的，我們先來(lái)研究虛擬存儲(chǔ)器系統(tǒng)實(shí)現(xiàn)的理論基礎(chǔ)：程序執(zhí)行的局部性規(guī)律。早在1968年P(guān)Denning就指出過(guò)，程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)

41、律，即在一段時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域內(nèi)。局部性原理-1那么程序?yàn)槭裁磿?huì)出現(xiàn)局部性規(guī)律呢？原因可以歸結(jié)為以下幾點(diǎn)：程序在執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過(guò)程調(diào)用指令外，大多數(shù)仍是順序執(zhí)行的。子程序調(diào)用將會(huì)使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過(guò)程調(diào)用的深度都不超過(guò)5。程序中存在許多循環(huán)結(jié)構(gòu)，循環(huán)體中的指令被多次執(zhí)行。程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)連續(xù)的存儲(chǔ)空間數(shù)組的訪問(wèn)，往往局限于很小的范圍內(nèi)。局部性原理- 2 所以局限性表現(xiàn)為： 時(shí)間局限性：如果程序中的某條指令一旦執(zhí)行，則不久的將來(lái)該指令可能再次被執(zhí)行；如果某個(gè)

42、存儲(chǔ)單元被訪問(wèn)，則不久以后該存儲(chǔ)單元可能再次被訪問(wèn)。產(chǎn)生時(shí)間局限性的典型原因是在程序中存在著大量的循環(huán)操作。 空間局限性：一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元，則在不久的將來(lái)，其附近的存儲(chǔ)單元也最有可能被訪問(wèn)。 即程序在一段時(shí)間內(nèi)所訪問(wèn)的地址，可能集中在一定的范圍內(nèi)，其典型原因是程序是順序執(zhí)行的。2。虛擬存儲(chǔ)器的定義 根據(jù)局部性原理，一個(gè)作業(yè)在運(yùn)行之前，沒(méi)有必要把全部作業(yè)裝入內(nèi)存，而僅將那些當(dāng)前要運(yùn)行的那部分頁(yè)面或段，先裝入內(nèi)存便可啟動(dòng)運(yùn)行，其余部分暫時(shí)留在磁盤上。程序在運(yùn)行時(shí)如果它所要訪問(wèn)的頁(yè)（段）已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去；但如果程序所要訪問(wèn)的頁(yè)（段）尚未調(diào)入內(nèi)存（稱為缺頁(yè)或缺段），此時(shí)程序應(yīng)利用

43、操作系統(tǒng)所提供的請(qǐng)求調(diào)頁(yè)（段）功能，將它們調(diào)入內(nèi)存，以使進(jìn)程能繼續(xù)執(zhí)行下去。如果此時(shí)內(nèi)存已滿，無(wú)法再裝入新的頁(yè)（段），則還須再利用頁(yè)（段）的置換功能，將內(nèi)存中暫時(shí)不用的頁(yè)（段）調(diào)出至磁盤上，騰出足夠的內(nèi)存空間后，再將所要訪問(wèn)的頁(yè)（段）調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。這樣，便可使一個(gè)大的用戶程序在較小的內(nèi)存空間中運(yùn)行；也可使內(nèi)存中同時(shí)裝入更多的進(jìn)程并發(fā)執(zhí)行。從用戶角度看，該系統(tǒng)所具有的內(nèi)存容量，將比實(shí)際內(nèi)存容量大得多，人們把這樣的存儲(chǔ)器稱為虛擬存儲(chǔ)器。 虛擬存儲(chǔ)器的定義-1 虛擬存儲(chǔ)器是采用請(qǐng)求調(diào)入和置換功能，將內(nèi)存和外存統(tǒng)一管理，達(dá)到把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行，給用戶提供的一個(gè)比內(nèi)存容量大的

44、一維的邏輯地址空間。 虛擬存儲(chǔ)器的邏輯容量由內(nèi)存和外存容量之和、計(jì)算機(jī)的地址結(jié)構(gòu)二者所決定，其運(yùn)行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。實(shí)現(xiàn)虛擬存儲(chǔ)技術(shù)的物質(zhì)基礎(chǔ)是：一是有相當(dāng)容量的輔助存儲(chǔ)器以存放所有并發(fā)作業(yè)的地址空間；二是有一定容量的內(nèi)存來(lái)存放運(yùn)行作業(yè)的部分程序；三是有動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)，實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換?？梢?jiàn)，虛擬存儲(chǔ)技術(shù)是一種性能非常優(yōu)越的存儲(chǔ)器管理技術(shù)，故被廣泛地應(yīng)用于大、中、小型機(jī)器和微型機(jī)中。虛擬存儲(chǔ)器的定義-2外存內(nèi)存虛擬存儲(chǔ)器邏輯地址虛擬存儲(chǔ)器實(shí)現(xiàn)方式請(qǐng)求分頁(yè)系統(tǒng)： 它是在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。它允許只

45、裝入若干頁(yè)（而非全部程序）的用戶程序和數(shù)據(jù)，就可以啟動(dòng)運(yùn)行，以后再通過(guò)調(diào)頁(yè)功能和頁(yè)面置換功能，陸續(xù)把將要運(yùn)行的頁(yè)面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁(yè)面置換到外存上，置換時(shí)以頁(yè)面為單位。請(qǐng)求分段系統(tǒng)： 它是在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段和分段置換功能所形成的段式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入若干段（而非全部段）的用戶程序和數(shù)據(jù)，就可以啟動(dòng)運(yùn)行，以后再通過(guò)調(diào)段功能和置換功能將不運(yùn)行的段調(diào)出，同時(shí)調(diào)入將要運(yùn)行的段，置換以段為單位。請(qǐng)求段頁(yè)式系統(tǒng)：它是在段頁(yè)式系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能所形成的段頁(yè)式虛擬存儲(chǔ)系統(tǒng)。3。虛擬存儲(chǔ)器的特征離散性：指在內(nèi)存分配時(shí)采用離散的分配方式，它是虛擬存儲(chǔ)器的最

46、基本的特征。多次性：指一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行，即在作業(yè)運(yùn)行時(shí)沒(méi)有必要將其全部裝入，只須將當(dāng)前要運(yùn)行的那部分程序和數(shù)據(jù)裝入內(nèi)存即可。多次性是虛擬存儲(chǔ)器最重要的特征。對(duì)換性：指允許在作業(yè)的運(yùn)行過(guò)程中在內(nèi)存和外存的對(duì)換區(qū)之間換進(jìn)、換出。虛擬性：指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。342請(qǐng)求分頁(yè)存儲(chǔ)管理 請(qǐng)求分頁(yè)存儲(chǔ)管理方式是在純分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)，它是目前常用的一種虛擬存儲(chǔ)器的方式。它允許只裝人若干頁(yè)(而非全部頁(yè))的用戶程序和數(shù)據(jù)，便可啟動(dòng)運(yùn)行。以后，再通過(guò)調(diào)頁(yè)功能及頁(yè)面置換功能，陸續(xù)地把即將要運(yùn)行的頁(yè)

47、面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁(yè)面換出到外存上，置換時(shí)以頁(yè)面為單位。 342請(qǐng)求分頁(yè)存儲(chǔ)管理 1。請(qǐng)求分頁(yè)中的硬件支持為了能實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)和置換功能，系統(tǒng)必須提供必要的硬件支持：擴(kuò)充的頁(yè)表機(jī)制和缺頁(yè)中斷機(jī)構(gòu)。 （1）請(qǐng)求分頁(yè)的頁(yè)表機(jī)制 它是在純分頁(yè)的頁(yè)表機(jī)制上形成的，由于只將應(yīng)用程序的一部分調(diào)入內(nèi)存，還有一部分仍在磁盤上，故需在頁(yè)表中再增加若干項(xiàng)，供程序(數(shù)據(jù))在換進(jìn)、換出時(shí)參考。在請(qǐng)求分頁(yè)系統(tǒng)中的每個(gè)頁(yè)表項(xiàng)如圖所示。 頁(yè)號(hào) 物理塊號(hào) 狀態(tài)位P 訪問(wèn)字段A 修改位M 外存地址請(qǐng)求分頁(yè)中的硬件支持-1其中各字段說(shuō)明如下：狀態(tài)位（中斷位P）：用于指示該頁(yè)是否已調(diào)入內(nèi)存，供程序訪問(wèn)時(shí)參考。外存地址：用于

48、指出該頁(yè)在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)使用。訪問(wèn)字段A：用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)，或最近已有多長(zhǎng)時(shí)間未被訪問(wèn)，提供給置換算法選擇換出頁(yè)面時(shí)參考。修改位M：表示該頁(yè)在調(diào)入內(nèi)存后是否被修改過(guò)。由于內(nèi)存中的每一頁(yè)都在外存上保留一份副本，因此，若未被修改，在置換該頁(yè)時(shí)就不需將該頁(yè)寫回到外存上，以減少系統(tǒng)的開(kāi)銷和啟動(dòng)磁盤的次數(shù)；若已被修改，則必須將該頁(yè)重寫到外存上，以保證外存中所保留的始終是最新副本。外存地址：用于指出該頁(yè)在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)使用 (2)缺頁(yè)中斷機(jī)構(gòu)在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，便要產(chǎn)生一缺頁(yè)中斷，請(qǐng)求OS將所缺頁(yè)調(diào)入內(nèi)

49、存。與一般中斷的主要區(qū)別在于：缺頁(yè)中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)，而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信號(hào)。缺頁(yè)中斷返回到該指令的開(kāi)始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。(3)地址變換機(jī)構(gòu) 請(qǐng)求分頁(yè)系統(tǒng)中的地址變換機(jī)構(gòu)，是在分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上，再為實(shí)現(xiàn)虛擬存儲(chǔ)器而增加了某些功能所形成的，如產(chǎn)生和處理缺頁(yè)中斷，以及從內(nèi)存中換出一頁(yè)的功能等等，下圖給出了請(qǐng)求分頁(yè)系統(tǒng)的地址變換過(guò)程。 缺頁(yè)中斷處理 是 否 否 是 是 否 產(chǎn)生缺頁(yè)中 否 是 斷請(qǐng)求調(diào)頁(yè) 是 開(kāi)始（程序請(qǐng)求訪問(wèn)一頁(yè))越界中斷CPU檢索快表頁(yè)表項(xiàng)是否在

50、快表中？訪問(wèn)頁(yè)表頁(yè)是否在內(nèi)存中？修改快表修改訪問(wèn)位和修改位形成物理地址 地址變換結(jié)束保留CPU現(xiàn)場(chǎng) 從外存中找到缺頁(yè) 頁(yè)號(hào)頁(yè)表長(zhǎng)度？ 內(nèi)存滿否？選擇一頁(yè)換出 該頁(yè)是否被修改？ 將該頁(yè)寫回外存 將一頁(yè)從外存換入內(nèi)存 修改頁(yè)表 CPU從外存讀缺頁(yè) 啟動(dòng)I/O硬件 2. 請(qǐng)求分頁(yè)存儲(chǔ)管理應(yīng)考慮的問(wèn)題 （1）最少物理塊數(shù)的確定 在為進(jìn)程分配物理塊時(shí)，首先應(yīng)該考慮的問(wèn)題是：能保證進(jìn)程能正常運(yùn)行所需的最少物理塊數(shù)（稱為最小物理塊數(shù)）。若系統(tǒng)為某進(jìn)程所分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無(wú)法運(yùn)行，這取決于指令的格式、功能和尋址方式。物理塊數(shù)目的下限，應(yīng)該是一條指令及其操作數(shù)可能涉及的頁(yè)面數(shù)目的上限，以保證每條指

51、令都能被執(zhí)行。（2）物理塊的分配和置換策略 在請(qǐng)求分頁(yè)系統(tǒng)中，可采取兩種分配策略固定和可變分配策略。在進(jìn)行置換時(shí)，也可采取兩種策略全局置換和局部置換。于是可組合成以下三種策略。固定分配局部置換策略：它基于進(jìn)程的類型（交互型或批處理型等），或根據(jù)程序員、系統(tǒng)管理員的建議，為每個(gè)進(jìn)程分配一固定頁(yè)數(shù)的內(nèi)存空間，在整個(gè)運(yùn)行期間都不再改變。如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁(yè)，則只能從該進(jìn)程在內(nèi)存的固定頁(yè)面中選出一頁(yè)換出，然后再調(diào)入另一頁(yè)，保證分配給該進(jìn)程的內(nèi)存空間不變。物理塊的分配和置換策略 -1可變分配全局置換策略：系統(tǒng)為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，而OS本身也保持一個(gè)空閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)時(shí)，由系

52、統(tǒng)從空閑物理塊隊(duì)列中，取出一物理塊分配給該進(jìn)程，并將欲調(diào)入的缺頁(yè)裝入其中。當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，OS才能從內(nèi)存中選擇一頁(yè)調(diào)出，該頁(yè)可能是系統(tǒng)中任一進(jìn)程的頁(yè)。可變分配局部置換：根據(jù)進(jìn)程的類型或程序員的要求，為每個(gè)進(jìn)程分配一定數(shù)目的內(nèi)存空間；但當(dāng)某進(jìn)程發(fā)生缺頁(yè)時(shí)，只允許從該進(jìn)程在內(nèi)存的頁(yè)面中選出一頁(yè)換出，而不影響其它進(jìn)程的運(yùn)行。（3）物理塊分配算法 在采用固定分配策略時(shí)，可采用以下幾種物理塊分配方法：平均分配算法：將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。按比例分配算法：這是根據(jù)進(jìn)程的大小按比例分配物理塊。考慮優(yōu)先權(quán)的分配算法：該方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一

53、部分按比例分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。（4）調(diào)頁(yè)策略 (fetch policy) 調(diào)入頁(yè)面的時(shí)機(jī)為了將進(jìn)程運(yùn)行時(shí)所缺的頁(yè)面調(diào)入內(nèi)存，可采取預(yù)調(diào)頁(yè)策略或請(qǐng)求調(diào)頁(yè)策略兩種方法。預(yù)調(diào)頁(yè)策略是一種主動(dòng)的缺頁(yè)調(diào)入策略，即將那些預(yù)計(jì)在不久的將來(lái)會(huì)被訪問(wèn)的程序或數(shù)據(jù)所在的頁(yè)面，預(yù)先調(diào)入內(nèi)存。由于預(yù)測(cè)的準(zhǔn)確率不高（50%），所以這種策略主要用于進(jìn)程的首次調(diào)入。有的系統(tǒng)將預(yù)調(diào)頁(yè)策略用于請(qǐng)求調(diào)頁(yè)，例如在VAX/VMS操作系統(tǒng)中，采用了一種稱為群頁(yè)式的調(diào)頁(yè)策略，當(dāng)系統(tǒng)將進(jìn)程所請(qǐng)求的頁(yè)面調(diào)入內(nèi)存時(shí)，也同時(shí)將其相鄰的幾個(gè)頁(yè)面調(diào)入內(nèi)存。請(qǐng)求調(diào)頁(yè)策略是指當(dāng)進(jìn)程在運(yùn)行中

54、發(fā)生缺頁(yè)時(shí)，就立即提出請(qǐng)求，由系統(tǒng)將缺頁(yè)調(diào)入內(nèi)存。目前的虛擬存儲(chǔ)器中，大多采用此策略。但這種策略在調(diào)頁(yè)時(shí)須花費(fèi)較大的系統(tǒng)開(kāi)銷，如需頻繁啟動(dòng)磁盤I/O。 調(diào)頁(yè)策略-1從何處調(diào)入頁(yè)面在虛擬存儲(chǔ)系統(tǒng)中，外存（硬盤）常常被分成兩部分；文件區(qū)（用于存放文件）和對(duì)換區(qū)（用于存放對(duì)換頁(yè)面）。通常，對(duì)換區(qū)的磁盤I/O速度比文件區(qū)要高。例如在UNIX系統(tǒng)中，在文件系統(tǒng)，為了提高文件區(qū)存儲(chǔ)空間的利用率，系統(tǒng)采用“成組鏈接表”方式來(lái)組織空閑盤塊，并采用離散的分配方式；而在對(duì)換區(qū)，為了提高頁(yè)面換進(jìn)換出的速度，采用連續(xù)分配方式。每當(dāng)進(jìn)程發(fā)出缺頁(yè)請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁(yè)調(diào)入內(nèi)存呢？在UNIX系統(tǒng)中，對(duì)于從未運(yùn)行過(guò)的頁(yè)面

55、，都應(yīng)從硬盤文件區(qū)調(diào)入；對(duì)于曾經(jīng)運(yùn)行過(guò)而又被換出的頁(yè)面，可以從對(duì)換區(qū)調(diào)入；對(duì)于共享頁(yè)面，該頁(yè)面可能已由其它進(jìn)程調(diào)入內(nèi)存，此時(shí)就無(wú)須再?gòu)膶?duì)換區(qū)調(diào)入。 3頁(yè)面置換算法 （Page Replacement Algorithms） 在進(jìn)程運(yùn)行過(guò)程中，如果發(fā)生缺頁(yè)，此時(shí)內(nèi)存中又無(wú)空閑塊時(shí)，為了保證進(jìn)程能正常運(yùn)行，就必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送磁盤的對(duì)換區(qū)。但將哪個(gè)頁(yè)面調(diào)出，則須根據(jù)一定的頁(yè)面置換算法來(lái)確定。頁(yè)面置換算法的性能指標(biāo)：缺頁(yè)率（ page fault rate ）表示“缺頁(yè)次數(shù) / 內(nèi)存訪問(wèn)次數(shù)” (比率)或“缺頁(yè)的平均時(shí)間間隔的倒數(shù)”。置換算法的好壞將直接影響系統(tǒng)的性能，不適當(dāng)?shù)乃惴赡?/p>

56、會(huì)導(dǎo)致進(jìn)程發(fā)生“抖動(dòng)”（Thrashing)。即剛被換出的頁(yè)很快又被訪問(wèn)，需重新調(diào)入，導(dǎo)致系統(tǒng)頻繁地更換頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行中把大部分時(shí)間花費(fèi)在完成頁(yè)面置換的工作上，我們稱該進(jìn)程發(fā)生了“抖動(dòng)”。 從理論上講，應(yīng)將那些以后不再被訪問(wèn)的頁(yè)面換出，或把那些在較長(zhǎng)時(shí)間內(nèi)不會(huì)再被訪問(wèn)的頁(yè)面換出。下面介紹幾種常用的置換算法。 （1）最佳（Optimal、OPT）置換算法它是一種理想化的算法，性能最好，但在實(shí)際上難于實(shí)現(xiàn)。即選擇那些永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面置換出去。但是要確定哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，目前來(lái)說(shuō)是很難估計(jì)的，所以該算法通常用來(lái)評(píng)價(jià)其它算法。例：假定系統(tǒng)為

57、某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁(yè)面號(hào)引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如下圖所示，進(jìn)程運(yùn)行時(shí)先將7，0，1三個(gè)頁(yè)面裝入內(nèi)存。當(dāng)進(jìn)程訪問(wèn)頁(yè)面2時(shí)，產(chǎn)生缺頁(yè)中斷，此時(shí)OS根據(jù)最佳置換算法，頁(yè)面7將在第18次才被訪問(wèn)，是三頁(yè)中將最久不被訪問(wèn)的頁(yè)面，所以被淘汰。接著訪問(wèn)頁(yè)面0時(shí)，發(fā)現(xiàn)已在內(nèi)存中，而不會(huì)產(chǎn)生缺頁(yè)中斷，以此類推。從圖可以看出，采用最佳置換算法，只發(fā)生了6次頁(yè)面置換，9次缺頁(yè)中斷。最佳（OPT）置換算法-1(2)先進(jìn)先出（FIFO）置換算法實(shí)用的置換算法關(guān)鍵是如何以過(guò)去頁(yè)面走向來(lái)預(yù)測(cè)將來(lái)的頁(yè)面走向，以達(dá)到最佳置換算法。FIFO算法

58、認(rèn)為最先進(jìn)入內(nèi)存的頁(yè)面，其不再使用的可能性比最近調(diào)入的頁(yè)面要大。所以該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只須把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)循環(huán)替換指針即可。它是一種最直觀的算法，但它性能最差，有Belady異?，F(xiàn)象：例如對(duì)頁(yè)面訪問(wèn)序列1 2 3 4 1 2 5 1 2 3 4 5 ，當(dāng)分配的物理塊從3塊增加到4塊，缺頁(yè)次數(shù)反而增加。 先進(jìn)先出（FIFO）置換算法-1先進(jìn)先出（FIFO）置換算法-2Beladys 奇異Belady現(xiàn)象：采用FIFO算法時(shí)，如果對(duì)一個(gè)進(jìn)程未分配它所要求的全部頁(yè)面，有時(shí)就會(huì)出現(xiàn)

59、分配的頁(yè)面數(shù)增多，缺頁(yè)率反而提高的異常現(xiàn)象。對(duì)頁(yè)面訪問(wèn)序列A B C D A B E A B C D E ，物理塊從3塊增加到4塊，缺頁(yè)次數(shù)增加。 FIFO Illustrating Beladys Anamoly（3）最近最久未使用置換算法 LRU（Least Recently Used）該算法是選擇最近最久未使用的頁(yè)面予以淘汰，這是局部性原理的合理近似，性能接近最佳算法。但由于需要記錄頁(yè)面使用時(shí)間的先后關(guān)系，硬件開(kāi)銷太大。系統(tǒng)在每個(gè)頁(yè)面設(shè)置一個(gè)訪問(wèn)字段，用以記錄這個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間T，當(dāng)要淘汰一個(gè)頁(yè)面時(shí)，選擇T最大的頁(yè)面。但在實(shí)現(xiàn)時(shí)需要硬件的支持（寄存器或棧）。硬件機(jī)構(gòu)如：

60、一個(gè)特殊的棧：把被訪問(wèn)的頁(yè)面移到棧頂，于是棧底的是最久未使用頁(yè)面。每個(gè)頁(yè)面設(shè)立移位寄存器：被訪問(wèn)時(shí)左邊最高位置1，定期右移并且最高位補(bǔ)0，于是寄存器數(shù)值最小的是最久未使用頁(yè)面。最近最久未使用置換算法-1最近最久未使用置換算法-2利用LRU置換算法對(duì)上例進(jìn)行頁(yè)面置換的結(jié)果如表32，表中用一個(gè)特殊棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)號(hào)，棧中物理塊的頁(yè)號(hào)按訪問(wèn)先后次序排序，它是通過(guò)硬件二個(gè)棧的彈出和壓入來(lái)實(shí)現(xiàn)特殊棧的頁(yè)號(hào)變化。當(dāng)進(jìn)程訪問(wèn)頁(yè)面2在內(nèi)存沒(méi)有時(shí)，頁(yè)號(hào)2從上面壓入，從下面擠出頁(yè)號(hào)7。接下進(jìn)程訪問(wèn)頁(yè)面0在內(nèi)存有時(shí)，直接在內(nèi)存訪問(wèn)，物理塊中頁(yè)號(hào)0提到最上面，其它的頁(yè)面2、1仍按原次序排列?？梢钥闯?，如