Возможно ли использование нескольких производителей для одного потребителя в режиме без блокировки?
У меня есть несколько тем, которые много общаются друг с другом. Я бы предпочел, чтобы это было без блокировки.
Для каждого потока я хочу иметь почтовый ящик, куда другие потоки могут отправлять ему сообщения (но только владелец может удалять сообщения). Это ситуация с несколькими производителями для одного потребителя. Могу ли я сделать это в условиях без блокировки / высокой производительности? (Это во внутреннем цикле гигантской симуляции.)
4 ответа
Конечно, если у вас есть атомный CompareAndSwap инструкция:
for (i = 0; ; i = (i + 1) % MAILBOX_SIZE)
{
if ((mailbox[i].owned == false) &&
(CompareAndSwap(&mailbox[i].owned, true, false) == false))
break;
}
mailbox[i].message = message;
mailbox[i].ready = true;
После прочтения сообщения потребительский поток просто устанавливает mailbox[i].ready = false; mailbox[i].owned = false; (в этой последовательности).
Очередь с несколькими потребителями без блокировки (MPSC) - один из самых простых алгоритмов без блокировок для реализации.
Самая базовая реализация требует простой односторонне-связанный список (SList) без блокировок только с push () и flush (). Функции доступны в Windows API как InterlockedFlushSList() и InterlockedPushEntrySList(), но их очень легко выполнить самостоятельно.
Несколько элементов Push (), поступающих от производителя, на SList с использованием CAS (блокировка сравнения и обмена).
Single Consumer выполняет flush (), который заменяет начало SList на NULL, используя XCHG (обмен с блокировкой). Потребитель тогда имеет список предметов в обратном порядке.
Чтобы обработать элементы по порядку, вы должны просто перевернуть список, возвращенный функцией flush (), перед его обработкой. Если вы не заботитесь о порядке, вы можете просто просмотреть список сразу, чтобы обработать его.
Две заметки, если вы катите свои собственные функции:
1) Если вы работаете в системе со слабым упорядочением памяти (например, PowerPC), вам необходимо поставить "барьер освобождения памяти" в начале функции push () и "барьер памяти aquire" в конце сброса () функция.
2) Вы можете значительно упростить и оптимизировать функции, потому что проблема ABA с SLists возникает во время функции pop (). Вы не можете иметь проблемы ABA с SList, если вы используете только push () и flush (). Это означает, что вы можете реализовать его как единый указатель, очень похожий на код без блокировки, и нет необходимости в счетчике последовательности, предотвращающем ABA.
Вот статья из Университета Рочестера, иллюстрирующая неблокирующую параллельную очередь. Алгоритм, описанный в статье, демонстрирует один метод создания очереди без блокировки.
Возможно, вы захотите взглянуть на строительные блоки Intel, я вспоминаю лекцию разработчика Intel, в которой упоминалось что-то подобное.