实现FCFS和SJF调度算法

1、操作系统实验报告实验一：作业调度学院：软件学院专业：软件工程 班级：软件工程12-01 姓名：* 学号：541213460157实验一：作业调度实现FCFS和SJF调度算法【实验题目】：编写程序，实现FCFS和SJF算法，模拟作业调度过程，加深对作业调度的理解。【实验内容】实现FCFS和SJF调度算法。 数据结构设计（JCB，后备作业队列） 算法实现与模拟（排序、调度） 输出调度结果，展示调度过程并解释【实验要求】1. 设计作业控制块(JCB)的数据结构 应包含实验必须的数据项，如作业ID、需要的服务时间、进入系统时间、完成时间，以及实验者认为有必要的其他数据项。2. 实现排序算法（将作业排队

2、） 策略1：按“进入系统时间”对作业队列排序(FCFS) 策略2：按“需要的服务时间”对作业队列排序（SJF）3. 实现调度过程模拟（1）每个作业用一个JCB表示，如果模拟FCFS，按策略1将作业排队，如果模拟SJF，按策略2将作业排队（2）选择队首的作业，将其从后备队列移出。（3）（作业运行过程，在本实验中，无需实现，可认为后备队列上的作业一但被调度程序选出，就顺利运行完毕，可以进入第4步）（4）计算选中作业的周转时间（5） 进行下一次调度（去往第2步）4.实现结果输出 输出作业状态表，展示调度过程 初始作业状态（未调度时） 每次调度后的作业状态5.撰写实验报告 包含实验要求中14项内容，要

3、求有设计图（结构图/流程图）和源代码。 注明使用的编程语言和环境。注意事项 实验中注重实现算法本质（先来先服务，短作业优先）。 两个算法可以使用一套程序，差别只在队列的排序方式。 这两个算法也可适用于进程调度。关于作业调度和进程调度的区别，只要求概念上理解清楚，不要求实现。设计作业控制块(JCB)的数据结构 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。具体结构如下：  typedef struct jcbchar name10; /*

4、0;作业名 */       char state;  /* 作业状态 */      int ts; /* 提交时间 */      float super; /* 优先权 */ int tb; /* 开始运行时间 */

5、0;     int tc;  /* 完成时间 */      float ti;  /* 周转时间 */    float wi;  /* 带权周转时间 */     int ntime;  /* 作业所需运行时间 *

6、/      char resource10;  /* 所需资源 */        struct jcb *next;  /* 结构体指针 */          JCB; JCB *p,*tail=NULL,*head=NULL;

7、60; 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。，组成一个后备队列等待，总是首先调度等待队列中队首的作业。  本实验采用链表的形式存放各后备队列当中的作业控制块，各个等待的作业按照提交时刻的先后次序排队。当一个作业进入系统时，就为其动态建立一作业控制块（JCB），挂入后备队列尾部。当作业调度时，从后备队列中按某种调度算法选择一作业，让其进入主存以便占用CPU执行。 每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转

8、时间、带权平均周转时间。设计图编程语言：c+编程环境：Visual C+ 6.0程序代码：FCFS：#include <iostream> using namespace std; class Fcfs private: int num10; /作业编号 double arriveTime10; /到达时间 double startTime10; /开始时间，进内存时间 double workTime10; /工作时间 double finishTime10; /完成时间 double cirTime10; /存放每一个作业的周转时间 /double freeTime10; /上一

9、个作业已结束，但下一个作业还未到，存放这一段空闲时间 public: Fcfs(int n) /n为作业数目 cout<<"默认第一个作业的到达时间为0。"<<endl; for(int i=0;i<n;i+) numi=i+1; /给作业编号 cout<<"第"<<numi<<"个作业："<<endl; cout<<"请输入该作业的到达时间：" cin>>arriveTimei; if(i=0) arriveTi

