?

Log in

No account? Create an account
me

Running lock free

Допустим, вы торопитесь и вы знаете куда вы спешите. Если это не так - лучше сходите посмотреть чудесный фильм :)


Итак, мы пишем программу, которая торопится. Для того, чтобы успеть мы как взрослые пацаны решили все распараллелить по тредам, ведь уже 21-й век и меньше двух тредов осталось разве что в отсталых сотовых телефонах.

Однако, многие треды приводят к многим печалям и для того, чтобы все работало как мы задумали нам нужно как-то ограничивать паралелизм. Надежным способом для этого служит mutex/critical_section/semaphore/younameit - надежный примитив синхронизации, изобретенный ндесят лет назад. Сводится он, как известно, к блокированию исполнения всех тредов кроме одного. Правильное приготовление этого метода описано в том числе здесь. Возможно, для вас станет открытием, что при реализации busy wait lock-а лучше делать предварительную проверку с помощью volatile read на предмет возможности захвата перед попыткой собственно захвата с помощью locked инструкции. Т.е. перед xchg [cs], xz / lock cmpxchg [cs], xz лучше сначала сделать простое cmp [cs], 0.

Однако, если мы действительно торопимся, то исполнять всего один тред из всех это совсем не то, что мы хотим делать. Особенно, если система может этот единственный тред вытеснить и наш тред будет ожидать какого-нибудь "важного" процесса типа чтения блока из swap-file-a. Btw, если вы торопитесь, то swap лучше таки отрубить напрочь. По идее, вытеснение единственного работающего треда в процессе это редкость. Однако, если ваша система носит гордое имя FreeBSD, то событие становится вероятным. А если вы имели неосторожность запустить свою программу на кластере и обязательно ждете все N-сто ответов, то вероятность успешно превращается в закономерность.

Как же нам обойти проблему и не ждать? Для этого человечество в лице Мориса Херлихуя (затрудняюсь правильно скзаать по-русски Herlihy) изобрело wait free synchronization. Точнее, Морис доказал, что с помощью примитива CAS (compare and swap) можно реализовать любой wait free алгоритм. Инструкция CAS имеет 3 параметра - адрес переменной, тестовое значение и новое значение. Если в переменной лежит тествое значение, то CAS заменяет его на новое, иначе значение переменной не меняется. На правильных процессорах CAS может выполняться атомарно.

bool CAS(void **addr, void *new, void *old)
    if (*addr == old) {
        *addr = new;
        return true;
    } else
        return false;
    }
_Winnie C++ Colorizer

Способ сделать любую операцию lock free, например, такой: У нас есть некая структура данных и есть указатель на нее по имени Ptr. Мы берем текущее значение Ptr, пусть это pDataOld. Мы копируем структуру и проводим нужную операцию с копией. В результате мы получаем модифицированную копию pDataNew. Теперь мы с помощью CAS пытаемся заменить значение на новое: CAS(Ptr, pDataNew, pDataOld). Если CAS прошла успешно, то все получилось, если обломалась, то кто-то успел раньше нас и нам надо начинать с начала.

Начиная с 486-го в процессорах Intel есть реализация CAS под именем cmpxchg. Сделать ее atomic можно с помощью префикса lock. Звать ее можно так.

Отлично. Не откладывая в долгий ящик переходим на lock-free синхронизацию между потоками с помощью lock-free stack. Lock-free stack - пожалуй самая простая структура данных, которую можно использовать для передачи данных из одного потока в другой. Используя свеже полученные знания быстро кодаем:

Push(T *obj)
    n = new Node(obj);
    n->Val = obj;
    do {
        n->Next = Top;
     } while (!CAS(&Top, n, n->Next));
  
T *Pop()
    for(;;) {
        Node *t = Top;
        if (t == 0)
            return 0;
        if (CAS(&Top, t->Next, t)) {
            T *res = t->Val;
            delete t; // жопа-кеды
            return res;
        }
    }
_Winnie C++ Colorizer

