多任务

      多任务系统可以划分为两类：非抢占式（cooperative multitasking）和抢占式多任务（preemptive multitaskin）。由调度程序来确定什么时候停止一个进程的运作，以便其他进程能够得到执行的机会，这个强制挂起的动作就叫作抢占（preemption）。进程在被抢占之前能够运行的时间是预先设置好的，而且有一个专门的名字，叫作进程的时间片（timeslice）。时间片实际上就是分配给每个可运行进程的处理器时间段。有效管理时间片能够使调度程序从系统全局的角度做出决定，这样做还可以避免个别进程独占系统资源。多数现代操作系统对程序运行都采用了动态时间片计算的方式，并且引入了可配置的计算策略。Linux独一无二的“公平”调度程序本身并没有采取时间片来达到公平调度。

      在非抢占式多任务模式下，除非自己进程主动停止运行，否则它会一直执行。

Linux的进程调度策略

        进程可以被分为I/O消耗型和处理消耗型.前者指进程的大部分时间用来提交I/O请求或是等待I/O请求.因此，这样的进程经常处于可运行状态，但通常都是运行短短的一会儿，因为它在等待更多的I/O请求时最后总会阻塞（这里所说的I/O是指任何类型的可阻塞资源，比如键盘输入，或者是网络I/O），多数用户图形界面程序（GUI）都属于I/O密集型，即便它从不读取或者写入磁盘，他们也会在多数时间里都在等待来自鼠标或者键盘的用户交互操作。

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

      调度策略通常需要在进程迅速响应和最大系统利用率之间寻求平衡。为了满足这个需求，调度程序通常采用一套非常复杂的算法来决定最值得运行的进程投入运行，但是它往往并不保证低优先级进程会被公平对待。Unix系统的调度程序更倾向于I/O消耗型程序，以便于提供更好的程序相应速度。Linux为了保证交互式应用程序和桌面系统的性能，所以对进程的响应做了优化（缩短相应时间），更倾向于优先调度I/O消耗性进程。虽然如此，但在下面你会看到，调度也并未忽略处理器消耗性的进程。

进程优先级

      调度算法中最基本的一类就是基于优先级的调度。这是一种根据进程的价值和对处理器时间的需求来对进程分级的想法。通常做法是（并未被Linux系统完全采用）有限极高的进程先运行，低的后运行，相同优先级的进程按照轮转的方式进行调度（一个接一个，重复的进行）。在某些系统中，优先级高的进程使用的时间片也越长。调度程序总是选择时间片未用尽而且优先级最高的进程运行。用户和系统都可以通过设置进程优先级来影响系统的调度。

时间片

          时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。调度策略必须规定一个默认的时间片，但这并不是件简单的事。时间片过长会导致系统对交互的影响表现欠佳。让人觉得系统无法并发执行应用程序；时间片过短会明显增加进程切换带来的处理器耗时，因为肯定会有相当一部分系统时间用在切换进程上，而这些进程能够用来运行的时间片却很短。此外 I/O消耗型和处理器消耗型进程之间的矛盾就体现出来了：I/O消耗型不需要长的时间片，而处理器消耗型的进程则希望越长越好。

        Linux系统是抢占式的，当一个进程进入可运行状态，它就被准许投入运行，在多数操作系统中，是否要将一个进程立刻投入运行（也就是抢占当前进程），是完全由进程优先级和是否有时间片决定的。而在Linux中使用新的CFS调度器，其抢占时机取决于新的可运行程序消耗了多少处理器使用比率。如果消耗的使用比率比当前进程小，则新进程立刻投入运行，抢占当前进程，否则，将推迟运行。

调度策略的活动

         想象下面这样一个系统，它拥有两个可运行的进程：一个文字编辑程序和一个视频编码程序。文字编辑程序显然是I/O消耗型，视频编码是处理器消耗型。在上述场景中，一旦文本编辑器被唤醒CFS注意到给他的处理器使用的比率是50%，但实际上使用的少之又少。特别是CFS发现文本编辑器比视频编码器运行的时间短的多。这种情况下，为了兑现让所有进程能公平分享处理器的承诺，它会立即抢占视频解码程序，让文本编辑器投入运行。文本编辑器运行后，立即处理用户的点击输入后，又一次进入睡眠等待用户下一次输入，因为文本编辑器并没有消费掉承诺给它的50%处理器使用率，因此情况依旧，CFS总是会毫不犹豫的让文本编辑器在需要的时候被投入运行，而让视频处理程序只能在剩下的时刻运行。

Linux调度算法

       Linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类（scheduler classes），它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，基础的调度器代码定义在kernel/sched.c文件中，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那一个程序。

       传统的Unix系统调度过程中有两个通用概念：进程优先级和时间片。时间片是指进程运行多少时间，进程一旦启动就会有一个默认的时间片。具有更高优先级的进程将运行得更频繁，而且也会被赋予更多时间片。这种调度存在一个根本问题--分配绝对时间片引发的固定的切换频率，给公平性造成了很大变数。CFS采用的方法是对时间片分配方式进行根本性的重新设计（就进程调度而言）：完全摒弃时间片而分配给进程一个处理器使用比重。这种方式CFS确保了进程调度中有恒定的公平性，而将切换频率置于不断变动中。

