記憶體柵欄與作業系統同步原語

– 10 分鐘閱讀

記憶體柵欄在現代處理器架構中扮演著關鍵角色，用於控制指令的重新排序，確保程式在多執行緒環境下的正確性。x86-64 架構由於其較強的記憶體模型，僅在 SeqCst 柵欄需要時才使用 mfence 指令，而 ARM64 則需使用 dmb ish 和 dmb ishld 指令來實作不同型別的柵欄。理解這些底層機制有助於開發者編寫高效且可靠的平行程式。作業系統核心提供了必要的原語，讓開發者得以有效地控制執行緒的阻塞與喚醒，避免 busy-waiting 的效能損耗。系統呼叫是使用者程式與核心互動的橋樑，而 POSIX 標準則定義了一系列可移植的執行緒同步原語，例如 Mutex、Reader-Writer 鎖和條件變數。

記憶體柵欄（Memory Fences）

到目前為止，我們還未討論過的一種與記憶體排序相關的指令是記憶體柵欄（memory fences）或記憶體屏障（memory barriers）。記憶體柵欄指令用於表示 std::sync::atomic::fence，我們在第67頁的「柵欄」章節中已經討論過。

正如我們之前所見，x86-64 和 ARM64 上的記憶體排序主要與指令重新排序有關。柵欄指令可以防止某些型別的指令被重新排序到它之前或之後。

記憶體柵欄型別

  • Acquire柵欄：必須防止前面的載入操作與後面的任何記憶體操作重新排序。
  • Release柵欄：必須防止後續的儲存操作與前面的任何記憶體操作重新排序。
  • SeqCst柵欄：必須防止柵欄之前的所有記憶體操作與柵欄之後的記憶體操作重新排序。

不同架構下的柵欄指令實作

讓我們來看看四種不同的柵欄在 x86-64 和 ARM64 上的編譯結果：

Rust原始碼 編譯後x86-64 編譯後ARM64
pub fn a() { fence(Acquire); } a: ret a: dmb ishld; ret
pub fn a() { fence(Release); } a: ret a: dmb ish; ret
pub fn a() { fence(AcqRel); } a: ret a: dmb ish; ret
pub fn a() { fence(SeqCst); } a: mfence; ret a: dmb ish; ret

內容解密：

  1. 在x86-64架構下，Acquire和Release柵欄並沒有生成任何指令，因為x86-64的基本記憶體排序語義已經滿足了這些柵欄的需求。
  2. 只有SeqCst柵欄會生成mfence指令，確保柵欄之前的所有記憶體操作都已完成。
  3. 在ARM64架構下，dmb ish指令用於Release和AcqRel柵欄，因為ARM64不隱含提供Acquire和Release語義。
  4. Acquire柵欄使用dmb ishld，它只等待載入操作完成，但允許前面的儲存操作重新排序。

第8章：作業系統原語

到目前為止，我們主要關注的是非阻塞操作。如果我們想要實作像互斥鎖（mutex）或條件變數（condition variable）這樣的功能，需要一種方式來有效地阻塞目前的執行緒。

與核心介面

與核心的溝通方式高度依賴於作業系統，甚至是其版本。通常，這些細節被隱藏在一個或多個函式庫後面，這些函式庫為我們處理這些問題。例如，使用Rust標準函式庫，我們可以直接呼叫File::open()來開啟檔案，而無需瞭解作業系統核心介面的任何細節。同樣地，使用C標準函式庫libc，可以呼叫標準的fopen()函式來開啟檔案。

呼叫這樣的函式最終會導致對作業系統核心的呼叫，也稱為系統呼叫（syscall），這通常是透過專門的處理器指令來完成的。

內容解密：

  1. 作業系統核心負責決定哪個程式或執行緒何時執行、在哪個處理器核心上執行以及執行多長時間。
  2. 當一個執行緒正在等待某件事情發生時，核心可以停止給它任何處理器時間，將優先權給其他可以更好地利用這個稀缺資源的執行緒。
  3. 我們需要一種方式來通知核心我們正在等待某些事情，並請求它將我們的執行緒置於睡眠狀態，直到發生相關事件。

核心互動的重要性

  • 沒有作業系統的幫助，我們可以透過自旋（spinning）來實作阻塞，即重複嘗試某件事情，但這可能會浪費大量的處理器時間。
  • 為了有效地阻塞，我們需要作業系統核心的幫助。

