1簡介

原子類型在構(gòu)建無鎖數(shù)據(jù)結(jié)構(gòu)，跨線程共享數(shù)據(jù)，線程間同步等多線程并發(fā)編程場景中起到至關(guān)重要的作用。本文將從Rust提供的原子類型和原子類型的內(nèi)存排序問題兩方面來介紹。

2Rust原子類型

Rust標(biāo)準(zhǔn)庫提供的原子類型在std::atomic模塊下。Rust提供了AtomicBool, AtomicU8, AtomicU16, AtomicUsize等原子類型。下面我們以AtomicUsize為例介紹原子類型提供的原子操作。基本的load，store， swap原子操作就不過多介紹了。第一個(gè)要介紹的就是重要的compare-and-swap(CAS)原子操作，絕大部分無鎖數(shù)據(jù)結(jié)構(gòu)都或多或少依賴CAS原子操作。Rust提供的compare_and_swap接口如下：

pubfncompare_and_swap(&self,
current:usize,
new:usize,
order:Ordering
)->usize

compare_and_swap接受一個(gè)期望的值和一個(gè)新的值，這里我們先忽略掉Ordering，后面會(huì)詳細(xì)介紹，如果變量的值等于期望的值，就將變量值替換成新的值返回成功，否則不做任何修改并返回失敗。compare_and_swap從語義上包含了讀(load)語義和寫(store)語義，先讀出變量的值，和期望值比較，然后寫入內(nèi)存。原子操作保證了這三個(gè)步驟是原子的，在三個(gè)步驟之間不會(huì)插入其他指令從而導(dǎo)致變量值被修改。從1.50.0開始compare_and_swap被deprecated了，現(xiàn)在需要使用compare_exchange和compare_exchange_weak接口來實(shí)現(xiàn)CAS原子操作。

pubfncompare_exchange(
&self,
current:usize,
new:usize,
success:Ordering,
failure:Ordering
)->Result

pubfncompare_exchange_weak(
&self,
current:usize,
new:usize,
success:Ordering,
failure:Ordering
)->Result

compare_exchange比compare_and_swap多了一個(gè)Ordering，兩個(gè)Ordering分別作為CAS成功的Ordering和失敗的Ordering，后面會(huì)有講解，這里先跳過。從源代碼可以看出compare_and_swap就是用compare_exchange實(shí)現(xiàn)的，只是compare_and_swap直接用成功情況下的Ordering生成在失敗情況下的Ordering，compare_exchange則有更高的靈活性。

pubfncompare_and_swap(&self,current:$int_type,new:$int_type,order:Ordering)->$int_type{
matchself.compare_exchange(current,
new,
order,
strongest_failure_ordering(order)){
Ok(x)=>x,
Err(x)=>x,
}
}

既然有了compare_exchange，那compare_exchange_weak是做什么用的呢？從官方文檔中可以看出兩個(gè)API的唯一區(qū)別是compare_exchange_weak允許spuriously fail。那么什么是spuriously fail，在x86平臺(tái)上CAS是一條指令完成的，這兩個(gè)API在x86平臺(tái)上效果沒有區(qū)別，但是在arm平臺(tái)上，CAS是由兩條指令完成的LL/SC(Load-link/store-conditional)，在arm平臺(tái)下會(huì)發(fā)生spuriously fail，來自Wikipedia的解釋

Real implementations of LL/SC do not always succeed even if there are no concurrent updates to the memory location in question. Any exceptional events between the two operations, such as a context switch, another load-link, or even (on many platforms) another load or store operation, will cause the store-conditional to spuriously fail.

