进程调度

简介

由于可能有多个进程或线程在竞争CPU，因此需要从所有就绪的线程或进程中选择下一个运行的，完成该工作的程序即为调度程序。总的来说，调度算法应当满足以下目标：

• 所有系统
  • 公平：给每个进程公平的CPU份额
  • 策略强制执行：满足不同系统的实际需求的策略
  • 平衡：保持系统的不同部分忙碌
• 批处理系统
  • 吞吐量：单位时间作业数
  • 周转时间：从提交到完成所花费的时间数
  • CPU利用率：保持CPU始终忙碌
• 交互式系统
  • 响应时间：快速的响应请求
  • 均衡性：满足用户需求
• 实时系统
  • 满足截至时间
  • 可预测性

先来先服务(FCFS)

非抢占式的先来先服务调度算法按照所有进程请求CPU的顺序来使用CPU，每个进程在获得CPU后会一直执行直到完成任务。但假设如下情况，一个需要耗时一小时任务先请求CPU，但剩余1000个任务仅需1秒即可完成，但由于较长的任务先请求CPU因此会先被执行，导致平均周转时间较长。

短作业优先

如果已知各个作业完成所需要的时间则可以利用短作业优先算法，该算法是非抢占式的，每次会从所有等待CPU的进程中选择需要时间最短的任务来运行，但该算法可能会导致运行时间较长的任务饥饿。

最短剩余时间优先

最短剩余时间优先是短作业优先的抢占式版本，调度程序会根据当前正在运行的任务和所有请求运行的任务的需要执行的时间来进行调度，从中选择剩余运行时间最短的一个来运行，如果剩余时间最短的那个不是当前正在运行的任务则将当前任务挂起，切换至剩余时间最短的任务运行。该方法能够使新的短作业获得较好的服务。

轮转调度

每个进程都被分配一个时间段并称为时间片，每个进程仅能在该时间段内运行，如果时间片结束时该进程仍旧没有运行完成则剥夺CPU并将CPU分配给另一个进程。如果该进程在时间片结束前阻塞或结束则立刻进行切换。

优先级调度

每次从所有进程中选择优先级最高的一个运行。为了防止高优先级的进程毫无止境的运行下去，可以每隔一段时间降低该进程的优先级，如果某一次优先级的降低导致了次高优先级的进程优先级比正在运行的进程的优先级高则进行切换。

多级队列

假设有N个队列（Q1,Q2….QN），其中各个队列中的作业(进程)的优先级都是不一样的。假设优先级Priority(Q1) > Priority(Q2) > … > Priority(QN)。对于某个特定的队列来说，遵循的依旧是时间片轮转法。也就是说，每个队列中的任务运行时的时间片长度与队列相关。而且各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。

多级队列调度算法流程如下：

• 进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
• 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
• 对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
• 在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）

彩票调度

彩票调度算法，每个待运行的进程分配一张彩票，每次需要调度的时候，随机抽取一张已分配的彩票，中奖的进程获得CPU，因此如果是优先级比较高的进程可以多为其分配一些彩票，来提升其得到CPU的概率。