操作系統(tǒng)第5章講存儲管理1連續(xù)分配

1、主要研究三方面的問題：主要研究三方面的問題： 放（放（PlacementPlacement） ?。ㄈ。‵etchFetch） 換（換（ReplacementReplacement） 存儲管理研究的內(nèi)容存儲管理研究的內(nèi)容 l第一個問題：放（第一個問題：放（PlacementPlacement），如何），如何 放入內(nèi)存？放入內(nèi)存？ 存儲管理研究的內(nèi)容存儲管理研究的內(nèi)容 連續(xù)連續(xù) 不連續(xù)不連續(xù) 多道固定分區(qū)存放多道固定分區(qū)存放 多道可變分區(qū)存放多道可變分區(qū)存放 單道連續(xù)存放單道連續(xù)存放 分頁存放分頁存放 分段存放分段存放 段頁式存放段頁式存放 放放 l第二個問題是：第二個問題是： ?。ㄈ。‵etch

2、Fetch），即如），即如 何從外存調(diào)入內(nèi)存。何從外存調(diào)入內(nèi)存。 存儲管理研究的內(nèi)容存儲管理研究的內(nèi)容 預調(diào)：預調(diào)：訪問前訪問前 預先調(diào)入內(nèi)存預先調(diào)入內(nèi)存 請調(diào)：請調(diào)：因空間不因空間不 足，訪問時請求足，訪問時請求 調(diào)入內(nèi)存調(diào)入內(nèi)存 單道連續(xù)一次調(diào)入單道連續(xù)一次調(diào)入 分頁式請求調(diào)入分頁式請求調(diào)入 分段式分段式請求調(diào)入請求調(diào)入 段頁式段頁式請求調(diào)入請求調(diào)入 取取 多道固定分區(qū)一次調(diào)入多道固定分區(qū)一次調(diào)入 多道可變分區(qū)一次調(diào)入多道可變分區(qū)一次調(diào)入 l第三個的問題：換（第三個的問題：換（ReplacementReplacement），即），即 請求從外存調(diào)入的頁或段與內(nèi)存中的哪些請求從外存調(diào)入的頁或

3、段與內(nèi)存中的哪些 塊或哪個存儲區(qū)對換？塊或哪個存儲區(qū)對換？ 存儲管理研究的內(nèi)容存儲管理研究的內(nèi)容 換換 先進先出算法先進先出算法FIFO 時鐘算法時鐘算法CLOCK 最優(yōu)算法最優(yōu)算法OPT 最近最少使用算法最近最少使用算法LRU 頁式策略頁式策略 5.15.1程序的裝入和鏈接程序的裝入和鏈接 一、源程序裝入內(nèi)存的三個步驟一、源程序裝入內(nèi)存的三個步驟 l編譯編譯 l鏈接鏈接 l裝入裝入 一、源程序裝入內(nèi)存的三個步驟一、源程序裝入內(nèi)存的三個步驟 如：有一作業(yè)如：有一作業(yè)A A，有，有4 4個程序段，裝入過程如下：個程序段，裝入過程如下： 主程主程 序段序段 子主程子主程 序段序段 數(shù)據(jù)段數(shù)據(jù)段 堆

4、棧段堆棧段 編譯編譯 主程主程 序段序段 子主程子主程 序段序段 數(shù)據(jù)段數(shù)據(jù)段 堆棧段堆棧段 0 40K 0 30K 0 20K 0 10K 鏈接鏈接 主程主程 序段序段 子主程子主程 序段序段 數(shù)據(jù)段數(shù)據(jù)段 堆棧段堆棧段 0 100K 裝入裝入 OS 用戶用戶 可用可用 空間空間 地址地址 重定重定 位位 0 800K 4096K 作業(yè)作業(yè)A的源的源 程序程序-名名 空間空間 作業(yè)作業(yè)A的目標的目標 模塊模塊-邏輯邏輯 地址空間地址空間 作業(yè)作業(yè)A重定位重定位 后的物理地址后的物理地址 空間空間 作業(yè)作業(yè)A的目標的目標 程序程序(可執(zhí)行可執(zhí)行 文件文件)-邏輯邏輯 地址空間地址空間 二、鏈接

5、方式二、鏈接方式 1 1、靜態(tài)鏈接、靜態(tài)鏈接-程序運行之前就事先程序運行之前就事先 將外部目標模塊鏈接成可執(zhí)行文件，稱為靜態(tài)將外部目標模塊鏈接成可執(zhí)行文件，稱為靜態(tài) 鏈接。例：如下作業(yè)鏈接。例：如下作業(yè)B B有三個目標程序模塊。有三個目標程序模塊。 鏈接鏈接 裝入裝入 OS 用戶用戶 可用可用 空間空間 地址地址 重定重定 位位 0 800K 4096K 模塊模塊A Call B Return 模塊模塊B Call C Return 模塊模塊C Return 0 L-1 0 M-1 0 N-1 模塊模塊A JSR “L” Return 模塊模塊B JSR “L+M” Return 模塊模塊C

