排程 (電腦)

排程（英語：Scheduling）在電腦中是分配工作所需資源的方法。資源可以指虛擬的計算資源，如執行緒、行程或資料流；也可以指硬體資源，如處理器、網路連接或擴充卡。

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

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

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

作業系統排程器的種類

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

行程排程器

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

長期排程器

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

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

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

中期排程器

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

短期排程器

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

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

排程規則

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

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

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