实现FCFS和SJF调度算法

操作系统实验报告实验一：作业调度学院：软件学院专业：软件工程班级：软件工程12-01姓名：***学号：541213460157实验一：作业调度实现FCFS和SJF调度算法【实验题目】：编写程序，实现FCFS和SJF算法，模拟作业调度过程，加深对作业调度的理解。【实验内容】实现FCFS和SJF调度算法。–数据结构设计（JCB，后备作业队列）–算法实现与模拟（排序、调度）–输出调度结果，展示调度过程并解释【实验要求】1.设计作业控制块(JCB)的数据结构–应包含实验必须的数据项，如作业ID、需要的服务时间、进入系统时间、完成时间，以及实验者认为有必要的其他数据项。2.实现排序算法（将作业排队）–策略1：按“进入系统时间”对作业队列排序(FCFS)–策略2：按“需要的服务时间”对作业队列排序（SJF）3.实现调度过程模拟（1）每个作业用一个JCB表示，如果模拟FCFS，按策略1将作业排队，如果模拟SJF，按策略2将作业排队（2）选择队首的作业，将其从后备队列移出。（3）（作业运行过程，在本实验中，无需实现，可认为后备队列上的作业一但被调度程序选出，就顺利运行完毕，可以进入第4步）（4）计算选中作业的周转时间（5）进行下一次调度（去往第2步）4.实现结果输出–输出作业状态表，展示调度过程•初始作业状态（未调度时）•每次调度后的作业状态5.撰写实验报告–包含实验要求中1~4项内容，要求有设计图（结构图/流程图）和源代码。–注明使用的编程语言和环境。注意事项•实验中注重实现算法本质（先来先服务，短作业优先）。•两个算法可以使用一套程序，差别只在队列的排序方式。•这两个算法也可适用于进程调度。关于作业调度和进程调度的区别，只要求概念上理解清楚，不要求实现。设计作业控制块(JCB)的数据结构每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。具体结构如下：typedefstructjcb{charname[10];/*作业名*/charstate;/*作业状态*/intts;/*提交时间*/floatsuper;/*优先权*/inttb;/*开始运行时间*/inttc;/*完成时间*/floatti;/*周转时间*/floatwi;/*带权周转时间*/intntime;/*作业所需运行时间*/charresource[10];/*所需资源*/structjcb*next;/*结构体指针*/}JCB;JCB*p,*tail=NULL,*head=NULL;作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。，组成一个后备队列等待，总是首先调度等待队列中队首的作业。本实验采用链表的形式存放各后备队列当中的作业控制块，各个等待的作业按照提交时刻的先后次序排队。当一个作业进入系统时，就为其动态建立一作业控制块（JCB），挂入后备队列尾部。当作业调度时，从后备队列中按某种调度算法选择一作业，让其进入主存以便占用CPU执行。每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。设计图编程语言：c++编程环境：VisualC++6.0程序代码：FCFS：#includeiostreamusingnamespacestd;classFcfs{private:intnum[10];//作业编号doublearriveTime[10];//到达时间doublestartTime[10];//开始时间，进内存时间doubleworkTime[10];//工作时间doublefinishTime[10];//完成时间doublecirTime[10];//存放每一个作业的周转时间//doublefreeTime[10];//上一个作业已结束，但下一个作业还未到，存放这一段空闲时间public:Fcfs(intn)//n为作业数目{cout默认第一个作业的到达时间为0。endl;for(inti=0;in;i++){num[i]=i+1;//给作业编号cout第num[i]个作业：endl;cout请输入该作业的到达时间：;cinarriveTime[i];if(i==0)arriveTime[i]=0;//默认第一个作业的到达时间为0cout请输入该作业的执行时间：;cinworkTime[i];if(i==0){startTime[i]=0;finishTime[i]=workTime[i];//freeTime[i]=0;}elseif(arriveTime[i]=finishTime[i-1])//如果后一个作业已到，而前一个作业未结束{startTime[i]=finishTime[i-1];//则后一个作业的开始时间为上一个作业的结束时间finishTime[i]=startTime[i]+workTime[i];//freeTime[i]=0;//前一个一结束就开始工作，没有空闲时间}elseif(arriveTime[i]finishTime[i-1]){//freeTime[i]=arriveTime[i]-finishTime[i-1];//计算空闲时间，前一个作业已完成，但后一个作业还没到，中间空闲时间startTime[i]=arriveTime[i];//由于来的时候前一个作业已完成，则该作业的开始时间即为它的到达时间finishTime[i]=startTime[i]+workTime[i];}cirTime[i]=finishTime[i]-arriveTime[i];}}//计算平均周转时间doublegetAverageCir(intn)//n为作业数{doubleaverageCir,sumCir=0;for(inti=0;in;i++)sumCir+=cirTime[i];averageCir=sumCir/n;returnaverageCir;}//打印输出voidprint(intn)//n为作业数{coutnum\tarrive\tstart\twork\tfinish\tcir\tendl;for(inti=0;in;i++){coutnum[i]\tarriveTime[i]\tstartTime[i]\tworkTime[i]\tfinishTime[i]\tcirTime[i]\tendl;}coutendl;cout平均周转时间：getAverageCir(n)endl;}};intmain(){intn;//n为作业数目cout请输入作业数目：;cinn;Fcfsf=Fcfs(n);f.print(n);return0;}SJF:#includeiostreamusingnamespacestd;classSJF{private:intnum[10];//作业编号doublearriveTime[10];//到达时间doublestartTime[10];//开始时间，进内存时间doubleworkTime[10];//工作时间doublefinishTime[10];//完成时间doublecirTime[10];//存放每一个作业的周转时间public:SJF(intn)//n为作业数目{inti;cout默认第一个作业的到达时间为0。endl;for(i=0;in;i++){num[i]=i+1;//给作业编号cout第num[i]个作业：endl;cout请输入该作业的到达时间：;cinarriveTime[i];if(i==0)arriveTime[i]=0;//默认第一个作业的到达时间为0cout请输入该作业的执行时间：;cinworkTime[i];if(i==0){startTime[i]=0;finishTime[i]=workTime[i];cirTime[i]=finishTime[i]-arriveTime[i];}else//排序{for(intj=1;ji;j++)//i=当前作业数目-1，这里不能用num[i]表示当前作业数起泡排序法{for(intk=1;k=i-j;k++)if(workTime[k]workTime[k+1]){doubletemp;temp=num[k];num[k]=num[k+1];num[k+1]=temp;temp=arriveTime[k];arriveTime[k]=arriveTime[k+1];arriveTime[k+1]=temp;temp=workTime[k];workTime[k]=workTime[k+1];workTime[k+1]=temp;}}}}for(i=1;in;i++)//排序后计算各作业的开始、结束、周转时间{startTime[i]=finishTime[i-1];finishTime[i]=startTime[i]+workTime[i];cirTime[i]=finishTime[i]-arriveTime[i];}}//计算平均周转时间doublegetAverageCir(intn)//n为作业数{doubleaverageCir,sumCir=0;for(inti=0;in;i++)sumCir+=cirTime[i];averageCir=sumCir/n;returnaverageCir;}//打印输出voidprint(intn)//n为作业数{coutnum\tarrive\tstart\twork\tfinish\tcir\tendl;for(inti=0;in;i++){coutnum[i]\tarriveTime[i]\tstartTime[i]\tworkTime[i]\tfinishTime[i]\tcirTime[i]\tendl;}coutendl;cout平均周转时间：getAverageCir(n)endl;}};intmain(){cout-----短作业优先-----endl;intn;//n为作业数目cout请输入作业数目：;cinn;SJFf=SJF(n);f.print(n);return0;}实例截图：五个进程，到达时间分别为5，10，13，20服务时间分别为6,2,4,6设置选择量n，当n=1时，选择FCFS当n=2时，选择SJF当n=3时，同时分别调用FCFS和SJFn不为1或2或3时提示错误，重新输入n；1-FCFS算法2-SJF算法实验总结：本次实验题目为作业调度。实现实现FCFS和SJF调度算法。能初步掌握FCFS和SJF调度算法。对于FCFS和SJF调度算法的思路清晰，只是将其转化为代码形式，在脑海中，没有思路。经过查阅资料和与同学们交流，逐渐形成了一定的模块化思路。结合相关程序，在调试程序的过程中，意识到书写格式规范化及其重要性。明白了其中的功能。FCFS与SJF各有优缺点。对于FCFS，当先执行的是长作业时，由于FCFS对短作业长时间等待，不利于短作业。对于SJF，必须预知作业的运行时间，当短作业过多时，则不利于长作业。采用SJF算法时，人机无法实现交互。由于没有考虑到作业紧迫性，不能保证作业能够及时得到处理。选择哪一种算法，则根据具体情况而定。