linux内核--进程调度

      调度程是内核的组成部分，它负责选择下一个要运行的进程。进程调度程序可看作在可运行态进程之间分配有限的处理器时间的内核子系统。Linux是一个多任务操作系统，只有通过调度程序的合理调度，系统资源才能最大限制的发挥作用，多进程才会有并发执行的效果。

       多任务操作系统分为非抢占式多任务和抢占式多任务。linux是一个抢占式的多任务操作系统，由调度程序决定什么时候停止一个进程的运行以便其它进程能够得到执行机会，这个强制的挂起动作就叫做抢占。进程在被抢占之前能够运行的时间是预先设置好的，叫进程的时间片。时间片实际是分配给每个可运行的进程的处理器时间段。而在非抢占式多任务模式下，除非进程自己主动停止，否则它会一直执运行。

策略

      策略决定调度程序在何时让什么进程运行。进程可以分为I/O消耗型和处理器消耗型。前者指进程的大部分时间用来提交I/O请求或等待I/O请求。因此，这样的进程经常处理可运行状态，但通常都是运行短短一会儿，因为它在等待更多的I/O请求时最后总会阻塞。相反，处理消耗型进程把时间大多用在执行代码上。除非被抢占，否则它们通常一直不停地运行，因为它们没有太多的I/O需求。对于这类处理消耗型的进程，调度策略是尽量降低它们的运行频率，对于它们而言，延长其运行时间会更合适些。

      调度策略通常在两个矛盾的目标中间寻找平衡：进程响应迅速（响应时间短）和最大系统利用率（高吞吐量）。调度算法中最基本的一类就是基于优先级的调度。优先级高的先运行，低的后运行，相同优先级的进程按轮转方式进去调 度（一个接一个，重复进行）。在包括Linux在内的某些操作系统中，优先级高的进程使用的时间片也较长。调度程序总是选择时间片未用尽且优先级高的进程运行。用户和系统都可以通过设置进程的优先级来影响系统的调度。

      Linux根据以上思想实现了一种基于动态优先级的调度方法。一开始，该方法先设置基本的优先级，然而它允许调度程序根据需要来加、减优先级。举个例子，如果一个进程在I/O等待上耗费的时候多于其运行时间，那么该进程显属于I/O消耗型进程。它的优先级会被动态提高。相反，如果一个进程的全部时间片一下就被耗尽，那么该进程属于处理器消耗型进程，它的优先级会被动态降低。

      时间片是一个数值，它表时进程在被抢占前所能持续运行的时间。调 度策略必须规定一个默认的时间片，时间片过长会导致系统对交互的响应表现欠佳；让人觉得系统无法并发执行应用程序；时间片过短会明显增大进程切换带来的消耗，因为肯定会有相当一部分系统时间用在进程切换上，而这些进程能够用来运行的时间片却很短。当一个进程的时间片耗尽时，就认为这个进程到期了。

       linux系统是抢占式的，当一个进程进入task_running状态，内核会检查它的优先级是否高于当前正在执行的进程。如果是这样，调度程序会被唤醒，抢占当前正在运行的进程并运行新的可运行进程。此外，当一个进程的时间片变为0时，它会被抢占，调度程序被响醒以选择一个新的进程。

调度程序的可执行队列

      调度程序中最基本的数据结构是运行队列，可执行队列是给处理器上的可执行进程的链表，每个处理器一个。每个可投入执行的进程都惟一归属于一个可执行队列。每个运行队列都有两个优先级数组，一个活跃的和一个过期的。优先级数组使可运行处理器的每一种优先级都包含一个相应的队列，而这些队列包含对应优先级上的可执行进程链表。

       许多操作系统在所有进程的时间片用完时，都采用一种显式的方法来重新计算每个进程的时间片。当一个进程的时间片耗尽时，它会被移至过期数组，但在此之前，时间片已经给它重新计算好了。

       选定一个进程并切换到它去执行是通过schedule()函数来实现的。当内核想要休眠时，会直接调用函数，另外，如果有哪个进程被抢占，那么该函数也会被唤起执行。schedule()函数独立于每一个处理器运行。因此，每个处理器对下一次该运行哪个进程做出自己的判断。

       调度程序通过进程的休眠时间来判断一个进程到底是I/O消耗型还是处理消耗型。为了支持这种推断机制，linux记录了一个进程用于休眠和用于执行的时间，这个值存在于task_struct的sleep_avg域中。

       休眠（被阻塞）的进程处理一个特殊的不可执行状态。进程休眠有各种原因，但肯定是为了等待一些事件。事件可能是一段时间、从文件I/O读更多数据，或者是某个硬件事件。休眠的一个常见原因就是文件I/O--如进程对一个文件执行了read()操作，而这需要从磁盘里读取。还有，进程在获取键盘输入的时候也需要等待。无论哪种情况，内核的操作都相同：进程把它自己标记为休眠状态，把自己从可执行队列移出，放入等待队列，然后调用schedule()选择和执行一个其它进程。唤醒的过程刚好相反：进程被设置为可执行状态，然后再从等待队列中移到可执行队列。

休眠和唤醒状态图

负载平衡程序

linux的调度程序为对称多下得系统的每个处理器准备了单独的可执行队列和锁，也就是说，每个处理器拥有一个自己的进程链表，而它只对属于自己的这些进程进行调度操作。出地效率考虑，整个调度系统从每个处理器来看都是独立的。如果出现一个处理器的队列上有5个进程，而另外一个处理器的队列上只有1个进程，该怎么办呢？这些问题由负载平衡程序解决，它负责保证可执行队列之间的负载平衡状态。如果发现了不均衡，就会把相对繁忙的队列中的进程抽到当前的可执行队列中来。理想状态下，每个队列上的进程数目应该相等。在单处理器系统中，不会执行负载均衡程序。

抢占和上下文切换

      上下文切换，也就是从一个可执行进程切换到另一个可执行进程。每当一个新的进程被选出来准备投入运行的时候，schedule()就会调用上下文切换功能函数context_switch()。

实时

linux提供了两种实时调度策略:SCHED_FIFO和SCHED_RR。而普通的、非实时的调度策略是SCHED_NORMAL。SCHED_FIFO实现了一种简单的、先入先出的调度算法，它不使用时间片。SCHED_FIFO级的进程比任何SCHED_NORMAL级的进程都先得到调度。一旦一个SCHED_FIFO级进程处于可执行状态，应该会一直执行，直到它自己受阻塞或显示的释放处理器为止，它不基于时间片，可以一直执行下去。只有较高优先级的SCHED_FIFO或SCHED_RR任务才能抢占SCHED_FIFO任务。如果有两个或者更多的SCHED_FIFO进程，它们会轮流执行。SCHED_RR与SCHED_FIFO大体相同，只是SCHED_RR级的进程在耗尽事先分配给它的时间后就不能再接着执行了。这两种实时算法实现的都是静态优先级。