Android SMP 入門

Android 3.0 以上版本平台版本已經過最佳化,可支援多處理器架構。本文件介紹以 C、C++ 和 Java 程式設計語言為對稱式多處理器系統編寫多執行緒程式碼時,可能會發生的問題 (以下僅為方便撰寫的「Java」僅稱為「Java」)。這可做為 Android 應用程式開發人員的初步介紹,而非針對這個主題進行完整討論。

簡介

SMP 是「對稱多處理器」的縮寫,其中說明兩個或以上相同的 CPU 核心共用主記憶體存取權的設計。直到幾年前,所有 Android 裝置都是 UP (統一處理器)。

大多數 (或非全部) Android 裝置始終具有多個 CPU,但過去只有一個用於執行應用程式,而其他裝置則用於執行應用程式,而其他裝置則管理多種裝置硬體 (例如無線電)。CPU 的架構可能不同,而在這些層級執行的程式無法使用主記憶體相互通訊。

現今銷售的大多數 Android 裝置都是採用 SMP 設計,因此軟體開發人員的工作流程會變得更複雜。多執行緒程式中的競爭狀況可能不會在單個處理器上造成明顯問題,但如果兩個或多個執行緒同時在不同核心上執行,可能會經常失敗。此外,如果在不同的處理器架構上執行,甚至在相同架構的不同實作上時,程式碼可能更難或較不容易發生失敗情形。通過 x86 完整測試的程式碼可能會在 ARM 上無法正常運作。如果使用較先進的編譯器重新編譯程式碼,程式碼可能會開始失敗。

本文件的其餘部分會說明原因,並說明如何確保程式碼正常運作。

記憶體一致性模型:為什麼 SMP 有些許差異

這就是複雜主題的高速光亮總覽。雖然部分區域並不完整,但請勿提供任何誤導或錯誤的資訊。如同下一節會說明,這裡的詳細資料通常不重要。

請參閱文件結尾的延伸閱讀,瞭解對主題進行更全面的處理方式。

記憶體一致性模型,或通常簡稱「記憶體模型」,說明程式設計語言或硬體架構對於記憶體存取行為的保證。例如,如果您將值寫入 A 地址,並將值寫入 B 位址,模型可能會保證每個 CPU 核心都照這個順序執行寫入作業。

大多數程式設計人員都習慣採用「依序一致性」,如下所述 (Adve & Gharachorloo):

  • 所有記憶體作業似乎一次僅執行一個作業
  • 單一執行緒中的所有作業似乎都會按照該處理者程式的描述順序執行。

我們暫時假設有一個非常簡單的編譯器或解譯器,不會產生意外情形:它會翻譯原始碼中的指派作業,按照相應的順序載入及儲存操作說明,每個存取權各一個指令。我們也會假設每個執行緒都會在自己的處理器上執行。

如果您查看一小段程式碼,並發現程式碼在記憶體中具有某些讀取和寫入作業,就會知道程式碼將按照預期順序執行這些讀取和寫入作業。CPU 實際上可能會重新排序指令並延遲讀取和寫入,但裝置上執行的程式碼無法指示 CPU 正在執行什麼動作,只能以簡單明瞭的方式執行指令。(我們將忽略記憶體對應裝置驅動程式 I/O)。

為了說明這些要點,考慮一小段程式碼會很有幫助,通常稱為「光學測試」

以下是一個簡單的範例,程式碼在兩個執行緒上執行:

討論串 1 討論串 2
A = 3
B = 5
reg0 = B
reg1 = A

在此和所有未來的例子中,記憶體位置會以大寫字母 (A、B、C) 表示,CPU 暫存器則是以「reg」開頭。所有記憶體一開始都是零。操作說明由上往下執行。在這邊,執行緒 1 會在位置 A 儲存值 3,然後在位置 B 儲存值 5。執行緒 2 會將位置 B 的值載入 reg0,然後將位置 A 的值載入至 reg1。(請注意,本信是按一組順序閱讀。)

系統假設執行緒 1 和執行緒 2 在不同 CPU 核心上執行。考慮多執行緒程式碼時,請「一律」假設。

依序一致性可保證在兩個執行緒執行完畢後,註冊會處於下列其中一種狀態:

註冊 狀態
reg0=5,reg1=3 可能 (優先執行執行緒 1)
reg0=0、reg1=0 可能 (先執行執行緒 2)
reg0=0,reg1=3 可能 (並行執行)
reg0=5,reg1=0 完全無法

為了進入我們在看到商店到 A 之前看到 B=5 的情況,所以讀取或寫入必需發生順序錯誤。不過,在循序一致性的機器上無法辦到。

單一處理器 (包括 x86 和 ARM) 通常具有依序一致性。執行緒似乎會以交錯方式執行,因為 OS 核心會在執行緒間切換。大多數的 SMP 系統 (包括 x86 和 ARM) 皆不一致。舉例來說,硬體在記憶體儲存過程中常常會進行緩衝區儲存,因此不會立即到達記憶體,並向其他核心顯示。

細節差異很大。例如,x86 儘管並非依序一致,但無法保證 reg0 = 5 和 reg1 = 0 是不可能的。系統會對儲存庫進行緩衝處理,但會保留順序。另一方面,ARM 則沒有。緩衝商店的順序不會保留,且商店可能無法同時連上其他所有核心。對於組裝程式設計人員而言,這些差異相當重要。不過,如下所示,C、C++ 或 Java 程式設計師應該也應該透過程式來隱藏這類架構差異。

到目前為止,我們不切實際的假設只有會重新訂購操作說明的硬體。實際上,編譯器也會重新排序操作說明,藉此改善效能。在我們的範例中,編譯器可能會決定,執行緒 2 中的部分較晚程式碼需要 reg1 的值之後才需要 reg0 因此先載入 reg1。或者,某些先前的程式碼可能已載入 A,而編譯器可能會決定重複使用該值,而非再次載入 A。無論是哪一種情況,載入至 reg0 和 reg1 的載入作業都能重新排序。

允許在硬體或編譯器中重新安排對不同記憶體位置的存取權,因為這不會影響單一執行緒的執行作業,而且可大幅改善效能。我們接著會小心,避免影響多執行緒程式的結果。

由於編譯器也可以重新排序記憶體存取作業,因此這個問題其實不是 SMP 新手。即使在單處理器上,編譯器還是可以重新安排載入作業,在範例中為 reg0 和 reg1,並且可在重新排序的操作說明之間安排 Thread 1。不過,如果編譯器發生未重新排序的情形,我們可能就不會觀察到這個問題。在大部分的 ARM SMP 中,即使沒有編譯器重新重新排序,仍可能在執行大量成功執行後看到重新排序。除非您以組裝語言編寫程式,否則 SMP 通常只會提高出現問題的可能性。

