第五章存儲器管理

1、12本章內(nèi)容本章內(nèi)容5.1 存儲管理概述存儲管理概述5.2 程序的裝入和鏈接程序的裝入和鏈接5.3 連續(xù)分配方式連續(xù)分配方式5.4 基本分頁存儲管理方式基本分頁存儲管理方式 5.5 基本分段存儲管理方式基本分段存儲管理方式5.6 基本段頁式存儲管理方式基本段頁式存儲管理方式35.1 存儲管理概述存儲管理概述5.1.1 存儲器層次45.1.2 存儲存儲管理管理任務(wù)任務(wù)v操作系統(tǒng)須占用內(nèi)存一部分存儲空間存放自身的操作系統(tǒng)須占用內(nèi)存一部分存儲空間存放自身的程序、數(shù)據(jù)、管理信息以及與硬件接口信息等，程序、數(shù)據(jù)、管理信息以及與硬件接口信息等，一般稱這部分內(nèi)存空間為系統(tǒng)區(qū)。系統(tǒng)區(qū)外的其一般稱這部分內(nèi)存空間

2、為系統(tǒng)區(qū)。系統(tǒng)區(qū)外的其余內(nèi)存空間存放用戶的程序和數(shù)據(jù)，稱為用戶區(qū)。余內(nèi)存空間存放用戶的程序和數(shù)據(jù)，稱為用戶區(qū)。存儲管理主要是對用戶區(qū)進(jìn)行管理，它包括以下存儲管理主要是對用戶區(qū)進(jìn)行管理，它包括以下4 4項(xiàng)任務(wù)項(xiàng)任務(wù)。 （1 1）內(nèi)存分配和回收）內(nèi)存分配和回收 （2 2）地址變換）地址變換 （3 3）內(nèi)存保護(hù)）內(nèi)存保護(hù) （4 4）內(nèi)存擴(kuò)充）內(nèi)存擴(kuò)充55.1.3 存儲存儲管理管理目標(biāo)目標(biāo)(1)內(nèi)存結(jié)構(gòu)細(xì)節(jié)對于用戶和用戶程序要透明。在高內(nèi)存結(jié)構(gòu)細(xì)節(jié)對于用戶和用戶程序要透明。在高級程序設(shè)計(jì)語言和匯編語言中將源程序和目標(biāo)程級程序設(shè)計(jì)語言和匯編語言中將源程序和目標(biāo)程序進(jìn)行分離，源程序獨(dú)立于內(nèi)存物理地址。序進(jìn)

3、行分離，源程序獨(dú)立于內(nèi)存物理地址。(2)提高內(nèi)存的利用率，解決大程序和小內(nèi)存之間的提高內(nèi)存的利用率，解決大程序和小內(nèi)存之間的矛盾。通過對存儲空間采取不同的管理方式，解矛盾。通過對存儲空間采取不同的管理方式，解決內(nèi)存管理中的碎片問題，提高內(nèi)存利用率。決內(nèi)存管理中的碎片問題，提高內(nèi)存利用率。(3)為用戶程序完成程序裝入。編譯程序產(chǎn)生可執(zhí)行為用戶程序完成程序裝入。編譯程序產(chǎn)生可執(zhí)行程序時(shí)，在可執(zhí)行目標(biāo)程序中生成地址重定位所程序時(shí)，在可執(zhí)行目標(biāo)程序中生成地址重定位所需信息，例如程序長度、數(shù)據(jù)區(qū)長度等。需信息，例如程序長度、數(shù)據(jù)區(qū)長度等。65.1.3 存儲存儲管理管理目標(biāo)目標(biāo)(4)解決內(nèi)存速度與解決內(nèi)存

4、速度與CPU速度不匹配問題。為了解決速度不匹配問題。為了解決內(nèi)存速度與內(nèi)存速度與CPU速度不匹配問題，引入了高速緩速度不匹配問題，引入了高速緩存。存。(5)實(shí)現(xiàn)內(nèi)存保護(hù)和共享。內(nèi)存保護(hù)是確保并發(fā)執(zhí)行實(shí)現(xiàn)內(nèi)存保護(hù)和共享。內(nèi)存保護(hù)是確保并發(fā)執(zhí)行的各個(gè)進(jìn)程在所分配的存儲區(qū)內(nèi)操作，互不干擾，的各個(gè)進(jìn)程在所分配的存儲區(qū)內(nèi)操作，互不干擾，通常由軟硬件結(jié)合方式實(shí)現(xiàn)。通常由軟硬件結(jié)合方式實(shí)現(xiàn)。75.2 程序的裝入和鏈接程序的裝入和鏈接鏈接程序裝入模塊第二步第三步裝入程序內(nèi)存第一步庫編譯程序產(chǎn)生的目標(biāo)模塊85.2.1 幾個(gè)幾個(gè)基本概念基本概念1.相對地址與相對地址空間相對地址與相對地址空間v在用匯編語言或高級語

5、言編寫的程序中，數(shù)據(jù)和在用匯編語言或高級語言編寫的程序中，數(shù)據(jù)和子程序通常用符號名進(jìn)行訪問。程序中各種符號子程序通常用符號名進(jìn)行訪問。程序中各種符號名集合所限定的空間稱作程序名字空間。名集合所限定的空間稱作程序名字空間。v經(jīng)匯編或編譯程序處理后，源程序中的各種符號經(jīng)匯編或編譯程序處理后，源程序中的各種符號名轉(zhuǎn)換成由機(jī)器指令和數(shù)據(jù)組成的目標(biāo)程序，用名轉(zhuǎn)換成由機(jī)器指令和數(shù)據(jù)組成的目標(biāo)程序，用相對地址替換符號地址。相對地址替換符號地址。v相對地址：相對于程序首指令相對地址：相對于程序首指令(通常為通常為0)的地址。的地址。v目標(biāo)程序中的邏輯地址集合稱作該程序的相對地目標(biāo)程序中的邏輯地址集合稱作該程序

6、的相對地址空間，又稱作邏輯地址空間。址空間，又稱作邏輯地址空間。95.2.1 幾個(gè)幾個(gè)基本概念基本概念2.絕對地址與絕對地址空間絕對地址與絕對地址空間v程序在內(nèi)存空間中的實(shí)際存儲單元地址稱做物理程序在內(nèi)存空間中的實(shí)際存儲單元地址稱做物理地址或絕對地址。內(nèi)存空間是指物理內(nèi)存中全部地址或絕對地址。內(nèi)存空間是指物理內(nèi)存中全部存儲單元的集合所限定的空間。物理地址的總體存儲單元的集合所限定的空間。物理地址的總體構(gòu)成運(yùn)行用戶程序的物理地址空間，又稱絕對地構(gòu)成運(yùn)行用戶程序的物理地址空間，又稱絕對地址空間。址空間。vCPU直接使用物理地址存取空間中的指令和數(shù)據(jù)，直接使用物理地址存取空間中的指令和數(shù)據(jù)，完成用戶

7、程序或系統(tǒng)程序。相對地址空間的大小完成用戶程序或系統(tǒng)程序。相對地址空間的大小由源程序決定，絕對地址空間的大小由系統(tǒng)硬件由源程序決定，絕對地址空間的大小由系統(tǒng)硬件配置決定。一個(gè)程序只有從相對地址空間裝入絕配置決定。一個(gè)程序只有從相對地址空間裝入絕對地址空間后才能運(yùn)行。對地址空間后才能運(yùn)行。105.2.1 幾個(gè)幾個(gè)基本概念基本概念3.地址重定位地址重定位v當(dāng)一個(gè)程序的相對地址裝入到與其邏輯地址空間當(dāng)一個(gè)程序的相對地址裝入到與其邏輯地址空間不一致的絕對地址空間中時(shí)，為了保證程序的正不一致的絕對地址空間中時(shí)，為了保證程序的正確運(yùn)行，必須把指令和數(shù)據(jù)的邏輯地址轉(zhuǎn)換為物確運(yùn)行，必須把指令和數(shù)據(jù)的邏輯地址轉(zhuǎn)

