操作系統(tǒng)-第4章(1)(第四版)

第四章存儲器管理4.1存儲器的層次結(jié)構(gòu)

4.2程序的裝入和鏈接

4.3連續(xù)分配存儲管理方式4.4對換4.4分頁存儲管理方式4.5分段存儲管理方式4.1存儲器的層次結(jié)構(gòu)

一、多級存儲器結(jié)構(gòu)

在現(xiàn)代計算機系統(tǒng)中，存儲器是信息的來源與歸宿，占據(jù)重要位置。但是，在現(xiàn)有技術條件下，任何一種存儲裝置，都無法同時從速度與容量兩方面，滿足用戶的需求。實際上它們組成了一個速度由快到慢，容量由小到大的存儲裝置層次。

圖4-1計算機系統(tǒng)存儲層次示意

速度快慢小大容量OS管理設備管理二、各種存儲器1．主存儲器簡稱內(nèi)存、主存、可執(zhí)行存儲器；主要部件，保存進程運行時的程序和數(shù)據(jù)，若干兆字節(jié)、中等速度、中等價格。主存儲器的訪問速度遠低于CPU執(zhí)行指令的速度，為緩和這一矛盾，在計算機系統(tǒng)中引入了寄存器和高速緩存。

2．寄存器速度最快，價格昂貴，容量小。以字(word)為單位。寄存器用于加速存儲器的訪問速度，如：用寄存器存放操作數(shù)。3．高速緩存

少量的、容量小（幾十KB~幾MB

）、非常快速、昂貴。主存中常訪問的信息存放在高速緩存中，減少訪主次數(shù)。4．磁盤緩存目前磁盤的I/O速度遠低于對主存的訪問速度，將頻繁使用的一部分磁盤數(shù)據(jù)和信息，暫時存放在磁盤緩存中，可減少訪問磁盤的次數(shù)。

即利用主存中的存儲空間，來暫存從磁盤中讀出(或?qū)懭?的信息。掉電則丟失。文件硬盤存放內(nèi)存調(diào)入磁盤緩沖備份磁帶文件出現(xiàn)于不同的存儲層次中三、存儲管理的目的

1)主存的分配和管理當用戶需要內(nèi)存時，系統(tǒng)為之分配相應的存儲空間；不需要時，及時回收，以供其它用戶使用。

2)提高主存儲器的利用率不僅能使多道程序動態(tài)地共享主存，提高主存利用率，最好還能共享主存中某個區(qū)域的信息。

3)“擴充”主存容量為用戶提供比主存物理空間大得多的地址空間，以至使用戶感覺他的作業(yè)是在這樣一個大的存儲器中運行。

4)存儲保護確保多道程序都在各自分配到存儲區(qū)域內(nèi)操作，互不干擾，防止一道程序破壞其它作業(yè)或系統(tǒng)文件的信息。

四、預備知識（補充）1.定位（存儲分配）為具體的程序和數(shù)據(jù)等分配存儲單元或存儲區(qū)工作。2.映射把邏輯地址轉(zhuǎn)換為相應的物理地址的過程。3.隔離按存取權(quán)限把合法區(qū)與非法區(qū)分隔，實現(xiàn)存儲保護。4.名空間程序員在程序中定義的標識符程序符號集合由程序員自定義沒有地址的概念符號指令數(shù)據(jù)說明I/O說明5、邏輯地址、邏輯地址空間邏輯地址(相對地址、虛地址)

用戶的程序經(jīng)過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式，其首地址為0，其余指令中的地址都相對于首地址而編址。用戶的程序地址(指令地址或操作數(shù)地址)均為邏輯地址。不能用邏輯地址在內(nèi)存中讀取信息。(why)作業(yè)地址空間（作業(yè)邏輯地址空間、作業(yè)虛空間）

用戶程序所有的邏輯地址集合對應的空間。由編譯程序生成作業(yè)地址空間01n-1

