第七章 實(shí)存管理技術(shù)

第七章實(shí)存管理技術(shù)存儲(chǔ)器是計(jì)算機(jī)最重要的資源之一，內(nèi)存管理一直是操作系統(tǒng)最主要的功能之一。內(nèi)存容量一直是計(jì)算機(jī)硬件資源中最緊張的資源，特別在多道程序設(shè)計(jì)技術(shù)條件下，一方面要充分利用內(nèi)存容量，另一方面必須保證多個(gè)程序在內(nèi)存中互不干擾即保證內(nèi)存安全。存儲(chǔ)器管理技術(shù)分實(shí)存管理和虛存管理?；镜拇鎯?chǔ)管理方法是分區(qū)法、覆蓋技術(shù)、交換技術(shù)、分頁(yè)法、分段法、段頁(yè)法。第七章實(shí)存管理技術(shù)7.1存儲(chǔ)管理的基本概念7.2連續(xù)分配存儲(chǔ)管理方式7.3離散分配存儲(chǔ)管理方式7.4交換技術(shù)7.5覆蓋技術(shù)7.1存儲(chǔ)管理的基本概念7.1.1存儲(chǔ)管理要解決的問(wèn)題7.1.2存儲(chǔ)管理的分類(lèi)7.1.3地址映射（重定位）7.1.1存儲(chǔ)管理要解決的問(wèn)題早期計(jì)算機(jī)系統(tǒng)中，內(nèi)存是最緊張的資源之一。為了在小內(nèi)存中運(yùn)行大程序，人們先發(fā)明了覆蓋技術(shù)。當(dāng)發(fā)明虛存管理技術(shù)后，才真正解決了在小內(nèi)存中運(yùn)行大程序的問(wèn)題。為了有效管理計(jì)算機(jī)內(nèi)存資源，操作系統(tǒng)的存儲(chǔ)管理要具備以下功能：1.內(nèi)存空間分配與回收根據(jù)某種分配方式，遵循某種分配算法，為進(jìn)程分配內(nèi)存，當(dāng)進(jìn)程結(jié)束時(shí)再回收內(nèi)存。2.地址映射設(shè)計(jì)地址變換機(jī)構(gòu)，靜態(tài)和動(dòng)態(tài)地址變換的方法。3.內(nèi)存保護(hù)怎樣讓內(nèi)存中各個(gè)進(jìn)程互不干擾，怎樣保證內(nèi)存中程序、數(shù)據(jù)的安全。4.內(nèi)存擴(kuò)充怎樣從邏輯上擴(kuò)充內(nèi)存。這屬于虛存管理的范疇。7.1.2存儲(chǔ)管理的分類(lèi)從分配方式上按進(jìn)程在內(nèi)存中是否連續(xù)，可以把存儲(chǔ)管理分成連續(xù)分配方式和離散分配方式兩類(lèi)。1.連續(xù)分配方式必須為進(jìn)程在內(nèi)存分配一片連續(xù)的空間。2.離散分配方式允許將一個(gè)進(jìn)程分散地裝入內(nèi)存的多個(gè)不相鄰的區(qū)域。從進(jìn)程是整體裝入還是局部裝入內(nèi)存可以把存儲(chǔ)管理分成實(shí)存管理和虛存管理兩類(lèi)。1.實(shí)存管理必須把進(jìn)程完整地裝入內(nèi)存。2.虛存管理允許將一個(gè)進(jìn)程局部地裝入內(nèi)存。7.1.3地址映射（重定位）1.地址空間和存儲(chǔ)空間源程序經(jīng)過(guò)編譯或匯編產(chǎn)生目標(biāo)文件，目標(biāo)文件經(jīng)過(guò)連接和裝配產(chǎn)生可以執(zhí)行的文件。在連接裝配時(shí)，語(yǔ)言系統(tǒng)并不知道將來(lái)這個(gè)執(zhí)行文件會(huì)放在內(nèi)存的哪個(gè)位置，為了方便地將執(zhí)行文件裝入內(nèi)存，把執(zhí)行文件中第一條指令的地址設(shè)為0。其他指令的地址都以它做參照。執(zhí)行文件中指令的地址稱(chēng)相對(duì)地址或邏輯地址。而相對(duì)地址的集合稱(chēng)相對(duì)地址空間，簡(jiǎn)稱(chēng)地址空間。內(nèi)存每個(gè)字節(jié)都有一個(gè)地址，這是物理地址是真實(shí)的地址，也稱(chēng)絕對(duì)地址。絕對(duì)地址空間也叫物理地址空間，簡(jiǎn)稱(chēng)存儲(chǔ)空間。一個(gè)程序的邏輯地址和它在內(nèi)存中的地址是不同的，顯然必須先將邏輯地址變成物理地址后程序才能正確運(yùn)行。2.靜態(tài)重定位

靜態(tài)重定位是由專(zhuān)門(mén)設(shè)計(jì)的重定位裝配程序來(lái)完成的，是在目標(biāo)程序裝入到內(nèi)存區(qū)時(shí)由裝配程序來(lái)完成地址轉(zhuǎn)換。優(yōu)點(diǎn)：無(wú)需增加地址轉(zhuǎn)換機(jī)構(gòu)

缺點(diǎn)：不能實(shí)現(xiàn)重新分配內(nèi)存

用戶(hù)必須事先確定所需的存儲(chǔ)量

每個(gè)用戶(hù)進(jìn)程需各自使用一個(gè)獨(dú)立的副本。