圖表翻譯：

  graph LR
    A[記憶體柵欄] --> B[Acquire柵欄]
    A --> C[Release柵欄]
    A --> D[SeqCst柵欄]
    B --> E[x86-64: 無指令]
    B --> F[ARM64: dmb ishld]
    C --> G[x86-64: 無指令]
    C --> H[ARM64: dmb ish]
    D --> I[x86-64: mfence]
    D --> J[ARM64: dmb ish]

圖表翻譯： 此圖表展示了不同型別的記憶體柵欄在x86-64和ARM64架構下的實作方式。可以看到x86-64對於某些柵欄提供了「免費」的語義，而ARM64則需要特定的指令來實作這些柵欄。

內容解密：

本章節主要討論了記憶體柵欄的概念及其在不同架構下的實作方式。同時，我們也瞭解了作業系統核心在實作阻塞操作中的重要性。這些知識對於編寫高效的平行程式至關重要。

作業系統同步原語：POSIX 與 Rust 的整合

在探討作業系統提供的同步機制時，我們不得不關注 POSIX 標準及其在不同系統上的實作。POSIX 提供了一套廣泛使用的執行緒相關功能，包括 mutex、reader-writer 鎖以及 condition variables。這些同步原語是建立在作業系統核心介面之上的函式庫功能。

POSIX 同步原語概述

POSIX Threads（pthreads）提供了一系列用於執行緒管理的同步原語，主要包括：

  1. Mutex（互斥鎖）：用於保護分享資源，防止多執行緒同時存取。

    • 初始化：pthread_mutex_init()
    • 銷毀：pthread_mutex_destroy()
    • 鎖定：pthread_mutex_lock() / pthread_mutex_trylock()
    • 解鎖：pthread_mutex_unlock()
    • 靜態初始化：PTHREAD_MUTEX_INITIALIZER

  2. Reader-Writer Lock（讀寫鎖）：允許多個讀者同時存取資源，但寫者具有獨佔權。

    • 初始化：pthread_rwlock_init()
    • 銷毀：pthread_rwlock_destroy()
    • 讀鎖定：pthread_rwlock_rdlock()
    • 寫鎖定：pthread_rwlock_wrlock()
    • 解鎖：pthread_rwlock_unlock()
    • 靜態初始化：PTHREAD_RWLOCK_INITIALIZER

  3. Condition Variable（條件變數）：用於執行緒間的協調，通常與 mutex 一起使用。

    • 初始化：pthread_cond_init()
    • 銷毀：pthread_cond_destroy()
    • 等待：pthread_cond_wait() / pthread_cond_timedwait()
    • 通知：pthread_cond_signal() / pthread_cond_broadcast()
    • 靜態初始化：PTHREAD_COND_INITIALIZER

Mutex 屬性組態

在初始化 mutex 時，可以透過 pthread_mutexattr_t 來設定其屬性，例如：

  • 鎖定行為：預設（PTHREAD_MUTEX_DEFAULT）、錯誤檢查（PTHREAD_MUTEX_ERRORCHECK）、遞迴鎖定（PTHREAD_MUTEX_RECURSIVE）等。

在 Rust 中封裝 POSIX 同步原語

雖然可以直接使用 libc 提供的 POSIX 介面，但 Rust 的所有權和借用規則使得直接使用這些介面變得複雜。以下是一個簡單的 Mutex 封裝範例：

use std::cell::UnsafeCell;
use libc::{pthread_mutex_t, pthread_mutex_init, pthread_mutex_lock, pthread_mutex_unlock};

pub struct Mutex {
    m: UnsafeCell<pthread_mutex_t>,
}

impl Mutex {
    pub fn new() -> Self {
        let mut mutex = Mutex { m: UnsafeCell::new(std::mem::MaybeUninit::uninit().assume_init()) };
        unsafe {
            pthread_mutex_init(self.m.get(), std::ptr::null());
        }
        mutex
    }

    pub fn lock(&self) {
        unsafe {
            pthread_mutex_lock(self.m.get());
        }
    }

    pub fn unlock(&self) {
        unsafe {
            pthread_mutex_unlock(self.m.get());
        }
    }
}

