CLH鎖的實(shí)現(xiàn)
CLH-Lock-1.png
CLH鎖的特點(diǎn)
- 使用鏈表來實(shí)現(xiàn)無界隊(duì)列
- 使用兩個(gè)
ThreadLocal變量表示指針县踢，一個(gè)指向自己的節(jié)點(diǎn)，一個(gè)指向前一個(gè)節(jié)點(diǎn)- 使用一個(gè)原子引用變量指向隊(duì)尾
- 對(duì)同一個(gè)鎖柄粹，一個(gè)線程可以多次獲取而不增加空間復(fù)雜度
- 當(dāng)線程結(jié)束后，GC會(huì)自動(dòng)回收內(nèi)存
CLH鎖的空間復(fù)雜度
如果有L把鎖呆细，n個(gè)線程棒坏，則CLH鎖的空間復(fù)雜度為O(n+L)妨猩。
解釋：如果有L把鎖潜叛，最多只使用其中的一把來保護(hù)共享數(shù)據(jù)的操作。對(duì)于這一點(diǎn)壶硅，可以參考讀寫鎖的簡單實(shí)現(xiàn)和使用為例進(jìn)行理解：
考慮最壞情形威兜，當(dāng)n個(gè)線程同時(shí)競爭其中的一把鎖L1，則根據(jù)
CLH-Lock-2.png
庐椒，則L1的空間復(fù)雜度為O(n+1)椒舵。當(dāng)n個(gè)線程依次執(zhí)行完共享數(shù)據(jù)操作后，除了
tail指針還在引用著在鎖創(chuàng)建時(shí)新建的qNode節(jié)點(diǎn)外约谈，其余的qNode節(jié)點(diǎn)都被回收了笔宿。所以當(dāng)這n個(gè)線程同時(shí)競爭其中的一把鎖L2時(shí)犁钟，增加的節(jié)點(diǎn)只有鎖創(chuàng)建時(shí)新建的qNode節(jié)點(diǎn)，其余的復(fù)雜度和L1一樣措伐。依次類推特纤，可證：有L把鎖军俊，n個(gè)線程侥加，則CLH鎖的空間復(fù)雜度為O(n+L)。