簡單的翻譯就是，即使變量的值沒有被更新LL/SC也不是100%成功，在LL/SC之間的異常事件如上下文切換，另外的LL，甚至load或者store都會(huì)導(dǎo)致spuriously fail。由于spuriously fail的存在，arm平臺(tái)上compare_exchange是compare_exchange_weak加上一個(gè)loop實(shí)現(xiàn)的。通常我們?cè)谑褂肅AS的時(shí)候會(huì)把它放在一個(gè)loop中，反復(fù)重試直到成功，在這種情況下用compare_exchange_weak會(huì)獲得一定的性能提升，如果用compare_exchange則會(huì)導(dǎo)致循環(huán)套循環(huán)。那我們?cè)撊绾芜x擇compare_change和compare_exchange_weak呢？如果你想在loop中使用CAS，絕大部分情況下使用compare_exchange_weak，除非你在每一次loop中做的事情很多，spuriously fail會(huì)導(dǎo)致很大的overhead即使它很少發(fā)生，這種情況下使用compare_exchange。再或者你使用loop就是為了避免spuriously fail，那直接使用compare_exchange就可以達(dá)到你的目的。

接下來介紹另外一個(gè)重要的原子操作fetch-and-add。

pubfnfetch_add(&self,val:usize,order:Ordering)->usize

fetch_add也包含了讀寫兩層語義，只是和CAS比起來它不關(guān)心變量當(dāng)前的值，所以它一定成功。fetch_add一般用來做全局計(jì)數(shù)器。Rust提供了一系列的fetch_and_xxx操作，其中比較有趣的是fetch_update:

pubfnfetch_update(
&self,
set_order:Ordering,
fetch_order:Ordering,
f:F
)->Result
where
F:FnMut(usize)->Option,

它會(huì)接受一個(gè)函數(shù)，并將函數(shù)應(yīng)用到變量上，把生成的值寫回變量中，因?yàn)?a href="http://www.asorrir.com/v/tag/132/" target="_blank">CPU不支持類似的指令，所以其實(shí)fetch_update是使用CAS來實(shí)現(xiàn)原子性的。源代碼如下，我們可以看這里使用的是compare_exchange_weak，因?yàn)樗谝粋€(gè)loop中。

pubfnfetch_update(&self,
set_order:Ordering,
fetch_order:Ordering,
mutf:F)->Result<$int_type,?$int_type>
whereF:FnMut($int_type)->Option<$int_type>{
letmutprev=self.load(fetch_order);
whileletSome(next)=f(prev){
matchself.compare_exchange_weak(prev,next,set_order,fetch_order){
x@Ok(_)=>returnx,
Err(next_prev)=>prev=next_prev
}
}
Err(prev)
}

3內(nèi)存排序

Rust提供了五種內(nèi)存排序，由弱到強(qiáng)如下，并且內(nèi)存排序被標(biāo)記為#[non_exhaustive]表示未來可能會(huì)加入新的類型。

#[non_exhaustive]
pubenumOrdering{
Relaxed,
Release,
Acquire,
AcqRel,
SeqCst,
}

Rust的內(nèi)存排序和C++20保持一致。內(nèi)存排序作用是通過限制編譯器和CPU的reorder，來使得多個(gè)線程看到的內(nèi)存順序和我們程序所期望的一樣，所以內(nèi)存排序主要針對(duì)的是內(nèi)存的讀(load)寫(store)操作。編譯器和CPU會(huì)在編譯時(shí)和運(yùn)行時(shí)來reorder指令來達(dá)到提升性能的目的，從而導(dǎo)致程序中代碼順序會(huì)和真正執(zhí)行的順序可能會(huì)不一樣，但是reorder的前提是不會(huì)影響程序的最終結(jié)果，也就是說編譯器和CPU不會(huì)reorder相互有依賴的指令從而破壞程序原本的語義。比方說兩條CPU指令，指令A(yù)讀取一塊內(nèi)存，指令B寫一塊內(nèi)存，如果CPU發(fā)現(xiàn)指令A(yù)要讀取的內(nèi)容在cache中沒有命中需要去內(nèi)存中讀取，需要花額外的CPU cycle，如果指令B要操作的內(nèi)存已經(jīng)在cache中命中了，它可以選擇先執(zhí)后面的指令B。這時(shí)候內(nèi)存排序的作用就體現(xiàn)出來了，內(nèi)存排序告訴編譯器和CPU哪些指令可以reorder哪些不可以。接下來分別介紹每一種內(nèi)存排序的意義。