內容解密：

  1. UnsafeCell 使用：由於 pthread_mutex_t 需要被修改，而 Rust 的借用規則不允許分享可變性，因此使用 UnsafeCell 來實作內部可變性。
  2. pthread_mutex_init 初始化：在 Mutex::new() 中呼叫 pthread_mutex_init 來初始化底層的 pthread_mutex_t。
  3. 鎖定與解鎖：lock() 和 unlock() 方法分別呼叫 pthread_mutex_lock() 和 pthread_mutex_unlock()，實作對 mutex 的操作。

同步原語的實作差異

不同作業系統對同步原語的實作可能有很大差異。例如：

  • 在某些系統上，mutex 的鎖定和解鎖操作可能直接對應到核心的 syscall。
  • 在其他系統上，函式庫會處理大部分操作，只有在執行緒需要被阻塞或喚醒時才會進行 syscall。

重要考量

  1. 穩定性介面：在 macOS 和 Windows 等系統上，直接使用 syscall 是不被允許的，程式應該透過函式庫介面與核心互動。
  2. POSIX 標準：POSIX 提供了一套標準的同步原語，但在不同系統上的實作可能有所不同。
  3. Rust 封裝：在 Rust 中封裝 POSIX 同步原語時，需要考慮 Rust 的所有權和借用規則，使用 UnsafeCell 來實作必要的可變性。
POSIX 同步原語關係圖
  graph TD;
    A[Mutex] --> B[pthread_mutex_init];
    A --> C[pthread_mutex_lock];
    A --> D[pthread_mutex_unlock];
    E[Reader-Writer Lock] --> F[pthread_rwlock_init];
    E --> G[pthread_rwlock_rdlock];
    E --> H[pthread_rwlock_wrlock];
    E --> I[pthread_rwlock_unlock];
    J[Condition Variable] --> K[pthread_cond_init];
    J --> L[pthread_cond_wait];
    J --> M[pthread_cond_signal];

圖表翻譯： 此圖表展示了POSIX標準中三種主要的同步原語：Mutex、Reader-Writer Lock和Condition Variable，並標示了它們對應的初始化、鎖定、解鎖和等待/通知函式。這些同步原語是平行程式設計中的基本構件，用於確保多執行緒環境下資源的安全存取。

未來方向

隨著平行程式設計需求的增加，進一步研究和最佳化同步機制將變得越來越重要。未來的研究方向可能包括：

  1. 更高效的同步演算法：開發新的同步演算法，以減少鎖競爭並提高多執行緒程式的效能。
  2. 硬體支援的同步機制：利用現代處理器提供的硬體支援（如事務記憶體）來實作更高效的同步。
  3. 跨平台同步機制：開發能夠在不同作業系統和硬體平台上高效運作的同步機制。

這些進展將有助於進一步提升平行程式設計的能力和效率，為未來的軟體開發提供更強大的支援。

Linux 系統中的 Futex 與同步機制

在探討 Linux 系統中的同步機制之前，我們先來瞭解 pthread 同步原語所面臨的問題。這些問題主要與物件移動和記憶體位址穩定性相關。

Pthread 同步原語與 Rust 的不相容問題

在 C 語言中，某些型別的資料結構依賴於其記憶體位址保持不變。例如，某些資料結構可能會包含指向自身的指標，或者將自身的指標儲存在某些全域資料結構中。在這種情況下，移動該物件到新的記憶體位置可能會導致未定義行為。

Rust 語言中常見的物件移動操作，例如函式傳回、引數傳遞或變數指定，都可能導致物件被移動到新的記憶體位置。因此，直接使用 pthread 同步原語會導致相容性問題。

解決方案：使用 Box 包裝 Mutex

為瞭解決上述問題，可以將 pthread mutex 包裝在 Box 中，使其擁有獨立的記憶體分配，從而確保其記憶體位址保持不變。

pub struct Mutex {
    m: Box<UnsafeCell<libc::pthread_mutex_t>>,
}

這種方法的缺點是，每個 Mutex 都會進行一次記憶體分配，這會增加建立、銷毀和使用 Mutex 的開銷。此外，這也會導致 new 函式無法被標記為 const，進而影響靜態 Mutex 的使用。

Futex：Linux 系統中的高效同步機制

Linux 系統中的 pthread 同步原語實際上是根據 futex（Fast User-space Mutex）系統呼叫實作的。Futex 提供了一種高效的同步機制，可以用於實作各種同步工具。

