1、 計算機科學 專業(yè)課程設計任務書學生姓名專業(yè)班級學號題 目動態(tài)分區(qū)分配方式的模擬1課題性質其它課題來源自擬課題指導教師馬宏琳同組姓名無主要內(nèi)容1）用C語言實現(xiàn)采用首次適應算法的動態(tài)分區(qū)分配過程alloc()和回收過程free()。其中，空閑分區(qū)通過空閑分區(qū)鏈表來管理，在進行內(nèi)存分配時，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。2）假設初始狀態(tài)如下，可用的內(nèi)存空間為640KB，并有下列的請求序列；作業(yè)1申請130KB；作業(yè)2申請60KB；作業(yè)3申請100KB；作業(yè)2釋放60KB；作業(yè)4申請200 KB；作業(yè)3釋放100 KB；作業(yè)1釋放130 KB；作業(yè)5申請140 KB；作業(yè)6申請60 KB；作業(yè)7申請5

2、0KB；作業(yè)6釋放60 KB請采用首次適應算法進行內(nèi)存塊的分配和回收，同時顯示內(nèi)存塊分配和回收后空閑內(nèi)存分區(qū)鏈的情況。任務要求 了解動態(tài)分區(qū)分配中使用的數(shù)據(jù)結構和分配算法，并進一步加深對動態(tài)分區(qū)存儲管理方式及其實現(xiàn)過程的理解。參考文獻任滿杰等操作系統(tǒng)原理實用教程 電子工業(yè)出版社 2006湯子瀛 計算機操作系統(tǒng)（修訂版）西安電子科技大學出版社 2001張堯學 史美林計算機操作系統(tǒng)教程實驗指導 清華大學出版社 2000 羅宇等 操作系統(tǒng)課程設計機械工業(yè)出版社 2005審查意見指導教師簽字：教研室主任簽字： 年 月 日 1 需求分析了解動態(tài)分區(qū)分配中使用的數(shù)據(jù)結構和分配算法，并進一步加深對動態(tài)分區(qū)存

3、儲管理方式及其實現(xiàn)過程的理解。采用首次適應算法的動態(tài)分區(qū)分配過程alloc()和回收過程free()。空閑分區(qū)通過空閑分區(qū)鏈表來管理，在進行內(nèi)存分配時，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間，即每次分配內(nèi)存空間是總是從低址部分開始進行循環(huán)，找到第一個合適的空間，便按作業(yè)所需分配的大小分配給作業(yè)。作業(yè)完成時，需要釋放作業(yè)所占空間，此時要考慮到四種情況：(1)回收區(qū)與插入點的前一個空閑分區(qū)相鄰接。此時將二者合并，修改前一分區(qū)的大小。(2)回收區(qū)與插入點的后一空閑分區(qū)相鄰接，將二者合并，用回收區(qū)的首址作為新空閑區(qū)的首址。(3)回收區(qū)同時與插入點的前后兩個空閑分區(qū)相鄰接，三者合并，使用前一空閑分區(qū)的表項和首址。

4、(4)回收區(qū)單獨存在。由于該算法的實現(xiàn)相對簡單，僅由我一人完成。2 概要設計typedef struct freeareaElemType;定義一個空閑區(qū)說明表結構，每申請一個作業(yè)，改作業(yè)便具有此結構體typedef struct DuLNodeDuLNode,*DuLinkList;定義一個雙向鏈表Status Initblock()開創(chuàng)帶頭結點的內(nèi)存空間鏈表,通過雙向鏈表把申請的作業(yè)鏈接起來，作業(yè)的插入和刪除，和鏈表中節(jié)點的插入和刪除類似。雙向鏈表如圖1所示Status First_fit(int ID,int request)傳入作業(yè)名及申請量采用首次適應算法實現(xiàn)動態(tài)內(nèi)存分區(qū)分配的模擬，

5、初始態(tài)640KB，只是一個虛態(tài)，每申請成功一個作業(yè)，便相應的640KB做相應的減少，同過雙向鏈表模擬主存的分配情況。內(nèi)存分配流程如圖2所示Status free(int ID)傳過來需要回收的分區(qū)號實現(xiàn)分區(qū)的回收，對不同情況采取不同的處理void show()顯示當前主存的分配情況3 運行環(huán)境硬件環(huán)境：Cpu:P2.4GH DRR: 0.98GB WINDOWS XP。軟件環(huán)境：在VC+6.0下編譯、調(diào)試。4 開發(fā)工具和編程語言開發(fā)工具: Microsort visual c+6.0中文版編程語言: c+5 詳細設計1)空閑區(qū)數(shù)據(jù)結構typedef struct freearea/定義一個空閑

