潛在的讀者/作家競爭條件僞代碼

我正在分析以下僞代碼的競爭條件（一些自我實踐），並看看可能性在哪裏。僞代碼描述了一個模糊的異步讀寫器。潛在的讀者/作家競爭條件僞代碼

寫線程

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

潛在的讀者/作家競爭條件僞代碼

回答

相關問題