10、mei=0; /默认第一个作业的到达时间为0 cout<<"请输入该作业的执行时间：" cin>>workTimei; if(i=0) startTimei=0; finishTimei=workTimei; /freeTimei=0; else if(arriveTimei<=finishTimei-1) /如果后一个作业已到，而前一个作业未结束 startTimei=finishTimei-1; /则后一个作业的开始时间为上一个作业的结束时间finishTimei=startTimei+workTimei; /freeTimei=0; /前

11、一个一结束就开始工作，没有空闲时间 else if(arriveTimei>finishTimei-1) /freeTimei=arriveTimei-finishTimei-1;/计算空闲时间，前一个作业已完成，但后一个作业还没到，中间空闲时间 startTimei=arriveTimei; /由于来的时候前一个作业已完成，则该作业的开始时间即为它的到达时间 finishTimei=startTimei+workTimei; cirTimei=finishTimei-arriveTimei; /计算平均周转时间 double getAverageCir(int n) /n为作业数 do

12、uble averageCir,sumCir=0; for(int i=0;i<n;i+) sumCir+=cirTimei; averageCir=sumCir/n; return averageCir; /打印输出 void print(int n) /n为作业数 cout<<"numt"<<"arrivet"<<"startt"<<"workt"<<"finisht"<<"cirt"<&

13、lt;endl; for(int i=0;i<n;i+) cout<<numi<<"t"<<arriveTimei<<"t"<<startTimei<<"t"<<workTimei<<"t"<<finishTimei<<"t"<<cirTimei<<"t"<<endl; cout<<endl; cout&

14、lt;<"平均周转时间："<<getAverageCir(n)<<endl; ; int main() int n; /n为作业数目 cout<<"请输入作业数目：" cin>>n; Fcfs f=Fcfs(n); f.print(n); return 0; SJF:#include<iostream>using namespace std;class SJF private: int num10; /作业编号 double arriveTime10; /到达时间 double start

15、Time10; /开始时间，进内存时间 double workTime10; /工作时间 double finishTime10; /完成时间 double cirTime10; /存放每一个作业的周转时间 public:SJF(int n) /n为作业数目 int i; cout<<"默认第一个作业的到达时间为0。"<<endl;for(i=0;i<n;i+) numi=i+1; /给作业编号 cout<<"第"<<numi<<"个作业："<<endl;

16、cout<<"请输入该作业的到达时间："cin>>arriveTimei;if(i=0)arriveTimei=0; /默认第一个作业的到达时间为0cout<<"请输入该作业的执行时间："cin>>workTimei;if(i=0) startTimei=0; finishTimei=workTimei; cirTimei=finishTimei-arriveTimei; else /排序 for(int j=1;j<i;j+) /i=当前作业数目-1，这里不能用numi表示当前作业数 起泡排序法fo

17、r (int k=1;k<=i-j;k+)if(workTimek>workTimek+1)double temp;temp=numk; numk=numk+1; numk+1=temp;temp=arriveTimek; arriveTimek=arriveTimek+1; arriveTimek+1=temp; temp=workTimek; workTimek=workTimek+1; workTimek+1=temp;for(i=1;i<n;i+) /排序后计算各作业的开始、结束、周转时间startTimei=finishTimei-1; finishTimei=st

18、artTimei+workTimei; cirTimei=finishTimei-arriveTimei;/计算平均周转时间double getAverageCir(int n) /n为作业数 double averageCir,sumCir=0; for(int i=0;i<n;i+) sumCir+=cirTimei; averageCir=sumCir/n; return averageCir; /打印输出void print(int n) /n为作业数cout<<"numt"<<"arrivet"<<&q

19、uot;startt"<<"workt"<<"finisht"<<"cirt"<<endl; for(int i=0;i<n;i+)cout<<numi<<"t"<<arriveTimei<<"t"<<startTimei<<"t"<<workTimei<<"t"<<finishTimei<<"t"<<cirTimei<<"t"<<endl;cout<<endl; cout<<"平均周转时