Java語(yǔ)言中非阻塞算法的實(shí)現(xiàn)

摘要：在多線程的程序中很重要的是要保證數(shù)據(jù)的同步和安全。為了保證線程間的協(xié)調(diào)和數(shù)據(jù)安全，不同線程訪問(wèn)相同數(shù)據(jù)需要實(shí)行互斥。如果強(qiáng)制實(shí)行互斥，即一個(gè)線程使用數(shù)據(jù)時(shí)就鎖定該數(shù)據(jù)，則不同線程可能會(huì)頻繁地把自己阻塞起來(lái)，等共享資源被釋放時(shí)再恢復(fù)。非阻塞算法即無(wú)等待且無(wú)鎖定的算法。我們可以使用Java的原子變量類(lèi)來(lái)開(kāi)發(fā)非阻塞算法程序。該類(lèi)可以實(shí)現(xiàn)對(duì)數(shù)據(jù)進(jìn)行原子性的讀、寫(xiě)和修改操作，不同線程在不鎖定數(shù)據(jù)的情況下也能安全地共享變量。

關(guān)鍵詞：非阻塞算法；并發(fā)；原子變量

中圖法分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）20-0224-02

Realization of Nonblocking Algorithms in Java

ZHU Yun

（College of Information Mechanical and Electrical Engineering， Shanghai Normal University， Shanghai 200234， China）

Abstract： Multi-threads programs should promise the synchronization and security of data. We usually lock a data for a thread while other threads have to block waiting for the data. The traditional synchronization technique may be expensive if the lock is heavily contended. In the realization of lock-free concurrent algorithms， we use atomic variables， which provide atomic read-modify-write operations for safely updating shared variables without locks.

Key words： nonblocking algorithms；concurrency； atomic variables

1 背景

在多線程構(gòu)造的應(yīng)用程序中，如果只是把工作分割在多個(gè)線程中，希望能夠高效率的使用硬件，其實(shí)是無(wú)法實(shí)現(xiàn)高效率的。因?yàn)槎鄶?shù)線程需要共享一些數(shù)據(jù)，當(dāng)一個(gè)線程工作時(shí)，其他線程都在等待同步的數(shù)據(jù)。要確保線程大部分時(shí)間都在工作，這給多線程程序設(shè)計(jì)帶來(lái)更高的要求。

1.1 同步的計(jì)數(shù)器類(lèi)

圖1的代碼實(shí)現(xiàn)了一個(gè)計(jì)數(shù)器類(lèi)。該類(lèi)保存了一個(gè)值，在多線程的程序中，要保持該值在各線程中的同步。

圖1 計(jì)數(shù)器類(lèi)代碼

代碼中對(duì)計(jì)數(shù)值v的獲取、增加和減少的操作都使用了synchronized關(guān)鍵字來(lái)同步。get（）、inc（）和dec（） 操作都是使用當(dāng)前值，并寫(xiě)出新值。這是傳統(tǒng)的Java同步方式。當(dāng)一個(gè)線程進(jìn)入synchronized定義的方法操作v值，則其他線程要進(jìn)入該同步方法需要先阻塞等待。我們可以把這些操作看成是原子的讀、修改和寫(xiě)操作，即同步方法中的各項(xiàng)操作在進(jìn)行時(shí)不能被其他線程打斷，一個(gè)方法可被視為一項(xiàng)完整的操作。

1.2 鎖定的優(yōu)缺點(diǎn)

我們可以通過(guò)鎖定資源在多線程中協(xié)調(diào)共享資源的使用。通過(guò)同步，保證一個(gè)線程獨(dú)占一些變量的訪問(wèn)權(quán)，而其他線程在最終獲得變量訪問(wèn)權(quán)時(shí)可以看到之前線程對(duì)變量所做的修改，如此有效地保護(hù)數(shù)據(jù)的一致性和安全。

但這種方案有它的缺點(diǎn)。那些被阻塞來(lái)等待的線程，它們無(wú)法進(jìn)行其他任何操作，導(dǎo)致硬件資源浪費(fèi)，更糟糕是帶來(lái)死鎖的風(fēng)險(xiǎn)。另外，頻繁地獲得和等待資源將呈現(xiàn)爭(zhēng)用的狀態(tài)，線程頻繁運(yùn)行和阻塞給程序帶來(lái)額外的開(kāi)銷(xiāo)。最后，如果阻塞了高優(yōu)先級(jí)的線程，可能造成低優(yōu)先級(jí)的線程優(yōu)先運(yùn)行而高優(yōu)先級(jí)的線程被阻塞的情況。

2 非阻塞算法

無(wú)等待且無(wú)鎖定算法，也稱(chēng)為非阻塞算法。一個(gè)算法在其他線程發(fā)生延遲和失敗時(shí)都能夠繼續(xù)運(yùn)行，或者每個(gè)線程能在有限步驟中正確計(jì)算自己的操作，這樣的算法稱(chēng)為無(wú)等待算法。而無(wú)鎖定算法只是要求僅某個(gè)線程總是執(zhí)行其操作。

非阻塞算法雖然實(shí)現(xiàn)起來(lái)更為復(fù)雜，但具有如下優(yōu)點(diǎn)：不阻塞高優(yōu)先級(jí)的線程，沒(méi)有線程因爭(zhēng)用資源頻繁地阻塞和運(yùn)行，避免死鎖，幫助降低運(yùn)行成本提高程序效率。

