StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I must say, this struck me as a <em>very</em> clever idea, and I thought about it for a <em>while</em> before I started to realize where (I <em>think</em>) the bug is here. So, on one hand, kudos on coming up with such a clever design! But, at the same time, <strong>shame on you</strong> for demonstrating "<a href="http://en.wikipedia.org/wiki/Kernighan" rel="noreferrer">Kernighan's</a> Law":</p> <blockquote> <p>Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.</p> </blockquote> <p>The issue is basically this: you are assuming that the <code>WaitOne</code> and <code>Release</code> calls effectively <em>serialize</em> all of your <code>Enqueue</code> and <code>Dequeue</code> operations; but that isn't quite what is going on here. Remember that the <code>Semaphore</code> class is used to <em>restrict the number of threads accessing a resource</em>, <strong>not</strong> to ensure a particular order of events. What happens <em>between</em> each <code>WaitOne</code> and <code>Release</code> is not guaranteed to occur in the same "thread-order" as the <code>WaitOne</code> and <code>Release</code> calls themselves.</p> <p>This is tricky to explain in words, so let me try to provide a visual illustration.</p> <p>Let's say your queue has a capacity of 8 and looks like this (let <code>0</code> represent <code>null</code> and <code>x</code> represent an object):</p> <pre> [ x x x x x x x x ] </pre> <p>So <code>Enqueue</code> has been called 8 times and the queue is full. Therefore your <code>_writeSema</code> semaphore will block on <code>WaitOne</code>, and your <code>_readSema</code> semaphore will return immediately on <code>WaitOne</code>.</p> <p>Now let's suppose <code>Dequeue</code> is called more or less concurrently on 3 different threads. Let's call these T1, T2, and T3.</p> <p>Before proceeding let me apply some labels to your <code>Dequeue</code> implementation, for reference:</p> <pre><code>public T Dequeue() { _readSema.WaitOne(); // A int index = Interlocked.Increment(ref _tail); // B index %= _capacity; if (index < 0) index += _capacity; T ret = Interlocked.Exchange(ref _array[index], null); // C Interlocked.Decrement(ref _count); _writeSema.Release(); // D return ret; } </code></pre> <p>OK, so T1, T2, and T3 have all gotten past point <strong>A</strong>. Then for simplicity let's suppose they each reach line <strong>B</strong> "in order", so that T1 has an <code>index</code> of 0, T2 has an <code>index</code> of 1, and T3 has an <code>index</code> of 2.</p> <p>So far so good. But here's the gotcha: <em>there is no guarantee that from here, T1, T2, and T3 are going to get to line <strong>D</strong> in any specified order</em>. Suppose T3 actually gets <em>ahead</em> of T1 and T2, moving past line <strong>C</strong> (and thus setting <code>_array[2]</code> to <code>null</code>) and all the way to line <strong>D</strong>.</p> <p>After this point, <code>_writeSema</code> will be signaled, meaning you have one slot available in your queue to write to, right? <strong>But your queue now looks like this!</strong></p> <pre> [ x x 0 x x x x x ] </pre> <p>So if another thread has come along in the meantime with a call to <code>Enqueue</code>, it will actually get <em>past</em> <code>_writeSema.WaitOne</code>, increment <code>_head</code>, and get an <code>index</code> of 0, <strong>even though slot 0 is not empty</strong>. The result of this will be that the item in slot 0 could actually be <em>overwritten</em>, before T1 (remember him?) reads it.</p> <p>To understand where your <code>null</code> values are coming from, you need only to visualize the reverse of the process I just described. That is, suppose your queue looks like this:</p> <pre> [ 0 0 0 0 0 0 0 0 ] </pre> <p>Three threads, T1, T2, and T3, all call <code>Enqueue</code> nearly simultaneously. T3 increments <code>_head</code> <em>last</em> but inserts its item (at <code>_array[2]</code>) and calls <code>_readSema.Release</code> <em>first</em>, resulting in a signaled <code>_readSema</code> but a queue looking like:</p> <pre> [ 0 0 x 0 0 0 0 0 ] </pre> <p>So if another thread has come along in the meantime with a call to <code>Dequeue</code> (before T1 and T2 are finished doing their thing), it will get past <code>_readSema.WaitOne</code>, increment <code>_tail</code>, and get an <code>index</code> of 0, <strong>even though slot 0 <em>is</em> empty</strong>.</p> <p>So there's your <em>problem</em>. As for a <em>solution</em>, I don't have any suggestions at the moment. Give me some time to think it over... (I'm posting this answer now because it's fresh in my mind and I feel it might help you.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload