文档介绍：该【操作系统实验三 】是由【mama】上传分享，文档一共【15】页，该文档可以免费在线阅读，需要了解更多关于【操作系统实验三 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。操作系统试验—存储安排?保藏[试验目的],并进一步加深对动态分区存储管理方式及实现过程的理解。、页表、地址转换和页面转换过程的模拟,加深对恳求调页系统的原理和实现过程的理解。[试验内容和步骤]-、动态分区安排方式的模拟1.??用C语言分别实现采纳首次适应算法和最佳适应算法的动态分区安排过程alloc()和回收过程free()。其中,空闲分区通过空闲分区链管理;在进行内存安排时,系统优先运用空闲区低端的空间。2.??假设初始状态下,可用的内在空间为640KB,并有下列的恳求序列:作业1申请130KB作业2申请60KB作业3申请100KB作业2释放60KB作业4申请200KB作业3释放100KB作业1释放130KB作业5申请140KB作业6申请60KB作业7申请50KB作业6释放60KB请分别采纳首次适应算法和最佳适应算法进行内存块的安排和回收,要求每次安排和回收后显示出空闲内存分区链的状况。3.??源代码如下://********?????????????动态分区安排方式的模拟???????????*********#include<>#include<>#defineFree0//空闲状态#defineBusy1//已用状态#defineOK1????//完成#defineERROR0//出错#defineMAX_length640//最大内存空间为640KBtypedefintStatus;typedefstructfreearea//定义一个空闲区说明表结构{???intID;???//分区号???????longsize;???//分区大小???????longaddress;//分区地址???????intstate;???//状态}ElemType;//----------??线性表的双向链表存储结构??------------typedefstructDuLNode//doublelinkedlist{???ElemTypedata;???????structDuLNode*prior;//前趋指针???????structDuLNode*next;??//后继指针}DuLNode,*DuLinkList;?DuLinkListblock_first;//头结点DuLinkListblock_last;??//尾结点Statusalloc(int);//内存安排Statusfree(int);//内存回收StatusFirst_fit(int,int);//首次适应算法StatusBest_fit(int,int);//最佳适应算法voidshow();//查看安排StatusInitblock();//开创空间表?StatusInitblock()//开创带头结点的内存空间链表{???????block_first=(DuLinkList)malloc(sizeof(DuLNode));???????block_last=(DuLinkList)malloc(sizeof(DuLNode));???????block_first->prior=NULL;???????block_first->next=block_last;???????block_last->prior=block_first;???????block_last->next=NULL;???????block_last->=0;???????block_last->=MAX_length;???????block_last->=0;???????block_last->=Free;???????returnOK;}//-----------------------?分?配?主?存?-------------------------Statusalloc(intch){???????intID,request;???????cout<<"请输入作业(分区号):";???????cin>>ID;???????cout<<"请输入须要安排的主存大小(单位:KB):";???????cin>>request;???????if(request<0||request==0)???????{??????????????cout<<"安排大小不合适,请重试!"<<endl;??????????????returnERROR;???????}???????if(ch==2)//选择最佳适应算法???????{???if(Best_fit(ID,request)==OK)cout<<"安排胜利!"<<endl;??????????????elsecout<<"内存不足,安排失败!"<<endl;??????????????returnOK;???????}???????else//默认首次适应算法???????{???if(First_fit(ID,request)==OK)cout<<"安排胜利!"<<endl;??????????????elsecout<<"内存不足,安排失败!"<<endl;??????????????returnOK;???????}}//------------------?首次适应算法?-----------------------StatusFirst_fit(intID,intrequest)//传入作业名及申请量{???????//为申请作业开拓新空间且初始化???????DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));???????temp->=ID;???????temp->=request;???????temp->=Busy;???????DuLNode*p=block_first->next;???????while(p)???????{??????????????if(p->==Free&&p->==request)??????????????{//有大小恰好合适的空闲块?????????????????????p->=Busy;?????????????????????p->=ID;?????????????????????returnOK;?????????????????????break;??????????????}??????????????if(p->==Free&&p->>request)??????????????{//有空闲块能满足需求且有剩余"?????????????????????temp->prior=p->prior;?????????????????????temp->next=p;??????????????????????????temp->=p->;?????????????????????p->prior->next=temp;?????????????????????p->prior=temp;?????????????????????p->=temp->+temp->;?????????????????????p->-=request;?????????????????????returnOK;?????????????????????break;??????????????}??????????????p=p->next;???????}???????returnERROR;}//--------------------??最佳适应算法??------------------------StatusBest_fit(intID,intrequest){???????intch;//记录最小剩余空间???????DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));???????temp->=ID;???????temp->=request;???????temp->=Busy;???????DuLNode*p=block_first->next;???????DuLNode*q=NULL;//记录最佳插入位置???????while(p)//初始化最小空间和最佳位置???????{??????????????if(p->==Free&&?????????????????????(p->>request||p->==request))??????????????{???q=p;?????????????????????ch=p->-request;?????????????????????break;??????????????}??????????????p=p->next;???????}???????while(p)???????{??????????????if(p->==Free&&p->==request)??????????????{//空闲块大小恰好合适?????????????????????p->=ID;?????????????????????p->=Busy;?????????????????????returnOK;?????????????????????break;??????????????}??????????????if(p->==Free&&p->>request)??????????????{//空闲块大于安排需求?????????????????????if(p->-request<ch)//剩余空间比初值还小?????????????????????{????????????????????????????ch=p->-request;//更新剩余最小值????????????????????????????q=p;//更新最佳位置指向?????????????????????}??????????????}??????????????p=p->next;???????}???????if(q==NULL)returnERROR;//没有找到空闲块???????else???????{//找到了最佳位置并实现安排??????????????temp->prior=q->prior;??????????????temp->next=q;??????????????temp->=q->;??????????????q->prior->next=temp;??????????????q->prior=temp;??????????????q->+=request;??????????????q->=ch;??????????????returnOK;???????}}//-----------------------???主?存?回?收???--------------------Statusfree(intID){???????DuLNode*p=block_first;???????while(p)???????{???if(p->==ID)??????????????{?????????????????????p->=Free;?????????????????????p->=Free;?????????????????????if(p->prior->==Free)//与前面的空闲块相连?????????????????????{???p->prior->+=p->;????????????????????????????p->prior->next=p->next;????????????????????????????p->next->prior=p->prior;?????????????????????}?????????????????????if(p->next->==Free)//与后面的空闲块相连?????????????????????{???????????????????????????p->+=p->next->;????????????????????????????p->next->next->prior=p;????????????????????????????p->next=p->next->next;??????????????????????????????????????????}????????????????????????????break;??????????????????}??????????????p=p->next;???????}???????returnOK;}//---------------??显示主存安排状况?------------------voidshow(){???cout<<"+++++++++++++++++++++++++++++++++++++++\n";???????cout<<"+++????????主?存?分?配?情?况????????+++\n";???????cout<<"+++++++++++++++++++++++++++++++++++++++\n";???????DuLNode*p=block_first->next;???????while(p)???????{???cout<<"分?区?号:";??????????????if(p->==Free)cout<<"Free"<<endl;??????????????elsecout<<p-><<endl;??????????????cout<<"起始地址:"<<p-><<endl;??????????????cout<<"分区大小:"<<p-><<"KB"<<endl;??????????????cout<<"状????态:";??????????????if(p->==Free)cout<<"空??闲"<<endl;??????????????elsecout<<"已安排"<<endl;??????????????cout<<"——————————————"<<endl;??????????????p=p->next;???????????}}//-----------------------?主??函??数---------------------------voidmain(){???????intch;//算法选择标记???????cout<<"???????动态分区安排方式的模拟???????\n";???????cout<<"************************************\n";???????cout<<"**1)首次适应算法??2)最佳适应算法?**\n";???????cout<<"************************************\n";???????cout<<"请选择安排算法:";???????cin>>ch;???????Initblock();//开创空间表???????intchoice;??//操作选择标记???????while(1)???????{???????????cout<<"********************************************\n";???????????cout<<"**????1:?安排内存????????2:?回收内存??????**\n";???????????cout<<"**????3:?查看安排????????0:?退????出??????**\n";???????????cout<<"********************************************\n";???????????cout<<"请输入您的操作?:";???????????cin>>choice;??????????????if(choice==1)alloc(ch);//?安排内存??????????????????????????????elseif(choice==2)??//?内存回收??????????????{?????????????????????intID;?????????????????????cout<<"请输入您要释放的分区号:";?????????????????????cin>>ID;?????????????????????free(ID);??????????????}??????????????elseif(choice==3)show();//显示主存??????????????elseif(choice==0)break;//退出??????????????else//输入操作有误??????????????{???cout<<"输入有误,请重试!"<<endl;?????????????????????continue;??????????????}???????}}?二、,。该作业共有320条指令,即它的地址空间为32页,目前它的全部页都还未调入内存。在模拟过程中,假如访问的指令已在内存,则显示其物理地址,并转下一条指令。假如所访问的指令还未装入内存,则发生缺页,此时需记录缺页的次数,并将相应页调入内存。假如4个内存块中均已装入该作业,则需进行页面转换。最终显示其物理地址,并转下一条指令。在全部320条指令执行完毕后,请计算并显示作业运行过程中发生的缺页率。:请分别考虑OPT、FIFO和LRU算法。:50%的指令是依次执行的25%的指令是匀称分布在前地址部分25%的指令是匀称分布在后地址部分详细的实施方法:①在[0,319]之间随机选取一条起始指令,其序号为m②依次执行下一条指令,即序号为m+1的指令③通过随机数,跳转到前地址部分[0,m-1]中的某条指令处,其序号为m1;④依次执行下一条指令,即序号为m1+1的指令⑤通过随机数,跳转到后地址部分[m1+2,319]中的某条指令处,其序号为m2;⑥依次执行下一条指令,即序号为m2+1的指令⑦重复跳转到前地址部分、依次执行、跳转到后地址部分、依次执行的过程,直至执行320条指令。??????在进程运行过程中,若其所要访问的页面不在内存需把它们调入内存,但内存已?无空闲??空间时,为了保证该进程能正常运行,系统必需从内存中调出一页程序或数据,送磁盘的对换区中。但应将哪个页面调出,所以须要依据肯定的算法来确定。在这一过程中,选择换出页面的算法称为页面置换算法。一个好的页面置换算法,应具有较低的页面更换频率。页面置换算法的好坏,将干脆影响到系统的性能。以下分别是试验要求的三个页面置换算法的介绍及设计思想。⑴最佳置换算法(Optimal):最佳置换算法是Blady在理论上提出的一种算法。其所选择的被淘汰页是将来不再被运用,或者是在最远的将来才被访问的页面。?采纳这种页面置换算法,?保证有最少的缺页率。但由于目前还无法预知一个进程在内存的若干个页面中,哪个在最长的时间内不会被访问,因而,现实中该算法是无法实现的。因此在该算法的模拟过程中,页面访问次序必需是给定的,详细实现为:对每一个物理块设置一个整数型的访问标记位,当须要置换物理块中的某一页时,将每一个物理块中的页面号与当前需调入页以后的每一页面号进行比较,若物理块中的页面号与全部的页面号都不同,则该页即为将来不再运用的页,将访问标记设置为1000,表示将来不会用,设置为一个很大数;若找到页号相同的则将其访问次序记入访问标记,比较访问标记,最大的即为最久不会被访问的,将其换出。?⑵先进先出法(FirstInFirstOut):该算法总是淘汰最先进入内存的页面,既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中,每当某一页面进入内存时(包括页面置换时页面的置入),物理块中各页面访问标记自动加一,置换后,将置换页面所在的物理块中访问标记减一;这样能防止当物理块访问标记出现两个以上相同的值的错误执行,更好地模拟了先进先出法;?⑶最近最久未运用(LeastRecentlyUsed):?该算法以最近的过去作为不久将来的近似,?将过去最长一段时间里不曾被运用的页面置换掉。在该算法的模拟过程中,每当物理块中的页面被访问时,便将其访问标记置为-1以后每执行一条指令,便将物理块中各页面的访问标记加一,需置换时访问标记最大的便是将要被置换的。四、??源代码#include<>#include<>#include<>#include<>#defineBsize4?typedefstructBLOCK//声明一种新类型——物理块类型{????????intpagenum;//页号???????essed;//访问字段,其值表示多久未被访问?}BLOCK;??????intpc;//程序计数器,用来记录指令的序号intn;//缺页计数器,用来记录缺页的次数staticinttemp[320];//用来存储320条随机数BLOCKblock[Bsize];//定义一大小为4的物理块数组voidinit();?????//程序初始化函数intfindExist(intcurpage);//查找物理块中是否有该页面intfindSpace();//查找是否有空闲物理块intfindReplace();//查找应予置换的页面voiddisplay();//显示voidsuijishu();//产生320条随机数,显示并存储到temp[320]voidpagestring();//显示调用的页面队列voidOPT();//OPT算法voidLRU();//LRU算法voidFIFO();//FIFO算法voidinit(){????for(inti=0;i<Bsize;i++)???{??????????block[i].pagenum=-1;???????block[i].accessed=0;???????pc=n=0;???}}intfindExist(intcurpage){?????for(inti=0;i<Bsize;i++)???????{??????????????if(block[i].pagenum==curpage)????????returni;//检测到内存中有该页面,返回block中的位置???????}????return-1;}intfindSpace(){?????????for(inti=0;i<Bsize;i++)???????{??????????if(block[i].pagenum==-1)????????returni;//找到空闲的block,返回block中的位置???????}??????????return-1;}intfindReplace(){???intpos=0;???for(inti=0;i<Bsize;i++)???{??????????if(block[i].accessed>block[pos].accessed)?????????pos=i;//找到应予置换页面,返回BLOCK中位置???}?returnpos;}voiddisplay(){???for(inti=0;i<Bsize;i++)???{??????????if(block[i].pagenum!=-1)??????????{???????printf("%02d",block[i].pagenum);}???}???cout<<endl;}voidsuijishu(){???intflag=0;????cin>>pc;????cout<<"******依据要求产生的320个随机数:*******"<<endl;????for(inti=0;i<320;i++)???????{?????????????????temp[i]=pc;??????????????if(flag%2==0)pc=++pc%320;????????if(flag==1)pc=rand()%(pc-1);????????if(flag==3)pc=pc+1+(rand()%(320-(pc+1)));????????flag=++flag%4;??????????????printf("%03d",temp[i]);????????if((i+1)%10==0)cout<<endl;???????}}voidpagestring(){?????????for(inti=0;i<320;i++)???????{??????????printf("%02d",temp[i]/10);???????if((i+1)%10==0)cout<<endl;???????}}voidOPT(){???????intexist,space,position;???????intcurpage;????for(inti=0;i<320;i++)???????{????????????????if(i%100==0)getch();??????????????pc=temp[i];???????????curpage=pc/10;???????????exist=findExist(curpage);????????if(exist==-1)??????????????{?????????????????????space=findSpace();????????????if(space!=-1)?????????????????????{