Waitfree
Каждый поток продвигается вперед не зависимо от внешних факторов (конкуренции со стороны других потоков, факта блокирования других потоков). Это самая сильная гарантия. Обычно это означает, что используются только такие примитивы как atomic_exchange, atomic_increment, atomic_fetch_and_add (InterlockedExchange, InterlockedIncrement, InterlockedExchangeAdd), и в алгоритме нет циклов, на выполнение которых могут повлиять другие потоки. atomic_compare_exchange (InterlockedCompareExchange) обычно не используется, т.к. с ним обычно связан цикл вида "выполнять atomic_compare_exchange, пока он не будет выполнен успешно".
Пример waitfree алгоритма:
void increment_reference_counter(rc_base* obj)
{
atomic_increment(obj->rc);
}
void decrement_reference_counter(rc_base* obj)
{
if (0 == atomic_decrement(obj->rc))
delete obj;
}
Как видно, любой поток может выполнить эти функции за конечное число шагов, не зависимо ни от чего.
Lockfree
Система в целом продвигается вперед. При этом каждый отдельный поток может не совершать продвижения вперед. Это более слабая гарантия, чем wait-free. Обычно используется примитив atomic_compare_exchange (InterlockedCompareExchange).
Пример lockfree алгоритма:
void stack_push(stack* s, node* n)
{
node* head;
do { head = s->head; n->next = head; } while (!atomic_compare_exchange(s->head, head, n));
}
Как видно, любой поток может "крутиться" в этом цикле теоретически бесконечно. НО любой повтор этого цикла означает, что какой-то другой поток *успешно* выполнил свою операцию. И никакой заблокированный/прерванный поток *не* может препятствовать продвижению других потоков. Отсюда следует, что система в целом продвигается вперед не зависимо ни от чего.
Obstruction-free
Поток продвигается вперед, только если не встречает конкуренции со стороны других потоков. В частности это означает, что при сильной конкуренции возможно *никакой* поток не будет совершать продвижения. Т.е. система будет находиться в т.н. livelock. Это самая слабая гарантия. Этот класс алгоритмов может показаться немного странным, поэтому тут стоит заметить, что (1) заблокированные/прерванные потоки не могут препятствовать прогрессу других потоков, и (2) obstruction-free алгоритмы могут быть более быстрые, чем lockfree.
Простого примера тут не привести, поэтому отсылаю интересующихся к оригиналу:
Obstruction-Free Synchronization: Double-Ended Queues as an Example
Mutex-based
Ну и собственно все эти алгоритмы противопоставляются mutex-based алгоритмам:
Система в целом может *не* продвигаться вперед. Например, поток прерван внутри критической секции, этот поток может заблокировать общесистемный прогресс, т.е. никакой выполняющийся поток не может выполнить никаких полезных действий. Или например, при использовании mutex-based алгоритмов возможен т.н. deadlock, очевидно, что при возникновении deadlock система не совершает прогресса.
Производительность/масштабируемость
Самое интересное — до этого момента я не сказал ни слова ни о производительности, ни о масштабируемости. Всё правильно — все эти слова ни об этом. Они о гарантиях, которые я описал выше. Так как же lockfree (waitfree, obstruction-free) соотносится с производительностью? Это зависит от конкретного алгоритма — они могут быть как быстрее/лучше масштабироваться, так и медленнее/хуже масштабироваться.
Функции increment_reference_counter()/decrement_reference_counter() скорее всего будут быстрее аналогичного mutex-based алгоритма, т.к. хотя бы одну тяжелую атомарную операцию вход/выход из критической секции содержать тоже будет, но там ещё будет собственно полезная работа + возможность заблокироваться/спин-ожидание.
Зато большинство lockfree алгоритмов для сложных структур данных (двусвязные списки) будут медленнее аналогичных mutex-based алгоритмов, т.к. будут содержать больше тяжелых атомарных операций (2-5). Но хотя тут сложный вопрос, т.к. mutex-based алгоритм будет вызывать много блокирования под нагрузкой, но с другой стороны мьютексы можно партицировать — т.е. имеем не один "большой" мьютекс, а много "маленьких", но с другой стороны, если у нас много "маленьких" мьютексов, то и операций захвата/освобождения будет больше. Т.е. тут каждый случай надо рассматривать в отдельности.
И тут я имею в виду только операции модификации, т.к. существует такая замечательная вещь как lockfree reader pattern, которая, кстати, может сочетаться и с mutex-based writer частью. Но это уже отдельная история.
Atomic-free
Т.о. lockfree это не о производительности. Есть класс алгоритмов синхронизации, которые именно о производительности. Они разрабатываются именно с мыслью не обеспечения каких-то гарантий, а с мыслью обеспечения максимальной производительности и линейной масштабируемости на многопроцессорных/многоядерных системах. Как следствие такие алгоритмы вполне могут содержать и mutex-based части. К сожалению общепринятого слова для них, насколько я знаю, нет. Поэтому их часто и называют lockfree, в смысле "не mutex-based". Я обычно называю такие алгоритмы atomic-free, с целью подчеркнуть факт минимизации тяжелых операций. Насколько я помню, термин почерпнут в какой-то работе David Dice.
Почему я всегда вместе со словом "производительность" употребляю слово "масштабируемость". Масштабируемость — это очень важный аспект алгоритмов синхронизации в контексте многопроцессорных/многоядерных систем, но он полностью отсутствует на однопроцессорных машинах. Зачастую у примитивов синхронизации следующий паттерн поведения. На однопроцессорной машине он выполняется Х времени, на двухпроцессорной — 2*Х времени, на четырех-процессорной — 10*Х времени и т.д. Поэтому в контексте многопроцессорности очень важно, что бы алгоритм не деградировал таким образом.
Для факультативного чтения могу предложить:
или более свежий:
Concurrent Programming Without Mutexes
Обе работы написаны KEIR FRASER и TIM HARRIS, и содержат достаточно обширную "вводную часть" с освещением всех базовых вопросов.