C課程設計論文存儲管理分區(qū)分配算法

1、遼 寧 工 業(yè) 大 學 C語言程序設計 課程設計論文題目： 存儲管理分區(qū)分配算法 院系： 專業(yè)班級： 學 號： 學生姓名： 指導教師： 教師職稱： 起止時間： 課程設計報告任務及評語院系：軟件學院 教研室：軟件教研窒學 號學生姓名專業(yè)班級程序設計報告題目存儲管理分區(qū)分配算法程序設計報告任務程序設計的任務與要求：1掌握C語言編程的根底知識。2較熟練地編寫C語言應用程序。3了解C語言的常用標準函數(shù)、編程技巧、異常處理。5聯(lián)系已學過的內(nèi)容，穩(wěn)固所學的理論，增強獨立工作能力。6通過設計主要使學生有一個獨立編寫程序的過程，對理論學習及動手能力都有一個很大的提高。7通過本次設計，進一步培養(yǎng)學生熱愛專業(yè)的思

2、想，同時對本專業(yè)綜合素質(zhì)的提高起一個積極的推動作用。課程設計過程中，要嚴格遵守實踐環(huán)節(jié)的時間安排，聽從指導教師的指導。正確地完成上述內(nèi)容，記錄實習日記，標準完整地撰寫出課程設計報告。指導教師評語及成績成績： 指導教師簽字： 2009 年 1 月 11 日目 錄第1章 課程設計的目的與要求11.1 課程設計目的11.2 課程設計的實驗環(huán)境11.3 課程設計的預備知識11.4 課程設計要求1第2章 課程設計內(nèi)容2程序功能介紹2程序整體設計說明2設計思路2數(shù)據(jù)結(jié)構(gòu)設計及用法說明3程序結(jié)構(gòu)流程圖9各模塊的功能及程序說明12程序結(jié)果13程序源代碼及注釋13第3章 課程設計總結(jié)23參考資料24第1章 課程

3、設計的目的與要求1.1 課程設計目的本課程設計是計算機科學與技術(shù)專業(yè)重要的實踐性環(huán)節(jié)之一，是在學生學習完?程序設計語言(C)?課程后進行的一次全面的綜合練習。本課程設計的目的和任務： 1. 穩(wěn)固和加深學生對C語言課程的根本知識的理解和掌握 2. 掌握C語言編程和程序調(diào)試的根本技能 3. 利用C語言進行根本的軟件設計4. 掌握書寫程序設計說明文檔的能力5. 提高運用C語言解決實際問題的能力 課程設計的實驗環(huán)境硬件要求能運行Windows 2000/XP操作系統(tǒng)的微機系統(tǒng)。C語言程序設計及相應的開發(fā)環(huán)境。 課程設計的預備知識熟悉C語言及C語言開發(fā)工具。 課程設計要求1. 分析課程設計題目的要求2.

4、 寫出詳細設計說明3. 編寫程序代碼，調(diào)試程序使其能正確運行4. 設計完成的軟件要便于操作和使用5. 設計完成后提交課程設計報告第2章 課程設計內(nèi)容程序功能介紹內(nèi)存區(qū)域的分配和管理：通過建表、查表、改表和回收登錄內(nèi)存使用情況，系統(tǒng)或用戶申請內(nèi)存時按選定的分配算法確定分區(qū)等，保證分配和回收。存儲管理分區(qū)分配的主要任務是管理存儲器資源，為多道程序運行提供有力的支撐。存儲管理的主要功能包括：1存儲分配。存儲管理將根據(jù)用戶程序的需要給它分配存儲器資源。2存儲擴充。由于物理內(nèi)存容量有限，難于滿足用戶程序的需求，存儲管理還應該能從邏輯上來擴充內(nèi)存儲器，為用戶提供一個比內(nèi)存實際容量大得多的編程空間，方便用戶

5、的編程和使用。首次適應算法，這種分配算法具有隨機性，它介于最正確適應算法和最差適應算法之間，通常適用于系統(tǒng)事先不掌握運行期間可能出現(xiàn)的請求分配和釋放回收的信息的情況。最正確適應算法將可利用空間表中一個大小不小于“請求且最接近“請求的空閑塊的一局局部配給用戶。分配與回收都需要對可利用空間表從頭至尾查詢一遍。為了防止每次分配都要查詢整個鏈表，通常要求節(jié)點從大到小排序，由此只需找到第一個足夠大的空閑塊即可予以分配。但回收時，必須把回收的空閑塊放置在符合大小順序關(guān)系的鏈表位置。在分配時容易產(chǎn)生太小而無法利用的內(nèi)存碎片，同時這種做法也保存了那些很大的內(nèi)存塊以備響應將來發(fā)生的內(nèi)存量較大的用戶“請求，從而使

