fcfs

操作系统-先来先服务FCFS和短

作业优先SJF进程调度算法

操作系统作业算法调

度报告

学院：

专业班级：

学生姓名：

学号：

报告题目：先来先服务和短作业优先算法

完成日期：2016年10月25日星期二

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

1、实验目的

通过这次实验，加深对进程概念的理解，进一步掌握进程状态的

转变、进程调度的策略及对系统性能的评价方法。

2、实验内容

问题描述：

设计程序模拟进程的先来先服务FCFS和短作业优先SJF调度过

程。假设有n个进程分别在T

1,…,Tn时刻到达系统，它们需要的

服务时间分别为S

1,…,Sn。分别采用先来先服务FCFS和短作业优

先SJF进程调度算法进行调度，计算每个进程的完成时间、周转

时间和带权周转时间，并且统计n个进程的平均周转时间和平均

带权周转时间。

3、程序要求：

1）进程个数n；每个进程的到达时间T1,…,Tn和服务时间

S1,…,Sn；选择算法1-FCFS，2-SJF。

2）要求采用先来先服务FCFS和短作业优先SJF分别调度进程

运行，计算每个进程的周转时间和带权周转时间，并且计算所有进程

的平均周转时间和带权平均周转时间；

3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状

态，如“时刻3：进程B开始运行”等等；

4）输出：要求输出计算出来的每个进程的周转时间、带权周转

时间、所有进程的平均周转时间以及带权平均周转时间。

4、需求分析

(1)输入的形式和输入值的范围

算法选择：FCFS-“1”，选SJF-“2”

真实进程数

各进程的到达时间

各进程的服务时间

(2)输出的形式

模拟整个调度过程、周转时间、带权周转时间、所有进程的平均周转

时间以及带权平均周转时间。

(3)程序所能达到的功能

输入进程个数Num，每个进程到达时间ArrivalTime[i]，服务时间

ServiceTime[i]。采用先来先服务FCFS或者短作业优先SJF进程调度

算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，

并且统计Num个进程的平均周转时间和平均带权周转时间。

(4)测试用例

5、调试分析

(1)调试过程中遇到的问题以及解决方法，设计与实现的回顾讨论和

分析

○1开始的时候没有判断进程是否到达，导致短进程优先算法运行结果

错误，后来加上了判断语句后就解决了改问题。

○2基本完成的设计所要实现的功能，总的来说，FCFS编写容易，SJF

需要先找到已经到达的进程，再从已经到达的进程里找到进程服务时

间最短的进程，再进行计算。

○3根据我所写的FCFS和SJF算法，如果用户输入的数据没有按照到达

时间的先后顺序，程序将出现问题？

解决办法：利用冒泡排序，根据达到时间的先后顺序进行排序。

○4从第二个进程开始，算法需要判断已在等待的进程，如果分批进行

判断与处理，规律性不强，代码很难实现？

解决办法：通过牺牲效率的方式，进行一个个判断与处理。为此，引

入变量当前时间、用零标记已处理过进程等方式，实现已在等待进程

的判断与判断。

(2)算法的改进设想

改进：即使用户输入的进程到达时间没有先后顺序也能准确的计算出

结果。（就是再加个循环，判断各个进程的到达时间先后，组成一个

有序的序列）

(3)经验和体会

通过本次实验，深入理解了先来先服务和短进程优先进程调度算法的

思想，培养了自己的动手能力，通过实践加深了记忆。

6、测试结果

(1)FIFS算法:

文件流输入算法选择,进程个数,进程的达到时间和服务时间

输出

(2)FIFS算法:

文件流输入算法选择,进程个数,进程的达到时间和服务时间

输出

7、附录(java)

packageexperiment;

edInputStream;

putStream;

tFoundException;

lFormat;

r;

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

法

publicclassA_FJFS_SJF{

//声明变量

//允许的最大进程数

publicstaticintMaxNum=100;

//真正的进程数

publicstaticintrealNum;

//当前时间

publicstaticintNowTime;

//各进程的达到时间

publicstaticintArrivalTime[]=new

int[MaxNum];

//各进程的服务时间

publicstaticintServiceTime[]=new

int[MaxNum];

//各进程的服务时间(用于SJF中的临时数

组)

