華東理工815操作系統(tǒng)第14講

1、最佳適應(yīng)算法最佳適應(yīng)算法(BF)(BF) v算法要求算法要求： 空閑分區(qū)表空閑分區(qū)表/ /鏈按容量大小遞增鏈按容量大小遞增的次序排列。的次序排列。 在進(jìn)行內(nèi)存分配時(shí)，在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表從空閑分區(qū)表/ /鏈?zhǔn)组_始順序鏈?zhǔn)组_始順序 查找查找，直到找到第一個(gè)滿足其大小要求的空閑分區(qū)，直到找到第一個(gè)滿足其大小要求的空閑分區(qū) 為止。為止。 按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作 業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。 如果該空閑分區(qū)大于作業(yè)的大小，則與首次適應(yīng)算如果該空閑分區(qū)大于作業(yè)的大小，則與首

2、次適應(yīng)算 法相同，將剩余空閑分區(qū)仍按容量大小遞增的次序法相同，將剩余空閑分區(qū)仍按容量大小遞增的次序 保留在空閑分區(qū)表保留在空閑分區(qū)表/ /鏈中。鏈中。 例例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)申系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)申 請(qǐng)分配內(nèi)存空間請(qǐng)分配內(nèi)存空間100KB100KB、30KB30KB及及7KB7KB。給出按最佳。給出按最佳 適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。 分配前的空閑分區(qū)表分配前的空閑分區(qū)表 0k 20k 52k 80k 651k 內(nèi)存空閑分區(qū)圖內(nèi)存空閑分區(qū)圖 72k 100k 220K 320K 2 1 3 4 解：解

3、：按最佳適應(yīng)算法，分配前的空閑分區(qū)表如上表。按最佳適應(yīng)算法，分配前的空閑分區(qū)表如上表。 申請(qǐng)作業(yè)申請(qǐng)作業(yè)100k100k，分配，分配3 3號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為20k,20k,起始地址起始地址200K200K； 申請(qǐng)作業(yè)申請(qǐng)作業(yè)30k30k， 分配分配2 2號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為2k2k，起始地址，起始地址50K 50K ； 申請(qǐng)作業(yè)申請(qǐng)作業(yè)7k7k， 分配分配1 1號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為1k1k，起始地址，起始地址79K 79K ； 其內(nèi)存分配圖及分配后空閑分區(qū)表如下其內(nèi)存分配圖及分配后空閑分區(qū)表如下 作業(yè)作業(yè)100K分配后的空閑分區(qū)表分配后的空閑分

4、區(qū)表作業(yè)作業(yè)30K分配后的空閑分區(qū)表分配后的空閑分區(qū)表 作業(yè)作業(yè)7K分配后的空閑分區(qū)表分配后的空閑分區(qū)表 (2)(2)該算法分配后的空閑分區(qū)表該算法分配后的空閑分區(qū)表 (1)(1)內(nèi)存分配示意圖內(nèi)存分配示意圖 0k 20k 52k 80k 651k 50k 72k 79k 100k 200k 220K 320K 4 1 3 2 v算法特點(diǎn)算法特點(diǎn) 若存在與作業(yè)大小一致的空閑分區(qū)，則它必若存在與作業(yè)大小一致的空閑分區(qū)，則它必 然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)，然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)， 則只劃分比作業(yè)稍大的空閑分區(qū)，從而保留了大則只劃分比作業(yè)稍大的空閑分區(qū)，從而保留了

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

6、找，找到的第一個(gè)能滿足作業(yè)要求的空閑分，找到的第一個(gè)能滿足作業(yè)要求的空閑分 區(qū)，一定是個(gè)最大的空閑區(qū)。這樣可保證每次分區(qū)，一定是個(gè)最大的空閑區(qū)。這樣可保證每次分 割后的剩下的空閑分區(qū)不至于太?。ㄟ€可被分配割后的剩下的空閑分區(qū)不至于太小（還可被分配 使用，以減少使用，以減少“外碎片外碎片”），仍把它按從大到?。?，仍把它按從大到小 的次序保留在空閑分區(qū)表的次序保留在空閑分區(qū)表/ /鏈中。鏈中。 空閑分區(qū)表空閑分區(qū)表 例例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作 業(yè)申請(qǐng)分配內(nèi)存空間業(yè)申請(qǐng)分配內(nèi)存空間100KB100KB、30KB30KB及及7KB7KB。給出。給出 按

