chapter4_存儲(chǔ)管理

1、3計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)4課程主要內(nèi)容課程主要內(nèi)容操作系統(tǒng)引論（操作系統(tǒng)引論（1章）章）進(jìn)程管理（進(jìn)程管理（2-3章）章）存儲(chǔ)管理（存儲(chǔ)管理（4章）章）設(shè)備管理（設(shè)備管理（5章）章）文件管理（文件管理（6章）章）操作系統(tǒng)接口（操作系統(tǒng)接口（7章）章）系統(tǒng)安全性（系統(tǒng)安全性（9章）章）*分布式操作系統(tǒng)分布式操作系統(tǒng)5第第4 4章章 存儲(chǔ)器管理存儲(chǔ)器管理 存儲(chǔ)管理的主要任務(wù)是為多道程序的運(yùn)行提供存儲(chǔ)管理的主要任務(wù)是為多道程序的運(yùn)行提供良好的環(huán)境，方便用戶使用存儲(chǔ)器，提高存儲(chǔ)器的良好的環(huán)境，方便用戶使用存儲(chǔ)器，提高存儲(chǔ)器的利用率以及從邏輯上擴(kuò)充存儲(chǔ)器。為此存儲(chǔ)管理應(yīng)利用率以及從邏輯上擴(kuò)充存儲(chǔ)器

2、。為此存儲(chǔ)管理應(yīng)具有以下功能具有以下功能:v實(shí)現(xiàn)內(nèi)存的分配和回收實(shí)現(xiàn)內(nèi)存的分配和回收v地址變換地址變換v“擴(kuò)充擴(kuò)充”內(nèi)存容量內(nèi)存容量v進(jìn)行存儲(chǔ)保護(hù)進(jìn)行存儲(chǔ)保護(hù)64.1存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)4.2程序的裝入和鏈接程序的裝入和鏈接4.3 連續(xù)分配存儲(chǔ)管理方式連續(xù)分配存儲(chǔ)管理方式4.4 基本分頁存儲(chǔ)管理方式基本分頁存儲(chǔ)管理方式4.5 基本分段存儲(chǔ)管理方式基本分段存儲(chǔ)管理方式第第4 4章章 存儲(chǔ)器管理存儲(chǔ)器管理4.6 虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念4.7 請求分頁存儲(chǔ)管理方式請求分頁存儲(chǔ)管理方式4.8 頁面置換算法頁面置換算法4.9 請求分段存儲(chǔ)管理方式請求分段存儲(chǔ)管理方式UNIX

3、系統(tǒng)中存儲(chǔ)器管理系統(tǒng)中存儲(chǔ)器管理本章作業(yè)本章作業(yè)74.1-4.3 教學(xué)目標(biāo)和重點(diǎn)難點(diǎn)教學(xué)目標(biāo)和重點(diǎn)難點(diǎn)目標(biāo)：目標(biāo)：1、了解一個(gè)程序從編譯、鏈接到被裝入執(zhí)行的過、了解一個(gè)程序從編譯、鏈接到被裝入執(zhí)行的過程，理解邏輯地址和物理地址的含義；程，理解邏輯地址和物理地址的含義；2、了解靜態(tài)鏈接和動(dòng)態(tài)鏈接，絕對裝入和可重定、了解靜態(tài)鏈接和動(dòng)態(tài)鏈接，絕對裝入和可重定位裝入；位裝入；3、理解幾種基本的連續(xù)分配方式，能區(qū)分是否有、理解幾種基本的連續(xù)分配方式，能區(qū)分是否有內(nèi)部碎片和外部碎片；內(nèi)部碎片和外部碎片；重點(diǎn)重點(diǎn)/難點(diǎn)：難點(diǎn)：1、內(nèi)部碎片和外部碎片（可命制單選題）、內(nèi)部碎片和外部碎片（可命制單選題）2、邏輯

4、地址和物理地址（可命制綜合應(yīng)用題）、邏輯地址和物理地址（可命制綜合應(yīng)用題）3、內(nèi)存分配策略（可命制單選題）、內(nèi)存分配策略（可命制單選題）84.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)(了解了解)n4.1.1 多級存儲(chǔ)器結(jié)構(gòu)多級存儲(chǔ)器結(jié)構(gòu) 寄存器寄存器高速緩存高速緩存主存主存磁盤緩存磁盤緩存磁盤磁盤可移動(dòng)存儲(chǔ)介質(zhì)可移動(dòng)存儲(chǔ)介質(zhì)CPU寄存器寄存器主存主存輔存輔存速度越快，價(jià)格越高，容量越小速度越快，價(jià)格越高，容量越小9n4.1.2 主存儲(chǔ)器與寄存器主存儲(chǔ)器與寄存器1、主存儲(chǔ)器：、主存儲(chǔ)器：用于保存進(jìn)程運(yùn)行時(shí)的程序和用于保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)，也稱可執(zhí)行存儲(chǔ)器。速度遠(yuǎn)低于數(shù)據(jù)，也稱可執(zhí)行存儲(chǔ)器。速度

5、遠(yuǎn)低于CPU執(zhí)行指令的速度。執(zhí)行指令的速度。2、寄存器：、寄存器：訪問速度最快，完全能與訪問速度最快，完全能與CPU協(xié)調(diào)工作。以字為單位。用于加速存儲(chǔ)器協(xié)調(diào)工作。以字為單位。用于加速存儲(chǔ)器的訪問速度。的訪問速度。4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)10n4.1.3 高速緩存和磁盤緩存高速緩存和磁盤緩存1、高速緩存：、高速緩存：容量大于或遠(yuǎn)大于寄存器，訪問容量大于或遠(yuǎn)大于寄存器，訪問速度快于主存儲(chǔ)器。根據(jù)程序執(zhí)行的局部性原理，速度快于主存儲(chǔ)器。根據(jù)程序執(zhí)行的局部性原理，將主存中一些經(jīng)常訪問的信息存放著高速緩存中，將主存中一些經(jīng)常訪問的信息存放著高速緩存中，減少訪問主存儲(chǔ)器的次數(shù)，提高程序的執(zhí)

6、行速度。減少訪問主存儲(chǔ)器的次數(shù)，提高程序的執(zhí)行速度。2、磁盤緩存：、磁盤緩存：將頻繁使用的一部分磁盤數(shù)據(jù)和將頻繁使用的一部分磁盤數(shù)據(jù)和信息，暫時(shí)存放在磁盤緩存中，可減少訪問磁盤信息，暫時(shí)存放在磁盤緩存中，可減少訪問磁盤的次數(shù)。的次數(shù)。4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)114.2 4.2 程序的裝入和鏈接程序的裝入和鏈接 一個(gè)用戶源程序要變一個(gè)用戶源程序要變?yōu)樵趦?nèi)存中可執(zhí)行的程為在內(nèi)存中可執(zhí)行的程序，通常要進(jìn)行以下處序，通常要進(jìn)行以下處理理：（1）編譯：編譯：由編譯程序由編譯程序?qū)⒂脩粼闯绦蚓幾g成若將用戶源程序編譯成若干個(gè)目標(biāo)模塊。干個(gè)目標(biāo)模塊。（2）鏈接鏈接：由鏈接程序：由鏈接程序?qū)⒛繕?biāo)

7、模塊和相應(yīng)的庫將目標(biāo)模塊和相應(yīng)的庫函數(shù)鏈接成裝入模塊。函數(shù)鏈接成裝入模塊。 （3）裝入裝入：由裝入程序：由裝入程序?qū)⒀b入模塊裝入內(nèi)存。將裝入模塊裝入內(nèi)存。庫庫目標(biāo)程序塊目標(biāo)程序塊1 1目標(biāo)程序塊目標(biāo)程序塊2 2第一步第一步鏈接程序鏈接程序裝入模塊裝入模塊第二步第二步裝入程序裝入程序第三步第三步用戶源程序用戶源程序編譯程序編譯程序在外存在外存在內(nèi)存在內(nèi)存12n4.2.1 程序的裝入程序的裝入v絕對裝入方式絕對裝入方式v可重定位裝入方式可重定位裝入方式v動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式n4.2.2 程序的鏈接程序的鏈接 根據(jù)鏈接時(shí)間的不同，可將鏈接分成三種：根據(jù)鏈接時(shí)間的不同，可將鏈接分成三種

