《操作系统大作业.doc》由会员分享，可在线阅读，更多相关《操作系统大作业.doc（24页珍藏版）》请在金锄头文库上搜索。
1、 序号 2010-2011学年度第二学期大作业课程名称： 操作系统 任课教师： 解晓萌 作业题目： 动态内存分区分配方式模拟 姓名： 陈卫兵 学 号： 200704601013002 专 业： 计算机科学与技术 教学中心： 本院 联系电话： 13570392215 评审日期_成绩_评审教师(签名)_华南理工大学网络教育学院 目 录1 题目要求12 设计思想13 数据定义24 处理流程35 源程序66 运行结果157 设计体会22 “计算机操作系统”课程设计大作业 动态内存分区分配方式模拟课程：操作系统班级：07春 计算机科学与技术学号：200704601013002姓名：陈卫兵手机：13570
2、3922151题目要求假设初始态下，可用内存空间为640K，并有下列请求序列，请分别用首次适应算法和最佳适应算法为作业分配和回收内存块，并显示出每次分配和回收后的空闲分区链的情况来以及内存占用情况图。作业1申请130K作业2申请60K作业3申请100k作业2释放60K作业4申请200K作业3释放100K作业1释放130K作业5申请140K作业6申请60K作业7申请50K作业6释放60K2设计思想根据题目要求，要用首次适应算法和最佳适应算法分别实现内存的动态分区，因此先介绍一下这两种算法的基本思想：首次适应算法中，空闲分区链是按地址递增的次序链接的，当要分配内存空间时，就查表，在各空闲分区中查找
3、满足大小要求的可用块，只要找到第一个足以满足要求的空间就停止查找，并把它分配出去，如果该空闲空间与所需空间大小一样，则将该分区的状态改为1，即已被分配，若还有剩余，则将剩余空间重新划为一个空闲分区，有新的起始地址，状态为0。最佳适应算法的空闲链是按照空闲块的大小为序、按增量方式排列的，即小块在前，大块在后，它在满足需要的前提下，尽量分配最小的空闲块，这样每次查找分配时第一次找到的能满足要求的必然的最佳的，若空闲空间大小与要分配的大小相差不多时，可直接将其状态改为1即可，若有剩余，则将剩余空闲空间重新划分为一个空闲区，并根据空闲区的大小对链表进行重新排序。首次适应算法的回收过程相对简单，因为分区
4、链是按照地址顺序链接的，因此释放内存时只需要判断要释放的分区前后是否也为空闲区，然后根据情况看是要跟前边或后边或前后都合并为一个大的空闲区，如果前后分区都已分配，则直接将该分区状态改为0即可。最佳适应算法回收时，因为它的分区链是按照空间大小排列的，因此不仅要看要释放分区前后是否为空闲，还要判断其地址是否前后相接，若地址不相接，则即使要释放分区前后均为空闲区，也不能进行合并，而且每次释放后要根据释放空间的大小对链表进行重新排序。3数据定义动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所
5、示：struct memory struct memory *former; /前向指针 int address;/分区起始地址 int num;/作业号 int size;/分配内存大小 int state;/状态字 struct memory *next; /后向指针;前向指针和后向指针分别用于与当前分区的前后分区相链接，address用于说明当前分区的起始地址，状态字为0时表示当前分区空闲，为1时表示已分配，num为分配的作业号，size表示分配的内存大小。4处理流程分配算法详细流程图见图5.1.1，其中各个条件分别为：P1: ptr-next=NULLP2: ptr-size=assi
6、gn-sizeP3: current!=NULLP4: current-size=assign-size¤t-state=0P5: ptr-size=assign-sizeP6: (ptr-next)-next!=NULL&is_optimist=true回收算法详细流程图见图5.1.2若为首先适应算法回收，则各条件分别为：P1: current!=NULLP2: current-state=1¤t-num=iP3: current=NULLP4: current-next=NULLP5: previous-state=0P6: (current-next)-next=
7、NULLP7: previous-state=0&(current-next)-state=0P8: (current-next)-state=0P9: is_optimist=true若为最佳适应算法，则各条件分别为：P1: current!=NULLP2: current-state=1¤t-num=iP3: current=NULLP4: current-next=NULLP5: previous-state=0&(previous-address+previous-size)=current-address)P6: (current-next)-next=NULLP7: p
8、revious-state=0&(current-next)-state=0&(previous-address+previous-size)=current-address)&(current-size+current-address)=(current-next)-address)P8:(current-next)-state=0&(current-size+current-address)=(current-next)-address)开始传入参数P1P2P3P4指针后移分配空间P5分配空间空间不足分配空间空间不足P6链表排序结束TFTFFTFTFTT图5.1.1F开始传入参数P1P2指
9、针后移P3内存无作业P4P5合并释放处于链尾释放空间处于链尾P6P7合并释放处于链尾P5合并释放P8合并释放处于链尾释放内存P7合并释放P5合并释放P8合并释放释放内存P9排序链表结束图5.1.2FTFTFTFTFTFFTFT TTFTFTFFTFT5源程序程序如下所示：#include #include using namespace std; struct memory struct memory *former; /前向指针 int address;/地址 int num;/作业号 int size;/分配内存大小 int state;/状态0表示空闲1表示已分配 struct memo
10、ry *next; /后向指针; typedef struct memory MEMORY; MEMORY *mem; const int size_min=10;/内存允许的最小空闲块的大小 bool is_optimist;/判断是否是最佳适应算法 void init(); /初始化内存块void exec();/执行相应算法void F_F(int); /依次初始化每个作业,并根据相应算法对作业分配内存void alloc(MEMORY *,MEMORY *);/分配内存算法（包括两种不同算法）void free(MEMORY *,int);/首次适应算法回收内存void free_op
11、timist(MEMORY *,int); /最佳适应算法回收内存void sort(MEMORY *);/对内存链进行排序 void insert(MEMORY *,MEMORY *); /按空间大小将作业顺序插入到内存链void print(MEMORY *);/打印内存链 void main() /主函数 int i=0; while(1) /选择算法 cout(华南理工大学“计算机操作系统”课程设计大作业n); cout(题 目：动态内存分区分配方式模拟n); cout(学生姓名：冯桥新n学生学号：200804692013001n); cout(n请输入一个数字(1,2,0); cout(n 1-首次适应算法); coutn 2-最佳适应算法endl; cout 0-中止程序i; if(i=1) /首次适应算法 cout(n以下为首次适应算法:n); is_optimist=false; init();exec(); if(i=2)/最佳适应算法 coutsize=640; mem-former=0; mem-next=0; void ex