不受資料限制的程式設計

幸運的是,這通常有一個簡單的方式,可以讓您避免將任何細節納入考量。就算您遵循一些簡單明瞭的規則,通常不會忘記前面的每一個部分,「依序一致性」部分除外。遺憾的是,如果您不小心違反這些規則,可能會出現其他小工具。

現代的程式設計語言鼓勵所謂的「無資料種族」程式設計風格,只要您承諾不會導入「資料競爭」,並避免使用幾項結構告知編譯器,編譯器和硬體承諾可以提供依序一致的結果。但這並不代表這些物件會避免重新排序記憶體存取權。這表示如果您遵循規則,就無法分辨記憶體存取正在重新排序。只要承諾不要去香腸工廠,就會知道香腸是美味又可愛的食物,這就像告訴你。資料競爭是公開造成記憶體重新排序的棘手事實。

什麼是「資料種族」?

如果有兩個執行緒同時存取相同的一般資料,且至少有一個執行緒修改了相同的資料,就會發生「資料競爭」。「一般資料」是指非用於執行緒通訊的同步物件。互斥鎖、條件變數、Java 易變性或 C++ 不可分割物件不是一般資料,而且其存取可以競賽。事實上,這些函式是用來防止其他物件發生資料競爭。

為了判斷兩個執行緒是否可同時存取相同的記憶體位置,我們可從上文忽略記憶體重新排序討論,並採用循序一致性。如果 AB 最初是為 false,下列程式就不會有資料競爭:

討論串 1 討論串 2
if (A) B = true if (B) A = true

由於系統不會重新排序作業,因此兩個條件都會評估為 false,且不會更新這兩個變數。所以無法產生資料競爭。您無須思考如果從 A 載入並儲存至 B 在執行緒 1 中的載入量以某種方式重新排序時會發生什麼情況。編譯器無法將 Thread 1 重新編寫為「B = true; if (!A) B = false」,以重新排序。這就像是在大片市中心中吃香腸一樣。

資料競爭是在基本內建類型上正式定義,例如整數、參照或指標。指派給 int 時,同時在其他執行緒中讀取它會造成資料競爭。但同時編寫 C++ 標準程式庫和 Java Collections 程式庫,可讓您瞭解程式庫層級的資料競爭。除非同一個容器有並行存取,且至少一個能更新容器,否則前者承諾不會導入資料競爭。如果在一個執行緒中同時更新 set<T>,同時在另一個執行緒中讀取這個類型,程式庫就可以導入資料競爭,因此可不正式視為「程式庫層級的資料競爭」。相反地,如果在一個執行緒中更新一個 set<T>,而在另一個執行緒中讀取另一個執行緒,則不會造成資料競爭,因為在這種情況下,程式庫承諾不會導入 (低階) 資料競爭。

一般來說,對資料結構中不同欄位的並行存取無法造成資料競爭。不過,這項規則有一個重要例外狀況:C 或 C++ 中的連續位元序列視為單一「記憶體位置」。為了確定資料競爭是否存在,系統會將存取該序列中的任何位元欄位視為存取全部欄位。這表示一般硬體無法更新個別位元,而不需要讀取及重新寫入相鄰位元。Java 程式設計師沒有類比的疑慮。

避免資料競爭

新型程式設計語言提供多種同步處理機制,可避免資料競爭。最基本的工具包括:

鎖或互斥鎖
互斥鎖 (C++11 std::mutexpthread_mutex_t) 或 Java 中的 synchronized 區塊,可確保程式碼的特定部分不會與存取相同資料的其他程式碼區段並行執行。這種設施及類似的設施一般稱為「鎖頭」。持續取得特定鎖定後再存取共用資料結構,然後才將其發布,避免在存取資料結構時造成資料競爭。並確保更新和存取作業能夠完整執行,也就是說,系統不會在中間執行其他資料結構更新。但這是目前最常見防止資料競爭的工具。使用 Java synchronized 區塊、C++ lock_guardunique_lock,可確保在例外狀況發生時能正確釋放鎖定。
易變性/原子變數
Java 提供的 volatile 欄位支援並行存取,不會導入資料競爭。自 2011 年起,C 和 C++ 支援具有相似語意的 atomic 變數和欄位。這類函式通常比鎖定更難使用,因為這種模式只能確保單一變數的個別存取作業不可部分完成。在 C++ 中,這通常會擴充為簡單的讀取-修改-寫入作業,例如遞增。Java 需要特殊方法呼叫。)與鎖定不同,volatileatomic 變數無法直接用於防止其他執行緒幹擾較長的程式碼序列。

請特別注意,volatile 在 C++ 和 Java 中有截然不同的意義。在 C++ 中,volatile 不會防範資料競爭,但較舊的程式碼通常會將其做為缺少 atomic 物件的解決方法。不建議這樣做;在 C++ 中,針對可由多個執行緒並行存取的變數使用 atomic<T>。C++ volatile 適用於裝置註冊等用途。

C/C++ atomic 變數或 Java volatile 變數可用於防止其他變數的資料競爭。如果宣告 flag 具有 atomic<bool>atomic_bool(C/C++) 或 volatile boolean (Java) 類型,且一開始為 false,則下列程式碼片段為無 data-race-free:

討論串 1 討論串 2
A = ...
  flag = true
while (!flag) {}
... = A

由於執行緒 2 等待設定 flag,因此執行緒 2 中 A 的存取權必須在執行緒後發生,而不是同時指派給執行緒 1 中的 A。因此,A 上沒有任何資料競爭。flag 的競賽不會計為資料競爭,因為揮發性/原子存取作業不是「一般的記憶體存取」。

實作作業必須能夠適度防止或隱藏記憶體重新排序,確保程式碼如上述光學測試可正常運作。相較於一般存取作業,這通常會使易變性/原子記憶體存取成本大幅增加。

雖然上述範例不受資料限制,但與 Java 中的 Object.wait() 或 C/C++ 中的條件變數一起鎖定,通常提供更好的解決方案,不必在消耗電池的情況下等待迴圈。

顯示記憶體重新排序時

