CPU 排程計算工具

以甘特圖顯示 CPU 排程的動作，也就是作業系統決定以什麼順序把 CPU 分配給多個等待執行之行程的方式。可切換先到先服務、最短工作優先、最短剩餘時間優先、循環分時、優先順序排程，比較平均等待時間與往返時間如何變化。

行程

範例方式

時間配額（循環分時）

名稱	到達時間	執行時間	優先順序

只使用有輸入執行時間的列（最多 8 個）。時間為 0 以上的整數，優先順序的數字越小越優先。

結果

平均往返時間: –
平均等待時間: –
平均回應時間: –
全部完成的時間: –

各方式的比較

往返時間 = 完成時間 − 到達時間，等待時間 = 往返時間 − 執行時間，回應時間 = 第一次分配到 CPU 的時間 − 到達時間。條件相同的行程，依到達較早者優先，若也相同則依表格上方的順序選擇。在循環分時中，時間用完的行程會排在同一時間到達的行程後面。切換所需的時間（內容切換的額外負擔）以 0 計算。

什麼是 CPU 排程

若只有 1 個 CPU，同時能執行的行程只有 1 個。有多個處於可執行狀態的行程時，由作業系統的 CPU 排程器決定下一個把 CPU 分配給誰。評估時會使用從到達到完成的往返時間、可以執行卻被迫等待的等待時間、到開始執行為止的回應時間等指標。即使是同一組行程，這些平均值也會因分配順序而大幅改變。在「全部在時間 0 到達」的範例中，先執行長度 24 之長行程的先到先服務，平均等待時間為 17，若改成由短到長執行則可減為 3。

先到先服務、最短工作優先、最短剩餘時間優先

先到先服務（FCFS）是依到達順序執行到結束的最簡單方式。短行程排在長行程後面時，短行程也會被迫等待很久（護航效應）。最短工作優先（SJF）從執行時間短的行程開始執行，使平均等待時間變小。最短剩餘時間優先（SRT）在每次有新行程到達時比較剩餘時間，若來了更短的行程，就從執行中的行程搶占 CPU。SRT 能使平均等待時間最小，但必須事先知道執行時間，而且長行程可能一直被延後（飢餓）。

循環分時與時間配額

循環分時是依序以固定時間（時間配額、時間片段）分配 CPU，並把時間用完的行程排到等待佇列最後面的方式。每個行程都能很快開始一點一點地執行，因此回應時間短，適合互動式系統。時間配額太長時與先到先服務相同，太短則行程切換（內容切換）變多，其負擔就無法忽視。請改變時間配額，確認比較表中的平均回應時間與切換次數如何變化。

優先順序排程與實際的作業系統

優先順序排程是從優先順序高的行程開始執行的方式，分為不搶占與可搶占兩種。為了防止優先順序低的行程一直等待的飢餓現象，會使用依等待時間提高優先順序的老化（aging）技巧。實際的作業系統會組合這些方式。例如依優先順序分成不同佇列、同一優先順序內以循環分時輪流，並逐步降低大量使用 CPU 之行程優先順序的多層回饋佇列，以及優先執行累計執行時間較少之行程的 Linux CFS 等。

練習作業系統題目

在環境切換（context switch）時，必須儲存切換前行程的哪些內容？

A該行程所使用的磁碟檔案內容
B暫存器的值與程式計數器等CPU的執行狀態
C該行程在實體記憶體中的全部內容

查看答案與解析

正確答案：B. 暫存器的值與程式計數器等CPU的執行狀態

在環境切換時，為了之後能從相同狀態繼續執行，會儲存通用暫存器、程式計數器、堆疊指標、運作模式等CPU的狀態，並載入接下來要執行行程的狀態。切換行程時，也會一併切換指示頁表位置的暫存器。記憶體與檔案的內容原本就保留著，因此不必在每次切換時儲存。

行程的環境切換有時造成的效能下降，實際上比儲存與還原暫存器所花的時間更大，其主要理由為何？

A因為每次切換，CPU的時脈頻率都會下降
B因為每次切換，都要重新從磁碟讀取程式
C因為切換之後，快取與TLB的未命中會增加

查看答案與解析

正確答案：C. 因為切換之後，快取與TLB的未命中會增加

儲存與還原暫存器本身只需很短的時間，但對切換後的行程而言，快取與TLB裡的內容是前一個行程的，在重新載入所需的資料與轉換結果之前，未命中會持續發生。在沒有ASID的CPU上，切換位址空間時還必須清空TLB。這種間接的成本，有時會比直接的切換時間更大。時脈並不會下降，也不會從磁碟重新讀取程式。

常見問題

等待時間與往返時間有什麼不同？

往返時間是行程從到達到完成的整段時間。等待時間是其中可以執行卻沒分配到 CPU 而等待的時間，等於往返時間減去執行時間（沒有輸入輸出等待時）。

哪一種方式的平均等待時間最短？

全部同時到達時，最短工作優先（SJF）能使平均等待時間最小；途中有行程到達且可搶占時，則是最短剩餘時間優先（SRT）。不過兩者都必須事先知道執行時間，實務上是由過去的執行時間來預測。

同一時間有 2 個行程都符合條件時，會選哪一個？

本工具會選到達較早者，若也相同則選表格中較上方的列。考題中常會寫明條件相同時的選法，請配合題目調整表格的順序。

考試中會怎麼出題？

在日本的基本資訊技術士考試、應用資訊技術士考試等資訊類證照考試中，常見的題型是給定行程的到達時間與處理時間表，求某種方式下特定行程的完成時間或平均往返時間。輸入表格後，可用甘特圖與結果表確認。