Планирование задач при мультиресурсной реализации алгоритмов распределенной обработки информации и управления

Современный подход к созданию распределенных программно-информационных технологий для корпоративных и производственных структур состоит в объединении в единую систему или сеть множества обрабатывающих средств (процессоров), средств хранения, обработки информации и управления (разноплатформенные системы управления базами данных, различные учетные системы).

На этапе системотехнического проектирования одной из важных задач является формирование алгоритмов рас пределенной обработки и управления [1]. На заданной структуре аппаратно-программных средств необходимо осуществить выбор системных и прикладных программ, структур данных и способов взаимодействия этих компонентов, обеспечивающих заданный режим применения программно-информационных технологий. При этом необходимо учитывать, что в распределенных системах режим реального времени предполагает лимитирование времени ответа системы управления на запрос объекта.

Ограничение на время реакции связывается в этом случае с выполнением периодических действий [2; 3]. Моменты запроса периодической задачи можно заранее определить путем прибавления к моменту начального запроса величины, кратной известному периоду

Таким образом, при реализации периодичных задач формирование алгоритмов распределенной обработки информации и управления должно осуществляться с учетом ограничений, представленных в форме классов ресурсов, жесткого регламента задач и временных пределов реализации задач.

Рассмотрим существующие ограничения на классы ресурсов. Решения, предложенные ранее в источниках [4-8], были связаны, прежде всего, с распределением процессоров. Вычислительные ограничения выражались в терминах времени выполнения и отношений предшествования.

Следовательно, предполагалось, что процессор является единственным ресурсом, необходимым для выполнения работ. Признание факта, что задаче кроме процессора могут потребоваться дополнительные ресурсы, приводит к исследованиям систем с ограниченными ресурсами [8].

Предлагаемая модель расширяет понятие стандартной модели [8], состоящей из множества г задач неравной длительности, связанных отношением предшествования и выполняемых на неприоритетной основе набором из и идентичных процессоров. В источнике [3] отмечается, что проблема планирования зависимых задач очень сложна, нахождение ее оптимального решения требует больших вычислительных ресурсов, сравнимых с теми, которые требуются собственно для выполнения задач управления. Отметим, что при таком подходе планирование приближается к статическому

В нашем случае дополнительно предполагается наличие множества ресурсов R = {R_t, „., R₅}. Если задаче Т . необходим ресурс R, то это требование принимается во внимание в течение всего периода выполнения задачи. Потребность задачи Т. в ресурсе R. обозначается черезр ._ (0< р_#<1).

Пусть г . (t) обозначает общее количество ресурсов R, которое используется в момент времени t. Тогда г . (0 = Sum(p) для всех Т, выполняемых в момент времени t. Основная проблема заключается в определении того, в какой степени использование различных списков планов для этой модели влияет на время завершения w.

Предположим, что для двух произвольных списков L и L' расширенная система из и процессоров выполняет набор из г задач с результирующими временами завершения w и w' соответственно. Для такой среды в [8] предлагается ряд решений, которые дают следующие результаты:

• -    при R = {RJ (в системе существует только один вид ресурсов, отличных от процессора) - w / w'< и;

• -    при R = {R₁} и независимости всех задач -w / w' < (3 - 1 / и);

• -    при R = (R₁, R₂, „., R_s}, независимости задач и и > г - w / w' <5+1.

Общий смысл этих результатов заключается в том, что добавление ресурсов в стандартную модель является причиной усиления ограничений на поведение в наихудших случаях. По существу используется одна и та же модель за исключением того, что все задачи для завершения требуют единичный интервал времени. С использованием этой модели получены ограничения на количество задач, число процессоров и правила формирования списка используемых статических планов. Показано, что эти алгоритмы ведут себя хуже, когда устраняются ограничения на ресурсы.

Классическим примером планирования независимых задач для жестких систем реального времени с одним процессором является алгоритм, разработанный Лью и Лейландом [9]. Этот алгоритм является динамическим, он использует вытесняющую многозадачность и основан на относительных статических (неизменяемых в течение жизни задачи) приоритетах.

Если предположить, что отдельные задачи требуют некоторого количества памяти в дополнение к некоторому количеству процессорного времени обработки, то следует рассматривать систему из m идентичных процессоров и и независимых задач, причем каждый процессор связан с определенным устройством памяти некоторой емкости. Когда процессор завершает выполнение задачи, в списке задач выбирается первая задача, чьи требования памяти не превышают его собственного объема. Для неприоритетной среды в источнике [8] предлагаются эвристические стратегии выбора задач на основе требований времени и памяти одновременно. Касаясь периодического набора задач, следует отметить, что ранее в этой работе для однопроцессорных планов при выполнении временных ограничений задач с более высокими приоритетами разрешалось приоритетное прерывание периодичных задач с низкими приоритетами. Нами рассматриваются неприоритетные многопроцессорные планы для набора независимых периодичных задач.

Итак, предполагается, что все задачи доступны одновременно. Цель - минимизация числа процессоров, требуемых для выполнения ряда задач при временных ограничениях на начало/конец выполнения заданий.

Пусть Е . - максимальное время выполнения одной итерации задачи J, а/- частота выполнения. Таким образом, каждой задаче J. соответствуют два параметра J: (/ ? , Е . ), 1 <. < и, где и - количество включаемых в план задач.

Период повторения равен Т, величине обратной^ ? . Рассмотрим два класса задач:

• 1)    если и задач сJ₁ по J_n распределены так, что/>/_{+ 1}, то предполагается, что/. = 2/ . ₊₁;

• 2)    допускаются задачи с любой частотой.

Рассматривая ограничения на время реакции системы, проанализируем периодичные задачи первого класса (с бинарным частотным распределением). Множество задач, удовлетворяющих бинарному частотному распределению, приведено в таблице.

Задачи J и J, спланированные на разных процессорах, приведены на рис. 1. План, уменьшающий количество процессоров с двух до одного, приведен на рис. 2. Проблемой является определение минимального количества процессоров без перебора всех возможных альтернатив.

Заметим, что слияние двух задач (рис. 2) создает новую периодичную задачу с периодом t1 (равным 2Т) и временем выполнения е1 (равным Тх + Е1). Кроме того, имеются два промежутка со следующими простоями: 71 - периодичный простой с длительностью ^ - et и А 2 -принудительное время простоя длинной 71 - Е2 (обозна-i чение А— указывает, что принудительное время простоя получается, когда/.объединяется сJ).

Рис. 1. Временная диаграмма для задач J и J ₂

Рис. 2. Ослабление ограничений на число процессоров путем слияния задач

В процессе объединения остальных задач плана нет необходимости рассматривать размещение задач в интервале принудительного простоя. Вместо этого для такой среды план с минимальным числом процессоров формируется в соответствии со следующим алгоритмом:

• 1)    пусть/₁ *, J₂*, - подмножества задач, назначаемых процессорам Р₁,Р₂. Сначала J₁*=J₂* = ... =0,а7₁ =7₂=... =<». Всякий раз, когда задача/добавляется в некоторое пустое подмножество, J*, ^ = Д - Е;

