【操作系統(tǒng)】分區(qū)分配算法 （首次適應(yīng)算法、最佳適應(yīng)算法）（C語言實(shí)現(xiàn)）

（編碼水平較菜，寫博客也只是為了個人知識的總結(jié)和督促自己學(xué)習(xí)，如果有錯誤，希望可以指出）

今天測試，發(fā)現(xiàn)一點(diǎn)問題：
1.最佳插入算法：對于插入的時候忘記修改temp.next.front的指向
2.回收頭節(jié)點(diǎn)的時候現(xiàn)在多了一種判斷。判斷頭節(jié)點(diǎn)的下一個是否為空。對如果不為空而且后面的空閑的話，做出了處理。原來則沒有這一情況。

3.首次適應(yīng)算法在 第一個分區(qū)未分配，第二個分區(qū)已分配時沒有改變 temp_next->front 的指向，所以導(dǎo)致了后續(xù)的一些小問題，已經(jīng)修改。

1.動態(tài)分區(qū)分配算法：

為了實(shí)現(xiàn)動態(tài)分區(qū)分配，通常將系統(tǒng)中的空閑分區(qū)鏈接成一個鏈。所謂順序查找是指依次搜索空閑分區(qū)鏈上的空閑分區(qū)，去尋找一個大小能滿足要求的分區(qū)。 --------計算機(jī)操作系統(tǒng)（第四版）

2.動態(tài)分區(qū)算法主要包括四種：

（1）.首次適應(yīng)算法（first fit，FF）：

要求，空閑分區(qū)鏈以地址遞增的順序鏈接。每次從鏈?zhǔn)组_始，直到找到第一個能滿足要求的空閑分區(qū)為止。
簡單來說，就是，每次都從第一個開始順序查找，找到一塊區(qū)域可以滿足要求的。

優(yōu)點(diǎn)：優(yōu)先利用內(nèi)存中低址部分的空閑分區(qū)，從而保留了高址部分的大空閑區(qū)，這為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。

缺點(diǎn)：低址部分不斷被劃分，會留下許多難以利用的，很小的空閑分區(qū)，稱為碎片。而每次查找又都是從低址部分開始的，這無疑又會增加查找可用空閑分區(qū)時的開銷。

（2）.循環(huán)首次適應(yīng)算法（next fit，NF）：

與FF算法區(qū)別就是，不是每次都從首次開始，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始。（第一次查找的話也是從首頁開始）。

特點(diǎn)：能使內(nèi)存中的空閑區(qū)分布得較均勻。

