2柬采、連續(xù)分配方式

（1）單一連續(xù)分配

內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分：

????系統(tǒng)區(qū)：僅提供給OS使用欢唾，通常放在內(nèi)存低址部分

????用戶區(qū)：除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間，提供給用戶使用粉捻。

最簡(jiǎn)單的一種存儲(chǔ)管理方式礁遣，只能用于單用戶、單任務(wù)的操作系統(tǒng)中肩刃。

????優(yōu)點(diǎn)：易于管理祟霍。

????缺點(diǎn)：對(duì)要求內(nèi)存空間少的程序，造成內(nèi)存浪費(fèi)盈包；程序全部裝入沸呐，很少使用的程序部分也占用內(nèi)存。

（2）固定分區(qū)分配

????把內(nèi)存分為一些大小相等或不等的分區(qū)(partition)呢燥，每個(gè)應(yīng)用進(jìn)程占用一個(gè)分區(qū)崭添。操作系統(tǒng)占用其中一個(gè)分區(qū)。

????提高：支持多個(gè)程序并發(fā)執(zhí)行叛氨，適用于多道程序系統(tǒng)和分時(shí)系統(tǒng)呼渣。最早的多道程序存儲(chǔ)管理方式。

????劃分為幾個(gè)分區(qū)力试，便只允許幾道作業(yè)并發(fā)

1）如何劃分分區(qū)大嗅懔凇：

????分區(qū)大小相等：只適合于多個(gè)相同程序的并發(fā)執(zhí)行（處理多個(gè)類型相同的對(duì)象）。缺乏靈活性畸裳。

????分區(qū)大小不等：多個(gè)小分區(qū)、適量的中等分區(qū)淳地、少量的大分區(qū)怖糊。根據(jù)程序的大小，分配當(dāng)前空閑的颇象、適當(dāng)大小的分區(qū)伍伤。

2）需要的數(shù)據(jù)結(jié)構(gòu)

????建立一記錄相關(guān)信息的分區(qū)表（或分區(qū)鏈表），表項(xiàng)有:| 起始位置 | 大小 | 狀態(tài) |

????分區(qū)表中遣钳，表項(xiàng)值隨著內(nèi)存的分配和釋放而動(dòng)態(tài)改變

3）程序分配內(nèi)存的過(guò)程：

????也可將分區(qū)表分為兩個(gè)表格：空閑分區(qū)表/占用分區(qū)表扰魂。從而減小每個(gè)表格長(zhǎng)度。

????檢索算法：空閑分區(qū)表可能按不同分配算法采用不同方式對(duì)表項(xiàng)排序(將分區(qū)按大小排隊(duì)或按分區(qū)地址高低排序)蕴茴。

????過(guò)程：檢索空閑分區(qū)表劝评；找出一個(gè)滿足要求且尚未分配的分區(qū)，分配給請(qǐng)求程序倦淀；若未找到大小足夠的分區(qū)蒋畜，則拒絕為該用戶程序分配內(nèi)存。

????固定分配的不足：

????????內(nèi)碎片（一個(gè)分區(qū)內(nèi)的剩余空間）造成浪費(fèi)

????????分區(qū)總數(shù)固定撞叽，限制并發(fā)執(zhí)行的程序數(shù)目姻成。

（3）動(dòng)態(tài)分區(qū)分配

????分區(qū)的大小不固定：在裝入程序時(shí)根據(jù)進(jìn)程實(shí)際需要插龄，動(dòng)態(tài)分配內(nèi)存空間，即——需要多少劃分多少科展。

????空閑分區(qū)表項(xiàng)：從1項(xiàng)到n項(xiàng)：

????????內(nèi)存會(huì)從初始的一個(gè)大分區(qū)不斷被劃分均牢、回收從而形成內(nèi)存中的多個(gè)分區(qū)。

優(yōu)點(diǎn)：并發(fā)進(jìn)程數(shù)沒(méi)有固定數(shù)的限制才睹，不產(chǎn)生內(nèi)碎片膨处。

缺點(diǎn)：有外碎片（分區(qū)間無(wú)法利用的空間）

1）數(shù)據(jù)結(jié)構(gòu)

? ? ①空閑分區(qū)表：

????????記錄每個(gè)空閑分區(qū)的情況。

????????每個(gè)空閑分區(qū)對(duì)應(yīng)一個(gè)表目砂竖，包括分區(qū)序號(hào)真椿、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)項(xiàng)。

? ? ②空閑分區(qū)鏈：

????????每個(gè)分區(qū)的起始部分乎澄，設(shè)置用于控制分區(qū)分配的信息突硝，及用于鏈接各分區(qū)的前向指針；

