华南操作系统大作业.docx

1、华南操作系统大作业“计算机操作系统”动态内存分区分配方式模拟学生姓名专业名称学号目 录1 题目要求 12 设计思想 13 数据定义 24 处理流程 35 源程序 66 运行结果 157 设计体会 22动态内存分区分配方式模拟1题目要求假设初始态下，可用内存空间为640K，并有下列请求序列，请分别用首次适应算法和最佳适应算法为作业分配和回收内存块，并显示出每次分配和回收后的空闲分区链的情况来以及内存占用情况图。作业1申请130K作业2申请60K作业3申请100k作业2释放60K作业4申请200K作业3释放100K作业1释放130K作业5申请140K作业6申请60K作业7申请50K作业6释放60K

2、2设计思想根据题目要求，要用首次适应算法和最佳适应算法分别实现内存的动态分区，因此先介绍一下这两种算法的基本思想：首次适应算法中，空闲分区链是按地址递增的次序链接的，当要分配内存空间时，就查表，在各空闲分区中查找满足大小要求的可用块，只要找到第一个足以满足要求的空间就停止查找，并把它分配出去，如果该空闲空间与所需空间大小一样，则将该分区的状态改为1，即已被分配，若还有剩余，则将剩余空间重新划为一个空闲分区，有新的起始地址，状态为0。最佳适应算法的空闲链是按照空闲块的大小为序、按增量方式排列的，即小块在前，大块在后，它在满足需要的前提下，尽量分配最小的空闲块，这样每次查找分配时第一次找到的能满足

3、要求的必然的最佳的，若空闲空间大小与要分配的大小相差不多时，可直接将其状态改为1即可，若有剩余，则将剩余空闲空间重新划分为一个空闲区，并根据空闲区的大小对链表进行重新排序。首次适应算法的回收过程相对简单，因为分区链是按照地址顺序链接的，因此释放内存时只需要判断要释放的分区前后是否也为空闲区，然后根据情况看是要跟前边或后边或前后都合并为一个大的空闲区，如果前后分区都已分配，则直接将该分区状态改为0即可。最佳适应算法回收时，因为它的分区链是按照空间大小排列的，因此不仅要看要释放分区前后是否为空闲，还要判断其地址是否前后相接，若地址不相接，则即使要释放分区前后均为空闲区，也不能进行合并，而且每次释放

4、后要根据释放空间的大小对链表进行重新排序。3数据定义动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所示：struct memory struct memory *former; /前向指针 int address;/分区起始地址 int num;/作业号 int size;/分配内存大小 int state;/状态字 struct memory *next; /后向指针;前向指针和后向指针分别用于与当前分区的前后分区相链接，address用于说明当前分区的起始地址，状态字为0时表示当

5、前分区空闲，为1时表示已分配，num为分配的作业号，size表示分配的内存大小。4处理流程分配算法详细流程图见图5.1.1，其中各个条件分别为：P1: ptr-next=NULLP2: ptr-size=assign-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: curr

6、ent-state=1¤t-num=iP3: current=NULLP4: current-next=NULLP5: previous-state=0P6: (current-next)-next=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=N

7、ULLP5: previous-state=0&(previous-address+previous-size)=current-address)P6: (current-next)-next=NULLP7: previous-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-add

8、ress)=(current-next)-address)5源程序程序如下所示：#include #include using namespace std; struct memory struct memory *former; /前向指针 int address;/地址 int num;/作业号 int size;/分配内存大小 int state;/状态0表示空闲1表示已分配 struct memory *next; /后向指针; typedef struct memory MEMORY; MEMORY *mem; const int size_min=10;/内存允许的最小空闲块的大小

9、 bool is_optimist;/判断是否是最佳适应算法 void init(); /初始化内存块void exec();/执行相应算法void F_F(int); /依次初始化每个作业,并根据相应算法对作业分配内存void alloc(MEMORY *,MEMORY *);/分配内存算法（包括两种不同算法）void free(MEMORY *,int);/首次适应算法回收内存void free_optimist(MEMORY *,int); /最佳适应算法回收内存void sort(MEMORY *);/对内存链进行排序 void insert(MEMORY *,MEMORY *); /

10、按空间大小将作业顺序插入到内存链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

