Linux是多任務操作系統(multitask OS), 在單處理器系統上，多任務操作系統需要使得在其上運行的進程認為是自己使得獨占處理器資源，所以這僅僅是邏輯上的並行。在多處理器系統裡，多任務操作系統可以實現真正實現並行，也就是在不同的處理器上運行著不同的進程。而如何在這兩種的機器上實現多進程並行執行（邏輯上和物理上），則是調度器的主要任務。
Linux scheduler的歷史
從1991年linux OS面世以來，到linux 2.4之前， linux的kernel scheduler的設計很簡單。
在linux1.2中，scheduler采用循環隊列來管理正在系統中運行的task(process),並且采用round-robin調度策略（policy）來進行task調度。 在linux 2.2 中，linux kernel scheduler引入了scheduling class的概念，並且對real time task, non-preemptible, non-real-time task 提供不同的調度策略。並且從linux2.2開始，scheduler開始支持SMP。
在linux 2.4以前kernel當中的scheduler的設計盡管設計簡單，容易實現，但是它在擴展性方面很差，尤其上在系統中有大量的進程存在需要調度，或在多個處理器的系統當中，該缺點尤其明顯。
所以，為了克服linux 2.4之前scheduler的缺點，在linux 2.5和linux 2.6早期的版本當中，引入了O(1) scheduler。O（1）引入了常量時間內timeslice的計算算法 和 為每個處理器管理一個runqueue，來修正之前scheduler設計的缺陷。
O(1) scheduler 擁有很好的可擴展性， 但是其需要維護大量的代碼來實現其復雜的啟發式算法，這是難以維護的。同時，O(1)在面對latency-sensitive 的任務的時候（通常稱為交互性任務）表現不是很好。所以在linux 2.6 kernel 系列的早期，開發者們引入了旨在提高O(1)在面對latency-sensitive 任務前性能的改動。在這其中，最值得注意的是RSDL（Rotating Staircase DeadLine） scheduler，這該scheduler中引入了fair scheduling的概念（來至於排隊論）。而這是RSDL的出現，最終在其基礎上，Ingo Molnar 實現了CFS（Complete Fair Scheduler），並最終被linux kernel采納。
