Типы алгоритмов для неблокирующей синхронизации

В работах [2,10] приводятся описания трёх типов алгоритмов для неблокирующей синхронизации.

Wait-free

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

Каждый поток продвигается вперед не зависимо от внешних факторов (конкуренции со стороны других потоков, факта блокирования других потоков). Это самая сильная гарантия. Обычно это означает, что используются только такие примитивы, как atomic_exchange, atomic_increment, atomic_fetch_and_add (InterlockedExchange, InterlockedIncrement, InterlockedExchangeAdd), и в алгоритме нет циклов, на выполнение которых могут повлиять другие потоки. Такие примитивы, как atomic_compare_exchange (InterlockedCompareExchange) обычно не используется, так как с ним обычно связан цикл вида «выполнять atomic_compare_exchange, пока он не будет выполнен успешно».

Пример wait-free алгоритма:

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;

}

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

Lock-free

Lock-free алгоритмом или алгоритмом без блокировок называется такой алгоритм, который гарантирует, что в течении времени, за которое некий программный поток выполнит некое известное ограниченное число шагов в операции над таким объектом или структурой, некий, возможно, другой поток обязательно завершит операцию над этим объектом или структурой.

Иными словами данный алгоритм гарантирует прогресс как минимум для одного потока. Другие потоки могут ждать, но один поток минимум должен прогрессировать. Система в целом продвигается вперед. Это более слабая гарантия, чем wait-free. Обычно используется примитив atomic_compare_exchange (InterlockedCompareExchange).

Пример lock-free алгоритма:

void stack_push(stack* s, node* n)

{

node* head;

do

{

head = s->head;

n->next = head;

}

while (!atomic_compare_exchange(s->head, head, n));

}

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

Дата добавления: 2015-11-14