6、整個鏈表逐漸趨向于節(jié)點大小差異甚遠的狀態(tài)。程序整體設計說明2.2.1設計思路在對數(shù)據(jù)結(jié)構(gòu)有一定掌握程度的情況下設計合理的數(shù)據(jù)結(jié)構(gòu)來描述存儲空間，實現(xiàn)分區(qū)存儲管理的內(nèi)存分配功能，應該選擇最適宜的適應算法首次適應算法，最正確適應算法，最后適應算法，最壞適應算法，實現(xiàn)分區(qū)存儲管理的內(nèi)存回收算法，在這些存儲管理中間必然會有碎片的產(chǎn)生，當碎片產(chǎn)生時，進行碎片的拼接，等等相關(guān)的內(nèi)容。2.2.2數(shù)據(jù)結(jié)構(gòu)設計及用法說明 1設計合理的數(shù)據(jù)結(jié)構(gòu)來描述存儲空間：1對于未分配出去的局部，用空閑分區(qū)鏈表來描述。struct freeList int startAddress; /* 分區(qū)起始地址 */int size;

7、 /* 分區(qū)大小 */struct freeList *next; /* 分區(qū)鏈表指針 */ 2對于已經(jīng)分配出去的局部，由裝入內(nèi)存的作業(yè)占據(jù)。struct usedList int startAddress; /* 分區(qū)起始地址 */int jobID; /* 分區(qū)中存放作業(yè)ID */struct usedList *next; /* 分區(qū)鏈表指針 */3將作業(yè)組織成鏈表。struct jobListint id; /* 作業(yè)ID */int size; /* 作業(yè)大小需要的存儲空間大小 */int status; /* 作業(yè)狀態(tài) 0 : new job ,1 : in the memory

8、, 2 : finished . */struct jobList *next; /* 作業(yè)鏈表指針 */以上將存儲空間分為空閑可占用兩局部，在usedlist中設jobID而不設size，可以在不增加空間復雜度與freelist相比的同時更方便的實現(xiàn)可變分區(qū)存儲管理從后面的一些函數(shù)的實現(xiàn)上可以得出這個結(jié)論。盡管設置joblist增加了空間復雜度，但它的存在，使得該程序可以方便的直接利用D盤中的JOB文件。該文件可以認為是一個和其他進程共享的資源。通過這個文件，其他進程寫入數(shù)據(jù)供讀取。這中思想在操作系統(tǒng)設計中表達的很多。2實現(xiàn)分區(qū)存儲管理的內(nèi)存分配功能，選擇適應算法首次適應算法，最正確適應算法

9、，最后適應算法，最壞適應算法。根本原理分析： 1 Best fit ：將空閑分區(qū)按大小從小到大排序，從頭找到大小適宜的分區(qū)。2 Worst fit：將空閑分區(qū)按大小從大到小排序，從頭找到大小適宜的分區(qū)。3 First fit ：將空閑分區(qū)按起始地址大小從小到大排序，4 Last fit ：將空閑分區(qū)按起始地址大小從大到小排序，由此，可將空閑分區(qū)先做適宜的排序后用對應的適應算法給作業(yè)分配存儲空間。排序函數(shù) orderbySize為零那么按分區(qū)大小排序，否那么按分區(qū)起始地址；inc為零從小到大排序，否那么從大到小排序；通過empty指針返回結(jié)果。void order(struct freeList

10、 *empty,int bySize,int inc)struct freeList *p,*q,*temp;int startAddress,size;for(p = (*empty) -> next;p;p = p -> next) /* 按bySize和inc兩個參數(shù)尋找適宜的節(jié)點，用temp指向它 */for(temp = q = p;q;q = q -> next)switch(bySize)case 0 : switch(inc)case 0:if(q->size < temp->size)temp = q;break;default:if(q-

11、>size > temp->size)temp = q;break; break;default: switch(inc)case 0:if(q->startAddress < temp->startAddress)temp = q;break;default:if(q->startAddress > temp->startAddress)temp = q;break; break; /* 交換節(jié)點的成員值 */ if(temp != p) startAddress = p->startAddress;size = p->siz

