CAS(Compare and swap)比較和替換是設(shè)計(jì)并發(fā)算法時(shí)用到的一種技術(shù)。簡(jiǎn)單來(lái)說,比較和替換是使用一個(gè)期望值和一個(gè)變量的當(dāng)前值進(jìn)行比較,如果當(dāng)前變量的值與我們期望的值相等,就使用一個(gè)新值替換當(dāng)前變量的值。這聽起來(lái)可能有一點(diǎn)復(fù)雜但是實(shí)際上你理解之后發(fā)現(xiàn)很簡(jiǎn)單,接下來(lái),讓我們跟深入的了解一下這項(xiàng)技術(shù)。
在程序和算法中一個(gè)經(jīng)常出現(xiàn)的模式就是“check and act”模式。先檢查后操作模式發(fā)生在代碼中首先檢查一個(gè)變量的值,然后再基于這個(gè)值做一些操作。下面是一個(gè)簡(jiǎn)單的示例:
class MyLock {
private boolean locked = false;
public boolean lock() {
if(!locked) {
locked = true;
return true;
}
return false;
}
}
上面這段代碼,如果用在多線程的程序會(huì)出現(xiàn)很多錯(cuò)誤,不過現(xiàn)在請(qǐng)忘掉它。
如你所見,lock()方法首先檢查 locked>成員變量是否等于 false,如果等于,就將 locked 設(shè)為 true。
如果同個(gè)線程訪問同一個(gè) MyLock 實(shí)例,上面的 lock()將不能保證正常工作。如果一個(gè)線程檢查 locked 的值,然后將其設(shè)置為 false,與此同時(shí),一個(gè)線程 B 也在檢查 locked 的值,又或者,在線程 A 將 locked 的值設(shè)為 false 之前。因此,線程 A 和線程 B 可能都看到 locked 的值為 false,然后兩者都基于這個(gè)信息做一些操作。
為了在一個(gè)多線程程序中良好的工作,”check then act” 操作必須是原子的。原子就是說”check“操作和”act“被當(dāng)做一個(gè)原子代碼塊執(zhí)行。不存在多個(gè)線程同時(shí)執(zhí)行原子塊。
下面是一個(gè)代碼示例,把之前的 lock()方法用 synchronized 關(guān)鍵字重構(gòu)成一個(gè)原子塊。
class MyLock {
private boolean locked = false;
public synchronized boolean lock() {
if(!locked) {
locked = true;
return true;
}
return false;
}
}
現(xiàn)在 lock()方法是同步的,所以,在某一時(shí)刻只能有一個(gè)線程在同一個(gè) MyLock 實(shí)例上執(zhí)行它。
原子的 lock 方法實(shí)際上是一個(gè)”compare and swap“的例子。
現(xiàn)在 CPU 內(nèi)部已經(jīng)執(zhí)行原子的 CAS 操作。Java5 以來(lái),你可以使用 java.util.concurrent.atomic 包中的一些原子類來(lái)使用 CPU 中的這些功能。
下面是一個(gè)使用 AtomicBoolean 類實(shí)現(xiàn) lock()方法的例子:
public static class MyLock {
private AtomicBoolean locked = new AtomicBoolean(false);
public boolean lock() {
return locked.compareAndSet(false, true);
}
}
locked 變量不再是 boolean 類型而是 AtomicBoolean。這個(gè)類中有一個(gè) compareAndSet()方法,它使用一個(gè)期望值和 AtomicBoolean 實(shí)例的值比較,和兩者相等,則使用一個(gè)新值替換原來(lái)的值。在這個(gè)例子中,它比較 locked 的值和 false,如果 locked 的值為 false,則把修改為 true。 如果值被替換了,compareAndSet()返回 true,否則,返回 false。
使用 Java5+提供的 CAS 特性而不是使用自己實(shí)現(xiàn)的的好處是 Java5+中內(nèi)置的 CAS 特性可以讓你利用底層的你的程序所運(yùn)行機(jī)器的 CPU 的 CAS 特性。這會(huì)使還有 CAS 的代碼運(yùn)行更快。