7、最壞適應(yīng)算法的內(nèi)存分配情況及分配后空閑按最壞適應(yīng)算法的內(nèi)存分配情況及分配后空閑 分區(qū)表。分區(qū)表。 0k 20k 52k 80k 651k 內(nèi)存空閑分區(qū)圖內(nèi)存空閑分區(qū)圖 72k 100k 220K 320K 3 4 2 1 作業(yè)作業(yè)100K分配后的空閑分區(qū)表分配后的空閑分區(qū)表作業(yè)作業(yè)30K分配后的空閑分區(qū)表分配后的空閑分區(qū)表 作業(yè)作業(yè)7K分配后的空閑分區(qū)表分配后的空閑分區(qū)表 解：解：按最壞適應(yīng)算法，分配前的空閑分區(qū)表如上表。按最壞適應(yīng)算法，分配前的空閑分區(qū)表如上表。 申請(qǐng)作業(yè)申請(qǐng)作業(yè)100k100k，分配，分配1 1號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為231k,231k,起始地址起始地址420K

8、420K； 申請(qǐng)作業(yè)申請(qǐng)作業(yè)30k30k，分配，分配1 1號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為201k201k，起始地址，起始地址450K 450K ； 申請(qǐng)作業(yè)申請(qǐng)作業(yè)7k7k，分配，分配1 1號(hào)分區(qū)，剩下分區(qū)為號(hào)分區(qū)，剩下分區(qū)為194k194k，起始地址，起始地址457K 457K ； 其內(nèi)存分配圖及分配后空閑分區(qū)表如下其內(nèi)存分配圖及分配后空閑分區(qū)表如下 (2)(2)該算法分配后的空閑分區(qū)表該算法分配后的空閑分區(qū)表 (1)內(nèi)存分配圖內(nèi)存分配圖 0k 20k 52k 80k 457k 651k 72k 100k 220K 320K 420k 450k 3 4 2 1 v算法特點(diǎn)算法特點(diǎn) 總是

9、挑選滿足作業(yè)要求的最大的分區(qū)總是挑選滿足作業(yè)要求的最大的分區(qū) 分配給作業(yè)。這樣使分給作業(yè)后剩下的空分配給作業(yè)。這樣使分給作業(yè)后剩下的空 閑分區(qū)也較大，可裝下其它作業(yè)。閑分區(qū)也較大，可裝下其它作業(yè)。 但由于最大的空閑分區(qū)總是因首先分但由于最大的空閑分區(qū)總是因首先分 配而劃分，當(dāng)有大作業(yè)到來時(shí)，其存儲(chǔ)空配而劃分，當(dāng)有大作業(yè)到來時(shí)，其存儲(chǔ)空 間的申請(qǐng)往往會(huì)得不到滿足。間的申請(qǐng)往往會(huì)得不到滿足。 快速適應(yīng)算法快速適應(yīng)算法(QF)(QF) v算法要求算法要求 又叫分類搜索法，將空閑分區(qū)根據(jù)容量大小又叫分類搜索法，將空閑分區(qū)根據(jù)容量大小 進(jìn)行分類，對(duì)于每一類具有相同容量的所有空閑進(jìn)行分類，對(duì)于每一類具有相

10、同容量的所有空閑 分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)（鏈）表。系統(tǒng)中分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)（鏈）表。系統(tǒng)中 存在多個(gè)空閑分區(qū)（鏈）表，同時(shí)在內(nèi)存中設(shè)立存在多個(gè)空閑分區(qū)（鏈）表，同時(shí)在內(nèi)存中設(shè)立 一張管理索引表，每個(gè)表項(xiàng)對(duì)應(yīng)了一種空閑分區(qū)一張管理索引表，每個(gè)表項(xiàng)對(duì)應(yīng)了一種空閑分區(qū) 類型，并指向該類型的空閑分區(qū)表的表頭?？臻e類型，并指向該類型的空閑分區(qū)表的表頭?？臻e 分區(qū)的分類是根據(jù)進(jìn)程常用的空間大小進(jìn)行劃分分區(qū)的分類是根據(jù)進(jìn)程常用的空間大小進(jìn)行劃分 的。的。 快速適應(yīng)算法快速適應(yīng)算法(QF)(QF) 優(yōu)點(diǎn)：優(yōu)點(diǎn)：查找效率高，找到該類后，取下第查找效率高，找到該類后，取下第 一塊分配即可；不會(huì)產(chǎn)生碎片

