操作系統調度理論：多道程序環境下 CPU 利用率與吞吐量計算

問題模型

單處理器系統，每個作業包含 N 個周期，每周期 T 時間。一半時間 I/O，一半 CPU 計算。I/O 可與 CPU 重疊。簡單輪循調度。計算 1、2、4 個作業並發時的：

• 時間周期（完成所有作業的實際時間）
• 吞吐量（單位時間完成作業數）
• CPU 利用率

兩種 I/O 分布模式：(a) 前半 I/O 後半 CPU；(b) 前 1/4 I/O、中間 1/2 CPU、後 1/4 I/O。答案指出 (a)(b) 結果相同。

核心結論（標準答案）

詳細推導邏輯

1 個作業

串行執行：I/O 和 CPU 不能重疊（無其他作業填補）。每周期 T 中 CPU 忙 T/2，共 N 周期 → 總時間 N·T，CPU 忙 N·T/2 → 利用率 50%。

2 個作業

作業 1 前半 I/O 時，作業 2 後半 CPU（或反之），完美交錯。CPU 全程無空閒 → 利用率 100%。總時間仍為 N·T（流水線滿載）。吞吐量翻倍。

4 個作業

前 N-1 個周期：CPU 滿載（100%）。最後一個周期：只有 1 個作業剩餘 CPU 部分，後半段 CPU 空閒。總時間 = (N-1)·T + 1.5T = (2N-1)T/2? 等等，標準答案給 (2N-1)NT 似乎有筆誤，應為 (2N-1)·T/2 或類似。但關鍵點：CPU 利用率達到 100% 直到最後階段。

關鍵洞見

I/O 可重疊是提高 CPU 利用率的關鍵。 多道程序度越高，越能掩蓋 I/O 等待，直到 CPU 成為瓶頸。此模型說明了多道程序技術的本質價值。