读/写器伪代码中竞争条件的可能性
我正在分析以下关于竞争条件的伪代码(一些自我练习)并查看可能性的位置。 伪代码描述了一个模糊的异步读写器。
作家线程
r = 0; w = 1; l = 2; //assign start slot numbers while(1) { write_slot(w); l = w; //last written slot is ww = not(r,l) //assigns next slot so that w is neither r or l }
读者主题
while(1) { r = l; //read from latest write read(r); }
到目前为止我发现的腐败/竞争条件的可能性是,如果变量读/写不是primefaces的,那么,例如,当读者读到它时,作者可以改变l
的值(可能导致通过撕裂读/写的无意义的r
值)。 是否有任何竞争条件可能导致读者和作者试图访问同一个插槽?
基本问题是即使变量赋值也不是primefaces操作。 困难在于您的伪代码将如何在硬件中执行。 大多数计算机使用“加载/存储”架构,其中来自存储器的值必须在移动到另一个存储器位置之前移动到寄存器(即,没有直接的存储器到存储器操作)。 这引入了一个中间状态(寄存器),它可能在诸如此类的multithreading情况下混淆。
我假设您将r
, w
和l
作为内存中的变量实现,这两个线程都可以看到。 全局和堆内存在同一进程的线程之间共享,因此这部分很容易。 但是,线程必须有自己的堆栈和寄存器状态,否则它们就无法工作。
一个赋值,如读者的行r = l;
首先将一个值从某个存储器位置(存储l
位置)加载到寄存器中,然后将该值存储到存储器(存储r
地方)。 所以赋值r = l
就像“伪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)
是存储addr(l)
的存储器地址, addr(r)
是addr(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 )和用于实现互斥的操作系统function(如挂起线程执行)。 通常,您会使用某些库为您执行同步,而不是尝试编写自己的技术。 例如,请参阅C的POSIX线程库的pthread_mutex_lock()和pthread_mutex_unlock()。