十字轉門

當內核線程需要阻塞一個請求鎖時，互斥鎖和RW鎖會使用turnstile。休眠隊列在處理其他資源等待時無法通過優先級繼承處理優先級反轉問題時的函數來解決，turnstiles的建立就是為了解決這個問題。

Turnstile是一種數據抽象，封裝休眠隊列和優先級繼承互斥鎖和讀/寫鎖相關的信息。Turnstiles在Solaris7大幅改變，但基本前提仍然是相同的。首先，我們要看着2.5.1/2.6機制，然後看看在Solaris7發生什麼改變。

圖1.tstile_mod的結構

tstile_mod的結構是這樣展開的。它保持turnstiles的鏈接，以及實施所需的各個領域，如pool，活躍的數字行在tsm_chunk陣列的活躍入turnstiles，鏈接到pool中的turnstiles，一個數組的指針到pool中的turnstiles塊（tsm_chunk[] -這些都是活躍的pool中的turnstiles）。turnstiles本身維護名單上的其他pool中的turnstiles，前向鏈路的結構與優先級繼承信息（pirec），數組有兩個休眠隊列，讀/寫鎖，讀操作和寫操作都保存在單獨的休眠隊列，而只有其中之一是用於互斥鎖。正如上個月我們所看到的，休眠隊列點上的隊列（sq_first）內核線程。其他環節結合在一起，包括內核線程鏈接turnstiles（KTHREAD阻塞時，對一個同步對象設置），如果一個點從KTHREAD結構pirec的內核線程的優先級改變，由於優先級反轉。由於繼承是接收者（高優先級），benef領域pirec點回的內核線程更好的優先級。

在開機時，當一個線程需要一個互斥或讀/寫鎖阻止從pool中分配一個turnstile，內核創建一個pool中的turnstiles塊。該pool是在圖1關閉tsp_list掛入turnstiles列表。turnstiles返回到可用pool時，線程被喚醒。代碼試圖保持pool中的turnstiles來匹配在系統上尋找在pool中的turnstiles每一次的內部thread_create（）函數被調用來創建一個新的內核線程的內核線程數。如果內核線程數大於turnstiles在pool中創建的內核線程的數量，代碼將動態分配的pool中的turnstiles。

當一個執行內核線程都需要一個鎖，它可以調用mutex_enter（）或mutex_tryenter（），它試圖獲取互斥鎖的地址通過兩種功能。更頻繁地調用mutex_enter（）; mutex_tryenter（）將立即返回，如果鎖不能被獲取，如果鎖被保有，而mutex_enter（）將導致典型的旋轉或阻止行為。mutex_tryenter（）例程存在的情況下，如果不能立即提供所需的互斥，調用代碼不起旋轉或阻塞。這樣一個使用的mutex_tryenter（）“功能運行”的旗幟，其中一個內核函數功能啓動時，抓起一個互斥。另一個內核線程使得相同的函數調用，它使一個mutex_tryenter（）進入呼叫，如果mutex_tryenter返回一個錯誤（持有鎖），我們知道另一個線程運行函數。讓我們來看看一個mutex_enter（）調用的流動，看到在turnstiles和優先級繼承被終結了。

mutex_enter（）函數檢查鎖定類型（自適應或自旋）鎖創建並初始化時建立的。如果鎖自鎖旋轉，它正被保有，代碼進入一個的自旋循環，通過循環試圖獲取鎖與每個通路。如果鎖是自適應的，目前被保有，代碼將檢查持有鎖的線程的狀態。如果持有人運行，旋進入循環，如果沒有，使的mutex_enter（）調用的內核線程最初請求鎖設置為阻止（休眠）。注意，輸入的自適應鎖的代碼段是在處理器的系統信息結構mutex_adaptive_lock_enter場遞增。自適應鎖進入的數量反映在mpstat的的SMTX列（1M）。

當一個鎖被鎖住，而鎖住者沒有運行的時候，這時為了能夠進行休眠應該使用一個turnstile來設置應答線程。Turnstile是從turnstile池中分配的，並且相關結構域會被初始化。turnstile的結構和可適應互斥結構都包含被內核用作整體實現的一部分的域。一個可適應互斥結構包含一個儲存着turnstile所等待線程的ID的域。如果等待域是空（這意味着，沒有線程在等待），一個turnstile是從池中分配的，那互斥等待域設置為剛剛分配的turnstile的ID，並且turnstile的ts_sobj_priv_data（turnstile同步對象私有數據）域設置為指向可適應互斥結構的地址。否則，如果一個線程已經在為互斥等待，那已經為互斥而分配的turnstile的地址被檢索。