11、=false; init();exec(); if(i=2) /最佳适应算法 coutsize=640; mem-former=0; mem-next=0; void exec()/执行算法 while(1) /选择申请或释放内存操作 cout*endl; cout申请内存请输入作业号（1-7）endl; cout释放内存请输入数字8endl; cout中止程序请输入数字0endl; cout*k; /根据k值选择相应的操作 if(k=1&k=7) F_F(k); if(k=8) int m; coutm; /选择相应的回收算法 if(is_optimist=false) free(mem,m

12、); else free_optimist(mem,m); else if(k=0) break; /回滚到选择算法的步骤void F_F(int i) /依次初始化每个作业,并根据相应算法对作业分配内存 int work=0,130,60,100,200,140,60,50;/作业序列，i从1开始（与作业号对应），因此从第一个开始存放作业值，第0个值为0，不是作业 MEMORY *running; running=(MEMORY *)malloc(sizeof(MEMORY); if(running!=NULL) running-former=NULL; running-address=0;

13、 running-num=i; /i从1开始循环 running-size=worki; /指定作业大小 running-state=0; /作业未分配 running-next=NULL; /根据相应算法为作业分配内存，详见alloc函数 alloc(mem,running); print(mem); coutendl; else cout没有足够的内存空间next; while(current!=NULL) /循环直到找到需要释放的作业位置 if(current-state=1¤t-num=i) break; previous=current; current=current-

14、next; if(current=NULL) cout内存中没有任何作业！next=NULL) /当前作业为内存中最后一个作业 if(previous-state=0) /与前一个相邻空闲区合并 previous-size=previous-size+current-size; previous-next=NULL; cout作业 num)释放 size)k 的空间state=0; cout作业 num)释放 size)k 的空间next)-next=NULL)/p6 /当前作业为倒数第二个作业(此种情况还是要单列出来讨论的否则会出现错误) if(previous-state=0&(curre

15、nt-next)-state=0) /p7 /释放的地址空间前后均为空闲区 previous-size=previous-size+current-size+(current-next)-size; previous-next=NULL; /与下边else（其他情况的不同之处） cout作业 num)释放 size)k 的空间state=0) /p5 /释放的地址空间前面有空闲块则把它和前面的合并 previous-size=previous-size+current-size; (current-next)-former=previous; previous-next=current-nex

16、t; cout作业 num)释放 size)k 的空间next)-state=0) /p8 /释放的地址空间后面有空闲块则把它和后面的空闲块合并 current-size=current-size+(current-next)-size; current-state=0; current-next=NULL; /与下边else（其他情况的不同之处） cout作业 num)释放 size)k 的空间state=0; cout作业 num)释放 size)k 的空间state=0&(current-next)-state=0) /p7 /所释放空间前后均为空闲区 previous-size=pre

17、vious-size+current-size+(current-next)-size; (current-next)-next)-former=previous; previous-next=(current-next)-next; cout作业 num)释放 size)k 的空间state=0) /p5 /释放的地址空间前面有空闲块则把它和前面的合并 previous-size=previous-size+current-size; (current-next)-former=previous; previous-next=current-next; cout作业 num)释放 size)

18、k 的空间next)-state=0) /p8 /释放的地址空间后面有空闲块则把它和后面的空闲块合并 current-size=current-size+(current-next)-size; current-state=0; (current-next)-next)-former=current; current-next=(current-next)-next; cout作业 num)释放 size)k 的空间state=0; cout作业 num)释放 size)k 的空间next=NULL) /内存没有作业运行 if(ptr-size=assign-size) /内存空间大于作业所需

19、空间，为内存分配空间 ptr-size=ptr-size-assign-size; assign-state=1; ptr-next=assign; assign-former=ptr; cout作业 num)申请size) k的内存空间endl; else cout没有足够的内存空间为作业num)分配next; while(current!=NULL) /当前区间不为空（最后一个区间的next为空），即没有循环到最后 /如果当前内存空间大于作业所需空间并且内存没有被分配 /则结束循环，当前current位置即为要插入的位置 if(current-size=assign-size¤

20、t-state=0) break; previous=current; /previous后移 current=current-next; if(current=NULL) /空闲链中没有为作业分配所需的空间，即释放的空闲区间小于要分配的作业空间 /不够用，则在所有作业后边另外再申请空闲区，如作业4 if(ptr-size=assign-size) /内存中还有足够没分配的空闲空间为此作业分配 /此时ptr指向内存上未分配空闲空间的起始地址 assign-address =640-(ptr-size); ptr-size=ptr-size-assign-size; assign-state=1

21、; assign-former=previous; previous-next=assign; cout作业 num)申请size) k的内存空间endl; else cout没有足够的内存空间为作业num)分配size-assign-size)num=assign-num; /划出与作业等同的空间 current-state=1; delete assign; cout作业 num)申请size) k的内存间size=current-size-assign-size; assign-state=1; assign-address=current-address+current-size; i

22、f(current-next=NULL) /此要分配的空间是空闲链的最后一个元素 assign-former=current; current-next=assign; else assign-next=current-next; (current-next)-former=assign; assign-former=current; current-next=assign; cout作业 num)申请size) k的内存空间next)-next!=NULL&is_optimist=true) sort(ptr);/排序由空闲块从小到大 void sort(MEMORY *ptr) /排序函数 MEMORY *temp=new MEMORY; temp-next=0; temp-former=0; while(ptr-next) if(ptr-