Linux进程调度的运行队列

运行队列

当Linux内核要寻找一个新的进程在CPU上运行时，必须只考虑处于可运行状态的进程，（即在TASK_RUNNING状态的进程），因为扫描整个进程链表是相当低效的，所以引入了可运行状态进程的双向循环链表，也叫运行队列（runqueue）。

运行队列容纳了系统中所有可以运行的进程，它是一个双向循环队列

该队列通过task_struct结构中的两个指针run_list链表来维持。队列的标志有两个：一个是“空进程”idle_task、一个是队列的长度。

有两个特殊的进程永远在运行队列中待着：当前进程和空进程。前面我们讨论过，当前进程就是由cureent指针所指向的进程，也就是当前运行着的进程，但是请注意，current指针在调度过程中（调度程序执行时）是没有意义的，为什么这么说呢？调度前，当前进程正在运行，当出现某种调度时机引发了进程调度，先前运行着的进程处于什么状态是不可知的，多数情况下处于等待状态，所以这时候current是没有意义的，http://Ubuntuone.cn/直到调度程序选定某个进程投入运行后，current才真正指向了当前运行进程；空进程是个比较特殊的进程，只有系统中没有进程可运行时它才会被执行，Linux将它看作运行队列的头，当调度程序遍历运行队列，是从idle_task开始、至idle_task结束的，在调度程序运行过程中，允许队列中加入新出现的可运行进程，新出现的可运行进程插入到队尾，这样的好处是不会影响到调度程序所要遍历的队列成员，可见，idle_task是运行队列很重要的标志。

另一个重要标志是队列长度，也就是系统中处于可运行状态（TASK_RUNNING）的进程数目，用全局整型变量nr_running表示，在/kernel/fork.c中定义如下：

int nr_running=1；

若 nr_running为0，就表示队列中只有空进程。在这里要说明一下：若nr_running为0，则系统中的当前进程和空进程就是同一个进程。但是Linux会充分利用CPU而尽量避免出现这种情况。