Линеаризуемость - Linearizability

Серым цветом обозначена линейная под-история, процессы, начинающиеся в b, не имеют линеаризуемой истории, потому что b0 или b1 могут завершиться в любом порядке до того, как произойдет b2.

В параллельное программирование, операция (или набор операций) линеаризуемый если он состоит из упорядоченного списка событий вызова и ответа (обратные вызовы ), который можно расширить, добавив такие события ответа, как:

1. Расширенный список можно переформулировать как последовательную историю ( сериализуемый ), и
2. Эта последовательная история является подмножеством исходного нерасширенного списка.

Неформально это означает, что неизмененный список событий линеаризуем. если и только если его призывы были сериализуемый, но некоторые ответы из расписания сериалов еще не вернулись.^[1]

В параллельной системе процессы могут обращаться к общему объекту одновременно. Поскольку несколько процессов обращаются к одному объекту, может возникнуть ситуация, в которой, пока один процесс обращается к объекту, другой процесс изменяет его содержимое. Этот пример демонстрирует необходимость линеаризуемости. В линеаризуемой системе, хотя операции над общим объектом перекрываются, кажется, что каждая операция выполняется мгновенно. Линеаризуемость - это строгое условие корректности, которое ограничивает возможные выходы, когда к объекту обращаются одновременно несколько процессов. Это свойство безопасности, которое гарантирует, что операции не завершатся неожиданным или непредсказуемым образом. Если система линеаризуема, это позволяет программисту рассуждать о системе.^[2]

История линеаризуемости

Линеаризуемость была впервые представлена ​​как модель согласованности от Herlihy и Крыло в 1987 году. Он включал в себя более ограничительные определения атомарной операции, такие как «атомарная операция - это операция, которая не может быть (или не может быть) прервана параллельными операциями», которые обычно расплывчаты относительно того, когда операция считается началом и завершением.

Атомарный объект можно понять сразу и полностью из его последовательного определения, как набор операций, выполняемых параллельно, которые всегда кажутся происходящими одна за другой; никаких несоответствий возникнуть не может. В частности, линеаризуемость гарантирует, что инварианты системы наблюдаемый и сохранился всеми операциями: если все операции по отдельности сохраняют инвариант, система в целом будет.

Определение линеаризуемости

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

А история это последовательность призывы и ответы сделано из объекта набором потоки или процессы. Вызов можно рассматривать как начало операции, а ответ - как сигнализируемый конец этой операции. Каждый вызов функции будет иметь последующий ответ. Это можно использовать для моделирования любого использования объекта. Предположим, например, что два потока, A и B, оба пытаются захватить блокировку, отступая, если она уже занята. Это можно было бы смоделировать как оба потока, вызывающие операцию блокировки, затем оба потока получают ответ, один успешный, другой нет.

Вызывает замок

B вызывает замок

Получает "неудавшийся" ответ

B получает "успешный" ответ

А последовательный история - это история, в которой все вызовы имеют немедленные ответы, то есть вызов и ответ считаются происходящими мгновенно. Последовательная история должна быть тривиальной для рассуждений, поскольку в ней нет реального параллелизма; предыдущий пример не был последовательным, и поэтому о нем трудно рассуждать. Вот тут-то и появляется линеаризуемость.

История ${\displaystyle \sigma }$ является линеаризуемый если существует такой линейный порядок выполненных операций, что:

1. За каждую выполненную операцию в ${\displaystyle \sigma }$, операция возвращает тот же результат при выполнении, что и операция, если бы все операции выполнялись одна за другой в порядке ${\displaystyle \sigma }$.
2. Если операция op₁ завершает (получает ответ) до операции₂ начинается (вызывает), затем op₁ предшествует op₂ в ${\displaystyle \sigma }$.^[1]

Другими словами:

• его вызовы и ответы можно переупорядочить, чтобы получить последовательную историю;
• что последовательная история верна в соответствии с последовательным определением объекта;
• если ответ предшествовал вызову в исходной истории, он все равно должен предшествовать ему при последовательном изменении порядка.

(Обратите внимание, что первые два пункта соответствуют сериализуемость: кажется, что операции выполняются в определенном порядке. Это последний пункт, который уникален для линеаризуемости и, таким образом, является основным вкладом Херлихи и Уинга.)^[1]

Давайте рассмотрим два способа изменить порядок блокировки в приведенном выше примере.

Вызывает замок

Получает "неудавшийся" ответ

B вызывает замок

B получает "успешный" ответ

Изменение порядка вызова B под ответом A дает последовательную историю. Об этом легко рассуждать, так как теперь все операции происходят в очевидном порядке. К сожалению, это не соответствует последовательному определению объекта (не соответствует семантике программы): A должен был успешно получить блокировку, а B должен был впоследствии прерваться.

B вызывает замок

