Многоуровневые очереди с обратными связями

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

Механизм диспетчеризации при этом должен

- оказывать предпочтение коротким процессам;

- оказывать предпочтение процессам, связанным в основном с вводом -выводом, чтобы обеспечить хороший коэффициент использования устройств ввода - вывода;

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

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

Для минимизации среднего времени ожидания большинство рассмотренных ранее алгоритмов с одной очередью использовали информацию, предоставляемую пользователем (например, время выполнения процесса). Во время исполнения информация о каждом процессе может быть пополнена и использована для изменения приоритета этого процесса. Тем самым связь между процессом и очередью становится динамической. Такие очереди называются очередями с обратной связью, поскольку информация о выполнении процесса используется для его диспетчеризации.

Пример многоуровневой очереди с обратными связями приведен на рис.5.4.

Новый процесс входит в сеть очередей с конца верхней очереди. Он перемещается по этой очереди, реализующей алгоритм FCFS , пока не получит в свое распоряжение центральный процессор. Если процесс завершается или освобождает ЦП, чтобы подождать завершения операции ввода-вывода или наступления некоторого события, то этот процесс выходит из сети­­ очередей. Если выделенный квант времени и­­стекает до того, как процесс добровольно освободит ЦП, этот процесс помещается в конец следующей очереди более низкого ­уровня. Этот процесс в следующий раз получит в свое распоряжение ЦП, когда он достигнет начала данной очереди, если при этом не будет процессов, ожидающих в первой очереди. Если данный процесс будет продолжать использовать полный квант вр­емени, предоставляемый на каждом уровне, он продолжит переход в конец очереди следующего нижележащего уровня. Обычно в системе предусматривается некоторая очередь самого нижнего уровня, которая реализует алгоритм циклического обслуживания и в которой данный процесс циркулирует до тех пор, пока не завершится.

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

Рис. 5.4. Многоуровневые очереди с обратными связями

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

Рассмотрим теперь, каким образом подобный механизм реагирует на различные типы процессов. Этот механизм должен оказывать предпочтение процессам, связанным с вводом-выводом, чтобы обеспечить хорошую загрузку устройств ввода-вывода и малое ­время реакции на запросы интерактивных пользователей. Действительно, так и будет, поскольку процесс, связанный с вводом-выводом, будет поступать­ в очередь с очень высоким приоритетом и ему будет быстро предоставляться ЦП. Квант времени для первой очереди выбирается достаточно большим, с тем чтобы подавляющее большинство заданий, связанных с вводом-выводом, успевало выдать запрос ввода-вывода еще до истечения первого кванта. Когда подобный процесс выдает запрос ввода-вывода, он выходит из сети очередей, причем получив истинно приоритетное обслуживание, что и требовалось.

Если верхнюю очередь сети (очередь с очень высоким приоритетом) поступает процесс, требующий много времени центрального процессора, то он получает в свое распоряжение ЦП весьма быстро, однако после истечения выделенного ему кванта времени процесс переходит в конец очереди следующего нижележащего уровня. Теперь этот процесс будет иметь более низкий приоритет, так что вновь поступающие процессы, особенно связанные по преимуществу с вводом-выводом, будут первыми получать в свое распоряжение ЦП. Со временем данный вычислительный процесс все же получит ЦП, ему будет выделен квант времени большей величины, чем в очереди наивысшего приоритета, но он снова не успеет завершиться по истечении этого полного кванта. Затем он будет помещен в конец очереди­ следующего нижележащего уровня. Таким образом, данный процесс будет продолжать переходить в очереди с более низкими приоритетами и будет дольше ждать в промежутках между выделяемыми ему квантами времени и каждый раз полностью использовать свой квант, когда будет получать в свое распоряжение ЦП (если при этом не будет прерываться из-за поступления процесса с более высоким приоритетом). В конце концов этот вычислительный процесс окажется в очереди самого низкого уровня с циклическим обслуживанием, где и будет циркулировать, пока не завершится.

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

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

На рис.5.5 показано выполнение ранее представленных процессов с использованием многоуровневых очередей с обратными связями для случаев как с постоянным значением кванта времени (q = 1), так и увеличивающимся в зависимости от уровня очереди (q = 2 ⁿ ). Числовые значения времени, характеризующего выполнение процессов, приведены в табл.5.3.

Рис.5.5. Сравнение алгоритмов диспетчеризации для многоуровневых очередей с обратными связями

Таблица 5.3

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

УПРАВЛЕНИЕ УСТРОЙСТВАМИ

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

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

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: