程序的排程

程序的排程是由作業系統完成的，其目的是為了在一個程序佔用CPU執行自己的操作後，選擇下一個程序來佔用CPU。排程發生的原因很簡單，每個程序都希望能夠佔用CPU進行工作。因此，排程程式會進行上下文切換，並選擇一個程序來執行其功能。

那麼，什麼時候進行排程呢？排程的原則又是什麼呢？

什麼時候排程程序

程序的排程可以理解為在程序的狀態發生變化時進行。以下是一些程序狀態的範例：

• 就緒態 -> 執行態：當一個程序被建立後，它進入就緒佇列中等待執行。當作業系統從就緒佇列中選擇一個程序時，它進入執行態並開始執行。
• 執行態 -> 阻塞態：當一個程序執行I/O操作時，它可能會進入阻塞態，等待I/O操作完成。此時，作業系統會將當前程序放入阻塞佇列，並切換到其他可執行的程序繼續執行。
• 執行態 -> 結束態：當一個程序完成其任務或遇到終止指令時，它會進入結束態。作業系統會從就緒佇列中選擇下一個程序進行執行。

因為程序的狀態發生變化時，作業系統需要考慮是否切換程序來佔用CPU執行業務。因此，只要程序狀態發生變化，就會觸發程序排程。

以什麼原則來排程程序

程序排程的原則主要有以下五種：

CPU利用率：排程程式應始終保持CPU處於繁忙狀態執行，以提高CPU的利用率。

系統吞吐率：系統吞吐率是指在一定時間內完成的程序數量。排程程式應儘量選擇能夠快速完成的程序，以提高系統的吞吐率。

週轉時間：指一個程序從建立到完成的總時間。排程程式應儘量減少程序的週轉時間，以提高系統的效率。也可以這麼理解：週轉時間的計算公式為：週轉時間 = 完成時間 - 建立時間；

等待時間：等待時間並不是所謂的阻塞時間，而是在就緒佇列中等待被執行的時間；

響應時間：指使用者發出請求後系統作出響應的時間。使用者與其互動這之間所產生的消耗時間越少，響應越好；

就是一句話，程序越快越短越好；

程序排程演演算法

排程演演算法基本分為兩類：非搶佔式排程演演算法、搶佔式的排程演演算法；

非搶佔式排程演演算法：這個演演算法就是之前說的所有程序都進行排隊等待，只有前面的程序都執行完了或者自己主動讓出CPU，才可以輪到後面的程序執行。常見的非搶佔式演演算法有：先來先服務（FCFS，First-Come, First-Served）和短作業優先（SJF，Shortest Job First）等。

搶佔式排程演演算法：也就是時間片機制，每個程序都只佔用CPU的一個時間片操作，執行完了就必須讓出CPU使用許可權給下一個程序使用。常見的搶佔式演演算法有：輪轉排程（Round Robin）、最短剩餘時間優先（SRTF，Shortest Remaining Time First）和優先順序排程等。

接下來我們詳細看下各個排程演演算法的優劣：

先來先服務

這個是一種最簡單的程序排程演演算法，所有程序按照到達時間的先後順序排隊，先到達的程序先被排程執行。這種排程演演算法類似於Java中的佇列，採用先進先出（FIFO）的原則。

這種排程演演算法存在一個明顯的問題，即如果一個程序執行時間較長，後面的程序就必須等待。

時間片輪轉排程

時間片輪轉排程是一種常見的程序排程演演算法，它將CPU時間劃分為固定大小的時間片（也稱為時間量），每個程序在一個時間片內執行，如果時間片用完後仍未執行完，則被移至就緒佇列的末尾，等待下一輪排程。雖然解決了排隊產生的問題，但是時間片如何劃分呢？如果時間片過長，可能會導致資源浪費，因為某些程序可能只需要很短的時間就能執行完畢，但它們仍然會佔用整個時間片。另一方面，如果時間片過短，會導致程序切換的頻率增加，增加了上下文切換的開銷，可能降低系統的效能。因此時間片的長度，需要有大致合理的數值。（《現代作業系統》的觀點是建議時間片長度在20ms~50ms）。

最短作業優先

