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

Механизм планирования должен:

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

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

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

Этих целей достигают многоуровневые очереди с обратными связями (рис. 18). Это схема, которая наиболее эффективна для систем, где выполняются смеси разнообразных заданий. Новые процессы поступают в сеть очередей с очень высоким начальным приоритетом и быстро обслуживаются, если они являются либо интерактивными, либо лимитируемыми вводом-выводом. Процессы, лимитируемые ЦП, полностью используют квант времени, а затем переходят в конец очереди следующего, более низкого приоритета уровня. Чем дольше процесс занимает ЦП, тем ниже становится его приоритет, пока процесс не опускается в очередь самого низкого приоритета, которая реализует принцип RR, где он и завершается. Размер кванта обычно увеличивается по мере перехода процесса в каждую следующую очередь.

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

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

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

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

3.7.Мультипроцессорные архитектуры. Планирование загрузки ресурсов

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

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

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

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

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