排程(英語:Scheduling)在電腦中是分配工作所需資源的方法。資源可以指虛擬的計算資源,如線程行程數據流;也可以指硬件資源,如處理器、網絡連接或擴充卡

進行排程工作的程式叫做排程器。排程器通常的實現使得所有計算資源都處於忙碌狀態(在負載均衡中),允許多位用戶有效地同時共用系統資源,或達到指定的服務質素。排程是計算自身的基礎,同時也是程式語言計算模型原生的部分。排程器使得在單處理器上通過多工處理,從而讓執行多個行程成為可能。

排程器可能會針對不同的目標設計,例如:吞吐率最大化、響應時間最小化、最低延遲[1]、或最大化公平。在實踐中,這些目標通常是互相衝突的,因此,排程器會實現一個權衡利弊的折中方案,而側重點則可能是前文提到的任何一種,這取決於用戶的需求和目的。

在即時環境,例如工業上用於自動控制(如機械人)的嵌入式系統,排程器必須保證行程的排程不能超過最後期限 —— 這是保持系統穩定執行的關鍵因素。排程也可能是通過一個管理性的後端進行,而任務是通過網絡發配到若干遠端裝置上的。

作業系統排程器的種類

排程器是作業系統的一個模組,它能夠選擇將被系統處理的下一個任務,或執行的下一個行程。作業系統可能會提供三種不同類型的排程器:長期排程器、中期排程器和短期排程器。這些名字表明了任務被執行的頻率。

行程排程器

行程排程器是作業系統的一部分,決定了何時執行什麼行程。它通常能夠暫停一個執行中的行程,將它放回到執行佇列當中,並執行一個新行程,我們把這樣的排程器叫做搶佔排程器。否則,它就是協同排程器。

長期排程器

長期排程器,決定了任務或行程是否會被就緒佇列(主記憶體中)所接納。當一個執行程式的嘗試被做出後,長期排程器或允許,或是延遲將它作為當前執行的一個行程。因此,這種排程器掌控着能在系統上執行的行程。排程器同時還決定並行的程度:同時執行程式的多少,在I/O密集型和CPU密集型行程之前做出劃分。

通常,大多數行程可以分為I/O密集型[2]和CPU密集型。I/O密集型程式將大多數時間都花在了I/O操作而不是運算上,而CPU密集型程式正好相反,將大多數時間花在了運算上,而很少產生I/O操作。選出一個I/O密集型和CPU密集型程式的良好組合,對於長期排程器是非常重要的。否則,假如所有的程式都是CPU密集型的,那麼I/O佇列將會幾乎永遠都是空的,這樣就會導致一些裝置從來沒被人用過,系統資源分配就是不均衡的。顯然,效能極佳的系統必然是CPU密集型和I/O密集型程式的組合。在現代作業系統中,這被用來保證即時行程能獲得足夠的CPU時間來完成任務。[3]

長期排程對大型系統,例如批次處理系統、電腦叢集、超級電腦和彩現場來說同樣重要。例如,在並行系統中,為了避免互動的多個行程,把時間都花在等待對方而產生阻塞,通常是需要進行協同排程的。在這種情況下,處理作業系統底層的排程器之外,還需要符合要求的額外排程程式來實現必要的功能。

中期排程器

中期排程器臨時將行程從主記憶體中去除,放入第二儲存裝置(如硬碟)中,或亦而反之。這通常被稱為「換出」和「換入」(同時也被錯誤叫做「分頁入」和「分頁出」)。中期排程器可能會將那些一直不活躍的行程,優先級低的行程,頻繁產生頁錯誤的行程,或者佔用大量主記憶體的行程放入交換區,為其它程式釋放主記憶體。當系統主記憶體充足時,或者程式不再處於阻塞狀態時,排程器又會將剛剛被放入交換區中的行程重新放入主記憶體中。

短期排程器

短期排程器(也就是CPU排程器)決定了在一個時鐘中斷、I/O中斷、系統呼叫其它種類的訊號之後,應該執行(分配CPU)給哪些主記憶體中的行程。可見,短期排程器作出決定的頻率比長期或中期排程器更加頻繁 —— 每隔一段非常短的固定時間,排程器就將做出一次決定。這種排程器可以是搶佔式的,能夠強行把一個在CPU執行中的程式中斷,然後分配給其它行程;也可以是非搶佔式的,這類排程器無法強行把行程從CPU上中斷。

搶佔式排程器的功能需要一個執行在內核態,能被中斷處理程式擷取的可程式化定時器才能實現。

排程規則

排程規則就是在同時佔用資源的多方之間進行資源分配的演算法。在路由器作業系統硬碟印表機,大多數嵌入式系統等裝置中,都能看到排程規則的應用。

排程演算法的主要目標,是使資源飢餓最小化,並保證使用資源多方的公平性。排程器需要處理在大量請求下如何分配資源的難題。排程演算法種類很多,在這一章,將會介紹幾種常見演算法。

封包交換的電腦網絡和其它統計多路復用領域,需要一個合適的排程演算法而不是一個先到先得的封包佇列。

參考來源

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.