一只小码农

每天进步一点点

进程调度

发表于 更新于 分类于 Valine：
本文字数： 7.3k 阅读时长 ≈ 7 分钟
进程调度问题，结合Linux kernel总结

Linux进程调度

调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。进程调度程序(常常简称调度程序)可看做在可运行态进程之间分配有限的**处理器时间资源的内核子系统**。调度程序是像Linux这样的多任务操作系统的基础。只有通过调度程序的合理调度，系统资源才能最大限度地发挥作用，多进程才会有并发执行的效果。

在一组处于可运行状态的进程中选择一个来执行，是调度程序所需完成的基本工作,最大程度的利用处理器时间为原则。

多任务操作系统

多任务操作系统就是能同时并发地交互执行多个进程的操作系统。在单处理器机器上，这会产生多个进程在同时运行的幻觉。在多处理器机器上，这会使多个进程在不同的处理机上真正同时、并行地运行。无论在单处理器或者多处理器机器上，多任务操作系统都能使多个进程处堵塞或者睡眠状态，

多任务系统可以划分为两类：

非抢占式多任务(cooperative multitasking)

在非抢占式多任务模式下，除非进程自己主动停止运行，否则它会一直执行。进程主动挂起自己的操作称为让步(yielding)。理想情况下，进程通常做出让步，以便让每个可运行进程享有足够的处理器时间。但这种机制有很多缺点：调度程序无法对每个进程该执行多长时间做出统一规定，所以进程独占的处理器时间可能超出用户的预料；更糟的是，一个决不做出让步的悬挂进程就能使系统崩溃。

抢占式多任务(preemptive multitasking)

由调度程序来决定什么时候停止一个进程的运行，以便其他进程能够得到执行机会。这个*强制的挂起动作就叫做抢占(preemption)**。进程在被抢占之前能够运行的时间是预先设置好的，而且有一个专门的名字，叫进程的时间片(timeslice)***。时间片实际上是分配给每个可运行进程的处理器时间段。有效管理时间片能使调度程序从系统全局的角度做出调度决定，这样做还可以避免个别进程独占系统资源

Linux进程调度

开始采用了一种叫做O(1)*调度程序的新调度程序一一它是因为其算法的行为而得名，0(1)调度程序虽然对于大服务器的工作负载很理想，但是在有很多交互程序要运行的桌面系统上则表现不佳，因为**其缺少交互进程*

