|
Указанная модель расширяет понятие стандартной модели, состоящей из множества г задач неравной длительности, связанных отношением предшествования, и выполняемых на неприоритетной основе набором из п идентичных процессоров. Дополнительно предполагается наличие множества ресурсов R=(R,,...,RS}. Если задаче 7,необходим ресурс Rj, то это требование принимается во внимание в течение всего периода выполнения задачи. Потребность задачи 7,в ресурсе /?, обозначается через ру (0 < р< 1). Положим r,(t) обозначает общее количество ресурсов Rt, которое используется в момент времени t. Тогда r(t) = Sum(p,y) для всех 7,-, выполняемых в момент времени г и r^t) < 1. Основная проблема заключается в определении того, в какой степени использование различных списков планов для этой модели влияет на время завершения w. Предположим, что для двух произвольных списков L и L’ расширенная система из п ресурсов выполняет набор из г задач с результирующими временами завершения w и w’ соответственно. Для такой среды предлагается следующее решение: при R={RiJ (в системе существует только один вид ресурсов) и/w' < п; при R={Rj} и независимости всех задач и>/ iv' < 3 -1 / п; при R=(Rj, R2,—, Rs), независимости задач и /2 > г wjw' < S +1. Общий смысл этих результатов заключается в том, что добавление ресурсов в стандартную модель является причиной усиления ограничений на поведение в наихудших случаях. По существу используется та же модель за исключением того, что все задачи для завершения требуют единичный интервал времени. Часто, используя эту модель, получаем ограничения на количество задач, число ресурсов и правила формирования списка использованных планов. Показано, что эти алгоритмы ведут себя хуже, когда устраняются ограничения на ресурсы. 65 |
Если приоритетные прерывания допускаются только в моменты времени; кратные w, то оптимальный неприоритетный, план для G может рассматриваться как оптимальный приоритетный план для G. Например, на рис. 2.18 показан случай, увеличения производительности разрешением приоритетных прерываний в конце каждого единичного интервала (т. е. w = 1). Включение приоритетных прерываний в конец каждого единичного интервала приводит к увеличению производительности на 117 %. Разрешение прерываний чаще, чемкаждые w/2 единиц,, не дает никакой выгоды, и для произвольного числа процессоров т (т > 1) длина Wn неприоритетного плана относится к длине приоритетного плана как Wn/Wp <2-\/т. 2.1.4. Периодичные задачи при формировании алгоритмов распределенной обработки и управления Введем новые ограничения в дополнение к ранее принятым; Эти новые ограничения представлены в форме классов ресурсов, периодичных задач с жесткими границами и временных пределов реализации задач. 2.1.4.1. Ограничения на классы ресурсов Решения, рассматриваемые до сих пор, были, связаны, прежде всего, с распределением процессоров. Вычислительные ограничения выражались в терминах времени выполнения и отношений предшествования. Следовательно, предполагалось, что процессор является единственным ресурсом, необходимым для выполнения работ. Признание факта, что задаче кроме процессора могут потребоваться дополнительные ресурсы, привело к исследованиям «систем с ограниченными ресурсами», в которых предполагается потребность в различных ресурсах, количество которых, ограничено. Указанная модель расширяет понятие стандартной модели, состоящей из множества г задач неравной длительности, связанных отношением предшествования, и выполняемых на неприоритетной основе набором из п идентичных: процессоров. Дополнительно предполагается наличие 70 множества ресурсов R={Rb...,Rs}Если задаче Ti необходим ресурс Rj, то это требование принимается во внимание в течение всего периода выполнения задачи. Потребность задачи Tj в ресурсе Rt обозначается черезру (0 < ру < 1). Положим rt(t) обозначает общее количество ресурсов Rb которое используется в момент времени t. Тогда г/?/ = Sumfp,^ для всех Tj, выполняемых в момент времени t и >;•(/)< 1. Основная проблема заключается в определении того, в какой степени использование различных списков планов для этой модели влияет на время завершения w. Предположим, что для двух произвольных списков L и L ’ расширенная система из п процессоров выполняет набор из г задач с результирующими временами завершения wnw’ соответственно. Для такой среды предлагается следующее решение: при R={Ri} (в системе существует только один вид ресурсов, отличных от процессора) w/w' Общий смысл этих результатов заключается в том, что добавление ресурсов в стандартную модель является причиной усиления ограничений на поведение в наихудших случаях. По существу используется та же модель за исключением того, что все задачи для завершения требуют единичный интервал времени. Часто, используя эту модель, получаем ограничения на количество задач, число процессоров и правила формирования списка использованных планов. Показано, что эти алгоритмы ведут себя хуже, когда устраняются ограничения на ресурсы. Можно предположить, что отдельные задачи требуют минимального количества памяти в дополнение к некоторому количеству времени обработки. Тогда рассматривается система из т идентичных процессоров и п независимых задач, причем каждый процессор связан с определенным 71 |