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

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

2、何從外存調(diào)入內(nèi)存。從外存調(diào)入內(nèi)存。存儲(chǔ)管理研究的內(nèi)容存儲(chǔ)管理研究的內(nèi)容預(yù)調(diào)：預(yù)調(diào)：訪問前訪問前預(yù)先調(diào)入內(nèi)存預(yù)先調(diào)入內(nèi)存請調(diào)：請調(diào)：因空間不因空間不足，訪問時(shí)請求足，訪問時(shí)請求調(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第三個(gè)的問題：換（第三個(gè)的問題：換（ReplacementReplacement），即），即請求從外存調(diào)入的頁或段與內(nèi)存中的哪些請求從外存調(diào)入的頁或段與內(nèi)存中的哪些塊或哪個(gè)存儲(chǔ)區(qū)對換？塊或哪個(gè)存儲(chǔ)區(qū)對換？存儲(chǔ)

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

4、010K鏈接鏈接主程主程序段序段子主程子主程序段序段數(shù)據(jù)段數(shù)據(jù)段堆棧段堆棧段0100K裝入裝入OS用戶用戶可用可用空間空間地址地址重定重定位位0800K4096K作業(yè)作業(yè)A的源的源程序程序-名名空間空間作業(yè)作業(yè)A的目標(biāo)的目標(biāo)模塊模塊-邏輯邏輯地址空間地址空間作業(yè)作業(yè)A重定位重定位后的物理地址后的物理地址空間空間作業(yè)作業(yè)A的目標(biāo)的目標(biāo)程序程序(可執(zhí)行可執(zhí)行文件文件)-邏輯邏輯地址空間地址空間二、鏈接方式二、鏈接方式 1 1、靜態(tài)鏈接、靜態(tài)鏈接-程序運(yùn)行之前就事先程序運(yùn)行之前就事先將外部目標(biāo)模塊鏈接成可執(zhí)行文件，稱為靜態(tài)將外部目標(biāo)模塊鏈接成可執(zhí)行文件，稱為靜態(tài)鏈接。例：如下作業(yè)鏈接。例：如下作業(yè)B

5、 B有三個(gè)目標(biāo)程序模塊。有三個(gè)目標(biāo)程序模塊。 鏈接鏈接裝入裝入OS用戶用戶可用可用空間空間地址地址重定重定位位0800K4096K模塊模塊ACall BReturn模塊模塊BCall CReturn模塊模塊CReturn0L-10M-10N-1模塊模塊AJSR “L”Return模塊模塊BJSR “L+M”Return模塊模塊CReturn0L-1LL+M-1L+ML+M+N-1作業(yè)作業(yè)B的目標(biāo)模塊的目標(biāo)模塊-邏輯地址空間邏輯地址空間作業(yè)作業(yè)B的目標(biāo)的目標(biāo)程序程序(可執(zhí)行可執(zhí)行文件文件)-邏輯邏輯地址空間地址空間二、鏈接方式二、鏈接方式2 2、裝入時(shí)動(dòng)態(tài)鏈接、裝入時(shí)動(dòng)態(tài)鏈接-程序在裝入內(nèi)程序在

6、裝入內(nèi)存時(shí)才將外部目標(biāo)模塊鏈接成完整的可執(zhí)行的存時(shí)才將外部目標(biāo)模塊鏈接成完整的可執(zhí)行的目標(biāo)模塊。目標(biāo)模塊。 裝入時(shí)鏈接裝入時(shí)鏈接地址地址重定重定位位4096K模塊模塊ACall BReturn模塊模塊BCall CReturn模塊模塊CReturn0L-10M-10N-1OS用戶用戶可用可用內(nèi)存內(nèi)存空間空間0800K模塊模塊AJSR “L”Return模塊模塊BJSR “L+M”Return模塊模塊CReturn0L-1LL+M-1L+ML+M+N-1作業(yè)作業(yè)B的目標(biāo)模塊的目標(biāo)模塊-邏輯地址空間邏輯地址空間基址寄存器基址寄存器二、鏈接方式二、鏈接方式3 3、運(yùn)行時(shí)動(dòng)態(tài)鏈接、運(yùn)行時(shí)動(dòng)態(tài)鏈接-由于

7、程序在每由于程序在每次運(yùn)行時(shí)，可能運(yùn)行的次運(yùn)行時(shí)，可能運(yùn)行的程序模塊可能不同，在程序模塊可能不同，在程序得到運(yùn)行時(shí)才將用到的目標(biāo)模塊鏈接成完程序得到運(yùn)行時(shí)才將用到的目標(biāo)模塊鏈接成完整的可執(zhí)行的目標(biāo)模塊。整的可執(zhí)行的目標(biāo)模塊。 三、重定位三、重定位-完成相對（邏輯）地址轉(zhuǎn)換完成相對（邏輯）地址轉(zhuǎn)換成內(nèi)存物理（絕對）地址的工作。分為靜態(tài)重成內(nèi)存物理（絕對）地址的工作。分為靜態(tài)重定位和動(dòng)態(tài)重定位。定位和動(dòng)態(tài)重定位。如下圖示：如下圖示：相對地址相對地址操作系統(tǒng)操作系統(tǒng)-50KB-50KB050K80K130K190K256K作業(yè)作業(yè)1-20KB作業(yè)作業(yè)2-40KB作業(yè)作業(yè)3-50KB作業(yè)作業(yè)4-60K

8、B作業(yè)作業(yè)1-20KB作業(yè)作業(yè)2-40KB作業(yè)作業(yè)3-50KB作業(yè)作業(yè)4-60KB020K40K050K60K00內(nèi)存物理地址內(nèi)存物理地址重定位重定位5.2 5.2 連續(xù)空間分配連續(xù)空間分配 方式：單道連續(xù)、多道固定、多道可變方式：單道連續(xù)、多道固定、多道可變5.2.1 5.2.1 單道連續(xù)分配單道連續(xù)分配單道單道: :指指任一時(shí)刻內(nèi)存只有一道作業(yè)，任一時(shí)刻內(nèi)存只有一道作業(yè)，該作業(yè)連續(xù)存放于內(nèi)存中。該作業(yè)連續(xù)存放于內(nèi)存中。特點(diǎn)：易于理解，訪問效率高、空間利特點(diǎn)：易于理解，訪問效率高、空間利用率低。用率低。（1 1）內(nèi)存空間安排：內(nèi)存除存在）內(nèi)存空間安排：內(nèi)存除存在OSOS外，外，余下的空間只供

9、一個(gè)用戶程序使用。余下的空間只供一個(gè)用戶程序使用。一、管理方法操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序0a aa+1a+1n n界地址寄存器界地址寄存器（2）設(shè)置越界檢查機(jī)構(gòu)：用戶程序每訪用戶程序每訪問一次主存，越界檢查機(jī)構(gòu)將訪問的地址問一次主存，越界檢查機(jī)構(gòu)將訪問的地址與界地址寄存器中的值比較。若越界，則與界地址寄存器中的值比較。若越界，則終止其執(zhí)行。終止其執(zhí)行。falsefalse界地址寄存器界地址寄存器A Aa aCPUCPUtruetrue地址地址A A終止程序運(yùn)行終止程序運(yùn)行操作系統(tǒng)操作系統(tǒng)用戶用戶程序程序0ana a（3 3）覆蓋（）覆蓋（overlapoverlap）技術(shù)）技術(shù) 引入原因

10、：因內(nèi)存小于作業(yè)的程序引入原因：因內(nèi)存小于作業(yè)的程序空間而引入覆蓋。空間而引入覆蓋。方法：將用戶空間劃分成一個(gè)固定方法：將用戶空間劃分成一個(gè)固定區(qū)和多個(gè)覆蓋區(qū)。主程序放固定區(qū)，區(qū)和多個(gè)覆蓋區(qū)。主程序放固定區(qū)，依次調(diào)用的子程序則放在同一個(gè)覆蓋依次調(diào)用的子程序則放在同一個(gè)覆蓋區(qū)。操作系統(tǒng)提供覆蓋系統(tǒng)調(diào)用函數(shù)，區(qū)。操作系統(tǒng)提供覆蓋系統(tǒng)調(diào)用函數(shù)，由用戶編程序時(shí)考慮調(diào)用。由用戶編程序時(shí)考慮調(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(4k

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

12、的若干塊。每塊分干塊。每塊分區(qū)的大小不一區(qū)的大小不一定相等。定相等。操作系統(tǒng)操作系統(tǒng)U1U1.U Un n用戶空間用戶空間 例如例如: :某存儲(chǔ)系統(tǒng)共某存儲(chǔ)系統(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ū)分區(qū)4-66K

13、B4-66KB050K80K130K分區(qū)分區(qū)3-60KB3-60KB190K256K 這樣，內(nèi)存就可這樣，內(nèi)存就可以同時(shí)裝入四個(gè)作以同時(shí)裝入四個(gè)作業(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-50KB050K80K130K190K256K作業(yè)作業(yè)1-20KB作業(yè)作業(yè)2-40KB作業(yè)作業(yè)3-50KB作業(yè)作業(yè)4-60KB 1.1.上下界寄存器上下界

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

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

16、態(tài)重定位技術(shù)。100500:MOV R1,(500)1230700例：程序例：程序A的邏輯地址空間如圖，將其裝的邏輯地址空間如圖，將其裝入內(nèi)存。內(nèi)存起始地址為入內(nèi)存。內(nèi)存起始地址為5000號(hào)單元。用號(hào)單元。用靜態(tài)重定位法畫出其裝入內(nèi)存后的情況。靜態(tài)重定位法畫出其裝入內(nèi)存后的情況。MOV R1，(500) 表示：將表示：將500號(hào)單元號(hào)單元（地址）的數(shù)據(jù)（地址）的數(shù)據(jù)123送入送入1號(hào)寄存器。號(hào)寄存器。靜態(tài)重定位裝入內(nèi)靜態(tài)重定位裝入內(nèi)存后的情況：存后的情況：100500:MOV R1,(500)12307005100550057005000邏輯地址邏輯地址:MOV R1,(5500)1230內(nèi)存

17、物理地址內(nèi)存物理地址2 2. .基址寄存器、長基址寄存器、長度寄存器的動(dòng)態(tài)地度寄存器的動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)。址轉(zhuǎn)換機(jī)構(gòu)。當(dāng)作當(dāng)作業(yè)被調(diào)度運(yùn)行時(shí)，將業(yè)被調(diào)度運(yùn)行時(shí)，將作業(yè)所占內(nèi)存基址及作業(yè)所占內(nèi)存基址及長度送基址、長度寄長度送基址、長度寄存器，每次內(nèi)存訪問存器，每次內(nèi)存訪問時(shí)，先看訪問地址是時(shí)，先看訪問地址是否小于長度，然后否小于長度，然后+ +基基址進(jìn)行訪存。見下圖。址進(jìn)行訪存。見下圖。操作系統(tǒng)操作系統(tǒng)-50KB-50KB050K80K130K190K256K作業(yè)作業(yè)1-20KB作業(yè)作業(yè)2-40KB作業(yè)作業(yè)3-50KB作業(yè)作業(yè)4-60KB（2 2）地址訪問保護(hù)技術(shù)的第二種方式）地址訪問保護(hù)技術(shù)的第

18、二種方式CPUCPU基地址寄存器基地址寄存器長度寄存器長度寄存器 + +TrueTrue地址地址A Afalse false 程序性中斷程序性中斷OSOS作業(yè)作業(yè)1 1作業(yè)作業(yè)2 2作業(yè)作業(yè)3 3作業(yè)作業(yè)4 4例：例：CPU要訪問上例作業(yè)要訪問上例作業(yè)2的的A地址時(shí)的檢查過程地址時(shí)的檢查過程CPUCPU基地址基地址80K80K限長限長40K40K + +TrueTrue地址地址A Afalse false 程序性中斷程序性中斷操作系統(tǒng)操作系統(tǒng)-50KB-50KB050K80K130K190K256K作業(yè)作業(yè)1-20KB作業(yè)作業(yè)2-40KB作業(yè)作業(yè)3-50KB作業(yè)作業(yè)4-60KB動(dòng)態(tài)重定位：動(dòng)態(tài)

19、重定位：指用戶代碼中的相對指用戶代碼中的相對地址先原封不動(dòng)地裝入內(nèi)存指定地地址先原封不動(dòng)地裝入內(nèi)存指定地址，在執(zhí)行期間才被動(dòng)態(tài)地轉(zhuǎn)換成址，在執(zhí)行期間才被動(dòng)態(tài)地轉(zhuǎn)換成絕對地址絕對地址. .（2 2）基址寄存器、長度寄存器和）基址寄存器、長度寄存器和動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)要求作業(yè)采用動(dòng)動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)要求作業(yè)采用動(dòng)態(tài)重定位技術(shù)態(tài)重定位技術(shù)100500:MOV R1,(500)1230700:MOV R1,(500)1230 內(nèi)存絕對地址內(nèi)存絕對地址5000510055005700+5000 基址寄存器基址寄存器相對地此相對地此700?長度寄存器長度寄存器700YN程序性中斷程序性中斷又例動(dòng)態(tài)重定位的實(shí)現(xiàn)

20、過程。指令又例動(dòng)態(tài)重定位的實(shí)現(xiàn)過程。指令MOV MOV R1,(3000)R1,(3000)（即把相對地址為（即把相對地址為30003000的單元的單元中的中的123123取到取到1 1號(hào)寄存器）號(hào)寄存器）（3 3）多道固定劃分法的作業(yè)調(diào)度技術(shù)）多道固定劃分法的作業(yè)調(diào)度技術(shù)OS4kB6kB12kB.3kB 4kB1kB2kB.5kB6kB.7kB 10kB 11kB8kB（1 1）多隊(duì)列法）多隊(duì)列法OS4kB6kB12kB.7kB 3kB 4kB5kB（2 2）單隊(duì)列）單隊(duì)列法法（4 4）固定分區(qū)法存在碎片問題）固定分區(qū)法存在碎片問題 內(nèi)部碎片：內(nèi)存某存儲(chǔ)區(qū)間大于其存放作內(nèi)部碎片：內(nèi)存某存儲(chǔ)區(qū)

21、間大于其存放作 業(yè)空間的部分。如：作業(yè)只有業(yè)空間的部分。如：作業(yè)只有3KB3KB時(shí)，而某內(nèi)存固定分區(qū)有時(shí)，而某內(nèi)存固定分區(qū)有4KB4KB。有。有1KB1KB內(nèi)內(nèi)部碎片。部碎片。 OS12KB固定固定4KB3KB內(nèi)部碎片內(nèi)部碎片外部碎片：內(nèi)存某存儲(chǔ)區(qū)間容不下要運(yùn)行外部碎片：內(nèi)存某存儲(chǔ)區(qū)間容不下要運(yùn)行 的作業(yè)時(shí)。的作業(yè)時(shí)。如：作業(yè)長度為：如：作業(yè)長度為：5KB5KB，8KB8KB，12KB12KB時(shí)，若時(shí)，若內(nèi)存固定分區(qū)只剩下內(nèi)存固定分區(qū)只剩下4KB4KB，則存在外部碎片。，則存在外部碎片。OSOS4KB4KB6KB6KB12KB12KB外部碎片外部碎片 一、管理方法5.2.3 多道連續(xù)可變劃分法

22、特點(diǎn)：多道、連續(xù)、但不固定劃分內(nèi)存。多道、連續(xù)、但不固定劃分內(nèi)存。 系統(tǒng)設(shè)置一個(gè)空閑塊隊(duì)列，初始狀態(tài)系統(tǒng)設(shè)置一個(gè)空閑塊隊(duì)列，初始狀態(tài)時(shí)隊(duì)列中只有一個(gè)連續(xù)的空閑塊。作業(yè)時(shí)隊(duì)列中只有一個(gè)連續(xù)的空閑塊。作業(yè)到達(dá)后，作業(yè)有多大就分配多大的空間。到達(dá)后，作業(yè)有多大就分配多大的空間。作業(yè)撤離時(shí)，將釋放的空間加入空閑隊(duì)作業(yè)撤離時(shí)，將釋放的空間加入空閑隊(duì)列。列。例題例題1 1：有以下：有以下4 4個(gè)作業(yè)，采用多道連續(xù)分個(gè)作業(yè)，采用多道連續(xù)分配技術(shù)配技術(shù)作業(yè)作業(yè)1-20KB作業(yè)作業(yè)2-40KB作業(yè)作業(yè)3-50KB作業(yè)作業(yè)4-60KB020K40K050K60K00操作系統(tǒng)操作系統(tǒng)-50KB-50KB空閑區(qū)空閑區(qū)

23、050K70K110K160K256K作業(yè)作業(yè)1-20KB作業(yè)作業(yè)2-40KB作業(yè)作業(yè)3-50KB作業(yè)作業(yè)4-60KB220K例題例題2 2：有以下：有以下5 5個(gè)作業(yè)，假設(shè)任一時(shí)間段個(gè)作業(yè)，假設(shè)任一時(shí)間段內(nèi)，內(nèi)存中每一作業(yè)的運(yùn)行時(shí)間相等，采內(nèi)，內(nèi)存中每一作業(yè)的運(yùn)行時(shí)間相等，采用用FCFSFCFS作業(yè)調(diào)度方法。作業(yè)調(diào)度方法。作業(yè)到來次序作業(yè)到來次序 所需存儲(chǔ)量所需存儲(chǔ)量 運(yùn)行時(shí)間運(yùn)行時(shí)間J1 60KB 10sJ2 100KB 5sJ3 30KB 20sJ4 70KB 8sJ5 50KB 15sOS0 40K 256KJ1J2J3J4J5共190K二、可變分區(qū)中的數(shù)據(jù)結(jié)構(gòu)二、可變分區(qū)中的數(shù)據(jù)結(jié)構(gòu)

24、 常用的數(shù)據(jù)結(jié)構(gòu)有兩種：空閑分區(qū)表和常用的數(shù)據(jù)結(jié)構(gòu)有兩種：空閑分區(qū)表和空閑分區(qū)鏈?？臻e分區(qū)鏈。 (1)(1)空閑分區(qū)表。為內(nèi)存中每個(gè)尚未分配空閑分區(qū)表。為內(nèi)存中每個(gè)尚未分配出去的分區(qū)設(shè)置一個(gè)表項(xiàng)，每個(gè)表項(xiàng)包含分出去的分區(qū)設(shè)置一個(gè)表項(xiàng)，每個(gè)表項(xiàng)包含分區(qū)序號(hào)、分區(qū)起始地址和分區(qū)的大小。區(qū)序號(hào)、分區(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)已使用已使用0k40k66k70k84k10

25、0k105k150k180k256k空閑分區(qū)表分區(qū)序號(hào)分區(qū)起始地址分區(qū)大小140k26kB270k14kB3100k5kB4150k30kB (2) (2)空閑分區(qū)鏈。在每個(gè)空閑分區(qū)中設(shè)置空閑分區(qū)鏈。在每個(gè)空閑分區(qū)中設(shè)置用于控制分區(qū)分配的信息及用于鏈接各個(gè)分用于控制分區(qū)分配的信息及用于鏈接各個(gè)分區(qū)的指針，將內(nèi)存中的空閑分區(qū)鏈接成一個(gè)區(qū)的指針，將內(nèi)存中的空閑分區(qū)鏈接成一個(gè)鏈表。不同的分配算法鏈表的組織方式不同。鏈表。不同的分配算法鏈表的組織方式不同。三、可變分區(qū)分配算法三、可變分區(qū)分配算法 ( (一一) )首次適應(yīng)首次適應(yīng)(First Fit)(First Fit)算法。算法。 該算法要求空閑分

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

27、10KB的作業(yè)后的情況。的作業(yè)后的情況。操作系統(tǒng)操作系統(tǒng)空閑區(qū)空閑區(qū)1(26KB)已使用已使用空閑區(qū)空閑區(qū)2(14KB)已使用已使用空閑區(qū)空閑區(qū)3(5KB)已使用已使用空閑區(qū)空閑區(qū)4(30KB)已使用已使用0k40k66k70k84k100k105k150k180k256k1 1解：解：（1 1）分配一個(gè)分配一個(gè)10KB10KB的作業(yè)前的鏈表組織形式。的作業(yè)前的鏈表組織形式。40k26kB70k14kB100k5kB150k30kB70k100k150k（2 2）分配一個(gè)）分配一個(gè)10KB10KB的作業(yè)后的的作業(yè)后的鏈表組織形式。鏈表組織形式。50k16kB70k14kB100k5kB150k

28、30kB70k100k150k操作系統(tǒng)操作系統(tǒng)空閑區(qū)空閑區(qū)1(26kB)已使用已使用空閑區(qū)空閑區(qū)2(14kB)已使用已使用空閑區(qū)空閑區(qū)3(5kB)已使用已使用空閑區(qū)空閑區(qū)4(30kB)已使用已使用0k40k66k70k84k100k105k150k180k256k表頭指針表頭指針表頭指針表頭指針三、可變分區(qū)分配算法三、可變分區(qū)分配算法 ( (二二) )下次適應(yīng)下次適應(yīng)(Next Fit)(Next Fit)算法。算法。 該算法從首次適應(yīng)算法演變而來。為了避該算法從首次適應(yīng)算法演變而來。為了避免低地址部分小空閑分區(qū)的不斷增加，在給進(jìn)免低地址部分小空閑分區(qū)的不斷增加，在給進(jìn)程分配內(nèi)存空間時(shí)，不再每

29、次從鏈?zhǔn)组_始查找，程分配內(nèi)存空間時(shí)，不再每次從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直到找到一個(gè)能滿足要求的空閑分開始查找，直到找到一個(gè)能滿足要求的空閑分區(qū)，并從中區(qū)，并從中“切出切出”一塊與請求的大小相等的一塊與請求的大小相等的內(nèi)存空間分配出去。內(nèi)存空間分配出去。例例2 2：根據(jù)右圖的內(nèi)存使用：根據(jù)右圖的內(nèi)存使用情況畫出下次適應(yīng)算法的鏈情況畫出下次適應(yīng)算法的鏈表組織形式及分配一個(gè)表組織形式及分配一個(gè)10KB10KB的作業(yè)后的情況。假設(shè)上次的作業(yè)后的情況。假設(shè)上次找到的空閑分區(qū)是空閑區(qū)找到的空閑分區(qū)是空閑區(qū)1 1。操作系統(tǒng)操作系

