Linux 進程調度中隊列機制深度解析：運行隊列與等待隊列

Linux 內核大量使用雙向鏈表實現隊列，進程調度子系統是典型應用場景。本文基於 include/linux/list.h、kernel/sched.c、include/linux/wait.h，詳細剖析運行隊列（runqueue）、優先級數組（prio_array）、等待隊列（wait_queue_head）的數據結構與操作接口。

進程狀態與隊列歸屬

1. 運行隊列：runqueue + prio_array

數據結構

struct prio_array {
    int nr_active;                    // 隊列中活動進程數
    unsigned long bitmap[BITMAP_SIZE]; // 優先級位圖，快速查找最高優先級
    struct list_head queue[MAX_PRIO]; // 140 個優先級隊列數組 (0-139)
};

struct runqueue {
    struct prio_array *active;        // 活動優先級數組
    struct prio_array *expired;       // 時間片耗盡優先級數組
    struct list_head queue_head;      // 兼容舊版
    // ... 鎖、負載均衡等字段
};

O(1) 調度核心機制

• 每個 CPU 一個 runqueue，包含 active 和 expired 兩個 prio_array
• 新進程/時間片未盡進程入 active 對應優先級隊列
• 時間片耗盡進程移入 expired 同優先級隊列
• active 為空時，指針交換：active <-> expired，O(1) 完成優先級重新劃分
• bitmap 位圖加速最高優先級查找：sched_find_first_bit()

進程入隊關鍵字段

struct task_struct {
    // ...
    struct list_head run_list;    // 掛載到 prio_array->queue[prio]
    int prio;                     // 動態優先級
    int static_prio;              // 靜態優先級
    struct runqueue *rq;          // 所屬運行隊列
    // ...
};

2. 等待隊列：wait_queue_head + wait_queue_t

數據結構

typedef struct __wait_queue_head {
    spinlock_t lock;               // 保護隊列自旋鎖
    struct list_head task_list;    // 隊列頭
} wait_queue_head_t;

typedef struct __wait_queue {
    unsigned int flags;            // WQ_FLAG_EXCLUSIVE 等
    struct task_struct *task;      // 等待的進程
    wait_queue_func_t func;        // 喚醒回調函數
    struct list_head task_list;    // 掛載到 wait_queue_head
} wait_queue_t;

兩類等待進程

• 非獨佔：flags=0，事件發生喚醒所有（如管道數據到達）
• 獨佔：flags=WQ_FLAG_EXCLUSIVE，喚醒一個即停止（如信號量、互斥鎖），避免驚群效應

3. 等待/喚醒接口族

典型使用模式

// 手動模式：精確控制
DEFINE_WAIT(wait);
prepare_to_wait_exclusive(&wq, &wait, TASK_INTERRUPTIBLE);
if (!condition)
    schedule();
finish_wait(&wq, &wait);

// 宏模式：簡潔安全
wait_event_interruptible(wq, condition);
// 等價於：
// while (!condition) {
//     prepare_to_wait(&wq, &wait, TASK_INTERRUPTIBLE);
//     if (!condition) schedule();
//     finish_wait(&wq, &wait);
// }
// 且自動處理信號、超時

4. 超時等待：schedule_timeout

signed long schedule_timeout(signed long timeout)
{
    // 設置當前進程狀態為 TASK_INTERRUPTIBLE/UNINTERRUPTIBLE
    // 將進程加入超時隊列（timer wheel）
    // schedule() 切換
    // 超時或被喚醒返回剩餘時間
}

• wait_event_timeout、wait_event_interruptible_timeout 內部調用
• 返回值：0=超時，>0=剩餘 jiffies，<0=信號中斷

總結

• 運行隊列：prio_array + bitmap 實現 O(1) 調度，雙緩衝交換處理時間片輪轉
• 等待隊列：wait_queue_head + wait_queue_t，支持獨佔/非獨佔、超時、信號響應
• 優先使用 wait_event* 宏，減少手動狀態管理錯誤
• 持有自旋鎖只能用 wake_up_locked，避免死鎖