Relaxed：Relaxed Ordering不施加任何限制，CPU和編譯器可以自由reorder，使用了Relaxed Ordering的原子操作只保證原子性。

//Globalvarible staticx:AtomicU32=AtomicU32::new(0); staticy:AtomicU32=AtomicU32::new(0); //Thread1 letr1=y.load(Ordering::Relaxed); x.store(r1,Ordering::Relaxed); //Thread2 letr2=x.load(Ordering::Relaxed);//A y.store(42,Ordering::Relaxed);//B

這段程序是允許產(chǎn)生r1 == r2 == 42。按照正常的程序執(zhí)行，這個(gè)結(jié)果看似不合理，但是因?yàn)槭褂昧薘elaxed Ordering，CPU和編譯器可以自由reorder指令，指令B被reorder到指令A(yù)之前，那就會(huì)產(chǎn)生r1 == r2 == 42。

Release：Release Ordering是針對(duì)寫操作(store)的，一個(gè)使用了Release Ordering的寫操作，任何讀和寫操作（不限于對(duì)當(dāng)前原子變量）都不能被reorder到該寫操作之后。并且所有當(dāng)前線程中在該原子操作之前的所有寫操作（不限于對(duì)當(dāng)前原子變量）都對(duì)另一個(gè)對(duì)同一個(gè)原子變量使用Acquire Ordering讀操作的線程可見。Release Ordering寫和Acquire Ordering讀要配對(duì)使用從而在兩個(gè)或多個(gè)線程間建立一種同步關(guān)系。具體例子在介紹完Acquire之后一起給出。

Acquire：Acquire Ordering是針對(duì)讀操作(load)的，一個(gè)使用了Acquire Ordering的讀操作，任何讀和寫操作（不限于對(duì)當(dāng)前原子變量）都不能被reorder到該讀操作之前。并且當(dāng)前線程可以看到另一個(gè)線程對(duì)同一個(gè)原子變量使用Release Ordering寫操作之前的所有寫操作（不限于對(duì)當(dāng)前原子變量）。

如果前面的例子中l(wèi)oad使用Acquire Ordering，store使用Release Ordering，那么reorder就不會(huì)發(fā)生，r1 == r2 == 42的結(jié)果就不會(huì)產(chǎn)生。Acquire和Release動(dòng)作特別像鎖的加鎖和釋放鎖的操作，因此Acquire Ordering和Release Ordering常被用在實(shí)現(xiàn)鎖的場景。看下面的例子

//Globalvarible staticDATA:AtomicU32=AtomicU32::new(0); staticFLAG:AtomicBool=AtomicBool::new(false); //Thread1 DATA.store(10,Ordering::Relaxed);//A FLAG.store(true,Ordering::Release);//B //Thread2 while!FLAG.load(Ordering::Acquire){}//C assert!(DATA.load(Ordering::Relaxed)==10);//D

這段程序展示了兩個(gè)線程之間同步的一種方式，在線程1中我們?cè)诠蚕韮?nèi)存中寫入數(shù)據(jù)，然后把FLAG置成true，表明數(shù)據(jù)寫入完成，在線程2中，我們用一個(gè)while循環(huán)等待FLAG被置成true，當(dāng)FLAG被置成true之后，線程2一定會(huì)讀到共享內(nèi)存中的數(shù)據(jù)。線程1中的Release Ordering寫和線程2中的Acquire Ordering讀建立了順序。當(dāng)線程2跳出C行的循環(huán)表明它可以讀到線程1在B行對(duì)FLAG的寫入，按照Release-Acquire Ordering的保證，A行對(duì)DATA的寫入不會(huì)被reorder到把FLAG置成true之后，并且對(duì)DATA的寫入也會(huì)對(duì)線程2可見。假如這里沒有使用Release-Acquire Ordering，那么線程對(duì)DATA的寫入用可能會(huì)被reorder到寫FLAG之后，那么線程2就會(huì)出現(xiàn)讀到了FLAG但是讀不到DATA的情況。

