操作系统-先来先服务算法FCFS(C语言).doc

实 验 报 告
题目

名称

C语言实现调度算法程序设计实验报告-先来先服务FCFS

院系

a

班级

完成时间

指导老师

本次实验成绩

主
要
原
理
及
所
参
考
的
资
料

算法原理：
设计程序模拟进程的先来先服务FCFS过程。假设有n个进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别采用先来先服务FCFS调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。
程序要求如下：
1）进程个数n；每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn。
2）要求采用先来先服务FCFS调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间；
3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；
4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间，所有进程的平均周转时间，带权平均周转时间。
主要参考书：
计算机操作系统第三版 西安电子科技大学出版社 汤小丹主编

主
要
算
法
具
体
实
验
步
骤

实现提示：
用C语言实现提示：
1）程序中进程调度时间变量描述如下：
static int MaxNum=100;
int ArrivalTime[MaxNum];
int ServiceTime[MaxNum];
int FinishTime[MaxNum];
int WholeTime[MaxNum];
double WeightWholeTime[MaxNum];
double AverageWT_FCFS;
double AverageWWT_FCFS;
2）进程调度的实现过程如下：
Ø 变量初始化；
Ø 接收用户输入n，T1, … ,Tn，S1, … ,Sn；
Ø 按照选择算法进行进程调度，计算进程的完成时间、周转时间和带权周转时间；
Ø 计算所有进程的平均周转时间和平均带权周转时间；
Ø 按格式输出调度结果。

实
验
要
求

1. 程序流程图
P=HEAD ; i=0
P=Q;P=P->NEXT;
P=P->NEXT;
Q->STARTTIME=TIME
Q->STATE=’T’
… …

开始
i++;输出执行进程信息
结束
P->STATE==’F’?
Q->ARRIVETIME > TIME?

i < n ?
Q->STARTTIME=ARRIVETIME
Q->STATE=’T’
… …
Y
N
Y
N
N
Y

2. 程序源代码
#include"stdio.h"
#include"stdlib.h"
typedef struct PCB //定义进程控制块
{ char name[10]; //进程名
char state; //运行状态
int ArriveTime; //到达时间
int StartTime; //进程开始时间
int FinishTime; //进程结束时间
int ServiceTime; //服务时间
float WholeTime;//周转时间
float WeightWholeTime;//带权周转时间
double AverageWT_FCFS; //平均周转时间
double AverageWWT_FCFS;//带权平均周转时间
struct PCB *next; //指向下个进程
}pcb;
double x=0,y=0;
int i;
int time; //计时器
int n; //进程个数
pcb *head=NULL,*p,*q; //进程链表指针
void run_FCFS(pcb *p1) //运行未完成的进程
{
time = p1->ArriveTime > time? p1->ArriveTime:time;
p1->StartTime=time;
printf("\n时刻：%d, 当前开始运行作业%s\n\n",time,p1->name);
time+=p1->ServiceTime;
p1->state='T';
p1->FinishTime=time;
p1->WholeTime=p1->FinishTime-p1->ArriveTime;
p1->WeightWholeTime=p1->WholeTime/p1->ServiceTime;
x+=p1->WholeTime;
y+=p1->WeightWholeTime;
p1->AverageWT_FCFS=p1->WholeTime/n;
p1->AverageWWT_FCFS=p1->WeightWholeTime/n;
printf(" 到达时间 开始时间 服务时间 完成时间 周转时间 带权周转时间 \n");
printf("%6d %10d %10d %8d %10.1f %10.2f \n ",p1->ArriveTime,p1->StartTime, p1->ServiceTime,p1->FinishTime,p1->WholeTime,p1->WeightWholeTime);
printf("\n平均周转时间 平均带权周转时间 \n");
printf(" %10.2f %10.2f\n ",p1->AverageWT_FCFS,p1->AverageWWT_FCFS);
}
void FCFS() //找到当前未完成的进程
{
int i;
p=head;
for(i=0;i<n;i++)
{

if(p->state=='F')
{
q=p; //标记当前未完成的进程
run_FCFS(q);
}
p=p->next;
}
}
void getInfo() //获得进程信息并创建进程
{
int num;
printf("\n进程个数:");
scanf("%d",&n);
for(num=0;num<n;num++)
{
p=(pcb *)malloc(sizeof(pcb));
printf("依次输入：\n进程名 到达时间 服务时间\n");
scanf("%s\t%d\t%d",&p->name,&p->ArriveTime,&p->ServiceTime);
if(head==NULL)
{head=p;q=p;time=p->ArriveTime;}
if(p->ArriveTime < time) time=p->ArriveTime;
q->next=p;
p->StartTime=0;
p->FinishTime=0;
p->WholeTime=0;
p->WeightWholeTime=0;
p->next=NULL;
p->state='F';
q=p;
}
}
void main()
{ printf("先来先服务FCFS算法模拟\n");
getInfo();
p=head;
FCFS();
}
3. 程序运行调试结果

实
验
心
得

这是第一次操作系统的实验是对先来先服务FCFS过程进行调度算法的描述，先来先服务调度算法就是每次调度是从就绪队列中选择一个最先进入该队列的进程进行处理。