28. Понятие взаимоблокировки процессов. Что такое ресурс? Типы ресурсов, последовательность событий, необходимых для использования ресурса

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

А также выгружаемыми и невыгружаемыми. Выгружаемые — могут быть безболезнено отобраны у процесса. Привером может служить память. Если у процесса заканчивается квант времени и высиления процесса могут быть выгружены на диск без какого-либо ущерба. Невыгружаемые нельзя выгрузить без нанесение ущерба системе. Нпр. Запись на компакт диски.

29-30-31.

Условия, необходимые для возникновения взаимоблокировки процессов.

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

Моделирование тупиков с помощью графов.

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

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

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

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

2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.

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

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

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

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

32-33. Методы борьбы с взаимоблокировками процессов: обнаружение взаимоблокировки при наличии одного ресурса каждого типа.

Методы борьбы с взаимоблокировками процессов: обнаружение взаимоблокировки при наличии нескольких ресурсов каждого типа.

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

Итак, основные направления борьбы с тупиками:

Игнорирование проблемы в целом (страусиный алгоритм)

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

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

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

Начнем с самого простого варианта: в системе существует только один ресурс каж­дого типа. Подобная система могла бы иметь один сканер, одно устройство для за­писи компакт-дисков, один плоттер и один накопитель на магнитной ленте, то есть не более чем по одному представителю каждого класса. Другими словами, мы ис­ключаем из рассмотрения системы с двумя одновременно подключенными прин­терами. Мы обратимся к ним позже и будем использовать другой метод.

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