进程先来先服务调度算法的动态演示研究
2017-09-20申鸿烨于维海
申鸿烨，于维海
（沈阳广播电视大学信息工程学院，沈阳110003)
进程先来先服务调度算法的动态演示研究
申鸿烨，于维海
（沈阳广播电视大学信息工程学院，沈阳110003)
进程的先来先服务算法在操作系统中具有重要地位，给出相关代码的动态演示，通过该演示，学生可以更加清晰地了解先来先服务算法的基本思想和工作流程，了解该算法与其他算法的联系与区别。
调度算法；先来先服务
0 引言
在日常生活中，经常要发生调度问题。例如，建筑工地中如何安排各工种的施工顺序等。在操作系统中，同样离不开调度，调度不仅涉及到进程调度，而且还包括作业调度。计算机中，CPU是计算机最主要的资源，只有通过调度才能把CPU分配给合适的进程。大型的计算机操作系统里，往往有上百个终端和主机相连接，有众多用户同时在线访问一台服务器，这些进程不可能一股脑地并发执行，而是按照一定的逻辑顺序先后执行，那么怎样从中挑选出合适的进程让它参与运行呢？率、吞吐量、周转时间、平均带权周转时间、就绪等待时间响应时间等。其中，先来先服务算法就是一种最简单的调度算法，它的思路就是排队买票的方法，每次调度从后备队列中挑选出最前面的一个，把它调入内存，分配相应的资源创建进程，然后把进程放入到就绪队列，然后把CPU分配给该进程让它参与运行，一直运行下去直到完成或者由于某种原因阻塞，放弃CPU才结束。这样当某个进程进入到就绪队列中时，它的PCB（Process Control Block进程控制块）将其链接到就绪队列的末尾，每次调度算法都从队首获取该进程，分配CPU，使其运行。
1 先来先服务算法
2 算法实现
以作业调度算法为例，它的工作是，把合适的作业，调入到内存中。设计一个调度算法包括多个指标：例如进程调度的设计目标，对于批处理系统而言，应该尽量提高各种资源的利用率和增加系统的平均吞吐量；如果是实时系统，为了提高系统对外部的响应，要考虑对时间的及时可靠处理的效率；还要考虑均衡性，尽量使系统中各类资源能够同时得到利用，提高资源的利用率，可以设置作业的优先级，优先考虑优先级高的作业。
衡量作业性能的标准方面，可以使用CPU利用
为演示需要，设有3个作业队列，编号分别是1、2、3，每个进程到达时间相差一个时间单位，如图1所示。
图1 先来先服务调度算法
各进程初始数据如下表1所示。
作业控制块JCB结构体包括：作业名称、作业到达时间、作业运行时间、作业开始运行的时间、作业完成的时间、作业的周转时间等，结构体如下：
JCB{
char jobName[10];//名称
intarriveTime;//到达时间
int runTime;//运行时长
intstartTime;//开始时间
intendTime;//完成时间
intzzTime;//周转时间
charstatus[10];//状态
};
init函数用于创建JCB，代码如下：
void init(struct JCB*jcb){
......
jcb[0].arriveTime=0;//本例假设每个进程相差一个时间单位
jcb[1].arriveTime=1;
jcb[2].arriveTime=2;
......
}
先来先服务意味着先到的进程优先运行，因此需要对其排序，使用sort函数将各个进程按照到达进程链的时间先后，按照升序排列，准备下一步运算。
void sort(struct JCB*jcb){
for(int i=0;i<3;i++){
intmin=jcb[i].arriveTime;
int idx=i;
for(int j=i+1;j<3;j++){
if(jcb[j].arriveTime min=jcb[j].arriveTime; idx=j; } } struct JCB t=jcb[i]; jcb[i]=jcb[minIndex]; 表1 各进程初始数据 jcb[idx]=t; } } //先来先服务调度算法 void runIt(struct JCB*jcb){ init(jcb);//创建JCB sort(jcb); intcurrentTime=0; //进程调度currentTime每次加1，直到进程全部被调度完成为止 for(i=0;i<3;i++){ jcb[i].startTime=currentTime; jcb[i].endTime=jcb[i].startTime+jcb[i].runTime; jcb[i].zzTime=jcb[i].endTime-jcb[i].arriveTime; strcpy(jcb[i].status,RUN); while(true){ if(currentTime==jcb[i].endTime){ strcpy(jcb[i].status,FINISH); break; }else{ printIt(jcb);//打印当前进程状态 } currentTime++;//模拟时钟不停运行，直到进程全部被调度完成为止 } } } 上述各函数分别进行了初始化等工作，下面执行printIt函数，逐个时间片将三个进程的工作状态列举打印出来，展示动态过程。 printIt(struct JCB*jcb){ printf("当前时间：%d
",currentTime); printf("作业号到达时间需要运行时间开始时间完成时间周转时间状态
"); for(inti=0;i<3;i++){ printf("%s%d%d%d%d%d%s
",jcb[i].job⁃Name,jcb[i].arriveTime,jcb[i].runTime,jcb[i].startTime,jcb[i]. endTime,jcb[i].zzTime,jcb[i].status); } } 通过计算，本例的先来先服务算法的性能如表2所示。 本文给出了操作系统课程中先来先服务算法的程序实现，给出了相关代码的动态演示，通过该演示，学生可以更加清晰地了解先来先服务算法的基本思想和工作流程，了解该算法与时间片轮转法、优先级法、短作业优先法、最短剩余时间优先法、多级队列法、多级反馈队列法之间的联系与区别，为后续课程的学习打下了良好铺垫。 [1]孟庆昌．操作系统[M]．北京：中央广播电视大学出版社，2008. [2](美)斯托林斯著．操作系统：精髓与设计原理[M]．北京：机械工业出版社，2010.9. [3]张尧学．计算机操作系统教程[M]．北京：清华大学出版社，2013.10. [4]Andrew S.Tanenbaum．操作系统设计与实现[M]．北京：电子工业出版社，2015.6. Research on the Dynam ic Demonstration FirstCome First Service Process Scheduling Algorithm SHENHong-ye，YUWei-hai First come first serve algorithm plays an important role in the operating system,gives the dynamic demonstration of the relevant code, through the demonstration,students canmore clearly understand the basic idea and working processof first come firstservice,don'tunder⁃stand connectionsand the algorithm with otheralgorithm. 申鸿烨（1973-），男，河北内丘人，硕士，研究生，研究方向为远程教育、云计算、大数据 2017-05-22 2017-07-28 2016年度辽宁省教育科学“十三五”规划课题（No.JG16EB182） 1007-1423（2017）22-0003-03 10.3969/j.issn.1007-1423.2017.22.001 于维海（1976-），男，辽宁沈阳人，硕士，讲师，研究方向为数据挖掘 Scheduling Algorithm;FirstCome FirstServed
3 运行
4 结语
（Schoolof Information Engineering,Shenyang Radio and TVUniversity,Shenyang 110003）
