Должен сказать, это поразило меня как очень умная идея, и я думал об этом пока , прежде чем начал понимать, где (я думаю ) ошибка здесь. Так что, с одной стороны, спасибо за такой умный дизайн! Но, в то же время, позор вам за демонстрацию " закона Кернигана ":
Отладка в два раза сложнее, чем писать код в первую очередь. Поэтому, если вы пишете код настолько умно, насколько это возможно, вы, по определению, недостаточно умны для его отладки.
В основном проблема заключается в следующем: вы предполагаете, что WaitOne и Release эффективно вызывают сериализацию всех ваших операций Enqueue и Dequeue; но это не совсем то, что здесь происходит. Помните, что класс Semaphore используется для ограничения количества потоков, обращающихся к ресурсу , , а не для обеспечения определенного порядка событий. То, что происходит между каждый WaitOne и Release, не обязательно происходит в том же «порядке потоков», что и сами WaitOne и Release.
Это сложно объяснить словами, поэтому позвольте мне привести наглядную иллюстрацию.
Допустим, ваша очередь имеет емкость 8 и выглядит следующим образом (пусть 0 представляет null и x представляют объект):
[ x x x x x x x x ]
Итак, Enqueue был вызван 8 раз, и очередь заполнена. Поэтому ваш _writeSema семафор заблокируется на WaitOne, а ваш _readSema семафор немедленно вернется на WaitOne.
Теперь давайте предположим, что Dequeue вызывается более или менее одновременно в 3 разных потоках. Давайте назовем их T1, T2 и T3.
Прежде чем продолжить, позвольте мне применить некоторые метки к вашей реализации Dequeue, для справки:
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;
}
Хорошо, значит, T1, T2 и T3 все прошли точку A . Затем для простоты предположим, что каждая из них достигает линии B «по порядку», так что у T1 index равно 0, у T2 index равно 1, а у T3 index равно 2 .
Пока все хорошо. Но вот что надо: нет никакой гарантии, что отсюда T1, T2 и T3 попадут в линию D в любом указанном порядке . Предположим, что T3 на самом деле получает впереди T1 и T2, перемещаясь за линию C (и таким образом устанавливая _array[2] в null) и вплоть до линии D .
После этого будет сигнализироваться _writeSema, что означает, что в вашей очереди есть один слот для записи, верно? Но ваша очередь теперь выглядит так!
[ x x 0 x x x x x ]
Таким образом, если в то же время появился другой поток с вызовом Enqueue, он на самом деле получит мимо _writeSema.WaitOne, увеличит _head и получит index из 0, хотя слот 0 не пуст . Результатом этого будет то, что элемент в слоте 0 может быть на самом деле перезаписан до того, как T1 (помните его?) Прочитает его.
Чтобы понять, откуда берутся ваши значения null, вам нужно лишь визуализировать обратную сторону процесса, который я только что описал. То есть предположим, что ваша очередь выглядит так:
[ 0 0 0 0 0 0 0 0 ]
Три потока, T1, T2 и T3, все вызывают Enqueue почти одновременно. T3 увеличивает _head last , но вставляет свой элемент (в _array[2]) и вызывает _readSema.Release first , в результате чего сигнализируется _readSema, но очередь выглядит как:
[ 0 0 x 0 0 0 0 0 ]
Так что, если в это же время появился другой поток с вызовом Dequeue (до того, как T1 и T2 закончат свою работу), он пройдет _readSema.WaitOne, увеличит _tail и получит index из 0, , хотя слот 0 является пустым .
Итак, вот ваша проблема . Что касается решения , у меня сейчас нет никаких предложений. Дайте мне немного времени подумать ... (Я отправляю этот ответ сейчас, потому что он свеж в моей памяти, и я чувствую, что он может вам помочь.)