Проблема тупиков и методы борьбы с ними

 

Содержание

Введение

1.Понятия тупиковых ситуаций. Условия возникновения и обнаружения тупиков

       1.1 Тупиковые ситуации……………………………………………...……...5

       1.2 Условия возникновения тупиков………………………………...……...7

       1.3 Обнаружения тупиков……...………………………………………….....8 

2. Основные направления и способы борьбы с тупиками

1. Основные направления борьбы с тупиками……………...…………...11
2. Способы предотвращения тупиков…...……………………………….13

2.3 Предотвращение тупиков за счет нарушения условий возникновения                                                                                                                                                               тупиков……………………………………………………………………...16 

Заключение

Список используемой литературы

 

 

Введение

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

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

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

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

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

         Такая ситуация называется дедлоком (deadlock), клинчем (clinch) или тупиком.  Иногда − взаимоблокировкой.

         Взаимоблокировки вероятны во  множестве других ситуаций помимо  запросов выделенных устройств  ввода/вывода. В системах баз данных  программа может оказаться вынужденной  заблокировать несколько записей,  чтобы избежать состояния конкуренции.  Если процесс A блокирует запись R1, процесс B блокирует запись R2, а  затем каждый процесс попытается  заблокировать чужую запись, мы  также окажемся в тупике. Таким  образом, взаимоблокировки появляются  при работе, как с аппаратными,  так и с программными ресурсами.

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

         Задачи курсовой работы:

         1. рассмотреть понятие тупиковой  ситуации;

         2. изучить условия возникновения  тупиков;

         3. описать основные направления  и способы борьбы с тупиками; 
 
 
 
 
 
 

1. Понятия тупиковых ситуаций. Условия возникновения и обнаружения тупиков

1.1 Тупиковые ситуации

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

Рис. 1. Пример тупиковой ситуации 

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

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

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

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

     Традиционная  последовательность событий при  работе с ресурсом состоит из запроса, использования и освобождения ресурса. Тип запроса зависит от природы  ресурса и от ОС. Запрос может  быть явным, например специальный вызов request, или неявным – open для открытия файла. Обычно, если ресурс занят и  запрос отклонен, запрашивающий процесс  переходит в состояние ожидания. 
 

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

   Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.

1. Условие взаимоисключения (Mutual exclusion). Одновременно использовать ресурс может только один процесс.
2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.
3. Условие неперераспределяемости (No preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.
4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.

   Для образования тупика необходимым  и достаточным является выполнение всех четырех условий.  

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

1.3 Обнаружение тупиков

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

     Рассмотрим  модельную ситуацию.

Процесс P1 ожидает ресурс R1.

Процесс P2 удерживает ресурс R2 и ожидает  ресурс R1.

Процесс P3 удерживает ресурс R1 и ожидает  ресурс R3.

Процесс P4 ожидает ресурс R2.

Процесс P5 удерживает ресурс R3 и ожидает  ресурс R2. 

     Вопрос  состоит в том, является ли данная ситуация тупиковой, и если да, то какие  процессы в ней участвуют. Для  ответа на этот вопрос можно сконструировать  граф ресурсов, как показано на рис.3. Из рисунка видно, что имеется цикл, моделирующий условие кругового ожидания, и что процессы P2,P3,P5, а может быть, и другие находятся в тупиковой ситуации.

Рис.2. Граф ресурсов 

     Визуально легко обнаружить наличие тупика, но нужны также формальные алгоритмы, реализуемые на компьютере.

     Один  из таких алгоритмов описан в [Таненбаум, 2002], там же можно найти ссылки на другие алгоритмы.

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

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

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

     Сложность восстановления обусловлена рядом  факторов.

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

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

     Восстановление  после тупика может потребовать  значительных усилий.

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

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

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