publicstaticintServiceTime_SJF[]=new

int[MaxNum];

//各进程的完成时间

publicstaticintFinishTime[]=new

int[MaxNum];

//各进程的周转时间

publicstaticintWholeTime[]=new

int[MaxNum];

//各进程的带权周转时间

publicstaticdoubleWeightWholeTime[]=

newdouble[MaxNum];

//FCFS和SJF的平均周转时间

publicstaticdoubleAverageWT_FCFS,

AverageWT_SJF;

//FCFS和SJF的平均带权周转时间

publicstaticdoubleAverageWWT_FCFS,

AverageWWT_SJF;

//FCFS中的周转时间总和

publicstaticintSumWT_FCFS=0;

//FCFS中的带权周转时间总和

publicstaticdoubleSumWWT_FCFS=0;

//SJF中的周转时间总和

publicstaticintSumWT_SJF=0;

//SJF中的带权周转时间总和

publicstaticdoubleSumWWT_SJF=0;

publicstaticScannerstdin;

publicstaticvoidmain(Stringargs[])

throwsFileNotFoundException{

//从文件中输入数据

BufferedInputStreamin=new

BufferedInputStream(newFileInputStream(

"./file/01"));

(in);

stdin=newScanner();

intchoice=t();//算法

选择：FCFS-“1”，选SJF-“2”

realNum=t();//真实进程

数

for(inti=0;i

各进程的到达时间

ArrivalTime[i]=t();

}

for(intj=0;j

各进程的服务时间

ServiceTime[j]=t();

ServiceTime_SJF[j]=

ServiceTime[j];

}

();

//算法选择：1-FCFS，2-SJF；

if(choice==1){

FCFS();

}elif(choice==2){

SJF();

}el{

n("算法选择错误");

}

}

//先来先服务FCFS进程调度算法

publicstaticvoidFCFS(){

//到达时间的冒泡排序，完成时间随之变

动（使先到者排在前面，后到者排在后面）

sort();

//计算每个进程的完成时间、周转时间、

带权周转时间、所有进程的平均周转时间以及带

权平均周转时间

FinishTime[0]=ArrivalTime[0]+

ServiceTime[0];

WholeTime[0]=ServiceTime[0];

WeightWholeTime[0]=(double)

WholeTime[0]/ServiceTime[0];

AverageWT_FCFS=AverageWWT_FCFS=0;

AverageWT_FCFS=AverageWT_FCFS+

WholeTime[0];

AverageWWT_FCFS=AverageWWT_FCFS+

WeightWholeTime[0];

for(intj=1;j

从第二个进程开始计算完成时间、周转时间、带

权周转时间

if(ArrivalTime[j]>FinishTime[j-1])

{//该进程是否在等待

FinishTime[j]=ArrivalTime[j]+

ServiceTime[j];

WholeTime[j]=ServiceTime[j];

}el{//该进程已在等待

FinishTime[j]=FinishTime[j-1]+

ServiceTime[j];

WholeTime[j]=FinishTime[j-1]-

ArrivalTime[j]+ServiceTime[j];

}

WeightWholeTime[j]=

(double)WholeTime[j]/ServiceTime[j];

}

for(inti=0;i

计算总周转时间、总带权周转时间

SumWT_FCFS=SumWT_FCFS+

WholeTime[i];

SumWWT_FCFS=SumWWT_FCFS+

WeightWholeTime[i];

}

AverageWT_FCFS=(double)SumWT_FCFS/

realNum;//平均周转时间

AverageWWT_FCFS=(double)SumWWT_FCFS

/realNum;//平均带权周转时间

//输出每个进程的完成时间、周转时间、

带权周转时间、所有进程的平均周转时间以及带

权平均周转时间

outPUT(1);

}

//短作业优先SJF进程调度算法

