2024年动态分区分配算法实验报告

操作系统试验报告试验二:动态分辨别配算法.学生：学号：学院：系别：专业：试验时间：报告时间：一、试验内容编写一个内存动态分辨别配模拟程序，模拟内存的分派和回收的完整过程。一个好的计算机系统不但要有一个足够容量的、存取速度高的、稳定可靠的主存储器，并且要能合理地分派和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须依照申请者的要求，按一定的方略分析主存空间的使用情况，找出足够的空闲区域分派给申请者。当作业撤离或积极偿还主存资源时，则存储管理要收回作业占用的主存空间或偿还部分主存空间。主存的分派和回收的实现与主存储器的管理方式有关的，通过本试验协助学生了解在可变分区管理方式下应怎样实现主存空间的分派和回收。三、试验原理模拟在可变分区管理方式下采取最先适应算法实现主存分派和回收。(1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，依照作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分辨别配给该作业；若无，则作业不能装入。伴随作业的装入、撤离，主存空间被提成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：05k05k10k14k26k32k512k作业1作业3空闲区作业2空闲区为了阐明哪些区是空闲的，能够用来装入新作业，必须要有一张空闲区阐明表，格式如下：起址长度状态第一栏14K12K未分配第二栏32K96K未分配MMMM其中，起址——指出一个空闲区的主存起始地址。长度——指出从起始地址开始的一个连续空闲的长度。状态——有两种状态，一个是“未分派”状态，指出对应的由起址指出的某个长度的区域是空闲区。(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{}类、指针，利用指针将classTable{}(空闲表类)和classPro{}(作业类)用链式存储的方式进行插入、删除、新建、排序等工作。(3)打印一份源程序并附上注释。#include<iostream.h>#include<string.h>classPro //作业对象{ public: Pro(){ Size=0; next=NULL; Start=0; Name[0]='\0'; } Pro(intSi,charNa[]){ Size=Si; next=NULL; Start=0; strcpy(Name,Na); } voidprintf() { cout<<Name<<"\t"<<Start<<endl; } voidArrange(intSta,Pro&Ne) { Start=Sta; next=&Ne; } Pro*next; //用来指向下一个输入的作业 intSize; //作业大小 charName[10]; // 作业名称 intStart; //在内存中存储的起始地址};classTable //空闲表{ public: Table*next; //指向下一个空闲区块 intSize; //空闲区块大小 Table(){ } Table(intSta,intSiz) { Start=Sta; Size=Siz; Over=Sta+Siz; next=NULL; } intStart; //空闲区块起始地址 intOver; //空闲区块结束地址};voidPri(Pro*ph){ if(ph) { cout<<endl<<"内存中的作业"<<endl<<"作业名"<<"\t"<<"起始地址"<<endl; for(Pro*p=ph;p;p=p->next) p->printf(); cout<<endl; } else cout<<"作业已所有运行完成！"<<endl;}voidPrik(Table*h){ if(h) { cout<<"空闲区块分派情况"<<endl<<"空闲区块起始地址"<<"\t"<<"空闲区块大小"<<endl; for(;h;h=h->next) cout<<"\t"<<h->Start<<"\t\t\t"<<h->Size<<endl; cout<<endl; } else cout<<"无空闲区块！"<<endl;}voidPX(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<p->Over&&hf1->Start>=p->Start&&hf1==h) h=h->next; elseif(hf1->Start<p->Over&&hf1->Start>=p->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<hp->Size) { 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->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->Start==(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) //1 { for(Table*h1=h;h1;h1=h->next) { if(h1->Over==p->Start) { Table*n=newTable(h1->Start,p->Size+h1->Size); PX(h,n); jugy=1; break; } } if(!jugy) { Table*n=newTable(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=newTable(p->Start,p->Size); 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; } 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<<"队列中没有这个作业!"<<endl;}voidJR(Pro*&ph,Pro*p,Table*&h) //加入作业{ Pro*pp=ph; intjugy=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<<"没有足够的空间分派！"<<endl;}intmain(){ cou