15 Вопрос. Планирование в системах пакетной обработки данных

"Первым пришел - первым обслужен"

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

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

"Кратчайшая задача - первая"

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

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

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

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