前言：操作系统必须为多个进程之间可能有竞争关系的请求分配计算机资源。对处理器而言，可分配的资源是处理器上的执行时间，分配的途径是“调度”。调度功能必须设计成可以满足多个目标，包括公平、任何进程都不会产生饥饿、有效的使用处理器时间以及较低的开销，此外，调度中还需要考量优先级和实时期限方面。从根本上说，调度是属于队列管理，用来在排队环境中减少延迟和优化性能。（只记录了一些基本概念，细节还要回顾书）

一、调度类型

长程调度：决定加入到待执行的进程池中。

中程调度：决定加入到部分或全部在内存中的进程集合中。

短程调度：决定哪一个可运行的进程将被处理器执行。

I/O调度：决定哪一个进程挂起的I/O请求将被可用的I/O设备处理。

调度类型和进程状态转换可通过如下图理解：

从用户角度看，响应时间通常是系统最重要的一个特性；
从系统角度看，吞吐量或处理器利用率是最重要的。
在处理器的长程、中程、短程调度中，长程调度确定何时允许一个新进程进入系统；中程调度确定何时把一个程序的部分或全部取进内存，使得该程序能够被执行；短程调度确定哪一个就绪进程下一次被处理器执行。

二、调度算法

以上类型的调度中，短程调度是执行的最频繁的，也是最重要的，为所有就绪进程的短程调度决策算法大概有：
1、先来先服务：选择等待服务时间最长的进程。
2、轮转：使用时间片限制任何正在运行的进程只能使用一段处理器时间，并在所有就绪进程中轮转。
3、最短进程优先：选择预期处理时间最短的进程，并且不抢占该进程。
4、最短剩余时间：选择预期的剩余处理时间最短的进程。当另一个进程就绪时，这个进程可能会被抢占。
5、最高响应比优先：调度决策基于对归一化周转时间的估计。
6、反馈：建立一组调度队列，基于每个进程的执行历史和其他一些准则，把它们分配到各个队列中。
注意：具体的调度算法的选择取决于预期的性能和实现的复杂度。

三、多处理器调度

1、分类

（1）松耦合、分布式多处理器、集群
（2）专门功能的处理器
（3）紧耦合多处理器

2、粒度

根据粒度的不同，区分5类并行度：

细：单指令流中固有的并行。

中等：在一个单独应用中的并行处理或多任务处理。（可以理解为多线程并行，重点研究）

粗：在多道程序环境中并发进程的多处理。（多进程并发）

非常粗：在网络节点上进行分布处理，以形成一个计算环境。（集群中的并行）

无约束：进程间没有显式的同步，多个无关进程。

3、线程调度（中等粒度）

在单处理器中，线程可以用作辅助构造程序，并在处理过程中重叠执行I/O，并且进行线程切换时的系统开销远远小于进程切换的系统开销；而在多处理器中，线程可以用于开发应用程序中真正的并行性。如果一个应用程序的各个线程同时在各个独立的处理器中执行，其性能就会得到显著的提高。但是，这也给线程管理和同步带来了一定的麻烦。
实现的四种方法：
（1）负载共享：进程不是分配到一个特定的处理器。系统维护一个就绪进程的全局队列，每个处理器只要空闲就从队列中选择一个线程，确保当有工作可做时，没有处理器空闲。注意，这里与“负载均衡”不同，负载均衡是基于一种比较永久的分配方案分配工作的。
（2）组调度：一组相关的线程基于一对一的原则，同时调度到一组处理器上运行。
（3）专用处理器分配：与“负载共享”的方法相反，它通过把线程指定到处理器来定义隐式的调度。在程序执行过程中，每个程序被分配给一组处理器，处理器的数目与程序中线程的数目相等。当程序终止时，处理器返回到总的处理器池中，可供分配给另一个程序。
（4）动态调度：在执行期间，进程中线程的数目可以改变。

四、实时调度

1、关于实时计算和实时系统：
实时计算正在成为越来越重要的原则。调度器可能是实时系统中最重要的组件。
实时计算定义：系统的正确性不仅取决于计算的逻辑结果，而且还依赖于产生结果的时间。我们可以通过定义实时进程或实时任务来定义实时系统。
实时系统特点：可确定性、可响应性、用户控制、可靠性、故障弱化操作。核心是短程任务调度器。
                  快速的进程或线程切换；
                  体积小；
                  迅速响应外部中断的能力；
                  通过诸如信号量、信号、事件之类进程间通信的工具，实现多任务处理
                  使用特殊的顺序文件，可以快速存储数据
                  基于优先级的抢占式调度；
                  最小化禁止中断的时间间隔；
                  用于使任务延迟一段固定的时间或暂停/恢复任务的原语；
                  特别的警报和超时设定。

