chapter4_存儲管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、區(qū)的大小可以相等，也可以不等，但事事先必須確定，在運行時不能改變先必須確定，在運行時不能改變。即分區(qū)大小及邊。即分區(qū)大小及邊界在運行時不能改變。界在運行時不能改變。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當某個用戶程序要裝入內(nèi)存時，由當某個用戶程序要裝入內(nèi)存時，由內(nèi)存分配程序檢索內(nèi)存分配程序檢索分區(qū)說明表分區(qū)說明表

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

23、浪費。所以主存的利相等，從而使一部分存儲空間被浪費。所以主存的利用率不高。用率不高。 例：在某系統(tǒng)中，采用固定分區(qū)分配管理方式，內(nèi)存分區(qū)例：在某系統(tǒng)中，采用固定分區(qū)分配管理方式，內(nèi)存分區(qū)（單位：字節(jié)）情況如圖所示，現(xiàn)有大小為（單位：字節(jié)）情況如圖所示，現(xiàn)有大小為1K、9K、33K、121K的多個作業(yè)要求進入內(nèi)存，試畫出它們進入內(nèi)存后的的多個作業(yè)要求進入內(nèi)存，試畫出它們進入內(nè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)主存浪費空間主存浪費空間=(8-1)+(32-9)+(120-33)+(331-121)=327(k)解：解：根據(jù)分區(qū)說明表，將根據(jù)分區(qū)說明表，將4個分區(qū)依次分配給個分區(qū)依次分配給4個作業(yè)，同個作業(yè)，同時修改分區(qū)說明表，其內(nèi)存分配和分區(qū)說明表如下所示：時修改分區(qū)說明表，其內(nèi)存分配和分區(qū)說明表如下所示： 0k 20k

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

26、存空間。33動態(tài)分區(qū)分配動態(tài)分區(qū)分配n主要特點主要特點 管理簡單，只需少量的軟件和硬件支持，便于管理簡單，只需少量的軟件和硬件支持，便于用戶了解和使用。進程的大小與某個分區(qū)大小相用戶了解和使用。進程的大小與某個分區(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ū)鏈。每個空閑分區(qū)的起始部分存放相應(yīng)的控制信息區(qū)鏈。每個空閑分區(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ū)的大小)，說明多余部分大小可不再切割，將，說明多余部分大小可不再切割，將整個分區(qū)分配給請求者；否則，從該分區(qū)中按請求的大小整個分區(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ù)檢索下一個表項繼續(xù)檢索下一個表項YYYNNN內(nèi)存分配流程圖內(nèi)存分配流程圖37（2）回收內(nèi)存）回收內(nèi)存n回收分區(qū)與已有空閑分區(qū)的相鄰情況有以下四種回收分區(qū)與已有空閑分區(qū)的相鄰情況有以下四種： 1）回收分區(qū)上鄰接一個空閑分區(qū)）回收分區(qū)上鄰接一個空閑分區(qū),合并后首地址為空閑分區(qū)的首地址合并后首地址為空閑分區(qū)的首地址,大大小為二者之和。小為二者之和。 2）回收分區(qū)下鄰接一個空閑分區(qū)）回收分區(qū)下鄰接一個空閑分區(qū),合并后首地址為回收分區(qū)的首地址合并后首地址為回收分區(qū)的首地址,大小為二者之和。大小為二者之和。 3）回

