操作系统课程设计报告14831

课 程 设 计 说 明 书设计题目： 操作系统课程设计 班 级： 信息学管理与信息系统2011级 学 号： 201101051012 姓 名： 李克乾 山 东 科 技 大 学2013年12 月 11 日课 程 设 计 任 务 书学院 信息科学与工程 专业 信息学管理与信息系统 班级 2011-2 姓名 李克乾 一、课程设计题目： 操作系统课程设计 二、课程设计主要参考资料（1）Abraham Silberschatz & Peter Baer Galvin & Greg Gagne. Operating System Concepts（第七版 影印版）. 高等教育出版社. 2007.3. （2） c+面向对象程序设计 电子工业出版社 （3）计算机操作系统（第三版） 西安电子科技大学出版社 三、课程设计应解决的主要问题：（1）CPU调度算法的模拟实现 （2）死锁相关算法的实现 （3）磁盘调度算法的实现 四、课程设计相关附件（如：图纸、软件等）：（1） 程序源代码 （2） 五、任务发出日期： 2013-10-1 课程设计完成日期： 2014-1-1 指导教师签字： 指导教师对课程设计的评语成绩： 指导教师签字： 年 月 日设计1 CPU调度算法的模拟实现一、设计目的利用C+编写CPU调度算法，实现先来先服务调度算法FCFS、优先级调度算法PS、短作业优先调度算法SJF、时间片轮转调度算法RR的运行过程和实现的结果，针对模拟进程，利用编写的CPU调度算法对需要运行的进程进行调度。进行算法评价，计算平均周转时间和平均等待时间。二、设计要求针对模拟进程，利用CPU调度算法进行调度，最后要进行算法评价，计算平均周转时间和平均等待时间，并且输出调度结果和输出算法评价指标。调度所需的进程参数由输入产生（手工输入或者随机数产生）。三、设计说明时间片轮转算法需要输入相应的时间片，所以独立编写一个程序，系统主体结构如下： CPU调度算法先来先服务算法优先级调度算法 短作业优先调度算法时间片轮转调度算法实现的结构体如下：struct task_struct char name10; /*进程名称*/ int number; /*进程编号*/ float come_time; /*到达时间*/ float run_begin_time; /*开始运行时间*/ float run_time; /*运行时间*/ float run_end_time; /*运行结束时间*/ int priority; /*优先级*/ int order; /*运行次序*/ int run_flag; /*调度标志*/ tasksMAX;运用switch语句对输入的进程进行相应的算法运行，进入相应的算法函数后会对进程进行调度并输出结果，并对结果进行评估。1. 先来先服务算法（FCFS）可用于作业调度，也可用于进程调度。每次调度都是从后备队列中选择一个或者多个最先进入队列的作业或进程，将他们调入内存进行分配资源，创建进程，放入就绪队列并开始执行。实现函数：int fcfs() /*先来先服务*/主要实现方法如下：执行程序输入进程相关信息寻找第一进程将进程保存至调度列，并进行调度判断所有进程都被调度在未调度的算法中需找最先到达进程是否打印结果信息2. 短作业优先调度算法（SJF），即从后备队列中选择一个或几个估计运行时间最短的作业或进程对其分配资源，并进行调度执行。实现函数：int sjf() /*短作业优先*/主要实现方法如下：执行程序输入进程信息判断最短服务时间进程把进程储存在调度序列并执行在未调度并已到达进程中寻找服务时间最短进程打印调度结果所有进程被调度否是3. 优先级调度算法即在将第一个到达的进程执行完毕后，会在此刻已经到达的进程或作业中选择优先权最高的一个或者几个进程对其进行资源分配并创建进程执行。实现函数：int ps() /*优先级调度*/主要实现方法如下：程序执行输入进程信息判断优先级最高进程把进程存储在调度序列并执行在未调度并已到达进程中寻找优先级最高进程打印调度结果所有进程被调度否是4. 在时间片调度算法的模拟实现中，时间片就是分配给进程运行的一段时间。在轮转法中，系统将所有的可运行（即就绪）进程按先来先服务的原则，排成一个队列，每次调度时把CPU分配给队首进程，并令其执行一个时间片。当某进程执行的时间片用完时，系统发出信号，通知调度程序，调度程序便据此信号来停止该进程的执行，并将刚运行的进程送到运行队列的末尾，等待下一次执行；然后，把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证运行队列中的所有进程，在一个给定的时间内，均能获得一时间片的处理机执行时间。实现函数（单独程序）主要实现方法如下：四、运行结果及分析设有如下3个进程：进程名称到达时间运行时间优先级A453B6101C582注：优先级一栏，数字大的表示优先级越高。根据本例来运行本算法，结果如下：采用先来先服务算法:采用优先级调度：采用短作业优先：时间片轮转算法：本程序已通过测试阶段，未出现进程调度错误情况。运行程序后，只需按照提示输入相应的进程的信息（进程名尽量输入单个字母）后选择需要的调度算法即可得出相应结果，并且可以循环运行多次。后期进行相应的美化加工，如需要，可进行可视化改造。结果分析：对于进程调度后得出的各项数据基本准确，当输入时间或其他数据信息出现精确度较高的数值时可能会出现一些误差，属于误差范围之内。程序基本可以实现CPU调度算法的过程解释。五、总结通过此次课程设计，更深入的理解了各个进程调度算法，及实现过程。在此过程中，遇到了困难，能及时请教同学，查询相关资料，及时解决了问题，但仍有不足之处，将会在今后学习中更加努力。六附录（完整代码）#includeusing namespace std;#define MAX 10struct task_struct char name10; /*进程名称*/ int number; /*进程编号*/ float come_time; /*到达时间*/ float run_begin_time; /*开始运行时间*/ float run_time; /*运行时间*/ float run_end_time; /*运行结束时间*/ int priority; /*优先级*/ int order; /*运行次序*/ int run_flag; /*调度标志*/ tasksMAX;int counter; /*实际进程个数*/int fcfs(); /*先来先服务*/int ps(); /*优先级调度*/int sjf(); /*短作业优先*/int hrrn(); /*响应比高优先*/int pinput(); /*进程参数输入*/int poutput(); /*调度结果输出*/int main() int option;pinput();printf(请选择调度算法（04）:n);printf(1.先来先服务n);printf(2.优先级调度n);printf(3.短作业优先n);printf(0.退出n);scanf(%d,&option);switch (option) case 0: printf(运行结束。n); break; case 1: printf(对进程按先来先服务调度。nn); fcfs(); break;case 2: printf(对进程按优先级调度。nn); ps(); break;case 3: printf(对进程按短作业优先调度。nn); sjf(); break;int fcfs() /*先来先服务*/float time_temp=0;int i;int number_schedul;time_temp=tasks0.come_time;for(i=0;icounter;i+) tasksi.run_begin_time=time_temp; tasksi.run_end_time=tasksi.run_begin_time+tasksi.run_time; tasksi.run_flag=1; time_temp=tasksi.run_end_time; number_schedul=i; tasksnumber_schedul.order=i+1;poutput();return main();int ps() /*优先级调度*/float temp_time=0;int i=0,j;int number_schedul,temp_counter;int max_priority;max_priority=tasksi.priority;j=1;while (jtasksi.priority) max_priority=tasksj.priority; i=j; j+; /*查找第一个被调度的进程*/*对第一个被调度的进程求相应的参数*/number_schedul=i;tasksnumber_schedul.run_begin_time=tasksnumber_schedul.come_time;tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time;tasksnumber_schedul.run_flag=1;temp_time=tasksnumber_schedul.run_end_time;tasksnumber_schedul.order=1;temp_counter=1;while (temp_countercounter) max_priority=0; for(j=0;jcounter;j+) if(tasksj.come_timemax_priority) max_priority=tasksj.priority; number_schedul=j; /*查找下一个被调度的进程*/ /*对找到的下一个被调度的进程求相应的参数*/ tasksnumber_schedul.run_begin_time=temp_time; tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time;tasksnumber_schedul.run_flag=1;temp_time=tasksnumber_schedul.run_end_time;temp_counter+;tasksnumber_schedul.order=temp_counter; poutput();return main();int sjf() /*短作业优先*/float temp_time=0;int i=0,j;int number_schedul,temp_counter;float run_time;run_time=tasksi.run_time;j=1;while (jcounter)&(tasksi.come_time=tasksj.come_time) if (tasksj.run_timetasksi.run_time) run_time=tasksj.run_time; i=j; j+; /*查找第一个被调度的进程*/*对第一个被调度的进程求相应的参数*/number_schedul=i;tasksnumber_schedul.run_begin_time=tasksnumber_schedul.come_time;tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time;tasksnumber_schedul.run_flag=1;temp_time=tasksnumber_schedul.run_end_time;tasksnumber_schedul.order=1;temp_counter=1;while (temp_countercounter) for(j=0;jcounter;j+) if(tasksj.come_time=temp_time)&(!tasksj.run_flag) run_time=tasksj.run_time;number_schedul=j;break; for(j=0;jcounter;j+) if(tasksj.come_time=temp_time)&(!tasksj.run_flag) if(tasksj.run_timerun_time) run_time=tasksj.run_time; number_schedul=j; /*查找下一个被调度的进程*/ /*对找到的下一个被调度的进程求相应的参数*/ tasksnumber_schedul.run_begin_time=temp_time; tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time; tasksnumber_schedul.run_flag=1; temp_time=tasksnumber_schedul.run_end_time; temp_counter+; tasksnumber_schedul.order=temp_counter; poutput();return main();int pinput() /*进程参数输入*/ int i; printf(please input the process counter:n); scanf(%d,&counter);if(counter=0)return 0;elsefor(i=0;icounter;i+) printf(*n); printf(please input the process of %d th :n,i+1); printf(please input the name:n); scanf(%s,tasksi.name); printf(please input the come_time:n); scanf(%f,&tasksi.come_time); printf(please input the run_time:n); scanf(%f,&tasksi.run_time); printf(please input the priority:n); scanf(%d,&tasksi.priority); tasksi.run_begin_time=0; tasksi.run_end_time=0; tasksi.order=0; tasksi.run_flag=0;return 0;int poutput() /*调度结果输出*/int i;float turn_round_time=0,f1,w=0;printf(name come_time run_time run_begin_time run_end_time priority order turn_round_timen);for(i=0;icounter;i+) f1=tasksi.run_end_time-tasksi.come_time; turn_round_time+=f1; w+=(f1/tasksi.run_time); printf( %s, %5.3f, %5.3f, %5.3f, %5.3f, %d, %d, %5.3fn,tasksi.name,tasksi.come_time,tasksi.run_time,tasksi.run_begin_time,tasksi.run_end_time,tasksi.priority,tasksi.order,f1);printf(average_turn_round_timer=%5.2fn,turn_round_time/counter);printf(weight_average_turn_round_timer=%5.2fn,w/counter);return 0;#include #include #define Myprintf printf(|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n)typedef struct PCBint ID;int ReachTime;int TotalTime;PCB;/进程号，到达时间和服务时间typedef struct NOTE /备份int ID;int TotalTime;NOTE;PCB A100; /5个进程PCB a100;NOTE temp;int queue50; /记录调度的进程int K=0;/调度进程数组的标识void INIT(int M)/初始化int i;int m;m=M;for(i=0;im;i+)Ai.ID=-1;int GetNum(int M)/计算进程数int m;m=M;int i;int j=0;for(i=0;im;i+)if(Ai.ID!=-1)j+;return j;int GetReach(int time,int M)/找出到达进程号int i;int m;m=M;for(i=0;im;i+)if(ai.ReachTime=time)ai.ReachTime=100;return i;return -1;int GetInsert(int M)/找出插入位置int i;int m;m=M;for(i=0;im;i+)if(Ai.ID=-1)return i;return -1;void Forward(int num)/前移int i;for(i=0;inum-1;i+)Ai.ID=Ai+1.ID;Ai.TotalTime=Ai+1.TotalTime;Anum-1.ID=-1;void Process(int Jiange)/执行进程 int jiange; jiange=Jiange;queueK=A0.ID;K+;A0.TotalTime=A0.TotalTime+jiange;temp.ID=A0.ID;temp.TotalTime=A0.TotalTime;int main()int i;int time;int t=0;int reach;int insert;int num;int M;int Jiange;printf(RR算法nn);printf(请输入进程个数n);scanf(%d,&M);printf(请输入R值n);scanf(%d,&Jiange);INIT(M);for(i=0;iM;i+)printf(请输入进程ID：);scanf(%d,&ai.ID);printf(请输入到达时间：);scanf(%d,&ai.ReachTime);printf(请输入服务时间：);scanf(%d,&ai.TotalTime);for(i=0;iM;i+)/运行时间t=t+ai.TotalTime;for(i=0;i50;i+)/初始化queuei=-1;for(time=0;time=t;time+)reach=GetReach(time,M);if(reach!=-1)/有进程到达insert=GetInsert(M);Ainsert.ID=areach.ID;Ainsert.TotalTime=areach.TotalTime;num=GetNum(M);if(num=1)continue;/进程数为1else/进程数不为1Process(Jiange);Forward(num);if(temp.TotalTime!=0)Anum-1.ID=temp.ID;Anum-1.TotalTime=temp.TotalTime;else/没有进程到达num=GetNum(M);if(num=1)/进程数为1Process(Jiange);if(temp.TotalTime=0)A0.ID=-1;else if(num=0)continue;/进程数为0elseProcess(Jiange);Forward(num);if(temp.TotalTime!=0)Anum-1.ID=temp.ID;Anum-1.TotalTime=temp.TotalTime;printf(n);printf(调度顺序为：n);Myprintf;for(i=0;i50;i+)if(queuei!=-1)printf(|%2d ,queuei);printf(|n);Myprintf;printf(n);return 0;设计2 死锁相关算法的实现一、设计目的编写算法，实现银行家算法、安全性算法、死锁检测算法判断系统安全状态、判断进程的资源请求是否可以被满足、判定系统是否为死锁状态。银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。二、设计要求其中算法所需的各种参数由输入产生（手工输入或者随机数产生）本模块课程设计的基本要求是能够输出各种判定结果（是否安全、安全序列、是否死锁、是否允许分配）。三、 设计说明1、算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。2、银行家算法步骤：（1）如果Requestior =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requestor=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： Available=Available-Requesti; Allocation=Allocation+Request;Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。 3、安全性算法步骤： （1）设置两个向量工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finishi=false，当有足够资源分配给进程时，令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程：Finishi=falseNeed0|requestij0)Finish=false判断开始运用c+实现对这三个算法的进行实现，通过自定义进程数和进程资源的各项数据情况对其进行分配，将其用函数分开，在实现每一步时进行调用。主要函数如下：showdata()/显示资源矩阵int changdata(int i)/进行资源分配int safe()/安全性算法void share()/利用银行家算法对申请资源对进行判定int compare(int *request,int *work,int N,int k) /如果Requestiwork则返回false，即对需求与现有资源的比较int check(int *work,int *request,int *allocation,int *finish,int *p,int m,int n)/调用安全公式进行检测void jiesuo(int *work,int *request,int *allocation,int *finish,int *p,int m,int n) /解锁函数voidoperate(int *work,int *request,int *allocation,int *finish,int *p,int m,int n)/操作函数int main()/主函数四、 运行结果及分析假设系统中有三个进程p，q，r和三类资源a，b，c，各种资源的数量分别为10,5,7，在T0时刻的资源分配情况如图资源情况进程Maxa b cAllocationa b cNeeda b c Availablea b c P7 5 3 0 1 07 4 33 3 2 Q3 2 22 0 01 2 2 R9 0 23 0 26 0 0运行程序后输入数据如图使用银行家算法所分配的情况和安全检查情况为死锁检测与排除的运行结果为这两个程序已经完成了对进程以资源之间检测与分配功能，并且能够在给出资源的分配情况后检测需求是否会发生死锁状况并给出解除方案。运行程序后只需按照提示操作即可观察到进程对资源的调用情况。五、 总结 多个进程同时运行时，系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列，使得系统能快速且安全地运行进程，不至发生死锁。银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。通过对算法的编写让我了解到计算机在调度进程时的具体过程，也明白了解决死锁的原理。六、附录#include#include#include#define False 0#define True 1int Max100100=0;/各进程所需各类资源的最大需求int Avaliable100=0;/系统可用资源char name100=0;/资源的名称int Allocation100100=0;/系统已分配资源int Need100100=0;/还需要资源int Request100=0;/请求资源向量int temp100=0;/存放安全序列int Work100=0;/存放系统可提供资源int p100=0;int q100100=0;int z100100=0;int M=100;/作业的最大数为100int N=100;/资源的最大数为100int gg=1;void showdata()/显示资源矩阵 int i,j; coutendl此时刻的资源分配情况为：endl; cout Max Allocation Need Avaliableendl; cout进程名 ; for(j=0;j4;j+) for(i=0;iN;i+) coutnamei ; cout ; coutendl; for(i=0;iM;i+) cout i ; for(j=0;jN;j+) coutMaxij ; cout ; for(j=0;jN;j+) coutAllocationij ; cout ; for(j=0;jN;j+) coutNeedij ;if(i=0) cout ; for (j=0;jN;j+) coutAvaliablej ;/输出分配资源 coutendl; int changdata(int i)/进行资源分配 int j;for (j=0;jM;j+) /pj=Avaliablej; Avaliablej=Avaliablej-Requestj; /qij=Allocationij; Allocationij=Allocationij+Requestj; /zij=Needij; Needij=Needij-Requestj;return 1;int safe()/安全性算法int i,d,k=0,m,h,s,apply,Finish100=0;int j;int flag=0;for(i=0;iN;i+)Worki=Avaliablei;coutendl 安全性检查 endl;cout Work Need Allocation Work+Allocation Finishendl;cout进程名 ;for(h=0;h4;h+) for(s=0;sN;s+) coutnames ; cout ; coutendl;for(i=0;iM;i+) apply=0; for(j=0;jN;j+) if (Finishi=False&Needij=Workj) apply+; if(apply=N) cout i ; for(d=0;dN;d+) coutWorkd ; cout ;for(d=0;dN;d+)coutNeedid ; cout ;for(d=0;dN;d+)coutAllocationid ; cout ; for(m=0;mN;m+) Workm=Workm+Allocationim; coutWorkm ; /变分配数 Finishi=True; tempk=i;cout ; couttrue ; coutendl;i=-1; k+; flag+; for(i=0;iM;i+) if(Finishi=False) for(j=0;jN;j+)Avaliablej=Avaliablej+Requestj; Allocationij=Allocationij-Requestj; Needij=Needij+Requestj; coutendl系统进入不安全状态！此时系统不分配资源！endl;/不成功系统不安全 return 0; coutendl此时系统是安全的!endl;/如果安全，输出成功 cout安全序列为:;for(i=0;iM;i+)/输出运行进程数组 couttempi; if(iM-1) cout; coutendl; return 0;void share()/利用银行家算法对申请资源对进行判定char ch;int i=0,j=0;ch=y;coutendl请输入要求分配的资源进程号(0-M-1i;/输入须申请的资源号coutendl请输入进程 i 申请的资源:endl;for(j=0;jN;j+) coutnamejRequestj;/输入需要申请的资源 for (j=0;jNeedij)/判断申请是否大于需求，若大于则出错 coutendl进程 i申请的资源大于它需要的资源; cout 分配不合理，不予分配！Avaliablej)/判断申请是否大于当前资源，若大于则 /出错 coutendl进程i申请的资源大于系统现在可利用的资源; cout 分配出错，不予分配!endl; ch=n; break; if(ch=y) changdata(i);/根据进程需求量变换资源 showdata();/根据进程需求量显示变换后的资源 safe();/根据进程需求量进行银行家算法判断 int main()/主函数 int t=1,i,j,number,choice,m,n,flag;char ming;cout*银行家算法的设计与实现*endl;coutendln;N=n;for(i=0;in;i+) cout资源i+1ming; namei=ming; coutnumber; Avaliablei=number;coutendl;coutm;M=m;coutendl请输入各进程的最大需求量(m*n矩阵)Max:endl;for(i=0;im;i+) for(j=0;jMaxij;do flag=0; coutendl请输入各进程已经申请的资源量(m*n矩阵)Allocation:endl; for(i=0;im;i+) for(j=0;jAllocationij; if(AllocationijMaxij) flag=1; Needij=Maxij-Allocationij; if(flag) coutendl申请的资源大于最大需求量，请重新输入!nendl;while(flag); showdata();/显示各种资源 safe();/用银行家算法判定系统是否安全while(1)if(t=1)coutendl 利用银行家算法预分配资源 endl;share();t=0;else break;coutendlt;coutendl; return 1;