操作系统进程调度算法——先来先服务、时间片轮转、优先级调度算法
一、先来先服务调度算法
（1）算法内容：先来先服务调度算法是一种最简单的调度算法，可以应用于高级调度也可以运用于低级调度。高级调度时，FCFS调度算法按照作业进入后备作业队列的先后顺序选择作业进入内存，即先进入后备作业队列的作业被优先选择进入内存，然后为选中的作业创建进程并分配该作业所需资源。低级调度时，FCFS调度算法每次从内存的进程/线程就绪队列中选择一个最先进入的进程/线程，然后由进程/线程调度程序将CPU分配给它并使其运行。
（2）算法要求：每个进程由一个进程控制快（PCB）表示。进程控制块可以包含如下信息：进程名，到达时间，运行时间，开始时间，完成时间，等待时间，周转时间，代权周转时间等。先进入就绪队列的进程，先分配处理机运行。一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或者因为等待某事件发生而不能继续运行时才释放处理机。
（3）设计思想：该算法按照进程到达时间先后顺序执行，先到达的先执行。
（4）算法分析：先定义一个PCB结构体；
定义input()输入函数，输入进程号、到达时间、运行时间；
定义output()输出函数，输出每个进程块的各种时间；
定义rank()排序函数，将进程按照到达时间进行排序；
定义FCFS()先来先服务算法函数，计算各种时间；
定义main()主函数，实现先来先服务功能；
（5）核心代码：
#include<stdio.h>
double atime; //平均周转时间
double awtime; //平均带权周转时间
struct PCB //声明结构体类型PCB
{
char name[20]; //进程号
int arrivaltime; //到达时间
int runtime; //运行时间
int starttime; //开始时间
int finishtime; //完成时间
int waitingtime; //等待时间
int cycletime; //周转时间
double wctime; //带权周转时间
};
struct PCB pcb[100];
/*输入函数*/
int input(int n)
{
printf("请依次输入进程号、到达时间、运行时间：n");
for(int i=0;i<n;i++)
{
scanf("%st%dt%d",pcb[i].name,&pcb[i].arrivaltime,&pcb[i].runtime);
}
}
/*输出函数*/
int output(int n)
{
printf("n======================================================================================================================n");
printf("进程号 t到达时间t运行时间t开始时间t完成时间t等待时间t周转时间t带权周转时间n");
printf("----------------------------------------------------------------------------------------------------------------------n");
for(int i=0;i<n;i++)
{
printf("%3st %dtt %dtt %dtt %dtt %dtt %dtt %.2lfn",pcb[i].name,pcb[i].arrivaltime,pcb[i].runtime,pcb[i].starttime,pcb[i].finishtime,pcb[i].waitingtime,pcb[i].cycletime,pcb[i].wctime);
}
printf("----------------------------------------------------------------------------------------------------------------------n");
printf("t平均周转时间 tt%.2lftn",atime);
printf("----------------------------------------------------------------------------------------------------------------------n");
printf("t平均带权周转时间tt%.2lftn",awtime);
printf("======================================================================================================================n");
}
/*按到达时间进行排序*/
int rank(int n)
{
struct PCB t;
for(int j=0;j<n-1;j++) //冒泡法排序
for(int i=0;i<n-1-j;i++)
{
if(pcb[i].arrivaltime>pcb[i+1].arrivaltime)
{
t=pcb[i];
pcb[i]=pcb[i+1];
pcb[i+1]=t;
}
}
}
/*先来先服务算法*/
int FCFS(int n)
{
/*完成时间*/
if(pcb[0].arrivaltime!=0) //第一个进程到达时间不为0时，其完成时间=开始时间+运行时间
{
pcb[0].finishtime=pcb[0].starttime+pcb[0].runtime;
}
else
pcb[0].finishtime=pcb[0].runtime; //第一个进程到达时间为0时，其完成时间=运行时间
for(int i=1;i<n;i++)
{
if(pcb[i-1].finishtime>=pcb[i].arrivaltime) //如果前一个进程的完成时间大于等于当前进程的到达时间
{
pcb[i].finishtime=pcb[i-1].finishtime+pcb[i].runtime; //当前进程的完成时间=前一个进程的完成时间+该进程的运行时间
}
else
{
pcb[i].finishtime=pcb[i].arrivaltime+pcb[i].runtime; //否则为当前进程的到达时间+运行时间
}
}
/*开始时间*/
pcb[0].starttime=pcb[0].arrivaltime; //第一个进程的开始时间即到达时间
for(int i=1;i<n;i++)
{
pcb[i].starttime=pcb[i-1].finishtime; //从第二个进程开始，开始时间=前一个进程的完成时间
}
/*等待时间 周转时间 带权周转时间*/
for(int i=0;i<n;i++)
{
pcb[i].waitingtime=pcb[i].starttime-pcb[i].arrivaltime; //等待时间=开始时间-到达时间
pcb[i].cycletime=pcb[i].finishtime-pcb[i].arrivaltime; //周转时间=完成时间-到达时间
pcb[i].wctime=pcb[i].cycletime/(pcb[i].runtime*1.0); //带权周转时间=周转时间/运行时间
}
/*平均周转时间 平均带权周转时间*/
int sum1=0;
double sum2=0;
for(int i=0;i<n;i++)
{
sum1+=pcb[i].cycletime; //求所有进程周转时间的和
sum2+=pcb[i].wctime; //求有所进程周转时间的和
}
atime=sum1/(n*1.0); //平均周转时间=所有进程周转时间的和/进程数
awtime=sum2/n; //平均带权周转时间=所有进程周转时间的和/进程数
}
/*主函数*/
int main()
{
printf("先来先服务FCFS算法模拟n请输入进程个数：n");
int n;
scanf("%d",&n); //输入进程数 n
input(n); //输入函数
rank(n); //排序函数，按到达时间给各进程排序 （升序）
FCFS(n); //先来先服务算法函数，计算各种时间
output(n); //输出函数
return 0;
}（6）测试数据或截图：
（6）运行结果分析：根据先来先服务算法，首先按到达时间大小将其排序，根据进程的输入信息，第一个进程a到达时间为0，其完成时间=运行时间=1，其余进程的完成时间=前一个进程的完成时间+该进程的运行时间，（如，b的完成时间=1+100=101，c的完成时间=101+1=102，d的完成时间=102+100=201）；第一个进程a的开始时间=到达时间=0，其余进程的开始时间=前一个进程的完成时间，（如，b的开始时间=a的完成时间=1，c的开始时间=b的完成时间=101，d的开始时间=c的完成时间=102）；每个进程的等待时间=开始时间-到达时间（如，a的等待时间=0-0=0，b的等待时间=1-1=0，c的等待时间=101-2=99，d的等待时间=102-3=99）；周转时间=完成时间-到达时间（如，a的周转时间=1-0=1，b的周转时间=101-1=100，c的周转时间=102-2=100，d的周转时间=202-3=199）；带权周转时间=周转时间/运行时间（如，a的带权周转时间=1/1=1，b的带权周转时间=100/100=1，c的带权周转时间=100/1=100，d的带权周转时间=199/100=1.99）；平均周转时间=所有进程周转时间的和/进程数(1+100+100+199)/4=100；平均带权周转时间=所有进程带权周转时间的和/进程数（1+1+100+1.99）/4=26。
二、时间片轮转调度算法
（1）算法内容：时间片轮转调度算法主要用于低级调度，调度方式实际上是一种基于时钟的抢占式调度算法。在采用时间片轮转调度算法的系统中，进程/线程就绪队列按到达时间的先后次序进行排队，按照先来先服务原则，将需要执行的所有进程按照到达时间大小排成一个升序的序列，每次都给一个进程同样大小的时间片，在这个时间片内如果进程执行结束了，那么把进程从进程队列中删去，如果进程没有结束，那么把该进程停止然后改成等待状态，放到进程队列的尾部，直到所有的进程都已执行完毕。
（2）算法要求：每个进程由一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名，到达时间，运行时间，完成时间，周转时间，带权周转时间，完成进程标志，剩余服务时间等。进程的运行时间以时间片为单位进行计算。
（3）设计思想：每次调度时，总是选择就绪队列的队首进程，让其在CPU上运行一个系统预先设置好的时间片。一个时间片内没有完成运行的进程，返回到绪队列末尾重新排队，等待下一次调度。时间片轮转调度属于抢占式调度，适用于分时系统。
（4）算法分析：先定义一个RR结构体；
input()输入函数；
rank()函数对进程到达时间排序；
rr_pcb()函数执行轮转调度算法；
output()输出函数；
main()主函数。
（5）核心代码：
#include<stdio.h>
double atime; //平均周转时间
double awtime; //平均带权周转时间
struct RR
{
char name[20]; //进程号
int arrivaltime; //到达时间
int runtime; //运行时间
int starttime; //开始时间
int finishtime; //完成时间
int cycletime; //周转时间
double wctime; //带权周转时间
int sign; //完成进程标志
int st1; //剩余服务时间
};
struct RR rr[100];
/*输入函数*/
int input(int n)
{
printf("请依次输入进程号、到达时间、运行时间：n");
for(int i=0;i<n;i++)
{
rr[i].sign=0;
scanf("%st%dt%d",rr[i].name,&rr[i].arrivaltime,&rr[i].runtime);
rr[i].st1=rr[i].runtime;
}
}
/*采用冒泡法，按进程的到达时间对进程进行排序*/
int rank(int n)
{
int i,j;
struct RR temp;
for(j=0;j<n-1;j++)
for(i=0;i<n-1-j;i++)
{
if(rr[i].arrivaltime>rr[i+1].arrivaltime)
{
temp=rr[i];
rr[i]=rr[i+1];
rr[i+1]=temp;
}
}
}
/*执行时间片轮转调度算法*/
int rr_pcb(int n)
{
printf("请输入时间片：n");
int t;
scanf("%d",&t); //输入时间片
int time=rr[0].arrivaltime; //给当前时间time赋初值
int flag=1; //标志就绪队列中有进程
int sum=0; //记录完成的进程数
printf("n====================================================================================================================n");
printf("进程号 t到达时间t运行时间t开始时间t完成时间t周转时间t带权周转时间n");
printf("--------------------------------------------------------------------------------------------------------------------n");
while(sum<n) //当完成的进程数小于进程总数
{
flag=0; //标记就绪队列没有进程
for(int i=0;i<n;i++) //时间片轮转法执行各进程
{
if(rr[i].sign==1)//已完成进程
continue;
else//未完成的进程
{
if(rr[i].st1<=t && time>=rr[i].arrivaltime)//还需运行的时间小于等于一个时间片
{
flag=1; //把进程加入到就绪队列中
time+=rr[i].st1;
rr[i].sign=1; //此进程完成
rr[i].finishtime=time; //完成时间
rr[i].cycletime=rr[i].finishtime-rr[i].arrivaltime; //计算周转时间=完成时间-到达时间
rr[i].wctime=rr[i].cycletime/(rr[i].runtime*1.0); //计算带权周转时间=周转时间/服务
printf("%3st %dtt %dtt %dtt %dtt %dtt %.2lfn",rr[i].name,
rr[i].arrivaltime,rr[i].runtime,time-rr[i].st1,time,rr[i].cycletime,rr[i].wctime);
}
else if(rr[i].st1>t&&time>=rr[i].arrivaltime) //还需服务时间至少大于一个时间片
{
flag=1; //把进程加入到就绪队列中
time+=t;
rr[i].st1-=t;
rr[i].cycletime=rr[i].finishtime-rr[i].arrivaltime; //计算周转时间=完成时间-到达时间
rr[i].wctime=rr[i].cycletime/(rr[i].runtime*1.0); //计算带权周转时间=周转时间/服务
printf("%3st %dtt %dtt %dtt %dtt %dtt %.2lfn",rr[i].name,
rr[i].arrivaltime,rr[i].runtime,time-t,time,rr[i].cycletime,rr[i].wctime);
}
if(rr[i].sign==1)
sum++; //一个进程执行完就+1
}
}
}
/*平均周转时间 平均带权周转时间*/
int sum1=0;
double sum2=0;
for(int i=0;i<n;i++)
{
sum1+=rr[i].cycletime; //求所有进程周转时间的和
sum2+=rr[i].wctime; //求所有进程带权周转时间的和
}
atime=sum1/(n*1.0); //平均周转时间=有进程周转时间的和/进程数
awtime=sum2/n; //平均带权周转时间=所有进程带权周转时间的和/进程数
}
/*输出函数*/
int output(int n)
{
printf("--------------------------------------------------------------------------------------------------------------------n");
printf("t平均周转时间 tt%.2lftn",atime);
printf("--------------------------------------------------------------------------------------------------------------------n");
printf("t平均带权周转时间tt%.2lftn",awtime);
printf("====================================================================================================================n");
}
/*主函数*/
int main()
{
printf("时间片轮转调度算法n请输入总进程数：n");
int n;
scanf("%d",&n); //输入总进程数
input(n); //输入函数
rank(n); //排序函数
rr_pcb(n); //计算各时间
output(n); //输出函数
return 0;
}（6）测试数据或截图：（时间片为1的见图1，时间片为5的见图2）
图1 时间片=1时运行结果截图
图2 时间片=5时运行结果截图
（7）运行结果分析：执行时间图像如下，
图4-24 执行时间图像
时间片=1时，a、b、c、d四个进程的运行时间都大于规定的时间片，一个时间片内没有完成运行，则都需要返回就绪队列的队尾，等待下一次调度继续执行。CPU被分配给当前就绪队列的第一个进程。
时间片=5时，第一个进程的运行时间等于20>5，一个时间片内没有完成运行，则进程a返回到就绪队列末尾重新排队，等待下一次调度；第二个进程的运行时间等于10>5，用完了规定的时间片，则进程b返回到绪队列末尾，等待再次被调度执行；第二个进程的运行时间等于15>5，则进程c返回到就绪队列的队尾，等到下一次轮转到自己时再投入运行；第四个进程的运行时间为5，刚好在一个时间片内完成运行，则进程d放弃CPU的使用权。此时，进程调度程序又将CPU分配给当前就绪队列的第一个进程，即进程a。
三、优先级调度算法
（1）算法内容：优先级调度算法既可以应用于高级调度（作业调度）也可以应用于低级调度（进程调度），还可用于实时系统。高级调度时，优先数调度算法每次从后备作业队列中选择优先级最高的作业调入内存，为其分配相应的资源并创建进程放入到进程就绪队列中。低级调度时，优先级调度算法每次从进程就绪队列中选择优先级最高的进程为其分配CPU而投入运行。如果有多个优先级最高的作业/进程，则可结合先来先服务或短作业/短进程优先调度策略。
（2）算法要求：每个进程由一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名，运行时间，优先数，进程状态等。进程的优先数及需要运行时间可以事先人为指定（也可由随机数产生）。每个进程的状态可以是就绪W（Wait）,运行R（Run）或者完成F（Finish）3个状态之一。
（3）设计思想：采用抢占式优先级调度算法，具有最高级优先级的就绪进程/线程首先得到CPU运行，并在运行过程中允许被具有更高优先级的就绪进程/线程抢占CPU。如果有多个优先级最高的进程，则结合先来先服务调度策略。每次运行之前，为每个进程任意确定它的“优先数”和“要求运行时间”。处理器总是选队首进程运行。采用动态改变优先数的办法，进程每运行1次，优先数减1，要求运行时间减1。进程运行一次后，若要求运行时间不等于0，则将它加入队列，否则，将状态改为“结束”，退出队列。若就绪队列为空，结束，否则重复上述步骤。
（4）算法分析：定义进程控制块；
input()函数;
output()函数；
max_priority()函数找出就绪态中优先级最高的进程；
psa_pcb()函数为优先级调度算法；
main()主函数；
（5）核心代码：
#include<stdio.h>
/*结构体*/
struct PSA
{
char name[10]; //进程名
int runtime; //运行时间
int priority; //优先数
char state; //状态，三状态：W-就绪；R-运行；F-结束
};
struct PSA psa[10]; //定义进程控制块数组
/*输入函数*/
int input(int n)
{
printf("请输入PCB的进程名，运行时间，优先数:n");
for(int i=0;i<n;i++) //i为进程编号
{
scanf("%st%dt%d",&psa[i].name,&psa[i].runtime,&psa[i].priority);
psa[i].state=‘W’; //初始状态都设为就绪
getchar();
}
}
/*输出函数*/
int output(int n)
{
printf("n==============================n");
printf("进程号 运行时间 优先数 状态n");
printf("------------------------------n");
for(int i=0;i<n;i++)
printf("%s %7d%9dt%sn",psa[i].name,psa[i].runtime,psa[i].priority,&psa[i].state);
printf("==============================n");
}
/*进程在就绪状态时找出最大优先数进程（返回值为最大优先数编号）*/
int max_priority(int n)
{
int max=-1; //max为最大优先数
int m; //m为最大优先数进程的编号
for(int i=0;i<n;i++)
{ //进程在就绪状态时找出最大优先数
if(psa[i].state==‘R’) //进程在运行状态
return -1;
else if((max<psa[i].priority)&&(psa[i].state==‘W’)) //进程在就绪状态
{
max=psa[i].priority;
m=i; //把最大优先数对应的编号赋给m
}
}
//确保最大优先数进程还没结束运行
if(psa[m].state==‘F’) //最大优先数进程已结束运行
return -1;
else //最大优先数进程还没结束运行
return m; //返回值为最大优先数编号
}
/*优先数调度算法*/
int psa_pcb(int n)
{
int max_time=-1,m=0;
int sum=0; //sum为程序总运行次数
for(int i=0;i<n;i++)
sum+=psa[i].runtime;
printf("n初始时各进程信息如下:n");
output(n);
getchar();
for(int j=0;j<sum;j++)
{
//当程序正在运行时
while(max_priority(n)!=-1) //max_priority ()为找出最大优先数进程函数，返回最大值对应的编号m
{
if(psa[max_priority(n)].priority!=0)
psa[max_priority(n)].state=‘R’; //由就绪转为运行态
else
{ //当优先级降为0，进程还没运行完时
for(int i=0;i<n;i++)
if(max_time<psa[i].runtime)
{
max_time=psa[i].runtime;
m=i; //返回对应的编号
}
max_time=-1;
psa[m].state=‘R’; //状态转为运行态
}
}
//判断程序状态(对优先数和运行时间操作)
for(int i=0;i<n;i++)
{
if(psa[i].state==‘R’) //当进程处于运行状态时
{
if(psa[i].priority>0) //优先数>0
psa[i].priority--; //每运行一次优先数-1
psa[i].runtime--; //每运行一次运行时间-1
}
if(psa[i].runtime==0) //运行时间完
psa[i].state=‘F’; //进程状态转为完成状态
else //运行时间没完
psa[i].state=‘W’; //进程状态转为就绪状态
}
output(n);
getchar();
}
}
/*主函数*/
int main()
{
printf("优先数调度算法：n输入总进程数：n");
int n;
scanf("%d",&n); //输入总进程数n
input(n); //输入函数
psa_pcb(n); //优先数调度算法
return 0;
}
（6）测试数据或截图：
（7）运行结果分析：初始时，a、b、c、d、e五个进程的状态都是就绪态（W），其中c的优先级最大，则c首先得到CPU运行，其运行时间为2，在运行状态时运行时间减1，优先数减1；进程a的运行时间为0，此时a的状态由就绪态变为完成态；之后c、e的优先数都是最大的，但根据先来先服务调度策略，c先处于运行态，优先数减1，运行时间减1为0，所以c变成完成态；此时只有b、d、e三个进程处于就绪态，其中e的优先数最大，则e获得CPU投入运行，其运行时间减1，优先数减1；然后b和e的优先数都一样大，根据先来先服务调度策略，则b抢占CPU处于运行态，运行时间减1为0，则b变成完成态；此时只剩下d和e两个进程，e的优先数较大，则e抢占CPU处于运行态，优先数和运行时间减1；e优先数减1后与d的一样大，但根据先来先服务原则，d先获得CPU，处于运行态，优先数和运行时间减1；此刻，e的优先数比d大，故e得到CPU运行，运行时间和优先数减1；d和e的优先数又是一样大，但d先运行，运行时间和优先数减1，则e优先数大于d，e获得CPU，运行时间减1为0，e处于完成态；最后只剩d获得CPU运行，运行时间减1为0，变成完成态。总之，优先级高的进程先获得CPU处于运行态，运行一次后，运行时间与优先数减1,当运行时间不为0时加入就绪队列，运行时等于0时状态改为结束（F）。如果有多个优先级一样高的进程，则根据先来先服务原则处理。