Load#1,450…………35000100450……Load#1,2450……3500………………2100操作系統(tǒng)20002450邏輯地址物理地址圖7-2靜態(tài)地址映射3.動(dòng)態(tài)重定位動(dòng)態(tài)重定位是在目標(biāo)程序執(zhí)行過(guò)程中，在CPU訪(fǎng)問(wèn)內(nèi)存之前，由硬件地址映射機(jī)構(gòu)來(lái)完成將要訪(fǎng)問(wèn)的指令或數(shù)據(jù)的邏輯地址向內(nèi)存的物理地址的轉(zhuǎn)換。優(yōu)點(diǎn)：內(nèi)存的使用更加靈活有效；幾個(gè)作業(yè)共享一程序段的單個(gè)副本比較容易；無(wú)需用戶(hù)干預(yù)，由系統(tǒng)來(lái)負(fù)責(zé)全部的存儲(chǔ)管理。缺點(diǎn)：需附加硬件支持；實(shí)現(xiàn)存儲(chǔ)器管理的軟件比較復(fù)雜。Load#1,450…………35000100450……Load#1,450……3500………………2100操作系統(tǒng)20002450邏輯地址物理地址圖7-3動(dòng)態(tài)地址映射基址寄存器2000＋7.2連續(xù)分配方式7.2.1單一連續(xù)分配方式7.2.2固定分區(qū)內(nèi)存管理方式7.2.3可變分區(qū)內(nèi)存管理方式7.2.1單一連續(xù)分配方式在單任務(wù)的操作系統(tǒng)條件下，讓用戶(hù)占用計(jì)算機(jī)所有資源，內(nèi)存管理采用單一連續(xù)分配方式。內(nèi)存被分成兩個(gè)區(qū)1.系統(tǒng)區(qū)供操作系統(tǒng)使用2.用戶(hù)區(qū)供用戶(hù)放一個(gè)程序操作系統(tǒng)區(qū)用戶(hù)區(qū)……7.2.2固定分區(qū)內(nèi)存管理方式分區(qū)管理是滿(mǎn)足多道程序設(shè)計(jì)的一種最早采用的存儲(chǔ)管理方法。其基本原理是給每一個(gè)進(jìn)程在內(nèi)存中劃分一塊可用的存儲(chǔ)區(qū)，連續(xù)存儲(chǔ)各進(jìn)程的程序和數(shù)據(jù)，使各進(jìn)程能并發(fā)進(jìn)行。

內(nèi)存分配算法：（1）首次適應(yīng)法空閑分區(qū)按物理地址為升序排列，在內(nèi)存現(xiàn)有空閑分區(qū)中，找到第一個(gè)可用的分區(qū)就分配。（2）最佳適應(yīng)法在內(nèi)存現(xiàn)有的空閑分區(qū)中，找一個(gè)浪費(fèi)最小的分區(qū)分配。

（3）最壞適應(yīng)法在現(xiàn)有內(nèi)存空閑區(qū)中，找一個(gè)浪費(fèi)最大的分區(qū)分配。（4）唯一最佳分配法作業(yè)按長(zhǎng)度分類(lèi)排隊(duì)，一個(gè)分區(qū)對(duì)應(yīng)一個(gè)隊(duì)，使這個(gè)隊(duì)中每個(gè)作業(yè)的長(zhǎng)度小于等于分區(qū)的長(zhǎng)度，使分配后內(nèi)存浪費(fèi)最小。從整體上看，這個(gè)算法也不是最佳的。

固定分區(qū)法

固定分區(qū)法就是把內(nèi)存固定劃分為若干個(gè)不等的區(qū)域，劃分的原則由系統(tǒng)決定。在整個(gè)執(zhí)行過(guò)程中保持分區(qū)長(zhǎng)度和分區(qū)個(gè)數(shù)不變。操作系統(tǒng)為每個(gè)用戶(hù)作業(yè)分配一個(gè)分區(qū)。

內(nèi)存管理

:分區(qū)號(hào)起始地址長(zhǎng)度狀態(tài)進(jìn)程名管理數(shù)據(jù)結(jié)構(gòu)：設(shè)置內(nèi)存分配表內(nèi)存分配：每個(gè)區(qū)分配一個(gè)進(jìn)程內(nèi)存回收：簡(jiǎn)單缺點(diǎn)：內(nèi)存利用率不高如何記錄系統(tǒng)的狀況呢？分配策略

分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)0100K200K400K700K1300K多個(gè)輸入隊(duì)列分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)0100K200K400K700K1300K單個(gè)輸入隊(duì)列（a）唯一最佳分配算法（b）其他分配算法固定分區(qū)

操作系統(tǒng)建立一個(gè)內(nèi)存分區(qū)管理表（分區(qū)號(hào)、分區(qū)長(zhǎng)度、分區(qū)首址和分區(qū)狀態(tài)），所有分區(qū)按物理地址升序排列，每個(gè)分區(qū)占表中一行。操作系統(tǒng)為作業(yè)分配內(nèi)存時(shí)，按（1）、（2）、（4）中某個(gè)分配算法查表，有合適的分區(qū)就分配，否則就不分配。固定分區(qū)法管理方式雖然簡(jiǎn)單，但是存在大量?jī)?nèi)碎片（在分區(qū)內(nèi)存在空余的空間，這就稱(chēng)為內(nèi)碎片），內(nèi)存利用率不高。

分區(qū)號(hào)分區(qū)長(zhǎng)度分區(qū)首址分區(qū)狀態(tài)

120KB20KB已分配

232KB40KB已分配

364KB72KB已分配

4128KB138KB未分配內(nèi)存分區(qū)管理表地址映射對(duì)于固定分區(qū)，可以采用靜態(tài)地址映射也可以采用動(dòng)態(tài)地址映射。內(nèi)存保護(hù)可以采用界限寄存器法，用兩個(gè)寄存器分別放用戶(hù)區(qū)的首地址和用戶(hù)的長(zhǎng)度。用戶(hù)程序訪(fǎng)問(wèn)內(nèi)存的地址必須在這個(gè)范圍內(nèi)，否則就是地址越界。7.2.3可變分區(qū)內(nèi)存管理方式

可變分區(qū)法

動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為它分配連續(xù)的內(nèi)存空間，各個(gè)分區(qū)是在相應(yīng)進(jìn)程裝入內(nèi)存時(shí)建立的，其大小恰好等于進(jìn)程的大小。

