|
назначается дробная часть а ресурсов устройства такая, что а = А/л. Задачи обслуживаются назначенными им устройствами с 0<я<1, пока 1) не закончится обслуживание задачи в дереве или 2) если не отменяется текущее назначение устройства; некоторые задачи, находящиеся на равном расстоянии от заключительного узла, будут пропускаться, пока не будет произведено переназначение. Когда происходит одно из этих событий, устройства переназначаются в соответствии с начальной процедурой назначения. План, сформированный согласно этим правилам, называется Мпланом; он изображен на рисунке 2.1.7. Доказано, что М-план, построенный таким образом, является оптимальным. Так как М-план — общий (GS) и так как PS эквивалентен GS, алгоритм формирует оптимальный план с приоритетами. Приоритетный план на рисунке 2.1.7, с получен при условии, что все задачи, выполняемые внутри каждого из временных интервалов выполнения на рисунке 2.1.7, Ь, являются независимыми. Следовательно, внутри каждого интервала задачи могут быть спланированы оптимальным образом с использованием приоритетных методов. Это осуществляется назначением задачи устройству, пока не завершится ее выполнение или не превысится интервал времени выполнения. В первом случае в точке завершения инициируется новая задача; во втором задача переназначается следующему в последовательности устройству. Представленный алгоритм можно считать обобщенным алгоритмом «критического пути» [7], так как, основываясь на удаленности заданий от заключительных задач, определена система приоритетов. Если применить уровневый алгоритм для исследования систем с неидентичными ресурсами, то можно показать, что уровневый алгоритм формирует наикратчайшие приоритетные планы на двух ресурсах для произвольных наборов задач. 50 |
дерева задач. Две задачи Tj и Tj называются равноудаленными от заключительной задачи (находятся на одном уровне), если сумма весов задач от Ti до заключительной (включая Tj) равна сумме весов задач от Tj до заключительной. Если в любой момент времени число задач л, требующих обслуживания, больше чем то каждой из задач на одном и-том же уровне назначается дробная часть а ресурсов процессора такая, что а = k/п. Задачи обслуживаются назначенными им процессорами с 0 < а < 1, пока 1) не закончится обслуживание задачи в дереве или 2) если не отменяется текущее назначение процессора; некоторые задачи, находящиеся на равном расстоянии от заключительного узла, будут пропускаться, пока не будет произведено переназначение. Когда происходит одно из этих событий, процессоры переназначаются в соответствии; с начальной процедурой назначения. План, сформированный, согласно этим правилам; называется Мпланом; он. изображен на рис. 2.12. Доказано, что М-план; построенный таким образом, является оптимальным. Так как М-план — общий (GS) и так как PS эквивалентен GS, алгоритм формирует оптимальный, план1 с приоритетами. Приоритетный план на рис: 2.12, с получен при условии, что все задачи, выполняемые внутри каждого из временных интервалов выполнения на рис. 2.12, Ь, являются независимыми. Следовательно, внутри каждого интервала задачи могут быть спланированы оптимальным образом с использованием приоритетных методов. Это осуществляется назначением задачи процессору, пока не завершится ее выполнение или не превысится интервал времени выполнения. В первом случае в точке завершения инициируется новая задача; во втором задача переназначается следующему в последовательности процессору. Представленный алгоритм можно считать обобщенным алгоритмом «критического пути» [10], так как, основываясь на удаленности заданий от заключительных задач, определена система приоритетов. Если применить уровневый алгоритм для исследования систем с неидентичными процессорами, то можно показать, что уровневый алгоритм формирует 56 |