操作系统实验(进程调度存储管理磁盘调度银行家算法.docx

《操作系统实验(进程调度存储管理磁盘调度银行家算法.docx》由会员分享，可在线阅读，更多相关《操作系统实验(进程调度存储管理磁盘调度银行家算法.docx（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验三 进程调度一、 实验目的多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。二、 实验要求1 设计进程调度算法，进程数不定2 包含几种调度算法，并加以实现3 输出进程的调度过程进程的状态、链表等。三、 参考例1 题目优先权法、轮转法简化假设1） 进程为计算型的（无I/O）2） 进程状态：ready、running、finish3） 进程需要的CPU时间以时间片为单位确定2 算法描述1） 优先权法动态优先权当前运行进程用完时间片后，其优先权减去一个常数。2） 轮转

2、法开始键盘输入进程数n，和调度方法的选择优先权法？轮转法产生n个进程，对每个进程产生一个PCB，并用随机数产生进程的优先权及进程所需的CPU时间按优先权大小，把n个进程拉成一个就绪队列初始化其他数据结构区链首进程投入运行时间片到，进程所需的CPU时间减1，优先权减3，输出个进程的运行情况所需的CPU时间=0？撤销进程就绪队列为空？结束将进程插入就绪队列NYNYYBN四、 实验流程图产生n个进程，对每个进程用随机数产生进程的轮转时间片数及进程所需的时间片数，已占用CPU的时间片数置为0按进程产生的先后次序拉成就绪队列链链首进程投入运行时间片到，进程所需时间片数减1，已占用CPU时间片数加1输出各

3、进程的运行情况进程所需时间片数=0？撤销该进程就绪队列为空吗？占用CPU的时间片数=轮转时间片数？占用CPU的时间片数置为0把该进程插入就绪队列尾BNYNYY结束N注意：1 产生的各种随机数的取值范围加以限制，如所需的CPU时间限制在120之间。2 进程数n不要太大通常取48个3 使用动态数据结构4 独立编程5 至少三种调度算法6 若有可能请在图形方式下，将PCB的调度用图形成动画显示。五实验过程：（1）输入：进程流文件（1.txt），其中存储的是一系列要执行的进程， 每个作业包括四个数据项：进程名 进程状态(1就绪 2等待 3运行) 所需时间 优先数(0级最高)进程0 1 50 2进程1 2

4、 10 4进程2 1 15 0进程3 3 28 5 进程4 2 19 1进程5 3 8 7输出: 进程执行流等待时间，平均等待时间本程序包括:FIFO算法，优先数调度算法，时间片轮转调度算法（2）程序代码#include #include #includeconst int block_time=10; /定义时间片的长度为10秒 const int MAXPCB=100; /定义最大进程数/定义进程结构体 typedef struct nodechar name20; int status;int time; int privilege;int finished; int wait_time

5、; pcb;pcb pcbsMAXPCB; int quantity;/初始化函数 void initial() int i;for(i=0;iMAXPCB;i+) strcpy(pcbsi.name,); pcbsi.status=0; pcbsi.time=0;pcbsi.privilege=0;pcbsi.finished=0; pcbsi.wait_time=0; quantity=0;/读数据函数 int readData() FILE *fp; char fname20; int i;coutfname; if(fp=fopen(fname,r)=NULL) cout错误,文件打不

6、开,请检查文件名endl; else while(!feof(fp) fscanf(fp,%s %d %d %d,pcbsquantity.name,&pcbsquantity.status,&pcbsquantity.time,&pcbsquantity.privilege); quantity+; /输出所读入的数据 cout输出所读入的数据endl; cout进程名 进程状态 所需时间 优先数endl; for(i=0;iquantity;i+) cout pcbsi.name pcbsi.status pcbsi.time pcbsi.privilegeendl; return(1);

7、 return(0);/重置数据,以供另一个算法使用 void init() int i;for(i=0;iMAXPCB;i+)pcbsi.finished=0; pcbsi.wait_time=0; /先进先出算法 void FIFO() int i,j; int total;/输出FIFO算法执行流 coutendl*endl; coutFIFO算法执行流:endl; cout进程名 等待时间endl; for(i=0;iquantity;i+) cout pcbsi.name pcbsi.wait_timeendl; for(j=i+1;jquantity;j+) pcbsj.wait_

8、time+=pcbsi.time; total=0; for(i=0;iquantity;i+) total+=pcbsi.wait_time; cout总等待时间:total 平均等待时间:total/quantityendl;/优先数调度算法 void privilege() int i,j,p; int passed_time=0; int total;int queueMAXPCB; int current_privilege=1000;for(i=0;iquantity;i+) current_privilege=1000; for(j=0;jquantity;j+) if(pcbs

9、j.finished=0)&(pcbsj.privilegecurrent_privilege) p=j; current_privilege=pcbsj.privilege; queuei=p;pcbsp.finished=1; pcbsp.wait_time+=passed_time; passed_time+=pcbsp.time; /输出优先数调度执行流 coutendl*endl; cout优先数调度执行流:endl; cout进程名 等待时间endl; for(i=0;iquantity;i+) cout pcbsqueuei.name pcbsqueuei.wait_timeen

10、dl; total=0; for(i=0;iquantity;i+) total+=pcbsi.wait_time; cout总等待时间:total 平均等待时间:total/quantityendl;/时间片轮转调度算法 void timer() int i,j,number,flag=1; int passed_time=0; int max_time=0; int round=0; int queue1000; int total=0;while(flag=1) flag=0; number=0;for(i=0;i1)for(i=0;iquantity;i+) if(pcbsi.fini

11、shed=0) flag=1; queuetotal=i; total+; if(pcbsi.time=block_time*(round+1) pcbsi.finished=1; round+; if(queuetotal-1=queuetotal-2) total-; coutendl*endl; cout时间片轮转调度执行流:endl; for(i=0;itotal;i+) coutpcbsqueuei.name ;coutendl;/显示void version() cout /* 进程调度 */; coutendlendl; /主函数 void main() int flag;ver

12、sion();initial();flag=readData();if(flag=1) FIFO(); init();privilege(); init();timer(); （3）运行结果：输入进程流文件名1.txt即可得出以下输出结果： 实验二 银行家算法一、 实验目的死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。二、 实验要求设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程

13、的申请动态的分配资源。系统能显示各个进程申请和释放资源，以及系统动态分配资源的过程，便于用户观察和分析；三、 数据结构1 可利用资源向量Available ，它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available（j）=k，标是系统中现有Rj类资源k个。2 最大需求矩阵Max，这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max（i，j）=k，表示进程i需要Rj类资源的最大数目为k。3 分配矩阵Allocation，这是一个nm的矩

14、阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Allocation（i，j）=k，表示进程i当前已经分到Rj类资源的数目为k。Allocation i表示进程i的分配向量，有矩阵Allocation的第i行构成。4 需求矩阵Need，这是一个nm的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need（i，j）=k，表示进程i还需要Rj类资源k个，才能完成其任务。Need i表示进程i的需求向量，由矩阵Need的第i行构成。上述三个矩阵间存在关系：Need（i，j）=Max（i，j）-Allocation（i，j）；四、 银行家算法Request i 是进程Pi 的请求向

15、量。Request i （j）=k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后，系统按下述步骤进行检查：1 如果Request i Need，则转向步骤2；否则，认为出错，因为它所请求的资源数已超过它当前的最大需求量。2 如果Request i Available，则转向步骤3；否则，表示系统中尚无足够的资源满足Pi的申请，Pi必须等待。3 系统试探性地把资源分配给进程Pi，并修改下面数据结构中的数值：Available = Available - Request iAllocation i= Allocation i+ Request iNeed i= Need i - Requ

16、est i4 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。假定系统有5个进程（p0,p1,p2,p3,p4）和三类资源（A，B，C），各种资源的数量分别为10，5，7，在T0时刻的资源分配情况如下图： Max Allocation Need Available A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 3 3 2 ( 2 3 0 )P1 3 2 2 2 0 0 1 2 2 (3 0 2 ) (0 2 0 )P2 9 0

17、 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1五、 安全性算法1 设置两个向量。Work：它表示系统可提供给进程继续运行的各类资源数目，它包含m个元素，开始执行安全性算法时，Work = Available。Finish：它表示系统是否有足够的资源分配给进程，使之运行完成，开始Finish（I）=false；当有足够资源分配给进程Pi时，令Finish（i）=true；2 从进程集合中找到一个能满足下述条件的进程。Finish（i）= = false；Need i work；如找到则执行步骤3；否则，执行步骤4；3 当进程Pi获得资

18、源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行Work = work + Allocation i Finish（i）=true；转向步骤2；4 若所有进程的Finish（i）都为true，则表示系统处于安全状态；否则，系统处于不安全状态。六、 系统流程图开 始输入资源数m, 及各类资源总数，初始化Available向量输入进程数n，i=1输入进程i的最大需求向量max。inmax资源总数提示错误重新输入i加1任选一个进程作为当前进程输入该进程的资源请求量Request 调用银行家算法，及安全性算法，完成分配，或并给出提示该进程的Need向量为0该进程已运行结束Need矩阵为0所有

19、进程运行都结束结 束NYYNNY初始化need 矩阵NY 七银行家算法程序代码#include#include#includeusing namespace std;typedef struct Max1 / 资源的最大需求量int m_a;int m_b;int m_c;Max; typedef struct Allocation1 /已分配的资源数int a_a;int a_b;int a_c;Allocation; typedef struct Need1 /还需要的资源数int n_a;int n_b;int n_c;Need; struct Available1 /可利用的资源量in

20、t av_a;int av_b;int av_c; q;struct pr /定义一个结构char name;Max max;Allocation allocation;Need need;int finishflag;p5;char na5;/*void init() /读入文件1.txtcout各进程还需要的资源数NEED：endl;FILE *fp;fp=fopen(1.txt,r+); / 打开文件1.txtfor(int i=0;i5;i+)fscanf(fp,%c,%d,%d,%d,%d,%d,%dn,&pi.name,&pi.max.m_a,&pi.max.m_b,&pi.max

21、.m_c,&pi.allocation.a_a,&pi.allocation.a_b,&pi.allocation.a_c);pi.need.n_a=pi.max.m_a-pi.allocation.a_a;pi.need.n_b=pi.max.m_b-pi.allocation.a_b;pi.need.n_c=pi.max.m_c-pi.allocation.a_c;coutpi.name: pi.need.n_a pi.need.n_b pi.need.n_cendl;fclose(fp); /关闭文件/*int fenpei()/分配资源coutAvailable:;coutq.av_a

22、 q.av_b q.av_cendl;int finishcnt=0,k=0,count=0;for(int j=0;j5;j+)pj.finishflag=0;while(finishcnt5)for(int i=0;i=pi.need.n_a&q.av_b=pi.need.n_b&q.av_c=pi.need.n_c)q.av_a+=pi.allocation.a_a;q.av_b+=pi.allocation.a_b;q.av_c+=pi.allocation.a_c;pi.finishflag=1;finishcnt+;nak+=pi.name;break;count+;/禁止循环过多

23、if(count5)return 0;return 1;/*int shq() /申请资源int m=0,i=0,j=0,k=0; /m为进程号; i,j,k为申请的三类资源数 cout请输入进程号和请求资源的数目!endl;cout如：进程号 资源A B Cendl;cout 0 2 0 2mijk;if(i=pm.need.n_a&j=pm.need.n_b &k=pm.need.n_c)if(i=q.av_a&j=q.av_b&k=q.av_c)pm.allocation.a_a+=i;pm.allocation.a_b+=j;pm.allocation.a_c+=k;pm.need.n

24、_a=pm.max.m_a-pm.allocation.a_a;pm.need.n_b=pm.max.m_b-pm.allocation.a_b;pm.need.n_c=pm.max.m_c-pm.allocation.a_c;cout各进程还需要的资源数NEED:n;for(int w=0;w5;w+) coutpw.name: pw.need.n_a pw.need.n_b pw.need.n_cendl;return 1;elsecoutAvailable让进程m等待.endl;else coutNeed,让进程m等待.endl;return 0;/*void main()int fla

25、g;char c;cout /* 银 行 家 算 法*/ endl;cout确认已经在1.txt文档中正确输入各进程的有关信息后按回车键endl;getch();init();q.av_a=10; /各种资源的数量q.av_b=5;q.av_c=7;while(flag)for(int i=0;i5;i+)q.av_a-= pi.allocation.a_a;q.av_b-= pi.allocation.a_b;q.av_c-= pi.allocation.a_c;if(fenpei()cout这样配置资源是安全的!endl;cout其安全序列是： ;for(int k=0;k5;k+)cou

26、tnak;coutendl;cout有进程发出Request请求向量吗?(Enter y or Y)endl;coutendl;c=getch();if(c=y|c=Y)if(shq()continue;else break;else flag=0;else flag=0;cout不安全!endl;八运行结果实验三 存储管理一 实验目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。二 实验内容（1） 通过计算不同算法的命中率比较算法的优劣。同时也

27、考虑了用户内存容量对命中率的影响。页面失效次数为每次访问相应指令时，该指令所对应的页不在内存中的次数。在本实验中，假定页面大小为1k，用户虚存容量为32k，用户内存容量为4页到32页。（2） produce_addstream通过随机数产生一个指令序列，共320条指令。A、 指令的地址按下述原则生成：1） 50%的指令是顺序执行的2） 25%的指令是均匀分布在前地址部分3） 25%的指令是均匀分布在后地址部分B、 具体的实施方法是：1） 在0，319的指令地址之间随机选取一起点m；2） 顺序执行一条指令，即执行地址为m+1的指令；3） 在前地址0，m+1中随机选取一条指令并执行，该指令的地址为

28、m；4） 顺序执行一条指令，地址为m+1的指令5） 在后地址m+2，319中随机选取一条指令并执行；6） 重复上述步骤1）5），直到执行320次指令C、 将指令序列变换称为页地址流在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第0页（对应虚存地址为0，9）；第10条第19条指令为第1页（对应虚存地址为10，19）；。第310条第319条指令为第31页（对应虚存地址为310，319）；按以上方式，用户指令可组成32页。（3） 计算并输出下属算法在不同内存容量下的命中率。1） 先进先出的算法（FIFO）；2） 最近最少使用算法（LRU）；3）

29、 最佳淘汰算法（OPT）；4） 最少访问页面算法（LFR）；其中3）和4）为选择内容开 始生成地址流输入算法号S1S4形成地址页号用户内存空间msize=2Msize32 OPT()FIFO()LRU()LFU()Msize加1S=? 是否用其他算法继续结 束NY1234YN提示出错，重新输入三 系统框图四页面置换算法程序代码：#include #include #includeconst int MAXSIZE=1000;/定义最大页面数 const int MAXQUEUE=3;/定义页框数typedef struct node int loaded; int hit; page;page

30、 pagesMAXQUEUE; /定义页框表 int queueMAXSIZE; int quantity; /初始化结构函数 void initial() int i; for(i=0;iMAXQUEUE;i+) pagesi.loaded=-1; pagesi.hit=0; for(i=0;iMAXSIZE;i+) queuei=-1; quantity=0; /初始化页框函数 void init() int i; for(i=0;iMAXQUEUE;i+) pagesi.loaded=-1; pagesi.hit=0; /读入页面流void readData() FILE *fp; ch

31、ar fname20;int i;coutfname;if(fp=fopen(fname,r)=NULL) cout错误,文件打不开,请检查文件名; else while(!feof(fp) fscanf(fp,%d ,&queuequantity);quantity+; cout读入的页面流:; for(i=0;iquantity;i+)coutqueuei ; /FIFO调度算法void FIFO() int i,j,p,flag;int absence=0;p=0;coutendl-endl; cout先进先出调度算法(FIFO)页面调出流:; for(i=0;iquantity;i+)

32、 flag=0; for(j=0;j=MAXQUEUE) coutpagesp.loaded ; pagesp.loaded=queuei; p=(p+1)%MAXQUEUE; absence+; absence-=MAXQUEUE; coutendl总缺页数:absenceendl; /最近最少使用调度算法（LRU）void LRU() int absence=0; int i,j; int flag;for(i=0;iMAXQUEUE;i+) pagesi.loaded=queuei; coutendl-endl; cout最近最少使用调度算法(LRU)页面流:;for(i=MAXQUEU

33、E;iquantity;i+) flag=-1; for(j=0;jMAXQUEUE;j+) if(queuei=pagesj.loaded) flag=j; /CAUTION pages0是队列头if(flag=-1) /缺页处理coutpages0.loaded ; for(j=0;jMAXQUEUE-1;j+) pagesj=pagesj+1; pagesMAXQUEUE-1.loaded=queuei;absence+; else /页面已载入 pagesquantity=pagesflag;for(j=flag;jMAXQUEUE-1;j+) pagesj=pagesj+1; pagesMAXQUEUE-1=pagesquantity;coutendl总缺页数:absenceendl; /显示 void version