Атомное сравнение и обмен со структурой в Go

Я пытаюсь создать неблокирующий пакет очереди для параллельного приложения, используя алгоритм Магеда М. Майкла и Майкла Л. Скотта, как описано здесь.

Для этого требуется использование атомарного CompareAndSwap, который предлагается в пакете "sync/atomic".
Однако я не уверен, каким будет Go-эквивалент следующего псевдокода:

E9:   if CAS(&tail.ptr->next, next, <node, next.count+1>)

где tail и next имеют тип:

type pointer_t struct {
    ptr   *node_t
    count uint
}

и node имеет тип:

type node_t struct {
    value interface{}
    next  pointer_t
}

Если я правильно понял, кажется, что мне нужно сделать CAS со структурой (и указателем, и uint). Возможно ли это вообще с пакетом atomic?

Спасибо за помощь!


go queue struct compare-and-swap
person ANisus    schedule 17.07.2012    source источник

Ответы (2)


arrow_upward
13
arrow_downward

Если я правильно понял, кажется, что мне нужно сделать CAS со структурой (и указателем >, и uint). Возможно ли это даже с атомарным пакетом?

Нет, это невозможно. Большинство архитектур поддерживают атомарные операции только с одним словом. Однако во многих научных работах используются более мощные операторы CAS (например, сравнение и замена местами), которые сегодня недоступны. К счастью, есть несколько приемов, которые обычно используются в таких ситуациях:

  • Например, вы можете украсть пару битов из указателя (особенно в 64-битных системах) и использовать их для кодирования вашего счетчика. Тогда вы могли бы просто использовать CompareAndSwapPointer Go, но вам нужно замаскировать соответствующие биты указателя, прежде чем вы попытаетесь разыменовать его.

  • Другая возможность — работать с указателями на вашу (неизменную!) структуру pointer_t. Всякий раз, когда вы хотите изменить элемент из вашей структуры pointer_t, вам придется создать копию, изменить копию и атомарно заменить указатель на вашу структуру. Эта идиома называется COW (копирование при записи) и работает с произвольно большими структурами. Если вы хотите использовать эту технику, вам придется изменить следующий атрибут на next *pointer_t.

Недавно я написал список блокировок на Go в образовательных целях. Вы можете найти (хорошо задокументированный) источник здесь: https://github.com/tux21b/goco/blob/master/list.go

В этом довольно коротком примере чрезмерно используется atomic.CompareAndSwapPointer, а также вводится атомарный тип для отмеченных указателей. (структура MarkAndRef). Этот тип очень похож на вашу структуру pointer_t (за исключением того, что он хранит bool+pointer вместо int+pointer). Он используется для того, чтобы убедиться, что узел не был помечен как удаленный, когда вы пытаетесь вставить элемент сразу после этого. Не стесняйтесь использовать этот источник в качестве отправной точки для ваших собственных проектов.

person tux21b    schedule 17.07.2012
comment
Спасибо, смокинг! Да, мой пакет также носит образовательный характер, и я не могу сказать, что у меня большой опыт работы с lock-free кодированием. Но ваш пакет помогает учиться. Однако я подожду, чтобы увидеть, смогу ли я получить ответ, который мог бы быть более конкретным по вопросу. - person ANisus; 18.07.2012
comment
О, извините за это. Сейчас я попытался более точно ответить на ваш вопрос. Не стесняйтесь спрашивать, если я снова что-то пропустил :) - person tux21b; 18.07.2012
comment
О да. Спасибо за дополнение к ответу. Это помогает мне понять, что возможно и каковы пределы атомарной операции. Нет, теперь я чувствую, что ваш ответ ответил на мой вопрос и дал мне дополнительную информацию, полезную для моего проекта. - person ANisus; 19.07.2012
comment
Почему бы не избежать дополнительной косвенности, сделав структуру node_t неизменяемым объектом и используя CAS для обновления поля ptr в pointer_t? - person Matt; 27.07.2012
comment
@Matt: Это не сработает. Предположим, у вас есть связанный список с тремя структурами node_t A -> B -> C. Если вы хотите добавить новый узел D в конец списка, вам нужно будет создать новый node_t для C и изменить B.next атомарно. К сожалению, нет никакой гарантии, что B все еще находится в списке. A.next уже может указывать на C напрямую, если кто-то решил удалить B. Эта проблема решается отдельной структурой markAndRef. - person tux21b; 27.07.2012
comment
Чтобы уточнить: type node_t struct{value interface{}; ptr *node_t; count uint} ... atomic.CompareAndSwapPointer(&tail, next, node_t{value, next, next.count+1}) - tail и next оба будут иметь тип *node_t. - person Matt; 27.07.2012
comment
Я знаю, я предполагал аналогичный макет, за исключением того, что я не предполагал хвостовой указатель (только голову). В любом случае, даже если вам удастся ввести такой хвостовой указатель, проблема останется прежней, если вы попытаетесь вставить что-то в середину (т.е. после узла, который можно удалить) списка. - person tux21b; 27.07.2012
comment
На самом деле node_t не будет полностью неизменным; можно изменить только поле ptr. В вашем примере вы бы не создали новый node_t для C; вы бы изменили C.ptr с помощью CAS. B будет по-прежнему указывать на C. CAS(&tail.ptr, nil, node_t{value, nil, 0}). К сожалению, я думаю, что мы теряем важный атрибут исходного алгоритма - для каждого вызова постановки в очередь делается только одно выделение. Я думаю, что способ Go сделать это — использовать пару каналов плюс горутину для управления связанным списком. Делитесь памятью, общаясь — не общайтесь, делясь памятью. - person Matt; 27.07.2012
comment
Хм. Поле счетчика все еще может быть изменено в новом хвосте, пока оно не будет вставлено в список. Таким образом, мы могли бы избежать распределения в цикле enqueue(). - person Matt; 27.07.2012
comment
Исходный алгоритм также использует как минимум два выделения памяти для каждого вызова постановки в очередь (node_t и markAndRef). Кроме того, я до сих пор не понимаю, что вы имеете в виду. Если вы хотите вставить новый узел D, вы не можете просто изменить C.ptr, потому что C.deleted / C.counter могут измениться одновременно, и ваш вставленный элемент будет потерян. Вы не можете заменить полный узел C по тем же причинам (удаление B). Каналы Go великолепны и просты для понимания, но они не являются lock-free/block-free и выполняют довольно много дорогостоящей работы в фоновом режиме. Поэтому эти структуры данных по-прежнему полезны в Go. - person tux21b; 27.07.2012

arrow_upward
0
arrow_downward

Вы можете сделать что-то вроде этого:

 if atomic.CompareAndSwapPointer(
    (*unsafe.Pointer)(unsafe.Pointer(tail.ptr.next)), 
    unsafe.Pointer(&next), 
    unsafe.Pointer(&pointer_t{&node, next.count + 1})
 )
person perreal    schedule 17.07.2012
comment
Я попробовал ваше предложение, но поскольку next равно var pointer_t, а не var *pointer_t, преобразовать его невозможно. Также node_t не имеет свойств node и count. .. но я признаю, что не понимаю, почему псевдокод говорит <node, next.count+1> - person ANisus; 18.07.2012