十字轉(zhuǎn)門介紹

Turnstile是一種數(shù)據(jù)抽象，封裝休眠隊(duì)列和優(yōu)先級繼承互斥鎖和讀/寫鎖相關(guān)的信息。Turnstiles在Solaris7大幅改變，但基本前提仍然是相同的。首先，我們要看著2.5.1/2.6機(jī)制，然后看看在Solaris7發(fā)生什么改變。

圖1.tstile_mod的結(jié)構(gòu)

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

在開機(jī)時，當(dāng)一個線程需要一個互斥或讀/寫鎖阻止從pool中分配一個turnstile，內(nèi)核創(chuàng)建一個pool中的turnstiles塊。該pool是在圖1關(guān)閉tsp_list掛入turnstiles列表。turnstiles返回到可用pool時，線程被喚醒。代碼試圖保持pool中的turnstiles來匹配在系統(tǒng)上尋找在pool中的turnstiles每一次的內(nèi)部thread_create()函數(shù)被調(diào)用來創(chuàng)建一個新的內(nèi)核線程的內(nèi)核線程數(shù)。如果內(nèi)核線程數(shù)大于turnstiles在pool中創(chuàng)建的內(nèi)核線程的數(shù)量，代碼將動態(tài)分配的pool中的turnstiles。

當(dāng)一個執(zhí)行內(nèi)核線程都需要一個鎖，它可以調(diào)用mutex_enter()或mutex_tryenter()，它試圖獲取互斥鎖的地址通過兩種功能。更頻繁地調(diào)用mutex_enter(); mutex_tryenter()將立即返回，如果鎖不能被獲取，如果鎖被保有，而mutex_enter()將導(dǎo)致典型的旋轉(zhuǎn)或阻止行為。mutex_tryenter()例程存在的情況下，如果不能立即提供所需的互斥，調(diào)用代碼不起旋轉(zhuǎn)或阻塞。這樣一個使用的mutex_tryenter()"功能運(yùn)行"的旗幟，其中一個內(nèi)核函數(shù)功能啟動時，抓起一個互斥。另一個內(nèi)核線程使得相同的函數(shù)調(diào)用，它使一個mutex_tryenter()進(jìn)入呼叫，如果mutex_tryenter返回一個錯誤(持有鎖)，我們知道另一個線程運(yùn)行函數(shù)。讓我們來看看一個mutex_enter()調(diào)用的流動，看到在turnstiles和優(yōu)先級繼承被終結(jié)了。

mutex_enter()函數(shù)檢查鎖定類型(自適應(yīng)或自旋)鎖創(chuàng)建并初始化時建立的。如果鎖自鎖旋轉(zhuǎn)，它正被保有，代碼進(jìn)入一個的自旋循環(huán)，通過循環(huán)試圖獲取鎖與每個通路。如果鎖是自適應(yīng)的，目前被保有，代碼將檢查持有鎖的線程的狀態(tài)。如果持有人運(yùn)行，旋進(jìn)入循環(huán)，如果沒有，使的mutex_enter()調(diào)用的內(nèi)核線程最初請求鎖設(shè)置為阻止(休眠)。注意，輸入的自適應(yīng)鎖的代碼段是在處理器的系統(tǒng)信息結(jié)構(gòu)mutex_adaptive_lock_enter場遞增。自適應(yīng)鎖進(jìn)入的數(shù)量反映在mpstat的的SMTX列(1M)。

當(dāng)一個鎖被鎖住，而鎖住者沒有運(yùn)行的時候，這時為了能夠進(jìn)行休眠應(yīng)該使用一個turnstile來設(shè)置應(yīng)答線程。Turnstile是從turnstile池中分配的，并且相關(guān)結(jié)構(gòu)域會被初始化。turnstile的結(jié)構(gòu)和可適應(yīng)互斥結(jié)構(gòu)都包含被內(nèi)核用作整體實(shí)現(xiàn)的一部分的域。一個可適應(yīng)互斥結(jié)構(gòu)包含一個儲存著turnstile所等待線程的ID的域。如果等待域是空(這意味著，沒有線程在等待)，一個turnstile是從池中分配的，那互斥等待域設(shè)置為剛剛分配的turnstile的ID，并且turnstile的ts_sobj_priv_data(turnstile同步對象私有數(shù)據(jù))域設(shè)置為指向可適應(yīng)互斥結(jié)構(gòu)的地址。否則，如果一個線程已經(jīng)在為互斥等待，那已經(jīng)為互斥而分配的turnstile的地址被檢索。

