Linux实时性分析-schedule-调度器

l SCHED_FIFO 

这是先进先出的实时进程。当调度程序把CPU分配给进程的时候，它把该进程描述符保留在运行队列链表的当前位置。如果没有其它可运行的更高优先级实时进程，进程就继续使用CPU，想用多久就用多久，即使还有其他具有相同优先级的实时进程处于可运行状态。

l SCHED_RR  

时间片轮转的实时进程。当调度程序把CPU分配给进程的时候，它把该进程的描述符放在运行队列链表的末尾。这种策略保证对所有具有相同优先级的SCHED_RR实时进程公平地分配CPU时间。

l SCHED_NORMAL 

普通的分时进程。当进程使用完成CPU时间片后，就会被退出活动队列，而加入到过期队列。只有当过期队列变成活动队列时，普通的时分进程才有机会获得CPU使用权。

在Linux，进程是分优先级的。进程调度器在调度进程时，会先选择最高优先级的进程运行。也是说，高优先级的进程会获得更多的运行机会。Linux-2.6进程的优先级分为0 ~ 139级，0级为最高优先级，139级为最低先级。在实时进程的优先级是在0 ~ 99之间。

进程的优先级可以用sched_setscheduler系统调用设置进程的静态优先级。

在进程调度时，选择进程是根据进程的动态优先级。SCHED_NORMAL进程的动态优先级是根据其静态优先级和进程的运行情况决定。也是说，SCHED_NORMAL进程的动态优先级会在运行时动态改变。使用sched_setscheduler设置SCHED_NORMAL进程的优先级后，在初始时，进程的动态优先级等于其静态优先级。

使用sched_setscheduler设置SCHED_RR或SCHED_FIFO的优先级后，其动态优级等于其静态优先级。在进程运行的过程中，其动态优先级不会发生改变。

我们都知道Linux进程的运行都基于时间片的。每个进程分一个时间片。当进程占用CPU并用完时间片后，调度程序会重设其时间片，然后调度下一个进程使用CPU。而进程的时间片设置与其静态优先级密切相关，一般能成正比关系。

调度程序选择进程使用CPU时，只在活动队列中找。只有活动队列中没有了任何进程，才把过期队列变成活动队列，原活动队列变成过期队列。空集用于接收过期进程。

在SMP系统中，每个CPU都独立维持一个运行队列。

当SCHED_RR或SCHED_NORMAL进程获得CPU使用权时，需要不断递减其时间片。下面就介绍在标准Linux下是如何递减进程的时间片。

  当我们使用request_irq在n中断号安装中断处理函数时，实际上是生成一个irqaction对象，该对象的中断服务例程指针指向我们的中断处理函数。然后把irqaction对象插到irq_desc数组第n个元素的action指向（irq_desc[n].action）的irqaction链表中的未尾。

中断产生后，内核代码将由中断向量导航到do_IRQ函数。在do_IRQ 调用函数__do_IRQ，并传入中断号n作为参数。在__do_IRQ函数把irq_desc数组的第n个元素action指向的中断处理函数全部启动，包括我们之前注册的中断处理函数，如 REF _Ref206988749 \h 图下所示。由此可知，在Linux实现了可以在同一个中断号中安装多个中断处理函数。也是说实现了中断复用。

现在我们再分析一下Linux中断延迟。

所谓中断延迟是指从外部中断信号输入到目的中断处理函数开始执行第一条指令所经历的时间。从本小节上文中，我们知道：在Linux中断向量并不是直接指中断处理函数。这会对中断延迟会造成一定的影响。我们现在假设在理想情况下（中断没有被禁用，中断处理时没有被嵌套，中断号没有被复用）分析Linux的中断延迟。

从中断信号输入到中断处理函数的第一条指令执行，所经历的时间可以分为三段：从中断信号输入到do_IRQ函数的开始执行；从do_IRQ函数开始执行到找到目标irq_desc_t对象；到中断处理函数的第一条指令开始执行。我们分别对这三段时间加以分析。

