题目先来先服务FCFS和短作业优先SJF进程调度算法

姓名：

学号：

专业：

学院：

指导教师：林若宁

二零一八年十一月

一、实验目的

模拟单处理器系统的进程调度，分别采用短作业优先和先来先服务的进程调度算法作为进程设计算法，以加深对进程的概念及进程调度算法的理解．

二、实验内容

1. 短作业优先调度算法原理

短作业优先调度算法，是指对短作业或断进程优先调度的算法。它们可以分别可以用于作业调度和进程调度。短作业优先调度算法，是从后备队列中选择一个或若干个运行时间最短的作业，将它们调入内存运行。短进程优先调度算法，是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

2. 先来先服务调度算法原理

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

三、程序设计

1.概要设计

程序包括主函数、FCFS算法函数、SJF算法函数、输出函数；主函数流程：输入文件中的数据—显示各进程数据—选择算法—调用相应算法的函数—输出结果

2.算法流程

SJF算法流程图：

3.详细设计

（1）定义一个结构体

typedef struct PCB

{

char job_id[10]; //作业ID

float Arr_time; //到达时刻

float Fun_time; //估计运行时间

float Wait_time; //等待时间

float Start_time; //开始时刻

float Fin_time; //完成时刻

float Tur_time; //周转时间

float WTur_time; //带权周转时间

int Order; //优先标记

}list;

（2）先来先服务算法函数

void fcfs(list *p,int count) //先来先服务算法{

list temp; //临时结构体变量int i;

int j;

for(i = 1;i < count;i++) //按到达时刻直接插入排序

{

temp = p[i];

j = i-1;

while(temp.Arr_time < p[j].Arr_time && j >= 0)

{

p[j+1] = p[j];

--j;

}

p[j+1] = temp;

}

for(i = 0;i < count;i++) //循环计算各个作业的时间值