B получает "успешный" ответ

Вызывает замок

Получает "неудавшийся" ответ

Это еще одна правильная последовательная история. Это тоже линеаризация! Обратите внимание на то, что определение линеаризуемости исключает изменение порядка только ответов, предшествующих вызовам; так как исходная история не имела ответов перед вызовами, мы можем изменить ее порядок по своему желанию. Следовательно, исходная история действительно линеаризуема.

Объект (в отличие от истории) является линеаризуемым, если все действительные истории его использования могут быть линеаризованы. Обратите внимание, что это утверждение намного сложнее доказать.

Линеаризуемость и сериализуемость

Рассмотрим следующую историю двух объектов, взаимодействующих с замком:

Вызывает блокировку

А успешно блокирует

B вызывает разблокировку

B успешно разблокируется

Вызывает разблокировку

А успешно разблокирует

Эта история недействительна, потому что есть точка, в которой и A, и B удерживают блокировку; более того, его нельзя переупорядочить в действительную последовательную историю без нарушения правила упорядочивания. Следовательно, он не поддается линеаризации. Однако при сериализуемости операцию разблокировки B можно перенести в перед Исходная блокировка A, которая является действительной историей (при условии, что объект начинает историю в заблокированном состоянии):

B вызывает разблокировку

B успешно разблокируется

Вызывает блокировку

А успешно блокирует

Вызывает разблокировку

А успешно разблокирует

Такое переупорядочение целесообразно при условии, что нет альтернативных средств связи между A и B. Линеаризуемость лучше, если рассматривать отдельные объекты по отдельности, поскольку ограничения на переупорядочение гарантируют, что несколько линеаризуемых объектов, рассматриваемых как единое целое, по-прежнему линеаризуемы.

Точки линеаризации

Это определение линеаризуемости эквивалентно следующему:

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

Эту альтернативу обычно гораздо проще доказать. Кроме того, пользователю гораздо проще рассуждать о нем, во многом благодаря его интуитивности. Это свойство происходить мгновенно или неделимо приводит к использованию термина атомный как альтернатива более длинному «линеаризуемому».^[1]

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

Примитивные атомарные инструкции

^{[соответствующий? ]}

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

• атомарное чтение-запись;
• атомарный своп (инструкция RDLK в некоторых Мэйнфреймы Берроуза, и XCHG инструкция x86 );
• испытать и установить;
• получить и добавить;
• сравнивать и менять местами;
• ссылка загрузки / магазин-условный.

Наиболее^{[нужна цитата ]} процессоры включать операции хранения, которые не являются атомарными по отношению к памяти. К ним относятся хранилища нескольких слов и строковые операции. Если прерывание с высоким приоритетом происходит, когда часть хранилища завершена, операция должна быть завершена, когда возвращается уровень прерывания. Подпрограмма, обрабатывающая прерывание, не должна обращаться к изменяемой памяти. Это важно учитывать при написании процедур обработки прерываний.

Когда есть несколько инструкций, которые должны быть выполнены без прерывания, используется инструкция ЦП, которая временно запрещает прерывания. Это должно быть ограничено лишь несколькими инструкциями, а прерывания должны быть повторно разрешены, чтобы избежать неприемлемого времени реакции на прерывания или даже потери прерываний. Этого механизма недостаточно в многопроцессорной среде, поскольку каждый ЦП может вмешиваться в процесс независимо от того, возникают прерывания или нет. Далее, при наличии конвейер команд, бесперебойные операции представляют угрозу безопасности, поскольку они потенциально могут быть связаны в бесконечный цикл создать отказ в обслуживании, как в Cyrix coma ошибка.

В Стандарт C и SUSv3 предоставлять sig_atomic_t для простых атомарных операций чтения и записи; не гарантируется, что увеличение или уменьшение будет атомарным.^[3] Более сложные атомарные операции доступны в C11, который обеспечивает stdatomic.h. Компиляторы используют аппаратные функции или более сложные методы для реализации операций; пример - libatomic GCC.

В Набор инструкций ARM обеспечивает LDREX и СТРЕКС инструкции, которые можно использовать для реализации доступа к атомной памяти с помощью эксклюзивные мониторы реализован в процессоре для отслеживания обращений к памяти по определенному адресу.^[4] Однако если переключатель контекста происходит между звонками в LDREX и СТРЕКСв документации отмечается, что СТРЕКС завершится ошибкой, указывая, что операцию следует повторить.

Атомарные операции высокого уровня

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

Другой подход, одобренный исследователями (но пока не широко используемый в индустрии программного обеспечения), заключается в разработке линеаризуемого объекта с использованием собственных атомарных примитивов, предоставляемых оборудованием. Это может увеличить доступный параллелизм и минимизировать затраты на синхронизацию, но требует математических доказательств, которые показывают, что объекты ведут себя правильно.

