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

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

4.2程序的裝入和鏈接

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

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

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

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

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

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

少量的、容量?。◣资甂B~幾MB

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

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

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

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

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

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

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

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

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

指令、數(shù)據(jù)movr1,[500]1230100500599作業(yè)地址空間6、物理地址、物理地址空間物理地址(絕對(duì)地址、實(shí)地址)物理地址是計(jì)算機(jī)主存單元的真實(shí)地址，又稱為絕對(duì)地址或?qū)嵉刂贰？芍苯訉ぶ?。主存空間（物理地址空間、存儲(chǔ)空間）物理地址的集合所對(duì)應(yīng)的空間組成了主存空間。主存空間01n-1

地址映射LoadA2003456

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

7.存儲(chǔ)共享

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

8.存儲(chǔ)保護(hù)與安全

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

2)存儲(chǔ)保護(hù)

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

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

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

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

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

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

（2）鏈接：由鏈接程序?qū)⒛繕?biāo)模塊和相應(yīng)的庫函數(shù)鏈接成裝入模塊

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

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

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

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

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

可重定位裝入方式:

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

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

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

(2)裝入時(shí)動(dòng)態(tài)鏈接。

(3)運(yùn)行時(shí)動(dòng)態(tài)鏈接。1．靜態(tài)鏈接方式(StaticLinking)圖

4-4程序鏈接示意圖

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

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

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

優(yōu)點(diǎn)：

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

(2)便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。PPAB靜態(tài)鏈接PAB裝入時(shí)動(dòng)態(tài)鏈接存在問題：

由于程序運(yùn)行所有可能用的目標(biāo)模塊在裝入時(shí)均全部鏈接在一起，所以將會(huì)把一些不會(huì)運(yùn)行的目標(biāo)模塊也鏈接進(jìn)去。如程序中的錯(cuò)誤處理模塊。3．運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-timeDynamicLinking)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

主要特點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

設(shè):u.size:

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

m.size:

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

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

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

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

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

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

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

4）回收分區(qū)不鄰接空閑分區(qū)，這時(shí)在空閑分區(qū)表中新建一表項(xiàng)，并填寫分區(qū)大小等信息?！厥辗謪^(qū)空閑分區(qū)…(a)…空閑分區(qū)回收分區(qū)…(b)…空閑分區(qū)回收分區(qū)空閑分區(qū)…(c)內(nèi)存回收情況思考：

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

在分區(qū)存儲(chǔ)管理方式中，必須把作業(yè)裝入到一片連續(xù)的內(nèi)存空間。如果系統(tǒng)中有若干個(gè)小的分區(qū)，其總?cè)萘看笥谝b入的作業(yè)，但由于它們不相鄰接，也將致使作業(yè)不能裝入內(nèi)存。例：如圖所示系統(tǒng)中有四個(gè)小空閑分區(qū)，不相鄰，但總?cè)萘繛?0KB，如果現(xiàn)有一作業(yè)要求分配40KB的內(nèi)存空間，由于系統(tǒng)中所有空閑分區(qū)的容量均小于40KB，故此作業(yè)無法裝入內(nèi)存。這種內(nèi)存中無法被利用的存儲(chǔ)空間稱為“零頭”或“碎片”。根據(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è)的存儲(chǔ)空間中未被利用的部分。如固定分區(qū)中存在的碎片。外部碎片：指系統(tǒng)中無法利用的小的空閑分區(qū)。如動(dòng)態(tài)分區(qū)中存在的碎片。2.碎片問題的解決方法

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

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

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

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

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

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