前言：学习操作系统时，总是听到关于“调度”的事情。 我记得刚学习计算机操作系统的时候，觉得调试很贵，不敢接触太深。 这可能是因为在学生时代的我在算法方面不强，但是这些调度过程经常以算法的形式出现在教科书上。 这确实是一种算法。 我对这些算法有一些抵触，但当时可能是被DotA迷惑了。 我现在真的觉得算法很有魅力。 即使没有学某个算法，自己也能根据现有的算法思维想出一二，那就太爽了。
正文也是在我复习《计算机操作系统》这本书的时候，想用代码的形式来解释这些吸引人的东西。
摘要：我们在做编码开发的时候，与流程打交道。 但是，由于某些高级语言的封装，正在开发的进程可能感觉不到代码创建或调用进程。 当然，这也不是本文的重点。 但是，操作系统不能忽略进程。 本节使用Java开发语言来模拟操作系统中进程的调度过程。
3358 www.Sina.com/http://blog.csdn.net/lemon _ tree 12138/article/details/49927033-- coding-naga
本文链接：
进程调度算法：1.FCFS: FCFS是“先服务”的意思。 昏迷刺猬按照进程添加到队列的优先级顺序调用。 这里我们先来看看FCFS的算法的过程图。
图-1进程FCFS调度进程
通过上面的流程图可以清楚地看到流程的调度顺序和整个流程。
只是，不知道读者是否注意到了一个问题。 那就是，在上图中，我们把过程(矩形)紧紧地粘在一起。 那么，有什么能让这些矩形不在一起呢？ 如果你是个注意细节的人，我想你已经注意到那个了。 现在，我想再问一个问题，如果我们队列中的进程都运行了，而且队列中没有进程，这时怎么办？ 在这种情况下，CPU保持空闲，直到进程请求处理器出现在队列中并运行。 所以，在模拟程序中，可以直接跳过这一段时间。
关于上面这一点，在我们的代码中也必须考虑。 重要的步骤如下
pre name=' code ' class=' Java ' @ overridepublicintexecute (process model . process list ) if ) process list==null|| (if (！ (processlistinstanceofprocessfcfsmodel [ ] () system.out.println(tag '数据类型错误) )； 返回- 2； } processfcfsmodel [ ] fcfsmodels=(processfcfsmodel [ ] ) processList； int runTimeSum=0； 处理器： fcfsmodelmodels (for )运行时summodel.getcomingtime (if ) (运行时sum=(int ) model.getcomingtime ) runTimeSum =model.getRunTime (； model.setfinishtime(runtimesum )； model.setturnaroundtime (runtime sum-model.getcomingtime )； model.setturnaroundweighttime (1.0 * model.getturnaroundtime )/model.getRunTime )； } return runTimeSum； ) } 2.SPF: SP
F的意思是短进程优先(Short Process First)。意思也很清楚，就是让短的进程先运行，是什么短呢？这里说的是进程的运行时间。不要误以为系统好牛逼，带进程要运行多长时间都可以提前知道。其实，这个值是程序提前写在进程里面的了，系统只要去读取这个值就可以了。这里同样也为SPF算法画了一个过程图。其实这两个算法在过程图没有太大的出入，不过在代码差别还不小。见图-2。
图-2 进程SPF调度过程
可以很明显地看到这里的进程B与左边的进程队列有一些分离的感觉，并且在进程B的上方还有“最短运行时间”的描述。的确，这里的B是在运行过程中选出运行时间最短的进程。
你不会要问我为什么不事先给这个等待的进程队列进行排序吧。如果是事先对队列进行排序，在“排序”这个操作上时间复杂度的确可以降低。不过，很遗憾。我们不能这样做。因为系统中的进程是一个动态的过程，在什么时候有什么进程过来，都还是未知数。我们不能让操作系统这么神通广大，不让我们人类怎么办？-_-!
SPF模拟调度过程的关键代码如下：
<pre name="code" class="java"><pre name="code" class="java">@Override public int execute(ProcessModel... processList) { if (processList == null || processList.length == 0) { System.out.println(TAG + ">数据为空"); return -1; } if (!(processList instanceof ProcessSPFModel[])) { System.out.println(TAG + ">数据类型出错"); return -2; } ProcessSPFModel[] processArray = (ProcessSPFModel[])processList; boolean[]runFlag = new boolean[processArray.length]; int runTimeSum = 0; int index = 0; ProcessSPFModel currentProcess = processArray[index]; while(!noProcessWaitting(runFlag)) { currentProcess.setStartRunTime(runTimeSum); if (runTimeSum < currentProcess.getComingTime()) { runTimeSum = (int)currentProcess.getComingTime(); } runTimeSum += currentProcess.getRunTime(); currentProcess.setFinishTime(runTimeSum); currentProcess.setTurnaroundTime(runTimeSum - currentProcess.getComingTime()); currentProcess.setTurnaroundWeightTime(1.0 * currentProcess.getTurnaroundTime() / currentProcess.getRunTime()); runFlag[index] = true; index = getIndexMinRuntime(processArray, runFlag, runTimeSum); if (0 <= index && index < processArray.length) { currentProcess = processArray[index]; } else { System.out.println("未知异常"); break; } } return runTimeSum; } 这里有一个getIndexMinRuntime(...)方法，它的功能就是获得进程列表中服务时间最短的进程，当然前提是这个进程已经Coming。
private int getIndexMinRuntime(ProcessSPFModel[] processArray, boolean[] runFlag, int runTimeSum) { if (processArray.length == 0 || runFlag.length != processArray.length) { return -1; } int earliestIndex = 0; long earliestTime = Long.MAX_VALUE; int index = -1; long minTime = Long.MAX_VALUE; for (int i = 0; i < processArray.length; i++) { if (runFlag[i]) { continue; } if (processArray[i].getComingTime() < earliestTime) { earliestIndex = i; earliestTime = processArray[i].getComingTime(); } if (processArray[i].getComingTime() > runTimeSum) { continue; } if (processArray[i].getRunTime() < minTime) { minTime = processArray[i].getRunTime(); index = i; } } index = index < 0 ? earliestIndex : index; return index; }在上面的代码里，有两个变量earliestIndex和earliestTime。前者是指尚未执行的最早到达的进程的下标，后者尚未执行的最早到达进程的到达时间。这定义这两个变量的目的是针对于，如果等待的队列中没有可执行的进程，那么我们就去在还没有执行且是最早到达的进程去选择。这一步事实上是模拟时间再向后推移。
实例和结果：
这里我们通过一个例子来说明采用FCFS和SPF调度算法时的调度性能。现有五个进程A、B、C、D、E，它们到达的时间分别是0、1、2、3、4，所要求的服务时间分别是4、3、5、2 、4。
通过FCFS和SPF调度算法计算出来的结果如下的图-3所示.
图-3 通过FCFS和SPF算法的调度过程
从上面的结果中，我们不难计算出FCFS算法的平均周转时间为2.8，而SPF算法的平均周转时间只有2.1。
进程D的周转时间从11降到了3，带权周转时间也是从5.5降到了1.5.而对于进程C就要稍微差一点了。C的周转时间从10升到了16，带权周转时间也从2升到了3.2。所以在短进程优先的调度算法中，短进程得到了很好地照顾。
因为SPF相对于FCFS平均的周转时间降了很多。所以，一般情况下我们可以考虑使用SPF调度算法来替代FCFS。不过，有时候还是要具体问题具体问题具体对待了。毕竟是FCFS也有相对SPF的优势。
关于FCFS和SPF的内容目前就到这里了。下一篇会再来详解一下“非抢占式优先权算法”和“抢占式优先权调度算法”。尽请期待。
https://github.com/William-Hai/ProcessSchedulingRules