1、策略
策略決定調度程序在何時讓什么進程運行。調度器的策略往往決定系統的整體印象，并且，還要負責優化使用處理器時間。
1.1 I/o消耗型和處理器消耗型。?
進程可以被分為I/O消耗型和處理器消耗型。前者指進程的大部分時間用來提交I/O請求或者等待I/O請求。因此，這樣的進程經常處于可運行狀態，但通常都是運行短短的一會兒，I/O請求時最后總會阻塞。
1.2 進程優先級
調度算法中最基本的一類就是基于優先級的調度。Linux內核提供了兩組獨立的優先級范圍。第一種是nice值，范圍從-20到+19，默認值是0,。nice的值越大優先級越低，nice值小的進程在nice直達的進城之前執行。第二個是實時優先級，其值是可配置的，默認情況下他的變化范圍是從0到99.任何實施進程的優先級度高于普通的進程。
1.3 時間片
1.4 進程搶占
?
1.5 調度策略的活動
2 Linux調度算法
設計新的調度算法是為了實現下列目標：
- 充分實現O(1)調度，不管有多少進程，新的調度采用的每個算法都能在恒定時間內完成。
- 全面實現SMP的可擴展性。每個村里起擁有自己的鎖和自己的可執行隊列。
- 強化SMP的親和力，盡量將相關一組任務分配給一個CPU進行連續的執行。只有在需要平衡任務隊列的大小時才在CPU之間移動進程。
- 加強交互性能。即使在系統處于相當負載的情況下，也能保證系統的相應，冰粒機調度交互式進程。
- 保證公平，在合理設定的時間范圍內，沒有進程會處于饑餓狀態。同樣的，也沒有進程能夠顯示公平地得到大量的時間片。
- 雖然最常見的優化情況是系統中只有1~2個可運行進程，但是優化也完全有能力擴展到具有多處理器且每個處理器上運行多個進程的系統中。
2.1 可執行隊列
調度程序中最基本的數據結構是運行隊列。可執行隊列定義域kernel/sechd.c中，由runqueue表示。
struct runqueue{spinlock_t lock; /* 保護運行隊列的自旋鎖 */unsigned long nr_running; /* 可運行任務數目 */unsigned long nr_switches; /* 上下文切換數目 */unsigned long expired_timestamp; /* 隊列最后被換出時間 */unsigned long nr_uninterruprible; /*處于不可中斷睡眠狀態的任務數目 */unsigned long long timestamp_last_tick; /* 最后一個調度程序的節拍 */struct task_struct *curr; /* 當前運行任務 */struct task_struct *idle; /* 該處理器的空任務 */struct mm_struct *prev_mm; /*最后運行任務的mm_struct結構體 */struct prio_array *active; /* 活動優先級隊列 */struct prio_array *expired; /*超時優先級隊列 */struct prio_array array[2]; /*實際優先級數組 */struct task_struct *migration_thread; /* 移出線程 */struct list_head *migration_queue; /*移出隊列 */atomic_t nr_iowait; /* 等待I/O操作的任務數量 */ };
?
由于可執行隊列是調度程序的核心數據結構體，所以有一組宏定義用于獲取與給定處理器或進程相關的可執行隊列。cpu_rq(processor)宏用于返回給定處理器可執行隊列的指針。this_rq()宏用來返回當前處理器的可執行隊列。最后，宏task_rq(task)返回給定任務多在的隊列指針。
在對可執行隊列晉城操作以前，應該先鎖住它。因為每個可執行隊列唯一的對應一個處理器，所以很少出現一個處理器需要鎖其他處理器的可執行隊列的情況。在其擁有者讀取或改寫隊列成員的時候，可執行隊列包含的鎖用來放置隊列被其他代碼改動。鎖住額運行隊列的最常見情況發生在你想鎖住的運行隊列上恰巧有一個特定的任務在運行，此時需要用到task_rq_lock()和task_rq_unlock()
2.2 優先級數組
每個運行隊列都有兩個優先級數組，一個活躍的和一個過期的。
2.3 重新計算時間片
?
)
