1、精選優(yōu)質文檔-傾情為你奉上 組號 成績 計算機操作系統(tǒng)課程設計報告 題目 基于可重定位分區(qū)分配算法的內存管理的設計與實現 專業(yè)： 計算機科學與技術 班級： 學號+姓名： 指導教師： 2016年12月 23 日一 設計目的掌握內存的連續(xù)分配方式的各種分配算法二 設計內容基于可重定位分區(qū)分配算法的內存管理的設計與實現。本系統(tǒng)模擬操作系統(tǒng)內存分配算法的實現，實現可重定位分區(qū)分配算法，采用PCB定義結構體來表示一個進程，定義了進程的名稱和大小，進程內存起始地址和進程狀態(tài)。內存分區(qū)表采用空閑分區(qū)表的形式來模擬實現。要求定義與算法相關的數據結構，如PCB、空閑分區(qū)；在使用可重定位分區(qū)分配算法時必須實現緊湊

2、。三 設計原理可重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法基本上相同，差別僅在于：在這種分配算法中，增加了緊湊功能。通常，該算法不能找到一個足夠大的空閑分區(qū)以滿足用戶需求時，如果所有的小的空閑分區(qū)的容量總和大于用戶的要求，這是便須對內存進行“緊湊”，將經過“緊湊”后所得到的大空閑分區(qū)分配給用戶。如果所有的小空閑分區(qū)的容量總和仍小于用戶的要求，則返回分配失敗信息四 詳細設計及編碼1. 模塊分析（1） 分配模塊這里采用首次適應(FF)算法。設用戶請求的分區(qū)大小為u.size,內存中空閑分區(qū)大小為m.size,規(guī)定的不再切割的剩余空間大小為size。空閑分區(qū)按地址遞增的順序排列；在分配內存時，從空閑分區(qū)表

3、第一個表目開始順序查找，如果m.sizeu.size且m.size-u.sizesize，說明多余部分太小，不再分割，將整個分區(qū)分配給請求者；如果m.sizeu.size且m.size-u.size>size，就從該空閑分區(qū)中按請求的大小劃分出一塊內存空間分配給用戶，剩余的部分仍留在空閑分區(qū)表中；如果m.size<u.size則查找下一個空閑分區(qū)表項，直到找到一個足夠大的空閑分區(qū)；如果沒有找到一個足夠大的內存空閑分區(qū)，但所有的小的空閑分區(qū)的容量總和大于用戶的要求，就進行緊湊，將緊湊后得到的大的空閑分區(qū)按上述的方式分配給用戶；但如果所有的小的空閑分區(qū)的容量總和仍不能滿足用戶需要，則分

4、配失敗。（2） 內存回收模塊進行內存回收操作時，先隨機產生一個要回收的進程的進程號，把該進程從進程表中中刪除，它所釋放的空閑內存空間插入到空閑分區(qū)表；如果回收區(qū)與插入點的前一個空閑分區(qū)相鄰，應將回收區(qū)與插入點的前一分區(qū)合并，修改前一個分區(qū)的大小；如果回收區(qū)與插入點的后一個空閑分區(qū)相鄰，應將回收區(qū)與插入點的后一分區(qū)合并，回收區(qū)的首址作為新空閑分區(qū)的首址，大小為二者之和；如果回收區(qū)同時與插入點的前、后空閑分區(qū)相鄰，應將三個分區(qū)合并，使用前一個分區(qū)的首址，取消后一個分區(qū)，大小為三者之和。（3） 緊湊模塊將內存中所有作業(yè)進行移動，使他們全都相鄰接，把原來分散的多個空閑小分區(qū)拼接成一個大分區(qū)。2. 流程

5、圖 否 否 是 是 3. 代碼實現#include<stdio.h>#include<stdlib.h>#include<time.h>#include<windows.h>#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define SIZE 15 /進程表/int ppNo=1; /用于遞增生成進程號 int pLength=0;struct PCBint pNo; /進程號(名)int pSize

6、; / 進程大小 int pOccupy; / 實際占用的內存 int pStartAddr; / 進程起始地址 int pState; /進程狀態(tài) ;struct PCB pList200;/空閑分區(qū)表部分/typedef int Status;typedef struct emptyNode /空閑分區(qū)結構體 int areaSize; /空閑分區(qū)大小 int aStartAddr; /空閑分區(qū)始址 struct emptyNode *next;emptyNode,*LinkList;int ListDelete(struct PCB *pList,int i);/AAA/刪除下標為i的進