8、：v靜態(tài)鏈接靜態(tài)鏈接v裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接v運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接4.2 4.2 程序的裝入和鏈接程序的裝入和鏈接返回目錄131 1、絕對裝入方式、絕對裝入方式n在編譯時(shí)，如果知道程序?qū)Ⅰv留在內(nèi)存的什么位置，在編譯時(shí)，如果知道程序?qū)Ⅰv留在內(nèi)存的什么位置，那么，編譯程序?qū)a(chǎn)生那么，編譯程序?qū)a(chǎn)生絕對地址的目標(biāo)代碼絕對地址的目標(biāo)代碼。絕對。絕對裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。裝入模塊被裝入內(nèi)存后，由于程序中的邏入內(nèi)存。裝入模塊被裝入內(nèi)存后，由于程序中的邏輯地址與實(shí)際內(nèi)存中的地址完全相同，故輯地址與實(shí)際內(nèi)存中的地址完全相同

9、，故不需對程不需對程序和數(shù)據(jù)的地址進(jìn)行修改序和數(shù)據(jù)的地址進(jìn)行修改。 n該裝入方式只適用于該裝入方式只適用于單道程序環(huán)境單道程序環(huán)境。14n重定位：重定位：由于一個(gè)作業(yè)裝入到與其地址空間不一致由于一個(gè)作業(yè)裝入到與其地址空間不一致的存儲(chǔ)空間所引起的，需對其有關(guān)地址部分進(jìn)行的存儲(chǔ)空間所引起的，需對其有關(guān)地址部分進(jìn)行調(diào)調(diào)整整的過程就稱為重定位（實(shí)質(zhì)是一個(gè)地址變換過程的過程就稱為重定位（實(shí)質(zhì)是一個(gè)地址變換過程/地址映射）。根據(jù)地址變換進(jìn)行的地址映射）。根據(jù)地址變換進(jìn)行的時(shí)間及采用技術(shù)手段不同手段不同，可分為，可分為靜態(tài)重定位靜態(tài)重定位和和動(dòng)態(tài)重定位動(dòng)態(tài)重定位兩類。兩類。2、可重定位裝入方式、可重定位裝入

10、方式基本概念基本概念n邏輯地址（相對地址，虛地址）邏輯地址（相對地址，虛地址）v用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對地址的形式，其代碼通常采用相對地址的形式，其首地址為首地址為0，其余，其余指令中的地址都指令中的地址都相對于首地址而編址相對于首地址而編址。v不能不能用邏輯地址在內(nèi)存中讀取信息。用邏輯地址在內(nèi)存中讀取信息。n物理地址（絕對地址，實(shí)地址）物理地址（絕對地址，實(shí)地址）v 內(nèi)存中存儲(chǔ)單元的地址，內(nèi)存中存儲(chǔ)單元的地址，可直接尋址可直接尋址。n地址轉(zhuǎn)換地址轉(zhuǎn)換v為了保證為了保證CPU執(zhí)行指令時(shí)可正確訪問存儲(chǔ)單元，需執(zhí)行指令

11、時(shí)可正確訪問存儲(chǔ)單元，需將用戶程序中的將用戶程序中的邏輯地址轉(zhuǎn)換邏輯地址轉(zhuǎn)換為運(yùn)行時(shí)由機(jī)器直接為運(yùn)行時(shí)由機(jī)器直接尋址的尋址的物理地址物理地址，這一過程稱為地址映射。，這一過程稱為地址映射。03456.LOAD A 200.0100200300.LOAD A 2003456邏輯地址空間邏輯地址空間110012001300物理地址空間物理地址空間200VR+1000BR原因原因:當(dāng)程序裝入內(nèi)存時(shí)當(dāng)程序裝入內(nèi)存時(shí), 操作系統(tǒng)要為該程序分配一個(gè)合適的內(nèi)操作系統(tǒng)要為該程序分配一個(gè)合適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致, 而而CPU

12、執(zhí)行指令時(shí)是按物理地址進(jìn)行的，所以要進(jìn)行地址轉(zhuǎn)換。執(zhí)行指令時(shí)是按物理地址進(jìn)行的，所以要進(jìn)行地址轉(zhuǎn)換。17基本概念基本概念n靜態(tài)地址轉(zhuǎn)換（靜態(tài)重定位）靜態(tài)地址轉(zhuǎn)換（靜態(tài)重定位）v當(dāng)用戶程序被當(dāng)用戶程序被裝入裝入內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏輯地內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換。址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換。v一般在裝入內(nèi)存時(shí)由軟件完成。一般在裝入內(nèi)存時(shí)由軟件完成。n動(dòng)態(tài)地址轉(zhuǎn)換（動(dòng)態(tài)重定位）動(dòng)態(tài)地址轉(zhuǎn)換（動(dòng)態(tài)重定位）v在程序在程序運(yùn)行運(yùn)行過程中要訪問數(shù)據(jù)時(shí)再進(jìn)行程序和過程中要訪問數(shù)據(jù)時(shí)再進(jìn)行程序和數(shù)據(jù)的地址變換（即在逐條指令執(zhí)行時(shí)完成地?cái)?shù)據(jù)的地址變換（即在逐條指令執(zhí)行時(shí)完成地址

13、映射。一般為了提高效率，此工作由硬件地址映射。一般為了提高效率，此工作由硬件地址映射機(jī)制來完成。硬件支持，軟硬件結(jié)合完址映射機(jī)制來完成。硬件支持，軟硬件結(jié)合完成）。成）。v硬件上需要一對寄存器的支持。硬件上需要一對寄存器的支持。182、可重定位裝入方式、可重定位裝入方式n可重定位裝入方式可重定位裝入方式：事先不知事先不知用戶程序在內(nèi)存的駐留位置，用戶程序在內(nèi)存的駐留位置，裝入程序在裝入時(shí)根據(jù)內(nèi)存的裝入程序在裝入時(shí)根據(jù)內(nèi)存的實(shí)際情況把相對地址（邏輯地實(shí)際情況把相對地址（邏輯地址）轉(zhuǎn)換為絕對地址，裝入到址）轉(zhuǎn)換為絕對地址，裝入到適當(dāng)?shù)奈恢?。（適當(dāng)?shù)奈恢?。（在裝入時(shí)在裝入時(shí)進(jìn)行地址轉(zhuǎn)換進(jìn)行地址轉(zhuǎn)換）

14、n用于多道程序環(huán)境用于多道程序環(huán)境1，12500193、動(dòng)態(tài)運(yùn)行裝入方式、動(dòng)態(tài)運(yùn)行裝入方式n如果事先不知用戶程序在內(nèi)存的駐留位置，程如果事先不知用戶程序在內(nèi)存的駐留位置，程序在運(yùn)行過程中，它在內(nèi)存中的位置序在運(yùn)行過程中，它在內(nèi)存中的位置可經(jīng)常改可經(jīng)常改變變。裝入程序把裝入模塊裝入內(nèi)存后，并不立。裝入程序把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中相對地址轉(zhuǎn)換為絕對地址，而即把裝入模塊中相對地址轉(zhuǎn)換為絕對地址，而是在是在程序運(yùn)行程序運(yùn)行時(shí)才進(jìn)行。這種方式需一個(gè)重定時(shí)才進(jìn)行。這種方式需一個(gè)重定位寄存器來支持。（位寄存器來支持。（在程序運(yùn)行過程中進(jìn)行地在程序運(yùn)行過程中進(jìn)行地址轉(zhuǎn)換址轉(zhuǎn)換）返回裝入內(nèi)存后

