程序排程演算法有哪些型別？哪些演算法會導致飢餓現象？

程序排程程式根據特定的排程演算法將不同的程序分配給CPU。

程序排程演算法的型別

程序排程演算法的不同型別如下：

先來先服務 (FCFS)

顧名思義，作業按照先來先服務的原則執行。這是一種基於FIFO（先進先出）的簡單演算法。它是搶佔式和非搶佔式的，其效能基於平均等待時間較差。

最短作業優先 (SJF)

它也被稱為最短作業優先或下一個最短作業。這是一種搶佔式和非搶佔式演算法，易於在批處理系統中實現，並且最擅長最小化等待時間。

輪詢排程

這是一種搶佔式排程演算法，其中每個程序都被賦予一個固定的執行時間，稱為時間片。在這個時間內，允許一個程序執行一個時間片，然後被搶佔，然後執行其他程序。透過這種方式，程序之間會進行上下文切換以儲存這些被搶佔程序的狀態。

優先順序排程

這是一種非搶佔式演算法，在批處理系統中工作，其中每個程序都被賦予一個優先順序，優先順序最高的程序首先執行，其他程序則根據優先順序執行，這可能會導致某些程序出現飢餓現象。

最短剩餘時間優先

此演算法基於SJF，是它的搶佔式版本，剩餘時間最短的程序首先執行。換句話說，最接近完成的程序首先執行，它可能會被一個具有更短執行時間的新的就緒作業搶佔。

多級佇列排程

在此排程中，多個佇列具有自己的排程演算法，並與具有相同特徵的程序一起維護。為此，為要執行的作業分配給每個佇列優先順序。

以上所有演算法都可以是搶佔式或非搶佔式的。這意味著在搶佔式程序中，如果高優先順序程序進入就緒佇列，排程程式可以搶佔低優先順序正在執行的程序。而在非搶佔式程序中，一旦程序進入執行狀態，就不能被搶佔。

導致飢餓的演算法

現在在SJF中，如果出現較長的程序，則它們必須等待更長時間，因此這會遭受飢餓。在輪詢排程中，由於每個程序都被賦予時間片或固定的執行時間，因此沒有飢餓的可能性。

在優先順序排程中，低優先順序的較長程序保持等待狀態，因此優先順序排程會發生飢餓，因為只有高優先順序程序快速執行，而低優先順序程序仍然等待。

在FCFS中，無論是較長程序還是較短程序，都沒有飢餓的可能性。最終，每個程序都會按照先來先服務的原則執行。

Bhanu Priya

更新於：2021年11月30日

4K+ 次瀏覽

啟動您的職業生涯

透過完成課程獲得認證

開始