动态分区式内存管理（完整代码）
操作系統實驗導航
實驗一：銀行家算法 https://blog.csdn.net/weixin_46291251/article/details/115384510
實驗二：多級隊列調度和多級反饋隊列調度算法 https://blog.csdn.net/weixin_46291251/article/details/115530582
實驗三：動態分區式內存管理 https://blog.csdn.net/weixin_46291251/article/details/115772341
實驗四：Linux下多進程通信 https://blog.csdn.net/weixin_46291251/article/details/116274665
實驗五：進程通信的三種方式 https://blog.csdn.net/weixin_46291251/article/details/116301250
實驗六：Linux文件系統實驗 https://blog.csdn.net/weixin_46291251/article/details/116423798
實驗七：自制簡單U盤引導程序 https://blog.csdn.net/weixin_46291251/article/details/116427629
實驗八：磁盤調度算法 https://blog.csdn.net/weixin_46291251/article/details/116431907
實驗九：請求分頁系統中的置換算法 https://blog.csdn.net/weixin_46291251/article/details/116443021
學習筆記：操作系統復習筆記 https://blog.csdn.net/weixin_46291251/article/details/117086851
背景知識：
關于內存管理的幾種方式：
固定分區：
原理：又稱定長分區或靜態分區模式，是滿足多道程序設計需要的最簡單的存儲管理技術。基本思想：給進入主存的用戶作業劃分一塊連續存儲區域，把作業裝入該連續存儲區域，若有多個作業裝入主存，則它們可并發執行。
使用大小相等的固定分區有兩個難點：程序可能太大而不能放到一個分區中，內存的，利用率很低。由于被裝入的數據塊小于分區大小，從而導致分區內部有浪費現象，成為“內部碎片”。對與大小不等的分區策略，最簡單的方法就是把每個進程分配到能夠容納它的最小分區中。
目前已經基本上沒有什么場合使用固定分區。
優勢：實現簡單，只需要極少的操作系統開銷
缺點：有內部碎片，對內存的使用不充分，活動進程的最大數目是固定的。
可變分區：
可變分區存儲管理不是預先把內存中的用戶區域劃分成若干固定分區，而是在作業要求裝入內存時，根據用戶作業的大小和當時內存空間使用情況決定是否為該作業分配一個分區。因此分區大小不是預先固定的，而是按作業需求量來劃分的；分區的個數和位置也不是預先確定的。它有效地克服了固定分區方式中，由于分區內部剩余內存空置造成浪費的問題。
可變分區方式常用的內存分配算法有以下幾種：
-
1、 最先適應分配算法
每次分配總是順序查找空閑區表，找到能滿足長度要求的空閑區就分配。優點是實現簡單，缺點是可能將大的空閑區分割成許多小的空閑區，形成許多不連續的“碎片”。碎片長度可能不能滿足作業要求，降低了內存利用率。
改進方法，可把空閑區按地址順序從小到大登記在空閑區表中，有利于大作業。問題是歸還空區時須按地址插入表中適當位置。 -
2、最優適應分配算法
按作業要求從所有空閑區中挑選一個能滿足要求的最小空閑區，這樣保證不去分割一個更大的區域，使裝入大作業時比較容易得到滿足。實現辦法：將空閑區按長度以遞增次序登記在表中，分配時按空閑區表順序查找即可。缺點是可能碎片更小而無法使用。回收時也要按長度扦入。 -
3、最壞適應分配算法
這種算法總是挑選一個最大的空閑區分割一部分給作業使用，使剩下部分不致太小，仍可供分配使用。實現辦法：空閑區表中的登記項按空閑區長度遞減順序排列，按序查找分配。
題目描述：動態分區式存貯區管理
設計一個動態分區式存貯區管理程序，要求支持不同的放置策略。如首次、最佳、最壞。
說明：
（1）分區描述器rd如下:
（2）主程序結構如下：
輸入放置策略 申請一塊內存作為主存循環處理用戶的請求（包括申請、釋放）需設計兩個函數處理用戶請求：
- 申請函數 Addr=Request(size)
- 釋放函數 Release(addr）
（3）數據實例：maxsize=512
J1申請162，J2申請64，J3申請120，J4申請86，J1完成，J3完成，J5申請72，J6申請100，J2完成，J7申請36，J8申請60，J4完成， J9申請110，J10申請42。備注：
- （a）所有大小其單位為節（1節=rd的大小）
- （b）作業申請n節,實際分配的分區大小應為n+1節。 其中一節作為分區描述器，其他n節提供給作業。
- （c）已分配區放在高地址處。
- （d）合并時應考慮四種情況： 假設回收區為r,上鄰為f1（f1需搜索自由主存隊列）,下鄰為f2（f2可直接計算）
A)f1空閑，f2已分配；
B)f1已分配，f2空閑；
C)f1空閑，f2空閑；
D)f1已分配，f2已分配；
設計思路：
-
向系統申請內存：
需要申請的內存單元的個數：totalNum
每個內存單元的大小：sizeof(rd)
程序實際向系統申請到達大小：maxsize
即：
const int totalNum = 512;//需要申請的塊數
const int maxsize = totalNum * sizeof(rd);//實際需要申請的大小
rd* MainHead = (rd*)malloc(maxsize);//申請到的資源 -
進程向程序申請內存Request：
原型：rd* Request(int need,int choice);
參數：need表示需要申請的大小，choice表示分配時采取的方法。
返回值：返回一個指針，指向申請到的空間的首地址，若為空則表示申請失敗。 -
進程釋放內存Release：
原型：bool Release(rd* r);
參數：r表示待釋放內存的首地址
返回值：返回1表示釋放成功，0表示失敗 -
可視化展示內存使用情況：
每一次讀取用戶的請求后，程序均輸出當前的內存使用情況，方便用戶查看，包括空閑隊列的情況、已用隊列的情況、內存總體分配情況。
數據結構：
- 分區描述器：
設計一個結構體rd用來表示分區描述器，其包含：
Flag：分配標志，空閑為0，不為0則表示進程編號
Size：分區大小，分區可用字數+分區描述器大小
*next：指向下一個同類型的區域
- 空閑內存隊列和已用內存隊列：
兩個隊列都通過鏈表的形式組織
分別為其設置頭節點Free和Used：
算法設計
三種算法：
首次：按物理地址的順序排列，優先地址最小的最佳：按照空閑容量遞增排列，優先最小的最壞：按照空閑容量遞減排列，優先最大的三種算法在分配和釋放的操作上沒有區別。
區別在于：空閑隊列變化以后需要排序，該排序對應的排序算法不同（依據是以上原理）。但在本程序中不使用排序算法，而是每次都遍歷搜索滿足條件的最值。
進程向程序申請內存Request：
無論是利用上述的哪種方法，都需要從已經給定的頭節點開始遍歷，找到>=需求的一塊空間。
找到滿足上述三種算法中最優的內存塊：找到內存大小比need大的內存塊中地址最小的、內存最小的、內存最大的。
上述最優的內存塊分兩種情況：
- 內存=need:這種情況只需要在free隊列刪除該節點，并將其加入used隊列即可。
- 內存>need:這種情況需要將原節點信息中的size減小need大小然后在used隊列中插入一個新節點。
進程釋放內存Release：
釋放進程時需要分以下四種情況：假設三塊連續內存分別為f1、r、f2
上鄰為f1（f1需搜索自由主存隊列）,下鄰為f2（f2可直接計算）
- A)f1空閑，f2已分配； //f和f1合并，修改表項f1，數量不變
- B)f1已分配，f2空閑； //f和f2合并，修改表項f2，數量不變
- C)f1空閑，f2空閑； //f1 f f2合并，修改表項f1，刪除f2
- D)f1已分配，f2已分配； //增加空閑表項f
這里設計兩個信號量bool f1_is_free = 1, f2_is_free = 1;分別用來判斷f1、f2是否已分配，然后程序遍歷兩個隊列正確修改信號量的值后，程序根據這兩個值分四種情況對兩個隊列做出相應的修改即可。
可視化展示內存使用情況：
首先遍歷輸出兩個隊列的以下信息：
- 1.頭節點相對于總內存起點的偏移量
- 2.該段內存實際大小
由于本程序中插入隊列元素時沒有對其排序，上述輸出不直觀，所以繼續采用以下方法輸出：
由內存的起點開始向后同時遍歷兩個隊列，每次找到與之最相鄰的那個內存塊。
找到內存塊后由flag判斷其是否已占用，由size判斷這塊內存的大小。
輸出頭節點相對于總內存起點的偏移量然后輸出不同數量的符號表示這塊空間
原則：未占用用‘-’表示，已占用用‘+’表示
輸出的數量（長度）與內存大小成正比。
輸出示例：
整體實現的代碼：
#include <iostream> #include <fstream> using namespace std;struct rd {//分區描述器int flag = -1; //分配標志，空閑為0，//不為0則表示進程編號int size = -1; //分區大小，分區可用字數+分區描述器大小rd* next = NULL; //對空閑區：指向下一個空閑分區，對已分配區：此項為零。 }; rd* Free = new rd, * Used = new rd;//分別用來存空閑隊列和已占用隊列const int totalNum = 512;//需要申請的塊數 const int maxsize = 512 * sizeof(rd);//實際需要申請的大小 rd* MainHead = (rd*)malloc(maxsize);//申請到的資源rd* Request(int need,int choice) {//申請地址的函數，返回申請到的地址，為NULL則無法申請。//size為要申請的danwei大小的個數，實際大小為size* sizeof(rd); int tem;rd* Ans = NULL;rd* p = NULL, * prep = new rd, * preAns = new rd;if (choice == 1) {//首次算法:按物理地址的順序排列，優先地址最小的tem = INT_MAX;for (p = Free->next, prep->next = p; p != NULL; p = p->next, prep = prep->next)if ((int)p < tem && p->size > need)tem = (int)p, Ans = p, preAns = prep;if (Ans == NULL)return NULL;}else if (choice == 2) {//最佳算法按:照空閑容量遞增排列，優先最小的tem = totalNum;for (p = Free->next, prep->next = p; p != NULL; p=p->next, prep= prep->next)if (p->size < tem && p->size > need)tem = p->size, Ans = p, preAns = prep;if (Ans == NULL)return NULL;}else if (choice == 3) {//最壞算法：按照空閑容量遞減排列，優先最大的tem = 0;for (p = Free->next, prep->next = p; p != NULL; p = p->next, prep = prep->next)if (p->size > tem) tem = p->size, Ans = p, preAns = prep;if (tem < need)return NULL;}//修改free隊列if (Ans->size == need)preAns->next = Ans->next;//刪除表項else {Ans->size -= need;//Ans =(Ans+Ans->size * sizeof(rd));//后一半劃分出去// cout<<"當前分配地址距離開始" << Ans - MainHead << endl;Ans += Ans->size;}Ans->flag = 1;Ans->size = need;//修改used隊列if (Used->next == NULL) {Used->next = Ans;Ans->next = NULL;} else {Ans->next = Used->next;Used->next = Ans;}return Ans; } bool Release(rd* r) {//釋放所給出的分區的地址，返回1表示正常釋放if (r->flag == 0) {cout << "該空間未使用，無法釋放" << endl;return 0;}rd* p = NULL;rd* f1 = NULL, * f2 = NULL;//先判斷usedfor (p = Used->next; p != NULL; p = p->next) {if (p->next == r)f1 = p;if (r->next == p)f2 = p;}//再判斷freefor (p = Free->next; p != NULL; p = p->next) {if (p+p->size == r)f1 = p;if (r+r->size == p)f2 = p;}//修改used隊列for (p = Used->next; p != NULL; p = p->next)if (p->next == r) {p->next = r->next;break;}bool f1_is_free = 1, f2_is_free = 1;if (f1->flag)f1_is_free = 0;if (f2 == NULL || f2->flag)f2_is_free = 0;//修改free隊列if (f1_is_free && !f2_is_free) { // A)f1空閑，f2已分配； //f和f1合并，修改表項f1，數量不變f1->next = r->next;f1->size += r->size;}else if (!f1_is_free && f2_is_free) { // B)f1已分配，f2空閑； //f和f2合并，修改表項f2，數量不變r->next = f2->next;r->flag = 0;r->size += f2->size;for (p = Free; p != NULL; p = p->next)//找到f2的前驅if (p->next == f2) {p->next = r;//后繼修改為rbreak;}}else if (f1_is_free && f2_is_free) { // C)f1空閑，f2空閑； //f1 f f2合并，修改表項f1，刪除f2for (p = Free; p != NULL; p = p->next)//找到f1的前驅if (p->next == f1) break;if (p != f2->next)//防止構成環路f1->next = f2->next;f1->size += (f2->size+r->size);for (p = Free; p != NULL; p = p->next)//找到f2的前驅if (p->next == f2) {p->next = f2->next;//后繼修改為rbreak;}}else if (!f1_is_free && !f2_is_free) {// D)f1已分配，f2已分配； //增加空閑表項fr->flag = 0;if (Free->next == NULL) {Free->next = r;r->next = NULL;}else {r->next = Free->next;Free->next = r;}}return 1; } void show_detail() {//展示內存的使用情況rd* p = NULL;rd* Cur = MainHead;//先判斷usedcout <<"Used:--";for (p = Used->next; p != NULL; p = p->next) {cout << p - MainHead <<"_"<<p->size<< "--->";}cout << endl;//再判斷freecout << "Free:--";for (p = Free->next; p != NULL; p = p->next) {cout << p - MainHead << "_" << p->size << "--->";}cout << endl;do{//直到當前是最后一塊為止for (p = Free->next; p != NULL; p = p->next)if (Cur == p) {break;}for (p = Used->next; p != NULL; p = p->next)if (Cur == p) {break;}//到此就找到了上一次的Cur后跟的塊（free或者used）//輸出可視化//512個字節，共分為26段，已用用+++++表示，未用用======表示，每段用三個符號表示string u = "+++";string f = "---";if (Cur->flag == 0) {//為free// cout << Cur->size;cout << Cur - MainHead;for (int i = 0; i < (Cur->size / 20); i++)cout << f;}if (Cur->flag != 0) {//為freecout << Cur - MainHead;for (int i = 0; i < (Cur->size / 20); i++)cout << u;}Cur += Cur->size;} while ((Cur - MainHead ) < totalNum-1);cout << "|||";cout << endl << endl << endl << endl;}int main() {while (1) {cout << "——————————請輸入放置策略————————" << endl;cout << "—— 首次：1 最佳：2 最壞：3 退出：0——" << endl;cout << "—————————————————————————" << endl;int method ;cin >> method;if(method==0) {system("cls");cout << "——————————Thanks!————————" << endl;return 0;}if (method != 1 && method != 2 && method != 3) {cout << "您的輸入有誤，請重新輸入:" << endl;continue;}MainHead = (rd*)malloc(maxsize);//申請到的資源Free = new rd, Used = new rd;//分別用來存空閑隊列和已占用隊列MainHead->next = NULL;rd* fir = MainHead;fir->next = NULL; fir->flag = 0; fir->size = totalNum - 1;Free->next = fir;char operat;int id, need;fstream In;In.open("請求.txt");if (!In.is_open())cout << "文件打開失敗" << endl;cout << "初始狀態：" << endl; show_detail();//展示初始狀態while (!In.eof()) {In >> operat;if (operat == '+') {In >> id >> need;rd* req = Request(need+1, method);//req為申請到的地址if (req == NULL) {cout << " 失敗___" << id << " +++ " << need << " " << endl;break;}cout << " 成功___" <<id<< " +++ " << need << " " << endl;req->flag = id;req->size = need+1;}else if (operat == '-') {In >> id ;rd* rel = Used->next;for (; rel != NULL; rel=rel->next)if (rel->flag == id)break;int rel_ans = 1;int rel_size = rel->size;if (rel == Used->next) {cout << "進程" << id << "沒有正在使用的空間" << endl;break;}else rel_ans = Release(rel);if (rel_ans == 0) {cout << "進程___" << id << "無法釋放" << endl;}else cout << " 成功___" << id << " --- " << rel_size << " " << endl;}else {cout << operat << "讀取失敗" << endl;break;}show_detail();//展示每次修改后的結果}free(MainHead); }return 0; }程序運行情況：
測試數據：
運行截圖：
- 方法二：最佳優先算法
總結
以上是生活随笔為你收集整理的动态分区式内存管理（完整代码）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： HDU1863
- 下一篇： 抖音表情包小程序，抖音广告流量主玩法