· Условие взаимоисключения (Mutual exclusion). Одновременно использовать ресурс может только один процесс.
· Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.
· Условие неперераспределяемости (No preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.
· Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.
Для образования тупика необходимым и достаточным является выполнение всех четырех условий.
Основные направления борьбы с тупиками
· Игнорирование проблемы в целом
· Предотвращение тупиков
· Обнаружение тупиков
· Восстановление после тупиков
Управление процессами. Тупики. Алгоритм банкира.
· Заранее объявлять все необходимые заданию ресурсы.
· Перед назначением ресурса осуществлять проверку на возможность возникновения клинчей. Если эта возможность исключена, то ресурс можно назначить.
Каждому процессу поставлено в соответствие целое число i(1<=i<=N).
Процессу i соответствует его максимальная потребность в устройствах МАКС[i], количество устройств, выделенных ему в данный момент (ВЫДЕЛУСТР[i]), полагающийся ему остаток (ОСТАТОК[i]) и признак (МОЖЕТ_НЕ_ОКОНЧИТЬСЯ[i]).
Система заводит глобальную переменную ОБЩ, обозначающую общее число имеющихся в системе устройств.
В начале работы неизвестно, может ли какой-либо процесс окончиться (МОЖЕТ_НЕ_ОКОНЧИТЬСЯ[i]=true для всех i).
Каждый раз, когда какой-то ОСТАТОК может быть выделен из числа остающихся незанятыми устройств, предполагается, что соответствующий процесс работает, пока не окончится, а затем его устройства освобождаются.
Если в конце концов все устройства освободятся, значит, все процессы могут окончиться и система находится в безопасном состоянии. Если состояние системы не безопасное, то она не удовлетворяет рассматриваемый запрос.
Begin
СВОБУСТР:=ОБЩУСТР;
For i:= 1 to N do Begin
СВОБУСТР:= СВОБУСТР – ВЫДЕЛУСТР[i];
МОЖЕТ_НЕ_ОКОНЧИТЬСЯ[i]:=true;
ОСТАТОК[i]:= МАКС[i]-ВЫДЕЛУСТР[i];
End;
ПРИЗНАК:=true;
WHILE (ПРИЗНАК) DO
ПРИЗНАК:=false;
For i:=1 to N do
Begin
If МОЖЕТ_НЕ_ОКОНЧИТЬСЯ[i] and (ОСТАТОК[i] <= СВОБУСТР)
Then begin
МОЖЕТ_НЕ_ОКОНЧИТЬСЯ[i]:=false;
СВОБУСТР:= СВОБУСТР+ ВЫДЕЛУСТР[i];
ПРИЗНАК:=true
End;
End;
End;
End;
If СВОБУСТР= ОБЩУСТР then состояние системы БЕЗОПАСНОЕ
Else состояние системы НЕБЕЗОПАСНОЕ
Управление процессами. Тупики. Алгоритм Медника. Выход из тупика.
Метод обнаружения позволяет обнаружить ситуацию тупика, когда она уже произошла.
Не препятствуя возникновению тупика, метод предполагает его обнаружение и восстановление прерванной им нормальной работы.
Для функционирования алгоритма необходимо использование таблиц, в которых собиралась бы информация:
· о назначении ресурсов процессам (РАСПРЕД)
· о процессах, блокированных при попытке обращения к ресурсу (БЛК).
НАЧАЛО «МЕДНИК»
(*Процесс Рj запрашивает занятый ресурс Уi*)
К = РАСПРЕД (i) (*К – номер процесса владеющего ресурсом Уi*)
ЦИКЛ-ПОКА БЛК (К) и JK
J = К
N = БЛК (К) (*N – номер ресурса, которого ожидает*)
К = РАСПРЕД (N) (* рассматриваемый процесс*)
ВСЕ-ЦИКЛ
ЕСЛИ J = К ТУПИК
ИНАЧЕ БЛК (J) = i (*Перевести процесс Рi в состояние ожидания*)
ВСЕ-ЕСЛИ
КОНЕЦ «МЕДНИК»
Выход из тупика
· основан на прекращении процессов. Процессы в тупике последовательно прекращаются (уничтожаются) в некотором систематическом порядке до тех пор, пока не станет доступным достаточное количество ресурсов для устранения тупика; в худшем случае уничтожаются все процессы, первоначально находившиеся в тупике, кроме одного.
· основан на перехвате ресурсов. У процессов отнимается достаточное количество ресурсов и отдается процессам, находящимся в тупике, чтобы ликвидировать тупик; процессы в первом множестве остаются с выданными запросами на перехваченные у них ресурсы.
Управление памятью. Типы адресов. Типы распределения памяти.
Функциями ОС по управлению памятью являются:
· отслеживание свободной и занятой памяти,
· выделение памяти процессам и освобождение памяти при завершении процессов,
· вытеснение процессов из оперативной памяти на диск, когда размеры основной памяти не достаточны для размещения в ней всех процессов,
· возвращение их в оперативную память, когда в ней освобождается место,
· настройка адресов программы на конкретную область физической памяти.
Типы адресов
Для идентификации переменных и команд используются:
· символьные имена (метки)(идентификаторы переменных в программе на алгоритмическом языке)
· виртуальные адреса (условные адреса, вырабатываемые транслятором)
· физические адреса (номера ячеек физической памяти)