順序調度

調度在計算機中是分配工作所需資源的方法。在後備隊列上等待的每個作業都需經過調度才能執行。在傳統的操作系統中，包括作業調度和進程調度兩步。

(1) 作業調度。作業調度的基本任務是從後備隊列中按照一定的算法，選擇出若干個作業，為它們分配運行所需的資源(首先是分配內存)。在將它們調入內存後，便分別為它們建立進程，使它們都成為可能獲得處理機的就緒進程，並按照一定的算法將它們插入就緒隊列。

(2) 進程調度。進程調度的任務是從進程的就緒隊列中，按照一定的算法選出一個進程，把處理機分配給它，併為它設置運行現場，使進程投入執行。值得提出的是，在多線程OS中，通常是把線程作為獨立運行和分配處理機的基本單位，為此，須把就緒線程排成一個隊列，每次調度時，是從就緒線程隊列中選出一個線程，把處理機分配給它。

調度的主要功能是根據作業控制塊中的信息，審查系統能否滿足用户作業的資源需求，以及按照一定的算法，從外存的後備隊列中選取某些作業調入內存，併為它們創建進程、分配必要的資源。然後再將新創建的進程插入就緒隊列，準備執行。因此，有時也把作業調度稱為接納調度(Admission Scheduling)。

對用户而言，總希望自己作業的週轉時間儘可能的少，最好週轉時間就等於作業的執行時間。然而對系統來説，則希望作業的平均週轉時間儘可能少，有利於提高 CPU 的利用率和系統的吞吐量。為此，每個系統在選擇作業調度算法時，既應考慮用户的要求，又能確保系統具有較高的效率。在每次執行作業調度時，都須做出以下兩個決定。

作業調度每次要接納多少個作業進入內存， 取決於多道程序度(Degree of Multiprogramming)，即允許多少個作業同時在內存中運行。當內存中同時運行的作業數目太多時，可能會影響到系統的服務質量，比如，使週轉時間太長。但如果在內存中同時運行作業的數量太少時，又會導致系統的資源利用率和系統吞吐量太低，因此，多道程序度的確定應根據系統的規模和運行速度等情況做適當的折衷。

應將哪些作業從外存調入內存，這將取決於所採用的調度算法。最簡單的是先來先服務調度算法，這是指將最早進入外存的作業最先調入內存；較常用的一種算法是短作業優先調度算法，是將外存上最短的作業最先調入內存；另一種較常用的是基於作業優先級的調度算法，該算法是將外存上優先級最高的作業優先調入內存；比較好的一種算法是“響應比高者優先”的調度算法。

先來先服務(FCFS)調度算法是一種最簡單的調度算法，該算法既可用於作業調度，也可用於進程調度。當在作業調度中採用該算法時，每次調度都是從後備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然後放入就緒隊列。 在進程調度中採用 FCFS 算法時， 則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞後才放棄處理機。

在早期的時間片輪轉法中，系統將所有的就緒進程按先來先服務的原則排成一個隊列，每次調度時，把 CPU 分配給隊首進程，並令其執行一個時間片。時間片的大小從幾 ms 到幾百 ms。當執行的時間片用完時，由一個計時器發出時鐘中斷請求，調度程序便據此信號來停止該進程的執行，並將它送往就緒隊列的末尾；然後，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒隊列中的所有進程在一給定的時間內均能獲得一時間片的處理機執行時間。換言之，系統能在給定的時間內響應所有用户的請求。 ^[1] 

在時間片輪轉算法中，時間片的大小對系統性能有很大的影響，如選擇很小的時間片將有利於短作業，因為它能較快地完成，但會頻繁地發生中斷、進程上下文的切換，從而增加系統的開銷；反之，如選擇太長的時間片，使得每個進程都能在一個時間片內完成，時間片輪轉算法便退化為 FCFS 算法， 無法滿足交互式用户的需求。 一個較為可取的大小是，時間片略大於一次典型的交互所需要的時間。這樣可使大多數進程在一個時間片內完成。

多級反饋隊列調度算法既能使高優先級的作業得到響應又能使短作業（進程）迅速完成。（對比一下FCFS與高優先響應比調度算法的缺陷）調度算法的實施過程如下所述：

(1) 應設置多個就緒隊列， 併為各個隊列賦予不同的優先級。 第一個隊列的優先級最高，第二個隊列次之，其餘各隊列的優先權逐個降低。該算法賦予各個隊列中進程執行時間片的大小也各不相同，在優先權愈高的隊列中，為每個進程所規定的執行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第 i+1 個隊列的時間片要比第 i 個隊列的時間片長一倍。

(2) 當一個新進程進入內存後，首先將它放入第一隊列的末尾，按 FCFS 原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按 FCFS原則等待調度執行；如果它在第二隊列中運行一個時間片後仍未完成，再依次將它放入第三隊列，……，如此下去，當一個長作業(進程)從第一隊列依次降到第 n 隊列後，在第 n 隊列中便採取按時間片輪轉的方式運行。

(3) 僅當第一隊列空閒時，調度程序才調度第二隊列中的進程運行；僅當第 1～(i-1)隊列均空時，才會調度第 i 隊列中的進程運行。如果處理機正在第 i 隊列中為某進程服務時，又有新進程進入優先權較高的隊列(第 1～(i-1)中的任何一個隊列)，則此時新進程將搶佔正在運行進程的處理機， 即由調度程序把正在運行的進程放回到第 i 隊列的末尾，把處理機分配給新到的高優先權進程。