執行佇列（run queue）

在任何一瞬間，系統上大多數工作其實並不在試圖執行——它們被阻塞著，等待一次按鍵、一次磁碟讀取，或一個網路封包。只有少數是可執行的：若有空閒 CPU，現在就準備好使用。執行佇列就是核心裡恰好那些可執行工作的清單——排程器從中挑選的等候佇列。當排程器問「接下來該誰跑？」時，它就是在從執行佇列裡選。

理解它最清楚的方式，是看一個工作穿過它的生命週期。一個工作在可執行時待在執行佇列裡。排程器挑出一個在 CPU 上跑。若那個工作阻塞了——譬如它呼叫 read() 而資料尚未就緒——核心便把它從執行佇列移除，工作入睡；它在等待時不會浪費排程器的注意力。稍後，當它的資料抵達（一個中斷喚醒它），核心把它放回執行佇列、再度可執行，排程器便會輪到它。所以執行佇列的成員隨著工作阻塞與喚醒而不斷變化。在多核機器上，現代核心為每個 CPU 各保留一個執行佇列（如此核心不會全擠在一個共享清單上爭奪），而一個負載平衡器偶爾在它們之間遷移工作，好讓各核心忙得均勻。

為何這個概念能釐清這麼多事：它釘住了「排程器從中挑選的對象」，並把兩個非常不同的狀態分開。一個大量用 CPU 的工作與一個阻塞在 I/O 上的工作，在鬆散的口語裡都「在跑」，但只有前者在執行佇列裡；被阻塞的那個則完全不在其中，直到被喚醒。這也是為何 Unix 上的負載平均計算可執行（與不可中斷）的工作——它本質上是在量度執行佇列有多長，亦即有多少工作在爭奪 CPU。請注意「佇列」是鬆散的術語：現代的執行佇列往往不是簡單的先進先出佇列，而是更精緻的結構（Linux 的 CFS 用一棵依各工作所得 CPU 多寡排序的紅黑樹），所以別把它想成嚴格的 FIFO。