8、換為物理地址，這項(xiàng)工作稱為地址重定位。理地址，這項(xiàng)工作稱為地址重定位。v地址重定位通常有靜態(tài)地址重定位和動態(tài)地址重地址重定位通常有靜態(tài)地址重定位和動態(tài)地址重定位兩種方式。定位兩種方式。 靜態(tài)地址重定位靜態(tài)地址重定位 動態(tài)地址重定位動態(tài)地址重定位115.2.2 程序程序的裝入的裝入v程序的程序的裝入裝入指給程序的指令和數(shù)據(jù)分配物指給程序的指令和數(shù)據(jù)分配物理內(nèi)存空間，也常被稱為理內(nèi)存空間，也常被稱為加載加載。一個(gè)程序。一個(gè)程序要運(yùn)行必須得裝入內(nèi)存，這需要將指令和要運(yùn)行必須得裝入內(nèi)存，這需要將指令和數(shù)據(jù)的邏輯地址轉(zhuǎn)換為物理地址，即需要數(shù)據(jù)的邏輯地址轉(zhuǎn)換為物理地址，即需要進(jìn)行地址變換。進(jìn)行地址變換。v

9、根據(jù)地址變換發(fā)生時(shí)機(jī)，裝入方式分為絕根據(jù)地址變換發(fā)生時(shí)機(jī)，裝入方式分為絕對裝入方式、可重定位裝入方式和動態(tài)運(yùn)對裝入方式、可重定位裝入方式和動態(tài)運(yùn)行時(shí)裝入方式三種。行時(shí)裝入方式三種。125.2.2 程序程序的裝入的裝入1 1、絕對裝入方式、絕對裝入方式v 在可執(zhí)行文件中記錄內(nèi)存地址，裝入時(shí)直接定位在上述在可執(zhí)行文件中記錄內(nèi)存地址，裝入時(shí)直接定位在上述( (即文件中記錄的地址即文件中記錄的地址) )內(nèi)存地址。內(nèi)存地址。v 優(yōu)點(diǎn)：裝入過程簡單。優(yōu)點(diǎn)：裝入過程簡單。v 缺點(diǎn)：過于依賴于缺點(diǎn)：過于依賴于硬件結(jié)構(gòu)，不適于多道硬件結(jié)構(gòu)，不適于多道程序系統(tǒng)。程序系統(tǒng)。135.2.2 程序程序的裝入的裝入2、可

10、重定位裝入方式、可重定位裝入方式v當(dāng)一個(gè)地址裝入與其地址空間不一致的存儲當(dāng)一個(gè)地址裝入與其地址空間不一致的存儲空間中，就得要進(jìn)行地址變換。也就是說將空間中，就得要進(jìn)行地址變換。也就是說將虛地址映射為內(nèi)存地址，把這種作法叫做虛地址映射為內(nèi)存地址，把這種作法叫做地地址重定位或地址映射。址重定位或地址映射。v在在裝入裝入一個(gè)作業(yè)時(shí)，把作業(yè)中的指令相對地一個(gè)作業(yè)時(shí)，把作業(yè)中的指令相對地址址全部轉(zhuǎn)換全部轉(zhuǎn)換為絕對地址（地址轉(zhuǎn)換工作是在為絕對地址（地址轉(zhuǎn)換工作是在作業(yè)執(zhí)行前集中一次完成的）在作業(yè)執(zhí)行過作業(yè)執(zhí)行前集中一次完成的）在作業(yè)執(zhí)行過程中就無須再進(jìn)行地址轉(zhuǎn)換工作。又稱程中就無須再進(jìn)行地址轉(zhuǎn)換工作。又稱

11、靜態(tài)靜態(tài)重定位裝入方式。重定位裝入方式。145.2.2 程序程序的裝入的裝入2、可重定位裝入方式、可重定位裝入方式v優(yōu)點(diǎn)：不需硬件支持，優(yōu)點(diǎn)：不需硬件支持，可以裝入有限多道程序可以裝入有限多道程序（如（如MS DOS中的中的TSR）。）。v缺點(diǎn)：一個(gè)程序通常需缺點(diǎn)：一個(gè)程序通常需要占用連續(xù)的要占用連續(xù)的 內(nèi)存空內(nèi)存空間，程序裝間，程序裝 入內(nèi)存后入內(nèi)存后不能移動。不能移動。 不易實(shí)現(xiàn)不易實(shí)現(xiàn)共享。共享。155.2.2 程序程序的裝入的裝入3、動態(tài)運(yùn)行時(shí)裝入方式、動態(tài)運(yùn)行時(shí)裝入方式v可重定位裝入方式雖然可用于可重定位裝入方式雖然可用于多道程序系統(tǒng)多道程序系統(tǒng)，但程，但程序執(zhí)行期間如果在內(nèi)存中發(fā)生

12、移動，則程序的物理序執(zhí)行期間如果在內(nèi)存中發(fā)生移動，則程序的物理地址都發(fā)生改變，須修改全部物理地址，否則程序地址都發(fā)生改變，須修改全部物理地址，否則程序?qū)o法正確執(zhí)行。所以，采用可重定位方式把程序?qū)o法正確執(zhí)行。所以，采用可重定位方式把程序裝入內(nèi)存后，程序在內(nèi)存中一般不再移動。裝入內(nèi)存后，程序在內(nèi)存中一般不再移動。v但實(shí)際應(yīng)用中，程序在內(nèi)存中的位置可能經(jīng)常需要但實(shí)際應(yīng)用中，程序在內(nèi)存中的位置可能經(jīng)常需要改變。改變。v動態(tài)運(yùn)行時(shí)裝入方式是在動態(tài)運(yùn)行時(shí)裝入方式是在CPU執(zhí)行訪問指令執(zhí)行訪問指令時(shí)，時(shí)，才將要訪問的程序或數(shù)據(jù)的邏輯地址轉(zhuǎn)換為物理地才將要訪問的程序或數(shù)據(jù)的邏輯地址轉(zhuǎn)換為物理地址。址。16

13、5.2.2 程序程序的裝入的裝入3、動態(tài)運(yùn)行時(shí)裝入方式、動態(tài)運(yùn)行時(shí)裝入方式v動態(tài)運(yùn)行時(shí)裝入方式的優(yōu)點(diǎn)是操作系統(tǒng)可將一個(gè)動態(tài)運(yùn)行時(shí)裝入方式的優(yōu)點(diǎn)是操作系統(tǒng)可將一個(gè)程序離散地存放在內(nèi)存空間。程序離散地存放在內(nèi)存空間。v在在程序的整個(gè)執(zhí)行期間，允許程序在內(nèi)存中改變程序的整個(gè)執(zhí)行期間，允許程序在內(nèi)存中改變位置位置。v這種加載方式有利于提高內(nèi)存利用率，也為實(shí)現(xiàn)這種加載方式有利于提高內(nèi)存利用率，也為實(shí)現(xiàn)虛擬存儲器提供了基礎(chǔ)。虛擬存儲器提供了基礎(chǔ)。v動態(tài)運(yùn)行時(shí)裝入方式的缺點(diǎn)是需要硬件支持，操動態(tài)運(yùn)行時(shí)裝入方式的缺點(diǎn)是需要硬件支持，操作系統(tǒng)實(shí)現(xiàn)較為復(fù)雜。作系統(tǒng)實(shí)現(xiàn)較為復(fù)雜。17動態(tài)地址重定位示意圖動態(tài)地址重定

14、位示意圖 1500 12345Load A 500 內(nèi)存空間內(nèi)存空間5001000+ VR BR500100 12345Load A 500 0 虛擬空間（作業(yè)地址空間）虛擬空間（作業(yè)地址空間）.3動態(tài)運(yùn)行時(shí)裝入方式動態(tài)運(yùn)行時(shí)裝入方式185.2.3 程序程序的鏈接的鏈接v根據(jù)鏈接時(shí)間的不同，可把鏈接分成如下三根據(jù)鏈接時(shí)間的不同，可把鏈接分成如下三種：種：(1) 靜態(tài)鏈接靜態(tài)鏈接(2) 裝入時(shí)動態(tài)鏈接裝入時(shí)動態(tài)鏈接(3) 運(yùn)行時(shí)動態(tài)鏈接運(yùn)行時(shí)動態(tài)鏈接191靜態(tài)鏈接方式靜態(tài)鏈接方式(Static Linking)p在程序運(yùn)行之前，先將各目標(biāo)模塊及它們在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫函數(shù)

