Вчера узнал

Автор: Коваленко Дмитрий
Дата: 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

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

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

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

Смысл такой.

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

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

//удаление (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. Надо понять за что я полторы тысячи отдал