动态分区分配算法-试验报告

1、操作系统实验报告实验二：动态分区分配算法学生：学号：学院：系别：专业：实验时间：报告时间：一、实验内容编写一个内存动态分区分配模拟程序，模拟内存的分配和回收的完整过程。一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时， 存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主

2、存空间的分配和回收。三、实验原理模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。(1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间， 若有,则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：操作系统作业1作业3空闲区作业205k10k14k26k32k512k空闲区为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：起址长度状态14K12K未分其中，起址一一指出一个空闲区的主存起始地

3、址。长度一一指出从起始地址开始的一个连续空闲的长度。状态有两种状态，一种是“未分配”状态， 指出对应的由起址指出的某个长度的区域是空闲区。配32K96K未分配3m栏第二栏(2)当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。(3)采用最先适应算法(顺序分配

4、算法)分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。(4)当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。(5)请按最先适应算法设计主存分配和回收的程序。假设初始时主存中没有作业，现按下面序列进行内存的申请与释放：作业1申请300K,作业2申请100K,作业1释放300K,作业

5、3申请150K,作业4申请30K,作业5申请40K,作业6申请60K,作业4释放30K。请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。四、实验报告(1)画出最先适应分配算法流程图、归还主存时的回收算法流程图。最先适应分配算法流程图：、是否/N归还主存时的回收算法流程图:输是输1w/改变输改变Y(2)程序中使用的数据结构及符号说明。答：本程序用C+语言编写，其中用到了class类、 指针， 利用指针将classTable(空闲表类)和classPro(作业类)用链式存储的方式进行插入、删除、新建、排序等工作。(3)打印一份源程序并附上注释。#in

6、clude#include(public:Pro()Size=0;next=NULL;Start=0;Name0=0;Pro(intSi,charNa)Size=Si;next=NULL;Start=0;classPro/作业对象strcpy(Name,Na);)voidprintf()(coutNametStartendl;)voidArrange(intSta,Pro&Ne)(Start=Sta;next=&Ne;)Pro*next;/用来指向下一个输入的作业intSize;作业大小charName10;/作业名称intStart;/在内存中存放的起始地址);classTa

7、ble/空闲表public:Table*next;/指向下一个空闲区块intSize;/空闲区块大小Table()Table(intSta,intSiz)Start=Sta;Size=Siz;Over=Sta+Siz;next=NULL;)intStart;/空闲区块起始地址intOver;/空闲区块结束地址)；voidPri(Pro*ph)(if(ph)(coutendl”内存中的作业endl作业名t起始地址next)p-printf();coutendl;)elsecout作业已全部运行完毕!next)cout,tStart,ttth-Sizeendl;coutendl;elsecout“

