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

Херлихи установил ''иерархию'' примитивов синхронизации в соответствии с их числом консенсуса. Он показал, что (1) число консенсуса регистров типа чтение-запись равно 1 (в силу чего задача консенсуса без ожидания не может быть решена даже для двух потоков), (2) число консенсуса для стеков и очередей FIFO равно 2, (3) существуют так называемые универсальные примитивы с числом консенсуса, равным 1. Типичными примерами таких примитивов являются сравнение с обменом (compare-and-swap, CAS) и подход с «условной записью» (load-linked/store-conditional, LL/SC).

Кроме того, Херлихи показал, что решение задачи о консенсусе может использоваться для реализации без ожидания любого совместно используемого объекта и, таким образом, для этой цели подойдет любой универсальный примитив. Он продемонстрировал свою идею при помощи так называемого универсального построения, которое принимает на вход последовательный код объекта и создает реализацию без ожидания для этого объекта, используя консенсус для разрешения состоянии гонки между параллельными операциями. Несмотря на важные практические последствия этого результата, само по себе универсальное построение оказалось весьма непрактичным. Основная идея заключалась в построении списка операций, использовании консенсуса для определения порядка операций и последующем итерационном выполнении потоков над списком, применяющих операции для определения текущего состоянии объекта. Построение требовало O(N3) памяти, чтобы гарантировать достаточное количество сохраненных операций для определения текущего состояния. Оно также оказалось очень медленным, из-за чего многим потокам приходилось заново вычислять одну и ту же информацию, что препятствовало распараллеливанию операций.