Дисциплины с несколькими очередями
На рис. 1.1 представлена простая модель с одной очередью
готовых процессов и тремя состояниями процессов. Для классификации готовых
к исполнению процессов по одному или нескольким критериям можно использовать
информацию, как задаваемую пользователем, так и определяемую в процессе
исполнения. Эта информация может включать заказанное время, фактически
использованное время, число выданных запросов на ввод/вывод. Она часто
используется .для того, чтобы по разному обслуживать процессы разных классов.
В каждом классе могут быть свои состояния готовности. Так, в пакетной
мультипрограммной системе нужно было бы присваивать более высокий
диспетчерский приоритет не процессу с большим объемом вычислений, а процессу
с большим числом обменов. Такая модель с пятью состояниями, не
перераспределяющая процессор, показана на рис. 1.2. Можно было бы считать,
что все заблокированные процессы находятся в одном и том же заблокированном
состоянии. Однако в системе со страничной организацией памяти полезно было
бы выделить различные очереди, чтобы отличать процессы, ожидающие
подкачки/откачки страницы, от процессов, ожидающих конца ввода/вывода,
заказанного пользователем.
Безотносительно к предшествующей классификации существует
общепринятое разбиение процессов на три класса: процессы реального времени,
интерактивные и пакетные, для каждого из которых создается своя очередь
готовых процессов. Процесс реального времени должен быть обслужен до
наступления конкретного момента времени, который часто зависит от специфики
внешнего устройства. Интерактивный процесс должен быть обслужен в
течение интервала времени, который человек считает приемлемым временем
реакции. Пакетный процесс (по крайней мере с этой точки зрения) не имеет
жестких требований ко времени обслуживания.
Наличие нескольких очередей готовых к исполнению
процессов может облегчить реализацию некоторых уже описанных стратегий.
При этом для каждой из очередей можно использовать свою дисциплину и
разные значения управляющих параметров (например, длины кванта).
В некоторых реализациях связь между процессом и очередью постоянна,
или статична; процесс всегда возвращается в одну и ту же очередь.
При других дисциплинах связь между процессом и очередью может изменяться
по мере исполнения процесса; она динамична, и процесс может при различных
обстоятельствах возвращаться в разные очереди.
Статическая связь. Для реализации стратегии
“избранного пользователя” можно для каждого класса ввести свою очередь
готовых процессов и устанавливать в каждом классе свой диспетчерский
приоритет. Как только процессор освобождается, диспетчер выбирает процесс
из непустой очереди с наивысшим приоритетом; при этом каждую очередь он
обслуживает с помощью дисциплины FCFS или циклически. Если используется
циклическая дисциплина, то с каждой очередью может быть связан свой квант
времени. Среди систем с несколькими очередями важную роль играет система,
имеющая три очереди для параллельного выполнения пакетных процессов,
интерактивных процессов и процессов реального времени. Пакетные процессы
помещаются в очередь с низким приоритетом, а интерактивные процессы и процессы
реального времени - в очереди с более высоким приоритетом. Часто говорят,
что процессы с низким приоритетом исполняются в фоновом, а с высоким в
оперативном режиме.
Для разбиения процессов на классы можно использовать
разные критерии. Простейший из них - предоставление более высокого приоритета
пользователю, который согласен заплатить дороже. При других критериях
приоритет зависит от объема запрошенной оперативной памяти или от того,
использует ли процесс часто употребляемый транслятор, который всегда находится
в оперативной памяти, или от того, требует ли процесс установки сменного
носителя. Для разбиения на классы можно использовать различные комбинации
этих критериев.
Динамическая связь. Для минимизации среднего
времени ожидания большинство рассмотренных алгоритмов с одной очередью
основаны на информации, предоставляемой пользователем, такой как, например,
заказанное время обслуживания. Во время исполнения информация о каждом
процессе может быть пополнена и использована для изменения приоритета этого
процесса. Тем самым связь между процессом и очередью становится динамической.
Такие очереди называются очередями с обратной связью, поскольку информация о
выполнении процесса используется для его диспетчеризации.
В основном дисциплины с обратной связью используют
несколько очередей готовых к исполнению процессов. На процессор
устанавливается первый процесс из непустой очереди наивысшего приоритета.
Процессу в любой очереди выделяется некоторый квант процессорного времени.
Если в течение этого кванта процесс не завершается, то он помещается в конец
следующей очереди с более низким приоритетом, возможно, после того, как он
пробудет некоторое время в заблокированном состоянии. Как только процесс
попадает в очередь с самым низким приоритетом, он остается там и обслуживается
циклически. Все остальные очереди обслуживаются в соответствии с дисциплиной
FIFO с перераспределением процессора. Новый процесс помещается в конец очереди
с самым большим приоритетом. Хотя существует несколько очередей, в каждый
конкретный момент на процессор устанавливается процесс только из одной очереди
или только в одну из них помещается процесс.
Логическим обоснованием этой дисциплины служит часто
наблюдаемый факт, что чем дольше процесс исполняется, тем меньше вероятность,
что он скоро закончится. Если это так, то с большей вероятностью закончится
тот процесс, который исполнялся меньше всего. Рассмотренная многоуровневая
дисциплина с обратной связью эффективна при условии, что скорость завершения
процесса уменьшается по мере его обслуживания. Это позволяет более быстро,
по сравнению с циклической дисциплиной, обслуживать короткие процессы, но,
в отличие от SJN и SRT, не требует заказа времени. Поэтому очереди с
обратной связью удобны для обслуживания интерактивных процессов, независимо
от того есть ли в системе пакетные процессы.
Расходы на ведение очереди процессов можно сократить
двумя способами: во-первых, можно уменьшить число очередей, позволив каждому
процессу оставаться некоторое время в той же очереди, прежде чем он перейдет
в очередь более низкого приоритета, и обслуживать все очереди циклически.
Можно предоставлять большие кванты времени для очередей с меньшим приоритетом,
вплоть до бесконечного кванта для очереди с самым низким приоритетом.
Это помогает сократить частоту переключения длинных процессов. Эти два
способа можно применять отдельно или в комбинации друг с другом.
Обратную связь можно использовать как для понижения,
так и для повышения приоритета процессов. Примером может служить система
с двумя очередями, в которой приписывание процесса к очереди вычислительных
процессов или к очереди процессов с большим числом обменов осуществляется
на основе данных о предшествующей интенсивности ввода/вывода.
Операционная система фирмы DEC ведет три очереди готовых
процессов с квантами в 0,2; 0,25 и 2 с. Процессу разрешено
по одному разу войти в первые две очереди, обслуживающиеся в режиме FIFO,
после чего он попадает в третью очередь, которая обслуживается в циклическом
режиме. Каждый новый запрос интерактивного процесса попадает в очередь с
самым большим приоритетом.