6、Return 0 L-1 L L+M-1 L+M L+M+N-1 作業(yè)作業(yè)B的目標模塊的目標模塊- -邏輯地址空間邏輯地址空間 作業(yè)作業(yè)B的目標的目標 程序程序(可執(zhí)行可執(zhí)行 文件文件)-邏輯邏輯 地址空間地址空間 二、鏈接方式二、鏈接方式 2 2、裝入時動態(tài)鏈接、裝入時動態(tài)鏈接-程序在裝入內(nèi)程序在裝入內(nèi) 存時才將外部目標模塊鏈接成完整的可執(zhí)行的存時才將外部目標模塊鏈接成完整的可執(zhí)行的 目標模塊。目標模塊。 裝入時鏈接裝入時鏈接 地址地址 重定重定 位位 4096K 模塊模塊A Call B Return 模塊模塊B Call C Return 模塊模塊C Return 0 L-1 0 M-1

7、 0 N-1 OS 用戶用戶 可用可用 內(nèi)存內(nèi)存 空間空間 0 800K 模塊模塊A JSR “L” Return 模塊模塊B JSR “L+M” Return 模塊模塊C Return 0 L-1 L L+M-1 L+M L+M+N-1 作業(yè)作業(yè)B的目標模塊的目標模塊- -邏輯地址空間邏輯地址空間 基址寄存器基址寄存器 二、鏈接方式二、鏈接方式 3 3、運行時動態(tài)鏈接、運行時動態(tài)鏈接-由于程序在每由于程序在每 次運行時，可能運行的次運行時，可能運行的程序模塊可能不同，在程序模塊可能不同，在 程序得到運行時才將用到的目標模塊鏈接成完程序得到運行時才將用到的目標模塊鏈接成完 整的可執(zhí)行的目標模塊

8、。整的可執(zhí)行的目標模塊。 三、重定位三、重定位-完成相對（邏輯）地址轉(zhuǎn)換完成相對（邏輯）地址轉(zhuǎn)換 成內(nèi)存物理（絕對）地址的工作。分為靜態(tài)重成內(nèi)存物理（絕對）地址的工作。分為靜態(tài)重 定位和動態(tài)重定位。定位和動態(tài)重定位。 如下圖示：如下圖示： 相對地址相對地址 操作系統(tǒng)操作系統(tǒng)-50KB-50KB 0 50K 80K 130K 190K 256K 作業(yè)作業(yè)1-20KB 作業(yè)作業(yè)2-40KB 作業(yè)作業(yè)3-50KB 作業(yè)作業(yè)4-60KB 作業(yè)作業(yè)1-20KB 作業(yè)作業(yè)2-40KB 作業(yè)作業(yè)3-50KB 作業(yè)作業(yè)4-60KB 0 20K 40K 0 50K 60K 0 0 內(nèi)存物理地址內(nèi)存物理地址 重定

9、位重定位 5.2 5.2 連續(xù)空間分配連續(xù)空間分配 方式：單道連續(xù)、多道固定、多道可變方式：單道連續(xù)、多道固定、多道可變 5.2.1 5.2.1 單道連續(xù)分配單道連續(xù)分配 單道單道: :指指任一時刻內(nèi)存只有一道作業(yè)，任一時刻內(nèi)存只有一道作業(yè)， 該作業(yè)連續(xù)存放于內(nèi)存中。該作業(yè)連續(xù)存放于內(nèi)存中。 特點：易于理解，訪問效率高、空間利特點：易于理解，訪問效率高、空間利 用率低。用率低。 （1 1）內(nèi)存空間安排：內(nèi)存除存在）內(nèi)存空間安排：內(nèi)存除存在OSOS外，外， 余下的空間只供一個用戶程序使用。余下的空間只供一個用戶程序使用。 一、管理方法 操作系統(tǒng)操作系統(tǒng) 用戶程序用戶程序 0 a a a+1a+1

10、 n n 界地址寄存器界地址寄存器 （2）設置越界檢查機構(gòu)：用戶程序每訪用戶程序每訪 問一次主存，越界檢查機構(gòu)將訪問的地址問一次主存，越界檢查機構(gòu)將訪問的地址 與界地址寄存器中的值比較。若越界，則與界地址寄存器中的值比較。若越界，則 終止其執(zhí)行。終止其執(zhí)行。 falsefalse 界地址寄存器界地址寄存器 A Aa a CPUCPU truetrue 地址地址A A 終止程序運行終止程序運行 操作系統(tǒng)操作系統(tǒng) 用戶用戶 程序程序 0 a n a a （3 3）覆蓋（）覆蓋（overlapoverlap）技術(shù)）技術(shù) 引入原因：因內(nèi)存小于作業(yè)的程序引入原因：因內(nèi)存小于作業(yè)的程序 空間而引入覆蓋?？?/p>