{

if(i == 0)

{

p[i].Start_time = p[i].Arr_time;

}

else

{

p[i].Start_time = p[i-1].Fin_time; //开始时刻==前一个作业的完成时刻}

p[i].Wait_time = p[i].Start_time - p[i].Arr_time; //等待==开始-到达

p[i].Fin_time = p[i].Start_time + p[i].Fun_time; //完成==开始+运行

p[i].Tur_time = p[i].Fin_time - p[i].Arr_time; //周转=完成-到达

p[i].WTur_time = p[i].Tur_time / p[i].Fun_time; //带权周转=周转/运行}

return;

}

（3）最短作业优先函数

void sjf(list *p,int count) //最短作业优先算法（sjf）

{

list item; //结构体变量

int i = 0;

int j = 0;

int k = 0; //最短运行时间作业的下标

int flag = 0; //优先级设置

float min = 0; //最短运行时间

float temp; //开始的时刻

temp = p[0].Arr_time;

//先求出最先到达作业的时刻for(i = 0;i < count;i++)

{

if(temp > p[i].Arr_time)

{

temp = p[i].Arr_time; //保存最先到达的作业的时刻

k = i; //最先到达的作业的下标，默认为p[0] }

}

for(i = 0;i < count;i++)

{

p[k].Order = ++flag; //设置优先级为1，最高优先级

p[k].Start_time = temp;

p[k].Wait_time = temp - p[k].Arr_time; //计算各个时间

p[k].Fin_time = temp + p[k].Fun_time;

p[k].Tur_time = p[k].Fin_time - p[k].Arr_time;

p[k].WTur_time = p[k].Tur_time / p[k].Fun_time;

min = 100;

temp = p[k].Fin_time; //后一个作业的开始时刻是前一个作业的完成时刻

for(j = 0;j < count;j++)

{

if(p[j].Order != 0 || temp - p[j].Arr_time <= 0) //跳过不满足条件的（已设置优先级的和到达时刻要晚于前一个作业的完成时刻的）

continue;

if(min > p[j].Fun_time)

{

min = p[j].Fun_time;

k = j; //求出满足条件最短运行时间的作业的下标

}

}

}

for(i = 1;i < count;i++) //按优先级排序

{

item = p[i];

j = i-1;

while(item.Order < p[j].Order && j >= 0)

{

p[j+1] = p[j];

--j;

}

p[j+1] = item;

}

return;

}

四、实验结果

测试数据：

（1）先来先服务算法调试

（2）最短作业优先算法调试

五、实验小结

FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业(进程)。

CPU繁忙型作业是指该类作业需要大量的CPU时间进行计算，而很少请求I/O。通常的科学计算便属于CPU繁忙型作业。

I/O繁忙型作业是指CPU进行处理时需频繁地请求I/O。目前的大多数事务处理都属于I/O 繁忙型作业。

SJ(P)F调度算法也存在不容忽视的缺点：

该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。

该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。

由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

#include "stdafx.h"

#include

#define MAX 100

typedef struct PCB

{

char job_id[10]; //作业ID

float Arr_time; //到达时刻

float Fun_time; //估计运行时间

float Wait_time; //等待时间

float Start_time; //开始时刻

float Fin_time; //完成时刻

float Tur_time; //周转时间

float WTur_time; //带权周转时间

int Order; //优先标记

}list;

void fcfs(list *p,int count);

void sjf(list *p,int count);

void print(list *p,int count);

void avg(list *p,int count);

void fcfs(list *p,int count) //先来先服务算法

{

list temp; //临时结构体变量

int i;

int j;

for(i = 1;i < count;i++) //按到达时刻直接插入排序

{

temp = p[i];

j = i-1;

while(temp.Arr_time < p[j].Arr_time && j >= 0)

{

p[j+1] = p[j];

--j;

}

p[j+1] = temp;

}

for(i = 0;i < count;i++) //循环计算各个作业的时间值

{

if(i == 0)

{

p[i].Start_time = p[i].Arr_time;

}

else

{

p[i].Start_time = p[i-1].Fin_time; //开始时刻==前一个作业的完成时刻}

p[i].Wait_time = p[i].Start_time - p[i].Arr_time; //等待==开始-到达

p[i].Fin_time = p[i].Start_time + p[i].Fun_time; //完成==开始+运行

p[i].Tur_time = p[i].Fin_time - p[i].Arr_time; //周转=完成-到达

p[i].WTur_time = p[i].Tur_time / p[i].Fun_time; //带权周转=周转/运行}

return;

}

void sjf(list *p,int count) //最短作业优先算法（sjf）

{

list item; //结构体变量

int i = 0;

int j = 0;

int k = 0; //最短运行时间作业的下标

int flag = 0; //优先级设置

float min = 0; //最短运行时间

float temp; //开始的时刻

temp = p[0].Arr_time;

//先求出最先到达作业的时刻for(i = 0;i < count;i++)

{

if(temp > p[i].Arr_time)

{

temp = p[i].Arr_time; //保存最先到达的作业的时刻

k = i; //最先到达的作业的下标，默认为p[0] }

}

for(i = 0;i < count;i++)

{

p[k].Order = ++flag; //设置优先级为1，最高优先级

p[k].Start_time = temp;

p[k].Wait_time = temp - p[k].Arr_time; //计算各个时间

p[k].Fin_time = temp + p[k].Fun_time;

p[k].Tur_time = p[k].Fin_time - p[k].Arr_time;

p[k].WTur_time = p[k].Tur_time / p[k].Fun_time;

min = 100;

temp = p[k].Fin_time; //后一个作业的开始时刻是前一个作业的完成时刻

for(j = 0;j < count;j++)

{

if(p[j].Order != 0 || temp - p[j].Arr_time <= 0) //跳过不满足条件的（已设置优先级的和到达时刻要晚于前一个作业的完成时刻的）

continue;

if(min > p[j].Fun_time)

{

min = p[j].Fun_time;

k = j; //求出满足条件最短运行时间的作业的下标

}

}

}

for(i = 1;i < count;i++) //按优先级排序

{

item = p[i];

j = i-1;

while(item.Order < p[j].Order && j >= 0)

{

p[j+1] = p[j];

--j;

}

p[j+1] = item;

}

return;

}

void print(list *p,int count) //输出各个作业的详细信息

{

int i;

printf("*****************************************************************\n");

printf("ID\t到达\t运行\t等待\t开始\t完成\t周转\t带权周转\n");

for(i = 0;i < count;i++)

{

printf("%s\t%.3f\t%.3f\t%.3f\t%.3f\t%.3f\t%.3f\t%.3f\n",p[i].job_id,p[i].Arr_time,p[i].Fun_time,p [i].Wait_time,p[i].Start_time,p[i].Fin_time,p[i].Tur_time,p[i].WTur_time);

}

return;

}

void avg(list *p,int count)

{

float AvgTur1; //平均周转

float AvgTur2; //平均带权周转

float t1 = 0;

float t2 = 0;

int i;

for(i = 0;i < count;i++)

{

t1 += p[i].Tur_time; //周转时间和

t2 += p[i].WTur_time; //带权周转和

}

AvgTur1 = t1/count;

AvgTur2 = t2/count;

printf("\n平均周转时间为：%f\t平均带权周转时间为：%f\n",AvgTur1,AvgTur2);

printf("\n*****************************************************************\n");

return;

}

int main()

{

list st[MAX]; //最多可以一百个作业

int job_count = 0; //作业数量

int flag = 1; //算法标记

int i = 0;

printf("请输入作业数量：");

scanf("%d",&job_count);

printf("请输入作业ID，到达时刻，估计运行时间(用空格隔开)：\n");

do

{

scanf("%s %f %f",st[i].job_id,&st[i].Arr_time,&st[i].Fun_time);

st[i].Order = 0; //优先级初始化

}while(++i < job_count);

printf("请选择算法：\n1, 先来先服务算法！\n2, 最短作业优先算法！\n");

scanf("%d",&flag);

switch(flag)

{

case 1 : {

fcfs(st,job_count);

printf("\n*******************************************\n\n");

printf("先来先服务算法\n");

} break;

case 2 : {

sjf(st,job_count);

printf("\n*******************************************\n\n");

printf("最短作业优先算法\n");

} break;

}

print(st,job_count);

avg(st,job_count);

return 0;

}