Исследование: неблокирующие параллельные алгоритмы сильно «перевыполняют» свои минимальные гарантии

Один из наиболее распространенных подходов к разработке параллельных программ состоит в использовании алгоритмов без блокировок (lock-free), поскольку они относительно просты в реализации и во многих случаях позволяют преобразовать линейный код в параллельный автоматически. Но минимальные гарантии lock-free весьма скудны: за фиксированное время гарантируется прогресс всего одного потока. Альтернативой является применение алгоритмов без ожидания (wait-free), которые гарантируют прогресс всех потоков, но реализация их крайне сложна, поэтому ими пользуются редко.

Между тем, исследователи из Массачусетского технологического института, Microsoft и Техниона показали, что в большом числе реальных применений алгоритмы без блокировок проявляют себя не хуже, чем алгоритмы без ожидания.

Как объясняют авторы исследования, процесс назначения потоков кода ядрам, являющийся продуктом «сложного сочетания задержек и правил планирования», в конечном итоге сильно похож на случайный. Они смоделировали планирование потоков так, чтобы в любое время была вероятность назначения новой нити любому ядру, и оказалось, что с таким «случайным» планировщиком широкий круг алгоритмов lock-free дает гарантии быстродействия не хуже, чем у wait-free.

Затем смоделировали худший случай — когда несколько ядер пишут данные в одну и ту же область памяти, и одному ядру это постоянно удается раньше остальных. Но даже в этом варианте количество ядер, делавших прогресс, никогда не было меньшим, чем квадратный корень из числа ядер, которым назначили потоки, — то есть все равно лучше, чем минимальная гарантия lock-free.