死鎖.jpeg

本人在并發(fā)方面屬于小白一枚，之前有嘗試看《Java并發(fā)編程實(shí)戰(zhàn)》、java concurrent包的源碼，一直感覺(jué)在看的過(guò)程中找不到融會(huì)貫通的那個(gè)點(diǎn)，拘泥于細(xì)節(jié)，浮于表面。所以就開(kāi)始嘗試著從源頭看起，想找到最本質(zhì)的東西。這篇文章是自己在看到了相關(guān)的書(shū)籍和文章之后，思考出來(lái)的一點(diǎn)東西，內(nèi)容并沒(méi)有什么深入的東西，但是本人通過(guò)對(duì)這些內(nèi)容的了解，感覺(jué)隱約看到了些不一樣的東西。

本文的整體思路：

• 為什么會(huì)出現(xiàn)并發(fā)
• 并發(fā)導(dǎo)致了哪些問(wèn)題
• 如何解決并發(fā)問(wèn)題

這里討論的背景是單機(jī)、單CPU，為了簡(jiǎn)化問(wèn)題本身。多CPU的計(jì)算機(jī)架構(gòu)和分布式系統(tǒng)的出現(xiàn)使得并發(fā)問(wèn)題變得更加棘手。

這里不會(huì)具體討論細(xì)節(jié)的東西，更想提現(xiàn)的是思路~

開(kāi)始的開(kāi)始

在搶占式調(diào)度操作系統(tǒng)出現(xiàn)之前，是不存在并發(fā)問(wèn)題的。計(jì)算機(jī)讀取一段計(jì)算機(jī)指令 -> cpu依次執(zhí)行指令 -> 完成，整個(gè)過(guò)程一氣呵成。不過(guò)這種方式存在兩個(gè)問(wèn)題：

• cpu不能被充分利用。在當(dāng)前執(zhí)行的程序做I/O操作的時(shí)候，cpu是空閑的，又因?yàn)椴荒鼙粨屨?，所以cpu就被閑置掉了。
• 不能讓計(jì)算機(jī)同時(shí)做多個(gè)事情。比如個(gè)人計(jì)算機(jī)的場(chǎng)景，想要同時(shí)聽(tīng)歌和瀏覽網(wǎng)頁(yè)。

于是出現(xiàn)了搶占式調(diào)度操作系統(tǒng)。

搶占的時(shí)機(jī)

根據(jù)上邊的兩個(gè)出現(xiàn)的問(wèn)題，就能判斷出來(lái)，應(yīng)該何時(shí)搶占：

• 在當(dāng)前程序做I/O操作的時(shí)候。發(fā)生I/O的時(shí)候，切換到另一個(gè)程序執(zhí)行，從而充分使用cpu。
• 在當(dāng)前程序執(zhí)行了一段時(shí)間的時(shí)候。在音樂(lè)軟件執(zhí)行了一段時(shí)間，這時(shí)候需要切換到瀏覽器軟件來(lái)執(zhí)行。當(dāng)兩個(gè)軟件在短時(shí)間內(nèi)快速切換并執(zhí)行時(shí)，就達(dá)到了兩個(gè)軟件在同時(shí)運(yùn)行的假象。

搶占.jpg

如上圖，當(dāng)搶占的時(shí)機(jī)出現(xiàn)的時(shí)候，執(zhí)行搶占這個(gè)動(dòng)作，從而完成程序的切換。

如何搶占

知道要什么時(shí)候搶占了，那下一個(gè)問(wèn)題來(lái)了，要怎么搶占？

要知道，在當(dāng)前程序執(zhí)行的時(shí)候，cpu運(yùn)行的僅僅是當(dāng)前程序的指令，也就是說(shuō)如果當(dāng)前程序不主動(dòng)讓出cpu的話，它就能夠一直運(yùn)行下去。為了能夠解決這個(gè)問(wèn)題，出現(xiàn)了一個(gè)新的概念：中斷（Interrupts）。

中斷會(huì)在以下場(chǎng)景被觸發(fā)：

