Как реализовать двойное сравнение и обмен в C/Linux?

Question

Я читал газету "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms", и я понял, что они предполагают, что компьютер выполняет следующий псевдокод атомарен:

CAS(Q->Tail,tail,<next.ptr,next.count+1>) 

Где Q-> Хвост и хвост указатель и экземпляр структуры, содержащий указатель и счетчик.

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

Answer 1

Я не знаю никаких операций CAS, которые работают в двух разных местах памяти. Однако, возможно, бумага использует структуру для указателя и счетчика в качестве обходного пути для обработки обоих полей как более крупного типа и, следовательно, изменения как атомарно.

Предполагая, что у вас есть структура из двух полей, указатель и счетчик: размер указателя 4 байта, размер счетчика 4 байта; правильно выровнен без заполнения до размера структуры 8 байтов. Предполагая, что у вас также есть операция CAS, которая обрабатывает значения 8 байтов (например, указатель на 64-разрядное целое число). Вы можете подготовить значения struct отдельно и использовать операцию CAS для структуры в целом, чтобы сразу изменить два значения.

Answer 2

Gcc также предоставляет встроенные модули для двойного слова CAS, вы можете использовать __sync_bool_compare_and_swap, если SizeOf (* Q-> Tail) == SizeOf (хвост) == SizeOf (third_arg) == 8. Так что все работы штраф, если вы можете увеличить «next.count» перед выполнением CAS.