Перспективным гибридом этих двух является обеспечение транзакционная память абстракция. Как и в случае с критическими секциями, пользователь отмечает последовательный код, который должен выполняться изолированно от других потоков. Затем реализация гарантирует, что код выполняется атомарно. Этот стиль абстракции распространен при взаимодействии с базами данных; например, при использовании Spring Framework, аннотирование метода с помощью @Transactional гарантирует, что все взаимодействия с базой данных будут происходить за один транзакция базы данных. Транзакционная память идет еще дальше, гарантируя, что все взаимодействия с памятью происходят атомарно. Как и в случае транзакций с базой данных, возникают проблемы, связанные с составом транзакций, особенно транзакций с базой данных и в памяти.

Распространенной темой при разработке линеаризуемых объектов является предоставление интерфейса по принципу «все или ничего»: либо операция завершается полностью, либо терпит неудачу и ничего не делает. (КИСЛОТА базы данных называют этот принцип атомарность.) Если операция завершилась неудачно (обычно из-за одновременных операций), пользователь должен повторить попытку, обычно выполняя другую операцию. Например:

• Сравнить и обменять записывает новое значение в место, только если его содержимое совпадает с предоставленным старым значением. Это обычно используется в последовательности чтение-изменение-CAS: пользователь считывает местоположение, вычисляет новое значение для записи и записывает его с помощью CAS (сравнение и замена); если значение изменяется одновременно, CAS откажет, и пользователь попытается снова.
• Ссылка загрузки / магазин-условно кодирует этот шаблон более прямо: пользователь считывает местоположение с помощью load-link, вычисляет новое значение для записи и записывает его с помощью store-conditional; если значение изменилось одновременно, SC (условное сохранение) завершится ошибкой, и пользователь попытается снова.
• В транзакция базы данных, если транзакция не может быть завершена из-за параллельной операции (например, в тупик ), транзакция будет прервана, и пользователю придется повторить попытку.

Примеры линеаризуемости

Счетчики

Чтобы продемонстрировать силу и необходимость линеаризуемости, мы рассмотрим простой счетчик, который можно увеличивать в различных процессах.

Мы хотели бы реализовать объект счетчика, к которому могут обращаться несколько процессов. Многие распространенные системы используют счетчики, чтобы отслеживать, сколько раз произошло событие.

К объекту счетчика могут обращаться несколько процессов, и он имеет две доступные операции.

1. Приращение - добавляет 1 к значению, хранящемуся в счетчике, возвращает подтверждение
2. Чтение - возвращает текущее значение, хранящееся в счетчике, не изменяя его.

Мы попытаемся реализовать этот объект счетчика, используя общие регистры

Наша первая попытка, которая, как мы увидим, является нелинейной, имеет следующую реализацию, использующую один общий регистр для процессов.

Неатомный

Наивная, неатомарная реализация:

Приращение:

1. Считайте значение в регистре R
2. Добавьте один к значению
3. Записывает новое значение обратно в регистр R

Читать:

Чтение регистра R

Эта простая реализация не поддается линеаризации, как показано в следующем примере.

Представьте, что два процесса работают, обращаясь к единственному объекту счетчика, инициализированному со значением 0:

1. Первый процесс считывает значение в регистре как 0.
2. Первый процесс добавляет единицу к значению, значение счетчика должно быть 1, но до того, как он закончит запись нового значения обратно в регистр, он может быть приостановлен, в то время как второй процесс выполняется:
3. Второй процесс считывает значение в регистре, которое все еще равно 0;
4. Второй процесс добавляет единицу к значению;
5. второй процесс записывает новое значение в регистр, теперь регистр имеет значение 1.

Второй процесс завершается, а первый продолжает работу с того места, где он остановился:

1. Первый процесс записывает 1 в регистр, не зная, что другой процесс уже обновил значение в регистре до 1.

В приведенном выше примере два процесса вызвали команду увеличения, однако значение объекта увеличилось только с 0 до 1 вместо 2, как должно было быть. Одна из операций приращения была потеряна из-за невозможности линеаризации системы.

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

Атомный

Чтобы реализовать линеаризуемый или атомарный объект счетчика, мы изменим нашу предыдущую реализацию так, чтобы каждый процесс Pя будет использовать собственный регистр Rя

Каждый процесс увеличивается и читает в соответствии со следующим алгоритмом:

Приращение:

1. Прочитать значение в регистре Rя.
2. Добавьте единицу к значению.
3. Записать новое значение обратно в Rя

Читать:

1. Регистры чтения R1, р2, ... рп.
2. Вернуть сумму всех регистров.

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

