從零開始自己動手寫自旋鎖

從零開始自己動手寫自旋鎖

前言

我們在寫並發程式的時候，一個非常常見的需求就是保證在某一個時刻只有一個執行緒執行某段程式碼，像這種程式碼叫做臨界區，而通常保證一個時刻只有一個執行緒執行臨界區的程式碼的方法就是鎖🔒。在本篇文章當中我們將會仔細分析和學習自旋鎖，所謂自旋鎖就是通過while循環實現的，讓拿到鎖的執行緒進入臨界區執行程式碼，讓沒有拿到鎖的執行緒一直進行while死循環，這其實就是執行緒自己「旋」在while循環了，因而這種鎖就叫做自旋鎖。

自旋鎖

原子性

在談自旋鎖之前就不得不談原子性了。所謂原子性簡單說來就是一個一個操作要麼不做要麼全做，全做的意思就是在操作的過程當中不能夠被中斷，比如說對變數data進行加一操作，有以下三個步驟：

  • 將data從記憶體載入到暫存器。
  • 將data這個值加一。
  • 將得到的結果寫回記憶體。

原子性就表示一個執行緒在進行加一操作的時候，不能夠被其他執行緒中斷，只有這個執行緒執行完這三個過程的時候其他執行緒才能夠操作數據data。

我們現在用程式碼體驗一下，在Java當中我們可以使用AtomicInteger進行對整型數據的原子操作：

import java.util.concurrent.atomic.AtomicInteger;

public class AtomicDemo {

  public static void main(String[] args) throws InterruptedException {
    AtomicInteger data = new AtomicInteger();
    data.set(0); // 將數據初始化位0
    Thread t1 = new Thread(() -> {
      for (int i = 0; i < 100000; i++) {
        data.addAndGet(1); // 對數據 data 進行原子加1操作
      }
    });
    Thread t2 = new Thread(() -> {
      for (int i = 0; i < 100000; i++) {
        data.addAndGet(1);// 對數據 data 進行原子加1操作
      }
    });
    // 啟動兩個執行緒
    t1.start();
    t2.start();
    // 等待兩個執行緒執行完成
    t1.join();
    t2.join();
    // 列印最終的結果
    System.out.println(data); // 200000
  }
}

從上面的程式碼分析可以知道，如果是一般的整型變數如果兩個執行緒同時進行操作的時候，最終的結果是會小於200000。

我們現在來模擬一下一般的整型變數出現問題的過程：

  • 主記憶體data的初始值等於0，兩個執行緒得到的data初始值都等於0。

  • 現在執行緒一將data加一，然後執行緒一將data的值同步回主記憶體，整個記憶體的數據變化如下：

  • 現在執行緒二data加一，然後將data的值同步回主記憶體（將原來主記憶體的值覆蓋掉了）：

我們本來希望data的值在經過上面的變化之後變成2，但是執行緒二覆蓋了我們的值，因此在多執行緒情況下，會使得我們最終的結果變小。

但是在上面的程式當中我們最終的輸出結果是等於20000的，這是因為給data進行+1的操作是原子的不可分的，在操作的過程當中其他執行緒是不能對data進行操作的。這就是原子性帶來的優勢。

自己動手寫自旋鎖

AtomicInteger類

現在我們已經了解了原子性的作用了，我們現在來了解AtomicInteger類的另外一個原子性的操作——compareAndSet，這個操作叫做比較並交換（CAS），他具有原子性。

public static void main(String[] args) {
  AtomicInteger atomicInteger = new AtomicInteger();
  atomicInteger.set(0);
  atomicInteger.compareAndSet(0, 1);
}

compareAndSet函數的意義：首先會比較第一個參數（對應上面的程式碼就是0）和atomicInteger的值，如果相等則進行交換，也就是將atomicInteger的值設置為第二個參數（對應上面的程式碼就是1），如果這些操作成功，那麼compareAndSet函數就返回true，如果操作失敗則返回false，操作失敗可能是因為第一個參數的值（期望值）和atomicInteger不相等，如果相等也可能因為在更改atomicInteger的值的時候失敗（因為可能有多個執行緒在操作，因為原子性的存在，只能有一個執行緒操作成功）。

自旋鎖實現原理

我們可以使用AtomicInteger類實現自旋鎖，我們可以用0這個值表示未上鎖，1這個值表示已經上鎖了。

  • AtomicInteger類的初始值為0。
  • 在上鎖時，我們可以使用程式碼atomicInteger.compareAndSet(0, 1)進行實現，我們在前面已經提到了只能夠有一個執行緒完成這個操作，也就是說只能有一個執行緒調用這行程式碼然後返回true其餘執行緒都返回false，這些返回false的執行緒不能夠進入臨界區，因此我們需要這些執行緒停在atomicInteger.compareAndSet(0, 1)這行程式碼不能夠往下執行，我們可以使用while循環讓這些執行緒一直停在這裡while (!value.compareAndSet(0, 1));，只有返回true的執行緒才能夠跳出循環，其餘執行緒都會一直在這裡循環，我們稱這種行為叫做自旋，這種鎖因而也被叫做自旋鎖。
  • 執行緒在出臨界區的時候需要重新將鎖的狀態調整為未上鎖的上狀態，我們使用程式碼value.compareAndSet(1, 0);就可以實現，將鎖的狀態還原為未上鎖的狀態，這樣其他的自旋的執行緒就可以拿到鎖，然後進入臨界區了。

