Управление параллелизмом

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

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

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

Управление параллелизмом в базах данных

Комментарии:

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

Управление параллелизмом в системах управления базами данных (СУБД; например, Bernstein et al. 1987 , Weikum and Vossen 2001 ), других транзакционных объектах и ​​связанных с ними распределенных приложениях (например, Grid-вычислениях и облачных вычислениях ) гарантирует, что транзакции базы данных выполняются одновременно, не нарушая целостность данных соответствующих баз данных . Таким образом, управление параллелизмом является важным элементом корректности в любой системе, где две или более транзакции базы данных, выполняемые с перекрытием во времени, могут получить доступ к одним и тем же данным, например, практически в любой системе баз данных общего назначения. Следовательно, с момента появления систем баз данных в начале 1970-х годов было накоплено огромное количество соответствующих исследований. Хорошо зарекомендовавшая себя теория управления параллелизмом для систем баз данных изложена в упомянутых выше ссылках: теория сериализуемости , которая позволяет эффективно разрабатывать и анализировать методы и механизмы управления параллелизмом. Альтернативная теория параллельного управления атомарными транзакциями над абстрактными типами данных. представлено в ( Lynch et al. 1993 ) и не используется ниже. Эта теория более совершенна, сложна, имеет более широкую сферу применения и реже используется в литературе по базам данных, чем классическая теория, описанная выше. Каждая теория имеет свои плюсы и минусы, акценты и понимание . В некоторой степени они дополняют друг друга, и их объединение может быть полезным.

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

Транзакция базы данных и правила ACID

Основные статьи: Транзакция базы данных и ACID

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

• Атомарность — либо эффекты всех операций, либо ни одна из них не сохраняются (семантика «все или ничего») после транзакции завершения ( фиксации или прерывания соответственно). Другими словами, для внешнего мира зафиксированная транзакция кажется (в силу ее воздействия на базу данных) неделимой (атомарной), а прерванная транзакция вообще не влияет на базу данных. Либо все операции выполнены, либо ни одна из них не выполнена.
• Согласованность . Каждая транзакция должна покидать базу данных в согласованном (корректном) состоянии, т. е. поддерживать заранее определенные правила целостности базы данных (ограничения на объекты базы данных и между ними). Транзакция должна перевести базу данных из одного согласованного состояния в другое согласованное состояние (однако на программисте транзакции лежит ответственность за то, чтобы сама транзакция была корректной, т. е. правильно выполняла то, что намеревалась выполнить (с точки зрения приложения). представление), в то время как предопределенные правила целостности применяются СУБД). Таким образом, поскольку базу данных обычно можно изменить только с помощью транзакций, все состояния базы данных согласованы.
• Изоляция . Транзакции не могут мешать друг другу (в результате их выполнения). Более того, обычно (в зависимости от метода управления параллелизмом) последствия незавершенной транзакции даже не видны другой транзакции. Обеспечение изоляции является основной целью управления параллелизмом.
• Долговечность . Эффекты успешных (зафиксированных) транзакций должны сохраняться даже при сбоях (обычно путем записи эффектов транзакции и события ее фиксации в энергонезависимой памяти ).

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

Зачем нужен контроль параллелизма?

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

1. Проблема потерянного обновления: вторая транзакция записывает второе значение элемента данных (данные) поверх первого значения, записанного первой параллельной транзакцией, и первое значение теряется для других транзакций, выполняемых одновременно, которым необходимо, в зависимости от их приоритета. , чтобы прочитать первое значение. Транзакции, которые прочитали неправильное значение, заканчиваются неверными результатами.
2. Грязная проблема чтения : транзакции считывают значение, записанное транзакцией, которая позже была прервана. Это значение исчезает из базы данных при прерывании и не должно быть прочитано какой-либо транзакцией («грязное чтение»). Транзакции чтения завершаются неверными результатами.
3. Проблема с неправильным суммированием: в то время как одна транзакция суммирует значения всех экземпляров повторяющегося элемента данных, вторая транзакция обновляет некоторые экземпляры этого элемента данных. Полученная сводка не отражает правильный результат для какого-либо (обычно необходимого для корректности) порядка приоритета между двумя транзакциями (если одна выполняется раньше другой), а скорее некоторый случайный результат, зависящий от времени обновлений и от того, были ли определенные результаты обновления были включены в сводку или нет.

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

Механизмы управления параллелизмом

Категории

Основными категориями механизмов управления параллелизмом являются:

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

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

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

Блокировки, взаимоблокировки и прерывания — все это приводит к снижению производительности и, следовательно, к компромиссам между категориями.

Методы

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

