先来先服务调度算法（C语言代码实现） 大三操作系统实验

实验原理:

先来先服务（First Come First Served,FCFS），是一种简单的调度算法，它既适用于作业调度，也适用于进程调度。先来先服务算法是按照作业或进程的到达先后次序来进行调度。当作业调度中采用该算法时，每次调度都是从后备队列中选择一个最先进入该队列中作业，将它调入内存，为其创建进程、分配相应的资源，将该作业的进程放入就绪队列。在进程调度中采用该算法时，每次调度是从就绪队列中选择一个最新进入该队列的进程，并给他分配处理机。

实验内容:

按作业提交的/到达的（到达后备队列的时间）先后次序从外存后备队列中选择几个最先进入该队列的作业为他们分配资源、创建进程，然后再放入就绪队列。 

每个作业由一个作业控制块JCB表示，JCB可以包含如下信息∶作业名、提交时间、所需的运行时间、作业状态等等。

作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。各个等待的作业按照提交时刻的先后次序排队。

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

#include <iostream>
#include <string.h>
#include <iomanip>

struct job
{
    char name[10];      //作业的名字
    int starttime;      //作业到达系统时间
    int needtime;       //作业服务时间
    int runtime;        //作业周转时间
    int endtime;        //作业结束时间
    int flag=0;           //作业完成标志   
	char state='W'; 		//作业状态，一开始都默认为就绪 
	double dqzz_time;    //带权周转时间
};

void fcfs(struct job jobs[50],int n){
   int i=0,j=0,sum=1;
   char t_name[10];
   int t_time;            
   for(i=0;i<n;i++) //按作业到达系统时间进行排序，最早到达的排在最前面 
	  {
		  for(j=i;j<n;j++) //按作业到达系统时间进行排序，最早到达的排在最前面 
		  {
			  if(jobs[j].starttime<jobs[i].starttime)
			  {   //把到达时间早的赋值到t_time
				  t_time=jobs[j].starttime;
				  jobs[j].starttime=jobs[i].starttime;
				  jobs[i].starttime=t_time;
				  //把到达时间早的赋值到t_time
				  t_time=jobs[j].needtime;
				  jobs[j].needtime=jobs[i].needtime;
				  jobs[i].needtime=t_time;
				  strcpy(t_name,jobs[j].name);
				  strcpy(jobs[j].name,jobs[i].name);
				  strcpy(jobs[i].name,t_name);//在t_name数组中排序
			  }
		  } 
	  }
	int nowtime=0;//系统时间 
	for(i=0;i<n;i++){
		if(nowtime<jobs[i].starttime){
			nowtime=jobs[i].starttime;
		}
		jobs[i].state='R';
    	jobs[i].endtime=nowtime+jobs[i].needtime;
		jobs[i].runtime=jobs[i].endtime-jobs[i].starttime;
		jobs[i].dqzz_time=double(jobs[i].runtime)/jobs[i].needtime;
		nowtime=jobs[i].endtime;
		jobs[i].state='F';		
	} 
}

 
void print(struct job jobs[50],int n)
{
    int i;
    double avertime;
    double dqzz_avertime;
    int sum_runtime=0;
    double  sum_time=0.00;
    printf("作业名  到达时间 运行时间 完成时间 周转时间 带权周转时间\n");
    for(i=0;i<n;i++)
    {
    printf("%s       %2d        %2d       %2d        %2d        %.2f\n",jobs[i].name,jobs[i].starttime,jobs[i].needtime,jobs[i].endtime,jobs[i].runtime,jobs[i].dqzz_time);
    
    sum_runtime=sum_runtime+jobs[i].runtime;
    sum_time=sum_time+jobs[i].dqzz_time;
    }
    avertime=sum_runtime*1.0/n;
    dqzz_avertime=sum_time*1.000/n;
    printf("平均周转时间:%.2f \n",avertime);
    printf("平均带权周转时间:%.3f \n",dqzz_avertime);
    printf("\n");
}

int main()
{
    struct job jobs[50];
    int n,i; //n个作业
    printf("请输入作业个数:");
    scanf("%d",&n);
    printf("请输入各作业的信息(格式：作业名 到达时间 服务时间)：\n");
    for(i=0;i<n;i++)
    {
        scanf("%s",jobs[i].name); //作业名
        scanf("%d",&jobs[i].starttime);//到达时间
        scanf("%d",&jobs[i].needtime);//运行（服务时间）时间
    }
    printf("\n");
	fcfs(jobs,n);
	printf("先来先服务(FCFS)调度算法运行结果：\n");
	print(jobs,n);
	
}

结果：

运行流程

需要提出的一点，这个调度算法的调度过程是先找作业或者进程中最先到来的那一个，也就是说，这个是看到达时间的，到达时间越早，则最先进行调度，值得注意的是，此调度算法是服务完一个作业或进程后，再服务下一个作业或者进程

优点：公平、算法实现简单
缺点：排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好，比如下面的P3进程，带权周转时间为8s，但是它只需要1s即可运行完成，即FCFS算法对长作业有利，对短作业不利，此外不利于I/O繁忙的作业

所谓的CPU繁忙，是指的这项作业的CPU计算部分的时间需要占用大量的时间，很少请求I/O。对应于I/O繁忙，那就是这项作业很是频繁的请求I/O，但是真正用于计算的时间却是不多，因此可以认为CPU繁忙的作业更接近于长作业的工作方式，因为它长时间占用了CPU，I/O繁忙更接近于短作业的工作方式

若进程是CPU繁忙型，则一旦占有CPU，就可能会运行很长时间，因此CPU繁忙型作业类似于长作业，FCFS算法对长作业有利。而对于I/O繁忙型作业，运行进程中要频繁访问I/O端口，即可能频繁放弃CPU，所以占用CPU的时间不会太长，一旦放弃CPU，则必须等待下次调度，因此FCFS算法不利于它。

具体关于I/O繁忙可以参考

《计算机操作系统》——调度算法_热衷做分母的博客-CSDN博客_i/o繁忙型适合什么调度算法