|
Читайте также: |
процессодин;
процессдва;
Parend end;
Рис. 5.5 Программная реализация примитивов взаимоисключения (версия 3).
В версии 4 (рис. 5.6) для этого предусматривается периодическая кратковременная установка ложного значения флага каждым вошедшим в цикл процессом. Благодаря этому другой процесс получает возможность выйти из своего цикла ожидания при по-прежнему установленном собственном флаге.
program версиячетыре;
var п1хочетвойти, п2хочетвойти: логический:
procedure процессодин;
Begin
while истина do begin
п1хочетвойти: = истина
while п2хочетвойти do begin
п1хочетвойти: = ложь;
задержка (случайная, несколькотактов);
п1хочетвойти: = истина
End
критическийучастокодин;
п1хочетвойти: = ложь;
прочиеоператорыодин
End
End;
procedure процессдва;
Begin
while истина do begin
п2хочетвойти: = истина;
while п1хочетвойти do begin
п2хочетвойти: = ложь;
задержка (случайная, несколькотактов);
п2хочетвойти: = истина
End
критическийучастокдва;
п2хочетвойти: = ложь;
прочиеоператорыдва
End
End;
Begin
п1хочетвойти: = ложь;
п2хочетвойти: = ложь;
Parbegin
процессодин;
процессдва parend
End;
Рис. 5.6 Программная реализация примитивов взаимоисключения (версия 4).
program алгоритмДеккера;
Var
избранныйпроцесс: (первый, второй);
п 1 хочетвойти, п2хочетвойти: логический;
procedure процессодин;
Begin
while истина do begin
п1хочетвойти: = истина;
while п2хочетвойти do
if избранныйпроцесс = второй then
Begin
п1 хочетвойти: = ложь;
while избранныйпроцесс = второй do;
п1хочетвойти: = истина
End
критическийучастокодин;
избранныйпроцесс: = второй;
п1 хочетвойти: = ложь;
прочиеоператорыодин
End
End;
procedure процессдва;
Begin
while истина do begin
п2хочетвойти: = истина
while п1 хочетвойти do
if избранныйпроцесс = первый then begin
п2хочетвойти: = ложь;
while избранныйпроцесс = первый do;
п2хочетвойти: = истина
End
критическийучастокдва;
избранныйпроцесс: = первый;
п2хочетвойти: = ложь;
прочиеоператорыдва
End
End;
Begin
п1 хочетвойти: = ложь;
п2хочетвойти: = ложь;
избранныйпроцесс: = первый;
Parbegin
процессодин;
процессдва
Parend
End;
Рис. 5.7. Реализация примитивов взаимоисключения согласно алгоритму Деккера.
В программе версии 4 гарантируется взаимоисключение и отсутствие тупика, однако возникает другая потенциальная проблема, также очень неприятная, а именно бесконечное откладывание.
Рассмотрим, каким образом это происходит.
Поскольку мы не можем делать никаких предположений об относительных скоростях асинхронных параллельных процессов, мы должны проанализировать все возможные последовательности выполнения программы.
Процессы здесь могут, например, выполняться «тандемом», друг за другом в следующей последовательности: каждый процесс может установить истинное значение своего флага; произвести проверку в начале цикла; войти в тело цикла; установить ложное значение своего флага; снова установить истинное значение флага; повторить всю эту последовательность, начиная с проверки при входе в цикл.
Когда процессы будут выполнять все эти действия, условия проверки будут оставаться истинными. Естественно, подобный режим работы весьма маловероятен — однако все же в принципе возможен. Поэтому версия 4 также оказывается неприемлемой.
Программу, реализующую взаимоисключение таким способом, нельзя применять, например, в системе управления космическими полетами, управления воздушным движением или в водителе ритма сердца человека, где даже малая вероятность бесконечного откладывания процесса и последующий отказ системы в целом категорически недопустимы.
Алгоритм, предложенный Деккером, позволяет при помощи небольшого по объему программного кода (рис. 5.7) изящно решить проблему взаимоисключения для двух процессов, не требуя при этом никаких специальных аппаратно-реализованных команд.
Алгоритм Деккера исключает возможность бесконечного откладывания процессов, из-за которых программа версии 4 неприемлема.
Рассмотрим, каким образом это делается.
Процесс «п1» уведомляет о желании войти в свой критический участок, устанавливая свой флаг. Затем он переходит к циклу, в котором проверяет, ре хочет ли также войти в свой критический участок и «п2». Если флаг «п2» не установлен, то «п1» пропускает тело цикла ожидания и входит в свой критический участок.
Предположим, однако, что «п1» при выполнении цикла проверки обнаруживает, что флаг «п2» установлен.
Это заставляет «п1» войти в тело своего цикла ожидания.
Здесь он анализирует значение переменной «избранныйпроцесс», которая используется для разрешения конфликтов, возникающих в случае, когда оба процесса одновременно хотят войти в свой критический участок. Если избранным процессом является «п1», он пропускает тело своего цикла if и повторно выполняет цикл проверки в ожидании момента, когда «п2» сбросит свой флаг. (Мы вскоре увидим, что «п2» со временем должен это сделать.)
Если процесс «п1» определяет, что преимущественное право принадлежит процессу «п2», он входит в тело своего цикла if, где сбрасывает свой собственный флаг, а затем блокируется в цикле ожидания, пока избранным процессом остается «п2». Сбрасывая свой флаг, «п1» дает возможность «п2» войти в свой критический участок.
Со временем «п2» выйдет из своего критического участка и выполнит свой код «выходвзаимоисключения». Операторы этого кода обеспечат возврат преимущественного права процессу «п1» и сброс флага «п2». Теперь у «п1» появляется возможность выйти из внутреннего цикла ожидания while и установить собственный флаг. Затем «п1» выполняет внешний цикл проверки. Если флаг «п2» (недавно сброшенный) по-прежнему сброшен, то «п1» входит в свой критический участок. Если, однако, «п2» сразу же пытается вновь войти в свой критический участок, то его флаг будет установлен, и «п1» снова придется войти в тело внешнего цикла while. Однако на этот раз «бразды правления» находятся уже у процесса «п1», поскольку сейчас именно он является избранным процессом (напомним, что «п2», выходя из своего критического участка, установил для переменной «избранный процесс» значение «первый»). Поэтому «п1» пропускает тело условной конструкции if и многократно выполняет внешний цикл проверки, пока «п2» «смиренно» не сбросит собственный флаг, позволяя процессу «п1» войти в свой критический участок.
Дата добавления: 2015-02-16; просмотров: 77 | Поможем написать вашу работу | Нарушение авторских прав |