指令、數(shù)據(jù)movr1,[500]1230100500599作業(yè)地址空間6、物理地址、物理地址空間物理地址(絕對地址、實地址)物理地址是計算機主存單元的真實地址，又稱為絕對地址或?qū)嵉刂?。可直接尋址。主存空間（物理地址空間、存儲空間）物理地址的集合所對應的空間組成了主存空間。主存空間01n-1

地址映射LoadA2003456

。。1200物理地址空間LoadAdata1data13456名空間LoadA20034560100200編譯連接邏輯地址空間BA=1000圖:名空間、地址空間、存儲空間源程序目標程序可執(zhí)行程序

7.存儲共享

內(nèi)存共享：兩個或多個進程共用內(nèi)存中相同區(qū)。目的：節(jié)省內(nèi)存空間，提高內(nèi)存利用率。實現(xiàn)進程通信：數(shù)據(jù)共享。共享內(nèi)容：代碼共享。數(shù)據(jù)共享。

8.存儲保護與安全

1)保護目的為多個程序共享內(nèi)存提供保障,使在內(nèi)存中的各道程序,只能訪問它自己的區(qū)域，避免各道程序間相互干攏，特別是當一道程序發(fā)生錯誤時,不致于影響其他程序的運行。通常由硬件完成保護功能，由軟件輔助實現(xiàn)。特權(quán)指令不能完成存儲保護。

2)存儲保護

ⅰ.保護系統(tǒng)程序區(qū)不被用戶侵犯。（有意或無意的）

ⅱ.不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)。（系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）

3)保護過程--防止地址越界每個進程都有自己獨立的進程空間，如果一個進程在運行時所產(chǎn)生的地址在其地址空間之外，則發(fā)生地址越界。即當程序要訪問某個內(nèi)存單元時，由硬件檢查是否允許，如果允許則執(zhí)行，否則產(chǎn)生地址越界中斷，由操作系統(tǒng)進行相應處理。9.內(nèi)存“擴充”

通過虛擬存儲技術實現(xiàn)用戶在編制程序時，不應該受內(nèi)存容量限制，所以要采用一定技術來“擴充”內(nèi)存的容量，使用戶得到比實際內(nèi)存容量大的多的內(nèi)存空間。具體實現(xiàn)是在硬件支持下，軟硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來統(tǒng)一使用。通過這種方法把內(nèi)存擴充，使用戶在編制程序時不受內(nèi)存限制。4.2程序的裝入和鏈接

在多道程序環(huán)境下，要使程序運行，必須創(chuàng)建進程，而創(chuàng)建進程第一件事就是將程序和數(shù)據(jù)裝入內(nèi)存。一個用戶源程序要變?yōu)樵趦?nèi)存中可執(zhí)行的程序，通常要進行以下處理：

（1）編譯：由編譯程序?qū)⒂脩粼闯绦蚓幾g成若干個目標模塊

（2）鏈接：由鏈接程序?qū)⒛繕四K和相應的庫函數(shù)鏈接成裝入模塊

（3）裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存庫目標程序塊1目標程序塊2第一步鏈接程序裝入模塊(.exe)第二步裝入程序第三步用戶源程序(.c;.c++)編譯程序.obj一、程序的裝入(由裝入程序?qū)⒀b入模塊(exe文件)裝入內(nèi)存)1．絕對裝入方式(AbsoluteLoadingMode)（早期）

如果在編譯時，事先知用戶程序在內(nèi)存的駐留位置，則編譯程序在編譯時就產(chǎn)生絕對地址的目標代碼。裝入程序就直接把裝入模塊中的程序和數(shù)據(jù)裝入到指定的位置，（不需進行地址轉(zhuǎn)換）該裝入方式只適用于單道程序環(huán)境。2．可重定位裝入方式(RelocationLoadingMode)

在多道程序環(huán)境下，目標模塊中的其它地址都是相對于0編址。應根據(jù)內(nèi)存的當前情況，將裝入模塊裝入到內(nèi)存的適當位置。

通常是把在裝入時對目標程序中指令和數(shù)據(jù)的修改過程稱為重定位。圖4-3作業(yè)裝入內(nèi)存時的情況修改指令地址修改數(shù)據(jù)地址指令中的相對地址是否要修改？

裝入模塊中所有的邏輯地址與實際裝入內(nèi)存的物理地址不同。從此裝入LOADl,[2500]365010002500100001100012500LOADl,[2500]365程序空間內(nèi)存空間0[12500]12500＝10000+2500物理地址基地址相對地址地址變換在裝入時一次完成，以后不改變，靜態(tài)再定位。是否允許程序運行時在內(nèi)存中移動位置？3．動態(tài)運行時裝入方式(DynamicRun-timeLoading)

可重定位裝入方式:

裝入模塊裝入到內(nèi)存中任何允許的位置。不允許程序運行時在內(nèi)存中移動位置。

實際情況：程序在運行過程中它在內(nèi)存中的位置可能經(jīng)常要改變。動態(tài)運行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行。因此，裝入內(nèi)存后的所有地址都仍是相對地址。二、程序的鏈接根據(jù)鏈接時間的不同，程序鏈接分成三種：

(1)靜態(tài)鏈接。

(2)裝入時動態(tài)鏈接。

(3)運行時動態(tài)鏈接。1．靜態(tài)鏈接方式(StaticLinking)圖

4-4程序鏈接示意圖

是一種事先鏈接方式，即在程序運行之前，先將各目標模塊及它們所需的庫函數(shù)，鏈接成一個完整的裝入模塊(執(zhí)行文件)，以后不再拆開。

實現(xiàn)靜態(tài)鏈接應解決的問題：（1）相對地址的修改（2）變換外部調(diào)用符號存在問題：（1）不便于對目標模塊的修改和更新。如要更新其中一個模塊，需要打開裝入模塊。（2）無法實現(xiàn)對目標模塊的共享。PPAB靜態(tài)鏈接2．裝入時動態(tài)鏈接(Load-timeDynamicLinking)

將用戶源程序編譯后所得到的一組目標模塊，在裝入內(nèi)存時，采用邊裝入邊鏈接的鏈接方式。

優(yōu)點：

(1)便于修改和更新。各目標模塊是分開存放的;修改容易；

(2)便于實現(xiàn)對目標模塊的共享。PPAB靜態(tài)鏈接PAB裝入時動態(tài)鏈接存在問題：

由于程序運行所有可能用的目標模塊在裝入時均全部鏈接在一起，所以將會把一些不會運行的目標模塊也鏈接進去。如程序中的錯誤處理模塊。3．運行時動態(tài)鏈接(Run-timeDynamicLinking)

定義：對某些模塊的鏈接推遲到程序執(zhí)行時才進行鏈接。在執(zhí)行過程中，當發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。三、重定位

地址映射：把作業(yè)地址空間中使用的邏輯地址變換成內(nèi)存空間中的物理地址的過程。如下圖，作業(yè)i經(jīng)過重定位，把地址集合映射到以1000為始址的內(nèi)存中，作為作業(yè)i的存儲空間。作業(yè)i1.重定位的類型

1)靜態(tài)重定位當用戶程序被裝入內(nèi)存時，一次性實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時由軟件完成），作業(yè)i在執(zhí)行前一次變址，直到該作業(yè)完成退出內(nèi)存為止。

動態(tài)重定位在程序運行過程中要訪問數(shù)據(jù)時再進行地址變換。由地址變換機構(gòu)進行的地址變換，硬件上需要重定位寄存器的支持。

重定位寄存器：在執(zhí)行一條指令取操作數(shù)時，要將指令給出的有效地址(500)與重定位寄存器中的內(nèi)容（1000）相加，得訪問地址（1500），從而實現(xiàn)了地址動態(tài)修改。裝入時未修改4.3連續(xù)分配存儲管理方式

