|
Обычно к ресурсов в системе воспринимаются как объединение к дискретных обслуживающих устройств. Задача может обслуживаться устройством на приоритетной или неприоритетной основе и в течение времени обслуживания устройство полностью занято этой задачей. Допустим, что ресурсы устройства могут быть доступны задачам в дробных частях а, которые меняются от 0 до 1. Так, например, задача, требующая t единиц времени, при назначении полному устройству может потребовать 2t единиц при использовании половины ресурсного времени (а = 0,5). Если распределение ресурсов устройств допускается изменять до завершения задачи, то можно говорить об общих планах, ставших возможными благодаря технике разделения ресурсного времени. Легко показать, что для заданного графа с заданным количеством устройств при критерии качества работы в виде минимального времени выполнения планы, полученные с использованием GS подхода, эквивалентны планам, сформированным PS методом. Имеется в виду, что разделение ресурсного времени не является необходимостью для формирования оптимального плана, если разрешено приоритетное прерывание. Далее будем использовать определение уровней и сформулируем алгоритм генерации оптимальных приоритетных планов для вычислений с древовидной структурой при произвольном числе ресурсов к и взаимно соизмеримых весах узлов. Алгоритм генерации 2-А. Алгоритм начинается с назначения отдельных устройств (т. е. а = 1) каждой из к самых дальних от корня дерева задач. Две задачи Т( и Tj называются равноудаленными от заключительной задачи (находятся на одном уровне), если сумма весов задач от Т; до заключительной (включая Tj) равна сумме весов задач от Tj до заключительной. Если в любой момент времени число задач п, требующих обслуживания, больше чем к, то каждой из задач на одном и том же уровне 49 |
Обобщим полученные оптимальные решения для случая, когда допускается любое количество процессоров и вычислительный граф является; корневым деревом: (т. е. деревом, в котором каждый узел, за исключением, входного И'заключительного, имеет, по крайней мере, одного преемника) с взаимно соизмеримыми весами узлов w,-. Вместе с тем рассматриваются понятия общего плана, (general; schedules, GS) и разделения/ процессорного времени. Обычно;к процессоров в системе воспринимаются как объединение к дискретных вычислительных устройств. Задача может обслуживаться; процессором на приоритетной или неприоритетной основе и в течение* времени, обслуживания все ресурсы процессора подчиняются этой задаче. Допустим, что ресурсы процессора могут быть доступны задачам в дробных частях, а, которые меняются от 0 до 1. Так, например, задача, требующая t единиц времени, при назначении полному процессору может потребовать 2t единиц при использовании половины процессорного времени (а = 0,5). Если распределение процессорных ресурсов допускается изменять до завершения задачи, то можно говорить об общих планах, ставших возможными! благодаря технике разделения процессорного времени. Легко показать, что для заданного графа с заданным количеством процессоров при критериикачества работы в виде минимального времени выполнения планы, полученные с использованием GS подхода, эквивалентны планам, сформированным PS методом. Имеется в виду, что разделение, процессорного времени не является необходимостью для; формирования, оптимального плана, если разрешено приоритетное прерывание. Далее будем; использовать, определение уровней; и сформулируем алгоритм генерации оптимальных приоритетных планов • для вычислений с древовидной структурой при ^произвольном числе процессоров А: и взаимно соизмеримых весах узлов. Алгоритм генерации 2-А. Алгоритм начинается с назначения отдельных процессоров (т. е. а = 1) каждой из £ самых дальних от корня 55 дерева задач. Две задачи Tj и Tj называются равноудаленными от заключительной задачи (находятся на одном уровне), если сумма весов задач от Ti до заключительной (включая Tj) равна сумме весов задач от Tj до заключительной. Если в любой момент времени число задач л, требующих обслуживания, больше чем то каждой из задач на одном и-том же уровне назначается дробная часть а ресурсов процессора такая, что а = k/п. Задачи обслуживаются назначенными им процессорами с 0 < а < 1, пока 1) не закончится обслуживание задачи в дереве или 2) если не отменяется текущее назначение процессора; некоторые задачи, находящиеся на равном расстоянии от заключительного узла, будут пропускаться, пока не будет произведено переназначение. Когда происходит одно из этих событий, процессоры переназначаются в соответствии; с начальной процедурой назначения. План, сформированный, согласно этим правилам; называется Мпланом; он. изображен на рис. 2.12. Доказано, что М-план; построенный таким образом, является оптимальным. Так как М-план — общий (GS) и так как PS эквивалентен GS, алгоритм формирует оптимальный, план1 с приоритетами. Приоритетный план на рис: 2.12, с получен при условии, что все задачи, выполняемые внутри каждого из временных интервалов выполнения на рис. 2.12, Ь, являются независимыми. Следовательно, внутри каждого интервала задачи могут быть спланированы оптимальным образом с использованием приоритетных методов. Это осуществляется назначением задачи процессору, пока не завершится ее выполнение или не превысится интервал времени выполнения. В первом случае в точке завершения инициируется новая задача; во втором задача переназначается следующему в последовательности процессору. Представленный алгоритм можно считать обобщенным алгоритмом «критического пути» [10], так как, основываясь на удаленности заданий от заключительных задач, определена система приоритетов. Если применить уровневый алгоритм для исследования систем с неидентичными процессорами, то можно показать, что уровневый алгоритм формирует 56 |