Очередь с несколькими потребителями без блокировки (MPSC) без блокировки - это один из самых простых алгоритмов без блокировок для реализации.
Самая базовая реализация требует простой список без блокировок с односвязными связями (SList) только с push () и flush (). Функции доступны в Windows API как InterlockedFlushSList () и InterlockedPushEntrySList (), но их очень легко выполнить самостоятельно.
Несколько элементов Push (), поступающих от производителя, на SList с использованием CAS (блокировка сравнения и обмена).
Single Consumer выполняет flush (), который меняет голову SList на NULL, используя XCHG (обмен с блокировкой). Потребитель затем имеет список предметов в обратном порядке.
Чтобы обработать элементы по порядку, вы должны просто перевернуть список, возвращенный функцией flush (), перед его обработкой. Если вас не волнует порядок, вы можете просто просмотреть список сразу, чтобы обработать его.
Две заметки, если вы катите свои собственные функции:
1) Если вы работаете в системе со слабым упорядочением памяти (например, PowerPC), вам нужно поставить «барьер освобождения памяти» в начале функции push () и «барьер памяти aquire» в конце функция flush ().
2) Вы можете значительно упростить и оптимизировать функции, потому что проблема ABA с SLists возникает во время функции pop (). Вы не можете иметь проблемы ABA с SList, если вы используете только push () и flush (). Это означает, что вы можете реализовать его как единый указатель, очень похожий на код без блокировки, и нет необходимости в счетчике последовательностей для предотвращения ABA.