6、區(qū)說明表結構int ID;long size;long address;int state;ElemType;2）雙向鏈表數(shù)據(jù)結構typedef struct DuLNode /雙向鏈表結構體 ElemType data; struct DuLNode *prior; /前趨指針 struct DuLNode *next; /后繼指針DuLNode,*DuLinkList;3）創(chuàng)建內(nèi)存空間鏈表Status Initblock()/開創(chuàng)帶頭結點的內(nèi)存空間鏈表block_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)

7、malloc(sizeof(DuLNode); block_first-prior=NULL; block_first-next=block_last; block_last-prior=block_first; block_last-next=NULL; block_last-data.address=0; block_last-data.size=MAX_length; block_last-data.ID=0; block_last-data.state=Free; return OK;4）分配主存Status alloc()int ID,request;coutID; coutrequ

8、est; if(request0 |request=0)cout分配大小不合適，請重試！endl;return ERROR;if(First_fit(ID,request)=OK)調(diào)用函數(shù)First_fit(ID,request)才是真正實現(xiàn)首次適應算法cout分配成功！endl;elsecout內(nèi)存不足，分配失??！data.ID=ID; temp-data.size=request; temp-data.state=Busy; DuLNode *p=block_first-next;while(p)if(p-data.state=Free & p-data.size=request)/有大小

9、恰好合適的空閑塊p-data.state=Busy;p-data.ID=ID;return OK;break;if(p-data.state=Free & p-data.sizerequest)/有空閑塊能滿足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;p-prior-next=temp; p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size-=request;return OK;break;p=p-next

10、;return ERROR;5）主存回收Status free(int ID)DuLNode *p=block_first;while(p)if(p-data.ID=ID)p-data.state=Free;p-data.ID=Free;if(p-prior-data.state=Free)/與前面的空閑塊相連p-prior-data.size+=p-data.size; p-prior-next=p-next; p-next-prior=p-prior;if(p-next-data.state=Free)/與后面的空閑塊相連p-data.size+=p-next-data.size;if(p

11、-next-next=NULL)p-next=null;elsep-next-next-prior=p;p-next=p-next-next;break;p=p-next;cout”分區(qū)號：”ID“回收成功”endl;return OK;6）顯示主存分配情況void show()cout+n;cout+ 主存分配情況 +n;coutnext;while(p)coutdata.ID=Free)coutFreeendl;elsecoutdata.IDendl;cout起始地址：data.address;cout 分區(qū)大?。篸ata.size KB;coutdata.state=Free)cout空

12、 閑endl;elsecout已分配next;7）主 函 數(shù)void main()Initblock();int choice;int i;for(i=0;i+) cout+n;cout+動態(tài)分區(qū)分配方式的模擬一+n;cout+首次適應算法+n;cout +n;cout + 1: 分配內(nèi)存 2: 回收內(nèi)存 +n;cout + 3: 查看分配 0: 退 出 +n;cout +n;coutchoice;if(choice=1)/ 分配內(nèi)存alloc();else if(choice=2)/ 內(nèi)存回收 int ID; coutID; free(ID);else if(choice=3)/顯示主存sh

13、ow();else if(choice=0)/退出break;else /輸入操作有誤cout輸入有誤，請重試！next-next=NULL)p-next=null;else滿足了要求，得到了正確結果，還有就是程序允許回收內(nèi)存中不存在的作業(yè)，如圖4所示這是不符合要求的，因為才程序中少了對用戶輸入作業(yè)號的判斷不符合情況的處理。7 測試結果作業(yè)1 申請30KB作業(yè)5 申請70KB作業(yè)2 申請600KB作業(yè)2 申請-80KB作業(yè)2申請30KB作業(yè)2 回收30KB作業(yè)3 申請78KB測試分區(qū)分配如圖5所示測試分區(qū)分配如圖6所示測試分區(qū)分配如圖7所示測試分區(qū)回收如圖8所示測試主存當前分配情況如圖9所示程