在這兩種情況下，我們現(xiàn)在有一個同步對象(可適應(yīng)互斥)的turnstile，并且我們能通過關(guān)聯(lián)turnstile繼續(xù)改變線程狀態(tài)以休眠和設(shè)置休眠序列。內(nèi)核的t_block()函數(shù)就是以這個目的被調(diào)用的，同時CL_SLEEP宏也為此調(diào)用。從之前的列中應(yīng)該記住，調(diào)度特定類的函數(shù)是通過宏調(diào)用的，這些宏用于實(shí)現(xiàn)正確的基于調(diào)度內(nèi)核線程類的功能。在TS和IA類線程情況下，ts_sleep()函數(shù)被調(diào)用，并且線程的優(yōu)先級設(shè)置為SYS優(yōu)先級。這是一個優(yōu)先級的提升--當(dāng)他被喚醒是，他會得到優(yōu)先于TS和IA而運(yùn)行的優(yōu)先級--同時線程的狀態(tài)被設(shè)置為TS_SLEEP。內(nèi)核線程的t_wchan域(等待渠道)設(shè)置為同步對象操作向量的地址--一個有可適應(yīng)互斥對象特定功能的數(shù)組?；叵霃纳蟼€月一個到相似函數(shù)設(shè)定的連接為休眠序列完成了。在這種turnstile的情況下，不同的同步對象的turnstile被用以定義一個操作的向量，這向量是一種簡單的包含對象種類，擁有者的地址，和未休眠的優(yōu)先級修改獨(dú)特對象函數(shù)的數(shù)據(jù)結(jié)構(gòu)。一個同步對象的操作結(jié)構(gòu)為了所有同步對象而被聲明，這存在于Solaris內(nèi)核中。

以下為結(jié)構(gòu)的定義:

/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域設(shè)置為turnstile的地址，而線程被插入到turnstile的休眠序列中。上個月我們討論的休眠序列函數(shù)被間接地通過在turnstile頭文件(線程在休眠序列中的插入通過稱作內(nèi)核的sleep_insert()函數(shù)的TSTILE_INSERT宏完成)中定義的宏而調(diào)用。當(dāng)全部完成后，內(nèi)核線程駐留在休眠序列中和turnstile連接(如圖1所示)，同時內(nèi)核線程的t_ts魚被設(shè)置，以參考turnstile的地址。一個內(nèi)核線程只能被一個同步對象在任意時間點(diǎn)堵塞，決不能超過一個。所以，t_ts將會同時變?yōu)榭罩羔樆蛘咭粋€指向單個turnstile的指針。

我們還沒有全部完成--現(xiàn)在是時候進(jìn)行優(yōu)先級繼承檢查來決定是否鎖住鎖的線程在一個比線程回應(yīng)鎖(被放置在turnstile休眠序列中)更低(更差)的優(yōu)先級中。內(nèi)核的pi_willto()函數(shù)被調(diào)用，互斥擁有者的優(yōu)先級和線程等待相檢查。如果擁有者的優(yōu)先級比等待線程優(yōu)先級更高，那么我們不存在優(yōu)先級調(diào)換的情況，而且代碼被釋放。如果等待者優(yōu)先級比擁有者高，我們需要優(yōu)先級調(diào)換，互斥擁有者的優(yōu)先級被提高以超過等待者。內(nèi)核線程的t_epri域被用來繼承優(yōu)先級，同時當(dāng)輪到按序安排線程派遣序列(在喚醒后)時，一個在t_epri中的非空值會導(dǎo)致被占用線程優(yōu)先級的繼承。

此時，turnstile已被設(shè)置，同時等待線程也已存在于turnstile的休眠隊(duì)列中、優(yōu)先級反轉(zhuǎn)的問題的潛力也已被檢查，以及如果需要的話，優(yōu)先級繼承已被執(zhí)行。內(nèi)核現(xiàn)在進(jìn)入調(diào)度動開關(guān)switch()函數(shù)，從調(diào)度隊(duì)列中找到最好的可運(yùn)行的線程并運(yùn)行它，進(jìn)而使得執(zhí)行內(nèi)核線程放棄處理器。

讀/寫鎖本質(zhì)上與此是相同的。當(dāng)內(nèi)核線程試圖獲得一個讀/寫鎖，而這個鎖目前正在由另一個線程持有，此時turnstile功能被調(diào)用來分配turnstile(或者如果這個鎖已經(jīng)被一個turnstile所擁有，則設(shè)置turnstile指針，這意味著至少有另外一個線程在等待)。然后內(nèi)核線程被放在與turnstile關(guān)聯(lián)的休眠隊(duì)列中。正如我們前面提到的，一個關(guān)聯(lián)讀/寫鎖的turnstile會擁有兩個獨(dú)立的休眠隊(duì)列鏈表，一個用來讀一個用來寫。

