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

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

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

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

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

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

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

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

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

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

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

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

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

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

Получает «неудачный» ответ

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

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

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

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

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

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

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

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

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

Получает «неудачный» ответ

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

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

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

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

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

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

Получает «неудачный» ответ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Функция сравнения и замены записывает новое значение в местоположение только в том случае, если его содержимое соответствует предоставленному старому значению. Обычно это используется в последовательности чтения-изменения-CAS: пользователь считывает местоположение, вычисляет новое значение для записи и записывает его с помощью CAS (сравнение и замена); если значение одновременно изменится, CAS завершится неудачно, и пользователь попытается еще раз.
• Load-link/store-conditional кодирует этот шаблон более напрямую: пользователь считывает местоположение с помощью 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 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. Используйте выборку и приращение, чтобы прочитать старое значение и записать увеличенное значение обратно.

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

Блокировка

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

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

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

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

См. также

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

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

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