Это банальный пример. В реальной системе операции могут быть более сложными, а ошибки вносятся чрезвычайно незаметными. Например, читая 64-битный значение из памяти может быть реализовано как два последовательный читает два 32-битный места в памяти. Если процесс прочитал только первые 32 бита, и до того, как он прочитает вторые 32 бита, значение в памяти изменится, у него не будет ни исходного значения, ни нового значения, а будет смешанное значение.

Кроме того, конкретный порядок, в котором выполняются процессы, может изменить результаты, что затрудняет обнаружение, воспроизведение и отлаживать.

Сравнить и обменять

Основная статья: Сравнить и обменять

Большинство систем предоставляют атомарную инструкцию сравнения и замены, которая читает из области памяти, сравнивает значение с «ожидаемым» значением, предоставленным пользователем, и записывает «новое» значение, если они совпадают, возвращая, успешно ли выполнено обновление. . Мы можем использовать это, чтобы исправить алгоритм неатомарного счетчика следующим образом:

1. Прочтите значение в ячейке памяти;
2. добавьте единицу к значению;
3. используйте функцию сравнения и замены, чтобы записать увеличенное значение обратно;
4. повторить попытку, если значение, считанное с помощью функции сравнения и замены, не соответствует значению, которое мы изначально считали.

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

Получение и увеличение

Основная статья: Получение и увеличение

Многие системы предоставляют команду атомарной выборки и увеличения, которая читает из области памяти, безусловно записывает новое значение (старое значение плюс один) и возвращает старое значение. Мы можем использовать это для исправления алгоритма неатомарного счетчика как следует:

1. Используйте выборку и инкремент, чтобы прочитать старое значение и записать увеличенное значение обратно.

Использование выборки и приращения всегда лучше (требует меньшего количества обращений к памяти) для некоторых алгоритмов, таких как показанный здесь, чем сравнение и замена,^[5] хотя Херлихи ранее доказал, что сравнение и замена лучше для некоторых других алгоритмов, которые вообще невозможно реализовать, используя только fetch-and-increment. Проекты ЦП с командами fetch-and-increment и compare-and-swap (или эквивалентными инструкциями) может быть лучшим выбором, чем те, у которых есть только одно или другое.^[5]

Блокировка

Основная статья: Lock (информатика)

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

1. Получите блокировку, исключающую одновременное выполнение критического раздела другими потоками (шаги 2-4);
2. прочитать значение в ячейке памяти;
3. добавьте единицу к значению;
4. записать увеличенное значение обратно в ячейку памяти;
5. отпустить замок.

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

Смотрите также

• Атомарная транзакция
• Модель согласованности
• КИСЛОТА
• Чтение-копирование-обновление (RCU)
• Чтение-изменение-запись
• Время проверки до времени использования

Рекомендации

1. Herlihy, Maurice P .; Крыло, Жаннетт М. (1990). «Линеаризуемость: условие корректности для параллельных объектов». Транзакции ACM по языкам и системам программирования. 12 (3): 463–492. CiteSeerX  10.1.1.142.5315. Дои:10.1145/78969.78972. S2CID  228785.
2. Шавит, Нир и Таубенфель, Гади (2016). «Вычислимость упрощенных структур данных: очереди и стеки в качестве примеров» (PDF). Распределенных вычислений. 29 (5): 396–407. Дои:10.1007 / s00446-016-0272-0. S2CID  16192696.
3. Керриск, Майкл (7 сентября 2018 г.). Программный интерфейс Linux. Пресс без крахмала. ISBN  9781593272203 - через Google Книги.
4. "Статья о разработке примитивов синхронизации ARM".
5. Фич, Вера; Хендлер, Дэнни; Шавит, Нир (2004). «О внутренней слабости примитивов условной синхронизации». Материалы двадцать третьего ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '04. Нью-Йорк, штат Нью-Йорк: ACM. С. 80–87. Дои:10.1145/1011767.1011780. ISBN  978-1-58113-802-3. S2CID  9313205.

дальнейшее чтение

• Herlihy, Maurice P .; Крыло, Жаннетт М. (1987). Аксиомы для параллельных объектов. Материалы 14-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования, POPL '87. п. 13. Дои:10.1145/41625.41627. ISBN  978-0-89791-215-0. S2CID  16017451.
• Херлихи, Морис П. (1990). Методология реализации высокопараллельных структур данных. Уведомления ACM SIGPLAN. 25. С. 197–206. CiteSeerX  10.1.1.186.6400. Дои:10.1145/99164.99185. ISBN  978-0-89791-350-8.
• Herlihy, Maurice P .; Крыло, Жаннетт М. (1990). «Линеаризуемость: условие корректности для параллельных объектов». Транзакции ACM по языкам и системам программирования. 12 (3): 463–492. CiteSeerX  10.1.1.142.5315. Дои:10.1145/78969.78972. S2CID  228785.
• Афир. «Модели сильной согласованности». aphyr.com. Афир. Получено 13 апреля 2018.