3 非阻塞算法在Java中的實(shí)現(xiàn)

3.1 原子變量類(lèi)

JDK 5.0之后，java.util.concurrent.atomic包中提供了原子變量類(lèi)AtomicXXX，分別有對(duì)應(yīng)不同數(shù)據(jù)類(lèi)型的原子變量類(lèi)。這些類(lèi)支持原子條件的比較并設(shè)置更新。在把原子變量更新為新值時(shí)能夠觀察其他線程對(duì)原子變量的修改，如果其他線程在本次更新完成之前就對(duì)變量做了修改，那么本次更新嘗試失敗，可以繼續(xù)下一次嘗試。雖然原子變量類(lèi)完成的更新功能與前文所述的同步計(jì)數(shù)器類(lèi)例子類(lèi)似，但原子變量的操作最終是轉(zhuǎn)成硬件原語(yǔ)來(lái)實(shí)現(xiàn)的。使用原子變量類(lèi)可以減少對(duì)共享資源的競(jìng)爭(zhēng)操作，從而提高了程序的吞吐量。

3.2 非阻塞計(jì)數(shù)器

我們使用原子變量類(lèi)來(lái)實(shí)現(xiàn)簡(jiǎn)單的非阻塞算法NonblockingCounter類(lèi)（代碼如圖2）。

圖2 非阻塞計(jì)數(shù)器代碼

這是一個(gè)使用 AtomicInteger類(lèi)的計(jì)數(shù)器。其中AtomicInteger類(lèi)的compareAndSet（）方法負(fù)責(zé)將參數(shù)變量更新為新值。這個(gè)方法在完成操作時(shí)能觀察參數(shù)變量，如果更新完成前其他線程修改了它的值，那么更新就失敗。這一過(guò)程實(shí)際是依靠硬件原語(yǔ)來(lái)實(shí)現(xiàn)的。程序把compareAndSet（）方法放在循環(huán)條件中，即本次比較更新操作失敗，就進(jìn)入下一次嘗試。這樣完成了非阻塞的計(jì)數(shù)器，不需要使用鎖定。

3.3 非阻塞堆棧

原子變量類(lèi)也可以用來(lái)構(gòu)造復(fù)雜一些的程序，如圖3程序中的ConcurrentStack類(lèi)。堆棧類(lèi)需要壓入或彈出節(jié)點(diǎn)，這個(gè)操作也需要在多線程程序中成為原子操作。

圖3 非阻塞堆棧代碼

使用AtomicReference< >類(lèi)建立對(duì)堆棧節(jié)點(diǎn)的引用。push（）方法獲得當(dāng)前的頭節(jié)點(diǎn)head，構(gòu)建一個(gè)新節(jié)點(diǎn)安裝在頭節(jié)點(diǎn)之前，并更新head指向新的頭節(jié)點(diǎn)。如果頭節(jié)點(diǎn)在初始觀察之后沒(méi)有變化，那么就完成入棧操作；如果另一個(gè)線程已經(jīng)修改了堆棧，那么過(guò)程就會(huì)重新開(kāi)始。pop（）方法在彈出節(jié)點(diǎn)完成新的head頭節(jié)點(diǎn)引用時(shí)，也使用compareAndSet方法來(lái)觀察原來(lái)的頭節(jié)點(diǎn)，如沒(méi)有被其他線程修改說(shuō)明堆棧結(jié)構(gòu)未變化，則完成此次出棧過(guò)程，將head指向新的頭節(jié)點(diǎn)，方法返回彈出的節(jié)點(diǎn)。

4 結(jié)束語(yǔ)

文中通過(guò)例子說(shuō)明了使用Java提供的原子變量類(lèi)在開(kāi)發(fā)非阻塞算法方面的應(yīng)用。這些原子變量類(lèi)比較并更新的操作由硬件原語(yǔ)來(lái)實(shí)現(xiàn)，一邊觀察其他線程對(duì)變量的修改一邊完成更新。使用原子變量類(lèi)開(kāi)發(fā)非阻塞算法，不通過(guò)鎖定派生線程，能開(kāi)發(fā)出具有更好吞吐率，更能防御死鎖和優(yōu)先級(jí)倒置分發(fā)生的并發(fā)程序。

參考文獻(xiàn)：

[1] Brian Goetz .Java theory and practice： Going atomic[EB/OL].

http：//www.ibm.com/developerworks/java/library/j-jtp11234/.

[2] Brian Goetz .Java theory and practice： Introduction to nonblocking algorithms[EB/OL].http：//www.ibm.com/developerworks/java/library/j-jtp04186/.

[3] 朱贇. 小議同步和原子變量類(lèi)[J]. 福建電腦， 2010， 26（6）.

[3] 陳國(guó)君. Java程序設(shè)計(jì)基礎(chǔ)[M]. 4版.北京： 清華大學(xué)出版社， 2013.

[4] Robert Lafore. Java數(shù)據(jù)結(jié)構(gòu)和算法[M]. 計(jì)曉云， 譯. 2版. 北京： 中國(guó)電力出版社， 2004.