操作系统课程设计实验报告

组号成绩计算机操作系统课程设计报告题目内存的连续分配算法专业：计算机科学与技术班级：2班学号姓名：20141308055张宇星指导教师：赵晓平2016年12月26日一、设计目的掌握内存的里联系分配方式的各种算法。二、设计内容本系统模拟操作系统内存分配算法的实现，实现可重定位分区分配算法，采用PCB定义结构体来表示一个进程，定义了进程的名称和大小，进程内存起始地址和进程状态。内存分区表用空闲分区表的形式来模拟实现。三、设计原理动态分区的实现是根据进程所申请的内存大小来决定动态的由系统进行分配内存空间大小，因此分区表里的空闲分区个数是不定的，根据进程数和进程大小决定的。可重定位分区算法比动态分区算法增加了紧凑的功能。四、详细设计及编码1、模块分析该实验可分为三大部分，每一部分又由个数不同的几个函数实现。第一部分是装入作业，第二部分是内存回收，第三部分是进行紧凑。装入作业的时候首先初始化一个链表，根据用户输入的操作代号进行相应的操作。若用户选择装入作业首先判断空闲分区表里有没有比作业需要的内存大的分区，若有直接分配，若没有进行紧凑操作，再将紧凑后的空闲分区与作业大小比较，若能装的下则分配给作业，若是进行紧凑后的空闲分区仍不能装入整个作业则通知用户内存不够。2、流程图2、代码实现#includestdio.h#includestdlib.h#includetime.h#includewindows.h#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineSIZE3检索空闲分区链进行紧凑形成连续空闲区空闲分区总和≥u.size?NYN找到＞u.size的分无法分配，返回请求分配u.size分区修改有关的数据结构进行紧凑形成连续空闲区按动态分区方式进行分配Y返回分区号及首址//进程表intppNo=1;//用于递增生成进程号intpLength=0;structPCB{intpNo;//进程号(名)intpSize;//进程大小intpOccupy;//实际占用的内存intpStartAddr;//进程起始地址intpState;//进程状态};structPCBpList[200];//////////////////空闲分区表部分/////////////////////////////////////////////////////typedefintStatus;typedefstructemptyNode{//空闲分区结构体intareaSize;//空闲分区大小intaStartAddr;//空闲分区始址structemptyNode*next;}emptyNode,*LinkList;intListDelete(structPCB*pList,inti);//删除下标为i的进程voidpSort(structPCB*pList);//内存中的进程按始址递增排序voidcompact(LinkList&L,structPCB*pList);//紧凑,内存中进程移动，修改进程数据结构；空闲分区合并，修改空闲分区表数据结构voidamalgamate(LinkList&L);//回收后进行合并空闲分区voidrecycle(LinkList&L,structPCB*pList);//回收，从进程表中删除进程，把释放出的空间插入到空闲分区链表中StatusInitList(LinkList&L);///构造一个新的有头节点的空链表LStatusClearList(LinkList&L);///将链表L重置为空表StatusListInsert(LinkList&L,LinkLists1);//根据始址进行插入voidDeleteElem(LinkList&L,intaStartAddr);//删除线性表中始址值为aStartAddr的结点voidPrintList(LinkListL);//输出各结点的值voidcreatP(structPCB*p);///初始化进程intsearch(LinkList&L,intpSize);//检索分区表,返回合适分区的首址intadd(LinkList&L);//返回空闲分区总和voidpListPrint(structPCB*pList);//AAA/输出内存中空间占用情况voiddistribute(LinkList&L,structPCB*process);intListDelete(structPCB*pList,inti)//AAA/删除下标为i的进程{for(;ipLength-1;i++){pList[i]=pList[i+1];}pLength--;}//ListDeletevoidpSort(structPCB*pList){//AAA/内存中的进程按始址递增排序inti,j;structPCBtemp;for(i=0;ipLength-1;i++){for(j=0;jpLength-i-1;j++){if(pList[j].pStartAddrpList[j+1].pStartAddr){temp=pList[j];pList[j]=pList[j+1];pList[j+1]=temp;}}}}voidcompact(LinkList&L,structPCB*pList){//AAA/紧凑,内存中进程移动，修改进程数据结构；空闲分区合并，修改空闲分区表数据结构printf(进行紧凑\n);//1、进程移动,修改进程数据结构inti;pList[0].pStartAddr=0;//第一个进程移到最上面for(i=0;ipLength-1;i++){pList[i+1].pStartAddr=pList[i].pStartAddr+pList[i].pOccupy;}//2、空闲分区合并，修改空闲分区表数据结构LinkListp=L-next,s;intsumEmpty=0;while(p!=NULL)//求空闲区总和{sumEmpty+=p-areaSize;p=p-next;}//printf(清空前\n);//PrintList(L);ClearList(L);//清空空闲分区表//printf(清空后\n);//PrintList(L);s=(LinkList)malloc(sizeof(emptyNode));s-aStartAddr=pList[pLength-1].pStartAddr+pList[pLength-1].pOccupy;s-areaSize=sumEmpty;ListInsert(L,s);//printf(插入后\n);//PrintList(L);//printf(\n紧凑后的\n);pListPrint(pList);PrintList(L);}voidamalgamate(LinkList&L){//AAA/回收后进行合并空闲分区LinkListp=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;}else{p=q;q=q-next;}}}voidrecycle(LinkList&L,structPCB*pList){//AAA/回收，从进程表中删除进程，把释放出的空间插入到空闲分区链表中intindex,delPNo,delPSize,delPOccupy,delPStartAddr;LinkLists;//srand(time(0));//index=rand()%pLength;printf(请输入要回收的进程号：);scanf(%d,&index);delPNo=pList[index-1].pNo;delPSize=pList[index-1].pSize;delPOccupy=pList[index-1].pOccupy;delPStartAddr=pList[index-1].pStartAddr;//printf(________________________________________________________________________________);ListDelete(pList,index-1);//pListPrint(pList);s=(LinkList)malloc(sizeof(emptyNode));s-areaSize=delPOccupy;s-aStartAddr=delPStartAddr;ListInsert(L,s);amalgamate(L);pListPrint(pList);//输出内存中空间占用情况PrintList(L);}/////////////////////////////////////////////////////////////////////////////StatusInitList(LinkList&L)//1AAA/构造一个新的有头节点的空链表L{LinkLists;L=(LinkList)malloc(sizeof(emptyNode));//生成新节点(头结点)if(!L)returnERROR;//申请内存失败s=(LinkList)malloc(sizeof(emptyNode));s-areaSize=100;s-aStartAddr=0;L-next=s;//头节点的指针域指向第一个结点s-next=NULL;returnOK;}//InitListStatusClearList(LinkList&L)//2AAA/将链表L重置为空表{LinkListp,r;p=L-next;r=p-next;while(p!=NULL){free(p);if(r==NULL){p=NULL;}else{p=r;r=p-next;}}L-next=NULL;returnOK;}//ClearListStatusListInsert(LinkList&L,LinkLists1)//AAA/*****根据始址进行插入{LinkListr=L,p=L-next,s;//指针s=(LinkList)malloc(sizeof(emptyNode));s-areaSize=s1-areaSize;s-aStartAddr=s1-aStartAddr;if(p==NULL){L-next=s;s-next=NULL;}else{while(p!=NULL){if(s1-aStartAddrp-aStartAddr){s-next=r-next;r-next=s;break;}r=p;p=p-next;//后移}if(p==NULL){r-next=s;s-next=NULL;}}returnOK;}//ListInsert2voidDeleteElem(LinkList&L,intaStartAddr)//*****删除线性表中始址值为aStartAddr的结点{LinkListp=L,q;while(p-next!=NULL){q=p-next;if(q-aStartAddr==aStartAddr){p-next=q-next;free(q);}elsep=p-next;}}//DeleteElem///////////////////////////////////////////////////////////////////////////////voidPrintList(LinkListL)//AAA/*****输出各结点的值{LinkList