公平调度

       完全公平调度(CFS)是一个针对普通进程的调度类，在Linux中称为SCHED_NORMAL，CFS算法实现定义在kernal/sched_fair.c中。CFS的出发点基于一个简单的理念：进程调度的效果应如同系统具备一个理想中的完美多任务处理器。在这种系统中，每个进程将能获得1/n的处理器时间，n是指可运行进程的数量。我们可以调度给每个进程无限小的时间周期，所以任何可测量周期内，我们给予n个进程中每个进程同样多的运行时间。如果进程运行非常短的时间，CFS充分考虑到了这将带来额外的消耗，现实中首先要考虑系统性能不受损失。CFS的做法是允许每一个进程运行一段时间，循环轮询、选择运行最少进程作为下一个运行进程，而不再采用时间片的做法了，CFS在所有课运行进程总数基础上计算出下一个运行进程应该运行多久，而不是依靠nice值来计算时间片。

      CFS不是完美的公平，它只是近乎完美的多任务，但是在它的确在多进程环境下，降低了调度延迟带来的不公平性。

公平调度实现

     公平调度实现由四部分组成：时间记账、进程选择、调度器入口、睡眠和唤醒。

     时间记账：所有的调度器对进程运行时间做记账。每次系统时钟节拍发生时，时间片就被减少一个节拍周期。当一个进程时间片被减少到0时，它就会被另一个尚未减到0的时间片可运行进程抢占。vruntime变量存放进程的虚拟运行时间。

      进程选择：CFS调度算法核心是选择具有最小vruntime的任务，CFS使用红黑树来组织可运行进程，并利用其迅速找到最小vruntime值的进程。

     调度器入口：进程调度的主要入口点是函数schedule()，它选择哪个进程可以执行，何时将其投入运行。

     睡眠和唤醒：睡眠的进程处于一个特殊的不可执行状态，这个状态非常重要，如果没有这个状态，调度程序可能会调度出一个本不愿意执行的进程。内核会将标记为修炼状态的进程从红黑树中移除。唤醒通过wake_up()进行，被唤醒的进程会被重新放入红黑树中。

抢占和上下文切换

        上下文切换，也就是从一个可执行进程切换到另一个可执行进程。内核提供了一个need_resched标志来表明是否需要重新执行一次调度。每个进程都包含一个need_resched标志，这是因为访问一个进程描述符的数值要比访问一个全局变量快。

用户抢占

      内核机枪返回用户空间的时候，如果need_resched标志被设置，会导致schedule()被调用，此时就会发生用户抢占。在内核返回用户空间的时候，它知道自己是安全的，因为既然它可以继续执行当前进程，那么它当然可以再去选择一个新的进程去执行。所以，内核无论是在中断处理程序还是在系统调用返回，都会检查need_resched标志。如果它被设置了，那么，内核会选择一个其他(更合适)进程投入运行。

      简而言之，用户前瞻在以下情况是产生：

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

内核抢占

        Linux完整地支持内核抢占。在不支持内核抢占的内核中，内核代码可以一直执行，到它完成为止。也就是说，调度程序没有办法在一个内核级的任务正在执行的时候重新调度--内核中的各任务是以协作的方式调度的，不具备抢占性。Linux在2.6版本的内核中引入了抢占机制，只要重新调度是安全的，内核就可以在任何时候抢占正在执行的任务。

        什么时候重新调度是安全的呢？只要没有持有锁，内核就可以进行抢占。锁时非抢占区的标志。由于内核是支持SMP的，所以，如果没有持有锁，正在执行的代码就是可以重新导入的，也就是可以抢占的。

        内核抢占会发生在：

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

实时调度策略

        Linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR。而普通的、非实时调度策略是SCHED_NORMAL.这些实时调度策略并不被完全公平调度器来管理而是被一个特殊的实时调度器管理。

        SCHED_FIFO实现了一个简单的、先入先出的调度算法：它不适用时间片。处于可运行状态的SCHED_FIFO级进程会比任何SCHED_NORMAL级的进程都先得到调度。一旦一个SCHED_FIFO级进程处于可执行状态，就会一直执行，知道它自己受阻塞或显示地释放处理器为止，它不基于时间片，可以一直执行下去。如果有两个或更多的同优先级的SCHED_FIFO级进程，他们会轮流执行，但是依然只有在他们愿意让出处理器时才会退出。

       SCHED_FIFO和SCHED_RR大体相同，只是SCHED_RR级的进程在耗尽实现分配给它的时间后就不能再继续执行了。也就是说，SCHED_RR是带有时间片的SCHED_FIFO。

      Linux通过sched_yield系统调用，提供了一种让进程显示地将处理器时间让给其他等待执行进程的机制。它是通过将进程从活动队列中移到过期队列中实现的。这样能确保一段时间不会再执行了。由于实时进程不会过期，所以属于例外。