动态分区分配存储管理系统

动态分区分派存储管理系统 学 院 专 业 学 号 学 生 姓 名 指 导 老 师 2023年3月19日 目录一、设计目的与内容3 1、设计目的3 2、设计内容3 3、设计规定3二、算法的基本思想31、初次适应算法32、循环初次适应算法3三、重要功能模块流程图4 1、主函数流程图.4 2、初次适应算法流程图.5 3、循环初次适应算法流程图.6四、系统测试.7输入界面，按规定输入：7五、结论8六、源程序9一、 设计目的与内容设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 l 进一步巩固和复习操作系统的基础知识。 l 培养学生结构化程序、模块化程序设计的方法和能力。 l 提高学生调试程序的技巧和软件设计的能力。 l 提高学生分析问题、解决问题以及综合运用 C 语言进行程序设计的能力。 设计内容：用高级语言编写和调试一个动态分区内存分派程序，演示实现下列两种动态分区分派算法 1. 初次适应算法2. 循环初次适应算法 设计规定：1. 内存中有0-100M 的空间为用户程序空间，最开始用户空间是空闲的 2. 作业数量、作业大小、进入内存时间、运营时间需要通过界面进行输入 3. 可读取样例数据（规定存放在外部文献中）进行作业数量、作业大小、进入内存时间、运营时间的初始化 4. 根据作业进入内存的时间，采用简朴的先进先出原则进行从外存到内存的调度，作业具有等待（从外存进入内存执行）、装入（在内存可执行）、结束（运营结束，退出内存）三种状态。（为了简化，不考虑CPU 的调度与切换，运营时间为作业在内存中驻留的时间） 5. 可以自动进行内存分派与回收，可根据需要自动进行紧凑与拼接操作，所有过程均有动态图形变化的显示 6. 采用可视化界面，可随时暂停显示当前内存分派和使用情况图。二、算法的思想1、初次适应算法 空闲分区链以地址递增的顺序链接，分派内存时，从链首开始顺序查找，直至找到一个大小能满足规定的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分派给请求者，取消的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足规定的分区，则本次内存分派失败，返回。2、循环初次适应算法 在为进程分派内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足规定的空闲分区，从中划出一块与请求大小相等的内存空间分派给作业三、重要功能模块流程图主函数开始Dulinklistpf 否Inputchoice(ch) 是Ch=2breakCh=1 结束multiplexInitpartitionlist(p) 否 是 否multiplex 是初次适应算法： 开始 Intt=1T&num 否 是Dulinklistpll=block.Intx=0Xn 否 是multiplex X+multiplexmultiplex结束循环初次适应算法开始 Intt=1T&num 否 是Dulinklistpll=block.Intm=0mn 否 是multiplex m+multiplexmultiplex结束四、系统测试程序运营实例如下：输入界面，按规定输入：五、结论 作业采用数组形式进行存储，起初想用数组模拟分区，但划分记录比较不易，时间空间复杂度较大，容易混乱，遂决定用链表形式模拟分区情况。基本能运营符合规定，能模拟出动态分区过程及最终结果六源程序#include #include #include #include #define Free 0#define Use 1#define MAX_length 100 /最大内存空间为100MB#define MaxNumber 100int FreePartitionMaxNumber=16,16,8,32,64,32,8,16,64;/空闲分区int ProcessNeedMaxNumber=7,18,9,20,35,8;/每个进程需求int FirstPartitionMaxNumber;/初次int CycleFirstPartitionMaxNumber;/循环int PartitionNumber=9,ProcessNum=6;/空闲分区数及进程数bool v();bool v()int j; cout初次适应算法endl; / FirstPartitionMethod();for(int i=0;iProcessNum;i+)/进程 for(j=0;j=ProcessNeedi) FirstPartitioni =j; FreePartitionj-=ProcessNeedi; break; / c_out(FirstPartition); for(i=0;iProcessNum;i+) coutFreePartitioni ; coutendl; / Beginning(); FreePartition0=16; FreePartition1=16; FreePartition2=8; FreePartition3=32; FreePartition4=64; FreePartition5=32; FreePartition6=8; FreePartition7=16; FreePartition8=64;cout循环初次适应算法endl; /CycleFirstPartitionMethod(); j=0; for(i=0;i=ProcessNeedi) CycleFirstPartitioni=j; FreePartitionj-=ProcessNeedi; break; j+; j=j%PartitionNumber; /c_out(CycleFirstPartition);for(i=0;iProcessNum;i+) coutCycleFirstPartitioni ;cout0;x-)for(int y = 1000;y0;y-);/-/-初始化-DuLinkList InitpartitionList(DuLinkList &p)p=(DuLinkList)malloc(sizeof(DuLNode);/申请空间if(!p)exit(0);p-size=100; /初始化大小printf(输入分区首地址:);scanf(%d,&p-start);p-state=0; /状态置空闲p-ID=0; /分区号p-next=NULL;p-prior=NULL;return p;/-/-输入函数-int Putin(int &n)int i;Job temp;printf(请输入任务数目:);scanf(%d,&n);a=(Job*)malloc(n*sizeof(Job);A=(Job*)malloc(n*sizeof(Job);for(i=0;in;i+)printf(n);printf(信息输入:nn);printf(作业号:);scanf(%d,&ai.num);printf(作业大小:);scanf(%d,&ai.size);printf(作业进入时间:);scanf(%d,&ai.ctime);printf(作业运营时间:);scanf(%d,&ai.rtime);ai.state=0; /默认状态为FreeAi = ai;for(int j = 0;j n;j+) for(i = j;i ai.ctime) temp = aj;aj = ai;ai = temp;/冒泡排序freopen(data.txt,w,stdout);for (i = 0;i n;i+)printf(%d %d %d %dn,ai.num,ai.size,ai.ctime,ai.rtime);fclose(stdout);freopen(CON,w,stdout);printf(保存成功nn);return 1;/-/-读文献-int order(int &n)Job temp;printf(Input the number of the task:n);scanf(%d,&n);a=(Job*)malloc(n*sizeof(Job);freopen(data.txt,r,stdin);for(int i=0;in;i+)scanf(%d,&ai.num);scanf(%d,&ai.size);scanf(%d,&ai.ctime);scanf(%d,&ai.rtime);fclose(stdin);freopen(CON,r,stdin);for(int j = 0;j n;j+) for(i = j;i ai.ctime) temp = aj;aj = ai;ai = temp;return 1;/-/-显示分区-void showPartition(DuLinkList pl)printf(nttt分区表n);printf(t-n);printf(t 开始地址t分区号t大小 状态 n);printf(t-n);while(pl)printf(t %dtt%dt%dt,pl-start,pl-ID,pl-size);if(pl-state = 0)printf(空闲 n);if(pl-state = 1)printf(已分派 n);pl=pl-next;printf(t-n);/-/-回收函数-void huishou(DuLinkList pl3,DuLinkList &pl)/pl3是分区链表指针 pl头while(pl3) if(pl3-state=0) if(pl3-next&pl3-prior&pl3-prior-state=0&pl3-next-state=1)/pl3-size+=pl3-prior-size; pl3-start=pl3-prior-start;pl3-state=0;pl3-ID=0; if(pl3-prior-prior) pl3-prior-prior-next=pl3;/pl3与最前一个 pl3-prior=pl3-prior-prior;/else pl3-prior=pl3-prior-prior;/pl3指向空pl=pl3;pl3=pl;/pl3与头else if(pl3-prior&pl3-next&pl3-next-state=0&pl3-prior-state=1)pl3-size+=pl3-next-size;pl3-state=0;pl3-ID=0;if(pl3-next-next)pl3-next-next-prior=pl3;/建立新链表pl3与最后一个结点pl3-next=pl3-next-next;/elsepl3-next=pl3-next-next;/指向空else if(!pl3-prior) if(pl3-next-state=0)pl3-size+=pl3-next-size;pl3-state=0;pl3-ID=0; if(pl3-next-next)pl3-next-next-prior=pl3;/pl3与最后pl3-next=pl3-next-next;/elsepl3-state=0;else if(!pl3-next)if(pl3-prior-state=0)pl3-size+=pl3-prior-size;pl3-state=0;pl3-ID=0;pl3-start=pl-start; if(pl3-prior-prior)pl3-prior-prior-next=pl3;/pl3与最前 pl3-prior=pl3-prior-prior;/elsepl3-prior=NULL;/pl3指向空pl=pl3;/pl3与头pl3=pl;/elsepl3-state=0;else if(pl3-next&pl3-prior&pl3-next-state=0&pl3-prior-state=0)pl3-size=pl3-size+pl3-next-size+pl3-prior-size;pl3-state=0;pl3-ID=0;pl3-start=pl3-prior-start;if(pl3-next-next)pl3-next-next-prior=pl3;if(pl3-prior-prior)pl3-prior-prior-next=pl3;pl3-next=pl3-next-next;/指向空pl3-prior=pl3-prior-prior;elsepl3-next=pl3-next-next;/指向空pl3-prior=pl3-prior-prior;/指向头pl=pl3;pl3=pl;pl3=pl3-next;/-/-初次适应算法-void Firstfit(DuLinkList block_first,int n)int t=1;int num=n;while(t&num)DuLinkList pl1=block_first,pl2,pl3=block_first;printf(时钟:%dn,t);DuLNode *p=block_first;DuLNode *q=block_first; for(int x=0;xn;x+)if(t=ax.ctime+ax.rtime) ax.state=2;for(int m=0;mID=am.num)/分区号等于作业号时q-state=Free;/在作业完毕时，作业号等于分区号时空闲q=q-next;showJob(n);showPartition(block_first);for( m=0;mn;m+)if(am.ctime=t)am.state=1;printf(作业:%d开始运营,对其分派!,am.num);for( m=0;mstate = 1|pl1-sizenext;if(pl1)pl2=(DuLinkList)malloc(sizeof(DuLNode);pl2-start=pl1-start+am.size;pl2-state=0;pl2-ID=0;pl2-size=pl1-size-am.size;if(pl2-size5)pl1-size=am.size;pl1-state=1;pl1-ID=am.num;if(pl1-next) pl1-next-prior=pl2;pl2-next=pl1-next;pl2-prior=pl1;pl1-next=pl2;pl1=block_first;elsepl1-state=1;pl1-ID=am.num;showJob(n);showPartition(block_first);elsecout内存局限性，等待释放endl;for(int i=m;in;i+)ai.ctime+=1;p=block_first;huishou(p, block_first);t+=1;/-/-显示作业-void showJob(int n)printf(nttt作业表:n);printf(t-n);printf(t 作业号t大小t进入时间t运营时间t状态 n);printf(t-n);for(int m=0;mn;m+)printf(t %dt %dt%dt %dt,am.num,am.size,am.ctime,am.rtime);if(am.state = 0)printf( 等待 n);if(am.state = 1)printf( 装入 n);if(am.state = 2)printf( 结束 n);printf(t-n);/-/- 循 环 首 次 适 应 算 法 -void Nextfit(DuLinkList block_first,int n)int t=1;int num=n;DuLinkList flag;flag=block_first;while(t&num)DuLinkList pl1=block_first,pl2,pl3=block_first;printf(时钟:%dn,t);DuLNode *p=block_first;DuLNode *q=block_first;for(int m=0;mID=am.num)q-state=Free;q=q-next;showJob(n);showPartition(block_first);for( m=0;mn;m+)if(am.ctime=t)am.state=1;printf(作业:%d开始运营,对其分派!,am.num);for( m=0;mstate = 1|flag-sizenext;pl1=flag;if(pl1)pl2=(DuLinkList)malloc(sizeof(DuLNode);pl2-start=pl1-start+am.size;pl2-state=0;pl2-ID=0;pl2-size=pl1-size-am.size;if(pl2-size5)pl1-size=am.size;pl1-state=1;pl1-ID=am.num;if(pl1-next)pl1-next-prior=pl2;pl2-next=pl1-next;pl2-prior=pl1;pl1-next=pl2;pl1=block_first;elsepl1-state=1;pl1-ID=am.num;flag=pl2;showJob(n);showPartition(block_first);elsecout内存局限性，等待释放endl;for(int i=m;in;i+)ai.ctime+=1;p=block_first;huishou(p, block_first);flag=block_first;t+=1;/-/-界面输入-void inputchoice(int &ch)coutendl;cout初次适应算法endl;cout循环初次适应算法endl;cout退出endl;cout显示endl;coutendl;cout请输入选择：endl;scanf(%d,&ch);/-void main()DuLinkList p;int n,ch;ch = 0;f = 1;coutendl;cout 动态分区分派存储管理系统 endl;coutendl;cout 请输入作业信息：endl;Putin(n);while(f)inputchoice(ch);switch(ch)case 1:InitpartitionList(p);Firstfit(p,n);ch = 0;break;case 2:InitpartitionList(p);Nextfit(p, n);ch = 0;break; case 3:f = 0;break; case 4:v();break;