15、的所有地址都仍然是相對地址。裝入內(nèi)存后的所有地址都仍然是相對地址。20二、程序的鏈接二、程序的鏈接1 1、靜態(tài)鏈接方式、靜態(tài)鏈接方式v是一種事先鏈接方式，即在程序運(yùn)行之前，先將各是一種事先鏈接方式，即在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫函數(shù)，鏈接成一個(gè)完整的目標(biāo)模塊及它們所需的庫函數(shù)，鏈接成一個(gè)完整的裝入模塊裝入模塊( (執(zhí)行文件執(zhí)行文件) )，以后不再拆開。，以后不再拆開。v實(shí)現(xiàn)靜態(tài)鏈接應(yīng)解決的問題：實(shí)現(xiàn)靜態(tài)鏈接應(yīng)解決的問題： （1 1）相對地址的修改）相對地址的修改 （2 2）變換外部調(diào)用符號）變換外部調(diào)用符號v存在問題：存在問題： （1 1）不便于對目標(biāo)模塊的修改和更新）不便于對

16、目標(biāo)模塊的修改和更新 （2 2）無法實(shí)現(xiàn)對目標(biāo)模塊的共享）無法實(shí)現(xiàn)對目標(biāo)模塊的共享21靜態(tài)鏈接方式靜態(tài)鏈接方式圖圖 4-3 程序鏈接示意圖程序鏈接示意圖22二、程序的鏈接二、程序的鏈接2、裝入時(shí)動(dòng)態(tài)鏈接方式、裝入時(shí)動(dòng)態(tài)鏈接方式v指將一組目標(biāo)模塊在裝入內(nèi)存時(shí)邊裝入邊鏈接的方式指將一組目標(biāo)模塊在裝入內(nèi)存時(shí)邊裝入邊鏈接的方式,具有便于修改和更新、便于實(shí)現(xiàn)對目標(biāo)模塊的共享。具有便于修改和更新、便于實(shí)現(xiàn)對目標(biāo)模塊的共享。v存在問題：存在問題：由于程序運(yùn)行所有可能用的目標(biāo)模塊在裝由于程序運(yùn)行所有可能用的目標(biāo)模塊在裝入時(shí)均全部鏈接在一起，所以將會(huì)把一些不會(huì)運(yùn)行的入時(shí)均全部鏈接在一起，所以將會(huì)把一些不會(huì)運(yùn)行的

17、目標(biāo)模塊也鏈接進(jìn)去。如程序中的錯(cuò)誤處理模塊。目標(biāo)模塊也鏈接進(jìn)去。如程序中的錯(cuò)誤處理模塊。3、運(yùn)行時(shí)動(dòng)態(tài)鏈接方式、運(yùn)行時(shí)動(dòng)態(tài)鏈接方式v在程序運(yùn)行中需要某些目標(biāo)模塊時(shí)，才對它們進(jìn)行鏈在程序運(yùn)行中需要某些目標(biāo)模塊時(shí)，才對它們進(jìn)行鏈接的方式。具有高效且節(jié)省內(nèi)存空間的優(yōu)點(diǎn)。接的方式。具有高效且節(jié)省內(nèi)存空間的優(yōu)點(diǎn)。返回234.3 連續(xù)分配存儲(chǔ)管理方式連續(xù)分配存儲(chǔ)管理方式q連續(xù)分配方式：連續(xù)分配方式：指為一個(gè)用戶程序分配一片連續(xù)的內(nèi)存空指為一個(gè)用戶程序分配一片連續(xù)的內(nèi)存空間。間。v4.3.1 單一連續(xù)分配方式單一連續(xù)分配方式v4.3.2 固定分區(qū)分配方式固定分區(qū)分配方式v4.3.3 動(dòng)態(tài)分區(qū)分配方式動(dòng)態(tài)分區(qū)

18、分配方式v4.3.6 動(dòng)態(tài)重定位分區(qū)分配方式動(dòng)態(tài)重定位分區(qū)分配方式v4.3.4 伙伴系統(tǒng)伙伴系統(tǒng)v分區(qū)的存儲(chǔ)保護(hù)分區(qū)的存儲(chǔ)保護(hù)v4.3.7覆蓋與交換覆蓋與交換返回目錄244.3.1 單一連續(xù)分配方式（單獨(dú)分區(qū)分配）單一連續(xù)分配方式（單獨(dú)分區(qū)分配）n存儲(chǔ)管理方法存儲(chǔ)管理方法：將內(nèi)存分為：將內(nèi)存分為系統(tǒng)區(qū)系統(tǒng)區(qū)（內(nèi)存低端，分（內(nèi)存低端，分配給配給OS用）和用）和用戶區(qū)用戶區(qū)（內(nèi)存高端，分配給用戶用）。（內(nèi)存高端，分配給用戶用）。采用靜態(tài)分配方式，即作業(yè)一旦進(jìn)入內(nèi)存，就要等采用靜態(tài)分配方式，即作業(yè)一旦進(jìn)入內(nèi)存，就要等待它運(yùn)行結(jié)束后才能釋放內(nèi)存。待它運(yùn)行結(jié)束后才能釋放內(nèi)存。n最簡單的一種存儲(chǔ)管理方式，

19、但只能用于最簡單的一種存儲(chǔ)管理方式，但只能用于單用戶、單用戶、單任務(wù)的單任務(wù)的OS中。中。25單一連續(xù)分配方式單一連續(xù)分配方式n主要特點(diǎn)主要特點(diǎn)：管理簡單，：管理簡單，只需小量的軟件和硬件只需小量的軟件和硬件支持，便于用戶了解和支持，便于用戶了解和使用。但因內(nèi)存中只裝使用。但因內(nèi)存中只裝入一道作業(yè)運(yùn)行，內(nèi)存入一道作業(yè)運(yùn)行，內(nèi)存空間浪費(fèi)大，各類資源空間浪費(fèi)大，各類資源的利用率也不高。的利用率也不高。系統(tǒng)區(qū)系統(tǒng)區(qū)-os用戶區(qū)用戶區(qū)用戶程序用戶程序26例子例子n一個(gè)容量為一個(gè)容量為256KB的內(nèi)存，操作系統(tǒng)占用的內(nèi)存，操作系統(tǒng)占用32KB，剩下，剩下224KB全部分配給用戶作業(yè)，如果一個(gè)作業(yè)僅需全部

20、分配給用戶作業(yè)，如果一個(gè)作業(yè)僅需64KB，那，那么就有么就有160KB的存儲(chǔ)空間被浪費(fèi)。的存儲(chǔ)空間被浪費(fèi)。操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)0KB32KB96KB256KB-1分配給用分配給用戶的空間戶的空間返回274.3.2 固定分區(qū)分配方式固定分區(qū)分配方式n是最早使用的一種可運(yùn)行多道程序的存儲(chǔ)管理方法。是最早使用的一種可運(yùn)行多道程序的存儲(chǔ)管理方法。n存儲(chǔ)管理方法存儲(chǔ)管理方法v內(nèi)存空間的劃分內(nèi)存空間的劃分：將內(nèi)存空間劃分為若干個(gè)固定大：將內(nèi)存空間劃分為若干個(gè)固定大小的分區(qū)，除小的分區(qū)，除OS占一區(qū)外，其余的一個(gè)分區(qū)裝入一占一區(qū)外，其余的一個(gè)分區(qū)裝入一道程序。分區(qū)的大小可以相等，也可以不等，但道程序。分