????????分區(qū)尾部則設(shè)置一后向指針置济，在分區(qū)末尾重復(fù)設(shè)置狀態(tài)位和分區(qū)大小表目方便檢索解恰。

2）分區(qū)分配算法

動(dòng)態(tài)分區(qū)方式，分區(qū)多浙于、大小差異各不相同护盈，此時(shí)把一個(gè)新作業(yè)裝入內(nèi)存，更需選擇一個(gè)合適的分配算法羞酗，從空閑分區(qū)表/鏈中選出一合適分區(qū)

①首次適應(yīng)算法FF(first-fit)

????空閑分區(qū)排序：以地址遞增的次序鏈接腐宋。

????檢索：分配內(nèi)存時(shí)，從鏈?zhǔn)组_(kāi)始順序查找直至找到一個(gè)大小能滿足要求的空閑分區(qū)檀轨；

????分配：從該分區(qū)中劃出一塊作業(yè)要求大小的內(nèi)存空間分配給請(qǐng)求者胸竞，余下的空閑分區(qū)大小改變?nèi)粤粼诳臻e鏈中。

????若從頭到尾檢索不到滿足要求的分區(qū)則分配失敗

優(yōu)點(diǎn)：優(yōu)先利用內(nèi)存低址部分参萄，保留了高地址部分的大空閑區(qū)卫枝；

缺點(diǎn)：但低址部分不斷劃分，會(huì)產(chǎn)生較多小碎片讹挎；而且每次查找從低址部分開(kāi)始校赤，會(huì)逐漸增加查找開(kāi)銷。

②循環(huán)首次適應(yīng)算法 (next-fit)

????空閑分區(qū)排序：按地址

????檢索：從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找筒溃，直到找到一個(gè)能滿足要求的空閑分區(qū)马篮。為實(shí)現(xiàn)算法，需要：

????????設(shè)置一個(gè)起始查尋指針

????????采用循環(huán)查找方式

????分配：分出需要的大小

優(yōu)點(diǎn)：空閑分區(qū)分布均勻铡羡，減少查找開(kāi)銷

缺點(diǎn)：缺乏大的空閑分區(qū)

③最佳適應(yīng)算法 (best-fit)

總是把能滿足要求积蔚、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”烦周。

????空閑分區(qū)排序：所有空閑分區(qū)按容量從小到大排序成空閑分區(qū)表或鏈尽爆。

????檢索：從表或鏈的頭開(kāi)始怎顾，找到的第一個(gè)滿足的就分配

????分配：分出需要的大小

? 缺點(diǎn)：每次找到最合適大小的分區(qū)割下的空閑區(qū)也總是最小，會(huì)產(chǎn)生許多難以利用的小空閑區(qū)（外碎片）

④最差適應(yīng)算法/最壞匹配法(worst-fit)：基本不留下小空閑分區(qū)漱贱，但會(huì)出現(xiàn)缺乏較大的空閑分區(qū)的情況槐雾。

⑤快速適應(yīng)算法

????根據(jù)進(jìn)程常用空間大小進(jìn)行劃分，相同大小的串成一個(gè)鏈幅狮，需管理多個(gè)各種不同大小的分區(qū)的鏈表募强。進(jìn)程需要時(shí)，從最接近大小需求的鏈中摘一個(gè)分區(qū)崇摄。類似的：伙伴算法

????能快速找到合適分區(qū)擎值，但鏈表信息會(huì)很多；實(shí)際上是空間換時(shí)間逐抑。

3）分區(qū)分配操作

分配內(nèi)存

????找到滿足需要的合適分區(qū)鸠儿，劃出進(jìn)程需要的空間

????????if s<=size，將整個(gè)分區(qū)分配給請(qǐng)求者

????????if s> size厕氨，按請(qǐng)求的大小劃出一塊內(nèi)存空間分配出去进每，余下部分留在空閑鏈中，將分配區(qū)首址返回給調(diào)用者命斧。

回收內(nèi)存

????進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)田晚，系統(tǒng)根據(jù)回收區(qū)首址a，在空閑分區(qū)鏈(表)中找到相應(yīng)插入點(diǎn)国葬，根據(jù)情況修改空閑分區(qū)信息贤徒，可能會(huì)進(jìn)行空閑分區(qū)的合并：

????????(1)回收區(qū)（首址a）與一個(gè)分區(qū)f1末尾（首址b+大小）鄰接：將回收區(qū)與f1合并胃惜，修改f1的表項(xiàng)的分區(qū)大小

