對于單處理器系統，每次只允許一個進程運行，任何其他進程必須等待，直到CPU空閑能被調度為止，多道程序的目的是在任何時候都有某些進程在運行，以使CPU使用率最大化。

CPU-I/O區間周期

CPU的成功調度依賴于進程的如下屬性：進程執行由CPU 執行和I/O等待周期。

進程在這兩個狀態之間切換，進程執行從 CPU 區間開始，在這之后是 I/O 區間，接著是另一個 CPU 區間，然后是另一個I/O區間，如此進行下去，最終，最后的CPU 區間通過系統請求終止執行。

CPU調度程序

每當CPU空閑時，操作系統就必須從就緒隊列中選擇一個進程來執行，進程選擇由短期調度程序 或 CPU 調度程序執行，調度程序從內存中選擇一個能夠執行的進程，并為之分配CPU。

就緒隊列不必是先進先出(FIFO)隊列。正如研究各種調度算法時將看到的，就緒隊列可實現為FIFO隊列、優先隊列、樹或簡單的無序鏈表，不過，從概念上講，就緒隊列內的所有進程都要排隊以等待在CPU上運行，隊列中的記錄通常為進程控制塊。

調度算法(重要)

CPU 調度處理是從就緒隊列中選擇進程并為之分配CPU的問題。

先到先服務調度(FCFS)

先到先服務(first-come, first-served(FCFS))

采用這種方案，先請求CPU的進程先分配到CPU，FCFS 策略可以用FIFO隊列來實現。當一個進程進入到就緒隊列，其PCB鏈接到隊列的尾部，當CPU空閑時，CPU分配給位于隊列頭的進程，接著該運行進程從隊列中刪除。采用 FCFS策略的平均等待時間通常是比較長的。

FCFS 調度算法是非搶占的，一旦CPU被分配給了一個進程，該進程就會保持CPU直到釋放CPU為止，即程序終止或是請求 I/O. FCFS 算法對于分布式系統(每個用戶需要定時地得到一定的CPU時間)是特別麻煩的。允許一個進程保持CPU 時間過長將是個嚴重的錯誤。

最短作業優先調度(SJF)

最短作業優先調度算法(shortest-job-first (SJF) scheduling algorithm)。

這一算法將每個進程與其下一個CPU區間段相關聯，當CPU為空閑時，他會賦給具有最短CPU區間的進程。如果兩個進程具有相同長度，那么可以使用FCFS調度來處理。

SJF 調度算法可以證明為最佳的，這是因為對于給定的一組進程，SJF 算法的平均等待時間最小，通過將短進程移到長進程之前，短進程等待時間的減少大于長進程等待時間的增加，因而，平均等待時間減少了。

優先級調度

SJF 算法可以作為通用優先級調度算法的一個特例。每個進程都有一個優先級與其關聯。具有最高優先級的進程會分配到CPU，具有相同優先級的進程按FCFS順序。SJF算法屬于簡單優先級算法，其優先級(p)為下一個(預測的)CPU區間的倒數，CPU區間越大，則優先級越小，反之亦然。

優先級可通過內部或外部方式來定義，內部定義優先級使用一些測量數據以計算進程優先級。例如，時間極限，內存要求，打開文件的數量和平均I/O區間與平均CPU區間之比都可以用于計算優先級。

優先級調度算法的一個主要問題是無阻塞 或饑餓，可以運行但缺乏CPU的進程可以認為是阻塞的，它在等待CPU。

輪轉法調度(RR)

輪轉法(round-robin, RR)調度算法是專門為分時系統設計的，它類似于FCFS調度，但是增加了搶占以切換進程。定義一個較小時間單元，稱之為時間片, 時間片通常為 10 - 100 ms， 將就緒隊列作為循環隊列。CPU 調度程序循環就緒隊列，為每一個進程分配不超過一個時間片的CPU。

為了實現RR調度，將就緒隊列保存為進程的FIFO隊列，新進程增加到就緒隊列的尾部，CPU調度程序從就緒隊列中選擇第一個程序，設置定時器在一個時間片之后中斷，再分派該進程。