為了實(shí)現(xiàn)內(nèi)存分配，系統(tǒng)中設(shè)置了相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄內(nèi)存的使用情況，常用的數(shù)據(jù)結(jié)構(gòu)形式有空閑分區(qū)鏈。內(nèi)存分配數(shù)據(jù)結(jié)構(gòu)，可以用空閑區(qū)鏈表，節(jié)點(diǎn)中包含空閑區(qū)的首址、長(zhǎng)度、鏈指針。在進(jìn)程PCB中包含進(jìn)程的內(nèi)存首址、長(zhǎng)度、訪(fǎng)問(wèn)權(quán)限等項(xiàng)目。分配算法：首次適應(yīng)法、最佳適應(yīng)法、最壞適應(yīng)法。分配時(shí)，操作系統(tǒng)填寫(xiě)PCB中進(jìn)程的內(nèi)存首址、長(zhǎng)度、訪(fǎng)問(wèn)權(quán)限。內(nèi)存回收為了最大限度的利用內(nèi)存資源，就要不斷將分散的小碎片拼接成一個(gè)大的空閑區(qū)，這里有個(gè)拼接的時(shí)機(jī)問(wèn)題，可以在分配時(shí)拼接，也可以在回收時(shí)拼接。拼接意味著要求進(jìn)程能在內(nèi)存中移動(dòng)，例如現(xiàn)在進(jìn)程的首址是a，將它向地址增大方向移動(dòng)b個(gè)字節(jié)，進(jìn)程的首址變成a+b。進(jìn)程長(zhǎng)度不變。地址映射為了實(shí)現(xiàn)內(nèi)存拼接，必須用動(dòng)態(tài)地址映射CPU提供基址寄存器、限長(zhǎng)寄存器、地址運(yùn)算器。進(jìn)程切換時(shí)，操作系統(tǒng)把PCB中的內(nèi)存信息(進(jìn)程的首址、長(zhǎng)度)寫(xiě)入基址寄存器和限長(zhǎng)寄存器同時(shí)將進(jìn)程PCB中的現(xiàn)場(chǎng)信息寫(xiě)入CPU的寄存器集合。動(dòng)態(tài)重定位的實(shí)現(xiàn)過(guò)程內(nèi)存保護(hù)利用基址寄存器和限長(zhǎng)寄存器，一個(gè)進(jìn)程只能訪(fǎng)問(wèn)自己的內(nèi)存區(qū)，只有操作系統(tǒng)進(jìn)程可以訪(fǎng)問(wèn)全部的內(nèi)存區(qū)。除了地址界限保護(hù)外，為了進(jìn)程間共享數(shù)據(jù)還需要訪(fǎng)問(wèn)權(quán)限保護(hù)，進(jìn)程可以給另一個(gè)進(jìn)程賦予訪(fǎng)問(wèn)權(quán)限，允許在訪(fǎng)問(wèn)權(quán)限范圍內(nèi)訪(fǎng)問(wèn)。動(dòng)態(tài)分區(qū)舉例外碎片進(jìn)程外的內(nèi)存空間碎片化能用壓縮方法解決OS移動(dòng)進(jìn)程使進(jìn)程和進(jìn)程相連。消耗CPU時(shí)間OS(8M)P1(20M)P2(14M)P3(18M)Empty(56M)Empty(4M)P4(8M)Empty(6M)P2(14M)Empty(6M)RefertoFigure7.4

例：現(xiàn)在有三個(gè)作業(yè)A(20KB)，B(80KB)，C(50KB)，內(nèi)存有兩個(gè)空閑區(qū)F1(110KB)，F(xiàn)2(60KB)。首次適應(yīng)法（設(shè)F1的首址<F2的首址）

A（占20KB）

B（占80KB）

C（占50KB）F1(100KB,10KB

)F2(50KB,10KB

)

首次適應(yīng)法（設(shè)F1的首址>F2的首址）

A（20KB）

B（80KB）最壞適應(yīng)法

A（20KB）

B（80KB）

C（50KB）F2（20KB，40KB）F1（80KB，30KB）F1(100KB,10KB

)F2(50KB,10KB

)

最佳適應(yīng)法

A（20KB）

B（80KB）可變分區(qū)分配采用最佳適應(yīng)算法，結(jié)果不一定是最佳的；采用最壞程序算法，結(jié)果不一定是最差的。F2(20KB,40KB

)F1(80KB,30KB

)伙伴系統(tǒng)全部可用空間被分成一個(gè)長(zhǎng)度是2U的塊如請(qǐng)求分配長(zhǎng)度s符合2U-1<s<=2U全部空間分配給它否則塊被分成兩個(gè)相等的伙伴。這個(gè)過(guò)程一直持續(xù)直到找到符合長(zhǎng)度<=s的伙伴伙伴系統(tǒng)舉例伙伴系統(tǒng)樹(shù)型表示7.3離散分配存儲(chǔ)管理方式固定分區(qū)和可變分區(qū)都是連續(xù)分配內(nèi)存的技術(shù)，把一個(gè)進(jìn)程裝入一個(gè)分區(qū)，使用這種方法會(huì)造成許多碎片，降低了內(nèi)存的利用率。產(chǎn)生碎片的根本原因就是要求把一個(gè)進(jìn)程連續(xù)地放在一個(gè)內(nèi)存區(qū)。雖然可變分區(qū)技術(shù)使用內(nèi)存拼接技術(shù)把分散的空閑分區(qū)集中成較大的分區(qū)，但要增加系統(tǒng)的開(kāi)銷(xiāo)。人們考慮能否化整為零提高內(nèi)存的利用率。7.3.1分頁(yè)式存儲(chǔ)管理方式7.3.2分段式存儲(chǔ)管理方式7.3.3段頁(yè)式存儲(chǔ)管理方式7.3.1分頁(yè)式存儲(chǔ)管理方式可變分區(qū)方式除了產(chǎn)生大量的外碎片，還有一個(gè)缺點(diǎn)，就是進(jìn)程動(dòng)態(tài)增長(zhǎng)不方便。分頁(yè)管理是解決碎片問(wèn)題的一種有效辦法，它允許進(jìn)程在內(nèi)存空間里是不連續(xù)的；還便于進(jìn)程動(dòng)態(tài)增長(zhǎng)。分頁(yè)管理技術(shù)原理（1）操作系統(tǒng)按一個(gè)2的整數(shù)次冪為長(zhǎng)度，把內(nèi)存用戶(hù)區(qū)分成若干存儲(chǔ)區(qū)，稱(chēng)為塊，每個(gè)塊的容量都是相同的，每個(gè)塊按物理地址值由小到大順序從0開(kāi)始編號(hào)，稱(chēng)為塊號(hào)。000000000000000001000000010000000…000000111000001000000001001000001…000001111………111111000111111001111111010111111…111111111

