實驗二——動態(tài)高優(yōu)先權(quán)優(yōu)先調(diào)度算法-王子瑜

1、操作系統(tǒng)課程實驗報告實驗名稱：動態(tài)分區(qū)存儲管理姓 名：王子瑜學(xué)號： 541413450235地點： 四教樓指導(dǎo)老師：放美專業(yè)班級： 軟件工程（測試技術(shù) 14-02）實驗成績：、實驗要求：熟悉并掌握動態(tài)分區(qū)分配的各種算法。 熟悉并掌握動態(tài)分區(qū)中分區(qū)回收的各種情況，并能夠?qū)崿F(xiàn)分區(qū)合并。、實驗容 ：用高級語言模擬實現(xiàn)動態(tài)分區(qū)存儲管理，要求：1、分區(qū)分配算法至少實現(xiàn)首次適應(yīng)算法、 最佳適應(yīng)算法和最壞適應(yīng)算法中的至 少一種。熟悉并掌握各種算法的空閑區(qū)組織方式。2、分區(qū)的初始化可以由用戶輸入初始分區(qū)的大小。（初始化后只有一個空閑分區(qū)，起始地址為 0，大小是用戶輸入的大?。?、分區(qū)的動態(tài)分配過程：由用戶輸入

2、作業(yè)號和作業(yè)的大小，實現(xiàn)分區(qū)過程。4、分區(qū)的回收：用戶輸入作業(yè)號，實現(xiàn)分區(qū)回收，同時，分區(qū)的合并要體現(xiàn)出 來。（注意：不存在的作業(yè)號要給出錯誤提示！ ）5、分區(qū)的顯示：任何時刻，可以查看當(dāng)前存的情況（起始地址是什么，大小多 大的分區(qū)時空閑的，或者占用的，能夠顯示出來）要求考慮：（ 1）存空間不足的情況，要有相應(yīng)的顯示；（ 2）作業(yè)不能同名，但是刪除后可以再用這個名字；（ 3）作業(yè)空間回收是輸入作業(yè)名， 回收相應(yīng)的空間，如果這個作業(yè)名不存在，也 要有相應(yīng)的提示。三、實驗代碼#include<stdio.h>#include<stdlib.h>#define SIZE 64

3、0/ 存初始大小#define MINSIZE 5/ 碎片最小值enum STATE Free, Busy ;struct subAreaNode int addr;int size;/ 起始地址/ 分區(qū)大小subAreaNode *pre;subAreaNode *nxt;subHead;/ 分區(qū)前向指針/ 分區(qū)后向指針/ 初始化空閑分區(qū)鏈void intSubArea()/ 分配初始分區(qū)存subAreaNode *fir = (subAreaNode *)malloc(sizeof(subAreaNode);/ 給首個分區(qū)賦值fir->addr = 0;fir->size =