实时系统的核心是短程任务调度器。

实时进程的几种调度器（如下图所示）：
       轮转抢占式调度器；
       优先级驱动非抢占式调度器；
       优先级驱动、在抢占点抢占的调度器；
       立即抢占式调度器。

2、实时调度
关键因素是满足“最后期限”，在很大程度上依靠抢占和对相对最后期限有反应的算法。

最大期限的概念：当可以指定进程完成的最后期限时，调度原则将降低其他目标，使得满足最后期限的作业数目的百分比最大。

实时调度算法大概有如下几种：
      静态表法：执行关于可行性调度的静态分析；
      静态优先级抢占法：同样执行一个静态分析，但是没有制定调度，而且用于给任务指定优先级，使得可以使用传统的基 于优先级的抢占式调度器；
      基于动态规划调度法：在运行时动态的确定可行性，而不是在开始运行前离线的确定；
      动态尽力调度法：不执行可行性分析，系统试图满足所有的最后期限，并终止任何已经开始运行但错过最后期限的进程

五、Linux调度

Linux2.4的实时调度器与非实时的进程调度器耦合在了一起。（Linux 2.6也是如此，但是对非实时调度器进行了改进）

（一）Linux的实时调度
负责Linux调度的三个类：
    SCHED_FIFO：先进先出实时线程
    SCHED_RR：轮转实时线程
    SCHED_OTHER：其他非实时线程
每个类都使用了多优先级，实时类的优先级高于SCHED_OTHER类。
默认的设置是：实时优先级类的优先级范围0~99，SCHED_OTHER类的范围是100~199 。（小优）

对于FIFO类，有以下规则：
1、除非在以下情况，系统不会中断一个正在执行的FIFO线程：
     a、另一个具有更高优先级的FIFO线程就绪；
     b、正在执行的FIFO线程因为等待一个事件（如I/O）而被阻塞；
     c、正在执行的FIFO线程通过调用sched_yield原语自愿放弃处理器。
2、当一个FIFO线程被中断后，它被放置在一个与其优先级相关联的队列中。
3、当一个FIFO线程就绪，并且如果该线程比当前正在执行的线程具有更高的优先级时，当前正在执行的线程被抢占，具有更高优先级且就绪的FIFO线程开始执行。如果有多个线程都具有最高的优先级，则选择等待时间最长的线程。

对于SCHED_RR类，与FIFO类类似，只是在RR策略下，每个线程都有一个时间量与之关联。当一个RR线程在它的时间量里执行结束后，它被挂起，然后调度器选择一个具有相同或更高优先级的实时线程运行。

下面举例说明两个类的区别：假设存在四个线程ABCD，共有三种优先级，其中，D>B=C>A，且B在队列中的等待时间长于C，那么
对于FIFO类，调度器的执行顺序为: D--->B--->C--->A
对于RR类，调度器的执行顺序为: D--->B--->C--->B--->C--->A
RR类将会按照“时间片”来执行，不会考虑线程的等待时间。

对于SCHED_OTHER类，只有当没有实时线程运行就绪时，才可以执行这个类中的线程。

（二）Linux非实时调度
Linux 2.6改进了Linux 2.4中的非实时调度类SCHED_OTHER类，采用了一种全新的优先级调度策略，称为O(1)调度策略。
这个程序的设计原则是不管系统的负载或者处理器的数目如何变化，选择合适的任务并执行的时刻都是恒定的。
Linux2.6为每个优先级级别维护了一个单独的队列。总的队列个数是MAX_PRIO，默认值是140。内核为每个处理器维护了两套调度用的数据结构，分别为活动的队列结构、过期的队列结构。
每一个非实时的任务都被分配了一个范围从100~139的初始优先级，默认值是120 。
时间片分配的范围是10~200ms，一般而言，具有较高优先级的任务分配的时间片也较大。
在优先级队列中，处理实时任务的方式与处理非实时任务的方式不同，应用了下面一些考虑：
   1、所有的实时任务具有静态的优先级；不会作动态优先级的改变。
   2、SCHED_FIFO任务没有时间片。这些任务以FIFO的方式调度。如果一个SCHED_FIFO任务被阻塞，当它没有被阻塞的时候，将返回到同样优先级的活动队列中。
   3、SCHED_RR任务从不移到过期队列中。当一个SCHED_RR任务用完了自己的时间片后，它将返回到具有同样时间片的优先级队列。时间片的值不会被改变。
这些规则的效果是活动队列与过期队列之间的转换仅仅发生在没有准备就绪的实时任务在等待执行的时候。

操作系统精髓与设计原理------调度概述