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

Я читал статью "Простые, быстрые и практичные алгоритмы неблокирующих и блокирующих параллельных очередей" и я понял, что они предполагают, что компьютер реализует следующий псевдокод атомарно:

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

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

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


c queue nonblocking lock-free
person marcmagransdeabril    schedule 23.08.2013    source источник
comment
Поскольку я не собираюсь покупать газету, что такое Tail? Действительно ли это указатель в сочетании со счетчиком?   -  person jxh    schedule 23.08.2013

Ответы (2)


arrow_upward
1
arrow_downward

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

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

person Ioan    schedule 23.08.2013
comment
Примечание: я не читал статью, просто предположил. Я могу ошибаться или могут быть другие способы, о которых я не знаю. - person Ioan; 23.08.2013
comment
DCAS работает с двумя разными операндами, но встречается довольно редко. DWCAS(doublewide) работает с двумя соседними значениями и эквивалентно тому, что вы делаете с достаточно широким CAS, чтобы вместить два меньших значения. - person rsaxvc; 13.04.2017

arrow_upward
0
arrow_downward

Gcc также предоставляет встроенные средства для CAS с двойным словом, вы можете использовать __sync_bool_compare_and_swap, если sizeof(*Q->Tail) == sizeof(tail) == sizeof(first_arg) == 8. Так что все работает нормально, если вы можете увеличить "next.count" перед выполнением CAS.

person uppi    schedule 23.08.2013