30、收分區(qū)上下鄰接空閑分區(qū)）回收分區(qū)上下鄰接空閑分區(qū),合并后首地址為上空閑分區(qū)的首地址合并后首地址為上空閑分區(qū)的首地址,大小為三者之和。大小為三者之和。 4）回收分區(qū)不鄰接空閑分區(qū)，這時在空閑分區(qū)表中新建一表項，并填）回收分區(qū)不鄰接空閑分區(qū)，這時在空閑分區(qū)表中新建一表項，并填寫分區(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 基于順序搜索的動態(tài)分區(qū)分配算法基于順序搜索的動態(tài)分區(qū)分配算法n為了將一個作業(yè)裝入內(nèi)存，應(yīng)按照一定的分配算法從空閑為了將

31、一個作業(yè)裝入內(nèi)存，應(yīng)按照一定的分配算法從空閑分區(qū)表（鏈）中選分區(qū)表（鏈）中選 出一個滿足作業(yè)需求的分區(qū)分配給作業(yè)，出一個滿足作業(yè)需求的分區(qū)分配給作業(yè)，如果這個空閑分區(qū)的容量比作業(yè)申請的空間要大，則將該如果這個空閑分區(qū)的容量比作業(yè)申請的空間要大，則將該分區(qū)一分為二，一部分分配給作業(yè)，剩下的部分仍然留在分區(qū)一分為二，一部分分配給作業(yè)，剩下的部分仍然留在空閑分區(qū)表（鏈）中，同時修改空閑分區(qū)表（鏈）中相應(yīng)空閑分區(qū)表（鏈）中，同時修改空閑分區(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） 前進39首次適應(yīng)算法（最先適應(yīng)算法）首次適應(yīng)算法（最先適應(yīng)算法）n算法：空閑分區(qū)（鏈）按算法：空閑分區(qū)（鏈）按地址遞增地址遞增的次序排列。的次序排列。在進行內(nèi)存分配時，在進行內(nèi)存分配時，從空閑分區(qū)表從空閑分區(qū)表/鏈首開始順序鏈首開始順序查找查找，直到找到第一個滿足其大小要求的空閑分，直到找到第一個滿足其大小要求的空閑分區(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)有三個作業(yè)分配申請內(nèi)系統(tǒng)中的空閑分區(qū)表如下表示，現(xiàn)有三個作業(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)算法的特點首次適應(yīng)算法的特點 優(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)存空間時，不再每次從空閑分區(qū)表在為作業(yè)分配內(nèi)存空間時，不再每次從空閑分區(qū)表/鏈首開始查找，而

36、是鏈首開始查找，而是從上次找到的空閑分區(qū)的下一個從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，空閑分區(qū)開始查找，直到找到第一個能滿足其大小要直到找到第一個能滿足其大小要求的空閑分區(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)有三個作業(yè)分配申請內(nèi)系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(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算法特點：算法特點：使存儲空間的利用更加均衡，不致使小的空閑使存儲空間的利用更加均衡，不致使小的空閑區(qū)集中在存儲區(qū)的一端，但這會導(dǎo)致缺乏大的空閑分區(qū)。區(qū)集中在存儲區(qū)的一端，但這會導(dǎo)致缺乏大的空閑分區(qū)。 0k 20k 52k 60k180k511k(1)內(nèi)存分配圖內(nèi)存分配圖27K52K160K210K45最佳適應(yīng)算法最佳適應(yīng)算法n算法要求：算法要求： 空閑分區(qū)表空閑分區(qū)表/鏈按鏈按容量大小遞增容量大小遞增的次序排列。的次序排列。在進行內(nèi)存分配時，

39、從空閑分區(qū)表在進行內(nèi)存分配時，從空閑分區(qū)表/鏈的鏈的首開始首開始順順序查找，直到找到第一個滿足其大小要求的空閑序查找，直到找到第一個滿足其大小要求的空閑分區(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)有三個作業(yè)分配申請系統(tǒng)中的空閑分區(qū)表如下，

40、現(xiàn)有三個作業(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算法特點算法特點 若存在與作業(yè)大小一致的空閑分區(qū)若存在與作業(yè)大小一致的空閑分區(qū),則它必然被選中，若則它必然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的空不存在與作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的空閑分區(qū)，從而保留了大的空閑分區(qū)閑分區(qū)，從而保留了大的空閑分區(qū)。但空閑區(qū)一般不可能正好但空閑區(qū)

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

44、閑分區(qū)表剩下的空閑仍留在空閑分區(qū)表/鏈中。鏈中。區(qū)號區(qū)號大小大小起址起址1331k180k2120k60k332k20k48k52k空閑分區(qū)表空閑分區(qū)表例例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(yè)分配申請內(nèi)存系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(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算法特點算法特點 總是挑選滿足作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使總是挑選滿足作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于最大的空閑分區(qū)總

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

48、銷。付出緊湊零頭的額外開銷。54n將空閑分區(qū)根據(jù)容量大小進行分類，具有相同容將空閑分區(qū)根據(jù)容量大小進行分類，具有相同容量的空閑分區(qū)單獨設(shè)立一個空閑分區(qū)鏈表，同時量的空閑分區(qū)單獨設(shè)立一個空閑分區(qū)鏈表，同時在內(nèi)存中設(shè)立一張管理索引表。在內(nèi)存中設(shè)立一張管理索引表。n第一步：根據(jù)進程的大小，從索引表中去尋找能第一步：根據(jù)進程的大小，從索引表中去尋找能容納它的最小空閑區(qū)鏈表；容納它的最小空閑區(qū)鏈表；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)總是為進程分配大小為系統(tǒng)總是為進程分配大小為2i的一個空閑分區(qū)。的一個空閑分區(qū)。其中其中mi U,2m是系統(tǒng)允許的最小分區(qū)尺寸。是系統(tǒng)允許的最小分區(qū)尺寸。n伙伴系統(tǒng)：綜合固定劃分技術(shù)和動態(tài)劃分技術(shù)的伙伴系統(tǒng)：綜合固定劃分技術(shù)和動態(tài)劃分技術(shù)的優(yōu)點。優(yōu)點。562、伙伴系統(tǒng)、伙伴系統(tǒng)存儲分配存儲分配n進程申請大小為進程申請大小為k的空間，系統(tǒng)為之分配一個的空間，系統(tǒng)為之分配一個2i的空閑分的空閑分區(qū)，其中，區(qū)，其中，2i-12u,即進程即進程內(nèi)存空間，失?。粌?nèi)存空間，失敗；n若找到，即把該空閑分區(qū)分配給進程。

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

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

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

53、，也將致使作業(yè)不能裝入內(nèi)存。于它們不相鄰接，也將致使作業(yè)不能裝入內(nèi)存。例例 ：如圖所示系統(tǒng)中有四個小空閑分區(qū)，并不相如圖所示系統(tǒng)中有四個小空閑分區(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)存中無法被利用的存儲空間稱為這種內(nèi)存中無法被利用的存儲空間稱為“零頭零頭”或或“碎片碎片”.根據(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è)的存儲空間中未被利用的部分。如：指分配給作業(yè)的存儲空間中未被利用的部分。如固定分區(qū)中存在的碎片。固定分區(qū)中存在的碎片。n外部碎片外部碎片：指系統(tǒng)中無法利用的小的空閑分區(qū)。如動態(tài)分區(qū)：指系統(tǒng)中無法利用的小的空閑分區(qū)。如動態(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ā)生了變化，這就必須對其地址加以修改或變換即稱為重定位），使地址加以修改或變換即稱為重定位），使本來分散的多個小空閑分區(qū)連成一個大的本來分散的多個小空閑分區(qū)連成一個大的空閑區(qū)。如圖所示。空閑區(qū)。如圖所示。v這種通過移動作業(yè)從把多個分散的小分區(qū)這種通過移動作業(yè)從把多個分散的小分區(qū)拼接成一個大分區(qū)的方法稱為拼接或緊湊拼接成一個大分區(qū)的方法稱為拼接或緊湊或緊縮或緊縮。v拼接時機：分區(qū)回收時；當找不到足

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

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

58、，而系統(tǒng)中總空閑分區(qū)容量可以滿足作業(yè)要求時，進行拼接。要求時，進行拼接。動態(tài)重定位分區(qū)分配算法流程圖動態(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)按按動態(tài)分區(qū)分配動態(tài)分區(qū)分配方式方式進行分配進行分配YYNN無法分配，返回無法分配，返回請求分配一個大小為請求分配一個大小為x的分區(qū)的分區(qū)64n動態(tài)重定位分區(qū)分配方式主要特點動態(tài)重定位分區(qū)分配方式主要特點v可以充分利用存儲區(qū)中的可以充分利用存儲區(qū)中的“零頭零頭/碎片碎片”，提高，提高

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

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