這是萌芽站長在學校資工系「作業系統」課程之筆記與摘要整理。我們都知道在電腦中，當程式運行時，會產生大量的處理程序（Process），那中央處理器（CPU）該如何做排程（Scheduling）呢？所以這個部分就是這篇要講的重點！順帶一提，程式可以被說成是被動的實體（Passive Entity），處理程序則可以被說成是活動的實體（Active Entity），前者由人或系統來控制與執行，後者建立後就能獨立運行於作業系統中，先把這個觀念搞懂後續會比較容易理解！本文僅供學術參考使用，花費五小時時間撰寫。
這邊假設中央處理器（CPU）都只有一顆，處理程序（Process）很多（為了方便整理解說，其實數量也只有設定在個位數）的情況。
▲ 當一堆的處理程序想搶唯一的中央處理器，那該怎麼辦呢？（圖：由萌芽站長使用 3D 小畫家繪製）
⏬ 直接跳到本篇章節目錄 ⏬
站長的廢話（不重要可以跳過 😅）：其實我以前沒有特別想說把自己的所學給打成文章，放到自己的網站上跟他人分享，一方面是很花時間，另外一方面是早期比較習慣用紙筆作筆記，但我的字跡不是很好看，所以只有部分大膽的 PO 出來了！不過隨著時間推移，我開始習慣用電子檔作筆記，加上現在所學的很多領域都跟電腦有關，教材也幾乎都電子化了！想說不浪費資源，我就用我自己的方式與語言來傳遞與整理這些知識，這當然也對我的考試分數很有幫助，整理的過程我能將這些知識記住的更清楚！老實說，我一直很不喜歡考試的教育制度，我認為人就是要不斷學習，學習時間已經不夠了怎麼還有時間在那邊考試呢？紙筆考試有時候根本無法證明一個人的真實能力呀！希望未來這方面能有所改善，我認為學習是主動的而非被動的，如果要考試才學習這些知識，那乾脆就別學了不是嗎？😜
本篇章節目錄
一、基本名詞解釋
二、CPU 排程的選用標準
三、往返時間（Turnaround Time）與等待時間（Waiting Time）
四、先到先服務（First Come First Served） 排程法
五、最短工作優先（Shortest Job First）排程法
六、最高反應時間比率優先排程法
七、優先等級（Priority）排程法
八、知更鳥式循環（Round Robin）排程法
九、多階層佇列（Multilevel Queue）排程法
十、多階層回饋佇列（Multilevel Feedback Queue）排程法
十一、現代電腦所採用的排程探討
一、基本名詞解釋
CPU Burst
使用 CPU 的時間（使用期）
CPU Bound Process
大的 CPU burst，處理程序使用 CPU 較長的時間，也就是使用更多的時間進行運算而不是 I/O。
I/O Burst
使用 I/O 的時間（使用期）
I/O Bound Process
小的 CPU burst，處理程序使用 CPU 較短的時間，也就是使用更多的時間進行 I/O 而不是運算。
💬 有些排程下，一旦處理程序佔有 CPU，就一定要等到它妥善處理完畢後才允許分派其他的處理程序給 CPU，但有些排程就用不著這麼沒有彈性了！
不可奪取的（Non Preemptive）
有先處理程序生成後優先等級非常高，一旦佔有 CPU，就不允許其他處理程序奪取 CPU，這類處理程序就叫做不可奪取的。
可奪取的（Preemptive）
大多處理程序依照排程政策，許可 CPU 被奪取，這類處理程序就叫做可奪取的。
💬 還有一些名詞解釋...
分派時間（Dispatch Latency）
分派程式停止某一個處理程序使用 CPU，並將 CPU 分派給另一個處理程序所需要的時間。
二、CPU 排程的選用標準 ⏏
1️⃣ 我們希望系統擁有最高的產量（Maximum Throughput）。
2️⃣ 使得往返時間（Turnaround Time）是最小的。
3️⃣ 使得所有處理程序的平均等待時間（Average Waiting Time）是最小的。
4️⃣ 使得系統內最慢的反應時間（Maximum Response Time）是所有方法中最小的。
5️⃣ 儘量讓 CPU 不斷忙碌，並有最高的 CPU 使用率（CPU Utilization）。
6️⃣ 使得反應時間之變異數（Variance in the Response Time）是最小的。
7️⃣ 使得交談使用者人數（Number of Interactive Users）是最多的。
8️⃣ 使得系統負擔（System Overhead）是最小的。
9️⃣ 使得資源被平衡的使用（Balance Resources Used）。
🔟 所有排程是公平的（Be Fair）。
三、往返時間（Turnaround Time）與等待時間（Waiting Time） ⏏
💬 名詞解釋：
往返時間（Turnaround Time）：使用者從開始提交（Submit）電腦工作到整個工作完成所需的時間，這當中包含中央處理器處理時間（CPU Time）、輸入輸出（I/O）的時間以及等待作業系統的時間。
等待時間（Waiting Time）：處理程序執行後中間有多少時間是被迫暫停執行的。
結束時間（End Time）：處理程序結束的時間。
抵達時間（Arrival Time）：處理程序抵達佇列的時間。
處理時間（Burst Time）：處理程序所需要執行的時間。
💬 計算方式：
往返時間（Turnaround Time） = 結束時間（End Time） - 抵達時間（Arrival Time）
等待時間（Waiting Time） = 往返時間（Turnaround Time） - 處理時間（Burst Time）
四、先到先服務（First Come First Served） 排程法 ⏏
此排程法簡稱 FCFS（First Come First Served），為不可奪取排程法，不適合使用者進行交談，也不適合分時（Time-sharing）系統。
以下是五個處理程序同時到達後的情況（時間單位為秒[s]）：
| 處理程序 | CPU 處理時間 | 往返時間 | 等待時間 |
| P1 P2 P3 P4 P5 |
8 6 2 7 5 |
8 14 16 23 28 |
0 8 14 16 23 |
甘特圖：
平均等待時間為：(0 + 8 + 14 + 16 + 23) / 5 = 12.2(秒)
五、最短工作優先（Shortest Job First）排程法 ⏏
此排程法簡稱 SJF（Shortest Job First），依照處理時間（使用 CPU 的時間）由小至大依序排列至佇列內，以進行 CPU 排程。若處理程序有相同處理時間，則以 FCFS 排程。可被區分為不可奪取最短工作優先排程法（Non-Preemptive SJF）及可奪取最短工作優先排程法（Preemptive SJF）。上述前者不適合分時（Time sharing）；後者適合分時（Time sharing），又稱最短剩餘時間優先（Shortest Remaining Time First）排程法，簡稱為 SRTF，它會隨時注意是否有較小處理時間之處理程序出現，若有，則將 CPU 讓給此使用處理時間較小的處理程序。
以下是五個處理程序同時到達後的情況（時間單位為秒[s]）：
| 處理程序 | CPU 處理時間 | 往返時間 | 等待時間 |
| P1 P2 P3 P4 P5 |
8 1 2 1 4 |
16 1 4 2 8 |
8 0 2 1 4 |
甘特圖：
平均等待時間為：(8 + 0 + 2 + 1 + 4) / 5 = 3(秒)
最短工作優先排程法有最少的平均等待時間，所以若以等待時間來評估好壞，此排程法是一個最佳的演算法（Optimal Algorithm），可惜實務上不可行，因為處理程序尚未執行前我們無法預估其處理時間。
接下來是五個處理程序不同時間到達後的情況（時間單位為秒[s]），用來解釋可奪取最短工作優先排程法：
| 處理程序 | 抵達時間 | CPU 處理時間 | 往返時間 | 等待時間 |
| P1 P2 P3 |
0 1 2 |
3 1 3 |
4 1 5 |
1 0 2 |
甘特圖：
平均等待時間為：(1 + 0 + 2) / 3 = 1(秒)
六、最高反應時間比率優先排程法 ⏏
反應時間比率（Response Ratio）與等待時間及處理時間有關，它的公式為：
反應時間比率 = (等待時間 + 處理時間) / 處理時間
反應時間比率愈高的處理程序優先處理，以反應時間比率當作變動優先等級來排程。
七、優先等級（Priority）排程法 ⏏
給每一個處理程序優先等級，並依照優先等級將處理程序由高優先等級排至低優先等級，然後依序分派處理程序佔有 CPU。若擁有相同優先等級則採用 FCFS。若一個高優先等級處理程序比一個較低優先等級處理程序後生成，它要排在較低優先等級處理程序的前方。
此排程可分為可奪取優先等級排程及不可奪取優先等級排程。
這種排程有個問題，若系統內不斷有較高優先等級之處理程序生出，則低優先等級之處理程序可能永遠無法被執行，我們稱此低優先等級處理程序被無限懸置（Indefinite Blocking）或餓死（Starvation）。
➡ 可利用時間升級（Aging）、變動優先等級（Dynamic Priority）或浮動優先等級（Floating Priority）機制來解決！
八、知更鳥式循環（Round Robin）排程法 ⏏
分時系統所採用的排程法，可奪取。
此排程法需要做時間片段的選擇：
時間片段太大 ➡ 先到先服務排程法（FCFS）
時間片段太小 ➡ 系統效率太差
※ 太小會導致 Context Switch 時間被佔滿，處理程序幾乎無法執行（或執行時間極少）。
九、多階層佇列（Multilevel Queue）排程法 ⏏
現在有多個佇列來做排程，當電腦系統內有許多不同優先等級處理程序要執行，且也有許多相同優先等級處理程序要執行， 則最高優先等級處理程序會先被執行，並且若有同時多個最高優先等級處理程序在系統內，則它們會優先在佇列內排隊等待被執行唷！
由於在多階層佇列排程法內的處理程序生成之後就永遠固定優先等級，這就有可能導致某些低優先等級處理程序餓死，實務上不適用。
十、多階層回饋佇列（Multilevel Feedback Queue）排程法 ⏏
此排程法是可奪取的，原則系統處理程序維持高優先等級，批次作業處理程序維持低優先等級，其餘處理程序則依時間升級機制游走於各個佇列中，因為中央處理器限制處理程序（CPU Bound Process）會隨著時間而降低優先等級，加上輸出/ 輸入限制處理程序（I/O Bound Process）會隨著時間提升優先等級，因此處理程序不會有餓死的情形發生。
十一、現代電腦所採用的排程探討 ⏏
現代電腦作業系統採用多階層回饋佇列，它提供多個佇列，每個佇列對應一個優先等級，處理程序依生成時給的優先等級，在相對的佇列內排隊等待。系統以分時方式至最高優先等級佇列最前面選取一個處理程序佔有 CPU 執行，若最高優先等級佇列內沒有處理程序，則至次高優先等級佇列內選取處理程序進行分時處理。有使用時間升級機制，允許處理程序依時間升級機制提升至較高優先等級或降低至較低等級佇列中。
現代電腦還有多處理器（Multiple Processor）的特色呢！效能越做越好了！
[ 文章結束囉！希望有幫助您學習！🥰 文章整理可能有所簡化或疏失，還請大家多方查證唷 ☺ ]
《上一篇》Google 最新 after & before 日期區間搜尋工具 
《下一篇》誰說討債只能找「討債公司」？讓立達徵信社幫您斯文討債、和平協商 
留言區 / Comments
萌芽論壇