• 執(zhí)行系統(tǒng)調(diào)用時(shí)。系統(tǒng)調(diào)用都是I/O相關(guān)，所以執(zhí)行系統(tǒng)調(diào)用就是在做I/O操作。
• 每隔固定時(shí)間。
• 異常。

一旦發(fā)生中斷，cpu的使用權(quán)就會(huì)從當(dāng)前執(zhí)行的程序手中回收，并交給操作系統(tǒng)。操作系統(tǒng)的調(diào)度系統(tǒng)會(huì)根據(jù)情況來(lái)決定接下來(lái)要運(yùn)行哪個(gè)程序。這樣就完成了一次搶占。

中斷是并發(fā)問(wèn)題的原罪

中斷的出現(xiàn)為操作系統(tǒng)對(duì)資源做掌控和充分利用提供了可能，但也同時(shí)帶來(lái)了新的問(wèn)題。

無(wú)論是進(jìn)程之間，還是線程之間，都可能存在共享的資源。共享資源不可怕，同時(shí)對(duì)共享做操作也不可怕，可怕的是在不恰當(dāng)?shù)臅r(shí)機(jī)發(fā)生了中斷。

比如看這個(gè)場(chǎng)景：

count = count + 1

這是一個(gè)累加操作，在高級(jí)語(yǔ)言中，這就是一行代碼，但是當(dāng)把它轉(zhuǎn)換成機(jī)器碼時(shí)，就變成了三條命令：

1. mov ax, 0x1111 # 把內(nèi)存地址0x1111中的數(shù)據(jù)讀取到ax寄存器
2. add ax, 1      # 對(duì)ax寄存器做加1操作
3. mov 0x1111, ax # 把a(bǔ)x寄存器中的數(shù)據(jù)存入內(nèi)存地址0x1111中

如果兩個(gè)線程同時(shí)在做這個(gè)操作，并且中斷發(fā)生在不恰當(dāng)?shù)臅r(shí)候，看看會(huì)導(dǎo)致什么問(wèn)題：

中斷問(wèn)題.png

當(dāng)線程1執(zhí)行完第二條指令時(shí)，此時(shí)ax寄存器的值為1。此時(shí)操作系統(tǒng)進(jìn)行了調(diào)度，進(jìn)行上下文切換，保存寄存器ax的值為1，切換至線程2。線程2完成了以上三條指令，內(nèi)存地址0x1111此時(shí)存儲(chǔ)的值為1。這時(shí)切換回線程1，恢復(fù)寄存器ax的值為1，執(zhí)行第三條指令，此時(shí)內(nèi)存地址0x1111的值為1。所以，當(dāng)兩個(gè)線程分別完成兩次加一操作后，結(jié)果為1。

并發(fā)問(wèn)題出現(xiàn)了。

如何解決并發(fā)問(wèn)題

上邊的這個(gè)場(chǎng)景就是很典型的并發(fā)問(wèn)題的場(chǎng)景，可以看出來(lái)導(dǎo)致并發(fā)問(wèn)題的原因有兩個(gè)：

• 對(duì)資源的操作不是原子的。
• 在操作過(guò)程中發(fā)生了中斷。

中斷是搶占式調(diào)度不可避免的，雖然能夠屏蔽中斷，但是這就又出現(xiàn)了剛才提到了非搶占調(diào)度的問(wèn)題。那么就看看能不能把操作變成原子操作。這時(shí)出現(xiàn)了鎖的概念。

鎖是什么

鎖出現(xiàn)的目的是希望提供一種方式，能夠把一串命令變成原子的操作，比如：

lock()
count = count + 1
unlock()

lock和unlock代表這個(gè)原子操作的開(kāi)始和結(jié)束，這兩者之間就是所謂的臨界區(qū)。希望鎖能夠達(dá)到的效果是，在同一時(shí)刻，有且僅有一個(gè)線程在臨界區(qū)中。這樣即使線程1在累加的過(guò)程中發(fā)生了中斷并切換到線程2運(yùn)行，線程2也無(wú)法做累加操作。

如何實(shí)現(xiàn)鎖

鎖的在概念上能夠解決共享資源上的并發(fā)問(wèn)題了，但是仔細(xì)想一下，其實(shí)鎖本身也是一種資源，是需要競(jìng)爭(zhēng)的，這就又出現(xiàn)了共享資源的并發(fā)問(wèn)題，比如：