12、e;p->startAddress = temp->startAddress;p->size = temp->size;temp->startAddress = startAddress;temp->size = size;3實現(xiàn)分區(qū)存儲管理的內(nèi)存回收算法。void insertFreeNode(struct freeList *empty,int startAddress,int size)插入回收的空節(jié)點分區(qū)，處理回收分區(qū)與空閑分區(qū)的四種鄰接關(guān)系。struct freeList *p,*q,*r; for(p = *empty;p -> next;

13、p = p -> next) ; /* 處理鏈表尾部的鄰接情況 */if(p = *empty | p -> startAddress + p -> size < startAddress)/* 與尾部不相鄰*/makeFreeNode(&r,startAddress,size); /* 通過r指針返回創(chuàng)立的空閑節(jié)點*/r -> next = p -> next; /* 插入獨立的空閑節(jié)點 */p -> next = r;return ;if(p -> startAddress + p -> size = startAddress)

14、 /* 與尾部上鄰 */p -> size += size; /* 合并尾部節(jié)點 */return ;q = (*empty) -> next; /* 處理鏈表首節(jié)點的鄰接情況 */if(startAddress + size = q -> startAddress) /* 與首節(jié)點下鄰 */q -> startAddress = startAddress; /* 合并首節(jié)點 */q -> size += size;else if(startAddress + size < q -> startAddress) /* 與首節(jié)點不相鄰 */makeFre

15、eNode(&r,startAddress,size);r -> next = (*empty) -> next;(*empty) -> next = r;else /* 處理鏈表中間的鄰接情況 */while(q -> next && q -> startAddress < startAddress)p = q;q = q -> next;if(p -> startAddress + p -> size = startAddress &&q -> startAddress = startAdd

16、ress + size) /* 上下鄰，合并節(jié)點 */p -> size += size + q -> size;p -> next = q -> next;free(q); /* 刪除多余節(jié)點 */else if(p -> startAddress + p -> size = startAddress && q -> startAddress != startAddress + size) /*上鄰，增加節(jié)點的大小*/p -> size += size;else if(p -> startAddress + p ->

17、 size != startAddress && q -> startAddress = startAddress + size) /* 下鄰 */q -> startAddress = startAddress; /* 修改節(jié)點起始地址 */q -> size += size; /* 修改節(jié)點的大小 */else /* 上下不相鄰 */makeFreeNode(&r,startAddress,size);r -> next = p -> next;p -> next = r;4當碎片產(chǎn)生時，進行碎片的拼接。void moveFrag

18、ment(struct jobList *jobs,struct freeList *empty,struct usedList *used)int size,status;struct usedList *p;int address = memoryStartAddress; /*全局變量，初始化時分配存儲空間始址*/if(*empty)->next = NULL) /* 空閑分區(qū)鏈表為空，提示并返回 */printf("nThe memory was used out at all.nMay be you should finish some jobs first or p

19、ress any key to try again !");getch();return;for(p = (*used) -> next;p;p = p-> next)/* 循環(huán)的修改占用分區(qū)的始址 */p -> startAddress = address;getJobInfo(jobs,p -> jobID,&size,&status); /* 由作業(yè)ID獲得作業(yè)大小 */address += size;(*empty)->next->startAddress = address;/*修改空閑分區(qū)的首節(jié)點始址、大小*/(*emp

20、ty) -> next -> size = memorySize - (address - memoryStartAddress);(*empty) -> next -> next = NULL; /* 刪除首節(jié)點后的所有節(jié)點 */5空閑分區(qū)隊列顯示：int showFreeList(struct freeList *empty)6作業(yè)占用鏈表顯示：int showUsedList(struct jobList *jobs,struct usedList *used) 從頭到尾顯示used鏈，同時通過其中的作業(yè)ID在jobs中查對應的大小。7從鍵盤輸入作業(yè)到D盤的JOB

