调度策略

Linux的调度基于分时(time sharing)技术：多个进程以“时间多路复用”方式运行，因为CPU的时间被分成“片(slice)”，给每个可运行进程一片。当然，单处理器在任何给定的时刻只能运行一个进程。如果当前运行的时间片或时限(quantum)到期时，该进程还没有运行完毕，进程切换就可以发生。分时依赖于定时中断，因此对进程是透明。不需要在程序中插入额外的代码来保证CPU分时。

分类

传统上把进程分类为“I/O受限”或“CPU受限”，前者频繁使用I/O设备，并花费很多时间等待I/O操作的完成；后者则需要大量CPU时间的数值计算应用程序。

另一种分类法把进程区分为三类：

交互式进程(interactive process)

这些进程经常与用户进行交互，因此，要花很多时间等待键盘和鼠标操作。当接受了输入后，进程必须被很快唤醒，否则用户将发行系统反应迟钝。

批处理进程(batch process)

这些进程不必与用户交互，因此经常在后台运行。因为这样的进程不必被很快地响应，因此常受到调度程序慢待。

实时进程(read-time process)

这些进程有很强的调度需要。这样的进程决不会被低优先级的进程阻塞，它们应该有一个短的响应时间

Linux进程是抢占式的。如果进程进入TASK_RUNNING状态，内核检查它的动态优先级是否大于当前正在运行进程的优先级。如果是，current的执行被中断，并调用调度程序选择另一个进程运行。当然，进程在它的时间片到期时也可以被抢占。此时，当前进程thread_info结构中的IF_NEDD_RESCHED标志被设置，以便时钟中断处理程序终止时调度程序被调用。

调度算法

SCHED_FIFO

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

SCHED_RR

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

SCHED_NORMAL

普通的分时进程

调度算法根据进程是普通进程还是实时进程而有很大不同

普通进程的调度

每个普通进程都有它自己的静态优先级，调度程序使用静态优先级来估价系统中这个进程与其他普通进程之间调度的程度。内核用100(最高优先级)到139(最低优先级)的数表示普通进程的静态优先级。

静态优先级本质上决定了进程的基本时间片，即进程用完了以前的时间片时，系统分配给进程的时间片长度。静态优先级和基本时间片的关系用下列公式确定

              |---  (140-静态优先级) * 20    若静态优先级<120

基本时间片(ms) = 

              |---  (140-静态优先级) * 5     若静态优先级>=120

普通进程优先级的典型值

说明           静态优先级       nice值          基本时间片     睡眠时间的极限值

最高静态优先级   100            -20             800ms        299ms

高静态优先级     110            -10             600ms        499ms

缺省静态优先级   120            0               100ms        799ms

低静态优先级     130            +10             50ms         999ms

最低静态优先级   140            +19              5ms         1199ms     

普通进程除了静态优先级，还有动态优先级，其值的范围100~139。动态优先级是调度程序在选择新进程来运行的时候使用的数。它与静态优先级的关系如下：

动态优先级 = max(100, min(静态优先级-bonus+5,139))

bonus是范围从0~10的值，值小于5表示降低动态优先级以示惩罚，值大于5表示增加动态优先级以示奖赏。bonus的值依赖于进程过去的情况，说得更准确一些，是与进程的平均睡眠时间相关。

活动和过期进程

即使具有较高静态优先级的普通进程获得了较大的CPU时间片，也不应该使静态优先级较低的进程无法运行。为了避免进程饥饿，当一个进程用它的时间片时，它应该被还没有用完时间片的低优先级进程取代。为了实现这种机制，调度程序维持两个不相交的可运行进程的集合。

活动进程

这些进程还没有用完它们的时间片，因此允许它们运行

过期进程

这些可运行进程已经用完了它们的时间片，并因此被禁止运行，直到所有活动进程都过期

实时进程的调度

每个实时进程都与一个实时优先级有关，实时进程优先级是一个范围从1~99的值。调度程序总是让优先级高的进程运行，换句话说，实时进程运行的过程中，禁止低优先级进程的执行。与普通进程相反，实时进程总是被当成活动进程。

如果几个可运行的实时进程具有相同的最高优先级，那么调度程序选择第一个出现在本地CPU的运行队列相应链表中的进程。

只有在下述事件之一发生时，实时进程才会被另外一个进程取代：

1、进程被另外一个具有更高实时优先级的实时进程抢占

2、进程执行了阻塞操作并进入睡眠

3、进程停止

4、进程通过调用系统调用sched_yield()自愿放弃CPU

5、进程是基于时间片轮转的实时进程，而且用完了它的实时进程

当系统调用nice()和setpriority()用于基于时间片轮转的实时进程是，不改变实时进程的优先级而会改变其基本时间片的长度。实际上，基于时间片轮转的实时进程的基本时间片的长度与实时进程的优先级无关，而依赖于进程的静态优先级。