11、間而引入覆蓋。 方法：將用戶空間劃分成一個固定方法：將用戶空間劃分成一個固定 區(qū)和多個覆蓋區(qū)。主程序放固定區(qū)，區(qū)和多個覆蓋區(qū)。主程序放固定區(qū)， 依次調(diào)用的子程序則放在同一個覆蓋依次調(diào)用的子程序則放在同一個覆蓋 區(qū)。操作系統(tǒng)提供覆蓋系統(tǒng)調(diào)用函數(shù)，區(qū)。操作系統(tǒng)提供覆蓋系統(tǒng)調(diào)用函數(shù)， 由用戶編程序時考慮調(diào)用。由用戶編程序時考慮調(diào)用。 操作系統(tǒng)操作系統(tǒng) 固定區(qū)固定區(qū)(4kB)(4kB) 覆蓋區(qū)覆蓋區(qū)(6kB)(6kB) 覆蓋區(qū)覆蓋區(qū)(10kB)(10kB) A(4kB)A(4kB) E(10kB)E(10kB)D(6kB)D(6kB) C(4kB)C(4kB)B(6kB)B(6kB) F(8kB)F(

12、8kB) 例例: :下圖的調(diào)用關(guān)系中下圖的調(diào)用關(guān)系中,B,B不會調(diào)用不會調(diào)用 C,CC,C也不會調(diào)用也不會調(diào)用B,B,所以過程所以過程B,CB,C不必不必 同時調(diào)入主存同時調(diào)入主存, , 同樣同樣D D、E E之間，之間，D D、 E E與與F F之間也有同樣的關(guān)系。之間也有同樣的關(guān)系。 多道：多道：任一時刻內(nèi)存可有多道作業(yè)，每道任一時刻內(nèi)存可有多道作業(yè)，每道 作業(yè)連續(xù)存放于內(nèi)存作業(yè)連續(xù)存放于內(nèi)存. . 5.2.2 5.2.2 多道固定劃分法多道固定劃分法 一、固定劃分管理方法一、固定劃分管理方法 （1 1）將用戶）將用戶 內(nèi)存空間分成內(nèi)存空間分成 長度固定的若長度固定的若 干塊。每塊分干塊。

13、每塊分 區(qū)的大小不一區(qū)的大小不一 定相等。定相等。 操作系統(tǒng)操作系統(tǒng) U1U1 . U Un n 用戶空間用戶空間 例如例如: :某存儲系統(tǒng)共某存儲系統(tǒng)共 256KB256KB采用固定分區(qū)采用固定分區(qū) 法，法，0-50K0-50K為為OSOS使用。使用。 50K-80K50K-80K為分區(qū)為分區(qū)1 1， 80K-130K80K-130K為分區(qū)為分區(qū)2 2， 130K-190K130K-190K為分區(qū)為分區(qū)3 3， 190K-256K190K-256K為分區(qū)為分區(qū)4 4。 見圖示見圖示 操作系統(tǒng)操作系統(tǒng)-50KB-50KB 分區(qū)分區(qū)1-30KB1-30KB 分區(qū)分區(qū)2-50KB2-50KB 分區(qū)

14、分區(qū)4-66KB4-66KB 0 50K 80K 130K 分區(qū)分區(qū)3-60KB3-60KB 190K 256K 這樣，內(nèi)存就可這樣，內(nèi)存就可 以同時裝入四個作以同時裝入四個作 業(yè)，分區(qū)業(yè)，分區(qū)1 1可裝入可裝入 小于小于30KB30KB的作業(yè)，的作業(yè)， 分區(qū)分區(qū)2 2可裝入小于可裝入小于 50KB50KB的作業(yè)，分區(qū)的作業(yè)，分區(qū) 3 3可裝入小于可裝入小于60KB60KB 的作業(yè)，分區(qū)的作業(yè)，分區(qū)4 4可可 裝入小于裝入小于66KB66KB的作的作 業(yè)。業(yè)。 操作系統(tǒng)操作系統(tǒng)-50KB-50KB 0 50K 80K 130K 190K 256K 作業(yè)作業(yè)1-20KB 作業(yè)作業(yè)2-40KB 作

