操作系統(tǒng)課程設(shè)計(jì)--模擬實(shí)現(xiàn)可變分區(qū)存儲(chǔ)管理

1、<p><b>　　電氣信息系</b></p><p>　　操作系統(tǒng) 課程設(shè)計(jì)報(bào)告</p><p>　　模擬實(shí)現(xiàn)可變分區(qū)存儲(chǔ)管理</p><p><b>　　一、設(shè)計(jì)目的</b></p><p>　　在熟練掌握計(jì)算機(jī)分區(qū)存儲(chǔ)管理方式的原理的基礎(chǔ)上，利用C程序設(shè)計(jì)語(yǔ)言在windows操作系統(tǒng)

2、下模擬實(shí)現(xiàn)操作系統(tǒng)的可變分區(qū)存儲(chǔ)管理的功能，一方面加深對(duì)原理的理解，另一方面提高根據(jù)已有原理通過(guò)編程解決實(shí)際問(wèn)題的能力，為進(jìn)行系統(tǒng)軟件開(kāi)發(fā)和針對(duì)實(shí)際問(wèn)題提出高效的軟件解決方案打下基礎(chǔ)。</p><p>　　二、各功能模塊分析實(shí)現(xiàn)</p><p>　　設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)來(lái)描述存儲(chǔ)空間：</p><p>　　對(duì)于未分配出去的部分，用空閑分區(qū)鏈表來(lái)描述。</p>

3、;<p>　　struct freeList </p><p><b>　　{</b></p><p>　　int startAddress; /* 分區(qū)起始地址 */</p><p>　　int size; /* 分區(qū)大小 */</p>

4、<p>　　struct freeList *next; /* 分區(qū)鏈表指針 */</p><p><b>　　}</b></p><p>　　對(duì)于已經(jīng)分配出去的部分，由裝入內(nèi)存的作業(yè)占據(jù)。</p><p>　　struct usedList </p><p><b&g

5、t;　　{</b></p><p>　　int startAddress; /* 分區(qū)起始地址 */</p><p>　　int jobID; /* 分區(qū)中存放作業(yè)ID */</p><p>　　struct usedList *next; /* 分區(qū)鏈表指針 */</p><p

6、><b>　　}</b></p><p><b>　　將作業(yè)組織成鏈表。</b></p><p>　　struct jobList</p><p><b>　　{</b></p><p>　　int id; /* 作業(yè)ID */<

7、/p><p>　　int size; /* 作業(yè)大?。ㄐ枰拇鎯?chǔ)空間大?。?*/</p><p>　　int status; /* 作業(yè)狀態(tài) 0 : new job ,1 : in the memory , 2 : finished . */</p><p>　　struct jobList *next; /* 作業(yè)鏈表指針

8、*/</p><p><b>　　}</b></p><p>　　以上將存儲(chǔ)空間分為空閑可占用兩部分，在usedlist中設(shè)jobID而不設(shè)size，可以在不增加空間復(fù)雜度（與freelist相比）的同時(shí)更方便的實(shí)現(xiàn)可變分區(qū)存儲(chǔ)管理（從后面的一些函數(shù)的實(shí)現(xiàn)上可以得出這個(gè)結(jié)論）。</p><p>　　盡管設(shè)置joblist增加了空間復(fù)雜度，但它的

9、存在，使得該程序可以方便的直接利用C盤(pán)中的Job.txt文件。該文件可以認(rèn)為是一個(gè)和其他進(jìn)程共享的資源。通過(guò)這個(gè)文件，其他進(jìn)程寫(xiě)入數(shù)據(jù)供讀取。這中思想在操作系統(tǒng)設(shè)計(jì)中體現(xiàn)的很多。</p><p>　　實(shí)現(xiàn)分區(qū)存儲(chǔ)管理的內(nèi)存分配功能，選擇適應(yīng)算法（首次適應(yīng)算法，最佳適 應(yīng)算法，最后適應(yīng)算法，最壞適應(yīng)算法）。</p><p><b>　　基本原理分析： </b>

