Кто-то может помочь определить ошибки в моем низком списке блокировки?
Если Вам будет интересно более подробно о том, как кластер Google работает, я предложу эту реализацию с открытым исходным кодом их HDFS.
Это основано Mapreduce Google.
4 ответа
Вы не синхронизируете доступ к элементу заголовка списка. Это плохо по крайней мере на двух уровнях:
присвоение значений заголовку списка может быть не таким атомарным, как вы думаете. Это означает, что несинхронизированная операция чтения потенциально может получить поврежденное значение.
Другая, более вероятная проблема заключается в том, что если ваш блок имеет несколько ядер, каждое из них может иметь в кэше процессора свою собственную копию значения. Чтобы они синхронизировали значения, вам нужен барьер памяти
As you discovered, lock free programming is very difficult to get right.
Windows already has support for lock-free singly linked lists,http://msdn.microsoft.com/en-us/library/ms684121(VS.85).aspx, you should try using that rather than roll your own.
The most obvious error is the name you've given it. Regardless of the fact that you've implemented it as a linked list, what you've implemented is a stack.
Consider what would happen in the following sequence of events when there are two items, A and B, in the list (stack really) like head -> A -> B, count is 2:
- Thread 1 starts the
pop()call but gets preempted right before_InterlockedCompareExchange64() - Thread 2 removes both items, A and B, from the stack and then puts two new items back onto the stack and the top item happens to be allocated at the same address as A, so we have, say
head -> A -> D. Note that thecountis back to 2 - Thread 1 resumes and successfully performs the CAS (
_InterlockedCompareExchange64()). Nowheadpoints to B, which was deallocated (bad) and D is lost (bad).
Это классическая проблема ABA . Вы должны использовать второе слово в качестве номера поколения вместо количества элементов, то есть никогда не уменьшайте его.
В списке рассылки ведется обсуждение экспериментальной библиотеки boost :: lockfree .
Также обратите внимание на очередь Херба Саттера без блокировок - это другой подход, при котором фиктивный узел не дает производителю и потребителю наступать друг на друга.