15、業(yè)作業(yè)3-50KB 作業(yè)作業(yè)4-60KB 1.1.上下界寄存器上下界寄存器 的地址檢查機構(gòu)。的地址檢查機構(gòu)。 當作業(yè)被調(diào)度運行當作業(yè)被調(diào)度運行 時，作業(yè)在內(nèi)存中時，作業(yè)在內(nèi)存中 的上下界地址送上的上下界地址送上 下界寄存器，每次下界寄存器，每次 內(nèi)存訪問時，地址內(nèi)存訪問時，地址 檢查機構(gòu)作越界檢檢查機構(gòu)作越界檢 查。查。 （2 2）地址訪問保護技術(shù)的第一種方式）地址訪問保護技術(shù)的第一種方式 操作系統(tǒng)操作系統(tǒng)-50KB-50KB 0 50K 80K 130K 190K 256K 作業(yè)作業(yè)1-20KB 作業(yè)作業(yè)2-40KB 作業(yè)作業(yè)3-50KB 作業(yè)作業(yè)4-60KB （1 1）上下界寄存器和地址檢

16、查機構(gòu)。）上下界寄存器和地址檢查機構(gòu)。 CPUCPU 下界寄存器下界寄存器上界寄存器上界寄存器 TrueTrue TrueTrue 地址地址A A 程序性中斷程序性中斷 操作系統(tǒng)操作系統(tǒng)-50KB-50KB 0 50K 80K 130K 190K 256K 作業(yè)作業(yè)1-20KB 作業(yè)作業(yè)2-40KB 作業(yè)作業(yè)3-50KB 作業(yè)作業(yè)4-60KB 靜態(tài)重定位：靜態(tài)重定位：指用戶代碼中使用的相對指用戶代碼中使用的相對 地址地址, ,連接程序連接程序?qū)⑵溲b配成絕對地址。將其裝配成絕對地址。 （即：在裝入一個作業(yè)時，把該作業(yè)中（即：在裝入一個作業(yè)時，把該作業(yè)中 的程序和數(shù)據(jù)地址一次全部轉(zhuǎn)換成絕對的程序和

17、數(shù)據(jù)地址一次全部轉(zhuǎn)換成絕對 地址。地址。) ) （2 2）上下界寄存器和地址檢查機構(gòu)要）上下界寄存器和地址檢查機構(gòu)要 求作業(yè)采用靜態(tài)重定位技術(shù)。求作業(yè)采用靜態(tài)重定位技術(shù)。 100 500 : : MOV R1,(500) 123 0 700 例：程序例：程序A的邏輯地址空間如圖，將其裝的邏輯地址空間如圖，將其裝 入內(nèi)存。內(nèi)存起始地址為入內(nèi)存。內(nèi)存起始地址為5000號單元。用號單元。用 靜態(tài)重定位法畫出其裝入內(nèi)存后的情況。靜態(tài)重定位法畫出其裝入內(nèi)存后的情況。 MOV R1，(500) 表示：將表示：將500號單元號單元 （地址）的數(shù)據(jù)（地址）的數(shù)據(jù)123送入送入1號寄存器。號寄存器。 靜態(tài)重定位

18、裝入內(nèi)靜態(tài)重定位裝入內(nèi) 存后的情況：存后的情況： 100 500 : : MOV R1,(500) 123 0 700 5100 5500 5700 5000 邏輯地址邏輯地址 : : MOV R1,(5500) 123 0 內(nèi)存物理地址內(nèi)存物理地址 2 2. .基址寄存器、長基址寄存器、長 度寄存器的動態(tài)地度寄存器的動態(tài)地 址轉(zhuǎn)換機構(gòu)。址轉(zhuǎn)換機構(gòu)。當作當作 業(yè)被調(diào)度運行時，將業(yè)被調(diào)度運行時，將 作業(yè)所占內(nèi)存基址及作業(yè)所占內(nèi)存基址及 長度送基址、長度寄長度送基址、長度寄 存器，每次內(nèi)存訪問存器，每次內(nèi)存訪問 時，先看訪問地址是時，先看訪問地址是 否小于長度，然后否小于長度，然后+ +基基 址進

19、行訪存。見下圖。址進行訪存。見下圖。 操作系統(tǒng)操作系統(tǒng)-50KB-50KB 0 50K 80K 130K 190K 256K 作業(yè)作業(yè)1-20KB 作業(yè)作業(yè)2-40KB 作業(yè)作業(yè)3-50KB 作業(yè)作業(yè)4-60KB （2 2）地址訪問保護技術(shù)的第二種方式）地址訪問保護技術(shù)的第二種方式 CPUCPU 基地址寄存器基地址寄存器長度寄存器長度寄存器 + + TrueTrue地址地址A A false false 程序性中斷程序性中斷 OSOS 作業(yè)作業(yè)1 1 作業(yè)作業(yè)2 2 作業(yè)作業(yè)3 3 作業(yè)作業(yè)4 4 例：例：CPU要訪問上例作業(yè)要訪問上例作業(yè)2的的 A地址時的檢查過程地址時的檢查過程 CPUCP