1. Блокировка (например, двухфазная блокировка — 2PL) — управление доступом к данным с помощью блокировок, назначенных данным. Доступ транзакции к элементу данных (объекту базы данных), заблокированному другой транзакцией, может быть заблокирован (в зависимости от типа блокировки и типа операции доступа) до момента снятия блокировки.
2. сериализации Проверка графа (также называемая проверкой сериализуемости, конфликтов или приоритетов) — проверка циклов расписания в графе и их прерывание.
3. Порядок меток времени (TO). Назначение меток времени транзакциям, а также контроль или проверка доступа к данным по порядку меток времени.

Другие основные типы управления параллелизмом, которые используются в сочетании с описанными выше методами, включают:

• Управление многоверсионным параллелизмом (MVCC). Повышение параллелизма и производительности за счет создания новой версии объекта базы данных каждый раз при записи объекта и разрешения операций чтения транзакций нескольких последних соответствующих версий (каждого объекта) в зависимости от метода планирования.
• Управление параллелизмом индексов — синхронизация операций доступа к индексам , а не к пользовательским данным. Специализированные методы обеспечивают существенный прирост производительности.
• Модель частного рабочего пространства ( отложенное обновление ). Каждая транзакция поддерживает частное рабочее пространство для данных, к которым осуществляется доступ, и ее измененные данные становятся видимыми вне транзакции только после ее фиксации (например, Weikum and Vossen 2001 ). Эта модель обеспечивает другое поведение управления параллелизмом, что во многих случаях дает преимущества.

Наиболее распространенным типом механизма в системах баз данных с момента их появления в 1970-х годах была сильная строгая двухфазная блокировка (SS2PL; также называемая строгим планированием или строгим 2PL ), которая является особым случаем (вариантом) двухфазной блокировки (2PL). . Это пессимистично. Несмотря на длинное название (по историческим причинам), идея механизма SS2PL проста: «Снимать все блокировки, примененные транзакцией, только после ее завершения». SS2PL (или строгость) — это также имя набора всех расписаний, которые могут быть созданы с помощью этого механизма, т. е. эти расписания SS2PL (или строгость) обладают свойством SS2PL (или строгость).

Основные цели механизмов управления параллелизмом

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

Корректность

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

Основная статья: Сериализуемость

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

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

Возможность восстановления

См. «Восстанавливаемость» в сериализуемости.

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

Распределение

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

Восстановление

Основная статья: Восстановление данных

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

Репликация

Основная статья: Репликация (информатика)

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

Управление параллелизмом в операционных системах

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

См. также

• Линеаризуемость - свойство некоторых операций в параллельном программировании.
• Блокировка (информатика) - механизм синхронизации для обеспечения ограничений доступа к ресурсу.
• Взаимное исключение . В вычислениях ограничение доступа к данным для одного потока за раз.
• Индексирование поисковыми системами – метод управления данными
• Семафор (программирование) - переменная, используемая в параллельной системе.
• Программная транзакционная память - механизм управления параллелизмом в программном обеспечении.
• Расширения транзакционной синхронизации — расширение архитектуры набора команд x86, которое добавляет аппаратную поддержку транзакционной памяти.
• Расписание транзакций базы данных
• Изоляция (информатика)
• Распределенное управление параллелизмом

Ссылки

• Эндрю С. Таненбаум, Альберт С. Вудхалл (2006): Проектирование и реализация операционных систем, 3-е издание , Prentice Hall , ISBN   0-13-142938-8
• Зильбершац, Ави; Гэлвин, Питер; Ганье, Грег (2008). Концепции операционных систем, 8-е издание . Джон Уайли и сыновья . ISBN  978-0-470-12872-5 .
• Филип А. Бернштейн , Вассос Хадзилакос, Натан Гудман (1987): Управление параллелизмом и восстановление в системах баз данных (бесплатная загрузка в формате PDF), Addison Wesley Publishing Company, 1987, ISBN   0-201-10715-5
• Герхард Вейкум , Готфрид Воссен (2001): Транзакционные информационные системы , Elsevier, ISBN   1-55860-508-8
• Нэнси Линч , Майкл Мерритт, Уильям Вейль, Алан Фекете (1993): Атомарные транзакции в параллельных и распределенных системах , Морган Кауфманн (Elsevier), август 1993 г., ISBN   978-1-55860-104-8 , ISBN   1-55860-104-X
• Йоав Раз (1992): «Принцип упорядочивания обязательств или гарантия сериализуемости в гетерогенной среде с несколькими автономными менеджерами ресурсов, использующими атомарные обязательства». ( PDF ), Труды Восемнадцатой Международной конференции по очень большим базам данных (VLDB), стр. 292–312, Ванкувер, Канада, август 1992 г. (также DEC-TR 841, Digital Equipment Corporation , ноябрь 1990 г.)