实现fcfs和sjf调度算法

操作系统实验报告

实验一：作业调度

实验一：作业调度

实现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可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。具体结构如下：  

typedef struct jcb{

char name[10]; /* 作业名 */      

char state;  /* 作业状态 */      

int ts; /* 提交时间 */      

float super; /* 优先权 */ 

int tb; /* 开始运行时间 */      

int tc;  /* 完成时间 */      

float ti;  /* 周转时间 */ 

   float wi;  /* 带权周转时间 */ 

    int ntime;  /* 作业所需运行时间 */      

char resource[10];  /* 所需资源 */      

  struct jcb *next;  /* 结构体指针 */         

} JCB;

 JCB *p,*tail=NULL,*head=NULL; 

作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。，组成一个后备队列等待，总是首先调度等待队列中队首的作业。  

本实验采用链表的形式存放各后备队列当中的作业控制块，各个等待的作业按照提交时刻的先后次序排队。当一个作业进入系统时，就为其动态建立一作业控制块（JCB），挂入后备队列尾部。当作业调度时，从后备队列中按某种调度算法选择一作业，让其进入主存以便占用CPU执行。 

每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。

设计图

编程语言：c++

编程环境：Visual C++ 6.0

程序代码：

FCFS：

#include

using namespace std;

class Fcfs {

private:

int num[10]; //作业编号

double arriveTime[10]; //到达时间

double startTime[10]; //开始时间，进存时间

double workTime[10]; //工作时间

double finishTime[10]; //完成时间

double cirTime[10]; //存放每一个作业的周转时间 //

double freeTime[10]; //上一个作业已结束，但下一个作业还未到，存放这一段空闲时间

public:

Fcfs(int n) //n为作业数目

{

cout<<"默认第一个作业的到达时间为0。"<

for(int i=0;i

{

num[i]=i+1; //给作业编号

cout<<"第"<

cout<<"请输入该作业的到达时间：";

cin>>arriveTime[i];

if(i==0)

arriveTime[i]=0; //默认第一个作业的到达时间为0

cout<<"请输入该作业的执行时间：";

cin>>workTime[i];

if(i==0)

{

startTime[i]=0;

finishTime[i]=workTime[i];

//freeTime[i]=0;

}

else if(arriveTime[i]<=finishTime[i-1]) //如果后一个作业已到，而前一个作业未结束

{

startTime[i]=finishTime[i-1]; //则后一个作业的开始时间为上一个作业的结束时间

finishTime[i]=startTime[i]+workTime[i];

//freeTime[i]=0; //前一个一结束就开始工作，没有空闲时间

}

else if(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];

}

}

//计算平均周转时间

double getAverageCir(int n) //n为作业数

{

double averageCir,sumCir=0;

for(int i=0;i

sumCir+=cirTime[i];

averageCir=sumCir/n;

return averageCir;

}

//打印输出

void print(int n) //n为作业数

{

cout<<"num\t"<<"arrive\t"<<"start\t"<<"work\t"<<"finish\t"<<"cir\t"<

{

cout<

}

cout<

cout<<"平均周转时间："<

}

};

int main()

{

int n; //n为作业数目

cout<<"请输入作业数目：";

cin>>n;

Fcfs f=Fcfs(n);

f.print(n);

return 0;

}

SJF:

#include

using namespace std;

class SJF{

private:

int num[10]; //作业编号

double arriveTime[10]; //到达时间

double startTime[10]; //开始时间，进存时间

double workTime[10]; //工作时间

double finishTime[10]; //完成时间

double cirTime[10]; //存放每一个作业的周转时间

public:

SJF(int n) //n为作业数目

{

int i;

cout<<"默认第一个作业的到达时间为0。"<

for(i=0;i

{

num[i]=i+1; //给作业编号

cout<<"第"<

cout<<"请输入该作业的到达时间：";

cin>>arriveTime[i];

if(i==0)

arriveTime[i]=0; //默认第一个作业的到达时间为0

cout<<"请输入该作业的执行时间：";

cin>>workTime[i];

if(i==0)

{

startTime[i]=0;

finishTime[i]=workTime[i];

cirTime[i]=finishTime[i]-arriveTime[i];

}

else //排序

{

for(int j=1;j当前作业数目-1，这里不能用num[i]表示当前作业数 起泡排序法

{

for (int k=1;k<=i-j;k++)

if(workTime[k]>workTime[k+1])

{

double temp;

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;i

{

startTime[i]=finishTime[i-1];

finishTime[i]=startTime[i]+workTime[i];

cirTime[i]=finishTime[i]-arriveTime[i];

}

}

//计算平均周转时间

double getAverageCir(int n) //n为作业数

{

double averageCir,sumCir=0;

for(int i=0;i

sumCir+=cirTime[i];

averageCir=sumCir/n;

return averageCir;

}

//打印输出

void print(int n) //n为作业数

{

cout<<"num\t"<<"arrive\t"<<"start\t"<<"work\t"<<"finish\t"<<"cir\t"<

for(int i=0;i

{

cout<

}

cout<

cout<<"平均周转时间："<

}

};

int main()

{

cout<<"-----短作业优先-----"<

int n; //n为作业数目

cout<<"请输入作业数目：";

cin>>n;

SJF f=SJF(n);

f.print(n);

return 0;

}

实例截图：

五个进程，到达时间分别为5，10，13，20

服务时间分别为6,2,4,6

设置选择量n，

当n=1时，选择FCFS

当n=2时，选择SJF

当n=3时，同时分别调用FCFS和SJF

n不为1或2或3时提示错误，重新输入n；

1-FCFS 算法

2-SJF算法

实验总结：

本次实验题目为作业调度。实现实现FCFS和SJF调度算法。能初步掌握FCFS和SJF调度算法。

对于FCFS和SJF调度算法的思路清晰，只是将其转化为代码形式，在脑海中，没有思路。经过查阅资料和与同学们交流，逐渐形成了一定的模块化思路。结合相关程序，在调试程序的过程中，意识到书写格式规化及其重要性。明白了其中的功能。FCFS与SJF各有优缺点。对于FCFS，当先执行的是长作业时，由于FCFS对短作业长时间等待，不利于短作业。对于SJF，必须预知作业的运行时间，当短作业过多时，则不利于长作业。采用SJF算法时，人机无法实现交互。由于没有考虑到作业紧迫性，不能保证作业能够及时得到处理。选择哪一种算法，则根据具体情况而定。

本文来源：https://www.2haoxitong.net/k/doc/b7f3f5d8a22d7375a417866fb84ae45c3a35c291.html