Когда говорят о диспетчеризации, то всегда в явном или неявном виде имеют в виду понятие задачи (потока). Если ОС не поддерживает механизм тредов, то можно заменять понятие задачи на понятие процесса. Так как эти термины часто используются именно в таком смысле, мы вынуждены будем использовать термин «процесс» как синоним термина «задача».
Известно большое количество правил (дисциплин диспетчеризации), в соответствии с которыми формируется список (очередь) готовых к выполнению задач. Различают два больших класса дисциплин обслуживания – бесприоритетные и приоритетные. При бесприоритетном обслуживании выбор задачи производится в некотором заранее установленном порядке без учета их относительной важности и времени обслуживания. При реализации приоритетных дисциплин обслуживания отдельным задачам предоставляется преимущественное право попасть в состояние исполнения. Перечень дисциплин обслуживания и их классификация приведены на рисунке 8.
Рис. 8. Классификация дисциплин диспетчеризации
Запомним о приоритетах следующее:
- приоритет, присвоенный задаче, может являться величиной постоянной;
- приоритет задачи может изменяться в процессе её решения.
Диспетчеризация с динамическими приоритетами требует дополнительных расходов на вычисление значений приоритетов исполняющихся задач, поэтому во многих ОС реального времени используются методы диспетчеризации на основе статических (постоянных) приоритетов. Хотя надо заметить, что динамические приоритеты позволяют реализовать гарантии обслуживания задач.
Рассмотрим кратко некоторые основные (наиболее часто используемые) дисциплины диспетчеризации.
Самой простой в реализации является дисциплина FCFS (first come – first served), согласно которой задачи обслуживаются «в порядке очерёди», то есть в порядке их появления (рис. 9). Те задачи, которые были заблокированы в процессе работы (попали в какое-либо из состояний ожидания, например, из-за операций ввода/вывода), после перехода в состояние готовности ставятся в эту очередь готовности перед теми задачами, которые ещё не выполнялись. Другими словами, образуются две очерёди: одна очередь образуется из новых задач, а вторая очередь – из ранее выполнявшихся, но попавших в состояние ожидание. Такой подход позволяет реализовать стратегию обслуживания «по возможности заканчивать вычисления в порядке их появления». Эта дисциплина обслуживания не требует внешнего вмешательства в ход вычислений, при ней не происходит перераспределение процессорного времени. Существующие дисциплины диспетчеризации процессов могут быть разбиты на два класса – вытесняющие (preemptive) и не вытесняющие (non-preemptive). В первых пакетных ОС часто реализовывали параллельное выполнение заданий без принудительного перераспределения процессора между задачами. В большинстве современных ОС для мощных вычислительных систем, а также и в ОС для ПК, ориентированных на высокопроизводительное выполнение приложений (Windows NT, OS/2, Unix), реализована вытесняющая многозадачность. Можно сказать, что рассмотренная дисциплина относится к не вытесняющим.
Рис. 9. Дисциплина диспетчеризации FCFS
К достоинствам этой дисциплины, прежде всего, можно отнести простоту реализации и малые расходы системных ресурсов на формирование очерёди задач.
Однако эта дисциплина приводит к тому, что при увеличении загрузки вычислительной системы растет и среднее время ожидания обслуживания, причем короткие задания (требующие небольших затрат машинного времени) вынуждены ожидать столько же, сколько и трудоёмкие задания. Избежать этого недостатка позволяют дисциплины SJN и SRT.
Дисциплина обслуживания SJN (shortest job next, что означает: следующим будет выполняться кратчайшее задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Необходимость сообщать ОС характеристики задач, в которых описывались бы потребности в ресурсах вычислительной системы, привела к тому, что были разработаны соответствующие языковые средства. В частности, язык JCL (job control language, язык управления заданиями) был одним из наиболее известных. Пользователи вынуждены были указывать предполагаемое время выполнения, и для того, чтобы они не злоупотребляли возможностью указать заведомо меньшее время выполнения (с целью получить результаты раньше других), ввели подсчет реальных потребностей. Диспетчер задач сравнивал заказанное время и время выполнения и в случае превышения указанной оценки в данном ресурсе ставил данное задание не в начало, а в конец очерёди. Ещё в некоторых ОС в таких случаях использовалась система штрафов, при которой в случае превышения заказанного машинного времени оплата вычислительных ресурсов осуществлялась уже по другим расценкам.
Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. И задания, которые в процессе своего исполнения были временно заблокированы (например, ожидали завершения операций ввода/вывода), вновь попадают в конец очерёди готовых к выполнению наравне с вновь поступающими. Это приводит к тому, что задания, которым требуется очень немного времени для своего завершения, вынуждены ожидать процессор наравне с длительными работами, что не всегда хорошо.
Для устранения этого недостатка и была предложена дисциплина SRT (shortest remaining time, следующее задание требует меньше всего времени для своего завершения).
Все эти три дисциплины обслуживания могут использоваться для пакетных режимов обработки, когда пользователь не вынужден ожидать реакции системы, а просто сдает свое задание и через несколько часов получает свои результаты вычислений. Для интерактивных же вычислений желательно прежде всего обеспечить приемлемое время реакции системы и равенство в обслуживании, если система является мультитерминальной. Если же это однопользовательская система, но с возможностью мультипрограммной обработки, то желательно, чтобы те программы, с которыми мы сейчас непосредственно работаем, имели лучшее время реакции, нежели наши фоновые задания. При этом мы можем пожелать, чтобы некоторые приложения, выполняясь без нашего непосредственного участия (например, программа получения электронной почты, использующая модем и коммутируемые линии для передачи данных), тем не менее, гарантированно получали необходимую им долю процессорного времени. Для решения подобных проблем используется дисциплина обслуживания, называемая RR (round robin, круговая, карусельная), и приоритетные методы обслуживания.
Дисциплина обслуживания RR предполагает, что каждая задача получает процессорное время порциями (квантами времени, q). После окончания кванта времени q задача снимается с процессора и он передаётся следующей задаче (рис. 10). Снятая задача ставится в конец очерёди задач, готовых к выполнению. Для оптимальной работы системы необходимо правильно выбрать закон, по которому кванты времени выделяются задачам.
Величина кванта времени q выбирается как компромисс между приемлемым временем реакции системы на запросы пользователей (с тем, чтобы их простейшие запросы не вызывали длительного ожидания) и накладными расходами на частую смену контекста задач. Очевидно, что при прерываниях ОС вынуждена сохранить достаточно большой объём информации о текущем (прерываемом) процессе, поставить дескриптор снятой задачи в очередь, загрузить контекст задачи, которая теперь будет выполняться (её дескриптор был первым в очерёди готовых к исполнению). Если величина q велика, то при увеличении очерёди готовых к выполнению задач реакция системы станет плохой. Если же величина мала, то относительная доля накладных расходов на переключения между исполняющимися задачами станет большой и это ухудшит производительность системы. В некоторых ОС есть возможность указывать в явном виде величину q либо диапазон её возможных значений, поскольку система будет стараться выбирать оптимальное значение сама.
Дисциплина диспетчеризации RR – это одна из самых распространенных дисциплин. Однако бывают ситуации, когда ОС не поддерживает в явном виде дисциплину карусельной диспетчеризации. Например, в некоторых ОС реального времени используется диспетчер задач, работающий по принципам абсолютных приоритетов (процессор предоставляется задаче с максимальным приоритетом, а при равенстве приоритетов он действует по принципу очерёдности). Другими словами, снять задачу с выполнения может только появление задачи с более высоким приоритетом. Поэтому если нужно организовать обслуживание задач таким образом, чтобы все они получали процессорное время равномерно и равноправно, то системный оператор может сам организовать эту дисциплину. Для этого достаточно всем пользовательским задачам присвоить одинаковые приоритеты и создать одну высокоприоритетную задачу, которая не должна ничего делать, но которая, тем не менее, будет по таймеру (через указанные интервалы времени) планироваться на выполнение. Эта задача снимет с выполнения текущее приложение, оно будет поставлено в конец очерёди, и поскольку этой высокоприоритетной задаче на самом деле ничего делать не надо, то она тут же освободит процессор и из очерёди готовности будет взята следующая задача.
В своей простейшей реализации дисциплина карусельной диспетчеризации предполагает, что все задачи имеют одинаковый приоритет. Если же необходимо ввести механизм приоритетного обслуживания, то это, как правило, делается за счёт организации нескольких очерёдей. Процессорное время будет предоставляться в первую очередь тем задачам, которые стоят в самой привилегированной очерёди. Если она пустая, то диспетчер задач начнет просматривать остальные очерёди. Именно по такому алгоритму действует диспетчер задач в операционных системах OS/2 и Windows NT.
При выполнении программ, реализующих какие-нибудь задачи контроля и управления (что характерно, прежде всего, для систем реального времени), может случиться такая ситуация, когда одна или несколько задач не могут быть реализованы (решены) в течение длительного промежутка времени из-за возросшей нагрузки в вычислительной системе. Потери, связанные с невыполнением таких задач, могут даться больше, чем потери от невыполнения программ с более высоким приоритетом. При этом оказывается целесообразным временно изменить приоритет «аварийных» задач (для которых истекает отпущенное для них время обработки). После выполнения этих задач их приоритет восстанавливается. Поэтому почти в любой операционной системе реального времени (ОС РВ) имеются средства для динамического изменения приоритета (dynamic priority variation) задачи. Есть такие средства и во многих операционных системах, которые не относятся к классу ОС РВ. Рассмотрим, например, как реализован механизм динамических приоритетов в операционной системе UNIX, которая, как известно, не относится к ОС РВ. Операцией системы класса UNIX относятся к мультитерминальным диалоговым системам. Основная стратегия обслуживания, применяемая в UNIX-системах, - это равенство в обслуживании и обеспечение приемлемого времени реакции системы. Реализуется эта стратегия за счет дисциплины диспетчеризации RR с несколькими очередями и механизма динамических приоритетов. Приоритет процесса вычисляется следующим образом. Во-первых, в вычислении участвуют значения двух полей дескриптора процесса - p_nice и р_сpu. Первое из них назначается пользователем явно или формируется по умолчанию с помощью системы программирования. Второе поле формируется диспетчером задач (планировщиком разделения времени) и называется системной составляющей или текущим приоритетом. Другими словами, каждый процесс имеет два атрибута приоритета. С учетом этого приоритета и распределяется между исполняющимися задачами процессорное время: текущий приоритет, на основании которого происходит планирование, и заказанный относительный приоритет (называемый nice number, или просто nice). Схема нумерации текущих приоритетов различна для различных версий UNIX. Например, более высокому значению текущего приоритета может соответствовать более низкий фактический приоритет планирования. Разделение между приоритетами режима ядра и задачи также зависит от версии. Рассмотрим частный случай, когда текущий приоритет процесса варьируется в диапазоне от 0 (низкий приоритет) до 127 (наивысший приоритет). Процессы, выполняющиеся в режиме задачи, имеют более низкий приоритет, чем в режиме ядра. Для режима задачи приоритет меняется в диапазоне 0-65, для режима ядра - 66-95 (системный диапазон). Процессы, приоритеты которых лежат в диапазоне 96-127, являются процессами с фиксированным приоритетом, не изменяемым операционной системой, и предназначены для поддержки приложений реального времени. Процессу, ожидающему недоступного в данный момент ресурса, система определяет значение приоритета сна, выбираемое ядром из диапазона системных приоритетов и связанное с событием, вызвавшим это состояние. Когда процесс пробуждается, ядро устанавливает значение текущего приоритета процесса равным приоритету сна. Поскольку приоритет такого процесса находится в системном диапазоне и выше, чем приоритет режима задачи, вероятность предоставления процессу вычислительных ресурсов весьма велика. Такой подход позволяет, в частности, быстро завершить системный вызов, в ходе выполнения которого могут блокироваться некоторые системные ресурсы. После завершения системного вызова перед возвращением в режим задачи ядро восстанавливает приоритет режима задачи, сохраненный перед выполнением системного вызова. Это может привести к понижению приоритета, что, в свою очередь, вызовет переключение контекста. Текущий приоритет процесса в режиме задачи p_priuser, как мы только что отмечали, зависит от значения относительного приоритета p_nice и степени использования вычислительных ресурсов р_сpu:
p_priuser=а*p_nice-b*p_cpu
Задача планировщика разделения времени - справедливо распределить вычислительный ресурс между конкурирующими процессами. Для принятия решения о выборе следующего запускаемого процесса планировщику необходима информация об использовании процессора. Эта составляющая приоритета уменьшается обработчиком прерываний таймера каждый тик. Таким образом, пока процесс выполняется в режиме задачи, его текущий приоритет линейно уменьшается. Каждую секунду ядро пересчитывает текущие приоритеты процессов, готовых к запуску (приоритеты которых меньше некоторого порогового значения; в нашем примере эта величина равна 65), последовательно увеличивая их за счет последовательного уменьшения отрицательного компонента времени использования процессора. Как результат, эти действия приводят к перемещению процессов в более приоритетные очереди и повышению вероятности их последующего выполнения. Возможно использование следующей формулы:
p_cpu–p_cpu/2
В этом правиле проявляется недостаток нивелирования приоритетов при повышении загрузки системы. Происходит это потому, что в таком случае каждый процесс получает незначительный объем вычислительных ресурсов и, следовательно, имеет малую составляющую р_срu, которая еще более уменьшается благодаря формуле пересчета величины р_срu. В результате загрузка процессора перестает оказывать заметное влияние на приоритет, и низкоприоритетные процессы (то есть процессы с высоким значением nice number) практически «отлучаются» от вычислительных ресурсов системы. В некоторых версиях UNIX для пересчета значения р_срu используется другая формула:
p_cpu=p_cpu*(2*load)/(2*load+1)
Здесь параметр load равен среднему числу процессов, находившихся в очереди на выполнение за последнюю секунду, и характеризует среднюю загрузку системы за этот период времени. Этот алгоритм позволяет частично избавиться от недостатка планирования по формуле p_cpu=p_cpu/2, поскольку при значительной загрузке системы уменьшение р_срu при пересчете будет происходить медленнее. Описанные алгоритмы диспетчеризации позволяют учесть интересы низкоприоритетных процессов, так как в результате длительного ожидания очереди на запуск приоритет таких процессов увеличивается, соответственно повышается и вероятность их запуска. Эти алгоритмы также обеспечивают более вероятный выбор планировщиком интерактивных процессов по отношению к сугубо вычислительным (фоновым). Такие задачи, как командный интерпретатор или редактор, большую часть времени проводят в ожидании ввода, имея, таким образом, высокий приоритет (приоритет сна). При наступлении ожидаемого события (например, пользователь осуществил ввод данных) им сразу же предоставляются вычислительные ресурсы. Фоновые процессы, потребляющие значительные ресурсы процессора, имеют высокую составляющую р_сpu и, как следствие, более низкий приоритет. Аналогичные механизмы имеют место и в таких операционных системах, как OS/2 или Windows NT/2000/XP. Правда, алгоритмы изменения приоритета задач в этих системах иные. Например, в Windows NT/2000/XP каждый поток выполнения имеет базовый уровень приоритета, который лежит в диапазоне от двух уровней ниже базового приоритета процесса, его породившего, до двух уровней выше этого приоритета. Базовый приоритет процесса определяет, сколь сильно могут различаться приоритеты потоков этого процесса и как они соотносятся с приоритетами потоков других процессов. Поток наследует этот базовый приоритет и может изменять его так, чтобы он стал немного больше или немного меньше. В результате получается приоритет планирования, с которым поток и начинает исполняться. В процессе исполнения потока его приоритет может отклоняться от базового. Например, если поток обрабатывает текущие результаты операций ввода пользователем своих данных, диспетчер задач Windows поднимает его динамический приоритет; если же он выполняет вычисления, то диспетчер задач постепенно снижает его приоритет до базового. Снижая приоритет одной задачи и поднимая приоритет другой, подсистемы могут управлять относительной приоритетностью потоков внутри процесса. Для определения порядка выполнения потоков диспетчер задач использует систему приоритетов, направляя на выполнение задачи с высоким приоритетом раньше задач с низким приоритетом. Система прекращает исполнение, или вытесняет (preempts), текущий поток, если становится готовым к выполнению другой поток с более высоким приоритетом. Имеется группа очередей - по одной для каждого приоритета. В операционных системах Windows NT/2000/XP используется один и тот же диспетчер задач. Он поддерживает 32 уровня приоритета. Задачи делятся на два класса: реального времени и переменного приоритета. Задачи реального времени, имеющие приоритеты от 16 до 31, - это высокоприоритетные потоки, используемые программами, критическими по времени выполнения, то есть требующими немедленного внимания системы (по терминологии Microsoft). Диспетчер задач просматривает очереди, начиная с самой приоритетной. При этом очередь пустая, то есть в ней нет готовых к выполнению задач с таким приоритетом, то осуществляется переход к следующей очереди. Следовательно, если есть задачи, требующие процессор немедленно, они будут обслужены в первую очередь. Для собственно системных модулей, функционирующих в статусе задачи, зарезервирована очередь с номером 0. Большинство задач в системе относятся к классу переменного приоритета с уровнем приоритета (номером очереди) от 1 до 15. Эти очереди используются задачами с переменным приоритетом (variable priority), так как диспетчер задач для оптимизации отклика системы корректирует их приоритеты по мере выполнения. Диспетчер приостанавливает исполнение текущей задачи, после того как та израсходует свой квант времени. При этом если прерванная задача - это поток временного приоритета, то диспетчер задач понижает приоритет этого потока выполнения на единицу и перемещает в другую очередь. Таким образом, приоритет задачи, выполняющей много вычислений, постепенно понижается (до значения его базового приоритета). С другой стороны, диспетчер повышает приоритет задачи после ее освобождения из состояния ожидания. Обычно добавка приоритету задачи определяется кодом исполнительной системы, находящимся вне ядра операционной системы, однако величина этой добавки зависит от типа события, которого ожидала заблокированная задача. Так, например, поток, ожидавший ввода очередного байта с клавиатуры, получает большую добавку к значению своего приоритета, чем поток ввода-вывода, работавший с дисковым накопителем. Однако в любом случае значение приоритета не может достигнуть 16. В операционной системе OS/2 схема динамической приоритетной диспетчеризации несколько иная, хоть и похожа. В OS/2 также имеется четыре класса задач. Для каждого класса задач имеется своя группа приоритетов с интервалом значений от 0 до 31. Итого, 128 различных уровней и, соответственно, 128 возможных очередей готовых к выполнению задач (потоков). Задачи, имеющие самые высокие значения приоритета, называются критическими по времени (time critical). В этот класс входят задачи, которые мы в обиходе называем задачами реального времени, то есть для них должен быть обязательно предоставлен определенный минимум процессорного времени. Наиболее часто встречающимися задачами этого класса являются задачи коммуникаций (например, задача управления последовательным портом, на который приходят биты по коммутируемой линии с подключенным модемом, или задачи управления сетевым оборудованием). Если такие задачи не получат управление в нужный момент времени, то сеанс связи может прерваться. Следующий класс задач имеет название приоритетного. Поскольку к этому классу относят задачи, которые выполняют по отношению к остальным задачам функции сервера (о модели клиент-сервер, по которой строятся современные операционные системы с микроядерной архитектурой), то его еще иногда называют серверным. Приоритет таких задач должен быть выше, поскольку это позволяет гарантировать, что запрос на некоторую функцию со стороны обычных задач выполнится сразу, а не будет дожидаться, пока до него дойдет очередь на фоне других пользовательских приложений. Большинство задач относят к обычному классу, его еще называют регулярным (regular), или стандартным. По умолчанию система программирования порождает задачу, относящуюся именно к этому классу. Наконец, существует еще класс фоновых задач, называемый в OS/2 остаточным. Программы этого класса получают процессорное время только тогда, когда нет задач из других классов, требующих процессор. В качестве примера такой задачи можно привести программу обновления индексного файла, используемого при поиске файлов, или программу проверки электронной почты. Внутри каждого из вышеописанных классов задачи, имеющие одинаковый уровень приоритета, выполняются в соответствии с дисциплиной RR. Переход от одного потока к другому происходит либо по окончании отпущенного ему кванта времени, либо по системному прерыванию, передающему управление задаче с более высоким приоритетом (таким образом система вытесняет задачи с более низким приоритетом для выполнения задач с более высоким приоритетом и может обеспечить быструю реакцию на важные события). OS/2 самостоятельно изменяет приоритет выполняющихся программ независимо от уровня, установленного самим приложением. Этот механизм называется повышением приоритета (priority boost). Операционная система изменяет приоритет задачи в трех случаях:
1. Повышение приоритета активной задачи (foreground boost). Приоритет задачи автоматически повышается, когда она становится активной. Это снижает время реакции активного приложения на действия пользователя по сравнению с фоновыми программами.
2. Повышение приоритета ввода-вывода (Input/Output boost). По завершении операции ввода-вывода задача получает самый высокий уровень приоритета ее класса. Таким образом обеспечивается завершение всех незаконченных операций ввода-вывода.
3. Повышение приоритета «забытой» задачи (starvation boost). Если задача не получает управление в течение достаточно долгого времени (этот промежуток времени задает оператор MAXWAIT в файле CONFIG.SYS), диспетчер задач OS/2 временно присваивает ей уровень приоритета, не превышающий критический. В результате переключение на такую «забытую» программу происходит быстрее. После выполнения приложения в течение одного кванта времени его приоритет вновь снижается до остаточного. В сильно загруженных системах этот механизм позволяет программам с остаточным приоритетом работать хотя бы в краткие интервалы времени. В противном случае они вообще никогда бы не получили управление.
Для систем, в которых процессы могут быть легко рассортированы по разным группам, был разработан другой класс алгоритмов планирования. Для каждой группы процессов создается своя очередь процессов, находящихся в состоянии готовность (рис. 11). Этим очередям приписываются фиксированные приоритеты. Например, приоритет очереди системных процессов устанавливается выше, чем приоритет очередей пользовательских процессов. А приоритет очереди процессов, запущенных студентами, ниже, чем для очереди процессов, запущенных преподавателями. Это значит, что ни один пользовательский процесс не будет выбран для исполнения, пока есть хоть один готовый системный процесс, и ни один студенческий процесс не получит в свое распоряжение процессор, если есть процессы преподавателей, готовые к исполнению. Внутри этих очередей для планирования могут применяться самые разные алгоритмы. Так, например, для больших счетных процессов, не требующих взаимодействия с пользователем (фоновых процессов), может использоваться алгоритм FCFS, а для интерактивных процессов – алгоритм RR. Подобный подход, получивший название многоуровневых очередей, повышает гибкость планирования: для процессов с различными характеристиками применяется наиболее подходящий им алгоритм.
Рис. 11. Несколько очередей планирования
Дальнейшим развитием алгоритма многоуровневых очередей является добавление к нему механизма обратной связи. Здесь процесс не постоянно приписан к определенной очереди, а может мигрировать из одной очереди в другую в зависимости от своего поведения.
Для простоты рассмотрим ситуацию, когда процессы в состоянии готовность организованы в 4 очереди, как на рисунке 12. Планирование процессов между очередями осуществляется на основе вытесняющего приоритетного механизма. Чем выше на рисунке располагается очередь, тем выше ее приоритет. Процессы в очереди 1 не могут исполняться, если в очереди 0 есть хотя бы один процесс. Процессы в очереди 2 не будут выбраны для выполнения, пока есть хоть один процесс в очередях 0 и 1. И наконец, процесс в очереди 3 может получить процессор в свое распоряжение только тогда, когда очереди 0, 1 и 2 пусты. Если при работе процесса появляется другой процесс в какой-либо более приоритетной очереди, исполняющийся процесс вытесняется новым. Планирование процессов внутри очередей 0 – 2 осуществляется с использованием алгоритма RR, планирование процессов в очереди 3 основывается на алгоритме FCFS.
Рис. 12. Схема миграции процессов в многоуровневых очередях планирования с обратной связью (вытеснение процессов более приоритетными процессами и завершение процессов на схеме не показано)
Родившийся процесс поступает в очередь 0. При выборе на исполнение он получает в свое распоряжение квант времени размером 8 единиц. Если продолжительность его CPU burst меньше этого кванта времени, процесс остается в очереди 0. В противном случае он переходит в очередь 1. Для процессов из очереди 1 квант времени имеет величину 16. Если процесс не укладывается в это время, он переходит в очередь 2. Если укладывается – остается в очереди 1. В очереди 2 величина кванта времени составляет 32 единицы. Если для непрерывной работы процесса и этого мало, процесс поступает в очередь 3, для которой квантование времени не применяется и, при отсутствии готовых процессов в других очередях, может исполняться до окончания своего CPU burst. Чем больше значение продолжительности CPU burst, тем в менее приоритетную очередь попадает процесс, но тем на большее процессорное время он может рассчитывать. Таким образом, через некоторое время все процессы, требующие малого времени работы процессора, окажутся размещенными в высокоприоритетных очередях, а все процессы, требующие большого счета и с низкими запросами к времени отклика, – в низкоприоритетных.
Миграция процессов в обратном направлении может осуществляться по различным принципам. Например, после завершения ожидания ввода с клавиатуры процессы из очередей 1, 2 и 3 могут помещаться в очередь 0, после завершения дисковых операций ввода-вывода процессы из очередей 2 и 3 могут помещаться в очередь 1, а после завершения ожидания всех других событий – из очереди 3 в очередь 2. Перемещение процессов из очередей с низкими приоритетами в очереди с высокими приоритетами позволяет более полно учитывать изменение поведения процессов с течением времени.
Многоуровневые очереди с обратной связью представляют собой наиболее общий подход к планированию процессов из числа подходов, рассмотренных нами. Они наиболее трудны в реализации, но в то же время обладают наибольшей гибкостью. Понятно, что существует много других разновидностей такого способа планирования, помимо варианта, приведенного выше. Для полного описания их конкретного воплощения необходимо указать:
- Количество очередей для процессов, находящихся в состоянии готовность.
- Алгоритм планирования, действующий между очередями.
- Алгоритмы планирования, действующие внутри очередей.
- Правила помещения родившегося процесса в одну из очередей.
- Правила перевода процессов из одной очереди в другую.
Изменяя какой-либо из перечисленных пунктов, мы можем существенно менять поведение вычислительной системы.
