1实验一先来先服务FCFS和短作业优先SJF进程调度算法.doc

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

一：需求分析
程序设计的任务：设计程序模拟进程的先来先服务FCFS和短作业优先SJF调度过程。假设有n个x进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。
通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。
（1） 输入的形式和输入值的范围
为免去测试时候需要逐步输入数据的麻烦，输入时采用输入文件流方式将数据放在.txt文件中，第一行为进程个数，第二行为进程到达时间（各个进程的到达时间之间用空格隔开），第三行为进程的服务时间（每个服务时间之间用空格隔开）。
（2） 输出的形式
模拟整个调度过程，输出每个时刻的进程运行状态，同时输出了每个进程的完成时间，并且按要求输出了计算出来的每个进程的周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。
（3） 程序所能达到的功能
能够模拟出进程的先来先服务FCFS算法和短作业优先SJF算法的调度过程，输入进程个数n；每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn；选择算法1-FCFS，2-SJF，3-退出，用户做出选择即可输出对应的算法调度过程或者退出程序。
（4） 测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果
测试数据及其输出结果：
作业

算法
进程名
A
B
C
D
E
平均
到达时间
0
1
2
3
4

服务时间
4
3
5
2
4

FCFS
完成时间
4
7
12
14
18

周转时间
4
6
10
11
14
9
带权周转时间
1
2
2
5.5
3.5
2.8

SJF
完成时间
4
9
18
6
13

周转时间
4
8
16
3
9
8
带权周转时间
1
2.67
3.2
1.5
2.25
2.1
也可看下面截图的测试结果

二：概要设计
程序包括主函数、FCFS算法函数、SJF算法函数、输出函数；
主函数流程：输入文件中的数据—显示各进程数据—选择算法—调用相应算法的函数—输出结果
三：详细设计
算法流程图：
FCFS先来先服务算法流程图：

开始

按排好的顺序第一个进程先进行

判断上一个进程的完成时间是否大于下一个进程的到达时间

N
Y

下一个进程的开始时间从上个进程的完成时间开始
下一个进程的开始时间从它本身的到达时间开始

更新各数据

循环累加，求总的周转时间，总的带权周转时间

求平均周转时间，带权周转时间

输出结果

调用结束

SJF算法流程图：

开始

初始化数据

利用一个for循环判断是否找到短作业

Y
N

直接进入下一未完成进程并且
FinishTime[Short]=ArrivalTime[Short]+ServiceTime[Short]

FinishTime[Short]=Finish+ServiceTime[Short]

Finish=FinishTime[Short]

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

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

计算平均周转时间、平均带权周转时间

调用结束

四：调试分析
(1) ：调试过程中遇到的问题以及解决方法，设计与实现的回顾讨论和分析；
开始的时候没有判断进程是否到达，导致短进程优先算法运行结果错误，后来加上了判断语句后就解决了改问题。
(2)：算法的性能分析及其改进设想；
即使用户输入的进程到达时间没有先后顺序也能准确的计算出结果。（加循环，判断各个进程的到达时间先后，组成一个有序的序列）
(3)：经验和体会。
通过本次实验，深入理解了先来先服务和短进程优先进程调度算法的思想，培养了自己的动手能力，通过实践加深了记忆。
五：用户使用说明
在同一目录下的.txt文件中按输入要求输入相关数据，并且根据提示选择相应的算法。
六：测试结果
测试数据：
输出结果：

七：附录
源程序：
#include<iostream>
#include<iomanip> //格式化输出结果
#include<sstream> //读取文件
#include<fstream> //读取文件
using namespace std;

const int MaxNum=100;
int ArrivalTime[MaxNum]; //到达时间
int ServiceTime[MaxNum]; //服务时间
int FinishTime[MaxNum]; //完成时间
int WholeTime[MaxNum]; //周转时间
double WeightWholeTime[MaxNum]; //带权周转时间
double AverageWT_FCFS,AverageWT_SJF; //平均周转时间
double AverageWWT_FCFS,AverageWWT_SJF; //平均带权周转时间

void FCFS(int n); //先来先服务
void SJF(int n); //短作业优先
void print(int n,int array[]);
void print(int n,double array[]);
void printproceed(int n); //输出FCFS进程运行状态

void main()
{
int n,i,j; //n:进程数；i、j:循环计数变量
ifstream in("text.txt");//读文件
string s;
for(i=0;i<3,getline(in,s);i++)
{ //当i=0读入进程数n ；i=1读入各进程到达时间 ；i=2读入各进程服务时间
istringstream sin(s);
switch(i)
{
case 0:
sin>>n;
break;
case 1:
for(j=0;j<n;j++)
sin>>ArrivalTime[j];
break;
case 2:
for(j=0;j<n;j++)
sin>>ServiceTime[j];
break;
}
}

//显示各进程数据
cout<<setfill(' ')<<setw(7)<<"进程名"<<setw(1)<<"";
char ch='A';
for(i=0;i<n;i++)
cout<<setw(3)<<char(ch+i);
cout<<endl<<"到达时间";
for(i=0;i<n;i++)
cout<<setw(3)<<ArrivalTime[i];
cout<<endl<<"服务时间";
for(i=0;i<n;i++)
cout<<setw(3)<<ServiceTime[i];
cout<<endl;

//选择算法：先来先服务FCFS-->1 短作业优先SJF-->2 关闭-->0
cout<<"请选择算法: FCFS-->1 SJF-->2 退出-->0"<<endl<<"选择:";
int choice;
cin>>choice;
while(choice!=0) //直到输入值为0跳出循环，结束程序
{
while(choice!=1 && choice !=2 && choice!=0 )
{
cout<<"Please enter 0, 1 or 2!"<<endl;
cin>>choice;
}
if(choice==0)
return;
if(choice==1)
FCFS(n); //进行先来先服务FCFS算法
else
SJF(n); //进行短作业优先服务SJF算法
cout<<endl<<"请选择: FCFS-->1 SJF-->2 退出-->0"<<endl<<"选择:";
cin>>choice;
}
return;
}