int flag = 0;

int lock() {
    while(flag == 1) {
        //空循環(huán)
    }
    flag = 1; //如果行執(zhí)行前發(fā)生中斷，就會(huì)出現(xiàn)問(wèn)題
}

int unlock() {
    flag = 0;
}

lock()
count = count + 1
unlock()

這種情況，僅僅通過(guò)軟件層面是無(wú)法解決的了，需要硬件的支持。

原子指令

為了能夠?qū)崿F(xiàn)鎖，cpu提供了一部分原子指令來(lái)做支持。

Test-And-Set

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr;
    *old_ptr = new;
    return old;
}

Compare-And-Swap

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}

Load-Linked And Store-Conditional (LL/SC)

int LoadLinked(int *ptr) {
    return *ptr;
}

int StoreConditional(int *ptr, int value) {
    if (no on has updated *ptr since the LoadLinked to this address) {
        *ptr = value;
        return 1; // success!
    } else {
        return 0; // failed to update
    }
}

Fetch-And-Add

int FetchAndAdd (int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

用原子指令實(shí)現(xiàn)鎖

有了這些原子指令，鎖就能夠?qū)崿F(xiàn)了。java這邊主要用的是CAS，所以用CAS來(lái)看下：

int guard = 0;

int lock() {
    while(CompareAndSwap(guard, 0, 1) == 1) {
        //spin
    }
}

int unlock() {
    guard = 0;
}

lock()
count = count + 1
unlock()

CAS指令保證了 （讀取flag，判斷是0） --> （設(shè)置flag = 1） 這兩個(gè)動(dòng)作是原子操作，不會(huì)被中斷，因此避免了并發(fā)問(wèn)題。這樣在硬件的支持下完成了鎖的實(shí)現(xiàn)，并發(fā)問(wèn)題有了解決方案。

自旋鎖的問(wèn)題

上邊的實(shí)現(xiàn)在競(jìng)爭(zhēng)鎖失敗的時(shí)候，當(dāng)前線程會(huì)一直空循環(huán)，競(jìng)爭(zhēng)成功后才繼續(xù)進(jìn)行下去，這就是自旋鎖(spin lock)。

自旋鎖很好地解決了互斥的問(wèn)題，但它也存在一些問(wèn)題：

1. 公平問(wèn)題。不能保證對(duì)線程公平，可能會(huì)出現(xiàn)線程饑餓。
2. 性能問(wèn)題。在單CPU中，自旋鎖的性能很差，每個(gè)thread在等待鎖的時(shí)候，都會(huì)消耗一個(gè)完整的時(shí)間片，這個(gè)消耗隨thread數(shù)量的增加而增加；在多CPU種，性能有所改善，當(dāng)某個(gè)CPU上的線程釋放了鎖時(shí)，其他CPU上的線程就能立即獲得鎖，停止輪詢(xún)。

yield一下就好

自旋鎖的自旋過(guò)程會(huì)浪費(fèi)cpu資源，從而導(dǎo)致性能下降。為了解決這個(gè)問(wèn)題提出了一個(gè)新的概念：yield。
當(dāng)競(jìng)爭(zhēng)鎖失敗時(shí)，通過(guò)yield指令來(lái)讓出cpu資源：

while(CompareAndSwap(guard, 0, 1) == 1) {
    yield();
}

這樣就解決了自旋鎖的性能問(wèn)題，但仍然存在問(wèn)題：

1. 公平問(wèn)題。自旋鎖的公平問(wèn)題這里仍然存在。
2. 性能問(wèn)題。如果一個(gè)thread獲得了鎖并且在釋放之前被搶占，這時(shí)被調(diào)度的其他thread會(huì)分別yield，有可能同一個(gè)thread被調(diào)度兩次，也就是說(shuō)yield兩次，這種情況要一直持續(xù)到，調(diào)度到競(jìng)爭(zhēng)到鎖的那個(gè)thread成功釋放鎖時(shí)才會(huì)終止。這期間可能產(chǎn)生大量的yield和調(diào)度操作。

用sleep和隊(duì)列代替自旋

為了解決自旋的公平問(wèn)題和性能問(wèn)題，操作系統(tǒng)提供了兩個(gè)新的系統(tǒng)調(diào)用park和unpark（Solaris系統(tǒng)中，其他系統(tǒng)的名稱(chēng)會(huì)有所不同）。park會(huì)使當(dāng)前線程掛起，unpark會(huì)使指定線程喚醒。

這兩個(gè)系統(tǒng)調(diào)用，在結(jié)合上隊(duì)列，看看如何實(shí)現(xiàn)一個(gè)鎖。

Lock {
 int guard = 0;
 int flag = 0;
 Queue<Integer> q = new Queue<Integer>();
}

Lock lock;

lock() {
    while(CompareAndSwap(lock.guard, 0, 1) == 1) {
        if (lock.flag = 0) {
            lock.flag = 1;
            lock.guard = 0;
        } else {
            lock.q.add(currentThreadId());
            lock.guard = 0;
            park();
        }
    }
}

unlock() {
    while(CompareAndSwap(lock.guard, 0, 1) == 1) {
        if(lock.q.isEmpty()) {
            lock.flag = 0;
        } else {
            unpark(lock.q.take());
        }
        lock.guard = 0;
    }
}

這個(gè)實(shí)現(xiàn)通過(guò)隊(duì)列記錄了競(jìng)爭(zhēng)過(guò)鎖的線程，用隊(duì)列的先后順序解決了鎖的公平問(wèn)題；通過(guò)park和unpark避免了自旋，解決了鎖的性能問(wèn)題。

更高級(jí)的同步原語(yǔ)

鎖的問(wèn)題算是全部解決了，不過(guò)在這個(gè)討論的過(guò)程中會(huì)有一種感覺(jué)，就是細(xì)節(jié)的東西太瑣碎了，在編程過(guò)程中要非常仔細(xì)地控制鎖。為了提效，計(jì)算機(jī)界的大佬們對(duì)常見(jiàn)的并發(fā)場(chǎng)景做了一層抽象，提出了一些比鎖更高層次的同步原語(yǔ)，從而屏蔽了鎖的細(xì)節(jié)。

互斥量（mutex）

mutex是最簡(jiǎn)單的同步原語(yǔ)了，它僅允許同一時(shí)刻只有一個(gè)線程進(jìn)入臨界區(qū)。

Mutex mutex;

void run() {
    mutex.lock();
    //do something
    mutex.unlock();
}

條件變量（condition variables）

為了能夠很好的解決生產(chǎn)者/消費(fèi)者這種的并發(fā)模型，提出了條件變量這個(gè)同步原語(yǔ)。

條件變量能夠讓一系列線程等待在某個(gè)條件上，當(dāng)這個(gè)條件滿(mǎn)足時(shí)，等待在該條件上的線程會(huì)被喚醒。條件變量需要和mutex配套使用。

Mutex mutex;
Condition notEmpty;
Condition notFull;

Queue queue;

void cunsum() {
    mutex.lock();
    while(queue.isEmpty()) {
        notEmpty.await(mutex);
    }
    data = queue.take();
    notFull.singal();
    mutex.unlock();
}

void product() {
    mutex.lock();
    while(queue.isFull()) {
        notFull.await(mutex);
    }
    queue.add(data);
    notEmpty.signal();
    mutex.unlock();
}

在await之前，必須保證已經(jīng)競(jìng)爭(zhēng)到mutex。await時(shí)，會(huì)將當(dāng)前線程加入到condition的等待隊(duì)列中，然后釋放mutex，線程等待。當(dāng)這個(gè)condition被signal時(shí)，之前等待的線程重新獲得mutex，并被喚醒，從之前await的位置繼續(xù)執(zhí)行。

信號(hào)量（Semaphore）

有了互斥量和條件變量這兩個(gè)同步原語(yǔ)之后，計(jì)算機(jī)屆的大佬又感覺(jué)有點(diǎn)兒麻煩，我們?cè)诮鉀Q并發(fā)問(wèn)題時(shí)，有時(shí)要用互斥量，有時(shí)又要用條件變量，如果能把這兩個(gè)合起來(lái)是不是方便些？于是就提出了信號(hào)量。