一、單一連續(xù)分配方式

最簡單的一種存儲管理方式，但只能用于單用戶、單任務的OS中。存儲管理方法：將內(nèi)存分為系統(tǒng)區(qū)（內(nèi)存低端，分配給OS用）和用戶區(qū)（內(nèi)存高端，分配給用戶用）。采用靜態(tài)分配方式，即作業(yè)一旦進入內(nèi)存，就要等待它運行結(jié)束后才能釋放內(nèi)存。主要特點：管理簡單，只需小量的軟件和硬件支持，便于用戶了解和使用。但因內(nèi)存中只裝入一道作業(yè)運行，內(nèi)存空間浪費大，各類資源的利用率也不高。系統(tǒng)區(qū)-os用戶區(qū)用戶程序工作流程

單一連續(xù)區(qū)分配采用靜態(tài)重定位方式，即作業(yè)或進程一旦進入主存，就一直等到它運行結(jié)束后才能釋放主存。下圖所示的主存分配與回收法。并且由裝入程序檢查其絕對地址是否越界，即可達到保護系統(tǒng)的目的。缺點：

不支持多道。主存利用率不高。程序的運行受主存容量限制。分區(qū)分配方式存儲管理

分區(qū)分配方式是滿足多道程序設計需要的一種最簡單的存儲管理方法。存儲管理方法

將內(nèi)存分成若干個分區(qū)（大小相等/不相等），除OS占一區(qū)外，其余的每一個分區(qū)容納一個用戶程序。按分區(qū)的變化情況，可將分區(qū)存儲管理進一步分為：固定分區(qū)存儲管理動態(tài)分區(qū)存儲管理二、固定分區(qū)分配（固定分區(qū)存儲管理）

是最早使用的一種可運行多道程序的存儲管理方法。存儲管理方法內(nèi)存空間的劃分：將內(nèi)存空間劃分為若干個固定大小的分區(qū)，除OS占一區(qū)外，其余的一個分區(qū)裝入一道程序。分區(qū)的大小可以相等，也可以不等，但事先必須確定，在運行時不能改變。即分區(qū)大小及邊界在運行時不能改變。系統(tǒng)需建立一張分區(qū)說明表或使用表，以記錄分區(qū)號、分區(qū)大小、分區(qū)的起始地址及狀態(tài)（已分配或未分配）。固定分區(qū)分配方式示意圖os用戶程序p4p1p20k20k56k65k125k135k區(qū)號大小起址狀態(tài)136k20k已分配29k56k未分配360k65k已分配410k125k已分配分區(qū)說明表分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)多個等待隊列單個等待隊列分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)圖：固定分區(qū)示意圖內(nèi)存分配當某個用戶程序要裝入內(nèi)存時，由內(nèi)存分配程序檢索分區(qū)說明表，從表中找出一個滿足要求的尚未分配的分區(qū)分配該程序，同時修改說明表中相應分區(qū)的狀態(tài)；若找不到大小足夠的分區(qū)，則拒絕為該程序分配內(nèi)存。當程序執(zhí)行完畢，釋放占用的分區(qū)，管理程序?qū)⑿薷恼f明表中相應分區(qū)的狀態(tài)為未分配，實現(xiàn)內(nèi)存資源的回收。主要特點：管理簡單，但因作業(yè)的大小并不一定與某個分區(qū)大小相等，從而使一部分存儲空間被浪費。所以主存的利用率不高。例題分配回收２０