不受資料限制的程式設計通常讓我們不必明確處理記憶體存取重新排序問題。但是在某些情況下,重新排序仍然可見:
  1. 如果程式含有錯誤導致無意間的資料競爭,編譯器和硬體轉換作業可能會變得明顯,而程式的行為也可能出乎意料。舉例來說,如果上述範例忘記宣告 flag 變動情形,執行緒 2 可能會發現未初始化的 A。或者,編譯器可能會決定標記在 Thread 2 的迴圈期間不可變更,並將程式轉換為
    討論串 1 討論串 2
    A = ...
      flag = true
    reg0 = 標記; while (!reg0) {}
    ... = A
    偵錯時,雖然 flag 為 true,但您可能會發現迴圈不斷持續。
  2. C++ 提供可明確放寬依序一致性的工具,即使沒有競賽也不受影響。完整作業可以採用明確的 memory_order_... 引數。同樣地,java.util.concurrent.atomic 套件針對一組類似的設施提供更多受限制的設施,特別是 lazySet()。Java 程式設計師有時會利用刻意進行資料競爭來達到類似效果。這些都能在程式設計複雜性下大幅提升效能。我們會按照下文進行簡短的討論。
  3. 部分 C 和 C++ 程式碼是以較舊的樣式編寫,與目前語言標準並非完全一致,其中使用 volatile 變數而不是 atomic 變數,且插入「柵欄」或「阻隔線」明確禁止記憶體排序。這需要明確說明存取順序,以及瞭解硬體記憶體模型。這些行與這幾行的程式設計樣式仍會用於 Linux kernel。這不應用於新的 Android 應用程式,也未在此處進一步討論。

練習

對記憶體一致性問題進行偵錯並不容易。如果缺少鎖定,atomicvolatile 宣告會導致部分程式碼讀取過時資料,您可能無法透過偵錯工具檢查記憶體傾印,找出原因。當您發出偵錯工具查詢時,CPU 核心可能已觀察到所有完整的存取權組合,而記憶體和 CPU 暫存器的內容也會顯示為「不可能」狀態。

C 中的禁止事項

以下列舉幾個錯誤程式碼的例子,以及簡單的修正方式。在開始之前,我們需要討論基本語言功能的用法。

C/C++ 和「volatile」

C 和 C++ volatile 宣告是一種非常特殊的工具,這會防止編譯器重新排序或移除易變性存取權。這對存取硬體裝置註冊的程式碼、對應至多個位置的記憶體,或與 setjmp 相關的記憶體相當實用。但 C 和 C++ volatile 與 Java volatile 不同,並非專為執行緒通訊而設計。

在 C 和 C++ 中,volatile 資料的存取權可透過非揮發性資料重新重新排序,而且不提供不可部分完成的保證。因此,volatile 無法用於可移植程式碼的執行緒之間共用資料,即使在單處理器上也是如此。C volatile 通常不會阻止硬體重新排序存取權,因此在多執行緒 SMP 環境中,它本身就比較不實用。因此,C11 和 C++11 支援 atomic 物件。建議您改用這些要素。

許多較舊的 C 和 C++ 程式碼仍會濫用 volatile 進行執行緒通訊。通常適合用於機器暫存器的資料,前提是資料必須與明確圍欄搭配使用,或是記憶體順序不重要。但並不保證未來編譯器能正常運作。

範例

在多數情況下,建議您使用鎖定 (例如 pthread_mutex_t 或 C++11 std::mutex) 而非不可部分完成的作業,但我們會採用後者,說明如何在實際情況下運用這些方式。

MyThing* gGlobalThing = NULL;  // Wrong!  See below.
void initGlobalThing()    // runs in Thread 1
{
    MyStruct* thing = malloc(sizeof(*thing));
    memset(thing, 0, sizeof(*thing));
    thing->x = 5;
    thing->y = 10;
    /* initialization complete, publish */
    gGlobalThing = thing;
}
void useGlobalThing()    // runs in Thread 2
{
    if (gGlobalThing != NULL) {
        int i = gGlobalThing->x;    // could be 5, 0, or uninitialized data
        ...
    }
}

這裡的概念是分配結構、初始化其欄位,最後,將結構「發布」儲存在全域變數中。此時,任何其他執行緒都能查看,但因為已完全初始化而沒有問題嗎?

問題是,在欄位初始化前,可以觀察到 gGlobalThing 的商店,原因通常是編譯器或處理器將商店重新排序至 gGlobalThingthing->x。從 thing->x 讀取的另一個執行緒可以看到 5、0,甚至是未初始化的資料。

這裡的核心問題是 gGlobalThing 上的資料競爭。如果執行緒 1 在 Thread 2 呼叫 useGlobalThing() 時呼叫 initGlobalThing(),則在寫入時可以讀取 gGlobalThing

如要修正這項錯誤,請將 gGlobalThing 宣告為不可分割。在 C++11 中:

atomic<MyThing*> gGlobalThing(NULL);

這可確保其他執行緒能以正確順序看到寫入作業。它也保證可防止其他允許,但不太可能發生在實際的 Android 硬體上。例如,這可以確保我們無法看到僅有部分寫入的 gGlobalThing 指標。

Java 的禁止事項

我們尚未討論過一些相關的 Java 語言功能,所以先簡單介紹這些功能。

從技術層面來說,Java 不需要程式碼是不受資料限制的。另外,也有少數經過精心編寫的 Java 程式碼,可在資料競爭時正確運作。不過,編寫這類程式碼非常麻煩,我們只是在下面簡短討論。更糟的是,指定這類程式碼意義的專家不再相信規格正確無誤。(這個規格適用於無資料種族)。

目前我們會採用無資料限制的模型,Java 基本上提供與 C 和 C++ 大致相同的保證。同樣地,該語言提供可明確放寬依序一致性的部分基本功能,特別是 java.util.concurrent.atomic 中的 lazySet()weakCompareAndSet() 呼叫。與 C 和 C++ 一樣,我們會暫時忽略這些內容。

Java 的「已同步」和「易變性」關鍵字

「syncd」關鍵字可提供 Java 語言的內建鎖定機制。每個物件都有相關聯的「監控」,可用於提供互斥的存取權。如果兩個執行緒嘗試在同一個物件上「同步處理」,其中一個執行緒會等待另一個執行緒完成。

如先前所述,Java 的 volatile T 是 C++11 的 atomic<T> 類比。允許同時存取 volatile 欄位,且不會導致資料競爭。也忽略 lazySet() 等資料競爭,Java VM 的工作是確保結果依循順序排列。

具體來說,如果執行緒 1 寫入了 volatile 欄位,而執行緒 2 隨後從相同欄位讀取資料,並顯示新寫入的值,則執行緒 2 也一定會顯示執行緒 1 先前發出的所有寫入作業。就記憶體效果而言,寫入易變性與監控版本類似,而從易變性讀取作業就好比監聽器獲取。

