求满足quiescent consistency而非sequential consistency的程序执行顺序示例

Yes, such executions do exist #

As Maurice Herlihy and Nir Shavit confirm in The Art of Multiprocessor Programming (Chapter 3), quiescent consistency and sequential consistency are independent—neither model implies the other. Below is a clear example of an execution that meets quiescent consistency but violates sequential consistency.

Example Execution #

Consider a single shared variable x initialized to 0, with two threads running the following code:

// Thread 1
x = 1;
int r1 = x;

// Thread 2
x = 2;
int r2 = x;

Suppose the execution produces the unexpected results:

• r1 = 2 (Thread 1 reads x as 2 after writing 1)
• r2 = 1 (Thread 2 reads x as 1 after writing 2)

Why This Violates Sequential Consistency #

Sequential consistency requires that there exists a global total order of all operations such that:

1. Each thread's operations follow their original program order.
2. Every read returns the value of the most recent write to that variable in the global order.

For our example, no such valid global order exists:

• If Thread 1's write to x comes before Thread 2's write, Thread 1's read must return 1 (its own write), and Thread 2's read must return 2 (the latest write). This contradicts our results.
• If Thread 2's write comes before Thread 1's write, Thread 2's read must return 2, and Thread 1's read must return 1. This also contradicts our results.

No permutation of operations can satisfy both sequential consistency rules while matching the observed results, so this execution does not meet sequential consistency.

Why This Satisfies Quiescent Consistency #

Quiescent consistency is a weaker model with two core requirements:

1. Each thread's operations preserve their original program order.
2. Operations separated by a quiescent period (a gap where no threads execute any operations) must appear in chronological order in a valid sequential interpretation.

For operations not separated by a quiescent period (like all operations in our example), quiescent consistency allows us to reorder them freely (as long as program order is maintained) to form a valid sequential execution that matches the observed results.

We can construct such an interpretation with this order:

1. Thread 2 writes x = 2
2. Thread 1 writes x = 1
3. Thread 2 reads x = 1 (matches r2 = 1)
4. Thread 1 reads x = 2 (matches r1 = 2)

This sequence respects both threads' program order (Thread 2's write comes before its read; Thread 1's write comes before its read) and produces the exact results from our execution. Since this valid sequential interpretation exists, the original execution satisfies quiescent consistency.

内容的提问来源于stack exchange，提问作者Mark B.