21、文件：void inputJob(void)8從JOB文件中讀出作業(yè)并創(chuàng)立作業(yè)鏈表：int makeJobList(struct jobList *jobs)9顯示作業(yè)鏈表：int showJobList(struct jobList *jobs) 10.更新作業(yè)鏈表中作業(yè)的狀態(tài)： int updateJobFile(struct jobList *jobs)11.根據(jù)作業(yè)鏈表更新JOB文件： int updateJobFile(struct jobList *jobs) 12.為作業(yè)分配存儲空間、狀態(tài)必須為0：int allocate(struct freeList *empty,int s

22、ize) 13.結(jié)束一個作業(yè)號為id的作業(yè)，釋放存儲空間由*startAddress返回空間的起始地址：int finishJob(struct usedList *used,int id,int *startAddress)14.插入釋放的空間到used鏈表中作業(yè)號為id，startAddress由函數(shù)13返回：void insertUsedNode(struct usedList *used,int id,int startAddress)15.獲取作業(yè)的信息： void getJobInfo(struct jobList *jobs,int id,int *size,int *statu

23、s)16.初始化存儲空間起始地址、大?。簐oid iniMemory(void)17.選擇適應算法：char selectFitMethod(void)18.根據(jù)參數(shù)startAddress、size創(chuàng)立空閑節(jié)點，由empty指針返回：void makeFreeNode(struct freeList *empty,int startAddress,int size)19.以要求的方式翻開文件：void openFile(FILE *fp,char *filename,char *mode)20.出現(xiàn)嚴重錯誤時顯示信息并結(jié)束程序；void errorMessage(void)2.2.3程序結(jié)構(gòu)

24、流程圖main主函數(shù)流程圖Assignnment函數(shù)流程圖Acceptment2函數(shù)2.2.4各模塊的功能及程序說明void acceptment1(RECT *head,RECT *back1)/*首先適應*/void acceptment2(RECT *head,RECT *back1)/*最正確適應，back1為回收結(jié)點的地址*/void print(RECT *head) /*輸出鏈表*/int backcheck(RECT *head,RECT *back1) 2.2.5程序結(jié)果程序源代碼及注釋/* 源程序*/*pcb.c*/#include "stdio.h"#

25、include "stdlib.h"#include "string.h"#define MAX 32767typedef struct node /*設置分區(qū)描述器*/ int address,size; struct node *next;RECT;/*函數(shù)原型*/RECT *assignment(RECT *head,int application);void acceptment1(RECT *head,RECT *back1);void acceptment2(RECT *head,RECT *back1) ;int backcheck(REC