例：在某系統(tǒng)中，采用固定分區(qū)分配管理方式，內(nèi)存分區(qū)（單位字節(jié)）情況如圖所示，現(xiàn)有大小為1K、9K、33K、121K的多個作業(yè)要求進入內(nèi)存，試畫出它們進入內(nèi)存后的空間分配情況，并說明主存浪費多大？10k20k28k60k180k511k234（1）內(nèi)存分區(qū)圖os區(qū)號大小起址狀態(tài)18k20k未分配232k28k未分配3120k60k未分配4331k180k未分配（2）分區(qū)說明表區(qū)號大小起址狀態(tài)18k20k已分配232k28k已分配3120k60k已分配4331k180k已分配（2）分區(qū)說明表0k20k28k60k180k511k23(1)內(nèi)存分配圖(3)主存浪費空間=(8-1)+(32-9)+(120-33)+(331-121)=7+23+87+210=327(k)解：根據(jù)分區(qū)說明表，將4個分區(qū)依次分配給4個作業(yè)，同時修改分區(qū)說明表，其內(nèi)存分配和分區(qū)說明表如下所示：1K9K33K121K結(jié)論：浪費嚴重；產(chǎn)生內(nèi)部碎片三、動態(tài)分區(qū)分配方式

動態(tài)分區(qū)分配又稱為可變式分區(qū)分配，是一種動態(tài)劃分存儲器的分區(qū)方法。存儲管理方法

不事先將內(nèi)存劃分成一塊塊的分區(qū)，而是在作業(yè)進入內(nèi)存時，根據(jù)作業(yè)的大小動態(tài)地建立分區(qū)，并使分區(qū)的大小正好適應作業(yè)的需要。因此系統(tǒng)中分區(qū)的大小是可變的，分區(qū)的數(shù)目也是可變的。

主要特點

管理簡單，只需小量的軟件和硬件支持，便于用戶了解和使用。進程的大小與某個分區(qū)大小相等，從而主存的利用率有所提高。1、分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表

用來登記系統(tǒng)中的空閑分區(qū)(分區(qū)號,分區(qū)起始地址,分區(qū)大小及狀態(tài)).分區(qū)號大小KB起始地址KB狀態(tài)132352空閑2……空表目3520504空閑4……空表目5………空閑分區(qū)鏈

用鏈頭指針將系統(tǒng)中的空閑分區(qū)鏈接起來，構(gòu)成空閑分區(qū)鏈。每個空閑分區(qū)的起始部分存放相應的控制信息(如大小,指向下一空閑分區(qū)的指針等).352KB504KB32KB^520KB空閑分區(qū)鏈頭指針2、分區(qū)分配算法

為了將一個作業(yè)裝入內(nèi)存，應按照一定的分配算法從空閑分區(qū)表（鏈）中選出一個滿足作業(yè)需求的分區(qū)分配給作業(yè)，如果這個空閑分區(qū)的容量比作業(yè)申請的空間要大，則將該分區(qū)一分為二，一部分分配給作業(yè)，剩下的部分仍然留在空閑分區(qū)表（鏈）中，同時修改空閑分區(qū)表（鏈）中相應的信息。目前常用分配算法有：首次適應算法循環(huán)首次適應算法最佳適應算法最壞適應算法首次適應算法（最先適應算法）算法

空閑分區(qū)（鏈）按地址遞增的次序排列。在進行內(nèi)存分配時,從空閑分區(qū)表/鏈首開始順序查找,直到找到第一個滿足其大小要求的空閑分區(qū)為止。然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表（鏈）中。區(qū)號大小起址132k20k28k52k3120k60k4331k180k空閑分區(qū)表解：按首次適應算法，

申請作業(yè)100k，分配3號分區(qū)，剩下分區(qū)為20k，起始地址160K；申請作業(yè)30k，分配1號分區(qū)，剩下分區(qū)為2k，起始地址50K；申請作業(yè)7k，分配2號分區(qū)，剩下分區(qū)為1k，起始地址59K；其內(nèi)存分配圖及分配后空閑分區(qū)表如下:例：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間100K、30K及7K。給出按首次適應算法的內(nèi)存分配情況及分配后空閑分區(qū)表。區(qū)號大小起址12k50k21k59k320k160k4331k380k(3)該算法分配后的空閑分區(qū)表0k20k52k60k180k511k(1)內(nèi)存分配圖50K59K160K380K首次適應算法的特點

