實(shí)驗(yàn)二——動(dòng)態(tài)高優(yōu)先權(quán)優(yōu)先調(diào)度算法

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

2、程。分區(qū)的回收：用戶輸入作業(yè)號(hào)，實(shí)現(xiàn)分區(qū)回收，同時(shí)，分區(qū)的合并要表達(dá)出來。注意：不存在的作業(yè)號(hào)要給出錯(cuò)誤提示！分區(qū)的顯示：任何時(shí)刻，可以查看當(dāng)前存的情況起始地址是什么，大小多大的分區(qū)時(shí)空閑的，或者占用的，能夠顯示出來要求考慮：1存空間缺乏的情況，要有相應(yīng)的顯示；2作業(yè)不能同名，但是刪除后可以再用這個(gè)名字；3作業(yè)空間回收是輸入作業(yè)名，回收相應(yīng)的空間，如果這個(gè)作業(yè)名不存在，也要有相應(yīng)的提示。三、實(shí)驗(yàn)代碼#include#include#define SIZE 640 / 存初始大小#define MINSIZE 5 / 碎片最小值enum STATE Free, Busy ;struct subA

3、reaNode int addr; / 起始地址 int size; / 分區(qū)大小 int taskId; / 作業(yè)號(hào) STATE state; / 分區(qū)狀態(tài) subAreaNode *pre; / 分區(qū)前向指針 subAreaNode *n*t; / 分區(qū)后向指針subHead;/ 初始化空閑分區(qū)鏈void intSubArea() / 分配初始分區(qū)存 subAreaNode *fir = (subAreaNode *)malloc(sizeof(subAreaNode); / 給首個(gè)分區(qū)賦值 fir-addr = 0; fir-size = SIZE; fir-state = Free;

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

5、大小為size的區(qū)間 subAreaNode *node = (subAreaNode *)malloc(sizeof(subAreaNode); node-addr = p-addr + size; node-size = p-size - size; node-state = Free; node-taskId = -1; / 修改分區(qū)鏈節(jié)點(diǎn)指針 node-pre = p; node-n*t = p-n*t; if(p-n*t != NULL) p-n*t-pre = node; p-n*t = node; / 分配空閑區(qū)間 p-size = size; p-state = Busy; p

6、-taskId = taskId; printf(存分配成功！n); return 1; p = p-n*t; printf(找不到適宜的存分區(qū)，分配失敗.n); return 0;/ 最正確適應(yīng)算法int bestFit(int taskId, int size) subAreaNode *tar = NULL; int tarSize = SIZE + 1; subAreaNode *p = subHead.n*t; while(p != NULL) / 尋找最正確空閑區(qū)間 if(p-state = Free & p-size = size & p-size size; p = p-n*t

7、; if(tar != NULL) / 找到要分配的空閑分區(qū) if(tar-size - size state = Busy; tar-taskId = taskId; else / 分配大小為size的區(qū)間 subAreaNode *node = (subAreaNode *)malloc(sizeof(subAreaNode); node-addr = tar-addr + size; node-size = tar-size - size; node-state = Free; node-taskId = -1; / 修改分區(qū)鏈節(jié)點(diǎn)指針 node-pre = tar; node-n*t

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

9、(p != NULL) if(p-state = Busy & p-taskId = taskId) flag = 1; if(p-pre != &subHead & p-pre-state = Free) & (p-n*t != NULL & p-n*t-state = Free) / 情況1：合并上下兩個(gè)分區(qū) / 先合并上區(qū)間 pp = p; p = p-pre; p-size += pp-size; p-n*t = pp-n*t; pp-n*t-pre = p; free(pp); / 后合并下區(qū)間 pp = p-n*t; p-size += pp-size; p-n*t = pp-n*

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

11、p-pre-state = Free) & (p-n*t = NULL | p-n*t-state = Busy) / 情況3：只合并上面的分區(qū) pp = p; p = p-pre; p-size += pp-size; p-n*t = pp-n*t; if(pp-n*t != NULL) pp-n*t-pre = p; free(pp); else / 情況4：上下分區(qū)均不用合并 p-state = Free; p-taskId = -1; p = p-n*t; if(flag = 1) / 回收成功 printf(存分區(qū)回收成功.n); return 1; else / 找不到目標(biāo)作業(yè)，回

12、收失敗 printf(找不到目標(biāo)作業(yè)，存分區(qū)回收失敗.n); return 0; / 顯示空閑分區(qū)鏈情況void showSubArea() printf(*n); printf(* 當(dāng)前的存分配情況如下： *n); printf(*n); printf(* 起始地址 | 空間大小 | 工作狀態(tài) | 作業(yè)號(hào) *n); subAreaNode *p = subHead.n*t; while(p != NULL) printf(*-*n); printf(*); printf(%d k |, p-addr); printf(%d k |, p-size); printf( %s |, p-stat

13、e = Free Free : Busy); if(p-taskId 0) printf(%d , p-taskId); else printf( ); printf(*n); p = p-n*t; printf(*n);int main() int option, ope, taskId, size; / 初始化空閑分區(qū)鏈 intSubArea(); / 選擇分配算法 while(1) printf(請(qǐng)選擇要模擬的分配算法： 0 表示首次適應(yīng)算法，1 表示最正確適應(yīng)算法n); scanf(%d, &option); if(option = 0) printf(你選擇了首次適應(yīng)算法，下面進(jìn)展算

14、法的模擬n); break; else if(option = 1) printf(你選擇了最正確適應(yīng)算法，下面進(jìn)展算法的模擬n); break; else printf(錯(cuò)誤：請(qǐng)輸入 0/1nn); / 模擬動(dòng)態(tài)分區(qū)分配算法 while(1) printf(n); printf(*n); printf(* 1: 分配存 2: 回收存 0: 退出 *n); printf(*n); scanf(%d, &ope); if(ope = 0) break; if(ope = 1) / 模擬分配存 printf(請(qǐng)輸入作業(yè)號(hào)： ); scanf(%d, &taskId); printf(請(qǐng)輸入需要分配

15、的存大小(KB)： ); scanf(%d, &size); if(size = 0) printf(錯(cuò)誤：分配存大小必須為正值n); continue; / 調(diào)用分配算法 if(option = 0) firstFit(taskId, size); else bestFit(taskId, size); / 顯示空閑分區(qū)鏈情況 showSubArea(); else if(ope = 2) / 模擬回收存 printf(請(qǐng)輸入要回收的作業(yè)號(hào)： ); scanf(%d, &taskId); freeSubArea(taskId); / 顯示空閑分區(qū)鏈情況 showSubArea(); else printf(錯(cuò)誤：請(qǐng)輸入 0/1/2n); printf(分配算