在這兩種情況下，我們現在有一個同步對象（可適應互斥）的turnstile，並且我們能通過關聯turnstile繼續改變線程狀態以休眠和設置休眠序列。內核的t_block()函數就是以這個目的被調用的，同時CL_SLEEP宏也為此調用。從之前的列中應該記住，調度特定類的函數是通過宏調用的，這些宏用於實現正確的基於調度內核線程類的功能。在TS和IA類線程情況下，ts_sleep()函數被調用，並且線程的優先級設置為SYS優先級。這是一個優先級的提升——當他被喚醒是，他會得到優先於TS和IA而運行的優先級——同時線程的狀態被設置為TS_SLEEP。內核線程的t_wchan域（等待渠道）設置為同步對象操作向量的地址——一個有可適應互斥對象特定功能的數組。回想從上個月一個到相似函數設定的連接為休眠序列完成了。在這種turnstile的情況下，不同的同步對象的turnstile被用以定義一個操作的向量，這向量是一種簡單的包含對象種類，擁有者的地址，和未休眠的優先級修改獨特對象函數的數據結構。一個同步對象的操作結構為了所有同步對象而被聲明，這存在於Solaris內核中。

以下為結構的定義：

/usr/include/sys/sobject.h:

/*

* The following datastructure is used to map

* synchronization object typenumbers to the

* synchronization object'ssleep queue number

* or the synch. object'sowner function.

*/

typedef struct _sobj_ops {

char *sobj_class;

syncobj_t sobj_type;

qobj_t sobj_qnum;

kthread_t * (*sobj_owner)();

void (*sobj_unsleep)(kthread_t *);

void (*sobj_change_pri)(kthread_t *, pri_t, pri_t *);

} sobj_ops_t;

最終，線程的t_ts域設置為turnstile的地址，而線程被插入到turnstile的休眠序列中。上個月我們討論的休眠序列函數被間接地通過在turnstile頭文件（線程在休眠序列中的插入通過稱作內核的sleep_insert()函數的TSTILE_INSERT宏完成）中定義的宏而調用。當全部完成後，內核線程駐留在休眠序列中和turnstile連接（如圖1所示），同時內核線程的t_ts魚被設置，以參考turnstile的地址。一個內核線程只能被一個同步對象在任意時間點堵塞，決不能超過一個。所以，t_ts將會同時變為空指針或者一個指向單個turnstile的指針。

我們還沒有全部完成——現在是時候進行優先級繼承檢查來決定是否鎖住鎖的線程在一個比線程迴應鎖（被放置在turnstile休眠序列中）更低（更差）的優先級中。內核的pi_willto()函數被調用，互斥擁有者的優先級和線程等待相檢查。如果擁有者的優先級比等待線程優先級更高，那麼我們不存在優先級調換的情況，而且代碼被釋放。如果等待者優先級比擁有者高，我們需要優先級調換，互斥擁有者的優先級被提高以超過等待者。內核線程的t_epri域被用來繼承優先級，同時當輪到按序安排線程派遣序列（在喚醒後）時，一個在t_epri中的非空值會導致被佔用線程優先級的繼承。

此時，turnstile已被設置，同時等待線程也已存在於turnstile的休眠隊列中、優先級反轉的問題的潛力也已被檢查，以及如果需要的話，優先級繼承已被執行。內核現在進入調度動開關switch（）函數，從調度隊列中找到最好的可運行的線程並運行它，進而使得執行內核線程放棄處理器。

讀/寫鎖本質上與此是相同的。當內核線程試圖獲得一個讀/寫鎖，而這個鎖目前正在由另一個線程持有，此時turnstile功能被調用來分配turnstile（或者如果這個鎖已經被一個turnstile所擁有，則設置turnstile指針，這意味着至少有另外一個線程在等待）。然後內核線程被放在與turnstile關聯的休眠隊列中。正如我們前面提到的，一個關聯讀/寫鎖的turnstile會擁有兩個獨立的休眠隊列鏈表，一個用來讀一個用來寫。

喚醒機制其實很簡單。在內核中使用鎖的約定中要求調用同步對象輸入例程（例如mutex_enter（）或rw_enter（）），其次需要在適當的時間調用結束例程（例如mutex_exit（）或rw_exit（）），從而釋放被持有的鎖。對於自適應的互斥鎖或讀/寫鎖，釋放功能需要檢查同步對象中的等待域。如果有正在等待的內核線程，turnstile宏TSTILE_WAKEONE（）會被引用，同時sleepq_wakeone（）函數會被調用。Turnstile的休眠隊列中最高優先級的線程將被調度類的特定喚醒程序喚醒，並根據其優先級放在適當的調度隊列（記住，在這種情況下，如果該線程在被放入休眠隊列時賦予了SYS優先級，則它會在任何TS和IA類線程之前被喚醒）。一旦執行，它會讓搶佔另一個被堵塞的同步對象。Turnstile現在可以返回到可用的turnstile池中了。

