《操作系统》实验指导书.docVIP

操作系统实验指导书（适用于计科、网络工程、软件工程、信计专业）计算机科学与技术学院2010-5目 录前言3实验一、进程管理与进程同步4实验二、存储器管理6实验三、磁盘调度算法的设计7实验四、文件系统原理与模拟实现8前 言本课程将系统学习操作系统的基本概念和常用算法以及其发展情况和应用情况。通过本课程的学习，学生应达到如下要求：1、加深理解操作系统原理。2、熟悉操作系统的常用算法并完成算法的程序设计。3、理解当前操作系统的应用前景和新的进展。本课程主要讲解操作系统的实现原理，如进程管理、进程同步、存储器管理、设备管理和文件系统等。要求学生理解操作系统的基本原理并完成其中多种典型的操作系统的算法的模拟序设计。学生可以采用任何一种自己熟悉的编程语言完成算法的程序设计，如C/C+、Delphi、VB、VC、C#等。实验一、进程管理实验目的：理解和掌握进程管理中死锁处理和进程同步的方法。实验内容：实现银行家算法、进程调度过程的模拟、读者-写者问题的写者优先算法。实验步骤：l 理解安全性算法和银行家算法的核心机制：针对3类资源、5个进程的情况，设计相应的数据结构，分别表示每个进程占用各类资源的情况；编程实现安全性算法函数，编制主函数，动态输入资源的占用情况，进程的资源申请，调用安全性函数，实现银行家算法；测试：输入可分配和不可分配的请求，测试系统的正确性。l 理解进程的三状态调度过程，及各状态间的转换关系；模拟若干个进程的运行过程，将其存入进程文件中。如：进程1：运行5秒后有3秒的I/O操作，之后有10秒的运行，结束。可以写成：”p1:r5,io3,r3 e;” ；编程实现调度算法函数，定义时间片大小和并发进程个数，不断从进程文件中读出进程信息，模拟进程的运行及调度过程；测试：针对进程文件里面的数据为正常、缺项、格式不正确等各种情况，检测程序的执行结果。l 设计读者-写者问题的写者优先算法；学习Windows平台下信号量的API函数的使用；编制读写进程的模拟信息文件，里面包含多个读写进程的运行描述：编制读者-写者问题的写者优先算法，从进程模拟信息文件中取出进程信息，按要求启动对应的进程模拟程序，决定出读者/写者进程的运行次序。实验结果:银行家算法程序提供一个用户界面，可以在上边发出资源申请命令，系统应能给出是否可以接受申请，并且有结论输出；进程调度模拟程序根据一个进程调度文件，模拟进程的各种调度过程，用适合的表达方式表示出来。写者优先同步控制程序根据一个读写进程模拟信息文件，按照写者优先同步控制过程，用适合的表达方式表示出各读写进程的执行次序。进程调度模拟程序: jingchendiaodu.cpp#includestdio.h#include#include#definegetpch(type)(type*)malloc(sizeof(type)#defineNULL0structpcb/*定义进程控制块PCB*/charname10;charstate;intsuper;intntime;intrtime;structpcb*link;*ready=NULL,*p;typedefstructpcbPCB;sort()/*建立对进程进行优先级排列函数*/PCB*first,*second;intinsert=0;if(ready=NULL)|(p-super)(ready-super)/*优先级最大者,插入队首*/p-link=ready;ready=p;else/*进程比较优先级,插入适当的位置中*/first=ready;second=first-link;while(second!=NULL)if(p-super)(second-super)/*若插入进程比当前进程优先数大,*/*插入到当前进程前面*/p-link=second;first-link=p;second=NULL;insert=1;else/*插入进程优先数最低,则插入到队尾*/first=first-link;second=second-link;if(insert=0)first-link=p;input()/*建立进程控制块函数*/inti,num;clrscr();/*清屏*/printf(n请输入进程号?);scanf(%d,&num);for(i=0;iname);printf(n输入进程优先数:);scanf(%d,&p-super);printf(n输入进程运行时间:);scanf(%d,&p-ntime);printf(n);p-rtime=0;p-state=w;p-link=NULL;sort();/*调用sort函数*/intspace()intl=0;PCB*pr=ready;while(pr!=NULL)l+;pr=pr-link;return(l);disp(PCB*pr)/*建立进程显示函数,用于显示当前进程*/printf(nqnametstatetsupertndtimetruntimen);printf(|%st,pr-name);printf(|%ct,pr-state);printf(|%dt,pr-super);printf(|%dt,pr-ntime);printf(|%dt,pr-rtime);printf(n);check()/*建立进程查看函数*/PCB*pr;printf(n*当前正在运行的进程是:%s,p-name);/*显示当前运行进程*/disp(p);pr=ready;printf(n*当前就绪队列状态为:n);/*显示就绪队列状态*/while(pr!=NULL)disp(pr);pr=pr-link;destroy()/*建立进程撤消函数(进程运行结束,撤消进程)*/printf(n进程%s已完成.n,p-name);free(p);running()/*建立进程就绪函数(进程运行时间到,置就绪状态*/(p-rtime)+;if(p-rtime=p-ntime)destroy();/*调用destroy函数*/else(p-super)-;p-state=w;sort();/*调用sort函数*/main()/*主函数*/intlen,h=0;charch;input();len=space();while(len!=0)&(ready!=NULL)ch=getchar();h+;printf(nTheexecutenumber:%dn,h);p=ready;ready=p-link;p-link=NULL;p-state=R;check();running();printf(n按任一键继续.);ch=getchar();printf(nn进程已经完成.n);ch=getchar();银行家算法程序:/*子函数声明*/intIsprocessallover();/判断系统中的进程是否全部运行完毕voidSystemstatus();/显示当前系统中的资源及进程情况intBanker(int,int*);/银行家算法voidAllow(int,int*);/若进程申请不导致死锁，用此函数分配资源voidForbidenseason(int);/若发生死锁，则显示原因/*全局变量*/intAvailiable3=3,3,2;/初始状态，系统可用资源量intMax53=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;/各进程对各资源的最大需求量intAllocation53=0,1,0,2,0,0,3,0,2,2,1,1,0,0,2;/初始状态，各进程占有资源量intNeed53=7,4,3,1,2,2,6,0,0,0,1,1,4,3,1;/初始状态时，各进程运行完毕，还需要的资源量intover5=0,0,0,0,0;/标记对应进程是否得到所有资源并运行完毕#include/*主函数*/voidmain()intprocess=0;/发出请求的进程intdecide=0;/银行家算法的返回值intRequest3=0,0,0;/申请的资源量数组intsourcenum=0;/申请的各资源量/*判断系统中进程是否全部运行完毕*/step1:if(Isprocessallover()=1)cout系统中全部进程运行完毕！;return;/*显示系统当前状态*/Systemstatus();/*人机交互界面*/step2:coutprocess;if(process=0)cout放弃申请,退出系统！;return;if(process5|overprocess-1=1)cout系统无此进程！n;gotostep2;cout此进程申请各资源（A，B，C）数目：n;for(inth=0;h3;h+)coutchar(65+h)sourcenum;Requesth=sourcenum;/*用银行家算法判断是否能够进行分配*/decide=Banker(process,Request);if(decide=0)/*将此进程申请资源分配给它*/Allow(process,Request);gotostep1;else/*不能分配，显示原因*/Forbidenseason(decide);gotostep2;/*子函数Isprocessallover()的实现*/intIsprocessallover()intprocessnum=0;for(inti=0;i5;i+)/*判断每个进程是否运行完毕*/if(overi=1)processnum+;if(processnum=5)/*系统中全部进程运行完毕*/return1;elsereturn0;/*子函数Systemstatus()的实现*/voidSystemstatus()cout此刻系统中存在的进程：n;for(inti=0;i5;i+)if(overi!=1)coutPi+1;coutendl;cout此刻系统可利用资源（单位：个）：n;coutABCn;for(inta=0;a3;a+)coutAvailiablea;coutendl;cout此刻各进程已占有资源如下（单位：个）:nABCn;for(intb=0;b5;b+)if(overb=1)continue;coutPb+1;for(intc=0;c3;c+)coutAllocationbc;coutendl;cout各进程运行完毕还需各资源如下（单位：个）:nABCn;for(intf=0;f5;f+)if(overf=1)continue;coutPf+1;for(intg=0;g3;g+)coutNeedfg;coutendl;/*子函数Banker(int,int&)的实现*/intBanker(intp,int*R)intnum=0;/标记各资源是否能满足各进程需要intFinish5=0,0,0,0,0;/标记各进程是否安全运行完毕intwork5=0,0,0,0,0;/用于安全检查intAvailiableTest3;/用于试分配intAllocationTest53;/同上intNeedTest53;/同上/*判断申请的资源是否大于系统可提供的资源总量*/for(intj=0;jAvailiablej)/*返回拒绝分配原因*/return1;/*判断该进程申请资源量是否大于初始时其申明的需求量*/for(inti=0;iNeedp-1i)/*返回拒绝原因*/return2;/*为检查分配的各数据结构赋初值*/for(intt=0;t3;t+)AvailiableTestt=Availiablet;for(intu=0;u5;u+)for(intv=0;v3;v+)AllocationTestuv=Allocationuv;for(intw=0;w5;w+)for(intx=0;x3;x+)NeedTestwx=Needwx;/*进行试分配*/for(intk=0;k3;k+)/修改NeedTestAvailiableTestk-=*(R+k);AllocationTestp-1k+=*(R+k);NeedTestp-1k-=*(R+k);/*检测进程申请得到满足后，系统是否处于安全状态*/for(intl=0;l3;l+)workl=AvailiableTestl;for(intm=1;m=5;m+)for(intn=0;n5;n+)num=0;/*寻找用此刻系统中没有运行完的进程*/if(Finishn=0&overn!=1)for(intp=0;p3;p+)if(NeedTestnp=workp)num+;if(num=3)for(intq=0;q3;q+)workq=workq+AllocationTestnq;Finishn=1;for(intr=0;r5;r+)if(Finishr=0&overr!=1)/*返回拒绝分配原因*/return3;return0;/*子函数Allow(int,int&)的实现*/voidAllow(intp,int*R)cout可以满足申请！;staticintovernum;/*对进程所需的资源进行分配*/for(intt=0;t3;t+)Availiablet=Availiablet-*(R+t);Allocationp-1t=Allocationp-1t+*(R+t);Needp-1t=Needp-1t-*(R+t);/*分配后判断其是否运行完毕*/overnum=0;for(intv=0;v3;v+)if(Needp-1v=0)overnum+;if(overnum=3)/*此进程运行完毕，释放其占有的全部资源*/for(intq=0;q3;q+)Availiableq=Availiableq+Allocationp-1q;/*标记该进程运行完毕*/overp-1=1;cout进程Pp所需资源全部满足，此进程运行完毕！n;/*子函数Forbidenseason(int)的实现*/voidForbidenseason(intd)cout不能满足申请，此进程挂起，原因为：n;switch(d)case1:cout申请的资源量大于系统可提供的资源量！;break;case2:cout申请的资源中有某种资源大于其声明的需求量！;break;case3:cout若满足申请，系统将进入不安全状态，可能导致死锁！;实验二、存储器管理实验目的：理解各类置换算法的原理和虚拟存储器管理的方法。实验内容： 编程实现LRU算法或CLOCK/改进算法等置换算法（二选一），模拟实现虚拟存储器的地址变换过程。实验步骤：l 理解LRU或CLOCK改进算法等置换算法；设计与算法相关的数据结构，如：LRU的堆栈或CLOCK改进算法中的循环结构；按照最多5块的内存分配情况，编程实现所选算法，动态输入访问内存的块号序列，输出置换结果；测试：输入合法、非法的访问序列数据，检查程序的正确性和健壮性。l 理解虚拟存储器的地址变换过程；设计用于模拟快表、页表、地址变换所用的寄存器的数据结构；编制页表的初始信息文件，举例说明文件中具有的信息：共有5块，每块的状态、在内存和外存的起始地址等。编程实现虚拟存储器地址变换算法程序