潜在的读者/作家竞争条件伪代码

我正在分析以下伪代码的竞争条件（一些自我实践），并看看可能性在哪里。伪代码描述了一个模糊的异步读写器。潜在的读者/作家竞争条件伪代码

写线程

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); 
}

我发现的腐败/竞态条件的可能性，到目前为止是如果变量读/写不是原子的，所以，例如，作者可以改变的值，而读取器读取一半（可能导致通过撕裂读/写的r的荒谬值）。但是，是否有任何竞争条件可能导致读写器试图访问同一个插槽？

来源

2016-01-21 davidhood2

如果这是伪代码，为什么使用[c]标记（http://stackoverflow.com/questions/tagged/ c）标签？ – unwind

write_slot（n）中的n是什么？ –

因为我已经使用了基于C的语法，因为那是我从 – davidhood2

基本问题是即使变量赋值也不是原子操作。难点在于你的伪代码如何在硬件中执行。大多数计算机使用“加载/存储”体系结构，其中来自存储器的值在被移动到另一个存储器位置（即，没有直接的存储器到存储器操作）之前必须被移动到寄存器。这引入了一个中间状态（寄存器），可能会在诸如此类的多线程情况下混合使用。

我假设你会实现r，w，并l作为变量内存这将是两个线程可见。全局和堆内存由同一进程的线程共享，因此这部分很容易。但是，线程必须具有自己的堆栈和寄存器状态，否则它们就无法工作。

赋值如读者的线r = l;将首先从某些存储位置（无论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)是哪里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()和pthread_mutex_unlock（）用于C的POSIX线程库。

来源

2016-01-21 18:55:47 e0k

潜在的读者/作家竞争条件伪代码

回答

相关问题