publicstaticvoidSJF(){

//到达时间的冒泡排序，完成时间随之变

动（使先到者排在前面，后到者排在后面）

sort();

intmin=0;

NowTime=ArrivalTime[0]+

ServiceTime[0];//计算第一次的NowTIme

FinishTime[0]=ServiceTime[0];//计算

第一个进程的完成时间

ServiceTime_SJF[0]=1000;//赋初值。

intallin=0,j,k;

for(inti=1;i

入循环，从第二个到达的进程开始

{

k=1;

min=0;

if(allin==0)//找到已经到达的进程

个数

{

for(j=0;ArrivalTime[j]<=

NowTime&&j

if(j>=realNum){

allin=1;

}

}

}el{

j=realNum;

}

j=j-1;//j是已经到达的进程数（减

去已经计算过的第一个进程）

while(k<=j)//从已经到达的进程里

找到服务时间最短的进程

{

if(ServiceTime_SJF[k]==0)//进程

的服务时间如果等于0，则跳过该进程

k++;

el

{

if(ServiceTime_SJF[min]>ServiceTime_SJF

[k])//比较，找到服务时间最短的进程

min=k;

k++;

}

}

ServiceTime_SJF[min]=0;//找完后

置零，便于下一次循环时跳过

NowTime+=ServiceTime[min];//累加

当前时间

FinishTime[min]=NowTime;//完成时

间

}

for(inti=0;i

算周转时间，带权周转时间，总的周转时间和总

的带权周转时间

{

WholeTime[i]=FinishTime[i]-

ArrivalTime[i];

WeightWholeTime[i]=

(double)WholeTime[i]/ServiceTime[i];

SumWT_SJF+=WholeTime[i];

SumWWT_SJF+=WeightWholeTime[i];

}

AverageWT_SJF=(double)SumWT_SJF/

realNum;//平均周转时间

AverageWWT_SJF=(double)SumWWT_SJF/

realNum;//平均带权周转时间

//输出每个进程的完成时间、周转时间、

带权周转时间、所有进程的平均周转时间以及带

权平均周转时间

outPUT(2);

}

//到达时间的冒泡排序，完成时间随之变动

（使先到者排在前面，后到者排在后面）

publicstaticvoidsort(){

inttemp1=0;

inttemp2=0;

for(inti=0;i

for(intj=0;j

{

if(ArrivalTime[j]>ArrivalTime[j

+1]){

temp1=ArrivalTime[j];

temp2=ServiceTime[j];

ArrivalTime[j]=ArrivalTime[j+

1];

ServiceTime[j]=ServiceTime[j+

1];

ArrivalTime[j+1]=temp1;

ServiceTime[j+1]=temp2;

}

}

}

}

//输出每个进程的完成时间、周转时间、带

权周转时间、所有进程的平均周转时间以及带权

平均周转时间

//a=1:输出FCFS结果a=2:输出

SJF结果

publicstaticvoidoutPUT(inta){

intk;

DecimalFormatformat=new

DecimalFormat("#.00");

("到达时

间:");

for(k=0;k

(ArrivalTime[k]+"

");

}

n("");

("服务时

间:");

for(k=0;k

(ServiceTime[k]+"

");

}

n("");

("完成时

间:");

for(k=0;k

(FinishTime[k]+"

");

}

n("");

("周转时

间:");

for(k=0;k

(WholeTime[k]+"

");

}

n("");

("带权周转时间:");

for(k=0;k

((WeightWh

oleTime[k])+"");

}

n("");

if(a==1){

n("平均周转时

间:"+

(AverageWT_FCFS));

n("平均带权周转时

间:"+(AverageWWT_FCFS));

}el{

n("平均周转时

间:"+

(AverageWT_SJF));

n("平均带权周转时

间:"+(AverageWWT_SJF));

}

//模拟整个调度过程，输出每个时刻的进

程运行状态

n("时刻"+

ArrivalTime[0]+":进程"+1+"开始运行");

for(inti=1;i

n("时刻"+

FinishTime[i-1]+":进程"+(i+1)

+"开始运行");

}

}

}