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

1、最佳適應(yīng)算法最佳適應(yīng)算法(BF)(BF) v算法要求算法要求： 空閑分區(qū)表空閑分區(qū)表/ /鏈按容量大小遞增鏈按容量大小遞增的次序排列。的次序排列。 在進(jìn)行內(nèi)存分配時，在進(jìn)行內(nèi)存分配時，從空閑分區(qū)表從空閑分區(qū)表/ /鏈?zhǔn)组_始順序鏈?zhǔn)组_始順序 查找查找，直到找到第一個滿足其大小要求的空閑分區(qū)，直到找到第一個滿足其大小要求的空閑分區(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)有三個作業(yè)申系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(yè)申 請分配內(nèi)存空間請分配內(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ū)表如上表。 申請作業(yè)申請作業(yè)100k100k，分配，分配3 3號分區(qū)，剩下分區(qū)為號分區(qū)，剩下分區(qū)為20k,20k,起始地址起始地址200K200K； 申請作業(yè)申請作業(yè)30k30k， 分配分配2 2號分區(qū)，剩下分區(qū)為號分區(qū)，剩下分區(qū)為2k2k，起始地址，起始地址50K 50K ； 申請作業(yè)申請作業(yè)7k7k， 分配分配1 1號分區(qū)，剩下分區(qū)為號分區(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算法特點算法特點 若存在與作業(yè)大小一致的空閑分區(qū)，則它必若存在與作業(yè)大小一致的空閑分區(qū)，則它必 然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)，然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)， 則只劃分比作業(yè)稍大的空閑分區(qū)，從而保留了大則只劃分比作業(yè)稍大的空閑分區(qū)，從而保留了

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

6、找，找到的第一個能滿足作業(yè)要求的空閑分，找到的第一個能滿足作業(yè)要求的空閑分 區(qū)，一定是個最大的空閑區(qū)。這樣可保證每次分區(qū)，一定是個最大的空閑區(qū)。這樣可保證每次分 割后的剩下的空閑分區(qū)不至于太?。ㄟ€可被分配割后的剩下的空閑分區(qū)不至于太?。ㄟ€可被分配 使用，以減少使用，以減少“外碎片外碎片”），仍把它按從大到?。园阉磸拇蟮叫?的次序保留在空閑分區(qū)表的次序保留在空閑分區(qū)表/ /鏈中。鏈中。 空閑分區(qū)表空閑分區(qū)表 例例 ：系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作 業(yè)申請分配內(nèi)存空間業(yè)申請分配內(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ū)表如上表。 申請作業(yè)申請作業(yè)100k100k，分配，分配1 1號分區(qū)，剩下分區(qū)為號分區(qū)，剩下分區(qū)為231k,231k,起始地址起始地址420K