那麼在Solaris7中有什麼不同呢？

正如我們前面提到的，Solaris7中的turnstiles被重新改寫：很多代碼被刪除，同時開發了一些新的、更高效的功能。Turnstiles被保留在一個全系統的哈希表turnstile_table[]中，這是一個turnstile_chain結構的數組。數組中的每一項都是turnstile_chain結構，同時也是一個turnstiles鎖鏈表的開頭。該數組利用同步對象（互斥鎖或讀/寫鎖）地址的散列函數來索引。Turnstile_table數組在引導時被初始化，如下面圖2中所示。

圖2.turnstile table的結構

鏈中的每個條目都具有其自己的鎖，以允許鏈執行併發遍歷。Turnstile本身具有不同的結構；對於每一個鏈，都有一個活動列表（ts_next）和一個空閒的列表（ts_free），還有一個計算在同步對象（waiters）中等待的線程數、一個同步對象的（ts_sobj）指針、一個連接到內核線程的線程指針，這個內核線程的優先級是通過優先級繼承得來的，以及多個休眠隊列。在2.6的實現中，每個turnstile有兩個休眠隊列。注意，優先級繼承的數據被集成到了turnstile中，所以不會再有pirec結構。

新開發的turnstile功能支持新的模型，並且集成了優先級繼承功能。在之前的版本中，優先級繼承代碼是內核例程中的一組獨立的函數（例如我們之前提到的pi_willto()函數）。一般事件的序列在所有的版本是一樣的。

讓我們繼續看上一節中的例子，內核進程通過執行mutex_enter()或者rwlock_enter()調用來請求鎖，而當前這個鎖正被另一個線程控制。---看看在Solaris7系統下會發生什麼。如上所述，在自適應互斥與控制者沒有運行的情況下，調用方將會阻止（對於讀/寫鎖，如果鎖被線程擁有，調用方總是會阻止）。Solaris7結果中，在一個同步對象turnstile_table[]調用時，我們索引的數組通過散列的同步對象的地址，如果已經存在一個turnstile（即已經有等待者），我們會得到正確的turnstile。否則，查找功能將簡單的返回一個沒有等待者的turnstile的地址。

現在已經完成了第一步。這意味着代碼有了turnstile。接下來，內核線程需要被設置為休眠狀態，並放在與turnstile休眠隊列，若存在優先級反轉條件，則需要測試和解決之。Solaris7的turnstile_block（）函數處理安置到休眠隊列中的請求鎖的線程，任何線程優先級反轉測試可能已經等待相同的鎖，就像2.6例子中那樣，放棄處理器進入調度的swtch()函數。

在turnstile_block（），指針設置根據從turnstile_lookup（）中的返回。如果turnstile指針為null，我們連接起來在哪個內核線程的t_ts的的指針指向turnstile。（當初始化內核線程是在Solaris7，創建一個turnstile和鏈接到其t_ts指針）。如果從查詢返回的指針不為空，那麼至少一個KTHREAD等待鎖作為一個結果，設置了適當的指針鏈接代碼（見圖2）。然後把線程進入休眠狀態，如同前面的例子中，通過調度類特定的休眠習慣（ts_sleep（））。插入同步對象使用sleepq_insert（）接口描述上個月休眠隊列。在檢票口的等待者空間遞增，代碼執行優先級反轉檢查（現在的turnstile_block（）例程的一部分）。同樣的規則適用於：如果鎖保持器的優先級是較低的（差）比請求的線程的優先級，所以請求線程的優先級被任性的支架;持有人的t_epri字段被設置到新的優先級，並繼承者指針在檢票口與內核線程。此時，調度員通過調用swtch（）輸入，猛拉關閉另一個內核線程調度隊列。

喚醒機制啓動如前面所述，如果有上的鎖的線程阻塞，鎖定出口例程的調用將導致一個turnstile_wakeup（）。在Solaris 7的代碼上的鎖阻塞的所有線程被喚醒，而不是隻是一個潛在的幾個線程醒來2.5.1/2.6的情況下。熟悉周圍操作系統設計的問題的讀者可能已經看到驚羣問題，這是一個豐富多彩的術語，用來描述一種情況，即多個線程正在等待相同的資源被喚醒，他們都取得了可運行，多處理器系統上，它們都使資源在同一時間被獲取。

在Sun編碼的Solaris 7中的一個足夠通用的方式turnstile_wakeup()中，從而使一個單一的的線程喚醒可以無誤地執行，而不是所有線程不可避免地一起醒來。不同的負載下的力竭性測試顯示，在實踐中，我們極少結束大量的線程阻塞鏈,因此幾乎從不碰到驚羣問題。”喚醒所有(wakeup-all)”的實施還解決了一些使喚醒一個場景變得棘手的位同步問題。