Лекция: Общий алгоритм построения списочных расписаний
[1]; для всех .
[2] Выбрать процессор с наименьшим среди всех процессоров (т.е. процессор на текущий момент с минимальным временем выполнения).
[3] Назначить следующим заданием на процессор, и модифицировать .
[4] Если, то увеличить и перейти к п.2. В противном случае, алгоритм заканчивается с расписанием, общая длина которого равняется максимуму из всех значений .
конец МСР.
Для изучаемой проблемы планирования заданий имеет смысл рассматривать 3 варианта упорядочивания для получения списка
а) список формируется в порядке уменьшения времен выполнения заданий, т.е. при условии. Данный вариант составления списочного расписания называется LPT (largest processing time, наибольшее время выполнения — другое название МСР — method critical path, метод критического пути [2]). Таким образом, в получаемом расписании первыми будут обслуживаться «большие» задания.
б) список формируется в порядке увеличения времен выполнения заданий, т.е. при условии. Данный вариант составления списочного расписания называется SPT (smallest processing time, наименьшее время выполнения).
в) список формируется в произвольном порядке. Данный вариант составления списочного расписания называется RPT (random processing time, произвольное время выполнения).
4.2.1. Составление расписаний методом критического пути.Метод критического пути отличается применением эвристического подхода, очень прост в реализации и позволяет получить требуемые по точности решения. В общем случае списочные расписания дают приближенные решения, однако для алгоритма LTP доказано, что
,
где — длина расписания, полученного при помощи алгоритма LTP, — длина оптимального расписания.
Таким образом, в наихудшем случае для (т.е. для ВС, состоящей из трех процессоров) при помощи метода LTP можно получить расписание, длина которого будет в раз больше длины оптимального расписания, т.е. длина увеличится приблизительно на.Для в наихудшем случае получаем отношение и т.д.
Ход работы алгоритма МСР проиллюстрируем примером, который позволяет убедиться в реализуемости и доступности данного метода.
Пример. Пусть ВС состоит из идентичных процессоров. На выполнение поступает независимых заданий, характеристика которых представлена в табл. 2.8… Решим данный пример каждым из алгоритмов, показав преимущества и недостатки каждого из них.
Таблица 2.8
Для алгоритма LTP сначала необходимо соответствующим образом упорядочить задания в порядке убывания элементов и сформировать список. При этом будет получен следующий список:
LTP: ;
Дальнейшие вычисления отражены в таблице 2.9. Временные диаграммы сформированных расписаний изображены на рис. 2.1.
Вычисления для LTP
Таблица 2.9
| Оценки результирующего расписания |
4.2.2. Составление расписаний методом SPT.Для алгоритма SPT сначала необходимо соответствующим образом упорядочить задания в порядке возрастания элементов и сформировать список. При этом будет получен следующий список: STP: ;
Дальнейшие вычисления отражены в таблице 2.10. Временные диаграммы сформированных расписаний изображены на рис.2.2.
Вычисления для STP
Таблица 2.10
| Оценки результирующего расписания |
Рис. 2.2. Расписание для STP
4.2.3. Составление расписаний методом RPT. Для алгоритма RTP список заданий можно организовать в любом порядке. Поэтому для простоты можно использовать исходный порядок (табл. 2.11).
RTP: .
Вычисления для RTP
Таблица 2.11
| Результирующее расписание |
Рис. 2.3. Расписание для RTP
Таким образом, получены следующие расписания:
LTP:,,, ;
STP:,,, ;
RTP:,,, .
Близкое к оптимальному решение было получено, в данном случае, при помощи алгоритма LTP и RTP, а алгоритм STP дал плохой результат.