C++ 的 atomic 有一項明顯的差異:如果我們在 Java 中編寫 volatile int x;,則 x++x = x + 1 相同;它會執行原子載入並遞增結果,然後執行不可部分完成的儲存庫。與 C++ 不同的是,整體的增量作業並非不可部分完成。原子增量作業是由 java.util.concurrent.atomic 提供。

範例

以下為單調計數器的簡易實作方式有誤(Java Theory andPractice: Managing volatility)

class Counter {
    private int mValue;
    public int get() {
        return mValue;
    }
    public void incr() {
        mValue++;
    }
}

假設 get()incr() 是從多個執行緒呼叫,而我們希望確保每個執行緒在呼叫 get() 時都能看到目前的計數。最明顯的問題是 mValue++ 實際上是三項運算:

  1. reg = mValue
  2. reg = reg + 1
  3. mValue = reg

如果兩個執行緒同時在 incr() 中執行,可能會導致其中一項更新遺失。如要讓遞增單位不可分割,我們需要將 incr() 宣告為「已同步」。

但仍無法播放,特別是在 SMP 上。仍有資料競爭,指出 get() 可以使用 incr() 並行存取 mValue。在 Java 規則下,get() 呼叫可按照其他程式碼的順序顯示。舉例來說,如果我們連續讀取了一列的兩個計數器,則結果可能會不一致,這是因為我們重新排列了 get() 呼叫 (由硬體或編譯器進行)。我們可宣告要同步處理的 get() 來修正問題。這項變更生效後,程式碼就顯然正確無誤。

遺憾的是,我們推出了鎖定爭用情況,可能導致效能降低。我們不必宣告要同步處理的 get(),而是使用「易變性」宣告 mValue (請注意,incr() 仍須使用 synchronize,因為 mValue++ 並非單一不可分割的作業)。這也能避免所有資料競爭,因此能保留依序一致性。 由於 incr() 同時會產生監控進入/結束負載,以及與易變性存放區相關的負擔,因此速度會稍微變慢,但 get() 速度會更快,因此即使讀取的寫入量過多,即使沒有爭用情況,仍是成功。(如要完全移除同步區塊,另請參閱 AtomicInteger)。

以下是另一個範例,類似於先前的 C 範例:

class MyGoodies {
    public int x, y;
}
class MyClass {
    static MyGoodies sGoodies;
    void initGoodies() {    // runs in thread 1
        MyGoodies goods = new MyGoodies();
        goods.x = 5;
        goods.y = 10;
        sGoodies = goods;
    }
    void useGoodies() {    // runs in thread 2
        if (sGoodies != null) {
            int i = sGoodies.x;    // could be 5 or 0
            ....
        }
    }
}

這與 C 程式碼的問題相同,也就是 sGoodies 上有資料競爭。因此,在 goods 中的欄位初始化之前,可能會觀察到 sGoodies = goods 指派作業。如果您使用 volatile 關鍵字宣告 sGoodies,系統就會還原依序一致性,且一切會正常運作。

請注意,只有 sGoodies 參照本身是可變動。對其中欄位的存取權則無法存取。一旦 sGoodies 變成 volatile,且記憶體順序正確保留後,您就無法並行存取這些欄位。陳述式 z = sGoodies.x 會執行 MyClass.sGoodies 的易變性載入作業,然後是 sGoodies.x 的不變性載入。如果您建立本機參照 MyGoodies localGoods = sGoodies,則後續的 z = localGoods.x 將不會執行任何易變性載入。

在 Java 程式設計中,常見的慣用語是著名的「雙檢查鎖定」:

class MyClass {
    private Helper helper = null;
    public Helper getHelper() {
        if (helper == null) {
            synchronized (this) {
                if (helper == null) {
                    helper = new Helper();
                }
            }
        }
        return helper;
    }
}

該想法是希望有一個與 MyClass 執行個體相關聯的 Helper 物件執行個體。我們只需建立一次,因此會透過專屬的 getHelper() 函式建立並傳回。為避免兩個執行緒建立執行個體時產生競爭,我們必須同步處理物件建立作業。不過,我們不想在每次呼叫中為「同步處理」區塊負擔負擔,因此只有在 helper 目前為空值時,我們才會這麼做。

這在 helper 欄位有資料競爭。另一個執行緒中的 helper == null 則可同時設定。

如要瞭解為何會失敗,請考慮稍微重新編寫相同的程式碼,如同編譯為類似 C 的語言一樣 (我們新增了幾個整數欄位來代表 Helper’s 建構函式活動):

if (helper == null) {
    synchronized() {
        if (helper == null) {
            newHelper = malloc(sizeof(Helper));
            newHelper->x = 5;
            newHelper->y = 10;
            helper = newHelper;
        }
    }
    return helper;
}

目前沒有任何項目可防止硬體或編譯器將商店重新排序為 helper,以對應至 x/y 欄位的值。其他執行緒可以找到 helper 非空值,但其欄位尚未設定且已可供使用。如需更多詳細資料和更多故障模式,請參閱附錄中的「雙重檢查鎖定功能毀損」聲明連結,或可在 Josh Bloch 撰寫的「有效的 Java 第 2 版」一文中,參閱附錄項目 71 (「行為延遲初始化」)。

解決方法有兩種:

  1. 完成簡單的操作並刪除外部檢查。這可確保我們絕不會在同步區塊外檢查 helper 的值。
  2. 宣告 helper 易變性。進行這項小幅變更後,範例 J-3 中的程式碼將在 Java 1.5 以上版本中正常運作。(您可能需要花一些時間說服自己是說錯的)。

以下為另一個 volatile 行為的插圖:

class MyClass {
    int data1, data2;
    volatile int vol1, vol2;
    void setValues() {    // runs in Thread 1
        data1 = 1;
        vol1 = 2;
        data2 = 3;
    }
    void useValues() {    // runs in Thread 2
        if (vol1 == 2) {
            int l1 = data1;    // okay
            int l2 = data2;    // wrong
        }
    }
}

查看 useValues() 時,如果 Thread 2 尚未觀察到 vol1 的更新,就無法判斷 data1data2 是否已設定。一旦看到 vol1 的更新,就會知道 data1 可以安全存取及正確讀取,而不會導入資料競爭。不過,它無法對 data2 做出任何假設,因為該商店是在揮發性商店之後執行。

請注意,volatile 無法用來防止彼此競爭的其他記憶體存取遭到重新排序。系統不保證會產生機器記憶體圍欄指示。另一個執行緒可在其他執行緒滿足特定條件時,才透過執行程式碼來避免資料競爭。

進行方式

在 C/C++ 中,則偏好 C++11 同步處理類別,例如 std::mutex。如果不是,請使用對應的 pthread 運算。這些元件包括適當的記憶體柵欄,可在所有 Android 平台版本上提供正確 (除非另有指定) 且有效率的行為。請務必正確使用。舉例來說,提醒您,條件變數等待可能會意外傳回,但不會發出信號,因此應該會顯示在迴圈中。

建議您不要直接使用原子函式,除非要實作的資料結構非常簡單,例如計數器。鎖定及解鎖 pthread 互斥鎖時,每個作業都需要一項不可部分完成,而且如果沒有爭用情況,通常成本會低於一次快取失敗,因此可以將互斥鎖呼叫替換為不可部分完成的作業,導致節省太多成本。如果資料結構較複雜的資料結構未鎖定,就必須特別謹慎地確保資料結構上的較高層級作業能保持完整 (而非只是完整組成部分)。

如果您使用原子作業,使用 memory_order... 或 lazySet() 放寬排序或許有助於提升效能,但比我們目前傳達的還更深入。在大部分使用這類程式碼的現有程式碼當中,我們發現之後存在錯誤。請盡可能避免出現這種狀況。 如果您的使用情境與下一節的內容不符,請確認您是專家,或是已諮詢專業人士。

避免使用 volatile 進行 C/C++ 中的執行緒通訊。

在 Java 中,一般而言,使用 java.util.concurrent 套件中的適當公用程式類別可以解決並行問題。程式碼經過妥善編寫並在 SMP 上經過完整測試。

也許您可以採取最安全的做法,就是讓物件不可變動。Java 的字串和整數等類別的物件會保留在物件建立後無法變更,可避免這些物件發生資料競爭的所有潛在問題。《Effective Java, 2nd Ed.》書籍提供了「項目 15:盡量減少變動性」的詳細說明。請特別注意,宣告 Java 欄位「Final」的重要性(Bloch)

提醒您,即使物件無法變更,仍要記得與其他執行緒進行通訊,不能進行任何形式的同步處理。這有時在 Java 中可能可以接受 (請見下方說明),但需要謹慎小心,也可能造成程式碼錯誤。如果效能不是極高,請新增 volatile 宣告。在 C++ 中,若沒有適當同步處理所需的指標或參照 (例如任何資料競爭),就會發生錯誤。在這種情況下,合理可能會導致間歇性當機。舉例來說,接收執行緒可能會因為商店重新排序,而看到未初始化的方法資料表指標。

如果現有的程式庫類別和不可變更類別都不適當,請使用 Java synchronized 陳述式或 C++ lock_guard / unique_lock 來保護讓多個執行緒存取任何欄位的存取權。如果互斥鎖不適用於您的情況,您應宣告共用欄位 volatileatomic,但請務必謹慎瞭解執行緒之間的互動。這些宣告並不會避免您遇到常見的並行程式設計錯誤,但可協助您避免在最佳化編譯器與 SMP 最佳化方面造成的神秘失敗問題。

您應該避免「發布」物件的參照,也就是在其建構函式中提供給其他執行緒使用。在 C++ 中,這較不重要,或者您遵循 Java 中的「無資料競爭」建議。但是,即使 Java 程式碼是在 Java 安全性模型的重要環境中執行,而且不受信任的程式碼也會存取「外洩」物件參照,因此可能會產生資料競爭,這是很有效的建議。如果您選擇忽略我們的警告並運用下一節所述的一些技巧,我們也非常重要。詳情請參閱「(Java 中的安全建構技巧)」一文。

進一步瞭解記憶體不足的記憶體訂單

C++11 及以上版本針對無資料限制的程式,提供放寬依序一致性保證的機制。各個不可分割作業的明確 memory_order_relaxedmemory_order_acquire (僅限載入) 和 memory_order_release(僅限儲存) 引數都提供比預設 (通常為隱含) 低的保證,memory_order_seq_cstmemory_order_acq_rel 提供 memory_order_acquirememory_order_release 保證,可提供不可部分完成的讀取-修改寫入作業。memory_order_consume 尚未充分指定或實作得很實用,因此目前應予以忽略。

Java.util.concurrent.atomic 中的 lazySet 方法與 C++ memory_order_release 存放區類似,有時候,Java 的一般變數會用來取代 memory_order_relaxed 存取,但實際上這類變數實際上較弱。與 C++ 不同的是,對宣告為 volatile 的變數沒有未排序的存取權。

一般情況下,除非極度容易使用效能,否則應避免出現這種情況。在 ARM 等弱排序的機器架構中,使用這種架構時,系統通常會按照每個原子作業數十次的機器循環順序來儲存這些架構。在 x86 中,只有商店才能取得最佳效能,因此較不顯眼。但稍微反觀,隨著記憶體系統越來越不是限制因素,優勢可能會隨著核心數量增加而降低。

弱點子的完整語意非常複雜。一般而言,這些規則要求對於語言規則有一定程度的瞭解,但我們這裡不會特別說明。例如:

  • 編譯器或硬體可將 memory_order_relaxed 存取 (但不得移出) 存取鎖定和發布的關鍵部分。這意味著,即使兩個 memory_order_relaxed 儲存庫是以重要區段分隔,仍可能會發生順序不彰的情形。
  • 當一般的 Java 變數以共用計數器濫用時,即使只由一個另一個執行緒增加,該執行緒仍可能看起來減少於另一個執行緒。不過,對於 C++ atomic memory_order_relaxed 而言,這並非如此。

我們將加入警告,在此提供少量的慣用語,似乎涵蓋許多因微不足順序排列的原子小學用途。其中許多都僅適用於 C++。

非賽車通行證

變數具有不可分割性的情況,是由於「有時」會與寫入同時讀取,但並非所有存取都會發生此問題。例如,由於變數是在重要區段外讀取,因此可能需要不可分割的形式,但所有更新內容都會受到鎖定保護。在這種情況下,由相同鎖定保護的讀取作業無法互相競爭,因為無法並行寫入。在這種情況下,非賽車存取 (在此例中為載入) 可以使用 memory_order_relaxed 加上註解,而不變更 C++ 程式碼的正確性。鎖定實作會針對其他執行緒進行存取時強制執行必要的記憶體順序,而 memory_order_relaxed 會指定基本上無須針對不可部分完成的存取權強制執行額外的排序限制。

Java 沒有實際的類比。