塊號(hào)塊內(nèi)地址#0#1#63假設(shè)每塊的容量是23個(gè)字節(jié)物理地址被分成兩部分，高位部分稱(chēng)為塊號(hào)，低位部分稱(chēng)為塊內(nèi)地址。假設(shè)內(nèi)存共有64個(gè)塊，每塊有8個(gè)字節(jié)。塊號(hào)是從物理地址中截出來(lái)，是物理地址固有的。物理地址=(塊號(hào)，塊內(nèi)地址)=(B,d)內(nèi)存塊的起始地址等于內(nèi)存塊號(hào)乘以塊長(zhǎng)。

物理地址（2）用戶(hù)進(jìn)程的邏輯空間也按內(nèi)存塊的大小分頁(yè)，每頁(yè)也按邏輯地址由小到大編號(hào)稱(chēng)為頁(yè)號(hào)。假設(shè)一個(gè)進(jìn)程有61個(gè)字節(jié)，以每頁(yè)8個(gè)字節(jié)分頁(yè)，分成8頁(yè)，如圖所示：000000000000000001000000010000000…000000111000001000000001001000001…000001111………000111000000111001000111010000111101

頁(yè)號(hào)頁(yè)內(nèi)地址#0#1#7每頁(yè)的容量是23邏輯地址被分成兩部分，高位部分稱(chēng)為頁(yè)號(hào)，低位部分稱(chēng)為頁(yè)內(nèi)地址。邏輯地址=(p,d)程序共有8頁(yè)，每頁(yè)有8個(gè)字節(jié)。頁(yè)號(hào)是從邏輯地址中截出來(lái)的。為程序的每一頁(yè)分配一個(gè)內(nèi)存塊，這就得出程序任何一頁(yè)裝入內(nèi)存后，它的頁(yè)內(nèi)地址就等于塊內(nèi)地址。

邏輯地址………

物理地址(塊號(hào)，塊內(nèi)地址)用(B，d)表示，邏輯地址(頁(yè)號(hào)，頁(yè)內(nèi)地址)用(p，d)表示，設(shè)邏輯地址是A，頁(yè)長(zhǎng)是L，從數(shù)學(xué)角度描述：

p=AdivLd=AmodL

因?yàn)長(zhǎng)=2m，所以p是A邏輯右移m位后的結(jié)果，d是A邏輯右移m位時(shí)，移出去的m位值。用匯編語(yǔ)言整數(shù)除法指令很容易描述，以A作為被除數(shù)，以L(fǎng)作為除數(shù)，商就是頁(yè)號(hào)，余數(shù)就是頁(yè)內(nèi)地址。其實(shí)不用對(duì)邏輯地址移位，也不用對(duì)邏輯地址做除法，在工程上直接根據(jù)頁(yè)長(zhǎng)的位數(shù)，將邏輯地址一分為二，高位部分是頁(yè)號(hào)，低位部分是頁(yè)內(nèi)地址（頁(yè)內(nèi)偏移）。

內(nèi)存空間分配與回收

頁(yè)式管理以塊為單位給進(jìn)程分配內(nèi)存，操作系統(tǒng)必須隨時(shí)掌握內(nèi)存塊的狀態(tài)（已分配、未分配、當(dāng)前空閑塊的總數(shù)）。下面建立內(nèi)存空間分配與回收的數(shù)學(xué)模型：首先看數(shù)據(jù)的性質(zhì)，內(nèi)存塊具有哪些屬性？ 內(nèi)存塊的起始地址、內(nèi)存塊的狀態(tài)（已分配或空閑），內(nèi)存塊的總數(shù)是固定的。這個(gè)模型要能反映內(nèi)存塊的地址和狀態(tài)信息。并且內(nèi)存塊的總數(shù)是不變的。從數(shù)據(jù)結(jié)構(gòu)和程序語(yǔ)言角度講，一個(gè)數(shù)組元素具備兩個(gè)特性，能否用一個(gè)數(shù)組元素代表一個(gè)內(nèi)存塊？用數(shù)組元素的值代表內(nèi)存塊的狀態(tài)，元素的下標(biāo)值代表內(nèi)存塊的地址。因?yàn)橐粋€(gè)內(nèi)存塊的狀態(tài)不是已分配就是未分配，可以用一個(gè)二進(jìn)制位表示，0表示未分配，1表示已分配。進(jìn)程和頁(yè)架A.0A.1A.2A.3B.0B.1B.2C.0C.1C.2C.3D.0D.1D.2D.3D.4

假定系統(tǒng)有m*n個(gè)內(nèi)存塊(m行n列)，用m*n的位圖表示：

0

1

2

3

4

5...3031323334353637...6263646566676869...949596979899100101…126127128129130131132133…158159160161162163164165…190191192193194195196197…222223224225226227228229…254255

012345...3031

01234567