喚醒機(jī)制其實(shí)很簡單。在內(nèi)核中使用鎖的約定中要求調(diào)用同步對象輸入例程(例如mutex_enter()或rw_enter())，其次需要在適當(dāng)?shù)臅r間調(diào)用結(jié)束例程(例如mutex_exit()或rw_exit())，從而釋放被持有的鎖。對于自適應(yīng)的互斥鎖或讀/寫鎖，釋放功能需要檢查同步對象中的等待域。如果有正在等待的內(nèi)核線程，turnstile宏TSTILE_WAKEONE()會被引用，同時sleepq_wakeone()函數(shù)會被調(diào)用。Turnstile的休眠隊(duì)列中最高優(yōu)先級的線程將被調(diào)度類的特定喚醒程序喚醒，并根據(jù)其優(yōu)先級放在適當(dāng)?shù)恼{(diào)度隊(duì)列(記住，在這種情況下，如果該線程在被放入休眠隊(duì)列時賦予了SYS優(yōu)先級，則它會在任何TS和IA類線程之前被喚醒)。一旦執(zhí)行，它會讓搶占另一個被堵塞的同步對象。Turnstile現(xiàn)在可以返回到可用的turnstile池中了。

那么在Solaris7中有什么不同呢?

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

圖2.turnstile table的結(jié)構(gòu)

鏈中的每個條目都具有其自己的鎖，以允許鏈執(zhí)行并發(fā)遍歷。Turnstile本身具有不同的結(jié)構(gòu);對于每一個鏈，都有一個活動列表(ts_next)和一個空閑的列表(ts_free)，還有一個計(jì)算在同步對象(waiters)中等待的線程數(shù)、一個同步對象的(ts_sobj)指針、一個連接到內(nèi)核線程的線程指針，這個內(nèi)核線程的優(yōu)先級是通過優(yōu)先級繼承得來的，以及多個休眠隊(duì)列。在2.6的實(shí)現(xiàn)中，每個turnstile有兩個休眠隊(duì)列。注意，優(yōu)先級繼承的數(shù)據(jù)被集成到了turnstile中，所以不會再有pirec結(jié)構(gòu)。

新開發(fā)的turnstile功能支持新的模型，并且集成了優(yōu)先級繼承功能。在之前的版本中，優(yōu)先級繼承代碼是內(nèi)核例程中的一組獨(dú)立的函數(shù)(例如我們之前提到的pi_willto()函數(shù))。一般事件的序列在所有的版本是一樣的。

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

現(xiàn)在已經(jīng)完成了第一步。這意味著代碼有了turnstile。接下來，內(nèi)核線程需要被設(shè)置為休眠狀態(tài)，并放在與turnstile休眠隊(duì)列，若存在優(yōu)先級反轉(zhuǎn)條件，則需要測試和解決之。Solaris7的turnstile_block()函數(shù)處理安置到休眠隊(duì)列中的請求鎖的線程，任何線程優(yōu)先級反轉(zhuǎn)測試可能已經(jīng)等待相同的鎖，就像2.6例子中那樣，放棄處理器進(jìn)入調(diào)度的swtch()函數(shù)。

在turnstile_block()，指針設(shè)置根據(jù)從turnstile_lookup()中的返回。如果turnstile指針為null，我們連接起來在哪個內(nèi)核線程的t_ts的的指針指向turnstile。(當(dāng)初始化內(nèi)核線程是在Solaris7，創(chuàng)建一個turnstile和鏈接到其t_ts指針)。如果從查詢返回的指針不為空，那么至少一個KTHREAD等待鎖作為一個結(jié)果，設(shè)置了適當(dāng)?shù)闹羔樻溄哟a(見圖2)。然后把線程進(jìn)入休眠狀態(tài)，如同前面的例子中，通過調(diào)度類特定的休眠習(xí)慣(ts_sleep())。插入同步對象使用sleepq_insert()接口描述上個月休眠隊(duì)列。在檢票口的等待者空間遞增，代碼執(zhí)行優(yōu)先級反轉(zhuǎn)檢查(現(xiàn)在的turnstile_block()例程的一部分)。同樣的規(guī)則適用于:如果鎖保持器的優(yōu)先級是較低的(差)比請求的線程的優(yōu)先級，所以請求線程的優(yōu)先級被任性的支架;持有人的t_epri字段被設(shè)置到新的優(yōu)先級，并繼承者指針在檢票口與內(nèi)核線程。此時，調(diào)度員通過調(diào)用swtch()輸入，猛拉關(guān)閉另一個內(nèi)核線程調(diào)度隊(duì)列。

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

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

當(dāng)內(nèi)核線程需要阻塞一個請求鎖時，互斥鎖和RW鎖會使用turnstile。休眠隊(duì)列在處理其他資源等待時無法通過優(yōu)先級繼承處理優(yōu)先級反轉(zhuǎn)問題時的函數(shù)來解決，turnstiles的建立就是為了解決這個問題。