Взаимоблокировка процессов.

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. Восстановление после тупиков