在程序語(yǔ)言中用二維數(shù)組表示這個(gè)位圖，每個(gè)元素的長(zhǎng)度是一個(gè)二進(jìn)制位，用一個(gè)數(shù)組元素表示一個(gè)內(nèi)存塊。 數(shù)組元素值表示對(duì)應(yīng)的內(nèi)存塊的狀態(tài)（空閑或占用）數(shù)組元素的下標(biāo)映射內(nèi)存塊的起始地址。 從分頁(yè)原理可知，內(nèi)存塊的起始地址等于內(nèi)存塊號(hào)乘以頁(yè)長(zhǎng)，在此頁(yè)長(zhǎng)是個(gè)常數(shù)，用元素的下標(biāo)值映射內(nèi)存塊號(hào)。塊號(hào)左移就可獲得塊的起始地址。假設(shè)i和j分別代表數(shù)組元素的行、列下標(biāo)。

B=i*n+j例：n=32,m=8,i=3,j=5B=i*n+j=3*32+5=101分配時(shí)遍歷數(shù)組，找到元素值是0的元素，再根據(jù)該元素的下標(biāo)計(jì)算內(nèi)存塊塊號(hào)B。分配后，將該元素值更改為1。

分配原則：設(shè)系統(tǒng)有m個(gè)空閑內(nèi)存塊，進(jìn)程申請(qǐng)n塊，如m>=n就分配，即要求進(jìn)程一次性的裝入內(nèi)存，不論這些塊在內(nèi)存中是否連續(xù)。一個(gè)進(jìn)程裝入內(nèi)存后，可以離散分布在各個(gè)內(nèi)存塊中，進(jìn)程不需要操作系統(tǒng)為它分配一個(gè)連續(xù)的內(nèi)存區(qū)。這正是分頁(yè)管理與分區(qū)管理的根本區(qū)別。

設(shè)k是系統(tǒng)當(dāng)前的空閑塊數(shù)，n是進(jìn)程的頁(yè)數(shù)，分配算法可以用N-S流程圖表示為：TTFF

k>=n

nx;q=&a[0][0];B=0;當(dāng)x>0*q==0(未分配)分配*q=1，填寫(xiě)頁(yè)表記錄塊號(hào)B,x--,k--修改q++;B++不分配

進(jìn)程結(jié)束后，要回收進(jìn)程占用的所有內(nèi)存塊，這時(shí)要根據(jù)內(nèi)存塊號(hào)計(jì)算它在位圖中的位置（即行下標(biāo)和列下標(biāo)）

i=Bdivnj=Bmodn

例：B=197，n=32i=Bdivn=197div32=6j=Bmodn=197mod32=5計(jì)算出內(nèi)存塊對(duì)應(yīng)的行和列下標(biāo)后，就可以訪(fǎng)問(wèn)數(shù)組，把該元素的值修改為0，系統(tǒng)空閑內(nèi)存塊數(shù)自增1，這個(gè)內(nèi)存塊就被系統(tǒng)收回；進(jìn)程如占有n塊，就把這個(gè)過(guò)程重復(fù)n次。地址映射地址映射是將邏輯地址轉(zhuǎn)換成真實(shí)的物理地址。由于內(nèi)存的一塊恰好裝入一頁(yè)，頁(yè)內(nèi)地址與塊內(nèi)地址一一對(duì)應(yīng)。邏輯地址是（p,d)物理地址是（B,d)現(xiàn)在的問(wèn)題是已知p，求B。因?yàn)檫M(jìn)程的一頁(yè)可以裝入內(nèi)存的任何一塊中，p和B之間不存

在一種可計(jì)算的線(xiàn)性函數(shù)。但是存在每頁(yè)對(duì)應(yīng)一個(gè)內(nèi)存塊的關(guān)系。一個(gè)顯而易見(jiàn)的方法是建立一張表(頁(yè)表)，表中每行代表一頁(yè)，每行的序號(hào)代表頁(yè)號(hào)，通過(guò)這張表描述頁(yè)號(hào)與塊號(hào)的關(guān)系。地址映射的工作是用頁(yè)號(hào)p查表，找到對(duì)應(yīng)的塊號(hào)B，再用B與頁(yè)內(nèi)地址d計(jì)算物理地址。為了提高地址映射的效率，需要硬件的支持。在CPU中設(shè)立頁(yè)表控制寄存器（其中包含頁(yè)表長(zhǎng)度L和頁(yè)表起始地址a）。頁(yè)表每個(gè)進(jìn)程都有自己的一張頁(yè)表，頁(yè)表的起始地址和長(zhǎng)度記錄在PCB中。當(dāng)進(jìn)程由就緒態(tài)變成執(zhí)行態(tài)時(shí)，由操作系統(tǒng)根據(jù)進(jìn)程的PCB將進(jìn)程頁(yè)表的起始地址和頁(yè)表長(zhǎng)度填入CPU頁(yè)表控制寄存器。pdLap<L

BBdp+ap+a越界中斷nya邏輯地址頁(yè)表寄存器頁(yè)表物理地址由于頁(yè)表是駐留在內(nèi)存的某個(gè)固定區(qū)域中，而取數(shù)據(jù)或指令又必須經(jīng)過(guò)頁(yè)表變換才能得到實(shí)際物理地址。因此，取一個(gè)數(shù)據(jù)或指令至少要訪(fǎng)問(wèn)內(nèi)存兩次以上。一次訪(fǎng)問(wèn)頁(yè)表以確定所取數(shù)據(jù)或指令的物理地址，另一次是根據(jù)地址取數(shù)據(jù)或指令。這比通常執(zhí)行指令的速度慢了一倍。

