|
<—1—► Т, т. J т, т, 1 в* Рисунок 2.1.5 Двухпроцессорный план с минимальным временем выполнения трех единичных задач Т, т5 Т6 Т, -Лит, т« т, Т. Т,п I I 1 1 0 1 2 3 4 5 6 (Ь) Рисунок 2.1.6 Оптимальная последовательность подмножества: а граф G для множества задач со всеми узлами, имеющими единичные веса; b оптимальный план с приоритетными прерываниями. Обобщим полученные оптимальные решения для случая, когда допускается любое количество ресурсов и вычислительный граф является корневым деревом (т. е. деревом, в котором каждый узел, за исключением входного и заключительного, имеет, по крайней мере, одного преемника) с взаимно соизмеримыми весами узлов Wj. Вместе с тем рассматриваются понятия общего плана (general schedules, GS) и разделения ресурсного времени. 48 |
менее чем за 1,5 единичных интервала времени, так как все задачи в Gw имеют длительность 1. На рис. 2.10 изображен план, когда три задачи одного уровня могут быть обслужены в минимальное время без простоя процессора. Так как такое планирование не использует холостого хода процессора, то последовательность подмножества может рассматриваться для создания PS плана минимальной длины. Пример оптимального PS алгоритма показан на рис. 2.11. Для этого примера оптимальной последовательностью подмножества для G является: {Tj}, {T2,T3},{T5,T6,T7},{T4,T8},{T9,Tio},{Tii}. н—1—н т, I т2 ,.Г т2 I т3 г ч---------1,5------► Рис. 2.10. Двухпроцессорный план с минимальным временем выполнения трех единичных задач > 2%, Т2 У5 1 Т« Т4 т9 т„ Т3 т« 1 Ь Tg Т,о 0 1 2 1 3 1 4 1 5 1 6 (Ь) Рис. 2.11. Оптимальная последовательность подмножества: а граф G для множества задач со всеми узлами, имеющими единичные веса; b оптимальный план с приоритетными прерываниями. 54 Обобщим полученные оптимальные решения для случая, когда допускается любое количество процессоров и вычислительный граф является; корневым деревом: (т. е. деревом, в котором каждый узел, за исключением, входного И'заключительного, имеет, по крайней мере, одного преемника) с взаимно соизмеримыми весами узлов w,-. Вместе с тем рассматриваются понятия общего плана, (general; schedules, GS) и разделения/ процессорного времени. Обычно;к процессоров в системе воспринимаются как объединение к дискретных вычислительных устройств. Задача может обслуживаться; процессором на приоритетной или неприоритетной основе и в течение* времени, обслуживания все ресурсы процессора подчиняются этой задаче. Допустим, что ресурсы процессора могут быть доступны задачам в дробных частях, а, которые меняются от 0 до 1. Так, например, задача, требующая t единиц времени, при назначении полному процессору может потребовать 2t единиц при использовании половины процессорного времени (а = 0,5). Если распределение процессорных ресурсов допускается изменять до завершения задачи, то можно говорить об общих планах, ставших возможными! благодаря технике разделения процессорного времени. Легко показать, что для заданного графа с заданным количеством процессоров при критериикачества работы в виде минимального времени выполнения планы, полученные с использованием GS подхода, эквивалентны планам, сформированным PS методом. Имеется в виду, что разделение, процессорного времени не является необходимостью для; формирования, оптимального плана, если разрешено приоритетное прерывание. Далее будем; использовать, определение уровней; и сформулируем алгоритм генерации оптимальных приоритетных планов • для вычислений с древовидной структурой при ^произвольном числе процессоров А: и взаимно соизмеримых весах узлов. Алгоритм генерации 2-А. Алгоритм начинается с назначения отдельных процессоров (т. е. а = 1) каждой из £ самых дальних от корня 55 |