(3）.最佳適應(yīng)算法（best，BF）：

將所有空閑分區(qū)按照空閑分區(qū)容量大小從小到大的順序連接起來，形成一個空閑分區(qū)鏈。
即，每次都是找空間容量不但可以滿足要求的空閑區(qū)，而且該空閑分區(qū)的容量還要最接近要求的容量大小。

優(yōu)點(diǎn)：每次分配給文件的都是最合適該文件大小的分區(qū)。

缺點(diǎn)：內(nèi)存中留下許多難以利用的小的空閑區(qū)（外碎片）。

(4).最壞適應(yīng)算法（worst，WF）：

與BF算法相反，WF算法是按照空閑分區(qū)容量從大到小的順序連接起來的，而且每次找空閑分區(qū)的時候也是按照空閑分區(qū)容量最大的。

特點(diǎn)：盡可能的分配大的分區(qū)。

缺點(diǎn)：使得內(nèi)存缺乏大分區(qū)，可能使得后續(xù)到來的大作業(yè)無法裝入內(nèi)存。

3.主要實(shí)現(xiàn)的是首次適應(yīng)算法和最佳適應(yīng)算法。

運(yùn)行截圖：

4.就不一一截圖了，還沒有發(fā)現(xiàn)什么問題。如果有人發(fā)現(xiàn)了，希望可以指正一下，不勝感激

5.代碼

#include<stdio.h> #include<stdlib.h>typedef struct lei_item //表示空閑分區(qū)表中的表箱 {int id; //假如 id 為-1，表示此分區(qū)時一個空閑分區(qū)。int base; //指向分區(qū)的首地址int size; //表示分區(qū)大小int status; //表示此分區(qū)是否已經(jīng)分配 0表示空閑 1表示已經(jīng)分配 }Item; typedef Item datatype;typedef struct lei_list {datatype* node; //表示一個datatype類型的鏈表的結(jié)點(diǎn)struct lei_list* front;struct lei_list* next; }List;#define Max 640 int memory = Max; //定義可用內(nèi)存空間為640List init(){ //初始化一個鏈表;List list;list.node = (datatype *)malloc(sizeof(datatype));list.node->base = 0;list.node->id = -1; //-1表示是空閑分區(qū)list.node->size = memory;list.node->status = 0; list.front = list.next = NULL;return list; }datatype* input(){ //初始化打算申請的內(nèi)存分區(qū)節(jié)點(diǎn)datatype* item = (datatype *)malloc(sizeof(datatype));printf("請輸入作業(yè)號：");scanf("%d",&item->id);printf("請輸入所需要的內(nèi)存的大小：");scanf("%d",&item->size);item->status = 0;return item; } void Momery_state(List *list){List* temp = list;printf("-----------------------------------\n");printf("內(nèi)存分配狀況\n");printf("-----------------------------------\n");while (temp){if(temp->node->status == 0 && temp->node->id == -1){printf("分區(qū)號：FREE\n");printf("起始地址：%d\n",temp->node->base);printf("內(nèi)存大小：%d\n",temp->node->size);printf("分區(qū)狀態(tài)：空閑\n");}else{printf("分區(qū)號：%d\t起始地址：%d\n",temp->node->id,temp->node->base);printf("內(nèi)存大小：%d\n",temp->node->size);printf("分區(qū)狀態(tài)：已分配\n");}printf("-----------------------------------\n");temp = temp->next;}}int First_fit(List *list){datatype* item = input();List* temp = list; //定義一個臨時變量list* ，指向listwhile (temp){if(temp->node->status == 0 && temp->node->size > item->size){ //如果此前的分區(qū)未分配，，并且分區(qū)大小大于 請求分配的大小 那么此時就可以進(jìn)行分配List *front = temp->front; //存儲當(dāng)前未分配分區(qū)的 上一個分區(qū)地址List *next = temp->next; //存儲當(dāng)前未分配分區(qū)的 下一個分區(qū)地址 int base = temp->node->base; //記錄未分配當(dāng)前分區(qū)的首地址datatype* new_node = (datatype*)malloc(sizeof(datatype)); // 多余出來的部分要新建立一個分區(qū)new_node->id = -1; //然后需要對這個新的分區(qū)進(jìn)行一些信息的設(shè)置new_node->size = temp->node->size - item->size; //新分區(qū)的大小 等于 還未分配的時的分區(qū)大小 - 請求分配的結(jié)點(diǎn)的大小 temp->node = item; //對請求分配的分區(qū)結(jié)點(diǎn)進(jìn)行分配temp->node->status = 1;new_node->status = 0;new_node->base = base + temp->node->size; //新建立分區(qū)的首地址是 請求分配的分區(qū)的首地址 + 請求分配的分區(qū)的大小List* temp_next = (List*)malloc(sizeof(List)); //臨時節(jié)點(diǎn) （申請一個新的鏈表節(jié)點(diǎn) 表示下一個分區(qū)） 并且進(jìn)行初始化temp_next->node = new_node; //保存下一個的分區(qū)的信息temp_next->front = temp_next->next = NULL; if(front == NULL && next == NULL){ //如果 front和next節(jié)點(diǎn)都是空，表明它是第一次分配分區(qū)temp->node->base = 0; //初始化首地址temp->next = temp_next; temp_next->front = temp;}if(front == NULL && next != NULL){ //在第一個分區(qū)中插入新的分區(qū)temp->node->base = 0;temp->node->status = 1;temp_next->front = temp;temp_next->next = temp->next;temp->next = temp_next;}if(front != NULL){ //表明不是第一次分配節(jié)點(diǎn)，此時需要在中間插入下一個節(jié)點(diǎn)temp->node->base = temp->front->node->base+temp->front->node->size; //初始化首地址temp_next->next = temp->next; //保證新插入的節(jié)點(diǎn)會記錄原先節(jié)點(diǎn)的下一個節(jié)點(diǎn)的首地址temp_next->front = temp; // 首尾都需要保證temp->next = temp_next; //最后讓所申請的分區(qū)節(jié)點(diǎn)的下一個節(jié)點(diǎn)指向 我們剛剛建立的臨時節(jié)點(diǎn)}return 1;} else if(temp->node->status == 0 && temp->node->size == item->size){item->base = temp->front->node->base+temp->front->node->size; //新插入分區(qū)的首地址 等于上一個分區(qū)的 首地址+分區(qū)的大小item->status = 1; //表示已經(jīng)分配temp->node = item;return 1;}else{temp = temp->next;continue;}temp = temp->next;}return 0; }int Momory_recycle(List *list){List* temp = list; //申請一個鏈表節(jié)點(diǎn) 指向list 的頭節(jié)點(diǎn)int number; //用于存放要釋放的節(jié)點(diǎn)的分區(qū)號printf("請輸入需要回收的ID號：");scanf("%d",&number);while (temp){ if(temp->node->id == number) //首先找到 節(jié)點(diǎn)id = number 的節(jié)點(diǎn)，然后分四種情況討論 { // 一、 要回收的是第一個結(jié)點(diǎn)if(temp->front == NULL){temp->node->status = 0;temp->node->id = -1;if(temp->next == NULL){temp->node->size = temp->node->size + temp->next->node->size;temp->next = temp->next;return 1;}if(temp->next->node->id == -1 && temp->next->node->status == 0){List* next = temp->next;// 此時來判斷 temp->next 是否是系統(tǒng)的最后一個結(jié)點(diǎn)// 此時只將當(dāng)前節(jié)點(diǎn) 和下一個結(jié)點(diǎn)合并就可以了//即 首地址不變， 分區(qū)狀態(tài) 和 分區(qū)id進(jìn)行變化 temp->node->size = temp->node->size + next->node->size;temp->node->status = 0;temp->node->id = -1;temp->next = next->next;if(next->next == NULL){free(next);return 1;}//如果不是最后一個結(jié)點(diǎn)的話就會多一個步驟// 讓 next->next->front 指向上一個結(jié)點(diǎn)else{next->next->front = temp;free(next); return 1;} }return 1;}//二、 前后都沒有空閑的分區(qū)//最簡單， 直接改變 分區(qū)的 id 和 分區(qū)的狀態(tài)就可以了。// 如果回收第一個分區(qū)的話 必須要先進(jìn)行處理，如果不先進(jìn)行處理 ，判斷 temp->front->node->id != -1 會報一個段錯誤。因為temp-》front 此時指向的是null if(temp->front->node->id != -1 && temp->front->node->status != 0 && temp->next->node->id != -1 && temp->next->node->status != 0){temp->node->status = 0;temp->node->id = -1;return 1;}//三、要回收的節(jié)點(diǎn) 前面和后面都是空閑的// 將三個空閑區(qū)合并到一起，起始地址為前面的分區(qū)的起始地址， 大小為三個空閑區(qū)大小之和//還需要做一個判斷，如果if(temp->front->node->id == -1 && temp->front->node->status == 0 && temp->next->node->id == -1 && temp->next->node->status == 0){List* front = temp->front;List* next = temp->next;front->node->size = front->node->size + temp->node->size + next->node->size; front->next = next->next;if(next->next == NULL){free(temp);return 1;}//如果不是最后一個結(jié)點(diǎn)的話就會多一個步驟// 讓 next->next->front 指向上一個結(jié)點(diǎn)else{next->next->front = front;free(temp); return 1;} return 1;}// 四、 要回收的節(jié)點(diǎn) 前面的節(jié)點(diǎn)是空閑的//合并后的分區(qū)起始地址為前一個結(jié)點(diǎn)， 分區(qū)大小為前一個節(jié)點(diǎn) 與 當(dāng)前節(jié)點(diǎn)之和。if(temp->front->node->id == -1 && temp->front->node->status == 0){List* front = temp->front;front->next = temp->next;temp->next->front = front;front->node->size += temp->node->size;free(temp);return 1;}//五、 要回收的節(jié)點(diǎn) 后面的額節(jié)點(diǎn)是空閑的//合并后的分區(qū)首地址為當(dāng)前節(jié)點(diǎn) ， 分區(qū)大小為當(dāng)前節(jié)點(diǎn) 與 當(dāng)前節(jié)點(diǎn)的下一個結(jié)點(diǎn)大小之和。// 這個需要多一個步驟， 改變分區(qū)的 id 和 分區(qū)的狀態(tài)。// 還要注意一點(diǎn)： 當(dāng)要回收的空間是和 系統(tǒng)最后的空閑區(qū)相鄰時 ， temp->next->next 指向的是null；if(temp->next->node->id == -1 && temp->next->node->status == 0){List* next = temp->next;// 此時來判斷 temp->next 是否是系統(tǒng)的最后一個結(jié)點(diǎn)// 此時只將當(dāng)前節(jié)點(diǎn) 和下一個結(jié)點(diǎn)合并就可以了//即 首地址不變， 分區(qū)狀態(tài) 和 分區(qū)id進(jìn)行變化 temp->node->size = temp->node->size + next->node->size;temp->node->status = 0;temp->node->id = -1;temp->next = next->next;if(next->next == NULL){free(next);return 1;}//如果不是最后一個結(jié)點(diǎn)的話就會多一個步驟// 讓 next->next->front 指向上一個結(jié)點(diǎn)else{next->next->front = temp;free(next); return 1;} }}temp = temp->next;}return 0;}int Best_fit(List *list){int min = 0; //記錄 最小分區(qū)的結(jié)點(diǎn)的大小int base_min = 0; //記錄 最小節(jié)點(diǎn)的結(jié)點(diǎn)的起始地址List* temp = list; datatype* item = input(); // 要對 item 的 起始地址 和 分配狀態(tài)進(jìn)行初始化while (temp){//如果分區(qū)未分配 就要進(jìn)行 比較操作， 并且記錄差值 和 分區(qū)的id號if(temp->node->status == 0 && temp->node->id == -1&& temp->node->size > item->size){if(min == 0){ //加入min為0 表示還未找到一個可以分配的分區(qū)min = temp->node->size;base_min = temp->node->base;}else{if(temp->node->size < min){ // 找到一個之后，需要找出最小的分區(qū) 也就是它的 size最小。min = temp->node->size;base_min = temp->node->base;}}}if(temp->node->status == 0 && temp->node->id == -1 && temp->node->size == item->size){int base = temp->node->base;temp->node = item;temp->node->status = 1;temp->node->base = base;return 1;}temp = temp->next;}//因為可能沒有任何一個空間可以滿足要求需要做一個判斷處理 temp = list;while (temp){if(temp->node->base == base_min){datatype* temp_node = (datatype*)malloc(sizeof(datatype)); //會有多余的空間多出來 所以需要在建立一個結(jié)點(diǎn)插入到鏈表中temp_node->id = -1;temp_node->status = 0;temp_node->base = base_min + item->size;temp_node->size = temp->node->size - item->size;temp->node = item; //對item進(jìn)行完整的初始化temp->node->base = base_min;temp->node->status = 1;List* temp_list_node = (List*)malloc(sizeof(List)); //新申請一個 鏈表的結(jié)點(diǎn) 并且初始化temp_list_node->node = temp_node;temp_list_node->front = temp;temp_list_node->next = temp->next;if(temp->next != NULL){temp->next->front = temp_list_node;}temp->next = temp_list_node;return 1;}temp = temp->next;}}int main(){printf("分區(qū)模擬\n");List list = init();int select;int insert_state,recycle_state;int insert_state_best;do{printf("請輸入要進(jìn)行的操作\n");printf("1-首次適應(yīng)算法， 2-最佳適應(yīng)算法， 3-內(nèi)存回收， 4-顯示內(nèi)存狀況， 5-退出\n");scanf("%d",&select);switch (select){case 1: // 1. 首次適應(yīng)算法insert_state = First_fit(&list);if(insert_state == 0){printf("分配失敗\n");}else {printf("分配成功！\n");} break;case 2: // 2. 最佳適應(yīng)算法insert_state_best = Best_fit(&list);if(insert_state_best == 1){printf("分配成功\n");} else {printf("分配失敗\n");} break;case 3: //3.內(nèi)存回收recycle_state = Momory_recycle(&list);if(recycle_state == 1){printf("回收成功！\n");}else{printf("回收失敗\n");}break;case 4: //4.顯示內(nèi)存狀況Momery_state(&list);break; }} while (select != 5);system("pause"); }

總結(jié)

以上是生活随笔為你收集整理的【操作系统】分区分配算法（首次适应算法、最佳适应算法）C语言的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。