7、程 void pSort(struct PCB *pList); /AAA/內存中的進程按始址遞增排序 void compact(LinkList &L,struct PCB *pList);/AAA/緊湊 ,內存中進程移動，修改進程數據結構；空閑分區(qū)合并，修改空閑分區(qū)表數據結構 void amalgamate(LinkList &L); /AAA/回收后進行合并空閑分區(qū) void recycle(LinkList &L,struct PCB *pList); /AAA/回收 ，從進程表中刪除進程 ，把釋放出的空間插入到空閑分區(qū)鏈表中 Status InitList(L

8、inkList &L); /1AAA/構造一個新的有頭節(jié)點的空鏈表LStatus ClearList(LinkList &L); /2AAA/將鏈表L重置為空表Status ListInsert(LinkList &L,LinkList s1); /AAA/*根據始址進行插入 void DeleteElem(LinkList &L,int aStartAddr);/*刪除線性表中始址值為aStartAddr的結點void PrintList(LinkList L); /AAA/*輸出各結點的值void creatP(struct PCB *p); /AAA/初始

9、化進程int search(LinkList &L,int pSize); /AAA/檢索分區(qū)表 ,返回合適分區(qū)的首址 int add(LinkList &L); /AAA/返回空閑分區(qū)總和 void pListPrint(struct PCB *pList); /AAA/輸出內存中空間占用情況 void distribute(LinkList &L,struct PCB *process);int ListDelete(struct PCB *pList,int i)/AAA/刪除下標為i的進程 for(;i<pLength-1;i+)pListi=pListi

10、+1;pLength-;/ListDeletevoid pSort(struct PCB *pList) /AAA/內存中的進程按始址遞增排序 int i,j;struct PCB temp;for(i=0;i<pLength-1;i+)for(j=0;j<pLength-i-1;j+)if(pListj.pStartAddr>pListj+1.pStartAddr)temp=pListj;pListj=pListj+1;pListj+1=temp;/AAA/緊湊 ,內存中進程移動，修改進程數據結構；空閑分區(qū)合并，修改空閑分區(qū)表數據結構 void compact(LinkLi

11、st &L,struct PCB *pList) printf("進行緊湊n"); /1、進程移動,修改進程數據結構int i;pList0.pStartAddr=0; /第一個進程移到最上面 for(i=0;i<pLength-1;i+)pListi+1.pStartAddr=pListi.pStartAddr+pListi.pOccupy;/2、 空閑分區(qū)合并，修改空閑分區(qū)表數據結構 LinkList p=L->next,s;int sumEmpty=0;while(p!=NULL)/求空閑區(qū)總和 sumEmpty+=p->areaSize;p

12、=p->next;ClearList(L); /清空空閑分區(qū)表s=(LinkList)malloc(sizeof(emptyNode);s->aStartAddr=pListpLength-1.pStartAddr+pListpLength-1.pOccupy; s->areaSize=sumEmpty;ListInsert(L,s); printf("n緊湊后的>>>>n"); pListPrint(pList);PrintList(L);void amalgamate(LinkList &L)/AAA/回收后進行合并空閑

13、分區(qū) LinkList p=L->next,q=p->next;while(q!=NULL)if(p->aStartAddr+p->areaSize=q->aStartAddr)p->areaSize+=q->areaSize;DeleteElem(L,q->aStartAddr);/刪除被合并的結點q=p->next; elsep=q;q=q->next;/AAA/回收 ，從進程表中刪除進程 ，把釋放出的空間插入到空閑分區(qū)鏈表中 void recycle(LinkList &L,struct PCB *pList) int

14、index,delPNo,delPSize,delPOccupy,delPStartAddr; LinkList s; srand(time(0); index=rand()%pLength; delPNo=pListindex.pNo; delPSize=pListindex.pSize; delPOccupy=pListindex.pOccupy; delPStartAddr=pListindex.pStartAddr; printf("_"); printf("回收內存 進程 P%d: 始址：%d K 占用：%d KBn",delPNo,delPS

15、tartAddr,delPOccupy); printf("n回收后>>>>n"); ListDelete(pList,index); /pListPrint(pList); s=(LinkList)malloc(sizeof(emptyNode);s->areaSize=delPOccupy; s->aStartAddr=delPStartAddr; ListInsert(L,s); amalgamate(L); pListPrint(pList);/輸出內存中空間占用情況 PrintList(L); /Status InitList(

16、LinkList &L) /1AAA/構造一個新的有頭節(jié)點的空鏈表LLinkList s;L=(LinkList)malloc(sizeof(emptyNode); /生成新節(jié)點(頭結點)if(!L) return ERROR; /申請內存失敗 s=(LinkList)malloc(sizeof(emptyNode);s->areaSize=900;s->aStartAddr=0;L->next=s; /頭節(jié)點的指針域指向第一個結點 s->next=NULL;return OK;/InitListStatus ClearList(LinkList &L)

17、 /2AAA/將鏈表L重置為空表LinkList p,r;p=L->next; r=p->next;while(p!=NULL)free(p);if(r=NULL)p=NULL;elsep=r; r=p->next;L->next=NULL;return OK;/ClearList /AAA/*根據始址進行插入 Status ListInsert(LinkList &L,LinkList s1)LinkList r=L,p=L->next,s;/指針 s=(LinkList)malloc(sizeof(emptyNode);s->areaSize=s

18、1->areaSize;s->aStartAddr=s1->aStartAddr;if(p=NULL)L->next=s;s->next=NULL;elsewhile(p!=NULL) if(s1->aStartAddr < p->aStartAddr) s->next=r->next; r->next=s; break; r=p; p=p->next; /后移 if(p=NULL) r->next=s; s->next=NULL; return OK;/ListInsert2void DeleteElem(L

19、inkList &L,int aStartAddr)/*刪除線性表中始址值為aStartAddr的結點LinkList p=L,q;while(p->next!=NULL)q=p->next;if(q->aStartAddr=aStartAddr)p->next=q->next;free(q);elsep=p->next;/DeleteElem/void PrintList(LinkList L)/AAA/*輸出各結點的值 printf("n空閑分區(qū)情況: 始址t 大小n");LinkList p=L->next;while

20、(p!=NULL) printf(" %d Kt%d KBn",p->aStartAddr,p->areaSize);p=p->next;printf("n");/PrintList void creatP(struct PCB *p) /AAA/初始化進程int size;srand(time(NULL); size=rand()%7+1; size*=10;p->pNo=ppNo+;p->pSize=size;p->pOccupy=0;p->pStartAddr=0;p->pState=0;int se

21、arch(LinkList &L,int pSize) /檢索分區(qū)表 ,返回合適分區(qū)的首址 LinkList p=L->next;while(p!=NULL)if(p->areaSize>=pSize)return p->aStartAddr;p=p->next;return -1;/沒有足夠大的 int add(LinkList &L) /返回空閑分區(qū)總和 LinkList p=L->next;int sum=0; while(p!=NULL)sum+=p->areaSize;p=p->next;return sum;void

22、pListPrint(struct PCB *pList)/AAA/輸出內存中空間占用情況 printf("n進程分配情況: 進程t 始址t占用n");for(int i=0;i<pLength;i+) printf(" P%dt %d Kt%d KBn", pListi.pNo,pListi.pStartAddr,pListi.pOccupy);void distribute(LinkList &L,struct PCB *process)LinkList p=L->next;while(p!=NULL)if(p->areaS

23、ize>=process->pSize) break; p=p->next;printf("%d KB < %d KB",process->pSize,p->areaSize);if(p->areaSize-process->pSize<=SIZE)/不用分割全部分配 （直接刪除此空閑分區(qū)結點）process->pStartAddr=p->aStartAddr; /進程始址變化 process->pState=1; /進程狀態(tài) process->pOccupy=p->areaSize; /進

24、程實際占用內存 為改空閑分區(qū)的大小 pListpLength+= *process; /把進程加入進程列表 printf(" 且 %d KB - %d KB = %d KB < %d KB 則 整區(qū)分配n", p->areaSize,process->pSize,p->areaSize-process->pSize,SIZE);pSort(pList); printf("n分配后>>>>n");pListPrint(pList);/輸出內存中空間占用情況 DeleteElem(L,p->aSta

25、rtAddr);else/分割分配 process->pStartAddr=p->aStartAddr; /進程始址變化 process->pState=1; /進程狀態(tài) process->pOccupy=process->pSize; /進程實際占用內存 為該進程的大小 pListpLength+= *process; /把進程加入進程列表 printf(" 且 %d KB - %d KB = %d KB > %d KB 則 劃分分配n", p->areaSize,process->pSize,p->areaSize-

26、process->pSize,SIZE);pSort(pList); /進程排序 printf("n分配后>>>>n");pListPrint(pList);/輸出內存中空間占用情況 /compact(L,pList);p->aStartAddr+=process->pSize; /空閑分區(qū)始址變化 p->areaSize-=process->pOccupy; /空閑分區(qū)大小 變化 int main()/0、創(chuàng)建一個進程，參數隨機數方式產生 struct PCB p; int i,num,dele,k,stAddr,fl

27、ag; LinkList s,L; printf("*可重定位分區(qū)分配*"); if(!InitList(L) /初始化空閑分區(qū)表 printf("創(chuàng)建表失敗n"); while(1) srand(time(0); flag=rand()%100+1; if(flag%2=0) creatP(&p);/初始化進程 printf("_"); printf("待裝入作業(yè):%d Size = %d KBn",p.pNo,p.pSize); /1、請求分配 size /2、檢索空閑分區(qū)表(首次適應FF) PrintList(L); stAddr=search(L,p.pSize);/得到足夠大的分區(qū)的始址 ，沒有則返回-1 if(stAd