30、統(tǒng)空閑區(qū)空閑區(qū)1(16kB)已使用已使用空閑區(qū)空閑區(qū)2(14KB)已使用已使用空閑區(qū)空閑區(qū)3(5KB)已使用已使用空閑區(qū)空閑區(qū)4(30KB)已使用已使用0k40k66k70k84k100k105k150k180k256k50k已使用已使用2 2解：解：（1 1）分配一個(gè)分配一個(gè)10KB10KB的作業(yè)前的鏈表組織形式。的作業(yè)前的鏈表組織形式。（2 2）分配一個(gè)）分配一個(gè)10KB10KB的作業(yè)后的的作業(yè)后的鏈表組織形式。鏈表組織形式。50k16kB70k14KB100k5KB150k30kB70k100k150k50k16KB80k4KB100k5KB150k30KB80k100k150k操作系統(tǒng)

31、操作系統(tǒng)空閑區(qū)空閑區(qū)1(16kB)已使用已使用空閑區(qū)空閑區(qū)2(14kB)已使用已使用空閑區(qū)空閑區(qū)3(5kB)已使用已使用空閑區(qū)空閑區(qū)4(30kB)已使用已使用0k40k66k70k84k100k105k150k180k256k50k已使用已使用表頭指針表頭指針表頭指針表頭指針三、可變分區(qū)分配算法三、可變分區(qū)分配算法 ( (三三) )最佳適應(yīng)最佳適應(yīng)(Best Fit)算法。算法。 最佳的含義是指每次為進(jìn)程分配內(nèi)存最佳的含義是指每次為進(jìn)程分配內(nèi)存時(shí)，總是把與進(jìn)程大小最匹配的空閑分區(qū)時(shí)，總是把與進(jìn)程大小最匹配的空閑分區(qū)分配出去。分配出去。 該算法若采用的數(shù)據(jù)結(jié)構(gòu)是空閑分區(qū)該算法若采用的數(shù)據(jù)結(jié)構(gòu)是空