• 2)    чтобы назначить очередную задачу/, необходимо найти такое наименьшее значение 7, чтобы выполнялось условие Е. < 7.. Добавить / в подмножество J^.

В случае, когда устранена бинарная частотная связь между задачами, принятая ранее, т.е. в режиме реального времени, реализуются периодичные задачи с независимым распределением частот, то задача становится более сложной, а оптимальное решение не может быть найдено точными методами. Были разработаны эвристические алгоритмы и проведено их относительное сравнение с применением моделирования. Предлагаемые подходы делятся на три группы.

• 1.    В порядке уменьшения частоты. Задачи располагаются в порядке уменьшения частоты, их назначение также должно проходить в этом порядке.

• 2.    В порядке уменьшения критерия загрузки. Критерий загрузки задачи /, обозначаемый L, определяется следующим образом: L . = Е . / Т . .

• 3.    Сохранение минимальной длины критического интервала. Критический интервал между двумя задачами определяется как минимальный интервал между временем завершения первой задачи и временем начала выполнения второй задачи в некоторой точке плана. Определение этого интервала не включает первую итерацию обоих задач, где по определению начало выполнения второй задачи немедленно следует за завершением первой задачи.

При тестировании данных методов задачи разделялись на два класса. В первом классе частоты задач кратны более, чем двум базовым частотам, а во втором - не более, чем двум базовым частотам. Ни один из алгоритмов не показал значительного превосходства над другими. Однако подход 2 исключительно хорошо показал себя на задачах первого класса. Подход 3 лучше решает некоторые задачи второго класса, а подходы 1, 2 неплохо решают задачи, которые оказались трудными для подхода 3. В этом нет ничего необычного, так как число процессоров, необходимых для задач второго класса, было значительно меньше, чем для задач первого класса.

Также были обнаружены некоторые интересные закономерности. Во многих случаях уменьшение частот задач или времени их выполнения может привести к увеличению количества требуемых процессоров. И наоборот, требуемое количество процессоров может быть уменьшено за счет увеличения частот задач или времен выполнения, т. е. путем увеличения загруженности процессора.

В источнике [6] показано, что рассмотренные алгоритмы могут быть реализованы как с помощью моделей одного класса, так и с использованием многокомпонентной сетевой модели, включающей детерминированные [7; 9] и стохастические компоненты [10]. Концепция многокомпонентной сетевой модели с GERT-подобной узловой логикой [6] позволяет объединить различные программные компоненты модельно-алгоритмического обеспечения единой базой данных и обеспечить эффективное формирование алгоритмов распределенной обработки и управления с учетом периодичных задач.