stringtranslate.com

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Для каждой завершенной операции в операция возвращает тот же результат выполнения, который бы вернула операция, если бы каждая операция была завершена одна за другой по порядку .
  2. Если операция op 1 завершается (получает ответ) до начала (вызова) операции op 2 , то операция op 1 предшествует операции op 2 в . [1]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Набор инструкций ARM предоставляет LDREXи STREXинструкции, которые могут использоваться для реализации атомарного доступа к памяти с помощью эксклюзивных мониторов , реализованных в процессоре для отслеживания обращений к памяти для определенного адреса. [4] Однако, если переключение контекста происходит между вызовами LDREXи STREX, в документации отмечается, что это STREXприведет к сбою, указывая на необходимость повторной попытки операции. В случае 64-битной архитектуры ARMv8-A он предоставляет LDXRи STXRинструкции для размера байта, полуслова, слова и двойного слова. [5]

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

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

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

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

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

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

Счетчики

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

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

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

  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 i использовал свой собственный регистр R i

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

Приращение:

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

Читать:

  1. Чтение регистров R 1, R 2, ... R n .
  2. Вернуть сумму всех регистров.

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

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

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

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

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

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

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

Извлечение и увеличение

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

  1. Используйте функцию fetch-and-increment, чтобы прочитать старое значение и записать увеличенное значение обратно.

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

Блокировка

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

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

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

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

Ссылки

  1. ^ abcd Herlihy, Maurice P.; Wing, Jeannette M. (1990). «Линеризуемость: условие корректности для параллельных объектов». Труды ACM по языкам и системам программирования . 12 (3): 463–492. CiteSeerX  10.1.1.142.5315 . doi :10.1145/78969.78972. S2CID  228785.
  2. ^ Шавит, Нир; Таубенфель, Гади (2016). «Вычислимость ослабленных структур данных: очереди и стеки как примеры» (PDF) . Распределенные вычисления . 29 (5): 396–407. doi :10.1007/s00446-016-0272-0. S2CID  16192696.
  3. ^ Керриск, Майкл (7 сентября 2018 г.). Интерфейс программирования Linux. No Starch Press. ISBN 9781593272203– через Google Книги.
  4. ^ «Статья о разработке примитивов синхронизации ARM».
  5. ^ "ARMv8-A Synchronization Primitives". стр. 6. Получено 2023-12-14 .
  6. ^ ab Fich, Faith; Hendler, Danny; Shavit, Nir (2004). "О присущей слабости примитивов условной синхронизации". Труды двадцать третьего ежегодного симпозиума ACM по принципам распределенных вычислений – PODC '04 . Нью-Йорк, Нью-Йорк: ACM. стр. 80–87. doi :10.1145/1011767.1011780. ISBN 978-1-58113-802-3. S2CID  9313205.

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