Rust 並發程式設計釋放與取得排序

Rust 提供了原子操作和記憶體排序機制，讓開發者得以精確控制多執行緒環境下的資料同步。釋放與取得排序是其中關鍵的同步機制，透過建立「發生於之前」（happens-before）關係，確保執行緒間的資料可見性。當一個執行緒以 Release 排序儲存資料，另一個執行緒以 Acquire 排序讀取資料時，釋放執行緒的操作結果對取得執行緒可見。文章中的程式碼範例展示瞭如何利用原子布林值和 compare_exchange 操作實作無鎖的資料存取保護，並解釋瞭如何使用原子指標進行延遲初始化。此外，文章還探討了消費序和順序一致序等更進階的記憶體排序概念，以及原子圍欄的使用，幫助讀者更深入地理解 Rust 的記憶體模型。

釋放與取得排序：深入理解並發程式設計中的同步機制

在並發程式設計的世界中，正確地同步不同執行緒之間的資料存取是至關重要的。Rust 語言透過其強大的所有權系統和原子操作，為開發者提供了精確控制記憶體排序的能力。其中，釋放（Release）與取得（Acquire）排序是確保執行緒間正確同步的關鍵機制。

瞭解釋放與取得排序

釋放與取得排序是一種記憶體排序約束，用於建立執行緒間的「發生於之前」（happens-before）關係。這種關係確保了當一個執行緒釋放資料（透過原子儲存操作），而另一個執行緒取得該資料（透過原子載入操作）時，釋放執行緒在釋放資料之前的所有操作，對取得執行緒在取得資料之後的操作都是可見的。

例項分析

考慮以下範例程式碼：

static mut DATA: u64 = 0;
static READY: AtomicBool = AtomicBool::new(false);

fn main() {
    thread::spawn(|| {
        // 安全：尚未設定 READY 標誌，因此沒有其他執行緒正在存取 DATA
        unsafe { DATA = 123 };
        READY.store(true, Release); // 之前的全部操作在此儲存之後可見
    });

    while !READY.load(Acquire) { // 在此載入 `true` 之後，之前的全部操作可見
        thread::sleep(Duration::from_millis(100));
        println!("waiting...");
    }

    // 安全：READY 已設定，因此 DATA 不再被修改
    println!("{}", unsafe { DATA });
}

程式碼解析

資料初始化與執行緒建立：主執行緒建立了一個新的執行緒，並在新執行緒中對靜態變數 DATA 進行指定操作（DATA = 123）。由於 DATA 是靜態可變變數，這種操作需要使用 unsafe 區塊。
釋放操作：新執行緒透過 READY.store(true, Release) 將 READY 標誌設為 true。這裡使用了 Release 排序，確保了在這個儲存操作之前的所有操作（包括對 DATA 的指定），對其他執行緒在執行取得操作之後都是可見的。
取得操作：主執行緒透過 READY.load(Acquire) 載入 READY 的值，並檢查是否為 true。這裡使用了 Acquire 排序，確保了在這個載入操作之後，主執行緒可以看到新執行緒在釋放操作之前的所有操作結果。
資料存取：一旦主執行緒觀察到 READY 為 true，它就能安全地存取 DATA，因為 Acquire 操作確保了 DATA 的指定操作對主執行緒是可見的。

#### 內容解密：

Release 排序：確保在 Release 操作之前的所有記憶體操作對其他執行緒在執行相應的 Acquire 操作之後可見。
Acquire 排序：確保在 Acquire 操作之後的操作能夠看到在相應 Release 操作之前的所有記憶體操作結果。
happens-before 關係：透過 Release 和 Acquire 操作建立的執行緒間同步關係，確保資料的正確存取。

更正式的解釋

happens-before 關係是在一個 Acquire 載入操作觀察到另一個 Release 儲存操作的結果時形成的。這種關係的確立，取決於原子變數的總修改順序。即使相同的數值被儲存多次，每一次操作都代表了總修改順序中的一個獨立事件。當我們載入一個數值時，所載入的數值對應於原子變數時間線上的某個特定點，這告訴我們可能正在與哪個操作進行同步。

總修改順序範例

考慮一個原子變數，其總修改順序如下：

初始化為 0。
執行緒二執行 Release-store 操作，儲存 7。
執行 Relaxed-store 操作，儲存 63。
執行緒一執行 Release-store 操作，再次儲存 7。