優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū),從而保留了高地址部分的大空閑區(qū)。但由于低地址部分不斷被劃分,致使低地址端留下許多難以利用的很小的空閑分區(qū)(碎片或零頭),而每次查找又都是從低地址部分開始,這無疑增加了查找可用空閑分區(qū)的開銷。區(qū)號大小起址132k20k28k52k3120k60k4331k180k(2)分配前空閑分區(qū)表三個作業(yè)分配申請內(nèi)存空間100K、30K及7K。循環(huán)首次適應算法算法

又稱為下次適應算法，由首次適應算法演變而來。在為作業(yè)分配內(nèi)存空間時,不再每次從空閑分區(qū)表/鏈首開始查找,而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找,直到找到第一個能滿足其大小要求的空閑分區(qū)為止。然后，再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表/鏈中。區(qū)號大小起址132k20k28k52k3120k60k4331k180k空閑分區(qū)表解：按循環(huán)首次適應算法，

申請作業(yè)100k，分配3號分區(qū)，剩下分區(qū)為20k,起始地址160K；申請作業(yè)30k，分配4號分區(qū)，剩下分區(qū)為301k，起始地址210K；申請作業(yè)7k，分配1號分區(qū)，剩下分區(qū)為25k，起始地址27K；其內(nèi)存分配圖及分配后空閑分區(qū)表如下：例：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間100K、30K及7K。給出按循環(huán)首次適應算法的內(nèi)存分配情況及分配后空閑分區(qū)表。區(qū)號大小起址125k27k28k52k320k160k4301k210k(3)該算法分配后的空閑分區(qū)表算法特點

使存儲空間的利用更加均衡，不致使小的空閑區(qū)集中在存儲區(qū)的一端，但這會導致缺乏大的空閑分區(qū)。0k20k52k60k180k511k(1)內(nèi)存分配圖27K52K160K210K區(qū)號大小起址132k20k28k52k3120k60k4331k180k(2)分配前空閑分區(qū)表三個作業(yè)分配申請內(nèi)存空間100K、30K及7K。最佳適應算法算法

空閑分區(qū)表/鏈按容量大小遞增的次序排列。在進行內(nèi)存分配時，從空閑分區(qū)表/鏈的首開始順序查找，直到找到第一個滿足其大小要求的空閑分區(qū)為止。按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。如果該空閑分區(qū)大于作業(yè)的大小，則與首次適應算法相同，將剩余空閑分區(qū)仍留在空閑分區(qū)表/鏈中。0k20k52k60k180k511k2134例：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間100K、30K及7K。給出按最佳適應算法的內(nèi)存分配情況及分配后空閑分區(qū)表。區(qū)號大小起址18k52k232k20k3120k60k4331k180k分配前的空閑分區(qū)表內(nèi)存分區(qū)按從小到大排隊解：按最佳適應算法，分配前的空閑分區(qū)表如上表。

申請作業(yè)100k，分配3號分區(qū)，剩下分區(qū)為20k,起始地址160K；申請作業(yè)30k，分配2號分區(qū)，剩下分區(qū)為2k，起始地址50K；申請作業(yè)7k，分配1號分區(qū)，剩下分區(qū)為1k，起始地址59K；其內(nèi)存分配圖及分配后空閑分區(qū)表如下區(qū)號大小起址18k52k320k160k232k20k4331k180k作業(yè)100K分配后的空閑分區(qū)表區(qū)號大小起址22k50k18k52k320k160k4331k180k作業(yè)30K分配后的空閑分區(qū)表區(qū)號大小起址11k59k22k50k320k160k4331k180k作業(yè)7K分配后的空閑分區(qū)表區(qū)號大小起址18k52k232k20k3120k60k4331k180k分配前的空閑分區(qū)表(2)該算法分配后的空閑分區(qū)表0k20k52k60k180k511k(1)內(nèi)存分配圖50K59K160K180K區(qū)號大小起址11k59k22k50k320k160k4331k180k算法特點

