Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Да я читал про все эти прибамбасы — уныние сплошное. Не так все это просто элегантно как с LL/SC.

А как с помощью LL/SC реализовать вставку элемента в очередь? Как вот такой код переписать на LL/SC?

struct node_t
{
  node_t*   next;
  void*     data;
};

struct queue_t
{
  node_t*   head;
  node_t*   tail;
};

void enqueue(queue_t* q, void* data)
{
  node_t* n = alloc_node();
  n->data = data;
  n->next = 0;
  gc_region_enter();
  for (;;)
  {
    node_t* tail = q->tail;
    if (CAS(&tail->next, 0, n))
      break;
  }
  CAS(&q->tail, tail, n);
  gc_region_leave();
}

Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>А как на 32-х битной x86 правильно атомарно заменить сразу два слова?

Смотря какие 2 слова, "два слова" бывают разные Слова смежные?

Здравствуйте, remark, Вы писали:

R>А как с помощью LL/SC реализовать вставку элемента в очередь? Как вот такой код переписать на LL/SC?

Просто реализовать СAS через LL/SC примерно так (на C-псевдокоде)?

CAS(addr, comp, new)
{

while (true) {

long oldValue = LL(add);
if (oldValue != comp)
 return oldValue;

if (SC(addr, new))
  return oldValue;

}

}

Здравствуйте, remark, Вы писали:

R>Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>>А как на 32-х битной x86 правильно атомарно заменить сразу два слова?

R>Смотря какие 2 слова, "два слова" бывают разные Слова смежные?

R>

А так и так . Мне просто интересен случай одновременного увеличение счетчика и перезапись указателя. Конкретно — реализация потокобезлпасного подсчета ссылок.

Здравствуйте, AcidTheProgrammer, Вы писали:

R>>А как с помощью LL/SC реализовать вставку элемента в очередь? Как вот такой код переписать на LL/SC?

ATP>Просто реализовать СAS через LL/SC примерно так (на C-псевдокоде)?

Нет, не СAS реализовать. А реализовать вставку в очередь на LL/SC, т.ч. ей не была бы нужна внешняя схема управления временем жизни объектов?

Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Здравствуйте, remark, Вы писали:

R>>Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>>>А как на 32-х битной x86 правильно атомарно заменить сразу два слова?

R>>Смотря какие 2 слова, "два слова" бывают разные Слова смежные?

ATP>А так и так . Мне просто интересен случай одновременного увеличение счетчика и перезапись указателя. Конкретно — реализация потокобезлпасного подсчета ссылок.

Смежные слова просто, есть инструкции CMPXCHG8B/CMPXCHG16B, которыми можно менять два смежных слова.
Не смежные — никак.

Здравствуйте, remark, Вы писали:

R>Здравствуйте, AcidTheProgrammer, Вы писали:

R>>>А как с помощью LL/SC реализовать вставку элемента в очередь? Как вот такой код переписать на LL/SC?

ATP>>Просто реализовать СAS через LL/SC примерно так (на C-псевдокоде)?

R>Нет, не СAS реализовать. А реализовать вставку в очередь на LL/SC, т.ч. ей не была бы нужна внешняя схема управления временем жизни объектов?

Видимо вы недопоняли — как через LL/SC реализовать CAS я написал, ну а дальше применяете вас же алгоритм, который вы описали выше.

Здравствуйте, AcidTheProgrammer, Вы писали:

R>>>>А как с помощью LL/SC реализовать вставку элемента в очередь? Как вот такой код переписать на LL/SC?

ATP>>>Просто реализовать СAS через LL/SC примерно так (на C-псевдокоде)?

R>>Нет, не СAS реализовать. А реализовать вставку в очередь на LL/SC, т.ч. ей не была бы нужна внешняя схема управления временем жизни объектов?

ATP>Видимо вы недопоняли — как через LL/SC реализовать CAS я написал, ну а дальше применяете вас же алгоритм, который вы описали выше.

Тот алгоритм, который я описал выше требует внешней схемы управления временем жизни узлов очереди (gc_region_enter()/gc_region_leave()). Вопрос — как реализовать этот алгоритм с помощью LL/SC, т.ч. ей не была бы нужна внешняя схема управления временем жизни объектов.

Это вопрос к тезису:

Да я читал про все эти прибамбасы — уныние сплошное. Не так все это просто элегантно как с LL/SC.

Если же этого сделать нельзя, то не понятно о какой элегантности LL/SC идёт речь. Если у нас всё равно есть схема управления временем жизни, то ABA проблемы нет как таковой.

Здравствуйте, remark, Вы писали:

Ну также, почти. Правда я не совсем понимаю ваш код:
Для вставки в очередь достаточно атомарной операции EXCHG или Swap, во всяком случае у меня во всех очередях используется такая операция.
(Может это моё ноу-хау Ну а EXCHG через LL/SC без проблем выводится.

Здравствуйте, remark, Вы писали:

R>Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>>Здравствуйте, remark, Вы писали:

R>>>Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>>>>А как на 32-х битной x86 правильно атомарно заменить сразу два слова?

R>>>Смотря какие 2 слова, "два слова" бывают разные Слова смежные?

ATP>>А так и так . Мне просто интересен случай одновременного увеличение счетчика и перезапись указателя. Конкретно — реализация потокобезлпасного подсчета ссылок.

R>Смежные слова просто, есть инструкции CMPXCHG8B/CMPXCHG16B, которыми можно менять два смежных слова.
R>Не смежные — никак.

Ну вроде как что-то припоминаю такое, а в винде его никак не вызвать (не на ассемблере)?

Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Ну также, почти. Правда я не совсем понимаю ваш код:
ATP>Для вставки в очередь достаточно атомарной операции EXCHG или Swap, во всяком случае у меня во всех очередях используется такая операция.
ATP>(Может это моё ноу-хау Ну а EXCHG через LL/SC без проблем выводится.

Ну так через XCHG будет не lock-free очередь, а блокирующая (если я правильно понял, о чём речь).
Задача портировать на LL/SC именно такую lock-free очередь.

Здравствуйте, AcidTheProgrammer, Вы писали:

R>>Смежные слова просто, есть инструкции CMPXCHG8B/CMPXCHG16B, которыми можно менять два смежных слова.
R>>Не смежные — никак.

ATP>Ну вроде как что-то припоминаю такое, а в винде его никак не вызвать (не на ассемблере)?

http://msdn.microsoft.com/en-us/library/ms683562%28VS.85%29.aspx

Здравствуйте, remark, Вы писали:

R>Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>>Ну также, почти. Правда я не совсем понимаю ваш код:
ATP>>Для вставки в очередь достаточно атомарной операции EXCHG или Swap, во всяком случае у меня во всех очередях используется такая операция.
ATP>>(Может это моё ноу-хау Ну а EXCHG через LL/SC без проблем выводится.

R>Ну так через XCHG будет не lock-free очередь, а блокирующая (если я правильно понял, о чём речь).
R>Задача портировать на LL/SC именно такую lock-free очередь.

R>

Извиняюсь если не до конца понимаю терминологию. Нужно было бы конечно сначала договориться что считаем блокирующей/не блокирующей. Здесь разве есть блокирование?

// Allocate new item for future element

ItemPtr pItem = new Item;
ItemPtr pOldTail = pItem;

// Swap new item and previous tail item
            
EXCHG(m_pQueueTail, pOldTail);

Здравствуйте, remark, Вы писали:

R>Здравствуйте, AcidTheProgrammer, Вы писали:

R>>>Смежные слова просто, есть инструкции CMPXCHG8B/CMPXCHG16B, которыми можно менять два смежных слова.
R>>>Не смежные — никак.

ATP>>Ну вроде как что-то припоминаю такое, а в винде его никак не вызвать (не на ассемблере)?

R>http://msdn.microsoft.com/en-us/library/ms683562%28VS.85%29.aspx

Она, насколько я понял, не доступна в 32-х битной версии. Для 64-х битной версии не доступна 128-бинтная и т.д. Задача используя именно примитивы разрядности = разрядности процессора обменять сразу два слова. Задачка что-то типа построить двойной СAS (DCAS) на основе одинарного и т.д.

Здравствуйте, AcidTheProgrammer, Вы писали:

R>>>>Смежные слова просто, есть инструкции CMPXCHG8B/CMPXCHG16B, которыми можно менять два смежных слова.
R>>>>Не смежные — никак.

ATP>>>Ну вроде как что-то припоминаю такое, а в винде его никак не вызвать (не на ассемблере)?

R>>http://msdn.microsoft.com/en-us/library/ms683562%28VS.85%29.aspx

ATP>Она, насколько я понял, не доступна в 32-х битной версии. Для 64-х битной версии не доступна 128-бинтная и т.д. Задача используя именно примитивы разрядности = разрядности процессора обменять сразу два слова. Задачка что-то типа построить двойной СAS (DCAS) на основе одинарного и т.д.

А ну это пожалуйста, одинарный CAS присутствует — InterlockedCompareExchange.

з.ы. а где написано, что InterlockedCompareExchange64() не доступна в 32-битной версии?

Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Извиняюсь если не до конца понимаю терминологию. Нужно было бы конечно сначала договориться что считаем блокирующей/не блокирующей. Здесь разве есть блокирование?

ATP>

ATP>// Allocate new item for future element

ATP>ItemPtr pItem = new Item;
ATP>ItemPtr pOldTail = pItem;

ATP>// Swap new item and previous tail item
            
ATP>EXCHG(m_pQueueTail, pOldTail);
ATP>

Блокироваться будет потребитель, если этот производитель прервётся в нехорошем месте (опять же, если я правильно угадал алгоритм).

Здравствуйте, remark, Вы писали:

ATP>>Извиняюсь если не до конца понимаю терминологию. Нужно было бы конечно сначала договориться что считаем блокирующей/не блокирующей. Здесь разве есть блокирование?

ATP>>

ATP>>// Allocate new item for future element

ATP>>ItemPtr pItem = new Item;
ATP>>ItemPtr pOldTail = pItem;

ATP>>// Swap new item and previous tail item
            
ATP>>EXCHG(m_pQueueTail, pOldTail);
ATP>>

R>Блокироваться будет потребитель, если этот производитель прервётся в нехорошем месте (опять же, если я правильно угадал алгоритм).

Дело даже не в конкретной очереди. Дело в том, что простое подавление ABA работает только в очень частных случаях, поэтому особой элегантности я в этом не вижу.
Другой пример — допустим есть хэш-таблица, один поток ищет элемент и инкрементирует счётчик в нём, другой поток может одновременно удалить элемент. Тут тоже простым подавлением ABA не обойдёшься.

А если говорить о частных случаях, то и с CAS можно жить. Вот например тут моя MPMC очередь, которая использует ABA-counter и структруную обработку исключений (SEH) для обхода проблем:
http://software.intel.com/en-us/blogs/2009/08/11/multi-producermulti-consumer-seh-based-queue/

Здравствуйте, remark, Вы писали:

R>>Блокироваться будет потребитель, если этот производитель прервётся в нехорошем месте (опять же, если я правильно угадал алгоритм).

EXCHG — это простой InterlockedExchange — от атомарен. Как он может прерваться? Tail есть всегда.

R>Дело даже не в конкретной очереди. Дело в том, что простое подавление ABA работает только в очень частных случаях, поэтому особой элегантности я в этом не вижу.

СAS проверяет значение элемента, а это недостаточное условие того что состояние не изменилось — следовательно начинаются пляски.
LL — ставит под контроль адрес (ячейку) памяти и если SC выполняется успешно, то значение точно не менялось. То есть, если перезапись была, но на тоже значение, то SC это замит, CAS -нет. В остальном они полностью эквивалентны.

R>Другой пример — допустим есть хэш-таблица, один поток ищет элемент и инкрементирует счётчик в нём, другой поток может одновременно удалить элемент. Тут тоже простым подавлением ABA не обойдёшься.

Тут соглачен. Вот тут нужен DCAS или что-то подобное.

R>А если говорить о частных случаях, то и с CAS можно жить. Вот например тут моя MPMC очередь, которая использует ABA-counter и структруную обработку исключений (SEH) для обхода проблем:
R>http://software.intel.com/en-us/blogs/2009/08/11/multi-producermulti-consumer-seh-based-queue/

Жить можно, но сложно

Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Здравствуйте, remark, Вы писали:

R>>>Блокироваться будет потребитель, если этот производитель прервётся в нехорошем месте (опять же, если я правильно угадал алгоритм).

ATP>EXCHG — это простой InterlockedExchange — от атомарен. Как он может прерваться? Tail есть всегда.

Ты же не весь код показал, там же ещё должно быть установление связей между элементами очереди. Вот там-то, я думаю, и будут проблемы. Насколько мне известно, сейчас lock-free очередей, которые используют XCHG в push() нет.

Здравствуйте, AcidTheProgrammer, Вы писали:

R>>>Блокироваться будет потребитель, если этот производитель прервётся в нехорошем месте (опять же, если я правильно угадал алгоритм).

ATP>EXCHG — это простой InterlockedExchange — от атомарен. Как он может прерваться? Tail есть всегда.

R>>Дело даже не в конкретной очереди. Дело в том, что простое подавление ABA работает только в очень частных случаях, поэтому особой элегантности я в этом не вижу.

ATP>СAS проверяет значение элемента, а это недостаточное условие того что состояние не изменилось — следовательно начинаются пляски.
ATP>LL — ставит под контроль адрес (ячейку) памяти и если SC выполняется успешно, то значение точно не менялось. То есть, если перезапись была, но на тоже значение, то SC это замит, CAS -нет. В остальном они полностью эквивалентны.

Условие, что значение одной переменной не изменилось, тоже является недостаточным для достижения корректности многих алгоритмов. Им всё равно необходимо управление временем жизни, а раз так, то ABA проблемы нет.
... ну либо им нужен multi-word LL/SC (транзакционная память).


R>>Другой пример — допустим есть хэш-таблица, один поток ищет элемент и инкрементирует счётчик в нём, другой поток может одновременно удалить элемент. Тут тоже простым подавлением ABA не обойдёшься.

ATP>Тут соглачен. Вот тут нужен DCAS или что-то подобное.

DCAS-ом тут не обойдёшься, тут будет нежен double-LL/SC (что в простанородье уже вобщем-то называется транзакционной памятью).