32、閑分區(qū)鏈，首先要求將空閑分區(qū)，按分區(qū)大小遞鏈，首先要求將空閑分區(qū)，按分區(qū)大小遞增的順序形成一空閑分區(qū)鏈。當(dāng)進(jìn)程要求增的順序形成一空閑分區(qū)鏈。當(dāng)進(jìn)程要求分配內(nèi)存時(shí)，第一次找到的滿足要求的空分配內(nèi)存時(shí)，第一次找到的滿足要求的空閑區(qū)，必然是最優(yōu)的。閑區(qū)，必然是最優(yōu)的。例例3 3：根據(jù)右圖的內(nèi)存使用：根據(jù)右圖的內(nèi)存使用情況畫出最佳適應(yīng)算法的鏈情況畫出最佳適應(yīng)算法的鏈表組織形式及分配一個(gè)表組織形式及分配一個(gè)10KB10KB的作業(yè)后的情況。的作業(yè)后的情況。操作系統(tǒng)操作系統(tǒng)空閑區(qū)空閑區(qū)1(26KB)已使用已使用空閑區(qū)空閑區(qū)2(14KB)已使用已使用空閑區(qū)空閑區(qū)3(5KB)已使用已使用空閑區(qū)空閑區(qū)4(30KB

33、)已使用已使用0k40k66k70k84k100k105k150k180k256k3 3解：解：（1 1）分配一個(gè)分配一個(gè)10KB10KB的作業(yè)前的鏈表組織形式。的作業(yè)前的鏈表組織形式。100k5KB70k14KB40k26KB150k30KB70k40k150k（2 2）分配一個(gè)）分配一個(gè)10KB10KB的作業(yè)后的的作業(yè)后的鏈表組織形式。鏈表組織形式。80k4KB100k5KB40k26KB150k30KB100k40k150k操作系統(tǒng)操作系統(tǒng)空閑區(qū)空閑區(qū)1(26KB)已使用已使用空閑區(qū)空閑區(qū)2(14KB)已使用已使用空閑區(qū)空閑區(qū)3(5KB)已使用已使用空閑區(qū)空閑區(qū)4(30KB)已使用已使用

