進程調度演算法
作業系統有三大調度機制，分別是進程調度、記憶體頁面置換和磁碟調度演算法。
進程調度演算法
定義
進程調度演算法也稱 CPU 調度演算法，畢竟進程是由 CPU 調度的，當 CPU 空閑時，作業系統就選擇記憶體中的某個「就緒狀態」的進程，並給其分配 CPU。
進程的狀態
在一個進程的活動期間至少具備三種基本狀態，即運行狀態、就緒狀態、阻塞狀態。為什麼說至少呢？當然，進程還有另外兩個基本狀態：創建狀態和結束狀態。
- 創建狀態（new）：進程正在被創建；
- 就緒狀態（Ready）：可運行，由於其他進程處於運行狀態而暫時停止運行；
- 運行狀態（Running）：該時刻進程佔用 CPU；
- 阻塞狀態（Blocked）：該進程正在等待某一事件發生（如等待輸入/輸出操作的完成）而暫時停止運行，這時，即使給它CPU控制權，它也無法運行；
- 結束狀態（Exit）：進程正在從系統中消失時的狀態；
狀態轉移過程：
- NULL -> 創建狀態：創建一個新進程的初始狀態；
- 創建狀態 -> 就緒狀態：當進程被創建完成並初始化後，一切就緒準備運行時，變為就緒狀態，進入就緒隊列，等待被CPU調度。
- 就緒狀態 -> 運行狀態：處於就緒隊列中的進程被作業系統的進程調度器選中後，就分配給 CPU， 正式運行該進程；
- 運行狀態 -> 結束狀態：當進程已經運行完成或出錯時，會被作業系統作結束狀態處理，作業系統得從就緒隊列選擇另外一個進程運行；
- 運行狀態 -> 就緒狀態：處於運行狀態的進程在運行過程中，由於分配給它運行的時間片用完了，作業系統會把該進程變為就緒態，接著從就緒態選中另外一個進程運行；
- 運行狀態 -> 阻塞狀態：當進程請求某個事件且必須等待時，例如請求 I/O 事件，此時作業系統必須選擇另外一個進程運行；
- 阻塞狀態 -> 就緒狀態：當進程要等待的事件完成時，它從阻塞狀態變到就緒狀態；
在虛擬記憶體管理的作業系統中，通常會把阻塞狀態的進程的物理記憶體空間換出到硬碟，等需要再次運行的時候，再從硬碟換入到物理記憶體。這麼做，可以使得阻塞狀態的進程不會暫用物理記憶體空間，畢竟物理記憶體空間是有限的，被阻塞狀態的進程佔用著物理記憶體是一種浪費物理記憶體的行為。
此外，進程還有一個狀態來描述進程沒有佔用實際的物理記憶體空間：掛起狀態，該狀態又可細分為兩種：
- 阻塞掛起狀態：進程在外存（硬碟）並等待某個事件的出現；
- 就緒掛起狀態：進程在外存（硬碟），但只要進入記憶體，立刻運行；
導致進程掛起的原因不只是因為進程所使用的記憶體空間不在物理記憶體，還包括如下情況：
- 通過 sleep 讓進程間歇性掛起，其工作原理是設置一個定時器，到期後喚醒進程。
- 用戶希望掛起一個程式的執行，比如在 Linux 中用
Ctrl+Z掛起進程；
什麼叫調度
選擇一個進程佔用著 CPU 在運行，稱為調度。
什麼時候會調度
在進程的生命周期中，當進程從一個運行狀態切換為另一狀態時，就會觸發一次調度。
比如以下幾種狀態轉換時會觸發 CPU 調度：
- 就緒狀態 -> 運行狀態：當進程被創建時，會進入到就緒隊列，作業系統會從就緒隊列選擇一個進程運行；
- 運行狀態 -> 結束狀態：當進程正常運行完成或異常出錯時，會被作業系統作結束狀態處理，作業系統得從就緒隊列選擇另外一個進程運行；
- 運行狀態 -> 阻塞狀態：當進程請求某個事件且必須等待時，例如請求 I/O 事件，此時作業系統必須選擇另外一個進程運行；
調度演算法分類
- 搶佔式調度演算法（正在運行時可被打斷）
- 從就緒隊列中挑選一個進程，然後讓該進程只運行一段時間，如果在該時間段結束時，該進程還沒執行完，則會把它掛起，接著調度程式從就緒隊列挑選另外一個進程。
- 搶佔式調度處理，需要在時間間隔的末端發生時鐘中斷，以便把 CPU 控制返回給調度程式進行調度，也就是常說的時間片機制；
- 非搶佔式調度演算法：
- 從就緒隊列中挑選一個進程，然後讓該進程一直運行，直到該進程運行結束或被阻塞，才會調用另外一個進程，這種沒有時鐘中斷。
常見調度演算法有哪些
1️⃣ 先來先服務（FCFS）
最簡單的調度演算法，就是非搶佔式的先來先服務（First Come First Severd, FCFS）演算法了。
先來後到，每次從就緒隊列選擇最先進入隊列的進程，然後一直運行，直到進程退出或被阻塞，才會繼續從隊列中選擇第一個進程接著運行。
缺陷：
FCFS 對長作業/進程有利，適用於 CPU 繁忙型作業的系統，而不適用於 I/O 繁忙型作業的系統。
若進程是CPU繁忙型，則一旦佔有CPU，就可能會運行很長時間，因此CPU繁忙型作業類似於長作業，FCFS演算法對長作業/進程有利；
而對於I/O繁忙型進程作業，運行進程中要頻繁訪問I/O埠，即可能頻繁放棄CPU，所以佔用CPU的時間不會太長，一旦放棄CPU，則必須等待下次調度，因此FCFS演算法不利於它。
看個例子（王道）：
2️⃣ 最短作業優先（SJF）
最短作業優先（Shortest Job First, SJF），它會優先選擇運行時間最短的進程來運行，這有助於提高系統的吞吐量。
SJF是非搶佔式的演算法。但也有個搶佔式的版本：最短剩餘時間優先（Shortest Remaining Time Next, SRTN）。
缺陷：
對長作業不利，很容易造成一種極端現象，如果源源不斷地有短作業進程到來，可能會使得長作業進程長時間得不到服務，產生飢餓。
比如，一個 長作業/進程 在就緒隊列等待運行，而這個就緒隊列有非常多的短作業，那麼就會使得長作業不斷的往後推，周轉時間變長，致使 長作業進程 長期不會被運行（長作業進程飢餓）。
看個例子（王道）：
短作業優先
最短剩餘時間優先
3️⃣ 高響應比優先（HRRN）
非搶佔式的高響應比優先 （Highest Response Ratio Next, HRRN）演算法主要是權衡了短作業和長作業。
每次進行進程調度時，先計算「響應比優先順序」，然後運行「響應比優先順序」最高的進程，響應比優先順序計算公式如下：
\]
要求服務時間就是運行時間，一個任務的要求服務時間一般是固定的，而等待時間動態變化，等於從進入就緒隊列到被CPU調度這段時間
公式分析：
等待時間相同時，要求服務時間越短，優先順序越高，短作業進程容易被選中運行；
要求服務時間相同時，等待時間越長，優先順序越高，兼顧了長作業進程，避免長作業進程飢餓的問題；
看個例子（王道）：
4️⃣ 時間片輪詢（RR）
使用最廣的演算法就是時間片輪轉（Round Robin, RR）了。
每個進程被分配一個時間段，稱為時間片（Quantum），即允許該進程在該時間段中運行，
- 如果時間片用完，進程還在運行，那麼將會把此進程掛起，並把 CPU 分配另外一個進程（從就緒隊列選）；
- 如果該進程在時間片結束前阻塞或結束，則 CPU 立即切換到下一個進程；
缺陷：
1）如果時間片設置太短會導致頻繁地發生進程上下文切換，降低了 CPU 效率；
2）如果設置太長，可能引起對短作業進程的響應時間變長，一般時間片設為 20ms~50ms 是一個比較合理的折中值。
5️⃣ 最高優先順序調度（HPF）
每次 CPU 調度時都是從就緒隊列中選擇最高優先順序的進程運行，稱為最高優先順序（Highest Priority First，HPF）調度演算法。
該演算法也有兩種處理優先順序高的方法：
- 搶佔式：當就緒隊列中出現優先順序高的進程，當前進程掛起，調度優先順序高的進程運行；
- 非搶佔式：當就緒隊列中出現優先順序高的進程，運行完當前進程，再選擇優先順序高的進程；
缺陷：
可能會導致低優先順序的進程永遠不會運行。
6️⃣ 多級回饋隊列（MFQ）
多級回饋隊列（Multilevel Feedback Queue）調度演算法是「時間片輪轉演算法」和「最高優先順序演算法」的綜合和發展。
「多級」表示有多個就緒隊列，每個隊列優先順序從高到低，同時優先順序越高時間片越短；
「回饋」表示如果有新的進程加入優先順序高的就緒隊列時，立刻停止當前正在運行的進程，轉而去運行優先順序高的隊列；
工作方式（⚠⚠⚠）：
- 設置多個就緒隊列，每個隊列有著不同優先順序，每個隊列按優先順序從高到低排列，同時優先順序越高的隊列設置的時間片越短；
- 每次新的進程會被放入到第一級隊列（優先順序最高）的末尾，按先來先服務的原則排隊等待被調度，如果某個進程在第一級隊列設置的時間片內沒運行完，則將其轉入到第二級隊列的末尾，以此類推，直至完成；
- 當較高優先順序的隊列為空，才調度較低優先順序的隊列中的進程運行。如果進程運行時，有新進程進入較高優先順序的隊列（如就緒隊列3），則停止當前運行的進程（如就緒隊列5）並將其移入到原隊列末尾，接著讓較高優先順序的進程運行；
優點：
1）對於短作業可以在第一級隊列很快被處理完；
2）對於長作業，如果在第一級隊列處理不完，可以移入下級隊列等待被執行；
3）該演算法很好的兼顧了長短作業，同時有較好的響應時間。
小結
參考
//xiaolincoding.com/os/#小白適合看嗎
//blog.csdn.net/zh13487/article/details/83928284
//www.bilibili.com/video/BV1YE411D7nH
