银行家算法等

1、课内实验报告课 程 名： 操作系统 任课教师： 沈超 专 业： 信息管理与信息系统 学 号： 姓 名： 二一六至二一七 年度 第 一 学期南京邮电大学 经济与管理学院 操作系统 课程实验第 一 次实验报告实验内容及基本要求：实验项目名称：调度系统的设计与实现实验类型：设计每组人数： 1实验内容及要求： 实验内容:本次实验的主要内容是模拟调度系统的实现，包括高级、中级和低级调度的管理系统实现，调度算法的设计与实现以及银行家算法的设计设计与实现。本次实验主要包括两部分内容：1、模拟具有三级调度的计算机系统进程运行过程，设计进程调度算法，将其存入进程文件中。如：进程1：运行5秒后有3秒的I/O操作，

2、之后有10秒的运行，结束。可以写成：”p1:r5,io3,r3 e;”。编程实现调度算法函数，设计优先级、时间片大小和并发进程个数，系统不断从进程文件中读出进程信息，选择一种进程调度算法，模拟进程的运行及调度过程，比较不同算法在周转时间和平均周转时间上的差异。针对进程文件里面的数据为正常、缺项、格式不正确等各种情况，检测程序的执行结果。2、理解安全性算法和银行家算法的核心机制：针对3类资源、5个进程的情况，设计相应的数据结构，分别表示每个进程占用各类资源的情况；编程实现安全性算法函数，编制主函数，动态输入资源的占用情况，进程的资源申请，调用安全性函数，实现银行家算法；输入可分配和不可分配的请求

3、，测试系统的正确性。实验要求:进程调度模拟程序根据一个进程调度文件，模拟进程的各种调度过程，用适合的表达方式表示出来。银行家算法程序提供一个用户界面，可以在上边发出资源申请命令，系统应能给出是否可以接受申请，并且有结论输出。思考:1、 终端型进程流适合使用哪种调度算法？长批处理作业适合使用哪种调度算法？2、 动态优先级调度算法的优先级变化率应该如何设置？实验结果：1.进程调度过程的模拟（1）概述 选择一个调度算法，实现处理机调度。 设计要求： 1）进程调度算法包括：先来先服务算法，时间片轮转算法，最高优先数优先优先算法，动态优先级算法。 2）可选择进程数量3）本程序包括四种算法，用C或C+语言

4、实现，执行时在主界面选择算法（可用函数实现），进入子页面后输入进程数，（运行时间，优先数由随机函数产生），执行，显示结果。（2）设计原理1）先来先服务算法 FCFS 每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源创建进程，然后放入就绪队列。2）时间片轮转法RR 系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个

5、时间片。 (3) 最高优先数优先优先算法 SPF短进程优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。 #include<windows.h>#include<iostream>#include<string.h>using namespace std;#define P_NUM 3 /进程数#define P_TIME 2/时间片长度#define MIN -9999enum state /进程状态 ready, /就绪 run, /执行 wait, /阻

6、塞 finish /完成;class Pcbpublic: static void print(); Pcb();protected: char* name; /进程名 int allTime; /需要运行时间 int cpuTime; /已用cpu时间 state process; /进程状态;class HPcb:public Pcbpublic: static void print(); static void highS(); static int getFirst();private: int firstNum;HPcb hpcbP_NUM;class FPcb:public Pcb

7、public: static void print(); static void fcfs();private: int comeTime;FPcb fpcbP_NUM;class RPcb:public Pcbpublic:static void print();static void rr();RPcb rpcbP_NUM;void RPcb:rr() int ii,i=0; int k=0; for(;i<P_NUM;i+) char* ch; ch=new char1; cout<<"请输入第"<<i+1<<"个进

8、程的进程名、需要运行的时间："<<endl; cin>>ch; =new charstrlen(ch)+1; strcpy(,ch); cin>>rpcbi.allTime; rpcbi.cpuTime=0; cess=ready; do for(i=0;i<P_NUM;i+) if(cess=ready) rpcbi.cpuTime+=P_TIME; cess=run; if(rpcbi.cpuTime>=rpcbi.allTime)/该进程

