Запросы и взаимоблокировки в срв. Методы предупреждения взаимоблокировки.
Взаимоблокировка процессов может происходить, когда несколько процессов борются за один ресурс.
Ресурсы бывают выгружаемые и невыгружаемые, аппаратные и программные.
Выгружаемый ресурс - этот ресурс безболезненно можно забрать у процесса (например: память).
Невыгружаемый ресурс - этот ресурс нельзя забрать у процесса без потери данных (например: принтер).
Проблема взаимоблокировок процессов возникает при борьбе за невыгружаемый ресурсы.
Условия необходимые для взаимоблокировки:
Условие взаимного исключения - в какой-то момент времени, ресурс занят только одним процессом или свободен.
Условие удержания и ожидания - процесс, удерживающий ресурс может запрашивать новые ресурсы.
Условие отсутствия принудительной выгрузки ресурса.
Условие циклического ожидания - должна существовать круговая последовательность из процессов, каждый, из которого ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
Методы борьбы с взаимоблокировками
Пренебрежением проблемой в целом (вдруг пронесет).
Обнаружение и устранение (взаимоблокировка происходит, но оперативно ликвидируется).
Динамическое избежание тупиков.
Предотвращение четырех условий, необходимых для взаимоблокировок.
Предотвращение условия взаимного исключения
Можно минимизировать количество процессов борющихся за ресурсы.
Например, с помощью спулинга для принтера, когда только демон принтера работает с принтером.
Предотвращение условия удержания и ожидания
Один из способов достижения этой цели, это когда процесс должен запрашивать все необходимые ресурсы до начала работы. Если хоть один ресурс недоступен, то процессу вообще ничего не предоставляется.
Предотвращение условия отсутствия принудительной выгрузки ресурса
Можно выгружать ресурсы, но могут быть проблемы с принтером.
Предотвращение условия циклического ожидания
Способы предотвращения:
Процесс сначала должен освободить занятый ресурс, прежде чем занять новый.
Можно пронумеровать все ресурсы (и упорядочить), и процессы должны запрашивать ресурсы только по возрастающему порядку.
Статический алгоритм планирования процессов - RMS.
Процессы должны удовлетворять условиям:
Процесс должен быть завершен за время его периода
Один процесс не должен зависеть от другого
Каждому процессу требуется одинаковое процессорное время на каждом интервале
У непериодических процессов нет жестких сроков
Прерывание процесса происходит мгновенно
Приоритет в этом алгоритме пропорционален частоте.
Процессу А он равен 33 (частота кадров)
Процессу В он равен 25
Процессу С он равен 20
Процессы выполняются по приоритету.
Динамический алгоритм планирования процессов – EDF.
Наибольший приоритет выставляется процессу, у которого осталось наименьшее время выполнения.
При больших загрузках системы EDF имеет преимущества.
Рассмотрим пример, когда процессу А требуется для обработки кадра - 15мс.
Проверяем, можно ли планировать эти процессы.
15/30+15/40+5/50=0.975<1
Загрузка системы 97.5%
Динамический алгоритм планирования EDF (Earliest Deadline First)
Алгоритм планирования RMS терпит неудачу.
Локализация и ликвидация взаимоблокировок.
Взаимоблокировка возникает, когда две и более задач постоянно блокируют друг из-за того, что задача каждой из сторон блокирует ресурс, необходимый другой стороне.
Возникновение тупиков является потенциальной проблемой любой операционной системы. Они возникают, когда имеется группа процессов, каждый из которых пытается получить исключительный доступ к некоторым ресурсам и претендует на ресурсы, принадлежащие другому процессу. В итоге все они оказываются в состоянии бесконечного ожидания.
С тупиками можно бороться, можно их обнаруживать, избегать и восстанавливать систему после тупиков. Однако цена подобных действий высока и соответствующие усилия должны предприниматься только в системах, где игнорирование тупиковых ситуаций приводит к катастрофическим последствиям.
Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.
Условие взаимоисключения (Mutual exclusion). Одновременно использовать ресурс может только один процесс.
Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.
Условие неперераспределяемости (No preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.
Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.
Для образования тупика необходимым и достаточным является выполнение всех четырех условий.
Обычно тупик моделируется циклом в графе, состоящем из узлов двух видов: прямоугольников – процессов и эллипсов – ресурсов, наподобие того, что изображен на рис. 7.1. Стрелки, направленные от ресурса к процессу, показывают, что ресурс выделен данному процессу. Стрелки, направленные от процесса к ресурсу, означают, что процесс запрашивает данный ресурс.