????????(2)回收區(qū)（首址a+大信⒗颉）與一個(gè)分區(qū)f2的首址b鄰接：將回收區(qū)與f2合并，修改f2的表項(xiàng)的首址船殉、分區(qū)大小

????????(3) （1）（2）兩種情況都有蝴簇，則將回收區(qū)與前后兩個(gè)分區(qū)F1质欲、F2鄰接：將三個(gè)分區(qū)合并混滔，使用F1的表項(xiàng)和F1的首址彩郊，取消F2的表項(xiàng)铝耻，大小為三者之和

????????(4) 回收區(qū)沒(méi)有鄰接的分區(qū)：為回收區(qū)單獨(dú)建立新表項(xiàng)甥材，填寫(xiě)回收區(qū)的首址與大小拉盾，根據(jù)其首址插到空閑鏈中的適當(dāng)位置

????動(dòng)態(tài)連續(xù)分配方式無(wú)法解決“外碎片”問(wèn)題

????當(dāng)前內(nèi)存分配有3個(gè)小碎片姊途，分別為30K钉疫，64K硼讽，40K。若有一個(gè)120K的作業(yè)申請(qǐng)一塊連續(xù)空間牲阁，無(wú)法滿足固阁。

????解決思路：移動(dòng)分區(qū)位置壤躲，將小碎片整合為一個(gè)足夠大小可被使用的分區(qū)。即緊湊思想

（4）動(dòng)態(tài)重定位分區(qū)分配?——有緊湊功能的動(dòng)態(tài)分區(qū)分配

用戶程序在內(nèi)存中移動(dòng)备燃，將空閑空間緊湊起來(lái)提高空間利用率碉克。但必然需要地址變化，增加“重定位”工作并齐。

地址變換過(guò)程是在程序執(zhí)行過(guò)程期間（相對(duì)地址與重定位寄存器中的地址相加）漏麦，隨著對(duì)每條指令的訪問(wèn)自動(dòng)進(jìn)行，稱為動(dòng)態(tài)重定位况褪。

動(dòng)態(tài)重定位分區(qū)分配算法與動(dòng)態(tài)分區(qū)分配算法基本相同撕贞，差別在于增加了緊湊的功能。

伙伴系統(tǒng)

????分區(qū)大小有規(guī)定测垛，且分區(qū)動(dòng)態(tài)變化

????????無(wú)論已分配還是空閑分區(qū)捏膨，大小都為2的k此冪。若整個(gè)可分配空間大小為2m赐纱，則1≤k≤m.

????????隨著系統(tǒng)運(yùn)行脊奋，內(nèi)存被不斷劃分，形成若干不連續(xù)的空閑分區(qū)疙描。對(duì)每一類具有相同大小的空閑分區(qū)設(shè)置一雙向鏈表诚隙，即會(huì)有k個(gè)鏈表，鏈表中的分區(qū)大小都是2m起胰。

????????進(jìn)程申請(qǐng)n個(gè)大小的空間時(shí)久又，計(jì)算n= 2i。則找i對(duì)應(yīng)的鏈表效五。若i大小的鏈表沒(méi)有地消，則找i+1的鏈表。找到的分區(qū)對(duì)半劃分后畏妖，一半用于分配脉执，一半鏈接到較小一級(jí)的鏈表里去。

????????一次分配和回收都可能對(duì)應(yīng)多次的劃分和合并戒劫。

（5）內(nèi)存空間管理之對(duì)換

當(dāng)內(nèi)存空間還是滿足不了需求時(shí)半夷，引入“對(duì)換”思想：

????把內(nèi)存中暫時(shí)不能運(yùn)行、或暫時(shí)不用的程序和數(shù)據(jù)調(diào)到外存上迅细，以騰出足夠的內(nèi)存巫橄；把已具備運(yùn)行條件的進(jìn)程和進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存茵典。

????按對(duì)換單位分類：

????????整體對(duì)換(或進(jìn)程對(duì)換)：以整個(gè)進(jìn)程為單位（連續(xù)分配）

????????頁(yè)面對(duì)換或分段對(duì)換：以頁(yè)或段為單位（離散分配）

實(shí)現(xiàn)進(jìn)程對(duì)換湘换，系統(tǒng)必須具備的功能：

????對(duì)換空間的管理

????進(jìn)程的換出、換入操作

對(duì)換空間的管理

在系統(tǒng)中設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)以記錄對(duì)換區(qū)的使用情況

對(duì)換空間的分配與回收是連續(xù)方式，與動(dòng)態(tài)分區(qū)方式時(shí)的內(nèi)存分配與回收雷同彩倚。