若存在與作業(yè)大小一致的空閑分區(qū),則它必然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的空閑分區(qū)，,從而保留了大的空閑分區(qū),但空閑區(qū)一般不可能正好和它申請的內(nèi)存空間大小一樣,因而將其分割成兩部分時,往往使剩下的空閑區(qū)非常小,從而在存儲器中留下許多難以利用的小空閑區(qū)（碎片或零頭）。最壞適應算法算法

空閑分區(qū)表/鏈按容量大小遞減的次序排列。在進行內(nèi)存分配時，從空閑分區(qū)表/鏈的首開始順序查找，直到找到第一個比之大的空閑分區(qū)為止。剩下的空閑仍留在空閑分區(qū)表/鏈中。區(qū)號大小起址1331k180k2120k60k332k20k48k52k空閑分區(qū)表例：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間100K、30K及7K。給出按最壞適應算法的內(nèi)存分配情況及分配后空閑分區(qū)表。按從大到小排隊區(qū)號大小起址1231k280k2120k60k332k20k48k52k作業(yè)100K分配后的空閑分區(qū)表區(qū)號大小起址1201k310k2120k60k332k20k48k52k作業(yè)30K分配后的空閑分區(qū)表區(qū)號大小起址1194k317k2120k60k332k20k48k52k作業(yè)7K分配后的空閑分區(qū)表解：按最壞適應算法，分配前的空閑分區(qū)表如上表。

申請作業(yè)100k，分配1號分區(qū)，剩下分區(qū)為231k,起始地址280K；申請作業(yè)30k，分配1號分區(qū)，剩下分區(qū)為201k，起始地址310K；申請作業(yè)7k，分配1號分區(qū)，剩下分區(qū)為194k，起始地址317K；其內(nèi)存分配圖及分配后空閑分區(qū)表如下：區(qū)號大小起址1331k180k2120k60k332k20k48k52k空閑分區(qū)表區(qū)號大小起址1194k317k2120k60k332k20k48k52k(2)該算法分配后的空閑分區(qū)表30k20k52k60k180k511k(1)內(nèi)存分配圖20K52K60K280K310K317K算法特點

總是挑選滿足作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于最大的空閑分區(qū)總是因首先分配而劃分，當有大作業(yè)到來時，其存儲空間的申請往往會得不到滿足。3．分區(qū)分配操作1)分配內(nèi)存—根據(jù)內(nèi)存分配算法圖

4-7內(nèi)存分配流程

設:u.size:

請求的分區(qū)大小為；

m.size:

空閑分區(qū)的大??；

size：規(guī)定不再切割的剩余分區(qū)的大小；

該分區(qū)整體分配分成兩部分找一個空閑區(qū)能滿足作業(yè)大小（2）回收內(nèi)存

當作業(yè)執(zhí)行結(jié)束時，應回收已使用完畢的分區(qū)。系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)，如有，則合成為一個大的空閑分區(qū)，然后修改有關的分區(qū)狀態(tài)信息。回收分區(qū)與已有空閑分區(qū)的相鄰情況有以下四種：

1）回收分區(qū)上鄰接一個空閑分區(qū),合并后首地址為空閑分區(qū)的首地址,大小為二者之和。

2）回收分區(qū)下鄰接一個空閑分區(qū),合并后首地址為回收分區(qū)的首地址,大小為二者之和。

3）回收分區(qū)上下鄰接空閑分區(qū),合并后首地址為上空閑分區(qū)的首地址,大小為三者之和。

4）回收分區(qū)不鄰接空閑分區(qū)，這時在空閑分區(qū)表中新建一表項，并填寫分區(qū)大小等信息。…回收分區(qū)空閑分區(qū)…(a)…空閑分區(qū)回收分區(qū)…(b)…空閑分區(qū)回收分區(qū)空閑分區(qū)…(c)內(nèi)存回收情況思考：

哪種回收情況，回收后，空閑分區(qū)數(shù)目要減少一個？四、可重定位分區(qū)分配方式1、碎片問題