接下來將可能發生兩種情況，進程可能只需要小于時間片的CPU區間，對于這種情況，進程本身會自動釋放CPU，調度程序接著處理就緒隊列的下一個進程，否則，如果當前運行進程的CPU區間比時間片要長，定時器會中斷并產生操作系統中斷，然后進程上下文切換，將進程加入到就緒隊列的尾部，接著CPU調度程序會選擇就緒隊列中的下一個進程。

RR調度算法是可搶占的，對于RR調度算法，隊列中沒有進程被分超過一個時間片的CPU時間(除非它是唯一可運行的進程)，如果進程的CPU區間超過了一個時間片，那么該進程會被搶占，而被放回就緒隊列。

RR算法的性能很大程度上依賴域時間片的大小，在極端情況下，如果時間片非常大，那么RR算法與FCFS算法一樣，如果時間片很小(如毫秒)，那么RR算法稱為處理器共享，(從理論上來說)n個進程對于用戶都有它自己的處理器，速度為真正處理數度的 1/n。這種方法用在 Control Data Corporation(CDC)的硬件上，可以用一組硬件和10組寄存器實現 10 個外設處理器。硬件為一組寄存器執行一個指令，然后為下一組執行，這種循環不斷進行，形成10個慢處理器器而不是1個塊處理器。

多級隊列調度

多級隊列調度算法將就緒隊列分成多個獨立隊列，根據進程的屬性，如內存大小，進程優先級、進程類型、一個進程被永久地分配到一個隊列，每個隊列有自己的調度算法。這種算法的優點是低調度開銷，缺點是不夠靈活。

多級反饋隊列調度

多級反饋隊列調度算法，允許進程在隊列之間移動，主要思想是根據不同CPU區間的特點以區分進程，如果進程使用過多的CPU時間，那么它會被移到更低的優先級隊列。

多處理器調度

之前討論的是單處理器系統內的CPU 問題，如果有多個CPU，則負載分配成為可能，但調度問題也相應的變得更加復雜。與單處理器中的CPU調度算法一樣，沒有最好的解決方案。

多處理器調度的方法

在一個多處理器中，CPU調度的一種方法是讓一個處理器(主服務器)處理所有的調度決定、I/O處理以及其他系統活動，其他的處理器只執行用戶代碼。這種非對稱多處理方法更為簡單，因為只有一個處理器訪問系統數據結構，減輕了數據共享的需要。

另一種方法是使用對稱處理器方法，即每個處理器自我調度，所有進程可能處于一個共同的就緒隊列中，或每個處理器都有它自己的私有就緒隊列。無論如何，調度通過每個處理器檢查共同就緒隊列并選擇一個進程來執行。如果多處理器試圖訪問和更新一個共同數據結構，那么每個處理器必須編程：必須保證兩個處理器不能選擇同一個進程，且進程不會從隊列中丟失。

處理器親和性

考慮一下，當一個進程在一個特定處理器上運行時，緩存中會發生什么？進程最近訪問的數據進入處理器緩存，結果是進程所進行的連續內存訪問通常在緩存中得以滿足。現在可以考慮一下，如果進程移到其他處理器上時，會發生什么：被遷移的第一個處理器的緩存中的內容必須為無效，而將要遷移的第二個處理器的緩存需要重新構建。由于使緩存無效或重新構建的代價高，絕大多數SMP系統試圖避免將進程從一個處理器移至另一個處理器，而是努力使一個進程在同一個處理器上運行，這被稱為處理器親和性，即一個進程需要對其運行所在的處理器的親和性。

負載平衡

負載平衡 設法將工作負載平均地分配到SMP系統中的所有處理器上，值得注意的是，負載平衡通常只是對那些擁有自己私有的可執行進程的處理器而言是必要的。在具有共同隊列的系統中，通常不需要負載平衡，因為一但處理器空閑，它立刻從共同隊列中取走一個可執行進程，但同樣值得注意的是，在絕大多數支持SMP中，每個處理器都具有一個可執行進程的私有隊列。

負載平衡常會抵消處理器的親和性的優點。