操作系统课程设计报告-主存空间的分配与回收.doc

操作系统课程设计报告学院：计算机科学与技术学院 专业：软件工程 班级：软件*班 姓 名*学 号*实验组*实验时间指导教师*成 绩实验项目名称主存空间的分配与回收实验目的通过该课程设计使我们理解在不同的存储管理方式下，如何实现主存空间的分配与回收。使学生初步具有研究、设计、编制和调试操作系统模块的能力实验内容及要求 设计要求： 1设计基于空闲区说明表的可变分区分配与回收算法； 2或设计基于空闲区链表的可变分区分配与回收算法； 3画出以上算法流程图； 4编程实现算法功能； 5编写课程设计说明书。 工作量要求：完成以上设计要求中的所有算法功能。实验环境硬件环境：Windows 7系统软件环境： VC+6.0开发工具总体设计本次课程设计中主要是模拟主存分配与回收，考虑到一个进程的五个状态，初始，就绪，等待，执行，终止五个状态，所以决定从一个进程的运行过程进行模拟，总体流程大致是首先创建一个进程即填写PCB信息，然后将进程送到后备集合，然后从后备集合从取出一个进程进行是分配。如果能分配，就将其送入就绪集合，然后从就绪集合中取出一个进程运行一个时间片（即一秒钟），接着将该进程送入就绪集合，如果运行时间减为零，就不送入就绪集合中。考虑到实际的需要，我添加了一个挂起状态，还添加了一个撤销进程函数，一个强制回收函数。在本次设计中用多线程模拟多进程，所以各个共享表都应该设置为线程安全的。程序框图及流程图程序框图： 程序流程图：主要源代码及注释#include#include#include#define OK 1 #define ERROR 0 typedef int Status;typedef struct node/定义一个空闲区说明表结构 int num; /分区序号 long start; /起始地址 long length; /分区大小 int state; /分区状态 char tag20;/作业名称job;typedef struct Node/ 线性表的双向链表存储结构 job data; struct Node *prior; /前趋指针 struct Node *next; /后继指针Node,*LinkList; LinkList first; /头结点LinkList end; /尾结点int flag;/记录要删除的分区序号Status Initblock()/开创带头结点的内存空间链表 first=(LinkList)malloc(sizeof(Node); end=(LinkList)malloc(sizeof(Node); first-prior=NULL; first-next=end; end-prior=first; end-next=NULL; end-data.num=1; end-data.start=0; end-data.length=600; end-data.state=0; strcpy(end-data.tag,无作业); return OK;void sort()/分区序号重新排序 Node *p=first-next,*q; q=p-next; for(;p!=NULL;p=p-next) for(q=p-next;q;q=q-next) if(p-data.num=q-data.num) q-data.num+=1; /显示主存分配情况void show() int flag=0;/用来记录分区序号 Node *p=first; p-data.num=0; p-data.start=0; p-data.length=0; p-data.state=1;strcpy(p-data.tag,); sort(); printf(ntt主存空间分配情况n); printf(*nn); printf(分区序号t作业名tt起始地址t分区大小t分区状态nn);p=p-next; while(p) printf(%dtt%stt%dtt%d,p-data.num,p-data.tag,p-data.start,p-data.length); if(p-data.state=0) printf(tt空闲nn); else printf(tt已分配nn); p=p-next; printf(*nn);/首次适应算法Status First_fit(int request,char name20) /为申请作业开辟新空间且初始化 Node *p=first-next; LinkList temp=(LinkList)malloc(sizeof(Node); temp-data.length=request; temp-data.state=1; strcpy(temp-data.tag,name); p-data.num=1; while(p) if(p-data.state=0)&(p-data.length=request) /有大小恰好合适的空闲块 p-data.state=1; return OK; break; else if(p-data.state=0) & (p-data.lengthrequest) /有空闲块能满足需求且有剩余 temp-prior=p-prior; temp-next=p; temp-data.start=p-data.start; temp-data.num=p-data.num; p-prior-next=temp; p-prior=temp; p-data.start=temp-data.start+temp-data.length; p-data.length-=request; p-data.num+=1; return OK; break; p=p-next; return ERROR;/最佳适应算法Status Best_fit(int request,char name20) int ch; /记录最小剩余空间 Node *p=first; Node *q=NULL; /记录最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node); temp-data.length=request; temp-data.state=1; strcpy(temp-data.tag,name); p-data.num=1; while(p) /初始化最小空间和最佳位置 if(p-data.state=0) & (p-data.length=request) ) if(q=NULL) q=p; ch=p-data.length-request; else if(q-data.length p-data.length)/找到最小插入空闲块 q=p; ch=p-data.length-request; p=p-next; if(q=NULL) return ERROR;/没有找到空闲块 else if(q-data.length=request)/相等字节写入 q-data.state=1; return OK; else/不相等，把节点插入链表 temp-prior=q-prior; temp-next=q; temp-data.start=q-data.start; temp-data.num=q-data.num; q-prior-next=temp; q-prior=temp; q-data.start+=request; q-data.length=ch; q-data.num+=1; return OK; return OK;/最差适应算法Status Worst_fit(int request,char name20) int ch; /记录最大剩余空间 Node *p=first-next; Node *q=NULL; /记录最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node); temp-data.length=request; temp-data.state=1; strcpy(temp-data.tag,name); p-data.num=1; while(p) /初始化最大空间和最佳位置 if(p-data.state=0 & (p-data.length=request) ) if(q=NULL) q=p; ch=p-data.length-request; else if(q-data.length data.length)/找到插入最大空闲快 q=p; ch=p-data.length-request; p=p-next; if(q=NULL) return ERROR;/没有找到空闲块 else if(q-data.length=request) q-data.length=1; return OK; else temp-prior=q-prior; temp-next=q; temp-data.start=q-data.start; temp-data.num=q-data.num; q-prior-next=temp; q-prior=temp; q-data.start+=request; q-data.length=ch; q-data.num+=1; return OK; return OK; /主存回收Status recovery(int flag) Node *p=first; for(;p!=NULL;p=p-next) if(p-data.num=flag) if(p-prior=first) if(p-next!=end)/当前P指向的下一个不是最后一个时 if(p-next-data.state=0) /与后面的空闲块相连 p-data.length+=p-next-data.length; p-next-next-prior=p; p-next=p-next-next; p-data.state=0;strcpy( p-data.tag,无作业); p-data.num=flag; else p-data.state=0; strcpy( p-data.tag,无作业); if(p-next=end)/当前P指向的下一个是最后一个时 p-data.state=0; strcpy( p-data.tag,无作业); /结束if(p-prior=block_first)的情况 else if(p-prior!=first) if(p-next!=end) deal1(p); else deal2(p); /结束if(p-prior!=block_first)的情况 /结束if(p-data.num=flag)的情况 printf(t*回收成功*); return OK; /主函数void main() int i; /操作选择标记 int a;/算法选择标记printf(*n); printf(tt用以下三种方法实现主存空间的分配n); printf(t(1)首次适应算法t(2)最佳适应算法t(3)最差适应算法n);printf(*n); printf(n); printf(请输入所使用的内存分配算法:); scanf(%d,&a); while(a3) printf(输入错误，请重新输入所使用的内存分配算法:n); scanf(%d,&a); switch(a) case 1:printf(nt*使用首次适应算法：*n);break; case 2:printf(nt*使用最佳适应算法：*n);break; case 3:printf(nt*使用最坏适应算法：*n);break; Initblock(); /开创空间表 while(1) show(); printf(t1: 分配内存t2: 回收内存t0: 退出n); printf(请输入您的操作：); scanf(%d,