Квантование с предпочтением процессам, интенсивно обращающихся к вводу/выводу

Дисциплина обслуживания очередей следующая: сначала выбирается процесс из очереди процессов, закончивших ввод/вывод. Делаются 2 очереди готовых процессов: одна из процессов, обращающихся часто к устройствам ввода\вывода. Вторая – для тех, кто основную часть времени считается на процессоре. Рассмотренные алгоритмы, основанные на квантовании, не используют никакой предварительной информации о процессах. Рассмотренные примеры алгоритмов относятся к классу вытесняющих.

Алгоритмы, основанные на приоритетах

Приоритет может быть статическим, например для процесса ядра, и динамическим – для пользовательских процессов. Динамический приоритет формируется в процессе счета как функция от времени нахождения процесса в различных очередях и др.

Вычисление приоритета основывается на статических и динамических характеристиках. Изменение приоритета может происходить по инициативе процесса, пользователя, ОС. Правила назначения приоритета процессов определяют эффективность работы системы.

Смешанные алгоритмы планирования

На практике концепции квантования и приоритетов часто используются совместно.

К примеру, в основе – концепция квантования, а определение кванта и/или дисциплина обслуживания очередей базируется на приоритетах.

БИЛЕТ 26. Планирование в ОС UNIX

Пересчет приоритета процесса происходит в момент выбора процесса для выполнения на ЦП 1 раз в секунду.

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

Эти группы используются для оптимизации доступа к блочным устройствам (например, к диску) и обеспечения быстрого отклика операционной системы на системные вызовы.

Группы приоритетов

(в порядке убывания): программа свопинга, управление блочными устройствами ввода/вывода, управление файлами, управление байт-ориентированными устройствами ввода/вывода, пользовательские процессы.

Планирование в Windows NT.

Квантование сочетается с использованием динамических абсолютных приоритетов.

В системе определено 32 уровня приоритетов.

Два класса нитей: Нити с переменными приоритетами(0-15] ;

Нити “реального” времени (16-31] – высокоприоритетные нити.

Нити с переменными приоритетами

Изначально процессу присваивается базовый приоритет.

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

Нить получает значение приоритета из диапазона базового приоритета.

Приоритет нити может отклоняться от своего базового приоритета, и это может быть не связано с изменением базового приоритета процесса ( см. диапазон значений динамического приоритета нитей).

Планирование свопинга в ОС Unix

При принятии нового процесса на обработку необходимо освободить ресурсы. Какой - то процесс скидывается в область своппинга.

Область свопинга - специально выделенное системой пространство внешней памяти

P_TIME – счетчик, находящийся в контексте процесса. Суммирует время нахождения процесса в состоянии мультипрограммной обработки или в области свопинга. При переходе из одного состояния в другое счетчик обнуляется. Для загрузки процесса в память из области свопинга выбирается процесс с максимальным значением P_TIME. Если для загрузки этого процесса нет свободного пространства оперативной памяти, то система ищет среди процессов в оперативной памяти процесс, ожидающий ввода/вывода (сравнительно медленных операций, процессы у которых приоритет выше значения P_ZERO) и имеющий максимальное значение P_TIME (т.е. тот, который находился в оперативной памяти дольше всех). Если такого процесса нет, то выбирается просто процесс с максимальным значением P_TIME.

Билет 27. Планирование в системах реального времени

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

Надо также учитывать последствия, к которым может привезт несоблюдение временных рамок.

Системы реального времени бывают “Жесткие” и ”мягкие ”.

В первом случае время завершения выполнения каждого из процессов должно быть гарантировано для всех сценариев функционирования системы.

Это может быть обеспечено за счет: полного тестирования всевозможных сценариев ; построения статического расписания ; выбора математически просчитанного алгоритма динамического планирования.

Периодические запросы – все моменты запроса периодического процесса можно определить заранее.

Пусть {Ti} набор периодических процессов с периодами – pi , предельными сроками выполнения di и требованиями ко времени выполнения ci.

Расписание удается построить не всегда.

Для проверки возможного составления расписания анализируется расписание на отрезке времени равному наименьшему общему множителю периодов этих процессов.

С целью определения возможности построения расписания используются различные критерии.

Необходимое условие наличия расписания:

Сумма коэффициентов использования m=S ci / pi <= k, где k - количество доступных процессоров.

Общие критерии для сравнения алгоритмов планирования

Планирование бывает краткосрочное, среднесрочное и долгосрочное: использование времени ЦП, пропускная способность (кол-во процессов в единицу времени), время ожидания (в очереди готовых), время оборота (полное время от момента поступления до завершения), время отклика (для интерактивных программ), время от поступления в систему до момента первого обращения к терминалу, предельный срок выполнения процесса.

БИЛЕТ 28.

Планирование обработки прерываний

Правильное планирование обработки прерываний – залог правильного планирования процессов.

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

Рассмотрим пример, в котором обработчик прерываний принтера блокирует на длительное время обработку прерываний от таймера, в результате чего системное время на некоторое время «замирает», и один из процессов (2), критически важный для пользователя, не получат управление в запланированное время.

Упорядоченное планирование прерываний

Механизм прерываний поддерживает приоритезацию и маскирование прерываний.

Источники прерываний делятся на классы – каждому классу свой уровень приоритета запроса на прерывание.

Дисциплина обслуживания приоритетов:относительная (выбор по наивысшему приоритету, но далее обработка не может быть отложена) ; абсолютная (происходит переход к обработке более приоритетного с откладыванием текущего).

В схеме с абсолютными приоритетами заложено маскирование, так как запрещаются запросы с равными или более низкими приоритетами. В общем случае - возможность маскирования прерываний любого класса и любого приоритета на некоторое время. Упорядочивание работы обработчиков прерываний – механизм приоритетных очередей. Наличие в ОС программного модуля – диспетчера прерываний. При возникновении прерывания – вызов диспетчера. Он блокирует все прерывания на некоторое время, устанавливает причину прерывания, сравнивает назначенный данному источнику прерывания приоритет с текущим приоритетом. В случае если у нового запроса на прерывание приоритет выше чем у текущего, то выполнение текущего приостанавливается и он помещается в соответствующую очередь. Иначе в соответствующую очередь помещается поступивший обработчик.

Планирование обработки прерываний в Windows NT

Все источники прерываний делятся на несколько классов, и каждому уровню присваивается уровень запроса прерывания – Interrupt Request Level (IRQL). Этот уровень и представляет приоритет данного класса.

Поступление запроса на прерывание/исключение – вызов диспетчера прерываний, который: Запоминает информацию об источнике прерывания ; Анализирует его приоритет.

Если приоритет <= IRQL прерванного, тоотложить в очередь, иначе текущий обработчик – в очередь, управление – новому.

Особенности планирования ввода/ вывода

Одна из важных задач планирования – обеспечение занятости внешних устройств

Для этого можно присваивать процессам высокий приоритет в периоды, когда они интенсивно используют ввод/ вывод

Эти периоды легко прослеживаются: процесс блокируется про обращении к вводу/выводу ; операции ввода/вывода обычно бывают сконцентрированы в отдельных частях программ.