10、;</p><p>　　1） Best fit ：將空閑分區(qū)按大小從小到大排序，從頭找到大小合適的分區(qū)。</p><p>　　2） Worst fit：將空閑分區(qū)按大小從大到小排序，從頭找到大小合適的分區(qū)。</p><p>　　3） First fit ：將空閑分區(qū)按起始地址大小從小到大排序，……</p><p>　　4） Last fit

11、：將空閑分區(qū)按起始地址大小從大到小排序，……</p><p>　　由此，可將空閑分區(qū)先做合適的排序后用對(duì)應(yīng)的適應(yīng)算法給作業(yè)分配存儲(chǔ)空間。排序函數(shù) order（bySize為零則按分區(qū)大小排序，否則按分區(qū)起始地址；inc為零從小到大排序，否則從大到小排序；通過(guò)empty指針?lè)祷亟Y(jié)果）。</p><p>　　void order(struct freeList **empty,int bySi

12、ze,int inc)</p><p><b>　　{</b></p><p>　　struct freeList *p,*q,*temp;</p><p>　　int startAddress,size;</p><p>　　for(p = (*empty) -> next;p;p = p -> next)

13、</p><p>　　{ /* 按bySize和inc兩個(gè)參數(shù)尋找合適的節(jié)點(diǎn)，用temp指向它 */</p><p>　　for(temp = q = p;q;q = q -> next)</p><p><b>　　{</b></p><p>　　switch(bySize)</p><

14、p><b>　　{</b></p><p>　　case 0 : switch(inc)</p><p><b>　　{</b></p><p>　　case 0:if(q->size < temp->size)</p><p>　　temp = q;break;</p

15、><p>　　default:if(q->size > temp->size)</p><p>　　temp = q;break;</p><p><b>　　} break;</b></p><p>　　default: switch(inc)</p><p><b>

16、　　{</b></p><p>　　case 0:if(q->startAddress < temp->startAddress)</p><p>　　temp = q;break;</p><p>　　default:if(q->startAddress > temp->startAddress)</p>

17、<p>　　temp = q;break;</p><p><b>　　} break;</b></p><p><b>　　}</b></p><p>　　} /* 交換節(jié)點(diǎn)的成員值 */ </p><p>　　if(

18、temp != p)</p><p><b>　　{ </b></p><p>　　startAddress = p->startAddress;</p><p>　　size = p->size;</p><p>　　p->startAddress = temp->startAddress;&

19、lt;/p><p>　　p->size = temp->size;</p><p>　　temp->startAddress = startAddress;</p><p>　　temp->size = size;</p><p><b>　　}</b></p><p><

20、;b>　　}</b></p><p><b>　　}</b></p><p>　　實(shí)現(xiàn)分區(qū)存儲(chǔ)管理的內(nèi)存回收算法：</p><p>　　void insertFreeNode(struct freeList **empty,int startAddress,int size)</p><p>　　插入回