20、U 基地址基地址80K80K限長限長40K40K + + TrueTrue地址地址A A false false 程序性中斷程序性中斷 操作系統(tǒng)操作系統(tǒng)-50KB-50KB 0 50K 80K 130K 190K 256K 作業(yè)作業(yè)1-20KB 作業(yè)作業(yè)2-40KB 作業(yè)作業(yè)3-50KB 作業(yè)作業(yè)4-60KB 動態(tài)重定位：動態(tài)重定位：指用戶代碼中的相對指用戶代碼中的相對 地址先原封不動地裝入內(nèi)存指定地地址先原封不動地裝入內(nèi)存指定地 址，在執(zhí)行期間才被動態(tài)地轉(zhuǎn)換成址，在執(zhí)行期間才被動態(tài)地轉(zhuǎn)換成 絕對地址絕對地址. . （2 2）基址寄存器、長度寄存器和）基址寄存器、長度寄存器和 動態(tài)地址轉(zhuǎn)換機構(gòu)

21、要求作業(yè)采用動動態(tài)地址轉(zhuǎn)換機構(gòu)要求作業(yè)采用動 態(tài)重定位技術(shù)態(tài)重定位技術(shù) 100 500 : : MOV R1,(500) 123 0 700 : : MOV R1,(500) 123 0 內(nèi)存絕對地址內(nèi)存絕對地址 5000 5100 5500 5700 + 5000 基址寄存器基址寄存器 相對地此相對地此 700? 長度寄存器長度寄存器 700 Y N 程序性中斷程序性中斷 又例動態(tài)重定位的實現(xiàn)過程。指令又例動態(tài)重定位的實現(xiàn)過程。指令MOV MOV R1,(3000)R1,(3000)（即把相對地址為（即把相對地址為30003000的單元的單元 中的中的123123取到取到1 1號寄存器）號寄

22、存器） （3 3）多道固定劃分法的作業(yè)調(diào)度技術(shù)）多道固定劃分法的作業(yè)調(diào)度技術(shù) OS 4kB 6kB 12kB .3kB 4kB1kB2kB .5kB6kB .7kB 10kB 11kB8kB （1 1）多隊列法）多隊列法 OS 4kB 6kB 12kB .7kB 3kB 4kB5kB （2 2）單隊列）單隊列法法 （4 4）固定分區(qū)法存在碎片問題）固定分區(qū)法存在碎片問題 內(nèi)部碎片：內(nèi)存某存儲區(qū)間大于其存放作內(nèi)部碎片：內(nèi)存某存儲區(qū)間大于其存放作 業(yè)空間的部分。如：作業(yè)只有業(yè)空間的部分。如：作業(yè)只有 3KB3KB時，而某內(nèi)存固定分區(qū)有時，而某內(nèi)存固定分區(qū)有4KB4KB。有。有1KB1KB內(nèi)內(nèi) 部碎

23、片。部碎片。 OS 12KB 固定固定 4KB 3KB 內(nèi)部碎片內(nèi)部碎片 外部碎片：內(nèi)存某存儲區(qū)間容不下要運行外部碎片：內(nèi)存某存儲區(qū)間容不下要運行 的作業(yè)時。的作業(yè)時。 如：作業(yè)長度為：如：作業(yè)長度為：5KB5KB，8KB8KB，12KB12KB時，若時，若 內(nèi)存固定分區(qū)只剩下內(nèi)存固定分區(qū)只剩下4KB4KB，則存在外部碎片。，則存在外部碎片。 OSOS 4KB4KB 6KB6KB 12KB12KB 外部碎片外部碎片 一、管理方法 5.2.3 多道連續(xù)可變劃分法 特點：多道、連續(xù)、但不固定劃分內(nèi)存。多道、連續(xù)、但不固定劃分內(nèi)存。 系統(tǒng)設置一個空閑塊隊列，初始狀態(tài)系統(tǒng)設置一個空閑塊隊列，初始狀態(tài)

