在CAS中，如何保證兩個(gè)線程的compare結(jié)果不是同時(shí)為true？比如一個(gè)簡(jiǎn)單的 int 變量，在不對(duì)這個(gè)變量加鎖的情況下僅使用 CompareAndSwap 是如何實(shí)現(xiàn)原子操作的？因?yàn)榭赡?2 個(gè)

在CAS中，如何保證兩個(gè)線程的compare結(jié)果不是同時(shí)為true？

比如一個(gè)簡(jiǎn)單的 int 變量，在不對(duì)這個(gè)變量加鎖的情況下僅使用 CompareAndSwap 是如何實(shí)現(xiàn)原子操作的？

因?yàn)榭赡?2 個(gè)線程同時(shí)拿到了這個(gè)變量，那么如果這時(shí) 2 個(gè)線程幾乎是同時(shí) compare 的時(shí)候可能就是同時(shí)為 true。

那么底層是否其實(shí)是存在類(lèi)似鎖的實(shí)現(xiàn)呢？

舉個(gè) Go 中協(xié)程的例子：

package main

import (

fmt

sync

sync/atomic

)

var counter int32 0

func main() {

n : 100

wg : new(sync.WaitGroup)

(n)

for i:0 i ltn i {

go inc(i, wg)

}

wg.Wait()

(counter)

}

func inc(i int, wg *sync.WaitGroup) {

d: 0

for {

old : counter

if (ampcount:

cas串級(jí)操作原理？

1、什么是CAS？

CAS：Compare and Swap，即比較再交換。

jdk5增加了并發(fā)包*,其下面的類(lèi)使用CAS算法實(shí)現(xiàn)了區(qū)別于synchronouse同步鎖的一種樂(lè)觀鎖。JDK 5之前Java語(yǔ)言是靠synchronized關(guān)鍵字保證同步的，這是一種獨(dú)占鎖，也是是悲觀鎖。

2、CAS算法理解

對(duì)CAS的理解，CAS是一種無(wú)鎖算法，CAS有3個(gè)操作數(shù)，內(nèi)存值V，舊的預(yù)期值A(chǔ)，要修改的新值B。當(dāng)且僅當(dāng)預(yù)期值A(chǔ)和內(nèi)存值V相同時(shí)，將內(nèi)存值V修改為B，否則什么都不做。

CAS比較與交換的偽代碼可以表示為：

do{

備份舊數(shù)據(jù)；

基于舊數(shù)據(jù)構(gòu)造新數(shù)據(jù)；

}while(!CAS( 內(nèi)存地址，備份的舊數(shù)據(jù)，新數(shù)據(jù) ))

注：t1，t2線程是同時(shí)更新同一變量56的值

因?yàn)閠1和t2線程都同時(shí)去訪問(wèn)同一變量56，所以他們會(huì)把主內(nèi)存的值完全拷貝一份到自己的工作內(nèi)存空間，所以t1和t2線程的預(yù)期值都為56。

假設(shè)t1在與t2線程競(jìng)爭(zhēng)中線程t1可以更新變量的值，而所有其他線程都失敗。失敗的線程不會(huì)被掛起，但會(huì)被告知本次比賽失敗，可以再試一次。T1線程將變量值更新為57，然后寫(xiě)入內(nèi)存。此時(shí)，對(duì)于t2，內(nèi)存值變?yōu)?7，與期望值56不一致，操作失敗(要改變的值不再是原來(lái)的值)。

(上圖通俗的解釋就是CPU更新了一個(gè)值，但是如果你要改變的值不再是原來(lái)的值，操作就會(huì)失敗，因?yàn)楹苊黠@，其他操作已經(jīng)先改變了這個(gè)值。)

意思是兩者比較時(shí)，如果相等，證明共享的數(shù)據(jù)沒(méi)有被修改，被新的值代替，然后繼續(xù)向下運(yùn)行；如果不相等，說(shuō)明共享的數(shù)據(jù)已經(jīng)被修改，放棄已經(jīng)做過(guò)的操作，然后重新執(zhí)行剛才的操作。很容易看出，CAS操作是基于共享數(shù)據(jù)不會(huì)被修改的假設(shè)，采用類(lèi)似于數(shù)據(jù)庫(kù)的提交-重試模式。當(dāng)同步的機(jī)會(huì)很少時(shí)，這種假設(shè)可以帶來(lái)很大的性能提升。

開(kāi)銷(xiāo)

