Четверг, 23 Май 2024, 00:02
Uchi.ucoz.ru
Меню сайта
Форма входа

Категории раздела
Учителю физики [224]
Учителю химии [112]
Учителю биологии [744]
Учителю информатики [147]
Учителю математики [110]
Учителю русского языка [250]
Учителю астрономии [437]
Учителю иностранного языка [182]
Учителю истории (открытые уроки) [151]
Учителю обществознания [53]
Учителю истории [354]
Учителю труда [14]
Учителю ОБЖ [2]
Учителю искусствоведения [0]
Изо
Учителю белорусского языка и литературы [1]
Учителю допризывной и медицинской подготовки [0]
Учителю географии [9]
Учителю МХК [1]
Учителю музыки [3]
Учителю физкультуры [15]
Учителю черчения [0]
Новости
Чего не хватает сайту?
500
Статистика
Зарегистрировано на сайте:
Всего: 51637


Онлайн всего: 1
Гостей: 1
Пользователей: 0
Яндекс.Метрика
Рейтинг@Mail.ru

Каталог статей


Главная » Статьи » По предмету » Учителю информатики

Программная реализация примитивов взаимоисключения. Алгоритм Деккера – Дейкстры.
Здесь приведены последовательные хронологические версии программной реализации упомянутого алгоритма Деккера. Детальный анализ выполнения каждой из программ предлагается провести читателю.
program версияодин;
var номерпроцесса: целое;
procedure процессодин;
begin
while истина do
begin
while номерпроцесса = 2 do;
критическийучастокодин;
номерпроцесса :=2;
прочиеоператорыодин
end
end;
procedure процессдва;
begin
while истина do
begin
while номерпроцесса = 1 do;
критическийучастокдва;
номерпроцесса :=1;
прочиеоператорыдва
end
end;
begin
номерпроцесса:=1;
parbegin
процессодин;
процессдва
parend
end.

Эта программа гарантирует взаимоисключение дорогой ценой. «Процессодин» должен выполняться первым, т. о. если «процессдва» готов ко входу в свой критический участок, он может получить разрешение на это со значительной задержкой. После того, как «процессодин» войдет в свой критический участок и затем выйдет из него, должен будет снова выполняться «процессдва», даже если «процессодин» хочет вновь войти в свой критический участок, а «процессдва» еще не готов. Т.о. процессы должны входить и выходить из своих участков строго поочередно. Если одному процессу приходится это делать во много раз чаще, чем другому, то он вынужден работать с гораздо меньшей скоростью, чем это необходимо. Достоинство этой программы в том, что она не может оказаться в состоянии полного тупика; если оба процесса одновременно пытаются войти в свои критические участки, то по крайней мере одному из них удается продолжить свою работу. Недостатком этой программы является тот факт, что если один из процессов со временем завершится, то со временем другой окажется не в состоянии продолжить выполнение. В этой программе имеется только одна внешняя переменная и, таким образом возникает проблема жесткой синхронизации процессов.
program версиядва;
var п1внутри, п2внутри: логический;
procedure процессодин;
begin
while истина do
begin
while п2внутри do;
п1внутри := истина;
критическийучастокодин;
п1внутри := ложь;
прочиеоператорыодин
end
end;
procedure процессдва;
begin
while истина do
begin
while п1внутри do;
п2внутри := истина;
критическийучастокодин;
п2внутри := ложь;
прочиеоператорыдва
end
end;
begin
п1внутри := ложь;
п2внутри := ложь;
parbegin
процессодин;
процессдва
parend
end.

