設計目的

所謂動態分區分配，就是指內存在初始時不會劃分區域，而是會在進程裝入時，根據所要裝入的進程大小動態地對內存空間進行劃分，以提高內存空間利用率，降低碎片的大小 動態分區分配算法有以下四種：

• 首次適應算法（First Fit）
  空閑分區以地址遞增的次序鏈接。分配內存時順序查找，找到大小滿足要求的第一個空閑分區就進行分配
• 鄰近適應算法（Next Fit）
  又稱循環首次適應法，由首次適應法演變而成，不同之處是分配內存時從上一次查找結束的位置開始繼續查找
• 最佳適應算法（Best Fit）
  空閑分區按容量遞增形成分區鏈，找到第一個能滿足要求的空閑分區就進行分配
• 最壞適應算法（Next Fit）
  又稱最大適應算法（Largest Fit），空閑分區以容量遞減的次序鏈接，找到第一個能滿足要求的空閑分區（也就是最大的分區）就進行分配

設計內容及要求

• 用C語言實現采用首次適應算法的動態分區分配過程alloc()和回收過程free()。其中，空閑分區通過空閑分區鏈表來管理，在進行內存分配時，系統優先使用空閑區低端的空間
• 假設初始狀態如下，可用的內存空間為640KB，并有下列的請求序列；采用首次適應算法進行內存塊的分配和回收，同時顯示內存塊分配和回收后空閑內存分區鏈的情況
• 假設初始狀態如下，可用的內存空間為640KB，并有下列的請求序列；
  作業1申請130KB
  作業2申請60KB
  作業3申請100KB
  作業2釋放60KB
  作業4申請200 KB
  作業3釋放100 KB
  作業1釋放130 KB
  作業5申請140 KB
  作業6申請60 KB
  作業7申請50KB
  作業6釋放60 KB
  請采用循環首次適應算法進行內存塊的分配和回收，同時顯示內存塊分配和回收后空閑內存分區鏈的情況。

設計準備

首次適應算法：

• 算法思想：
  將空閑分區鏈以地址遞增的順序連接；在進行內存分配時，從鏈首開始順序查找，直到找到一塊分區的大小可以滿足需求時，按照該作業的大小，從該分區中分配出內存，將剩下的空閑分區仍然鏈在空閑分區鏈中
• 優點：高址部分的大的空閑分區得到保留，為大作業的內存分配創造了條件
• 缺點：（1）每次都是優先利用低址部分的空閑分區，造成低址部分產生大量的外碎片。（2）每次都是從低址部分查找，使得查找空閑分區的開銷增大

內存回收：

將釋放作業所在內存塊的狀態改為空閑狀態，刪除其作業名，設置為空。并判斷該空閑塊是否與其他空閑塊相連，若釋放的內存空間與空閑塊相連時，則合并為同一個空閑塊，同時修改分區大小及起始地址

設計過程

我們以空閑分區鏈為例來說明采用FF算法時的分配情況，FF算法要求空閑分區鏈以地址遞增的次序鏈接

• 在分配內存時，從鏈首開始順序查找，直至找到一個大小能滿足要求的空閑分區為止
• 然后再按照作業的大小，從該分區中劃出一塊內存空間分配給請求者，余下的空閑分區仍留在空閑鏈中
• 若從鏈首直至鏈尾都不能找到一個能滿足要求的分區，則此次內存分配失敗，返回

了解動態分區分配中使用的數據結構和分配算法，并進一步加深對動態分區存儲管理方式及其實現過程的理解。采用首次適應算法的動態分區分配過程alloc()和回收過程free()。空閑分區通過空閑分區鏈表來管理，在進行內存分配時，系統優先使用空閑區低端的空間，即每次分配內存空間是總是從低址部分開始進行循環，找到第一個合適的空間，便按作業所需分配的大小分配給作業。 作業完成時，需要釋放作業所占空間，此時要考慮到四種情況：

• 回收區與插入點的前一個空閑分區相鄰接。此時將二者合并，修改前一分區的大小。
• 回收區與插入點的后一空閑分區相鄰接，將二者合并，用回收區的首址作為新空閑區的首址。
• 回收區同時與插入點的前后兩個空閑分區相鄰接，三者合并，使用前一空閑分區的表項和首址。
• 回收區單獨存在。

設計結果并分析

菜單

作業1申請130KB

作業2申請60KB

作業3申請100KB

作業2釋放60KB

作業4申請200KB

作業3釋放100KB

作業1釋放100KB

作業5申請140KB

作業6申請60KB

作業7申請50KB

作業6釋放60KB

原理框圖

模塊設計

• void initNode(struct nodespace *p)
  創建一個雙鏈表存儲信息

• void myMalloc1(int teskid,int size,struct nodespace *node)
  申請空間函數

• void myFree(int teskid,struct nodespace *node)
  釋放空間函數

• void printNode(struct nodespace *node)
  打印輸出節點存儲信息了，即內存申請剩余情況

• void destory(struct nodespace *node)
  退出程序并銷毀清空節點

• void menu()
  主菜單，提示用戶進行相應的操作

C語言源程序——建議使用Devc ++ 運行