24、時隊列中只有一個連續(xù)的空閑塊。作業(yè)時隊列中只有一個連續(xù)的空閑塊。作業(yè) 到達后，作業(yè)有多大就分配多大的空間。到達后，作業(yè)有多大就分配多大的空間。 作業(yè)撤離時，將釋放的空間加入空閑隊作業(yè)撤離時，將釋放的空間加入空閑隊 列。列。 例題例題1 1：有以下：有以下4 4個作業(yè)，采用多道連續(xù)分個作業(yè)，采用多道連續(xù)分 配技術(shù)配技術(shù) 作業(yè)作業(yè)1-20KB 作業(yè)作業(yè)2-40KB 作業(yè)作業(yè)3-50KB 作業(yè)作業(yè)4-60KB 0 20K 40K 0 50K 60K 0 0 操作系統(tǒng)操作系統(tǒng)-50KB-50KB 空閑區(qū)空閑區(qū) 0 50K 70K 110K 160K 256K 作業(yè)作業(yè)1-20KB 作業(yè)作業(yè)2-40KB

25、 作業(yè)作業(yè)3-50KB 作業(yè)作業(yè)4-60KB 220K 例題例題2 2：有以下：有以下5 5個作業(yè)，假設任一時間段個作業(yè)，假設任一時間段 內(nèi)，內(nèi)存中每一作業(yè)的運行時間相等，采內(nèi)，內(nèi)存中每一作業(yè)的運行時間相等，采 用用FCFSFCFS作業(yè)調(diào)度方法。作業(yè)調(diào)度方法。 作業(yè)到來次序作業(yè)到來次序 所需存儲量所需存儲量 運行時間運行時間 J1 60KB 10s J2 100KB 5s J3 30KB 20s J4 70KB 8s J5 50KB 15s OS 0 40K 256K J1J2J3J4J5 共190K 二、可變分區(qū)中的數(shù)據(jù)結(jié)構(gòu)二、可變分區(qū)中的數(shù)據(jù)結(jié)構(gòu) 常用的數(shù)據(jù)結(jié)構(gòu)有兩種：空閑分區(qū)表和常用的數(shù)

26、據(jù)結(jié)構(gòu)有兩種：空閑分區(qū)表和 空閑分區(qū)鏈?？臻e分區(qū)鏈。 (1)(1)空閑分區(qū)表。為內(nèi)存中每個尚未分配空閑分區(qū)表。為內(nèi)存中每個尚未分配 出去的分區(qū)設置一個表項，每個表項包含分出去的分區(qū)設置一個表項，每個表項包含分 區(qū)序號、分區(qū)起始地址和分區(qū)的大小。區(qū)序號、分區(qū)起始地址和分區(qū)的大小。 例：根據(jù)右圖的內(nèi)存使用情況填寫空閑分區(qū)例：根據(jù)右圖的內(nèi)存使用情況填寫空閑分區(qū) 表。表。 操作系統(tǒng)操作系統(tǒng) 空閑區(qū)空閑區(qū)1(26KB) 已使用已使用 空閑區(qū)空閑區(qū)2(14KB) 已使用已使用 空閑區(qū)空閑區(qū)3(5KB) 已使用已使用 空閑區(qū)空閑區(qū)4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k

27、105k 150k 180k 256k 空閑分區(qū)表空閑分區(qū)表 分區(qū)分區(qū) 序號序號 分區(qū)起分區(qū)起 始地址始地址 分區(qū)分區(qū) 大小大小 140k26kB 270k14kB 3100k5kB 4150k30kB (2) (2)空閑分區(qū)鏈。在每個空閑分區(qū)中設置空閑分區(qū)鏈。在每個空閑分區(qū)中設置 用于控制分區(qū)分配的信息及用于鏈接各個分用于控制分區(qū)分配的信息及用于鏈接各個分 區(qū)的指針，將內(nèi)存中的空閑分區(qū)鏈接成一個區(qū)的指針，將內(nèi)存中的空閑分區(qū)鏈接成一個 鏈表。不同的分配算法鏈表的組織方式不同。鏈表。不同的分配算法鏈表的組織方式不同。 三、可變分區(qū)分配算法三、可變分區(qū)分配算法 ( (一一) )首次適應首次適應(F

28、irst Fit)(First Fit)算法。算法。 該算法要求空閑分區(qū)以地址遞增的次序該算法要求空閑分區(qū)以地址遞增的次序 排序。排序。 如果采用的是鏈表結(jié)構(gòu)，分配時則從鏈如果采用的是鏈表結(jié)構(gòu)，分配時則從鏈 表的開始順序進行查找，直到找到一個能夠表的開始順序進行查找，直到找到一個能夠 滿足進程大小要求的空閑分區(qū)為止。然后，滿足進程大小要求的空閑分區(qū)為止。然后， 按進程的大小，從分區(qū)中按進程的大小，從分區(qū)中“切出切出”一塊內(nèi)存一塊內(nèi)存 空間分配給請求者，余下的空閑分區(qū)仍然留空間分配給請求者，余下的空閑分區(qū)仍然留 在鏈表中。在鏈表中。 例例1 1：根據(jù)右圖的內(nèi)存使用：根據(jù)右圖的內(nèi)存使用 情況畫出首