11、；一塊分配即可；不會(huì)產(chǎn)生碎片； 缺點(diǎn)：缺點(diǎn)：分區(qū)歸還給系統(tǒng)時(shí)算法復(fù)雜，系統(tǒng)分區(qū)歸還給系統(tǒng)時(shí)算法復(fù)雜，系統(tǒng) 開銷大；內(nèi)存空間存在一定的浪費(fèi)。開銷大；內(nèi)存空間存在一定的浪費(fèi)。 3 3、分區(qū)分配操作、分區(qū)分配操作_ _分配內(nèi)存和回收內(nèi)存分配內(nèi)存和回收內(nèi)存 （1 1）分配內(nèi)存）分配內(nèi)存 系統(tǒng)利用某種分配算法，從空閑分區(qū)表系統(tǒng)利用某種分配算法，從空閑分區(qū)表/ /鏈中找到所需大鏈中找到所需大 小的分區(qū)。小的分區(qū)。 分區(qū)的切割：分區(qū)的切割： 設(shè)請(qǐng)求的分區(qū)大小為設(shè)請(qǐng)求的分區(qū)大小為u.sizeu.size，空閑分區(qū)的大小為，空閑分區(qū)的大小為m.size,m.size, 若若m.size-u.sizem.size

12、-u.size sizesize（sizesize是事先規(guī)定的不再切割的剩余分是事先規(guī)定的不再切割的剩余分 區(qū)的大?。?，說明多余部分大小，可不再切割，將整個(gè)分區(qū)分區(qū)的大?。f明多余部分大小，可不再切割，將整個(gè)分區(qū)分 配給請(qǐng)求者；否則，從該分區(qū)中按請(qǐng)求的大小劃分出一塊內(nèi)存配給請(qǐng)求者；否則，從該分區(qū)中按請(qǐng)求的大小劃分出一塊內(nèi)存 空間分配出去，余下的部分仍留在空閑分區(qū)表空間分配出去，余下的部分仍留在空閑分區(qū)表/ /鏈中，然后，鏈中，然后， 將分配區(qū)的首址返回給調(diào)用者。將分配區(qū)的首址返回給調(diào)用者。 分配流程圖如下分配流程圖如下 從頭開始查表從頭開始查表 從該分區(qū)中劃出從該分區(qū)中劃出u.sizeu.s

13、ize大小的分區(qū)大小的分區(qū) 檢索完否？檢索完否？ 返回返回 m.sizeu.sizem.sizeu.size m.size-u.sizem.size-u.size sizesize 將該分區(qū)分配給請(qǐng)求者，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)將該分區(qū)分配給請(qǐng)求者，修改有關(guān)數(shù)據(jù)結(jié)構(gòu) 返回返回 將該分區(qū)從分區(qū)表將該分區(qū)從分區(qū)表/ /鏈中移出鏈中移出 繼續(xù)檢索下一個(gè)表項(xiàng)繼續(xù)檢索下一個(gè)表項(xiàng) Y Y Y Y Y Y N N N N N N 內(nèi)存分配流程圖內(nèi)存分配流程圖 （2 2）回收內(nèi)存）回收內(nèi)存 當(dāng)作業(yè)執(zhí)行結(jié)束時(shí)，釋放所占有的內(nèi)存當(dāng)作業(yè)執(zhí)行結(jié)束時(shí)，釋放所占有的內(nèi)存 空間，空間，OSOS應(yīng)回收已使用完畢的內(nèi)存分區(qū)。應(yīng)回收已使

14、用完畢的內(nèi)存分區(qū)。 系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在 空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)，空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)， 如有，則合成為一個(gè)大的空閑分區(qū)，然后修如有，則合成為一個(gè)大的空閑分區(qū)，然后修 改有關(guān)的分區(qū)狀態(tài)信息。改有關(guān)的分區(qū)狀態(tài)信息。 回收分區(qū)與已有空閑分區(qū)的相鄰情況有回收分區(qū)與已有空閑分區(qū)的相鄰情況有 以下四種以下四種： （2 2）回收內(nèi)存）回收內(nèi)存 回收分區(qū)回收分區(qū)R 空閑分區(qū)空閑分區(qū)F1 (a) 內(nèi)存回收情況內(nèi)存回收情況 1)1)回收分區(qū)回收分區(qū)R R上面鄰接一個(gè)上面鄰接一個(gè) 空閑分區(qū)空閑分區(qū)F1F1，合并后首，合并后首 地址為空閑

