線程調度是操作系統內核中的主要內容之一，它對整個操作系統的執行效率至關重要。OSKit當然也包括此項內容，而且由於線程的調度更加頻繁，所以調度成學這部分在操作系統中的比重要比它在UNIX中大許多。
4.1 線程調度算法分析
4.1.1 線程調度算法的總體描述
在分時系統中，內核給每個線程分配一段CPU時間，這段時間稱為時間片，當這段時間過去之後，內核將調度另一個線程讓其變為執行態。這就是所謂的時間片輪轉法。
與UNIX中的線程調度十分相似的是，OSKit的調度程序也采用了一種被稱為多級反饋循環調度，此種算法屬於操作系統調度程序中最常用的一種。其核心思想是：內核給線程分一個時間片，並把該線程反饋回若干優先級隊列中的某一個。一個線程在結束它之前，可能需要多次通過多次的"反饋循環"。當內核作上下文切換和恢復的時候，調度程序必須保證該線程從原來掛起的地方繼續執行，否則這種調度算法是不能采用的。
因此，我認為有必要向大家重申一下線程的上下文切換和恢復。首先，所謂線程的上下文是指由用戶地址空間的內容、硬件寄存器的內容以及與該線程有關的內核數據結構組成的。更加嚴格的講，線程的上下文是由它的用戶級上下文、寄存器上下文以及系統級上下文組成。
4.1.2 優先級逆轉法
OSKit中采用了操作系統設計中比較精彩的優先級逆轉算法，即在一個優先級較低的線程占有mutex的同時，另一個優先級較高的線程又來申請此mutex，這樣，優先級較高的線程就被比他低的線程阻塞。
此時我們引入了優先級逆轉算法，也就是說，當上述情況發生的時候，線程調度程序就將優先級較低的線程的優先級提升至與較高優先級線程一樣，這樣可以使得占有mutex的線程快速執行。
如果現在需要調度的線程不止兩個的話，該算法允許進行遞歸，也就是說，那個優先級低的線程執行還需要另外一個mutex，而此mutex被另一個優先級更低的線程占有，所以，調度程序就依次提升優先級低的線程的優先級，這就是遞歸提升。
但是，如過我們支持遞歸提升優先級的話，就可能出現死鎖，所以我們又必須引入一套檢驗死鎖的程序，這大大增加了操作系統核心的大小和系統的開銷，但使得操作系統更加完善，並可以處理實時線程。
4.2 pthread/pthread_scheduler.c
此源碼文件包括了一套完整的線程調度機制，OSKit的全部線程調度算法都集中在了這個文件之中，通過閱讀下面的函數分析，將使讀者了解OSKit到底是用什麼函數來具體實現線程調度的，並且能對我在前面敘述的概念的理解有所加深。
4.2.1清空等待調度的線程隊列
說明：為了能讓大家真正從概念上了解此函數的作用，我想有必要先說明一下什麼是線程等待隊列。由於調度程序在操作系統中也是作為一個線程出現的，並且同一時間，它只能調度一個線程，所以就會造成有許多線程等待調度但無法接受調度的情況，OSKit提供的這個函數正彌補了這個缺陷，他將所有的等待調度的線程用鏈表的形式鏈接在一起，這就是所謂的等待調度的線程隊列。顯然，清空它實際上就是釋放鏈表的指針。
static inline int posix_runq_empty ( void )
4.2.2得到等待隊列中優先級最高的線程的優先級
說明：當調度線程完成手頭的工作，要對下一個線程進行調度時，就將面臨一個問題，到底應該調度哪個等待調度的線程？OSKit提供的這個函數可以返回此時在等待隊列中優先級最高的線程，供調度線程調度。
static inline int posix_runq_maxprio ( void )return PRIORITY_MAX - ( prio - 1 );
4.2.3得到指向下一個要執行線程的指針
說明：當某個線程要轉執行態的時候，調度程序並不知道這個線程掛起在了什麼地方，我們可以通過調用OSKit提供的這個函數來找到指向要執行線程的指針。
static inline int posix_runq_onrunq ( pthread_thread_t *pthread )
4.2.4在線程的執行隊列的隊尾追加一個線程
說明：將優先級最低的線程，或者是由於其他原因要最後執行的線程添加到線程執行隊列的最後。
static inline void posix_runq_insert_tail ( pthread_thread_t *pthread )
4.2.5在線程的執行隊列的隊頭追加一個線程
說明：將優先級最高的線程或者是由於某種原因要現執行的線程添加到線程執行隊列的最前面。
static inline void posix_runq_insert_head ( pthread_thread_t *pthread )
4.2.6將等待隊列中優先級最高的線程提出隊列執行
說明：當操作系統要執行在線程執行隊列裡等待線程的時候，理所當然應該從頭開始，我們考調有此函數來實現線程出對執行的功能。
static inline pthread_thread_t * posix_runq_dequeue ( void )
注： 返回指向下一個等待線程的指針
4.2.7從等待隊列中刪除獨占資源的線程
說明：為了使操作系統能夠在總體最優化的前提下運行，OSKit規定不允許某一個線程長時間獨占系統資源，如果發現此類時間，就可以調用這個函數來將獨占資源的線程從執行隊列中刪除，以保持線程調度的公平合理。
static inline void posix_runq_remove ( pthread_thread_t *pthread )
4.2.8此時用到的調度算法
說明：在前面的章節裡，我曾經提到，線程的調度算法仿佛其屬性一樣，在初始化的時候就賦給了它，但它卻是可以更改的，OSKit就是通過調用下面的這個函數來實現在線程創建之後來改變調度算法的。
int posix_sched_schedules ( int policy )
if ( policy == SCHED_RR || policy == SCHED_FIFO )
return 1;
return 0;
4.2.9將一個線程變為運行態
說明：眾所周知，線程在系統中一般有三種狀態，OSKit通過調用該函數實現線程轉執行態的功能。
int posix_sched_setrunnable ( pthread_thread_t *pthread )
4.2.10終止該線程目前的調度算法
說明：這又是在線程創建之後改變其調度算法的一種函數調用，它的功能是中止該線程目前的調度算法。
void posix_sched_disassociate ( pthread_thread_t *pthread )
{
if (posix_runq_onrunq(pthread)) {
/* * On the scheduler queue, so its not running. */
posix_runq_remove ( pthread );
}
}
4.2.11為一個新的線程創建調度參數
說明：所謂調度參數就是調度程序決定是否執行某個線程的依據。例如，某用戶態線程最近使用CPU時間的統計等。
void posix_sched_init_schedstate ( pthread_thread_t *pthread,const struct sched_param *param )
4.2.12改變線程的調度狀態
說明：如果其調度參數符合調度條件，調度程序會通過調用OSKit提供這個函數來改變此線程的調度狀態，並將它轉為准備調度態。此時該線程被鎖住，而且要關中斷
int posix_sched_change_state ( pthread_thread_t *pthread , const struct sched_param *param )
4.2.13優先級遷移
說明：這是我在上面提到的優先級逆轉法的具體實現，OSKit就是通過調用它來完成對線程優先級的動態變更的。
int posix_sched_priority_bump ( pthread_thread_t *pthread, int newprio )
注意：這只是暫時的，僅僅適用於實時線程
4.2.14基於某種原因，線程被送回等待隊列
說明：當線程在操作系統中執行的時候，完全有可能由於用戶的原因造成當線程執行完它的時間片後返回執行隊列時，位置改變了。下邊是我對OSKit提供的幾種改變原因的注解。
int posix_sched_dispatch ( resched_flags_t reason, pthread_thread_t *pthread )
switch (reason) {
case RESCHED_USERYIELD: posix_runq_insert_tail(pthread);
/* 如果由用戶造成線程為空閒態，則插入隊尾 */
case RESCHED_YIELD: posix_runq_insert_head(pthread);
/* 如果由用戶造成線程為空閒態，則插入隊尾 */
case RESCHED_PREEMPT:
/* 根據線程擁有的優先級和其調度算法來具體分析 */
if (pthread->policy == SCHED_RR) {
if (--pthread->ticks == 0) {
posix_runq_insert_tail(pthread);
/* 如果是時間片輪轉發調度且只有一個ticks，則插入隊尾 */
pthread->ticks = SCHED_RR_INTERVAL;
}
else
posix_runq_insert_head(pthread);
/* 雖然是時間片輪轉法，但擁有的ticks不止一個，則插入對頭 */
}
else if (pthread->policy == SCHED_FIFO)
posix_runq_insert_head(pthread);
/* 如果是先來先處理法，則插入對頭 */
case RESCHED_INTERNAL: /* 使線程變為空閒態 */
default:
if (pthread == IDLETHREAD)
/* 停止所有的調度算法，將線程變成空閒態 */
panic("posix_sched_dispatch: Idlethread!\n");
}
4.2.15返回優先級最高的處於等待狀態的線程
說明：當調度程序要將一個出於等待狀態的線程加入到執行隊列中的時候，就需要有一個函數，它能返回優先級最高的等待線程，下面的函數正好就完成了這項任務。
pthread_thread_t * posix_sched_thread_next ( void )
{ if ( posix_runq_empty( ) )
return 0;
return posix_runq_dequeue( );
}
4.2.16改變線程的優先級
說明：實質是將線程從隊列中刪除，重新賦給優先級，再插入到隊尾。
OSKIT_INLINE void threads_change_priority (pthread_thread_t *pthread, int newprio)
4.2.17優先級繼承
說明：所謂優先級繼承，其理論的實質就是所有出於等待狀態的線程，在等待過程中，它的優先級會隨時間的推移慢慢提高。
void pthread_priority_inherit ( pthread_thread_t *pwaiting_for )
4.2.18不繼承優先級
說明：這其實與上一個優先級繼承正好相反，無論等待了多長時間，線程的優先級都不會因此而改變。
void pthread_priority_uninherit ( pthread_thread_t *punblocked )
4.2.19優先級遞減
說明：如果一個線程總是處於執行狀態，則出於總體最優化的考慮，OSKit會調用此函數將其優先級逐步遞減，從而使得更多的線程有被執行的可能。
void pthread_priority_decreasing_recompute ( pthread_thread_t *pthread)
本 章 小 結
本章從線程調度的一般性概括到具體實現，系統地闡述了OSKit的線程調度機制。
在第一節主要是對一般的線程調度概念的描述，並且對OSKit中最為精彩的優先級逆轉法的理論作了詳細的論述。第二節中以源代碼中的pthreads/pthread_scheduler.c為例，從等待調度的線程隊列、線程的執行隊列到優先級繼承、優先級遞減等，完整的闡明了OSKit的線程調度機制。