21、區(qū)的大小可以相等，也可以不等，但事事先必須確定，在運(yùn)行時(shí)不能改變先必須確定，在運(yùn)行時(shí)不能改變。即分區(qū)大小及邊。即分區(qū)大小及邊界在運(yùn)行時(shí)不能改變。界在運(yùn)行時(shí)不能改變。v系統(tǒng)需建立一張系統(tǒng)需建立一張分區(qū)說明表或使用表分區(qū)說明表或使用表，以記錄分區(qū)，以記錄分區(qū)號、分區(qū)大小、分區(qū)的起始地址及狀態(tài)（已分配或號、分區(qū)大小、分區(qū)的起始地址及狀態(tài)（已分配或未分配）。未分配）。28固定分區(qū)分配方式示意圖固定分區(qū)分配方式示意圖圖圖 4-4 固定分區(qū)使用表固定分區(qū)使用表20K20K未未n內(nèi)存分配內(nèi)存分配v當(dāng)某個(gè)用戶程序要裝入內(nèi)存時(shí)，由當(dāng)某個(gè)用戶程序要裝入內(nèi)存時(shí)，由內(nèi)存分配程序檢索內(nèi)存分配程序檢索分區(qū)說明表分區(qū)說明表

22、，從表中找出一個(gè)滿足要求的尚未分配的，從表中找出一個(gè)滿足要求的尚未分配的分區(qū)分配該程序，同時(shí)修改說明表中相應(yīng)分區(qū)的狀態(tài)；分區(qū)分配該程序，同時(shí)修改說明表中相應(yīng)分區(qū)的狀態(tài)；若找不到大小足夠的分區(qū)，則拒絕為該程序分配內(nèi)存。若找不到大小足夠的分區(qū)，則拒絕為該程序分配內(nèi)存。v當(dāng)程序執(zhí)行完畢，當(dāng)程序執(zhí)行完畢，釋放占用的分區(qū)釋放占用的分區(qū)，管理程序?qū)⑿薷?，管理程序?qū)⑿薷恼f明表中相應(yīng)分區(qū)的狀態(tài)為未分配，說明表中相應(yīng)分區(qū)的狀態(tài)為未分配，實(shí)現(xiàn)內(nèi)存資源的實(shí)現(xiàn)內(nèi)存資源的回收回收。n主要特點(diǎn)主要特點(diǎn)v管理簡單，但因作業(yè)的大小并不一定與某個(gè)分區(qū)大小管理簡單，但因作業(yè)的大小并不一定與某個(gè)分區(qū)大小相等，從而使一部分存儲(chǔ)空間被

23、浪費(fèi)。所以主存的利相等，從而使一部分存儲(chǔ)空間被浪費(fèi)。所以主存的利用率不高。用率不高。 例：在某系統(tǒng)中，采用固定分區(qū)分配管理方式，內(nèi)存分區(qū)例：在某系統(tǒng)中，采用固定分區(qū)分配管理方式，內(nèi)存分區(qū)（單位：字節(jié)）情況如圖所示，現(xiàn)有大小為（單位：字節(jié)）情況如圖所示，現(xiàn)有大小為1K、9K、33K、121K的多個(gè)作業(yè)要求進(jìn)入內(nèi)存，試畫出它們進(jìn)入內(nèi)存后的的多個(gè)作業(yè)要求進(jìn)入內(nèi)存，試畫出它們進(jìn)入內(nèi)存后的空間分配情況，并說明主存浪費(fèi)多大？空間分配情況，并說明主存浪費(fèi)多大？ 0k 20k 28k 60k 180k 511k1234（1）內(nèi)存分區(qū)圖）內(nèi)存分區(qū)圖os區(qū)號區(qū)號大小大小起址起址狀態(tài)狀態(tài)18k20k未分配未分配23

24、2k28k未分配未分配3120k60k未分配未分配4331k180k未分配未分配（2）分區(qū)說明表）分區(qū)說明表區(qū)號區(qū)號大小大小起址起址狀態(tài)狀態(tài)18k20k已分配已分配232k28k已分配已分配3120k60k已分配已分配4331k180k已分配已分配（2）分區(qū)說明表）分區(qū)說明表(3)主存浪費(fèi)空間主存浪費(fèi)空間=(8-1)+(32-9)+(120-33)+(331-121)=327(k)解：解：根據(jù)分區(qū)說明表，將根據(jù)分區(qū)說明表，將4個(gè)分區(qū)依次分配給個(gè)分區(qū)依次分配給4個(gè)作業(yè)，同個(gè)作業(yè)，同時(shí)修改分區(qū)說明表，其內(nèi)存分配和分區(qū)說明表如下所示：時(shí)修改分區(qū)說明表，其內(nèi)存分配和分區(qū)說明表如下所示： 0k 20k

25、28k 60k180k511k23(1)內(nèi)存分配圖內(nèi)存分配圖1K9K33K121K返回324.3.3 動(dòng)態(tài)分區(qū)分配方式動(dòng)態(tài)分區(qū)分配方式n動(dòng)態(tài)分區(qū)分配又稱為可變式分區(qū)分配，是一種動(dòng)動(dòng)態(tài)分區(qū)分配又稱為可變式分區(qū)分配，是一種動(dòng)態(tài)劃分存儲(chǔ)器的分區(qū)方法。態(tài)劃分存儲(chǔ)器的分區(qū)方法。n存儲(chǔ)管理方法存儲(chǔ)管理方法v內(nèi)存不是預(yù)先劃分好的；內(nèi)存不是預(yù)先劃分好的；v作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配；用情況來決定是否分配；v若有足夠的空間，則按需要分割一部分分區(qū)給若有足夠的空間，則按需要分割一部分分區(qū)給該進(jìn)程；否則令其等待內(nèi)存空間。該進(jìn)程；否則令其等待內(nèi)

26、存空間。33動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配n主要特點(diǎn)主要特點(diǎn) 管理簡單，只需少量的軟件和硬件支持，便于管理簡單，只需少量的軟件和硬件支持，便于用戶了解和使用。進(jìn)程的大小與某個(gè)分區(qū)大小相用戶了解和使用。進(jìn)程的大小與某個(gè)分區(qū)大小相等，從而主存的利用率有所提高。等，從而主存的利用率有所提高。341、分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)n空閑分區(qū)表空閑分區(qū)表v用來登記系統(tǒng)中的空閑分區(qū)用來登記系統(tǒng)中的空閑分區(qū)(分區(qū)號、分區(qū)起始地址、分分區(qū)號、分區(qū)起始地址、分區(qū)大小及狀態(tài)區(qū)大小及狀態(tài))。n空閑分區(qū)鏈空閑分區(qū)鏈v用鏈頭指針將系統(tǒng)中的空閑分區(qū)鏈接起來，構(gòu)成空閑分用鏈頭指針將系統(tǒng)中的空閑分區(qū)鏈接起來，構(gòu)成空閑分

27、區(qū)鏈。每個(gè)空閑分區(qū)的起始部分存放相應(yīng)的控制信息區(qū)鏈。每個(gè)空閑分區(qū)的起始部分存放相應(yīng)的控制信息(如如大小、指向下一空閑分區(qū)的指針等大小、指向下一空閑分區(qū)的指針等)。353、分區(qū)分配操作、分區(qū)分配操作_分配內(nèi)存和回收內(nèi)存分配內(nèi)存和回收內(nèi)存（1）分配內(nèi)存）分配內(nèi)存v系統(tǒng)利用某種分配算法，從空閑分區(qū)表系統(tǒng)利用某種分配算法，從空閑分區(qū)表/鏈中找到所需大小鏈中找到所需大小的分區(qū)。的分區(qū)。v分區(qū)的切割：分區(qū)的切割： 設(shè)請求的分區(qū)大小為設(shè)請求的分區(qū)大小為u.size，空閑分區(qū)的大小為，空閑分區(qū)的大小為m.size。若。若m.size-u.size size(size是事先規(guī)定的不再切是事先規(guī)定的不再切割的剩余

28、分區(qū)的大小割的剩余分區(qū)的大小)，說明多余部分大小可不再切割，將，說明多余部分大小可不再切割，將整個(gè)分區(qū)分配給請求者；否則，從該分區(qū)中按請求的大小整個(gè)分區(qū)分配給請求者；否則，從該分區(qū)中按請求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)表區(qū)表/鏈中，然后將分配區(qū)的首址返回給調(diào)用者。鏈中，然后將分配區(qū)的首址返回給調(diào)用者。36從頭開始查表從頭開始查表從該分區(qū)中劃出從該分區(qū)中劃出u.size大小的分區(qū)大小的分區(qū)檢索完否檢索完否？返回返回m.sizeu.sizem.size-u.size size將該分區(qū)分配給請求者，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)將該分區(qū)

