《操作系统磁盘分配》由会员分享，可在线阅读，更多相关《操作系统磁盘分配（27页珍藏版）》请在金锄头文库上搜索。
1、一 动态分区分配方式的模拟1.1 题目要求要求：用 C 语言或 C+语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。假设初始状态如下，可用的内存空间为640KB，并有下列的请求序列；作业 1 申请 130KB 作业 2 申请 60KB 作业 3 申请 100KB 作业 2 释放 60KB 作业 4 申请 200 KB 作业 3 释放 100 KB 作业 1 释放 130 KB 作业 5 申请 140 KB 作业 6 申请 60 KB 作业 7 申请 50KB
2、作业 6 释放 60 KB 请分别采用首次适应算法和最佳适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。1.2 设计思想根据题目要求，要用首次适应算法和最佳适应算法分别实现内存的动态分区，因此先介绍一下这两种算法的基本思想：首次适应算法中，空闲分区链是按地址递增的次序链接的，当要分配内存空间时，就查表，在各空闲分区中查找满足大小要求的可用块，只要找到第一个足名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 27 页 -2 以满足要求的空间就停止查找，并把它分配出去，如果该空闲空间与所需空间大小一样，则将该分区的状态改为1，即已被分配，若还有剩余，则将
3、剩余空间重新划为一个空闲分区，有新的起始地址，状态为0。最佳适应算法的空闲链是按照空闲块的大小为序、按增量方式排列的，即小块在前，大块在后，它在满足需要的前提下，尽量分配最小的空闲块，这样每次查找分配时第一次找到的能满足要求的必然的最佳的，若空闲空间大小与要分配的大小相差不多时，可直接将其状态改为1 即可，若有剩余，则将剩余空闲空间重新划分为一个空闲区，并根据空闲区的大小对链表进行重新排序。首次适应算法的回收过程相对简单，因为分区链是按照地址顺序链接的，因此释放内存时只需要判断要释放的分区前后是否也为空闲区，然后根据情况看是要跟前边或后边或前后都合并为一个大的空闲区，如果前后分区都已分配，则直
4、接将该分区状态改为0 即可。最佳适应算法回收时，因为它的分区链是按照空间大小排列的，因此不仅要看要释放分区前后是否为空闲，还要判断其地址是否前后相接，若地址不相接，则即使要释放分区前后均为空闲区，也不能进行合并，而且每次释放后要根据释放空间的大小对链表进行重新排序。1.3 数据结构动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所示：struct memory struct memory*former;/前向指针int address;/分区起始地址int num;/作业号int si
5、ze;/分配内存大小int state;/状态字struct memory*next;/后向指针名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 27 页 -3;前向指针和后向指针分别用于与当前分区的前后分区相链接，address 用于说明当前分区的起始地址，状态字为 0 时表示当前分区空闲，为 1 时表示已分配，num为分配的作业号，size表示分配的内存大小。1.4 各模块算法流程图1.4.1 分配算法详细流程图见图 5.1.1，其中各个条件分别为：P1:ptr-next=NULL P2:ptr-size=assign-size P3:current!=NULL P4:curr
6、ent-size=assign-size¤t-state=0 P5:ptr-size=assign-size P6:(ptr-next)-next!=NULL&is_optimist=true 1.4.2 回收算法详细流程图见图 5.1.2 若为首先适应算法回收，则各条件分别为：P1:current!=NULL P2:current-state=1¤t-num=i P3:current=NULL P4:current-next=NULL P5:previous-state=0 P6:(current-next)-next=NULL P7:previous-state=0
7、&(current-next)-state=0 P8:(current-next)-state=0 P9:is_optimist=true 若为最佳适应算法，则各条件分别为：P1:current!=NULL P2:current-state=1¤t-num=i P3:current=NULL P4:current-next=NULL P5:previous-state=0&(previous-address+previous-size)=current-addr ess)P6:(current-next)-next=NULL P7:previous-state=0&(current
8、-next)-state=0&(previous-address+pr evious-size)=current-address)&(current-size+current-address)=(c名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 27 页 -4 urrent-next)-address)P8:(current-next)-state=0&(current-size+current-address)=(current-next)-address)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 27 页 -5 开始传入参数P1 P2 P3 P4 指针后移
9、分配空间P5 分配空间空间不足分配空间空间不足P6 链表排序结束T F T F F T F T F T T 图 5.1.1 F 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 27 页 -6 开始传入参数P1 P2 指针后移P3 内存无作业P4 P5 合并释放处于链尾释放空间处于链尾P6 P7 合并释放处于链尾P5 合并释放P8 合并释放处于链尾释放内存P7 合并释放P5 合并释放P8 合并释放释放内存P9 排序链表结束图 5.1.2 F T F T F T F T F T F F T F T T F T F T F F T F T 名师资料总结-精品资料欢迎下载-名师精心整理-
10、第 6 页，共 27 页 -7 1.5 程序清单1.5.1 程序源代码程序如下所示：#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;/内存允许的最小空闲块的大小bool is_o
11、ptimist;/判断是否是最佳适应算法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*);/按空间大小将作业顺序插入到内存链void pr
12、int(MEMORY*);/打印内存链void main()/主函数int i=0;while(1)/选择算法cout(nPlease select a number(1,2,0);cout(n 1-首次适应算法);coutn 2-最佳适应算法 endl;cout 0-中止程序 i;if(i=1)/首次适应算法cout(n 以下为首次适应算法:n);名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 27 页 -8 is_optimist=false;init();exec();if(i=2)/最佳适应算法coutsize=640;mem-former=0;mem-next=0;vo
13、id 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);else free_optimist(mem,m);else if(k=0)/回滚到选择算法的步骤break;void F_F(int i)名师资料总结-精品资料欢迎下载-名师精心整理-
14、第 8 页，共 27 页 -9 /依次初始化每个作业,并根据相应算法对作业分配内存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;running-num=i;/i 从 1 开始循环running-size=worki;/指定作业大小running-state
15、=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-next;if(current=NULL)cout内存中没有任何作业！next=NULL)/当前作业为内存中最后一个作业if(previous-state
16、=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&(current-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=curren
