2.6.25內(nèi)核實(shí)現(xiàn)了新的自旋鎖，叫做ticket spin_lock，ticket就是排隊(duì)的意思，就像看電影時(shí)拿著票有序入場(chǎng)一樣，新的自旋鎖不再是亂搶自旋鎖了，而是有序地獲得自旋鎖，這樣就消除了 一些不必要的混亂。這樣做的初衷是什么呢？首先看看自旋鎖的意義，它是一種十分高效的鎖，得不到鎖的時(shí)候不是睡眠而是自旋，自旋就是忙等，這樣就免去了睡 眠-切換-喚醒-切換的開(kāi)銷(xiāo)，畢竟一個(gè)進(jìn)程睡眠必然導(dǎo)致一次硬切換，而喚醒仍然需要一次硬切換。但是在忙等期間，cpu實(shí)際上沒(méi)有做什么有意義的事情，這 是一點(diǎn)小小的弊端，但是任何事必須圖一方面，和睡眠-切換-喚醒的開(kāi)銷(xiāo)比起來(lái)，這么做是十分有意義的。另外要明白的是，當(dāng)前實(shí)現(xiàn)的自旋鎖的爭(zhēng)搶實(shí)體實(shí)際上 是cpu，而不是進(jìn)程，在單cpu的非搶占內(nèi)核上，自旋鎖是不必要的，在單cpu的搶占內(nèi)核，自旋鎖實(shí)際就是禁用了搶占而已，只有在多cpu的環(huán)境下，自 旋鎖作為鎖的意義才真正存在，所以我們說(shuō)是cpu獲得了自旋鎖而不是別的。要了解新自旋鎖的意義還要了解老自旋鎖的實(shí)現(xiàn)。老的自旋鎖是一個(gè)整數(shù)，在cpu 企圖獲得鎖的時(shí)候要將此數(shù)減一，然后看看是否為0，如果為0，那么就獲得了鎖，如果為負(fù)數(shù)就說(shuō)明別的cpu比此cpu先獲得了鎖，然后此cpu進(jìn)入忙等， 等待占有鎖的cpu釋放鎖從而將鎖置為1，然后它再次將其減一后與0比較。這么實(shí)現(xiàn)可以看出，一個(gè)cpu企圖獲得鎖時(shí)所探測(cè)到的鎖的值是負(fù)數(shù)并且絕對(duì)值越 大，那么就有越多的cpu在爭(zhēng)搶這個(gè)自旋鎖，這看起來(lái)沒(méi)有問(wèn)題，就像踢足球一樣，那么多人搶一個(gè)球，但是足球有個(gè)人技術(shù)，團(tuán)隊(duì)合作在里面，有輸有贏的結(jié) 果，而自旋鎖就不一樣了，所有的cpu要公平競(jìng)爭(zhēng)，沒(méi)有團(tuán)隊(duì)，沒(méi)有個(gè)人技術(shù)，但是這個(gè)實(shí)現(xiàn)真的就很公平嗎？如果不考慮硬件告訴緩存，那么它可能還是比較公 平的，但是幾乎每個(gè)cpu都有硬件高速緩存，如果一個(gè)cpu得到了自旋鎖那么信息就會(huì)被讀入該cpu的緩存行，后來(lái)它釋放了這個(gè)自旋鎖，但是馬上它又去爭(zhēng) 搶同一個(gè)鎖，這樣這個(gè)cpu對(duì)于別的cpu就是不公平的，它再次得到自旋鎖的可能性要比別的cpu要大，因此，老的自旋鎖實(shí)現(xiàn)方案看似公平實(shí)際不公平，按 道理應(yīng)該讓等待時(shí)間最長(zhǎng)的cpu獲得自旋鎖。要得到這樣的效果，改進(jìn)點(diǎn)已經(jīng)很明確了，就是增加一個(gè)隊(duì)列，這個(gè)隊(duì)列的元素按照等待時(shí)間排隊(duì)，數(shù)據(jù)結(jié)構(gòu)也很簡(jiǎn) 單，增加一個(gè)list_head字段即可，如果這么實(shí)現(xiàn)當(dāng)然比較好，比較規(guī)則，比較規(guī)范，但是不是那么藝術(shù)和高效，于是新的ticket自旋鎖由運(yùn)而生。
?? 以上從理論角度闡述了老的自旋鎖的實(shí)現(xiàn)，下面看一下具體的代碼，主要是純粹的獲得鎖和釋放鎖的代碼，不再討論開(kāi)關(guān)搶占的內(nèi)容：
那 么ticket自旋鎖是如何實(shí)現(xiàn)的呢？它實(shí)際上是一個(gè)16位的數(shù)，被分為高8位和低8位，高8位代表的是爭(zhēng)搶者的順序號(hào)，也就是說(shuō)高8位從小到大的順序正 是爭(zhēng)搶者獲得鎖的順序，低8位代表?yè)碛姓叩男畔?。具體過(guò)程就是，一個(gè)cpu請(qǐng)求自旋鎖的時(shí)候，首先遞加自旋鎖的高8位存入一個(gè)變量，然后比較是否和低8位 相等，若不等則忙等，忙等中不斷比較先前存入的變量和自旋鎖的低8位是否相等，一旦相等，則代表成功獲得鎖，結(jié)束爭(zhēng)搶過(guò)程。注意，只有在一個(gè)擁有鎖的 cpu釋放鎖的時(shí)候才會(huì)導(dǎo)致自旋鎖的低8位加1。說(shuō)了等于白說(shuō)，還是看代碼實(shí)現(xiàn)吧：
linux內(nèi)核的文檔上對(duì)于ticket自旋鎖的解釋可沒(méi)有我這里這么隨便，還給出圖了呢？他們把自旋鎖的高8位叫做next，而低8位叫做了owner，想領(lǐng)略一下大師的文筆就請(qǐng)?jiān)L問(wèn)：http://lwn.net/Articles/267968/
?? ticket自旋鎖的實(shí)現(xiàn)是如此之簡(jiǎn)單使得你我都嘆為觀止，其實(shí)是個(gè)學(xué)過(guò)點(diǎn)數(shù)據(jù)結(jié)構(gòu)和算法的都會(huì)想到使用隊(duì)列來(lái)實(shí)現(xiàn)排隊(duì)的自旋鎖，卻沒(méi)想到linux用一 個(gè)16位的數(shù)就搞定了一切，我們難免有一些慚愧，還好，有一位老大和我們這些俗人是屬于一隊(duì)的，那就是微軟，windows下的排隊(duì)自旋鎖就是用隊(duì)列實(shí)現(xiàn) 的，而且實(shí)現(xiàn)極其復(fù)雜，再怎么說(shuō)，他和我們這些俗人的想法一致，我們也就沒(méi)有什么好慚愧的了。隊(duì)列實(shí)現(xiàn)有隊(duì)列實(shí)現(xiàn)的好處，比如便于擴(kuò)展，而用16位的數(shù)實(shí) 現(xiàn)的排隊(duì)自旋鎖難免讓人覺(jué)得有耍小聰明的味道，可是這就是linux，無(wú)數(shù)的小聰明積累而成的大師級(jí)的作品。下面就談?wù)剋indows下的排隊(duì)自旋鎖的實(shí) 現(xiàn)，它的實(shí)現(xiàn)比linux早，但是linux在任何方面都是不甘落后的。
?? windows的每個(gè)cpu上都有一個(gè)標(biāo)志，通過(guò)該標(biāo)志，這些標(biāo)志就是排隊(duì)自旋鎖的排隊(duì)實(shí)體，當(dāng)一個(gè)cpu要一個(gè)自旋鎖時(shí)，就將此cpu的標(biāo)志排隊(duì)，系統(tǒng) 中每個(gè)自旋鎖擁有一個(gè)隊(duì)列，此cpu的標(biāo)志要排入的隊(duì)列就是它爭(zhēng)搶的自旋鎖的隊(duì)列，注意是排入隊(duì)尾，當(dāng)有cpu釋放了自旋鎖的時(shí)候，下一個(gè)獲得鎖的cpu 就是釋放鎖的cpu標(biāo)志所在的位置后面的第一個(gè)cpu，那么釋放者是怎么把擁有權(quán)交給下一個(gè)等待者的呢？其實(shí)很簡(jiǎn)單，排隊(duì)的不是一個(gè)標(biāo)志嗎？釋放者只需要 將下一個(gè)cpu的標(biāo)志設(shè)置為一個(gè)大家商量好的標(biāo)志，該標(biāo)志表明等待者可以擁有鎖了，然后隊(duì)列中的所有cpu都在其自身的標(biāo)志上忙等就可以了，一旦檢測(cè)到標(biāo) 志代表它可以擁有鎖了，那么忙等就結(jié)束了。這個(gè)實(shí)現(xiàn)有一個(gè)很大的優(yōu)點(diǎn)就是忙等的點(diǎn)并不是全局的，而是局部的本cpu的一個(gè)標(biāo)志，因此同步的開(kāi)銷(xiāo)就很小了， 而不像linux的實(shí)現(xiàn)，動(dòng)不動(dòng)就來(lái)個(gè)lock前綴用于鎖總線。
?? 另外linux的排隊(duì)自旋鎖實(shí)現(xiàn)還有一個(gè)弊端就是只能最多有2的8次方即256個(gè)cpu等待自旋鎖，linux的解決辦法就是提供補(bǔ)丁，該補(bǔ)丁我還沒(méi)有見(jiàn) 過(guò)，因此不再討論，而windows的實(shí)現(xiàn)方式卻非常容易被擴(kuò)展，畢竟對(duì)于排隊(duì)相關(guān)的概念，隊(duì)列是一種標(biāo)準(zhǔn)的實(shí)現(xiàn)方式。
?? 上面闡述了排隊(duì)自旋鎖的相關(guān)實(shí)現(xiàn)，不管是linux還是windows，其引入的目的就是使系統(tǒng)更加高效，更加公平，當(dāng)然還有一個(gè)很少有人在意的原因就是 為了更加有序，因?yàn)橛行虻臇|西是便于管理的，而一切錯(cuò)誤的根源就是混亂和無(wú)序，操作系統(tǒng)內(nèi)核的目的就是管理，它是以管理員身份存在的，因此有序也就成了它 的一個(gè)要求，內(nèi)核很不喜歡無(wú)序的東西，因此才有了優(yōu)先級(jí)，隊(duì)列的概念。