Готово! Изготовив подобный код я не замедлил его запустить. И чудо произошло - программа магическим образом ускорилась даже на моем рабочем компе всего с 2-мя ядрами. Теперь она не ждала впустую на тупых critical sections, а молотила во все транзисторы.

Однако, у вас может возникнуть резонный вопрос - что это за комментарий такой после delete t? Дело в том, что если эту строчку закомментировать, то все будет отлично работать, разве что будет бесконечно есть память. Но вы можете это побороть регулярно рестартуя программу :) Если это не входит в ваши планы, то строчку придется вернуть и успех наступает неотвратимо. Тот, кто самостоятельно догадается о механизме возникновения успеха будет пользоваться моим безграничным уважением.

Для остальных сообщаю, что проблема имеет название ABA и происходит это так:

Первый тред выполняет Pop(), считывает текущий Top, записывает его в t и готовится стать отцом заменить Top на t->Next. Для этого он зачитывает t->Next в регистр и... Но в этом месте его прерывают. Его более шустрый сосед выполняет Pop(), который заканчивается успешно (у нас же lock-free) и выполняет пресловутый delete t; Т.е. теперь первый тред имеет указатель t, выставленный на объект, который уже во free memory. Но это ведь не страшно, ведь великий CAS защитит нас и не даст выставить Top в уже неправильный t->Next? Правильно? Конечно, правильно. Однако, второй тред не стоит на месте и в свою очередь зовет Push(), который успешно выполняется целиком. Теперь, если у нас перспективный memory manager, который первыми выделяет недавно освободившиеся блоки, то элемент Node, который Push() выделяет с помощью "new Node" будет в точности равен t из первого потока. Занавес, смена декораций и управление передается первому потоку. Первый поток выполняет CAS и CAS оказывается успешным, ведь Top таки равен t. Правда, хотя адрес и совпадает, это уже совсем другой объект и t->Next у него совсем другой, но первый поток об этом не узнает, ведь он уже прочитал t->Next в регистр. Хобана жопа-кеды. (Термин жопа-кеды - (с) by sim0nsays).

Что же делать, что же делать??? Очевидный ответ - не использовать delete t, однако, думаю, он не всем подойдет :) Далее мнения разошлись и предлагаются такие варианты исправления:

1. В качестве указателя использовать пару (указатель, счетчик). Счетчик прибавлять за каждую операцию. Другие публикации автора. Однако, этот метод требует более широкой операции CAS (т.н. CAS2), которая могла бы менять одновременно 8 байт для 32-битной и 16 байт для 64-битной платформы. Такие инструкции в x86 есть, но связываться с ними совсем не хочется. Это совсем не common path, а редко используемые инструкции. Поэтому у тех, кто их таки использует велика вероятность стать экспертом по особенностям реализации cmpxchg8b на каком-нибудь новом или маргинальном процессоре типа VIA. Еще в gamedev-е меня научили тратить время более продуктивным способом, чем искать ошибки в hardware/драйверах. Можно, конечно, реализовать и без CAS2 и даже есть такая бесплатная "реализация". Однако, так как их замена CAS2 не является атомарной, то и вся эта бесплатная "реализация" некорректна.

1а. Т.к. CAS2 редко где есть, то расположим counter в младших битах указателя. Без комментариев.

1б. Используем в качестве указателя 32-битное число. Скажем, в старших битах индекс в массиве, в младших - counter. Уже лучше, но тогда нам нужно либо ограничить сверху количество Node, которые потребуются программе (если закажем мало - стремно, могут кончится, если много - жалко память), либо нужен lock-free dynamic array. К тому же counter может wrap-нуться...

2.
Hazard pointers - вроде изобретение небезызвестного Doug Lea. Рабочая идея, но треды, которые знают про другие треды... Пожалуйста, без меня, я такого с memory manager`ом уже наелся :)

3. Cнабдить каждый Node RefCounter-ом. Изобретение товарища Valois.

Изобретении Valois-a мне сначала понравилось. Выглядит самым простым решением - добавляем в Node RefCount. Чтение указателей на Node реализуется с помощью функции SafeRead:

Node *SafeRead(Node *volatile*ptr)
    for(;;) {
        Node * volatile res = *ptr;
        if (res == 0)
            return 0;
        atomic_add(res->RefCount, 1);
        if (res == *ptr)
            return res;
        else
            atomic_add(res->RefCount, -1);
    }
_Winnie C++ Colorizer

Т.е. если несколько объектов прочитали в Pop() указатель на один и тот же объект, то объект не будет освобожден, пока все треды не прекратят на него смотреть. ABA удалось избежать. Открываем шампанское!

Закрываем шампанское. Теперь мы можем прибавлять RefCount объекту, который был освобожден в соседнем треде и уже болтается во free memory! Для этого переключение потоков должно произойти между "res = *ptr" и "atomic_add()". Мы, конечно, после этого вернем все "на место" и вычтем прибавленную единичку, но какие волшебные баги это может породить, если память из под Node была использована в другом месте мне даже представить страшно. То ли я чего-то не понял, то ли товарищ Valois предлагает форменную диверсию или забыл сообщить, что под Node надо сделать выделенный пул и выделять память под Node только из него. Да и race-condition-ами пугают.

Посмотрев на все это и отчаявшись найти короткий кусок кода, который делает только то, что нужно и ничего больше, напесал свой. Для решения проблемы ABA я сделал RefCount на весь стек. Память будет освободжаться только когда никто не использует стек. Конечно, если все треды только и делают, что лезут в стек такое никогда не случится и память будет поглощаться неограниченно. Однако, в моем случае использование таких стеков гораздо менее напряженное. Код здесь. Если вы вдруг найдете ошибку в этом коде буду очень вам признателен.

Рассмотренные нами реализации стека - lock free, но вовсе не wait-free, как могло показаться. Ведь в них таки есть циклы и они могут в них крутиться, а wait-free гарантирует выполнение за конечное число шагов. Ну что, хотите по-настоящему? Тогда вас заинтересуют wait-free алгоритмы (подробнее про различия).

Например, wait free stack по имени elimination-backoff stack

Удачи!

Update Ошибку наконец нашли, ура! Исправить, имхо, таки можно, например, так

Comments

Page 1 of 2
<<[1] [2] >>
not yet :)
интересно, но есть и минусы.
во-первых, для новых элементов стэка вызывается new, я не уверен, но вроде два потока не смогут выполнить обращение к memory manager одновременно (может не на всех ОС).
во-вторых, всё же эффективнее обойтись без swap, а делать изменение объекта in-place. в некоторых условиях один поток in-place обгонит 2 и более со swap.
в-третьих, синхронизация - неизбежное зло. на мой взгляд выход в том, чтобы минимизировать необходимость синхронизации на уровне алгоритма. часто можно написать алгоритм, который будет гарантировать, что одновременного обращения к одному элементу быть не может, либо это встречается крайне редко и вынесено в отдельный случай. но тут всё зависит от специфики задачи. при data-параллелизме это относительно просто, а при function-параллелизме сложнее.
это также завязано с вопросом на каком уровне лучше параллелить приложение. в gamedev этот выбор ограничен, т.к. используется много библиотек, где уже ничего не поменять.
я работаю в HPC, есть больше свободы, data-параллелизм и проблема синхронизации стоит не так остро.
Забавно, что lock free становится единственным способом синхронизации в GPGPU, сотни тредов останавливать на локе совсем западло.
И в CUDA, и в DX11 есть CAS (а хорошо бы CAS2).

А жопа-кеды это не я, это Давыдов (http://davydov.blogspot.com/).
Мониторы (локи) вообще мутанты придумали.
Мне всегда нравился CSP, и не менее всегда нравились LL-SC/CAS2.

Локи кстати как рефкаунты - они мозг разжижают и не дают выползти из локальной оптимизации.
> если обломалась, то кто-то успел раньше нас и нам надо начинать с начала.

Таким образом в случае сильной нагрузки можем получить ситуацию, когда N-k тредов копируют, копируют и копируют.
Экспоненциально причём.
Но это не отменяет моей нелюбви к "мониторам"!
Отличное начало, Андрей, спасибо! :)
Спасибо! :)
Убогий язык C++, в котором нет нормальных библиотек :). Вот в java есть java.util.concurrent.ConcurrentLinkedQueue.
А тут товарищи зажигают с hash_maps:
http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html
Убогий язык Джава, в котором нет нормальных шаблонов? :-)
Можно немного оффтоповый и банальный вопрос. Не очень как-то пока удалось понять в какую сторону копать.
Допустим, есть дерево в каждом узле хранится много результатов, зависящих от результатов, хранящихся в дочерних узлах. Дерево пересчитывается много раз для разных параметров. Как такое лучше параллелить? Дерево может быть сильно несбалансированным, так что вычисление в разных тредах разных ветвей выглядит не слишком привлекательно. Так как дерево предполагается неглубоким, есть вариант тупо создать каждому треду свою копию дерева, и считать в разных тредах для разных входных параметрах. В какую сторону тут лучше смотреть 8) ? Спасибо.
ну я небольшой специалист по этой теме. Думаю, зависит от размера дерева, времени, которое нужно для просчета одного узла итп. Если можно в разных тредах считать разные копии дерева, то это будет явно проще всего. А раз проще, то и быстрее в изготовлении и надежнее :)
хорошо тебе. мои-то читатели считают, что волшебное слово synchronized решает все пробемы.

но тут такое дело. если мы бьёмся за latency (например, нам нужно быстро-быстро перерисовывать сложный объект), то такой подход имеет смысл. то есть мы жертвуем overhead-ом того, что какие-то треды считают впустую, чтобы добиться latency. если же нас интересует throughput - то есть, когда все ядра и так гарантированно делают что-то полезное, то от такого подхода будет только хуже - поскольку часть работы теперь будет выкидываться в помойку.
согласен
Забавно, я подобное читал в Game Programming Gems, но у тебя тема полнее раскрыта.
Спасибо.
да я и не претендовал вообще-то, теме сто лет в обед. По сцылке решение с CAS2, которое мне не нравится, если вы пост читали :) и только под 32bit, да и сорцы не целиком.
ring buffer, да. в движке за миллион вроде он и поюзан. Когда одна нить push другая pop - отличная вещь. Мне не подошел, писателей больше одного.

правильный new/delete не делает lock. При желании можно сделать custom alloc, но зачем? Это место не тормозит, оно просто дает шанс системе отобрать управление у потока, если использовать critical section. Задача - не давать системе шанса забрать управление :)

Возможно, для вас станет открытием, что при реализации busy wait lock-а лучше делать предварительную проверку с помощью volatile read на предмет возможности захвата перед попыткой собственно захвата с помощью locked инструкции.

Получается, что volatile read (в ассемблере?) выставляет memory barrier?
Push(T *obj)
    n = new Node(obj);
    n->Val = obj;
    do {
        n->Next = Top;
     } while (!CAS(&Top, n, n->Next));

А чем цикл, который жрет CPUшные ресурсы, лучше чем засыпание потока?
PS: Кстати, мне кажется подобный подход к синхронизации чем-то похож на многоверсионность.

Edited at 2008-10-19 09:29 pm (UTC)
усыпят тред сразу надолго - как минимум квант шедулера. а тут есть надежда, что мы немножко в цикле покрутимся и ресурс освободится. для приведенного тут стека это весьма вероятное развитие событий. в общем случае хорошая реализация (e.g. memory manager в NT) крутится в цикле не больше нного числа раз и потом засыпает.
CAS2 вообще не от всего помогает. допустим второй тред тупо сделал Pop() и освободил элемент. после этого он выделил эту память под что-то другое. теперь там может быть *вообще все что угодно*. то есть t->Next с какой-то вероятностью совпадет с &Top и капец.
Ага, но мы же заменяем Top, чтобы были кеды нужно, чтобы каунтер совпал тоже. Каунтер совпасть может, но если он 32-битный, то ждать долго, а если 64-битный, то я готов ставить все деньги, что wrap-нутся не успеет :)
Page 1 of 2
<<[1] [2] >>
me

April 2014

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
27282930   
Powered by LiveJournal.com