Reader/Writer 伪代码中潜在的竞争条件

Question

我正在分析以下针对竞争条件的伪代码（一些自我练习）并查看可能性所在。伪代码描述了一个模糊的异步 reader/writer.

作者线程

r = 0; w = 1; l = 2; //assign start slot numbers
while(1) { 
  write_slot(w);
  l = w; //last written slot is w 
  w = not(r,l) //assigns next slot so that w is neither r or l
}

Reader 话题

while(1) {
 r = l; //read from latest write
 read(r);
}

到目前为止我发现的 corruption/race 条件的可能性是变量 read/writes 不是原子的，因此，例如，作者可以更改 l 的值而 reader 正在阅读它的一半（可能会导致 r 通过撕裂 read/write 的无意义值）。但是，是否存在任何可能导致 reader 和编写器都尝试访问同一插槽的竞争条件？

Answer 1

根本的问题是即使变量赋值也不是原子操作。困难在于如何在硬件中执行您的伪代码。大多数计算机使用 "load/store" 体系结构，其中内存中的值必须先移动到寄存器，然后才能移动到另一个内存位置（即没有直接的 memory-to-memory 操作）。这引入了一个中间状态（寄存器），它可能会在 multi-threaded 这种情况下混淆。

我假设您将实现 r、w 和 l 作为变量 在内存中 两个线程。全局和堆内存在同一个进程的线程之间共享，所以这部分很简单。但是，线程必须有自己的堆栈和寄存器状态，否则它们将无法工作。

诸如 reader 行 r = l; 之类的赋值将首先从某个内存位置（存储 l 的任何位置）加载一个值到寄存器中，然后存储该值到内存（存储 r 的任何位置）。所以赋值 r = l 类似于 "pseudo-assembly":

    load   r1,addr(l)     ; load l from memory into register r1
    store  addr(r),r1     ; store register r1 to wherever r is kept

其中r1是某个寄存器，addr(l)是l所在的内存地址，addr(r)是r的地址。

你的问题是一个线程（比如 reader）的寄存器可以保持一个中间值，而另一个线程（编写器）修改内存。当从寄存器存储到内存时，第一个线程（reader）将覆盖此内存。

考虑以下事件序列。符号 [writer] 和 [reader] 指定哪个线程在做什么。 reader的赋值r = l就是上面的汇编操作，作者在这中间进行了比较麻烦的操作：

    [writer]  r=0; w=1; l=2;    // (given starting conditions)
    [writer]  write_slot(w)     // w==1
    [reader]  load r1,addr(l)   // load l (value 2) into register r1
    [writer]  l = w;            // l gets w, which is 1
    [writer]  w = not(r,l)      // since r *in memory* is still 0,
                                //   and l in memory is 1,
                                //   this picks 2 for w.
    [reader]  store addr(r),r1  // stores 2 to r *in memory*
    [reader]  read(r)           // read(2) since r==2
    [writer]  write_slot(w)     // write(2) since w==2

最后两个操作可以并行发生，因此它们将尝试同时访问同一个插槽。所以你的问题的答案是肯定的，它可能会发生。

解决此类问题的一种方法是强制执行互斥：通过让其他线程等待来确保某些代码段不被中断。有一些特殊的硬件指令（例如 POSIX 线程库的 "compare & exchange" CMPXCHG) and operating system features (like suspending thread execution) used to implement mutual exclusion. Typically you would use some library to do synchronization for you and not try to write your own technique. For example, see pthread_mutex_lock() 和 pthread_mutex_unlock()

Reader/Writer 伪代码中潜在的竞争条件

Potential for Race Conditions in Reader/Writer Pseudocode

c

multithreading

asynchronous

pseudocode

race-condition