24519

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

Доклад

Информатика, кибернетика и программирование

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

Русский

2013-08-09

35.63 KB

33 чел.

Вопрос 24. Взаимные блокировки процессов. Методы предотвращения, обнаружения и ликвидации тупиков.

§4.4.6. Синхронизирующие объекты ОС.

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

Например, в ОС Windows NT используются следующие объекты синхронизации:

 критические секции (для потоков одного процесса);

 семафоры;

 мьютексы (mutexmutual exclusion) – двоичные семафоры для синхронизации потоков разных процессов;

события (events) – используются с целью оповещения потоков о свершении какого-либо события;

таймеры – используются для формирования временных интервалов или конкретного времени взаимодействия потоков.

Тупики.

Тупики – это взаимные блокировки процессов, называемые также дедлоками (deadlocks) или клинчами (clinch).

В приведенном выше примере (см. рис. 4.11) если переставить местами операции P(e) и P(b) в программе "писателе", то при некотором стечении обстоятельств эти два процесса могут взаимно заблокировать друг друга. Действительно, пусть "писатель" первым войдет в критическую секцию и обнаружит отсутствие свободных буферов. Он начнет ждать, когда "читатель" возьмет очередную запись из буфера, но "читатель" не сможет этого сделать, так как для этого необходимо войти в критическую секцию, вход в которую заблокирован процессом "писателем".

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

Рис. 4.12. Возникновение взаимных блокировок при выполнении программы:

a – фрагменты программ А и В;  б – взаимная блокировка;

в – очередь к диску; г – независимое использование ресурсов

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

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

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

Проблема тупиков включает в себя решение следующих задач: предотвращение тупиков; распознавание тупиков; восстановление системы после тупиков.

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

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

Восстановление системы после тупиков реализуется следующими способами:

- снять с выполнения некоторые процессы для освобождения части ресурсов;

- вернуть некоторые процессы в область свопинга;

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

Из всего вышесказанного ясно, что использовать семафоры нужно очень осторожно, так как одна незначительная ошибка может привести к останову системы. Для облегчения написания корректных программ, было предложено высокоуровневое средство синхронизации, называемое монитором.

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

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


 

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

45328. Референдум – понятие, виды правовое регулирование 25.75 KB
  Форма прямого волеизъявления граждан РФ по наиболее важным вопросам государственного и местного значения в целях принятия решений осуществляемого посредством голосования граждан РФ обладающих правом на участие в референдуме. Виды референдума в зависимости от территории: 1 всероссийский референдум он проводится по вопросам общефедерального значения на основании решения Президента РФ; 2 референдум субъекта РФ он проводится по вопросам ведения соответствующего субъекта РФ или совместного ведения РФ и субъектов РФ если указанные вопросы не...
45329. Функции Президента Российской Федерации 21 KB
  Назначение с согласия Государственной Думы Председателя Правительства РФ других членов Правительства РФ направление его политики и принятие решения об отставке Правительства РФ; 2 представление Государственной Думе кандидатуры на должность Председателя Центрального банка РФ постановление перед ней вопроса об освобождении от должности Председателя Центрального банка РФ; 3 представление Совету Федерации кандидатур для назначения на должности судей Конституционного Суда РФ...
45330. Порядок избрания и освобождения от должности Президента Российской Федерации 23.1 KB
  Порядок избрания и освобождения от должности Президента Российской Федерации. Президент Российской Федерации избирается сроком на шесть лет гражданами Российской Федерации на основе всеобщего равного и прямого избирательного права при тайном голосовании. Президентом Российской Федерации может быть избран гражданин Российской Федерации не моложе 35 лет постоянно проживающий в Российской Федерации не менее 10 лет Одно и то же лицо не может занимать должность Президента Российской Федерации более двух сроков подряд. Порядок выборов Президента...
45331. ИНСТИТУТ УПОЛНОМОЧЕННОГО ПО ПРАВАМ ЧЕЛОВЕКА В РФ 22.83 KB
  ИНСТИТУТ УПОЛНОМОЧЕННОГО ПО ПРАВАМ ЧЕЛОВЕКА В РФ В РФ защитой прав и свобод граждан их соблюдения государственными органами власти органами местного самоуправления и должностными лицами занимается Уполномоченный по правам человека в РФ. В пределах своей компетенции Уполномоченный по правам человека в РФ: 1 рассматривает жалобы граждан РФ и находящихся на территории РФ иностранных граждан и лиц без гражданства; 2 рассматривает жалобы на решения или действия государственных органов органов местного самоуправления должностных лиц...
45332. Государственная Дума Российской Федерации - палата Федерального Собрания Российской Федерации 26.28 KB
  Полномочия местного самоуправления это закрепленные федеральным законодательством а также нормативными правовыми актами субъектов Российской Федерации и правовыми актами органов местного самоуправления за населением соответствующих территорий выборными и иными органами местного самоуправления права и обязанности связанные с реализацией задач и функций местного самоуправления на соответствующей территории. Полномочия местного самоуправления реализуются как непосредственно населением городских и сельских поселений других территорий путем...
45333. Конституционно-правовой статус члена Совета Федерации и депутата Государственной Думы 25.69 KB
  Конституционно-правовой статус члена Совета Федерации и депутата Государственной Думы Конституционно-правовой статус члена Совета Федерации и депутата Государственной Думы определяется Конституцией РФ ст. О статусе члена Совета Федерации и депутата Государственной Думы Федерального Собрания Российской Федерации. Депутатом Государственной Думы является избранный представитель народа уполномоченный осуществлять в Государственной Думе законодательные и иные полномочия предусмотренные Конституцией РФ и федеральным законом. Срок полномочий...
45334. Система законодательных (представительных) и исполнительных органов государственной власти субъектов Российской Федерации 20.8 KB
  Система законодательных представительных и исполнительных органов государственной власти субъектов Российской Федерации устанавливается ими самостоятельно в соответствии с основами конституционного строя Российской Федерации и ФЗ от 06. Об общих принципах организации законодательных представительных и исполнительных органов государственной власти субъектов Российской Федерации.Образование формирование деятельность законодательных представительных и исполнительных органов государственной власти субъектов Российской Федерации их...
45335. Законодательный процесс в РФ 25.93 KB
  В составе городского поселения также могут находиться сельские населенные пункты не имеющие статуса сельских поселений в которых местное самоуправление осуществляется населением непосредственно и или через выборные и иные органы местного самоуправления. Городской округ городское поселение которое не входит в состав муниципального района и органы местного самоуправления которого осуществляют полномочия по решению установленных законом вопросов местного значения поселения и вопросов местного значения муниципального района а также могут...
45336. Подходы к построению систем искусственного интеллекта 33 KB
  Структурный подход Под структурным подходом подразумевается попытки построить искусственный интеллект путём моделирования структуры человеческого мозга. Основной моделируемой структурной единицей в персептронах как и в большинстве других вариантов моделирования мозга является нейрон. Позднее возникли и другие модели которые обычно называют нейронные сети . Эти модели различаются по строению отдельных нейронов по топологии связей между ними и по алгоритмам обучения.