1568.动态分区管理系统 《操作系统原理》课程设计.doc

计算机科学与技术专业操作系统原理课程设计课题名称：动态分区管理系统 姓 名： 班 级： 学 号： 课程设计起止时间：2005年12月26日至12月30日指导教师： 成绩：课程设计任务书操作系统原理课程设计任务书设计题目：动态分区管理系统任务下达时间：2005年12月26日任务完成时间：2005年12月30日指导教师： 指导教师评语一、所得结果：二、存在问题：成绩评阅人一、设计原理 利用C程序设计语言在windows操作系统下模拟实现操作系统的动态分区存储管理的功能。一方面加深对计算机分区存储管理方式的理解，另一方面通过编程提高解决实际问题的能力。二、工作原理 分区管理是把内存划分成若干个大小不等的区域，除操作系统占用了一个区域之外，其余由多道环境下的各并发进程共享。分区管理的基本原理是给每一个内存中的进程划分一块适当大小的存储区，以连续存储各个进程的程序和数据，使各个进程得以并发执行。三、 详细设计（一）、主要系统函数说明1、设计合理的数据结构来描述存储空间1）对于未分配出去的部分，用空闲分区链表来描述。struct freeList int startAddress; /* 分区起始地址 */int size; /* 分区大小 */struct freeList *next; /* 分区链表指针 */2） 对于已经分配出去的部分，由装入内存的作业占据。struct usedList int startAddress; /* 分区起始地址 */int jobID; /* 分区中存放作业ID */struct usedList *next; /* 分区链表指针 */3） 作业组织成链表。struct jobListint id; /* 作业ID */int size; /* 作业大小（需要的存储空间大小） */int status; /* 作业状态 0 : new job ,1 : in the memory , 2 : finished . */struct jobList *next; /* 作业链表指针 */将存储空间分为空闲可占用两部分，在usedList中设jobID而不设size，可以在不增加空间复杂度（与freeList相比）的同时更方便的实现可变分区存储管理。尽管设置jobList增加了空间复杂度，但它的存在，使得该程序可以方便的直接利用D盘中的JOB文件。该文件可以认为是一个和其他进程共享的资源。通过这个文件，其他进程写入数据供读取。2、实现分区存储管理的内存分配功能，选择适应算法。 基本原理分析： 1）Best fit ：将空闲分区按大小从小到大排序，从头找到大小合适的分区。2）Worst fit：将空闲分区按大小从大到小排序，从头找到大小合适的分区。3）First fit：将空闲分区按起始地址大小从小到大排序，从头找到大小合适的分区。4）Last fit ：将空闲分区按起始地址大小从大到小排序，从头找到大小合适的分区。 可将空闲分区先做合适的排序后用对应的适应算法给作业分配存储空间。排序函数 order（ bySize为零则按分区大小排序，否则按分区起始地址；inc为零从小到大排序，否则从大到小排序；通过empty指针返回结果 ）。void order(struct freeList *empty,int bySize,int inc)struct freeList *p,*q,*temp;int startAddress,size;for(p = (*empty) -> next;p;p = p -> next) /* 按bySize和inc两个参数寻找合适的节点，用temp指向它 */for(temp = q = p;q;q = q -> next)switch(bySize)case 0 : switch(inc)case 0:if(q->size < temp->size)temp = q;break;default:if(q->size > temp->size)temp = q;break; break;default: switch(inc)case 0:if(q->startAddress < temp->startAddress)temp = q;break;default:if(q->startAddress > temp->startAddress)temp = q;break; break; /* 交换节点的成员值 */ if(temp != p) startAddress = p->startAddress;size = p->size;p->startAddress = temp->startAddress;p->size = temp->size;temp->startAddress = startAddress;temp->size = size;3、实现分区存储管理的内存回收算法void insertFreeNode(struct freeList *empty,int startAddress,int size)插入回收的空节点分区，处理回收分区与空闲分区的四种邻接关系。struct freeList *p,*q,*r; for(p = *empty;p -> next;p = p -> next) ; /* 处理链表尾部的邻接情况 */if(p = *empty | p -> startAddress + p -> size < startAddress)/* 与尾部不相邻*/makeFreeNode(&r,startAddress,size); /* 通过r指针返回创建的空闲节点*/r -> next = p -> next; /* 插入独立的空闲节点 */p -> next = r;return ;if(p -> startAddress + p -> size = startAddress) /* 与尾部上邻 */p -> size += size; /* 合并尾部节点 */return ;q = (*empty) -> next; /* 处理链表首节点的邻接情况 */if(startAddress + size = q -> startAddress) /* 与首节点下邻 */q -> startAddress = startAddress; /* 合并首节点 */q -> size += size;else if(startAddress + size < q -> startAddress) /* 与首节点不相邻 */makeFreeNode(&r,startAddress,size);r -> next = (*empty) -> next;(*empty) -> next = r;else /* 处理链表中间的邻接情况 */while(q -> next && q -> startAddress < startAddress)p = q;q = q -> next;if(p -> startAddress + p -> size = startAddress && q -> startAddress = startAddress + size) /* 上下邻，合并节点 */p -> size += size + q -> size;p -> next = q -> next;free(q); /* 删除多余节点 */else if(p -> startAddress + p -> size = startAddress && q -> startAddress != startAddress + size) /*上邻，增加节点的大小*/p -> size += size;else if(p -> startAddress + p -> size != startAddress && q -> startAddress = startAddress + size) /* 下邻 */q -> startAddress = startAddress; /* 修改节点起始地址 */q -> size += size; /* 修改节点的大小 */else /* 上下不相邻 */makeFreeNode(&r,startAddress,size);r -> next = p -> next;p -> next = r;4、当碎片产生时，进行碎片的拼接。5、空闲分区队列显示：int showFreeList(struct freeList *empty)6、作业占用链表显示：int showUsedList(struct jobList *jobs,struct usedList *used) 从头到尾显示used链，同时通过其中的作业ID在jobs中查对应的大小7、从输入作业到D盘的JOB文件：void inputJob(void)8、从JOB文件中读出作业并创建作业链表：int makeJobList(struct jobList *jobs)9、显示作业链表：int showJobList(struct jobList *jobs) 10.更新作业链表中作业的状态： int updateJobFile(struct jobList *jobs)11.根据作业链表更新JOB文件： int updateJobFile(struct jobList *jobs) 12.为作业分配存储空间、状态必须为0：int allocate(struct freeList *empty,int size) 13.结束一个作业号为id的作业，释放存储空间（由*startAddress返回空间的起始地址）：int finishJob(struct usedList *used,int id,int *startAddress)14.插入释放的空间到used链表中（作业号为id，startAddress由函数13返回）：void insertUsedNode(struct usedList *used,int id,int startAddress)15.获取作业的信息： void getJobInfo(struct jobList *jobs,int id,int *size,int *status)16.初始化存储空间起始地址、大小：void iniMemory(void)17.选择适应算法：char selectFitMethod(void)18.根据参数startAddress、size创建空闲节点，由empty指针返回：void makeFreeNode(struct freeList *empty,int startAddress,int size)19.以要求的方式打开文件：void openFile(FILE *fp,char *filename,char *mode)20.出现严重错误时显示信息并结束程序；void errorMessage(void)（二）、程序流程图创建分区头节点删除上次的结果文件输入键盘字符step step=1字符step为？Initializiation step=2Put job into memorystep=7Move fragment togetherstep=6step=3 step=4 Finish jobstep=5Show current memory used by jobsShow current free listExit四、 运行结果五、 分析结果本次设计的题目是动态分区存储管理，经调试后成功。动态分区的在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变。改变了固定分区法中那种即使是小作业也要占据大分区的现象，从而提高了内存的利用率。六、 调试步骤1、Initializiation.按顺序利用了openFile()、iniMemory()、makeFreeNode()inputJob()、makeJobList()、allocate()insertUsedNode()selectFitMethod()等自编函数.2 、Put job into memory(allocate memory)按顺序利用了showJobList()（选手动逐个为作业分配存储空间时）、openFile()、order()、allocate()、errorMessage()、insertUsedNode()、updateJobStatus()、updateJobFile()函数3、Finish job(reuse memory)按顺序利用了openFile()、showUsedList()、getJobInfo()、insert FreeNode()、updateJobStatus()、updateJobFile()、errorMessage()等自编函数。4、Show current free list 按顺序利用了openFile()、showFreeList()函数。5、Show current memory used by jobs按顺序利用了openFile()、showUsedList()函数。6、Move fragment together按顺序利用了openFile()、moveFragment()函数。7、Exit按顺序利用了openFile()、exit(0)函数。通过这次课程设计我练习了用C语言编写系统软件，对操作系统中的可变分区存储管理的原理及使用方法有了更深刻的了解。在这过程中也遇到了一些问题，通过查阅资料和询问老师得以解决。比如怎么更合理的设计数据结构时，我想了很多方法。后来在老师的帮助下选择了这个，还是很好的。还有为了使程序更完善，我尝试着将程序中的输入部分全部改为字符串。成功的避免了接受整型数据时输入字符后引起的错误，使程序能接受任何输入而正常结束。但是由于时间的关系，这个设计还有很多不够完善的地方需要以后进一步改善。七、 参考文献计算机操作系统教程（第二版） 清华大学出版社 张尧学 史美林编著操作系统习题解答与实验指导（第二版） 清华大学出版社操作系统实验教程 清华大学出版社 任爱华编操作系统原理及其使用 清华大学出版社 方今编操作系统原理 人民邮电出版社 孙忠秀编