Futex 的基本操作

Futex 系統呼叫主要提供了兩種操作：FUTEX_WAIT 和 FUTEX_WAKE。FUTEX_WAIT 操作會將執行緒置於睡眠狀態，而 FUTEX_WAKE 操作則會喚醒正在等待的執行緒。

這些操作並不會修改原子變數的值，而是由核心記住哪些執行緒正在等待哪些記憶體位址，以便在 FUTEX_WAKE 操作時喚醒正確的執行緒。

Futex 的使用範例

以下是使用 futex 系統呼叫的範例程式碼：

#[cfg(not(target_os = "linux"))]
compile_error!("Linux only. Sorry!");

use std::sync::atomic::{AtomicU32, Ordering};

pub fn wait(a: &AtomicU32, expected: u32) {
    // 參考 futex(2) 手冊頁面瞭解系統呼叫簽名
    unsafe {
        libc::syscall(
            libc::SYS_futex, // futex 系統呼叫
            a as *const AtomicU32, // 操作的原子變數
            libc::FUTEX_WAIT, // futex 操作
            expected, // 預期的值
            std::ptr::null(), // 超時引數（這裡為空）
            std::ptr::null(), // uaddr2 引數（這裡為空）
        );
    }
}

pub fn wake(a: &AtomicU32) {
    unsafe {
        libc::syscall(
            libc::SYS_futex,
            a as *const AtomicU32,
            libc::FUTEX_WAKE,
            1, // 喚醒一個執行緒
            std::ptr::null(),
            std::ptr::null(),
        );
    }
}

fn main() {
    let counter = AtomicU32::new(0);

    // 模擬執行緒 1
    std::thread::spawn(move || {
        wait(&counter, 0);
        println!("Thread 1: Counter is now non-zero!");
    });

    // 模擬執行緒 2
    std::thread::spawn(move || {
        // 模擬一些工作
        std::thread::sleep(std::time::Duration::from_millis(100));
        counter.fetch_add(1, Ordering::SeqCst);
        wake(&counter);
        println!("Thread 2: Counter is now non-zero and notified!");
    });

    std::thread::sleep(std::time::Duration::from_secs(1));
}

#### 內容解密：

上述程式碼展示瞭如何使用 futex 系統呼叫實作執行緒同步。wait 函式將執行緒置於睡眠狀態，直到指定的原子變數值發生變化。wake 函式則喚醒正在等待的執行緒。

  1. wait 函式：該函式接受一個原子變數 a 和一個預期值 expected。如果原子變數的當前值與 expected 相同，則執行緒將進入睡眠狀態，等待被喚醒。

  2. wake 函式：該函式接受一個原子變數 a，並喚醒一個正在等待該變數的執行緒。

  3. main 函式：該範例展示了兩個執行緒之間的同步。執行緒 1 進入睡眠狀態，等待計數器變數的值發生變化。執行緒 2 在一段延遲後修改計數器變數的值，並喚醒執行緒 1。

Futex 的優勢

Futex 提供了一種高效的同步機制，避免了不必要的核心切換，從而提高了效能。此外，futex 還可以被用於實作各種同步工具，如 Mutex、Condition Variable 等。

隨著作業系統和程式語言的發展，同步機制也在不斷演進。未來，我們可以期待更多高效、靈活的同步機制被開發出來，以滿足日益增長的並發程式設計需求。

參考資料

Futex 操作流程圖

  sequenceDiagram
    participant Thread1 as "執行緒 1"
    participant Thread2 as "執行緒 2"
    participant Futex as "Futex"

    Thread1->>Futex: FUTEX_WAIT
    Note over Thread1,Futex: 執行緒 1 進入睡眠狀態
    Thread2->>Futex: 修改原子變數
    Thread2->>Futex: FUTEX_WAKE
    Futex->>Thread1: 喚醒執行緒 1
    Thread1->>Thread1: 繼續執行

圖表翻譯： 此圖表展示了 futex 操作的基本流程。執行緒 1 首先呼叫 FUTEX_WAIT 操作進入睡眠狀態。執行緒 2 修改原子變數後，呼叫 FUTEX_WAKE 操作喚醒執行緒 1。最終，執行緒 1 繼續執行。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。