Я провел сегодня, глядя в безблокировочные очереди. У меня есть несколько производителей, несколько потребителей ситуации. Для тестирования я реализовал систему, использующую Interlocked SList, под Win32, и она удвоила производительность моего многопоточного кода на основе задач. К сожалению, я хочу поддерживать несколько платформ. Блокировка на нескольких платформах сама по себе не является проблемой, и я могу с уверенностью предположить, что могу блокировать без проблем. Однако фактическая реализация теряет меня.

Большая проблема заключается в том, что вам нужно гарантировать, что push / pop для списка будет использовать только один блокированный вызов. В противном случае вы оставляете место для другой нити, чтобы затянуть и облажаться. Я не уверен, как реализация Microsoft работает скрытно и хотел бы узнать больше.

Может ли кто-нибудь указать мне на полезную информацию (платформа и язык довольно нерелевантны)?

Кроме того, я хотел бы знать, возможно ли реализовать вектор без блокировки. Это было бы очень полезно для меня :) Ура!

Изменить: После прочтения статьи DDJ травы я вижу уменьшенную очередь блокировки, которая очень похожа на ту, что у меня уже была. Тем не менее, я заметил, что в конце есть бумаги, которые могут создать настоящую очередь без блокировки, используя операцию двойного сравнения и обмена (DCAS). Кто-нибудь реализовал очередь, используя cmpxchg8b (или cmpxchg16b в этом отношении)?

Я просто размышляю над этим (не читая статьи), но вы можете использовать эту систему для одновременного обновления указателя головы и хвоста и, таким образом, избежать проблем с другим потоком, попадающим между двумя атомарными операциями. Однако вам все еще нужно получить следующий указатель головы, чтобы проверить его относительно указателя хвоста, чтобы увидеть, изменили ли вы только что хвост. Как избежать того, чтобы другой поток изменял эту информацию, пока другой поток готовится сделать это сам? Как именно это реализовано без блокировки? Или мне лучше читать неразборчивость, которая является исследовательской работой? ;)