算法調度

在計算中，算法調度是通過某種方式指定的工作被分配給完成工作的資源的方法。 該工作可以是虛擬計算元素，例如執行緒，進程或數據流，其又被調度到諸如處理器，網路連結或擴展卡之類的硬體資源上。

調度程式執行調度活動。 調度程式通常被實現，因此它們使所有計算機資源保持繁忙（如在負載平衡中），允許多個用戶有效地共享系統資源，或實現目標服務質量。 調度是計算本身的基礎，也是計算機系統執行模型的固有部分; 調度的概念使得可以使用單箇中央處理單元（CPU）進行計算機多任務處理。

基本介紹

• 中文名：算法調度
• 外文名：Algorithm scheduling

進程調度程式

進程調度程式是作業系統的一部分，用於決定在某個特定時間點運行哪個進程。它通常能夠暫停正在運行的進程，將其移動到正在運行的佇列的後面並啟動一個新進程;這樣的付淋舟承調度程式稱為搶先調度程式，否則它是一個協作調度程式。

長期調度

長期調度程式或許可調度程式決定允許哪些作業或進程進入就緒佇列（陵淋戒在主存儲器中）;也就是說，當嘗試執行程式時，其對當前正在執行的進程集的許可由長期調度程式授權或延遲。因此，這個調度程式決定了在系統上運行什麼進程，以及任何時候要支持的並發程度 - 是否要同時執行多個或幾個進墓汽立程，以及I/O密集型和CPU之間的分配方式-要處理密集的過程。長期調度程式負責控制多道程式的程度。

通常，大多數進程可以描述為I/O綁定或CPU綁定。I/O綁定進程是指花費更多時間進行I/O而不是進行計算的進程。相反，CPU綁定的進程不經常生成I/O請求，使用更多的時間進行計算。重要的是，長期調度程式選擇I/O綁定和CPU綁定進程的良好進程組合。如果所有進程都受I/O限制，則就緒佇列幾乎總是為空，短期調度程式幾乎沒有。另一櫃屑淚方面，如果所有進程都受CPU限制，則I/O等待佇列幾乎總是為空，設備將不使用，系統將再次失衡。因此，具有最佳性能的系統將具有CPU綁定和I/O綁定進程的組合。在現代作業系統中，這用於確保實時進程獲得足夠的CPU時間來完成任務。

長期調度在大規模系統中也很重要，例如批處理系統，計算機集群，超級計算機和渲染農場。例如，在並發系統中，通常需要對互動過程進行協同調度，以防止它們因為彼此等待而阻塞。在這些情況下，除了作業系統中的任何基礎準入調度支持之外，專用作業調度器軟體通常用於輔助這些功能。

中級調度

中期調度程式暫時從主記憶體中刪除進程並將它們放在輔助記憶體（例如硬碟驅動器）中，反之亦然，這通常被稱為“交換”或“交換”（也錯誤地稱為“分頁”）在“）中”或“分頁”。中期調度程式可能決定換出一段時間內未處於活動狀態的進程，或者具有低優先權的進程，或者頻繁發生頁面錯誤的進程，或者占用大量進程的進程。記憶體以便為其他進程釋放主記憶體，稍後當更多記憶體可用時，或者當進程被解除阻塞並且不再等待資源時，將進程交換回來。

在當今的許多系統中（那些支持將虛擬地址空間映射到除交換檔案之外的輔助存儲的系統），中期調度程式實際上可以通過將二進制檔案視為其上的“交換進程”來執行長期調度程式的角色請雅烏。執行。這樣，當需要一段二進制時，它可以按需交換，或“延遲載入”。

短期調度

短時調度程式（也稱為CPU調度程式）決定在時鐘中斷，I / O中斷，作業系統調用或其他形式之後要執行哪些就緒的記憶體中進程（分配CPU）信號因此，短期調度程式比長期或中期調度程式更頻繁地進行調度決策 - 調度決策至少必須在每個時間片之後進行，並且這些決策非常短。該調度程式可以是搶占式的，這意味著它能夠在CPU決定將CPU分配給另一個進程時強制從CPU中刪除進程，或者非搶占式（也稱為“自願”或“合作”），其中如果調度程式無法“強制”關閉CPU的進程。

搶占式調度程式依賴於可程式間隔計時器，該計時器調用在核心模式下運行的中斷處斷全局滲理程式並實現調度功能。

算法

先來先服務(FCFS)調度算法

FCFS是按戶朵照作業/進程進入系統的先後次序進行調度，先進入系統者先調度；即啟動等待時間最長的作業/進程。是一種最簡單的調度算法，即可用於作業調度，也可用於進程調度。

先來先服務（先進先出）優缺點
1、比較有利於長作業（進程），而不利於短作業（進程） 。
2、有利於CPU繁忙型作業（進程） ，而不利於I/O繁忙型作業（進程） 。
3、用於批處理系統，不適於分時系統。

短作業優先調度算法（SJF）