提高查找速度一個(gè)最快的辦法就是把頁(yè)表放在寄存器中而不是內(nèi)存中，但由于寄存器價(jià)格太貴，這樣做是不可取的。另一種辦法是在地址變換機(jī)構(gòu)中加入一個(gè)高速聯(lián)想存儲(chǔ)器，構(gòu)成一張快表。在快表中，存入那些當(dāng)前執(zhí)行進(jìn)程中最常用的頁(yè)號(hào)與所對(duì)應(yīng)的塊號(hào)，從而以提高查找速度。(2)快表的地址轉(zhuǎn)換由于在某段時(shí)間內(nèi)執(zhí)行程序時(shí)，是在一個(gè)范圍內(nèi)逐條順序執(zhí)行指令；數(shù)組一類(lèi)數(shù)據(jù)結(jié)構(gòu)在內(nèi)存占據(jù)一片連續(xù)存儲(chǔ)空間，訪(fǎng)問(wèn)數(shù)組時(shí)也是在數(shù)組范圍內(nèi)訪(fǎng)問(wèn)，所以快表的命中率可達(dá)到80%到90%。CPU存取一個(gè)數(shù)據(jù)的平均時(shí)間為：T=命中率×（訪(fǎng)內(nèi)時(shí)間＋訪(fǎng)cache時(shí)間）＋非命中率×（2×訪(fǎng)內(nèi)時(shí)間＋訪(fǎng)cache時(shí)間）例：訪(fǎng)內(nèi)時(shí)間是100ns，訪(fǎng)cache時(shí)間是20ns，訪(fǎng)cache命中率是85%計(jì)算CPU存取一個(gè)數(shù)據(jù)的平均時(shí)間。T=0.85*(100+20)+0.15*(200+20)=135ns

頁(yè)的共享和保護(hù)

分頁(yè)存儲(chǔ)管理技術(shù)使每個(gè)進(jìn)程分別存儲(chǔ)在內(nèi)存的不連續(xù)的存儲(chǔ)塊中，這種靈活性允許兩個(gè)和多個(gè)進(jìn)程共享程序庫(kù)中的例程或公共數(shù)據(jù)段的同一副本，共享的方法是使這些相關(guān)進(jìn)程的邏輯空間中的頁(yè)指向相同的內(nèi)存塊。 共享頁(yè)面是有條件的，故實(shí)現(xiàn)信息共享的前提是提供附加的保護(hù)措施，對(duì)共享信息加以保護(hù)。

頁(yè)共享與保護(hù)進(jìn)程1頁(yè)表1ed1ed2…ed40data1data10…ed1ed2…ed40data1data10…2122…606170…2122…607180…進(jìn)程2頁(yè)表2ed1ed2…ed40data1data10…主存data1data10……212260617007180分頁(yè)系統(tǒng)中共享editor示意圖7.3.2分段式存儲(chǔ)管理方式其實(shí)程序在邏輯上是分成不同段的，每個(gè)段具有其獨(dú)特的性質(zhì)，例如一個(gè)代碼段是只執(zhí)行的，一個(gè)數(shù)據(jù)段只允許讀，另一個(gè)數(shù)據(jù)段可允許讀和寫(xiě)。顯然，如以段作為內(nèi)存分配的最小單位，這便于對(duì)各個(gè)段實(shí)施控制和保護(hù)。這些段的長(zhǎng)度可以不同，段和段在內(nèi)存中也可以不連續(xù)。每個(gè)段在內(nèi)存占據(jù)一片連續(xù)的空間。分段基本原理內(nèi)存分配與回收分段管理中，內(nèi)存的最小分配對(duì)象是段，特別地是為每個(gè)段分配各自的連續(xù)空間，在內(nèi)存里段和段之間可以不連續(xù)。分配算法與可變分區(qū)的分配算法相似，可以采用最佳適應(yīng)法、最壞適應(yīng)法和首次適應(yīng)法等分配算法。顯然仍然要解決外碎片的問(wèn)題。分段基本原理內(nèi)存分配的數(shù)據(jù)結(jié)構(gòu)要采用空閑區(qū)鏈表，為了提高內(nèi)存的利用率，必須實(shí)施內(nèi)存碎片拼接的方案，內(nèi)存碎片拼接的時(shí)機(jī)可以在分配時(shí)刻或回收時(shí)刻?？梢岳斫夥侄喂芾砑夹g(shù)繼承了可變分區(qū)管理技術(shù)，但管理上要比可變分區(qū)更復(fù)雜。例如可變分區(qū)管理以進(jìn)程為內(nèi)存分配的最小對(duì)象，為一個(gè)進(jìn)程只進(jìn)行一次分配工作；而分段管理以段為內(nèi)存分配的最小對(duì)象，為一個(gè)進(jìn)程的每個(gè)段要進(jìn)行一次分配工作。分段基本原理地址映射從前面論述中，知道進(jìn)程被分成若干個(gè)邏輯段，每個(gè)段在內(nèi)存中占據(jù)一片連續(xù)的空間，內(nèi)存分配可以按可變分區(qū)的算法，必須進(jìn)行外碎片拼接。那么采用靜態(tài)地址映射還是動(dòng)態(tài)地址映射呢？答案顯然是必須采用動(dòng)態(tài)地址映射。否則無(wú)法實(shí)施外碎片拼接。

地址映射是將邏輯地址轉(zhuǎn)換為物理地址，先研究邏輯地址的構(gòu)成。

分段基本原理進(jìn)程的邏輯地址空間在分段存儲(chǔ)管理方式中，段是一組相關(guān)的邏輯信息的集合。每個(gè)段都有自己的名字和長(zhǎng)度，通常用一個(gè)段號(hào)來(lái)代替段名，每個(gè)段都從0開(kāi)始編址，并采用一段連續(xù)的地址空間，段的長(zhǎng)度由相應(yīng)的邏輯信息組的長(zhǎng)度決定。分段系統(tǒng)中的邏輯地址由段號(hào)s和段內(nèi)地址d組成，是一個(gè)二維地址（s,d）。是程序員負(fù)責(zé)安排的地址。由于分段的進(jìn)程邏輯地址空間是二維的，所以分段的地址映射在于如何把二維段地址結(jié)構(gòu)動(dòng)態(tài)地變成一維的內(nèi)存地址結(jié)構(gòu)。內(nèi)存分配時(shí)，是為任何一個(gè)段分配一個(gè)連續(xù)的內(nèi)存片，一個(gè)段內(nèi)的所有邏輯地址在該內(nèi)存片中的順序仍然不變。假設(shè)段的物理起始地址是a，由于段的起始邏輯地址是0，邏輯地址中作為偏移地址，加上段物理起始地址就是所求的物理地址。所以邏輯地址為x的單元其物理地址為a+x

