對于多道程式設計的系統，就會有多個程序或者線程在同時競争CPU。對于單核系統，排程問題，就是選擇下一個要運作的程序或者線程是哪一個。
線程的排程與程序類似，對于按核心級别的排程，與線程所屬的程序基本沒有關系。
程序切換的代價是比較大的，包括使用者态到核心态的切換、儲存目前程序的狀态、記憶體映像的改變、排程程式以及載入新程序的狀态；另外，會導緻高速緩存的失效。
排程程式要考慮的要素：
（1）程序是CPU密集型還是I/O密集型。I/O密集型可能會需要盡快運作，并且很快就阻塞。CPU密集型可能會長期占用CPU。
（2）何時排程。建立程序、程序退出、程序阻塞以及I/O中斷發生。
（3）是否支援搶占。支援搶占的排程，可以不必等待目前程序運作完或阻塞，直接上CPU運作。
一、排程算法的分類。
不同的環境需要不同的排程算法，也有不同的考量名額：
（1）批處理。批處理系統下，不需要特别快的響應速度，是以可以考慮非搶占以及每個程序都有長時間的搶占算法。名額主要是：吞吐量、周轉時間以及CPU使用率。
（2）互動式。互動式系統下，搶占是必須的，因為操作者會希望比較快的得到響應。考慮的名額主要是最小響應時間、均衡性。
（3）實時。實時系統下，最重要的是滿足截止時間要求，即在一定的時間内完成任務。
二、批處理系統中的排程
1、先來先服務（first-come-first-serve）。最簡單的方式，非搶占式的先來先服務，從字面意思就可以看出，把任務作為一個隊列，先來先服務。缺點是，無法展現任務的輕重緩急，達不到理想的名額性能。
2、最短作業優先。非搶占式下，即當一個任務完成時，從任務隊列中挑選最短的一個作業執行。相對于先來先服務，提高了一些性能。運作時間必須提前掌握。
3、最短剩餘時間優先。即最短作業優先的搶占版本。排程程式總是選擇剩餘運作時間最短的作業執行。每當一個新的作業到達，如果運作時間比目前程序的剩餘運作時間短，就挂起目前程序并切換到新的程序。
三、互動式系統中的排程
1、輪轉排程。最簡單且最公平的方法，給每個程序配置設定一個時間片。時間片耗盡時，程序會下CPU并加入到就緒隊列的末尾。問題的關鍵是選擇合适的時間片。
2、優先級排程。程序有輕重緩急，于是給程序設定不同的優先級，每次排程優先級最高的程序運作。當然，這樣可能會導緻低優先級程序饑餓。解決方案是，實行獎懲機制，高優先級程序耗盡時間片時會降低它的優先級。
3、多級隊列。給不同優先級的程序隊列，設定不同機關的時間片。同時，也實行獎懲機制，耗盡時間片會改變程序的隊列級别。
四、線程的排程
線程的排程，取決于支援的是核心級線程還是使用者級線程。
對于使用者級線程，核心不知道線程的存在，就給了程序很大的自主權。核心隻是排程程序，程序中的排程程式選擇哪個線程來運作。
對于核心級線程，線程的排程就交給了系統完成。
五、Linux中的程序與線程排程
首先明确一個概念，Linux系統中甚至沒有真正的線程。不過，可以認為Linux是系統的線程是核心線程，是以排程是基于線程的。
一個程序由于其運作空間的不同, 進而有核心線程和使用者程序的區分, 核心線程運作在核心空間, 之是以稱之為線程是因為它沒有虛拟位址空間, 隻能通路核心的代碼和資料, 而使用者程序則運作在使用者空間, 但是可以通過中斷, 系統調用等方式從使用者态陷入核心态。
使用者程序運作在使用者空間上, 而一些通過共享資源實作的一組程序我們稱之為線程組, Linux下核心其實本質上沒有線程的概念, Linux下線程其實上是與其他程序共享某些資源的程序而已。但是我們習慣上還是稱他們為線程或者輕量級程序。
是以, Linux上程序分3種，核心線程（或者叫核心程序）、使用者程序、使用者線程, 當然如果更嚴謹的，也可以認為使用者程序和使用者線程都是使用者程序。
Linux中，程序和線程都被維護為一個task_struct結構，線程和程序被同等對待來進行排程。
Linux将線程區分為3類：
（1）實時先入先出。
（2）實時輪轉。
（3）分時。
實時先入先出有最高的優先級，不會被其他線程搶占，除非是另外一個剛剛準備好的且優先級更高的實時先入先出線程。
實時輪轉線程與實時先入先出類似，不過有一個輪轉體系，即配置設定一個時間片，時間到了就可以被搶占。時間片消耗完就進入實時輪轉線程清單的末尾。其實，這兩種都不是真的實時，因為執行的最後期限無法确定，隻是比分時線程有更高的優先級。
實時線程的優先級從0-99,0是實時線程的最高優先級，99是實時線程的最低優先級。
傳統的非實時線程，優先級從100-139。Linux系統根據非實時線程的優先級配置設定時間量。
Linux使用一個重要的結構，排程隊列。每個CPU有自己的排程隊列，包括兩個數組：活動的和過期失效的。每個數組包括了140個連結清單頭，對應140個優先級的連結清單。
排程器從正在活動數組中選擇一個優先級最高的任務，如果時間片耗盡失效，就加入到過期失效數組中。如果程序在時間片内被阻塞，那麼在時間片失效之前，等待的事件發生就可以繼續運作，放回到正在活動的數組中。如果活動數組沒有任務了，排程器交換指針，使得活動數組和失效數組調換。
不同的優先級被賦予不同的時間片長度，優先級越高的程序，時間片越長。
Linux采用靜态優先級與動态優先級結合的方式。Linux采用了獎懲機制，目的在于獎勵互動程序以及懲罰占用CPU的程序。一個程序初始被賦予了一個優先級，耗盡和阻塞會改變nice值，活動與過期程序轉換時，動态改變程序優先級。
另外，對于多核處理器，運作隊列資料結構與某一個處理器相對應，排程器盡量進行親和排程，即将之前在某個處理器上運作過的任務再次調入該處理器。
排程器隻考慮可以運作的任務，不可運作的任務和正在等待各種I/O操作的或核心事件的任務被放入等待隊列中。每一種等待某種事件的任務組成一個等待隊列。等待隊列的頭部包含一個指向任務連結清單的指針及一個自旋鎖。