29、分配給請求者，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回將該分區(qū)從分區(qū)表將該分區(qū)從分區(qū)表/鏈中移出鏈中移出繼續(xù)檢索下一個(gè)表項(xiàng)繼續(xù)檢索下一個(gè)表項(xiàng)YYYNNN內(nèi)存分配流程圖內(nèi)存分配流程圖37（2）回收內(nèi)存）回收內(nèi)存n回收分區(qū)與已有空閑分區(qū)的相鄰情況有以下四種回收分區(qū)與已有空閑分區(qū)的相鄰情況有以下四種： 1）回收分區(qū)上鄰接一個(gè)空閑分區(qū)）回收分區(qū)上鄰接一個(gè)空閑分區(qū),合并后首地址為空閑分區(qū)的首地址合并后首地址為空閑分區(qū)的首地址,大大小為二者之和。小為二者之和。 2）回收分區(qū)下鄰接一個(gè)空閑分區(qū)）回收分區(qū)下鄰接一個(gè)空閑分區(qū),合并后首地址為回收分區(qū)的首地址合并后首地址為回收分區(qū)的首地址,大小為二者之和。大小為二者之和。 3）回

30、收分區(qū)上下鄰接空閑分區(qū)）回收分區(qū)上下鄰接空閑分區(qū),合并后首地址為上空閑分區(qū)的首地址合并后首地址為上空閑分區(qū)的首地址,大小為三者之和。大小為三者之和。 4）回收分區(qū)不鄰接空閑分區(qū)，這時(shí)在空閑分區(qū)表中新建一表項(xiàng)，并填）回收分區(qū)不鄰接空閑分區(qū)，這時(shí)在空閑分區(qū)表中新建一表項(xiàng)，并填寫分區(qū)大小等信息。寫分區(qū)大小等信息。回收分區(qū)回收分區(qū)空閑分區(qū)空閑分區(qū)(a)空閑分區(qū)空閑分區(qū)回收分區(qū)回收分區(qū)(b)空閑分區(qū)空閑分區(qū)回收分區(qū)回收分區(qū)空閑分區(qū)空閑分區(qū)(c)內(nèi)存回收情況內(nèi)存回收情況返回384.3.4 基于順序搜索的動(dòng)態(tài)分區(qū)分配算法基于順序搜索的動(dòng)態(tài)分區(qū)分配算法n為了將一個(gè)作業(yè)裝入內(nèi)存，應(yīng)按照一定的分配算法從空閑為了將

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

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

33、在空閑分區(qū)表（鏈）中。留在空閑分區(qū)表（鏈）中。區(qū)號區(qū)號大小大小起址起址132k20k28k52k3120k60k4331k180k空閑分區(qū)表空閑分區(qū)表解：解：按首次適應(yīng)算法，按首次適應(yīng)算法，申請作業(yè)申請作業(yè)100k，分配，分配3號分區(qū)，剩下號分區(qū)，剩下分區(qū)為分區(qū)為20k，起始地址，起始地址160K ；申請作業(yè)申請作業(yè)30k，分配，分配1號分區(qū)，號分區(qū)，剩下分區(qū)為剩下分區(qū)為2k，起始地址，起始地址50K ；申請作業(yè)申請作業(yè)7k，分配，分配2號分區(qū)，號分區(qū)，剩下分區(qū)為剩下分區(qū)為1k，起始地址，起始地址59K。其內(nèi)存分配圖及分配后空閑。其內(nèi)存分配圖及分配后空閑分區(qū)表如下：分區(qū)表如下：例例 ：系統(tǒng)中的

34、空閑分區(qū)表如下表示，現(xiàn)有三個(gè)作業(yè)分配申請內(nèi)系統(tǒng)中的空閑分區(qū)表如下表示，現(xiàn)有三個(gè)作業(yè)分配申請內(nèi)存空間存空間100K、30K及及7K，給出按首次適應(yīng)算法的內(nèi)存分配情，給出按首次適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。況及分配后空閑分區(qū)表。區(qū)號區(qū)號大小大小起址起址12k50k21k59k320k160k4331k180k(2)該算法分配后的空閑分區(qū)表該算法分配后的空閑分區(qū)表0k20k52k60k180k511k(1)內(nèi)存分配圖內(nèi)存分配圖50K59K160K180Kv首次適應(yīng)算法的特點(diǎn)首次適應(yīng)算法的特點(diǎn) 優(yōu)先利用內(nèi)存優(yōu)先利用內(nèi)存低地址部分低地址部分的空閑分區(qū)，從而保留了高地址的空閑分區(qū)，從而保留了高

35、地址部分的大空閑區(qū)。但由于低地址部分不斷被劃分，致使低地址部分的大空閑區(qū)。但由于低地址部分不斷被劃分，致使低地址端留下許多難以利用的很小的空閑分區(qū)端留下許多難以利用的很小的空閑分區(qū)(碎片或零頭碎片或零頭)，而每次，而每次查找又都是從低地址部分開始，這無疑增加了查找可用空閑分查找又都是從低地址部分開始，這無疑增加了查找可用空閑分區(qū)的開銷。區(qū)的開銷。返回42循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法n算法要求算法要求 又稱為下次適應(yīng)算法，又稱為下次適應(yīng)算法，由首次適應(yīng)算法演變而來由首次適應(yīng)算法演變而來。在為作業(yè)分配內(nèi)存空間時(shí)，不再每次從空閑分區(qū)表在為作業(yè)分配內(nèi)存空間時(shí)，不再每次從空閑分區(qū)表/鏈?zhǔn)组_始查找，而

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

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

38、分區(qū)表。區(qū)號區(qū)號大小大小起址起址125k27k28k52k320k160k4301k210k(2)該算法分配后的空閑分區(qū)表該算法分配后的空閑分區(qū)表返回v算法特點(diǎn)：算法特點(diǎn)：使存儲(chǔ)空間的利用更加均衡，不致使小的空閑使存儲(chǔ)空間的利用更加均衡，不致使小的空閑區(qū)集中在存儲(chǔ)區(qū)的一端，但這會(huì)導(dǎo)致缺乏大的空閑分區(qū)。區(qū)集中在存儲(chǔ)區(qū)的一端，但這會(huì)導(dǎo)致缺乏大的空閑分區(qū)。 0k 20k 52k 60k180k511k(1)內(nèi)存分配圖內(nèi)存分配圖27K52K160K210K45最佳適應(yīng)算法最佳適應(yīng)算法n算法要求：算法要求： 空閑分區(qū)表空閑分區(qū)表/鏈按鏈按容量大小遞增容量大小遞增的次序排列。的次序排列。在進(jìn)行內(nèi)存分配時(shí)，

39、從空閑分區(qū)表在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表/鏈的鏈的首開始首開始順順序查找，直到找到第一個(gè)滿足其大小要求的空閑序查找，直到找到第一個(gè)滿足其大小要求的空閑分區(qū)為止。分區(qū)為止。 按這種方式為作業(yè)分配內(nèi)存，就能把既滿足按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。如果該空閑分區(qū)大于作業(yè)的大小，則與首作業(yè)。如果該空閑分區(qū)大于作業(yè)的大小，則與首次適應(yīng)算法相同，將剩余空閑分區(qū)仍留在空閑分次適應(yīng)算法相同，將剩余空閑分區(qū)仍留在空閑分區(qū)表區(qū)表/鏈中。鏈中。例例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請系統(tǒng)中的空閑分區(qū)表如下，