9、执行完成 rpcbi.cpuTime-=P_TIME; system("cls"); print(); Sleep(1000); cess=finish; rpcbi.cpuTime=rpcbi.allTime;/防止所用时间超过总的时间 system("cls"); print(); Sleep(1000); else rpcbi.cpuTime-=P_TIME; system("cls"); print(); Sleep(1000); rpcbi.cpuTime+=P_TIME; cess=re

10、ady; for(i=0;i<P_NUM;i+)if(cess!=ready)k+;if(k=2) for(i=0;i<P_NUM;i+) if(cess=run) break; rpcbi.cpuTime+=P_TIME; cess=run; if(rpcbi.cpuTime>=rpcbi.allTime)/该进程执行完成 cess=finish; rpcbi.cpuTime=rpcbi.allTime;/防止所用时间超过总的时间 system("cls"); print(); Sl

11、eep(1000); else system("cls"); print(); Sleep(1000); cess=run; for(ii=0;ii<P_NUM;ii+)/用于判断是否还有进程未完成 if(cess!=finish) break; while(ii<P_NUM);/还有进程未完成 cout<<"所有进程已运行完成！"<<endl;void HPcb:highS() /最高优先数优先的调度算法 int ii,f,i=0; for(;i<P_NUM;i+) cha

12、r* ch; ch=new char1; cout<<"请输入第"<<i+1<<"个进程的进程名优先、需要运行的时间："<<endl; cin>>ch; =new charstrlen(ch)+1; strcpy(,ch); cin>>hpcbi.firstNum>>hpcbi.allTime; hpcbi.cpuTime=0; cess=ready; do f=getFirst(); hpcbf.cpuTime+

13、=P_TIME; hpcbf.firstNum-; cess=run; if(hpcbf.cpuTime>=hpcbf.allTime)/该进程执行完成 hpcbf.cpuTime-=P_TIME; system("cls"); print(); Sleep(1000); hpcbf.firstNum=MIN; cess=finish; hpcbf.cpuTime=hpcbf.allTime;/防止所用时间超过总的时间 system("cls"); print(); Sleep(1000); else hpcbf

14、.cpuTime-=P_TIME;/为了输出改变前的相关信息 hpcbf.firstNum+;/为了输出改变前的相关信息 system("cls"); print(); Sleep(1000); hpcbf.cpuTime+=P_TIME; hpcbf.firstNum-; cess=ready; for(ii=0;ii<P_NUM;ii+)/用于判断是否还有进程未完成 if(hpcbii.firstNum!=MIN) break; while(ii<P_NUM);/还有进程未完成 cout<<"所有进程已运行完成！&qu

15、ot;<<endl;Pcb:Pcb() delete name;void FPcb:fcfs() /先来先服务算法 int i=0; for(;i<P_NUM;i+) char* ch; ch=new char1; cout<<"请输入第"<<i+1<<"个进程的进程名,需要运行的时间："<<endl; cin>>ch; =new charstrlen(ch)+1; strcpy(,ch); cin>>fpcbi.allTim

