調度在計算機中是分配工作所需資源的方法。資源可以指虛擬的計算資源，如執行緒、進程或數據流；也可以指硬體資源，如處理器、網路連線或擴展卡。順序調度是指採用順序原則進行任務或作業的調度。常見的順序調度算法有先來先服務調度算法、基於時間片的輪轉調度算法。
基本介紹
- 中文名：順序調度
- 外文名：Sequential Scheduling
- 學科：作業系統
- 定義：採用順序原則進行調度
- 有關術語：調度
- 領域：處理機管理
調度,調度有關因素,決定接納多少個作業,決定接納哪些作業,有關順序調度算法,先來先服務調度算法,時間片輪轉法,多級反饋佇列調度算法,
調度
調度在計算機中是分配工作所需資源的方法。在後備佇列上等待的每個作業都需經過調度才能執行。在傳統的作業系統中，包括作業調度和進程調探臘巴度兩步。
(1) 作業調度。作業調度的基本任務是從後備佇列中按照一定的算法，選擇出若干個作業，為它們分配運行所需的資源(首先是分配記憶體)。在將它們調入記憶體後，便分別為它們建立進程，使它們都成為可能獲得處理機的就緒進程，並按照一定的算法將它們插入就緒佇列。
(2) 進程調度。進程調度的任務是從進程的就緒佇列中，按照一定的算法選出一個進程，把處理機分配給它，並為它設定運行現場，使進程投入執行。值得提出的是，在多執行緒OS中，通常是把執行緒作為獨立運行和分配處理機的基本單位，為此，須把就緒執行緒排成一個佇列，每次調度時，是從就緒執行緒佇列中選出一個執行緒，把處理機分配給它。
調度有關因素
調度的主要功能是根據作業控制塊中的信息，審查系統能否滿足用戶作業的資源需求，以及按照一定的算法，從外存的後備佇列中選取某些作業調入記憶體，並為它們創建進程、分配必要的資源。然後再將新創建的進程插入就緒佇列，準備執行。因此，有時也把作業調度稱為接納調度(Admission Scheduling)。
對用戶而言達敬只，總希望自己作業的周轉時間儘可能的少，最好周轉時間就等於作業的執行時間。然而對系統來說，則希望作業的平均周轉時間儘可能少，有利於提高 CPU 的利用率和系統的吞吐量。為此，每灶背講遷個系統在選擇作業調度算法時，既應考慮用戶的要求，又能確保系統具有較高的效率。在每次執行作業調度時，祝舉都須做出以下兩個決定。
決定接納多少個作業
作業調度每次要接納多少個作業進入記憶體， 取決於多道程式度(Degree of Multiprogramming)，即允許多少個作業同時在記憶體中運行。當記憶體中同時運行的作業數目太多時，可能會影響到系統的服務質量，比如，使周轉時間太長。但如果在記憶體中同時運行作業的數量太少時，又會導致系統的資源利用率和系統吞吐量太低，因此，多道程式度的確定應根據系統的規模和運行速度等情況做適當的折衷。
決定接納哪些作業
應將哪些作業從外存調入記憶體，這將取決於所採用的調度算法。最簡單的是先來先服務調度算法，這是指將最早進入外存的作業最先調入記憶體；較常用的一種算法是短作業優先調度算法，是將外存上最短的作業最先調入記憶體；另一種較常用的是基於作業優先權的調度算法，該算法是將外存上優先權最高的作業優先調入記憶體；比較好的一種算法是“回響比高者優先”的調度算法。
有關順序調度算法
先來先服務調度算法
先來先服務(FCFS)調度算法是一種最簡單的調度算法，該算法既可用於作業調度，也可用於進程調度。當在作業調度中採用該算法時，每次調度都是從後備作業佇列中選擇一個或多個最先進入該佇列的作業，將它們調入記憶體，為它們分配資源、創建進程，然後放入就緒佇列。 在進程調度中採用 FCFS 算法時， 則每次調度是從就緒佇列中選擇一個最先進入該佇列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞後才放棄處理機。
時間片輪轉法
基本原理
在早期的時間片輪轉法中，系統將所有的就緒進程按先來先服務的原則排成一個佇列，每次調度時，把 CPU 分配給隊首進程，並令晚贈鞏其執行一個時間片。時間片的大小從幾 ms 到幾百 ms。當執行的時和全才間片用完時，由一個計時器發出時鐘中斷請求，調度程式便據此信號來停止該進程的執行，並將它送往就緒佇列的末尾；然後，再把處理機分配給就緒佇列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒佇列中的所有進程在一給定的時間內均能獲得一時間片的處理機執行時間。換言之，系統能在給定的時間內回響所有用戶的請求。
時間片大小的確定
在時間片輪轉算法中，時間片的大小對系統性能有很大的影響，如選擇很小的時間片將有利於短作業，因為它能較快地完成，但會頻繁地發生中斷、進程上下文的切換，從而增加系統的開銷；反之，如選擇太長的時間片，使得每個進程都能在一個時間片內完成，時間片輪轉算法便退化為 FCFS 算法， 無法滿足互動式用戶的需求。 一個較為可取的大小是，時間片略大於一次典型的互動所需要的時間。這樣可使大多數進程在一個時間片內完成。
多級反饋佇列調度算法
(1) 應設定多個就緒佇列， 並為各個佇列賦予不同臘探虹朵的優先權。 第一個佇列的優先權最高，第二個佇列次之，其餘各佇列的優先權逐個降低。該算法賦予各個佇列中進程執行時間片的大小也各不相同，在優先權愈高的佇列中，為每個進程所規定的執行時間片就愈小。例如，第二個佇列的時間片要比第一個佇列的時間片長一倍，……，第 i+1 個佇列的時間片要比第 i 個佇列的時間片長一倍。
(2) 當一個新進程進入記憶體後，首先將它放入第一佇列的末尾，按 FCFS 原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，調度程式便將該進程轉入第二佇列的末尾，再同樣地按 FCFS原則等待調度執行；如果它在第二佇列中運行一個時間片後仍未完成，再依次將它放入第三佇列，……，如此下去，當一個長作業(進程)從第一佇列依次降到第 n 佇列後，在第 n 佇列中便採取按時間片輪轉的方式運行。
(3) 僅當第一佇列空閒時，調度程式才調度第二佇列中的進程運行；僅當第 1～(i-1)佇列均空時，才會調度第 i 佇列中的進程運行。如果處理機正在第 i 佇列中為某進程服務時，又有新進程進入優先權較高的佇列(第 1～(i-1)中的任何一個佇列)，則此時新進程將搶占正在運行進程的處理機， 即由調度程式把正在運行的進程放回到第 i 佇列的末尾，把處理機分配給新到的高優先權進程。
時間片輪轉法
基本原理
在早期的時間片輪轉法中，系統將所有的就緒進程按先來先服務的原則排成一個佇列，每次調度時，把 CPU 分配給隊首進程，並令其執行一個時間片。時間片的大小從幾 ms 到幾百 ms。當執行的時間片用完時，由一個計時器發出時鐘中斷請求，調度程式便據此信號來停止該進程的執行，並將它送往就緒佇列的末尾；然後，再把處理機分配給就緒佇列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒佇列中的所有進程在一給定的時間內均能獲得一時間片的處理機執行時間。換言之，系統能在給定的時間內回響所有用戶的請求。
時間片大小的確定
在時間片輪轉算法中，時間片的大小對系統性能有很大的影響，如選擇很小的時間片將有利於短作業，因為它能較快地完成，但會頻繁地發生中斷、進程上下文的切換，從而增加系統的開銷；反之，如選擇太長的時間片，使得每個進程都能在一個時間片內完成，時間片輪轉算法便退化為 FCFS 算法， 無法滿足互動式用戶的需求。 一個較為可取的大小是，時間片略大於一次典型的互動所需要的時間。這樣可使大多數進程在一個時間片內完成。
多級反饋佇列調度算法
(1) 應設定多個就緒佇列， 並為各個佇列賦予不同的優先權。 第一個佇列的優先權最高，第二個佇列次之，其餘各佇列的優先權逐個降低。該算法賦予各個佇列中進程執行時間片的大小也各不相同，在優先權愈高的佇列中，為每個進程所規定的執行時間片就愈小。例如，第二個佇列的時間片要比第一個佇列的時間片長一倍，……，第 i+1 個佇列的時間片要比第 i 個佇列的時間片長一倍。
(2) 當一個新進程進入記憶體後，首先將它放入第一佇列的末尾，按 FCFS 原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，調度程式便將該進程轉入第二佇列的末尾，再同樣地按 FCFS原則等待調度執行；如果它在第二佇列中運行一個時間片後仍未完成，再依次將它放入第三佇列，……，如此下去，當一個長作業(進程)從第一佇列依次降到第 n 佇列後，在第 n 佇列中便採取按時間片輪轉的方式運行。
(3) 僅當第一佇列空閒時，調度程式才調度第二佇列中的進程運行；僅當第 1～(i-1)佇列均空時，才會調度第 i 佇列中的進程運行。如果處理機正在第 i 佇列中為某進程服務時，又有新進程進入優先權較高的佇列(第 1～(i-1)中的任何一個佇列)，則此時新進程將搶占正在運行進程的處理機， 即由調度程式把正在運行的進程放回到第 i 佇列的末尾，把處理機分配給新到的高優先權進程。