40、現(xiàn)有三個(gè)作業(yè)分配申請內(nèi)存空間內(nèi)存空間100K、30K及及7K。給出按最佳適應(yīng)算法的內(nèi)存。給出按最佳適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。分配情況及分配后空閑分區(qū)表。區(qū)號區(qū)號大小大小起址起址18k52k232k20k3120k60k4331k180k分配前的空閑分區(qū)表分配前的空閑分區(qū)表 0k 20k 52k 60k180k511k2134內(nèi)存分區(qū)內(nèi)存分區(qū)解：解：按最佳適應(yīng)算法，分配前的空閑分區(qū)表如上表。按最佳適應(yīng)算法，分配前的空閑分區(qū)表如上表。申請作業(yè)申請作業(yè)100k，分配，分配3號分區(qū)，剩下分區(qū)為號分區(qū)，剩下分區(qū)為20k,起始地址起始地址160K；申請作申請作業(yè)業(yè)30k，分配，分配2號分區(qū)

41、，剩下分區(qū)為號分區(qū)，剩下分區(qū)為2k，起始地址，起始地址50K ；申請作申請作業(yè)業(yè)7k，分配，分配1號分區(qū)，剩下分區(qū)為號分區(qū)，剩下分區(qū)為1k，起始地址，起始地址59K 。其內(nèi)存。其內(nèi)存分配圖及分配后空閑分區(qū)表如下：分配圖及分配后空閑分區(qū)表如下：區(qū)號區(qū)號大小大小起址起址18k52k320k160k232k20k4331k180k1)作業(yè)作業(yè)100K分配后的空閑分區(qū)表分配后的空閑分區(qū)表區(qū)號區(qū)號大小大小起址起址12k50k28k52k320k160k4331k180k2)作業(yè)作業(yè)30K分配后的空閑分區(qū)表分配后的空閑分區(qū)表區(qū)號區(qū)號大小大小起址起址11k59k22k50k320k160k4331k180k

42、3)作業(yè)作業(yè)7K分配后的空閑分區(qū)表分配后的空閑分區(qū)表(2) 分配后的空閑分區(qū)表分配后的空閑分區(qū)表返回 0k 20k 52k 60k180k511k(1)內(nèi)存分配圖內(nèi)存分配圖50K59K160K180K區(qū)號區(qū)號大小大小起址起址11k59k22k50k320k160k4331k180kv算法特點(diǎn)算法特點(diǎn) 若存在與作業(yè)大小一致的空閑分區(qū)若存在與作業(yè)大小一致的空閑分區(qū),則它必然被選中，若則它必然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的空不存在與作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的空閑分區(qū)，從而保留了大的空閑分區(qū)閑分區(qū)，從而保留了大的空閑分區(qū)。但空閑區(qū)一般不可能正好但空閑區(qū)

43、一般不可能正好和它申請的內(nèi)存空間大小一樣，因而將其分割成兩部分時(shí)，往和它申請的內(nèi)存空間大小一樣，因而將其分割成兩部分時(shí)，往往使剩下的空閑區(qū)非常小，從而在存儲(chǔ)器中留下許多難以利用往使剩下的空閑區(qū)非常小，從而在存儲(chǔ)器中留下許多難以利用的小空閑區(qū)（碎片或零頭）。的小空閑區(qū)（碎片或零頭）。49最壞適應(yīng)算法最壞適應(yīng)算法n算法要求算法要求 空閑分區(qū)表空閑分區(qū)表/鏈鏈按容量大小遞減按容量大小遞減的次序排列。的次序排列。在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表/鏈的鏈的首開始首開始順順序查找，直到找到第一個(gè)比之大的空閑分區(qū)為止，序查找，直到找到第一個(gè)比之大的空閑分區(qū)為止，剩下的空閑仍留在空

44、閑分區(qū)表剩下的空閑仍留在空閑分區(qū)表/鏈中。鏈中。區(qū)號區(qū)號大小大小起址起址1331k180k2120k60k332k20k48k52k空閑分區(qū)表空閑分區(qū)表例例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請內(nèi)存系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請內(nèi)存空間空間100K、30K及及7K。給出按最壞適應(yīng)算法的內(nèi)存分配情況。給出按最壞適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。及分配后空閑分區(qū)表。解：解：按最壞適應(yīng)算法，分配前的空閑分區(qū)表如上表。按最壞適應(yīng)算法，分配前的空閑分區(qū)表如上表。申請作業(yè)申請作業(yè)100k，分配，分配1號分區(qū)，剩下分區(qū)為號分區(qū)，剩下分區(qū)為231k，起始地址，起始地址280K；

45、申請申請作業(yè)作業(yè)30k，分配，分配1號分區(qū)，剩下分區(qū)為號分區(qū)，剩下分區(qū)為201k，起始地址，起始地址310K ；申申請作業(yè)請作業(yè)7k，分配，分配1號分區(qū)，剩下分區(qū)為號分區(qū)，剩下分區(qū)為194k，起始地址，起始地址317K 。其內(nèi)存分配圖及分配后空閑分區(qū)表如下：其內(nèi)存分配圖及分配后空閑分區(qū)表如下：區(qū)號區(qū)號大小大小起址起址1231k280k2120k60k332k20k48k52k1)作業(yè)作業(yè)100K分配后的空閑分區(qū)表分配后的空閑分區(qū)表區(qū)號區(qū)號大小大小起址起址1201k310k2120k60k332k20k48k52k2)作業(yè)作業(yè)30K分配后的空閑分區(qū)表分配后的空閑分區(qū)表區(qū)號區(qū)號大小大小起址起址11

46、94k317k2120k60k332k20k48k52k3)作業(yè)作業(yè)7K分配后的空閑分區(qū)表分配后的空閑分區(qū)表區(qū)號區(qū)號大小大小起址起址1194k317k2120k60k332k20k48k52k(2) 分配后的空閑分區(qū)表分配后的空閑分區(qū)表3 0k 20k 52k 60k180k511k(1)內(nèi)存分配圖內(nèi)存分配圖20K52K60K280K310K317K返回v算法特點(diǎn)算法特點(diǎn) 總是挑選滿足作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使總是挑選滿足作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于最大的空閑分區(qū)總

47、是因首先分配而劃分，當(dāng)有大作業(yè)到來時(shí)，最大的空閑分區(qū)總是因首先分配而劃分，當(dāng)有大作業(yè)到來時(shí)，其存儲(chǔ)空間的申請往往會(huì)得不到滿足。其存儲(chǔ)空間的申請往往會(huì)得不到滿足。534.3.5 基于索引搜索的動(dòng)態(tài)分區(qū)分配算法基于索引搜索的動(dòng)態(tài)分區(qū)分配算法n固定劃分方案限制了系統(tǒng)中活躍進(jìn)程的數(shù)目。并固定劃分方案限制了系統(tǒng)中活躍進(jìn)程的數(shù)目。并且，只能運(yùn)行不超過分區(qū)大小的進(jìn)程，如果進(jìn)程且，只能運(yùn)行不超過分區(qū)大小的進(jìn)程，如果進(jìn)程遠(yuǎn)遠(yuǎn)小于分區(qū)大小，則內(nèi)存空間的利用率非常低。遠(yuǎn)遠(yuǎn)小于分區(qū)大小，則內(nèi)存空間的利用率非常低。n動(dòng)態(tài)劃分方案使存儲(chǔ)管理復(fù)雜化，并且需要系統(tǒng)動(dòng)態(tài)劃分方案使存儲(chǔ)管理復(fù)雜化，并且需要系統(tǒng)付出緊湊零頭的額外開