15、，鏈接成一個(gè)完整的裝配模所需的庫函數(shù)，鏈接成一個(gè)完整的裝配模塊，以后塊，以后不再拆開不再拆開。我們把這種。我們把這種事先事先進(jìn)行進(jìn)行鏈接的方式稱為靜態(tài)鏈接方式。鏈接的方式稱為靜態(tài)鏈接方式。p鏈接時(shí)需要進(jìn)行下面的修改：鏈接時(shí)需要進(jìn)行下面的修改：201靜態(tài)鏈接方式靜態(tài)鏈接方式(Static Linking)(1) 對相對地址進(jìn)行修改。在由編譯程序所產(chǎn)生的所對相對地址進(jìn)行修改。在由編譯程序所產(chǎn)生的所有目標(biāo)模塊中，使用的都是相對地址，其起始地有目標(biāo)模塊中，使用的都是相對地址，其起始地址都為址都為0，每個(gè)模塊中的地址都是相對于起始地址，每個(gè)模塊中的地址都是相對于起始地址計(jì)算的。計(jì)算的。 (2) 變換外部

16、調(diào)用符號。將每個(gè)模塊中所用的外部調(diào)變換外部調(diào)用符號。將每個(gè)模塊中所用的外部調(diào)用符號也都變換為相對地址，如下圖所示。這種用符號也都變換為相對地址，如下圖所示。這種先進(jìn)行鏈接所形成的一個(gè)完整的裝入模塊，又稱先進(jìn)行鏈接所形成的一個(gè)完整的裝入模塊，又稱為為可執(zhí)行文件可執(zhí)行文件。通常都不再拆開它，要運(yùn)行時(shí)可。通常都不再拆開它，要運(yùn)行時(shí)可直接將它裝入內(nèi)存。這種事先進(jìn)行鏈接，以后不直接將它裝入內(nèi)存。這種事先進(jìn)行鏈接，以后不再拆開的鏈接方式，稱為再拆開的鏈接方式，稱為靜態(tài)鏈接靜態(tài)鏈接方式。方式。21模塊模塊ACALL B；Return；0L-15.2.3 程序程序的鏈接的鏈接模塊模塊BCALL C；Retur

17、n；0M-1模塊模塊CReturn；0N-1(a) 目標(biāo)模塊目標(biāo)模塊模塊模塊AJMP L；Return；0L-1模塊模塊BJMP L+M；Return；LL+M-1模塊模塊CReturn；L+ML+M+N-1(b) 裝入模塊裝入模塊222裝入時(shí)動態(tài)鏈接裝入時(shí)動態(tài)鏈接(Load-time Dynamic Linking)v這是指將用戶源程序編譯后所得到的一組目標(biāo)模這是指將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接邊裝入邊鏈接的鏈接方的鏈接方式。式。v用戶源程序經(jīng)編譯后所得的目標(biāo)模塊，是在裝入用戶源程序經(jīng)編譯后所得的目標(biāo)模塊，是在裝入內(nèi)存時(shí)邊裝入邊鏈

18、接的，即在裝入一個(gè)目標(biāo)模塊內(nèi)存時(shí)邊裝入邊鏈接的，即在裝入一個(gè)目標(biāo)模塊時(shí)，若發(fā)生一個(gè)外部模塊調(diào)用事件，將引起裝入時(shí)，若發(fā)生一個(gè)外部模塊調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存，還要修改目標(biāo)模塊中的相對地址。存，還要修改目標(biāo)模塊中的相對地址。v裝入時(shí)動態(tài)鏈接方式有以下優(yōu)點(diǎn)：裝入時(shí)動態(tài)鏈接方式有以下優(yōu)點(diǎn)：(1) 便于修改和更新。便于修改和更新。(2) 便于實(shí)現(xiàn)對目標(biāo)模塊的共享。便于實(shí)現(xiàn)對目標(biāo)模塊的共享。233運(yùn)行時(shí)動態(tài)鏈接運(yùn)行時(shí)動態(tài)鏈接(Run-time Dynamic Linking)v在許多情況下，應(yīng)用程序在運(yùn)行時(shí)，每次要運(yùn)行在許

19、多情況下，應(yīng)用程序在運(yùn)行時(shí)，每次要運(yùn)行的模塊可能是不相同的。的模塊可能是不相同的。v但由于事先無法知道本次要運(yùn)行哪些模塊，故只但由于事先無法知道本次要運(yùn)行哪些模塊，故只能是將所有可能要運(yùn)行到的模塊都全部裝入內(nèi)存能是將所有可能要運(yùn)行到的模塊都全部裝入內(nèi)存，并在裝入時(shí)全部鏈接在一起。，并在裝入時(shí)全部鏈接在一起。v顯然這是低效的。顯然這是低效的。v運(yùn)行時(shí)動態(tài)鏈接運(yùn)行時(shí)動態(tài)鏈接方式，是將對某些目標(biāo)模塊的鏈方式，是將對某些目標(biāo)模塊的鏈接推遲到程序執(zhí)行時(shí)需要該接推遲到程序執(zhí)行時(shí)需要該(目標(biāo)目標(biāo))模塊時(shí)，才對模塊時(shí)，才對它進(jìn)行的鏈接，亦即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一它進(jìn)行的鏈接，亦即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被

20、調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。上。245.3 連續(xù)分配方式連續(xù)分配方式 連續(xù)分配方式是指為用戶進(jìn)程分配連連續(xù)分配方式是指為用戶進(jìn)程分配連續(xù)內(nèi)存空間的內(nèi)存管理方式。早期操作系續(xù)內(nèi)存空間的內(nèi)存管理方式。早期操作系統(tǒng)都是采用連續(xù)分配方式管理內(nèi)存。連續(xù)統(tǒng)都是采用連續(xù)分配方式管理內(nèi)存。連續(xù)分配方式通常分為：單一連續(xù)分配、固定分配方式通常分為：單一連續(xù)分配、固定分區(qū)分配、可變分區(qū)分配、動態(tài)可重定位分區(qū)分配、可變分區(qū)分配、動態(tài)可重定位分區(qū)分配等分區(qū)分配等255.3.1 單

21、一連續(xù)分配單一連續(xù)分配v單一連續(xù)分配方式是最簡單的一種存儲管理方式，單一連續(xù)分配方式是最簡單的一種存儲管理方式，只能用于單用戶、單任務(wù)的操作系統(tǒng)中。在此方只能用于單用戶、單任務(wù)的操作系統(tǒng)中。在此方式中，把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分。式中，把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分。v系統(tǒng)區(qū)僅提供給操作系統(tǒng)使用；用戶區(qū)是指除系系統(tǒng)區(qū)僅提供給操作系統(tǒng)使用；用戶區(qū)是指除系統(tǒng)區(qū)之外的全部內(nèi)存空間，提供給用戶作業(yè)使用，統(tǒng)區(qū)之外的全部內(nèi)存空間，提供給用戶作業(yè)使用，一次只允許一個(gè)作業(yè)進(jìn)入內(nèi)存。作業(yè)往往只占用一次只允許一個(gè)作業(yè)進(jìn)入內(nèi)存。作業(yè)往往只占用戶區(qū)的一部分，其余部分空閑，內(nèi)存利用率較低。戶區(qū)的一部分，其余部分空閑

22、，內(nèi)存利用率較低。v單一連續(xù)分配存儲管理方式只適用于程序的絕對單一連續(xù)分配存儲管理方式只適用于程序的絕對裝入。裝入。265.3.2 固定分區(qū)分配固定分區(qū)分配v 基本思想：基本思想：把內(nèi)存劃分成若干個(gè)把內(nèi)存劃分成若干個(gè)大小固定，個(gè)數(shù)固定大小固定，個(gè)數(shù)固定的存儲區(qū)域，每個(gè)存的存儲區(qū)域，每個(gè)存儲區(qū)域稱為一個(gè)分區(qū)，儲區(qū)域稱為一個(gè)分區(qū)，每個(gè)分區(qū)中裝入一道每個(gè)分區(qū)中裝入一道作業(yè)，每個(gè)作業(yè)只裝作業(yè)，每個(gè)作業(yè)只裝入一個(gè)分區(qū)中。入一個(gè)分區(qū)中。20K28K60K124K256KOS進(jìn)程進(jìn)程A（6K）進(jìn)程進(jìn)程B（25K）進(jìn)程進(jìn)程C（36K）內(nèi)存狀態(tài)內(nèi)存狀態(tài)275.3.2 固定分區(qū)分配固定分區(qū)分配1. 劃分分區(qū)的方法