8、420K； 申請作業(yè)申請作業(yè)30k30k，分配，分配1 1號分區(qū)，剩下分區(qū)為號分區(qū)，剩下分區(qū)為201k201k，起始地址，起始地址450K 450K ； 申請作業(yè)申請作業(yè)7k7k，分配，分配1 1號分區(qū)，剩下分區(qū)為號分區(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算法特點算法特點 總是

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

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

11、；一塊分配即可；不會產(chǎn)生碎片； 缺點：缺點：分區(qū)歸還給系統(tǒng)時算法復(fù)雜，系統(tǒng)分區(qū)歸還給系統(tǒng)時算法復(fù)雜，系統(tǒng) 開銷大；內(nèi)存空間存在一定的浪費。開銷大；內(nè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ū)大小為設(shè)請求的分區(qū)大小為u.sizeu.size，空閑分區(qū)的大小為，空閑分區(qū)的大小為m.size,m.size, 若若m.size-u.sizem.size

12、-u.size sizesize（sizesize是事先規(guī)定的不再切割的剩余分是事先規(guī)定的不再切割的剩余分 區(qū)的大?。?，說明多余部分大小，可不再切割，將整個分區(qū)分區(qū)的大?。?，說明多余部分大小，可不再切割，將整個分區(qū)分 配給請求者；否則，從該分區(qū)中按請求的大小劃分出一塊內(nèi)存配給請求者；否則，從該分區(qū)中按請求的大小劃分出一塊內(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ū)分配給請求者，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)將該分區(qū)分配給請求者，修改有關(guān)數(shù)據(jù)結(jié)構(gòu) 返回返回 將該分區(qū)從分區(qū)表將該分區(qū)從分區(qū)表/ /鏈中移出鏈中移出 繼續(xù)檢索下一個表項繼續(xù)檢索下一個表項 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é)束時，釋放所占有的內(nèi)存當(dāng)作業(yè)執(zhí)行結(jié)束時，釋放所占有的內(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ū)， 如有，則合成為一個大的空閑分區(qū)，然后修如有，則合成為一個大的空閑分區(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上面鄰接一個上面鄰接一個 空閑分區(qū)空閑分區(qū)F1F1，合并后首，合并后首 地址為空閑

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

16、表項數(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ū)表中表項數(shù)不但閑分區(qū)表中表項數(shù)不但 沒有增加，反而減少一沒有增加，反而減少一 項。項。 （2 2）回收內(nèi)存）回收內(nèi)存 內(nèi)存回收情況內(nèi)存回收情況 回收分區(qū)回收分區(qū)R (d)

17、 4)4)回收分區(qū)回收分區(qū)R R不鄰接空閑分不鄰接空閑分 區(qū)，這時在空閑分區(qū)表區(qū)，這時在空閑分區(qū)表 中新建一表項，并填寫中新建一表項，并填寫 分區(qū)首地址、大小等信分區(qū)首地址、大小等信 息。息。 這種情況下，回收后空這種情況下，回收后空 閑分區(qū)表中表項數(shù)增加閑分區(qū)表中表項數(shù)增加 一項。一項。 四、伙伴系統(tǒng)四、伙伴系統(tǒng) 1 1、固定分區(qū)：限制了活動進(jìn)程的數(shù)目，內(nèi)存利用率低、固定分區(qū)：限制了活動進(jìn)程的數(shù)目，內(nèi)存利用率低 動態(tài)分區(qū)：算法復(fù)雜，系統(tǒ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、分配和回收的時間性能取決于查找空閑分區(qū)的位置、分配和回收的時間性能取決于查找空閑分區(qū)的位置 和分割、合并空閑分區(qū)所花費的時間和分割、合并空閑分區(qū)所花費的時間 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)的共 同特點：將空閑分區(qū)根據(jù)

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

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

21、續(xù)的內(nèi)存空間。如果系統(tǒng)中有若干個到一片連續(xù)的內(nèi)存空間。如果系統(tǒng)中有若干個 小的分區(qū)，其總?cè)萘看笥谝b入的作業(yè)，但由小的分區(qū)，其總?cè)萘看笥谝b入的作業(yè)，但由 于它們不相鄰接，也將導(dǎo)致作業(yè)不能裝入內(nèi)存。于它們不相鄰接，也將導(dǎo)致作業(yè)不能裝入內(nèi)存。 例：例：如圖所示系統(tǒng)中有四個小空閑分區(qū)，不相鄰，如圖所示系統(tǒng)中有四個小空閑分區(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è)的存儲空間中未被作業(yè)的存儲空間中未被 利用的部分。如固定分利用的部分。如固定分 區(qū)中存在的碎片。區(qū)中存在的碎片。 v這種內(nèi)存中無法被利用的存儲空間稱為這種內(nèi)存中無法被利用的存儲空間稱為“零頭零頭”或或 “碎片碎片”。根據(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ū)。如 動態(tài)分區(qū)中存在的碎片。動態(tài)分區(qū)中存在的碎片。 2 2、碎片問題的解決方法、碎片問題的解決方法 對系統(tǒng)中存在碎片，目前主要有兩種技術(shù)對系統(tǒng)中存在碎片，目前主要有兩種技術(shù)( (之一之一) )： v 拼接或緊湊或緊縮技術(shù)拼接或緊湊或緊縮技術(shù) 將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在內(nèi)將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在內(nèi)

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

25、業(yè)作業(yè)C 作業(yè)作業(yè)B 20KB20KB 30KB 90KB30KB 90KB 15KB15KB 25KB25KB 作業(yè)作業(yè)A 操作系統(tǒng)操作系統(tǒng) 動態(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)修改有關(guān) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 按動態(tài)分區(qū)按動態(tài)分區(qū) 分配方式進(jìn)行分配分配方式進(jìn)行分配 Y Y N N 無法分配，返回?zé)o法分配，返回 請求分配一個請求分配一個 大小為大小為x的分區(qū)的分區(qū) v動態(tài)重定位分區(qū)分配技術(shù)動態(tài)重定位

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

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