結果並非仰賴正確性

我們只使用賽車負載來產生提示時,通常也不用為載入強制執行任何記憶體排序。如果這個值不可靠,我們也無法確實使用結果推測其他變數的任何資訊。因此,即使無法保證記憶體排序,且負載是透過 memory_order_relaxed 引數提供,也沒關係。

常見的情況是使用 C++ compare_exchange,以不可分割的形式將 x 替換為 f(x)。初始載入 f(x)x 不一定要可靠。如果取得錯誤,compare_exchange 就會失敗,我們也會重試。x 的初始載入可以使用 memory_order_relaxed 引數,只有實際 compare_exchange 的記憶體排序很重要。

不可部分修改,但有未讀資料

有時候,資料會由多個執行緒平行修改,但在平行運算完成之前不會檢查。例如,在 C++ 中使用 fetch_add() 或在 C 中使用 atomic_fetch_add_explicit() ,就會由多個執行緒並行遞增的計數器,但一律忽略這些呼叫的結果。只有在所有更新都完成後,系統才會在結束時讀取產生的值。

在此情況下,您無法判斷對這項資料的存取權是否已重新排序,因此 C++ 程式碼可能會使用 memory_order_relaxed 引數。

簡易事件計數器是常見的範例。由於這很常見,因此建議您對本案例進行一些觀察:

  • 使用 memory_order_relaxed 可改善效能,但可能無法解決最重大的效能問題:每次更新都需要擁有計數器快取行的專屬存取權。這會導致每當有新的執行緒存取計數器時,就會造成快取遺失。如果更新經常需要在執行緒之間交替使用,那麼避免每次都更新共用計數器來解決問題,例如使用執行緒本機計數器,並在最後加上總結。
  • 這項技巧與上一節結合:使用 memory_order_relaxed 的所有作業更新值時,可以同時讀取近似值和不可靠的值。不過,請務必將產生的值視為完全不可靠。這是因為計數似乎已增加一次,並不代表可以計算另一個執行緒以達到執行增量的時間點。遞增單位可能會改為以先前的程式碼重新排序。(與先前提過的類似情況相同,C++ 會保證這類計數器的第二次載入作業,不會傳回低於相同執行緒中較早載入的值。除非計數器溢出。)
  • 尋找嘗試透過執行個別不可部分 (或非) 讀取和寫入、但不將遞增單位視為整個原子的形式來計算近似計數器值的程式碼時,是很常見的情況。一般引數是針對效能計數器或類似情況,這麼做「十分接近」。通常不會。當更新夠頻繁 (您可能會在意) 更新,大部分計數都會遺失。在四核心裝置上,可能會遺失超過一半的現象。 (簡易練習:請建構兩個執行緒情境,其中計數器會更新一百萬次,但最終計數器值為一個)。

簡單標記通訊

memory_order_release 儲存庫 (或讀取 - 修改-寫入作業) 可確保在 memory_order_acquire 載入 (或讀取-修改-寫入作業) 之後讀取寫入值時,也會觀察到 memory_order_release 儲存庫之前的任何儲存 (一般或不可分割)。相反地,凡是 memory_order_release 之前的載入,都不會觀察追蹤 memory_order_acquire 載入作業的任何商店。與 memory_order_relaxed 不同,這可讓這類不可部分的作業,將某個執行緒的進度傳達給另一個執行緒。

舉例來說,我們可以在 C++ 中, 將上述的雙重檢查鎖定範例重新編寫為

class MyClass {
  private:
    atomic<Helper*> helper {nullptr};
    mutex mtx;
  public:
    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper == nullptr) {
        lock_guard<mutex> lg(mtx);
        myHelper = helper.load(memory_order_relaxed);
        if (myHelper == nullptr) {
          myHelper = new Helper();
          helper.store(myHelper, memory_order_release);
        }
      }
      return myHelper;
    }
};

獲取負載和發布儲存庫可確保如果看到非空值的 helper,我們也會看到其欄位已正確初始化。此外,我們也整合了先前非競速載入可使用 memory_order_relaxed 的觀察結果。

Java 程式設計師可以把 helper 代表為 java.util.concurrent.atomic.AtomicReference<Helper>,並使用 lazySet() 做為發布版本存放區。載入作業將繼續使用純 get() 呼叫。

在這兩種情況下,系統均會集中在初始化路徑上,這對效能而言不太可能至關重要。以下是較容易判讀的入侵方式:

    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper != nullptr) {
        return myHelper;
      }
      lock_guard&ltmutex> lg(mtx);
      if (helper == nullptr) {
        helper = new Helper();
      }
      return helper;
    }

這可以提供相同的快速路徑,但必須使用循序方式依循非效能重大路徑上的預設作業。

即使是在這裡,helper.load(memory_order_acquire) 可能會在目前 Android 支援的架構上產生相同的程式碼,做為對 helper 的簡單 (依序一致) 參照。實際上,最適合的最佳化功能可能是採用 myHelper 來消除第二次載入,不過日後的編譯器可能會自動執行此作業。

取得/發布順序並不會導致商店發生延遲,也無法確保其他執行緒以一致的順序向其他執行緒顯示。因此,不支援某些麻煩,但 Dekker 的共同排除演算法一般常見的程式碼模式:所有執行緒都會先設定一個標記,表示他們想要進行某些操作;如果執行緒「t」卻發現沒有其他執行緒嘗試執行某些操作,則可放心繼續操作,由於 t 的旗標仍設有設定,因此其他執行緒無法繼續執行。如果使用取得/發布順序存取標記,則這項作業會失敗,因為在錯誤執行後,其他人還是不會看見執行緒的標記。預設的 memory_order_seq_cst 則不會。

不可變更的欄位

如果物件欄位在首次使用時初始化,但之後從未變更,則可以透過低排序存取的方式初始化及讀取該欄位。在 C++ 中,這可以宣告為 atomic,並使用 memory_order_relaxed 或在 Java 中存取,但可以在沒有 volatile 的情況下宣告,且在不使用特殊測量的情況下存取。這需要下列所有訴訟保留:

  • 您應從欄位本身的值得知是否已初始化。如要存取欄位,快速路徑 test-and-return 值應只讀取欄位一次。在 Java 中,後者很重要。即使欄位測試已初始化,第二次載入也可能會讀取先前未初始化的值。在 C++ 中,「讀取一次」規則僅是不錯的做法。
  • 初始化與後續載入都必須不可分割,使用者就不應看到部分更新。如果是 Java,該欄位不得為 longdouble。如果是 C++,您必須進行不可部分完成的指派作業;由於 atomic 的建構並非完整作業,因此先建構將無法運作。
  • 重複初始化必須安全無虞,因為多個執行緒可能會同時讀取未初始化的值。在 C++ 中,這通常會遵循所有不可分割式類型的「可快速複製」規定;具有巢狀擁有指標的類型需要在複製建構函式中取消配置,無法輕易複製。如果是 Java,我們接受某些參照類型:
  • Java 參照僅限包含最終欄位的不可變更類型。不可變動類型的建構函式不應發布物件的參照。在這種情況下,Java 最終欄位規則可確保讀者查看參照時,也會看到初始化的最終欄位。C++ 與這些規則和自有物件的指標沒有任何類比,因此除了違反「可輕易複製」的要求之外,也是可接受的做法。