AcqRel：AcqRel Ordering主要用于read-modify-write類型的操作，比如compare_and_swap，表明了它同時(shí)具有Acquire和Release的語義，讀的部分用Acquire Ordering，寫的部分用Release Ordering。

SeqCst：SeqCst是Sequential Consistent的縮寫，是一種最強(qiáng)的Ordering，在對(duì)讀使用Acquire Ordering，對(duì)寫使用Release Ordering，對(duì)read-modify-write使用AcqRel Ordering的基礎(chǔ)上再保證所有線程看到所有使用了SeqCst Ordering的操作是同一個(gè)順序，不論操作的是不是同一個(gè)變量。

這里包含了兩層意思，第一層意思SeqCst禁止了所有的reorder，針對(duì)內(nèi)存讀(load)寫(store)的reorder一共有四種情況：

loadload reorder：Arquire Ordering保證

loadstore reorder：Arquire Ordering和Release Ordering保證

storestore reorder：Release Ordering保證

storeload reorder：SeqCst Ordering保證

看下面的例子

//Globalvarible staticx:AtomicU32=AtomicU32::new(0); staticy:AtomicU32=AtomicU32::new(0); //Thread1 x.store(1,Ordering::SeqCst);//A letr1=y.load(Ordering::SeqCst);//B //Thread2 y.store(1,Ordering::SeqCst);//C letr2=x.load(Ordering::SeqCst);//D

這里如果不使用SeqCst Ordering就會(huì)出現(xiàn)r1 == r2 == 0的結(jié)果，原因是每一個(gè)線程中的load可以被reorder到store之前，即使我們分別對(duì)load和store使用Acquire Ordering和Release Ordering，因?yàn)樗鼈兌疾槐ＷCstoreload的reorder。

SeqCst Ordering的第二層意思是所有使用了SeqCst Ordering的操作在全局有一個(gè)順序，并且所有的線程都看到同樣的順序。比如說全局的順序是A->B->C->D，那么r1 == 0 && r2 == 1，并且第三個(gè)線程如果看到了y == 1，那么它一定能看到x == 1，這就是SeqCst Ordering全局唯一順序代表的意義。雖然使用SeqCst Ordering可以保證更嚴(yán)格的全局一致性，但是它也會(huì)帶來性能損失，使用正確并且合適的內(nèi)存排序才能獲得最優(yōu)的性能。

最后解釋一下compare_exchange兩個(gè)Ordering的含義，CAS包含1.讀變量，2.和期望值比較，3.寫變量三個(gè)步驟，第一個(gè)Ordering表示CAS成功下即變量當(dāng)前的值等于期望值時(shí)候，整個(gè)操作的Ordering，第二個(gè)Ordering表示如果當(dāng)前比較失敗了情況下，第一步讀操作的Ordering。看一個(gè)用CAS實(shí)現(xiàn)自旋鎖的例子

//Globallock
staticLOCK:AtomicBool=AtomicBool::new(false);
//Thread1
//Getlock
while(LOCK.compare_exchange_weak(false,true,Ordering::Acquire,Ordering::Relaxed).is_err()){}
do_something();
//Unlock
LOCK.store(false,Ordering::Release);

//Thread2
//Getlock
while(LOCK.compare_exchange_weak(false,true,Ordering::Acquire,Ordering::Relaxed).is_err()){}
do_something();
//Unlock
LOCK.store(false,Ordering::Release);

4總結(jié)

本文介紹了Rust提供的原子類型，原子操作以及和原子操作配合使用的內(nèi)存排序。深入地理解內(nèi)存排序才能寫出正確并且性能最優(yōu)的程序。內(nèi)存排序是一個(gè)很深的話題，如有錯(cuò)誤，歡迎指正，歡迎在評(píng)論區(qū)留言交流。

審核編輯：湯梓紅