29、次適應算法的鏈情況畫出首次適應算法的鏈 表組織形式及分配一個表組織形式及分配一個10KB10KB 的作業(yè)后的情況。的作業(yè)后的情況。 操作系統(tǒng)操作系統(tǒng) 空閑區(qū)空閑區(qū)1(26KB) 已使用已使用 空閑區(qū)空閑區(qū)2(14KB) 已使用已使用 空閑區(qū)空閑區(qū)3(5KB) 已使用已使用 空閑區(qū)空閑區(qū)4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 1 1解：解：（1 1）分配一個分配一個10KB10KB 的作業(yè)前的鏈表組織形式。的作業(yè)前的鏈表組織形式。 40k 26kB 70k 14kB 100k 5kB 150k 30kB 70k100k

30、150k （2 2）分配一個）分配一個10KB10KB的作業(yè)后的的作業(yè)后的 鏈表組織形式。鏈表組織形式。 50k 16kB 70k 14kB 100k 5kB 150k 30kB 70k100k150k 操作系統(tǒng)操作系統(tǒng) 空閑區(qū)空閑區(qū)1(26kB) 已使用已使用 空閑區(qū)空閑區(qū)2(14kB) 已使用已使用 空閑區(qū)空閑區(qū)3(5kB) 已使用已使用 空閑區(qū)空閑區(qū)4(30kB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 表頭指針表頭指針 表頭指針表頭指針 三、可變分區(qū)分配算法三、可變分區(qū)分配算法 ( (二二) )下次適應下次適應(Next F

31、it)(Next Fit)算法。算法。 該算法從首次適應算法演變而來。為了避該算法從首次適應算法演變而來。為了避 免低地址部分小空閑分區(qū)的不斷增加，在給進免低地址部分小空閑分區(qū)的不斷增加，在給進 程分配內(nèi)存空間時，不再每次從鏈首開始查找，程分配內(nèi)存空間時，不再每次從鏈首開始查找， 而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)而是從上次找到的空閑分區(qū)的下一個空閑分區(qū) 開始查找，直到找到一個能滿足要求的空閑分開始查找，直到找到一個能滿足要求的空閑分 區(qū)，并從中區(qū)，并從中“切出切出”一塊與請求的大小相等的一塊與請求的大小相等的 內(nèi)存空間分配出去。內(nèi)存空間分配出去。 例例2 2：根據(jù)右圖的內(nèi)存使用：根據(jù)右

32、圖的內(nèi)存使用 情況畫出下次適應算法的鏈情況畫出下次適應算法的鏈 表組織形式及分配一個表組織形式及分配一個10KB10KB 的作業(yè)后的情況。假設上次的作業(yè)后的情況。假設上次 找到的空閑分區(qū)是空閑區(qū)找到的空閑分區(qū)是空閑區(qū)1 1。 操作系統(tǒng)操作系統(tǒng) 空閑區(qū)空閑區(qū)1(16kB) 已使用已使用 空閑區(qū)空閑區(qū)2(14KB) 已使用已使用 空閑區(qū)空閑區(qū)3(5KB) 已使用已使用 空閑區(qū)空閑區(qū)4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 50k 已使用已使用 2 2解：解：（1 1）分配一個分配一個10KB10KB 的作業(yè)前的鏈表組織形式