48、銷。付出緊湊零頭的額外開銷。54n將空閑分區(qū)根據(jù)容量大小進(jìn)行分類，具有相同容將空閑分區(qū)根據(jù)容量大小進(jìn)行分類，具有相同容量的空閑分區(qū)單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，同時(shí)量的空閑分區(qū)單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立一張管理索引表。在內(nèi)存中設(shè)立一張管理索引表。n第一步：根據(jù)進(jìn)程的大小，從索引表中去尋找能第一步：根據(jù)進(jìn)程的大小，從索引表中去尋找能容納它的最小空閑區(qū)鏈表；容納它的最小空閑區(qū)鏈表；n第二步：從鏈表中取下第一塊進(jìn)行分配，不對任第二步：從鏈表中取下第一塊進(jìn)行分配，不對任何分區(qū)產(chǎn)生分割。能保留大的分區(qū)。何分區(qū)產(chǎn)生分割。能保留大的分區(qū)。1、快速適應(yīng)算法（、快速適應(yīng)算法（quick fit）55

49、2、伙伴系統(tǒng)、伙伴系統(tǒng)n伙伴系統(tǒng)內(nèi)存的用戶可用空間為伙伴系統(tǒng)內(nèi)存的用戶可用空間為2u。n系統(tǒng)總是為進(jìn)程分配大小為系統(tǒng)總是為進(jìn)程分配大小為2i的一個(gè)空閑分區(qū)。的一個(gè)空閑分區(qū)。其中其中mi U,2m是系統(tǒng)允許的最小分區(qū)尺寸。是系統(tǒng)允許的最小分區(qū)尺寸。n伙伴系統(tǒng)：綜合固定劃分技術(shù)和動(dòng)態(tài)劃分技術(shù)的伙伴系統(tǒng)：綜合固定劃分技術(shù)和動(dòng)態(tài)劃分技術(shù)的優(yōu)點(diǎn)。優(yōu)點(diǎn)。562、伙伴系統(tǒng)、伙伴系統(tǒng)存儲(chǔ)分配存儲(chǔ)分配n進(jìn)程申請大小為進(jìn)程申請大小為k的空間，系統(tǒng)為之分配一個(gè)的空間，系統(tǒng)為之分配一個(gè)2i的空閑分的空閑分區(qū)，其中，區(qū)，其中，2i-12u,即進(jìn)程即進(jìn)程內(nèi)存空間，失??；內(nèi)存空間，失??；n若找到，即把該空閑分區(qū)分配給進(jìn)程。

50、若找到，即把該空閑分區(qū)分配給進(jìn)程。n若當(dāng)前無尺寸為若當(dāng)前無尺寸為2i的空閑分區(qū)，則：的空閑分區(qū)，則： （1）將）將i變成變成i+1,查找一個(gè)尺寸為查找一個(gè)尺寸為2i+1的空閑分區(qū)。若存在，的空閑分區(qū)。若存在，轉(zhuǎn)（轉(zhuǎn)（2）執(zhí)行；否則，繼續(xù)執(zhí)行（）執(zhí)行；否則，繼續(xù)執(zhí)行（1） （2）等分）等分2i+1空閑分區(qū)：產(chǎn)生兩個(gè)空閑分區(qū)：產(chǎn)生兩個(gè)2i的伙伴分區(qū)；的伙伴分區(qū)； （3）把其中一個(gè)）把其中一個(gè)2i的伙伴分區(qū)作為空閑分區(qū)；的伙伴分區(qū)作為空閑分區(qū)； （4）另一個(gè)）另一個(gè)2i空閑分區(qū)分配給進(jìn)程，結(jié)束。空閑分區(qū)分配給進(jìn)程，結(jié)束。572、伙伴系統(tǒng)、伙伴系統(tǒng)回收回收n當(dāng)系統(tǒng)執(zhí)行完畢，釋放一個(gè)尺寸為當(dāng)系統(tǒng)執(zhí)行完畢

51、，釋放一個(gè)尺寸為2i的分區(qū)時(shí)，的分區(qū)時(shí)，系統(tǒng)用下面的算法回收該分區(qū)：系統(tǒng)用下面的算法回收該分區(qū)：n如果被回收分區(qū)的伙伴分區(qū)非空閑，那么保留該如果被回收分區(qū)的伙伴分區(qū)非空閑，那么保留該分區(qū)為一個(gè)獨(dú)立的空閑分區(qū)，否則分區(qū)為一個(gè)獨(dú)立的空閑分區(qū)，否則 （1）合并回收分區(qū)及其伙伴分區(qū)，從而得到一個(gè)）合并回收分區(qū)及其伙伴分區(qū)，從而得到一個(gè)尺寸為尺寸為2i+1的空閑分區(qū)；的空閑分區(qū)； （2）系統(tǒng)再次調(diào)用本算法回收上一步得到的尺寸）系統(tǒng)再次調(diào)用本算法回收上一步得到的尺寸為為2i+1的空閑分區(qū)。的空閑分區(qū)。583、哈希算法、哈希算法n利用哈?？焖俨檎业膬?yōu)點(diǎn)，以及空閑分區(qū)在可利利用哈?？焖俨檎业膬?yōu)點(diǎn)，以及空閑分區(qū)

52、在可利用空閑區(qū)表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造用空閑區(qū)表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的每一個(gè)表項(xiàng)記錄了一個(gè)對應(yīng)的空閑分區(qū)鏈表頭指每一個(gè)表項(xiàng)記錄了一個(gè)對應(yīng)的空閑分區(qū)鏈表頭指針。針。594.3.6 動(dòng)態(tài)可重定位分區(qū)分配方式動(dòng)態(tài)可重定位分區(qū)分配方式1、碎片問題、碎片問題 在分區(qū)存儲(chǔ)管理方式中，必須把作業(yè)裝入在分區(qū)存儲(chǔ)管理方式中，必須把作業(yè)裝入到一片到一片連續(xù)的內(nèi)存空間連續(xù)的內(nèi)存空間。如果系統(tǒng)中有若干個(gè)。如果系統(tǒng)中有若干個(gè)小的分區(qū)，其總?cè)萘看笥谝b入的作業(yè)，但由小的分區(qū)，其總?cè)萘看笥谝b入的作業(yè)，但由于它們不相鄰接

53、，也將致使作業(yè)不能裝入內(nèi)存。于它們不相鄰接，也將致使作業(yè)不能裝入內(nèi)存。例例 ：如圖所示系統(tǒng)中有四個(gè)小空閑分區(qū)，并不相如圖所示系統(tǒng)中有四個(gè)小空閑分區(qū)，并不相鄰，但總?cè)萘繛猷?，但總?cè)萘繛?0KB，如果現(xiàn)有一作業(yè)要求分，如果現(xiàn)有一作業(yè)要求分配配40KB的內(nèi)存空間，由于系統(tǒng)中所有空閑分區(qū)的內(nèi)存空間，由于系統(tǒng)中所有空閑分區(qū)的容量均小于的容量均小于40KB，故此作業(yè)無法裝入內(nèi)存。，故此作業(yè)無法裝入內(nèi)存。 這種內(nèi)存中無法被利用的存儲(chǔ)空間稱為這種內(nèi)存中無法被利用的存儲(chǔ)空間稱為“零頭零頭”或或“碎片碎片”.根據(jù)碎片出現(xiàn)的情況分為根據(jù)碎片出現(xiàn)的情況分為以下兩種：以下兩種：操作系統(tǒng)作業(yè)A20KB20KB作業(yè)B30K

