【正文】 分配已分配 ”標(biāo)志；若未找到大小足標(biāo)志；若未找到大小足夠的分區(qū)，則拒絕為之分配內(nèi)存。夠的分區(qū)，則拒絕為之分配內(nèi)存。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬28n 分區(qū)大小固定，靈活性仍不足，會產(chǎn)生內(nèi)存碎片；分區(qū)大小固定，靈活性仍不足，會產(chǎn)生內(nèi)存碎片；在某些用于控制相同對象的場合仍有一定應(yīng)用。在某些用于控制相同對象的場合仍有一定應(yīng)用。作業(yè) 2： 30K作業(yè) 1： 112K齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬29 動態(tài)分區(qū)分配動態(tài)分區(qū)分配n 動態(tài)分區(qū)分配是動態(tài)分區(qū)分配是 根據(jù)進(jìn)程的實際需要，動態(tài)根據(jù)進(jìn)程的實際需要，動態(tài)地為之分配內(nèi)存空間地為之分配內(nèi)存空間 。又稱為可變分區(qū)分配。又稱為可變分區(qū)分配。n 示意圖示意圖齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬30可變分區(qū)內(nèi)存使用示意圖可變分區(qū)內(nèi)存使用示意圖齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬31 動態(tài)分區(qū)分配動態(tài)分區(qū)分配n 三個問題三個問題– 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)– 分區(qū)分配算法分區(qū)分配算法– 分區(qū)分配操作分區(qū)分配操作齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬32n 記錄內(nèi)存的使用情況，為分配提供依據(jù)。記錄內(nèi)存的使用情況，為分配提供依據(jù)。n (1)空閑分區(qū)表空閑分區(qū)表在系統(tǒng)中設(shè)置一張空閑分區(qū)表，在系統(tǒng)中設(shè)置一張空閑分區(qū)表， 用于記錄每用于記錄每個空閑分區(qū)的情況。每個空閑分區(qū)占一個表個空閑分區(qū)的情況。每個空閑分區(qū)占一個表目目 ，表目中包括分區(qū)序號、分區(qū)始址及分區(qū)，表目中包括分區(qū)序號、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)項。的大小等數(shù)據(jù)項。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬33n (2)空閑分區(qū)鏈空閑分區(qū)鏈每個分區(qū)的每個分區(qū)的 起始起始 部部分，設(shè)置用于鏈接分，設(shè)置用于鏈接各分區(qū)的前向指針各分區(qū)的前向指針；在分區(qū)；在分區(qū) 尾部尾部 設(shè)置設(shè)置一后向指針。通過一后向指針。通過前、后向鏈接指針前、后向鏈接指針，可將所有的空閑，可將所有的空閑分區(qū)鏈接成一個雙分區(qū)鏈接成一個雙向鏈。向鏈。 前后向指針，大小，狀態(tài)齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬34n 按照一定的分配算法，從空閑分區(qū)表或空閑按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。n 常用的三種分配算法：常用的三種分配算法：l首次適應(yīng)算法首次適應(yīng)算法l循環(huán)適應(yīng)算法循環(huán)適應(yīng)算法l最佳適應(yīng)算法最佳適應(yīng)算法齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬35(1)首次適應(yīng)算法首次適應(yīng)算法n 空閑分區(qū)空閑分區(qū) 以地址遞增以地址遞增 的次序鏈接。的次序鏈接。 分配時，從鏈?zhǔn)追峙鋾r，從鏈?zhǔn)组_始順序查找，直至找到一個大小能滿足要求的空開始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)閑分區(qū) ；； 然后根據(jù)作業(yè)的大小，從該分區(qū)中劃出一然后根據(jù)作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中空閑鏈中 。n 優(yōu)點：傾向于利用內(nèi)存中低址的空閑區(qū)，保留了高優(yōu)點：傾向于利用內(nèi)存中低址的空閑區(qū)，保留了高址部分的大空閑區(qū)，為以后到達(dá)的大作業(yè)分配大的址部分的大空閑區(qū)，為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。內(nèi)存空間創(chuàng)造了條件。缺點：低址不斷被劃分，會產(chǎn)生大量的碎片；每次缺點：低址不斷被劃分，會產(chǎn)生大量的碎片；每次從低址開始查找，會增加查找可用空間的開銷。從低址開始查找，會增加查找可用空間的開銷。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬36(1)首次適應(yīng)算法首次適應(yīng)算法圖中采用的空閑分區(qū)鏈按地址由小到大的順序?qū)臻e分區(qū)進(jìn)行組織，開始指向以 40k為首址的空閑分區(qū)（其大小為 46k，下一個空閑分區(qū)為始址為 118k）。作業(yè) 5大小為 36k齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬37(2)循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法n 分配時，分配時， 不每次均從鏈?zhǔn)组_始查找，而是從上次找不每次均從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找到的空閑分區(qū)的下一個空閑分區(qū)開始查找 ，直至找，直至找到第一個能滿足要求的空閑分區(qū)，并從中劃出一塊到第一個能滿足要求的空閑分區(qū)，并從中劃出一塊與請求的大小相等的內(nèi)存空間分配給作業(yè)。與請求的大小相等的內(nèi)存空間分配給作業(yè)。n 需需 設(shè)置一起始查尋指針，以指示下一次起始查尋的設(shè)置一起始查尋指針，以指示下一次起始查尋的空閑分區(qū)，并采用循環(huán)查找方式?？臻e分區(qū)，并采用循環(huán)查找方式。 即如果最后一個即如果最后一個(鏈尾鏈尾 )空閑分區(qū)，其大小仍不能滿足要求，應(yīng)返回空閑分區(qū)，其大小仍不能滿足要求，應(yīng)返回到第一個空閑分區(qū)，比較其大小是否滿足要求。找到第一個空閑分區(qū)，比較其大小是否滿足要求。找到后，應(yīng)立即調(diào)整起始查尋指針。到后，應(yīng)立即調(diào)整起始查尋指針。n 優(yōu)點：空閑分區(qū)分布均更均勻，減少了查找空閑分優(yōu)點：空閑分區(qū)分布均更均勻，減少了查找空閑分區(qū)的開銷，但會導(dǎo)致缺乏大的空閑分區(qū)。區(qū)的開銷，但會導(dǎo)致缺乏大的空閑分區(qū)。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬38(3)最佳適應(yīng)算法最佳適應(yīng)算法n 每次為作業(yè)分配內(nèi)存時，每次為作業(yè)分配內(nèi)存時， 總是把既能滿足要求，又總是把既能滿足要求，又是最小的空閑分區(qū)分配給作業(yè)是最小的空閑分區(qū)分配給作業(yè) ，避免了，避免了 “大材小用大材小用 ”。n 為了加速尋找，為了加速尋找， 要求將所有的空閑區(qū)，按其容量大要求將所有的空閑區(qū)，按其容量大小以遞增的順序形成一空閑區(qū)鏈小以遞增的順序形成一空閑區(qū)鏈 。這樣，第一次找。這樣，第一次找到的滿足要求的空閑區(qū)，必然是最優(yōu)的。到的滿足要求的空閑區(qū)，必然是最優(yōu)的。n 特點：每次似乎是最佳的，然而在宏觀上卻不一定特點：每次似乎是最佳的，然而在宏觀上卻不一定。每次分配后所切割下來的剩余部分總是最小的。每次分配后所切割下來的剩余部分總是最小的，在存儲器中會留下許多這樣難以利用的小空閑區(qū)。在存儲器中會留下許多這樣難以利用的小空閑區(qū)。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬39(3)最佳適應(yīng)算法最佳適應(yīng)算法圖中采用的空閑分區(qū)鏈按容量由小到大的順序組織齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬40 (分配－回收分配－回收 )1)分配內(nèi)存分配內(nèi)存若若 =size，說明多余部分太小，可說明多余部分太小，可不再切割，將整個分區(qū)不再切割，將整個分區(qū)分配給請求者；否則，分配給請求者；否則，從該分區(qū)中劃分出與請從該分區(qū)中劃分出與請求的大小相等的內(nèi)存空求的大小相等的內(nèi)存空間分配出去，余下的部間分配出去，余下的部分仍留在空閑分區(qū)鏈或分仍留在空閑分區(qū)鏈或空閑分區(qū)表中。最后，空閑分區(qū)表中。最后，將分配區(qū)的首址返回給將分配區(qū)的首址返回給調(diào)用者。調(diào)用者。 空閑分區(qū)大小 用戶作業(yè)大小 齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬412)回收內(nèi)存回收內(nèi)存n 當(dāng)一個進(jìn)程（或程序）釋放其所占內(nèi)存區(qū)時，系統(tǒng)當(dāng)一個進(jìn)程（或程序）釋放其所占內(nèi)存區(qū)時，系統(tǒng)將首先檢查回收區(qū)是否與其它空閑區(qū)相鄰，若相鄰將首先檢查回收區(qū)是否與其它空閑區(qū)相鄰，若相鄰則合并成一個空閑區(qū)，否則，將回收區(qū)插入空閑分則合并成一個空閑區(qū)，否則，將回收區(qū)插入空閑分區(qū)表（或空閑分區(qū)鏈）中的適當(dāng)位置。區(qū)表（或空閑分區(qū)鏈）中的適當(dāng)位置。n 回收情況：回收情況：– A. 只有前鄰空閑區(qū)只有前鄰空閑區(qū)– B. 只有后鄰空閑區(qū)只有后鄰空閑區(qū)– C. 既有前鄰空閑區(qū)又有后鄰空閑區(qū)既有前鄰空閑區(qū)又有后鄰空閑區(qū)– D. 沒有鄰接空閑區(qū)沒有鄰接空閑區(qū)根據(jù)不同情況，根據(jù)不同情況， A、 B、 C有不同的合并策略。有不同的合并策略。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬42回收內(nèi)存示意圖回收內(nèi)存示意圖n A. 將 R合并到 f1， ； + ??n B. 將 f2 合并到 R ， ； + ??n C. f R、 f2合并到 f1， ； ++ ；撤消 f2空閑區(qū)表項 ??n D. R作為一個新空閑區(qū)，插入到空閑區(qū)表（鏈）的適當(dāng)位置。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬43 動態(tài)動態(tài) 重定位重定位 分區(qū)分配分區(qū)分配n n n 齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬44n 為了充分利用內(nèi)存碎片為了充分利用內(nèi)存碎片，可利用，可利用 “緊湊緊湊 ”操作操作 把把多個碎片處理為一個比多個碎片處理為一個比較大的分區(qū)，以便利用較大的分區(qū)，以便利用。 n 經(jīng)過緊湊后的某些用戶經(jīng)過緊湊后的某些用戶程序在內(nèi)存中的位置發(fā)程序在內(nèi)存中的位置發(fā)生了變化生了變化 ，此時需對程，此時需對程序和數(shù)據(jù)的地址加以修序和數(shù)據(jù)的地址加以修改（變換），即改（變換），即 需要進(jìn)需要進(jìn)行重定位行重定位 。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬45n 采用動態(tài)運行時裝入方式，地址轉(zhuǎn)換推遲到程序指采用動態(tài)運行時裝入方式，地址轉(zhuǎn)換推遲到程序指令真正要執(zhí)行時進(jìn)行。令真正要執(zhí)行時進(jìn)行。n 為避免影響速度，為避免影響速度， 必須有硬件地址變換機構(gòu)的支持必須有硬件地址變換機構(gòu)的支持（重定位寄存器）（重定位寄存器） ，用它來存放程序在內(nèi)存中的起，用它來存放程序在內(nèi)存中的起始地址。程序在執(zhí)行時，始地址。程序在執(zhí)行時， 真正訪問的內(nèi)存地址是相真正訪問的內(nèi)存地址是相對地址與重定位寄存器中的地址相加而形成的對地址與重定位寄存器中的地址相加而形成的 。n 地址變換過程是在程序執(zhí)行期間，隨著對每條指令地址變換過程是在程序執(zhí)行期間，隨著對每條指令和數(shù)據(jù)的訪問而自動進(jìn)行的，故稱為和數(shù)據(jù)的訪問而自動進(jìn)行的，故稱為 動態(tài)重定位動態(tài)重定位 。n 當(dāng)系統(tǒng)對內(nèi)存進(jìn)行了當(dāng)系統(tǒng)對內(nèi)存進(jìn)行了 “緊湊緊湊 ”，而使若干程序從內(nèi)存，而使若干程序從內(nèi)存的某處移至另一處時，不需對程序做任何修改，只的某處移至另一處時，不需對程序做任何修改，只要用該程序的新起始地址，去置換原來的起始地址要用該程序的新起始地址，去置換原來的起始地址即可。即可。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬46齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬47與動態(tài)分區(qū)分配算法基本相同，差別僅在于：增加了緊湊功能 ，在找不到足夠大的空閑分區(qū)來滿足用戶需求時進(jìn)行緊湊。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬48n 優(yōu)點：解決了動態(tài)分區(qū)分配所引入的優(yōu)點：解決了動態(tài)分區(qū)分配所引入的 “內(nèi)存內(nèi)存零頭零頭 ”問題。消除內(nèi)存碎片，提高內(nèi)存利用問題。消除內(nèi)存碎片，提高內(nèi)存利用率。率。n 缺點：提高硬件成本，緊湊時花費缺點：提高硬件成本，緊湊時花費 CPU時間時間。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬49動態(tài)重定位動態(tài)重定位 VS 靜態(tài)重定位靜態(tài)重定位n 靜態(tài)重定位靜態(tài)重定位 :當(dāng)用戶程序被裝入內(nèi)存時，一當(dāng)用戶程序被裝入內(nèi)存時，一次性實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后次性實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換。不再轉(zhuǎn)換。n 動態(tài)重定位動態(tài)重定位 :在程序運行過程中要訪問數(shù)據(jù)在程序運行過程中要訪問數(shù)據(jù)時再進(jìn)行地址變換。由地址變換機構(gòu)進(jìn)行的時再進(jìn)行地址變換。由地址變換機構(gòu)進(jìn)行的地址變換，硬件上需要重定位寄存器的支持地址變換，硬件上需要重定位寄存器的支持。動態(tài)重定位分區(qū)分配動態(tài)重定位分區(qū)分配 VS動態(tài)分區(qū)分配動態(tài)分區(qū)分配相對而言，前者具有緊湊功能，需要重定位相對而言，前者具有緊湊功能，需要重定位寄存器支持寄存器支持齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬50 對換對換 (Swapping)n n 把內(nèi)存中暫時不能運行的進(jìn)程或暫時不用的程序和把內(nèi)存中暫時不能運行的進(jìn)程或暫時不用的程序和數(shù)據(jù)，換出到外存，而把已具備運行條件的進(jìn)程或數(shù)據(jù)，換出到外存，而把已具備運行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，換入內(nèi)存，使其投入運進(jìn)程所需要的程序和數(shù)據(jù)，換入內(nèi)存，使其投入運行行 (從而提高內(nèi)存利用率從而提高內(nèi)存利用率 )。n 如果對換如果對換 以整個進(jìn)程為單位以整個進(jìn)程為單位 ，稱之為，稱之為 “整體對換整體對換 ”或或“進(jìn)程對換進(jìn)程對換 ”。目的是為了解決內(nèi)存緊張問題。目的是為了解決內(nèi)存緊張問題如果對換如果對換 以以 “頁頁 ”或或 “段段 ”為單位為單位 ，則稱之為，則稱之為 “頁面對頁面對換換 ”或或 “分段對換分段對換 ”。目的是為了支持虛擬存儲系統(tǒng)。目的是為了支持虛擬存儲系統(tǒng)n 此小節(jié)僅介紹進(jìn)程對換。為了進(jìn)程對換，需三方面此小節(jié)僅介紹進(jìn)程對換。為了進(jìn)程對換，需三方面功能：對換空間的管理、進(jìn)程的換出及換入。功能：對換空間的管理、進(jìn)程的換出及換入。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬51n 把把 外存分為外存分為 文件區(qū)和對換區(qū)文件區(qū)和對換區(qū)l 文件區(qū)文件區(qū) ：用于：用于 存放文件存放文件 ；為了提高空間的利；為了提高空間的利用率，對其采用用率，對其采用 離散分配方式離散分配方式 。l 對換區(qū)對換區(qū) ：用于：用于 存放從內(nèi)存換出的進(jìn)程存放從內(nèi)存換出的進(jìn)程 ；因?qū)?；因?qū)Q操作頻繁，為提高進(jìn)程換入換出速度，對換操作頻繁，為提高進(jìn)程換入換出速度，對其采用其采用 連續(xù)分配方式連續(xù)分配方式 。(對換是在對換是在 內(nèi)存與內(nèi)存與 外存的對換區(qū)之間進(jìn)行外存的對換區(qū)之間進(jìn)行））齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬52n 為了對對換區(qū)中的空閑盤塊進(jìn)行管理，在系為了對對換區(qū)中的空閑盤塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的統(tǒng)中應(yīng)配置相應(yīng)的 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) ，以記錄外存的，以記錄外存的使用情況。與內(nèi)存在動態(tài)分區(qū)分配方式中所使用情況。與內(nèi)存在動態(tài)分區(qū)分配方式中所用的數(shù)據(jù)結(jié)構(gòu)相似，同樣可以用空閑分區(qū)表用的數(shù)據(jù)結(jié)構(gòu)相似，同樣可以用空閑分區(qū)表或空閑分區(qū)鏈?；蚩臻e分區(qū)鏈。n 對換空間的對換空間的 分配與回收分配與回收 ，與動態(tài)分區(qū)分配方，