|
является кратным целому числу w. Далее рассматриваются оптимальные решения для корневых деревьев с взаимно соизмеримыми весами узлов и любым числом ресурсов. Планы с приоритетными прерываниями могут противопоставляться неприоритетным или простым планам (basic schedules, BS). В последнем типе планов задача обслуживается ресурсом до тех пор, пока не завершится ее выполнение. В приоритетном плане обслуживание некоторой задачи может быть приостановлено, если такое действие приводит к улучшению показателя производительности. Известна нижняя граница на оптимальном PS-плане для множества из п независимых задач с весами (продолжительность задачи или времена выполнения) (w,,w2,...,wnI и к ресурсами. Эта оптимальная длительность определяется как max {max {щ.}, (Y wf) / к}. l В оптимальном плане необходимо разбить множество узлов в графе с узлами удельного веса в последовательность непересекающихся подмножеств так, чтобы все узлы в подмножестве были независимы. Все узлы из одного подмножества или на одном уровне являются кандидатами на одновременное выполнение. В W-уровневом графе заключительный узел занимает исключительно первый уровень. Узлы, которые могут быть выполнены в течение единичного периода времени, предшествующего выполнению заключительного узла, занимают второй уровень, и так далее, вплоть до начального или входного узла в графе, который занимает N-R уровень. Подобное назначение уровней соответствует методам разбиения по 45 |
2.Т.З.1. Обычные среды планирования: Эта часть работы разделена на две части согласно оптимизируемым критериям производительности. Первая часть обсуждения акцентирует внимание на минимизации, максимального времени выполнения и минимизации количества процессоров; вторая часть имеет целью сравнение приоритетных и неприоритетных планов при формировании распределенных алгоритмов обработки информации и управления. 1. Минимизация времени выполнения процессов и количества процессоров Отдельно рассмотрены планы с наличием приоритетного прерывания и планы без допущения приоритетных прерываний. Планы с приоритетными прерываниями обозначаются как PS-планы (preemptive schedules, PS). Сначала рассмотрим получаемое оптимальное решение длянаиболее распространенного случая; когда любой граф с взаимно соизмеримыми весами узлов выполняется на двух процессорах. Множество узлов считают взаимно, соизмеримым, если существует w такой, что каждый вес узла является кратным-целому числу w. Далее рассматриваются оптимальные решения для корневых деревьев с взаимно соизмеримыми весами узлов и любым числом процессоров. Планы с приоритетными прерываниями могут противопоставляться неприоритетным или простым планам (basic schedules, BS). В последнем типе планов задача обслуживается процессором до тех пор, пока не завершится ее выполнение. В приоритетном плане обслуживание процессором некоторой задачи может быть, приостановлено, если такое действие приводит к улучшению показателя производительности. Известна нижняя граница на оптимальном PS-плане для множества из п независимых задач с весами (продолжительность задачи, или времена выполнения) {wi,W2,...,wn} и £ процессорами. Эта оптимальная длительность определяется как 51 п max {тах{и>.}, (V w{) / к}. 1-z-rt /=i Другими словами, оптимальная длина PS не может быть меньше, чем наибольшая по длительности задача распределенного алгоритма или сумма времен выполнения, деленная на количество процессоров. В оптимальном алгоритме необходимо разбить множество узлов в графе с узлами удельного веса в последовательность непересекающихся подмножеств так, чтобы-все узлы в подмножестве были независимы. Все узлы из одного подмножества или на одном уровне являются кандидатами на одновременное выполнение. В TV-уровневом графе заключительный узел занимает исключительно первый уровень. Узлы, которые могут быть выполнены в течение единичного периода времени, предшествующего выполнению заключительного узла, занимают второй уровень, и так далее, вплоть до начального или входного узла в графе, который занимает TV-й уровень. Подобное назначение уровней соответствует методам разбиения по старшинству (предшествования), рассмотренным Рамамурти и Гонзалесом. В частности, описанная выше процедура назначения соответствует разбиению по последнему предшествованию, т. е. назначение узлов уровням, с отнесением момента, инициирования задачи к самому последнему возможному времени без увеличения минимального времени выполнения, с условием, что число процессоров не меньше максимального числа задач среди уровней. Для произвольного графа G отношение предшествования будет существовать между подмножеством благодаря предшествованию, которое существует между узлами в изначальном графе. PS план для G может быть создан путем планирования сначала подмножествас наибольшим номером затем следующего, нижележащего уровня-и так далее. Когда подмножество состоит только из одного узла, узел из нижележащего подмножества перемещается вверх, если это не нарушает ограничений предшествования. Если каждое из подмножеств спланировано оптимально, то в результате получаем план подмножеств. Показано, что для двух 52 |