在分區(qū)存儲管理方式中，必須把作業(yè)裝入到一片連續(xù)的內(nèi)存空間。如果系統(tǒng)中有若干個小的分區(qū)，其總?cè)萘看笥谝b入的作業(yè)，但由于它們不相鄰接，也將致使作業(yè)不能裝入內(nèi)存。例：如圖所示系統(tǒng)中有四個小空閑分區(qū)，不相鄰，但總?cè)萘繛?0KB，如果現(xiàn)有一作業(yè)要求分配40KB的內(nèi)存空間，由于系統(tǒng)中所有空閑分區(qū)的容量均小于40KB，故此作業(yè)無法裝入內(nèi)存。這種內(nèi)存中無法被利用的存儲空間稱為“零頭”或“碎片”。根據(jù)碎片出現(xiàn)的情況分為以下兩種：操作系統(tǒng)作業(yè)A20KB作業(yè)B30KB作業(yè)C15KB作業(yè)D25KB系統(tǒng)中的碎片os用戶程序p4p1p20k20k56k65k125k135k內(nèi)部碎片內(nèi)部碎片內(nèi)部碎片25KB作業(yè)D15KB作業(yè)C30KB作業(yè)B20KB作業(yè)A操作系統(tǒng)外部碎片外部碎片外部碎片外部碎片內(nèi)部碎片外部碎片內(nèi)部碎片：指分配給作業(yè)的存儲空間中未被利用的部分。如固定分區(qū)中存在的碎片。外部碎片：指系統(tǒng)中無法利用的小的空閑分區(qū)。如動態(tài)分區(qū)中存在的碎片。2.碎片問題的解決方法

對系統(tǒng)中存在碎片，目前主要有兩種技術：拼接或緊湊或緊縮技術將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在內(nèi)存中的位置發(fā)生了變化，這就必須對其地址加以修改或變換即稱為重定位），使本來分散的多個小空閑分區(qū)連成一個大的空閑區(qū)。如圖所示。這種通過移動作業(yè)從把多個分散的小分區(qū)拼接成一個大分區(qū)的方法稱為拼接或緊湊或緊縮。

拼接時機：分區(qū)回收時；當找不到足夠大的空閑分區(qū)且總空閑分區(qū)容量可以滿足作業(yè)要求時。操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C作業(yè)D20KB30KB90KB15KB25KB建立在動態(tài)重定位基礎上動態(tài)重定位分區(qū)分配算法流程圖有大于x的空閑分區(qū)嗎？返回分區(qū)號空閑分區(qū)總和大于x嗎？拼接并修改相應數(shù)據(jù)結(jié)構(gòu)返回修改有關數(shù)據(jù)結(jié)構(gòu)按動態(tài)分區(qū)分配方式進行分配YYNN無法分配，返回請求分配一個大小為x的分區(qū)動態(tài)重定位分區(qū)分配技術

在動態(tài)分區(qū)分配算法中增加拼接功能，在找不到足夠大的空閑分區(qū)來滿足作業(yè)要求，而系統(tǒng)中總空閑分區(qū)容量可以滿足作業(yè)要求時，進行拼接。特點:

可以充分利用存儲區(qū)中的“零頭/碎片”，提高主存的利用率。但若“零頭/碎片”大多，則拼接頻率過高會使系統(tǒng)開銷加大。五、分區(qū)的存儲保護

存儲保護是為了防止一個作業(yè)有意或無意地破壞操作系統(tǒng)或其它作業(yè)，常用的存儲保護方法有：1、界限寄存器方法

上下界寄存器方法基址、限長寄存器方法2、存儲保護鍵方法給每個存儲塊分配一個單獨的保護鍵，它相當于一把鎖。進入系統(tǒng)的每個作業(yè)也賦予一個保護鍵，它相當于一把鑰匙。當作業(yè)運行時，檢查鑰匙和鎖是否匹配，