[科普中国]-算法调度

在计算中，算法调度是通过某种方式指定的工作被分配给完成工作的资源的方法。 该工作可以是虚拟计算元素，例如线程，进程或数据流，其又被调度到诸如处理器，网络链接或扩展卡之类的硬件资源上。

调度程序执行调度活动。 调度程序通常被实现，因此它们使所有计算机资源保持繁忙（如在负载平衡中），允许多个用户有效地共享系统资源，或实现目标服务质量。 调度是计算本身的基础，也是计算机系统执行模型的固有部分; 调度的概念使得可以使用单个中央处理单元（CPU）进行计算机多任务处理。

进程调度程序进程调度程序是操作系统的一部分，用于决定在某个特定时间点运行哪个进程。它通常能够暂停正在运行的进程，将其移动到正在运行的队列的后面并启动一个新进程;这样的调度程序称为抢先调度程序，否则它是一个协作调度程序。

长期调度长期调度程序或许可调度程序决定允许哪些作业或进程进入就绪队列（在主存储器中）;也就是说，当尝试执行程序时，其对当前正在执行的进程集的许可由长期调度程序授权或延迟。因此，这个调度程序决定了在系统上运行什么进程，以及任何时候要支持的并发程度 - 是否要同时执行多个或几个进程，以及I/O密集型和CPU之间的分配方式-要处理密集的过程。长期调度程序负责控制多道程序的程度。

通常，大多数进程可以描述为I/O绑定或CPU绑定。I/O绑定进程是指花费更多时间进行I/O而不是进行计算的进程。相反，CPU绑定的进程不经常生成I/O请求，使用更多的时间进行计算。重要的是，长期调度程序选择I/O绑定和CPU绑定进程的良好进程组合。如果所有进程都受I/O限制，则就绪队列几乎总是为空，短期调度程序几乎没有。另一方面，如果所有进程都受CPU限制，则I/O等待队列几乎总是为空，设备将不使用，系统将再次失衡。因此，具有最佳性能的系统将具有CPU绑定和I/O绑定进程的组合。在现代操作系统中，这用于确保实时进程获得足够的CPU时间来完成任务。

长期调度在大规模系统中也很重要，例如批处理系统，计算机集群，超级计算机和渲染农场。例如，在并发系统中，通常需要对交互过程进行协同调度，以防止它们因为彼此等待而阻塞。在这些情况下，除了操作系统中的任何基础准入调度支持之外，专用作业调度器软件通常用于辅助这些功能。

中级调度中期调度程序暂时从主内存中删除进程并将它们放在辅助内存（例如硬盘驱动器）中，反之亦然，这通常被称为“交换”或“交换”（也错误地称为“分页”）在“）中”或“分页”。中期调度程序可能决定换出一段时间内未处于活动状态的进程，或者具有低优先级的进程，或者频繁发生页面错误的进程，或者占用大量进程的进程。内存以便为其他进程释放主内存，稍后当更多内存可用时，或者当进程被解除阻塞并且不再等待资源时，将进程交换回来。

在当今的许多系统中（那些支持将虚拟地址空间映射到除交换文件之外的辅助存储的系统），中期调度程序实际上可以通过将二进制文件视为其上的“交换进程”来执行长期调度程序的角色。执行。这样，当需要一段二进制时，它可以按需交换，或“延迟加载”。

短期调度短时调度程序（也称为CPU调度程序）决定在时钟中断，I / O中断，操作系统调用或其他形式之后要执行哪些就绪的内存中进程（分配CPU）信号因此，短期调度程序比长期或中期调度程序更频繁地进行调度决策 - 调度决策至少必须在每个时间片之后进行，并且这些决策非常短。该调度程序可以是抢占式的，这意味着它能够在CPU决定将CPU分配给另一个进程时强制从CPU中删除进程，或者非抢占式（也称为“自愿”或“合作”），其中如果调度程序无法“强制”关闭CPU的进程。

抢占式调度程序依赖于可编程间隔计时器，该计时器调用在内核模式下运行的中断处理程序并实现调度功能。

算法先来先服务(FCFS)调度算法FCFS是按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业/进程。是一种最简单的调度算法，即可用于作业调度，也可用于进程调度。

先来先服务（先进先出）优缺点
1、比较有利于长作业（进程），而不利于短作业（进程） 。
2、有利于CPU繁忙型作业（进程） ，而不利于I/O繁忙型作业（进程） 。
3、用于批处理系统，不适于分时系统。

短作业优先调度算法（SJF）SJF是从队列中选出一个估计运行时间最短的作业优先调度，即可用于作业调度，也可用于进程调度

SJF调度算法也存在不容忽视的缺点
1、对长作业不利。严重的是，若一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度——饥饿。
2、完全未考虑作业(进程)的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。
3、由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

高响应比优先调度算法高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。

该算法中的响应比是指作业等待时间与运行比值,响应比公式定义如下：响应比 =(等待时间+要求服务时间)/要求服务时间

优点：等待时间相同的作业，则要求服务的时间愈短，其优先权愈高，对短作业有利。要求服务的时间相同的作业，则等待时间愈长，其优先权愈高，是先来先服务。长作业，优先权随等待时间的增加而提高，其等待时间足够长时，其优先权便可升到很高， 从而也可获得处理机，对长作业有利。是一种折衷，既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得不到服务1。

缺点：要进行响应比计算，增加了系统开销**。**

简单的时间片轮转法(RR—Round Robin)系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片；当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首；时间片的大小从几ms到几百ms 。

缺点：紧迫任务响应慢。 时间片选取 太小，会频繁发生中断、进程上下文切换，增加系统开销，但利于短作业 太大，退化成FCFS —时间片应该略大于一次典型交互的时间。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学