動機
之前看完linux kernel的同步方式，對同步有新的理解，可以重新面對這個話題了
原子性、可見性
- 原子性: 全都完成，不然就是根本沒做
- race condition
- primitive有可能不是atomic
- java的long與double就不是
- 大部分arch可以讓32bit的資料atomic
- 但long與double不是阿
- 就可能要分兩次，這樣就出事了
- C++的atomic類別
- C++支援struct，但是struct的大小不一定
- 如果有align那好說，但是如果沒有compiler就要自己動手腳(好麻煩)
- Word Tearing
- 更新相鄰的資料時，會影響到隔壁!?
- 像boolean在java是1byte!
- 這與arch能處理的最小單位有關，大部分arch是8bits
- 所以要更新就要一次跑1byte
- 可以同時跑2個thread做java的BitSet(可以想成byte[])set
- 可能只更新其中一位或是兩位都更新
- 因為是做bitwise，所以是一次更新1byte
- java的long與double就不是
- 可見性: 在後面的指令能看到前面的影響
- reorder與亂序執行
- 不同arch的reorder規則
- 強(只准store-load): x86, sparc-tso
- 弱(LL,LS,SS,SL都可): powerpc, ia64, arm
- 資料相依
- write-read, write-write, read-write
- 這在任何arch都不會被reorder，但僅限single thread的scope
- smp與multi-thread之間沒有 (所以需要後面的規則)
- 不同arch的reorder規則
- cache
- reorder與亂序執行
- 順序性: 前面跑完才能跑後面
- reorder是會保證single thread中的code與reorder前跑出來的結果是一樣的
java memory model
happen-before(hb)
在放在A指令之前的指令所做出的改變，A指令一定看的到
- 同一個scope中具有順序性
- 在同一thread中，前一條指令對後一條指令是happen-before
- 前一個synchronized的解鎖，對後一個synchronized的加鎖是happen-before
- 先寫後讀 (先啟動後執行)
- 一個volatile的寫，對後續任何volatile的讀是happen-before
- thread的start，對該thread的所有指令是happen-before
- thread的interrupt，對所有檢查interrupt的指令是happen-before
- thread的join，對所有檢查thread存活的指令是happen-before
- obj初始化，對obj的finalize是happen-before
- A hb B，且B hb C，則A hb C
causality (因果關係)
下面是無中生有(out-of-thin-air)的其中一種例子 foo被reorder成foo2，就happen-before而言，這沒錯，但執行下去就出事
// x == y == 0
void foo(){
r1=x;
if(r1 != 0)
y=42;
}
/*
void foo2(){
y=42;
r1=x;
if(r1 != 0)
y=0;
}
*/
void bar(){
r2 = y;
if(r2 != 0)
x=42;
}
// r1==r2==42?
為了防止這種事發生，才有causality檢查
根據
- 控制流
- 資料相依
去看執行結果會不會有奇怪的東西
關於如何檢查，我看了好久還是不太懂，在ref有範例，等PLT的功力回來再說吧
實際上的做法是
- 保持原子性
- volatile (++是複合動作，要注意)
- 原本volatile只是確保取值都從mem拿，確保可見性
- 但java memory model保證volatile讀寫比較不會被reorder，進而保證了原子性(只有一寫對一個以上的讀才有!!)
- 但沒有mutual exclusion，所以如果很多thread一起攻擊的話就會出事，可以看下面的code
- synchronized
- 上barrier與禁止reorder，保持可見性與順序性
java的volatile
一個加一個減，照理來說要是0
public class Main {
public static volatile int race = 0;
private static final int INCREASE_COUNT = 10000;
public static void main (String[] args) {
Thread[] threads = new Thread[2];
System.out.println(System.currentTimeMillis());
threads[0] = new Thread(new Runnable() {
@Override
public void run () {
for (int i = 0; i < INCREASE_COUNT; i++) {
race++;
}
}
});
threads[1] = new Thread(new Runnable() {
@Override
public void run () {
for (int i = 0; i < INCREASE_COUNT; i++) {
race--;
}
}
});
threads[0].start();
threads[1].start();
while (Thread.activeCount() > 1) {
Thread.yield();
}
System.out.println(System.currentTimeMillis());
System.out.println(race);
}
}
volatile的happen-before是寫之後可以被所有讀看到，但是剛剛是一個讀前面有一堆寫 要處理這件事就是加個條件，在不符合條件時就不做事，確保只有一個寫
public class Main {
public static volatile int race = 0;
private static final int INCREASE_COUNT = 10000000;
public static void main (String[] args) {
Thread[] threads = new Thread[2];
System.out.println(System.currentTimeMillis());
threads[0] = new Thread(new Runnable() {
@Override
public void run () {
for (int i = 0; i < INCREASE_COUNT; i++) {
if (race <= 0) {
race++;
} else {
i--;
}
}
}
});
threads[1] = new Thread(new Runnable() {
@Override
public void run () {
for (int i = 0; i < INCREASE_COUNT; i++) {
if (race > 0) {
race--;
} else {
i--;
}
}
}
});
threads[0].start();
threads[1].start();
while (Thread.activeCount() > 1) {
Thread.yield();
}
System.out.println(System.currentTimeMillis());
System.out.println(race);
}
}
所以如果真的需要就是用AtomicInteger，同時我用jdoodle去跑明顯這個比較快 因為不是每次的loop都會做事，可能有不做事的時候，導致時間的浪費
import java.util.concurrent.atomic.AtomicInteger;
public class Main {
public static AtomicInteger race = new AtomicInteger();
private static final int INCREASE_COUNT = 10000000;
public static void main (String[] args) {
Thread[] threads = new Thread[2];
System.out.println(System.currentTimeMillis());
threads[0] = new Thread(new Runnable() {
@Override
public void run () {
for (int i = 0; i < INCREASE_COUNT; i++) {
race.incrementAndGet();
}
}
});
threads[1] = new Thread(new Runnable() {
@Override
public void run () {
for (int i = 0; i < INCREASE_COUNT; i++) {
race.decrementAndGet();
}
}
});
threads[0].start();
threads[1].start();
while (Thread.activeCount() > 1) {
Thread.yield();
}
System.out.println(System.currentTimeMillis());
System.out.println(race);
}
}
建到一半的物件
Double-Checked Locking
用在multi-thread生singlton，但是會出事
class Foo {
private Helper helper = null;
public Helper getHelper() {
if (helper == null) {
synchronized(this) {
if (helper == null)
helper = new Helper();
}
}
return helper;
}
}
在設定helper的值時，可以reorder成
- 先給ref
- 之後init物件
但拿到ref就會讓if過，最後有人會拿到建到一半的物件
其中一個解法是volatile，因為不會reorder
class Foo {
private volatile Helper helper = null;
public Helper getHelper() {
if (helper == null) {
synchronized(this) {
if (helper == null)
helper = new Helper();
}
}
return helper;
}
}
另一個解法是static的field，class初始化完static要存在可以利用這個特點
private static class LazyFooHolder {
public static Foo foo = new Foo();
}
public static Foo getInstance() {
return LazyFooHolder.foo;
}
final field
java memory model保證任何access final的thread會看到freeze後的資料
中間是藉由禁reorder(freeze不能在設值前發生，access不能再freeze前發生)
但有趣的是，如果把this傳出去就不一定了
Obj1 obj = new Obj1();
final_field = 42;
ptr1 = this;
//freeze final_field
ptr2 = this;
如果有thread看到ptr1，就直接去用，這樣就無法保證一定看的到final_field，因為設定ptr的指令可能被reorder，最後ptr1拿到的就是建到一半的物件(連final都還沒跑完)
cpp memory model
基本就是基於java memory model，但多了可以控制atomic的memory barrier可以寬到哪邊去
介紹memory barrier
就是控制reorder不要讓指令跑過barrier
而指令可以分成Load或Store，所以有四種case
- LoadStore
- LoadLoad
- LoadLoad + LoadStore組成Acquire semantics
- java的volatile的寫與cpp的memory_order_acquire
- StoreStore
- StoreStore + LoadStore組成Release semantics
- java的volatile的讀與cpp的memory_order_release
- StoreLoad
- 只有這個是強與弱memory model都可以reorder的，所以call這個一定會有事發生
barrier有cpu版與compiler版，效力自然是cpu比較大
memory_order
- memory_order_relaxed
- 就是沒有barrier，只剩下原子性
- memory_order_acquire
- 在這點之後的所有write與自己的read不會超過這裡
- 可以想成是第一個write，然後後面有很多其他write與自己的read
- 更形象一點可以想成上蓋
- 對應到java的volatile寫
- memory_order_consume
- 與memory_order_acquire很像
- 但是只限制與目前變數有關的write不超過這邊
- memory_order_release
- 在這點之後的所有write與自己的read不會超過這裡
- 可以想成是最後一個read，然後前面有很多其他write與自己的read
- 更形象一點可以想成下底
- 對應到java的volatile讀
- memory_order_acq_rel
- acquire + release
- 這感覺就很像楚河漢界，上半部與下半部不會混在一起
- memory_order_seq_cst
- 就是java的volatile，照順序來
臨時追加: ABA問題
主要是在lock-free才會提到，因為會看修改前與修改後沒有內容是不是沒被動過，但是如果只是看起來沒被動過?
ABA問題有三個條件
- 重複讀某變數，同時只用此變數做condtion
- 每次讀與寫都沒有同步
- 被多個thread修改，值有可能變回去以前的某一個值
如何處理
加入一個變數，只能單調遞增 在做cond時除了看原本的變數，這個單調遞增的變數也要看
轉帳問題
1. 小琳在 ATM 1 转账 100 块钱给小李；
2. 由于ATM 1 出现了网络拥塞的原因卡住了，这时候小琳跑到旁边的 ATM 2 再次操作转账；(有兩次轉帳)
3. ATM 2 没让小琳失望，执行了 CAS(100,0)，很痛快地完成了转账，此时小琳的账户余额为 0；(第一次轉帳)
4. 小王这时候又给小琳账上转了 100，此时小琳账上余额为 100；
5. 这时候 ATM 1 网络恢复，继续执行 CAS(100,0)，居然执行成功了，小琳账户上余额又变为了 0；(第二次轉帳)
6. 这时候小王微信跟小琳说转了 100 过去，是否收到呢？小琳去查了下账，摇了摇头，那么问题来了，钱去了哪呢？
Ref
The Java Memory Model(這個有因果關係檢查的範例) Java Memory Model Pragmatics(人性化很多，適合第一次看) JSR-133 Review(中文的，解釋得很好) 对优化说不 - Linux中的Barrier ABA problem