15、分區(qū)地址為空閑分區(qū)F1F1的首的首 地址，大小為地址，大小為F1F1和和R R二者二者 大小之和。大小之和。 這種情況下，回收后空這種情況下，回收后空 閑分區(qū)表中表項(xiàng)數(shù)不變。閑分區(qū)表中表項(xiàng)數(shù)不變。 （2 2）回收內(nèi)存）回收內(nèi)存 空閑分區(qū)空閑分區(qū)F2 回收分區(qū)回收分區(qū)R (b) 內(nèi)存回收情況內(nèi)存回收情況 2) 2)回收分區(qū)回收分區(qū)R R下面鄰接一下面鄰接一 個(gè)空閑分區(qū)個(gè)空閑分區(qū)F2F2，合并后，合并后 首地址為回收分區(qū)首地址為回收分區(qū)R R的首的首 地址，大小為地址，大小為R R和和F2F2二者二者 大小之和。大小之和。 這種情況下，回收后空這種情況下，回收后空 閑分區(qū)表中表項(xiàng)數(shù)不變。閑分區(qū)表中

16、表項(xiàng)數(shù)不變。 （2 2）回收內(nèi)存）回收內(nèi)存 空閑分區(qū)空閑分區(qū)F2 回收分區(qū)回收分區(qū)R 空閑分區(qū)空閑分區(qū)F1 (c) 內(nèi)存回收情況內(nèi)存回收情況 3)3)回收分區(qū)回收分區(qū)R R上下鄰接空閑上下鄰接空閑 分區(qū)分區(qū)F1F1和和F2F2，合并后首，合并后首 地址為上空閑分區(qū)地址為上空閑分區(qū)F1F1的的 首地址，大小為首地址，大小為F1F1、R R和和 F2F2三者大小之和。三者大小之和。 這種情況下，回收后空這種情況下，回收后空 閑分區(qū)表中表項(xiàng)數(shù)不但閑分區(qū)表中表項(xiàng)數(shù)不但 沒有增加，反而減少一沒有增加，反而減少一 項(xiàng)。項(xiàng)。 （2 2）回收內(nèi)存）回收內(nèi)存 內(nèi)存回收情況內(nèi)存回收情況 回收分區(qū)回收分區(qū)R (d)

17、 4)4)回收分區(qū)回收分區(qū)R R不鄰接空閑分不鄰接空閑分 區(qū)，這時(shí)在空閑分區(qū)表區(qū)，這時(shí)在空閑分區(qū)表 中新建一表項(xiàng)，并填寫中新建一表項(xiàng)，并填寫 分區(qū)首地址、大小等信分區(qū)首地址、大小等信 息。息。 這種情況下，回收后空這種情況下，回收后空 閑分區(qū)表中表項(xiàng)數(shù)增加閑分區(qū)表中表項(xiàng)數(shù)增加 一項(xiàng)。一項(xiàng)。 四、伙伴系統(tǒng)四、伙伴系統(tǒng) 1 1、固定分區(qū)：限制了活動(dòng)進(jìn)程的數(shù)目，內(nèi)存利用率低、固定分區(qū)：限制了活動(dòng)進(jìn)程的數(shù)目，內(nèi)存利用率低 動(dòng)態(tài)分區(qū)：算法復(fù)雜，系統(tǒng)開銷大動(dòng)態(tài)分區(qū)：算法復(fù)雜，系統(tǒng)開銷大 折中方案：伙伴系統(tǒng)折中方案：伙伴系統(tǒng) 2 2、伙伴系統(tǒng)規(guī)定：已分配、伙伴系統(tǒng)規(guī)定：已分配/ /空閑分區(qū)的大小都是空閑分區(qū)

