Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 52
В конце статьи есть ссылка на бенчмарк, можно запустить локально.
Идея со спинлоком хорошая — вечером напишу, и добавлю в статью результаты.
Если добавите сами, присылайте pull-request.
Идея со спинлоком хорошая — вечером напишу, и добавлю в статью результаты.
Если добавите сами, присылайте pull-request.
и как итог со спинлоком?
Добавил в конец статьи. Все как предсказывал lostmsu.
Спасибо. Просто чудесно доказательно, что lock-free для мутабельных языков — только лишний геморрой. :)
Попробуйте реализацию с __try/__except вместо hazard pointers. Именно такая реализация используется в windows как на уровне ядра, так и в юзермоде. Там даже сделана специальная оптимизация, есть особая проверка в KiTrap0E, но и без такой оптимизации должно быть быстро.
Когда начал читать статью, думал, что никогда не писал lock-free стек. А потом оказалось, что именно этим и занимался, только на GPU, ибо вариантов других там особо не было (ну кроме совсем медленных).
> Hazard Pointers
А как гарантируется что между точками «проверяем все локальные указатели» и «удаляем элемент» один из потоков не начнет работу с этим элементом?
А как гарантируется что между точками «проверяем все локальные указатели» и «удаляем элемент» один из потоков не начнет работу с этим элементом?
Удаляющий поток:
1. Убрать A с вершины стека.
2. Прочитать все hazard-указатели, убедиться, что там нет A.
3. Удалить А.
Читающий поток:
a) Прочитать вершину стека
b) Сохранить прочитанную вершину в hazard указатель
c) Прочитать вершину стека опять. Если она изменилась, то перейти к a)
Если a) произошло до 1, но b) произошло после или в течение 2, то при повторной проверке (с)) вершина будет уже изменена, то есть проверка провалится, и мы перейдем опять к a), не начав работу с элементом.
1. Убрать A с вершины стека.
2. Прочитать все hazard-указатели, убедиться, что там нет A.
3. Удалить А.
Читающий поток:
a) Прочитать вершину стека
b) Сохранить прочитанную вершину в hazard указатель
c) Прочитать вершину стека опять. Если она изменилась, то перейти к a)
Если a) произошло до 1, но b) произошло после или в течение 2, то при повторной проверке (с)) вершина будет уже изменена, то есть проверка провалится, и мы перейдем опять к a), не начав работу с элементом.
А что отложено по осям на графиках результатов замеров Dell Precision T5500?
Хм… по поводу hazard pointer-ов.
А чем плох вариант, если поток при намерении изменить элемент, запишет его адрес не себе в «видимый снаружи указатель», а поставит метку (свой thread id, например) в спец. поле в самом элементе? А при освобождении — соответственно, стирает её.
А конкурирующий поток сперва проверяет метку, и если элемент свободен — ставит свою. А если занят (т.е. всё равно ждать) — либо ждёт, либо по вашим вариантам — кладёт в очередь и т.д.
Да, на эту метку уйдёт сколько-то памяти (она ведь в каждом элементе).
Но за счёт этого устранится необходимость ходить по hazard pointer-ам всех потоков.
А чем плох вариант, если поток при намерении изменить элемент, запишет его адрес не себе в «видимый снаружи указатель», а поставит метку (свой thread id, например) в спец. поле в самом элементе? А при освобождении — соответственно, стирает её.
А конкурирующий поток сперва проверяет метку, и если элемент свободен — ставит свою. А если занят (т.е. всё равно ждать) — либо ждёт, либо по вашим вариантам — кладёт в очередь и т.д.
Да, на эту метку уйдёт сколько-то памяти (она ведь в каждом элементе).
Но за счёт этого устранится необходимость ходить по hazard pointer-ам всех потоков.
Это видимо будет уже не lock-free, т.к. подобная метка — это по сути уже самодельный мьютекс (точнее спинлок, т.к. не зависит от ядра), причем рекурсивный ;)
так-то да. Но ровно так же сыграет и наличие адреса этого элемента в некоем hazard-pointer потока.
Логика работы абсолютно та же, за исключением того, что не нужно перерывать массив hazard-pointer-ов в поисках «нет ли там вдруг этого элемента?».
Логика работы абсолютно та же, за исключением того, что не нужно перерывать массив hazard-pointer-ов в поисках «нет ли там вдруг этого элемента?».
Продолжая рассуждения дальше, имхо не будет особой разницы, если сделать не lock-free код, но код использующий спин-локи, и максимально минимизирующий время пребывания в локе потоком, используя схемы доступа аналогичные первому «глючному» коду. Мне кажется используя спинлоки, можно достичь той-же производительности, и иметь при этом куда меньше проблем, т.к. со спин локом не составит труда например сделать:
время, в течении которого тут будет удерживаться лок — это буквально время исполнения нескольких ассемблерных инструкций, сравнимо с оверхедом от lock-free кода.
P.S. Возможно просто стек — не очень удачный пример структуры данных, на которой получается большой выйгрыш от lock-free
spin_lock(m_lock);
old_head = m_head;
if(m_head != NULL)
m_head = m_head->next;
spin_unlock(m_lock);
время, в течении которого тут будет удерживаться лок — это буквально время исполнения нескольких ассемблерных инструкций, сравнимо с оверхедом от lock-free кода.
P.S. Возможно просто стек — не очень удачный пример структуры данных, на которой получается большой выйгрыш от lock-free
Разницы почти не будет только если вместо прямой блокировки использовать «try» функцию
(вроде TryEnterCriticalSection под windows или аналога в других системах).
А если как у вас — то это в чистом виде lock-код, со всеми вытекающими, описанными в начале статьи. Его проблема — в том, что нет никакого гарантированного «времени исполнения нескольких ассемблерных инструкций». Никто не обещает, что во время блокировки не произойдёт переключения контекстов, и ваш поток не уйдёт в спячку, может даже надолго. И другие потоки тогда тоже будут вынуждены стоять на входе в блокировку.
(вроде TryEnterCriticalSection под windows или аналога в других системах).
А если как у вас — то это в чистом виде lock-код, со всеми вытекающими, описанными в начале статьи. Его проблема — в том, что нет никакого гарантированного «времени исполнения нескольких ассемблерных инструкций». Никто не обещает, что во время блокировки не произойдёт переключения контекстов, и ваш поток не уйдёт в спячку, может даже надолго. И другие потоки тогда тоже будут вынуждены стоять на входе в блокировку.
Это самодельный Lock. А что будет если поток у вас упадет после того как установил свой thread id? Кто будет освобождать ресурс?
Тогда не понятно что делать, если более одного потока хотят работать с элементом. Первый поток поставил свой thread id в спец поле, и начал работать с элементом. Второй поток теперь свой thread id поставить не может, но и надеяться, что первый поток продержит элемент достаточно долго, тоже нельзя.
А это просто такой вариант hazard-pointer-а, без необходимости поиска.
Соответственно, решение в самой статье, раздел segfault
Соответственно, решение в самой статье, раздел segfault
Вот! Вся фишка, что у второго потока теперь есть ВЫБОР!
В случае лока он может только уснуть в функции блокировки. А здесь он может принять решение. Например, так же лечь спать. (но тогда в чём смысл делать lock-free?). Или сделать что-нибудь полезное.
В случае лока он может только уснуть в функции блокировки. А здесь он может принять решение. Например, так же лечь спать. (но тогда в чём смысл делать lock-free?). Или сделать что-нибудь полезное.
Кстати — а кэш не профайлили? Думаю что ему живется существенно легче с usleep
Думаю, что перед тем как искать хорошие реализации, можно в тестовом проекте и походить по граблям.
Походить по граблям самому конечно очень интересно и полезно, но сложность lock-free алгоритмов нельзя недооценивать, если сам Jon Skeet в большинстве случаев предпочитает locking.
В параллельном программировании грабли (race condition) случаются раз в год и только у заказчика :). ABA проблем в этом деле чемпион. Так что никаких велосипедов и много верификации алгоритмов.
Хм, описывая ваше решение коротко: контеншин на одной ячейке памяти (кеш линии) — это плохо, давайте займем чем-нибудь потоки на время 250usec (для статьи это sleep, но у нас есть еще и секретный способ :). Кроме того, что в жизни потоки и так заняты чем-то еще кроме pop и push, использует для этого очень секретный способ: Room synchronization. В простейшем виде: можно копить push() каждого локального среда в маленький list и раз 250usec добавлять его целиком, с pop() чуть сложнее :). Если у вас стэк основанный на массиве, то у вас две комнаты в одной собираются потоки которые хотят сделать push и получают номерки со смещением куда они будут вписывать данные, в другой комнате pop() потоки со смещением откуда читать. И переключатель, пока одни парни параллельно пишут, каждый в свою ячейку, вторые копятся, потом парни меняются. Как быстро раздавать номерки это еще один очень секретный алгоритм.
А чем вас не устроил boost_1_53_0/boost/lockfree/stack.hpp (оттестированное решение работающее на множестве платформ)?
Расскажите, пожалуйста, про автоматическую проверку таких алгоритмов. Ведь наверняка есть какие-то наработки.
Возможно, уместно запостить немного state of the art: комбинация техник separation logic и rely-guarantee, носящая имя RGsep, была специально заточена, чтобы сделать формальные доказательства memory safety и linearisability неблокирующих алгоритмов подъемными. В частности, если интересна теория, то по ссылке вроде как есть примеры с неблокирующим стеком, разными реализациями списков. Насколько хороша утилита, делающая это автоматически, пока не интересовался.
«В случае для стека, каждый поток имеет спецальный видимый всем указатель (назовем его «локальный указатель»), где хранится адрес элемента, с которым данный поток работает в настоящий момент.»
Может, я чего-то не понял — но чем это от блокировки отличается? Если поток, который собирался поменять элемент и поместил его адрес в «локальный указатель», отправится системой спать, то никакой другой поток этот элемент поменять не сможет, ведь так?
Может, я чего-то не понял — но чем это от блокировки отличается? Если поток, который собирался поменять элемент и поместил его адрес в «локальный указатель», отправится системой спать, то никакой другой поток этот элемент поменять не сможет, ведь так?
Все прочитанное вызвало у меня ощущение разумности за исключением 42, что подвергает сомнению всё остальное.
Замена выровненного машинного слова в памяти не вызывает случайного значения при чтении. Невыровненые или не размером в регистр машины — легко, выровненные — нет. В противном случае managed runtimes, ака Java и другие должны падать постоянно, так как там объекты хранят указатели на другие объекты и ссылки меняются и читаются в разных трэдах. Я сам участвовал в написании JVM и без этого просто ничего не выйдет.
Замена выровненного машинного слова в памяти не вызывает случайного значения при чтении. Невыровненые или не размером в регистр машины — легко, выровненные — нет. В противном случае managed runtimes, ака Java и другие должны падать постоянно, так как там объекты хранят указатели на другие объекты и ссылки меняются и читаются в разных трэдах. Я сам участвовал в написании JVM и без этого просто ничего не выйдет.
Когда в С++ что-то определено как Undefined Behavior, это не всегда значит, что на практике оно действительно поведет себя не так, как ожидается. Это всего лишь значит, что не гарантируется, что оно поведет себя так, как ожидается. Я очень сомневаюсь, что на современном железе действительно может быть возвращено что-то кроме 100 и 200, но поведение не определенное, и лучше сделать надежно.
Но иногда неопределенное поведение действительно ведет себя непредсказуемо. Например, угадайте, что выведет вот такой код, скомпилированный g++ с -O2?
Но иногда неопределенное поведение действительно ведет себя непредсказуемо. Например, угадайте, что выведет вот такой код, скомпилированный g++ с -O2?
for (int i = 0; i >= 0; ++ i)
{
if (i % 1000000000 == 0) printf("%d\n", i);
}
Почему gcc не предупреждает об этом? Вроде не так сложно выявить int % unsigned long. Или для этого есть скрытый флаг, не входящий в -Wall -Wextra?
Проблема не во взятии по модулю, проблема в переполнении i — это заметить сложнее. Переполнение знакового типа — это неопределенное поведение. В данном случае g++ заменяет цикл на while (true), потому что i может только увеличиваться, а значит i >= 0 всегда верно. Так как переполнение знакового типа неопределено, здесь компилятор имеет право сделать такое предположение.
5.4
Так что знаковое переполнение — это неопределенное поведение.
Беззнаковое переполнение определено:
3.9.1.4.
В С++11 появились знаковые типы int16_t, int32_t, int8_t, int64_t, для которых переполнение определено.
If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined.
Так что знаковое переполнение — это неопределенное поведение.
Беззнаковое переполнение определено:
3.9.1.4.
Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2^n where n is the number of bits in the value representation of that particular size of integer.
В С++11 появились знаковые типы int16_t, int32_t, int8_t, int64_t, для которых переполнение определено.
Я бы отнёс это к
-Wstrict-overflow=1. В крайнем случае, предупреждению точно есть место среди пяти уровней -Wstrict-overflow. Вечером поищу багрепорты/рассылки на эту тему, т. к. надо бы добавить предупреждение.
Думаю, что-то типа этого:
./a.cpp:1: error: expected unqualified-id before ‘for’
./a.cpp:1: error: expected constructor, destructor, or type conversion before ‘>=’ token
./a.cpp:1: error: expected unqualified-id before ‘++’ token</code>hazard pointers это очень громоздкое и негибкое решение. Число потоков заранее неизвестно, их могут быть тысячи, они могут появляться и исчезать. Контейнер завязанный на конкретные потоки очень негибок.
Вы не думали что если из-за освобождения памяти возникает исключение, проще всего будет его ловить? Просто поставить __try/__except?
Вы не думали что если из-за освобождения памяти возникает исключение, проще всего будет его ловить? Просто поставить __try/__except?
«Версии указателей» — это из серии «побеги модели Лампорта прорастают через трещины в асфальте».
Если представить что стек содержит в себе запросы, а потоки забирают от туда элементы для обработки, то тогда какая разница, что там новый элемент-запрос, находящийся по адресу А, он же является таким же запросом, таким образом проблема АВА, зависит от того, что реализует стек. В вашем примере: «Поток 1 просыпается, и вызывает CAS. CAS выполняется успешно, не смотря на то, что за это время m_head изменился три раза! Как следствие, элемент B потерян.» Элемент В продолжает находиться в цепочке, а новый элемент запрос по адресу А в вершине стека (А->В->C), он его забирает и обрабатывает. Другое дело, если важно получить именно тот, первый элемент из стека, который раньше располагался по адресу А.
т.е в вашем примере:
1.Допустим, что в стеке сейчас два элемента, A -> C.
2. Поток 1 вызывает Pop, читает в строке 22 m_head (A), в строке 26 читает old_head->next (С), а затем операционная система усыпляет поток.
3. Поток 2 вызывает Pop, и успешно убирает элемент A.
4. Поток 2 вызывает Push, и успешно вставляет элемент B.
5. Поток 2 вызывает Push опять, и вставляет элемент, расположенный по тому же адресу, что и A (либо A был освобожден, и затем другой элемент был заведен по тому же адресу, либо пользователь решил вставить элемент, который он только что взял со стека, обратно)
Поток 1 просыпается, и вызывает CAS. CAS выполняется успешно, не смотря на то, что за это время m_head изменился три раза! Как следствие, элемент B потерян
Стек
1. А->C
2. А->C
3. C
4. B->C
5. A (new)->B->C
6. B->C
каким образом мы теряем B?
1.Допустим, что в стеке сейчас два элемента, A -> C.
2. Поток 1 вызывает Pop, читает в строке 22 m_head (A), в строке 26 читает old_head->next (С), а затем операционная система усыпляет поток.
3. Поток 2 вызывает Pop, и успешно убирает элемент A.
4. Поток 2 вызывает Push, и успешно вставляет элемент B.
5. Поток 2 вызывает Push опять, и вставляет элемент, расположенный по тому же адресу, что и A (либо A был освобожден, и затем другой элемент был заведен по тому же адресу, либо пользователь решил вставить элемент, который он только что взял со стека, обратно)
Поток 1 просыпается, и вызывает CAS. CAS выполняется успешно, не смотря на то, что за это время m_head изменился три раза! Как следствие, элемент B потерян
Стек
1. А->C
2. А->C
3. C
4. B->C
5. A (new)->B->C
6. B->C
каким образом мы теряем B?
для тех, кто будет читать эту статьию и пишет на C#
Статья будет не актуальна, в случае, если CAS реализован правильно, т.е. атомарно. Interlocked это позовляет делать. Также пишут, что есть атомарные CAS реализации в других ОС, но не в Windows…
От куда взято: boyet com/Articles/LockfreeStack.html
private static bool CAS( ref Node location, Node newValue, Node comparand )
{
// 1. если comparand и location равны, то другой поток не трогал значение location.
// 2. location будет присвоен newValue.
// 3. Метод вернёт старое значение location не зависимо от присвоения.
// 4. copmarand сранится со старым значением location (node.Next == старый head.Next ?)
// 5. если location(старый, возвращенный) не был изменён другим потоком то и CAS вернёт true, т.к. он совпадёт с comparand
return comparand == Interlocked.CompareExchange( ref location,
newValue,
comparand);
}
Там даже автор отвечает на безосновательное обвинение в якобы АВА проблема. Но т.к. CAS атомарен, то ABA проблемы не будет.
Статья будет не актуальна, в случае, если CAS реализован правильно, т.е. атомарно. Interlocked это позовляет делать. Также пишут, что есть атомарные CAS реализации в других ОС, но не в Windows…
От куда взято: boyet com/Articles/LockfreeStack.html
private static bool CAS( ref Node location, Node newValue, Node comparand )
{
// 1. если comparand и location равны, то другой поток не трогал значение location.
// 2. location будет присвоен newValue.
// 3. Метод вернёт старое значение location не зависимо от присвоения.
// 4. copmarand сранится со старым значением location (node.Next == старый head.Next ?)
// 5. если location(старый, возвращенный) не был изменён другим потоком то и CAS вернёт true, т.к. он совпадёт с comparand
return comparand == Interlocked.CompareExchange( ref location,
newValue,
comparand);
}
Там даже автор отвечает на безосновательное обвинение в якобы АВА проблема. Но т.к. CAS атомарен, то ABA проблемы не будет.
> Также пишут, что есть атомарные CAS реализации в других ОС, но не в Windows…
А авторы WinAPI и не знают…
http://msdn.microsoft.com/en-us/library/windows/desktop/ms683560(v=vs.85).aspx
«Performs an atomic compare-and-exchange operation on the specified values.»
CAS везде атомарен. Код по вашей ссылке действительно не страдает от ABA проблемы, но не потому, что его CAS как-то более атомарен чем CAS в С++, а потому что в C# автоматический сборщик мусора (о чем он и говорит), Соответственно если мы увидели элемент на стеке, пока мы на него держим ссылку, память по этой ссылке не освободится, новый элемент по этому адресу не заведется, и проблема ABA не случится.
А авторы WinAPI и не знают…
http://msdn.microsoft.com/en-us/library/windows/desktop/ms683560(v=vs.85).aspx
«Performs an atomic compare-and-exchange operation on the specified values.»
CAS везде атомарен. Код по вашей ссылке действительно не страдает от ABA проблемы, но не потому, что его CAS как-то более атомарен чем CAS в С++, а потому что в C# автоматический сборщик мусора (о чем он и говорит), Соответственно если мы увидели элемент на стеке, пока мы на него держим ссылку, память по этой ссылке не освободится, новый элемент по этому адресу не заведется, и проблема ABA не случится.
Хотел спросить у вас. Делал три дня двунаправленный связанный список. Операции добавление-добавление или удаление-удаление работают без ошибок, добавление-удаление валится структура списка. Есть два типа добавления перед или после заданного узла. Так вот если во время добавления нового узла перед заданным узлом, заданный узел был удален, структура рушится. Я пришел к выводу, что необходимо атомарно менять сразу две ячейки памяти, а может даже четыре. Есть ли возможность менять сразу две ячейки памяти атомарно? Вы реализовывали двунаправленный список?
"между тем, как мы получили адрес, и тем, как мы увеличили счетчик ссылок, память могла быть освобождена." — одно из решений — откладывать ref deq и делать его в специальном потоке, остановив все остальные потоки в safe point. sape point делать через mem write access в страницу, которая переводится в read only, чтобы собрать всех обратившихся в page fault хендлере.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Частые ошибки при разработке lockfree-алгоритмов и их решения