Войти
«Обеденные философы», классическая проблема, связанная с параллелизмом и общими ресурсами В информатике, параллелизм - это способность различных частей или единиц программы, алгоритма или задачи выполняться вне очереди или в частичном порядке, не влияя на конечный результат. Это позволяет выполнять параллельное выполнение параллельных модулей, что может значительно повысить общую скорость выполнения в многопроцессорных и многоядерных системах. В более технических терминах параллелизм относится к свойству декомпозиции программы, алгоритма или проблемы на независимые от порядка или частично упорядоченные компоненты или единицы.
Для общих параллельных вычислений был разработан ряд математических моделей, включая Сети Петри, вычисления процессов, модель параллельной машины с произвольным доступом, модель актора и язык координации Reo.
Как отмечает Лесли Лэмпорт (2015), «в то время как параллельное выполнение программы рассматривалось в течение многих лет, информатика параллелизма началось с основополагающей статьи Эдсгера Дейкстры 1965 года, в которой была представлена проблема взаимного исключения... В последующие десятилетия наблюдался огромный рост интереса к параллелизму, особенно в distri бутилированные системы. Оглядываясь на истоки этой области, можно выделить фундаментальную роль, которую играет Эдсгер Дейкстра ».
Поскольку вычисления в параллельной системе могут взаимодействовать друг с другом во время выполнения, количество возможных путей выполнения в системе может быть чрезвычайно большим, а результирующий результат может быть неопределенным. Одновременное использование общих ресурсов может быть источником неопределенности, приводящей к таким проблемам, как взаимоблокировки и нехватка ресурсов.
Дизайн параллельных систем часто влечет за собой поиск надежных методов для координации их выполнения, обмена данными, выделения памяти и планирования выполнения для минимизации время отклика и максимизация пропускной способности.
Теория параллелизма была активной областью исследований в теоретической информатике. Одно из первых предложений было Основополагающая работа Карла Адама Петри о сетях Петри в начале 1960-х годов. Поэтому было разработано множество формализмов для моделирования и рассуждений о параллелизме.
Был разработан ряд формализмов для моделирования и понимания параллельных систем, в том числе:
Некоторые из этих моделей параллелизма в первую очередь предназначены для поддержки рассуждений и спецификации, в то время как другие могут использоваться на протяжении всего цикла разработки, включая проектирование, реализацию, проверку, тестирование и моделирование параллельных систем. Некоторые из них основаны на передаче сообщений, в то время как другие имеют другие механизмы для параллелизма.
Распространение различных моделей параллелизма побудило некоторых исследователей разработать способы объединения этих различных теоретических моделей. Например, Ли и Сангиованни-Винсентелли продемонстрировали, что так называемая модель «помеченного сигнала» может использоваться для обеспечения общей структуры для определения денотационной семантики множества различных моделей параллелизма, в то время как Нильсен, Сассон и Винскель продемонстрировали, что теорию категорий можно использовать для обеспечения аналогичного единого понимания различных моделей.
Теорема представления параллелизма в модели акторов обеспечивает довольно общий способ представляют собой параллельные системы, которые закрыты в том смысле, что они не получают сообщений извне. (Другие системы параллелизма, например, вычисление процессов могут быть смоделированы в модели актора с использованием протокола двухфазной фиксации.) Математическое обозначение, обозначаемое закрытой системой S, строится все лучше приближения из начального поведения, называемого ⊥S, с использованием функции аппроксимации поведения прогрессия Sдля построения обозначения (значения) для S следующим образом:
Таким образом, S можно математически охарактеризовать в терминах всех его возможных вариантов поведения.
Различные типы временной логики могут использоваться, чтобы помочь рассуждать о параллельных системах. Некоторые из этих логик, например линейная темпоральная логика и логика дерева вычислений, позволяют делать утверждения о последовательностях состояний, через которые может проходить параллельная система. Другие, такие как логика Хеннесси-Милнера и логика действий Лэмпорта, строят свои утверждения из последовательностей действий (изменений состояния). Основное применение этой логики - написание спецификаций для параллельных систем.
Параллельное программирование охватывает языки программирования и алгоритмы, используемые для реализации параллельных систем. Параллельное программирование обычно считается более общим, чем параллельное программирование, потому что оно может включать произвольные и динамические шаблоны взаимодействия и взаимодействия, тогда как параллельные системы обычно имеют заранее определенный и хорошо структурированный шаблон взаимодействия. Основные цели параллельного программирования включают правильность, производительность и надежность. Параллельные системы, такие как Операционные системы и Системы управления базами данных, как правило, предназначены для работы в течение неограниченного времени, включая автоматическое восстановление после сбоя, и не прекращают работу неожиданно (см. Управление параллелизмом ). Некоторые параллельные системы реализуют форму прозрачного параллелизма, при которой параллельные вычислительные объекты могут конкурировать за один ресурс и совместно использовать его, но сложность этой конкуренции и совместного использования скрыта от программиста.
Поскольку они используют общие ресурсы, параллельные системы обычно требуют включения какого-то типа арбитра где-нибудь в своей реализации (часто в базовом оборудовании) для управления доступом к этим ресурсам. Использование арбитров вводит возможность неопределенности в параллельных вычислениях, что имеет серьезные последствия для практики, включая правильность и производительность. Например, арбитраж вводит неограниченный недетерминизм, который вызывает проблемы с проверкой модели, потому что он вызывает взрыв в пространстве состояний и может даже привести к тому, что модели будут иметь бесконечное количество состояний.
Некоторые модели параллельного программирования включают сопроцессы и детерминированный параллелизм. В этих моделях потоки управления явно передают свои временные интервалы либо системе, либо другому процессу.
