代码之家 › 专栏 › 技术社区 › davidhood2

读取器/写入器伪码中存在竞争条件的可能性

pseudocode race-condition asynchronous multithreading c

davidhood2 · 技术社区 · 9 年前

我正在分析以下关于比赛条件的伪代码(有点自我练习),并看看可能性在哪里。伪代码描述了一个模糊的异步读写器。

编写器线程

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
}

读卡器线程

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

到目前为止,我发现的损坏/竞争条件的可能性是,如果变量读/写不是原子的,因此,例如,编写器可以更改 l 当读者读到一半时(可能会产生一个无意义的值 r 通过撕裂的读/写)。但是,是否存在可能导致读写器试图访问同一插槽的竞争条件?

1 回复 | 直到 9 年前

e0k 9 年前

根本问题是,即使变量赋值也不是原子操作。困难在于如何在硬件中执行伪代码。大多数计算机使用“加载/存储”架构,其中来自内存的值必须在移动到另一个内存位置之前移动到寄存器中(即没有直接的内存到内存操作)。这引入了一个中间状态(寄存器),在这样的多线程情况下,它可能会把事情搞混。

我假设你会实施 r , w 和 l 作为变量 在存储器中 这对两个线程都是可见的。全局和堆内存在同一进程的线程之间共享,因此这一部分很容易。然而,线程必须有自己的堆栈和寄存器状态,否则它们将无法工作。

诸如读者行之类的作业 r = l; 将首先从某个内存位置(无论何处 我 存储)到寄存器中,然后将该值存储到存储器中 r 存储)。所以任务 r = l 类似于“伪组件”:

    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) 是任何位置的内存地址 我 存储,并且 addr(r) 是的地址 r .

在您的情况下,问题是一个线程(例如,读取器)的寄存器可能在另一个线程修改内存时保持中间值。当从寄存器存储到内存时,第一个线程(读取器)将覆盖该内存。

考虑以下事件序列。符号 [writer] 和 [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

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

解决此类问题的一种方法是强制执行 相互排斥 :通过让其他线程等待来确保某段代码不中断。有特殊的硬件指令(如“比较和交换” CMPXCHG )以及用于实现互斥的操作系统特性(如挂起线程执行)。通常,您会使用一些库来为您进行同步,而不会尝试编写自己的技术。例如,请参见 pthread_mutex_lock() 和C的POSIX线程库的pthread_mutex_unlock()。