Вторая версия алгоритма Деккера (рис. 2) свободна от этого за счет наличия двух глобальных логических переменных (флагов-признаков) «п1внутри» и «п2внутри», которые имеют истинное значение, если «процессодин» или «процессдва» находятся
внутри своих критических участков соответственно.
Слабым местом этой версии программы является то, что между моментом, когда
процесс, находящийся в цикле ожидания, определяет, что он может идти дальше и
моментом, когда этот процесс устанавливает флаг-признак, говорящий о том, что он
вошел в свой критический участок, проходит достаточно времени, чтобы другой процесс
успел проверить еще не установленный флаг-признак и войти в свой критический участок.
Поэтому необходимо, чтобы в то время как один процесс выполняет свой цикл
ожидания, другой процесс не мог выйти из своего собственного цикла ожидания. Слабое
место этой программы – возможность одновременного входа в свои критические
участки.
program версиятри;
var п1хочетвойти, п2хочетвойти: логический;
procedure процессодин;
begin
while истина do
begin
п1хочетвойти := истина;
while п2хочетвойти do;
критическийучастокодин;
п1хочетвойти := ложь;
прочиеоператорыодин
end
end;
procedure процессдва;
begin
while истина do
begin
п2хочетвойти := истина;
while п1хочетвойти do;
критическийучастокдва;
п2хочетвойти := ложь;
прочиеоператорыдва
end
end;
begin
п1хочетвойти := ложь;
п2хочетвойти := ложь;
parbegin
процессодин;
процессдва
parend
end.
Программа версии 3 (рис. 3) позволила решить одну задачу, однако сразу же появилась другая. Здесь взаимоисключение регулируется при помощи двух глобальных логических переменных (флагов-признаков) «п1хочетвойти» и «п2хочетвойти», которые принимают истинное значение перед попыткой входа в свой критический участок. Если каждый процесс перед переходом на цикл проверки будет устанавливать свой флаг, то каждый процесс будет обнаруживать, что флаг другого процесса установлен и будет бесконечно оставаться в цикле while. Эта версия программы может служить примером тупика для двух процессов. Главный недостаток этой программы это, то, что каждый из процессов может заблокироваться в своем цикле ожидания while. Нужно найти способ «разорвать» эти циклы.
program версиячетыре;
var п1хочетвойти, п2хочетвойти!_u_[_(: логический;
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.
В программе версии 4 (рис. 4) гарантируется взаимоисключение и отсутствие тупика, однако возникает другая потенциальная проблема – бесконечное откладывание. Поскольку мы не можем делать никаких предположений об относительных скоростях асинхронных параллельных процессов, мы должны проанализировать все возможные последовательности выполнения программы. Процессы здесь могут выполняться «тандемом», друг за другом в следующей последовательности: каждый процесс может установить истинное значение своего флага; произвести проверку в начале цикла; войти в тело цикла; установить ложное значение своего флага; снова установить истинное значение флага; повторить всю эту последовательность, начиная с проверки при входе в цикл. Когда процессы будут выполнять эти действия, условия проверки будут оставаться истинными и до выполнения какого либо критического участка («критическийучастокодин» или «критическийучастокдва») процесс может дойти очень не скоро. Вызываемая процедура «задержка» позволяет случайным образом сократить время откладывания, но сразу возникают другие вопросы:
1. На сколько сократится время откладывания?
2. Какой процесс активизируется?
3. Как очередность исполнения критического участка зависит от процедуры?
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.
Алгоритм Деккера исключает недостаток программы версии 4 – бесконечное откладывание входа в свой критический участок. Рассмотрим, как это делается. Процесс «п1» уведомляет о своем желании войти в свой критический участок, устанавливая свой флаг (п1хочетвойти := истина). Затем он переходит к циклу, в котором проверяет, не хочет ли также войти в свой критический участок и процесс «п2» (while п2хочетвойти do…). Если флаг «п2» не установлен т. е. п2хочетвойти = ложь, то «п1» пропускает тело цикла ожидания и входит в свой критический участок. Предположим, что «п1» при выполнении цикла проверки обнаруживает, что флаг «п2» установлен. Это заставляет «п1» войти в тело своего цикла ожидания. Здесь он анализирует значение переменной «избранный процесс» ( if избранныйпроцесс = второй then …), которая используется для разрешения конфликтов, возникающих в случае, когда оба процесса одновременно хотят войти в свой критический участок. Если избранным процессом является «п1», он пропускает тело своего цикла if и повторно выполняет цикл проверки (while п2хочетвойти do…) в ожидании момента, когда «п2» сбросит свой флаг. Если процесс «п1» определяет, что преимущественное право принадлежит процессу «п2», он входит в тело своего цикла if, где сбрасывает свой собственный флаг(п1хочетвойти := ложь), а затем блокируется в цикле ожидания, пока избранным процессом остается «п2». Сбрасывая свой флаг, «п1» дает возможность «п2» войти в свой критический участок. Со временем «п2» выйдет из своего критического участка и выполнит свой код «выходвзаимоисключения» Операторы этого кода обеспечат возврат преимущественного права процессу «п1» (избранныйпроцесс := первый) и сброс флага «п2» (п2хочетвойти := ложь). Теперь у «п1» появляется возможность выйти из внутреннего цикла ожидания while (while избранныйпроцесс = второй do;) и установить собственный флаг (п1хочетвойти := истина). Затем «п1» выполняет внешний цикл проверки (while п2хочетвойти do…). Если флаг «п2» (недавно сброшенный) по-прежнему сброшен, то «п1» входит в свой критический участок. Если, однако, «п2» сразу же пытается войти в свой критический участок, то его флаг будет установлен, и «п1» снова придется войти в тело внешнего цикла while. Однако на этот раз «бразды правления» находятся уже у процесса «п1», поскольку сейчас именно он является избранным процессом (напомним, что «п2», выходя из своего критического участка, установил для переменной «избранный процесс» значение «первый»). Поэтому «п1» пропускает тело условной конструкции if и многократно выполняет внешний цикл проверки, пока «п2» «смиренно» не сбросит собственный флаг, позволяя процессу «п1» войти в свой критический участок. Проблема бесконечного откладывания –разобраться самим.
Категория: Учителю информатики | Добавил: Wrecker (04 Авг 2012)
Просмотров: 1121 | Рейтинг: 1.0/ 11 Оштрафовать | Жаловаться на материал
Похожие материалы
Всего комментариев: 0

Для блога (HTML)


Для форума (BB-Code)


Прямая ссылка

Профиль
Четверг
23 Май 2024
00:02


Вы из группы: Гости
Вы уже дней на сайте
У вас: непрочитанных сообщений
Добавить статью
Прочитать сообщения
Регистрация
Вход
Улучшенный поиск
Поиск по сайту Поиск по всему интернету
Наши партнеры
Интересное
Популярное статьи
Портфолио ученика начальной школы
УХОД ЗА ВОЛОСАМИ ОЧЕНЬ ПРОСТ — ХОЧУ Я ЭТИМ ПОДЕЛИТ...
Диктанты 2 класс
Детство Л.Н. Толстого
Библиографический обзор литературы о музыке
Авторская программа элективного курса "Практи...
Контрольная работа по теме «Углеводороды»
Поиск
Главная страница
Используются технологии uCoz