行程與排程

為什麼你的電腦能同時開十幾個分頁？

想像你坐在咖啡廳，筆電上同時開著瀏覽器的十幾個分頁、一個音樂播放器、背景下載的更新程式，還有一個正在打字的文件編輯器。直覺上你會以為這些程式「同時」在跑——但如果你的筆電只有一顆 CPU 核心，物理上它一次其實只能執行一條指令。那麼，這種「同時感」是哪裡來的？

答案藏在作業系統(operating system)最核心的兩個機制裡：行程(process) 的管理，以及決定「下一個輪到誰用 CPU」的 排程(scheduling)。作業系統就像一位手腳極快的餐廳服務生，在十幾桌客人之間飛快地切換——切換得夠快，每一桌都覺得自己被專心服務著。這篇文章就要拆解這位「服務生」是怎麼做決策的。

行程是什麼：執行中的程式

我們先把兩個容易混淆的詞分清楚。

• 程式(program)：躺在硬碟上的一個檔案，例如 chrome.exe。它是靜態的、死的，只是一堆機器碼。
• 行程(process)：當你雙擊那個檔案、把它載入記憶體開始執行時，就誕生了一個行程。它是動態的、活的。

一個行程不只是程式碼。作業系統為每個行程維護一份完整的「身分檔案」，稱為 行程控制區塊(Process Control Block, PCB)，裡面記錄了：

• 行程識別碼(PID)
• 目前的狀態(state)
• 程式計數器(program counter)：下一條要執行的指令在哪裡
• CPU 暫存器(register)的內容
• 記憶體配置資訊
• 開啟的檔案、I/O 裝置等資源清單

同一個程式可以同時跑出多個行程——你開兩個瀏覽器視窗，就是兩個各自獨立、互不干擾記憶體空間的行程。

行程 vs 執行緒：更輕量的執行單位

行程之間彼此隔離，這很安全，但也有代價：建立一個行程很「重」，而且行程間要互相溝通(inter-process communication)很麻煩。

於是有了 執行緒(thread)。一個行程內部可以有多條執行緒，它們共享同一份記憶體空間、開啟的檔案等資源，但各自擁有獨立的程式計數器、暫存器與堆疊(stack)。

打個比方：行程是一間有獨立門禁的辦公室，執行緒則是這間辦公室裡的多名員工。員工共用辦公室的白板與檔案櫃（共享記憶體），但每個人手上有自己的待辦清單（獨立堆疊）。

因為共享記憶體，多執行緒程式要特別小心 競爭條件(race condition)——兩條執行緒同時改同一份資料導致結果錯亂，這需要鎖(lock)等同步機制來防範。

行程的一生：狀態與轉換

一個行程從生到死，會在幾個狀態之間移動。最常見的三狀態模型是：

• 就緒(ready)：萬事俱備，只等 CPU 分配時間給它。
• 執行(running)：正握有 CPU、正在執行指令。
• 等待／阻塞(waiting / blocked)：在等某件事完成，例如等硬碟把資料讀進來、等使用者按鍵。此時就算給它 CPU 也沒用。

狀態之間的轉換像這樣：

            [被排程選中]
   ready ───────────────▶ running
     ▲                      │  │
     │ [I/O 完成]           │  │ [時間配額用盡 / 被搶佔]
     │                      │  └──────────▶ ready
   waiting ◀────────────────┘
            [發出 I/O 請求]

關鍵觀察：在單核心系統中，同一時刻只有一個行程處於 running。所謂「多工(multitasking)」，其實是作業系統讓眾多行程在 ready 與 running 之間快速輪替，製造出並行(concurrency)的假象。注意「並行」與「平行(parallelism)」不同：平行需要多個核心真正同時執行，並行則只需要在時間軸上交錯。

換手的代價：上下文切換

當 CPU 從行程 A 切換去執行行程 B 時，作業系統必須：

1. 把 A 目前的 CPU 暫存器、程式計數器等狀態，完整存回 A 的 PCB；
2. 從 B 的 PCB 載入 B 之前存下的狀態；
3. 讓 CPU 從 B 上次中斷的地方繼續跑。

