多道程式作業系統的基礎。通過在程序之間切換cpu，作業系統可以提高計算機的吞吐率。
對于單處理器系統，每次隻允許一個程序運作：任何其他程序必須等待，直到cpu空閑能被排程為止。
多道程式的目标是在任何時候都有某些程序在運作，以使cpu的使用率最大化。多道程式的思想較為簡單，當一個程序必須等待時，作業系統會從該程序拿走cpu的使用權，而将cpu交給其他程序。
cpu的成功排程依賴于程序的如下屬性：
程序執行由cpu執行周期和i/o等待周期組成。程序在這兩個狀态之間切換(cpu burst—i/o bust)。
程序執行從cpu區間（cpu burst）開始，在這之後是i/o區間（i/o burst）。接着另外一個cpu區間，然後是另外一個i/o區間，如此進行下去，最終，最後的cpu區間通過系統請求中止執行。
經過大量cpu區間的長度的測試。發現具有大量短cpu區間和少量長cpu區間。i/o限制程式通常具有很多短cpu區間。cpu限制程式可能有少量的長cpu區間。這種分布有助于選擇合适的cpu排程算法。
每當cpu空閑時，作業系統就必須從就緒隊列中選擇一個程序來執行。程序選擇由短期排程程式（short-term scheduler）或cpu排程程式執行。排程程式從記憶體中選擇一個能夠執行的程序，并為之配置設定cpu。
就緒隊列不必是先進先出（fifo）隊列，也可為優先隊列、樹或簡單的無序連結清單。不過隊列中所有的程序都要排隊以等待在cpu上運作。隊列中的記錄通常為程序控制塊（pcb）。
cpu排程決策可在如下4種情況環境下發生：
（1）當一個程序從運作切換到等待狀态（如：i/o請求，或者調用wait等待一個子程序的終止）
（2）當一個程序從運作狀态切換到就緒狀态（如：出現中斷）
（3）當一個程序從等待狀态切換到就緒狀态（如：i/o完成）
（4）當一個程序終止時
對于第1和4兩種情況，沒有選擇而隻有排程。一個新程序（如果就緒隊列中已有一個程序存在）必須被選擇執行。對于第２和第３兩種情況，可以進行選擇。
當排程隻能發生在第1和4兩種情況下時，稱排程是非搶占的（nonpreemptive）或協作的（cooperative）；否則，稱排程方案為搶占的（preemptive）。采用非搶占排程，一旦cpu配置設定給一個程序，那麼該程序會一直使用cpu直到程序終止或切換到等待狀态。
搶占排程對方問共享資料是有代價（如加鎖）的，需要新的機制來協調對共享資料的通路。
搶占對于作業系統核心的設計也有影響。在處理系統調用時，核心可能忙于程序活動。這些活動可能涉及要改變重要核心資料(如i/o隊列)。
因為根據定義中斷能随時發生，而且不能總是被核心所忽視，是以受中斷影響的代碼段必須加以保護以避免同時通路。作業系統需要在任何時候都能夠接收中斷，否則輸入會丢失或輸出會被改寫。為了這些代碼段不被多個程序同時通路，在進入時就要禁止中斷，而在退出時要重新允許中斷。
分派程式（dispatch）是一個子產品，用來将cpu的控制交給由短期排程程式選擇的程序。
其功能包括：
切換上下文
切換到使用者模式
跳轉到使用者程式的合适位置，以重新啟動程式。
分派程式停止一個程序而啟動另一個所花的時間成為分派延遲（dispatch latency）。
為了比較cpu排程算法所提出的準則：
cpu使用率 : 需要使cpu盡可能忙
吞吐量 : 指一個時間單元内所完成程序的數量
周轉時間 : 從程序送出到程序完成的時間段稱為周轉時間，周轉時間是所有時間段之和，包括等待進入記憶體、在就緒隊列中等待、在cpu上執行和i/o執行
等待時間 : 在就緒隊列中等待所花費時間之和
響應時間 : 從送出請求到産生第一響應的時間
需要使cpu使用率和吞吐量最大化，而使周轉時間、等待時間和響應時間最小化。絕大多數情況下需要優化平均值，有時需要優化最大值或最小值，而不是平均值。
最簡單的cpu排程算法是先到先服務算法（first-come，first-served scheduling）：先請求cpu的程序先配置設定到cpu。fcfs政策可以用fifo隊列來容易實作。當一個程序進入就緒隊列，其pcb連結到隊列的尾部。當cpu空閑時，cpu配置設定給位于隊列頭的程序，接着運作程序從隊列中删除。
fcfs政策的代碼編寫簡單且容易了解，不過采用fcfs政策的平均等待時間通常比較長。當程序cpu區間時間變化很大，平均等待時間會變化很大。
比如以下例子
程序
區間時間
p1
24
p2
3
p3
如果按照p1 p2 p3 順序到達，gantt圖如下:
平均等待時間：(0+24+27)/3 = 17
如果按p2 p3 p1 順序到達，
平均等待時間：(0+3+6)/3 = 3
另外考慮在動态情況下的性能，假設有一個cpu限制程序和許多i/o限制程序，cpu限制程序會移回到就緒隊列并被配置設定到cpu。再次所有i/o程序會在就緒隊列中等待cpu程序的完成。由于所有其他程序都等待一個大程序釋放cpu，這稱之為護航效果（convoy effect）。與讓較短程序最先執行相比，這樣會導緻cpu和裝置使用率變的很低。
fcfs排程算法是非搶占的。對于分時系統（每個使用者需要定時的等待一定的cpu時間）是特别麻煩。允許一個程序保持cpu時間過長是個嚴重錯誤。
将每個程序與下一個cpu區間段相關聯。當cpu為空閑時，它會賦給具有最短cpu區間的程序。如果兩個程序具有同樣長度，那麼可以使用fcfs排程來處理。注意，一個更為适當地表示是最短下一個cpu區間的算法，這是因為排程檢查程序的下一個cpu區間的長度，而不是其總長度。
6
8
7
p4
sjf: (0+3 + 9 + 16)/4 = 7
fcfs: (0+6+14+21)/4 = 10.25
sjf算法的平均等待時間最小。sjf算法的真正困難是如何知道下一個cpu區間的長度。對于批處理系統的長期（作業）排程，可以将使用者送出作業時間所制定的程序時間極限作為長度。sjf排程經常用于長期排程。
它不能在短期cpu排程層次上加以實作。我們可以預測下一個cpu區間。認為下一個cpu區間的長度與以前的相似。是以通過計算下一個cpu區間長度的近似值，能選擇具有最短預測cpu區間的程序來運作。下一個cpu區間通常可預測為以前cpu去剪的測量長度的指數平均（exponential average）。
sjf算法可能是搶占的或非搶占的。搶占sjf算法可搶占目前運作的程序，而非搶占的sjf算法會允許目前的程序先完成其cpu區間。搶占sjf排程有時稱為最短剩餘時間優先排程（shortest-remaining-time-first scheduling）。
到達時間
８
1
４
2
９
５
根據gantt圖：
平均等待時間：
(0+0+(5-3)+(10-1)+(17-2))/4 = 26/4 = 6.5
非搶占sjf:
(0+(8-1)+(12-3)+(17-2))/4 = 7.75
sjf算法可作為通用的優先級排程算法的一個特例。每個程序都有一個優先級與其關聯，具有最高優先級的程序會配置設定到cpu。具有相同優先級的程序按fcfs順序排程。sjf，其優先級（p）為下一個cpu區間的倒數。cpu區間越大，則優先級越小，反之亦然。
優先級通常是固定區間的數字，如０～７，但是數字大小與優先級的高低沒有定論。
對于下例，假設數字越小優先級越高
優先級
10
３
１
p5
5
２
平均等待時間為：
(0+1+6+16+18)/5 = 8.2
優先級可通過内部或外部方式來定義。内部定義優先級使用一些測量資料以計算程序優先級。外部優先級是通過作業系統之外的準則來定義，如程序重要性等。
優先級排程可以是搶占的或非搶占的。
優先級排程算法的一個重要問題是無限阻塞（indefinite blocking）或饑餓（starvation）。可以運作但缺乏cpu的程序可認為是阻塞的，它在等待cpu。優先級排程算法會使某個有低優先級無窮等待cpu。
低優先級程序務求等待問題的解決之一是老化（aging）。老化是一種技術，以逐漸增加在系統中等待很長時間的程序的優先級。
專門為分時系統設計。它類似于fcfs排程，但是增加了搶占以切換程序。定義一個較小的時間單元，稱為時間片（time quantum，or time slice）。将就緒隊列作為循環隊列。cpu排程程式循環就緒隊列，為每個程序配置設定不超過一個時間片段的cpu。
新程序增加到就緒隊列的尾部。cpu排程程式從就緒隊列中選擇第一個程序，設定定時器在一個時間片之後中斷，再分派該程序。接下來将可能發生兩種情況。程序可能隻需要小于時間片的cpu區間。對于這種情況，程序本身會自動釋放cpu。排程程式接着處理就緒隊列的下一個程序。否則，如果目前運作程序的cpu區間比時間片要長，定時器會中斷産生作業系統中斷，然後進行上下文切換，将程序加入到就緒隊列的尾部，接着cpu排程程式會選擇就緒隊列中的下一個程序。
rr政策的平均等待時間通常較長
比如以下例子,使用４ms時間片
畫出gantt圖：
(0+4+7+(10-4))/3 = 5.66
如果就緒，那麼每個程序會得到1/n的cpu時間，其長度不超過q時間單元。每個程序必須等待cpu時間不會超過(n-1)q個時間單元，直到它的下一個時間片為止。
rr算法的性能很大程度上依賴于時間片的大小。在極端情況下，如果時間片非常大，那麼rr算法與fcfs算法一樣。如果時間片很小，那麼rr算法稱為處理器共享，n個程序對于使用者都有它自己的處理器，速度為真正處理器速度的1/n。
小的時間片會增加上下文切換的次數，是以，希望時間片比上下文切換時間長，事實上，絕大多數現代作業系統，上下文切換的時間僅占時間片的一小部分。
周轉時間也依賴于時間片的大小。
前台（互動）程序和背景（批處理）程序。這兩種不同各類型的程序具有不同響應時間要求，也有不同排程需要。與背景程序相比，前台程序要有更高（或外部定義）的優先級。
多級隊列排程算法将就緒隊列分成多個獨立隊列。根據程序的屬性，如記憶體大小等，一個程序被永久地配置設定到一個隊列(低排程開銷但是不夠靈活)，每個隊列有自己的排程算法。前台隊列可能采用rr算法排程，而背景排程可能采用fcfs算法排程。
另外，隊列之間必須有排程，通常采用固定優先級搶占排程，例如前台隊列可以比背景隊列具有絕對優先值。另一種可能在隊列之間劃分時間片例如，前台隊列可以有80%的時間用于在程序之間進行rr排程，而背景隊列可以有20%的cpu時間采用fcfs算法排程程序。
與多級隊列排程相反，多級回報隊列排程允許程序在隊列之間移動。主要思想是根據不同cpu區間的特點以區分程序。如果程序使用過多cpu時間，那麼它可能被轉移到較低優先級隊列。這種方案将i/o限制和互動程序留在更高優先級隊列。此外，在較低優先級隊列中等待時間過長的程序會被轉移到更高優先級隊列。這種形式的老化組織饑餓的發生。
通常，多級回報隊列排程程式可由下列參數來定義：
隊列數量。
每個隊列的排程算法。
用以确定何時更新到更高優先級隊列的方法。
用以确定何時降級到更低優先級隊列的方法。
用以确定程序在需要服務時應進入哪個隊列的方法。
如果多個cpu，則負載配置設定（load sharing）成為可能。其中主要讨論處理器功能相同（或同構）的系統，可以将任何處理器用于運作隊列内的任何程序。
在一個多處理器中，cpu排程的一種方法是讓一個處理器（主伺服器）處理所有的排程決定、i/o處理以及其他系統活動，其他的處理器隻執行使用者代碼。這種非對稱處理（asymmetric multiprocessing）方法更為簡單，因為隻有一個處理器通路系統資料結構，減輕了資料共享的需要。
另一種方法是使用對稱多處理（symmetric multiprocessing，smp）方法，即每個處理器自我排程。所有程序可能處于一個共同的就緒隊列中，或每個處理器都有自己的私有就緒隊列。無論如何，排程通過每個處理器檢查共同就緒隊列并選擇一個程序來執行。如果多個處理器試圖通路和更新一個共同資料結構，那麼每個處理器必須仔程式設計：必須確定兩個處理器不能選擇同一程序，且程序不會從隊列中丢失。
程序移到其他處理器上時，被遷移的第一個處理器的緩存中的内容必須為無效，而将要遷移的第二個處理器上的緩存需重新建構。由于使緩存無效或重構的代價高，因而smp努力的使一個程序在同一個處理器上運作，這被稱為處理器親和性，即一個程序需有一種對其他運作所在的處理器的親和性。
處理器親和性的幾種形式：
軟親和性（soft affinity，作業系統具有設法讓一個程序保持在同一個處理器上運作的政策，但不能做任何保證）
硬親和性（hard affinity，允許程序指定它不允許移至其他處理器）,如linux
負載平衡設法将工作負載平均地配置設定到smp系統中的所有處理器上。通常隻是對那些擁有自己私有的可執行的程序的處理器而言是必要的，在具有共同隊列的系統中，通常不需要負載平衡，因為一旦處理器空閑，會立刻從就緒隊列中取走一個可執行程序。
兩種方法：push migration和pull migration，對于push migration，一個特定的任務周期性地檢查每個處理器上的負載，如果發現不平衡，即通過将程序從超載處理器移到（或推送到）空閑或不太忙的處理器，進而平均地配置設定負載，當空閑處理器從一個忙的處理器上推送pull一個等待任務時，發生pull migration。push migration和pull migration不能互相排斥。
負載平衡會抵消處理器親和性。
提供多個邏輯（而非實體的）處理器來運作幾個線程，稱為對稱多線程（smt），或超線程（hyperthreading）技術。
smt的思想是在同一個實體處理器上生成多個邏輯處理器，即使系統僅有單處理器，每個邏輯處理器都有它自己的架構狀态，包括通用目的和機器狀态寄存器。每個邏輯處理器負責自己的中斷處理，這意味着中斷被送到并被邏輯處理器所處理，每個邏輯處理器共享其實體處理器的資源，如緩存或總線。
smt是硬體而非軟體提供的。硬體應該提供每個邏輯處理器的架構狀态的表示以及中斷處理方法。排程程式首先設法把不同線程分别排程到每個實體處理器上，而不是排程到同一個實體處理器的不同邏輯處理器上。
系統排程的是核心線程，而不是程序。使用者線程由線程庫管理，核心并不了解它們。使用者線程最終必須映射到相應的核心級線程,盡管這種映射可能是間接的，可能使用輕量級程序（lwp）。
使用者線程和核心線程的差別之一是它們是如何被排程的。在執行多對一模型和多對多模型系統上，線程庫排程使用者級線程到一個有效的lwp上運作，這被稱為程序競争範圍（process-contention scope，pcs）方法，因為cpu競争發生在屬于相同程序的線程之間。為了決定排程哪個核心線程到cpu，核心采用系統競争範圍（system-contention scope，scs）方法來進行，競争cpu發生在系統所有線程中，采用一對一的模型的系統，排程僅使用scs方法。
pcs是根據優先級完成的。