潜力在读/写假code竞态条件 [英] Potential for Race Conditions in Reader/Writer Pseudocode

问题描述

我分析了竞争条件下的伪$ ​​C $ C（有点自我练习），并在寻找的可能性在哪里。伪code介绍一个模糊的异步读/写器。

写线程的

  R = 0; W = 1; L = 2; //指定起始时隙号
而（1）{
  write_slot（重量）;
  L =瓦; //最后写入插槽为w
  W =不（R，L）//分配下一时隙以便w是既不R或L
}
 

读线程的

 而（1）{
 R = l;和//从最新的写读
 读（r）;
}
 

我发现的腐败/竞争条件的可能性，到目前为止是，如果变量的读/写操作不是原子等，例如，笔者可以改变 L值，而读者是中途读它（可能导致通过撕破读/写研究的无意义值）。
是否有任何竞争条件但是，这种可能会导致这两个读写器试图访问同一插槽？

解决方案

最根本的问题是，即使变量赋值不是一个原子操作。困难的是如何在你的伪code将在硬件上执行。大多数计算机使用一个装入/存储体系结构，其中从存储器中的值必须被移动到另一存储位置之前（即，不存在直接存储器到存储器操作）被移动到寄存器中。这引入一​​个中间状态（寄存器），可以像这样在多线程情况下可能混为一谈。

我假设你将实施研究，是W 和→作为变量的内存的这将是两个线程可见。全局和堆内存在同一进程的线程之间共享，所以这部分很简单。但是，线程必须有自己的堆栈和寄存器状态，否则他们就不会工作。

这是任务，如读者的行 R =升; 将首先从一些内存位置加载一个值（无论→存储）到一个寄存器中，那么这个值存储到内存中（无论是存储研究）。因此，分配 R =→会是这样的伪集结号：

 负载R1，地址（L）;负载L从内存到寄存器r1
    存储地址（R），r1为店内寄存器r1到哪里r为保持
 

其中， R1 一些寄存器，地址（L）是哪里→存储和地址（R）是研究。<地址/ p>

你的情况的问题是，一个线程的寄存器（例如，读取器）能保持的中间值，而另一个线程（作家）修改存储器。然后第一个线程（读者）将在寄存器中存储到内存时覆盖此内存。

考虑以下事件序列。记号 [作家] 和 [阅读] 指定线程正在做什么。读者的分配 R =→给出上述装配操作，为此笔者在两者之间进行繁琐的操作：

  [作家] R = 0; W = 1; L = 2; //（考虑启动条件）
    [作家] write_slot（W）//W¯¯== 1
    [阅读]负载R1，地址（L）//负载L（值2）到寄存器r1
    [作家] L =瓦; //升获得W，这是1
    [作家] W =不（R，L）//由于r *在存储器*仍为0，
                                //和L在存储器是1，
                                //这个挑选2瓦特
    [阅读]店地址（R），R1 //门店2至R *内存*
    [读卡器]读（r）//读取（2）由于r == 2
    [作家] write_slot（w）的//写入（2）由于瓦特== 2
 

然后将最后两个操作可能发生在平行，因此它们将尝试在同一时间访问相同的槽。所以回答你的问题是肯定的，它可能发生。

解决像这样的一种方法是强制执行的互斥的：确保code的一些片段是通过使其他线程等待中断。有特殊的硬件指令（如比较和放大器;交流 CMPXCHG ）和操作系统功能（如挂起线程执行），用来实现互斥。通常情况下，你会使用一些库来为你做同步，而不是试图编写自己的技术。例如，请参见 pthread_mutex_lock（）的和C的POSIX线程库的调用pthread_mutex_unlock（）

I'm analysing the following pseudocode for race conditions (a bit of self practise) and looking at where the possibilities are. The pseudocode describes a vague asynchronous reader/writer.

Writer Thread

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 Thread

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

The possibilities of corruption/race conditions I've found so far are if the variables read/writes are not atomic and so, for example, the writer could change the value of l whilst the reader is halfway through reading it (could lead to a nonsensical value of r through torn read/write). Is there any race conditions however that could potentially lead to both the reader and writer attempting to access the same slot?

解决方案

The fundamental problem is that even variable assignment is not an atomic operation. The difficulty is in how your pseudocode would be executed in hardware. Most computers use a "load/store" architecture where values from memory must be moved to a register before being moved to another memory location (i.e. there are no direct memory-to-memory operations). This introduces an intermediate state (the register) that could possibly mix things up in a multi-threaded situation such as this.

I'm assuming that you would implement r, w, and l as variables in memory that would be visible to both threads. Globals and heap memory are shared between threads of the same process, so this part is easy. However, threads must have their own stack and register states, otherwise they just wouldn't work.

An assignment such as the reader's line r = l; would first load a value from some memory location (wherever l is stored) into a register, then store this value to memory (wherever r is stored). So the assignment r = l would be something like the "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

where r1 is some register, addr(l) is the memory address of wherever l is stored, and addr(r) is the address of r.

The problem in your case is that the register of one thread (say, the reader) could keep an intermediate value while another thread (writer) modifies memory. The first thread (the reader) would then overwrite this memory when storing from register to memory.

Consider the following sequence of events. The notation [writer] and [reader] specify which thread is doing what. The reader's assignment r = l is given as the above assembly operations, for which the writer performs troublesome operations in between:

    [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

The last two operations could then occur in parallel and so they would be attempting to access the same slot at the same time. So the answer to your question is yes, it could happen.

One way to fix something like this is to enforce mutual exclusion: ensuring that some segment of code is uninterrupted by making other threads wait. There are special hardware instructions (like "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() and pthread_mutex_unlock() of the POSIX thread library for C.

这篇关于潜力在读/写假code竞态条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！