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

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

2、同，將剩余空閑分區(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 80k651k內(nèi)存空閑分區(qū)圖內(nèi)存空閑分區(qū)圖72k100k220K320K2134解：解：按最佳適應(yīng)算法，分配前的空閑分區(qū)表如上表。按

3、最佳適應(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ū)表分配后的空閑分區(qū)表作業(yè)作業(yè)30K分配后的空閑分區(qū)表分配后的空閑分

4、區(qū)表作業(yè)作業(yè)7K分配后的空閑分區(qū)表分配后的空閑分區(qū)表(2)(2)該算法分配后的空閑分區(qū)表該算法分配后的空閑分區(qū)表(1)(1)內(nèi)存分配示意圖內(nèi)存分配示意圖 0k 20k 52k 80k651k50k72k79k100k200k220K320K4132v算法特點算法特點 若存在與作業(yè)大小一致的空閑分區(qū)，則它必若存在與作業(yè)大小一致的空閑分區(qū)，則它必然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)，然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的空閑分區(qū)，從而保留了大則只劃分比作業(yè)稍大的空閑分區(qū)，從而保留了大的空閑分區(qū)，但空閑區(qū)一般不可能正好和它申請的空閑分區(qū)，但空閑區(qū)一般不可能正好和它申請

5、的內(nèi)存空間大小一樣，因而將其分割成兩部分時，的內(nèi)存空間大小一樣，因而將其分割成兩部分時，往往使剩下的空閑區(qū)非常小，從而在存儲器中留往往使剩下的空閑區(qū)非常小，從而在存儲器中留下許多難以利用的小空閑區(qū)（外碎片或外零頭）。下許多難以利用的小空閑區(qū)（外碎片或外零頭）。最壞適應(yīng)算法最壞適應(yīng)算法(WF)(WF)v算法要求算法要求 空閑分區(qū)表空閑分區(qū)表/ /鏈鏈按容量大小遞減按容量大小遞減的次序排列。的次序排列。在進行內(nèi)存分配時，在進行內(nèi)存分配時，從空閑分區(qū)表從空閑分區(qū)表/ /鏈首開始順鏈首開始順序查找序查找，找到的第一個能滿足作業(yè)要求的空閑分，找到的第一個能滿足作業(yè)要求的空閑分區(qū)，一定是個最大的空閑區(qū)。這