18、的大小都是2 2的的k k 次冪（次冪（lkmlkm） 3 3、分配和回收方法：、分配和回收方法：P126P126 4 4、分配和回收的時(shí)間性能取決于查找空閑分區(qū)的位置、分配和回收的時(shí)間性能取決于查找空閑分區(qū)的位置 和分割、合并空閑分區(qū)所花費(fèi)的時(shí)間和分割、合并空閑分區(qū)所花費(fèi)的時(shí)間 5 5、在當(dāng)前、在當(dāng)前OSOS中，普遍采用虛擬內(nèi)存機(jī)制中，普遍采用虛擬內(nèi)存機(jī)制 在多處理機(jī)系統(tǒng)中，伙伴系統(tǒng)得到大量的應(yīng)用在多處理機(jī)系統(tǒng)中，伙伴系統(tǒng)得到大量的應(yīng)用 五、哈希算法（五、哈希算法（1 1） 1 1、分類搜索算法（快速適應(yīng)算法）和伙伴系統(tǒng)的共、分類搜索算法（快速適應(yīng)算法）和伙伴系統(tǒng)的共 同特點(diǎn)：將空閑分區(qū)根據(jù)

19、分區(qū)大小進(jìn)行分類，對(duì)同特點(diǎn)：將空閑分區(qū)根據(jù)分區(qū)大小進(jìn)行分類，對(duì) 于每一類具有相同大小的空閑分區(qū)，單獨(dú)設(shè)立一于每一類具有相同大小的空閑分區(qū)，單獨(dú)設(shè)立一 個(gè)空閑分區(qū)鏈表。為進(jìn)程分配內(nèi)存空間時(shí)，需在個(gè)空閑分區(qū)鏈表。為進(jìn)程分配內(nèi)存空間時(shí)，需在 一張管理索引表中查找所需空間大小所對(duì)應(yīng)的表一張管理索引表中查找所需空間大小所對(duì)應(yīng)的表 項(xiàng)，通過指針找到一個(gè)空閑分區(qū)。項(xiàng)，通過指針找到一個(gè)空閑分區(qū)。 五、哈希算法（五、哈希算法（2 2） 2 2、哈希算法利用哈希快速查找的優(yōu)點(diǎn)，以及空閑分區(qū)、哈希算法利用哈?？焖俨檎业膬?yōu)點(diǎn)，以及空閑分區(qū) 在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)在可利用空間表中的分布規(guī)律，建立哈

20、希函數(shù)，構(gòu) 造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，每一個(gè)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，每一個(gè) 表項(xiàng)記錄了一個(gè)對(duì)應(yīng)的空閑分區(qū)鏈鏈表表頭指針。表項(xiàng)記錄了一個(gè)對(duì)應(yīng)的空閑分區(qū)鏈鏈表表頭指針。 3 3、進(jìn)行分配時(shí)，根據(jù)所需空閑分區(qū)大小，通過哈希函、進(jìn)行分配時(shí)，根據(jù)所需空閑分區(qū)大小，通過哈希函 數(shù)計(jì)算，得到在哈希表中的位置，找到相應(yīng)的空閑數(shù)計(jì)算，得到在哈希表中的位置，找到相應(yīng)的空閑 分區(qū)鏈表，實(shí)現(xiàn)最佳分配策略。分區(qū)鏈表，實(shí)現(xiàn)最佳分配策略。 六、可重定位分區(qū)分配方式六、可重定位分區(qū)分配方式 1 1、碎片問題、碎片問題 在分區(qū)存儲(chǔ)管理方式中，必須把作業(yè)裝入在分區(qū)存儲(chǔ)管理方式中，必須把作業(yè)裝入 到一片連

21、續(xù)的內(nèi)存空間。如果系統(tǒng)中有若干個(gè)到一片連續(xù)的內(nèi)存空間。如果系統(tǒng)中有若干個(gè) 小的分區(qū)，其總?cè)萘看笥谝b入的作業(yè)，但由小的分區(qū)，其總?cè)萘看笥谝b入的作業(yè)，但由 于它們不相鄰接，也將導(dǎo)致作業(yè)不能裝入內(nèi)存。于它們不相鄰接，也將導(dǎo)致作業(yè)不能裝入內(nèi)存。 例：例：如圖所示系統(tǒng)中有四個(gè)小空閑分區(qū)，不相鄰，如圖所示系統(tǒng)中有四個(gè)小空閑分區(qū)，不相鄰， 但總?cè)萘繛榈側(cè)萘繛?0KB90KB，如果現(xiàn)有一作業(yè)要求分配，如果現(xiàn)有一作業(yè)要求分配 40KB40KB的內(nèi)存空間，由于系統(tǒng)中所有空閑分區(qū)的的內(nèi)存空間，由于系統(tǒng)中所有空閑分區(qū)的 容量均小于容量均小于40KB40KB，故此作業(yè)無法裝入內(nèi)存。，故此作業(yè)無法裝入內(nèi)存。 系統(tǒng)中