這個過程稱為 上下文切換(context switch)。它是純粹的「行政開銷」——切換的那段時間，CPU 沒有替任何使用者程式做有用的計算。雖然單次切換只花微秒等級的時間，但若排程太頻繁，累積起來的浪費就很可觀。這也是後面排程演算法要權衡的重點之一。

排程演算法：誰先用 CPU？

當多個行程都在 ready 狀態排隊，作業系統的 排程器(scheduler) 必須挑一個來執行。挑選的策略就是排程演算法。我們先建立兩個重要概念：

• 非搶佔式(non-preemptive)：行程一旦拿到 CPU，就一直跑到自己主動讓出（結束或進入等待）為止。
• 搶佔式(preemptive)：作業系統可以強制中斷正在執行的行程，把 CPU 收回去給別人。現代桌面與手機作業系統幾乎都是搶佔式，這樣才能保證沒有任何一個程式能霸佔 CPU 不放。

下面介紹四種經典演算法。

FCFS（先到先服務）

先來先服務(First-Come, First-Served) 就像便利商店排隊結帳：誰先進就緒佇列，誰先被服務，做完才換下一個。非搶佔式，實作簡單、公平直覺。

缺點是 護航效應(convoy effect)：如果一個超耗時的行程排在前面，後面一堆小行程都得苦等。就像一台推著滿車貨物的客人排在你前面結帳。

SJF（最短工作優先）

最短工作優先(Shortest Job First) 改成優先服務「預估執行時間最短」的行程。可以證明，SJF 能讓平均等待時間最小化。

但它有兩個問題：一是作業系統其實無法事先準確知道一個行程要跑多久（只能用歷史資料預測）；二是若短工作源源不絕地進來，長工作可能永遠排不到，造成 飢餓(starvation)。

RR（輪流排程）

輪流排程(Round Robin) 是搶佔式的代表。系統給每個行程一段固定的 時間配額(time quantum / time slice)，例如 10 毫秒。時間一到，不管行程做完沒，都被強制換下、排到佇列尾端，換下一個上場。

RR 的精神是公平與良好的回應性——每個行程都不必等太久就能輪到一次。時間配額的設定是門藝術：太大就退化成 FCFS；太小則上下文切換太頻繁，開銷吃掉效能。

優先權排程

優先權排程(Priority Scheduling) 給每個行程一個優先權數字，永遠先服務優先權最高的。SJF 其實可看成「以執行時間長短為優先權」的特例。

優先權排程同樣有飢餓問題：低優先權行程可能一直被插隊。解法是 老化(aging)——讓一個行程等越久，它的優先權就慢慢提高，最終一定輪得到。

動手看一個例子

假設有三個行程同時在時間 0 抵達就緒佇列，各自需要的 CPU 時間（稱為 執行時間／突發時間 burst time）如下：

我們比較 FCFS（依 P1、P2、P3 順序） 與 SJF 兩種排程下的表現。

FCFS（執行順序 P1 → P2 → P3）

時間軸： |---- P1 ----|-- P2 --|- P3 -|
        0           8        12     14

• P1 等待時間 ＝ 0
• P2 等待時間 ＝ 8（要等 P1 跑完）
• P3 等待時間 ＝ 12（要等 P1、P2 跑完）
• 平均等待時間 ＝ $(0 + 8 + 12) / 3 \approx 6.67$

SJF（依突發時間排序，執行順序 P3 → P2 → P1）

時間軸： |- P3 -|-- P2 --|---- P1 ----|
        0     2        6            14

• P3 等待時間 ＝ 0
• P2 等待時間 ＝ 2
• P1 等待時間 ＝ 6
• 平均等待時間 ＝ $(0 + 2 + 6) / 3 \approx 2.67$

同樣三個行程、總工時相同（最後都在時間 14 全部做完），但 SJF 把短工作擺前面，平均等待時間從 6.67 降到 2.67。這直觀地說明了為什麼 SJF 在「平均等待時間」這個指標上是最優的：讓短工作先走，能減少後面所有人累積的等待。

重點回顧