33、。的作業(yè)前的鏈表組織形式。 （2 2）分配一個）分配一個10KB10KB的作業(yè)后的的作業(yè)后的 鏈表組織形式。鏈表組織形式。 50k 16kB 70k 14KB 100k 5KB 150k 30kB 70k100k150k 50k 16KB 80k 4KB 100k 5KB 150k 30KB 80k100k150k 操作系統(tǒng)操作系統(tǒng) 空閑區(qū)空閑區(qū)1(16kB) 已使用已使用 空閑區(qū)空閑區(qū)2(14kB) 已使用已使用 空閑區(qū)空閑區(qū)3(5kB) 已使用已使用 空閑區(qū)空閑區(qū)4(30kB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 50k 已

34、使用已使用 表頭指針表頭指針 表頭指針表頭指針 三、可變分區(qū)分配算法三、可變分區(qū)分配算法 ( (三三) )最佳適應最佳適應(Best Fit)算法。算法。 最佳的含義是指每次為進程分配內(nèi)存最佳的含義是指每次為進程分配內(nèi)存 時，總是把與進程大小最匹配的空閑分區(qū)時，總是把與進程大小最匹配的空閑分區(qū) 分配出去。分配出去。 該算法若采用的數(shù)據(jù)結(jié)構(gòu)是空閑分區(qū)該算法若采用的數(shù)據(jù)結(jié)構(gòu)是空閑分區(qū) 鏈，首先要求將空閑分區(qū)，按分區(qū)大小遞鏈，首先要求將空閑分區(qū)，按分區(qū)大小遞 增的順序形成一空閑分區(qū)鏈。當進程要求增的順序形成一空閑分區(qū)鏈。當進程要求 分配內(nèi)存時，第一次找到的滿足要求的空分配內(nèi)存時，第一次找到的滿足要求

35、的空 閑區(qū)，必然是最優(yōu)的。閑區(qū)，必然是最優(yōu)的。 例例3 3：根據(jù)右圖的內(nèi)存使用：根據(jù)右圖的內(nèi)存使用 情況畫出最佳適應算法的鏈情況畫出最佳適應算法的鏈 表組織形式及分配一個表組織形式及分配一個10KB10KB 的作業(yè)后的情況。的作業(yè)后的情況。 操作系統(tǒng)操作系統(tǒng) 空閑區(qū)空閑區(qū)1(26KB) 已使用已使用 空閑區(qū)空閑區(qū)2(14KB) 已使用已使用 空閑區(qū)空閑區(qū)3(5KB) 已使用已使用 空閑區(qū)空閑區(qū)4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 3 3解：解：（1 1）分配一個分配一個10KB10KB 的作業(yè)前的鏈表組織形式。的作

36、業(yè)前的鏈表組織形式。 100k 5KB 70k 14KB 40k 26KB 150k 30KB 70k40k150k （2 2）分配一個）分配一個10KB10KB的作業(yè)后的的作業(yè)后的 鏈表組織形式。鏈表組織形式。 80k 4KB 100k 5KB 40k 26KB 150k 30KB 100k40k150k 操作系統(tǒng)操作系統(tǒng) 空閑區(qū)空閑區(qū)1(26KB) 已使用已使用 空閑區(qū)空閑區(qū)2(14KB) 已使用已使用 空閑區(qū)空閑區(qū)3(5KB) 已使用已使用 空閑區(qū)空閑區(qū)4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 表頭指針表頭指針

37、表頭指針表頭指針 三、可變分區(qū)分配算法三、可變分區(qū)分配算法 ( (四四) )最壞適應最壞適應(Worst Fit)算法。算法。 該算法與最佳適應算法相反，要求空該算法與最佳適應算法相反，要求空 閑分區(qū)按分區(qū)大小遞減的順序排序，每次閑分區(qū)按分區(qū)大小遞減的順序排序，每次 分配時，從鏈首找到最大的空閑分區(qū)分配時，從鏈首找到最大的空閑分區(qū)“切切 出出”一塊進行分配。一塊進行分配。 該算法的特點是基本上不會留下小空該算法的特點是基本上不會留下小空 閑分區(qū)，不易形成碎片。缺點是大的空閑閑分區(qū)，不易形成碎片。缺點是大的空閑 分區(qū)被切割，當有較大的進程需要運行時，分區(qū)被切割，當有較大的進程需要運行時， 系統(tǒng)往

38、往不能滿足要求。系統(tǒng)往往不能滿足要求。 例例4 4：根據(jù)右圖的內(nèi)存使用：根據(jù)右圖的內(nèi)存使用 情況畫出最壞適應算法的鏈情況畫出最壞適應算法的鏈 表組織形式及分配一個表組織形式及分配一個10KB10KB 的作業(yè)后的情況。的作業(yè)后的情況。 操作系統(tǒng)操作系統(tǒng) 空閑區(qū)空閑區(qū)1(26KB) 已使用已使用 空閑區(qū)空閑區(qū)2(14KB) 已使用已使用 空閑區(qū)空閑區(qū)3(5KB) 已使用已使用 空閑區(qū)空閑區(qū)4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 4 4解：解：（1 1）分配一個分配一個10KB10KB 的作業(yè)前的鏈表組織形式。的作業(yè)前的鏈

39、表組織形式。 150k 30KB 40k 26KB 70k 14KB 100k 5KB 40k70k100k （2 2）分配一個）分配一個10KB10KB的作業(yè)后的的作業(yè)后的 鏈表組織形式。鏈表組織形式。 40k 26KB 160k 20KB 70k 14KB 100k 5KB 160k70k100k 操作系統(tǒng)操作系統(tǒng) 空閑區(qū)空閑區(qū)1(26KB) 已使用已使用 空閑區(qū)空閑區(qū)2(14KB) 已使用已使用 空閑區(qū)空閑區(qū)3(5KB) 已使用已使用 空閑區(qū)空閑區(qū)4(30KB) 已使用已使用 0k 40k 66k 70k 84k 100k 105k 150k 180k 256k 表頭指針表頭指針 表頭指針表頭指針 四、可變分區(qū)的作業(yè)