多任務系統可以分為：非搶占式和搶占式。Linux提供搶占式多任務模式。進程在被搶占之前能夠運行的時間叫進程的時間片，Linux獨一無二的公平調度程序本身並沒有采用時間片來達到公平調度。
Linux之前采用O(1)調度器，它對大服務器的工作負載很理想，但是對響應時間敏感的程序卻有不足。在2.6.23內核版本中用完全公平調度算法（CFS）代替了O(1)調度算法。
進程可以被分為I/O消耗型和處理器消耗型。I/O消耗型指進程的大部分時間用來提交I/O請求或是等待I/O請求。處理器消耗型指進程把事件大多數用在執行代碼上。調度策略通常在兩個矛盾中尋找平衡：進程響應迅速和最大系統利用率。Linux更傾向於優先調度I/O消耗型進程。
調度程序總是選擇時間片未用盡而且優先級最高的進程運行。
Linux采用兩種不同的優先級范圍。第一種是nice值，越大的nice值意味著更低的優先級。第二種是實時優先級，其值可以配置，越高的實時優先級數值意味著進程優先級越高。任何實時進程的優先級都高於普通進程。
CFS做法：允許每個進程運行一段時間，循環輪轉，選擇運行最少的進程作為下一個運行進程，而不再采用分配給每一個進程時間片的做法，CFS在所有可運行進程總數基礎上計算出一個進程應該運行多久，而不是依靠nice值來計算時間片。CFS引入每個進程獲得的時間片底線（最小粒度）默認情況為1ms，絕對的nice值不再影響調度決策，任何進程所獲得的處理器時間由它自己和其他所有可運行進程nice值的相對差決定。
Linux調度的實現：
時間記賬
調度器實體結構是struct sched_entity，它嵌入在進程描述符struct task_struct中。虛擬時間以ns為單位，存在vruntime變量中，它和定時器節拍不再相關，vruntime變量可以准確測定進程的運行時間，而且可以知道誰應該是下一個被運行的進程。
進程選擇
當CFS需要選擇下一個運行進程時，它會挑一個具有最小vruntime的進程，這就是CFS調度算法的核心：選擇具有最小的vruntime的任務。這裡采用紅黑樹實現的。
調度器入口
進程調度的主要入口點是schedule函數，該函數會以優先級為序，從高到低，依次檢查每一個調度器，並且從最高優先級的調度器中，選擇最高優先級的進程。
睡眠和喚醒
對於睡眠，內核的操作是：進程把自己標記為休眠狀態，從可執行紅黑樹中移出，放入等待隊列，然後調用schedule函數選擇和執行一個其他進程。對於喚醒，正好相反，進程被設置為可執行狀態，然後再從等待隊列中移到可執行紅黑樹中。
休眠有兩種進程狀態：TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。它們唯一的區別在於處在TASK_UNINTERRUPTIBLE的進程會忽略信號，處於TASK_INTERRUPTIBLE狀態的進程如果接收到一個信號，會被提前喚醒並響應該信號。兩種狀態的進程位於同一個等待隊列上，等待某些事情，不能夠運行。
關於休眠還需要注意一點：存在虛假的喚醒，所以有時候需要一個循環處理來保證進程被喚醒的條件真正大達成。
等待隊列的使用
static DECLARE_WAIT_QUEUE_HEAD(button_waitq); //定義等待隊列頭
wait_event_interruptible(button_waitq, ev_press); //休眠
wake_up_interruptible(&button_waitq); //喚醒
搶占和上下文切換
上下文切換就是從一個可執行進程切換到另一個可執行進程。Schedule函數主要完成兩個工作：其一，把虛擬內存從上一個進程映射切換到新進程中。其二，從上一個進程的處理器狀態切換到新進程的處理器狀態。
內核必須知道在什麼時候調用schedule函數，如何僅靠用戶程序代碼顯式地調用schedule，它們可能就會永遠的執行下去，所以內核中提供了一個need_resched標志來表明是否需要重新執行一次調度，該標志對於內核來講是一個信息，它表示有其他進程應當被運行了，要盡快調用調度程序。
用戶搶占
內核即將返回用戶空間的時候，如果need_resched標志被設置，會導致schedule函數被調用，此時就會發生用戶搶占。用戶搶占在如下情況時產生：其一，從系統調用返回用戶空間時。其二，從中斷處理程序返回用戶空間時。
內核搶占
在2.6版內核中，內核引入搶占能力，只要重新調度是安全的，即只要沒有持有鎖，內核就可以在任何時候搶占正在執行的任務。為了支持內核搶占，在每個進程的thread_info引入preempt_count計數器，當做一把鎖來使用。內核搶占在如下情況時產生：其一，中斷處理程序正在執行，且返回內核空間之前。其二，內核代碼再一次具有可搶占性的時候。其三，如果內核中的任務顯式地調用schedule函數。其四，如果內核中的任務阻塞（這樣會調用schedule函數）。
