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

Тупики

Состояние процесса.

1)Рождение. Процесс находится в этом состояние, когда рождена всего лишь 1 нить.

2)Готовность, если хотя бы одна из его нитей находится в состояние готовность и не одной в состояние исполнения.

3)Исполнение, если одна из его нитей находится в состояние исполнение.

4) Ожидания, если все его нити находятся в состояние ожидания.

5)Завершил исполнения, если все его нити находятся в состояние завершил исполнение.

Нить1 Нить2

Создать нить 2

Переключения контекста нитей

Ожидание ввода а,в

Переключение контекста нитей

Ввести массив а

Ожидание ввода массива а

Ввести массив в

Ожидание ввода массива в

Ввести массив с

Ожидание ввода массива с

Переключение контекста нитей

а =а +в

переключение контекста нитей

с =а +с

вывести массив с

Ожидание вывода массива с

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

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

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

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

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

Тупики могут иметь место:

1. На аппаратных ресурсах (пример с принтером);

2. На программных ресурсах.

Пример:

В системах управления базами данных (СУБД) могут быть локализованы записи каким-либо процессом. В этом случае может получиться так, что один из процессов заблокировал записи необходимые другому процессу и наоборот.

Ресурсами могут быть:

1. Устройства;

2. Данные.

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

Ресурсы делятся на:

1. Разделяемые;

2. выделенные.

Разделяемыми ресурсами называются ресурсы, которые допускают разделение между процессами (процессор, память, диски).

Выделенные ресурсы - это ресурсы, которые не допускают разделения (лентопротяжный механизм, регистры).

Пример:

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

Традиционная последовательность событий при работе с ресурсами состоит:

1. запрос ресурсов;

2. Использование ресурсов;

3. Освобождение ресурсов.

Тип запроса зависит от ОС и природы ресурса (явные и неявные).

Были сформированы в 1970 году Коффмоном, Элфиком, Шошани.

Условия:

1. Условие взаимоисключения – одновременно использовать ресурс может только один процесс.

2. Условие ожидания ресурса – процессы удерживают ресурсы уже выделенные им и могут запрашивать другие.

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

4. Условие кругового ожидания – существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу удерживаемому другим процессом цепи.

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