正在關閉記事

雖然這份文件並非只是刮開表面,但管理程度不多於淺的傻瓜。這是非常廣泛的主題,進一步探索的部分領域:

  • 實際的 Java 和 C++ 記憶體模型會以「之前發生之前」關係表示,其中指定了兩個動作保證依特定順序執行的時機。定義資料競爭時,我們非正式說明會「同時」執行兩個記憶體存取。官方定義是指先前各方皆未發生。它會指示您瞭解 Java 或 C++ 記憶體模型中「happens-before」和「syncs-with」的實際定義。雖然「同時」的直覺式概念通常更好,但這些定義具有指導性,特別是在您考慮在 C++ 中使用順序弱的 atomic 作業時。(目前的 Java 規格只會以非正式的方式定義 lazySet())。
  • 瞭解重新排序程式碼時可和禁止執行的編譯器。(JSR-133 規格提供了一些重要的法律轉型範例,可以產生非預期的結果)。
  • 瞭解如何在 Java 和 C++ 中編寫不可變的類別 (除了「在建構後不要變更任何項目」以外)。
  • 對「有效 Java、第 2 版」一文中「並行」一節提供的建議進行內部化建議。(例如,您應該避免呼叫在同步區塊中要覆寫的方法)。
  • 詳閱 java.util.concurrentjava.util.concurrent.atomic API,看看有哪些可用 API。請考慮使用 @ThreadSafe@GuardedBy 等並行註解 (來自 net.jcip.annotations)。

附錄的「延伸閱讀」一節提供文件和網站的連結,可進一步闡述這些主題。

附錄

實作同步處理儲存庫

(這不是多數程式設計人員會實作的想法,但討論內容真的更加完善)。

如果是 int 等小型內建類型以及 Android 支援的硬體,一般載入和商店操作說明可確保商店完全 (甚至完全不顯示) 顯示在載入相同位置的其他處理器上。因此,我們提供了一些「原子」的基本概念,

正如我們先前所看到的,這並不容易。為了確保依序保持一致,我們也必須避免重新排序作業,並確保其他程序能以一致的順序向其他程序顯示記憶體作業。事實上,Android 支援的硬體會自動執行後者,但前提是我們必須謹慎選擇執行前者,因此在本範例中,我們基本上會忽略後者。

記憶體作業的順序會防止編譯器重新排序,以及防止硬體重新排序。以下說明後者。

ARMv7、x86 和 MIPS 上的記憶體排序,會配合「圍欄」指示強制執行,以防止圍欄在圍欄之前指示出現指示。(這些操作說明通常又稱為「障礙」指示,但這樣可能會混淆 pthread_barrier 樣式的阻隔線,而這遠大於該指令。)圍欄指示的精確含義是一個相當複雜的主題,必須處理多種不同類型的柵欄互動的保證,以及這些資料如何與硬體提供的其他排序保證搭配使用。這只是概略的總覽,所以我們將逐步說明這些詳細資料。

最基本的排序保證是由 C++ memory_order_acquirememory_order_release 不可部分完成的作業提供:在取得負載後,應該可以看到發布儲存庫之前的記憶體作業。在 ARMv7 中,由以下程式碼強制執行:

  • 請在商店指示前方加上適當的圍欄指示。 這種做法可防止先前的所有記憶體存取動作依商店指示重新排序。(也無需使用後續商店指示來防止重新排序)。
  • 依照適當的圍欄指示執行負載指示,避免以後續存取的方式重新安排負載。(此外,至少再次提供不需要的訂購,且至少在載入前載入內容)。

統整這些優勢,就足以進行 C++ 取得/發行訂購流程。 對於 Java volatile 或 C++ 進行依序一致的 atomic,這些是必要步驟,但並不足夠。

如要瞭解其他需求,請參考我們先前稍早提到的 Dekker 演算法片段。flag1flag2 是 C++ atomic 或 Java volatile 變數,兩者的初始皆為 false。

討論串 1 討論串 2
flag1 = true
if (flag2 == false)
    critical-stuff
flag2 = true
if (flag1 == false)
    critical-stuff

依序一致性表示必須先執行給 flag「n」的指派作業,並向其他執行緒中的測試看到。因此,我們絕對不會看到這些執行緒同時執行「重要內容」。

但是,獲取新客排序所需的圍欄只會加入每個執行緒的開頭和結尾的圍欄,這並不實用。我們還需要確認,如果 volatile/atomic 商店後面跟著 volatile/atomic 載入,則系統不會重新排列兩個商店。一般而言,做法是在依序一致的存放區之前和之後新增圍欄,藉此強制執行。(這個柵欄通常會按照所有較後續的記憶體存取順序排序所有先前的記憶體存取動作),因此這項效果比必要的強度高出許多。)

我們可以改將額外圍欄與依序一致的載入建立關聯。由於商店較不常使用,我們所述的慣例在 Android 上較為常見和使用。

如前一節所述,我們需要在這兩項運算之間插入商店/載入阻隔線。在 VM 針對易變性存取執行的程式碼如下所示:

揮發性負載 揮發性商店
reg = A
fence for "acquire" (1)
fence for "release" (2)
A = reg
fence for later atomic load (3)

實際機器架構通常會提供多種類型的圍欄,這些圍欄會排序不同類型的存取作業,費用也可能會有不同。在兩者之間做出的選擇十分微小,而且必須確保以一致的順序向其他核心顯示商店,並正確組合多個圍欄組合的記憶體順序。詳情請參閱劍橋大學 (University of Cambridge) 頁面,當中會 收集原子學與實際處理器的對應關係