?，F(xiàn)在已知邏輯地址（s，d），怎樣計(jì)算它在內(nèi)存的物理地址？與分頁(yè)管理的分析一樣，關(guān)鍵是找到邏輯地址與物理地址之間的映射關(guān)系。由于每個(gè)段在內(nèi)存是連續(xù)的，可以將段的物理地址看成是由基址和偏移地址（a，d）組成，根據(jù)前面分析，偏移地址又等于段內(nèi)地址，關(guān)鍵要找s和a的聯(lián)系。分配內(nèi)存時(shí)，是隨機(jī)為一個(gè)段分配空間，所以s和a之間不會(huì)存在某種線(xiàn)性函數(shù)關(guān)系，即不可能用數(shù)值計(jì)算的方法求解。但是段號(hào)s和段物理起始地址a之間確實(shí)存在著一一對(duì)應(yīng)的關(guān)系，可以用一個(gè)表(段表)保存這個(gè)關(guān)系，根據(jù)表的起始地址和s找該段的起始物理地址a。然后計(jì)算a+d

得到所要的物理地址。操作系統(tǒng)每個(gè)進(jìn)程建立一個(gè)表，保存其段號(hào)s和段物理起始地址a之間的關(guān)系，稱(chēng)為段表。在查表中仍然要防止地址越界的問(wèn)題。所以表中除了段物理起始地址外，還要保存段的長(zhǎng)度值。硬件上要提供相應(yīng)的段表控制寄存器，當(dāng)進(jìn)程切換時(shí)，操作系統(tǒng)把新進(jìn)程PCB中的段表起始地址和段表長(zhǎng)度值寫(xiě)入段表控制寄存器中，進(jìn)程訪(fǎng)問(wèn)內(nèi)存時(shí)，按照段表控制寄存器找段表，通過(guò)查表找段的物理起始地址。地址映射

段號(hào)段內(nèi)地址段表始址邏輯地址(2,100)>=段號(hào)越界中斷

+1K5002006000123基址段號(hào)段長(zhǎng)物理地址8292段式存儲(chǔ)的地址變換機(jī)構(gòu)2100+6K8K9K4Kyn>=yn段內(nèi)地址越界段表長(zhǎng)度4段的共享和保護(hù)

段的共享段的共享是指兩個(gè)以上的進(jìn)程，使用同一個(gè)子程序或數(shù)據(jù)段，而在內(nèi)存中只保留該信息的一個(gè)副本。具體地說(shuō)，只需在每個(gè)進(jìn)程的段表中，用相應(yīng)的表項(xiàng)裝入共享段在內(nèi)存的起始地址即可。內(nèi)存保護(hù)分段管理優(yōu)點(diǎn)之一就是方便內(nèi)存保護(hù)。前面看到怎樣進(jìn)行地址越界保護(hù)，它只是內(nèi)存保護(hù)的一部分，為了實(shí)施訪(fǎng)問(wèn)權(quán)限保護(hù)，在段表中再增加訪(fǎng)問(wèn)權(quán)限字段，每個(gè)進(jìn)程訪(fǎng)問(wèn)該段時(shí)還要進(jìn)行訪(fǎng)問(wèn)權(quán)限檢查，符合的才允許訪(fǎng)問(wèn)，否則拒絕訪(fǎng)問(wèn)。段的共享與保護(hù)

例子：有一個(gè)多用戶(hù)系統(tǒng)，可以容納40個(gè)用戶(hù)，他們都執(zhí)行一個(gè)文本編輯程序，如果文本編輯程序有160K的代碼和40K的數(shù)據(jù)區(qū)，則需要： （160+40）*40=8M的內(nèi)存空間，如果160K的代碼是可重入的，則在內(nèi)存中只保存一個(gè)副本就可以了，則需要：160+40*40=1760K內(nèi)存空間。段的共享與保護(hù)進(jìn)程1頁(yè)表ed1ed2…ed40data1data10…ed1ed2…ed40data1data10…2122…606170…2122…607180…進(jìn)程2頁(yè)表ed1ed2…ed40data1data10…主存editordata1data1data10……212260617007180editordata1段長(zhǎng)16016040基址8080380editordata1data140240…80420240280380進(jìn)程1進(jìn)程2段表（a）分頁(yè)系統(tǒng)中共享editor示意圖（b）分段系統(tǒng)中共享editor示意圖分頁(yè)與分段分配方式共享代碼段的比較進(jìn)程1頁(yè)表ed1ed2…ed40data1data10…ed1ed2…ed40data1data10…2122…606170…2122…607180…進(jìn)程2頁(yè)表ed1ed2…ed40data1data10…主存data1data10……212260617007180引入分段的理由：邏輯上的完整動(dòng)態(tài)鏈接信息共享信息保護(hù)分頁(yè)和分段的區(qū)別：頁(yè)的大小是固定的，頁(yè)的長(zhǎng)度是由內(nèi)存塊長(zhǎng)度決定的。段的長(zhǎng)度是可變的，段的長(zhǎng)度是由信息的長(zhǎng)度決定的；分頁(yè)的邏輯地址空間是一維的，分段的邏輯地址空間是二維的；分頁(yè)存在內(nèi)碎片，分段存在外碎片；邏輯地址分頁(yè)分段7.3.3段頁(yè)式存儲(chǔ)管理方式分頁(yè)存儲(chǔ)管理能有效地提高內(nèi)存的利用率，分段存儲(chǔ)管理能很好地滿(mǎn)足用戶(hù)的需要，段頁(yè)式存儲(chǔ)管理則是分頁(yè)和分段兩種存儲(chǔ)管理方式的結(jié)合，它同時(shí)具備了兩者的優(yōu)點(diǎn)。也繼承了兩者的缺點(diǎn)。

