Взаимоисключение для N процессов

Алгоритм Деккера

Алгоритм Деккера свободен от таких недостатков, как бесконечное откладывание.

program Dekker;

var р_n:l . . 2;

р_1, р_2 : boolean ;

procedure p1;

Begin

While true do

Begin

p_l:=true;

While p_2 do

if p_n=2 then

Begin

p_l:=false,

while p_n=2 do;

p_l:=true;

end;

кр_участок1;

р_n:=2;

p_l . =false;

прочие_операторы1;

end;

end;

procedure p2 ;

Begin

While true do

Begin

p_2:=true;

While p_l do

if p_n=l then

Begin

p_2:=false;

while p__n=l do;

p_2:=true;

end;

кр_участок2;

p_n:=1 ;

p_2:=false;

прочие_операторы2;

end ;

end ;

Begin

p_l:=false;

p_2:=false;

p_n:=l;

Parbegin

p1;

p2 ;

parend;

End.

Рис 1. Реализация примитивов взаимоисключения по алгоритму Деккера

.Конструкция «parbegin/parend» позволяет организовать параллельную работу процессов р1 и р2. Каждый из этих процессов представляет собой бесконечный цикл с многократным вхождением в свой критический участок. Процесс pl уведомляет о своем желании войти в свой критический участок, устанавливая флаг р1. Затем он переходит к циклу, в котором проверяет, не хочет ли также войти в свой критический участок и р2. Если флаг р_2 не установлен, р1 пропускает цикл ожидания и входит в свой критический участок. Предположим, что флаг р2 оказывается установленным, и процесс р1 входит в свой цикл ожидания. Здесь он анализирует значение переменной выбора процесса рn которая используется для разрешения конфликтов, возникающих при попытке двух процессов одновременно войти в свои критические участки. Если р_n=1, то pi пропускает тело своего цикла if и повторно выполняет цикл проверки в ожидании момента, когда р2 сбросит свой флаг. Если процесс pi определяет, что преимущественное право принадлежит процессу р2, то он сбрасывает свой собственный флаг р1 и блокируется в цикле ожидания, пока избранным процессом остается р2. Сбрасывая свой флаг, pi дает возможность процессу р2 войти в свой критический участок. Со временем р2 выйдет из своего критического участка, сбросит свой флаг р2 и возвратит преимущественное право процессу p1. Теперь процесс pi имеет возможность выйти из цикла ожидания и установить собственный флаг р1 Если флаг р_2 по-прежнему сброшен, то p1 может войта в свой критический участок. Если р2 вновь попытается войти в свой критический участок, то на этот раз преимущественное право находится уже у процесса р1 и ничто не может ему помешать войти в свой критический участок. Таким образом, Алгоритм Деккера обладает следующими свойствами:

• Не требует специальных аппаратных команд.

• Процесс, работающий вне своего критического участка, не может помешать другому процессу войти в свой критический участок.

• Процесс, желающий войти в критический участок, получает такую возможность без бесконечного откладывания.

Взаимоисключение для N процессов

Программное решение проблемы реализации примитивов взаимоисключения для n процессов первым предложил Дейкстра. Затем Кнут усовершенствовал алгоритм Дейкстры, исключив возможность бесконечного откладывания процессов, однако в варианте Кнута некоторый процесс по-прежнему мог испытывать (потенциально) длительную задержку. В связи с этим многие ученые начали искать алгоритмы, обеспечивающие более короткие задержки. Так, Эйзенберг и Макгайр предложили решение, гарантирующее, что процесс будет входить в свой критический участок не более чем за n-1 попыток. Лэмпорт разработал алгоритм, применимый, в частности, для распределенных систем обработки данных. Алгоритм Лэмпорта предусматривает “предварительное получение номерка”, подобно тому, как это делается в модных кондитерских, и поэтому получил наименование алгоритма кондитера (Bakery Algorithm). Бринк Хансен также предложил возможные варианты управления параллельными распределенными процессами.

Кроме программных, существуют и аппаратные реализации взаимоисключения, которые получили большое применение в современных мультипроцессорных системах, поскольку аппаратное управление взаимоисключением выполняется значительно быстрее.

Тупики

В мультипрограммной системе процесс находится в состоянии тупика, если он ожидает некоторого события, которое никогда не произойдет.

В компьютерной системе существует большое количество ресурсов, каждый из которых может использоваться в конкретный момент времени только одним процессом. Часто процесс для выполнения задачи нуждается в исключительном доступе не к одному, а к нескольким ресурсам. Предположим, что имеется два процесса A и B. Процесс A имеет в исключительном доступе ресурс R1, процесс B – ресурс R2. Если при этом процессу A для продолжения работы потребуется ресурс R2, то его запрос на получение ресурса будет отклонен до тех пор, пока ресурс не будет освобожден процессом B. Если же при этом процессу B для продолжения работы окажется необходимым иметь в исключительном доступе ресурс R1, то и процесс B окажется, как и процесс A, заблокированным. Такая ситуация называется тупиком, тупиковой ситуацией или взаимоблокировкой/ также дедлоками (deadlocks), клинчами (clinch)/

Условия возникновения тупиков

• Процессы требуют предоставления им права монопольного использования ресурсов, которые им выделяются (условие взаимоисключения).

• Процессы удерживают за собой ресурсы, уже выделенные им, ожидая в тоже время выделения дополнительных ресурсов (условие ожидания ресурсов).

• Уже выделенные ресурсы нельзя отобрать у процессов (условие неперераспределяемости).

• Существует цепь процессов, в которой каждый процесс удерживает ресурсы, требующиеся другому процессу (условие кругового ожидания).

Пример тупика. Пусть двум потокам, принадлежащим разным процессам и выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например принтер и последовательный порт. Такая ситуация может возникнуть, например, во время работы приложения, задачей которого является распечатка информации, поступающей по модемной связи.

На рисунке показаны фрагменты соответствующих программ. Поток А запрашивает сначала принтер; а затем порт, а поток В запрашивает устройства в обратном порядке. Предположим, что после того, как ОС назначила принтер потоку А и установила связанную с этим ресурсом блокирующую переменную, поток А был прерван. Управление получил поток В, который сначала выполнил запрос на получение СОМ-порта, затем при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым потоком А. Управление снова получил поток А, который в соответствии со своей программой

сделал попытку занять порт и был заблокирован, поскольку порт уже выделен потоку В. В таком положении потоки А и В могут находиться сколь угодно долго.

В зависимости от соотношения скоростей потоков они могут либо взаимно блокировать друг друга, либо образовывать очереди к разделяемым ресурсам, либо совершенно независимо использовать разделяемые ресурсы.

В рассмотренных примерах тупик был образован двумя потоками, но взаимно блокировать друг друга может и большее число потоков. Возможно такое распределение ресурсов R_iмежду несколькими потоками T_j, которое приводит к возникновению взаимных блокировок. Стрелки обозначают потребность потока в ресурсах. Сплошная стрелка означает, что соответствующий ресурс был выделен потоку, а пунктирная стрелка соединяет поток с тем ресурсом, который необходим, но не может быть пока выделен, поскольку занят другим потоком. Например, потоку Т₁ для выполнения работы необходимы ресурсы R₁ и R₂, из которых выделен только один — R₁, а ресурс R₂ удерживается потоком Т₂.

Ни один из четырех показанных на рисунке потоков не может продолжить свою работу, так как не имеет всех необходимых для этого ресурсов.

Невозможность потоков завершить начатую работу из-за возникновения взаимных блокировок снижает производительность вычислительной системы. Поэтому проблеме предотвращения тупиков уделяется большое внимание. На тот случай, когда взаимная блокировка все же возникает, система должна предоставить администратору средства, с помощью которых он смог бы распознать тупик, отличить его от обычной блокировки из-за временной недоступности ресурсов. И, наконец, если тупик диагностирован, то нужны средства для снятия взаимных блокировок и восстановления нормального вычислительного процесса.

Тупики могут быть предотвращены на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы тупик не мог возникнуть при любом соотношении взаимных скоростей потоков. Так, если бы в рассмотренном ранее примере поток А и поток В запрашивали ресурсы в одинаковой последовательности, то тупик был бы в принципе невозможен. Другой, более гибкий подход к предотвращению тупиков заключается в том, что ОС каждый раз при запуске задач анализирует их потребности в ресурсах и определяет, может ли в данной мультипрограммной смеси возникнуть тупик. Если да, то запуск новой задачи временно откладывается. ОС может также использовать определенные правила при назначении ресурсов потокам, например, ресурсы могут выделяться операционной системой в определенной последовательности, общей для всех потоков.

В исследованиях по проблеме тупиковможновыделить четыре основные направления:

• предотвращение тупиков;

• обход тупиков;

• обнаружение тупиков;

• восстановление после тупиков.

При предотвращении тупиков целью является обеспечение условий, исключающих возможность возникновения тупиковых ситуаций. Такой подход является эффективным, но приводит к нерациональному использованию ресурсов.

Методы обхода предусматривают применение специальных мер по обходу тупиковой ситуации в случае увеличения вероятности её возникновения.

Методы обнаружения тупиков применяются в системах, где допускается возможность возникновения тупиковой ситуации. Цель этих методов установить сам факт возникновения тупика и определить процессы и ресурсы, в него вовлеченные.

Методы восстановления после тупиков применяются для устранения тупиковых ситуаций, для обеспечения дальнейшей работы ОС и нормального завершения процессов, попавших в тупиковую ситуацию.