信號(hào)量是一個(gè)包含了數(shù)值的對(duì)象，wait()會(huì)對(duì)數(shù)值減1，當(dāng)數(shù)值小于零時(shí)，線程等待，直到數(shù)值大于等于零時(shí)被喚醒；post()會(huì)對(duì)數(shù)值加1，如果有等待的線程，喚醒它們。

把信號(hào)量當(dāng)互斥量使用

Semaphore semaphore;
semphore.init(1);

void run() {
    semaphore.wait();
    //do something
    semaphore.post();
}

信號(hào)量實(shí)現(xiàn)生產(chǎn)者/消費(fèi)者模型

int MAX = 10;

Semaphore full;
full.init(0);

Semaphore empty;
full.init(MAX);

Semaphore mutex;
lock.init(1);

Queue queue;

void cunsum() {
    full.wait();
    mutex.lock();
    data = queue.take();
    mutex.unlock();
    empty.post();
}

void product() {
    empty.wait();
    mutex.lock();
    queue.add(data);
    mutex.unlock();
    full.post();
}

管程（Monitor）

有了上面的這些原語(yǔ)之后，大佬們還是覺(jué)得用起來(lái)不夠簡(jiǎn)單，還是要關(guān)心一些并發(fā)問(wèn)題的細(xì)節(jié)，它們希望把這些再封裝一下，讓使用者完全不關(guān)心這些細(xì)節(jié)，讓他們能夠像寫(xiě)單線程的程序一樣來(lái)寫(xiě)并發(fā)程序，于是提出了管程這個(gè)概念。

“管程”這個(gè)翻譯很棒，顧名思義，管程就是一個(gè)管道，在同一時(shí)刻，只有一個(gè)線程能夠訪問(wèn)管道內(nèi)的程序。

不像上邊的幾個(gè)同步原語(yǔ)在操作系統(tǒng)層面就有實(shí)現(xiàn)了，管程是在編程語(yǔ)言層面才提供的同步原語(yǔ)，對(duì)于不同的語(yǔ)言，都會(huì)針對(duì)自己所關(guān)心的場(chǎng)景有著自己不同的實(shí)現(xiàn)。

java里面的管程

Object lock = new Object();

synchronized(lock) {
    //do something;
}

sychronized代碼塊在編譯之后，會(huì)在開(kāi)始和結(jié)束的位置加上monitorenter和monitorexit指令，代表管程的進(jìn)入和退出。至于管程具體的實(shí)現(xiàn)，就要看java語(yǔ)言本身的實(shí)現(xiàn)了。對(duì)于不同的java版本，管程的實(shí)現(xiàn)都會(huì)有所不同。

總結(jié)

上邊討論的這些內(nèi)容總結(jié)一下，就是下圖了。

工具概覽.png

由于中斷、進(jìn)程調(diào)度等原因，導(dǎo)致了并發(fā)問(wèn)題的出現(xiàn)。為了解決這個(gè)問(wèn)題，提出了鎖的概念，并在硬件層面上通過(guò)一些原子指令來(lái)支持鎖的實(shí)現(xiàn)。為了隱藏掉鎖的實(shí)現(xiàn)細(xì)節(jié)，并希望能夠更高效的解決并發(fā)問(wèn)題，于是提出了互斥量、信號(hào)量、管程等同步原語(yǔ)。再往上一層，無(wú)論是操作系統(tǒng)，還是各種應(yīng)用程序，在解決并發(fā)問(wèn)題的時(shí)候基本都是使用前邊說(shuō)這些概念和思路。

以上，歡迎討論和指正~

tip

這篇文章的內(nèi)容大部分來(lái)自于一本叫做《Operate System: Three Easy Pieces》的操作系統(tǒng)教材。這本教材是開(kāi)源的，屬于操作系統(tǒng)的入門(mén)教材，教材編寫(xiě)的很有趣，有興趣的人可以去看一看。本文內(nèi)容主要來(lái)自對(duì)Concurrency那個(gè)部分的思考。