操作系统实验报告书

试验一：进程调度1.试验目的：通过这次试验，加深对进程概念的理解，深入掌握进程状态的转变、进程调度的方略及对系统性能的评价措施。2.试验内容：设计程序模拟进程的轮转法调度过程。假设初始状态为：有n个进程处在就绪状态，有m个进程处在阻塞状态。采用轮转法进程调度算法进行调度(调度过程中，假设处在执行状态的进程不会阻塞)，且每过t个时间片系统释放资源，唤醒处在阻塞队列队首的进程。程序规定如下：1）.输出系统中进程的调度次序；2）.计算CPU运用率。3.试验环境：硬件环境：GhostXPSP3纯净版Y6.0Pentium(R)Dual-CoreCPUE6700@3.20GHz3.19GHz,1.96GB的内存物理地址扩展软件环境：MicrosoftWindowsXP,VisualStudio4.源代码：#include<iostream>#include<algorithm>#include<queue>usingnamespacestd;constintMaxNum=100;structNode{ intindex; intarriveTime; intrest;};boolNodeCmp(constNode&a,constNode&b){ returna.arriveTime<b.arriveTime;}intn;//进程数intArrivalTime[MaxNum];intServiceTime[MaxNum];intPServiceTime[MaxNum];intFinishTime[MaxNum];intWholeTime[MaxNum];doubleWeightWholeTime[MaxNum];boolFinished[MaxNum];doubleAverageWT,AverageWWT;boolisEnterQue[MaxNum];intcntTimes[MaxNum];voidinit(){ memset(PServiceTime,0,sizeof(PServiceTime)); memset(Finished,0,sizeof(Finished)); memset(FinishTime,0,sizeof(FinishTime)); memset(WholeTime,0,sizeof(WholeTime)); memset(WeightWholeTime,0,sizeof(WeightWholeTime));}intsum(intarray[],intn){ intsum=0; inti; for(i=0;i<n;i++) { sum+=array[i]; } returnsum;}doublesum(doublearray[],intn){ doublesum=0; inti; for(i=0;i<n;i++) { sum+=array[i]; } returnsum;}voidprint(){ inti=0; cout<<"进程完毕时间:"; for(i=0;i<n;i++) { cout<<FinishTime[i]<<''; } cout<<endl; cout<<"周转时间:"; for(i=0;i<n;i++) { cout<<WholeTime[i]<<''; } cout<<endl; cout<<"带权周转时间:"; for(i=0;i<n;i++) { printf("%.2f",WeightWholeTime[i]); } cout<<endl;}voidSearchToEnterQue(queue<Node>&que,Node*pArr,intmaxArrivalTime){ inti; for(i=0;i<n;i++) { if(pArr[i].arriveTime>maxArrivalTime) break; if(isEnterQue[pArr[i].index]==false) { que.push(pArr[i]); isEnterQue[pArr[i].index]=true; } }}voidWork(intq){ init(); memset(isEnterQue,0,sizeof(isEnterQue)); memset(cntTimes,0,sizeof(cntTimes)); Node*pNodeArr=newNode[n]; inti; for(i=0;i<n;i++) { pNodeArr[i].index=i; pNodeArr[i].arriveTime=ArrivalTime[i]; pNodeArr[i].rest=ServiceTime[i]; } sort(pNodeArr,pNodeArr+n,NodeCmp); inttotalTime=sum(ServiceTime,n); inttime=pNodeArr[0].arriveTime; queue<Node>que; que.push(pNodeArr[0]); isEnterQue[pNodeArr[0].index]=true; Nodecur; cout<<"================================================="<<endl; while(!que.empty()) { cur=que.front(); que.pop(); cntTimes[cur.index]++; if(cntTimes[cur.index]==1) printf("在%d时刻，进程%d开始执行。。。\n",time,cur.index); if(cur.rest>q) { time+=q; cur.rest-=q; } else { time+=cur.rest; Finished[cur.index]=true; FinishTime[cur.index]=time; cur.rest=0; printf("在%d时刻，进程%d执行结束。\n",time,cur.index); } SearchToEnterQue(que,pNodeArr,time); if(cur.rest!=0) que.push(cur); if(que.empty())//若队列为空，则在time之后才到达的进程找最早抵达的进程入队列 { for(i=0;i<n;i++) { if(isEnterQue[i]==false)//找到了 { que.push(pNodeArr[i]);//入队列 time=pNodeArr[i].arriveTime; break; } } } } for(i=0;i<n;i++) { WholeTime[i]=FinishTime[i]-ArrivalTime[i]; WeightWholeTime[i]=(double)WholeTime[i]/(double)ServiceTime[i]; } AverageWT=(double)sum(WholeTime,n)/(double)n; AverageWWT=(double)sum(WeightWholeTime,n)/(double)n; cout<<"================================================="<<endl; print(); cout<<endl<<endl; cout<<"================================================="<<endl; printf("平均周转时间:%.2f,平均带权周转时间:%.2f\n",AverageWT,AverageWWT); delete[]pNodeArr;}intmain(){// freopen("test.txt","rw",stdin); intq;//时间片大小 inti; cout<<"输入进程数:"; cin>>n;; cout<<"输入每个进程的抵达时间:"<<endl; for(i=0;i<n;i++) cin>>ArrivalTime[i]; cout<<"输入每个进程的服务时间:"<<endl; for(i=0;i<n;i++) cin>>ServiceTime[i]; cout<<"输入时间片大小"<<endl; cin>>q; Work(q); return0;}5.试验成果： 6.试验分析和体会：试验二分区式存储管理1.试验目的：通过这次试验，加深对内存管理的认识，深入掌握内存的分派、回收算法的思想。2.试验内容：设计程序模拟内存的动态分区法存储管理。内存空闲区使用自由链管理，采用最坏适应算法从自由链中寻找空闲区进行分派，内存回收时假定不做与相邻空闲区的合并。假定系统的内存共640K，初始状态为操作系统自身占用64K。在t1时间之后，有作业A、B、C、D分别祈求8K、16K、64K、124K的内存空间；在t2时间之后，作业C完毕；在t3时间之后，作业E祈求50K的内存空间；在t4时间之后，作业D完毕。规定编程序分别输出t1、t2、t3、t4时刻内存的空闲区的状态。3.试验环境：硬件环境：GhostXPSP3纯净版Y6.0Pentium(R)Dual-CoreCPUE6700@3.20GHz3.19GHz,1.96GB的内存物理地址扩展软件环境：MicrosoftWindowsXP,VisualStudio4.源代码：#include<stdio.h>#include<stdlib.h>structfreelink{ intlen,address;//len为分区长度；address为分区起始地址 structfreelink*next;};//内存占用区用链表描述，其结点类型描述如下：structbusylink{ charname;//作业或进程名name='S'表达OS占用 intlen,address; structbusylink*next;};//并设全程量：structfreelink*free_head=NULL;//自由链队列带头结点）队首指针?structbusylink*busy_head=NULL,*busy_tail=NULL;//占用区队列队（带头结点）首指针//占用区队列队尾指针//设计子函数：voidstart(void)/*设置系统初始状态*/{structfreelink*p;structbusylink*q;free_head=(structfreelink*)malloc(sizeof(structfreelink));free_head->next=NULL;//创立自由链头结点busy_head=busy_tail=(structbusylink*)malloc(sizeof(structbusylink));busy_head->next=NULL;//创立占用链头结点p=(structfreelink*)malloc(sizeof(structfreelink));p->address=64;p->len=640-64;//（OS占用了K）p->next=NULL;free_head->next=p;q=(structbusylink*)malloc(sizeof(structbusylink));q->name='S';/*S表达操作系统占用*/ q->len=64;q->address=0;q->next=NULL;busy_head->next=q;busy_tail=q;}voidrequireMemo(charname,intrequire)/*模拟内存分派*/{ structfreelink*w,*u,*v,*x,*y; structbusylink*p; x=free_head; y=free_head->next; while((y!=NULL)&&(y->len<require))//找到第一种满足条件的空闲区 { x=y; y=y->next; } if(y!=NULL) { p=(structbusylink*)malloc(sizeof(busylink)); p->name=name; p->address=y->address; p->len=require; p->next=NULL; busy_tail->next=p;//把p插入到busy_head的尾部 busy_tail=p; w=x->next; x->next=w->next; if(w->len==require) { free(w); } else { w->address=w->address+require; w->len=w->len-require; u=free_head; v=free_head->next; while((v!=NULL)&&(v->len<w->len))//假如此结点尚有多出，就此又重新插入到空闲区域链中（按照长度由小到大的次序排列） { u=v; v=v->next; } u->next=w; w->next=v; } } else printf("can'tallocate!\n");}voidfreeMemo(charname)/*模拟内存回收*/{ structbusylink*p,*q; structfreelink*w,*u,*v,*s1=NULL,*s2=NULL; intlen,address; intflag1=1,flag2=1; p=busy_head->next; while((p!=NULL)&&(p->name!=name))//找到要回收的结点 { q=p; p=p->next; } if(p==NULL) { printf("%cisnotexist\n",name); } else { if(p==busy_tail) busy_tail=q; q->next=p->next; len=p->len; address=p->address; free(p); w=(structfreelink*)malloc(sizeof(freelink)); w->len=len; w->address=address; u=free_head; v=free_head->next; while((v!=NULL)&&(flag1==1||flag2==1))//归并算法 { if((w->address==(v->address+v->len))&&flag1) { s1=v; u->next=s1->next; w->address=v->address; w->len+=v->len; v=v->next; flag1=0; } elseif(((w->address+w->len)==v->address)&&flag2) { s2=v; u->next=s2->next; w->len+=v->len; v=v->next; flag2=0; } else { u=v; v=v->next; } u=free_head; v=free_head->next; } if(s1!=NULL) free(s1); if(s2!=NULL) free(s2); if(v!=NULL) { while((v!=NULL)&&(v->len<w->len)) { u=v; v=v->next; } } u->next=w; w->next=v; }}voidpast(inttime)/*模拟系统过了时间time，用sleep(),或者用个空循环*/{ printf("时间%d后：\n",time);}voidprintlink()/*输出内存空闲状况（自由链的结点）*/{ structfreelink*p; p=free_head->next; if(p==NULL) printf("无空闲区！\n"); else { while(p!=NULL) { printf("首地址:%d\t长度:%d\n",p->address,p->len); p=p->next; } } printf("\n"); }voidprintlink1()/*输出内存占用的状况*/{ structbusylink*p; p=busy_head->next; if(p==NULL) printf("无内存占有区！\n"); else { while(p!=NULL) { printf("名字:%c\t首地址:%d\t长度:%d\n",p->name,p->address,p->len); p=p->next; } } }// 设计主函数：intmain(){ start(); past(1); requireMemo('A',8);requireMemo('B',16); requireMemo('C',64);requireMemo('D',124); printf("内存占用区为：\n"); printlink1(); printf("内存空闲区为:\n"); printlink(); past(2); freeMemo('C'); printf("内存占用区为：\n"); printlink1(); printf("内存空闲区为:\n"); printlink(); past(3); requireMemo('E',50); printf("内存占用区为：\n"); printlink1(); printf("内存空闲区为:\n"); printlink(); return0;}5.试验成果：6.试验分析和体会：首先，对链表又有深入的理解，尚有就是加深理解内存的分派与回收，分派与回收的方略，并掌握动态分区这种内存管理的详细实行措施。再者，就是在编程中碰到的困难，在编写归并程序首先是自己考虑问题不全面，写的程序就只顾及到一种结点，而没有实既有两个结点的状况，于是后来再加了一条else语句，就没有出现问题。尚有一种问题就是将多出的结点free时也出现问题，加了一条if(s==NULL）,成立就释放掉。一开始把free语句写在while循环内，一旦把找到的结点释放掉，则找不到下一种结点，也会出错，因此应当把free放到while循环外。试验三虚拟存储管理1.试验目的：存储管理的重要功能之一是合理的分派空间。祈求页式管理是一种常用的虚拟存储管理技术。本试验的目的是祈求页式存储管理中页面置换算法模拟设计，理解虚拟存储技术的特点，掌握祈求页式存储管理的页面置换措施。2.试验内容：（1）通过随机数产生一种指令序列，共320条指令。指令的地址按下述原则生成：50%的指令是次序执行的；25%的指令是均匀分布在前地址部分；25%的指令是均匀分布在后地址部分。详细的实行措施是：在[0,319]的指令地址之间随机选用一起点m;次序执行一条指令，即执行地址为m+1的指令；在前地址[0,m+1]中随机选用一条指令并执行，该指令的地址为m’；次序执行一条指令，其地址为m’+1;在后地址[m’+2,319]中随机选用一条指令并执行；反复上述环节，直至执行320次指令。将指令序列变换成页地址流设：①页面大小为1K；②顾客内存容量为4页到32页；③顾客虚存容量为32K；在顾客虚存中，按每K寄存10条指令排列虚存地址，即320条指令在虚存中的寄存方式为：第0条~第9条指令为第0页（对应的虚存地址为[0，9]）；第10条~第19条指令为第1页（对应的虚存地址为[10，19]）；.第310条~第319条指令为第31页（对应的虚存地址为[310，319]）；按以上方式，顾客指令可构成32页。计算并输出下述多种算法在不一样的内存容量下的命中率。先进先出的算法（FIFO）；近来至少使用算法（LRR）；最佳淘汰法（OPT）：先淘汰最不常用的页地址；至少访问页面算法（LFR）；近来不常常使用算法（NUR）。其中③和④为选择内容。命中率=1-（页面失效次数）/（页地址流长度）在本试验中，页地址流的长度为320，页面失效次数为每次访问对应指令时，该指令所对应的页不在内存的次数。随机数产生措施有关随机书产生措施，可以使用系统提供函数rand()，分别进行初始化和产生随机数。例如：srand();语句可初始化的一种随机数；a[0]=10*rand()/32767*319+1;a[1]=10*rand()/32767*a[0];语句可用来产生a[0]与a[1]中的随机数。3.试验环境：硬件环境：GhostXPSP3纯净版Y6.0Pentium(R)Dual-CoreCPUE6700@3.20GHz3.19GHz,1.96GB的内存物理地址扩展软件环境：MicrosoftWindowsXP,VisualStudio4.源代码：#include<iostream>#include<deque>//队列#include<ctime>//获取系统的时间usingnamespacestd;typedefstruct//页面的构造体信息{intid;//页面的id号intstaytime;//在内存中的停留的时间intunusualtime;//多久未被使用的时间}Cpage;deque<int>queue;//可以直接的使用队列的措施deque<Cpage>interPage;//内存中的页面deque<Cpage>exterPage;//外存中页面intxianzaiweizhi;intlacknum[2]={0,0};//缺失的页面数intgetRandNum(intrange)//返回[0,range)范围内的整数{returnint(rand()%range);//根据srand函数得到随机数}voidInitDevice()//初始化运行队列按照25%50%25%的原则生成{srand(int(time(NULL)));//通过调用系统时间,产生随机数,并强制的转化成整型intyehao=getRandNum(320);//随机选择第一条指令queue.push_back(yehao);//将其插入队列if(yehao<319)queue.push_back(yehao+1);//次序执行下一条指令while(queue.size()<320)//一直运行到队列中的个数等于320{yehao=getRandNum(yehao);//跳转到m1属于[0,m-1]queue.push_back(yehao);//将m1插入队列if(yehao<319)queue.push_back(yehao+1);//将m1+1插入队列inttemp=320-(yehao+2);yehao=yehao+2+getRandNum(temp);//跳转到m2属于[m+2,319]queue.push_back(yehao);//插入队列if(yehao<319)queue.push_back(yehao+1);//将m2+1插入队列}while(queue.size()>320)//假如队列中的个数不小于320,则把多出的队列进行出栈的操作queue.pop_back();}voidInitMemoryQueue()//初始化页面{xianzaiweizhi=0;exterPage.clear();//对外存的页面进行清除interPage.clear();//对内存的页面进行清除for(inti=0;i<32;i++){Cpagetemp;temp.id=i;temp.staytime=0;//停留时间和未使用的时间都初始化未0temp.unusualtime=0;exterPage.push_back(temp);//将产生的页面进行入队的操作}}intshuyunageyemian(intcmdId)//通过强制转换成整数的形式判断指令属于哪个页面{returnint(cmdId/10);}intyemianzhuantai(intPageId,boolsign)//分别在内外存中查找页面存在返回位置不存在返回-1{if(sign)//在内存中进行查找for(inti=0;i<interPage.size();i++){if(PageId==interPage[i].id)returni;} else//在外存中进行查找for(intj=0;j<exterPage.size();j++)if(PageId==exterPage[j].id)returnj;return-1;//假如内外存中都不在的话，返回-1}voiddirectFlod(intPageId)//当内存空间尚有剩余时直接调入{intstatus=yemianzhuantai(PageId,false);if(status==-1)return;interPage.push_back(exterPage[status]);//向内存插入exterPage.erase(exterPage.begin()+status);//从外存删除队列开始的位置加上偏移量}intfifo()//FIFO算法中查找在内存中呆了最久的页面{intmax=0;for(unsignedi=1;i<interPage.size();i++)if(interPage[i].staytime>interPage[max].staytime)//找到在内存中停留时间时间最长max=i;returnmax;//返回停留时间最长的最大值}intlru()//LRU算法中查找最久未使用的页面{intmax=0;for(intj=0;j<interPage.size();j++)if(interPage[j].unusualtime>interPage[max].unusualtime)//找到最久未被使用的算法max=j;returnmax;//返回未被使用的最大值}boolManage(intcount,intPageId)//当内存已经满了需要按照算法调度{intstatus=yemianzhuantai(PageId,false);//获取执行页面在外存中的索引地址if(status==-1)returnfalse;inttargetStatus=0;if(count==0)targetStatus=fifo();//根据fifo算法内存中需要互换的位置elseif(count==1)targetStatus=lru();//根据lru算法内存中需要互换的位置interPage[targetStatus].staytime=0;//将要互换的内存//页面的停留时间和近来多久未被使用的时间进行初始化为0interPage[targetStatus].unusualtime=0;swap(exterPage[status],interPage[targetStatus]);//内外层中的页面进行互换returntrue;}voidrun(intcount){while(xianzaiweizhi<320)//假如目前的位置在合理的范围内{for(inti=0;i<interPage.size();i++)//对内存中的页面进行操作