2003 - Linux 2.6 核心革命（O(1) 排班、NPTL、可搶佔）#

案件摘要#

2003 年 12 月 17 日，Linux 2.6 發布——核心史上最大的一次革命：

\[ \text{O(1) 排班器} + \text{NPTL 執行緒} + \text{可搶佔核心} + \text{ALSA} + \text{udev}. \]

桌面多媒體與企業級伺服器的雙重勝利——2.6 讓 Linux 同時勝任「桌面的 MP3 播放」與「資料中心的重負載」。

前因 -- 為什麼會有這個案子#

2.4 排班器的缺陷：2.4 的排班器是 O(n)——每次排班要掃描所有行程，行程數上千時（企業伺服器）效率崩潰——彌補的缺陷：O(n) 排班。Ingo Molnar 寫出 O(1) 排班器（2003.1 先進入 2.4.20/2.5）。
LinuxThreads 的缺陷：舊執行緒實作每個執行緒是一個不同 pid 的行程、訊號處理怪異、無法發揮 SMP——彌補的缺陷：執行緒不是一等公民。NPTL（Native POSIX Thread Library，2003，Red Hat 的 Molnar/Drepper）用「一個行程多個輕量執行緒」解決。
可搶佔的渴望：2.4 核心不可搶佔——音樂播放時核心忙，聲音就斷——彌補的缺陷：桌面延遲。2.6 加上可搶佔核心（CONFIG_PREEMPT）。

線索與推理 -- 2.6 的技術面貌（2003）#

技術	2.6 版狀態	版本脈絡	彌補的缺陷
O(1) 排班	每級優先度一個執行佇列，取隊首 O(1)	2.5.2（2002）試驗	2.4 O(n) 掃描
NPTL	一個行程多個 clone 執行緒，futex 同步	2003，Red Hat	LinuxThreads 的 pid 怪異
可搶佔	核心碼可被高優先度行程搶佔	CONFIG_PREEMPT	桌面音訊延遲
ALSA	進階 Linux 音訊架構取代 OSS	2.6.1 整合	OSS 的混音器僵化
udev	動態 /dev 裝置管理（2003.12，Greg KH）	取代 devfs	靜態 /dev 的混亂
檔案系統	ext3（日誌）穩定支援	見 `../UNIX/2003-ext3日誌式檔案系統.md`	ext2 當機慢
NUMA	非一致記憶體存取支援	大型機器	伺服器擴展性

C 範例：NPTL 執行緒（2003 的革命）#

/* NPTL (2003)：執行緒成為一等公民 */
#include <pthread.h>
#include <stdio.h>

void *worker(void *arg) {
    printf("thread pid=%d tid=%lu\n",
           getpid(), (unsigned long)pthread_self());
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, worker, NULL);  /* 同一 pid，兩個執行緒 */
    pthread_create(&t2, NULL, worker, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
}

（NPTL 之前：每個執行緒不同 pid，ps 顯示成多個行程；NPTL 之後：一個 pid，多個輕量執行緒——POSIX 語義正確。）

Shell 範例：O(1) 排班與可搶佔的實證#

# O(1) 排班：上千行程也能即時回應
$ for i in $(seq 1000); do sleep 100 & done
$ nice -n -20 top -b -n1 | head -5   # 高優先度行程立刻被排班

# chrt（即時排班）：SCHED_FIFO 即時類別
$ chrt -f 50 mytask        # 即時等級 50——核心立即搶佔普通行程

C 範例：futex（NPTL 的同步基礎）#

/* futex (2003)：fast userspace mutex——無競爭時不進核心 */
#include <linux/futex.h>
#include <sys/syscall.h>

int futex_wait(int *uaddr, int val) {
    return syscall(SYS_futex, uaddr, FUTEX_WAIT, val, NULL);
}
int futex_wake(int *uaddr, int n) {
    return syscall(SYS_futex, uaddr, FUTEX_WAKE, n);
}

（理論：鎖的快速路徑在使用者空間原子指令完成，只有競爭時才陷入核心——效能與正確性兼得。）

結案 -- 後果與影響#

企業級勝利：O(1) + NUMA 讓 Linux 進入資料中心；2003 年後 Oracle、IBM 正式支援 Linux。
桌面與手機的基礎：可搶佔 + ALSA 讓多媒體流暢；Android（2008）的流暢度建立在此。
CFS 的接棒：O(1) 仍有「互動性偵測」的啟發式缺陷——2007 年 Ingo Molnar 再寫 CFS（完全公平排班器）（2.6.23），用紅黑樹取代啟發式。
udev → systemd 的前奏：Greg KH 的 udev 讓裝置管理現代化，為 systemd 的裝置依賴鋪路。
歷史教訓：一次革命三戰場（桌面/伺服器/手機）——2.6 是 Linux 成為「通用核心」的分水嶺。

關鍵人物與文獻#

I. Molnar：O(1) 排班（2002–03）、NPTL（2003）、CFS（2007）。
U. Drepper：NPTL 與 glibc；〈The Native POSIX Thread Library for Linux〉(2003)。
G. Kroah-Hartman：udev (2003)。
相關案件：1996-Linux2.0與SMP.md、2007-CFS排班與2.6.23.md。