自旋鎖程式碼實現

import java.util.concurrent.atomic.AtomicInteger;

public class SpinLock {
	
  // 0 表示未上鎖狀態
  // 1 表示上鎖狀態
  protected AtomicInteger value;

  public SpinLock() {
    this.value = new AtomicInteger();
    // 設置 value 的初始值為0 表示未上鎖的狀態
    this.value.set(0);
  }

  public void lock() {
    // 進行自旋操作
    while (!value.compareAndSet(0, 1));
  }

  public void unlock() {
    // 將鎖的狀態設置為未上鎖狀態
    value.compareAndSet(1, 0);
  }

}

上面就是我們自己實現的自旋鎖的程式碼，這看起來實在太簡單了，但是它確實幫助我們實現了一個鎖，而且能夠在真實場景進行使用的，我們現在用程式碼對上面我們寫的鎖進行測試。

測試程式：

public class SpinLockTest {

  public static int data;
  public static SpinLock lock = new SpinLock();

  public static void add() {
    for (int i = 0; i < 100000; i++) {
      // 上鎖 只能有一個執行緒執行 data++ 操作 其餘執行緒都只能進行while循環
      lock.lock();
      data++;
      lock.unlock();
    }
  }

  public static void main(String[] args) throws InterruptedException {
    Thread[] threads = new Thread[100];
    // 設置100個執行緒
    for (int i = 0; i < 100; i ++) {
      threads[i] = new Thread(SpinLockTest::add);
    }
    // 啟動一百個執行緒
    for (int i = 0; i < 100; i++) {
      threads[i].start();
    }
    // 等待這100個執行緒執行完成
    for (int i = 0; i < 100; i++) {
      threads[i].join();
    }
    System.out.println(data); // 10000000
  }
}

在上面的程式碼單中，我們使用100個執行緒，然後每個執行緒循環執行100000data++操作，上面的程式碼最後輸出的結果是10000000，和我們期待的結果是相等的，這就說明我們實現的自旋鎖是正確的。

自己動手寫可重入自旋鎖

可重入自旋鎖

在上面實現的自旋鎖當中已經可以滿足一些我們的基本需求了，就是一個時刻只能夠有一個執行緒執行臨界區的程式碼。但是上面的的程式碼並不能夠滿足重入的需求，也就是說上面寫的自旋鎖並不是一個可重入的自旋鎖，事實上在上面實現的自旋鎖當中重入的話就會產生死鎖。

我們通過一份程式碼來模擬上面重入產生死鎖的情況：

public static void add(int state) throws InterruptedException {
  TimeUnit.SECONDS.sleep(1);
  if (state <= 3) {
    lock.lock();
    System.out.println(Thread.currentThread().getName() + "\t進入臨界區 state = " + state);
    for (int i = 0; i < 10; i++)
      data++;
    add(state + 1); // 進行遞歸重入 重入之前鎖狀態已經是1了 因為這個執行緒進入了臨界區
    lock.unlock();
  }
}
  • 在上面的程式碼當中加入我們傳入的參數state的值為1，那麼在執行緒執行for循環之後再次遞歸調用add函數的話，那麼state的值就變成了2。
  • if條件仍然滿足，這個執行緒也需要重新獲得鎖，但是此時鎖的狀態是1，這個執行緒已經獲得過一次鎖了，但是自旋鎖期待的鎖的狀態是0，因為只有這樣他才能夠再次獲得鎖，進入臨界區，但是現在鎖的狀態是1，也就是說雖然這個執行緒獲得過一次鎖，但是它也會一直進行while循環而且永遠都出不來了，這樣就形成了死鎖了。

可重入自旋鎖思想

針對上面這種情況我們需要實現一個可重入的自旋鎖，我們的思想大致如下：

  • 在我們實現的自旋鎖當中，我們可以增加兩個變數，owner一個用於存當前擁有鎖的執行緒，count一個記錄當前執行緒進入鎖的次數。
  • 如果執行緒獲得鎖，owner = Thread.currentThread()並且count = 1。
  • 當執行緒下次再想獲取鎖的時候，首先先看owner是不是指向自己，則一直進行循環操作，如果是則直接進行count++操作，然後就可以進入臨界區了。
  • 我們在出臨界區的時候，如果count大於一的話，說明這個執行緒重入了這把鎖，因此不能夠直接將鎖設置為0也就是未上鎖的狀態，這種情況直接進行count--操作，如果count等於1的話，說明執行緒當前的狀態不是重入狀態（可能是重入之後遞歸返回了），因此在出臨界區之前需要將鎖的狀態設置為0，也就是沒上鎖的狀態，好讓其他執行緒能夠獲取鎖。

