并行程序设计: 执行顺序

多執行緒環境下，程式會出問題，往往在於執行順序的不確定性。一旦顧及分散式系統 (distributed systems)，執行順序和衍生的時序 (timing) 問題更加複雜。

我們將從如何定義程式執行的順序開始說起，為了簡單起見，我們先從單執行緒的觀點來看執行順序這件事，其中最關鍵知識就是 Sequenced-before，你將會發現就連單執行緒的程式，也可能會產生不確定的執行順序。

• 原文地址

Evaluation

所謂求值 (Evaluation)，其實指二件事情，一是 value computations，對一串運算式計算的結果；另一是 side effect，亦即修改物件狀態，像是修改記憶體內變數的值、呼叫函式庫的 I/O 處理函式之類的操作。

Sequenced-before

sequenced-before 是種對 同一個執行緒 下，求值順序關係的描述。

• 若 A is sequenced-before B，代表 A 的求值會先完成，才進行對 B 的求值
• 若 A is not sequenced before B 而且 B is sequenced before A，代表 B 的求值會先完成，才開始對 A 的求值。
• 若 A is not sequenced before B 而且 B is not sequenced before A，代表兩種可能，一種是順序不定，甚至這兩者的求值過程可能會重疊（因為 CPU 重排指令交錯的關係）或不重疊。

而程式語言的工作，就是定義一連串關於 sequenced-before 的規範，舉例來說： 以下提到的先於、先進行之類的用詞，全部的意思都是 sequenced-before，也就是「先完成之後才開始進行」

• i++ 這類的後置運算子，value computation 會先於 side effect
• 對於 assignment operator 而言 (=, +=, -= 一類)，會先進行運算元的 value computation，之後才是 assignment 的 side effect，最後是整個 assignment expression 的 value computation。

虽然规格书定义了关于 sequenced-before 的规范，但不可能面面俱到，还是存在有些执行顺序是未定义的，例如 f1() + f2() + f3()，规格书只规定了 + 操作是在对 f1(), f2(), f3() 求值之后进行的，但是对于求值时的 f1() 这类函数呼叫，并没有规定哪个函数先进行调用求值，所以在求值时第一个调用的可能是 f1() 或 f2() 或 f3()。

sequenced-before 的规范缺失导致了 partial order 场景的出现，二这可能会导致未定义行为，例如经典的头脑体操 i = i++：

出现这个未定义行为的原因是，i++ 的 side effect 与 = 之间不存在 sequenced-bofore 关系 (因为 partial order)，而这会导致该语句的执行结果是不确定的 (没想到吧，单线程的程序你也有可能不确定执行顺序 🤣)

• C++ sequenced-before graphs
• Order of evaluation from cppreference
• What are sequence points, and how do they relate to undefined behavior?

Happens-before

短片:

• Happened Before Relationship
• Happened Before Relation (cont)

从上图可以看出 happens-before 其实就是在 sequenced-before 基础上增加了多执行绪 communication 情形，可以理解为 happens-before 将 sequenced-before 扩大到涵盖多执行绪的情形了，即执行顺序有先后次序 (执行顺序其实不太准确，执行结果显现 的先后次序更加准确 🤣)

图中的 concurrent events 其实就是多执行绪下没有先后次序的情形

Java 规格书 17.4.5. Happens-before Order 也能佐证我们的观点:

If one action happens-before another, then the first is visible to and ordered before the second.

C11 正式将并行和 memory order 相关的规范引入到语言的标准:

• 5.1.2.4 Multi-threaded executions and data races

All modifications to a particular atomic object M occur in some particular total order, called the modification order of M. If A and B are modifications of an atomic object M, and A happens before B, then A shall precede B in the modification order of M, which is defined below.

cppreference std::memory_order

Regardless of threads, evaluation A happens-before evaluation B if any of the following is true:

1. A is sequenced-before B
2. A inter-thread happens before B

在多执行绪情况下，如果没法确保 happens-before 关系，程序往往会产生意料之外的结果，例如:

1

int counter = 0;

