Алгоритм Шиманьского - Szymańskis algorithm

Алгоритм взаимного исключения Шиманского это алгоритм взаимного исключения разработал компьютерный ученый д-р. Болеслав Шиманский, который имеет много полезных свойств, включая линейное ожидание,[1][2] и какое расширение[3] решил открытую проблему, опубликованную Лесли Лэмпорт[4] существует ли алгоритм с постоянным числом коммуникационных битов на процесс, который удовлетворяет всем разумным требованиям справедливости и отказоустойчивости, которые задумал Лампорт (в решении Лампорта использовалось n факторных коммуникационных переменных по сравнению с 5 Шиманским).

Алгоритм

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

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

# Протокол входафлаг[себя] ← 1                    # Стоя вне зала ожиданияЖдите(все флаг[1..N] ∈ {0, 1, 2}) # Подождите, пока откроется дверьфлаг[себя] ← 3                    # Стоя в дверяхесли любой флаг[1..N] = 1:            # Другой процесс ожидает входа    флаг[себя] ← 2                # Ожидание входа других процессов    Ждите(любой флаг[1..N] = 4)     # Подождите, пока процесс войдет, и закройте дверьфлаг[себя] ← 4                    # Дверь закрытаЖдите(все флаг[1..себя-1] ∈ {0, 1})   # Подождите, пока все с более низким ID завершат протокол выхода# Критический раздел# ...# Выход из протоколаЖдите(все флаг[себя+1..N] ∈ {0, 1, 4}) # Убедитесь, что все в зале ожидания                                       # понял, что дверь должна быть закрытафлаг[себя] ← 0 # Покинуть. Откройте дверь, если в зале ожидания никого нет

Обратите внимание, что порядок тестов «все» и «все» должен быть одинаковым. Также "любые" тесты должны выполняться не в self, а в другом потоке. Например, если тестом является любой флаг [1..N] = 1 и только флаг [self] = 1, то считается, что тест не прошел / вернул 0. Несмотря на интуитивное объяснение, алгоритм был непростым для доказать правоту однако из-за его благоприятных свойств было желательно доказательство правильности, и были представлены многочисленные доказательства.[2][5]

Рекомендации

  1. ^ а б Шиманский, Болеслав К. (1988). «Простое решение проблемы параллельного программирования Лампорта с линейным ожиданием». Материалы 2-й международной конференции по суперкомпьютерам - ICS '88. ICS '88: Материалы 2-й Международной конференции по суперкомпьютерам. Сен-Мало, Франция: ACM. С. 621–626. Дои:10.1145/55364.55425. ISBN  978-0-89791-272-3. S2CID  18612278.
  2. ^ а б Манна, Зоар; Пнуэли, Амир (1990). «Упражнение по проверке многопроцессорных программ». Красота - это наше дело: поздравление с днем ​​рождения Эдсгеру В. Дейкстре. Springer Verlag. С. 289–301. ISBN  978-0-387-97299-2.
  3. ^ Шиманский, Болеслав (1990). «Возвращение к взаимному исключению» (PDF). Пятая Иерусалимская конференция по информационным технологиям. Иерусалим, Израиль: 110–117.
  4. ^ Лэмпорт, Лесли (1986). «Проблема взаимного исключения: часть II - постановка и решения». Журнал ACM. 33 (2): 327–348. CiteSeerX  10.1.1.32.9808. Дои:10.1145/5383.5385. S2CID  7387839.
  5. ^ де Ровер, Виллем-Поль; де Бур, Франк; Ханнеманн, Ульрих; Хуман, Йозеф; Лахнеч, Ясин; Поэль, Маннес; Цвиерс, Иов (ноябрь 2002 г.). Проверка параллелизма. Номер 54 в Кембриджских трактатах по теоретической информатике. Издательство Кембриджского университета. Дои:10.2277/0521806089 (неактивно 10.09.2020). ISBN  978-0-521-80608-4.CS1 maint: DOI неактивен по состоянию на сентябрь 2020 г. (связь)

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