вой компании могут довольно точно предсказать, сколько времени займет обработка пакета из 1000 исков, поскольку они делают это каждый день. Если в очереди есть несколько одинаково важных задач, планировщик выбирает первой, самую короткую задачу. Посмотрите на рис. 2.11. У нас есть четыре задачи: А, В, С и D, со временем выполнения 8, 4, 4 и 4 мин соответственно. Если мы запустим их в данном порядке, оборотное время задачи А будет 8 мин, В - 12 мин, С - 16 мин, D - 20 мин и среднее время будет равно 14 мин.

Рис. 2.11. Пример алгоритма планирования Кратчайшая задача - первая : а - запуск четырех задач в исходном порядке; б - запуск в соответствии с алгоритмом

Запустим задачи в соответствии с алгоритмом, как показано на рис. 2.11, б. Теперь значения оборотного времени составляют 4, 8, 12 и 20 мин соответственно, а среднее время равно 11 мин. Алгоритм оптимизирует задачу. Рассмотрим четыре процесса со временем выполнения а, 6, с и d. Первая задача выполняется за время а, вторая - за время а + 6 и т. д. Среднее оборотное время будет равно (4а + 36 + 2с + d)/A. Очевидно, что вклад а в среднее время больше, чем всех остальных интервалов времени, поэтому первой должна выполняться самая быстрая задача, а последней - с наибольшей длительностью, вносящая вклад, равный собственному оборотному времени. Точно так же рассматривается система из любого количества задач.

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

Один из методов привлекает к оценке длину процесса, базируясь на предыдущем его поведении. При этом запускается процесс, у которого оцененное время самое маленькое. Допустим, что предполагаемое время исполнения команды равно Го и предполагаемое время следующего запуска равно Т\. Можно улучшить оценку, взяв взвешенную сумму этих времен аТо + (1 - а) х Ti. Выбирая соответствующее значение а, мы можем заставить алгоритм оценки быстро забывать о предыдущих запусках или, наоборот, помнить о них в течение долгого времени. Взяв а = 1/2, мы получим серию оценок:

Го, Го/2 + Г,/2, Го/4 + Г1/4 + Г2/2, Го/8 + Г1/8 + Г2/4 + Гз/2.

После трех запусков вес Го в оценке уменьшится до 1/8.

Метод оценки следующего значения серии через взвещенное среднее предыдущего значения и предыдущей оценки часто называют старением. Этот метод применим во многих ситуациях, где необходима оценка по предыдущим значениям. Проще всего реализовать старение при а = 1/2. На каждом щаге нужно всего лищь добавить к текущей оценке новое значение и разделить сумму пополам (со сдвигом вправо на 1 бит).

Следует отметить, что эта схема работает лищь в случае одновременного наличия задач. В качестве контрпримера можно рассмотреть пять задач, А, В, С, D и Е, причем первые две доступны сразу же, а три оставшиеся - еще через три минуты. Время выполнения этих задач составляет 2, 4, 1, 1 и 1 мин соответственно.

Вначале можно выбрать только А или В, поскольку остальные недоступны. Если руководствоваться алгоритмом Кратчайшая задача - первая , задачи будут запущены в следующем порядке: А, В, С, D, Е и среднее оборотное время составит 4,6 мин. Если же запустить их в порядке В, С, D, Е, А, оно будет равно 4,4 мин.

2.4.5. Гарантированное планирование

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

Чтобы сдержать это обещание, система должна отслеживать распределение процессора между процессами с момента создания каждого процесса. Затем система рассчитывает количество ресурсов процессора, на которое процесс имеет право, например время с момента создания, деленное на п. Теперь можно сосчитать отношение времени, предоставленного процессу, к времени, на которое он имеет право. Полученное значение 0,5 означает, что процессу выделили только половину положенного, а 2,0 говорит о том, что процессу досталось в два раза больше его нормы. Далее запускается процесс, у которого это отношение наименьшее, пока оно не станет больше, чем у его ближайшего соседа.

2.4.6. Лотерейное планирование

Хотя идея обещаний пользователям и их выполнения хороша, но ее трудно реализовать. Для более простой реализации предсказуемых результатов применяется другой алгоритм, называемый лотерейным планированием [86].

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

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

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

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

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

2.4.7. Планирование в системах реального времени

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

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