#include<stdio.h> #include<stdlib.h> struct nodespace{int teskid; // 作業號 int begin; // 開始地址 int size; // 大小 int status; // 狀態 0代表占用，1代表空閑 struct nodespace *next; // 后指針 }; void initNode(struct nodespace *p){if(p == NULL){ //如果為空則新創建一個 p = (struct nodespace*)malloc(sizeof(struct nodespace));}p->teskid = -1;p->begin = 0;p->size = 640;p->status = 1;p->next =NULL; } void myMalloc1(int teskid,int size,struct nodespace *node){while(node != NULL){if(node->status == 1){ //空閑的空間 if(node->size > size){ //當需求小于剩余空間充足的情況 //分配后剩余的空間 struct nodespace *p = (struct nodespace*)malloc(sizeof(struct nodespace));p->begin = node->begin + size;p->size = node->size - size;p->status = 1;p->teskid = -1;//分配的空間 node->teskid = teskid; node->size = size;node->status = 0;//改變節點的連接 p->next = node->next; node->next = p;printf("==================================分配內存成功！==================================\n");break; }else if(node->size == size){ //需求空間和空閑空間大小相等時 node->teskid = teskid; node->size = size;node->status = 0;printf("==================================分配內存成功！==================================\n");break;} }if(node->next == NULL){printf("===============================分配失敗，沒有足夠的空間！=============================\n");break;}node = node->next;} } void myFree(int teskid,struct nodespace *node){if(node->next == NULL && node->teskid == -1){printf("================================您還沒有分配任何作業！================================\n");}while(node != NULL){if(node->status == 1 && node->next->status ==0 && node->next->teskid == teskid){struct nodespace *q = node->next;node->next = node->next->next;free(q);printf("==================================釋放內存成功！==================================\n");if(node->next->status == 1){ //下一個空間是空閑空間時 node->size = node->size + node->next->size;struct nodespace *q = node->next;node->next = node->next->next;free(q);printf("==================================釋放內存成功！==================================\n");}break;}else if(node->status == 0 && node->teskid == teskid){ //釋放空間和空閑空間不連續時 node->status = 1;node->teskid = -1;if(node->next != NULL && node->next->status == 1){ //下一個空間是空閑空間時 node->size = node->size + node->next->size;struct nodespace *q = node->next;node->next = node->next->next;free(q);}printf("==================================釋放內存成功！==================================\n");break;}else if(node->next == NULL){ //作業號不匹配時 printf("==================================沒有此作業！！==================================\n");break;}node = node->next;}} void printNode(struct nodespace *node){printf(" 內存情況 \n"); printf(" -------------------------------------------------------\n");printf("| 起始地址\t結束地址\t大小\t狀態\t作業號\t|\n");while(node != NULL){if(node->status==1){printf("| %d\t\t%d\t\t%dKB\tfree\t 無\t|\n", node->begin + 1, node->begin+node->size, node->size);}else{printf("| %d\t\t%d\t\t%dKB\tbusy\t %d\t|\n", node->begin + 1, node->begin+node->size, node->size, node->teskid);}node = node->next;}printf(" -------------------------------------------------------\n"); } void destory(struct nodespace *node){struct nodespace *q = node;while(node != NULL){node = node->next;free(q);q = node;} } void menu(){printf("\n"); printf("\t\t\t\t ╭═════════════════════════════════○●○●═══╮\n");printf("\t\t\t\t │ 首次適應算法的動態分區分配方式模擬 │\n");printf("\t\t\t\t ╰═══○●○●═════════════════════════════════╯\n");printf("\t\t\t\t ┌───────────────────────────────────────────-┐\n");printf("\t\t\t\t │ │\n");printf("\t\t\t\t │ 1. 申請內存 │\n");printf("\t\t\t\t │ │\n");printf("\t\t\t\t │ 2. 回收內存 │\n");printf("\t\t\t\t │ │\n");printf("\t\t\t\t │ 3. 查看內存情況 │\n");printf("\t\t\t\t │ │\n");printf("\t\t\t\t │ 4. 退出 │\n");printf("\t\t\t\t │ │\n");printf("\t\t\t\t └────────────────────────────────────────────┘\n");printf("\t\t\t\t\t\t 請您選擇(1-4):\t"); }int main(){// node為整個空間 system("color 0f");//system("mode con cols=120 lines=50");struct nodespace *init = (struct nodespace*)malloc(sizeof(struct nodespace));struct nodespace *node = NULL;initNode(init); //初始化主鏈 node = init; //指向鏈表頭 int option; int teskid;int size;while(1){menu(); //打印想要進行的操作scanf("%d",&option);if(option == 1){printf("請輸入作業號；");scanf("%d",&teskid);printf("此作業申請的空間大小(KB):");scanf("%d",&size);myMalloc1(teskid,size,node);printf("\n"); printNode(node);}else if(option == 2){printf("請輸入作業號:");scanf("%d",&teskid);myFree(teskid,node);printf("\n"); printNode(node);}else if(option == 3){printNode(node);}else if(option == 4){destory(node);initNode(init);node = init;break;}else{printf("===========================您的輸入有誤，請重新輸入！============================\n");continue;}} return 0; }

總結

以上是生活随笔為你收集整理的首次适应算法 动态分区分配方式的模拟 C语言——课程设计实习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。