• 程式是靜態檔案，行程是執行中的程式；行程的完整狀態記錄在 PCB 中。執行緒是行程內更輕量、共享記憶體的執行單位。
• 行程在 ready／running／waiting 三個狀態間轉換；單核心下同一時刻只有一個行程在 running，多工是快速輪替造成的並行假象。
• 上下文切換是換手行程時的必要開銷，本身不產生有用計算，排程設計需盡量減少不必要的切換。
• 四大經典排程：FCFS（簡單但有護航效應）、SJF（平均等待最短但需預測且會飢餓）、RR（搶佔式、公平、回應快）、優先權（可彈性但需老化防飢餓）。
• 搶佔式排程讓作業系統能強制收回 CPU，是現代互動式系統保證回應性的關鍵。

深入探討（研究所視角）

排程指標的精確定義

要客觀評比排程演算法，需要量化指標。對一個行程而言，常用三個時間指標：

• 周轉時間(turnaround time) ＝ 完成時間 － 抵達時間。從進入系統到徹底做完，總共花了多久。
• 等待時間(waiting time) ＝ 周轉時間 － 實際執行（突發）時間。即在就緒佇列乾等的總時長。
• 回應時間(response time) ＝ 第一次被排上 CPU 的時間 － 抵達時間。即從送出到「開始有反應」的延遲。

這三者衡量的面向不同。批次運算系統在意 周轉時間 與 吞吐量(throughput，單位時間完成的行程數)；而互動式系統（桌面、手機）最在意 回應時間——使用者點一下按鈕，能多快看到畫面動起來，比「整體跑完多快」更影響體驗。這正是 RR 雖然平均周轉時間未必最佳，卻廣受互動式系統採用的原因：它的回應時間表現優異。

排程設計本質上是一個多目標權衡問題：最小化平均等待、最大化吞吐、保證公平、避免飢餓、控制切換開銷，這些目標彼此常有衝突，沒有單一演算法能全贏。

搶佔式排程的延伸：SRTF 與優先權反轉

SJF 的搶佔式版本稱為 最短剩餘時間優先(Shortest Remaining Time First, SRTF)：每當有新行程抵達，排程器比較「新行程的突發時間」與「目前行程的剩餘時間」，若新來的更短就立刻搶佔。SRTF 在理論上能進一步壓低平均等待時間，但搶佔本身帶來更多上下文切換成本，且預測剩餘時間同樣困難。

搶佔式優先權排程還潛藏一個著名陷阱——優先權反轉(priority inversion)：高優先權行程 H 需要一把鎖，但這把鎖正被低優先權行程 L 持有；偏偏中優先權行程 M 不斷搶佔 L，使 L 遲遲無法執行、無法釋放鎖，結果 H 被間接卡死。1997 年 NASA 的火星拓荒者號(Mars Pathfinder)就因此反覆重啟，最終靠遠端啟用 優先權繼承(priority inheritance) 協定修復——讓持鎖的低優先權行程暫時繼承等鎖者的高優先權，儘快做完釋放鎖。這個案例提醒我們：排程不能脫離同步機制孤立地看。

從理論到現代核心

真實系統遠比四大經典演算法複雜。典型作法是 多層回饋佇列(Multilevel Feedback Queue, MLFQ)：設置多個不同優先權的佇列，行程依其行為動態升降——用滿時間配額（像是 CPU 密集型）就被降級，主動讓出 CPU（像是 I/O 密集型的互動程式）則維持高優先權。如此能在不預知突發時間的前提下，近似 SJF 的效果，同時兼顧互動回應。Linux 過去的 完全公平排程器(Completely Fair Scheduler, CFS) 則改用紅黑樹(red-black tree)追蹤每個行程累積的「虛擬執行時間」，總是挑虛擬時間最少者執行，以 $O(\log n)$ 的複雜度逼近理想中的「處理器資源完全均分」。

延伸思考可連結到本讀本的其他主題：排程器挑中行程後，記憶體管理(memory management)還得確保它的分頁(page)在實體記憶體中（否則觸發分頁錯誤又得阻塞等 I/O）；多核心時代則進一步衍生 負載平衡(load balancing) 與 快取親和性(cache affinity)——把行程固定在同一核心執行，可重用該核心快取(cache)中的資料，這又把排程與計算機組織的議題綁在了一起。排程，遠不只是「誰先用 CPU」這麼單純的排隊問題。