54、B30KB作業(yè)C15KB15KB作業(yè)D25KB25KB60系統(tǒng)中的碎片系統(tǒng)中的碎片n內(nèi)部碎片內(nèi)部碎片：指分配給作業(yè)的存儲(chǔ)空間中未被利用的部分。如：指分配給作業(yè)的存儲(chǔ)空間中未被利用的部分。如固定分區(qū)中存在的碎片。固定分區(qū)中存在的碎片。n外部碎片外部碎片：指系統(tǒng)中無法利用的小的空閑分區(qū)。如動(dòng)態(tài)分區(qū)：指系統(tǒng)中無法利用的小的空閑分區(qū)。如動(dòng)態(tài)分區(qū)中存在的碎片。中存在的碎片。25KB作業(yè)作業(yè)D15KB作業(yè)作業(yè)C30KB作業(yè)作業(yè)B20KB作業(yè)作業(yè)A操作系統(tǒng)操作系統(tǒng)外外部部碎碎片片外部碎片外部碎片os用用戶戶程程序序p4p1p20k20k56k65k125k135k內(nèi)部碎片內(nèi)部碎片內(nèi)內(nèi)部部碎碎片片612 2、

55、碎片問題的解決方法、碎片問題的解決方法n拼接或緊湊或緊縮技術(shù)拼接或緊湊或緊縮技術(shù)v將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在內(nèi)存中的位置發(fā)生了變化，這就必須對其內(nèi)存中的位置發(fā)生了變化，這就必須對其地址加以修改或變換即稱為重定位），使地址加以修改或變換即稱為重定位），使本來分散的多個(gè)小空閑分區(qū)連成一個(gè)大的本來分散的多個(gè)小空閑分區(qū)連成一個(gè)大的空閑區(qū)。如圖所示。空閑區(qū)。如圖所示。v這種通過移動(dòng)作業(yè)從把多個(gè)分散的小分區(qū)這種通過移動(dòng)作業(yè)從把多個(gè)分散的小分區(qū)拼接成一個(gè)大分區(qū)的方法稱為拼接或緊湊拼接成一個(gè)大分區(qū)的方法稱為拼接或緊湊或緊縮或緊縮。v拼接時(shí)機(jī)：分區(qū)回收時(shí)；當(dāng)找不到足

56、夠大拼接時(shí)機(jī)：分區(qū)回收時(shí)；當(dāng)找不到足夠大的空閑分區(qū)且總空閑分區(qū)容量可以滿足作的空閑分區(qū)且總空閑分區(qū)容量可以滿足作業(yè)要求時(shí)。業(yè)要求時(shí)。操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C作業(yè)D20KB20KB30KB 90KB30KB 90KB15KB15KB25KB25KB623 3、動(dòng)態(tài)重定位、動(dòng)態(tài)重定位n拼接或緊湊，都會(huì)對程序或數(shù)據(jù)的地址產(chǎn)生移位拼接或緊湊，都會(huì)對程序或數(shù)據(jù)的地址產(chǎn)生移位影響，必須進(jìn)行重定位。而為了使地址的轉(zhuǎn)換不影響，必須進(jìn)行重定位。而為了使地址的轉(zhuǎn)換不會(huì)影響到指令的執(zhí)行速度，必須有硬件地址變換會(huì)影響到指令的執(zhí)行速度，必須有硬件地址變換機(jī)構(gòu)的支持。機(jī)構(gòu)的支持。n重定位寄存器：重定位寄存器：存放程序（

57、數(shù)據(jù)）在內(nèi)存中的起存放程序（數(shù)據(jù)）在內(nèi)存中的起始地址。程序在執(zhí)行時(shí)，真正訪問的內(nèi)存地址是始地址。程序在執(zhí)行時(shí)，真正訪問的內(nèi)存地址是相對地址與重定位寄存器中的地址相加而形成的。相對地址與重定位寄存器中的地址相加而形成的。n動(dòng)態(tài)重定位：動(dòng)態(tài)重定位：地址變換是在程序執(zhí)行期間，隨著地址變換是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行的。對每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行的。v動(dòng)態(tài)重定位分區(qū)分配技術(shù)動(dòng)態(tài)重定位分區(qū)分配技術(shù) 在動(dòng)態(tài)分區(qū)分配算法中增加拼接功能，在找不到足夠大的空在動(dòng)態(tài)分區(qū)分配算法中增加拼接功能，在找不到足夠大的空閑分區(qū)來滿足作業(yè)要求，而系統(tǒng)中總空閑分區(qū)容量可以滿足作業(yè)閑分區(qū)來滿足作業(yè)要求

58、，而系統(tǒng)中總空閑分區(qū)容量可以滿足作業(yè)要求時(shí)，進(jìn)行拼接。要求時(shí)，進(jìn)行拼接。動(dòng)態(tài)重定位分區(qū)分配算法流程圖動(dòng)態(tài)重定位分區(qū)分配算法流程圖有大于有大于x的的空閑分區(qū)嗎？空閑分區(qū)嗎？返回分區(qū)號返回分區(qū)號空閑分區(qū)空閑分區(qū)總和大于總和大于x嗎？嗎？拼接拼接并修改相應(yīng)數(shù)據(jù)結(jié)構(gòu)并修改相應(yīng)數(shù)據(jù)結(jié)構(gòu)返回返回修改有關(guān)數(shù)據(jù)結(jié)構(gòu)修改有關(guān)數(shù)據(jù)結(jié)構(gòu)按按動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配方式方式進(jìn)行分配進(jìn)行分配YYNN無法分配，返回?zé)o法分配，返回請求分配一個(gè)大小為請求分配一個(gè)大小為x的分區(qū)的分區(qū)64n動(dòng)態(tài)重定位分區(qū)分配方式主要特點(diǎn)動(dòng)態(tài)重定位分區(qū)分配方式主要特點(diǎn)v可以充分利用存儲(chǔ)區(qū)中的可以充分利用存儲(chǔ)區(qū)中的“零頭零頭/碎片碎片”，提高，提高

59、主存的利用率。主存的利用率。 v若若 “零頭零頭/碎片碎片”大多，則拼接頻率過高會(huì)使大多，則拼接頻率過高會(huì)使系統(tǒng)開銷加大。系統(tǒng)開銷加大。返回分配分配方式方式有無內(nèi)有無內(nèi)部碎片部碎片有無外有無外部碎片部碎片優(yōu)點(diǎn)優(yōu)點(diǎn)缺點(diǎn)缺點(diǎn)單一連單一連續(xù)分配續(xù)分配有有無無簡單簡單只能用在單用戶、單任務(wù)只能用在單用戶、單任務(wù)的的OS固定分固定分區(qū)分配區(qū)分配有有無無可用于多道程序系統(tǒng)的最可用于多道程序系統(tǒng)的最簡單的分配方案簡單的分配方案存儲(chǔ)空間浪費(fèi)存儲(chǔ)空間浪費(fèi)首次適首次適應(yīng)算法應(yīng)算法無無有有動(dòng)態(tài)分區(qū)分配中最簡單的動(dòng)態(tài)分區(qū)分配中最簡單的方案方案低地址部分用得太多，高低地址部分用得太多，高地址部分相對空閑，導(dǎo)致地址部分相

60、對空閑，導(dǎo)致查找效率低查找效率低循環(huán)首循環(huán)首次適應(yīng)次適應(yīng)無無有有查找時(shí)間很少，內(nèi)存空間查找時(shí)間很少，內(nèi)存空間分布均勻分布均勻會(huì)導(dǎo)致缺乏大的空閑分區(qū)會(huì)導(dǎo)致缺乏大的空閑分區(qū)最佳適最佳適應(yīng)算法應(yīng)算法無無有有使得外部碎片都很小，對使得外部碎片都很小，對于一次分配來說是最佳的于一次分配來說是最佳的需要查找整個(gè)內(nèi)存空間，需要查找整個(gè)內(nèi)存空間，費(fèi)時(shí)，長期來看留下了很費(fèi)時(shí)，長期來看留下了很多難以利用的小空閑區(qū)多難以利用的小空閑區(qū)最差適最差適應(yīng)算法應(yīng)算法無無有有使得留下來的空閑區(qū)較大，使得留下來的空閑區(qū)較大，便于下次利用便于下次利用需要查找整個(gè)內(nèi)存空間，需要查找整個(gè)內(nèi)存空間，費(fèi)時(shí)，過早用掉大的空閑費(fèi)時(shí)，過早用掉