Синхронизация без ожидания: различия между версиями

Самым значительным шагом в направлении практичности стало рассмотрение более слабых условий прогресса. Пока теоретики работали над реализациями без ожидания, более прагматичные исследователи искали неблокирующие реализации совместно используемых объектов. Неблокирующая реализация гарантирует, что после конечного количества шагов любой операции эта операция будет завершена. В отличие от алгоритмов без ожидания, в данном случае принципиально возможна ситуация, когда одна операция в структуре данных без блокировок будет постоянно «голодать» из-за поведения остальных. Однако на практике такая ситуация встречается редко, в частности, потому, что техники контроля над конкуренцией – такие как экспоненциальная задержка [1] – часто используются для подавления конкуренции при ее возникновении, что делает повторяющееся вмешательство еще менее вероятным. Таким образом, отсутствие сильной гарантии прогресса (такой как свобода от ожиданий) на практике нередко оказывается допустимым.

Сделанное Херлихи и др. [15] наблюдение, заключающееся в том, что более слабые условия прогресса позволяют создавать более простые и практичные алгоритмы, позволило Херлихи определить еще более слабое условие: алгоритм без препятствий не гарантирует, что операция завершится, за исключением случаев, если она не встречает препятствий от других операций. По сравнению с алгоритмами без блокировки алгоритмы без препятствий проще в разработке, проще по структуре и быстрее работают в условиях общего случая без конкуренции. Обратной стороной этих преимуществ алгоритмов без препятствий является потенциальная возможность динамической взаимоблокировки (livelock), при которой две или несколько операций постоянно вмешиваются в работу друг друга в бесконечном цикле. Эта проблема имеет не только теоретическую значимость; она встречалась и на практике [16]. К счастью, можно довольно легко устранить возможность взаимоблокировки при помощи механизмов контроля конкуренции, способных вмешиваться в процесс выполнения операций во избежание взаимного вмешательства.