存中保存了對每個進程的唯一描述, 並通過若干結構與其他進程連接起來.
調度器面對的情形就是這樣, 其任務是在程序之間共享CPU時間, 創造並行執行的錯覺, 該任務分為兩個不同的部分, 其中一個涉及調度策略, 另外一個涉及上下文切換.
通常來說，操作系統是應用程序和可用資源之間的媒介。
典型的資源有內存和物理設備。但是CPU也可以認為是一個資源，調度器可以臨時分配一個任務在上面執行（單位是時間片）。調度器使得我們同時執行多個程序成為可能，因此可以與具有各種需求的用戶共享CPU。
內核必須提供一種方法, 在各個進程之間盡可能公平地共享CPU時間, 而同時又要考慮不同的任務優先級.
調度器的一個重要目標是有效地分配 CPU 時間片，同時提供很好的用戶體驗。調度器還需要面對一些互相沖突的目標，例如既要為關鍵實時任務最小化響應時間, 又要最大限度地提高 CPU 的總體利用率.
調度器的一般原理是, 按所需分配的計算能力, 向系統中每個進程提供最大的公正性, 或者從另外一個角度上說, 他試圖確保沒有進程被虧待.
傳統的Unix操作系統的都奧杜算法必須實現幾個互相沖突的目標:
進程響應時間盡可能快
後台作業的吞吐量盡可能高
盡可能避免進程的饑餓現象
低優先級和高優先級進程的需要盡可能調和等等
調度策略(scheduling policy)的任務就是決定什麼時候以怎麼樣的方式選擇一個新進程占用CPU運行.
傳統操作系統的調度基於分時(time sharing)技術: 多個進程以”時間多路服用”方式運行, 因為CPU的時間被分成”片(slice)”, 給每個可運行進程分配一片CPU時間片, 當然單處理器在任何給定的時刻只能運行一個進程.
如果當前可運行進程的時限(quantum)到期時(即時間片用盡), 而該進程還沒有運行完畢, 進程切換就可以發生.
分時依賴於定時中斷, 因此對進程是透明的, 不需要在承租中插入額外的代碼來保證CPU分時.
調度策略也是根據進程的優先級對他們進行分類. 有時用復雜的算法求出進程當前的優先級, 但最後的結果是相同的: 每個進程都與一個值(優先級)相關聯, 這個值表示把進程如何適當地分配給CPU.
在linux中, 進程的優先級是動態的. 調度程序跟蹤進程正在做什麼, 並周期性的調整他們的優先級. 在這種方式下, 在較長的時間間隔內沒有任何使用CPU的進程, 通過動態地增加他們的優先級來提升他們. 相應地, 對於已經在CPU上運行了較長時間的進程, 通過減少他們的優先級來處罰他們.
進程饑餓，即為Starvation，指當等待時間給進程推進和響應帶來明顯影響稱為進程饑餓。當饑餓到一定程度的進程在等待到即使完成也無實際意義的時候稱為饑餓死亡。
產生饑餓的主要原因是
在一個動態系統中，對於每類系統資源，操作系統需要確定一個分配策略，當多個進程同時申請某類資源時，由分配策略確定資源分配給進程的次序。
有時資源分配策略可能是不公平的，即不能保證等待時間上界的存在。在這種情況下，即使系統沒有發生死鎖，某些進程也可能會長時間等待．當等待時間給進程推進和響應帶來明顯影響時，稱發生了進程饑餓，當饑餓到一定程度的進程所賦予的任務即使完成也不再具有實際意義時稱該進程被餓死。
舉個例子，當有多個進程需要打印文件時，如果系統分配打印機的策略是最短文件優先，那麼長文件的打印任務將由於短文件的源源不斷到來而被無限期推遲，導致最終的饑餓甚至餓死。
當涉及有關調度的問題時, 傳統上把進程分類為”I/O受限(I/O-dound)”或”CPU受限(CPU-bound)”.
另外一種分類法把進程區分為三類:
注意
前面的兩類分類方法在一定程序上相互獨立
例如, 一個批處理進程很有可能是I/O受限的(如數據庫服務器), 也可能是CPU受限的(比如圖形繪制程序)
在linux中, 調度算法可以明確的確認所有實時進程的身份, 但是沒辦法區分交互式程序和批處理程序(統稱為普通進程), linux2.6的調度程序實現了基於進程過去行為的啟發式算法, 以確定進程應該被當做交互式進程還是批處理進程. 當然與批處理進程相比, 調度程序有偏愛交互式進程的傾向
根據進程的不同分類Linux采用不同的調度策略.
對於實時進程，采用FIFO或者Round Robin的調度策略.
對於普通進程，則需要區分交互式和批處理式的不同。傳統Linux調度器提高交互式應用的優先級，使得它們能更快地被調度。而CFS和RSDL等新的調度器的核心思想是”完全公平”。這個設計理念不僅大大簡化了調度器的代碼復雜度，還對各種調度需求的提供了更完美的支持.
注意Linux通過將進程和線程調度視為一個，同時包含二者。進程可以看做是單個線程，但是進程可以包含共享一定資源（代碼和/或數據）的多個線程。因此進程調度也包含了線程調度的功能.
linux進程的調度算法其實經過了很多次的演變, 但是其演變主要是針對與普通進程的, 因為前面我們提到過根據進程的不同分類Linux采用不同的調度策略.實時進程和普通進程采用了不同的調度策略, 更一般的普通進程還需要啟發式的識別批處理進程和交互式進程.
實時進程的調度策略比較簡單, 因為實時進程值只要求盡可能快的被響應, 基於優先級, 每個進程根據它重要程度的不同被賦予不同的優先級，調度器在每次調度時, 總選擇優先級最高的進程開始執行. 低優先級不可能搶占高優先級, 因此FIFO或者Round Robin的調度策略即可滿足實時進程調度的需求.
但是普通進程的調度策略就比較麻煩了, 因為普通進程不能簡單的只看優先級, 必須公平的占有CPU, 否則很容易出現進程饑餓, 這種情況下用戶會感覺操作系統很卡, 響應總是很慢.
此外如何進程中如果存在實時進程, 則實時進程總是在普通進程之前被調度
一開始的調度器是復雜度為O(n)的始調度算法(實際上每次會遍歷所有任務，所以復雜度為O(n)), 這個算法的缺點是當內核中有很多任務時，調度器本身就會耗費不少時間，所以，從linux2.5開始引入赫赫有名的O(1)調度器
然而，linux是集全球很多程序員的聰明才智而發展起來的超級內核，沒有最好，只有更好，在O(1)調度器風光了沒幾天就又被另一個更優秀的調度器取代了，它就是CFS調度器Completely Fair Scheduler. 這個也是在2.6內核中引入的，具體為2.6.23，即從此版本開始，內核使用CFS作為它的默認調度器，O(1)調度器被拋棄了, 其實CFS的發展也是經歷了很多階段，最早期的樓梯算法(SD), 後來逐步對SD算法進行改進出RSDL(Rotating Staircase Deadline Scheduler), 這個算法已經是”完全公平”的雛形了， 直至CFS是最終被內核采納的調度器, 它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進程的睡眠時間，也不再企圖區分交互式進程。它將所有的進程都統一對待，這就是公平的含義。CFS的算法和實現都相當簡單，眾多的測試表明其性能也非常優越
更多CFS的信息, 請參照
http://www.ibm.com/developerworks/cn/linux/l-completely-fair-scheduler/index.html?ca=drs-cn-0125
另外內核文檔sched-design-CFS.txt中也有介紹
2個調度器
可以用兩種方法來激活調度
一種是直接的, 比如進程打算睡眠或出於其他原因放棄CPU
另一種是通過周期性的機制, 以固定的頻率運行, 不時的檢測是否有必要
因此當前linux的調度程序由兩個調度器組成：主調度器，周期性調度器(兩者又統稱為通用調度器(generic scheduler)或核心調度器(core scheduler))
並且每個調度器包括兩個內容：調度框架(其實質就是兩個函數框架)及調度器類
調度器類是實現了不同調度策略的實例，如 CFS、RT class等。
它們的關系如下圖
![調度器的組成](https://www.unixlinux.online/unixlinux/UploadFiles_9426/201703/2017030111464152.jpg "\")
當前的內核支持兩種調度器類（sched_setscheduler系統調用可修改進程的策略）：CFS（公平）、RT（實時）；5種調度策略：SCHED_NORAML（最常見的策略）、SCHED_BATCH（除了不能搶占外與常規任務一樣，允許任務運行更長時間，更好地使用高速緩存，適合於成批處理的工作）、SCHED_IDLE（它甚至比nice 19還有弱，為了避免優先級反轉使用）和SCHED_RR（循環調度，擁有時間片，結束後放在隊列末）、SCHED_FIFO（沒有時間片，可以運行任意長的時間）；其中前面三種策略使用的是cfs調度器類，後面兩種使用rt調度器類。<喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+Mrj2tfe2yMb3wOA8L3N0cm9uZz48L3A+DQo8cD61scewtcTE2rrL1qez1jLW1rX3tsjG98Dgo6hzY2hlZF9zZXRzY2hlZHVsZXLPtc2ztffTw7/J0N64xL34s8y1xLLfwtSjqaO6PHN0cm9uZz5DRlOjqLmrxr2197bIxvejqTwvc3Ryb25nPqGiPHN0cm9uZz5SVKOoyrXKsbX3tsjG96OpPC9zdHJvbmc+PC9wPg0KPHA+PHN0cm9uZz411ta197bIst/C1Dwvc3Ryb25nPjwvcD4NCjx0YWJsZT4NCjx0aGVhZD4NCgk8dHI+DQoJPHRoPg0KCQnX1rbOPC90aD4NCgk8dGggYWxpZ249"center"> 描述
其中前面三種策略使用的是cfs調度器類，後面兩種使用rt調度器類。
另外，對於調度框架及調度器類，它們都有自己管理的運行隊列，調度框架只識別rq（其實它也不能算是運行隊列），而對於cfs調度器類它的運行隊列則是cfs_rq（內部使用紅黑樹組織調度實體），實時rt的運行隊列則為rt_rq（內部使用優先級bitmap+雙向鏈表組織調度實體）
本質上, 通用調度器(核心調度器)是一個分配器,與其他兩個組件交互.
調度器用於判斷接下來運行哪個進程.
內核支持不同的調度策略(完全公平調度, 實時調度, 在無事可做的時候調度空閒進程,即0號進程也叫swapper進程,idle進程), 調度類使得能夠以模塊化的方法實現這些側露額, 即一個類的代碼不需要與其他類的代碼交互
當調度器被調用時, 他會查詢調度器類, 得知接下來運行哪個進程
在選中將要運行的進程之後, 必須執行底層的任務切換.
這需要與CPU的緊密交互. 每個進程剛好屬於某一調度類, 各個調度類負責管理所屬的進程. 通用調度器自身不涉及進程管理, 其工作都委托給調度器類.
首先，我們需要清楚，什麼樣的進程會進入調度器進行選擇，就是處於TASK_RUNNING狀態的進程，而其他狀態下的進程都不會進入調度器進行調度。
系統發生調度的時機如下
調用cond_resched()時
顯式調用schedule()時
從系統調用或者異常中斷返回用戶空間時
從中斷上下文返回用戶空間時
當開啟內核搶占(默認開啟)時，會多出幾個調度時機，如下
在系統調用或者異常中斷上下文中調用preempt_enable()時(多次調用preempt_enable()時，系統只會在最後一次調用時會調度)
在中斷上下文中，從中斷處理函數返回到可搶占的上下文時(這裡是中斷下半部，中斷上半部實際上會關中斷，而新的中斷只會被登記，由於上半部處理很快，上半部處理完成後才會執行新的中斷信號，這樣就形成了中斷可重入)
而在系統啟動調度器初始化時會初始化一個調度定時器，調度定時器每隔一定時間執行一個中斷，在中斷會對當前運行進程運行時間進行更新，如果進程需要被調度，在調度定時器中斷中會設置一個調度標志位，之後從定時器中斷返回，因為上面已經提到從中斷上下文返回時是有調度時機的，在內核源碼的匯編代碼中所有中斷返回處理都必須去判斷調度標志位是否設置，如設置則執行schedule()進行調度。
而我們知道實時進程和普通進程是共存的，調度器是怎麼協調它們之間的調度的呢，其實很簡單，每次調度時，會先在實時進程運行隊列中查看是否有可運行的實時進程，如果沒有，再去普通進程運行隊列找下一個可運行的普通進程，如果也沒有，則調度器會使用idle進程進行運行。
之後的章節會放上代碼進行詳細說明。
系統並不是每時每刻都允許調度的發生，當處於硬中斷期間的時候，調度是被系統禁止的，之後硬中斷過後才重新允許調度。而對於異常，系統並不會禁止調度，也就是在異常上下文中，系統是有可能發生調度的。