Существуют формальные, программно реализованные методы распознавания тупиков, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки.

Если же тупиковая ситуация возникла, то можно снять с выполнения только часть заблокированных потоков, освободив ресурсы, ожидаемые остальными потоками, можно вернуть некоторые потоки в область подкачки, можно совершить «откат» некоторых потоков до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в тех местах, после которых возможно возникновение тупика.

Предотвращение тупиков. Доказано, что возникновение тупика не возможно, если нарушено хотя бы одно из вышеуказанных четырех условий. Условие взаимоисключения, является необходимым и не может быть нарушено, следовательно нужно обратить внимание на оставшиеся три условия. Предотвращения тупиков можно добиться одним из трех способов, каждый из которых нарушает одно условие возникновения тупиков.

• Каждый процесс должен запрашивать все требуемые ему ресурсы сразу, причем не может начать выполнение до тех пор, пока все они не будут ему предоставлены.

Этот способ нарушает условие ожидания ресурсов. Но требование о том, что программа должна запрашивать все ресурсы сразу, а не по мере потребности, означает, что значительная часть ресурсов компьютера будет использоваться вхолостую. Кроме того, такая стратегия существенно увеличивает вероятность бесконечного откладывания, так как может никогда не оказаться свободным весь набор ресурсов, требуемый программе.

• Если процесс, удерживающий определенные ресурсы, получает отказ в удовлетворении запроса на дополнительные ресурсы, этот процесс должен освободить свои первоначальные ресурсы и затем запросить их снова вместе с дополнительными.

Этот способ нарушает условие неперераспределяемости, вынуждая процессы освобождать ресурсы до момента их завершения. Но в таком случае существует риск, что вместе с освобождаемыми ресурсами процесс может потерять всю работу, проделанную до этого момента.

Если известно, что в данный момент состояние является надежным это не значит, что оно все время будет оставаться таковым. Например, если в данной ситуации процесс П1 запросит дополнительный ресурс, а ОС его выделит, то состояние станет ненадежным.

Рис. 1.Пример ненадежного состояния.

В подобной ситуации независимо от того, какой процесс запросит оставшийся резервный ресурс, нельзя гарантировать, что все три процесса смогут закончить свою работу. Если ни один из процессов не вернет ресурсы, выделенные ему, то дальнейшие запросы ОС не сможет удовлетворять и можно будет констатировать наличие тупиковой ситуации.

Сейчас уже ясно, каким образом осуществляется распределение ресурсов согласно алгоритму банкира. При этом сохраняются все четыре условия возникновения тупиковой ситуации и ОС не создает процессам каких либо ограничений в распределении ресурсов, пока состояние остается надежным. Согласно алгоритму банкира система удовлетворяет только те запросы, при которых её состояние остается надежным. Однако алгоритм банкира имеет и ряд недостатков;

• Количество ресурсов должно быть фиксированным;

• Количество процессов должно оставаться постоянным;

• Конечный период времени, за который гарантированно выполняются запросы, может быть весьма большим;

• Пользователи должны до начала выполнения указывать максимальную потребность в ресурсах.

Обнаружение тупиков - это установление факта наличия тупиковой ситуации и определение процессов и ресурсов, вовлеченных в тупиковую ситуацию. Обычно алгоритмы обнаружения тупиков работают в системах, где выполняются три первых условия возникновения тупиков и проверяют, не возник ли режим кругового ожидания. Применение алгоритмов обнаружения тупиков связано с дополнительными затратами машинного времени. Следовательно, при реализация в ОС алгоритма обнаружения тупиков нужно ответить на вопрос «В каких случаях, и как часто нужно выполнять алгоритм обнаружения тупиков и не будут ли накладные расходы превышать эффект от локализации и устранения тупиков? »

Восстановление после тупиков. В современных системах восстановление после тупиков осуществляется, как правило, путем принудительного вывода некоторого процесса из системы, чтобы остальные процессы могли использовать его ресурсы и завершить свою работу. В некоторых случаях требуется уничтожить несколько процессов, чтобы остальные получили возможность завершения. Важное значение имеет определение процессов, подлежащих уничтожению. При этом могут использоваться такие критерии как: приоритет, суммарное время выполнения, количество используемых ресурсов.

Оптимальным способом восстановления после тупиков является механизм приостановки/возобновления процессов, но не все системы имеют такие возможности и не все процессы допускают приостановку. Этот механизм позволяет перевести процесс в состояние ожидания, а затем вновь активизировать, причем без потери результатов работы. Исследования в этой области важны и для обеспечения возможности временного отключения системы без потери промежуточных результатов.

Дата добавления: 2015-07-26; просмотров: 342; Нарушение авторских прав

Мы поможем в написании ваших работ!