Как реализовать решение ABA?

Я пытаюсь реализовать очередь FIFO Майкла-Скотта из здесь . Я не могу реализовать их решение проблемы ABA. Я получаю эту ошибку.

error: incompatible type for argument 1 of '__sync_val_compare_and_swap'

Для справки, я использую Linux для компиляции на архитектуре Intel. Если вам нужна дополнительная информация о моей настройке, пожалуйста, спросите.

Кажется, что sync_val_CAS обрабатывает только до 32-битных значений. Поэтому, когда я удаляю их счетчик, который используется для устранения проблемы ABA, все компилируется и работает нормально.

Кто-нибудь знает о соответствующей 64-битной инструкции CAS, которую я должен использовать здесь?

В качестве дополнительного вопроса: есть ли лучшие (более быстрые) реализации очередей FIFO без блокировок? Я наткнулся на это от Нира Шавит и др., что кажется интересным. Мне интересно, видели ли другие подобные попытки? Спасибо.


linux concurrency intel fifo lock-free
person Boilermaker    schedule 05.06.2012    source источник
comment
Решение ABA дает решение CDC или решение BEB   -  person Jay    schedule 05.06.2012
comment
Какой язык вы используете? С?   -  person    schedule 08.06.2012
comment
См. stackoverflow.com/questions /38984153/ для структуры указателя C++11 + ABA-счетчика с обновлениями сравнения-обмена, но эффективной загрузкой только указателя (с использованием объединения).   -  person Peter Cordes    schedule 20.05.2017

Ответы (3)


arrow_upward
0
arrow_downward

Предполагая gcc, попробуйте использовать переключатель «Марш». Что-то вроде этого: -march=i686

Существует также файл __sync_bool_compare_and_swap. Не знаю быстрее или нет.

person johnnycrash    schedule 06.06.2012
comment
-mcx16 требуется для CMPXCHG16B. - person Damon; 06.06.2012
comment
Мы используем redhat linux на Intel, и March=i686 — один из переключателей, которые нам подошли. Мы просто согласились с этим, так как он действует как главный выключатель, который включает и другие хорошие вещи. Я помню, мы заставили атомарные встроенные функции работать и с другими коммутаторами. - person johnnycrash; 06.06.2012
comment
@Дэймон. Эй, это 16-байтовый CAS? Ооооооооооооооооооооооооочень круто. Что было бы неплохо, так это то, что он мог бы одновременно выполнять две отдельные 8-байтовые ячейки с двумя отдельными 8-байтовыми локациями. Так что мы могли бы сделать гораздо больше намного проще. - person johnnycrash; 06.06.2012
comment
Спасибо за информацию, johnnycrash, это полезно, но не совсем так. установка -march=i686 дает мне ошибку «ошибка: выбранный вами ЦП не поддерживает набор инструкций x86-64». Казалось бы, это указывает на то, что мой процессор не выполняет 64-битные инструкции, но это не так. 'uname -a' подтверждает это, так как в своем выводе он содержит x86_64. На этой странице есть дополнительная информация. gcc.gnu.org/onlinedocs/gcc/i386-and- x86_002d64-Options.html. Кажется, предполагается, что -march=native поможет, но не продолжайте. к вашему сведению, я использую Intel Xeon proc. Что мне здесь не хватает? - person Boilermaker; 07.06.2012
comment
Попробуйте мои точные настройки: -march=i686 -pipe -m32. Вы компилируете 64 или 32 бит? Кажется, я помню проблему, когда мог потребоваться другой переключатель. Что за ксенон? en.wikipedia.org/wiki/Xeon. Не похоже, что каждый ксенон будет иметь 64-битную возможность, но я действительно не знаю. Я почти уверен, что переключатель -march или переключатель на этой странице gcc - это то, что вам нужно. Поиграйте с ними. - person johnnycrash; 07.06.2012
comment
Вы пробовали, __sync_bool_compare_and_swap ‹-- BOOL. Это может больше поддерживаться на разных платформах. - person johnnycrash; 07.06.2012
comment
Вы возвращаете результат вызова __sync_val_compare_and_swap (return __sync_val_compare_and_swap(a,b,c)) или присваиваете его переменной? - person johnnycrash; 07.06.2012
comment
У меня стоит Gulftown X5670 Xeon. sync_bool имеет ту же ошибку, что и sync_val. gcc версии 4.2.3. Результат cmpxchg является частью условия if. Он не назначается и не возвращается. Я буду продолжать пробовать разные варианты, чтобы увидеть, работает ли что-нибудь. Спасибо еще раз. - person Boilermaker; 07.06.2012