14、序運行結果如圖10所示參考文獻1任滿杰等操作系統(tǒng)原理實用教程 電子工業(yè)出版社 20062湯子瀛 計算機操作系統(tǒng)（修訂版）西安電子科技大學出版社 20013張堯學 史美林計算機操作系統(tǒng)教程實驗指導 清華大學出版社 2000 4羅宇等 操作系統(tǒng)課程設計機械工業(yè)出版社 20055曾平，曾林 操作系統(tǒng)清華大學出版社 2006心得體會由于已經(jīng)學過動態(tài)分區(qū)分配，我也了解了什么是首次適應算法，以及首次適應算法的實現(xiàn)過程，剛開始以為會很順利的做完此次課程設計，但往往會出現(xiàn)眼高手低的情況，先是因為很久都沒用過C+來編寫代碼了，以致剛開始時，出現(xiàn)了很多小問題，真是把頭都搞大了，如具體的格式，以及鏈表的具體使用等等

15、出現(xiàn)問題，還得拿出原來的課本學習查看，費了點時間，不過讓我再次回味了曾經(jīng)的C+編程，加深了原來的記憶。經(jīng)過網(wǎng)上搜材料以及整體平時的學習材料，后來程序的大體框架算是出來了，不過在不斷調(diào)試過程中我發(fā)現(xiàn)了很多不完善的地方，比如在回收內(nèi)存方面，少了一種情況的處理，以致每次要回收最后一個作業(yè)時都會出現(xiàn)錯誤的框子；還有就是若要刪除內(nèi)存中不存在的作業(yè)，程序卻允許執(zhí)行，這個問題難為了我好久，改完后又接著出現(xiàn)新的問題，成了內(nèi)存中存在的作業(yè)在刪除時也提示用戶重新輸入，原因在于判斷條件加的地方不合適。通過本次課程設計我學到了很多東西，也增加了我不斷摸索和學習的興趣，由原來的書本知識演化成了真的動手實踐，獲益匪淺。實

16、驗代碼/*動態(tài)分區(qū)分配方式的模擬一首次適應算法 *#include#include#define Free 0 /空閑狀態(tài)#define Busy 1 /已用狀態(tài)#define OK 1 /完成#define ERROR 0 /出錯#define MAX_length 640 /最大內(nèi)存空間為640KBtypedef int Status;typedef struct freearea/定義一個空閑區(qū)說明表結構int ID;long size;long address;int state;ElemType;typedef struct DuLNode /double linked list E

17、lemType data; struct DuLNode *prior; /前趨指針 struct DuLNode *next; /后繼指針DuLNode,*DuLinkList;DuLinkList block_first; /頭結點DuLinkList block_last; /尾結點Status alloc();/內(nèi)存分配Status free(int); /內(nèi)存回收Status First_fit(int,int);/首次適應算法void show();/查看分配Status Initblock();/開創(chuàng)空間表Status Initblock()/開創(chuàng)帶頭結點的內(nèi)存空間鏈表block

18、_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(DuLNode); block_first-prior=NULL; block_first-next=block_last; block_last-prior=block_first; block_last-next=NULL; block_last-data.address=0; block_last-data.size=MAX_length; block_last-data.ID=0; block_last-data.state=Fr

19、ee; return OK;/- 分 配 主 存 -Status alloc()int ID,request;coutID; coutrequest; if(request0 |request=0)cout分配大小不合適，請重試！endl;return ERROR;if(First_fit(ID,request)=OK)cout分配成功！endl;elsecout內(nèi)存不足，分配失??！data.ID=ID; temp-data.size=request; temp-data.state=Busy; DuLNode *p=block_first-next;while(p)if(p-data.sta

20、te=Free & p-data.size=request)/有大小恰好合適的空閑塊p-data.state=Busy;p-data.ID=ID;return OK;break;if(p-data.state=Free & p-data.sizerequest)/有空閑塊能滿足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;p-prior-next=temp; p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size

21、-=request;return OK;break;p=p-next;return ERROR;/- 主 存 回 收 -Status free(int ID)DuLNode *p=block_first;while(p)if(p-data.ID=ID)p-data.state=Free;p-data.ID=Free;if(p-prior-data.state=Free)/與前面的空閑塊相連p-prior-data.size+=p-data.size; p-prior-next=p-next; p-next-prior=p-prior;if(p-next-data.state=Free)/與后面的空閑塊相連p-data.