由于中断向量是直接指向do_IRQ函数的，所以从中断信号输入到do_IRQ函数开始执行第一条指令的时间固定。这时，内核代码以中断号作为参数，调用__do_IRQ函数。在__do_IRQ函数，以中断号作为下标直接定位到目标中断处理函数对应的irq_desc_t对象。这段时间也是固定的。而这时，在该irq_desc_t对象下的action元素直接向我们中断处理函数所在的irqaction对象。也是在理想情况下Linux的中断延迟是固定的。

然而在Linux的外部中断是不分优先级的，在执行中断处理程序时，也可能会被其它中断所嵌套而造成延缓，在网络繁忙而CPU主频不高的情况下尤其明显。另外在内核代码是有些执行点关中断的，这也会造成中断延迟的不确定性。

Linux的进程调度器的主函数是schedule。在shedule函数中有两个重要变量：prev是当前正在使用CPU的进程；next是下一个将要使用CPU的进程。调度程序的一个很大的任务就是找到next。

schedule的主要工作可以分为两步。

l 找到next

1、schedule()检查prev的状态。如果不是可运行状态，而且它没有在内核态被抢占，就应该从运行队列删除prev进程。不过，如果它是非阻塞挂起信号，而且状态为TASH_INTERRUPTIBLE，函数就把该进程状态设置为TASK_RUNNING，并将它插入运行队列。这个操作与把处理器分配给prev是不同的，它只是给prev一次选中执行的机会。在内核抢占的情况下，该步不会被执行。

2、检查本地运行队列中是否有进程。如果没有则在其它CPU的运行队列中迁移一部份进程过来。如果在单CPU系统或在其它CPU的运行队列中迁移进程失败，next只能选择swapper进程，然后马上跳去switch_tasks执行进程切换。

3、若本地运行队列中有进程，但没有活动进程队列为空集。也就是说运行队列中的进程都在过期进程队列中。这时把活动进程队列改为过期进程队列，把原过期进程队列改为活动进程队列。空集用于接收过期进程。

4、现在可以在活动进程队列中搜索一个可运行进程了。首先，schedule()搜索活动进程队列的集合位掩码的第一个非0位。当对应的优先级链表不空时，就把位掩码的相应位置1。因此，第一个非0位下标对应包含最佳运行进程的链表。随后，返回该链表的第一个进程。值得一提的是，在Linux-2.6下这步能很短的固定的时间内完成。

这时next找到了。

5、检查next是否不是实时进程以及是否从TASK_INTERRUPTIBLE或TASK_STOPPED状态被唤醒。如果这两个条件都满足，重新计算其动态优先级。然后把next从原来的优先级撒离插入到新的优先级中。

也是说，实时进程是不会改变其优先级的。

l 切换进程

找到next后，就可以实施进程切换了。

1、把next的进程描述符第一部分字段的内容装入硬件高速缓存。

2、清除prev的TIF_NEED_RESCHED的标志。

3、设置prev的进程切换时刻。

4、重新计算并设置prev的平均睡眠时间。

5、如果prev != next，切换prev和next硬件上下文。

这时，CPU已经开始执行next进程了。

在Linux-2.6，schedule函数在寻找next时，其算法效率得到极大的提高，时间复杂达到O(1)。而schedule函数性能好坏最关键也就这里。整体来说，schedule的时间复杂度为O(1)。

现在我们分析这种情况：一个实时进程为了等待外部事件而进入休眠；当外部事件发生时产生中断而触发中断处理函数，并在中断处理函数中唤醒实时进程；当实时进程被唤醒后，占抢当前进程，获得CPU使用权，响应外部事件。下面我们看看当内核遇到这种情况时，内部是如何动作的，并由此考察标准Linux的抢占延迟。

假设实时进程是next，当前进程是current。

在next进程的内核态中，为了等待外部事件调用wait_event_interruptible使进程进入休眠，这时next进程就被加入到等待队列。调度程序则调度其它进程使用CPU，该进程暂时称为current。

