Linux內核中大量使用了隊列，這裡僅列舉它在進程調度中的幾處應用。Linux內核中的隊列是以雙鏈表的形式連接起來的，include/linux/list.h中定義了隊列並提供了一些接口，詳細的介紹可以參考[1]中的附錄。
Linux中的進程有如下幾個主要狀態：
進程狀態
說明
TASK_RUNNING
進程正在運行或將要被運行。
TASK_INTERRUPTIBLE
進程正在睡眠，等待某個條件的完成。
TASK_UNINTERRUPTIBLE
深度睡眠，不會被信號打擾。
TASK_STOPPED
進程運行被停止。
TASK_TRACED
進程被調試程序停止，被另一個進程跟蹤。
兩個額外的狀態是EXIT_ZOMBIE和EXIT_DEAD，表示進程處於僵死狀態還是真正死亡。處於僵死狀態的進程會等待其父進程的收養（否則就會被init進程收養），而真正死亡的進程會被直接刪除。
狀態為TASK_RUNNING的進程都會被放入運行隊列（runqueue）中，這是通過task_struct（定義在include/linux/sched.h）中的run_list成員來鏈接的。不過，為了讓內核每次都能選取優先級最合適的進程，Linux為每個優先級構建了一個queue。這是通過struct prio_array來實現的，struct prio_array的定義在kernel/sched.c，大致如下：
struct prio_array {
int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};
queue成員就是隊列數組。每個CPU有各自的runqueue，每一個runqueue又有包含兩個prio_array，一個是活動隊列，一個是時間片耗盡的隊列。當運行隊列空時，內核便會交換兩個隊列的指針，原來的耗盡隊列就成了新的活動隊列！這和prio_array中的bitmap是決定調度算法為O(1)的關鍵。
狀態為TASK_STOPPED，EXIT_ZOMBIE或EXIT_DEAD的進程不會被放入專門的隊列中，它們直接通過pid或者通過父進程的孩子隊列來訪問。
TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE狀態的進程會被放入等待隊列。不同的是，每個等待事件都會有一個等待隊列，該隊列中的進程等待同一事件的完成。（“事件”一個動態的過程，不好通過具體的結構來定義一個“事件”。這裡等待一個事件就是查看某個條件是否為真，比如某個標志變量是否為真。）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;
進入等待狀態的接口有兩類：
prepare_to_wait*()/finish_wait()
wait_event*()
其實wait_event*()內部也是調用prepare_to_wait*()，把它放入一個循環中。而且wait_event*()在事件完成時會自動調用finish_wait()。決定使用哪個要看情況而定。（sleep_on*()是遺棄的接口，現在已經不再使用，雖然還支持。）等待隊列中的進程有兩種，一種是exclusive的進程，另一種是nonexclusive的進程。所謂exclusive是指喚醒的進程等待的資源是互斥的，每次只喚醒一個（喚醒多個也可以，不過最後還是只有一個會被喚醒，其余的又被重新添加到等待隊列中，這樣效率會大打折扣）。一般，等待函數會把進程設為nonexclusive和uninterruptible，帶“interruptible”的會專門指定狀態為interruptible；而帶“timeout”的會在超時後退出，因為它會調用schedule_timeout()；帶“exclusive”的則會把進程設為exclusive。
喚醒的接口雖然只有wake_up*()，但它內部也分成好幾種。帶“interruptible”的喚醒函數只會喚醒狀態是TASK_INTERRUPTIBLE的進程，而不帶的則會喚醒TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE的進程；所有喚醒函數都會把等待同一事件的nonexclusive進程全部喚醒，或者把其中一個exclusive的進程喚醒；而帶“nr”的則會喚醒指定個數的exclusive的進程，帶“all”的會把全部exclusive進程喚醒。帶“sync”會忽略優先級的檢查，高優先級的進程可能會被延遲。最後，持有自旋鎖時只能調用wait_up_locked()。
進程管理是Linux內核中最關鍵的部分，它的性能幾乎直接決定著內核的好壞，其中使用的一些設計和算法非常復雜。這裡僅僅是介紹了隊列在其中的使用情況，更深入的探索還有待繼續去探索。
