Неблокирующие методы бесконфликтного доступа к памяти

Кроме обозначенной в предыдущем параграфе проблемы увеличения времени отклика потоков при увеличении количества запросов на выполнение КС использование блокировок может привести к ряду других проблем, которые подробно описаны в литературе (например [ehter]). Эти проблемы в первую очередь связаны с возможным нарушением предоставляемых используемыми средствами бесконфликтного доступа к памяти гарантий прогресса взаимодействующих в системе потоков. Крайний случай нарушения таких гарантий — возникновение ситуации мертвой блокировки (взаимоблокировки), когда система полностью перестает прогрессировать. Даже если сам алгоритм или механизм взаимного исключения удовлетворяет условию отсутствия мертвой блокировки (см. параграф 1.3), то при наличии нескольких ресурсов и соблюдении ряда других известных условий возможна ситуация мертвой блокировки по порядку блокирования. Существующие решения, устраняющие возможность возникновения мертвой блокировки, требуют как дополнительных трудозатрат со стороны программиста, так и влияют на производительность. Ряд других известных проблем: конвоирование, инверсия приоритета, живые блокировки (англ. livelock), приводят к замедлению прогресса в целом, что в конечном счете влияет на производительность всей системы. Кроме того, проблемой при использовании блокирующих методов бесконфликтного доступа может стать использование слишком грубой гранулярности (англ. coarse-grained) при блокировании, что приводит к излишней синхронизации неконфликтующих операций и, следовательно, ухудшению масштабируемости и потере в производительности. Использование мелко-гранулированных (англ. fine-grained) блокировок решает данную проблему, создавая ряд других [ehter, fraser].

Эти и другие проблемы блокирующих методов бесконфликтного доступа к памяти стали причиной активного исследования и развития неблокирующих методов. Существующие неблокирующие методы предоставляют более строгие по сравнению с блокирующими методами гарантии прогресса системы, которые обеспечивают продвижение всех потоков системы даже при условии остановки, либо замедления любого из потоков. Выделяют [ehter, fraser] следующие гарантии прогресса (живость), которые может предоставлять неблокирующий алгоритм:

· свобода от ожидания (англ. wait-freedom) — самая строгая и трудно реализуемая на практике гарантия, в случае предоставления которой каждый поток программы, реализующей неблокирующий алгоритм, выполняется в любом случае за конечное число шагов, даже при условии возникновения конфликтов по данным с другими потоками. При выполнении условия свободы от ожидания для любой операции потока может быть подсчитано наихудшее время выполнения, а сам поток никогда не попадет в ситуацию перманентной живой блокировки;

· свобода от блокировок (англ. lock-freedom) — гарантируется, что как минимум один поток выполнится за конечное число шагов, даже при условии возникновения конфликтов по данным с другими потоками, тем самым вся система в целом может выполняться;

· свобода от преград (англ. obstruction-freedom) — самая слабая форма гарантии прогресса, при соблюдении которой поток выполняется за собственное определенное конечное число шагов, только при условии отсутствия конфликтов по данным с другими потоками, тем самым допускается ситуация живой блокировки.

Неблокирующий алгоритм может предоставлять любую гарантию прогресса. При этом чем строже предоставляемая гарантия, тем большую цену в плане потери общей производительности приходится платить. Основная проблема таких алгоритмов — это их сложность, что, в частности, приводит к трудности их верификации и валидации и делает необходимым использование формальных методов и инструментов верификации, описываемых в данном пособии. Сложность эта возникает из-за того, что неблокирующие алгоритмы — это в первую очередь различные эвристики, написанные с применением аппаратно-зависимых атомарных операций. Кроме данной проблемы с неблокирующими алгоритмами связан ряд других: проблема ABA [dechev], проблема управления динамической памятью [shann] и так называемая проблема “пинг-понга” — создание большой нагрузки на шину памяти при условии использования в алгоритмах спин-блокировок или активного ожидания.

Первоначально большая часть исследований в данной области была посвящена созданию эффективных неблокирующих алгоритмов и протоколов для различных часто используемых структур данных: стэка [hendler], очереди [kogan], хэш-таблицы [shalev]. Однако описанные в подобных исследованиях приемы трудно применимы при разработке других алгоритмов, особенно в распределенных системах — они достаточно сложны и узкоспециализированны (рассчитаны на конкретную структуру данных).

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