1、背景介绍

CPU调度： 指从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程；调度程序是一个挑选进程/线程的内核函数(通过一些调度策略)。在进程/线程生命周期的状态切换时会触发调度。

内核运行调度程序的条件(满足一条即可)： 一个程序从运行状态切换到等待状态；一个进程被终结了。调度程序必须等待事件结束(不可抢占)；调度程序在中断被响应后执行，当前的进程从运行切换到就绪，或者一个进程从等待切换到就绪，当前运行的进程可以被换出(可以抢占)。

2、调度原则

执行模型： 程序在CPU突发和I/O中交替，每个调度决定都是关于下一个CPU突发时将哪个工作交给CPU；在时间分片机制下，线程可能在结束当前CPU突发前被迫放弃CPU。

下面是一些可以衡量调度算法的指标： CPU使用率： CPU处于忙状态所占时间的百分比；吞吐量： 在单位时间内完成的进程数量； 周转时间： 一个进程从初始化到结束，包括所有等待时间所花费的时间； 等待时间： 进程在就绪队列中的总时间； 响应时间： 从一个请求被提交到产生第一次响应所花费的时间。

一个好的调度算法需要包含以下特征：减少响应时间： 及时处理用户的输出并尽快地将输出提供给用户；减少平均响应时间的波动： 在交互系统中，可预测性比高差异低平均更加重要；增加吞吐量： 包括以下两个方面：减少开销(操作系统开销，上下文切换)和系统资源的高效利用(CPU，I/O设备)；减少等待时间： 减少每个进程的等待时间。

公平 的定义：不是保证每一个进程都占用相同的CPU时间，但可以时保证每一个进程都等待相同的时间，保证公平通常会增加平均的相应时间。

3、调度算法

常见的调度算法包括以下几种：FCFS-先来先服务，SPN(SJF) ；SRT-短进程优先(短作业优先)短剩余时间优先；HRRN-最高相应比优先；Round Robin-轮循：使用时间切片和抢占来轮流执行任务；Multilevel Feedback Queues-多级反馈队列：优先队列中的轮循；Fair Share Scheduling-公平共享调度。

3.1 FCFS算法

FCFS队列的规定：如果进程在执行中阻塞，队列中的下一个会得到CPU。下图通过举一个例子来进行说明。

从上图可以看出，优先调用短进程可以缩短程序整体的周转时间。

FCFS的优点为：主要为简单实现；缺点为：平均等待时间的波动较大；花费时间较少的任务可能排在花费时间长的任务后面；可能导致I/O和CPU之间的重叠处理，CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也在等待。

3.2 短任务优先-SPN

按照预测的完成时间来讲任务入队，如果进程的执行时间越短，则越早将进程越早执行，其优先级越高。短任务优先可以是可抢占的也可以是不可抢占的，其中可抢占(Shortest Remaining Time(SRT))的指的是在进程运行过程中，若有一个进程的预测运行时间要小于当前运行进程的剩余执行时间，则将当前正在执行的进程暂停执行，将CPU控制权交给新的剩余执行时间更短的进程。

最短任务优先的优点如上述可以缩短程序总的等待时间；其缺点为：一方面可能导致饥饿，连续的段任务流会使长任务饥饿，短任务可用时任何长任务的CPU时间都会增加平均等待时间，有违公平性的原则；另一方面SRT的实现需要预知未来，这就会涉及到怎样预估下一个CPU突发的持续时间，简单的解决方法是询问用户，若用户欺骗就杀死进程。

3.3 最高响应比优先-HRRN

在SPN调度的基础上进行了改进，关注进程等待了多长时间，不可抢占，防止了长进程测无限期推迟，有效缓解了SPN中长进程的饥饿现象，响应的计算方法为：

R = ( W + S ) / S

其中 W指等待时间；S指执行时间，SPN中只考虑了执行时间，选择 R值最高的进程来优先执行。

此算法的缺点和SPN一样无法准确预估进程所需要的执行时间，优点如上述可以有效缓解长进程的饥饿现象。

3.4 轮循算法-Round Robin

该算法给每一个进程一个固定的时间片，当进程执行时间超过时间片之后，换成其他进程继续执行，这样做可以较好地保证CPU利用的公平性，但是会产生较大的等待时间。

轮循算法示意图如下图所示：

RR会产出较多的额外的上下文切换；且时间量子的选择对于RR算法的执行效率影响巨大，若时间量子太大，则会使进程等待时间过长，极限情况下会退化成FCFS；如果时间量子太小，反应比较迅速但是由于频繁进行上下文切换会使吞吐量收到影响；一个好的RR算法需要选择一个合适的时间量子，基于经验规则：选择使上下文切换开销处于1%以内的时间量子。

3.5 公平共享算法-FFS

重点强调公平，在用户级别实现对CPU资源的公平调度。使用FFS的原因是因为：一些用户组比其他用户组更加重要；保重不重要的组无法垄断资源；未使用的资源按照每个组所分配的资源的比例来分配；没有达到资源使用率目标的组获得更到的优先级。

4、实时调度

实时调度应用于需要规定时间内完成某个任务，如火车，机床的控制等。实时调度的定义为：正确性依赖于其时间和功能两方面的一种操作系统。其性能指标包括：时间约束的及时性，速度和平均性能相对不重要。其主要特性为：时间约束的可预测性。

实时调度又可以分为“强实时系统”：需要在保证时间内完成重要的任务，必须完成；“弱实时系统”：要求重要的进程的优先级更高，尽量完成，并非必须完成。

实时调度的相关术语：任务：如一次计算，一次文件读取，一次信息传递等等；属性： 取得进展所需要的资源，定时参数；release： 进程就绪的时间；relative deadline： 相对结束时间；absolute deadline： 绝对结束时间；execution time： 执行时间。

实时调度算法可以分为两大类：静态优先级调度和动态优先级调度。速率单调调度(RM) 算法是一种静态优先级调度算法，进程优先级在任务执行之前就已经确定了，其通难任务周期安排优先级，周期越短优先级越高。最早期限调度(EDF) 算法是一种动态优先级调度算法，进程任务距离deadline 越短，其优先级越高，执行deadline 最早的任务。

5、多处理器调度

在多CPU的情况下，怎样完成多处理器调度，包括选择哪一个CPU进行处理当前任务和怎样保证所有CPU是load balance的。

优先级反转(priority inversion)，指的是低优先级的进程抢占了更低优先级的执行时间，从而影响了高优先级进程的正常运行，导致系统重启。

优先级反转的解决方法：将低优先级的任务的优先级根据需要使用他们共享资源的高优先级任务的优先级进行动态调整，即低优先级任务继承高优先级任务的优先级，当他们需要使用共享资源时。