调度

调度在计算机中是分配工作所需资源的方法。资源可以指虚拟的计算资源，如线程、进程或数据流；也可以指硬件资源，如处理器、网络连接或扩展卡。

进行调度工作的程序叫做调度器。调度器通常的实现使得所有计算资源都处于忙碌状态（在负载均衡中），允许多位用户有效地同时共享系统资源，或达到指定的服务质量。调度是计算自身的基础，同时也是编程语言计算模型固有的部分。调度器使得在单处理器上通过多任务处理，从而让执行多个进程成为可能。

调度器可能会针对不同的目标设计，例如：吞吐率最大化、响应时间最小化、最低延迟、或最大化公平。在实践中，这些目标通常是互相冲突的，因此，调度器会实现一个权衡利弊的折中方案，而侧重点则可能是前文提到的任何一种，这取决于用户的需求和目的。

在实时环境，例如工业上用于自动控制（如机器人）的嵌入式系统，调度器必须保证进程的调度不能超过最后期限 —— 这是保持系统稳定运行的关键因素。调度也可能是通过一个管理性的后端进行，而任务是通过网络发配到若干远程设备上的。

调度器是操作系统的一个模块，它能够选择将被系统处理的下一个任务，或执行的下一个进程。操作系统可能会提供三种不同类型的调度器：长期调度器、中期调度器和短期调度器。这些名字表明了任务被执行的频率。

1. 长期调度器：长期调度器，决定了任务或进程是否会被就绪队列（内存中）所接纳。当一个运行程序的尝试被做出后，长期调度器或允许，或是延迟将它作为当前执行的一个进程。因此，这种调度器掌控着能在系统上运行的进程。调度器同时还决定并发的程度：同时执行程序的多少，在I/O密集型和CPU密集型进程之前做出划分。通常，大多数进程可以分为I/O密集型和CPU密集型。I/O密集型程序将大多数时间都花在了I/O操作而不是运算上，而CPU密集型程序正好相反，将大多数时间花在了运算上，而很少产生I/O操作。选出一个I/O密集型和CPU密集型程序的良好组合，对于长期调度器是非常重要的。否则，假如所有的程序都是CPU密集型的，那么I/O队列将会几乎永远都是空的，这样就会导致一些设备从来没被人用过，系统资源分配就是不均衡的。显然，性能极佳的系统必然是CPU密集型和I/O密集型程序的组合。在现代操作系统中，这被用来保证实时进程能获得足够的CPU时间来完成任务。长期调度对大型系统，例如批处理系统、计算机集群、超级计算机和渲染场来说同样重要。例如，在并发系统中，为了避免交互的多个进程，把时间都花在等待对方而产生阻塞，通常是需要进行协同调度的。在这种情况下，处理操作系统底层的调度器之外，还需要匹配要求的额外调度程序来实现必要的功能。
2. 中期调度器：中期调度器临时将进程从内存中去除，放入第二储存设备（如硬盘）中，或亦而反之。这通常被称为“换出”和“换入”（同时也被错误叫做“分页入”和“分页出”）。中期调度器可能会将那些一直不活跃的进程，优先级低的进程，频繁产生页错误的进程，或者占用大量内存的进程放入交换区，为其它程序释放内存。当系统内存充足时，或者程序不再处于阻塞状态时，调度器又会将刚刚被放入交换区中的进程重新放入内存中。
3. 短期调度器：短期调度器（也就是CPU调度器）决定了在一个时钟中断、I/O中断、系统调用其它种类的信号之后，应该执行（分配CPU）给哪些内存中的进程。可见，短期调度器作出决定的频率比长期或中期调度器更加频繁 —— 每隔一段非常短的固定时间，调度器就将做出一次决定。这种调度器可以是抢占式的，能够强行把一个在CPU运行中的程序中断，然后分配给其它进程；也可以是非抢占式的，这类调度器无法强行把进程从CPU上中断。抢占式调度器的功能需要一个运行在内核态，能被中断处理程序捕获的可编程定时器才能实现。

[描述来源：维基百科 URL：https://en.wikipedia.org/wiki/Scheduling_(computing)]

发展历史

调度是一直伴随着计算机学科发展的一个问题，1973年，C. L. Liu和James W. Layland从需要保证服务的程序功能所特有的特性的角度研究了单处理器上的多程序调度问题。 结果表明，最佳固定优先级调度程序具有处理器利用率的上限，对于大型任务集，该上限可能低至70％。 他们还表明，可以通过基于当前最后期限动态分配优先级来实现全处理器利用率，并讨论了这两种调度技术的组合。

1989年，基于C. L. Liu和James W. Layland的工作，J. Lehoczky等人表示了速率单调调度算法满足周期性任务集的期限的能力的精确表征。 此外，他们还给出了随机分析，给出了随机生成的任务集的故障利用率的概率分布。 结果表明，随着任务集大小的增加，任务计算时间变得不重要，故障利用率收敛于由任务周期确定的常数。 对于均匀分布的任务，88％的故障利用率是合理的表征。

由于多处理器调度的问题可以被陈述为找到要在多处理器系统上执行的一般任务图的调度，该调度问题是NP难的，并且当时已经存在许多基于启发式搜索的方法以获得最优和次优的解决方案。1994年，Hong Ren等人试图使用遗传算法来解决多处理器调度问题。该算法中搜索节点的表示基于在每个单独处理器中执行的任务的顺序，提出的遗传算子基于任务图中任务之间的优先关系。他们的仿真结果比较了所提出的遗传算法，列表调度算法，使用随机任务图的最优调度，以及机器人逆动力学计算任务图。1999年，Nick McKeown提出了input-queued switches的iSLIP调度算法。

2001年，Scott Fluhrer，Itsik Mantin，Adi Shamir提出了RC4密钥调度算法的几个弱点。 他们识别大量弱密钥，其中少量密钥位的知识足以确定许多状态和输出位。 他们使用这些弱键为RC4构建新的识别器，并使用实际的复杂性来安装相关的密钥攻击。 最后，他们表明RC4在广泛部署的有线等效保密协议（WEP，它是802.11标准的一部分）中使用的共同操作模式中是完全不安全的，其中固定的密钥与已知的IV修饰符连接在一起。 他们对这种模式的新的被动密文攻击可以在一个可忽略的时间内恢复一个任意长的密钥。

主要事件

发展分析

瓶颈

多处理器调度的问题是NP难的，大部分NP难问题似乎都需要超多项式时间。这些问题是否在多项式时间内无法确定，是计算机科学中最大的开放性问题之一。

未来发展方向

更高效率的调度算法，或更宏观一点，研究NP问题——这是一个不仅仅受到数学界和计算机学界关注的问题。

Contributor: Yuanyuan Li