А.) Глобальная структура данных
if (alloc[i,*] + request[*] > claim[i,*j]
{
<Ошибка> /* Суммарный запрос превышает требования */
}
else if (request[*] > available [*])
{
<Приостановка процесса>
}
else /* Моделируем выполнение запроса */
{
<Определение нового состояния:
alloc[i,*] = alloc[i, *] + request[*];
available[*] = available[*] - request!*];
>
}
if (safe(newstate))
{
<Выполнение распределения> }
else {
<Восстановление исходного состояния >
<Приостановка процесса > }
б) Алгоритм выделения ресурсов
boolean safe (state S)
{
int currentavail[m];
process rest[<Количество процессов>];
currentavail = available;
rest = { Все процессы };
possible = true;
while(possible)
{
< Найти Pk в rest такой, что
claim[k,*] - alloc[k,*] <= currentavail; > if (<Найден>) /* Моделирование выполнения Pk */
{
currentavail = currentavail + alloc[k,*];
rest = rest - {Pk};
}
else
possible = false;
}
return (rest == NULL);
}
в) Проверка безопасности алгоритма (алгоритм банкира)
Устранение взаимоблокировок обладает тем достоинством, что при его использовании не нужны ни перераспределение, ни откат процессов, как в случае обнаружения взаимоблокировок; кроме того, этот метод накладывает меньше ограничений по сравнению с предотвращением взаимоблокировок. Однако использование этого метода требует выполнения определенных условий.
Должны быть заранее указаны максимальные требования каждого процесса к ресурсам.
Рассматриваемые процессы должны быть независимы, т.е. порядок их выполнения не должен ограничиваться никакими требованиями синхронизации.
Должно иметься фиксированное количество распределяемых ресурсов.
Ни один процесс не должен завершаться в состоянии захвата ресурсов.
6.4. Обнаружение взаимоблокировок
Стратегии предотвращения взаимоблокировок весьма консервативны; они решают проблему взаимоблокировок путем ограничения доступа процессов к ресурсам и наложения ограничений на процессы. Их противоположность — стратегии обнаружения взаимоблокировок, которые не ограничивают доступ к ресурсам и не налагают никаких ограничений на действия процессов. При обнаружении взаимоблокировок запрошенные ресурсы выделяются процессам при первой возможности. Периодически операционная система выполняет алгоритм, который позволяет обнаружить условия циклического ожидания (см. рис. 6.5).
Алгоритм обнаружения взаимоблокировки
Проверка наличия взаимоблокировки может выполняться как при каждом запросе ресурса, так и менее часто, в зависимости от того, насколько вероятно возникновение взаимоблокировки. С одной стороны, проверка при каждом запросе ресурса имеет два основных преимущества: раннее обнаружение и упрощение алгоритма, поскольку он основан на инкрементальных изменениях состояния системы. С другой стороны, столь частая проверка приводит к заметному потреблению времени процессора.
Обобщенный алгоритм обнаружения взаимоблокировок описан в [COFF71]. В нем используются матрица распределения и вектор доступности, описанные в предыдущем разделе. Кроме того, определена матрица запросов Q такая, что qij представляет собой количество ресурсов типа j, затребованное процессом i. Алгоритм работает, помечая незаблокированные процессы. Изначально все процессы не помечены. После этого выполняются следующие шаги.
Помечаем все процессы, у которых строки в матрице распределения состоят из одних нолей.
Временный вектор W инициализируем значениями вектора доступности.
Находим индекс i, такой, что процесс i в настоящий момент не помечен, и i-я строка матрицы Q не превышает W, т.е. для всех 1 < k < т выполняется Qik < Wk. Если такой строки нет, алгоритм прекращает свою работу.
Если такая строка имеется, помечаем процесс i и добавляем соответствующую строку матрицы распределения к W, т.е. выполняем присвоение Wk = Wk + Aik для всех 1<=k<=m . Возвращаемся к шагу 3.
Взаимоблокировка имеется тогда и только тогда, когда после выполнения алгоритма есть непомеченные процессы; каждый непомеченный процесс заблокирован. Стратегия этого алгоритма состоит в поиске процесса, запросы которого могут быть удовлетворены доступными ресурсами, а затем предполагается, что эти ресурсы ему выделены и процесс, завершив свою работу, освобождает их. После этого алгоритм приступает к поиску другого процесса, который может успешно завершить свою работу. Заметим, что данный алгоритм не гарантирует предотвращения взаимоблокировок — это зависит от порядка удовлетворения запросов процессов. Все, что делает данный алгоритм, — это определяет, имеется ли взаимоблокировка в настоящий момент.
Для иллюстрации алгоритма обнаружения взаимоблокировок рассмотрим рис. 6.8. Алгоритм работает следующим образом.
Помечаем Р4, поскольку этот процесс не имеет распределенных ему ресурсов.
Устанавливаем W = (0 0 0 0 1).
Запрос процесса Р3 не превышает W, так что помечаем Р3 и устанавливаем
W = W + (0 0 0 1 0) = (0 0 0 1 1).
Других непомеченных процессов, строки матрицы Q которых не превышают W, нет. Алгоритм прекращает свою работу.
Таким образом, алгоритм позволяет заключить, что процессы Р1 и Р2 взаимно заблокированы.