最短作業優先排程演演算法是一種非搶佔式的排程演演算法，它根據程序的執行時間長短進行排隊，將作業時間短的程序排在前面先執行。

我都不知道程序的執行時間長短的，系統咋知道的？其實系統通過預估程序的執行時間來進行排程，一般可以使用過去的歷史執行時間進行估算。但是預估的準不準呢，那肯定不準，所以問題來了，預估的準確性是一個問題。如果預估不準確，可能會導致程序的等待時間增加或者執行時間不均衡。如果短時間的程序一直在排在前面執行，那麼長時間的程序可能會一直等待執行的機會。

最短剩餘時間優先

他是搶佔式的排程演演算法，可以利用CPU的時間片機制，是基於最短作業優先演演算法的改進版本。該演演算法會根據程序的剩餘執行時間進行排隊，將剩餘執行時間最短的程序優先執行。但是這個時間也是預估的而且每個程序的剩餘執行時間需要進行實時監控和計算。

如果沒有時間片的限制，SRTF演演算法會變成最短作業優先演演算法，因為每個程序都能從頭到尾一次性執行完畢。

優先順序排程

它根據程序的優先順序來確定執行順序。每個程序都有一個優先順序值，通常在建立程序時由作業系統分配。如果多個程序的優先順序相同，則按照先來先服務（FIFO）的方式依次執行。程序的優先順序一般都已經由作業系統在建立的時候都已經設定好了的，如果硬要設定的話，可以去工作管理員看看；

優先順序排程可以細分為搶佔式和非搶佔式；這個就不用說了，我單獨說下搶佔式，在搶佔式優先順序排程中，如果有高優先順序的程序到達，當前正在執行的程序會被中斷，讓高優先順序的程序先執行。

所以說他仍然有點問題，那就是低優先順序的程序需要排很長時間的隊才可以執行；

多級反饋佇列排程

多級反饋佇列排程是一種綜合了優先順序排程和時間片輪轉排程的程序排程演演算法。它通過多個就緒佇列按照優先順序和時間片的不同來排列程序，以實現更加靈活和高效的排程，但是他並不是按照優先順序依次進入就緒佇列的，而是都在第一級佇列開始執行，執行完就放入第二級佇列，依次往下排而已，這個優先順序只是單獨對於就緒佇列來講的並不是程序的優先順序；

他就兼顧了長短作業的場景，因為短作業很可能在前面的就緒佇列中已經執行完了，而後面的長作業佔用的CPU時間片也更長了。

這個演演算法類比銀行辦手續的場景：

• 銀行大廳中本身三個排隊佇列，佇列1優先順序最高但是辦理的時間卻是最短的，這也對應著優先順序越高時間片越短；
• 新來的客戶都先進入佇列1叫號排隊，但是隻辦理1分鐘的業務，辦理不完的客戶都去佇列2依次排隊，當佇列1中的客戶全辦理完之後，工作人員開始處理佇列2中的客戶，然後依次排隊，直至佇列中的程序都處理完畢為止；
• 但是如果在辦理其他佇列的過程中又有新客戶來了，則會終止當前客戶的辦理並重新進入對尾排隊，工作人員會立馬處理佇列1中的客戶。

可以發現，對於要辦理短業務的客戶來說，可以很快的輪到並解決。對於要辦理長業務的客戶，一下子解決不了，就可以放到下一個佇列，雖然等待的時間稍微變長了，但是輪到自己的辦理時間也變長了，

多級反饋佇列排程演演算法兼顧了優先順序和時間片的特點，能夠適應不同型別的程序和任務。通過合理設定每個佇列的優先順序和時間片長度，可以根據實際情況提高系統的執行效率和響應速度。

總結

程序排程是作業系統中重要的任務之一。排程程式根據程序的狀態變化，選擇下一個程序來佔用CPU執行任務。排程的原則包括CPU利用率、系統吞吐率、週轉時間、等待時間和響應時間等。排程演演算法分為非搶佔式和搶佔式兩種型別，其中常見的演演算法包括先來先服務、時間片輪轉、最短作業優先、最短剩餘時間優先、優先順序排程和多級反饋佇列排程。每種演演算法都有其優點和缺點，