34、0k40k66k70k84k100k105k150k180k256k表頭指針表頭指針表頭指針表頭指針三、可變分區(qū)分配算法三、可變分區(qū)分配算法 ( (四四) )最壞適應(yīng)最壞適應(yīng)(Worst Fit)算法。算法。 該算法與最佳適應(yīng)算法相反，要求空該算法與最佳適應(yīng)算法相反，要求空閑分區(qū)按分區(qū)大小遞減的順序排序，每次閑分區(qū)按分區(qū)大小遞減的順序排序，每次分配時(shí)，從鏈?zhǔn)渍业阶畲蟮目臻e分區(qū)分配時(shí)，從鏈?zhǔn)渍业阶畲蟮目臻e分區(qū)“切切出出”一塊進(jìn)行分配。一塊進(jìn)行分配。 該算法的特點(diǎn)是基本上不會(huì)留下小空該算法的特點(diǎn)是基本上不會(huì)留下小空閑分區(qū)，不易形成碎片。缺點(diǎn)是大的空閑閑分區(qū)，不易形成碎片。缺點(diǎn)是大的空閑分區(qū)被切割，

35、當(dāng)有較大的進(jìn)程需要運(yùn)行時(shí)，分區(qū)被切割，當(dāng)有較大的進(jìn)程需要運(yùn)行時(shí)，系統(tǒng)往往不能滿足要求。系統(tǒng)往往不能滿足要求。例例4 4：根據(jù)右圖的內(nèi)存使用：根據(jù)右圖的內(nèi)存使用情況畫出最壞適應(yīng)算法的鏈情況畫出最壞適應(yīng)算法的鏈表組織形式及分配一個(gè)表組織形式及分配一個(gè)10KB10KB的作業(yè)后的情況。的作業(yè)后的情況。操作系統(tǒng)操作系統(tǒng)空閑區(qū)空閑區(qū)1(26KB)已使用已使用空閑區(qū)空閑區(qū)2(14KB)已使用已使用空閑區(qū)空閑區(qū)3(5KB)已使用已使用空閑區(qū)空閑區(qū)4(30KB)已使用已使用0k40k66k70k84k100k105k150k180k256k4 4解：解：（1 1）分配一個(gè)分配一個(gè)10KB10KB的作業(yè)前的鏈表組

