自适應自旋鎖--吞吐量和延遲以及管理開銷的折中

很多時候，當一個程序為了等待mutex而剛剛進入睡眠的時候，mutex已經被釋放了，如果能在第一時間感覺mutex被釋放那是再好不過的了，解決該問題的方式就是用自旋忙等而不是阻塞等待，是這樣嗎？ 

關于競态，當初由于不能忍受頻繁的睡眠/喚醒而引入了自旋鎖，然後又因為自旋鎖在實時系統中會導緻其它程序長時間延遲造成吞吐量下降而在實時系統中又恢複 了睡眠/喚醒，實時系統中的首要特性不是節省開銷，而是保證運作，睡眠/喚醒機制保證了争搶鎖的程序不會影響到别的程序進而保證了吞吐量不會被降低，但是 自旋鎖用mutex實作的代價是客觀存在的，它必須實作優先級繼承或者優先級置頂以保證不會發生優先級逆轉和死鎖，因為現在自旋鎖可以睡眠了，而核心又是 可以搶占的，一旦有高優先級的程序就緒，那麼它就會搶占低優先級的程序，這是如果低優先級的程序正好持有那一把鎖，那麼就會被阻塞而不能運作（單cpu或 者程序/cpu綁定的情況），此時一個中間優先級的程序搶占了低優先級的程序，那麼這會導緻高優先級的程序的阻塞時間過于長，在實時系統中必須避免這種情 況，是以在實時系統核心中，比如linux核心中，就實作了優先級繼承協定-PIP，協定的實作引入了大量的資料結構和算法，這就引入了管理開銷，這些開 銷會抵消掉一部分睡眠/喚醒帶來的吞吐量的提高和其它程序延遲的降低，是以，下面的一杆秤就需要在這二者之間撥弄秤砣了。 

傳統自旋鎖的實作保證了自旋鎖的持有者不會被打斷，這就可以保證即使高優先級的程序被破延遲也隻是在自旋，而自旋時間内持有鎖的程序會一直運作，而且運作 邏輯一直和這把鎖有關，即使它釋放了鎖之後沒有被等待者搶到，那麼搶到鎖的程序也不會做别的事（在ticket spin lock中這種混亂得到了改善），雖然延遲是有的，但是起碼都是在圍繞着鎖作正經事而不會被别的程序打斷，如果你真的在持有自旋鎖的時候調用了一個 schedule，那麼隻能怪寫代碼的人了。是以傳統的自旋鎖不用任何開銷就可以避免優先級逆轉之類的令人難堪的局面，是的，沒有任何開銷，把搶占一關鎖 一占完事，剩下的就盡情執行吧，不會被打擾，然而這樣的話雖然避免了優先級逆轉帶來的争搶鎖高優先級的程序延遲但是會引入不争搶鎖的所有高優先級程序的延 遲，因為自旋鎖簡單的關閉了搶占（簡單無開銷）。是以傳統的自旋鎖和睡眠/喚醒機制都不适合實時系統，帶有優先級繼承協定的mutex機制實作的自旋鎖是 可以的，但是管理優先級繼承協定的資料結構和算法也夠嗆，這麼多的但是降到底如何是好，現在有三種方案實作實時系統自旋鎖，第一就是傳統自旋鎖，第二就是 傳統的睡眠/喚醒機制，第三就是實作PIP的mutex機制，前兩種都基本沒有管理開銷但是因為影響系統吞吐量和延遲，第二種還會引入睡眠/喚醒開銷，這 導緻這兩種不能用，第三個方案由于不怎麼影響系統延遲但是運作開銷很大，運作開銷有睡眠/喚醒的開銷，管理複雜資料結構和算法的開銷。是以，将這三種方案 的優勢組合然後避免它們的劣勢是最好的結果了，其實這三種方案正交化一下就是：自旋鎖，睡眠/喚醒，PIP協定，其中PIP是不可省略的，是以選擇自旋鎖 的低開銷和睡眠/喚醒的高吞吐量，是以結果就是自适應自旋鎖，也就是說它會在某些情況下自旋而在另外一些情況下睡眠，這就是它的優勢。那麼在何種情況下自 旋呢？理想的情況就是自動學習，起初可能會很影響性能，畢竟要學習嘛，多次嘗試自旋以後，會得到一些統計值，比如得到鎖的平均延遲，平均自旋次數，n次自 旋内得到鎖的次數，系統根據這些統計值決定下一次是自旋還是睡眠。然而這種實作合理嗎？看似很合理啊，也很智能，幾乎不用怎麼配置就可以自動運作的很好， 但是想想看，這畢竟是在核心，核心不是秀算法的地方，智能的，複雜的算法還是在使用者空間秀比較好，核心算法和資料結構的特征就是簡單，高效，是以核心實作 的自适應鎖還是要另外開辟新的方案。 

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1274144