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

Кроме того, Херлихи показал, что решение задачи о консенсусе может использоваться для реализации без ожидания любого совместно используемого объекта и, таким образом, для этой цели подойдет любой универсальный примитив. Он продемонстрировал свою идею при помощи так называемого ''универсального построения'', которое принимает на вход последовательный код объекта и создает реализацию без ожидания для этого объекта, используя консенсус для разрешения состояния гонки между параллельными операциями. Несмотря на важные практические последствия этого результата, само по себе универсальное построение оказалось весьма непрактичным. Основная идея заключалась в построении списка операций, используя консенсус для определения порядка операций, и последующем итерационном выполнении потоков над списком, применяющих операции для определения текущего состоянии объекта. Построение требовало <math>O(N^3) \;</math> памяти, чтобы гарантировать достаточное количество сохраненных операций для определения текущего состояния. Оно также оказалось очень медленным, из-за чего многим потокам приходилось заново вычислять одну и ту же информацию, что препятствовало распараллеливанию операций.