动态分区分配存储管理报告.doc

淮北师范大学程序设计课程设计动态分区分配存储管理系统学 院 计算机科学与技术 专 业 计算机科学与技术 学 号 学 生 姓 名 指导教师姓名 2012年3月 20 日一、课题要求课程设计的目的：操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。l 进一步巩固和复习操作系统的基础知识。l 培养学生结构化程序、模块化程序设计的方法和能力。l 提高学生调试程序的技巧和软件设计的能力。l 提高学生分析问题、解决问题以及综合利用C 语言进行程序设计的能力。设计内容：用高级语言编写和调试一个动态分区内存分配程序，演示实现下列两种动态分区分配算法1. 首次适应算法2. 循环首次适应算法设计要求：1. 内存中有0-100M 的空间为用户程序空间，最开始用户空间是空闲的2. 作业数量、作业大小、进入内存时间、运行时间需要通过界面进行输入3. 可读取样例数据（要求存放在外部文件中）进行作业数量、作业大小、进入内存时间、运行时间的初始化4. 根据作业进入内存的时间，采用简单的先进先出原则进行从外存到内存的调度，作业具有等待（从外存进入内存执行）、装入（在内存可执行）、结束（运行结束，退出内存）三种状态。（为了简化，不考虑CPU 的调度与切换，运行时间为作业在内存中驻留的时间）5. 能够自动进行内存分配与回收，可根据需要自动进行紧凑与拼接操作，所有过程均有动态图形变化的显示6. 采用可视化界面，可随时暂停显示当前内存分配和使用情况图。设计结束需提交下列资料：1、课程设计报告。报告中至少应包括： 相关操作系统的知识介绍，程序总的功能说明、程序各模块的功能说明、程序设计的流程图、源程序清单。2、源程序和编译连接后的可执行程序文件。时间安排：分析设计贮备阶段（1 天）编程调试阶段（7 天）写课程设计报告、考核（2 天）二、算法的基本思想1、定义基本结构： 1作业结构： typedef struct JOB int num; /作业号 int size; /作业大小 int ctime; /作业进入时间 int rtime; /作业运行时间 int state; /作业状态Job;2)分区结构：typedef struct DuLNode int ID; /分区号 int start; /开始地址 int size; /大小 int state; /0=尚未使用 1=使用 2=释放 struct DuLNode *prior;/前驱指针 struct DuLNode *next; /后即指针DuLNode, * DuLinkList;2、基本操作：int Firstfit(int);/首次适应算法int Next_fit(int); /循环首次适应算法void showJob(int); /显示作业表void showPartiton(DuLinkList);/显示分区表DuLinkList InitpartitionList(DuLinkList &p);/初始化void huishou(DuLinkList pl3,DuLinkList &pl);/回收函数int Putin(int &n);/输入函数，输入作业相关信息3、首次适应算法 空闲分区链以地址递增的次序链接，分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，取消的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。4、循环首次适应算法 在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。三、主要功能模块流程图主函数：结束输出并继续选择21循环首次适应首次适应算法Switch输入作业信息、操作选择信息等开始3首次适应算法： 循环首次适应算法开始查找大小是否满足划分空间结束是指向下一个否开始查找大小是否满足划分空间，并记录当前位置结束作业？无回到链首有作业？指向下一个链尾？是否有无回到链首是否当前位置四、系统测试程序运行实例如下：1、输入界面，按要求输入：2、选择算法及分区首地址：3、运行结束后显示，并继续选择：五、源程序及系统文件使用说明#include #include #include #include #define Free 0#define Use 1#define MAX_length 100 /最大内存空间为100MB/-作业结构体数组-typedef struct JOBint num; /作业号int size; /作业大小int ctime; /作业进入时间int rtime; /作业运行时间int state; /作业状态Job;typedef struct DuLNodeint ID; /分区号int start; /开始地址int size; /大小int state; /0=尚未使用 1=使用 2=释放struct DuLNode *prior;/前驱指针struct DuLNode *next; /后即指针DuLNode, * DuLinkList;/-int Firstfit(int);/首次适应算法int Next_fit(int); /循环首次适应算法void showJob(int); /显示作业表void showPartiton(DuLinkList);/显示分区表/-/-全局变量-int f;Job *A; /排序前Job *a; /排序后Job *temp;/-功能函数-void delay()for(int x = 10000;x0;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)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-prior=pl3-prior-prior;else pl3-prior=pl3-prior-prior;pl=pl3;pl3=pl;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-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-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-prior=pl3-prior-prior;elsepl3-prior=NULL;pl=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 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-ne