6、樣可保證每次分區(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。給出。給出按最壞適應(yīng)算法的內(nèi)存分配情況及分配后空閑按最壞適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。分區(qū)表。 0k 20k 52k

7、80k651k內(nèi)存空閑分區(qū)圖內(nèi)存空閑分區(qū)圖72k100k220K320K3421作業(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,起始地址起始地址420K420K； 申請作業(yè)申請作業(yè)30k30k，分配，分配1 1號分區(qū)，剩下分區(qū)為號分區(qū)，剩下分區(qū)為201k201k，起始地址，起始地址450K 450

8、K ； 申請作業(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 80k457k651k72k100k220K320K420k450k3421v算法特點算法特點 總是挑選滿足作業(yè)要求的最大的分區(qū)總是挑選滿足作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使分給作業(yè)后剩下的空分配給作業(yè)。這樣使分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。閑分區(qū)也較大，可

9、裝下其它作業(yè)。 但由于最大的空閑分區(qū)總是因首先分但由于最大的空閑分區(qū)總是因首先分配而劃分，當有大作業(yè)到來時，其存儲空配而劃分，當有大作業(yè)到來時，其存儲空間的申請往往會得不到滿足。間的申請往往會得不到滿足?？焖龠m應(yīng)算法快速適應(yīng)算法(QF)(QF)v算法要求算法要求 又叫分類搜索法，將空閑分區(qū)根據(jù)容量大小又叫分類搜索法，將空閑分區(qū)根據(jù)容量大小進行分類，對于每一類具有相同容量的所有空閑進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)（鏈）表。系統(tǒng)中分區(qū)，單獨設(shè)立一個空閑分區(qū)（鏈）表。系統(tǒng)中存在多個空閑分區(qū)（鏈）表，同時在內(nèi)存中設(shè)立存在多個空閑分區(qū)（鏈）表，同時在內(nèi)存中設(shè)立一張管理

10、索引表，每個表項對應(yīng)了一種空閑分區(qū)一張管理索引表，每個表項對應(yīng)了一種空閑分區(qū)類型，并指向該類型的空閑分區(qū)表的表頭?？臻e類型，并指向該類型的空閑分區(qū)表的表頭?？臻e分區(qū)的分類是根據(jù)進程常用的空間大小進行劃分分區(qū)的分類是根據(jù)進程常用的空間大小進行劃分的。的?？焖龠m應(yīng)算法快速適應(yīng)算法(QF)(QF) 優(yōu)點：優(yōu)點：查找效率高，找到該類后，取下第查找效率高，找到該類后，取下第一塊分配即可；不會產(chǎn)生碎片；一塊分配即可；不會產(chǎn)生碎片； 缺點：缺點：分區(qū)歸還給系統(tǒng)時算法復(fù)雜，系統(tǒng)分區(qū)歸還給系統(tǒng)時算法復(fù)雜，系統(tǒng)開銷大；內(nèi)存空間存在一定的浪費。開銷大；內(nèi)存空間存在一定的浪費。3 3、分區(qū)分配操作、分區(qū)分配操作_ _

11、分配內(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-u.size sizesize（sizesize是事先規(guī)定的不再切割的剩余分是事先規(guī)定的不再切割的剩余分區(qū)的大小），說明多余部分大小，可不再切割，將整個分區(qū)分區(qū)的大?。f明多余部分大小，可不再切割，將整個分區(qū)分配給請

12、求者；否則，從該分區(qū)中按請求的大小劃分出一塊內(nèi)存配給請求者；否則，從該分區(qū)中按請求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)表空間分配出去，余下的部分仍留在空閑分區(qū)表/ /鏈中，然后，鏈中，然后，將分配區(qū)的首址返回給調(diào)用者。將分配區(qū)的首址返回給調(diào)用者。 分配流程圖如下分配流程圖如下 從頭開始查表從頭開始查表從該分區(qū)中劃出從該分區(qū)中劃出u.sizeu.size大小的分區(qū)大小的分區(qū)檢索完否？檢索完否？返回返回m.sizeu.sizem.sizeu.sizem.size-u.sizem.size-u.size sizesize將該分區(qū)分配給請求者，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)將該分區(qū)分配給請求者

13、，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回將該分區(qū)從分區(qū)表將該分區(qū)從分區(qū)表/ /鏈中移出鏈中移出繼續(xù)檢索下一個表項繼續(xù)檢索下一個表項Y YY YY YN NN NN N內(nèi)存分配流程圖內(nèi)存分配流程圖（2 2）回收內(nèi)存）回收內(nèi)存 當作業(yè)執(zhí)行結(jié)束時，釋放所占有的內(nèi)存當作業(yè)執(zhí)行結(jié)束時，釋放所占有的內(nèi)存空間，空間，OSOS應(yīng)回收已使用完畢的內(nèi)存分區(qū)。應(yīng)回收已使用完畢的內(nèi)存分區(qū)。 系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)，空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)，如有，則合成為一個大的空閑分區(qū)，然后修如有，則合成為一個大的空閑分區(qū)，然后修改有關(guān)的分區(qū)狀態(tài)信息。改

14、有關(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，合并后首，合并后首地址為空閑分區(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)存回收情況

15、2) 2)回收分區(qū)回收分區(qū)R R下面鄰接一下面鄰接一個空閑分區(qū)個空閑分區(qū)F2F2，合并后，合并后首地址為回收分區(qū)首地址為回收分區(qū)R R的首的首地址，大小為地址，大小為R R和和F2F2二者二者大小之和。大小之和。 這種情況下，回收后空這種情況下，回收后空閑分區(qū)表中表項數(shù)不變。閑分區(qū)表中表項數(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、

16、R R和和F2F2三者大小之和。三者大小之和。 這種情況下，回收后空這種情況下，回收后空閑分區(qū)表中表項數(shù)不但閑分區(qū)表中表項數(shù)不但沒有增加，反而減少一沒有增加，反而減少一項。項。 （2 2）回收內(nèi)存）回收內(nèi)存內(nèi)存回收情況內(nèi)存回收情況回收分區(qū)回收分區(qū)R(d)4)4)回收分區(qū)回收分區(qū)R R不鄰接空閑分不鄰接空閑分區(qū)，這時在空閑分區(qū)表區(qū)，這時在空閑分區(qū)表中新建一表項，并填寫中新建一表項，并填寫分區(qū)首地址、大小等信分區(qū)首地址、大小等信息。息。 這種情況下，回收后空這種情況下，回收后空閑分區(qū)表中表項數(shù)增加閑分區(qū)表中表項數(shù)增加一項。一項。四、伙伴系統(tǒng)四、伙伴系統(tǒng)1 1、固定分區(qū)：限制了活動進程的數(shù)目，內(nèi)存利

17、用率低、固定分區(qū)：限制了活動進程的數(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ū)的大小都是2 2的的k k次冪（次冪（lkmlkm）3 3、分配和回收方法：、分配和回收方法：P126P1264 4、分配和回收的時間性能取決于查找空閑分區(qū)的位置、分配和回收的時間性能取決于查找空閑分區(qū)的位置和分割、合并空閑分區(qū)所花費的時間和分割、合并空閑分區(qū)所花費的時間5 5、在當前、在當前OSOS中，普遍采用虛擬內(nèi)存機制中，普遍采用虛擬內(nèi)存機制 在多處理機系統(tǒng)

