Стратегия организации процессов.

1й пришел, 1й обслуживается (FCFS)

Является наиболее простой стратегией процессоров и заключается в том что процессор передается тому процессу который раньше его запросил. Ему присущ эффект конвоя в том случае когда в компьютере имеется один большой процесс и несколько малых то все процессы собираются в очереди готовых процессов, а затем в очередь выполнения процессов. Эта стратегия уменьшает загруженность ЦП и ПУ.

Стратегия «Наиболее короткая работа выполняется первой» (SJF)

Является одним из методов борьбы с эффектом конвоя, позволяет процессу из очереди выполниться первым. SJF часто применяется в долгосрочных планировщиках обслуживающих пакетный режим.

Приоритетное планирование.

Эта стратегия предполагает, что каждому процессу приписывается приоритет определяющий очередность предоставления ему ЦП. Обычно приоритет – это целое, положительное число в некотором диапазоне. Приоритеты назначаются исходя из совокупности внутренних и внешних по отношению ОС факторов. Внутренние факторы:

1. Требование к памяти количество открытых файлов отношение среднего времени ввода/вывода к среднему времени использования ресурсов ЦП и тд.

Внешние факторы:

1. Важность процессов и тд.

Недостаток стратегии: блокирование на неопределенное время низкоприоритетных процессов.

Карусельная стратегия (RR)

Применяется в системах разделения времени, определяется отрезок времени, называемый квантом. Очередь готовых процессов рассматривается как кольцевая. Процессы циклически перемещаются по очереди, получается P на время равное кванту. Новый процесс добавляется в хвост очереди, если процесс не завершился в свой квант, то его работа принудительно прерывается и он перемещается в хвост очереди.

12.12.2012

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

Взаимоблокировка процессов может происходить, когда несколько процессов борются за один ресурс. Ресурсы бывают выгружаемые и невыгружаемые. Выгружаемый ресурс можно забрать у процесса без потери данных. Невыгружаемый – нельзя забрать у процесса без потери данных. Проблема взаимоблокировок процессов возникают при борьбе за невыгружаемые ресурсы. Условие возникновения тупиков:

1. Условие взаимоисключений – одновременно использовать ресурс может только 1 процесс.

2. Условия ожидания ресурсов – процессы удерживают ресурс уже выделенный им, и могут запрашивать другие ресурсы.

3. Условие неперераспредиляемости – ресурс выделенный ранее не может быть принудительно забран у процесса, освобождены могут быть только удерживаемым их процессом.

4. Условия кругового ожидания – существует кольцевая цепь процессов в которой каждый ждет доступа к ресурсу удерживаемому другим процессом цепи.

Для образования тупика необходимым и достаточным является выполнением всех 4 условий. Основные направления борьбы с тупиками:

1. Игнорирование проблемы в целом

2. Предотвращение тупиков – цель предотвращения тупиков обеспечить условия исключающие возможность безопасно это или нет. Рассмотрим алгоритм банкира:

   1. Предположим что у него n устройств

   2. Операционная система принимает запрос от пользовательского процесса если его максимальная потребность не превышает n.

   3. Пользователь гарантирует что если ОС в состоянии удовлетворить свой запрос, то устройства будут возвращены системе в течении конечного времени.

   4. Текущее состояние системы называется надежным, если ОС может обеспечить всем процессам их выполнение в течении конечного времени.

   5. В соответствии с данным алгоритмом выделении устройств возможно только если состояние системы остается надежным. Однако использование этого метода требует выполнении следующих условий:

      1. Число пользователей и число ресурсов фиксировано

      2. Число работающих пользователей постоянно

      3. Клиенты гарантированно возвращают ресурсы

      4. Должны быть заранее указанны максимальные требования процессов к ресурсам.

3. Обнаружение тупиков

4. Восстановление после тупиков

Предотвращение тупиков за счет условия возникновения тупиков.

Нарушение условия взаимоисключения.

В качестве примера рассмотрим Принтер:

Извесно, что пытаться осушествлять вывод на принтер могут несколько процессов. Воизбежание этого, организуется промежуточное формирование всех выходных данных процесса на диске. Лишь 1 системный процесс «сервис принтера» отвечающий за вывод документов на печать, реально с ним взаимодействует. Эта схема называется спулингом. Таким образом, принтер становится разделяемым устройством и тупики для него устранены.

Нарушение условия ожидания дополнительных ресурсов.

Этого условия можно избежать потребовав выполнения стратегии двухфазного захвата:

1. В первой фазе процесс должен запрашивать все необходимые ему ресурсы сразу. До тех пор пока они не будут предоставлены. Процесс не может продолжать выполнение.

2. Если в первой фазе некоторые ресурсы которые нужны данному процессу заняты другими процессами, он освобождает все ресурсы что были ему выделены, и пытается повторить первую фазу.

Нарушение условия кругового ожидания.

Один из способов – упорядочить ресурсы, например присвоить всем ресурсам уникальные номера и потребовать что бы процессы запрашивали ресурсы в порядке возрастания.

Тогда круговое ожидание возникнуть не может. После последнего запроса и освобождение всех ресурсов, можно разрешить процессу опять осуществить первый запрос. Пример – создание иерархии спин-блокировок. Спин-блокировка – простейший способ синхронизации, может быть захвачена и освобождена процессом. Классическая тупиковая ситуация: Процессор П1 захватывает Спин-блокировку С1 и претендует на С2, а процесс П2 захватывает С2 и хочет дополнительно захватить С1. Что бы этого избежать все спин-блокировки помещаются в упорядочный список. Захват может осуществляться только в порядке, указанным в списке.

Нарушение условия неперераспределяемости.

В соответствии со 2м принципом Хавендера, можно отбирать ресурсы у удерживающих их процессов до их завершения. Этот принцип предотвращает возникновение условия перепераспределяемости ресурсов и требует что бы процесс, имеющий некоторые ресурсы, если он получает отказ на запрос о выделении доп. ресурсов, должен освободить все принадлежащие ему ресурсы и при необходимости запрашивать их снова вместе с дополнительными. Такая ситуация действенно веден к нарушению данного условия.