4、SIZE;fir->state = Free;fir->taskId = -1;fir->pre= &subHead;fir->nxt= NULL;/ 初始化分區(qū)頭部信息subHead.pre = NULL;subHead.nxt = fir;/ 首次適應(yīng)算法int firstFit(int taskId, int size)subAreaNode *p = subHead.nxt;while(p != NULL)if(p->state = Free && p->size >= size) / 找到要分配的空閑分區(qū)if(p-&g

5、t;size - size <= MINSIZE) / 整塊分配p->state = Busy;p->taskId = taskId; else / 分配大小為 size 的區(qū)間subAreaNode *node = (subAreaNode *)malloc(sizeof(subAreaNode);node->addr = p->addr + size;node->size = p->size - size;node->state = Free;node->taskId = -1;node->pre = p;node->nxt

6、 = p->nxt;if(p->nxt != NULL) p->nxt->pre = node;p->nxt = node;/ 分配空閑區(qū)間p->size = size;p->state = Busy;p->taskId = taskId;printf(" 存分配成功！ n");return 1;p = p->nxt;printf(" 找不到合適的存分區(qū)，分配失敗 .n");return 0;int bestFit(int taskId, int size)subAreaNode *tar = NUL

7、L;int tarSize = SIZE + 1;subAreaNode *p = subHead.nxt;while(p != NULL)/ 尋找最佳空閑區(qū)間if(p->state = Free && p->size >= size && p->size < tarSize) tar = p;tarSize = p->size;p = p->nxt;if(tar != NULL) / 找到要分配的空閑分區(qū)if(tar->size - size <= MINSIZE) / 整塊分配tar->state

8、= Busy;tar->taskId = taskId; else subAreaNode *node = (subAreaNode *)malloc(sizeof(subAreaNode);node->addr= tar->addr + size;node->size =tar->size - size;node->state= Free;node->taskId = -1;/ 修改分區(qū)鏈節(jié)點指針node->pre =tar;node->nxt =tar->nxt;if(tar->nxt !=NULL) tar->nxt

9、->pre = node;tar->nxt = node;/ 分配空閑區(qū)間tar->size = size;tar->state = Busy;tar->taskId = taskId;printf(" 存分配成功！ n");return 1; else / 找不到合適的空閑分區(qū).n");printf(" 找不到合適的存分區(qū)，分配失敗return 0;/ 回收存int freeSubArea(int taskId)int flag = 0;subAreaNode *p = subHead.nxt, *pp;while(p !

10、= NULL)if(p->state = Busy && p->taskId = taskId) flag = 1;if(p->pre != &subHead && p->pre->state = Free)&& (p->nxt != NULL && p->nxt->state = Free) / 情況 1：合并上下兩個分區(qū)/ 先合并上區(qū)間pp = p;p = p->pre;p->size += pp->size;p->nxt = pp->nxt

11、;pp->nxt->pre = p;free(pp);pp = p->nxt;p->size += pp->size;p->nxt = pp->nxt;if(pp->nxt != NULL) pp->nxt->pre = p;free(pp); else if(p->pre = &subHead | p->pre->state = Busy)&& (p->nxt != NULL && p->nxt->state = Free) / 情況 2：只合并下面的分區(qū)p

12、p = p->nxt;p->size += pp->size;p->state = Free;p->taskId = -1;p->nxt = pp->nxt;if(pp->nxt != NULL) pp->nxt->pre = p;free(pp); else if(p->pre != &subHead && p->pre->state = Free)&& (p->nxt = NULL | p->nxt->state = Busy) pp = p;p = p-

13、>pre;p->size += pp->size;p->nxt = pp->nxt;if(pp->nxt != NULL) pp->nxt->pre = p;free(pp); else / 情況 4：上下分區(qū)均不用合并p->state = Free;p->taskId = -1;p = p->nxt;if(flag = 1) / 回收成功printf(" 存分區(qū)回收成功 .n");return 1; else return 0;/ 顯示空閑分區(qū)鏈情況void showSubArea（）printf(&quo

14、t;*n");printf("*當(dāng)前的存分配情況如下：*n");printf("*n");printf（"* 起始地址 | 空間大小 | 工作狀態(tài) | 作業(yè)號 *n"）;subAreaNode *p = subHead.nxt;while(p != NULL)printf("*n");printf("*");printf("%d k |", p->addr);printf("%d k |", p->size);printf("

15、; %s |", p->state = Free ? "Free" : "Busy");if(p->taskId > 0) else printf(" ");printf("*n");p = p->nxt;*n");printf(" int main()int option, ope, taskId, size;/ 初始化空閑分區(qū)鏈intSubArea();/ 選擇分配算法while(1)printf(" 請選擇要模擬的分配算法：0 表示首次適應(yīng)算法，

16、 1 表示最佳適應(yīng)算法 n");scanf("%d", &option);if(option = 0) break; else if(option = 1) printf(" 你選擇了最佳適應(yīng)算法，下面進行算法的模擬break; else printf(" 錯誤：請輸入 0/1nn");n");/ 模擬動態(tài)分區(qū)分配算法while(1)printf("n");printf(*n");printf("* 1: 分配存 2: 回收存 0: 退出 *n");printf(*n

17、");scanf("%d", &ope);if(ope = 0) break;if(ope = 1) / 模擬分配存printf(" 請輸入作業(yè)號： ");scanf("%d", &taskId);scanf("%d", &size);if(size <= 0) n");printf(" 錯誤：分配存大小必須為正值continue;/ 調(diào)用分配算法if(option = 0) firstFit(taskId, size); else bestFit(tas

18、kId, size);/ 顯示空閑分區(qū)鏈情況showSubArea(); else if(ope = 2) / 模擬回收存printf(" 請輸入要回收的作業(yè)號： ");scanf("%d", &taskId);freeSubArea(taskId);/ 顯示空閑分區(qū)鏈情況showSubArea(); else printf（" 分配算法模擬結(jié)束 n"）;return 0;運行結(jié)果：當(dāng)前的內(nèi)存分配情況如下，-起始地址:空間大小：工作狀態(tài)：作業(yè)號*«-*0k !50k !Busyi i150k !70k 1Busy!3120k !100k !Bus yii2* »* *220300kMBk! 80!105k ! k !BusyBusy1 OHB MMMM11