可重入鎖程式碼實現：

實現的可重入鎖程式碼如下：

public class ReentrantSpinLock extends SpinLock {

  private Thread owner;
  private int count;

  @Override
  public void lock() {
    if (owner == null || owner != Thread.currentThread()) {
      while (!value.compareAndSet(0, 1));
      owner = Thread.currentThread();
      count = 1;
    }else {
      count++;
    }

  }

  @Override
  public void unlock() {
    if (count == 1) {
      count = 0;
      value.compareAndSet(1, 0);
    }else
      count--;
  }
}

下面我們通過一個遞歸程式去驗證我們寫的可重入的自旋鎖是否能夠成功工作。

測試程式：

import java.util.concurrent.TimeUnit;

public class ReentrantSpinLockTest {

  public static int data;
  public static ReentrantSpinLock lock = new ReentrantSpinLock();

  public static void add(int state) throws InterruptedException {
    TimeUnit.SECONDS.sleep(1);
    if (state <= 3) {
      lock.lock();
      System.out.println(Thread.currentThread().getName() + "\t進入臨界區 state = " + state);
      for (int i = 0; i < 10; i++)
        data++;
      add(state + 1);
      lock.unlock();
    }
  }

  public static void main(String[] args) throws InterruptedException {
    Thread[] threads = new Thread[10];
    for (int i = 0; i < 10; i++) {
      threads[i] = new Thread(new Thread(() -> {
        try {
          ReentrantSpinLockTest.add(1);
        } catch (InterruptedException e) {
          e.printStackTrace();
        }
      }, String.valueOf(i)));
    }
    for (int i = 0; i < 10; i++) {
      threads[i].start();
    }
    for (int i = 0; i < 10; i++) {
      threads[i].join();
    }
    System.out.println(data);
  }
}

上面程式的輸出：

Thread-3	進入臨界區 state = 1
Thread-3	進入臨界區 state = 2
Thread-3	進入臨界區 state = 3
Thread-0	進入臨界區 state = 1
Thread-0	進入臨界區 state = 2
Thread-0	進入臨界區 state = 3
Thread-9	進入臨界區 state = 1
Thread-9	進入臨界區 state = 2
Thread-9	進入臨界區 state = 3
Thread-4	進入臨界區 state = 1
Thread-4	進入臨界區 state = 2
Thread-4	進入臨界區 state = 3
Thread-7	進入臨界區 state = 1
Thread-7	進入臨界區 state = 2
Thread-7	進入臨界區 state = 3
Thread-8	進入臨界區 state = 1
Thread-8	進入臨界區 state = 2
Thread-8	進入臨界區 state = 3
Thread-5	進入臨界區 state = 1
Thread-5	進入臨界區 state = 2
Thread-5	進入臨界區 state = 3
Thread-2	進入臨界區 state = 1
Thread-2	進入臨界區 state = 2
Thread-2	進入臨界區 state = 3
Thread-6	進入臨界區 state = 1
Thread-6	進入臨界區 state = 2
Thread-6	進入臨界區 state = 3
Thread-1	進入臨界區 state = 1
Thread-1	進入臨界區 state = 2
Thread-1	進入臨界區 state = 3
300

從上面的輸出結果我們就可以知道，當一個執行緒能夠獲取鎖的時候他能夠進行重入，而且最終輸出的結果也是正確的，因此驗證了我們寫了可重入自旋鎖是有效的！

總結

在本篇文章當中主要給大家介紹了自旋鎖和可重入自旋鎖的原理，並且實現了一遍，其實程式碼還是比較簡單關鍵需要大家將這其中的邏輯理清楚：

  • 所謂自旋鎖就是通過while循環實現的，讓拿到鎖的執行緒進入臨界區執行程式碼，讓沒有拿到鎖的執行緒一直進行while死循環。
  • 可重入的含義就是一個執行緒已經競爭到了一個鎖，在競爭到這個鎖之後又一次有重入臨界區程式碼的需求，如果能夠保證這個執行緒能夠重新進入臨界區，這就叫可重入。
  • 我們在實現自旋鎖的時候使用的是AtomicInteger類，並且我們使用0和1這兩個數值用於表示無鎖和鎖被佔用兩個狀態，在獲取鎖的時候使用while循環不斷進行CAS操作，直到操作成功返回true，在釋放鎖的時候使用CAS將鎖的狀態從1變成0。
  • 實現可重入鎖最重要的一點就是需要記錄是那個執行緒獲得了鎖，同時還需要記錄獲取了幾次鎖，因為我們在解鎖的時候需要進行判斷，之後count = 1的情況才能將鎖的狀態從1設置成0。

以上就是本篇文章的所有內容了，我是LeHung，我們下期再見！！！更多精彩內容合集可訪問項目：//github.com/Chang-LeHung/CSCore

關注公眾號：一無是處的研究僧，了解更多電腦（Java、Python、電腦系統基礎、演算法與數據結構）知識。

Tags:

VirMach 便宜 VPS

QNews

QNews