实现竞争线程临界区互斥所需的最低硬件支持是什么

当多个线程共享公共数据时，为避免数据修改过程中产生竞态条件，必须实现互斥机制。若硬件支持原子test-and-set指令，即可落地这类互斥方案。

但我们能否采用更精简的硬件支撑？仅具备原子读操作与原子写操作时，是否能够实现互斥？Dekker's algorithm与Peterson's algorithm就是典型的可在仅存在原子读、原子写操作的条件下，实现2个进程间互斥的算法。

Peterson's algorithm可扩展支持N个进程，对应的算法实现如下：

lock(for Process i):

/* repeat for all partners */
for (count = 0; count < (NUMPROCS-1); count++) {
    flags[i] = count;                 // I think I'm in position "count" in the queue
    turn[count] = i;                  // and I'm the most recent process to think I'm in position "count"

    "wait until                       // wait until
     (for all k != i, flags[k]<count) // everyone thinks they're behind me 
     or (turn[count] != i)"           // or someone later than me thinks they're in position "count"

                                      // now I can update my estimated position to "count"+1 

 }                                    // now I'm at the head of the queue so I can start my critical section          


Unlock (for Process i):

/* tell everyone we are finished */
flags[i] = -1;                        // I'm not in the queue anymore

经分析，该算法仅需原子读与原子写操作支持，但上述算法仅适用于进程总数N已知的场景，无法扩展至N动态变化的场景——因为该场景下并发数组的插入与分配操作本身就需要互斥保护。

待解答问题 #

基于上述前提，提出如下技术问询：

• 在无test-and-set指令的抢占式多核环境中，是否存在已知算法可实现动态N个线程间的互斥？
• 若取消无饥饿的要求，是否能够实现该场景下的互斥？
• 抑或已有结论证明，无原子test-and-set指令就无法实现该场景下的互斥？

本问题默认假设采用顺序一致性内存模型，若该假设并非必要条件也可予以说明。所有硬件都可通过一定方式编写满足顺序一致性要求的程序。

结论与说明 #

• 不存在仅依赖原子读、原子写操作就能实现动态N线程互斥的算法，即便取消无饥饿要求也无法实现。
  这是异步共享内存并发模型中的已证明结论：仅支持原子读写的共享寄存器，无法在参与进程总数无界、动态变化的场景下实现互斥。其核心矛盾在于：动态增减线程时，首先需要维护一份共享的参与线程列表，而对这份列表的并发修改本身就需要互斥保护，形成了“实现互斥需要先有互斥”的循环依赖，仅靠原子读写无法打破这个循环。
• 上述可支持固定N进程的扩展Peterson算法，本质是提前预分配了固定长度的共享状态数组（flags、turn），绕开了动态调整共享结构的问题，因此只适用于进程总数提前已知的场景，无法直接套用到动态N的场景中。
• 顺序一致性假设不会改变上述结论。哪怕硬件提供严格的顺序一致性内存模型，只要不提供读-改-写类原子原语（比如test-and-set、compare-and-swap、fetch-and-add等），就不可能实现动态N线程的互斥。日常开发中用到的支持任意线程数的各类锁实现，底层都必然依赖至少一种读-改-写原子指令，不存在纯原子读写的实现方案。

内容的提问来源于stack exchange，提问作者Sourav Kannantha B