XI Международная студенческая научная конференция Студенческий научный форум - 2019

Современный подход к созданию распределенных программно-информационных технологий (ПИТ) для корпоративных и производственных структур состоит в объединении в единую систему или сеть множества обрабатывающих средств (процессоров), средств хранения, обработки и управления информацией (разноплатформенные СУБД, различные учетные системы), средств обмена и коммутации структуры. На этапе системотехнического проектирования одной из важных задач является задача формирования алгоритмов распределенной обработки и управления [3]. На заданной структуре аппаратно-программных средств необходимо осуществить выбор системных и прикладных программ, структур данных и способов взаимодействия этих компонентов, обеспечивающих заданный режим применения ПИТ.

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

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

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

Итак, в нашем случае дополнительно предполагается наличие множества ресурсов R={R₁,...,R_S}. Если задаче T_j необходим ресурс R_i, то это требование принимается во внимание в течение всего периода выполнения задачи. Потребность задачи T_j в ресурсе R_i обозначается через p_ij ( ).

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

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

при R={R₁} (в системе существует только один вид ресурсов, отличных от процессора) - ;

при R={R₁} и независимости всех задач - ;

при R=(R₁, R₂,…, R_S}, независимости задач и - .

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

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

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

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

Пусть E_i – максимальное время выполнения одной итерации задачи J_i, а f_i – частота выполнения. Таким образом, каждой задаче J_i соответствуют два параметра J_i:(f_i, E_i), , где n – количество включаемых в план задач.

Период повторения равен T_i величине, обратной f_i. Рассмотрим два класса задач.

1) Если n задач с J₁ по J_n распределены так, что f_i > f_i+1, то предполагается, что f_i = 2f_i+1;

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

Рассматривая ограничения на время реакции системы управления, проанализируем периодичные задачи первого класса (с бинарным частотным распределением). Заметим, что слияние двух задач, создает новую периодичную задачу с периодом t₁ (равным 2T₁) и временем выполнения е₁ (равным T₁ + E₁). Кроме того, имеются два промежутка с простоями: I₁ периодичный простой с длительностью t₁ - е₁, и принудительное время простоя длинной I₁ - E₂ (обозначение указывает, что принудительное время простоя получается, когда J_j объединяется с J_i.) В процессе объединения остальных задач плана нет необходимости в рассмотрении размещения задач в интервале принудительного простоя.

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

1) Пусть J₁*, J₂*,… – подмножества задач, назначаемых процессорам P₁, P2,…. Сначала , а . Всякий раз, когда задача J_j назначается в некоторое пустое подмножество J_l*, I_l = T_j - E_j .

2) Чтобы назначить очередную задачу J_i, необходимо найти наименьшее l такое, чтобы выполнялось условие , и назначить Ji в подмножество J_l*.

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

Предлагаемые подходы делятся на три группы.

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

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

3. Сохранение минимальной длины критического интервала.

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

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

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

Список литературы

1. Барский, А.Б. Параллельные процессы в вычислительных системах/ А.Б. Барский.- М.: Радио и связь, 1990.

2. Воеводин, В.В. Математические модели и методы в параллельных процессах/ В.В. Воеводин.- М.: Наука, 1986.

3. Слепцов, А.И. Автоматизация проектирования управляющих систем/ А.И. Слепцов, А.А. Юрасов.- Киев: Техника, 1986.

4. Олифер, В.Г. Компьютерные сети. Принципы, технологии, протоколы/В.Г. Олифер, Н.А. Олифер.- СПб: Питер, 1999.

5. Олифер, В.Г. Сетевые операционные системы/В.Г. Олифер, Н.А. Олифер.- СПб: Питер, 2001.

6. Филлипс, Д. Методы анализа сетей: Пер. с англ./ Д. Филлипс, А. Гарсия-Диас. М.: Мир, 1984.

7. Gonzales, J.M. Deterministic Processor Scheduling / J.M. Gonzales// Computing Surveys. Vol. 9. No. 3. 1977.

8. Neumann, K. Stochastic Project Networks. Temporal Analysis, Scheduling and Cost Minimization/ K. Neumann// Lecture Notes in Economics and Mathematical Systems, No. 34, Springer-Verlag, 1990.

9. Phillips, D.T. Fundamentals of network analysis / D.T. Phillips, A. Garsia-Diaz. Prentice-Hall, Inc. Englewood Cliffs. New Jersy, 1981.

Код для цитирования: Скопировать