Лекция 4 (27.09.2012) Приоритетное планирование

Алгоритм SGF и гарантированного планирования представляют собой частный случай приоритетного планирования. При приоритетном планировании каждому процессу присваивается определенное числовое значение приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SGF в качестве приоритета выступает оценка продолжительности задачи (чем меньше это значение, тем выше приоритет), а для гарантированного планирования приоритетом служит вычисленный коэффициент справедливости (чем он меньше, тем выше у процесса приоритет). Алгоритм назначения приоритетов может опираться как на внутренние параметры, связанные с происходящим внутри ОС, так и на внешние по отношению к ней.

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

Приоритеты бывают статические и динамические. Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов, низкоприоритетные процессы могут не запускаться неопределенно долгое время. Решение этой проблемы может быть достигнуто с помощью увеличения со временем значения приоритета процесса, находящихся в состоянии готовности. Пусть изначально процессом назначается приоритет от 128 до 255. Каждый раз по истечению определенного кванта времени, значение приоритета готовых процессов уменьшается на 1. Процессу, побывавшему в состоянии исполнения присваивается первоначальное значение приоритета. Даже такая грубая схема гарантирует, что любому процессу в разумные сроки будет предоставлено право на исполнение.

Тупики

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

Множество процессов находится в тупиковых ситуациях, если каждый процесс из множества ожидает события, которое может вызвать только другой процесс данного множества. Так как все процессы чего-то ожидают, то ни один из них не сможет инициировать событие, которое разбудило бы другой процесс из этого множества, и следовательно, все процессы будут спать. Существует 4 условия возникновения тупиков: 1) Условие взаимоисключения (одновременно использовать ресурс может только один процесс);

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

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

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

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

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

Способы борьбы с тупиками:

1. Игнорирование проблемы в целом. Простейший подход не замечать такую проблему. Для того, чтобы принять такое решение необходимо оценить вероятность возникновения взаимоблокировки и сравнить ее с вероятностью ущерба от других отказов аппаратного и программного обеспечения. Любая ОС, имеющая в ядре ряд массивов фиксированной размерности, потенциально страдает от тупиков, даже если они не обнаружены. Подход большинства популярных ОС состоит в том, чтобы игнорировать данную проблему в предположении что маловероятный случайный тупик предпочтительнее, чем нелепые правила, заставляющие пользователя ограничивать свои действия.

2. Предотвращение. Цель – обеспечить условия, исключающие возможность возникновения тупиковых ситуаций. Большинство методов связано с предотвращением одного из условий возникновения. Путем тщательного распределения ресурсов. Алгоритм банкира, придумал Дейкстра, базируется на так называемых безопасных или надежных состояниях. Безопасное состояние – то, для которого имеется по крайней мере одна последовательность событий, которая не приведет к взаимоблокировке. Модель основана на действиях банкира, который имея в наличии капитал, выдает кредиты. Суть алгоритма: предположим, что у ОС в наличии n устройств; ОС принимает от пользовательского процесса запрос, если его максимальная потребность не превышает n; пользователь гарантирует, что если ОС в состоянии удовлетворить его запрос, то все устройства будут возвращены ОС в течение конечного времени; текущее состояние системы называется надежным, если ОС может обеспечить всем процессам их выполнение в течение конечного времени. В соответствии с этим алгоритмом выделение устройств возможно, только если состояние системы останется надежным. Термин «ненадежное состояние» не предполагает, что обязательно возникнут тупики, он лишь говорит о том, что в случае неблагоприятной последовательности событий, система может зайти в тупик. Предотвращение тупиков за счет нарушения условий их возникновения. Нарушение условия взаимоисключения: в общем случае избежать невозможно, т.к. доступ к некоторым ресурсам должен быть исключительным, тем не менее некоторые устройства можно обобществить – на примере принтера организуется промежуточное формирование всех выходных данных на диске, т.е. на разделяемом устройстве; лишь один системный процесс, называемый сервисом или демоном принтера, отвечающий за вывод документов на печать, по мере освобождения принтера реально работает с ним (эта схема называется spooling), т.о. принтер становится разделяемым устройством и тупик для него устранен. К сожалению не для всех устройств и не для всех данных можно организоваться spooling. Нарушение условия ожидания дополнительных ресурсов: для этого применяется стратегия двухфазного захвата; в первой фазе процесс должен запрашивать все необходимые ему ресурсы сразу; до тех пор, пока они ему не предоставлены, процесс не может продолжать выполнение; если в первой фазе некоторые ресурсы, которые были нужны данному процессу, уже заняты другим процессом, то он освобождает все ресурсы, которые были ему выделены и пытается повторить первую фазу. Нарушение условия отсутствия перераспределения: было бы здорово, если бы можно было отнимать ресурсы у удерживающих их процессов до завершения этих процессов; минусы – можно отнимать только те ресурсы, состояние которых легко сохранить, а потом восстановить (например состояние процессора); если процесс в течение какого-то времени использует ресурс, а затем освобождает его, то он может потерять результаты работы. Нарушение условия кругового ожидания: упорядочить ресурсы, например присвоить всем ресурсам уникальные номера и потребовать, чтобы процессы запрашивали ресурсы в порядке их возрастания, тогда круговое ожидание возникнуть не может; после последнего запроса и освобождения всех ресурсов, можно разрешить процессу опять осуществить первый запрос; практически невозможно найти порядок, который удовлетворил бы всех; другой способ – действовать в соответствии с правилом, согласно которому каждый процесс может иметь только один ресурс в каждый момент времени (если нужен второй ресурс – освободи первый), что для многих процессов неприемлемо.

3. Обнаружение. Сводится к фиксации тупиковой ситуации и выявлении вовлеченных в него процессов. Для этого производится проверка наличия циклического ожидания в случаях, когда выполнены первые три условия возникновения тупиков. Рассмотрим: процесс P1 ожидает ресурс R1, процесс R2 удерживает R1 и ожидает R2, P3 удерживает R1 и ожидает R3, P4 ожидает R2, P5 удерживает R3 и ожидает R2. Является ли ситуация тупиковой?

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