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

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

Основополагающая статья Мориса Херлихи «Синхронизация без ожидания» [12] была посвящена проблеме реализации параллельных структур данных без ожидания, таким образом, чтобы каждая операция на этой структуре данных завершалась за конечное количество шагов вызывающим ее потоком, независимо от того, насколько быстро или медленно выполняются другие потоки и даже от того, не происходит ли у некоторых или всех из них окончательной остановки. Реализации, основанные на блокировках, не являются вариантами без ожидания, поскольку в период, когда один поток удерживает блокировку, другие могут предпринять неограниченное количество шагов в ожидании блокировки. Требование реализации без ожидания позволяет потенциально избавиться от присущих блокировкам недостатков.

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

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