如果我們 Acquire-load 載入到 7，我們可能與執行緒二的 Release-store 操作或執行緒一的 Release-store 操作建立 happens-before 關係。

鎖定機制範例

互斥鎖（Mutex）是 Release 和 Acquire 排序最常見的應用場景。當執行緒解鎖互斥鎖時，它使用 Release 排序；當執行緒鎖定互斥鎖時，它使用 Acquire 排序。這樣就建立了解鎖操作和隨後鎖定操作之間的 happens-before 關係，確保了資料的正確同步。

Mermaid 圖解：釋放與取得排序的流程

  graph LR
    A[執行緒 1：釋放資料] -->|Release 操作|> B[原子變數]
    B -->|Acquire 操作|> C[執行緒 2：取得資料]
    D[執行緒 1 內的操作] -->|happens-before|> E[執行緒 2 內的操作]

圖表翻譯：

此圖表展示了透過 Release 和 Acquire 操作在兩個執行緒之間建立 happens-before 關係的流程。執行緒 1 執行 Release 操作將資料儲存到原子變數，而執行緒 2 透過 Acquire 操作從原子變數中載入資料，從而確保執行緒 1 在釋放資料之前的操作結果對執行緒 2 在取得資料之後的操作可見。

使用釋放與取得引導進行無鎖初始化

在多執行緒程式設計中，正確地使用原子操作和記憶體順序對於確保資料的正確性和執行緒間的同步至關重要。本章節將探討如何利用釋放（Release）與取得（Acquire）記憶體順序來實作無鎖的資料結構和初始化過程。

無鎖鎖定機制範例

以下範例展示了一種簡單的無鎖鎖定機制，利用原子布林值（AtomicBool）來保護對靜態變數 DATA 的存取：

static mut DATA: String = String::new();
static LOCKED: AtomicBool = AtomicBool::new(false);

fn f() {
    if LOCKED.compare_exchange(false, true, Acquire, Relaxed).is_ok() {
        // 安全：我們持有獨佔鎖，因此沒有其他執行緒正在存取 DATA。
        unsafe { DATA.push('!') };
        LOCKED.store(false, Release);
    }
}

fn main() {
    thread::scope(|s| {
        for _ in 0..100 {
            s.spawn(f);
        }
    });
}

內容解密：

我們使用 AtomicBool 型別的 LOCKED 變數來實作鎖定機制。
compare_exchange 操作嘗試將 LOCKED 從 false 變更為 true。如果成功，表示獲得鎖定，可以安全地存取 DATA。
使用 Acquire 記憶體順序確保在獲得鎖定後，對 DATA 的存取不會被重排到鎖定操作之前。
在完成對 DATA 的操作後，使用 Release 記憶體順序將 LOCKED 設定為 false，釋放鎖定，確保之前的操作不會被重排到此操作之後。

使用指標進行延遲初始化

對於較大的資料型別，無法直接使用單一原子變數進行初始化。此時，可以透過原子指標（AtomicPtr）來實作無鎖的延遲初始化：

use std::sync::atomic::AtomicPtr;

fn get_data() -> &'static Data {
    static PTR: AtomicPtr<Data> = AtomicPtr::new(std::ptr::null_mut());
    let mut p = PTR.load(Acquire);
    if p.is_null() {
        p = Box::into_raw(Box::new(generate_data()));
        if let Err(e) = PTR.compare_exchange(std::ptr::null_mut(), p, Release, Acquire) {
            // 安全：p 來自上面的 Box::into_raw，且未與其他執行緒分享。
            drop(unsafe { Box::from_raw(p) });
            p = e;
        }
    }
    // 安全：p 非空且指向已正確初始化的值。
    unsafe { &*p }
}

內容解密：

使用 AtomicPtr 儲存指向 Data 的指標，利用空指標作為未初始化的標記。
使用 Acquire 記憶體順序載入指標，確保如果指標非空，則指向的資料已正確初始化。
如果指標為空，則生成新的 Data 例項，並嘗試使用 compare_exchange 將其指標原子地存入 PTR。
使用 Release 記憶體順序確保在 compare_exchange 成功時，資料的初始化操作不會被重排到指標的儲存之後。
如果 compare_exchange 失敗，表示其他執行緒已完成初始化，則釋放當前執行緒生成的資料，並使用其他執行緒儲存的指標。