arrow_upward
0
arrow_downward

GCC, который я последний раз просматривал в 2009 году, не поддерживает смежные двойные слова CAS. Пришлось реализовать поточную сборку.

Вы можете найти мою реализацию очереди M&S (включая на уровне абстракции сборочную реализацию DCAS) и другие структуры данных без блокировок здесь;

http://www.liblfds.org

Кратко взглянув на статью Нира Шавита и др., очередь требует безопасного восстановления памяти, которую, я подозреваю, вам нужно будет реализовать - она ​​не будет встроена в очередь. SMR API будет доступен в следующем выпуске (через пару недель).

person Community    schedule 08.06.2012
comment
спасибо за либ. Похоже, это было бы очень полезно. К сожалению, я не смог его использовать. Он отлично строится, создавая файл liblfds.a в каталоге /bin. Затем я просто ссылаюсь на это, когда компилирую свою программу, но компоновщик не может найти queue_new. Я получаю эту ошибку "неопределенная ссылка на `queue_new (queue_state**, unsigned long long)'. Вероятно, это что-то тривиальное, и я чувствую себя новичком, спрашивающим об этом, но, возможно, вы можете указать, что я делаю неправильно? Я пробовал "g++ myprog.cpp path/to/libflds.a", а также "g++ -L/path/to/libflds.a -llfds myprog.cpp" - person Boilermaker; 12.06.2012
comment
Также из любопытства, сталкивались ли вы с эта версия очереди Майкла Скотта? Выглядит очень интересно, хотя и немного сложно. Я попытаюсь реализовать его в flds, как только разберусь с вещами, и посмотрю, дает ли это преимущества производительности, на которые они претендуют. - person Boilermaker; 12.06.2012
comment
Я думаю, вы можете столкнуться с украшением имени. liblfds — это библиотека C — я компилирую ее с помощью gcc. g++ может пытаться ссылаться на него, как если бы это была библиотека C++. Погуглите об украшении имени. - person ; 12.06.2012
comment
Эта версия очереди M&S является очередью M&S :-) она реализована в liblfds. Это довольно просто, как только вы поймете это. - person ; 12.06.2012
comment
Нет, я пробовал gcc, та же проблема. 'gcc myprog.c path/to/libflds.a' должен работать на самом деле, не так ли? - person Boilermaker; 12.06.2012
comment
Я удивлен. Я думал, что это очередь M&S. Но приятно знать, что новая версия реализована, мне было любопытно, как она будет работать по сравнению с оригиналом. - person Boilermaker; 12.06.2012
comment
Странный. Я думал, что когда я щелкнул по этой исходной ссылке (которая в настоящее время указывает на документ Шавита), он перешел на веб-страницу с исправленной версией очереди M&S. Две ссылки в их нынешнем виде предназначены для разных алгоритмов (во всяком случае, AFAIK - я не читал статью Шавита). - person ; 12.06.2012
comment
Является ли gcc ссылкой в ​​вашей системе? возможно, он все еще указывает на что-то, что компилируется по умолчанию в режиме C++. - person ; 12.06.2012
comment
Нет, это тоже не проблема. Не могли бы вы сказать мне, почему закрыт форум на liblfds.org? Может быть, мы могли бы лучше поговорить там? - person Boilermaker; 12.06.2012
comment
Как ни странно, я просто работаю над тем, чтобы исправить форум. Это закрытый банкомат из-за автоматического спама. Если у вас есть форум phpBB и вы позволяете людям регистрироваться (с проверкой кода), вы получаете массу успешных регистраций роботов, которые спамят доску. Я просто настраиваю регистрацию, требующую ответа по электронной почте. - person ; 12.06.2012
comment
Хм. Можно было бы подумать, что капча позаботится об этом. Пожалуйста, дайте мне знать, когда это закончится. Было бы здорово поговорить с вами о некоторых деталях liblfds. - person Boilermaker; 12.06.2012
comment
Работает! На самом деле, это тоже новая доска - я недавно перешел с виртуальной машины сackmounted.com на Amazon, и phpBB не справился с переносом, поэтому я создал новую доску. Ты будешь первым участником :-) - person ; 12.06.2012

arrow_upward
0
arrow_downward

Lock-free может быть не тем, что вам нужно, поскольку lock-free не обязательно означает отсутствие ожидания. Если вам нужна быстрая потокобезопасная очередь (не без блокировок!), рассмотрите возможность использования Стандартные блоки потоков concurrent_queue.

person Brad Werth    schedule 20.02.2014