在某些架構 (特別是 x86) 中,「取得」和「發布」障礙並沒有必要性,因為硬體一律都會強制執行足夠的排序。因此,在 x86 中,只有最後一個圍欄 (3) 才會產生。同樣地,在 x86 上,不可部分完成的讀取-修改-寫入作業,會以隱含形式加入強大的圍欄。因此不必加上圍欄。在 ARMv7 中,我們討論的所有圍欄都屬於必要的。

ARMv8 提供 LDAR 和 STLR 指令,可直接強制執行 Java 易變性或 C++ 的依序一致的載入和商店要求。這些限制可避免上述不必要的重新排序限制。ARM 上的 64 位元 Android 程式碼會使用這些程式碼;我們選擇著重在 ARMv7 圍欄位置,因為這個位置對於實際需求的需求較多。

其他資訊

提供更深層或廣度的網頁和文件。較一般實用的文章則靠近清單頂端。

共用記憶體一致性模型:教學課程
Adve & Gharachorloo 撰寫於 1995 年,如果你想深入瞭解記憶體一致性模型,不妨從這裡著手。
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
記憶障礙
撰寫簡短摘要文章。
https://en.wikipedia.org/wiki/Memory_barrier
執行緒基本資訊
介紹 Hans Boehm 的 C++ 和 Java 多執行緒程式設計簡介。資料競爭和基本同步處理方法的討論。
http://www.hboehm.info/c++mm/threadsintro.html
實作 Java 並行
這本書於 2006 年發布,涵蓋多個主題的詳細主題。強烈建議所有使用 Java 編寫多執行緒程式碼的使用者。
http://www.javaconcurrencyinpractice.com
JSR-133 (Java 記憶體模型) 常見問題
Java 記憶體模型的簡介,包括同步程序、易變變數及最終欄位建構方式。(有點註明日期,尤其是討論其他語言的時候)。
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html
Java 記憶體模型中的程式轉換有效性
應該針對 Java 記憶體模型的其餘問題提供技術說明。這些問題並不適用於不含資料種族的計畫。
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.112.1790&rep=rep1&type=pdf
java.util.concurrent 套件總覽
java.util.concurrent 套件的說明文件。頁面底部附近有一個「記憶體一致性屬性」部分,其中說明瞭各種類別做出的保證。
java.util.concurrent 套件摘要
Java 理論和練習:使用 Java 打造安全的建築技巧
本文將詳細說明物件建構期間逸出的相關規定,並提供適用於執行緒安全的建構函式指南。
http://www.ibm.com/developerworks/java/library/j-jtp0618.html
Java 理論與練習:管理波動
這篇文章:說明 Java 中的易變欄位可以執行哪些操作,哪些功能無法完成。
http://www.ibm.com/developerworks/java/library/j-jtp06197.html
「雙重檢查鎖定功能異常」聲明
Bill Pugh 詳細說明在沒有 volatileatomic 的情況下,仔細檢查鎖定失敗的各種方式。包含 C/C++ 和 Java。
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[ARM] Barrier Litmus 測試和教戰手冊
討論 ARM SMP 的問題,透過簡短的 ARM 程式碼片段。如果您發現本頁面的例子不夠具體,或想要閱讀 DMB 指示的正式說明,請閱讀以下內容。同時也說明可執行程式碼的記憶體障礙使用指示 (如果您是即時產生程式碼,可能就很適合使用)。請注意,這個先前版本為 ARMv8,後者也支援額外的記憶體排序指示,並移至較強的記憶體模型。詳情請參閱「ARMv8-A 架構設定檔的 ARM® 架構參考資料手冊」一文 (ARMv8-A 架構設定檔)。
http://infocenter.arm.com/help/topic/com.arm.doc.genc007826/Barrier_Litmus_Tests_and_Cookbook_A08.pdf
Linux 核心記憶體障礙
Linux kernel 記憶體障礙的說明文件。當中包含一些實用的範例和 ASCII 圖片。
http://www.kernel.org/doc/Documentation/memory-barriers.txt
ISO/IEC JTC1 SC22 WG21 (C++ 標準) 14882 (C++ 程式設計語言)、第 1.10 節和第 29 節 (「原子作業程式庫」)
C++ 完整作業功能的草擬標準。此版本接近 C++14 標準,其中包含 C++11 對這個區域的微幅變更。
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
(簡介:http://www.hpl.hp.com/tech08-pdf)
ISO/IEC JTC1 SC22 WG14 (C 標準) 9899 (C 程式設計語言) 第 7.16 章 (「Atomics <stdatomic.h>」)
ISO/IEC 9899-201x C 原子作業功能的草案標準。詳情請參閱後續的瑕疵報告。
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
C/C++11 與處理器的對應關係 (劍橋大學)
Jaroslav Sevcik 和 Peter Sewell 將 C++ 原子學翻譯成各種常見的處理器指令集。
http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
Dekker 的演算法
「並行程式設計中共同排除問題的已知正確解決方案」。維基百科文章是完整演算法,其中探討如何更新,以便配合現代化的最佳化編譯器和 SMP 硬體。
https://en.wikipedia.org/wiki/Dekker's_algorithm
ARM 與 Alpha 版的註解,並解決依附元件
來自 Catalin Marinas 的 arm-kernel 郵寄清單電子郵件。包含地址和控制依附元件的完整摘要。
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html
每位程式設計師的記憶須知
這篇長篇詳盡的文章由 Ulrich Drepper 說明不同記憶體類型,尤其是 CPU 快取。
http://www.akkadia.org/drepper/cpumemory.pdf
原因:ARM 記憶體模型不一致的原因
本白皮書是由 ARM, Ltd 的 Chong & Ishtiaq 所撰寫,旨在以審慎且易於存取的方式描述 ARM SMP 記憶體模型。本文以「觀測能力」的定義出自本文。再次提醒,此為 ARMv8 之前的 ARMv8。
http://portal.acm.org/ft_gateway.cfm?id=1353528&type=pdf&coll&dl&CFID=96099715&CFTOKEN=57505711
編譯器寫入工具的 JSR-133 教戰手冊
Doug Lea 將其寫成 JSR-133 (Java 記憶體模型) 說明文件。其中包含許多編譯器寫入者使用的 Java 記憶體模型初始實作指南,不過仍會受到廣泛引用,且可能會提供深入分析資訊。遺憾的是,此處討論的四個圍欄變數並不適用於 Android 支援的架構,而上述 C++11 對應現在是更準確的食譜來源,即使是 Java 也不例外。
http://g.oswego.edu/dl/jmm/cookbook.html
x86-TSO:優質程式設計師的 x86 多處理器模型
x86 記憶體模型的精確說明。深入瞭解 ARM 記憶體模型的詳盡說明更加複雜。
http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf