Вчера узнал

Автор: Коваленко Дмитрий
Дата: 24.01.20

про технику синхронизации с использованием "опасных указателей".

Она описана в книге "Практика многопоточного программирования" Уильямса.

Написано что книга "для профессионалов"

Смысл такой.

Мы, где-то снаружи от синхронизируемых данных, сохраняем указатель на эти данные.

Пока этот указатель присутствует данные менять нельзя.

//удаление (pop) из однонаправленного списка.

std::atomic<void*>& hazadPointer=get_hazard_pointer_for_current_thread();

node* old_head=head.load();

do
{
 node* temp;
 
 do
 {
  temp=old_head;
 
  hazadPointer.store(old_head); //<----- установка "опасного указателя"

  old_head=head.load();
 }
 while(old_head!=temp);
}
/* Если я правильно понял - вся возня с hazadPointer-ами нужна для безопасного обращения к old_head->next */
while(old_head && !head.compare_exchange_strong(old_head,old_head->next));

hazadPointer.store(nullptr); //<---- сброс "опасного указателя"

//тут дальше old_head либо грохается (если на него не ссылаются hazadPointer-ы)
//либо помещается в список отложенного удаления. (1)
//
//перед выходом просматриваем список с отложенными ударениями и для каждого элемента повторяем (1)
//

Я так понимаю, предполагается что критический случай с помещением old_head в список отложенного удаления будет происходить ОЧЕНЬ редко. Тем не менее мы все равно будем каждый раз "платить" сканированием списка hazadPointer-ов.

-----
Я несколько раз просмотрел/перечитал эту главу и накатал свою дуболомную альтернативу с нормальной блокировкой. Для того, чтобы оценить и сравнить.

На компьютере не тестировал, поэтому могут быть опечатки. Полагаю, что работать она будет

//блокировка доступа к списку (g_head)
static std::atomic<std::thread::id> g_headGuard; //полагаю тут будет установлен 0

//указатель на голову однонаправленного списка. наверное тут нужно указывать volatile?
static node* g_head=nullptr;

//......
//удаление (pop) из однонаправленного списка.

//------------------------------- захват блокировки списка
std::thread::id curThreadID=std::this_thread::get_id();

for(;;)
{
 std::thread::id noThread=std::thread::id(); //полагаю тут будет установлен 0
 
 if(g_headGuard.compare_exchange_strong(noThread,curThreadID))
  break;
}//for[ever]

assert(g_headGuard.load()==curThreadID);

//------------------------------- сохраняем и отрезаем голову списка (монопольная операция)
node* old_head=g_head;

if(g_head)
 g_head=g_head->next;

//------------------------------- снимаем блокировку списка
g_headGuard.store(std::thread::id());

//------------------------------- здесь с old_head можно делать что хочешь.

На сколько я понимаю —

Что мы будем пытаться заменить голову в первом способе:

while(old_head && !head.compare_exchange_strong(old_head,old_head->next));

Что мы будем пытаться захватить блокировку во втором:

if(g_headGuard.compare_exchange_strong(noThread,curThreadID))

суть одна и та же.

Во втором, конечно, после захвата блокировки есть пара монопольно выполняемых команд (чтение и обновление g_head). Но в этой главе написано что операции с atomic типа в 100 медленнее обычных операций. Так что чтение и обновление g_head (во втором варианте) погоду не делают — да?

Но зато во втором нет возни со списками hazadPointers и отложенных удалений. Причем эта возня еще и дырявая, как я понял.

Может кто прокомментировать эти самые "опасные указатели" — в чем их лютое преимущество?

Может я что-то не догнал с ними?

Спасибо.

PS. Надо понять за что я полторы тысячи отдал

Здравствуйте, Коваленко Дмитрий, Вы писали:

КД>Вчера узнал

Автор: Коваленко Дмитрий
Дата: 24.01.20

про технику синхронизации с использованием "опасных указателей".

КД>Она описана в книге "Практика многопоточного программирования" Уильямса.

КД>Может кто прокомментировать эти самые "опасные указатели" — в чем их лютое преимущество?

КД>Может я что-то не догнал с ними?

Сам спросил, сам отвечу

Нужно было эту (седьмую) главу сначала читать.

В начале русским по белому написано, что преимущество (структур без блокировок) в том, что если любой поток отвалится в процессе модификации структуры, то другие потоки смогут продолжить работу с этой структурой.

Это раз.

При использовании структур без блокировок общая производительность может снизиться.

Это два.

Добавлю, что в конце этой главы идет "лютый ад" (на самом деле это не так), который хрен поймешь, пока не прочитаешь пятую главу. Так что задом наперед книгу читать не получится

Вот. Спасибо всем, кто помог понять всю эту хрень.