22、的碎片（系統(tǒng)中的碎片（1 1） os 用用 戶戶 程程 序序 p4 p1 p2 0k 20k 56k 65k 125k 135k 內(nèi)部碎片內(nèi)部碎片 內(nèi)部碎片內(nèi)部碎片 內(nèi)部碎片內(nèi)部碎片 內(nèi)部碎片內(nèi)部碎片 n內(nèi)部碎片內(nèi)部碎片：指分配給：指分配給 作業(yè)的存儲(chǔ)空間中未被作業(yè)的存儲(chǔ)空間中未被 利用的部分。如固定分利用的部分。如固定分 區(qū)中存在的碎片。區(qū)中存在的碎片。 v這種內(nèi)存中無法被利用的存儲(chǔ)空間稱為這種內(nèi)存中無法被利用的存儲(chǔ)空間稱為“零頭零頭”或或 “碎片碎片”。根據(jù)碎片出現(xiàn)的情況分為以下兩種：。根據(jù)碎片出現(xiàn)的情況分為以下兩種： 系統(tǒng)中的碎片（系統(tǒng)中的碎片（2 2） 25KB25KB 作業(yè)作業(yè)D 1

23、5KB15KB 作業(yè)作業(yè)C 30KB30KB 作業(yè)作業(yè)B 20KB20KB 作業(yè)作業(yè)A 操作系統(tǒng)操作系統(tǒng) 外部碎片外部碎片 外部碎片外部碎片 外部碎片外部碎片 外部碎片外部碎片 外部碎片外部碎片 n外部碎片外部碎片：指系統(tǒng)中無法利用的小的空閑分區(qū)。如：指系統(tǒng)中無法利用的小的空閑分區(qū)。如 動(dòng)態(tài)分區(qū)中存在的碎片。動(dòng)態(tài)分區(qū)中存在的碎片。 2 2、碎片問題的解決方法、碎片問題的解決方法 對(duì)系統(tǒng)中存在碎片，目前主要有兩種技術(shù)對(duì)系統(tǒng)中存在碎片，目前主要有兩種技術(shù)( (之一之一) )： v 拼接或緊湊或緊縮技術(shù)拼接或緊湊或緊縮技術(shù) 將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在內(nèi)將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在內(nèi)

24、 存中的位置發(fā)生了變化，這就必須對(duì)其地址加以存中的位置發(fā)生了變化，這就必須對(duì)其地址加以 修改或變換即稱為重定位），使本來分散的多個(gè)修改或變換即稱為重定位），使本來分散的多個(gè) 小空閑分區(qū)連成一個(gè)大的空閑區(qū)。如圖所示。小空閑分區(qū)連成一個(gè)大的空閑區(qū)。如圖所示。 這種通過移動(dòng)作業(yè)從把多個(gè)分散的小分區(qū)拼這種通過移動(dòng)作業(yè)從把多個(gè)分散的小分區(qū)拼 接成一個(gè)大分區(qū)的方法稱為拼接或緊湊或緊縮接成一個(gè)大分區(qū)的方法稱為拼接或緊湊或緊縮。 拼接時(shí)機(jī)：分區(qū)回收時(shí)；當(dāng)找不到足夠大的空拼接時(shí)機(jī)：分區(qū)回收時(shí)；當(dāng)找不到足夠大的空 閑分區(qū)且總空閑分區(qū)容量可以滿足作業(yè)要求時(shí)。閑分區(qū)且總空閑分區(qū)容量可以滿足作業(yè)要求時(shí)。 作業(yè)作業(yè)D 作