18、中，伙伴系統(tǒng)得到大量的應(yīng)用在多處理機系統(tǒng)中，伙伴系統(tǒng)得到大量的應(yīng)用五、哈希算法（五、哈希算法（1 1）1 1、分類搜索算法（快速適應(yīng)算法）和伙伴系統(tǒng)的共、分類搜索算法（快速適應(yīng)算法）和伙伴系統(tǒng)的共同特點：將空閑分區(qū)根據(jù)分區(qū)大小進行分類，對同特點：將空閑分區(qū)根據(jù)分區(qū)大小進行分類，對于每一類具有相同大小的空閑分區(qū)，單獨設(shè)立一于每一類具有相同大小的空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表。為進程分配內(nèi)存空間時，需在個空閑分區(qū)鏈表。為進程分配內(nèi)存空間時，需在一張管理索引表中查找所需空間大小所對應(yīng)的表一張管理索引表中查找所需空間大小所對應(yīng)的表項，通過指針找到一個空閑分區(qū)。項，通過指針找到一個空閑分區(qū)。五、哈希

19、算法（五、哈希算法（2 2）2 2、哈希算法利用哈希快速查找的優(yōu)點，以及空閑分區(qū)、哈希算法利用哈?？焖俨檎业膬?yōu)點，以及空閑分區(qū)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，每一個造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，每一個表項記錄了一個對應(yīng)的空閑分區(qū)鏈鏈表表頭指針。表項記錄了一個對應(yīng)的空閑分區(qū)鏈鏈表表頭指針。3 3、進行分配時，根據(jù)所需空閑分區(qū)大小，通過哈希函、進行分配時，根據(jù)所需空閑分區(qū)大小，通過哈希函數(shù)計算，得到在哈希表中的位置，找到相應(yīng)的空閑數(shù)計算，得到在哈希表中的位置，找到相應(yīng)的空閑分區(qū)鏈表，實現(xiàn)最佳分配策

20、略。分區(qū)鏈表，實現(xiàn)最佳分配策略。六、可重定位分區(qū)分配方式六、可重定位分區(qū)分配方式1 1、碎片問題、碎片問題 在分區(qū)存儲管理方式中，必須把作業(yè)裝入在分區(qū)存儲管理方式中，必須把作業(yè)裝入到一片連續(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è)要求分配40

21、KB40KB的內(nèi)存空間，由于系統(tǒng)中所有空閑分區(qū)的的內(nèi)存空間，由于系統(tǒng)中所有空閑分區(qū)的容量均小于容量均小于40KB40KB，故此作業(yè)無法裝入內(nèi)存。，故此作業(yè)無法裝入內(nèi)存。 系統(tǒng)中的碎片（系統(tǒng)中的碎片（1 1）os用用戶戶程程序序p4p1p20k20k56k65k125k135k內(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ù)碎片出

22、現(xiàn)的情況分為以下兩種：。根據(jù)碎片出現(xiàn)的情況分為以下兩種：系統(tǒng)中的碎片（系統(tǒng)中的碎片（2 2）25KB25KB作業(yè)作業(yè)D15KB15KB作業(yè)作業(yè)C30KB30KB作業(yè)作業(yè)B20KB20KB作業(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ù)拼接或緊

23、湊或緊縮技術(shù) 將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在內(nèi)將內(nèi)存中所有作業(yè)移到內(nèi)存一端（作業(yè)在內(nèi)存中的位置發(fā)生了變化，這就必須對其地址加以存中的位置發(fā)生了變化，這就必須對其地址加以修改或變換即稱為重定位），使本來分散的多個修改或變換即稱為重定位），使本來分散的多個小空閑分區(qū)連成一個大的空閑區(qū)。如圖所示。小空閑分區(qū)連成一個大的空閑區(qū)。如圖所示。 這種通過移動作業(yè)從把多個分散的小分區(qū)拼這種通過移動作業(yè)從把多個分散的小分區(qū)拼接成一個大分區(qū)的方法稱為拼接或緊湊或緊縮接成一個大分區(qū)的方法稱為拼接或緊湊或緊縮。 拼接時機：分區(qū)回收時；當找不到足夠大的空拼接時機：分區(qū)回收時；當找不到足夠大的空閑分區(qū)且總空閑分區(qū)容

24、量可以滿足作業(yè)要求時。閑分區(qū)且總空閑分區(qū)容量可以滿足作業(yè)要求時。作業(yè)作業(yè)D作業(yè)作業(yè)C作業(yè)作業(yè)B20KB20KB30KB 90KB30KB 90KB15KB15KB25KB25KB作業(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ū)分配方式進行分配分配方式進行分配YYNN無法分配，返回?zé)o法分配，返回請求分配一個請求分配一個大小為大小為x的分區(qū)的分區(qū)v動態(tài)重定位分

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

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