SJF是從佇列中選出一個估計運行時間最短的作業優先調度，即可用於作業調度，也可用於進程調度

SJF調度算法也存在不容忽視的缺點
1、對長作業不利。嚴重的是，若一長作業(進程)進入系統的後備佇列(就緒佇列)，由於調度程式總是優先調度那些(即使是後進來的)短作業(進程)，將導致長作業(進程)長期不被調度——飢餓。
2、完全未考慮作業(進程)的緊迫程度，因而不能保證緊迫性作業(進程)會被及時處理。
3、由於作業(進程)的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該算法不一定能真正做到短作業優先調度。

高回響比優先調度算法

高回響比優先調度算法既考慮作業的執行時間也考慮作業的等待時間，綜合了先來先服務和最短作業優先兩種算法的特點。

該算法中的回響比是指作業等待時間與運行比值,回響比公式定義如下：回響比 =(等待時間+要求服務時間)/要求服務時間

優點：等待時間相同的作業，則要求服務的時間愈短，其優先權愈高，對短作業有利。要求服務的時間相同的作業，則等待時間愈長，其優先權愈高，是先來先服務。長作業，優先權隨等待時間的增加而提高，其等待時間足夠長時，其優先權便可升到很高， 從而也可獲得處理機，對長作業有利。是一種折衷，既照顧了短作業，又考慮了作業到達的先後次序，又不會使長作業長期得不到服務。

缺點：要進行回響比計算，增加了系統開銷。
　　

簡單的時間片輪轉法(RR—Round Robin)

系統將所有的就緒進程按先來先服務的原則排成一個佇列，每次調度時，把CPU分配給隊首進程，並令其執行一個時間片；當執行的時間片用完時，由一個計時器發出時鐘中斷請求，調度程式便停止該進程的執行，並將其放就緒佇列尾；然後，再把處理機分配給就緒佇列中新的隊首；時間片的大小從幾ms到幾百ms 。

缺點：緊迫任務回響慢。 時間片選取 太小，會頻繁發生中斷、進程上下文切換，增加系統開銷，但利於短作業 太大，退化成FCFS —時間片應該略大於一次典型互動的時間。

搶占式調度程式依賴於可程式間隔計時器，該計時器調用在核心模式下運行的中斷處理程式並實現調度功能。

算法

先來先服務(FCFS)調度算法

FCFS是按照作業/進程進入系統的先後次序進行調度，先進入系統者先調度；即啟動等待時間最長的作業/進程。是一種最簡單的調度算法，即可用於作業調度，也可用於進程調度。

先來先服務（先進先出）優缺點
1、比較有利於長作業（進程），而不利於短作業（進程） 。
2、有利於CPU繁忙型作業（進程） ，而不利於I/O繁忙型作業（進程） 。
3、用於批處理系統，不適於分時系統。

短作業優先調度算法（SJF）

SJF是從佇列中選出一個估計運行時間最短的作業優先調度，即可用於作業調度，也可用於進程調度

SJF調度算法也存在不容忽視的缺點
1、對長作業不利。嚴重的是，若一長作業(進程)進入系統的後備佇列(就緒佇列)，由於調度程式總是優先調度那些(即使是後進來的)短作業(進程)，將導致長作業(進程)長期不被調度——飢餓。
2、完全未考慮作業(進程)的緊迫程度，因而不能保證緊迫性作業(進程)會被及時處理。
3、由於作業(進程)的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該算法不一定能真正做到短作業優先調度。

高回響比優先調度算法

高回響比優先調度算法既考慮作業的執行時間也考慮作業的等待時間，綜合了先來先服務和最短作業優先兩種算法的特點。

該算法中的回響比是指作業等待時間與運行比值,回響比公式定義如下：回響比 =(等待時間+要求服務時間)/要求服務時間

優點：等待時間相同的作業，則要求服務的時間愈短，其優先權愈高，對短作業有利。要求服務的時間相同的作業，則等待時間愈長，其優先權愈高，是先來先服務。長作業，優先權隨等待時間的增加而提高，其等待時間足夠長時，其優先權便可升到很高， 從而也可獲得處理機，對長作業有利。是一種折衷，既照顧了短作業，又考慮了作業到達的先後次序，又不會使長作業長期得不到服務。

缺點：要進行回響比計算，增加了系統開銷。
　　

簡單的時間片輪轉法(RR—Round Robin)

系統將所有的就緒進程按先來先服務的原則排成一個佇列，每次調度時，把CPU分配給隊首進程，並令其執行一個時間片；當執行的時間片用完時，由一個計時器發出時鐘中斷請求，調度程式便停止該進程的執行，並將其放就緒佇列尾；然後，再把處理機分配給就緒佇列中新的隊首；時間片的大小從幾ms到幾百ms 。

缺點：緊迫任務回響慢。 時間片選取 太小，會頻繁發生中斷、進程上下文切換，增加系統開銷，但利於短作業 太大，退化成FCFS —時間片應該略大於一次典型互動的時間。