25、業(yè)作業(yè)C 作業(yè)作業(yè)B 20KB20KB 30KB 90KB30KB 90KB 15KB15KB 25KB25KB 作業(yè)作業(yè)A 操作系統(tǒng)操作系統(tǒng) 動(dòng)態(tài)重定位分區(qū)分配算法流程圖動(dòng)態(tài)重定位分區(qū)分配算法流程圖 有大于有大于x的的 空閑分區(qū)嗎？空閑分區(qū)嗎？ 返回分區(qū)號(hào)返回分區(qū)號(hào) 空閑分區(qū)空閑分區(qū) 總和大于總和大于x嗎？嗎？ 拼接并修改拼接并修改 相應(yīng)數(shù)據(jù)結(jié)構(gòu)相應(yīng)數(shù)據(jù)結(jié)構(gòu) 返回返回 修改有關(guān)修改有關(guān) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 按動(dòng)態(tài)分區(qū)按動(dòng)態(tài)分區(qū) 分配方式進(jìn)行分配分配方式進(jìn)行分配 Y Y N N 無法分配，返回?zé)o法分配，返回 請(qǐng)求分配一個(gè)請(qǐng)求分配一個(gè) 大小為大小為x的分區(qū)的分區(qū) v動(dòng)態(tài)重定位分區(qū)分配技術(shù)動(dòng)態(tài)重定位

26、分區(qū)分配技術(shù) 在動(dòng)態(tài)分區(qū)分配算法中增加拼接功能，在找不到足夠大的在動(dòng)態(tài)分區(qū)分配算法中增加拼接功能，在找不到足夠大的 空閑分區(qū)來滿足作業(yè)要求，而系統(tǒng)中總空閑分區(qū)容量可以滿足空閑分區(qū)來滿足作業(yè)要求，而系統(tǒng)中總空閑分區(qū)容量可以滿足 作業(yè)要求時(shí)，進(jìn)行拼接。作業(yè)要求時(shí)，進(jìn)行拼接。 可重定位分區(qū)分配方式主要特點(diǎn)可重定位分區(qū)分配方式主要特點(diǎn) 可以充分利用存儲(chǔ)區(qū)中的可以充分利用存儲(chǔ)區(qū)中的“零頭零頭/ /碎碎 片片”，提高主存的利用率。，提高主存的利用率。 但若但若 “ “零頭零頭 / /碎片碎片”太多，則拼接頻率過高會(huì)使系統(tǒng)太多，則拼接頻率過高會(huì)使系統(tǒng) 開銷加大。開銷加大。 七、分區(qū)的存儲(chǔ)保護(hù)（七、分區(qū)的存儲(chǔ)

27、保護(hù)（1） 存儲(chǔ)保護(hù)是為了防止一個(gè)作業(yè)有意或無意存儲(chǔ)保護(hù)是為了防止一個(gè)作業(yè)有意或無意 地破壞操作系統(tǒng)或其它作業(yè)，常用的存儲(chǔ)保護(hù)地破壞操作系統(tǒng)或其它作業(yè)，常用的存儲(chǔ)保護(hù) 方法有：方法有： 1 1、界限寄存器方法、界限寄存器方法 n 上下界寄存器方法上下界寄存器方法：用這兩個(gè)寄存器分別存：用這兩個(gè)寄存器分別存 放作業(yè)的起始地址和結(jié)束地址。在作業(yè)運(yùn)行放作業(yè)的起始地址和結(jié)束地址。在作業(yè)運(yùn)行 過程中，將每一個(gè)訪問內(nèi)存的地址都同這兩過程中，將每一個(gè)訪問內(nèi)存的地址都同這兩 個(gè)寄存器的內(nèi)容比較，如超出這個(gè)范圍便產(chǎn)個(gè)寄存器的內(nèi)容比較，如超出這個(gè)范圍便產(chǎn) 生保護(hù)性中斷。生保護(hù)性中斷。 七、分區(qū)的存儲(chǔ)保護(hù)（七、分區(qū)的存儲(chǔ)保護(hù)（2） 存儲(chǔ)保護(hù)是為了防止一個(gè)作業(yè)有意或無意存儲(chǔ)保護(hù)是為了防止一個(gè)作業(yè)有意或無意 地破壞操作系統(tǒng)或其它作業(yè)，常用的存儲(chǔ)保護(hù)地破壞操作系統(tǒng)或其它作業(yè)，常用的存儲(chǔ)保護(hù) 方法有：方法有： 1 1、界限寄存器方法、界限寄存器方法 n基址、限長(zhǎng)寄存器方法基址、限長(zhǎng)寄存器方法：用這兩個(gè)寄存器分：用這兩