未來，我們可以進一步探索更複雜的無鎖資料結構和演算法，利用 Rust 的所有權和借用系統來確保記憶體安全，同時保持高效的平行效能。此外，研究和應用更先進的同步機制和記憶體模型最佳化技術，將有助於推動多執行緒程式設計的發展和應用。

效能最佳化分析

在實作無鎖資料結構時，效能是一個重要的考量因素。正確地使用原子操作和記憶體順序可以在確保正確性的同時，最大化程式的平行度和效能。未來的工作可以集中在對不同無鎖演算法的效能進行深入分析和比較，以指導實際應用中的選擇和最佳化。

安全性考量

安全性是多執行緒程式設計中的另一個重要方面。利用 Rust 的型別系統和所有權機制，可以在編譯期捕捉許多常見的平行程式設計錯誤，從而提高程式的可靠性和安全性。未來，可以進一步研究如何結合形式化驗證技術和靜態分析工具，進一步加強對平行程式的正確性和安全性的保障。

探討消費序（Consume Ordering）與順序一致序（Sequentially Consistent Ordering）

在前面的範例中，我們探討了記憶體排序的基本概念。如果暫時擱置嚴格的記憶體模型，以更實際的角度來看，可以說釋出序（release ordering）防止了資料初始化被重新排序到與其他執行緒共用指標的儲存操作之後。這一點至關重要，因為否則其他執行緒可能會在資料完全初始化之前就看到它。同樣地，我們可以將取得序（acquire ordering）解釋為防止重新排序，進而避免在指標被載入之前就存取資料。然而，人們可能會合理地懷疑這在實踐中是否有意義。資料的位址未知之前，它怎麼可能被存取？我們可能會得出結論：比取得序更弱的排序可能就足夠了。而這種更弱的排序就是消費序（consume ordering）。

消費序（Consume Ordering）詳解

消費序基本上是取得序的一種輕量級、更高效的變體，其同步效果僅限於依賴於載入值的事物。這意味著，如果你從一個原子變數中消費載入（consume-load）一個釋出儲存（release-store）的值 x，那麼基本上，該儲存操作發生在對依賴表示式（如 *x、array[x] 或 table.lookup(x + 1)）的評估之前，但不一定發生在獨立操作（如讀取另一個我們不需要 x 值的變數）之前。

消費序的好處與挑戰

好訊息是，在所有現代處理器架構上，消費序都是透過與放寬序（relaxed ordering）完全相同的指令來實作的。換句話說，消費序可以是「免費」的，至少在某些平台上，這是取得序所無法做到的。

壞訊息是，實際上沒有編譯器真正實作消費序。事實證明，不僅「依賴」評估的概念難以定義，而且在轉換和最佳化程式時保持這種依賴關係的完整性更加困難。例如，編譯器可能會將 x + 2 - x 最佳化為簡單的 2，有效地丟棄了對 x 的依賴。對於更真實的表示式，如 array[x]，如果編譯器能夠對 x 的可能值或陣列元素做出邏輯推斷，也可能發生更為微妙的變化。當考慮控制流程（如 if 陳述式或函式呼叫）時，問題變得更加複雜。

消費序的實作困境

由於這些問題，編譯器通常會將消費序升級為取得序，以確保安全。C++20 標準甚至明確建議不要使用消費序，因為事實證明，除了取得序之外，其他實作方式是不可行的。

// 無法直接使用Ordering::Consume，因為Rust未暴露此選項
// 但我們可以探討其理論上的應用

內容解密：

上述 Rust 程式碼區塊展示了在 Rust 中無法直接使用 Ordering::Consume 的情況。雖然消費序在理論上可以提供更高效的同步機制，但在實際編譯器實作中，由於其複雜性，消費序並未被支援。

順序一致序（Sequentially Consistent Ordering）

最強的記憶體排序是順序一致序：Ordering::SeqCst。它包含了取得序（對於載入操作）和釋出序（對於儲存操作）的所有保證，並且還保證了操作的全域性一致順序。這意味著程式中每個使用 SeqCst 排序的操作都是所有執行緒都同意的單一全序的一部分。這個全序與每個個別變數的總修改順序一致。

SeqCst 排序的特點

由於 SeqCst 排序嚴格強於取得和釋出記憶體排序，因此順序一致的載入或儲存操作可以取代取得-載入或釋出-儲存，以形成發生之前（happens-before）的關係。換句話說，取得-載入不僅可以與釋出-儲存形成發生之前關係，也可以與順序一致的儲存形成發生之前關係，反之亦然。

use std::sync::atomic::Ordering::SeqCst;
static A: AtomicBool = AtomicBool::new(false);
static B: AtomicBool = AtomicBool::new(false);
static mut S: String = String::new();

fn main() {
    let a = thread::spawn(|| {
        A.store(true, SeqCst);
        if !B.load(SeqCst) {
            unsafe { S.push('!') };
        }
    });

    let b = thread::spawn(|| {
        B.store(true, SeqCst);
        if !A.load(SeqCst) {
            unsafe { S.push('!') };
        }
    });

    a.join().unwrap();
    b.join().unwrap();
}

內容解密：

此範例程式碼展示了使用 SeqCst 排序的原子操作。兩個執行緒首先將自己的原子布林值設為 true，以警告另一個執行緒它們即將存取 S，然後檢查另一個執行緒的原子布林值，以檢視是否可以安全地存取 S 而不會引起資料競爭。由於 SeqCst 排序保證了操作的全域性一致順序，因此可以確保只有其中一個執行緒能夠存取 S。

圍欄（Fences）

除了對原子變數的操作之外，還有一種可以應用記憶體排序的方法：原子圍欄。

std::sync::atomic::fence 函式表示一個原子圍欄，可以是釋出圍欄（Release）、取得圍欄（Acquire）或兩者兼有（AcqRel 或 SeqCst）。SeqCst 圍欄還額外參與順序一致的全序。

原子圍欄允許你將記憶體排序與原子操作分開。這在你想要將記憶體排序應用於多個操作，或者只在特定條件下應用記憶體排序時非常有用。

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

// 定義原子變數
static FLAG: AtomicBool = AtomicBool::new(false);

fn main() {
    // 設定釋出圍欄
    std::sync::atomic::fence(Ordering::Release);
    
    // 執行某些操作...
    
    // 設定取得圍欄
    std::sync::atomic::fence(Ordering::Acquire);
}

內容解密：

上述程式碼展示瞭如何在 Rust 中使用 std::sync::atomic::fence 函式來設定釋出圍欄和取得圍欄。圍欄可以用於控制記憶體操作的順序，確保在多執行緒環境中的資料一致性。

記憶體排序層級示意圖

  graph LR
    A[Relaxed Ordering] --> B[Consume Ordering]
    A --> C[Acquire/Release Ordering]
    C --> D[SeqCst Ordering]
    B -.->|理論上更高效，但未被實作| E[實際應用受限]

圖表翻譯： 此圖示展示了不同記憶體排序之間的層級關係。從放寬序（Relaxed Ordering）到順序一致序（SeqCst Ordering），排序的強度逐漸增加。消費序（Consume Ordering）理論上提供了一種更高效的同步機制，但由於實作困難，尚未被編譯器支援。取得/釋出序（Acquire/Release Ordering）提供了一種有效的同步方式，而順序一致序則保證了全域性一致的操作順序。

內容解密：

此 Mermaid 圖表展示了不同記憶體排序之間的層級關係，從最弱的放寬序到最強的順序一致序。消費序雖然理論上更高效，但由於實作困難，尚未被編譯器支援。取得/釋出序和順序一致序在實際應用中非常重要，用於確保多執行緒環境中的資料一致性。

玄貓

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

Rust 並發程式設計 釋放與取得排序

釋放與取得排序：深入理解並發程式設計中的同步機制

瞭解釋放與取得排序

例項分析

程式碼解析

#### 內容解密：

更正式的解釋

總修改順序範例

鎖定機制範例

Mermaid 圖解：釋放與取得排序的流程

圖表翻譯：

使用釋放與取得引導進行無鎖初始化

無鎖鎖定機制範例

內容解密：

使用指標進行延遲初始化

內容解密：

效能最佳化分析

安全性考量

探討消費序（Consume Ordering）與順序一致序（Sequentially Consistent Ordering）

消費序（Consume Ordering）詳解

消費序的好處與挑戰

消費序的實作困境

內容解密：

順序一致序（Sequentially Consistent Ordering）

SeqCst 排序的特點

內容解密：

圍欄（Fences）

內容解密：

記憶體排序層級示意圖

內容解密：

玄貓

Rust 並發程式設計釋放與取得排序