本博客系列是學習併發編程過程中的記錄總結。由於文章比較多,寫的時間也比較散,所以我整理了個目錄貼(傳送門),方便查閱。 "併發編程系列博客傳送門" 本文是轉載問斬,原文請見 "這裡" 一、Exchanger簡介 Exchanger——交換器,是JDK1.5時引入的一個同步器,從字面上就可以看出,這個 ...
本博客系列是學習併發編程過程中的記錄總結。由於文章比較多,寫的時間也比較散,所以我整理了個目錄貼(傳送門),方便查閱。
本文是轉載問斬,原文請見這裡
一、Exchanger簡介
Exchanger——交換器,是JDK1.5時引入的一個同步器,從字面上就可以看出,這個類的主要作用是交換數據。
Exchanger有點類似於CyclicBarrier
,我們知道CyclicBarrier是一個柵欄,到達柵欄的線程需要等待其它一定數量的線程到達後,才能通過柵欄。
Exchanger可以看成是一個雙向柵欄,如下圖:
Thread1線程到達柵欄後,會首先觀察有沒其它線程已經到達柵欄,如果沒有就會等待,如果已經有其它線程(Thread2)已經到達了,就會以成對的方式交換各自攜帶的信息,因此Exchanger非常適合用於兩個線程之間的數據交換。
二、Exchanger示例
我們來看一個示例,理解下Exchanger的功能:
示例:假設現在有1個生產者,1個消費者,如果要實現生產者-消費者模式,一般的思路是利用隊列作為一個消息隊列,生產者不斷生產消息,然後入隊;消費者不斷從消息隊列中取消息進行消費。如果隊列滿了,生產者等待,如果隊列空了,消費者等待。
我們來看下如何利用Exchanger實現生產者-消息者模式:
生產者:
public class Producer implements Runnable {
private final Exchanger<Message> exchanger;
public Producer(Exchanger<Message> exchanger) {
this.exchanger = exchanger;
}
@Override
public void run() {
Message message = new Message(null);
for (int i = 0; i < 3; i++) {
try {
Thread.sleep(1000);
message.setV(String.valueOf(i));
System.out.println(Thread.currentThread().getName() + ": 生產了數據[" + i + "]");
message = exchanger.exchange(message);
System.out.println(Thread.currentThread().getName() + ": 交換得到數據[" + String.valueOf(message.getV()) + "]");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
消費者:
public class Consumer implements Runnable {
private final Exchanger<Message> exchanger;
public Consumer(Exchanger<Message> exchanger) {
this.exchanger = exchanger;
}
@Override
public void run() {
Message msg = new Message(null);
while (true) {
try {
Thread.sleep(1000);
msg = exchanger.exchange(msg);
System.out.println(Thread.currentThread().getName() + ": 消費了數據[" + msg.getV() + "]");
msg.setV(null);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
Main:
public class Main {
public static void main(String[] args) {
Exchanger<Message> exchanger = new Exchanger<>();
Thread t1 = new Thread(new Consumer(exchanger), "消費者-t1");
Thread t2 = new Thread(new Producer(exchanger), "生產者-t2");
t1.start();
t2.start();
}
}
輸出:
生產者-t2: 生產了數據[0]
生產者-t2: 交換得到數據[null]
消費者-t1: 消費了數據[0]
生產者-t2: 生產了數據[1]
消費者-t1: 消費了數據[1]
生產者-t2: 交換得到數據[null]
生產者-t2: 生產了數據[2]
消費者-t1: 消費了數據[2]
生產者-t2: 交換得到數據[null]
上述示例中,生產者生產了3個數據:0、1、2。通過Exchanger與消費者進行交換。可以看到,消費者消費完後會將空的Message交換給生產者。
三、Exchanger原理
Exchanger的構造
我們先來看下Exchanger的構造,Exchanger只有一個空構造器:
public Exchanger() {
participant = new Participant();
}
構造時,內部創建了一個Participant對象,Participant是Exchanger的一個內部類,本質就是一個ThreadLocal,用來保存線程本地變數Node:
static final class Participant extends ThreadLocal<Node> {
public Node initialValue() { return new Node(); }
}
我們可以把Node對象理解成每個線程自身攜帶的交換數據:
@sun.misc.Contended static final class Node {
int index; // Arena index
int bound; // Last recorded value of Exchanger.bound
int collides; // Number of CAS failures at current bound
int hash; // Pseudo-random for spins
Object item; // This thread's current item
volatile Object match; // Item provided by releasing thread
volatile Thread parked; // Set to this thread when parked, else null
}
Exchanger的單槽位交換
Exchanger有兩種數據交換的方式,當併發量低的時候,內部採用“單槽位交換”;併發量高的時候會採用“多槽位交換”。
我們先來看下exchange方法:
public V exchange(V x) throws InterruptedException {
Object v;
Object item = (x == null) ? NULL_ITEM : x; // translate null args
if ((arena != null ||
(v = slotExchange(item, false, 0L)) == null) &&
((Thread.interrupted() || // disambiguates null return
(v = arenaExchange(item, false, 0L)) == null)))
throw new InterruptedException();
return (v == NULL_ITEM) ? null : (V)v;
}
可以看到exchange其實就是一個用於判斷數據交換方式的方法,它的內部會根據Exchanger的某些欄位狀態來判斷當前應該採用單槽交換(slotExchange)還是多槽交換(arenaExchange),整個判斷的流程圖如下:
Exchanger的arena欄位是一個Node類型的數組,代表了一個槽數組,只在多槽交換時會用到。此外,Exchanger還有一個slot欄位,表示單槽交換結點,只在單槽交換時使用。
slot欄位最終會指向首個到達的線程的自身Node結點,表示線程占用了槽位。
//多槽交換數組
private volatile Node[] arena;
//單槽交換節點
private volatile Node slot;
單槽交換示意圖:
我們來看下Exchanger具體是如何實現單槽交換的,單槽交換方法slotExchange並不複雜,slotExchange的入參item表示當前線程攜帶的數據,返回值正常情況下為配對線程攜帶的數據:
/**
* 單槽交換
*
* @param item 待交換的數據
* @return 其它配對線程的數據; 如果多槽交換被激活或被中斷返回null, 如果超時返回TIMED_OUT(一個Obejct對象)
*/
private final Object slotExchange(Object item, boolean timed, long ns) {
Node p = participant.get(); // 當前線程攜帶的交換結點
Thread t = Thread.currentThread();
if (t.isInterrupted()) // 線程的中斷狀態檢查
return null;
for (Node q; ; ) {
if ((q = slot) != null) { // slot != null, 說明已經有線程先到並占用了slot
if (U.compareAndSwapObject(this, SLOT, q, null)) {
Object v = q.item; // 獲取交換值
q.match = item; // 設置交換值
Thread w = q.parked;
if (w != null) // 喚醒在此槽位等待的線程
U.unpark(w);
return v; // 交換成功, 返回結果
}
// CPU核數數多於1個, 且bound為0時創建arena數組,並將bound設置為SEQ大小
if (NCPU > 1 && bound == 0 && U.compareAndSwapInt(this, BOUND, 0, SEQ))
arena = new Node[(FULL + 2) << ASHIFT];
} else if (arena != null) // slot == null && arena != null
// 單槽交換中途出現了初始化arena的操作,需要重新直接路由到多槽交換(arenaExchange)
return null;
else { // 當前線程先到, 則占用此slot
p.item = item;
if (U.compareAndSwapObject(this, SLOT, null, p)) // 將slot槽占用
break;
p.item = null; // CAS操作失敗, 繼續下一次自旋
}
}
// 執行到這, 說明當前線程先到達, 且已經占用了slot槽, 需要等待配對線程到達
int h = p.hash;
long end = timed ? System.nanoTime() + ns : 0L;
int spins = (NCPU > 1) ? SPINS : 1; // 自旋次數, 與CPU核數有關
Object v;
while ((v = p.match) == null) { // p.match == null表示配對的線程還未到達
if (spins > 0) { // 優化操作:自旋過程中隨機釋放CPU
h ^= h << 1;
h ^= h >>> 3;
h ^= h << 10;
if (h == 0)
h = SPINS | (int) t.getId();
else if (h < 0 && (--spins & ((SPINS >>> 1) - 1)) == 0)
Thread.yield();
} else if (slot != p) // 優化操作:配對線程已經到達, 但是還未完全準備好, 所以需要再自旋等待一會兒
spins = SPINS;
else if (!t.isInterrupted() && arena == null &&
(!timed || (ns = end - System.nanoTime()) > 0L)) { //已經自旋很久了, 還是等不到配對, 此時才阻塞當前線程
U.putObject(t, BLOCKER, this);
p.parked = t;
if (slot == p)
U.park(false, ns); // 阻塞當前線程
p.parked = null;
U.putObject(t, BLOCKER, null);
} else if (U.compareAndSwapObject(this, SLOT, p, null)) { // 超時或其他(取消), 給其他線程騰出slot
v = timed && ns <= 0L && !t.isInterrupted() ? TIMED_OUT : null;
break;
}
}
U.putOrderedObject(p, MATCH, null);
p.item = null;
p.hash = h;
return v;
}
上述代碼的整個流程大致如下:
首先到達的線程:
- 如果當前線程是首個到達的線程,會將slot欄位指向自身的Node結點,表示槽位被占用;
- 然後,線程會自旋一段時間,如果經過一段時間的自旋還是等不到配對線程到達,就會進入阻塞。(這裡之所以不直接阻塞,而是自旋,是出於線程上下文切換開銷的考慮,屬於一種優化手段)
稍後到達的配對線程:
如果當前線程(配對線程)不是首個到達的線程,則到達時槽(slot)已經被占用,此時slot指向首個到達線程自身的Node結點。配對線程會將slot置空,並取Node中的item作為交換得到的數據返回,另外,配對線程會把自身攜帶的數據存入Node的match欄位中,並喚醒Node.parked
所指向的線程(也就是先到達的線程)。
首先到達的線程被喚醒:
線程被喚醒後,由於match不為空(存放了配對線程攜帶過來的數據),所以會退出自旋,然後將match對應的值返回。
這樣,線程A和線程B就實現了數據交換,整個過程都沒有用到同步操作。
Exchanger的多槽位交換
Exchanger最複雜的地方就是它的多槽位交換(arenaExchange),我們先看下,什麼時候會觸發多槽位交換?
我們之前說了,併發量大的時候會觸發多槽交換,這個說法並不准確。
單槽交換(slotExchange)中有這樣一段代碼:
也就是說,如果在單槽交換中,同時出現了多個配對線程競爭修改slot槽位,導致某個線程CAS修改slot失敗時,就會初始化arena多槽數組,後續所有的交換都會走arenaExchange:
/**
* 多槽交換
*
* @param item 待交換的數據
* @return 其它配對線程的數據; 如果被中斷返回null, 如果超時返回TIMED_OUT(一個Obejct對象)
*/
private final Object arenaExchange(Object item, boolean timed, long ns) {
Node[] a = arena;
Node p = participant.get(); // 當前線程攜帶的交換結點
for (int i = p.index; ; ) { // 當前線程的arena索引
int b, m, c;
long j;
// 從arena數組中選出偏移地址為(i << ASHIFT) + ABASE的元素, 即真正可用的Node
Node q = (Node) U.getObjectVolatile(a, j = (i << ASHIFT) + ABASE);
if (q != null && U.compareAndSwapObject(a, j, q, null)) { // CASE1: 槽不為空,說明已經有線程到達併在等待了
Object v = q.item; // 獲取已經到達的線程所攜帶的值
q.match = item; // 把當前線程攜帶的值交換給已經到達的線程
Thread w = q.parked; // q.parked指向已經到達的線程
if (w != null)
U.unpark(w); // 喚醒已經到達的線程
return v;
} else if (i <= (m = (b = bound) & MMASK) && q == null) { // CASE2: 有效槽位位置且槽位為空
p.item = item;
if (U.compareAndSwapObject(a, j, null, p)) { // 占用該槽位, 成功
long end = (timed && m == 0) ? System.nanoTime() + ns : 0L;
Thread t = Thread.currentThread();
for (int h = p.hash, spins = SPINS; ; ) { // 自旋等待一段時間,看看有沒其它配對線程到達該槽位
Object v = p.match;
if (v != null) { // 有配對線程到達了該槽位
U.putOrderedObject(p, MATCH, null);
p.item = null;
p.hash = h;
return v; // 返回配對線程交換過來的值
} else if (spins > 0) {
h ^= h << 1;
h ^= h >>> 3;
h ^= h << 10;
if (h == 0) // initialize hash
h = SPINS | (int) t.getId();
else if (h < 0 && // approx 50% true
(--spins & ((SPINS >>> 1) - 1)) == 0)
Thread.yield(); // 每一次等待有兩次讓出CPU的時機
} else if (U.getObjectVolatile(a, j) != p) // 優化操作:配對線程已經到達, 但是還未完全準備好, 所以需要再自旋等待一會兒
spins = SPINS;
else if (!t.isInterrupted() && m == 0 &&
(!timed || (ns = end - System.nanoTime()) > 0L)) { // 等不到配對線程了, 阻塞當前線程
U.putObject(t, BLOCKER, this);
p.parked = t; // 在結點引用當前線程,以便配對線程到達後喚醒我
if (U.getObjectVolatile(a, j) == p)
U.park(false, ns);
p.parked = null;
U.putObject(t, BLOCKER, null);
} else if (U.getObjectVolatile(a, j) == p &&
U.compareAndSwapObject(a, j, p, null)) { // 嘗試縮減arena槽數組的大小
if (m != 0) // try to shrink
U.compareAndSwapInt(this, BOUND, b, b + SEQ - 1);
p.item = null;
p.hash = h;
i = p.index >>>= 1; // descend
if (Thread.interrupted())
return null;
if (timed && m == 0 && ns <= 0L)
return TIMED_OUT;
break; // expired; restart
}
}
} else // 占用槽位失敗
p.item = null;
} else { // CASE3: 無效槽位位置, 需要擴容
if (p.bound != b) {
p.bound = b;
p.collides = 0;
i = (i != m || m == 0) ? m : m - 1;
} else if ((c = p.collides) < m || m == FULL ||
!U.compareAndSwapInt(this, BOUND, b, b + SEQ + 1)) {
p.collides = c + 1;
i = (i == 0) ? m : i - 1; // cyclically traverse
} else
i = m + 1; // grow
p.index = i;
}
}
}
/**
* 單槽交換
*
* @param item 待交換的數據
* @return 其它配對線程的數據; 如果多槽交換被激活或被中斷返回null, 如果超時返回TIMED_OUT(一個Obejct對象)
*/
private final Object slotExchange(Object item, boolean timed, long ns) {
Node p = participant.get(); // 當前線程攜帶的交換結點
Thread t = Thread.currentThread();
if (t.isInterrupted()) // 線程的中斷狀態檢查
return null;
for (Node q; ; ) {
if ((q = slot) != null) { // slot != null, 說明已經有線程先到並占用了slot
if (U.compareAndSwapObject(this, SLOT, q, null)) {
Object v = q.item; // 獲取交換值
q.match = item; // 設置交換值
Thread w = q.parked;
if (w != null) // 喚醒在此槽位等待的線程
U.unpark(w);
return v; // 交換成功, 返回結果
}
// CPU核數數多於1個, 且bound為0時創建arena數組,並將bound設置為SEQ大小
if (NCPU > 1 && bound == 0 && U.compareAndSwapInt(this, BOUND, 0, SEQ))
arena = new Node[(FULL + 2) << ASHIFT];
} else if (arena != null) // slot == null && arena != null
// 單槽交換中途出現了初始化arena的操作,需要重新直接路由到多槽交換(arenaExchange)
return null;
else { // 當前線程先到, 則占用此slot
p.item = item;
if (U.compareAndSwapObject(this, SLOT, null, p)) // 將slot槽占用
break;
p.item = null; // CAS操作失敗, 繼續下一次自旋
}
}
// 執行到這, 說明當前線程先到達, 且已經占用了slot槽, 需要等待配對線程到達
int h = p.hash;
long end = timed ? System.nanoTime() + ns : 0L;
int spins = (NCPU > 1) ? SPINS : 1; // 自旋次數, 與CPU核數有關
Object v;
while ((v = p.match) == null) { // p.match == null表示配對的線程還未到達
if (spins > 0) { // 優化操作:自旋過程中隨機釋放CPU
h ^= h << 1;
h ^= h >>> 3;
h ^= h << 10;
if (h == 0)
h = SPINS | (int) t.getId();
else if (h < 0 && (--spins & ((SPINS >>> 1) - 1)) == 0)
Thread.yield();
} else if (slot != p) // 優化操作:配對線程已經到達, 但是還未完全準備好, 所以需要再自旋等待一會兒
spins = SPINS;
else if (!t.isInterrupted() && arena == null &&
(!timed || (ns = end - System.nanoTime()) > 0L)) { //已經自旋很久了, 還是等不到配對, 此時才阻塞當前線程
U.putObject(t, BLOCKER, this);
p.parked = t;
if (slot == p)
U.park(false, ns); // 阻塞當前線程
p.parked = null;
U.putObject(t, BLOCKER, null);
} else if (U.compareAndSwapObject(this, SLOT, p, null)) { // 超時或其他(取消), 給其他線程騰出slot
v = timed && ns <= 0L && !t.isInterrupted() ? TIMED_OUT : null;
break;
}
}
U.putOrderedObject(p, MATCH, null);
p.item = null;
p.hash = h;
return v;
}
多槽交換方法arenaExchange的整體流程和slotExchange類似,主要區別在於它會根據當前線程的數據攜帶結點Node中的index欄位計算出命中的槽位。
如果槽位被占用,說明已經有線程先到了,之後的處理和slotExchange一樣;
如果槽位有效且為null,說明當前線程是先到的,就占用槽位,然後按照:spin->yield->block
這種鎖升級的順序進行優化的等待,等不到配對線程就會進入阻塞。
另外,由於arenaExchange利用了槽數組,所以涉及到槽數組的擴容和縮減問題,讀者可以自己去研讀源碼。
其次,在定位arena數組的有效槽位時,需要考慮緩存行的影響。由於高速緩存與記憶體之間是以緩存行為單位交換數據的,根據局部性原理,相鄰地址空間的數據會被載入到高速緩存的同一個數據塊上(緩存行),而數組是連續的(邏輯,涉及到虛擬記憶體)記憶體地址空間,因此,多個slot會被載入到同一個緩存行上,當一個slot改變時,會導致這個slot所在的緩存行上所有的數據(包括其他的slot)無效,需要從記憶體重新載入,影響性能。
需要註意的是,由於不同的JDK版本,同步工具類內部的實現細節千差萬別,所以最關鍵的還是理解它的設計思想。Exchanger的設計思想和LongAdder有些類似,都是通過
無鎖+分散熱點
的方式提升性能,但是個人感覺JDK1.8中的Exchanger實現更為複雜,特別是其中的多槽交換,還涉及了緩存行相關的東西。