作業系統原理：程序排程

程序是作業系統資源配置設定和排程的基本機關，也是作業系統的基礎結構。如果說程式是指令、資料及其組織形式的描述，那麼程序是程式的實體。

本文簡單介紹了程序排程的意義，以及幾種常見的程序排程算法的簡單原理及優缺點。

程序排程的任務

1. 儲存處理機的現場資訊：在排程其他程序之前先要儲存目前程序的現場資訊，比如寄存器中的内容等
2. 按照算法選取程序：按照某種算法選擇就緒隊列中的一個程序，将其狀态改為運作狀态然後為其配置設定處理機資源
3. 配置設定處理機資源給程序：配置設定處理器給程序，比如将程序的控制塊中有關資訊寫入處理器相應的寄存器，讓程序從上一次斷點開始運作

排程方式

1. 非搶占式：該方式一旦處理器被配置設定給一個程序就無法被其他程序剝奪。隻有目前程序結束後釋放資源或者目前程序阻塞其他程序才能使用處理器資源。
2. 搶占式：這種方式下系統會根據某種原則暫停目前程序，進而把處理器資源讓給其他程序。這樣可以防止一個程序長時間占用系統資源。資源搶占的原則有：優先權原則、短程序優先原則、時間片原則幾種。

短程序優先和先來先服務（FCFS）

程序的短程序優先和FCFS與作業排程相似，在此不做介紹。

參考：作業與作業排程

時間片輪轉排程算法

時間片輪轉算法是分時系統中常見的程序排程算法。該算法采用了非常公平的排程方式，即每個程序都享有相同的運作時間片長度，時間片結束就必須将資源讓給下一個程序。這樣每一個程序都能平均的占有處理器。

基本原理：系統從就緒隊列隊首排程一個程序，并在一個時間片後自動中斷。如果目前程序沒有完成，就将它轉入就緒隊列隊尾，然後排程就緒隊列的新程序。如果程序在時間片内已經完成，就在程序完成時中斷，排程就緒隊列的新程序。

程序切換時機：根據原理，我們可以發現程序隻會在兩種情況下切換：(1)時間片結束，切換新的程序；(2)程序完成而時間片還未結束，排程新程序，開啟新時間片

時間片長度的确定：時間片長度的确定決定了時間片輪轉法的優異性。比如說時間片太長，就失去了輪轉的意義，該算法就會與FCFS算法相同；如果時間片太短，就會導緻系統中斷和程序排程頻繁，增加了系統開銷。是以确定一個合适的時間片大小很重要，它将決定輪轉算法的效率。

優先級排程算法

非搶占式優先級排程：該算法規定一旦将處理機資源配置設定給就緒隊列中的高優先級程序，就必須等到該程序結束或阻塞才能把資源釋放。

搶占式優先級排程：把處理機優先配置設定給高優先級程序，如果執行過程中有更高優先級程序就緒，會中斷目前程序把資源配置設定給更高優先級程序

靜态優先級：靜态優先級是在程序建立時就确定的，無法改變。确定靜态優先級的依據有：（1）程序類型：比如系統程序優先級往往高于使用者程序；（2）程序對資源需求：往往需求資源少的程序優先級高；（3）使用者需求：根據使用者程序緊迫程度确定優先級

動态優先級：動态優先級會在程序建立時先賦予一個初始值，但是根據後來的等待情況等會動态調節。高響應比算法就是典型的動态優先級，它會根據程序等待時間和所需服務時間動态調節。

多隊列排程算法

前面所述的各種算法，因為系統隻設定了一個就緒隊列，即排程算法是固定的、單一的，是以無法滿足使用者的不同排程政策。這裡引入了多隊列排程算法來解決這個問題。顧名思義多隊列就是多個就緒隊列，每個隊列對應一類程序和一種排程算法。這樣就針對不同的使用者需求提供了多種排程政策

多級回報隊列(multileved feedback queue)排程算法

前面的各種排程算法有局限性，即在未提供程序長度時短程序優先等基于程序長度的算法都無法使用。而多級隊列回報排程算法就解決了這個問題。

1.排程機制

（1）設定多個就緒隊列，并為每個隊列設定遞減的優先級。同時每個隊列的時間片也不同，越高優先級的隊列的時間片越短

（2）每個隊列采取先來先服務（FCFS）政策，隊列中的程序按照FCFS政策和時間片輪轉法排程。

（3）按照隊列優先級排程隊列，先為高優先級隊列配置設定處理器資源。