动态分区分配算法 实验报告
更新时间:2023-10-21 01:10:01 阅读量: 综合文库 文档下载
- 动态分区分配算法推荐度:
- 相关推荐
操作系统实验报告
实验二: 动态分区分配算法 .
学 生: 学 号: 学 院:
系 别: 专 业: 实验时间: 报告时间:
一、实验内容
编写一个内存动态分区分配模拟程序,模拟内存的分配和回收的完整过程。
一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器,而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时,存储管理必须根据申请者的要求,按一定的策略分析主存空间的使用情况,找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时,则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理方式有关的,通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。 三、实验原理
模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。
(1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时,根据作业需要的主存量查看是否有足够的空闲空间,若有,则按需要量分割一个分区分配给该作业;若无,则作业不能装入。随着作业的装入、撤离,主存空间被分成许多个分区,有的分区被作业占用,而有的分区是空闲的。例如:
0 5k 10k 14k 26k 32k 512k 操作系统 作业1 作业3 空闲区 作业2 空闲区
为了说明哪些区是空闲的,可以用来装入新作业,必须要有一张空闲区说明表,格式如下:
第一栏 第二栏 ?
起 址 14 K 32 K ? 长 度 12 K 96 K ? 状 态 未 分 配 未 分 配 ? 其中,起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态,一种是“未分配”状态,指出对应的由起址指出的某个长度的区域是空闲区。
(2) 当有一个新作业要求装入主存时,必须查空闲区说明表,从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量,这时应把原来的空闲区变成两部分:一部分分给作业占用;另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区,而尽量保存高地址部分有较大的连续空闲区域,以利于大型作业的装入。为此,在空闲区说明表中,把每个空闲区按其地址顺序登记,即每个后继的空闲区其起始地址总是比前者大。
(3) 采用最先适应算法(顺序分配算法)分配主存空间。
按照作业的需要量,查空闲区说明表,顺序查看登记栏,找到第一个能满足要求的空闲
区。当空闲区大于需要量时,一部分用来装入作业,另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配,所以把主存区分配给作业后并不实际启动装入程序装入作业,而用输出“分配情况”来代替。
(4) 当一个作业执行结束撤离时,作业所占的区域应该归还,归还的区域如果与其它空闲区相邻,则应合成一个较大的空闲区,登记在空闲区说明表中。
(5) 请按最先适应算法设计主存分配和回收的程序。假设初始时主存中没有作业,现按下面序列进行内存的申请与释放:
作业1申请300K,作业2申请100K,作业1释放300K,作业3申请150K, 作业4申请30K, 作业5申请40K, 作业6申请60K, 作业4释放30K。 请你为它们进行主存分配和回收,把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。 四、实验报告
(1) 画出最先适应分配算法流程图、归还主存时的回收算法流程图。
最先适应分配算法流程图: 输入作业 对象 改变空闲区块队列 +改变作业队列 顺序遍历空闲 区块队列 输出结果 是否有足够空N 间的空闲区块 Y
归还主存时的回收算法流程图: 输入作业 对象 改变空闲区块队列 +改变作业队列 是否存在该N 作业? 输出结果 Y
(2) 程序中使用的数据结构及符号说明。
答:本程序用c++语言编写,其中用到了class{}类、指针,利用指针将class Table{}(空闲表类)和class Pro{}(作业类)用链式存储的方式进行插入、删除、新建、排序等工作。
(3) 打印一份源程序并附上注释。 #include } 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< void Prik(Table *h) { if(h) { cout<<\空闲区块分配情况\空闲区块起始地址\空闲区块大小\ for(;h;h=h->next) cout<<\ 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=p; } else { if(h->next==NULL) { p->next=h; h=p; } else { for(;hp;hp=hp->next) { if(p->Size 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 Table(pph->Start,ph->Size+pph->Size+p->Size); PX(h,n); break; } pph1=pph; } if(!pph) //4 { ph->Size=ph->Size+p->Size; *n=new 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); } (4) Prik(head); exit(0); } } return 0; 打印程序运行时的初值和运行结果,要求如下: (5) 如果在要申请一个100K的作业空间,能否满足? 答:本程序初定内存总容量为1000K,所以可以满足;当总容量小于500K时,无法申请。
正在阅读:
动态分区分配算法 实验报告10-21
尔雅 钢琴艺术赏析 考试答案03-20
南京大学国家自然科学基金申请书-指导版01-15
附:“我的寝室梦想”评比结果11-05
突袭3闪电战秘籍09-22
生产与运作管理课程设计报告方案一04-21
2-1全科医学基础(学生用书)09-16
团委书记事迹材料10-12
二学期大学物理期末考试试卷(A卷)12-10
- 计算机试题
- 【2012天津卷高考满分作文】鱼心人不知
- 教育心理学历年真题及答案--浙江教师资格考试
- 20180327-第六届“中金所杯”全国大学生金融知识大赛参考题库
- 洪林兴达煤矿2018年度水情水害预测预报
- 基本要道讲义
- 机电设备安装试运行异常现象分析与对策
- 《有机化学》复习资料-李月明
- 非常可乐非常MC2--非常可乐广告策划提案 - 图文
- 2011中考数学真题解析4 - 科学记数法(含答案)
- 企业人力资源管理师三级07- 09年真题及答案
- 基于单片机的光控自动窗帘控制系统设计说明书1 - 图文
- 20160802神华九江输煤皮带机安装方案001
- (共53套)新人教版一生物必修2(全册)教案汇总 word打印版
- 2014行政管理学总复习
- 中国银监会关于加强地方政府融资平台贷款风险监管的指导意见
- 民宿酒店核心竞争与研究
- 游园活动谜语大全2012
- 河南省天一大联考2016届高三英语5月阶段性测试试题(六)(A卷)
- 小型超市管理系统毕业论文详细设计4
- 分区
- 算法
- 分配
- 实验
- 报告
- 动态