26、T *head,RECT *back1);void print(RECT *head);/*變量聲明*/RECT *head,*back,*assign1,*p;int application1,maxblocknum;char way;/*主函數(shù)*/main() char choose10; int check; head=malloc(sizeof(RECT); /*建立可利用區(qū)表的初始狀態(tài)*/ p=malloc(sizeof(RECT); head->size=MAX; head->address=0; head->next=p; maxblocknum=1; p-&g

27、t;size=MAX; p->address=0; p->next=NULL; print(head); /*輸出可利用表初始狀態(tài)*/ printf("Enter the way(best or first(b/f)n");/*選擇適應策略*/ scanf("%c",&way); do printf("Enter the assign or accept(as/ac)n"); scanf("%s",choose); /*選擇分配或回收*/ if(strcmp(choose,"as&qu

28、ot;)=0) /*as為分配*/ printf("Input application:n"); scanf("%d",&application1);/*輸入申請空間大小*/ assign1=assignment(head,application1);/*調(diào)用分配函數(shù)*/ if(assign1->address=-1)/*分配不成功*/ printf("Too large application!,assign fails!nn"); else printf("Success!ADDRESS=%5dn"

29、;,assign1->address); /*分配成功*/ print(head); /*輸出*/ else if(strcmp(choose,"ac")=0) /*回收*/ back=malloc(sizeof(RECT); printf("Input Adress and Size!n"); scanf("%d%d",&back->address,&back->size);/*輸入回收地址和大小*/ check=backcheck(head,back); /*檢查*/ if(check=1) if

30、(tolower(way)='f')/*首先適應算法*/ acceptment1(head,back); /*首先適應*/ else acceptment2(head,back);/*最正確適應*/ print(head); while(!strcmp(choose,"as")|!strcmp(choose,"ac");/*分配函數(shù)*/RECT *assignment(RECT *head,int application) RECT *after,*before,*assign; assign=malloc(sizeof(RECT); /

31、*分配申請空間*/ assign->size=application; assign->next=NULL; if(application>head->size|application<=0) assign->address=-1; /*申請無效*/ else before=head; after=head->next; while(after->size<application)/*查找適應的結(jié)點*/ before=before->next; after=after->next; if(after->size=appli

32、cation) /*結(jié)點大小等于申請大小那么完全分配*/ if(after->size=head->size) maxblocknum-; before->next=after->next; assign->address=after->address; free(after); else if(after->size=head->size) maxblocknum-; after->size=after->size-application; /*大于申請空間那么截取相應大小分配*/ assign->address=after-

33、>address+after->size; if(tolower(way)='b')/*如果是最正確適應，將截取后剩余結(jié)點重新回收到適宜位置*/ before->next=after->next; back=after; acceptment2(head,back); if(maxblocknum=0) /*修改最大數(shù)和頭結(jié)點值*/ before=head; head->size=0; maxblocknum=1; while(before!=NULL) if(before->size>head->size) head->s

34、ize=before->size; maxblocknum=1; else if(before->size=head->size) maxblocknum+; before=before->next; assign1=assign; return assign1; /*返回分配給用戶的地址*/void acceptment1(RECT *head,RECT *back1)/*首先適應*/ RECT *before,*after; int insert; before=head; after=head->next; insert=0; while(!insert)

35、/*將回收區(qū)插入空閑區(qū)表*/ if(after=NULL)| (back1->address<=after->address)&& (back1->address>=before->address) before->next=back1; back1->next=after; insert=1; else before=before->next; after=after->next; if(back1->address=before->address+before->size)/*與上一塊合并*/ b

36、efore->size=before->size+back1->size; before->next=back1->next; free(back1); back1=before; if(after!=NULL&&(after->address=back1->address+back1->size) /*與下一塊合并*/ back1->size=back1->size+after->size; back1->next=after->next; free(after); if(head->size

37、<back1->size) /*修改最大塊值和最大塊個數(shù)*/ head->size=back1->size; maxblocknum=1; else if(head->size=back1->size) maxblocknum+;/*最正確適應，back1為回收結(jié)點的地址*/void acceptment2(RECT *head,RECT *back1) RECT *before,*after; int insert ; insert=0; before=head; after=head->next; if(head->next=NULL) /*

38、如果可利用區(qū)表為空*/ head->size=back1->size; head->next=back1; maxblocknum+; back1->next=NULL; else while(after!=NULL) /*與上一塊合并*/ if(back1->address=after->size+after->address) before->next=after->next; back->size=after->size+back1->size; free(after); after=NULL; else after

39、=after->next; before=before->next; before=head; after=head->next; while(after!=NULL) if(after->address=back1->size+back1->address) /*與下一塊合并*/ back1->size=back1->size+after->size; before->next=after->next; free(after); after=NULL; else before=before->next; after=af

40、ter->next; before=head;/*將回收結(jié)點插入到適宜的位置*/ after=head->next; do if(after=NULL|(after->size>back1->size) before->next=back1; back1->next=after; insert=1; else before=before->next; after=after->next; while(!insert); if(head->size<back1->size) /*修改最大塊值和最大塊數(shù)*/ head->

41、size=back1->size; maxblocknum+; else if(head->size=back1->size) maxblocknum+; void print(RECT *head) /*輸出鏈表*/ RECT *before,*after; int index,k; before=head->next; index=1; if(head->next=NULL) printf("NO part for assignment!n"); else printf("*index*address*end*size*n&quo

42、t;); while(before!=NULL) printf("-n"); printf(" %-13d%-13d%-13d%-13dn",index,before->address,before->address+before->size-1,before->size); printf("-n"); index+; before=before->next; /*檢查回收塊的合法性，back1為要回收的結(jié)點地址*/int backcheck(RECT *head,RECT *back1) RECT *b

43、efore,*after; int check=1; if(back1->address<0|back1->size<0) check=0;/*地址和大小不能為負*/ before=head->next; while(before!=NULL)&&check)/*地址不能和空閑區(qū)表中結(jié)點出現(xiàn)重疊*/ if(back1->address<before->address) &&(back1->address+back1->size>before->address) |(back1->address>=before->address)&&(back1->address<before->address+before->siz