Планировщики с приоритетами

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

Приоритеты процессов в транспьютере
Простейшим случаем такой организации является транспьютер, имеющий две очереди. В транспьютере при этом планировщик не может отобрать управление у высокоприоритетного процесса. В этом смысле низкоприоритетные задачи вынуждены полагаться на "порядочность" высокоприоритетных, т. е. на то, что те освобождают процессор в разумное время.
Отчасти похожим образом организован планировщик системы VAX/VMS. Он имеет 32 приоритетных очереди, из которых старшие 16 называются процессами реального времени, а младшие — разделенного.
При этом процесс реального времени исполняется всегда, когда готов к исполнению, и в системе нет более приоритетных процессов. ОС и процессы разделенного времени также вынуждены полагаться на его порядочность. Поэтому привилегия запускать такие процессы контролируется администратором системы.

Легко понять, что разделение времени обеспечивает более или менее справедливый доступ к процессору для задач с одинаковым приоритетом. В случае транспьютера, который имеет только один приоритет и, соответственно, одну очередь для задач разделенного времени, этого оказывается достаточно. Однако современные ОС как общего назначения, так и реального времени, имеют много уровней приоритета. Для чего это нужно и как достигается в этом случае справедливое распределение времени процессора?
Дело в том, что в системах такого типа приоритет процессов разделенного времени является динамической величиной. Он изменяется в зависимости от того, насколько активно задача использует процессор и другие системные ресурсы.
В системах с пакетной обработкой, когда для задачи указывают верхнюю границу времени процессора, которое она может использовать, часто более короткие задания идут с более высоким приоритетом. Кроме того, более высокий приоритет дают задачам, которые требуют меньше памяти. В системах разделенного времени часто оказывается сложно заранее определить время, в течение которого будет работать задача. Например, вы отлаживаете программу. Для этой цели вы запускаете символьный отладчик и начинаете исполнять вашу программу в пошаговом режиме. Естественно, что вы не можете даже приблизительно предсказать как астрономическое время отладки, так и время центрального процессора, занятое при этом. Поэтому обычно такие системы не ограничивают время исполнения задачи и другие ре-сУрсы и вынуждены прогнозировать поведение программы в будущем на основании ее поведения в прошлом.
Так, если программа начала вычисления, не прерываемые никакими обращениями к внешней памяти или терминалу, мы можем предположить, что она будет заниматься такими вычислениями и дальше. Напротив, если программа сделала несколько запросов на ввод-вывод, следует ожидать, что она и дальше будет активно выдавать такие запросы. Предпочтительными для системы будут те программы, которые захватывают процессор на короткое время и быстро отдают его, переходя в состояние ожидания внешнего или внутреннего события. Таким процессам система стремится присвоить более высокий приоритет. Если программа ожидает завершения запроса на обращение к диску, то это также выгодно для системы — ведь на большинстве машин чтение с диска и запись на него происходят параллельно с работой центрального процессора.
Таким образом, система динамически повышает приоритет тем заданиям, которые освободили процессор в результате запроса на ввод-вывод или ожидание события и, наоборот, снижает тем заданиям, которые были сняты по истечении кванта времени. Однако приоритет не может превысить определенного значения — стартового приоритета задачи.
При этом наиболее высокий приоритет автоматически получают интерактивные задачи и программы, занятые интенсивным вводом-выводом. Во время выполнения таких программ процессор часто оказывается свободен, и управление получают низкоприоритетные вычислительные задания. Поэтому системы семейства UNIX и VAX/VMS даже при очень высокой загрузке обеспечивают как приемлемое время реакции для интерактивных программ, так и приемлемое астрономическое время исполнения для пакетных заданий. Благодаря наличию класса планирования реального времени, эти же ОС можно использовать и в задачах реального времени таких, как управление атомным реактором.
Система VMS повышает приоритет также и тем задачам, которые остановились в ожидании подкачки страницы. Это сделано потому, что если программа несколько раз выскочила за пределы своего рабочего набора (т. е. потребовала еще страницу, когда ее рабочий набор весь занят), то она, скорее всего, будет делать это и далее, а процессор на время подкачки она освобождает.
Нужно отметить, что процесс разделенного времени может повысить свой приоритет до максимального в классе разделения времени, но никогда не сможет стать процессом реального времени. А для процессов реального времени динамическое изменение приоритетов обычно не применяется.

Управление приоритетами во OS-9
Любопытно реализовано динамическое изменение приоритета в OS-9. В этой ОС каждый процесс имеет статически определенный приоритет и возраст
(age) — количество просмотров очереди с того момента, когда этот процесс в последний раз получал управление. Обе эти характеристики представлены 16-разрядными беззнаковыми числами. Процесс может повысить или понизить свой приоритет, исполнив соответствующий системный вызов, но система по собственной инициативе никогда не меняет его. При этом управление каждый раз получает процесс с наибольшей суммой статического приоритета и динамически изменяющегося возраста (рис. 8.1 — в изображенной на рисунке ситуации будет выбран процесс 12). Если у двух процессов такие суммы равны, то берется процесс с большим приоритетом. Если у них равны и приоритеты, то берется тот, который оказался ближе к началу очереди.

Рис. 8.1. Приоритеты и возраст в OS/9

Этот алгоритм гарантирует, что любой низкоприоритетный процесс рано или поздно получит управление. Если же нам нужно, чтобы он получал управление раньше, то мы должны просто повысить его приоритет.
Кроме того, можно запретить исполнение процессов со статическим приоритетом ниже заданного. Это может уменьшить загрузку процессора и, например, позволит высокоприоритетным процессам обработать увеличившийся поток внешних событий. Понятно, что такой запрет можно вводить только на небольшое время, чтобы не нарушить справедливое распределение процессора.
Возможна и более тонкая регулировка — системный вызов, который запрещает увеличивать возраст процесса больше заданного значения. То есть, процесс, стоя в очереди, может достичь этого максимального возраста, после чего он по-прежнему остается в очереди, но его возраст уже не увеличивается.
Получающаяся в результате схема распределения времени процессора отчасти похожа на двухслойную организацию VAX/VMS, когда исполнение процессов со статическим приоритетом, превышающим границу, не может быть прервано низкоприоритетным процессом.