並行程式的噩夢——資料競爭
並行程式的噩夢——資料競爭
前言
在本文當中我主要通過不同執行緒對同一個資料進行加法操作的例子，層層遞進，使用忙等待、synchronized和鎖去解決我們的問題，切實體會為什麼資料競爭是並行程式的噩夢。
問題介紹
在本文當中會有一個貫穿全文的例子：不同的執行緒會對一個全域性變數不斷的進行加的操作！然後比較結果，具體來說我們設定一個靜態類變數
data，然後使用兩個執行緒迴圈10萬次對data進行加一操作！！！
像這種多個執行緒會存在同時對同一個資料進行修改操作的現象就叫做資料競爭。資料競爭會給程式造成很多不可預料的結果，讓程式存在許多漏洞。而我們上面的任務就是一個典型的資料競爭的問題。
並行不安全版本
在這一小節我們先寫一個上述問題的並行不安全的版本：
public class Sum {
public static int data;
public static void main(String[] args) throws InterruptedException {
Thread t1 = new Thread(() -> {
for (int i = 0; i < 100000; i++)
data++;
});
Thread t2 = new Thread(() -> {
for (int i = 0; i < 100000; i++)
data++;
});
t1.start();
t2.start();
// 讓主執行緒等待 t1 和 t2
// 直到 t1 和 t2 執行完成
t1.join();
t2.join();
System.out.println(data);
}
}
// 輸出結果
131888
上面兩個執行緒執行的結果最終都會小於200000，為什麼會出現這種情況呢？
我們首先來看一下記憶體的邏輯佈局圖：
data全域性變數儲存在主記憶體當中，當現成開始執行的時候會從主記憶體拷貝一份到執行緒的工作記憶體當中，也就是執行緒的本地記憶體，在本地進行計算之後就會將本地記憶體當中的資料同步到主記憶體
我們現在來模擬一下出現問題的過程：
- 主記憶體
data的初始值等於0，兩個執行緒得到的data初始值都等於0。
- 現線上程一將
data加一，然後執行緒一將data的值同步回主記憶體，整個記憶體的資料變化如下：
- 現線上程二
data加一，然後將data的值同步回主記憶體（將原來主記憶體的值覆蓋掉了）：
我們本來希望data的值在經過上面的變化之後變成2，但是執行緒二覆蓋了我們的值，因此在多執行緒情況下，會使得我們最終的結果變小。
忙等待（Busy waiting）
那麼我們能在不使用鎖或者synchronized的情況實現上面這個任務嗎？答案是可以，這種方法叫做忙等待。具體怎麼做呢，我們可以用一個布林值flag去標識是那個執行緒執行sum++，我們先看程式碼然後進行分析：
public class BusyWaiting {
public static int sum;
public static boolean flag;
public static void main(String[] args) throws InterruptedException {
Thread t1 = new Thread(() -> {
for (int i = 0; i < 100000; i++) {
// 當 flag == false 的時候這個執行緒進行
// sum++ 操作然後讓 flat = true
// 讓另外一個執行緒進行 sum++ 操作
while (flag);
sum++;
flag = true;
System.out.println("Thread 1 : " + sum);
}
});
Thread t2 = new Thread(() -> {
for (int i = 0; i < 100000; i++) {
// 當 flag = true 的之後這個執行緒進行
// sum++ 操作然後讓 flat = false
// 讓另外一個執行緒進行 sum++ 操作
while (!flag) ;
sum++;
flag = false;
System.out.println("Thread 2 : " + sum);
}
});
t1.start();
t2.start();
// 讓主執行緒等待 t1 和 t2
// 直到 t1 和 t2 執行完成
t1.join();
t2.join();
System.out.println(sum);
}
}
上面程式碼的流程是一個執行緒進行完sum++操作之後會將自己的flag變成另外一個值，然後自己的while迴圈當中的條件會一直為true自己就會一直處於while迴圈當中，然後另外一個執行緒的while迴圈條件會變成false，則另外一個執行緒會執行sum++操作，然後將flag變成另外一個值，然後執行緒又開始執行了......
忙等待中資料競爭的BUG
但是上面的程式碼會出現問題，就是在執行一段時間之後兩個執行緒都會卡死，都會一直處於死迴圈當中。這是因為一個執行緒在更新完flag之後，另外一個執行緒的flag值沒有更新，也就是說兩個執行緒的flag值不一樣，這樣就都會處於死迴圈當中。出現這個問題的原因是一個執行緒更新完flag之後，另外一個執行緒的flag使用的還是舊值。
比如在某個時刻主記憶體當中的flag的值等於false，執行緒t1和執行緒t2當中的flag的值都等於false，這個情況下執行緒t1是可以進行sum++操作的，然後執行緒t1進行sum++操作之後將flag的值改成true，然後將這個值同步更新回主記憶體，但是此時執行緒t2拿到的還是舊值false，他依舊處於死迴圈當中，就這樣兩個執行緒都處於死迴圈了。
上面的問題本質上是一個資料可見性的問題，也就是說一個執行緒修改了flag的值，另外一個執行緒拿不到最新的值，使用的還是舊的值，而在java當中給我們提供了一種機制可以解決資料可見性的問題。在java當中我們可以使用volatile去解決資料可見性的問題。當一個變數被volatile關鍵字修飾時，對於共用資源的寫操作先要修改工作記憶體，但是修改結束後會立刻將其重新整理到主記憶體中。當其他執行緒對該volatile修飾的共用資源進行了修改，則會導致當前執行緒在工作記憶體中的共用資源失效，所以必須從主記憶體中再次獲取。這樣的話就可以保證共用資料的可見性了。因為某個執行緒如果修改了volatile修飾的共用變數時，其他執行緒的值會失效，然後重新從主記憶體當中載入最新的值，關於volatile的內容還是比較多，在本文當中我們只談他在本文當中作用。
修改後的正確程式碼如下：
public class BusyWaiting {
public static volatile int sum;
public static volatile boolean flag;
public static void main(String[] args) throws InterruptedException {
Thread t1 = new Thread(() -> {
for (int i = 0; i < 100000; i++) {
// 當 flag == false 的時候這個執行緒進行
// sum++ 操作然後讓 flat = true
// 讓另外一個執行緒進行 sum++ 操作
while (flag);
sum++;
flag = true;
System.out.println("Thread 1 : " + sum);
}
});
Thread t2 = new Thread(() -> {
for (int i = 0; i < 100000; i++) {
// 當 flag = true 的之後這個執行緒進行
// sum++ 操作然後讓 flat = false
// 讓另外一個執行緒進行 sum++ 操作
while (!flag) ;
sum++;
flag = false;
System.out.println("Thread 2 : " + sum);
}
});
t1.start();
t2.start();
// 讓主執行緒等待 t1 和 t2
// 直到 t1 和 t2 執行完成
t1.join();
t2.join();
System.out.println(sum);
}
}
上面的sum也需要使用volatile進行修飾，因為如果某個執行緒++之後，如果另外一個執行緒沒有更新最新的值就進行++的話，在資料更新回主記憶體的時候就會覆蓋原來的值，最終的結果就會變小，因此需要使用volatile進行修飾。
在上文當中我們主要分析瞭如何使用忙等待來解決我們的問題，但是忙等待有一個很大的問題就是執行緒會不斷的進行迴圈，這很消耗CPU資源，在下文當中我們將主要介紹兩種方法解決本文開頭提出的問題，而且可以不進行迴圈操作，而是將執行緒掛起，而不是一直在執行。
synchronized並行安全版本
synchronized是java語言的關鍵字，它可以用來保證程式的原子性。在並行的情況下我們可以用它來保證我們的程式在某個時刻只能有一個執行緒執行，保證同一時刻只有一個執行緒獲得synchronized鎖物件。
public class Sum01 {
public static int sum;
public static synchronized void addSum() {
for (int i = 0; i < 100000; i++)
sum++;
}
public static void main(String[] args) throws InterruptedException {
Thread t1 = new Thread(Sum01::addSum);
Thread t2 = new Thread(Sum01::addSum);
t1.start();
t2.start();
// 讓主執行緒等待 t1 和 t2
// 直到 t1 和 t2 執行完成
t1.join();
t2.join();
System.out.println(sum);
}
}
// 輸出結果
200000
上面的程式碼addSum方法加入了synchronized進行修飾，在java當中被synchronized的靜態方法在同一個時刻只能有一個執行緒能夠進入，也就是說上面的程式碼會讓執行緒t1或者t2先執行addSum函數，然後另外一個執行緒在進行執行，那這個跟序列執行就一樣了。那麼我們就可以不在靜態方法上加synchronized的關鍵字，可以使用靜態程式碼塊：
public class Sum02 {
public static int sum;
public static Object lock = new Object();
public static void addSum() {
for (int i = 0; i < 100000; i++)
synchronized (lock) {
sum++;
}
}
public static void main(String[] args) throws InterruptedException {
Thread t1 = new Thread(Sum02::addSum);
Thread t2 = new Thread(Sum02::addSum);
t1.start();
t2.start();
// 讓主執行緒等待 t1 和 t2
// 直到 t1 和 t2 執行完成
t1.join();
t2.join();
System.out.println(sum);
}
}
上面程式碼雖然沒有使用用synchronized修飾的靜態方法，但是上面的程式碼使用了用synchronized修飾的同步程式碼塊，在每一個時刻只能有一個執行緒執行下面這段程式碼：
// synchronized 修飾的程式碼塊稱作同步程式碼塊 ，
// lock 是一個 全域性的靜態類變數 只有競爭到 lock 物件的執行緒
// 才能夠進入同步程式碼塊 同樣的每一個時刻只能有一個執行緒進入
synchronized (lock) {
sum++;
}
上面程式碼雖然沒有使用靜態同步方法（synchronized修飾的靜態方法），但是有同步程式碼塊（synchronized修飾的程式碼塊），在一個程式碼當中會有100000次進入同步程式碼塊，這裡也花費很多時間，因此上面的程式碼的效率也不高。
其實我們可以用一個臨時變數儲存100000次加法的結果，最後一次將結果加入到data當中：
public class Sum03 {
public static int sum;
public static Object lock = new Object();
public static void addSum() {
int tempSum = 0;
for (int i = 0; i < 100000; i++)
tempSum++;
synchronized (lock) {
sum += tempSum;
}
}
public static void main(String[] args) throws InterruptedException {
Thread t1 = new Thread(Sum03::addSum);
Thread t2 = new Thread(Sum03::addSum);
t1.start();
t2.start();
// 讓主執行緒等待 t1 和 t2
// 直到 t1 和 t2 執行完成
t1.join();
t2.join();
System.out.println(sum);
}
}
使用鎖進行臨界區的保護
臨界區：像這種與資料競爭有關的程式碼塊叫做臨界區，比如上文程式碼當中的
sum++。
在java當中除了使用synchronized形成同步方法或者同步程式碼塊的方法保證多個執行緒存取臨界區的順序，還可以使用鎖對臨界區進行保護。在java當中一個非常常用的鎖就是可重入鎖ReentrantLock，可以保證在lock和unlock之間的區域在每一個時刻只有一個執行緒在執行。
import java.util.concurrent.locks.ReentrantLock;
public class Sum04 {
public static int sum;
public static ReentrantLock lock = new ReentrantLock();
public static void addSum() {
int tempSum = 0;
for (int i = 0; i < 100000; i++)
tempSum++;
lock.lock();
try {
sum += tempSum;
}catch (Exception ignored) {
}finally {
lock.unlock();
}
}
public static void main(String[] args) throws InterruptedException {
Thread t1 = new Thread(Sum04::addSum);
Thread t2 = new Thread(Sum04::addSum);
t1.start();
t2.start();
// 讓主執行緒等待 t1 和 t2
// 直到 t1 和 t2 執行完成
t1.join();
t2.join();
System.out.println(sum);
}
}
synchronized和鎖對可見性的影響
在上文當中我們僅僅提到了
synchronized和鎖可以保證在每一個時刻只能有一個執行緒在臨界區當中執行，這一點其實前面的忙等待也可以實現，但是後面我們提到了第一版忙等待的實現是有錯誤的，在程式執行的時候程式會陷入死迴圈。因此synchronized和鎖也會有這樣的問題，但是為什麼synchronized和鎖可以使得程式能夠正常執行呢？原因如下：
synchronized關鍵字能夠保證可見性，synchronized關鍵字能夠不僅能夠保證同一時刻只有一個執行緒獲得鎖，並且還會確保在鎖釋放之前，會將對變數的修改重新整理到主記憶體當中。JDK給我們提供的鎖工具（比如ReentrantLock）也能夠保證可見性，鎖的lock方法能夠保證在同一時刻只有一個執行緒獲得鎖然後執行同步方法，並且會確保在鎖釋放(鎖的unlock方法)之前會將對變數的修改重新整理到主記憶體當中。
資料競爭的知名後果——死鎖
死鎖是由於多個執行緒相互之間競爭資源而形成的一種相互僵持的局面。
在前面的忙等待當中的那個錯誤如果不仔細思考是很容易忽略的，由此可見資料競爭給並行程式設計帶來的難度。下面一個典型的存在死鎖可能的程式碼：
public class DeadLock {
public static Object fork = new Object();
public static Object chopsticks = new Object();
public static void fork() {
System.out.println(Thread.currentThread().getName() + "想獲得叉子");
synchronized (fork) {
System.out.println(Thread.currentThread().getName() + "已經獲得叉子");
System.out.println(Thread.currentThread().getName() + "想獲得筷子");
synchronized (chopsticks) {
System.out.println(Thread.currentThread().getName() + "已經獲得筷子");
}
}
}
public static void chopsticks() {
System.out.println(Thread.currentThread().getName() + "想獲得筷子");
synchronized (chopsticks) {
System.out.println(Thread.currentThread().getName() + "已經獲得筷子");
System.out.println(Thread.currentThread().getName() + "想獲得叉子");
synchronized (fork) {
System.out.println(Thread.currentThread().getName() + "已經獲得叉子");
}
}
}
public static void main(String[] args) throws InterruptedException {
Thread t1 = new Thread(DeadLock::fork);
Thread t2 = new Thread(DeadLock::chopsticks);
t1.start();
t2.start();
t1.join();
t2.join();
}
}
// 輸出結果
Thread-0想獲得叉子
Thread-1想獲得筷子
Thread-0已經獲得叉子
Thread-0想獲得筷子
Thread-1已經獲得筷子
Thread-1想獲得叉子
// 在這裡已經卡死
- 執行緒1想先獲得叉子，再獲得筷子。
- 執行緒2想先獲得筷子，再獲得叉子。
假如有一個狀態執行緒1已經獲得叉子，執行緒2已經獲得筷子，現線上程1想獲得執行緒2手中的筷子，執行緒2想獲得執行緒1的叉子，由此產生一個窘境，兩個執行緒都想從對方獲得東西，也就是說兩個執行緒都無法得到資源，兩個執行緒都卡死了，因而產生了死鎖。根據上面的分析我們可以發現死鎖產生最根本的原因還是資料競爭。
死鎖產生的條件
- 互斥條件：一個資源只能被一個執行緒佔有，如果其他執行緒想得到這個資源必須由其他執行緒釋放。
- 不剝奪條件：一個執行緒獲得的資源在沒有使用完之前不能被其他執行緒強行獲得，只能由執行緒主動釋放。
- 請求保持條件：至少保持了一個資源而且提出新的資源請求，比如上面執行緒1獲得了叉子又請求筷子。
- 迴圈等待條件：執行緒1請求執行緒2的資源，執行緒2請求執行緒3的資源，....，執行緒\(N\)請求執行緒1的資源。
如果想破壞死鎖，那就去破壞上面四個產生死鎖的條件即可。
總結
在本篇文章當中主要通過一道並行的題，通過各種方法去解決，在本文當中最重要的例子就是忙等待了，在忙等待的例子當中我們分析我們程式的問題，體會了資料競爭問題的複雜性，他會給我們的並行程式造成很多的問題，比如後面提到的死鎖的問題。除此之外我們還介紹了關於volatile和synchronized還有鎖對資料可見性的影響。
以上就是本文所有的內容了，希望大家有所收穫，我是LeHung，我們下期再見！！！（記得點贊收藏哦！）
更多精彩內容合集可存取專案：https://github.com/Chang-LeHung/CSCore
關注公眾號：一無是處的研究僧，瞭解更多計算機（Java、Python、計算機系統基礎、演演算法與資料結構）知識。