什麼是自旋鎖?
自旋鎖(spinlock):是指當一個線程在擷取鎖的時候,如果鎖已經被其它線程擷取,那麼該線程将循環等待,然後不斷的判斷鎖是否能夠被成功擷取,直到擷取到鎖才會退出循環。
擷取鎖的線程一直處于活躍狀态,但是并沒有執行任何有效的任務,使用這種鎖會造成busy-waiting。
Java如何實作自旋鎖?
下面是個簡單的例子:
-
public class SpinLock { private AtomicReference<Thread> cas = new AtomicReference<Thread>(); public void lock() { Thread current = Thread.currentThread(); // 利用CAS while (!cas.compareAndSet(null, current)) { // DO nothing } } public void unlock() { Thread current = Thread.currentThread(); cas.compareAndSet(current, null); }
lock()方法利用的CAS,當第一個線程A擷取鎖的時候,能夠成功擷取到,不會進入while循環,如果此時線程A沒有釋放鎖,另一個線程B又來擷取鎖,此時由于不滿足CAS,是以就會進入while循環,不斷判斷是否滿足CAS,直到A線程調用unlock方法釋放了該鎖。
自旋鎖存在的問題
使用自旋鎖會有以下一個問題:
1. 如果某個線程持有鎖的時間過長,就會導緻其它等待擷取鎖的線程進入循環等待,消耗CPU。使用不當會造成CPU使用率極高。
2. 上面Java實作的自旋鎖不是公平的,即無法滿足等待時間最長的線程優先擷取鎖。不公平的鎖就會存在“線程饑餓”問題。
自旋鎖的優點
- 自旋鎖不會使線程狀态發生切換,一直處于使用者态,即線程一直都是active的;不會使線程進入阻塞狀态,減少了不必要的上下文切換,執行速度快
- 非自旋鎖在擷取不到鎖的時候會進入阻塞狀态,進而進入核心态,當擷取到鎖的時候需要從核心态恢複,需要線程上下文切換。 (線程被阻塞後便進入核心(Linux)排程狀态,這個會導緻系統在使用者态與核心态之間來回切換,嚴重影響鎖的性能)
可重入的自旋鎖和不可重入的自旋鎖
文章開始的時候的那段代碼,仔細分析一下就可以看出,它是不支援重入的,即當一個線程第一次已經擷取到了該鎖,在鎖釋放之前又一次重新擷取該鎖,第二次就不能成功擷取到。由于不滿足CAS,是以第二次擷取會進入while循環等待,而如果是可重入鎖,第二次也是應該能夠成功擷取到的。
而且,即使第二次能夠成功擷取,那麼當第一次釋放鎖的時候,第二次擷取到的鎖也會被釋放,而這是不合理的。
為了實作可重入鎖,我們需要引入一個計數器,用來記錄擷取鎖的線程數。
public class ReentrantSpinLock {
private AtomicReference<Thread> cas = new AtomicReference<Thread>();
private int count;
public void lock() {
Thread current = Thread.currentThread();
if (current == cas.get()) { // 如果目前線程已經擷取到了鎖,線程數增加一,然後傳回
count++;
return;
}
// 如果沒擷取到鎖,則通過CAS自旋
while (!cas.compareAndSet(null, current)) {
// DO nothing
}
}
public void unlock() {
Thread cur = Thread.currentThread();
if (cur == cas.get()) {
if (count > 0) {// 如果大于0,表示目前線程多次擷取了該鎖,釋放鎖通過count減一來模拟
count--;
} else {// 如果count==0,可以将鎖釋放,這樣就能保證擷取鎖的次數與釋放鎖的次數是一緻的了。
cas.compareAndSet(cur, null);
}
}
}
}
自旋鎖的其他變種
1. TicketLock
TicketLock主要解決的是公平性的問題。
思路:每當有線程擷取鎖的時候,就給該線程配置設定一個遞增的id,我們稱之為排隊号,同時,鎖對應一個服務号,每當有線程釋放鎖,服務号就會遞增,此時如果服務号與某個線程排隊号一緻,那麼該線程就獲得鎖,由于排隊号是遞增的,是以就保證了最先請求擷取鎖的線程可以最先擷取到鎖,就實作了公平性。
可以想象成銀行辦理業務排隊,排隊的每一個顧客都代表一個需要請求鎖的線程,而銀行服務視窗表示鎖,每當有視窗服務完成就把自己的服務号加一,此時在排隊的所有顧客中,隻有自己的排隊号與服務号一緻的才可以得到服務。
實作代碼:
public class TicketLock {
/**
* 服務号
*/
private AtomicInteger serviceNum = new AtomicInteger();
/**
* 排隊号
*/
private AtomicInteger ticketNum = new AtomicInteger();
/**
* lock:擷取鎖,如果擷取成功,傳回目前線程的排隊号,擷取排隊号用于釋放鎖. <br/>
*
* @return
*/
public int lock() {
int currentTicketNum = ticketNum.incrementAndGet();
while (currentTicketNum != serviceNum.get()) {
// Do nothing
}
return currentTicketNum;
}
/**
* unlock:釋放鎖,傳入目前持有鎖的線程的排隊号 <br/>
*
* @param ticketnum
*/
public void unlock(int ticketnum) {
serviceNum.compareAndSet(ticketnum, ticketnum + 1);
}
}
上面的實作方式是,線程擷取鎖之後,将它的排隊号傳回,等該線程釋放鎖的時候,需要将該排隊号傳入。但這樣是有風險的,因為這個排隊号是可以被修改的,一旦排隊号被不小心修改了,那麼鎖将不能被正确釋放。一種更好的實作方式如下:
public class TicketLockV2 {
/**
* 服務号
*/
private AtomicInteger serviceNum = new AtomicInteger();
/**
* 排隊号
*/
private AtomicInteger ticketNum = new AtomicInteger();
/**
* 新增一個ThreadLocal,用于存儲每個線程的排隊号
*/
private ThreadLocal<Integer> ticketNumHolder = new ThreadLocal<Integer>();
public void lock() {
int currentTicketNum = ticketNum.incrementAndGet();
// 擷取鎖的時候,将目前線程的排隊号儲存起來
ticketNumHolder.set(currentTicketNum);
while (currentTicketNum != serviceNum.get()) {
// Do nothing
}
}
public void unlock() {
// 釋放鎖,從ThreadLocal中擷取目前線程的排隊号
Integer currentTickNum = ticketNumHolder.get();
serviceNum.compareAndSet(currentTickNum, currentTickNum + 1);
}
}
上面的實作方式是将每個線程的排隊号放到了ThreadLocal中。
TicketLock存在的問題
多處理器系統上,每個程序/線程占用的處理器都在讀寫同一個變量serviceNum ,每次讀寫操作都必須在多個處理器緩存之間進行緩存同步,這會導緻繁重的系統總線和記憶體的流量,大大降低系統整體的性能。
下面介紹的MCSLock和CLHLock就是解決這個問題的。
2. CLHLock
CLH鎖是一種基于連結清單的可擴充、高性能、公平的自旋鎖,申請線程隻在本地變量上自旋,它不斷輪詢前驅的狀态,如果發現前驅釋放了鎖就結束自旋,獲得鎖。
實作代碼如下:
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
/**
* CLH的發明人是:Craig,Landin and Hagersten。
* 代碼來源:http://ifeve.com/java_lock_see2/
*/
public class CLHLock {
/**
* 定義一個節點,預設的lock狀态為true
*/
public static class CLHNode {
private volatile boolean isLocked = true;
}
/**
* 尾部節點,隻用一個節點即可
*/
private volatile CLHNode tail;
private static final ThreadLocal<CLHNode> LOCAL = new ThreadLocal<CLHNode>();
private static final AtomicReferenceFieldUpdater<CLHLock, CLHNode> UPDATER = AtomicReferenceFieldUpdater.newUpdater(CLHLock.class, CLHNode.class,
"tail");
public void lock() {
// 建立節點并将節點與目前線程儲存起來
CLHNode node = new CLHNode();
LOCAL.set(node);
// 将建立的節點設定為尾部節點,并傳回舊的節點(原子操作),這裡舊的節點實際上就是目前節點的前驅節點
CLHNode preNode = UPDATER.getAndSet(this, node);
if (preNode != null) {
// 前驅節點不為null表示當鎖被其他線程占用,通過不斷輪詢判斷前驅節點的鎖标志位等待前驅節點釋放鎖
while (preNode.isLocked) {
}
preNode = null;
LOCAL.set(node);
}
// 如果不存在前驅節點,表示該鎖沒有被其他線程占用,則目前線程獲得鎖
}
public void unlock() {
// 擷取目前線程對應的節點
CLHNode node = LOCAL.get();
// 如果tail節點等于node,則将tail節點更新為null,同時将node的lock狀态職位false,表示目前線程釋放了鎖
if (!UPDATER.compareAndSet(this, node, null)) {
node.isLocked = false;
}
node = null;
}
}
3. MCSLock
MCSLock則是對本地變量的節點進行循環。
/**
* MCS:發明人名字John Mellor-Crummey和Michael Scott
* 代碼來源:http://ifeve.com/java_lock_see2/
*/
public class MCSLock {
/**
* 節點,記錄目前節點的鎖狀态以及後驅節點
*/
public static class MCSNode {
volatile MCSNode next;
volatile boolean isLocked = true;
}
private static final ThreadLocal<MCSNode> NODE = new ThreadLocal<MCSNode>();
// 隊列
@SuppressWarnings("unused")
private volatile MCSNode queue;
// queue更新器
private static final AtomicReferenceFieldUpdater<MCSLock, MCSNode> UPDATER = AtomicReferenceFieldUpdater.newUpdater(MCSLock.class, MCSNode.class,
"queue");
public void lock() {
// 建立節點并儲存到ThreadLocal中
MCSNode currentNode = new MCSNode();
NODE.set(currentNode);
// 将queue設定為目前節點,并且傳回之前的節點
MCSNode preNode = UPDATER.getAndSet(this, currentNode);
if (preNode != null) {
// 如果之前節點不為null,表示鎖已經被其他線程持有
preNode.next = currentNode;
// 循環判斷,直到目前節點的鎖标志位為false
while (currentNode.isLocked) {
}
}
}
public void unlock() {
MCSNode currentNode = NODE.get();
// next為null表示沒有正在等待擷取鎖的線程
if (currentNode.next == null) {
// 更新狀态并設定queue為null
if (UPDATER.compareAndSet(this, currentNode, null)) {
// 如果成功了,表示queue==currentNode,即目前節點後面沒有節點了
return;
} else {
// 如果不成功,表示queue!=currentNode,即目前節點後面多了一個節點,表示有線程在等待
// 如果目前節點的後續節點為null,則需要等待其不為null(參考加鎖方法)
while (currentNode.next == null) {
}
}
} else {
// 如果不為null,表示有線程在等待擷取鎖,此時将等待線程對應的節點鎖狀态更新為false,同時将目前線程的後繼節點設為null
currentNode.next.isLocked = false;
currentNode.next = null;
}
}
}
4. CLHLock 和 MCSLock
- 都是基于連結清單,不同的是CLHLock是基于隐式連結清單,沒有真正的後續節點屬性,MCSLock是顯示連結清單,有一個指向後續節點的屬性。
- 将擷取鎖的線程狀态借助節點(node)儲存,每個線程都有一份獨立的節點,這樣就解決了TicketLock多處理器緩存同步的問題。
自旋鎖與互斥鎖
- 自旋鎖與互斥鎖都是為了實作保護資源共享的機制。
- 無論是自旋鎖還是互斥鎖,在任意時刻,都最多隻能有一個保持者。
- 擷取互斥鎖的線程,如果鎖已經被占用,則該線程将進入睡眠狀态;擷取自旋鎖的線程則不會睡眠,而是一直循環等待鎖釋放。
總結
- 自旋鎖:線程擷取鎖的時候,如果鎖被其他線程持有,則目前線程将循環等待,直到擷取到鎖。
- 自旋鎖等待期間,線程的狀态不會改變,線程一直是使用者态并且是活動的(active)。
- 自旋鎖如果持有鎖的時間太長,則會導緻其它等待擷取鎖的線程耗盡CPU。
- 自旋鎖本身無法保證公平性,同時也無法保證可重入性。
- 基于自旋鎖,可以實作具備公平性和可重入性質的鎖。
- TicketLock:采用類似銀行排号叫好的方式實作自旋鎖的公平性,但是由于不停的讀取serviceNum,每次讀寫操作都必須在多個處理器緩存之間進行緩存同步,這會導緻繁重的系統總線和記憶體的流量,大大降低系統整體的性能。
- CLHLock和MCSLock通過連結清單的方式避免了減少了處理器緩存同步,極大的提高了性能,差別在于CLHLock是通過輪詢其前驅節點的狀态,而MCS則是檢視目前節點的鎖狀态。
- CLHLock在NUMA架構下使用會存在問題。在沒有cache的NUMA系統架構中,由于CLHLock是在目前節點的前一個節點上自旋,NUMA架構中處理器通路本地記憶體的速度高于通過網絡通路其他節點的記憶體,是以CLHLock在NUMA架構上不是最優的自旋鎖。