操作系统动动态分配管理系统.doc

操作系统动动态分配管理系统 作者： 日期：2 个人收集整理 勿做商业用途淮北师范大学 操作系统设计实验报告题目-动态分区分配管理系统班级：09非师 设计者：曹严严指导老师：周影时间： 2012/03/14-2012/03/15 目录1程序设计的内容和相关的要求-2程序总的功能说明-3程序的模块的说明-4程序设计的流程图-5程序的操作说明及运行结果-6源程序的清单-7心得体会-1程序设计的内容和相关的要求课程设计的目的：操作系统课程设计是计算机学院重要的教学环节,它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。l进一步巩固和复习操作系统的基础知识。l培养学生结构化程序、模块化程序设计的方法和能力。l提高学生调试程序的技巧和软件设计的能力。l提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。实现的任务：编写一个动态分区分配程序.设计内容:用高级语言编写和调试一个动态分区内存分配程序,演示实现下列两种动态分区分配算法1.首次适应算法2。循环首次适应算法设计要求：1。内存中有0-100M的空间为用户程序空间，最开始用户空间是空闲的；2.作业数量、作业大小、进入内存空间、运行时间需要通过界面进行输入;3.可读取样例数据（要求存放在外部文件夹中）进行作业数量、作业大小、进图内存时间、运行时间的初始化；4.根据作业进图内存的时间，采用简单的先进先出原则进行从外村到内存的调度,作业具有等待（从外存进入内存执行）、装入（在内存可执行)、结束（运行结束，退出内存)三种状态.(为了简化，不考虑cpu的调度与切换，运行时间为作业在内存中驻留的时间）；5.能够自动进行内存分配与回收，可根据需要自动进行紧凑与拼接操作,所有过程均有动态图形变化的显示;6.采用可视化界面,可随时暂停显示当前内存分配和使用情况图。2程序总的功能说明：本程序可以从界面直接输入作业并进行动态的内存分配,也可以自动地生成作业文件并自行调度进行内存分配，每次分配可以选择两种算法（首次适应算法和循环首次算法）中的一种，每次作业结束后可以进入操作主界面进行再次作业的操作。3程序各模块的功能说明：（1） 界面显示函数：showInterface（PL p,Job job)；显示操作界面showJob(Job job）；显示作业链表；showPartitiion(PL pl)显示分区链表（2） 执行练习的功能函数:copyJob(Job p）；作业链表复制函数函数InitpartitionList(PL &p）；链表初始化分区函数函数CreateJoblist(Job &job,int count）;创建作业链表函数InsertNode(Job p，Job job）；按时间顺序创建链表函数InitpartitionList(PL &p）；初始化分区链表函数（3）文件函数 openFile(）；打开文件函数 ReadFile()；读取文件函数RandomParameter(）；随即参数读入文件函数 main()/主函数4程序设计的流程图 : 总体设计流程图:动态分区分配界面作业生成退出操作界面输入自动生成文件生成方式12 3分配方式首次适应循环首次适应应123作为一个整体首次适应算法：开始接受作业作业n-执行进入内存回收释放空间结束Intime=timeWaitingjobstate （0或1） 空闲分区状态 （0或1）n=0作业等待序列YNYNY0010回收函数:回收函数回收区在空闲分区前不连接回收连接回收回收区在空闲分区间回收区在空闲分区后5程序操作说明书及结果在vc+6.0环境中运行本程序,先进行编译，然后再进行链接，在进行执行将会出现显示界面。按照显示界面上显示的提示进行操作，就可以实现相应的功能：1。运行进入操作主界面：6源程序清单include#include includestdio.h#includestdlib.h#include windows.hdefine MemorySize 100/为空闲分区分配的最大空间（按题目要求）int workload；/输入作业的数量；typedef struct jobListint id;/ 作业的name int size；/ 作业大小（需要的存储空间大小) int intime； /进入时间int runtime； /运行时间int state； /作业的状态(0表示等待，1表示执行，2表示结束并释放）struct jobList *next;/ 作业链表指针 Job；typedef struct partitionListint id;int startAddress;/分区起始地址 int size；/分区大小int state； /分区的状态struct partitionList *prior；struct partitionList *next；/ 分区链表指针 *PL；FILE *fp;/*打开文件*/void openFile（）if(（fp=（fopen（”D:作业文件.txt”,”w”)）=NULL)printf（”无法打开文件!n”)；exit(0）；/*读取文件*/void ReadFile()if（(fp=(fopen(D:作业文件。txt，”r)）=NULL)printf（”无法打开文件!n”);exit（0）；/*将随机产生进程的参数写入文件*/void RandomParameter（）openFile（);for（int i=0;iworkload；i+）fprintf（fp,d %d d %d %dn，i+1,rand（）80，rand(）20,rand(）10+1,0);fclose（fp)；/*显示分区函数*/void showPartitiion(PL pl)printf（”t*n”）；printf(”t StartAddrtidtsize state n”)；printf(”t*n）;while（pl)printf（t* %dtt%dtdtd ”，plstartAddress，plid,plsize,pl-state）；printf(n”)；pl=pl-next;printf(t*n）;Sleep(1000)；if（kbhit(）=1）system(“pause”);/*按进入时间顺序创建一个作业链表*/void InsertNode（Job p,Job &job） /将创建的新结点插入到链表中Job q1,q2;q1=job;q2=job-next;int i=0;if(！q2)p-next=q2；q1-next=p; while(q2！=NULLq2intimep-intime）q1=q2;q2=q2next;i=1;if（！q2&i=1）p-next=q2；q1-next=p;if(q2！=NULLp-intimeintime）p-next=q2;q1-next=p;Job CreateJoblist(Job job,int count）/创建作业链表job=（Job）malloc(sizeof(jobList)）;if（!job）exit（0);job-next=NULL;Job p；printf(idtsizetintimetruntimen”)；for(int i=0；icount;i+)p=(Job)malloc（sizeof(jobList）；if（!p)exit(0）；scanf(”dtdtdtd”，pid,p-size，&pintime，&p-runtime）;pstate=0；if(p-size100）printf(作业过大不能为之分配内存，请重新输入的作业：n); scanf（%dtdtdt%d”，&p-id,&p-size，&p-intime，p-runtime); p-state=0； InsertNode(p，job）; else InsertNode(p,job）；return job；/*从外部文件读入数据并进行作业初始化*/Job ReadInitJob（Job &job)ReadFile();job=(Job）malloc（sizeof(jobList)；if（!job）exit（0）；job-next=NULL；Job p；for(int i=0；iworkload;i+)p=（Job）malloc(sizeof（jobList）;if（！p）exit（0）;fscanf(fp,%d %d d %d d，&pid，&p-size,&pintime,pruntime，&p-state); InsertNode(p,job)；return job；/*初始化分区链表*/PL InitpartitionList(PL p）p=(PL)malloc(sizeof(partitionList）);if(！p)exit（0）;p-size=MemorySize；printf（”输入分区首地址：);scanf（”d，&pstartAddress）;p-state=0；p-id=0;p-next=NULL；p-prior=NULL;return p；/*将一个作业链表复制到另一个链表*/Job copyJob(Job p） Job q,L，s=p，r；L=(Job)malloc（sizeof(jobList)）；Lnext=NULL；r=L；s=snext;while（s) q=(Job)malloc（sizeof（jobList)）;qid=sid；q-state=0;qintime=s-intime;q-runtime=s-runtime；qsize=ssize;rnext=q；qnext=NULL；r=q；s=snext;return L;/*将一个分区链表复制到另一个链表*/PL copypartition(PL p）PL q，L,s=p，r；L=（PL）malloc（sizeof(partitionList）)；L-next=NULL；r=L;s=snext;while（s) q=（PL)malloc（sizeof(partitionList);q-size=s-size；qstartAddress=sstartAddress；qstate=s-state；rnext=q；qnext=NULL；r=q;s=s-next;return L；/*作业链表*/void showJob(Job job）job=job-next;printf（n将作业按进入时间排序表示：n”)；printf(”t*n”）;printf（”t* idtsizetintimetruntimetstate n）;printf(t*n”）;while（job）printf(”t dt%dt%dtdtd *”,job-id，jobsize,job-intime,jobruntime,job-state）；printf(n)；job=jobnext；printf（”t*n”）;printf（”n）；/*回收内存*/void Recover（PL pl3，PL &pl)while(pl3) if（pl3-state=0） if（pl3next&pl3priorpl3prior-state=0&pl3-nextstate=1）pl3size+=pl3-priorsize; pl3-startAddress=pl3prior-startAddress;pl3state=0；pl3id=0； if（pl3priorprior） pl3-priorpriornext=pl3; pl3prior=pl3-prior-prior；else pl3prior=pl3prior-prior；pl=pl3;pl3=pl；else if(pl3-prior&pl3-nextpl3-nextstate=0&pl3-prior-state=1）pl3-size+=pl3-next-size;pl3state=0;pl3-id=0；if(pl3next-next)pl3next-nextprior=pl3；pl3-next=pl3-next-next;elsepl3next=pl3-nextnext；else if(！pl3-prior） if（pl3-nextstate=0)pl3size+=pl3-nextsize;pl3state=0;pl3id=0; if（pl3-nextnext）pl3nextnextprior=pl3；pl3-next=pl3next-next;elsepl3state=0;else if（！pl3next)if（pl3prior-state=0)pl3size+=pl3priorsize；pl3-state=0；pl3id=0；pl3-startAddress=plstartAddress; if（pl3-priorprior)pl3priorpriornext=pl3; pl3prior=pl3prior-prior；elsepl3-prior=NULL;pl=pl3;pl3=pl；elsepl3-state=0;else if（pl3nextpl3prior&pl3nextstate=0&pl3prior-state=0)pl3-size=pl3-size+pl3next-size+pl3prior-size；pl3-state=0；pl3-id=0；pl3startAddress=pl3prior-startAddress；if（pl3next-next)pl3nextnextprior=pl3；if（pl3priorprior）pl3-priorpriornext=pl3;pl3-next=pl3next-next;pl3prior=pl3priorprior;elsepl3-next=pl3-nextnext；pl3-prior=pl3prior-prior;pl=pl3;pl3=pl;pl3=pl3next；/*首次适应算法*/void CycleFirstFit(PL pl，Job job)int t=0；int n=workload;while(t+1&n）PL pl1=pl,pl2;printf（时钟:%dn”,t);Job job1=job；job1=job1next;Job j1=job;j1=j1next;Job j2=job;j2=j2next;Job j3=job;j3=j3-next;PL pl3=pl；while(j2)if（j2-intime+j2runtime=t)printf（”作业id:d运行结束，释放内存！,j2id);n=n-1；j2state=2；showJob(job)；showPartitiion(pl);j2=j2next；while(j1)if(j1intime=t）printf(”作业id：d开始运行,对其分配！,j1id）;j1-state=1;j1=j1-next；while（job1)if（t=job1-intime)while（pl1&（pl1sizestate=1）) pl1=pl1next；if（pl1)pl2=(PL)malloc(sizeof(partitionList)）;pl2-startAddress=pl1-startAddress+job1size;pl2state=0;pl2-id=0;pl2-size=pl1size-job1size;if(pl2-size5）pl1size=job1size;pl1state=1；pl1id=job1-id;if（pl1next）pl1next-prior=pl2；pl2next=pl1-next;pl2-prior=pl1；pl1-next=pl2；pl1=pl；elsepl1state=1;pl1id=job1-id;showJob（job)；showPartitiion（pl);elseprintf（”内存不足,将作业:d置于等待状态！等待内存释放在进行分配!n”，job1-id）；Job j=job1;while(j）j-intime+=1;jstate=0;j=jnext;Job jj=job;jj=jj-next;while(jj）if(jjstate=2)while（pl3)if（pl3id=jjid)pl3-state=0;pl3=pl3-next;jj=jjnext;pl3=pl；Recover（pl3，pl)；job1=job1-next;t=t+1；Sleep（500);PL p=pl；while（p)p-state=0;p=p-next;showJob(job)；showPartitiion（pl);printf(”所有进程分配完毕！n）；/*循环首次算法*/void FirstFit(PL pl，Job job）int t=0；int n=workload；while（t+1&n)PL pl1=pl，pl2;printf(时钟：dn，t）；Job job1=job;job1=job1-next；Job j1=job；j1=j1next;Job j2=job;j2=j2next；Job j3=job;j3=j3next;PL pl3=pl;while(j2）if(j2intime+j2runtime=t）printf(作业id:%d运行结束,释放内存!n”,j2id);n=n-1；j2state=2；pl3=pl；while(pl3）if(pl3id=j2-id）pl3state=0;pl3=pl3-next；showJob（job）;showPartitiion（pl)；/进程运行结束时进行内存回收j2=j2-next;while(j1)if(j1-intime=t）printf（作业id：d开始运行,对其进行分配!,j1-id）；j1-state=1；j1=j1-next；while(job1)if（t=job1intime）while（pl1&(pl1-sizenext；if(pl1)pl2=(PL）malloc(sizeof(partitionList）)；pl2startAddress=pl1startAddress+job1-size；pl2state=0；pl2id=0；pl2size=pl1-sizejob1-size;if（pl2size=5)/碎片最大值设为 5pl1size=job1-size；pl1-state=1;pl1-id=job1id;if(pl1next）pl1nextprior=pl2；pl2-next=pl1next；pl2-prior=pl1；pl1-next=pl2;pl1=pl；elsepl1state=1；pl1-id=job1-id；showJob(job)；showPartitiion（pl）;elseprintf（内存不足，将作业：%d置于等待状态!等待内存释放在进行分配!n”,job1id);Job j=job1;while（j）jintime+=1;jstate=0；j=jnext;pl3=pl;Recover（pl3，pl)；job1=job1-next;t=t+1;Sleep（500）；PL p=pl；while（p）pstate=0;p=pnext；showJob（job);showPartitiion(pl)；printf（”所有进程分配完毕！n”）;/*界面显示*/void showInterface(PL p，Job job）int a，con=0;Job j1,j2；while(1）printf(t1。首次适应nn); printf（”t2。循环首次适应nn”）； printf(t3.退出n请选择：n”）；if(con=0con=1）scanf（”d,&a)；switch（a）case 1:InitpartitionList(p）;j1=copyJob(job）; FirstFit（p，j1); break；case 2:InitpartitionList（p)；j2=copyJob（job）；CycleFirstFit( p，j2)； break; case 3:exit（0）;break；printf（重新选用算法（输入1),退出本次作业操作（输入3)n”）； scanf(%d,&con); if（con=1）