21、收的空節(jié)點(diǎn)分區(qū)，處理回收分區(qū)與空閑分區(qū)的四種鄰接關(guān)系。</p><p><b>　　{</b></p><p>　　struct freeList *p,*q,*r;</p><p>　　for(p = *empty;p -> next;p = p -> next) ; /* 處理鏈表尾部的鄰接情況 */</p>

22、<p>　　if(p == *empty || p -> startAddress + p -> size < startAddress)/* 與尾部不相鄰*/</p><p><b>　　{</b></p><p>　　makeFreeNode(&r,startAddress,size); /* 通過(guò)r指針?lè)祷貏?chuàng)建的空閑節(jié)點(diǎn)*

23、/</p><p>　　r -> next = p -> next; /* 插入獨(dú)立的空閑節(jié)點(diǎn) */</p><p>　　p -> next = r;</p><p><b>　　return ;</b></p><p><b>　　}</b&g

24、t;</p><p>　　if(p -> startAddress + p -> size == startAddress) /* 與尾部上鄰 */</p><p><b>　　{</b></p><p>　　p -> size += size; /* 合

25、并尾部節(jié)點(diǎn) */</p><p><b>　　return ;</b></p><p><b>　　}</b></p><p>　　q = (*empty) -> next; /* 處理鏈表首節(jié)點(diǎn)的鄰接情況 */</p><p>　　if(startAddr

26、ess + size == q -> startAddress) /* 與首節(jié)點(diǎn)下鄰 */</p><p><b>　　{</b></p><p>　　q -> startAddress = startAddress; /* 合并首節(jié)點(diǎn) */</p><p>　　q -&

27、gt; size += size;</p><p><b>　　}</b></p><p>　　else if(startAddress + size < q -> startAddress) /* 與首節(jié)點(diǎn)不相鄰 */</p><p><b>　　{</b></p><p&

28、gt;　　makeFreeNode(&r,startAddress,size);</p><p>　　r -> next = (*empty) -> next;</p><p>　　(*empty) -> next = r;</p><p><b>　　}</b></p><p><b&g

29、t;　　else </b></p><p>　　{ /* 處理鏈表中間的鄰接情況 */</p><p>　　while(q -> next && q -> startAddress < startAddress)</p><p><b>　

30、　{</b></p><p><b>　　p = q;</b></p><p>　　q = q -> next;</p><p><b>　　}</b></p><p>　　if(p -> startAddress + p -> size == startAddress

31、 &&\</p><p>　　q -> startAddress == startAddress + size) /* 上下鄰，合并節(jié)點(diǎn) */</p><p><b>　　{</b></p><p>　　p -> size += size + q -> size;</p><p&g

32、t;　　p -> next = q -> next;</p><p>　　free(q); /* 刪除多余節(jié)點(diǎn) */</p><p><b>　　}</b></p><p>　　else if(p -> startAddress + p -> size

33、== startAddress &&\</p><p>　　q -> startAddress != startAddress + size) /*上鄰，增加節(jié)點(diǎn)的大小*/</p><p><b>　　{</b></p><p>　　p -> size += size;</p><p><

34、;b>　　}</b></p><p>　　else if(p -> startAddress + p -> size != startAddress &&\</p><p>　　q -> startAddress == startAddress + size) /* 下鄰 */</p><p&g

35、t;<b>　　{</b></p><p>　　q -> startAddress = startAddress; /* 修改節(jié)點(diǎn)起始地址 */</p><p>　　q -> size += size; /* 修改節(jié)點(diǎn)的大小 */</p><p><b>　　}<

36、/b></p><p><b>　　else</b></p><p>　　{ /* 上下不相鄰 */</p><p>　　makeFreeNode(&r,startAddress,size);</p><p>　　r

37、-> next = p -> next;</p><p>　　p -> next = r;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　當(dāng)碎

38、片產(chǎn)生時(shí)，進(jìn)行碎片的拼接。</p><p>　　void moveFragment(struct jobList *jobs,struct freeList **empty,struct usedList **used)</p><p><b>　　{</b></p><p>　　int size,status;</p><

39、p>　　struct usedList *p;</p><p>　　int address = memoryStartAddress; /*全局變量，初始化時(shí)分配存儲(chǔ)空間始址*/</p><p>　　if((*empty)->next == NULL) /* 空閑分區(qū)鏈表為空，提示并返回 */</p><p><b>　　{<

40、/b></p><p>　　printf("\nThe memory was used out at all.\nMay be you should finish some jobs first or press any key to try again !");</p><p><b>　　getch();</b></p>&

41、lt;p><b>　　return;</b></p><p><b>　　}</b></p><p>　　for(p = (*used) -> next;p;p = p-> next) /* 循環(huán)的修改占用分區(qū)的始址 */</p><p><b>　　{</b></p&

42、gt;<p>　　p -> startAddress = address;</p><p>　　getJobInfo(jobs,p -> jobID,&size,&status); /* 由作業(yè)ID獲得作業(yè)大小 */</p><p>　　address += size;</p><p><b>　　}</b&

43、gt;</p><p>　　(*empty)->next->startAddress = address;/*修改空閑分區(qū)的首節(jié)點(diǎn)始址、大小*/</p><p>　　(*empty) -> next -> size = memorySize - (address - memoryStartAddress);</p><p>　　(*empty

44、) -> next -> next = NULL; /* 刪除首節(jié)點(diǎn)后的所有節(jié)點(diǎn) */</p><p><b>　　}</b></p><p>　　空閑分區(qū)隊(duì)列顯示：int showFreeList(struct freeList *empty)</p><p>　　作業(yè)占用鏈表顯示：int showUsedLis

45、t(struct jobList *jobs,struct usedList *used) </p><p>　　從頭到尾顯示used鏈，同時(shí)通過(guò)其中的作業(yè)ID在jobs中查對(duì)應(yīng)的大小。</p><p>　　從鍵盤(pán)輸入作業(yè)到D盤(pán)的JOB文件：void inputJob(void)</p><p>　　從JOB文件中讀出作業(yè)并創(chuàng)建作業(yè)鏈表：int makeJobLis

46、t(struct jobList **jobs)</p><p>　　顯示作業(yè)鏈表：int showJobList(struct jobList *jobs) </p><p>　　10.更新作業(yè)鏈表中作業(yè)的狀態(tài)： int updateJobFile(struct jobList *jobs)</p><p>　　11.根據(jù)作業(yè)鏈表更新JOB文件： int upda

47、teJobFile(struct jobList *jobs) </p><p>　　12.為作業(yè)分配存儲(chǔ)空間、狀態(tài)必須為0：int allocate(struct freeList **empty,int size) </p><p>　　13.結(jié)束一個(gè)作業(yè)號(hào)為id的作業(yè)，釋放存儲(chǔ)空間（由*startAddress返回空間的起始地址）：int finishJob(

48、struct usedList **used,int id,int *startAddress)</p><p>　　14.插入釋放的空間到used鏈表中（作業(yè)號(hào)為id，startAddress由函數(shù)13返回）：</p><p>　　void insertUsedNode(struct usedList **used,int id,int startAddress)</p>

49、<p>　　15.獲取作業(yè)的信息： void getJobInfo(struct jobList *jobs,int id,int *size,int *status)</p><p>　　16.初始化存儲(chǔ)空間起始地址、大?。簐oid iniMemory(void)</p><p>　　17.選擇適應(yīng)算法：char selectFitMethod(void)</p>

50、<p>　　18.根據(jù)參數(shù)startAddress、size創(chuàng)建空閑節(jié)點(diǎn)，由empty指針?lè)祷兀?lt;/p><p>　　void makeFreeNode(struct freeList **empty,int startAddress,int size)</p><p>　　19.以要求的方式打開(kāi)文件：void openFile(FILE **fp,char *filename

51、,char *mode)</p><p>　　20.出現(xiàn)嚴(yán)重錯(cuò)誤時(shí)顯示信息并結(jié)束程序；void errorMessage(void)</p><p>　　三、總體界面與程序流程分析</p><p>　　Dynamic Zonal Memory Management</p><p>　　其中1、Initializiation.按順序利用了ope

52、nFile()、iniMemory()、makeFreeNode()、inputJob()（選擇利用C盤(pán)JOB文件時(shí)提供作業(yè)信息）、makeJobList()、allocate()、insertUsedNode()（選擇利用C盤(pán)JOB文件時(shí)先將狀態(tài)為1的作業(yè)放到存儲(chǔ)空間中，以恢復(fù)上次的模擬實(shí)驗(yàn)，或使本次模擬時(shí)不出錯(cuò)）selectFitMethod()等自編函數(shù)。</p><p>　　2、Put job into

53、memory(allocate memory)</p><p>　　按順序利用了showJobList()（選手動(dòng)逐個(gè)為作業(yè)分配存儲(chǔ)空間時(shí)）、openFile()、order()、allocate()、errorMessage()、insertUsedNode()、updateJobStatus()updateJobFile()函數(shù)</p><p>　　（自動(dòng)為如上作業(yè)分配存儲(chǔ)后狀態(tài)的變化

54、——>） </p><p>　　3、Finish job(reuse memory)</p><p>　　按順序利用了openFile()、showUsedList()、getJobInfo()、insert FreeNode()、updateJobStatus()、updateJobFile()、errorMessage()等自編函數(shù)。 </p>

55、<p>　　（完成部分作業(yè)后作業(yè)——>）</p><p>　　4、Show current free list 按順序利用了openFile()、showFreeList()函數(shù)。 （如下圖為當(dāng)前空閑分區(qū)）</p><p>　　5、Show current memory used by jobs按順序利用

56、了openFile()、showUsedList()函數(shù)。 （如下圖為當(dāng)前作業(yè)占用的分區(qū)）</p><p>　　6、Move fragment together按順序利用了openFile()、moveFragment()函數(shù)。</p><p><b>　　整理 </b></p><p>　　7、Exit按順序利用了ope

57、nFile()、exit(0)函數(shù)。</p><p><b>　　四、主程序流程圖</b></p><p><b>　　step=’1’</b></p><p>　　step=’2’ </p><p><b>　　step=’6’</b></p>&l

58、t;p>　　step=’3’step=’4’ </p><p>　　step=’5’ </p><p><b>　　step=’7’</b></p><p><b>　　五、結(jié)果分析與總結(jié)</b></p><p>　　程序中創(chuàng)建的兩個(gè)文件</p><p>　　1）B

59、est fit算法驗(yàn)證： </p><p>　　如下圖分配大小為50的8號(hào)作業(yè)，恰好占用大小為50的空閑而非大小為240的。</p><p>　　2）Worst fit算法驗(yàn)證：</p><p>　　如下圖分配大小為50的8號(hào)作業(yè)，占用大小為100空閑而非大小為70的。</p><p>　　3）First fit算法驗(yàn)證：</p>

60、<p>　　如下圖分配大小為50的8號(hào)作業(yè)，占用起始地址為110空閑而非350的。</p><p>　　4）Last fit算法驗(yàn)證：</p><p>　　如下圖分配大小為50的8號(hào)作業(yè)，占用起始地址為350空閑而非110的。</p><p>　　總結(jié)：通過(guò)這次課程設(shè)計(jì)我練習(xí)了用C語(yǔ)言寫(xiě)系統(tǒng)軟件，對(duì)OS中可變分區(qū)存儲(chǔ)管理有了更深刻的了解。在寫(xiě)程序的時(shí)候

61、也遇到了一些困難。比如在設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)時(shí)特別猶豫，總想找一個(gè)很合適的。但是，后來(lái)才知道，關(guān)鍵要多嘗試，而空想是沒(méi)有用的。最后我證實(shí)了自己的設(shè)計(jì)的合理性。還有為了使程序更健壯，我嘗試著將程序中的輸入部分全部改為字符（串）。成功的避免了接受整型數(shù)據(jù)時(shí)輸入字符后引起的錯(cuò)誤，使程序能接受</p><p>　　任何輸入而正常結(jié)束。很遺憾的是因?yàn)闀r(shí)間問(wèn)題，沒(méi)有把這個(gè)模擬程序?qū)懗蓜?dòng)畫(huà)形式，還可以加幾句代碼后實(shí)現(xiàn)動(dòng)態(tài)的增加作業(yè)。&