当外部事件发生时，产生了中断信号，触发了中断处理函数。在中断处理函数中，调用wake_up_interruptible把next唤醒。在调用wake_up_interruptible函数时，传入参数是等待队列。wake_up_interruptible函数会试图唤醒等待队列中的所有进程。为了方便起见，这里假设等待队列中只有一个正处于等待状态的进程next。在wake_up_interruptible会调用try_to_wake_up试图把等待进程next唤醒。

在单CPU系统中，try_to_wakey_up把next插入到本地运行队列中。若next的优先级比当前进程current进程优先级高，则调用set_tsk_need_resched函数设置current进程内核堆栈中的TIF_NEED_RESCHED标志。该标志会强制把当前进程current调度出去。然后把next的运行状态改为TASK_RUNNING。也是说，当next被唤醒时，若next的优先级比current的优先级高，就允许抢占当前current进程；否则仅是把next插入运列队列和把运行状态改为TASK_RUNNING。

正如前面的所述，中断发生后，在do_IRQ中断服务函数调用__do_IRQ函数完成后会调用irq_exit函数作后步处理。irq_exit函数退出后，do_IRQ函数也退出。这是内核执行路径进入一段汇编代码。这里有一个内核抢占检查点，在x86平台该检查点的代码如下程序清单所示。

如果当前进程current的TIF_NEED_RESCHED标志为0，说明没有需要切换的进程，因此，程序跳转到restore_all处。如果需要进行进程切换，就调用preempt_schedule_irq函数。在preempt_shedule_irq函数中，关掉本地中断和内核抢占，然后调用schedule()函数实施调度。如果next在运行进行队列中优先级最高且在其优先级中唯一，next进程获得CPU使用权。

内核抢占的情形大致就是这样。其中，从实时程序被唤醒到该实时程序真正开始使用CPU的这一段时间就是抢占延迟。上述情形也告诉我们，只有内核在运行中断/异常程序时才会发生内核抢占。当然若中断被禁止或内核抢占被禁止，都不可能发生内核抢占。

       preempt_disable是递减内核抢占标志。若该标志被递减到0内核抢占启用。

       preempt_enable_no_resched是递增内核抢占标志。若该标志被递增到大于0内核抢占禁用。

preempt_enable不但递减内核抢占标志。它还在递减完成后，检查TIF_NEED_RESCHED标志是否被设置。若被设置，会检查内核抢占标志是否为0及是否允许中断。如果这些条件都为真，则调用schedule函数实施进程调度。当启用可延迟函数的时候，preempt_enable会被执行。

由此可见，内核抢占还会发生在启用可延迟函数的时候。

我们考察一下在标准Linux-2.6的抢占延迟的情况。

外部事件发生后，产生中断信号。这时由中断向量指向的do_IRQ 会马上被执行。在do_IRQ函数会执行__do_IRQ函数，并由此去执行我们的中断处理函数。在中断处理函数中，唤醒实时进程。这时，抢占延时开始计时。执行完成中断处理函数后，__do_IRQ函数退出，转而执行exit_IRQ函数。在exit_irq函数中，会检查系统中是否有挂起的软中断。如果有挂起的软中断，就执行挂起的软中断处理函数。软中断处理完成后，exit_irq退出，do_IRQ函数也退出。由于挂起软中断的数目不确定（虽然只执行小于10个）以及软中断处理函数的运行时间不确定，exit_irq函数的运行时间不可预测。然后内核执行路径进入一段汇编代码中，调用schedule函数实施调度。由于schedule的时间复杂为O(1)，而且关中断和禁用抢占，schedule的执行时间可以确定。若实时进程的优先级为最高，实时进程就会被调度执行。这时，抢占延时计时结束。

也是说，在do_IRQ函数中，由于执行完中断处理函数后就处理软中断，而造成抢占延迟的不确定。还有，在处理软中断时，系统是不关中断的，而且处理软中断的时间比较长，被其它硬件中断嵌套的机会比大。这进一步影响了标准Linux内核抢占的实时性。