动态分区分配算法 实验报告
操作系统实验报告
实验二:动态分区分配算法.
学生：
学号：
学院：
系别：
专业：
实验时间：
报告时间：
一、实验内容
编写一个内存动态分区分配模拟程序，模拟内存的分配和回收的完整过程。
一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。
三、实验原理
模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。
(1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：
为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：
第一栏
第二栏
其中，起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区。
(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。
(3) 采用最先适应算法（顺序分配算法）分配主存空间。
按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲
区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。
(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。
(5) 请按最先适应算法设计主存分配和回收的程序。假设初始时主存中没有作业，现按下面序列进行内存的申请与释放：
作业1申请300K，作业2申请100K，作业1释放300K，作业3申请150K，
作业4申请30K，作业5申请40K，作业6申请60K，作业4释放30K。
请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。
四、实验报告
(1) 画出最先适应分配算法流程图、归还主存时的回收算法流程图。
最先适应分配算法流程图：
归还主存时的回收算法流程图：
(2) 程序中使用的数据结构及符号说明。
答：本程序用c++语言编写，其中用到了class{}类、指针，利用指针将class Table{}(空闲表类)和class Pro{}(作业类)用链式存储的方式进行插入、删除、新建、排序等工作。
(3) 打印一份源程序并附上注释。
#include
#include
class Pro //作业对象
{
public:
Pro(){
Size=0;
next=NULL;
Start=0;
Name[0]='\0';
}
Pro(int Si,char Na[]){
Size=Si;
next=NULL;
Start=0;
strcpy(Name,Na);
}
void printf()
{
cout< } void Arrange(int Sta,Pro &Ne) { Start=Sta; next=&Ne; } Pro *next; //用来指向下一个输入的作业 int Size; //作业大小 char Name[10]; // 作业名称 int Start; //在内存中存放的起始地址 }; class Table //空闲表 { public: Table *next; //指向下一个空闲区块 int Size; //空闲区块大小 Table(){ } Table(int Sta,int Siz) { Start=Sta; Size=Siz; Over=Sta+Siz; next=NULL; } int Start; //空闲区块起始地址 int Over; //空闲区块结束地址 }; void Pri(Pro *ph) { if(ph) { cout< for(Pro *p=ph;p;p=p->next) p->printf(); cout< } else cout<<"作业已全部运行完毕！"< } void Prik(Table *h) { if(h) { cout<<"空闲区块分配情况"< for(;h;h=h->next) cout<<"\t"< cout< } else cout<<"无空闲区块！"< } void PX(Table *&h,Table *p) //排序顺序空闲区块 { Table *hp=h->next; Table *hf=h; Table *hf2=h; Table *hf1=h; if(p->Start==1000) return; for(;hf1;hf1=hf1->next) //检查新增空闲区块是否是原空闲区块 { if(hf1->Start h=h->next; else if(hf1->Start { hf2->next=hf1->next; } hf2=hf1; } if(!h) //检查有无空闲区块,当空闲区块是原空闲块时会去除重新分配 { h=p; } else { if(h->next==NULL) { p->next=h; h=p; } else { for(;hp;hp=hp->next) { if(p->Size { p->next=hp; hf->next=p; break; } hf=h; } if(!hp) hf->next=p; } } } void ZJKX(Table *&h,Pro *p,Pro *pp) //空闲区块的改变 { int pos=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->Start) //3 { pph1->next=pph->next; ph1->next=ph->next; Table *n=new Table(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->Start==(pp1->Start+pp1->Size)) //2 { for(Table *h2=h;h2;h2=h2->next) { if((p->Start+p->Size)==h2->Start) { Table *n=new Table(p->Start,p->Size+h2->Size); PX(h,n); jugy=1; break; } } if(!jugy) { Table *n=new Table(p->Start,p->Size); PX(h,n); jugy=1; break; } } else if((p->Start+p->Size)==pp1->Start) //1 { for(Table *h1=h;h1;h1=h->next) { if(h1->Over==p->Start) { Table *n=new Table(h1->Start,p->Size+h1->Size); PX(h,n); jugy=1; break; } } if(!jugy) { Table *n=new Table(p->Start,p->Size); PX(h,n); jugy=1; break; } } pph1=pph; } } if(!jugy) for(Table *pph=h;pph;pph=pph->next) //5 if(pph->Over==p->Start) { pph->Size=pph->Size+p->Size; pph->Over=pph->Over+p->Size; PX(h,pph); break; } if(!h) { Table *x=new Table(p->Start,p->Size); h=x; } } void SF(Pro *&ph,char N[],Table *&h) //释放作业 { int jugy=0; Pro *pp=ph; if(!strcmp(ph->Name,N)) { ZJKX(h,ph,ph); ph=ph->next; jugy=1; } else for(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<<"队列中没有这个作业!"< } void JR(Pro *&ph,Pro *p,Table *&h) //加入作业{ Pro *pp=ph; int jugy=0; //分割空闲区块Table *hpp=h; for(Table *hp=h;hp;hp=hp->next) { if(p->Size<=hp->Size) { p->Start=hp->Start; if(p->Start+p->Size==1000) { if(hpp==hp) h=NULL; else hpp->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; } } else cout<<"没有足够的空间分配！"< } int main() { cout<<"这是一个采用最先适应算法（顺序分配算法）分配主存空间的小测试。"< cout<<"这里一共有1000kb内存可供使用，有三种选择："< int choice; Pro *ph=NULL; Table *head=new Table(0,1000); char Na[10]; int size; while(1) { cout<<"请输入你的选择:"; cin>>choice; if(choice==1) { cout<<"请输入作业名以及作业大小："; cin>>Na>>size; Pro *p=new Pro(size,Na); JR(ph,p,head); Pri(ph); Prik(head); } else if(choice==2) { cout<<"请输入作业名称："; cin>>Na; SF(ph,Na,head); Pri(ph); Prik(head); } else if(!choice) { Pri(ph); Prik(head); exit(0); } } return 0; } (4) 打印程序运行时的初值和运行结果，要求如下： (5) 如果在要申请一个100K的作业空间，能否满足？ 答：本程序初定内存总容量为1000K，所以可以满足；当总容量小于500K时，无法申请。