//------------------先来先服务----------------------------------------
void FCFS(int n)
{

//第一个进程先服务
FinishTime[0]=ArrivalTime[0]+ServiceTime[0];
WholeTime[0]=FinishTime[0]-ArrivalTime[0];
WeightWholeTime[0]=double(WholeTime[0])/double(ServiceTime[0]);

for(int i=1;i<n;i++)
{

if(FinishTime[i-1]>ArrivalTime[i])
FinishTime[i]=FinishTime[i-1]+ServiceTime[i];//如果上一个进程的完成时间大于下一个进程的到达时间，
//那么下一个进程的开始时间从上一个进程的完成时间开始
else
FinishTime[i]=ArrivalTime[i]+ServiceTime[i];//否则，下一个进程的开始时间从它本身的到达时间开始
WholeTime[i]=FinishTime[i]-ArrivalTime[i];
WeightWholeTime[i]=double(WholeTime[i])/double(ServiceTime[i]);
}
double totalWT=0,totalWWT=0;
for(int j=0;j<n;j++)
{ //循环累加，求总的周转时间，总的带权周转时间
totalWT+=WholeTime[j];
totalWWT+=WeightWholeTime[j];
}
AverageWT_FCFS=totalWT/double(n);
AverageWWT_FCFS=totalWWT/double(n);

//输出各结果
cout<<"---------先来先服务FCFS--------------"<<endl;
cout<<"完成时间分别为:";
print(n,FinishTime);
cout<<"周转时间分别为:";
print(n,WholeTime);
cout<<"带权周转时间分别为:";
print(n,WeightWholeTime);
cout<<"平均周转时间:"<<AverageWT_FCFS<<endl;
cout<<"平均带权周转时间:"<<AverageWWT_FCFS<<endl;
printproceed(n);
}
//------------------短作业优先--------------------------------
void SJF(int n)
{
int Short; //存放当前最短作业的序号
int Finish=0; //存放当前完成时间
double totalWT=0,totalWWT=0;

for(int a=0;a<n;a++) //初始化完成时间为0
FinishTime[a]=0;

int i; //循环计数累加变量
for(i=0;i<n;i++)
{
int tag=0; //用于标记当前完成时间内，是否找到短作业
int Max=10000;
for(int j=0;j<n;j++)
{
if(FinishTime[j]==0 && ArrivalTime[j]<=Finish && ServiceTime[j]<=Max)
{
Max=ServiceTime[j];
Short=j;
tag=1;
}
}
if(tag==1)
{ //找到短作业
FinishTime[Short]=Finish+ServiceTime[Short];
}
if(tag==0)
{ //未找到
for(int k=0;k<n,FinishTime[k]==0;k++)
{ //直接进入下一未完成进程
Short=k;
break;
}
FinishTime[Short]=ArrivalTime[Short]+ServiceTime[Short];
}
Finish=FinishTime[Short];
}
for(i=0;i<n;i++)
{ //计算周转时间、带权周转时间
WholeTime[i]=FinishTime[i]-ArrivalTime[i];
WeightWholeTime[i]=double(WholeTime[i])/double(ServiceTime[i]);
}
for(int j=0;j<n;j++)
{ //计算总的周转时间、总的带权周转时间
totalWT+=WholeTime[j];
totalWWT+=WeightWholeTime[j];
}
AverageWT_FCFS=totalWT/double(n);
AverageWWT_FCFS=totalWWT/double(n);

//输出各值
cout<<"---------短作业优先SJF--------------"<<endl;
cout<<"完成时间:";
print(n,FinishTime);
cout<<"周转时间:";
print(n,WholeTime);
cout<<"带权周转时间:";
print(n,WeightWholeTime);
cout<<"平均周转时间:"<<AverageWT_FCFS<<endl;
cout<<"平均带权周转时间:"<<AverageWWT_FCFS<<endl;
printproceed(n);
}

void print(int n,int array[])
{ //打印int型数组
for(int i=0;i<n;i++)
cout<<array[i]<<" ";
cout<<endl;
}
void print(int n,double array[])
{ //打印double型数组
for(int i=0;i<n;i++)
cout<<array[i]<<" ";
cout<<endl;
}
void printproceed(int n)
{ //打印各时刻各进程的运行情况
char ch='A';
for(int i=0;i<n;i++)
{
int StartTime=FinishTime[i]-ServiceTime[i];
cout<<"时刻"<<StartTime<<":进程"<<char(ch+i)<<"开始运行"<<endl;
cout<<"时刻"<<FinishTime[i]<<":进程"<<char(ch+i)<<"停止运行"<<endl;
}
}