23、劃分分區(qū)的方法 分區(qū)大小相等，即所有內(nèi)存分區(qū)大小相等。其缺分區(qū)大小相等，即所有內(nèi)存分區(qū)大小相等。其缺點(diǎn)是當(dāng)分區(qū)太大時(shí)，會造成內(nèi)存空間浪費(fèi)；當(dāng)點(diǎn)是當(dāng)分區(qū)太大時(shí)，會造成內(nèi)存空間浪費(fèi)；當(dāng)分區(qū)太小時(shí)，會造成大作業(yè)無法運(yùn)行。它主要分區(qū)太小時(shí)，會造成大作業(yè)無法運(yùn)行。它主要適用于一臺計(jì)算機(jī)控制多個(gè)相同對象的場合。適用于一臺計(jì)算機(jī)控制多個(gè)相同對象的場合。 分區(qū)大小不等，即所有內(nèi)存分區(qū)大小不等?？梢苑謪^(qū)大小不等，即所有內(nèi)存分區(qū)大小不等?？梢园褍?nèi)存劃分成多個(gè)較小分區(qū)、適量中等分區(qū)及把內(nèi)存劃分成多個(gè)較小分區(qū)、適量中等分區(qū)及少量大分區(qū)，以適應(yīng)不同程序的需求。少量大分區(qū)，以適應(yīng)不同程序的需求。285.3.2 固定分區(qū)分

24、配固定分區(qū)分配2. 內(nèi)存的分配與回收內(nèi)存的分配與回收v為了便于內(nèi)存分配，通常將分區(qū)按為了便于內(nèi)存分配，通常將分區(qū)按大小進(jìn)行排隊(duì)大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括，并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括每個(gè)分區(qū)的起始地址、大小及狀態(tài)每個(gè)分區(qū)的起始地址、大小及狀態(tài)(是否已分配是否已分配)，見下圖，見下圖a所示。所示。v當(dāng)有一用戶程序要裝入時(shí)，由內(nèi)存分配程序檢索當(dāng)有一用戶程序要裝入時(shí)，由內(nèi)存分配程序檢索該表，從中找出一個(gè)能滿足要求的、尚未分配的該表，從中找出一個(gè)能滿足要求的、尚未分配的分區(qū)，將之分配給該程序，然后將該表項(xiàng)中的狀分區(qū)，將之分配給該程序，然后將該表項(xiàng)中的狀態(tài)置為態(tài)置

25、為“已分配已分配”；v若未找到大小足夠的分區(qū)，則拒絕為該用戶程序若未找到大小足夠的分區(qū)，則拒絕為該用戶程序分配內(nèi)存。存儲空間分配情況如下圖分配內(nèi)存。存儲空間分配情況如下圖b所示。所示。2920K28K60K124K256K5.3.2 固定分區(qū)分配固定分區(qū)分配OS進(jìn)程進(jìn)程A（6K）進(jìn)程進(jìn)程B（25K）進(jìn)程進(jìn)程C（36K）（a）分區(qū)說明表）分區(qū)說明表（b）內(nèi)存狀態(tài)）內(nèi)存狀態(tài)區(qū)號區(qū)號分區(qū)長度分區(qū)長度起始地起始地址址狀態(tài)狀態(tài)1 18K8K20K20K已分配已分配2 232K32K28K28K已分配已分配3 364K64K60K60K已分配已分配4 4132K132K124K124K未分配未分配圖圖 固

26、定分區(qū)使用表固定分區(qū)使用表 305.3.2 固定分區(qū)分配固定分區(qū)分配v當(dāng)用戶程序要裝入執(zhí)行時(shí)當(dāng)用戶程序要裝入執(zhí)行時(shí),通過請求表通過請求表提出內(nèi)存分配要求和所要求的內(nèi)存空提出內(nèi)存分配要求和所要求的內(nèi)存空間大小。從分區(qū)說明表中查詢，從中間大小。從分區(qū)說明表中查詢，從中找出一個(gè)大小滿足要求的空閑分區(qū)，找出一個(gè)大小滿足要求的空閑分區(qū)，并將其分配給申請者。并將其分配給申請者。v 固定分區(qū)的回收，只需將對應(yīng)的分區(qū)固定分區(qū)的回收，只需將對應(yīng)的分區(qū)狀態(tài)置為未使用即可。狀態(tài)置為未使用即可。31要求要求Xk大小分區(qū)大小分區(qū)取分區(qū)說明表第一項(xiàng)取分區(qū)說明表第一項(xiàng)狀態(tài)位置正在使用狀態(tài)位置正在使用取下一表項(xiàng)取下一表項(xiàng)無法

27、分配無法分配該分區(qū)空閑？該分區(qū)空閑？分區(qū)長度分區(qū)長度Xk?表結(jié)束？表結(jié)束？返回分區(qū)號返回分區(qū)號否否否否否否是是是是是是圖圖5.10 5.10 固定分區(qū)分配算法固定分區(qū)分配算法325.3.2 固定分區(qū)分配固定分區(qū)分配3. 地址變換地址變換v 固定分區(qū)存儲的地址變換即可采用靜態(tài)重固定分區(qū)存儲的地址變換即可采用靜態(tài)重定位，也可采用動態(tài)重定位。定位，也可采用動態(tài)重定位。335.3.2 固定分區(qū)分配固定分區(qū)分配v優(yōu)點(diǎn)：優(yōu)點(diǎn)： 實(shí)現(xiàn)簡單、開銷小實(shí)現(xiàn)簡單、開銷小v 缺點(diǎn)：缺點(diǎn)： 必須預(yù)先能夠估計(jì)作業(yè)要占用的空間，必須預(yù)先能夠估計(jì)作業(yè)要占用的空間，分區(qū)總數(shù)固定，限制了并發(fā)作業(yè)的的數(shù)分區(qū)總數(shù)固定，限制了并發(fā)作業(yè)

28、的的數(shù)目；目； 內(nèi)碎片（占用分區(qū)之內(nèi)未被利用的空間內(nèi)碎片（占用分區(qū)之內(nèi)未被利用的空間）造成浪費(fèi)）造成浪費(fèi)345.3.3 可變分區(qū)分配可變分區(qū)分配v 可變分區(qū)的原理可變分區(qū)的原理v固定分區(qū)主存利用率不高，使用起來不靈活，固定分區(qū)主存利用率不高，使用起來不靈活，所以出現(xiàn)了可變分區(qū)的管理技術(shù)。所以出現(xiàn)了可變分區(qū)的管理技術(shù)。v動態(tài)分區(qū)原則：存儲空間的劃分是在作業(yè)裝入動態(tài)分區(qū)原則：存儲空間的劃分是在作業(yè)裝入時(shí)進(jìn)行的。從可用的自由存儲空間內(nèi)，劃出一時(shí)進(jìn)行的。從可用的自由存儲空間內(nèi)，劃出一個(gè)大小正好等于作業(yè)大小的存儲區(qū)，并分配給個(gè)大小正好等于作業(yè)大小的存儲區(qū)，并分配給這一作業(yè)。這一作業(yè)。v動態(tài)分區(qū)，在系統(tǒng)初

