Методы реализации
Действия, выполняемые при диспетчеризации и планировании могут существенно увеличить накладные расходы если сами они не подчиняются некоторой определенной дисциплине. Так, если переключение процессов будет происходить достаточно часто, и если при каждом переключении потребуется время на обработку очереди, вычисление приоритета, изменение кванта, то может просто не остаться времени на выполнение процессов пользователя.
Общий принцип реализации управляющих программ состоит в том, что на часто выполняемые действия необходимо тратить меньше времени, чем на редко выполняемые. С другой стороны, действия, требующие много времени, должны выполняться редко. Применение этого принципа к управлению процессором приводит к так называемому многоуровневому планированию, которое не следует путать с использованием нескольких очередей. Многоуровневое планирование - это разбиение функций управления процессором на два или три уровня. Самый нижний уровень, обращение к которому происходит наиболее часто, должен, включать по крайней мере диспетчеризацию, которая передает управление первому процессу из очереди готовых к исполнению процессов. Самый высокий уровень, вызываемый реже всего, выполняет такие действия, как перевычисление кванта или приоритета на основе информации о состоянии ввода/вывода. Промежуточным звеном здесь является обработка очередей, в которые готовые к исполнению процессы помещаются, возможно, раз в несколько миллисекунд. При помещении процесса в очередь можно перевычислять приоритет и состояние процесса. Однако данный принцип реализации требует, чтобы эти действия не выполнялись в то время, когда процесс находится в очереди.
До сих пор, когда говорилось об очередях работ и готовых к исполнению процессов, подразумевалось, что они действительно состоят из работ и процессов. Но стоимость обслуживания очередей, фактически состоящих из работ или процессов, была бы, конечно, непомерно высокой. Рассматриваемые очереди на самом деле являются списками дескрипторов, обращаться с которыми гораздо легче, чем с теми объектами, которые они описывают. Более того, при этом можно хранить все списки в оперативной памяти, даже для тех работ и процессов, которые находятся во внешней памяти.
При циклической диспетчеризации процесс всегда помещается в конец очереди готовых к исполнению процессов, но в большинстве других дисциплин то, что называется “очередью” готовых к исполнению процессов, на самом деле очередью не является. При планировании с учетом временных ограничений, а также в дисциплинах SJN и SRT со старением или без него очередь готовых к исполнению процессов надо поддерживать в соответствии с приоритетами. Если такая очередь имеет вид линейного списка из n элементов, то вставка нового элемента требует O(n) операций. Если же очередь организована в виде пирамиды, то вставка требует только О(log n) операций.
Если управление процессором должно зависеть от времени, то необходим таймер. Многие ЭВМ имеют простой интервальный таймер. Ему можно передать произвольное число, которое будет уменьшаться при каждом прерывании вплоть до нуля, после чего таймер выдаст прерывание. Чтобы на базе одного такого таймера получить набор виртуальных таймеров для различных целей, можно использовать очередь с приоритетами. Каждый элемент определяет процесс, которому необходим сигнал, и время, когда этот сигнал должен поступить. Очередь упорядочена по времени. После каждого прерывания по времени интервал таймера устанавливается равным разности между моментом времени, когда должно произойти следующее прерывание и временем, определенным для прерывания, которое только что произошло. Специальные действия требуются только в том случае, когда во вставляемом элементе указано время, предшествующее тому, которое установлено на таймер. В этом случае таймер надо устанавливать заново.
Списки используются не только для организации работ с таймером и процессами в готовом и заблокированном состояниях, но также для учета работ, находящихся в ведении планировщика. Очередь работ, о которой уже говорилось, не обязательно должна быть одна. Можно иметь несколько очередей разных классов работ. Это особенно удобно, если и диспетчер различает те же самые классы. Прежде чем выбрать работу, планировщик должен учесть все работы в соответствующих позициях очереди. Если к планировщику обращаются только в том случае, когда освобождается ресурс, то он должен отложить выбор работы до тех пор, пока не разместит по очередям все работы, появившиеся с момента его последнего вызова. Другим подходом является вызов планировщика не только при освобождении ресурса, но и при появлении работы. Эту работу можно поставить в очередь и даже выбрать ее, если есть в наличии все необходимые ей ресурсы. Создается процесс, т. е. его дескриптор помещается в соответствующую очередь готовых к исполнению процессов, и в нем отмечается, что процессу выделены некоторая память, файлы и устройства.
Список необеспеченных классов может стать пустым по двум причинам: в связи с тем, что общая доля гарантированного времени обслуживания меньше единицы, или из-за того, что все процессы по крайней мере одного класса заблокированы. В этом случае класс, находящийся в начале списка, можно сразу же перевести в список необеспеченных, и тогда он начнет получать обслуживание сверх гарантированного минимума. Можно также вместо этого установить на процессор процесс, которому не было дано никаких гарантий. В большинстве случаев из-за блокирования процессов можно удовлетворить гарантии даже тогда, когда общая доля гарантированного времени обслуживания превышает единицу. Однако, используя такие “гарантии”, необходимо учитывать, что существует определенная вероятность их не выполнения в те периоды времени, когда в заблокированном состоянии находится всего несколько классов процессов.