自2.6内核系统开发初期，开发人员为了提高对交 互程序的调度性能引入了新的进程调度算法。其中最为著名的是“**反转楼梯最后期限调度算法(Rotating Staircase Deadline scheduler(RSDL)**,该算法吸取了队列理论，将公平调度的概念引入了 Linux调度程序。并且最终在2623内核版本中替代了 0(1)调度算法，它此刻被称为“完全公平调度算法”，或者简称CFS

策略

根据进程分类确定策略

进程可以被分为I/O消耗型和处理器消耗型。

  • IO消耗型

    指进程的大部分时间用来提交I/O请求或是等待I/O请求。因此，这样的进程经常处于可运行状态，但通常都是**运行短短的一会儿**，因为它在等待更多的I/O请求时总会阻塞

    举例来说，多数用户图形界面程序（GUI）都属于I/O密集型，即便它们从不读取或者写入磁盘，它们也会在多数时间里都在等待来自鼠标或者键盘的用户交互操作。

  • 处理器耗费型(用于计算)

    处理器耗费型进程把时间大多用在执行代码上。除非被抢占，否则它们通常都一直不停地运行，因为它们没有太多的I/O需求。但是，因为它们不属于I/O驱动类型，所以从系统响应速度考虑，调度器不应该经常让它们运行。对于这类处理器消耗型的进程，调度策略往往是**尽量降低它们的调度频率，而延长其运行时间**。

有必要指出，随着CPU变得越来越快*，更多的进程倾向为I/O密集型**。这种现象之所以发生是因为CPU 的改进比磁盘的改进快得多***，其结果是，未来对I/O密集型进程的调度处理似乎更为重要。这里的基本思想 是，如果需要运行I/O密集型进程，那么就应该让它尽快得到机会，以便发出磁盘请求并保持磁盘始终忙 碌。从图中可以看到，如果进程是I/O密集型的，则需要多运行一些这类进程以保持CPU的充分利用。

调度策略通常要在两个矛盾的目标中间寻找平衡：进程响应迅速（响应时间短）和最大系统利用率（高吞吐量）。

Linux为了保证交互式应用和桌面系统的性能，所以对进程的响应做了优化（缩短响应时间），更倾向于优先调度I/O消耗型进程

根据进程优先级确定调度策略

调度算法中最基本的一类就是基于优先级的调度。这是一种根据进程的价值和其对处理器时

间的需求来对进程分级的想法。

通常做法是（其并未被Linux系统完全采用）优先级高的进程先运行，低的后运行，相同优先级的进程按轮转方式进行调度（一个接一个，重复进行）。

Linux采用了两种不同的优先级范围:

nice值

它的范围是从-20到+19, 默 认值为0 ；越大的nice值意味着更低的优先级;

在Mac OS X, 进程的nice值 代表分配给进程的时间片的绝对值；而Linux系统中，nice值则代表时间片的比例。你可以通过ps-el命令査看系统中的进程列表，结果中标记N1的一列就是进程对应的nice值。

实时优先级

默认情况下它的变化范围是从0到99 （包括0和99）。与nice值意义相反，越高的实时优先级数值意味着进程优先级越高。

实时优先级和nice优先级处于互不相交的两个范畴

时间片

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。*调度策略必须规定一*** *个默认的时间片***

时间片太长

时间片过长会导致系统对交互的响应表现欠佳，让人觉得系统无法并发执行应用程序

时间片太短

会明显增大进程切换带来的处理器耗时，因 为肯定会有相当一部分系统时间用在进程切换上，而这些进程能够用来运行的时间片却很短。

i/o消耗型和处理器消耗型的进程之间的矛盾在这里也再次显露出来：I/O消耗型不需要长的时间片，而处理器消耗型的进程则希望越长越好

Linux的CFS调度器并没有直接分配时间片到进程，它是将处理器的使用比划分给了进程。

进程所获得的处理器时间其实是和系统负载密切相关的。这个比例进一步还会受进程nice值的影响

Linux系统是抢占式的,其抢占时机取决于新的可运行程序消耗了多少处理器使用比。如果消耗的使用比比当前进程小，则新进程立刻投入运行，抢 占当前进程。否则，将推迟其运行。

案例：文本编辑器（IO）VS视频编码器（处理）

对于视频编码器。它对什么时间开始运行没有太严格的要求 用户几乎分辨不出也并不关心它到底是立刻就运行还是半秒钟以后才开始的。当然，它完成得越早越好，至于所花时间并不是我们关注的主要问题。

​

Linux调度算法

Linux调度器是以**模块方式提供**的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。

这种模块化结构被称为调度器类（scheduler classes）,它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，基础的调度器代码定义kemel/schedx文件中，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那一个程序。

完全公平调度（CFS）是一个**针对普通进程的调度类**，在Linux中称为SCHED_NORMAL（在POSIX中称为SCHED_OTHER） , CFS算法实现定义在文件kemel/sched_fair.c中

Unix系统中的进程调度–CFS公平调度

CFS的做法是允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了，CFS在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠nice值来计算时间片

任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。nice值对时间片的作用不再是算数加权，而是几何加权。任何nice值对应的绝对时间不再是一个绝对值，而是处理器的使用比。CFS称为公平调度器是因为它确保给每个进程公平 的处理器使用比。正如我们知道的，CFS不是完美的公平，它只是近乎完美的多任务。但是它确实在多进程环境下，降低了调度延迟带来的不公平性。

目标延迟

CFS为完美多任务中的无限小调度周期的近似值设立了一个目标。越小的调度周期将带来越好的交互性，同时也更接近完美的多任务。但是你必须承受更高的切换代价和更差的系统总吞吐能力。

最小粒度

CFS为此引入每个进程获得的时间片底线， 这个底线称为最小粒度。默认情况下这个值是1ms。如此一来，即便是可运行进程数量趋于无穷，每个最少也能获得1ms的运行时间，确保切换消耗被限制在一定范围内（避免为了降低延迟不断的无限小调度周期，从而增加了进程切换的消耗）

Linux调度的实现

时间记账

所有的调度器都必须对进程运行时间做记账。多数Unix系统，正如我们前面所说，分配一个时间片给每一个进程。那么当每次系统时钟节拍发生时，时间片都会被减少一个节拍周期。当一个进程的时间片被减少到0时，它就会被另一个尚未减到0的时间片可运行进程抢占。

进程选择

当CFS需要选择下一个运行进程时，它会挑一个具有最小vruntime的进程。这其实就是CFS调度算法的核心：选择具有最小vruntime的任务。【**最完美的调度：所有可运行进程的vruntime值将一致**】

CFS使用**红黑树**来组织可运行进程队列，并利用其迅速找到最小vruntime值的进程。

调度器入口

进程调度的主要入口点是函数schedule(),它定义在文件kemel/sched.c中。Schedule()通常都需要和一个具体的调度类相关联，也就是说，它会找到一个最高优先级的调度类睡眠和唤醒。

pick_next_task()会以优先级为序，从高到低，依次检查每一个调度类，并且从最高优先级的调度类中，选取最高优先级的进程。

睡眠和唤醒

休眠(被阻塞)的进程处于一个特殊的不可执行状态。这点非常重要，如果没有这种特殊状态的话，调度程序就可能选出一个本不愿意被执行的进程。

休眠的操作

内核的操作都相同：进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule。选择和执行一个其他进程。

休眠有两种相关的进程状态：**TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE**.它们的唯_区别是处于TASK_UNINTERRUPTIBLE的进程会忽略信号，而处于TASK_INTERRUPTIBLE状态的进程如果接收到一个信号，会被提前唤醒并响应该信号。 两种状态的进程位于同一个等待队列上，等待某些事件，不能够运行。

唤醒的操作

唤醒操作通过函数wake_up()进行，它会唤醒指定的等待队列上的所有进程。它调用函数try_to_wake_up(),该函数负责将进程设置为TASK_RUNNING状态，调用enqueue_task()将此进程放入红黑树中，如果被唤醒的进程优先级比当前正在执行的进程的优先级高，还要设置need_resched标志

抢占和上下文切换

上下文切换

上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由定义在kemel/sched.c中的context_switch()函数负责处理。每当一个新的进程被选出来准备投入运行的时候，schedule()就会调用该函数。它完成了两项基本的工作：

  • 调用声明在<asm/mmu_context.h>中的switch_mm(),该函数负责把虚拟内存从上一个进程映射切换到新进程中。

  • 调用声明在＜asm/system.h＞中的switch_to(),该函数负责从上一个进程的处理器状态切换

    到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息，还有其他任何与体系结’

    构相关的状态信息，都必须以每个进程为对象进行管理和保存。

抢占

内核提供了一个**need_resched**标志来表明是否需要重新执行一次调度。

用户抢占

  • 从系统调返回用户空间时。
  • 从中断处理程序返回用户空间时。

内核抢占

  • 中断处理程序正在执行，且返回内核空间之前。
  • 内核代码再一次具有可抢占性的时候。
  • 如果内核中的任务显式地调用schedule。
  • 如果内核中的任务阻塞(这同样也会导致调用schedule())

调度【现代操作系统中根据不同操作系统总结】

何时调度

在创建一个新进程之后，需要决定是运行父进程还是运行子进程。

由于这两种进程都处于就绪状态，所以这是一种正常的调度决策，可以任意决定，也就是说，调度程序可以合法选择先运行父进程还是先运行子进程。

在一个进程退出时必须做出调度决策。

一个进程不再运行（因为它不再存在），所以必须从就绪进程集中选择另外某个进程。如果没有就绪的进程，通常会运行一个系统提供的空闲进程。

当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时，必须选择另一个进程运行。

有时，阻塞的原因会成为选择的因素。例如，如果A是一个重要的进程，并正在等待B退出临界区，让B随后运行将会使得B退出临界区，从而可以让A运行。不过问题是，通常调度程序并不拥有做出这种相关考虑的必要信息。

在一个I/O中断发生时，必须做出调度决策。

如果中断来自I/O设备，而该设备现在完成了工作，某些被阻塞的等待该I/O的进程就成为可运行的就绪进程了。是否让新就绪的进程运行，这取决于调度程序的决定，或者让中断发生时运行的进程继续运行，或者应该让某个其他进程运行。

根据如何处理时钟中断，可以把调度算法分为两类。

  • 非抢占式调度算法

    非抢占式调度算法挑选一个进程，然后让该进程运行直至被阻塞（阻塞在I/O上或等待另一个进程），或者直到该进程自动释放CPU。即使该进程运行了若干个小时，它也不会被强迫挂起。这样做的结果是，在时钟中断发生时不会进行调度。在处理完时钟中断后，如果没有更高优先级的进程等待到时，则被中断的进程会继续执行。

  • 抢占式调度算法

    抢占式调度算法挑选一个进程，并且让该进程运行某个固定时段的最大值。如果在该时段结束时，该进程仍在运行，它就被挂起，而调度程序挑选另一个进程运行（如果存在一个就绪进程）。进行抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把CPU控制返回给调度程序。如果没有可用的时钟，那么非抢占式调度就是惟一的选择了。

调度算法分类

不同的环境需要不同的调度算法，在不同的系统中，调度程序的优化是不同的。

  • 批处理

    批处理系统在商业领域仍在广泛应用，用来处理薪水册、存货清单、账目收入、账目支出、利息计算 （在银行）、索赔处理（在保险公司）和其他的周期性的作业。在批处理系统中，不会有用户不耐烦地在终端旁等待一个短请求的快捷响应。因此，*非抢占式算法**，或对每个进程都有长时间周期的抢占式算法***，通常都是可接受的。这种处理方式减少了进程的切换从而改善了性能。这些批处理算法实际上相当普及，并经常可以应用在其他场合。

  • 交互式

为了避免一个进程霸占CPU拒绝为其他进程服务，抢占是必需的。即便没有进程想永远运行，但是，某个进程由于一个程序错误也可能无限期地排斥所有其他进程。为了避免这种现象发生，抢占也是必要的。服务器也归于此类，因为通常它们要服务多个突发的（远程）用户。

  • 实时

有实时限制的系统中，抢占有时是不需要的，因为进程了解它们可能会长时间得不到运行，所以 通常很快地完成各自的工作并阻塞。实时系统与交互式系统的差别是，实时系统只运行那些用来推进现有应用的程序，而交互式系统是通用的，它可以运行任意的非协作甚至是有恶意的程序。

在所有的情形中，公平是很重要的。相似的进程应该得到相似的服务。

保持系统的所有部分尽可能忙碌。【CPU针对于CPU密集作业和磁盘针对于IO密集作业的组合，保证CPU和磁盘是尽可能忙碌，减少空转】

批处理系统中的调度

先来先服务（first-come first-served）

使用该算法，进程按照它们请求CPU的顺序使用CPU。【**非抢占式**】

过程

有一个就绪进程的单一队列。早上，当第一个作业从外部进入系统，就立即开始并允许运行它所期望的时间。不会中断该作业，因为它需要很长的时间运行。当其他作业进入时，它们就被安排到队列的尾部。当正在运行的进程被阻塞时，队列中的第一个进程就接着运行。在 被阻塞的进程变为就绪时，就像一个新来到的作业一样，排到队列的末尾。

优缺点
  • 主要优点是易于理解并且便于在程序中运用
  • 在计算密集型和IO密集型应用的组合上容易出现问题。

IO密集型应用在运行期间，多半时间花费在磁盘读写操作上，且时间比较长，影响了计算密集型应用对于CPU的占有使用。

最短作业优先

适用于运行时间可以预知的另一个**非抢占式**的批处理调度算法

当输入队列中有**若干个同等重要的作业**被启动时，调度程序应使用最短作业优先（shortest job first）算法

a) 有4个作业A、B、C、D，运行时间分别为8、4、4、4分钟。若按图中的次序运行，则A的周转时间为8分钟，B为12分钟，C为16分钟，D为20分钟，平均为14分钟。

b）目前周转时间分别为4、8、12和20分钟，平均为11分钟。可以证明最短作业是最优的。

为什么最短作业最优的推导

考虑有4个作业的情况，其运行时间分别为a、b、c、d。第一个作业在时间a结束，第二个在时间a+b结束，以此类推。平均周转时间为（4a+3b+2c+d）/4。显然a对平均值影响最大，所以它应是最短作业，其次是b，再次是c，最后的d只影响它自己的周转时间

只有在所有的作业都可同时运行的情形下，最短作业优先算法才是最优化的，不然，运行时间成本里还需要考虑对相关作业的等待时间。

最短剩余时间优先

最短作业优先的*抢占式版本**是最短剩余时间优先（shortest remaining time next）算法。使用这个算法， 调度程序总是选择剩余运行时间最短的那个进程运行。再次提醒，有关的运行时间必须提前掌握。当一个新的作业到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，而运行新的进程***【抢占】。这种方式可以使新的短作业获得良好的服务

谢谢你的支持哦，继续加油.