24519

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

Доклад

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

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

Русский

2013-08-09

35.63 KB

31 чел.

Вопрос 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, г).

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

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

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

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

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

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

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

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

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

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

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

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


 

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

24181. Причины феодальной раздробленности Древнерусского государства 42.71 KB
  Причины феодальной раздробленности Древнерусского государства Для возникновения феодальной раздробленности были экономические социальные и этнические причины. Появление изгоев и закупов свидетельствует о наличии расслоения в старой свободной общине и создании категорий крестьян вынужденных вступать в поземельную зависимость не от государства а от частных господ. На этом более высоком уровне феодализации политическая раздробленность Древнерусского государства была закономерной и вела к укреплению его функций в интересах отдельных земель...
24182. Положительные и отрицательные последствия феодальной раздробленности 17.63 KB
  Положительные: 1 трудности жизни на юге заставляли людей уходить на север и восток страны заселяя и осваивая эти прежде неразвитые окраины древней Руси. Значение периода феодальной раздробленности в русской истории У политической раздробленности как у любого исторического явления есть и положительные и отрицательные стороны: 1. Положительные: исчезла пропасть между центрами и окраинами; последние превратились в самостоятельные княжества которые по уровню хозяйственного социальнополитического и культурного развития превосходили Киевскую...
24183. Сущность социальных отношений 47 KB
  Социальные нормы – это средства социальной регуляции поведения индивидов и групп. Социальная роль – это социальная функция модель поведения объективно заданная социальной позицией личности в системе социальных и межличностных отношений. С социальной стратификацией связано понятие социальной мобильности. Под социальной мобильностью понимается любой переход индивида или социального объекта ценности то есть всего того что создано или модифицировано человеческой деятельностью из одной социальной позиции в другую.
24184. Классификация социальных процессов 50 KB
  В тех случаях когда цели и способы их достижения у индивида или группы не могут удовлетворить индивида компромисса достичь не удается и индивид не приспосабливается к новым условиям окружающей среды. Ассимиляция ссимиляция это процесс взаимного культурного проникновения через который личности и группы приходят к разделяемой всеми участниками процесса общей культуре. Это всегда двухсторонний процесс в котором каждая группа имеет возможности для проникновения своей культуры в другие группы пропорционально своему размеру престижу и другим...
24185. Применение имитационного моделирования 47.5 KB
  Имитационное моделирование это частный случай математического моделирования. Применение имитационного моделирования К имитационному моделированию прибегают когда: дорого или невозможно экспериментировать на реальном объекте; невозможно построить аналитическую модель: в системе есть время причинные связи последствие нелинейности стохастические случайные переменные; необходимо сымитировать поведение системы во времени. Цель имитационного моделирования состоит в воспроизведении поведения исследуемой системы на основе результатов...
24186. АЛЛЕРГИЯ 276 KB
  В поддержании аллергического иммунного ответа важны долговременные клетки памяти в т. Схема 1 Классификация аллергических реакций: Влмфзависимые Активные Немедленная по ДжеллКумбсу гуморальные и анафилаксия 1й тип реагины Тлмфзависимые Пассивные Отсроченная 5 ч 2й цитолиз клеточные АТ и клетки Замедленная дни 3й имм. Неклеточные структуры тканей коллагена миелина базальной мембраны почек – вовлекаются соседние клетки вторично. Медиаторы: гаммаинтерферон...
24187. ПАТОЛОГИЯ ВОДНО-СОЛЕВОГО ОБМЕНА 289.5 KB
  Эфферентная часть: основной механизм – регуляция почек – диуреза: а Вегетативная нервная симпатическая адреналин – чревный нерв – снижение диуреза; б Гипоталамогипофизарная регуляция: супраоптические и паравентрикулярные ядра – АДГ задний гипофиз – почечные канальцы гиалуронидаза – активация реабсорбции – тоже снижение диуреза; в передний гипофиз – АКТГ – надпочечники – альдостерон – почечные канальцы сукцинатдегидрогеназа – усиление реабсорбции Na и пассивно – воды г диэнцефальный мозг адреногломерулотропин –...
24188. КИСЛОТНО-ОСНОВНОЕ СОСТОЯНИЕ 70 KB
  Начальные сдвиги и компенсаторные реакции при нарушениях КОС Нарушения КОС Сдвиг КОС Компенсация Дыхательные Ацидоз рН  рСО2 НСО3 Алкалоз рН рСО2 НСО3 Негазовые Ацидоз рН НСО3 рСО2 Алкалоз рН НСО3 рСО2 Схема 1 Работа гемоглобиновой буферной системы Легкие О2 Нв НвО2 СО2  Кровь: венозный_Нв артериальный_НвО2щелочные_продукты  Нв  ...
24189. ПАТОФИЗИОЛОГИЯ ОБМЕНА БЕЛКА И НК 374 KB
  ПАТОФИЗИОЛОГИЯ ОБМЕНА БЕЛКА И НК Роль белков в организме незаменимые аминокислоты типы синтеза белка типы патологии белкового обмена типы алиментарной недостаточности периоды голодания и особенности обмена; синдром мальадсорбции; нарушения синтеза белка в клетке; диспротеинозы; амилоидоз – формы теории развития стадии; подагра. Пластическая роль белков структурная основа тканей и основа ферментов определяет их главенствующую роль в метаболизме. В отличие от жиров и углеводов полное белковое голодание даже при наличии...