Взаимоблокировка процессов.
12.12.2012
Стратегия организации процессов.
1й пришел, 1й обслуживается (FCFS)
Является наиболее простой стратегией процессоров и заключается в том что процессор передается тому процессу который раньше его запросил. Ему присущ эффект конвоя в том случае когда в компьютере имеется один большой процесс и несколько малых то все процессы собираются в очереди готовых процессов, а затем в очередь выполнения процессов. Эта стратегия уменьшает загруженность ЦП и ПУ.
Стратегия «Наиболее короткая работа выполняется первой» (SJF)
Является одним из методов борьбы с эффектом конвоя, позволяет процессу из очереди выполниться первым. SJF часто применяется в долгосрочных планировщиках обслуживающих пакетный режим.
Приоритетное планирование.
Эта стратегия предполагает, что каждому процессу приписывается приоритет определяющий очередность предоставления ему ЦП. Обычно приоритет – это целое, положительное число в некотором диапазоне. Приоритеты назначаются исходя из совокупности внутренних и внешних по отношению ОС факторов. Внутренние факторы:
1. Требование к памяти количество открытых файлов отношение среднего времени ввода/вывода к среднему времени использования ресурсов ЦП и тд.
Внешние факторы:
1. Важность процессов и тд.
Недостаток стратегии: блокирование на неопределенное время низкоприоритетных процессов.
Карусельная стратегия (RR)
Применяется в системах разделения времени, определяется отрезок времени, называемый квантом. Очередь готовых процессов рассматривается как кольцевая. Процессы циклически перемещаются по очереди, получается P на время равное кванту. Новый процесс добавляется в хвост очереди, если процесс не завершился в свой квант, то его работа принудительно прерывается и он перемещается в хвост очереди.
Взаимоблокировка процессов может происходить, когда несколько процессов борются за один ресурс. Ресурсы бывают выгружаемые и невыгружаемые. Выгружаемый ресурс можно забрать у процесса без потери данных. Невыгружаемый – нельзя забрать у процесса без потери данных. Проблема взаимоблокировок процессов возникают при борьбе за невыгружаемые ресурсы. Условие возникновения тупиков:
1. Условие взаимоисключений – одновременно использовать ресурс может только 1 процесс.
2. Условия ожидания ресурсов – процессы удерживают ресурс уже выделенный им, и могут запрашивать другие ресурсы.
3. Условие неперераспредиляемости – ресурс выделенный ранее не может быть принудительно забран у процесса, освобождены могут быть только удерживаемым их процессом.
4. Условия кругового ожидания – существует кольцевая цепь процессов в которой каждый ждет доступа к ресурсу удерживаемому другим процессом цепи.
Для образования тупика необходимым и достаточным является выполнением всех 4 условий. Основные направления борьбы с тупиками:
1. Игнорирование проблемы в целом
2. Предотвращение тупиков – цель предотвращения тупиков обеспечить условия исключающие возможность безопасно это или нет. Рассмотрим алгоритм банкира:
a. Предположим что у него n устройств
b. Операционная система принимает запрос от пользовательского процесса если его максимальная потребность не превышает n.
c. Пользователь гарантирует что если ОС в состоянии удовлетворить свой запрос, то устройства будут возвращены системе в течении конечного времени.
d. Текущее состояние системы называется надежным, если ОС может обеспечить всем процессам их выполнение в течении конечного времени.
e. В соответствии с данным алгоритмом выделении устройств возможно только если состояние системы остается надежным. Однако использование этого метода требует выполнении следующих условий:
i. Число пользователей и число ресурсов фиксировано
ii. Число работающих пользователей постоянно
iii. Клиенты гарантированно возвращают ресурсы
iv. Должны быть заранее указанны максимальные требования процессов к ресурсам.
3. Обнаружение тупиков
4. Восстановление после тупиков