В информационных технологиях и компьютерной науке , особенно в областях компьютерного программирования , операционных систем , многопроцессорных систем и баз данных , управление параллелизмом гарантирует, что будут получены правильные результаты для параллельных операций, при этом эти результаты будут получены как можно быстрее.
Компьютерные системы, как программное обеспечение, так и аппаратное обеспечение , состоят из модулей или компонентов. Каждый компонент разработан для правильной работы, т. е. для соблюдения или соответствия определенным правилам согласованности. Когда компоненты, работающие одновременно, взаимодействуют посредством обмена сообщениями или совместного использования доступных данных (в памяти или хранилище ), согласованность определенного компонента может быть нарушена другим компонентом. Общая область управления параллелизмом предоставляет правила, методы, методологии проектирования и теории для поддержания согласованности компонентов, работающих одновременно при взаимодействии, и, таким образом, согласованности и правильности всей системы. Внедрение управления параллелизмом в систему означает применение ограничений операций, которые обычно приводят к некоторому снижению производительности. Согласованность и правильность операций должны достигаться с максимально возможной эффективностью, не снижая производительность ниже разумного уровня. Управление параллелизмом может потребовать значительной дополнительной сложности и накладных расходов в параллельном алгоритме по сравнению с более простым последовательным алгоритмом .
Например, сбой в управлении параллелизмом может привести к повреждению данных из-за прерванных операций чтения или записи.
Комментарии:
Управление параллелизмом в системах управления базами данных (СУБД; например, Bernstein et al. 1987, Weikum and Vossen 2001), других транзакционных объектах и связанных с ними распределенных приложениях (например, Grid computing и Cloud computing ) гарантирует, что транзакции базы данных выполняются одновременно , не нарушая целостности данных соответствующих баз данных . Таким образом, управление параллелизмом является существенным элементом для корректности в любой системе, где две или более транзакции базы данных, выполняемые с перекрытием времени, могут получить доступ к одним и тем же данным, например, практически в любой системе баз данных общего назначения. Следовательно, с момента появления систем баз данных в начале 1970-х годов был накоплен огромный объем соответствующих исследований. Хорошо зарекомендовавшая себя теория управления параллелизмом для систем баз данных изложена в ссылках, упомянутых выше: теория сериализуемости , которая позволяет эффективно проектировать и анализировать методы и механизмы управления параллелизмом. Альтернативная теория управления параллелизмом атомарных транзакций над абстрактными типами данных представлена в (Lynch et al. 1993) и не используется ниже. Эта теория более утонченная, сложная, с более широким охватом и меньше использовалась в литературе по базам данных, чем классическая теория выше. Каждая теория имеет свои плюсы и минусы, акцент и понимание . В некоторой степени они дополняют друг друга, и их слияние может быть полезным.
Для обеспечения корректности СУБД обычно гарантирует, что генерируются только сериализуемые расписания транзакций , если только сериализуемость намеренно не ослаблена для повышения производительности, но только в случаях, когда корректность приложения не страдает. Для поддержания корректности в случаях неудачных (прерванных) транзакций (что всегда может произойти по многим причинам) расписания также должны иметь свойство восстанавливаемости (из прерывания). СУБД также гарантирует, что никакие эффекты зафиксированных транзакций не будут потеряны, и никакие эффекты прерванных ( откатных ) транзакций не останутся в связанной базе данных. Общая характеристика транзакций обычно суммируется с помощью правил ACID ниже. Поскольку базы данных стали распределенными или нуждались в сотрудничестве в распределенных средах (например, федеративные базы данных в начале 1990-х годов и облачные вычисления в настоящее время), эффективное распределение механизмов управления параллелизмом получило особое внимание.
Концепция транзакции базы данных (или атомарной транзакции ) развивалась для того, чтобы обеспечить как хорошо понятное поведение системы базы данных в неисправной среде, где сбои могут произойти в любое время, так и восстановление после сбоя в хорошо понятное состояние базы данных. Транзакция базы данных — это единица работы, обычно инкапсулирующая ряд операций над базой данных (например, чтение объекта базы данных , запись, получение блокировки и т. д.), абстракция, поддерживаемая в базе данных и других системах. Каждая транзакция имеет четко определенные границы с точки зрения того, какие выполнения программы/кода включены в эту транзакцию (определяются программистом транзакции с помощью специальных команд транзакции). Каждая транзакция базы данных подчиняется следующим правилам (поддержкой в системе базы данных; т. е. система базы данных разработана для того, чтобы гарантировать их для транзакций, которые она запускает):
Концепция атомарной транзакции была расширена в течение многих лет до того, что стало бизнес-транзакциями , которые фактически реализуют типы Workflow и не являются атомарными. Однако такие расширенные транзакции также обычно используют атомарные транзакции в качестве компонентов.
Если транзакции выполняются последовательно , т. е. последовательно без перекрытия во времени, то не существует параллельности транзакций. Однако, если параллельные транзакции с чередующимися операциями разрешены неконтролируемым образом, могут возникнуть некоторые неожиданные, нежелательные результаты, такие как:
Большинству высокопроизводительных транзакционных систем необходимо запускать транзакции одновременно, чтобы соответствовать требованиям производительности. Таким образом, без управления параллелизмом такие системы не могут ни предоставлять правильные результаты, ни поддерживать свои базы данных согласованно.
Основными категориями механизмов управления параллелизмом являются:
Различные категории обеспечивают различную производительность, т. е. различные средние скорости завершения транзакций ( пропускную способность ), в зависимости от типа транзакции, уровня параллелизма вычислений и других факторов. Если выбор и знания о компромиссах доступны, то следует выбрать категорию и метод, чтобы обеспечить наивысшую производительность.
Взаимная блокировка между двумя транзакциями (где каждая из них блокирует другую) или более приводит к взаимоблокировке , когда вовлеченные транзакции останавливаются и не могут достичь завершения. Большинство неоптимистичных механизмов (с блокировкой) склонны к взаимоблокировкам, которые разрешаются преднамеренным прерыванием остановившейся транзакции (что освобождает другие транзакции в этой взаимоблокировке) и ее немедленным перезапуском и повторным выполнением. Вероятность взаимоблокировки обычно низкая.
Блокировки, взаимоблокировки и прерывания приводят к снижению производительности, а отсюда и к компромиссам между категориями.
Существует множество методов управления параллелизмом. Большинство из них можно реализовать в рамках любой из основных категорий, указанных выше. Основные методы [1] , каждый из которых имеет множество вариантов и в некоторых случаях может перекрываться или комбинироваться, следующие:
Другие основные типы управления параллелизмом, которые используются вместе с вышеперечисленными методами, включают:
Наиболее распространенным типом механизма в системах баз данных с момента их появления в 1970-х годах была Strong strict Two-phase locking (SS2PL; также называемая Rigorous scheduling или Rigorous 2PL ), которая является частным случаем (вариантом) Two-phase locking (2PL). Она пессимистична. Несмотря на свое длинное название (по историческим причинам), идея механизма SS2PL проста: «Снять все блокировки, примененные транзакцией, только после того, как транзакция завершена». SS2PL (или Rigorousness) — это также название набора всех расписаний, которые могут быть сгенерированы этим механизмом, т. е. эти SS2PL (или Rigorous) расписания обладают свойством SS2PL (или Rigorousness).
Механизмы управления параллелизмом в первую очередь должны работать правильно, т. е. поддерживать правила целостности каждой транзакции (в отношении параллелизма; правила целостности, специфичные для приложения, здесь не рассматриваются), пока транзакции выполняются одновременно, и, таким образом, целостность всей транзакционной системы. Корректность должна быть достигнута с максимально возможной производительностью. Кроме того, все больше возникает необходимость в эффективной работе, когда транзакции распределены по процессам , компьютерам и компьютерным сетям . Другими субъектами, которые могут влиять на управление параллелизмом, являются восстановление и репликация .
Для корректности, общей основной целью большинства механизмов управления параллелизмом является генерация расписаний со свойством сериализуемости . Без сериализуемости могут возникнуть нежелательные явления, например, деньги могут исчезнуть со счетов или появиться из ниоткуда. Сериализуемость расписания означает эквивалентность (в результирующих значениях базы данных) некоторому последовательному расписанию с теми же транзакциями (т. е., в котором транзакции последовательны без перекрытия во времени и, таким образом, полностью изолированы друг от друга: невозможен одновременный доступ любых двух транзакций к одним и тем же данным). Сериализуемость считается наивысшим уровнем изоляции среди транзакций базы данных и основным критерием корректности для параллельных транзакций. В некоторых случаях скомпрометированные, ослабленные формы сериализуемости допускаются для лучшей производительности (например, популярный механизм изоляции Snapshot ) или для соответствия требованиям доступности в высокораспределенных системах (см. Конечная согласованность ), но только если корректность приложения не нарушается релаксацией (например, релаксация не допускается для денежных транзакций, поскольку при релаксации деньги могут исчезать или появляться из ниоткуда).
Почти все реализованные механизмы управления параллелизмом достигают сериализуемости, предоставляя сериализуемость конфликтов , широкий частный случай сериализуемости (т. е. он охватывает, позволяет использовать большинство сериализуемых расписаний и не накладывает существенных дополнительных ограничений, вызывающих задержки), который может быть реализован эффективно.
Управление параллелизмом обычно также обеспечивает свойство Recoverability расписаний для поддержания корректности в случаях прерванных транзакций (что всегда может произойти по многим причинам). Recoverability (после прерывания) означает, что ни одна зафиксированная транзакция в расписании не считывала данные, записанные прерванной транзакцией. Такие данные исчезают из базы данных (при прерывании) и являются частями неправильного состояния базы данных. Чтение таких данных нарушает правило согласованности ACID. В отличие от Serializability, Recoverability не может быть скомпрометирована, ослаблена в любом случае, поскольку любое ослабление приводит к быстрому нарушению целостности базы данных при прерываниях. Основные методы, перечисленные выше, предоставляют механизмы сериализуемости. Ни один из них в своей общей форме автоматически не обеспечивает восстанавливаемость, и для поддержки восстанавливаемости необходимы специальные соображения и усовершенствования механизмов. Обычно используемый особый случай восстанавливаемости — Strictness , который позволяет эффективно восстанавливать базу данных после сбоя (но исключает оптимистичные реализации).
С быстрым технологическим развитием вычислений разница между локальными и распределенными вычислениями по сетям или шинам с низкой задержкой стирается. Таким образом, довольно эффективное использование локальных методов в таких распределенных средах является обычным явлением, например, в компьютерных кластерах и многоядерных процессорах . Однако локальные методы имеют свои ограничения и используют многопроцессорные (или многоядерные) потоки для масштабирования. Это часто превращает транзакции в распределенные, если им самим необходимо охватывать многопроцессорные процессы. В этих случаях большинство локальных методов управления параллелизмом плохо масштабируются.
Все системы подвержены сбоям, и управление восстановлением после сбоя является обязательным. Свойства сгенерированных расписаний, которые диктуются механизмом управления параллелизмом, могут влиять на эффективность и результативность восстановления. Например, свойство Strictness (упомянутое в разделе Восстанавливаемость выше) часто желательно для эффективного восстановления.
Для обеспечения высокой доступности объекты базы данных часто реплицируются . Обновления реплик одного и того же объекта базы данных должны быть синхронизированы. Это может повлиять на способ управления параллелизмом (например, Gray et al. 1996 [2] ).
Многозадачные операционные системы, особенно операционные системы реального времени , должны поддерживать иллюзию того, что все задачи, запущенные поверх них, работают одновременно, даже если в любой момент времени на самом деле работает только одна или несколько задач из-за ограничений оборудования, на котором работает операционная система. Такая многозадачность довольно проста, когда все задачи независимы друг от друга. Однако, когда несколько задач пытаются использовать один и тот же ресурс или когда задачи пытаются обмениваться информацией, это может привести к путанице и непоследовательности. Задача параллельных вычислений — решить эту проблему. Некоторые решения включают «блокировки», аналогичные блокировкам, используемым в базах данных, но они рискуют вызвать собственные проблемы, такие как взаимоблокировка . Другие решения — неблокирующие алгоритмы и чтение-копирование-обновление .