如果现在有两个执行绪在同时执行，执行绪 A 执行 counter++，执行绪 B 将 counter 的值打印出来。因为 A 和 B 两个执行绪不具备 happens-before 关系，没有保证 counter++ 后的效果对打印 counter 是可见的，导致打印出来的可能是 1 也可能是 0，这个也就是图中的 concurrent events 关系。

The Happens-Before Relation

• The Happens-Before Relation

Let A and B represent operations performed by a multithreaded process. If A happens-before B, then the memory effects of A effectively become visible to the thread performing B before B is performed.

No matter which programming language you use, they all have one thing in common: If operations A and B are performed by the same thread, and A’s statement comes before B’s statement in program order, then A happens-before B.

Happens-Before Does Not Imply Happening Before

In this case, though, the store to A doesn’t actually influence the store to B. (2) still behaves the same as it would have even if the effects of (1) had been visible, which is effectively the same as (1)’s effects being visible. Therefore, this doesn’t count as a violation of the happens-before rule.

Happening Before Does Not Imply Happens-Before

The happens-before relationship only exists where the language standards say it exists. And since these are plain loads and stores, the C++11 standard has no rule which introduces a happens-before relation between (2) and (3), even when (3) reads the value written by (2).

这里说的 happens-before 关系必须要在语言标准中有规定的才算，单执行绪的情况自然在标准内，多执行绪的情况，标准一般会制定相关的同步原语之间的 happens-before 关系，例如对 mutex 的连续两个操作必然是 happens-before 关系，更多的例子见后面的 synchronized-with 部分。

Synchronized-with

从 Java 切入

• synchronized 关键字

• volatile 关键字

• thread create/join

C++ 的观点

The library defines a number of atomic operations and operations on mutexes that are specially identified as synchronization operations. These operations play a special role in making assignments in one thread visible to another.

又是 visible 说明强调的还是 happens-before 这一关系 🤣

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>       // std::cout
#include <thread>         // std::thread
#include <mutex>          // std::mutex

std::mutex mtx;           // mutex for critical section
int count = 0;

void print_thread_id (int id) {
    // critical section (exclusive access to std::cout signaled by locking mtx):
    mtx.lock();
    std::cout << "thread #" << id  << "  count:" << count << '\n';
    count++;
    mtx.unlock();
}
int main () {
    std::thread threads[10];
    // spawn 10 threads:
    for (int i=0; i<10; ++i)
        threads[i] = std::thread(print_thread_id,i+1);
    for (auto& th : threads) th.join();
    return 0;
}

这段程序里每个执行的 thread 之间都是 happens-before / synchronized-with 关系，因为它们的执行体都被 mutex 包裹了，而对 mutex 的操作是 happens-before 关系的。如果没有使用 mutex，那么 thread 之间不存在 happens-before 关系，打印出来的内容也是乱七八糟的。

• cppreference std::mutex
• cplusplus std::mutex::lock

深入 Synchronizes-with

• The Synchronizes-With Relation

Memory Consistency Models

這樣的幻象要成立，在於程式設計師和該系統（硬體、編譯器等產生、執行程式的平台）達成一致的協定，系統保證程式設計師只要照著規則走，程式執行結果會是正確的。

但什樣叫做正確？正確的意思不是保證只會發生一種執行結果，而是定義在所有可能發生的執行結果中，哪些是允許的。我們把這樣的約定稱為 Memory Consistency Models，系統要想辦法在保證正確的情況下，盡可能的最佳化，讓程式跑的又快又好。

程序效能提高的代价是写程序变得困难，因为需要遵守上面所谓的规则

Sequential Consistency

• Leslie Lamport

A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

1. 对于每个独立的处理单元，执行时都维持程序的顺序 (Program Order)
2. 整个程序以某种顺序在所有处理器上执行

Lamport 的定義相當洗鍊：第一點言明程式在處理器內會照順序執行，第二點則說所有處理器會以某種順序執行程式。看似平實的話語，但真實世界卻可能不是這樣。

Weak Memory Model vs. Strong Memory Model