29、啟時(shí)，除了操作系統(tǒng)中常動態(tài)分區(qū)，在系統(tǒng)初啟時(shí)，除了操作系統(tǒng)中常駐內(nèi)存部分之外，只有一個(gè)空閑分區(qū)。駐內(nèi)存部分之外，只有一個(gè)空閑分區(qū)。355.3.3 可變分區(qū)分配可變分區(qū)分配進(jìn)程進(jìn)程 A A（8K8K）進(jìn)程進(jìn)程 D D（124K124K）進(jìn)程進(jìn)程 B B（16K16K）進(jìn)程進(jìn)程 C C（64K64K）OSOS進(jìn)程進(jìn)程A(8K)A(8K)進(jìn)程進(jìn)程B(16K)B(16K)進(jìn)程進(jìn)程C(64K)C(64K)進(jìn)程進(jìn)程D(124K)D(124K)OSOS進(jìn)程進(jìn)程A(8K)A(8K)進(jìn)程進(jìn)程B(16K)B(16K)進(jìn)程進(jìn)程C(64K)C(64K)OSOS進(jìn)程進(jìn)程A(8K)A(8K)進(jìn)程進(jìn)程B(16K)B(16K

30、)OSOS進(jìn)程進(jìn)程A(8K)A(8K)36內(nèi)存分配變化過程內(nèi)存分配變化過程OSA（8K）8K空閑區(qū)空閑區(qū)B（16K）E（50K）D（124K）14K空閑區(qū)空閑區(qū)F（16K）OSA（8K）8K空閑區(qū)空閑區(qū)空閑區(qū)空閑區(qū)16KE（50K）F（16K）空閑合并空閑合并124+14=138K進(jìn)程進(jìn)程E（50K）進(jìn)程進(jìn)程F（16K）進(jìn)入內(nèi)存進(jìn)入內(nèi)存進(jìn)程進(jìn)程B（16K）進(jìn)程進(jìn)程D（124K）完成完成OSA（8K）24K空閑區(qū)空閑區(qū)B（16K）C完成（完成（64K）空閑區(qū)空閑區(qū)D（124K）375.3.3 可變分區(qū)分配可變分區(qū)分配2. 可變分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)可變分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)為了便于內(nèi)存的分配與回收，需設(shè)

31、置用于記錄為了便于內(nèi)存的分配與回收，需設(shè)置用于記錄分區(qū)使用情況的數(shù)據(jù)結(jié)構(gòu)。分區(qū)使用情況的數(shù)據(jù)結(jié)構(gòu)。 空閑分區(qū)表。系統(tǒng)設(shè)置一張空閑分區(qū)表，記錄內(nèi)空閑分區(qū)表。系統(tǒng)設(shè)置一張空閑分區(qū)表，記錄內(nèi)存中每個(gè)空閑分區(qū)的序號、大小和起始地址，存中每個(gè)空閑分區(qū)的序號、大小和起始地址，每個(gè)空閑分區(qū)在空閑分區(qū)表中占一個(gè)表目。每個(gè)空閑分區(qū)在空閑分區(qū)表中占一個(gè)表目。385.3.3 可變分區(qū)分配可變分區(qū)分配2. 可變分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)可變分區(qū)分配的數(shù)據(jù)結(jié)構(gòu) 空閑分區(qū)鏈。為了實(shí)現(xiàn)對空閑分區(qū)的分配和鏈接，空閑分區(qū)鏈。為了實(shí)現(xiàn)對空閑分區(qū)的分配和鏈接，在每個(gè)空閑分區(qū)的起始單元中存儲兩個(gè)值，一在每個(gè)空閑分區(qū)的起始單元中存儲兩個(gè)值，一

32、個(gè)是空閑分區(qū)的大小，另一個(gè)是指向下一空閑個(gè)是空閑分區(qū)的大小，另一個(gè)是指向下一空閑分區(qū)的指針。分區(qū)的指針。395.3.3 可變分區(qū)分配可變分區(qū)分配2. 2. 可變分區(qū)分配的數(shù)據(jù)可變分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)已分配分區(qū)表。已分配分區(qū)表。系統(tǒng)設(shè)置系統(tǒng)設(shè)置一張已分配分區(qū)表，記一張已分配分區(qū)表，記錄內(nèi)存中每個(gè)已分配分錄內(nèi)存中每個(gè)已分配分區(qū)的大小、起始地址和區(qū)的大小、起始地址和狀態(tài)（記錄存放的作業(yè)狀態(tài)（記錄存放的作業(yè)名），每個(gè)已分配分區(qū)名），每個(gè)已分配分區(qū)在已分配分區(qū)表中占一在已分配分區(qū)表中占一個(gè)表目。個(gè)表目。起始地址起始地址 長度長度狀態(tài)狀態(tài)0K0K15K15KJ1J138K38K10K10KJ2J268K

33、68K12K12KJ3J3110K110K10K10KJ4J4已分配分區(qū)表已分配分區(qū)表405.3.3 可變分區(qū)分配可變分區(qū)分配3.常用的空閑分區(qū)分配算法有以下四種：常用的空閑分區(qū)分配算法有以下四種： 首次適應(yīng)（首次適應(yīng)（first fit）算法）算法 循環(huán)首次適應(yīng)（循環(huán)首次適應(yīng)（next fit）算法）算法 最佳適應(yīng)（最佳適應(yīng)（best fit）算法）算法 最差適應(yīng)（最差適應(yīng)（worst fit）算法）算法413動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法 首次適應(yīng)算法首次適應(yīng)算法(FF,FirstFit)v要求可用表或自由鏈按起始要求可用表或自由鏈按起始地址遞增地址遞增的次的次序排列。序排列。v從表頭查

34、詢，一旦找到大小滿足的分區(qū)就從表頭查詢，一旦找到大小滿足的分區(qū)就結(jié)束探索。結(jié)束探索。v例題：如圖所示是某一個(gè)時(shí)刻例題：如圖所示是某一個(gè)時(shí)刻J1、J2、J3、J4在在內(nèi)存中的分配情況、空閑區(qū)表和已分區(qū)表，它們內(nèi)存中的分配情況、空閑區(qū)表和已分區(qū)表，它們的長度分別是的長度分別是15KB、10KB、12KB、10KB。J5和和J6兩個(gè)新作業(yè)的長度分別為兩個(gè)新作業(yè)的長度分別為5KB和和13KB。按照。按照最先適應(yīng)算法進(jìn)行內(nèi)存分配，描述分配后內(nèi)存、最先適應(yīng)算法進(jìn)行內(nèi)存分配，描述分配后內(nèi)存、空閑區(qū)表以及已分區(qū)表的情況。空閑區(qū)表以及已分區(qū)表的情況。423動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法最先適應(yīng)算法分配前的狀態(tài)

35、最先適應(yīng)算法分配前的狀態(tài)起始地址起始地址 長度長度狀態(tài)狀態(tài)0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4已分區(qū)表已分區(qū)表0J1J4J3J21538486880110120起始地址起始地址 長度長度狀態(tài)狀態(tài)15K15K23K23K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空閑區(qū)表空閑區(qū)表J5J5和和J6J6兩個(gè)新作業(yè)的長度分別為兩個(gè)新作業(yè)的長度分別為5KB5KB和和13KB13KB。433動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法最先適應(yīng)算法分配后的狀態(tài)最先適應(yīng)算法分配后的狀態(tài)起始地

36、址起始地址長度長度狀態(tài)狀態(tài)0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J415K15K5K5KJ5J520K20K13K13KJ6J6已分區(qū)表起始地址起始地址長度長度狀態(tài)狀態(tài)33K33K5K5K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空閑區(qū)表3848110J6J1J4J3J20156880120J533J5J5和和J6J6兩個(gè)新作業(yè)的長度分別為兩個(gè)新作業(yè)的長度分別為5KB5KB和和13KB13KB。44重點(diǎn)回顧重點(diǎn)回顧v死鎖的避免：銀行家算法死鎖的避免：銀行家算法v死鎖的

37、檢測與解除死鎖的檢測與解除45重點(diǎn)回顧重點(diǎn)回顧v相對地址與相對地址空間相對地址與相對地址空間v絕對地址與絕對地址空間絕對地址與絕對地址空間v地址重定位地址重定位46重點(diǎn)回顧重點(diǎn)回顧v程序程序的裝入的裝入 絕對裝入方式絕對裝入方式 可重定位裝入方式可重定位裝入方式 動態(tài)運(yùn)行時(shí)裝入方式動態(tài)運(yùn)行時(shí)裝入方式v程序鏈接程序鏈接 (1) (1) 靜態(tài)鏈接靜態(tài)鏈接 (2) (2) 裝入時(shí)動態(tài)鏈接裝入時(shí)動態(tài)鏈接(3) (3) 運(yùn)行時(shí)動態(tài)鏈接運(yùn)行時(shí)動態(tài)鏈接47重點(diǎn)回顧重點(diǎn)回顧v連續(xù)分配方式：是指為用戶進(jìn)程分配連續(xù)連續(xù)分配方式：是指為用戶進(jìn)程分配連續(xù)內(nèi)存空間的內(nèi)存管理方式。內(nèi)存空間的內(nèi)存管理方式。 單一連續(xù)分配單

38、一連續(xù)分配 固定分區(qū)分配：分區(qū)大小和個(gè)數(shù)固定固定分區(qū)分配：分區(qū)大小和個(gè)數(shù)固定 可變分區(qū)分配：分區(qū)大小和個(gè)數(shù)隨內(nèi)存的動態(tài)可變分區(qū)分配：分區(qū)大小和個(gè)數(shù)隨內(nèi)存的動態(tài)分配和回收變化分配和回收變化48重點(diǎn)回顧重點(diǎn)回顧 可變分區(qū)分配算法可變分區(qū)分配算法 首次適應(yīng)（首次適應(yīng)（first fit）算法）算法49從該空閑區(qū)中截取所需從該空閑區(qū)中截取所需大小，修改調(diào)整可用表大小，修改調(diào)整可用表從空閑區(qū)表第一從空閑區(qū)表第一表目順序查找表目順序查找從可用表中移去該從可用表中移去該表目，調(diào)整可用表表目，調(diào)整可用表取下一表項(xiàng)取下一表項(xiàng)無法分配無法分配該該 空閑區(qū)空閑區(qū)長度長度SIZE？該該 空閑區(qū)空閑區(qū)長度長度=SIZE

39、？表目查完？表目查完？返回分配起始地址返回分配起始地址否否否否是是是是是是否否圖圖 最先適應(yīng)算法最先適應(yīng)算法請求請求SIZESIZE大小的分區(qū)大小的分區(qū)503動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法動態(tài)分區(qū)存儲管理可采用多動態(tài)分區(qū)存儲管理可采用多種數(shù)據(jù)結(jié)構(gòu)對內(nèi)存進(jìn)行管理種數(shù)據(jù)結(jié)構(gòu)對內(nèi)存進(jìn)行管理v每個(gè)空閑區(qū)用每個(gè)空閑區(qū)用map數(shù)據(jù)結(jié)數(shù)據(jù)結(jié)構(gòu)構(gòu)vstrut mapvunsigned m_size;vchar * m_addr;vstruct map cornmapN; m_addrm_addrm_sizem_sizem_addrm_addrm_sizem_size空閑區(qū)空閑區(qū)已分配已分配空閑區(qū)空閑區(qū)已分配

40、已分配空閑區(qū)空閑區(qū)已分配已分配513動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法 最先適應(yīng)法最先適應(yīng)法vChar *malloc(struct map *mp,int size) /空閑表指針，空閑表指針，作業(yè)大小作業(yè)大小vint regint;vstruct map *bp;v/從從mp開始，只要開始，只要size不等于不等于0，逐個(gè)地址檢查，逐個(gè)地址檢查 m_addrm_addrm_sizem_sizem_addrm_addrm_sizem_size空閑區(qū)空閑區(qū)已分配已分配空閑區(qū)空閑區(qū)已分配已分配空閑區(qū)空閑區(qū)已分配已分配mp52for(bp=mp;bp-m_size;bp+) if(bp-m_size

41、=size) regint=bp-m_addr; bp-m_addr+=size;if(bp-m_size-=size)=0)/賦值并判斷賦值并判斷do bp+; (bp-1)-m_addr=bp-m_addr;while(bp-1)-m_size=bp-m_size);return(regint); return(0); m_addrm_addrm_sizem_sizem_addrm_addrm_sizem_size空閑區(qū)空閑區(qū)已分配已分配空閑區(qū)空閑區(qū)已分配已分配空閑區(qū)空閑區(qū)已分配已分配mp533動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法 最先適應(yīng)算法最先適應(yīng)算法缺點(diǎn)：缺點(diǎn)： 由于查找總是從表首開始，

42、前面的空閑區(qū)由于查找總是從表首開始，前面的空閑區(qū)被分割的很小時(shí)，能滿足分配要求的可能被分割的很小時(shí)，能滿足分配要求的可能性就越小，查找次數(shù)越多性就越小，查找次數(shù)越多 碎片問題碎片問題543動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法最佳適應(yīng)算法最佳適應(yīng)算法(BF,Best Fit)v要求可用表（空閑表）或自由鏈按分區(qū)要求可用表（空閑表）或自由鏈按分區(qū)大小遞增大小遞增的次序排列。的次序排列。v從表頭查詢，一旦找到大小滿足的分區(qū)從表頭查詢，一旦找到大小滿足的分區(qū)就結(jié)束探索就結(jié)束探索。553動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法分配前的狀態(tài)分配前的狀態(tài)起始地址起始地址長度長度狀態(tài)狀態(tài)0K0K15K15KJ1J138K

43、38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4已分區(qū)表起始地址起始地址 長度長度 狀態(tài)狀態(tài)15K15K23K23K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空閑區(qū)表J5J5和和J6J6兩個(gè)新作業(yè)的長度分別為兩個(gè)新作業(yè)的長度分別為5KB5KB和和13KB13KB。起始地址起始地址 長度長度 狀態(tài)狀態(tài)48K48K20K20K未分配未分配15K15K23K23K未分配未分配80K80K30K30K未分配未分配空閑區(qū)表0J1J4J3J2153848688011012056 最佳適應(yīng)算法分配后的狀態(tài)最佳適應(yīng)算法分配

44、后的狀態(tài)起始地址起始地址長度長度狀態(tài)狀態(tài)0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J448K48K5K5KJ5J553K53K13K13KJ6J6已分區(qū)表起始地址起始地址長度長度狀態(tài)狀態(tài)66K66K2K2K未分配未分配15K15K23K23K未分配未分配80K80K30K30K未分配未分配空閑區(qū)表J6J3J1J4J201538486880110120J566J5J5和和J6J6兩個(gè)新作業(yè)的長度分別為兩個(gè)新作業(yè)的長度分別為5KB5KB和和13KB13KB。3動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法573動態(tài)分區(qū)分配算法動態(tài)

45、分區(qū)分配算法最佳適應(yīng)法最佳適應(yīng)法v優(yōu)點(diǎn)：優(yōu)點(diǎn)： 分配后所剩余的空白塊會最小分配后所剩余的空白塊會最小 平均而言，只要查找一半的表格便能找到平均而言，只要查找一半的表格便能找到v缺點(diǎn)：缺點(diǎn)： 由于空閑區(qū)是按大小而不是按地址排序，因此由于空閑區(qū)是按大小而不是按地址排序，因此釋放時(shí)，要在整個(gè)鏈表上搜索地址相鄰的空閑區(qū)釋放時(shí)，要在整個(gè)鏈表上搜索地址相鄰的空閑區(qū) 空閑區(qū)分配后剩余部分成為碎片空閑區(qū)分配后剩余部分成為碎片583動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法最差適應(yīng)算法最差適應(yīng)算法(WF)v按空閑區(qū)按空閑區(qū)大小遞減大小遞減的順序組成空閑區(qū)可用表的順序組成空閑區(qū)可用表或自由鏈?；蜃杂涉?。v最壞適應(yīng)算法的思想

46、與最佳適應(yīng)算法相反，最壞適應(yīng)算法的思想與最佳適應(yīng)算法相反，將所有的空白分區(qū)按容量遞減的順序排列，最將所有的空白分區(qū)按容量遞減的順序排列，最前面的最大的空閑區(qū)就是找到的分區(qū)。該算法前面的最大的空閑區(qū)就是找到的分區(qū)。該算法是取所有空閑區(qū)中最大的一塊，把剩余的塊再是取所有空閑區(qū)中最大的一塊，把剩余的塊再變成一個(gè)新小一點(diǎn)的空閑區(qū)。變成一個(gè)新小一點(diǎn)的空閑區(qū)。59分配前的狀態(tài)分配前的狀態(tài)起始地址起始地址長度長度狀態(tài)狀態(tài)0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J4已分區(qū)表起始地址起始地址長度長度 狀態(tài)狀態(tài)15K15K23K2

47、3K未分配未分配48K48K20K20K未分配未分配80K80K30K30K未分配未分配空閑區(qū)表J5J5和和J6J6兩個(gè)新作業(yè)的長度分別為兩個(gè)新作業(yè)的長度分別為5KB5KB和和13KB13KB。起始地址起始地址 長度長度 狀態(tài)狀態(tài)80K80K30K30K未分配未分配15K15K23K23K未分配未分配48K48K20K20K未分配未分配空閑區(qū)表0J1J4J3J2153848688011012060 最壞適應(yīng)算法分配后的狀態(tài)起始地址起始地址長度長度狀態(tài)狀態(tài)0K0K15K15KJ1J138K38K10K10KJ2J268K68K12K12KJ3J3110K110K10K10KJ4J480K80K5

48、K5KJ5J585K85K13K13KJ6J6已分區(qū)表起始地址起始地址長度長度狀態(tài)狀態(tài)15K15K23K23K未分配未分配48K48K20K20K未分配未分配98K98K12K12K未分配未分配空閑區(qū)表J5J5和和J6J6兩個(gè)新作業(yè)的長度分別為兩個(gè)新作業(yè)的長度分別為5KB5KB和和13KB13KB。1538486880110120J1J4J3J20J5J6 98613動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法最壞適應(yīng)算法最壞適應(yīng)算法v優(yōu)點(diǎn)：優(yōu)點(diǎn)： 分配時(shí)只需查找一次就可以成功分配時(shí)只需查找一次就可以成功v缺點(diǎn)：缺點(diǎn)：過早用掉大的空閑區(qū)，剩余的分區(qū)越過早用掉大的空閑區(qū)，剩余的分區(qū)越來越小來越小 ，無法運(yùn)行

49、大程序，無法運(yùn)行大程序623動態(tài)分區(qū)分配算法動態(tài)分區(qū)分配算法循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法(next fit)v該算法是由首次適應(yīng)算法演變而成的。在為進(jìn)程該算法是由首次適應(yīng)算法演變而成的。在為進(jìn)程分配內(nèi)存空間時(shí)，分配內(nèi)存空間時(shí)，不再是不再是每次都從每次都從鏈?zhǔn)祖準(zhǔn)组_始查找開始查找，而是，而是從上次找到從上次找到的空閑分區(qū)的的空閑分區(qū)的下一個(gè)下一個(gè)空閑分區(qū)空閑分區(qū)開始查找，直至找到一個(gè)能滿足要求的空閑分區(qū)開始查找，直至找到一個(gè)能滿足要求的空閑分區(qū)。v為實(shí)現(xiàn)該算法，應(yīng)設(shè)置一起始查尋指針，用于指為實(shí)現(xiàn)該算法，應(yīng)設(shè)置一起始查尋指針，用于指示下一次起始查尋的空閑分區(qū)。示下一次起始查尋的空閑分區(qū)。v該算

50、法能使內(nèi)存中的空閑分區(qū)分布得更均勻，從該算法能使內(nèi)存中的空閑分區(qū)分布得更均勻，從而減少了查找空閑分區(qū)時(shí)的開銷，但這樣會缺乏而減少了查找空閑分區(qū)時(shí)的開銷，但這樣會缺乏大的空閑分區(qū)。大的空閑分區(qū)。634動態(tài)分區(qū)時(shí)的回收與拼接動態(tài)分區(qū)時(shí)的回收與拼接當(dāng)某一個(gè)用戶作業(yè)完成釋放所占分區(qū)時(shí)，系統(tǒng)當(dāng)某一個(gè)用戶作業(yè)完成釋放所占分區(qū)時(shí)，系統(tǒng)應(yīng)進(jìn)行回收。應(yīng)進(jìn)行回收。在可變式分區(qū)中，應(yīng)該檢查回收區(qū)與內(nèi)存中前在可變式分區(qū)中，應(yīng)該檢查回收區(qū)與內(nèi)存中前后空閑區(qū)是否相鄰，后空閑區(qū)是否相鄰，若相鄰，則應(yīng)進(jìn)行合并，形成一個(gè)較大的空閑若相鄰，則應(yīng)進(jìn)行合并，形成一個(gè)較大的空閑區(qū)，并對相應(yīng)的鏈表指針進(jìn)行修改；區(qū)，并對相應(yīng)的鏈表指針進(jìn)行

51、修改；若不相鄰，應(yīng)將空閑區(qū)插入到空閑區(qū)鏈表的適若不相鄰，應(yīng)將空閑區(qū)插入到空閑區(qū)鏈表的適當(dāng)位置。當(dāng)位置。644動態(tài)分區(qū)時(shí)的回收與拼接動態(tài)分區(qū)時(shí)的回收與拼接654動態(tài)分區(qū)時(shí)的回收與拼接動態(tài)分區(qū)時(shí)的回收與拼接v釋放區(qū)鄰接的分區(qū)情況可能是：釋放區(qū)鄰接釋放區(qū)鄰接的分區(qū)情況可能是：釋放區(qū)鄰接的是另一進(jìn)程的已分配區(qū)，或者是空閑區(qū)。的是另一進(jìn)程的已分配區(qū)，或者是空閑區(qū)。v下面以首次適應(yīng)法說明了系統(tǒng)回收該進(jìn)程占下面以首次適應(yīng)法說明了系統(tǒng)回收該進(jìn)程占用區(qū)存在的四種可能情況。用區(qū)存在的四種可能情況。v設(shè)進(jìn)程的釋放區(qū)為設(shè)進(jìn)程的釋放區(qū)為R，與，與R相鄰的兩個(gè)空閑區(qū)相鄰的兩個(gè)空閑區(qū)分別為分別為F1和和F2。R的首地址送的

52、首地址送LOC，R的尾地的尾地址送址送LOC1，R的大小送的大小送SIZE。66(a)若釋放區(qū)若釋放區(qū)R與與F1相鄰接，即其低地址部分鄰相鄰接，即其低地址部分鄰接一空閑區(qū)。將接一空閑區(qū)。將R與與F1合并，合并后的空閑區(qū)合并，合并后的空閑區(qū)仍記為仍記為F1。4動態(tài)分區(qū)時(shí)的回收與拼接動態(tài)分區(qū)時(shí)的回收與拼接低地址低地址 高地址高地址空閑區(qū)空閑區(qū) F1進(jìn)程進(jìn)程 P 占用區(qū)占用區(qū)2低地址低地址 高地址高地址占用區(qū)占用區(qū)2空閑區(qū)空閑區(qū) F1(a)合并后合并后674動態(tài)分區(qū)時(shí)的回收與拼接動態(tài)分區(qū)時(shí)的回收與拼接如何判斷釋放區(qū)如何判斷釋放區(qū)R 是否與某個(gè)空閑區(qū)相鄰呢？是否與某個(gè)空閑區(qū)相鄰呢？只要從鏈?zhǔn)组_始查找即

53、可：若只要從鏈?zhǔn)组_始查找即可：若F1的首地址的首地址+F1的大小的大小=R的首地址，說明的首地址，說明R與與F1相鄰接。相鄰接。只要修改只要修改F1的大小的大小= F1的大小的大小+LOC，其它參，其它參數(shù)不變和在鏈中的位置不變。數(shù)不變和在鏈中的位置不變。684動態(tài)分區(qū)時(shí)的回收與拼接動態(tài)分區(qū)時(shí)的回收與拼接(b)若釋放區(qū)若釋放區(qū)R與與F2相鄰接，即其高地址部分鄰接一空相鄰接，即其高地址部分鄰接一空閑區(qū)。將閑區(qū)。將R與與F2合并，合并后的空閑區(qū)記仍記為合并，合并后的空閑區(qū)記仍記為F2。 判斷釋放區(qū)判斷釋放區(qū)R 是否與是否與F2空閑區(qū)相鄰，只要從鏈?zhǔn)组_空閑區(qū)相鄰，只要從鏈?zhǔn)组_始查找。始查找。 若若L

54、OC+SIZE=F2的首地址，說明的首地址，說明R與與F2相鄰接。需相鄰接。需修改修改F2的首地址的首地址=LOC，F(xiàn)2的大小的大小= F2的大小的大小+SIZE。694動態(tài)分區(qū)時(shí)的回收與拼接動態(tài)分區(qū)時(shí)的回收與拼接(b)合并后合并后低地址低地址 高地址高地址占用區(qū)占用區(qū)1 進(jìn)程進(jìn)程 P 空閑區(qū)空閑區(qū)F2低地址低地址 高地址高地址空閑區(qū)空閑區(qū)F2占用區(qū)占用區(qū)1704動態(tài)分區(qū)時(shí)的回收與拼接動態(tài)分區(qū)時(shí)的回收與拼接(c) 若釋放區(qū)若釋放區(qū)R的高、低地址部分都鄰接一個(gè)空閑區(qū)。的高、低地址部分都鄰接一個(gè)空閑區(qū)。應(yīng)將三個(gè)分區(qū)合并為一個(gè)大空閑區(qū)，并記為應(yīng)將三個(gè)分區(qū)合并為一個(gè)大空閑區(qū)，并記為F1。 先將先將R與

55、與F2合并，記為合并，記為F2。再將再將F 2與與F1合并，并將合并，并將F2從鏈中刪除。從鏈中刪除?？臻e區(qū)空閑區(qū)F1 釋放區(qū)釋放區(qū)R空閑區(qū)空閑區(qū)F2空閑區(qū)空閑區(qū)F1合并后合并后714動態(tài)分區(qū)時(shí)的回收與拼接動態(tài)分區(qū)時(shí)的回收與拼接(d)若釋放區(qū)若釋放區(qū)R上下都不鄰接空閑區(qū)，將其插入上下都不鄰接空閑區(qū)，將其插入空閑區(qū)鏈的適當(dāng)位置即可。空閑區(qū)鏈的適當(dāng)位置即可。725. 地址變換和分區(qū)保護(hù)地址變換和分區(qū)保護(hù) 地址變換地址變換 對動態(tài)分區(qū)可采用動態(tài)重定位裝入方式，程序和對動態(tài)分區(qū)可采用動態(tài)重定位裝入方式，程序和數(shù)據(jù)的地址轉(zhuǎn)換由硬件完成。數(shù)據(jù)的地址轉(zhuǎn)換由硬件完成。 硬件中設(shè)置兩個(gè)專門控制寄存器：基址寄存器

56、和硬件中設(shè)置兩個(gè)專門控制寄存器：基址寄存器和限長寄存器?；芳拇嫫鞔娣欧纸o作業(yè)使用的分區(qū)限長寄存器?；芳拇嫫鞔娣欧纸o作業(yè)使用的分區(qū)的起始地址，限長寄存器存放作業(yè)占用的分區(qū)的長的起始地址，限長寄存器存放作業(yè)占用的分區(qū)的長度。當(dāng)作業(yè)占用度。當(dāng)作業(yè)占用CPU 運(yùn)行時(shí)，操作系統(tǒng)把該區(qū)的起運(yùn)行時(shí)，操作系統(tǒng)把該區(qū)的起始地址和長度存入基址寄存器和限長寄存器。作業(yè)始地址和長度存入基址寄存器和限長寄存器。作業(yè)執(zhí)行時(shí)，硬件根據(jù)基址寄存器進(jìn)行地址轉(zhuǎn)換。執(zhí)行時(shí)，硬件根據(jù)基址寄存器進(jìn)行地址轉(zhuǎn)換。735. 地址變換和分區(qū)保護(hù)地址變換和分區(qū)保護(hù) 分區(qū)保護(hù)分區(qū)保護(hù) 基址基址/限長保護(hù)法限長保護(hù)法 保護(hù)鍵法保護(hù)鍵法 74動態(tài)

57、分區(qū)優(yōu)缺點(diǎn)動態(tài)分區(qū)優(yōu)缺點(diǎn)v優(yōu)點(diǎn)：優(yōu)點(diǎn)：內(nèi)存利用率提高，避免了內(nèi)碎片內(nèi)存利用率提高，避免了內(nèi)碎片v 缺點(diǎn)：缺點(diǎn)： 出現(xiàn)了外碎片（分區(qū)之間未被利用出現(xiàn)了外碎片（分區(qū)之間未被利用的空間）的空間）755.3.4 動態(tài)可重定位分區(qū)分配動態(tài)可重定位分區(qū)分配1.緊湊（拼接）技術(shù)緊湊（拼接）技術(shù) 緊湊（拼接）技術(shù)將內(nèi)存中的所有作業(yè)進(jìn)行緊湊（拼接）技術(shù)將內(nèi)存中的所有作業(yè)進(jìn)行移動，同時(shí)修改每個(gè)程序的起始地址，使空移動，同時(shí)修改每個(gè)程序的起始地址，使空閑區(qū)全都相鄰接。這樣把分散的多個(gè)小分區(qū)閑區(qū)全都相鄰接。這樣把分散的多個(gè)小分區(qū)拼接成一個(gè)大分區(qū)，大作業(yè)可裝入該分區(qū)。拼接成一個(gè)大分區(qū)，大作業(yè)可裝入該分區(qū)。緊湊之后要對被

58、移動作業(yè)的物理地址進(jìn)行相緊湊之后要對被移動作業(yè)的物理地址進(jìn)行相應(yīng)修改。應(yīng)修改。765.3.4 動態(tài)可重定位分區(qū)分配動態(tài)可重定位分區(qū)分配775.3.4 動態(tài)可重定位分區(qū)分配動態(tài)可重定位分區(qū)分配2.動態(tài)重定位的實(shí)現(xiàn)過程動態(tài)重定位的實(shí)現(xiàn)過程v動態(tài)可重定位分區(qū)法中加載程序時(shí)采用動態(tài)可重定位分區(qū)法中加載程序時(shí)采用動態(tài)運(yùn)行動態(tài)運(yùn)行時(shí)裝入時(shí)裝入方式，作業(yè)裝入內(nèi)存后的所有地址仍是邏方式，作業(yè)裝入內(nèi)存后的所有地址仍是邏輯地址，將邏輯地址轉(zhuǎn)換為物理地址的工作推遲輯地址，將邏輯地址轉(zhuǎn)換為物理地址的工作推遲到程序指令執(zhí)行時(shí)進(jìn)行。到程序指令執(zhí)行時(shí)進(jìn)行。v系統(tǒng)中增設(shè)一個(gè)重定位寄存器，用它來存放程序系統(tǒng)中增設(shè)一個(gè)重定位寄存

59、器，用它來存放程序或數(shù)據(jù)在內(nèi)存中的起始地址。程序執(zhí)行時(shí)，真正或數(shù)據(jù)在內(nèi)存中的起始地址。程序執(zhí)行時(shí)，真正訪問的物理地址是邏輯地址與重定位寄存器中的訪問的物理地址是邏輯地址與重定位寄存器中的地址相加而形成的。地址相加而形成的。785.3.4 動態(tài)可重定位分區(qū)分配動態(tài)可重定位分區(qū)分配795.4 基本分頁存儲管理方式基本分頁存儲管理方式5.4.1 基本概念基本概念1頁面頁面v分頁存儲管理是將一個(gè)進(jìn)程的邏輯地址空間分成分頁存儲管理是將一個(gè)進(jìn)程的邏輯地址空間分成大小相等的若干片，這樣的片被稱為頁或頁面。大小相等的若干片，這樣的片被稱為頁或頁面。程序的頁面從程序的頁面從0開始編號，稱為頁號。一般情況下開始編

60、號，稱為頁號。一般情況下，進(jìn)程長度不會剛好是頁面大小的整數(shù)倍，進(jìn)程，進(jìn)程長度不會剛好是頁面大小的整數(shù)倍，進(jìn)程的最后一頁往往裝不滿，形成頁內(nèi)碎片。的最后一頁往往裝不滿，形成頁內(nèi)碎片。v頁式存儲管理中，頁面大小應(yīng)適中。若頁面太小頁式存儲管理中，頁面大小應(yīng)適中。若頁面太小，雖可減小頁內(nèi)碎片，提高內(nèi)存利用率，但會使，雖可減小頁內(nèi)碎片，提高內(nèi)存利用率，但會使每個(gè)進(jìn)程占用較多頁面，進(jìn)程的頁表過長，增加每個(gè)進(jìn)程占用較多頁面，進(jìn)程的頁表過長，增加內(nèi)存存放頁表的開銷。反之，若頁面太大，雖可內(nèi)存存放頁表的開銷。反之，若頁面太大，雖可減小頁表長度，但會增大頁內(nèi)碎片。減小頁表長度，但會增大頁內(nèi)碎片。805.4.1 基