Linux內(nèi)核中大量使用了隊(duì)列，這里僅列舉它在進(jìn)程調(diào)度中的幾處應(yīng)用。Linux內(nèi)核中的隊(duì)列是以雙鏈表的形式連接起來的，include/linux/list.h中定義了隊(duì)列并提供了一些接口，詳細(xì)的介紹可以參考**[1]**中的附錄。

Linux中的進(jìn)程有如下幾個(gè)主要狀態(tài)：

進(jìn)程狀態(tài)

說明

TASK_RUNNING

進(jìn)程正在運(yùn)行或?qū)⒁贿\(yùn)行。

TASK_INTERRUPTIBLE

進(jìn)程正在睡眠，等待某個(gè)條件的完成。

TASK_UNINTERRUPTIBLE

深度睡眠，不會(huì)被信號(hào)打擾。

TASK_STOPPED

進(jìn)程運(yùn)行被停止。

TASK_TRACED

進(jìn)程被調(diào)試程序停止，被另一個(gè)進(jìn)程跟蹤。

兩個(gè)額外的狀態(tài)是EXIT_ZOMBIE和EXIT_DEAD，表示進(jìn)程處于僵死狀態(tài)還是真正死亡。處于僵死狀態(tài)的進(jìn)程會(huì)等待其父進(jìn)程的收養(yǎng)(否則就會(huì)被init進(jìn)程收養(yǎng))，而真正死亡的進(jìn)程會(huì)被直接刪除。

狀態(tài)為TASK_RUNNING的進(jìn)程都會(huì)被放入運(yùn)行隊(duì)列(runqueue)中，這是通過task_struct(定義在include/linux/sched.h)中的run_list成員來鏈接的。不過，為了讓內(nèi)核每次都能選取優(yōu)先級(jí)最合適的進(jìn)程，Linux為每個(gè)優(yōu)先級(jí)構(gòu)建了一個(gè)queue。這是通過struct prio_array來實(shí)現(xiàn)的，struct prio_array的定義在kernel/sched.c，大致如下：

struct prio_array

int nr_active;

unsigned long bitmap[BITMAP_SIZE];

struct list_head queue[MAX_PRIO];

};

queue成員就是隊(duì)列數(shù)組。每個(gè)CPU有各自的runqueue，每一個(gè)runqueue又有包含兩個(gè)prio_array，一個(gè)是活動(dòng)隊(duì)列，一個(gè)是時(shí)間片耗盡的隊(duì)列。當(dāng)運(yùn)行隊(duì)列空時(shí)，內(nèi)核便會(huì)交換兩個(gè)隊(duì)列的指針，原來的耗盡隊(duì)列就成了新的活動(dòng)隊(duì)列！這和prio_array中的bitmap是決定調(diào)度算法為O(1)的關(guān)鍵。

狀態(tài)為TASK_STOPPED，EXIT_ZOMBIE或EXIT_DEAD的進(jìn)程不會(huì)被放入專門的隊(duì)列中，它們直接通過pid或者通過父進(jìn)程的孩子隊(duì)列來訪問。

TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE狀態(tài)的進(jìn)程會(huì)被放入等待隊(duì)列。不同的是，每個(gè)等待事件都會(huì)有一個(gè)等待隊(duì)列，該隊(duì)列中的進(jìn)程等待同一事件的完成。(“事件”一個(gè)動(dòng)態(tài)的過程，不好通過具體的結(jié)構(gòu)來定義一個(gè)“事件”。這里等待一個(gè)事件就是查看某個(gè)條件是否為真，比如某個(gè)標(biāo)志變量是否為真。)wait_queue_head_t的定義在include/linux/wait.h中，如下：

typedef struct _ _wait_queue_head {

spinlock_t lock;

struct list_head task_list;

}wait_queue_head_t;

wait_queue_t的定義如下：

typedef struct _ _wait_queue {

unsigned int flags;

struct task_struct * task;

wait_queue_func_t func;

struct list_head task_list;

}wait_queue_t;

進(jìn)入等待狀態(tài)的接口有兩類：

prepare_to_wait*()/finish_wait()

wait_event*()

其實(shí)wait_event*()內(nèi)部也是調(diào)用prepare_to_wait*()，把它放入一個(gè)循環(huán)中。而且wait_event*()在事件完成時(shí)會(huì)自動(dòng)調(diào)用finish_wait()。決定使用哪個(gè)要看情況而定。(sleep_on*()是遺棄的接口，現(xiàn)在已經(jīng)不再使用，雖然還支持。)等待隊(duì)列中的進(jìn)程有兩種，一種是exclusive的進(jìn)程，另一種是nonexclusive的進(jìn)程。所謂exclusive是指喚醒的進(jìn)程等待的資源是互斥的，每次只喚醒一個(gè)(喚醒多個(gè)也可以，不過最后還是只有一個(gè)會(huì)被喚醒，其余的又被重新添加到等待隊(duì)列中，這樣效率會(huì)大打折扣)。一般，等待函數(shù)會(huì)把進(jìn)程設(shè)為nonexclusive和uninterruptible，帶“interruptible”的會(huì)專門指定狀態(tài)為interruptible；而帶“timeout”的會(huì)在超時(shí)后退出，因?yàn)樗鼤?huì)調(diào)用schedule_timeout()；帶“exclusive”的則會(huì)把進(jìn)程設(shè)為exclusive。

喚醒的接口雖然只有wake_up*()，但它內(nèi)部也分成好幾種。帶“interruptible”的喚醒函數(shù)只會(huì)喚醒狀態(tài)是TASK_INTERRUPTIBLE的進(jìn)程，而不帶的則會(huì)喚醒TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE的進(jìn)程；所有喚醒函數(shù)都會(huì)把等待同一事件的nonexclusive進(jìn)程全部喚醒，或者把其中一個(gè)exclusive的進(jìn)程喚醒；而帶“nr”的則會(huì)喚醒指定個(gè)數(shù)的exclusive的進(jìn)程，帶“all”的會(huì)把全部exclusive進(jìn)程喚醒。帶“sync”會(huì)忽略優(yōu)先級(jí)的檢查，高優(yōu)先級(jí)的進(jìn)程可能會(huì)被延遲。最后，持有自旋鎖時(shí)只能調(diào)用wait_up_locked()。

進(jìn)程管理是Linux內(nèi)核中最關(guān)鍵的部分，它的性能幾乎直接決定著內(nèi)核的好壞，其中使用的一些設(shè)計(jì)和算法非常復(fù)雜。這里僅僅是介紹了隊(duì)列在其中的使用情況，更深入的探索還有待繼續(xù)去探索。

參考資料

Linux Kernel Development, Second Edition, Robert Love, Sam Publishing.

Understanding the Linux Kernel, 3rd Edition, Daniel P. Bovet, Marco Cesati, O’Reilly.

The Linux Kernel Primer: A Top-Down Approach for x86 and PowerPC Architectures, Claudia Salzberg Rodriguez, Gordon Fischer, Steven Smolski, Prentice Hall PTR.

總結(jié)

以上是生活随笔為你收集整理的linux进程运行队列,Linux进程调度中队列的使用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。