动态分区分配算法

计算机操作系统动态分区磁盘调度算法一个好的计算机系统不仅要有足够的存储容量，较高的存取速度和稳定可靠的存储器，而且能够合理的分配和使用这些主存空间。当用户提出申请主存空间的要求时，存储管理能够按照一定的策略分析主存的使用情况，找出足够的空间分配给申请者；当作业运行完毕，存储管理要回收作业占用的主存空间。本实验采取可变分区存储管理方法，用常用分区管理算法模拟磁盘管理过程，以加深了解操作系统的存储管理功能。1.本实验是模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。2.采用最先适应法、最佳适应法、最坏适应法分配主存空间。3.当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。4.当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。5.设计的模拟系统中，进程数不小于5，进程调度方式可以采用实验一中的任何一种。6.运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。首次适应算法将内存中的空闲区按照地址由低到高的顺序形成空闲区表当一个新作业要求装入主存时，查空闲区表，从中找到第一个满足要求的空闲区，为作业分配主存空间，并将剩余空闲区按照地址由小到大的顺序插入空闲区表的合适位置，修改已分配表当作业运行结束后，回收作业的主存空间，并与相邻空闲区合并，修改空闲区表和已分配表每次主存分配和回收后，打印空闲区表和已分配表详细描述实验设计思想、程序结构及各模块设计思路；详细描述程序所用数据结构及算法；明确给出测试用例和实验结果；为增加程序可读性，在程序中进行适当注释说明；认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等；#includeiostream#includecstdlibusingnamespacestd;constintprocsize=5;typedefstructNode{intPId;//进程IdintPrio;//进程优先数intNeedRunTime;//进程需要运行时间intRoom;//进程所需空间大小Node*next;//就绪队列中的下个就绪进程的地址}PCB;typedefstruct{//就绪链式队列结构体PCB*front;PCB*rear;}AleadyQueue;typedefstructTab{//分区表结构体intCalledId;//调用该分区的进程IdintTabId;//分区号intSize;//大小intStartAdd;//始址char*Status;//使用状态Tab*next;//指向下个分区}Table;voidCinInfo(PCBP[procsize]){//输入进程信息cout\t\t请输入5个进程,格式如下:\n\n;coutPId优先数运行时间所需内存大小(最好是小于20)\n;inti=0,j=0;for(i,j;iprocsize;i++,j++){cinP[j].PIdP[j].PrioP[j].NeedRunTimeP[j].Room;}}voidSort(PCBP[procsize]){//根据优先数由冒泡法对进程进行排序inti,j,exchange=1;//exchange表示相邻PCB是否调换PCBTemp;for(i=procsize;i1&&exchange;i--){exchange=0;for(j=0;ji-1;j++)if(P[j].PrioP[j+1].Prio){Temp=P[j];P[j]=P[j+1];P[j+1]=Temp;exchange=1;}}}AleadyQueueInitQueue(){//就绪队列初始化函数AleadyQueueQ;Node*p;p=(Node*)malloc(sizeof(PCB));if(!p){cout就绪队列初始化失败！\n;exit(0);}else{Q.front=Q.rear=p;Q.front-next=NULL;returnQ;}}voidEnQueue(AleadyQueue&Queue,PCB&P){//进程入队操作函数Node*p;p=(Node*)malloc(sizeof(PCB));if(!p)cout分配节点失败！\n;else{*p=P;p-next=NULL;Queue.rear-next=p;Queue.rear=p;}}voidEnQueue1(AleadyQueue&Queue,PCB&P){//进程入队操作函数Node*p;p=(Node*)malloc(sizeof(PCB));if(!p)cout分配节点失败！\n;else{*p=P;p-next=NULL;Queue.rear-next=p;Queue.rear=p;}}PCBOutQueue(AleadyQueue&Q){//进程出队操作函数Node*P;P=(Node*)malloc(sizeof(PCB));if(Q.front-next!=NULL){P=Q.front-next;Q.front-next=P-next;}return*P;}PCBOutQueue1(AleadyQueue&Q){//进程出队操作函数Node*P;P=(Node*)malloc(sizeof(PCB));if(Q.front-next!=NULL){P=Q.front-next;Q.front-next=P-next;}return*P;}voidprintinfo(AleadyQueueQ){//打印就绪队列的情况cout目前就绪队列进程情况如下：\n;coutPId\t\tPriority\t\tNeedTime\t\tRoom\n;Q.front=Q.front-next;while(1){if(Q.front!=NULL){coutQ.front-PId\t\tQ.front-Prio\t\t\t;coutQ.front-NeedRunTime\t\t\tQ.front-Roomendl;Q.front=Q.front-next;}elsebreak;}}intchose(){//选择所选算法inti;cout请选择：\n;cout1、采用首次适应算法为进程分配内存!\n;cout2、采用最佳适应算法为进程分配内存!\n;cout3、采用最坏适应算法为进程分配内存!\n;cout4、结束!\n;cini;returni;}Table*CreateMMTable(){//定义主存分区表Table*FT;//用尾插入法Table*R;Table*P;FT=(Table*)malloc(sizeof(Tab));R=FT;FT-next=NULL;intnum=0;intLastAdd=0;intLastSize=1;while(1){P=(Table*)malloc(sizeof(Tab));P-CalledId=0;//被调用的进程调Id初始化为0P-TabId=num;//主存分区号P-Size=3*num+1;//分区大小P-StartAdd=LastAdd+LastSize;//分区始址P-Status=Free;//分区状态num++;//分区号加1LastAdd=P-StartAdd;//重新定义LastAdd为上次的StartAddLastSize=P-Size;//同上P-next=NULL;R-next=P;R=P;if(P-StartAdd==93)//内存初始化完毕break;}returnFT;}Table*CreateUsedTable(){//创建已分配表Table*T;T=(Table*)malloc(sizeof(Tab));T-next=NULL;returnT;}voidCoutMMTable(Table*FTL){//打印主存表情况cout主存表情况：\n;cout分区号\t\t分区始址\t分区大小\t状态\n;FTL=FTL-next;while(1){coutFTL-TabId\t\tFTL-StartAdd\t\t;coutFTL-Size\t\t;coutFTL-Statusendl;FTL=FTL-next;if(FTL-next==NULL)break;}}voidCoutFreeTable(Table*FTL){//打印空闲区表cout空闲区表情况：\n;cout分区号\t\t分区始址\t分区大小\t状态\n;FTL=FTL-next;while(1){coutFTL-TabId\t\tFTL-StartAdd\t\t;coutFTL-Size\t\t;printf(%s\n,FTL-Status);FTL=FTL-next;if(FTL-next==NULL)break;}}voidCoutUsedTable(Table*UTL){//打印已分配表cout已分配表情况：\n;cout分区号\t\t分区始址\t分区大小\t状态\n;UTL=UTL-next;while(1){if(UTL-Status==Used){coutUTL-TabId\t\tUTL-StartAdd\t\t;coutUTL-Size\t\t;printf(%s\n,UTL-Status);}UTL=UTL-next;if(UTL-next==NULL)break;}}intDistribMM(Table*MMTableList,PCBTemp,Table*FTL,Table*UTL){//分配一块一定大小的内存Table*P;Table*TempMM;//需要改为已分配节点的上一个节点TempMM=MMTableList;Table*TTT;TTT=MMTableList-next;while(1){//查找满足大小的分区节点if(TTT-Size=Temp.Room&&TTT-Status==Free)break;TTT=TTT-next;if(TTT==NULL){cout\n\n\n\t\t\t\t警告!内存不足....\n\n\n;return0;}}//while//以下是内存改为已分配P=(Table*)malloc(sizeof(Tab));while(1){if(TempMM-next==TTT)break;TempMM=TempMM-next;}P-next=TempMM-next;TempMM-next=P;P-StartAdd=TTT-StartAdd;P-Size=Temp.Room;P-CalledId=Temp.PId;P-TabId=TTT-TabId;P-Status=Used;P=P-next;while(P!=NULL){(P-TabId)++;P=P-next;}FTL=FTL-next;while(1){//将空闲分区对应的首地址更改if(FTL-StartAdd==TTT-StartAdd)break;FTL=FTL-next;}TTT-StartAdd=FTL-StartAdd=TTT-StartAdd+Temp.Room;//空闲表的首地址=原来+RoomTTT-Size=FTL-Size=TTT-Size-Temp.Room;while(FTL!=NULL){(FTL-TabId)++;FTL=FTL-next;}return2;}voidReturnMM(Table*MMTab