16、e; eTime=i+1; fpcbi.cpuTime=0; cess=ready; for(i=0;i<P_NUM;i+) /P_NUM个进程 for(int j=0;j<fpcbi.allTime;j+=P_TIME) /每个进程所用时间 fpcbi.cpuTime+=P_TIME; /第i个进程所用时间加个时间片 if(fpcbi.cpuTime<fpcbi.allTime) /第i个进程还未完成 cess=run; /将其状态设为就绪态 if(fpcbi.cpuTime>=fpcbi.allTime) if(

17、i+1)!=P_NUM) /如果第i+1个进程不是最后一个进程,便于下一个程序从就绪状态到运行状态 fpcbi.cpuTime-=P_TIME; system("cls"); print(); Sleep(1000); fpcbi.cpuTime+=P_TIME; fpcbi.cpuTime=fpcbi.allTime; cess=finish; fpcbi+1.process=run; system("cls"); print(); Sleep(1000); else fpcbi.cpuTime-=P_TIME; system(&qu

18、ot;cls"); print(); Sleep(1000); cess=finish; fpcbi.cpuTime=fpcbi.allTime; system("cls"); print(); Sleep(1000); else fpcbi.cpuTime-=P_TIME; system("cls"); print(); Sleep(1000); fpcbi.cpuTime+=P_TIME; cout<<"所有进程已运行完成！"<<endl;int HPcb:getFirst()

19、/得到优先级最高的进程 int k=0; for(int i=1;i<P_NUM;i+) if(hpcbk.firstNum<hpcbi.firstNum) k=i; return k;void HPcb:print() cout<<"*"<<endl; cout<<"进程名"<<"t"<<"还需运行时间t"<<"已用CPU时间"<<"t"<<"优先级&quo

20、t;<<"t"<<"状态"<<endl; for(int i=0;i<P_NUM;i+) cout<<<<"tt"<<hpcbi.allTime-hpcbi.cpuTime<<"tt"<<hpcbi.cpuTime<<"t"<<hpcbi.firstNum<<"t" switch(cess) case

21、wait:cout<<"阻塞态"<<endl;break; case ready:cout<<"就绪态"<<endl;break; case run:cout<<"运行态"<<endl;break; case finish:cout<<"完成态"<<endl;break; cout<<"-"<<endl; cout<<endl;void RPcb:print() c

22、out<<"*"<<endl; cout<<"进程名"<<"t"<<"还需运行时间t"<<"已用CPU时间"<< "t"<<"状态"<<endl; for(int i=0;i<P_NUM;i+) cout<<<<"tt"<<rpcbi.allTime-rpcbi.cpu

23、Time<<"tt"<<rpcbi.cpuTime<<"t" switch(cess) case wait:cout<<"阻塞态"<<endl;break; case ready:cout<<"就绪态"<<endl;break; case run:cout<<"运行态"<<endl;break; case finish:cout<<"完成态"

24、;<<endl;break; cout<<"-"<<endl; cout<<endl;void FPcb:print() cout<<"*"<<endl; cout<<"进程名"<<"t"<<"还需运行时间t"<<"已用CPU时间"<<"t"<<"状态"<<endl; for(int

25、 i=0;i<P_NUM;i+) cout<<<<"tt"<<fpcbi.allTime-fpcbi.cpuTime<<"tt"<<fpcbi.cpuTime<<"t" switch(cess) case wait:cout<<"阻塞态"<<endl;break; case ready:cout<<"就绪态"<<endl;break;

26、 case run:cout<<"运行态"<<endl;break; case finish:cout<<"完成态"<<endl;break; cout<<"-"<<endl; cout<<endl;void main() char ch; cout<<"请选择算法：n1. 先来先服务算法n2. 时间片轮转调度算法n3.最高优先数优先的调度算法n"<<endl; cin>>ch; if(ch=&#

27、39;1') FPcb:fcfs(); else if(ch='2') RPcb:rr(); else if(ch='3') HPcb:highS();2. 安全性算法和银行家算法的核心机制银行家算法原理：我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全,银行家规定: (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; (2) 顾客可以分期贷款,但贷款的总数不能超过最大需求量; (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾

28、客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.   操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。银行家算法进程i发出请求资源申请， (1)如果Request j<=

29、needi,j,转向步骤(2),否则认为出错，因为他所需要的资源数已经超过它所宣布的最大值。 (2)如果：Request ij<=availablei,j，转向步骤(3)，否则表示尚无足够资源，进程i需等待。 (3)若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：  可利用资源向量Availablei,j= Availablei,j- 最大需求矩阵Request j； 分配矩阵Allocationij= Allocationij+ Request

30、60;j； 需求矩阵needij= needij- Request j； (4)试分配后，执行安全性检查，调用check()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。 (5)用dowhile 循环语句实现输入字符y/n判断是否继续进行资源申请。安全性检测算法(1) 设置两个向量： 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work= Available。 工作向量Finish，它表示系统是否有足够的资源

31、分配给进程，使之运行完成。开始时先做Finishi=false；当有足够的资源分配给进程时，再令Finishi=true。 (2)在进程中查找符合以下条件的进程： 条件1：Finishi=false；条件2：needij<=Workj 若找到，则执行步骤(3)否则，执行步骤(4) (3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj= Workj+ Allocationij；Finishi=true； goto step (2)；(4)如果所有的Finishi=true都满足，则表示系统处于安全状态，否则，处于不安全状态。流程图程序源代码#inclu

32、de <stdio.h> #include <stdlib.h> #include <conio.h> #include <iostream.h> # define m 50 int no1; /进程数int no2; /资源数 int r; int allocationmm,needmm,availablem,maxmm; char name1m,name2m; /定义全局变量 void main() void check(); void print(); int i,j,p=0,q=0; char c; int requestm,alloca

33、tion1mm,need1mm,available1m; printf("*n"); printf("* 银行家算法的设计与实现 *n"); printf("*n"); printf("请输入进程总数:n"); scanf("%d",&no1); printf("请输入资源种类数:n"); scanf("%d",&no2); printf("请输入Max矩阵:n"); for(i=0;i<no1;i+) for(j

34、=0;j<no2;j+) scanf("%d",&maxij); /输入已知进程最大资源需求量 printf("请输入Allocation矩阵:n"); for(i=0;i<no1;i+) for(j=0;j<no2;j+) scanf("%d",&allocationij); /输入已知的进程已分配的资源数for(i=0;i<no1;i+) for(j=0;j<no2;j+) needij=maxij-allocationij; /根据输入的两个数组计算出need矩阵的值 printf(

35、"请输入Available矩阵n"); for(i=0;i<no2;i+) scanf("%d",&availablei); /输入已知的可用资源数print(); /输出已知条件check(); /检测T0时刻已知条件的安全状态 if(r=1) /如果安全则执行以下代码 do q=0; p=0; printf("n请输入请求资源的进程号(04)：n"); for(j=0;j<=10;j+) scanf("%d",&i); if(i>=no1) printf("输入错误，

36、请重新输入：n"); continue; else break; while（i） printf("n请输入该进程所请求的资源数requestj:n"); for(j=0;j<no2;j+) scanf("%d",&requestj); for(j=0;j<no2;j+) if(requestj>needij) p=1; /判断请求是否超过该进程所需要的资源数 if(p) printf("请求资源超过该进程资源需求量，请求失败！n"); else for(j=0;j<no2;j+) if(re

37、questj>availablej) q=1; /判断请求是否超过可用资源数 if(q) printf("没有做够的资源分配，请求失败！n"); else /请求满足条件 for(j=0;j<no2;j+) available1j=availablej; allocation1ij=allocationij; need1ij=needij; /保存原已分配的资源数，仍需要的资源数和可用的资源数 availablej=availablej-requestj; allocationij+=requestj; needij=needij-requestj;/系统尝试把

38、资源分配给请求的进程 print(); check(); /检测分配后的安全性 if(r=0) /如果分配后系统不安全 for(j=0;j<no2;j+) availablej=available1j; allocationij=allocation1ij; needij=need1ij; /还原已分配的资源数，仍需要的资源数和可用的资源数 printf("返回分配前资源数n"); print(); printf("n你还要继续分配吗？Y or N ?n"); /判断是否继续进行资源分配 c=getche(); while(c='y'

39、;|c='Y'); void check() /安全算法函数 int k,f,v=0,i,j; int workm,am; bool finishm; r=1; for(i=0;i<no1;i+) finishi=false; / 初始化进程均没得到足够资源数并完成for(i=0;i<no2;i+) worki=availablei;/worki表示可提供进程继续运行的各类资源数k=no1; do for(i=0;i<no1;i+) if(finishi=false) f=1; for(j=0;j<no2;j+) if(needij>workj)

40、f=0; if(f=1) /找到还没有完成且需求数小于可提供进程继续运行的资源数的进程 finishi=true; av+=i; /记录安全序列号 for(j=0;j<no2;j+) workj+=allocationij; /释放该进程已分配的资源 k-; /每完成一个进程分配，未完成的进程数就减1 while(k>0); f=1; for(i=0;i<no1;i+) /判断是否所有的进程都完成 if(finishi=false) f=0; break; if(f=0) /若有进程没完成，则为不安全状态 printf("系统处在不安全状态！"); r=0

41、; else printf("n系统当前为安全状态，安全序列为：n"); for(i=0;i<no1;i+) printf("p%d ",ai); /输出安全序列 void print() /输出函数 int i,j; printf("n"); printf("*此时刻资源分配情况*n"); printf("进程名/号| Max | Allocation | Need |n"); for (i = 0; i < no1; i+) printf(" p%d/%d "

42、,i,i); for (j = 0; j < no2; j+) printf("%d ",maxij); for (j = 0; j < no2; j+) printf(" %d ",allocationij); for (j = 0; j < no2; j+) printf(" %d ",needij); printf("n"); printf("n"); printf("各类资源可利用的资源数为:"); for (j = 0; j < no2; j

43、+) printf(" %d",availablej); printf("n"); 小结：深刻学习了进程调度的三种算法和银行家算法，对其有了更深程度的理解，并且更深的理解了操作系统内部的运算方法，对此产生了浓厚的兴趣，课下也会深入去学习。成绩评定：该生对待本次实验的态度 认真 良好 一般 比较差。本次实验的过程情况 很好 较好 一般 比较差对实验结果的分析 很好 良好 一般 比较差文档书写符合规范程度 很好 良好 一般 比较差综合意见：成绩指导教师签名日期12.2 操作系统 课程实验第 二 次实验报告实验内容及基本要求：实验项目名称：内存分配算法模拟实现

44、实验类型：操作每组人数： 1实验内容及要求： 实验内容:本实验的主要内容是实现存储管理系统中的内存分配、地址变换和虚拟存储管理中的页面置换。具体内容包括三个方面：1、掌握动态分区分配的基本原理，设计动态分区分配系统，可以实现首次适应算法、最坏适应算法和最佳适应算法进行分区分配。2、理解虚拟存储器的地址变换过程，设计用于模拟快表、页表、地址变换所用的寄存器的数据结构。编制页表的初始信息文件，举例说明文件中具有的信息：共有5块，每块的状态、在内存和外存的起始地址等。编程实现虚拟存储器地址变换算法程序，动态输入所要访问的逻辑地址，变换过程文字描述以及变换后的物理地址；检查输入有效、无效地址，测试程序

45、的正确性和错误处理能力。3、编程实现LRU算法或CLOCK/改进算法等置换算法（二选一），模拟实现虚拟存储器的地址变换过程。理解LRU或CLOCK改进算法等置换算法；设计与算法相关的数据结构，如：LRU的堆栈或CLOCK改进算法中的循环结构；按照最多5块的内存分配情况，编程实现所选算法，动态输入访问内存的块号序列，输出置换结果；输入合法、非法的访问序列数据，检查程序的正确性和健壮性。实验要求:虚拟地址变换程序提供逻辑地址输入界面，形象地表示出变换成物理地址的过程与最后变换成的物理地址。置换算法程序提供内存访问序列的输入界面，输出正确的置换过程描述和置换结果。思考:1、 地址变换产生错误的原因有

46、哪些？2、 在页面置换过程中，为什么会出现抖动的情况？实验结果：Clock算法的思想：当某一页首次装入内存中时，则将该页框的使用位设置为1；当该页随后被访问到时（在访问产生缺页中断之后），它的使用位也会被设置为1。对于页面置换算法，用于置换算法，用于置换的候选页框集合（当前进程：局部范围；整个内存；全局范围）被看做是一个循环缓冲区，并且有一个指针与之相关联。当一页被置换时，该指针被设置成指向缓冲区中的下一页框。当需要置换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一页框。每当遇到一个使用位为1的页框时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有页框的使用位均为0时，则

47、选择遇到的第一个页框置换；如果所有页框的使用位均为1时，则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，置换该页框中的页。主函数模块  函数名称：int main() 功能：显示主菜单，调用函数  检测模块  函数名称：bool inblock(int num) 、bool inblock2(int num)  功能：检测读入的页号是否存在内存中、检测页号是否在内存中并把访问位和修改位置1  修改模块  函数名称：bool change()、int whichpage()  功能：判断页面是否已经被修改、判断内存中第几个需要被置换