8、无空闲区块！next;Table*hf=h;Table*hf2=h;Table*hf1=h;if(p-Start=1000)return;for(;hf1;hf1=hf1-next)/检查新增空闲区块是否是原空闲区块(if(hf1-StartOver&hf1-Start=p-Start&hf1=h)h=h-next;elseif(hf1-StartOver&hf1-Start=p-Start)(hf2-next=hf1-next;)hf2=hf1;)if(!h)/检查有无空闲区块，当空闲区块是原空闲块时会去除重新分配(h=p；)else(if(h-next=NULL)p

9、-next=h;h=p;)else(for(;hp;hp=hp-next)(if(p-SizeSize)(p-next=hp;hf-next=p;break;)hf=h;)if(!hp)hf-next=p;)voidZJKX(Table*&h,Pro*p,Pro*pp)/空闲区块的改变intpos=p-Start+p-Size,jugy=0;Table*ph1=h;for(Table*ph=h;ph;ph=ph-next)if(ph-Start=pos)jugy=1;Table*pph1=h;Table*pph=h;for(;pph;pph=pph-next)if(pph-Over=p

10、-Start)/3(pph1-next=pph-next;ph1-next=ph-next;Table*n=newTable(pph-Start,ph-Size+pph-Size+p-Size);PX(h,n);break;)pph1=pph;)if(!pph)/4(ph-Size=ph-Size+p-Size;ph-Start=p-Start;PX(h,ph);)ph1=ph;)if(!jugy)(Table*pph1=h;for(Table*pph=h;pph&!jugy;pph=pph-next)(for(Pro*pp1=pp;pp1;pp1=pp1-next)if(p-Star

11、t=(pp1-Start+pp1-Size)2(for(Table*h2=h;h2;h2=h2-next)(if(p-Start+p-Size)=h2-Start)(Table*n=newTable(p-Start,p-Size+h2-Size);PX(h,n);jugy=1;break;)if(!jugy)Table*n=newTable(p-Start,p-Size);PX(h,n);jugy=1;break;)elseif(p-Start+p-Size)=pp1-Start)/1for(Table*h1=h;h1;h1=h-next)if(h1-Over=p-Start)(Table*n

12、=newTable(h1-Start,p-Size+h1-Size);PX(h,n);jugy=1;break;)if(!jugy)(*n=newTable(p-Start,p-Size);PX(h,n);jugy=1;break;pph1=pph;)if(!jugy)for(Table*pph=h;pph;pph=pph-next)Table/5if(pph-Over=p-Start)(pph-Size=pph-Size+p-Size;pph-Over=pph-Over+p-Size;PX(h,pph);break;if(!h)(Table*x=newTable(p-Start,p-Size

13、);h=x;)voidSF(Pro*&ph,charN口,Table*&h)/释放作业(intjugy=0;Pro*pp=ph;if(!strcmp(ph-Name,N)(ZJKX(h,ph,ph);ph=ph-next;jugy=1;elsefor(Pro*p=ph-next;p;p=p-next)(if(!strcmp(N,p-Name)/完成作业的删除：删除作业对象+增加空闲区块对象，并检查是否可以合并(ZJKX(h,p,ph);pp-next=p-next;jugy=1;)pp=p;)if(!jugy)cout队列中没有这个作业!next)/分割空if(p-SizeSi

14、ze)(p-Start=hp-Start;if(p-Start+p-Size=1000)(if(hpp=hp)h=NULL;elsehpp-next=NULL;jugy=1;else(hp-Size=hp-Size-p-Size;hp-Start=p-Start+p-Size;jugy=1;break;)if(jugy)(if(!ph)(ph=p；)else(for(;pp-next;pp=pp-next);作业队列尾部插入新作业对象pp-next=p;)elsecout没有足够的空间分配！endl;)intmain()(cout这是一个采用最先适应算法(顺序分配算法)分配主存空间的小测试。e

15、ndl;cout这里一共有1000kb内存可供使用，有三种选择：endl1、载入一个作业endl2、释放一个作业”endl0、结束测试endl;intchoice;Pro*ph=NULL;Table*head=newTable(0,1000);charNa10;intsize;while(1)coutchoice;if(choice=1)(coutNasize;Pro*p=newPro(size,Na);JR(ph,p,head);Pri(ph);Prik(head);elseif(choice=2)(coutNa;SF(ph,Na,head);Pri(ph);Prik(head);elsei

16、f(!choice)(Pri(ph);Prik(head);exit(0);)return0;)(4)打印程序运行时的初值和运行结果，要求如下这是一个采用最先适应算法（顺序分配算法）分配主存空间的小测试这里；共有邛即助内存可供使甫，肓三钟选择：繇一健脑输入盗滋择:1:1精菊入柞嵬名以及作业大小；作山300300空闲区块大小6 6阿sil空闲区块大小03000300空闲区块大小700700tttt地i i,0,0的IIIIflfl空闲区空闲区庆及作业大小：作业21002100选名里器.AIA-乙 25-刖青青此地业始1AJAJAnAnw.lw.l2 2大:1:1及圣以选名依午qaxs.cc主ui?Hurlrl一仲2 20 0 I I择称选名的业入.AMffl加主R R主E E7 7： 宾哈宾哈二一itKVf5KVf5/ /Q Q计三工收什“12112380380柞业3030?入?a作业大小作业430430空闲区块大小80806US6US;鬻簿睚鼠作业大小:作业660660空闲区块大小2s2s600600re7T.exe-空闲区块大小293060293060。0d00d0582582112112FKKE.圣I I配怕b b8 8分迟28402840I区区JP4JP42 2t