36、織形式。的作業(yè)前的鏈表組織形式。150k30KB40k26KB70k14KB100k5KB40k70k100k（2 2）分配一個(gè)）分配一個(gè)10KB10KB的作業(yè)后的的作業(yè)后的鏈表組織形式。鏈表組織形式。40k26KB160k20KB70k14KB100k5KB160k70k100k操作系統(tǒng)操作系統(tǒng)空閑區(qū)空閑區(qū)1(26KB)已使用已使用空閑區(qū)空閑區(qū)2(14KB)已使用已使用空閑區(qū)空閑區(qū)3(5KB)已使用已使用空閑區(qū)空閑區(qū)4(30KB)已使用已使用0k40k66k70k84k100k105k150k180k256k表頭指針表頭指針表頭指針表頭指針?biāo)摹⒖勺兎謪^(qū)的作業(yè)分配過程四、可變分區(qū)的作業(yè)分配過程在找到合適的空閑塊后，從其中將在找到合適的空閑塊后，從其中將作業(yè)大小的空間分給作業(yè)，而剩余部分作業(yè)大小的空間分給作業(yè)，而剩余部分掛入空閑隊(duì)列。掛入空閑隊(duì)列。 下面下面F F 是空閑塊集合是空閑塊集合; size(; size(k k) )為塊為塊k k 的大小的大小; size(u); size(u)為用戶所需空間。分配為用