前面說(shuō)過(guò)，CAS(比較和交換)是CPU的指令級(jí)操作，只有一個(gè)原子操作，所以速度很快。而且CAS避免了請(qǐng)求操作系統(tǒng)決定鎖的問(wèn)題，直接在CPU內(nèi)部完成，不打擾操作系統(tǒng)。但是CAS沒(méi)有費(fèi)用？不要！那里 這是緩存未命中的情況。這個(gè)問(wèn)題比較復(fù)雜。首先，我們需要知道CPU的硬件架構(gòu):

上圖可以看到一個(gè)8核CPU的電腦系統(tǒng)。cache(CPU有一個(gè)cache(CPU的內(nèi)部緩存，寄存器)，管芯中有一個(gè)互聯(lián)模塊，讓管芯中的兩個(gè)內(nèi)核可以互相通信。圖中央的系統(tǒng)互連模塊允許四個(gè)芯片相互通信，并將芯片與主存儲(chǔ)器連接。數(shù)據(jù)在系統(tǒng)中以 單位傳輸高速緩存線 "，對(duì)應(yīng)內(nèi)存中2的冪的字節(jié)塊，通常在32到256字節(jié)之間。當(dāng)CPU將一個(gè)變量從內(nèi)存讀入其寄存器時(shí)，它必須首先將包含該變量的緩存行讀入CPU緩存。類(lèi)似地，當(dāng)CPU將寄存器中的值存儲(chǔ)到內(nèi)存中時(shí)，它不僅必須將包含該值的緩存行讀取到CPU緩存中，還必須確保沒(méi)有其他CPU擁有該緩存行的副本。

例如，如果CPU0對(duì)某個(gè)變量執(zhí)行比較和交換操作，而該變量的緩存行在CPU7的緩存中，則會(huì)發(fā)生以下簡(jiǎn)化的事件序列:

CPU0檢查了本地緩存，沒(méi)有找到緩存行。

請(qǐng)求轉(zhuǎn)發(fā)到CPU0和CPU1的互聯(lián)模塊，檢查CPU1的本地緩存，沒(méi)有發(fā)現(xiàn)緩存線。

請(qǐng)求被轉(zhuǎn)發(fā)到系統(tǒng)互連模塊，并且檢查了其他三個(gè)管芯，并且知道緩存線受到CPU6和CPU的保護(hù)。7被保持在模具中。

請(qǐng)求被轉(zhuǎn)發(fā)到CPU6和CPU7的互連模塊，檢查這兩個(gè)CPU的緩存，找到CPU7的緩存中的緩存行。

CPU7將高速緩存行發(fā)送到附屬的互連模塊，并刷新其自己的高速緩存中的高速緩存行。

CPU6和CPU7的互連模塊將緩存線發(fā)送到系統(tǒng)互連模塊。

系統(tǒng)互連模塊將緩存線發(fā)送給CPU0和CPU1的互連模塊。

CPU0和CPU1的互連模塊將緩存線發(fā)送到CPU0的緩存。

CPU0現(xiàn)在可以對(duì)緩存中的變量執(zhí)行CAS操作。

以上是刷新不同CPU緩存的開(kāi)銷(xiāo)。最好的CAS操作消耗大約40納秒，超過(guò)60個(gè)時(shí)鐘周期。 "最佳案例 "這里的意思是對(duì)一個(gè)變量執(zhí)行CAS操作的CPU正好是最后一個(gè)操作該變量的CPU，所以對(duì)應(yīng)的緩存行已經(jīng)在該CPU的緩存中了。類(lèi)似地，最好的鎖操作(a "往返對(duì) "包括獲取鎖然后釋放鎖)花費(fèi)超過(guò)60納秒和超過(guò)100個(gè)時(shí)鐘周期。 "最佳案例 "這里意味著用于表示鎖的數(shù)據(jù)結(jié)構(gòu)已經(jīng)在獲取和釋放鎖的CPU的緩存中。因?yàn)閷?duì)并行編程的深刻理解，鎖操作比CAS操作更費(fèi)時(shí)。

在為鎖操作的數(shù)據(jù)結(jié)構(gòu)中需要兩個(gè)原子操作。高速緩存未命中消耗大約140納秒，超過(guò)200個(gè)時(shí)鐘周期。CAS操作需要在存儲(chǔ)新值時(shí)查詢變量的舊值，大約需要300納秒，超過(guò)500個(gè)時(shí)鐘周期。想想這個(gè)。在執(zhí)行CAS操作時(shí)，CPU可以執(zhí)行500條通用指令。這顯示了細(xì)粒度鎖的局限性。