操作系统存储管理实验

PAGEPAGE1***大学计算机科学系实验报告书实验题目：C++模拟存储管理及分区分配实现课程名称：操作系统实验目的：1、通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法。

2、通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。

实验环境：VC6.0++实验内容1、设计页面置换程序，模拟实现下面三种页面置换算法：

FIFO、LRU、OPT算法设计一个请求页式存储管理方案。2、设计一个可变式分区分配的存储管理方案。并模拟实现分区的分配和回收过程。实现下面三种算法：首次适应算法，最佳适应算法，最差适应算法实验设计原理1、页式存储系统打破存储分配的连续性，使得一个程序的逻辑地址空间可以分布在若干个离散的内存块上，从而达到充分利用内存，提高内存效率的目的。页式存储系统将内存分为等长的若干区域，每个区域即一个页面。在对用户程序进行分配时，由系统调用页面置换算法对程序地址进行分配。常用页面置换算法有如下几种：理想页面（OPT）置换算法：发生缺页时，有些页面在内存中将很快被访问，而其他页可能要到10、100或1000条指令后才被访问，对每个页面首次访问前要执行的指令数进行标记，置换掉最大的标记数页面。先进先出（FIFO）置换算法：发生缺页时，总是选择最先装入的页面调出。最近最少使用（LRU）置换算法：发生缺页时，总是选择距离现在最长时间没有使用的页面调出，而将使用过的页面放在最近位置。2、分区分配分区管理是能满足多道程序运行的最简单的存储管理方案。其基本思想是把内存划分成若干个连续区域，成为分区，每个分区装入一个运行程序。分区的方式可以归纳成固定分区和可变分区。算法设计与流程程序设计流程图如下：页面置换算法流程图：ff结束初始化内存页面数、实际页面数、页号判断置换算法访问一个指令地址，计算地址页面号FIFO算法淘汰一页该页在内存该页在内存该页在内存内存有空白页？打印置换结果指令访问完？内存有空白页？OPT算法淘汰一页打印置换结果指令访问完？指令访问完？内存有空白页？LRU算法淘汰一页打印置换结果调入当前所需页调入当前所需页调入当前所需页olYYYNNNYNNYYNYYYNNN1、页面置换算法程序设计如下：#include<iostream.h>#defineM40#defineN10//可用内存页面structPro//页面结构体{ intnum; inttime;};intInput(intm,Prop[]){ cout<<"请输入实际页数："; do { cin>>m; if(m>M)cout<<"数目太多，请重试"<<endl; elsebreak; }while(1);cout<<endl<<"请输入各页面号"<<endl; for(inti=0;i<m;i++) { cin>>p[i].num; p[i].time=0; } returnm;}voidPrint(Pro*page,intn)//打印当前的页面{ for(inti=0;i<n;i++) cout<<page[i].num<<""; cout<<endl;}intSearch(inte,Pro*page,intn)//在内存页面中查找{ for(inti=0;i<n;i++) if(e==page[i].num) returni; return-1;}intMax(Pro*page,intn){ inte=page[0].time,i=0; while(i<n)//找出离现在时间最长的页面 { if(e<page[i].time) e=page[i].time; i++; }for(i=0;i<n;i++) if(e==page[i].time) returni; return-1;}intCompfu(Pro*page,inti,intt,Prop[]){ intcount=0; for(intj=i;j<M;j++) { if(page[t].num==p[j].num)break; elsecount++; } returncount; }intmain(){ intnu; cout<<"可用内存页面数:"<<endl; cin>>nu; if(nu>N) { cout<<"页面过大"<<endl; return0; } Prop[M]; Propage[N]; charc; intm=0/*实际页数*/,t=0/*页面循环*/; floatn=0;//缺页次数 m=Input(m,p); do{ for(inti=0;i<nu;i++)//初始化页面基本情况 { page[i].num=0; page[i].time=2-i; } /*intj=0,count=1; page[0].num=p[0].num; inti=1,k=1; while(i<N) { intflag=1; for(j=0;j<i;j++) if(p[k].num==page[i].num) {n++;flag=0;break;} if(flag==1){page[i].num=p[k].num;i++;} count++;k++; }*/i=0; cout<<"f:FIFO页面置换"<<endl; cout<<"l:LRU页面置换"<<endl; cout<<"o:OPT页面置换"<<endl; cout<<"按其它键结束"<<endl; cin>>c; if(c=='f')//FIFO页面置换 { n=0; cout<<"页面置换情况:"<<endl; while(i<m) { if(Search(p[i].num,page,nu)>=0)i++;//找到相同的页面 else { if(t==nu)t=0; n++;//缺页次数加1 page[t].num=p[i].num; Print(page,nu); t++; i++; } } cout<<"缺页次数："<<n<<"缺页率："<<n/m<<endl; } i=0; if(c=='l')//LRU页面置换 { n=0; cout<<"页面置换情况："<<endl; while(i<m) { if(Search(p[i].num,page,nu)>=0) { intj=Search(p[i].num,page,nu); for(intk=j;k>0;k--) page[k].num=page[k-1].num; page[k].num=page[j].num; i++; } else { if(t==nu)t=0; n++; for(intk=nu-1;k>0;k--) page[k].num=page[k-1].num; page[k].num=p[i].num; Print(page,nu); t++; i++; } } cout<<"缺页次数："<<n<<"缺页率："<<n/m<<endl; } if(c=='o')//OPT页面置换 { n=0; while(i<m) { if(Search(p[i].num,page,nu)>=0)i++; else { inttemp=0,cn; for(t=0;t<nu;t++) { if(temp<Compfu(page,i,t,p)) { temp=Compfu(page,i,t,p); cn=t; } } page[cn]=p[i]; n++; Print(page,nu); i++; } } cout<<"缺页次数："<<n<<"缺页率："<<n/m<<endl; } }while(c=='f'||c=='l'||c=='o'); return0;}2、分区算法#include"stdio.h"#include"stdlib.h"#include"string.h"#defineMAX32767typedefstructnode//设置分区描述器{intaddress;//地址intsize;//大小structnode*next;}RECT;//函数原型声明RECT*assignment(RECT*head,intapplication);//分配区间voidacceptment1(RECT*head,RECT*back1);voidacceptment2(RECT*head,RECT*back1);intbackcheck(RECT*head,RECT*back1);voidprint(RECT*head);//变量声明RECT*head,*back,*assign1,*p;intapplication1/*申请空间大小*/,maxblocknum;charway;main(){charchoose[10];//分配或回收intcheck;head=malloc(sizeof(RECT));//建立可利用区表的初始状态p=malloc(sizeof(RECT));head->size=MAX;head->address=0;head->next=p;maxblocknum=1;p->size=MAX;p->address=0;p->next=NULL;print(head);//输出可利用表初始状态printf("Entertheway(bestorfirst(b/f)\n");//选择适应策略scanf("%c",&way);do{ printf("Entertheassignoraccept(as/ac)\n");scanf("%s",choose);//选择分配或回收if(strcmp(choose,"as")==0)//as为分配{ printf("Inputapplication:\n");scanf("%d",&application1);//输入申请空间大小assign1=assignment(head,application1);//调用分配函数if(assign1->address==-1)//分配不成功printf("Toolargeapplication!,assignfails!!\n\n");elseprintf("Success!!ADDRESS=%5d\n",assign1->address);//分配成功print(head);//输出}elseif(strcmp(choose,"ac")==0)//回收 {back=malloc(sizeof(RECT));printf("InputAdressandSize!!\n");scanf("%d%d",&back->address,&back->size);//输入回收地址和大小check=backcheck(head,back);//检查if(check==1) {if(tolower(way)=='f')//首先适应算法acceptment1(head,back);//首先适应elseacceptment2(head,back);//最佳适应print(head); } }}while(!strcmp(choose,"as")||!strcmp(choose,"ac"));}//分配函数RECT*assignment(RECT*head,intapplication){ RECT*after,*before,*assign;assign=malloc(sizeof(RECT));//分配申请空间assign->size=application;assign->next=NULL;if(application>head->size||application<=0)assign->address=-1;//申请无效else{ before=head;after=head->next;while(after->size<application)//查找适应的结点 { before=before->next;after=after->next; }if(after->size==application)//结点大小等于申请大小则完全分配 { if(after->size==head->size)maxblocknum--;before->next=after->next;assign->address=after->address;free(after); }else { if(after->size==head->size)maxblocknum--;after->size=after->size-application;//大于申请空间则截取相应大小分配assign->address=after->address+after->size;if(tolower(way)=='b')//如是最佳适应，将截取后剩余结点重新回收到合适位置 { before->next=after->next;back=after;acceptment2(head,back); } }if(maxblocknum==0)//修改最大数和头结点值 { before=head;head->size=0;maxblocknum=1;while(before!=NULL) { if(before->size>head->size) { head->size=before->size;maxblocknum=1; }else if(before->size==head->size)maxblocknum++;before=before->next; } }}assign1=assign;returnassign1;//返回分配给用户的地址}voidacceptment1(RECT*head,RECT*back1)//首先适应{ RECT*before,*after;intinsert;before=head;after=head->next;insert=0;while(!insert)//将回收区插入空闲区表{ if((after==NULL)|| ((back1->address<=after->address)&& (back1->address>=before->address))) { before->next=back1; back1->next=after; insert=1; } else { before=before->next; after=after->next; } } if(back1->address==before->address+before->size)//与上一块合并{ before->size=before->size+back1->size; before->next=back1->next; free(back1); back1=before; }if(after!=NULL&&(after->address==back1->address+back1->size)){//与下一块合并 back1->size=back1->size+after->size; back1->next=after->next; free(after); } if(head->size<back1->size)//修改最大块值和最大块个数 { head->size=back1->size; maxblocknum=1; } else if(head->size==back1->size) maxblocknum++;}//最佳适应，back1为回收结点的地址voidacceptment2(RECT*head,RECT*back1){ RECT*before,*after;intinsert;insert=0;before=head;after=head->next;if(head->next==NULL)//如果可利用区表为空{ head->size=back1->size; head->next=back1; maxblocknum++; back1->next=NULL; } else { while(after!=NULL)//与上一块合并 if(back1->address==after->size+after->address) { before->next=after->next; back->size=after->size+back1->size; free(after); after=NULL; } else { after=after->next; before=before->next; } before=head;after=head->next;while(after!=NULL) if(after->address==back1->size+back1->address)//与下一块合并 { back1->size=back1->size+after->size; before->next=after->next; free(after); after=NULL; } else { before=before->next; after=after->next; } before=head;//将回收结点插入到合适的位置 after=head->next; do{ if(after==NULL||(after->size>back1->size)) { before->next=back1; back1->next=after; insert=1; } else { before=before->next; after=after->next; } }while(!insert);if(head->size<back1->size)//修改最大块值和最大块数 { head->size=back1->size;maxblocknum++; }else if(head->size==back1->size)maxblocknum++;}}voidprint(RECT*head)//输出链表{ RECT*before/*,after*/;intindex;before=head->next;index=1;if(head->next==NULL)printf("NOpartforassignment!!\n");else{ printf("*****index*******address********end*********size*****\n");while(before!=NULL) { printf("\n");printf("%-13d%-13d%-13d%-13d\n",index,before->address,before->address+before->size-1,before->size);printf("\n");index++;before=before->next; }}}//检查回收块的合法性，back1为要回收的结点地址intbackcheck(RECT*head,RECT*back1){ RECT*before/*,after*/;intcheck=1;if(back1->address<0||back1->size<0)check=0;//地址和大小不能为负before=head->next;while((before!=NULL)&&check)//地址不能和空闲区表中结点出现重叠 if(((back1->address<before->address) &&(back1->address+back1->size>before->address))