分段和分頁(yè)都有各自的優(yōu)勢(shì)。分頁(yè)對(duì)程序員來(lái)說(shuō)是透明的，它消除了外部碎片，因而可以更有效地使用主存。它具有處理不斷增長(zhǎng)的數(shù)據(jù)的能力。分段是由程序員決定的，對(duì)段的共享及保護(hù)操作容易，支持動(dòng)態(tài)鏈接等優(yōu)勢(shì)。把它們二者的優(yōu)點(diǎn)結(jié)合起來(lái)，就形成了非常具有優(yōu)勢(shì)的“段頁(yè)式存儲(chǔ)管理”方式。7.3.3.1段頁(yè)式管理原理程序員仍然按分段編程，邏輯地址是二維地址（段號(hào)，段內(nèi)地址）。操作系統(tǒng)仍對(duì)內(nèi)存用戶(hù)區(qū)實(shí)施分塊，物理地址由塊號(hào)和塊內(nèi)地址組成（塊號(hào)，塊內(nèi)地址）。操作系統(tǒng)對(duì)進(jìn)程以段為單位進(jìn)行分頁(yè)，一個(gè)段被分成若干頁(yè)，每一頁(yè)剛好占一個(gè)內(nèi)存塊，內(nèi)存里段和段之間可以不連續(xù)，一個(gè)段內(nèi)的頁(yè)和頁(yè)之間也可以不連續(xù)。7.3.3.1段頁(yè)式管理原理內(nèi)存分配和回收雖然名叫段頁(yè)式，其實(shí)內(nèi)存并沒(méi)有段的影子只有大小相同的塊，塊長(zhǎng)度決定了頁(yè)的長(zhǎng)度。所以?xún)?nèi)存分配和回收與分頁(yè)式管理是一樣的。內(nèi)存分配和回收操作簡(jiǎn)單，內(nèi)存的利用率比分頁(yè)式稍低一些，因?yàn)槊恳欢蔚淖詈笠豁?yè)會(huì)有內(nèi)碎片。這是繼承了分頁(yè)式的優(yōu)點(diǎn)。7.3.3.1段頁(yè)式管理原理地址映射首先研究邏輯地址在段頁(yè)式中的變化。程序員編程時(shí)仍然是分段編程，所以邏輯地址仍是二維的，即段號(hào)和段內(nèi)地址。操作系統(tǒng)以段為單位分頁(yè)，就把段內(nèi)地址分成兩部分，即頁(yè)號(hào)和頁(yè)內(nèi)地址，這樣，邏輯地址變成（段號(hào)，頁(yè)號(hào)，頁(yè)內(nèi)地址）。再來(lái)看物理地址，物理地址是（塊號(hào)，塊內(nèi)地址），因?yàn)橐粔K正好裝入一頁(yè)，所以，頁(yè)7.3.3.1段頁(yè)式管理原理內(nèi)地址就等于塊內(nèi)地址。下面就要考慮段號(hào)和頁(yè)號(hào)與塊號(hào)之間的聯(lián)系。因?yàn)橐远螢閱挝环猪?yè)，所以每個(gè)段都要一個(gè)頁(yè)表，頁(yè)表每項(xiàng)裝入對(duì)應(yīng)的塊號(hào)；每個(gè)進(jìn)程分多個(gè)段，一個(gè)進(jìn)程設(shè)置一個(gè)段表。段表項(xiàng)目?jī)?nèi)容與分段式中的段表內(nèi)容不同，為了檢查地址越界，一個(gè)段表項(xiàng)至少包括頁(yè)表的長(zhǎng)度和頁(yè)表的起始地址。7.3.3.1段頁(yè)式管理原理

主程序段04K8K12K15K16K子程序段04K8K數(shù)據(jù)段04K8K12K10K（a）一個(gè)進(jìn)程地址空間的結(jié)構(gòu)段號(hào)（s）段內(nèi)頁(yè)號(hào)（p）頁(yè)內(nèi)偏移量（d）（b）段頁(yè)式地址結(jié)構(gòu)的組成圖7.2進(jìn)程地址空間和地址結(jié)構(gòu)段頁(yè)式分配的地址變換圖解

>=越界中斷

＋段頁(yè)式存儲(chǔ)的地址變換機(jī)構(gòu)0123基址段號(hào)2頁(yè)表長(zhǎng)度頁(yè)表+B1塊號(hào)頁(yè)號(hào)0123>=塊內(nèi)地址塊號(hào)段號(hào)2頁(yè)號(hào)2頁(yè)內(nèi)地址d段表地址段表長(zhǎng)度段內(nèi)地址YNYN7.3.3.1段頁(yè)式管理原理從地址映射看到，為了計(jì)算內(nèi)存物理地址需要兩次訪(fǎng)問(wèn)內(nèi)存（段表，頁(yè)表），顯然增加執(zhí)行一條指令的時(shí)間，使進(jìn)程執(zhí)行時(shí)間延長(zhǎng)，這是段頁(yè)式管理天生缺陷，為了提高訪(fǎng)問(wèn)內(nèi)存的速度，可以用增加快表的方法，利用高速緩沖內(nèi)存存放段表和頁(yè)表的子集，縮短計(jì)算物理地址的時(shí)間。7.3.3.1段頁(yè)式管理原理內(nèi)存共享和保護(hù)段頁(yè)式管理吸取了分段式管理和分頁(yè)式管理的優(yōu)點(diǎn)，可以說(shuō)在內(nèi)存分配回收方面吸取了分頁(yè)管理的優(yōu)點(diǎn)，在內(nèi)存共