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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автори:	Симоненко, В.П., Сергиенко, А.М.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2016
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/140242
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Динамическое распределение работ по ресурсам в неоднородной системе с ограничениями реального времени / В.П. Симоненко, А.М. Сергиенко // Системні дослідження та інформаційні технології. — 2016. — № 3. — С. 42-50. — Бібліогр.: 8 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-140242
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1402422025-02-23T19:07:45Z Динамическое распределение работ по ресурсам в неоднородной системе с ограничениями реального времени Динамічний розподіл робіт по ресурсах в неоднорідній системі з обмеженнями реального часу Dynamical task scheduling in the heterogeneous system with the real time limitations Симоненко, В.П. Сергиенко, А.М. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Предложен метод динамического распределения работ в неоднородной вычислительной системе в реальном времени. Основой метода является предварительная подготовка исходной информации с учетом ограничений на продолжительность планирования, сложности выполняемых работ, а также индивидуальных характеристик ресурсов, таких как производительность, емкость памяти, наличие загруженных исходных данных и математического обеспечения. Алгоритм такой подготовки состоит в формировании матрицы запасов времени выполнения работ на ресурсах и в последовательности преобразований этой матрицы в матрицу стоимостей с применением матрицы проверки конфликтности назначений. После подготовки информации задача планирования решается венгерским алгоритмом поиска максимального паросочетания в графе. Запропоновано метод динамічного розподілу робіт у неоднорідній обчислювальній системі в реальному часі. Основою методу є попередня підготовка вихідної інформації з урахуванням тривалості планування, складності виконуваних робіт, а також індивідуальних характеристик ресурсів, таких як продуктивність, ємність пам'яті, наявність завантажених математичного забеспечення та початкових даних. Алгоритм такої підготовки полягає у формуванні матриці запасів часу виконання робіт на ресурсах і в послідовності перетворень цієї матриці у матрицю вартостей із застосуванням матриці перевірки конфліктності призначень. Після підготовки інформації завдання планування вирішується угорським алгоритмом пошуку максимального паросполучення у графі. A method of dynamic real time scheduling of tasks in a heterogeneous system is considered. The method consists in a preliminary preparation of the initial information set, taking into account the duration of the scheduling, the complexity of tasks, as well as individual resource characteristics such as performance, memory capacity, availability of downloaded software and initial data. The algorithm of this preparation consists in forming a job time reserve matrix and performing a sequence of transformations of this matrix to the cost matrix taking into account the assignment conflict matrix. After preparation of the initial information set, the planning problem is solved by the Hungarian algorithm of finding the maximum bipartite matching. 2016 Article Динамическое распределение работ по ресурсам в неоднородной системе с ограничениями реального времени / В.П. Симоненко, А.М. Сергиенко // Системні дослідження та інформаційні технології. — 2016. — № 3. — С. 42-50. — Бібліогр.: 8 назв. — рос. 1681–6048 DOI: 10.20535/SRIT.2308-8893.2016.3.04 https://nasplib.isofts.kiev.ua/handle/123456789/140242 004.383 ru Системні дослідження та інформаційні технології application/pdf Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
spellingShingle	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Симоненко, В.П. Сергиенко, А.М. Динамическое распределение работ по ресурсам в неоднородной системе с ограничениями реального времени Системні дослідження та інформаційні технології
description	Предложен метод динамического распределения работ в неоднородной вычислительной системе в реальном времени. Основой метода является предварительная подготовка исходной информации с учетом ограничений на продолжительность планирования, сложности выполняемых работ, а также индивидуальных характеристик ресурсов, таких как производительность, емкость памяти, наличие загруженных исходных данных и математического обеспечения. Алгоритм такой подготовки состоит в формировании матрицы запасов времени выполнения работ на ресурсах и в последовательности преобразований этой матрицы в матрицу стоимостей с применением матрицы проверки конфликтности назначений. После подготовки информации задача планирования решается венгерским алгоритмом поиска максимального паросочетания в графе.
format	Article
author	Симоненко, В.П. Сергиенко, А.М.
author_facet	Симоненко, В.П. Сергиенко, А.М.
author_sort	Симоненко, В.П.
title	Динамическое распределение работ по ресурсам в неоднородной системе с ограничениями реального времени
title_short	Динамическое распределение работ по ресурсам в неоднородной системе с ограничениями реального времени
title_full	Динамическое распределение работ по ресурсам в неоднородной системе с ограничениями реального времени
title_fullStr	Динамическое распределение работ по ресурсам в неоднородной системе с ограничениями реального времени
title_full_unstemmed	Динамическое распределение работ по ресурсам в неоднородной системе с ограничениями реального времени
title_sort	динамическое распределение работ по ресурсам в неоднородной системе с ограничениями реального времени
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2016
topic_facet	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
url	https://nasplib.isofts.kiev.ua/handle/123456789/140242
citation_txt	Динамическое распределение работ по ресурсам в неоднородной системе с ограничениями реального времени / В.П. Симоненко, А.М. Сергиенко // Системні дослідження та інформаційні технології. — 2016. — № 3. — С. 42-50. — Бібліогр.: 8 назв. — рос.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT simonenkovp dinamičeskoeraspredelenierabotporesursamvneodnorodnojsistemesograničeniâmirealʹnogovremeni AT sergienkoam dinamičeskoeraspredelenierabotporesursamvneodnorodnojsistemesograničeniâmirealʹnogovremeni AT simonenkovp dinamíčnijrozpodílrobítporesursahvneodnorídníjsistemízobmežennâmirealʹnogočasu AT sergienkoam dinamíčnijrozpodílrobítporesursahvneodnorídníjsistemízobmežennâmirealʹnogočasu AT simonenkovp dynamicaltaskschedulingintheheterogeneoussystemwiththerealtimelimitations AT sergienkoam dynamicaltaskschedulingintheheterogeneoussystemwiththerealtimelimitations
first_indexed	2025-11-24T15:03:56Z
last_indexed	2025-11-24T15:03:56Z
_version_	1849684537599066112
fulltext	 В.П. Симоненко, А.М. Сергиенко, 2016 42 ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 УДК 004.383 DOI: 10.20535/SRIT.2308-8893.2016.3.04 ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ РАБОТ ПО РЕСУРСАМ В НЕОДНОРОДНОЙ СИСТЕМЕ С ОГРАНИЧЕНИЯМИ РЕАЛЬНОГО ВРЕМЕНИ В.П. СИМОНЕНКО, А.М. СЕРГИЕНКО Аннотация. Предложен метод динамического распределения работ в неодно- родной вычислительной системе в реальном времени. Основой метода являет- ся предварительная подготовка исходной информации с учетом ограничений на продолжительность планирования, сложности выполняемых работ, а также индивидуальных характеристик ресурсов, таких как производительность, ем- кость памяти, наличие загруженных исходных данных и математического обеспечения. Алгоритм такой подготовки состоит в формировании матрицы запасов времени выполнения работ на ресурсах и в последовательности преоб- разований этой матрицы в матрицу стоимостей с применением матрицы про- верки конфликтности назначений. После подготовки информации задача планирования решается венгерским алгоритмом поиска максимального паро- сочетания в графе. Ключевые слова: расписание, двудольный граф, венгерский алгоритм, пла- нировщик. ВВЕДЕНИЕ Планирование вычислений состоит в определении плана решения совокуп- ности работ с определенным временем исполнения и ограничениями по времени их выхода из вычислительной системы (ВС). Система планирова- ния должна обеспечить выполнение требования минимального суммарного временного отклонения моментов выхода работ из ВС от заданных сроков их выполнения при соблюдении порядка следования. Планирование в реаль- ном времени, т.е. динамическое планирование, означает, что такая задача должна быть решена за интервал времени, который оказывается меньшим чем некоторое значение, определяемое допустимым временем реакции ВС на поток заявок на работы. Поэтому такое планирование является довольно трудной задачей. В общем случае задача планирования, даже с одним вы- числительным узлом, относится к классу NP-полных [1, 2]. В большинстве случаев разработчики систем планирования в реальном времени используют статические алгоритмы и заранее определяют макси- мальный список заявок на работы, допустив наихудший случай для получе- ния статической таблицы, управляющей распределением работ, т.е. плана. Этот план фиксируется и используется для безусловного исполнения в ди- намическом режиме со следующими допущениями: — все временные ограничения остаются неизменными на время выпо- лнения плана; — все работы вкладываются в свое критическое время исполнения и выхода работ из системы. Динамическое распределение работ по ресурсам неоднородной системе с ограничениями … Системні дослідження та інформаційні технології, 2016, № 3 43 В других случаях при помощи приемов статического планирования создается статический список приоритетов для использования в динамиче- ском режиме во время диспетчеризации самих работ. Если система реального времени работает только в динамическом ре- жиме, то использование допущений статического планирования, когда все известно априори, недопустимо. В этом случае выбирается один из возмож- ных алгоритмов составления расписания и тщательно анализируется на применимость его в динамическом режиме в конкретной вычислительной системе. Как правило, применяются алгоритмы, использующие планирова- ние по спискам, и приоритетное обслуживание [3–6]. В работе предлагается динамическое планирование выполнять с ис- пользованием математического аппарата поиска максимального паросоче- тания. Для этого разработан метод преобразования исходной информации о множестве работ в исходные данные для составления плана с помощью это- го аппарата. Причем распределение заявок на работы по ресурсам реализу- ется для неоднородной параллельной вычислительной системы (НПВС) с учетом ограничений реального времени и выполняется планировщиком нижнего уровня. В качестве этого аппарата целесообразно использовать венгерский алгоритм, а также его модификацию, описанную авторами в ра- боте [7], которая имеет меньшую временную сложность. ПОСТАНОВКА ЗАДАЧИ Рассмотрим общую постановку задачи планирования с ограничениями ре- ального времени. На вход НПВС поступает множество работ. Из него выби- рается порция n работ, которые следует распределить на n имеющихся ре- сурсов. Каждая работа характеризуется тремя временными параметрами: iTin — момент поступления i-й входной работы в ВС; iTout — момент выхода i-й работы из ВС; i wT — длительность выполнения i-й работы на вычислительном узле НПВС, имеющем максимальную производительность, ni ,,1  , которая равна оценке сложности этой работы. Распределенная ВС, такая как НПВС, имеет множество ресурсов; j-й характеризуется производительностью jR . Для i-й работы можно опреде- лить время решения ее на j-м ресурсе в относительных единицах. Для этого определим },...,{max 1 max nRRR  . Определим относительную производительность j-го вычислительного узла как maxRRZ jj  , nj ,,1  . Имея значения относительной производительности узлов, можно опре- делить отношение работа–ресурс с учетом времени выполнения работы и производительности каждого узла НПВС. Для этого сформируем матрицу связности С, в которой элемент ji w ZTjiC ],[ определяет относительное время выполнения i-й работы на j-м ресурсе с учетом его производительно- сти. Причем значение ],[ jiC определяет относительное время выполнения В.П. Симоненко, А.М. Сергиенко ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 44 i-й работы на j-м ресурсе ввиду того, что 10  jZ . Элемент ],[ jiC также учитывает наличие загруженных исходных данных и математического обес- печения. Например, при их отсутствии 0],[ jiC . В системах с несколькими обслуживающими ресурсами часто исполь- зуется стратегия минимизации максимальной из продолжительностей ис- пользования ресурсов, что обычно связано с повышением быстродействия такой системы при функционировании в интерактивном режиме. В работе используется критерий минимума времени выполнения всех работ, посколь- ку предполагается, что все заявки на работы являются независимыми и тре- буется, чтобы не достигалось максимально допустимое время реакции iTout на i-ю заявку. Обычно iTout указывается в спецификации заявки. При этом для выполнения каждой работы обеспечивается требуемое быстродействие системы. В связи с тем, что работа, выполняемая с ограничениями в реальном времени, должна завершиться до заданного времени реакции iTout , то необ- ходимо учитывать временной запас загрузки ресурса: ],[inout , jiCTT i i iji t  . Запас ji t , может принимать как положительные, так и отрицательные значения в зависимости от сложности i wT работы и относительной произво- дительности jZ j-го ресурса. Положительные значения ji t , означают, что работа i, назначенная на ресурс j, будет завершена на промежуток времени ji t , до назначенного срока, а отрицательные — что выход заявки из системы произойдет позже назначенного срока с задержкой ji t , . Примерная матрица t элементов ji t , для некоторых наборов работ и ресурсов показана на рис. 1. Ресурсы 1 2 3 4 5 6 1 1 3 2 3 4 5 2 2 0 5 6 4 2 3 3 6 1 7 9 1 4 1 3 4 5 1 1 5 1 4 4 1 5 1 Р аб от ы 6 8 1 2 4 3 2 Рис. 1. Исходная матрица t При вычислении ji t , следует учитывать, что на момент планирования PT все заявки имеют одно и то же базовое время начала планирования неза- Динамическое распределение работ по ресурсам неоднородной системе с ограничениями … Системні дослідження та інформаційні технології, 2016, № 3 45 висимо от времени прихода заявок в систему, т.е. считается, что заявки хра- нятся в буфере. Кроме этого, следует учитывать время работы планировщи- ка, т.е. длительность планирования T . Поэтому можно принять  TTT P i in . В соответствии с требованиями режима реального времени значение   n i ji t1 , должно быть больше или равно 0. При невозможности получения варианта распределения с выполнением требования по времени выхода для всех заявок и при включении в распределение значений с ji t , <0 их сумма должна быть минимальной. ПРИВЕДЕНИЕ УСЛОВИЙ ПЛАНИРОВАНИЯ К ЗАДАЧЕ ПОИСКА МАКСИМАЛЬНОГО ПАРОСОЧЕТАНИЯ В указанной выше постановке решение задачи назначения можно свести к задаче поиска максимального паросочетания во взвешенном двудольном графе, которая решается венгерским алгоритмом или алгоритмом направ- ленного поиска. Следует отметить, что поиск варианта распределения вы- полняется для НПВС, для которой решение ищется в разреженной бинарной матрице связности. Эта матрица формируется в соответствии с венгерским алгоритмом и с ее помощью ищется максимальное паросочетание для не- взвешенного двудольного графа. В этом случае можно применить адаптив- ный алгоритм, временная сложность которого зависит от коэффициента за- полнения матрицы связности двудольного графа, а при коэффициенте заполнения менее 0,7 временная сложность не превышает )log( 5,1 nnO [7]. Для поставленной задачи требуется модификация формирования ис- ходных данных и формирование базовой (начальной) области поиска. Рас- смотрим процедуры формирования исходных данных и области поиска на примере решения задачи назначения для шести работ на шести процессор- ных узлах. После обработки временных ограничений и учета производи- тельности каждого узла получим исходную матрицу t (рис. 1). Информация в матрице t указывает только объем работы и относи- тельное время ее выполнения с учетом производительности вычислитель- ных узлов. Однако из-за неоднородности НПВС приходится учитывать ин- дивидуальные характеристики каждого вычислительного узла, связанные с возможностью выполнения работы. Это наличие оперативной памяти доста- точного объема, исходных данных в узле, программ, соответствующих заяв- ке на работу и т.п. Для правильного планирования требуется оценка прин- ципиальной возможности выполнения работ в каждом узле, которая учитывает эти критерии. Для этого необходимо сформировать матрицу Q проверки конфликтности назначений i-й работы в j-й узел:    p x ji xji CQ 1 , , , В.П. Симоненко, А.М. Сергиенко ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 46 где ji xC , — степень выполнения x-го обязательного требования для назначе- ния i-й заявки на j-й ресурс. Для матрицы на рис.1 матрица Q показана на рис. 2. Ввиду того, что обязательное требование следует выполнять без- условно, то элементы jiQ , могут принимать лишь значения 1 или 0. На следующем этапе формирования исходной информации необходимо выполнить фильтрацию элементов матрицы t в соответствии со значения- ми элементов матрицы Q . В результате получаем новую матрицу t , пока- занную на рис. 3, где символом  обозначены варианты невозможных на- значений: Для формирования плана распределения работ по процессорным узлам в соответствии с требованиями венгерского алгоритма и ограничениями, накладываемыми постановкой задачи, требуется сформировать начальную или исходную зону поиска. Для этого выполним следующие действия. Необходимо учесть, что положительные значения элементов матрицы t соответствуют назначениям, которые безусловно включаются в решение, так как любое назначение, соответствующее 0,  ji t , не противоречит усло- виям временных ограничений. Поэтому всем положительным элементам присваиваем значения 0, а у отрицательных элементов поменяем знак на положительный. В результате получаем новую матрицу t  (рис. 4). ПОИСК ПЛАНА ПО ВЕНГЕРСКОМУ АЛГОРИТМУ Дальнейшие действия по формированию исходной области и собственно поиск паросочетания выполняются в соответствии с венгерским алгорит- мом. Для этого из каждого элемента столбца матрицы t  вычитается наи- меньший элемент этого столбца: ji t i ji t ji t ,,, min    .  Рис. 2. Матрица проверки конф- ликтных назначений jiQ , Рис. 3. Матрица t после фильт- рации конфликтных назначений t 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 0 0 1 0 1 1 3   4  2 1 1 1 0 1 1 2 –2 0 –5  –4 –2 3 0 1 0 1 1 0 3  6  7 9  4 0 1 1 1 1 0 4  –3 –4 –5 –1  5 1 0 0 1 1 1 5 –1   1 –5 –1 6 1 1 0 1 1 1 6 8 1  4 3 2 Динамическое распределение работ по ресурсам неоднородной системе с ограничениями … Системні дослідження та інформаційні технології, 2016, № 3 47 Из каждого элемента строки полученной матрицы t  вычитается наи- меньший элемент этой строки: ji t i ji t ji t ,,, minˆ    . В результате в каждой строке и каждом столбце матрицы t̂ имеем ну- левой элемент (рис. 5). Для поиска решения из исходной матрицы поиска t̂ выделяем нуле- вые элементы и формируем исходную матрицу для поиска максимального паросочетания (ОPR) (рис. 6). Для получения решения используем один из алгоритмов поиска максимального паросочетания в невзвешенном двудоль- ном графе. Для него необходимо инвертировать значения элементов матри- цы ОPR, т.е. заменить в ней все нулевые элементы на единичные и наобо- рот. Получаем матрицу поиска решения PR (рис. 7): 1 2 3 4 5 6 1 2 3 4 5 6 1 0 0   0  1 0 0   0  2 2 0 5  4 2 2 2 0 2  4 2 3  0  0 0  3  0  0 0  4  3 4 5 1  4  2 0 4 0  5 1   0 5 1 5 1   0 5 1 6 0 0  0 0 0 6 0 0  0 0 0 Рис. 4. Промежуточная матрица t  Рис. 5. Исходная матрица поиска t̂ 1 2 3 4 5 6 1 2 3 4 5 6 1 0 0 1 1 0 1 1 1 1 0 0 1 1 2 1 0 1 1 1 1 2 0 1 0 0 0 0 3 1 0 1 0 0 1 3 0 1 0 1 1 0 4 1 1 0 1 0 1 4 0 0 1 0 1 0 5 1 1 1 0 1 1 5 0 0 0 1 0 0 6 0 0 1 0 0 0 6 1 1 0 1 1 1 Рис. 6. Матрица области поиска реше- ния (ОPR) Рис. 7. Матрица поиска решения (PR) Для рассматриваемого примера, следуя венгерскому алгоритму, найде- но максимальное паросочетание (рис. 8). Оно является окончательным пла- ном размещения заявок по узлам, поскольку мощность полученного паросо- четания равна размерности решения задачи, т.е. все заявки распределены. В.П. Симоненко, А.М. Сергиенко ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 48 1 2 3 4 5 6 1 1 1 0 0 1 1 2 0 1 0 0 0 0 3 0 1 0 1 1 0 4 0 0 1 0 1 0 5 0 0 0 1 0 0 6 1 1 0 1 1 1 Рис. 8. План распределения В том случае, если совершенное паросочетание не получено, т.е. когда мощность полученного паросочетания меньше размерности матрицы PR, необходимо найти новую область поиска в соответствии с венгерским алго- ритмом. В результате такого выполнения определяются элементы ji t , , ко- торые могут быть дополнительно включены в зону поиска. Рассмотрим пример, иллюстрирующий формирование новой зоны по- иска, в соответствии с венгерским алгоритмом. В качестве исходной примем матрицу, представленную на рис. 9. Y1 Y2 Y3 Y4 Y5 Y6 X1 3 0  2 0 2 X2 5 2 8 0  4 X3 2  0 3 4 3 X4 8 0 7  3 1 X5 0 1 0  0 0 X6   1 3 0 6 Рис. 9. Исходная матрица, не имеющая прямого решения Для данного примера имеем предварительное распределение, отмечен- ное выделенными нулями. Поиск максимального паросочетания по этой матрице не дает решения. Для дальнейшего поиска решения определяется минимальная опора. Минимальной опорой называют минимальное множе- ство строк или столбцов, т.е. линий, содержащих все нулевые элементы. Для этого выполняют алгоритм [8]: 1. Отмечают в каждой строке, в которой есть решение, все нули. 2. Помечают знаком «+» каждую строку, не содержащую отмеченных нулей. 3. Помечают знаком «+» каждый столбец, содержащий отмеченные ну- ли, в какой-либо из строк, помеченных знаком «+». 4. Помечают знаком «+» каждую строку, содержащую отмеченный нуль в каком-либо столбце, помеченном знаком «+». 5. Действия повторяют до тех пор, пока возможно помечать знаком «+» новые строки и столбцы. Динамическое распределение работ по ресурсам неоднородной системе с ограничениями … Системні дослідження та інформаційні технології, 2016, № 3 49 Выделим минимальную опору. Для этого отметим все непомеченные знаком «+» строки (в примере — 532 ,, XXX ) и все помеченные столбцы (в примере — 52 , YY ). В результате, получаем помеченную матрицу (рис. 10). Y1 Y 2 Y 3 Y 4 Y5 Y6 X1 3 0  2 0 2 + X 2 5 2 8 0  4 X 3 2  0 3 4 3 X 4 8 0 7  3 1 + X 5 0 1 0  0 0 X 6   1 3 0 6 + + + Рис.10. Матрица с выделенной минимальной опорой Затем формируется новая зона поиска. Для этого рассматривается под- матрица, образованная элементами, через которые не проходят отмеченные на рис. 10 линии и берется наименьший элемент этой подматрицы, в приме- ре — равный 1. Этот элемент вычитается из элементов всех тех столбцов, через которые не проходят отмеченные линии, и затем он прибавляется к элементам всех тех строк, через которые проходят выделенные линии. В данном примере единица вычитается из элементов столбцов 6431 ,,, YYYY и прибавляется затем к элементам строк 532 ,, XXX . В результате этих действий изменяется количество нулей, определяющих зону поиска реше- ния. После этого снова выполняется попытка найти максимальное паросо- четание. Вышеописанные действия повторяются до тех пор, пока не будет получено максимальное паросочетание. Результирующая матрица показана на рис. 11. Y 1 Y 2 Y 3 Y 4 Y 5 Y 6 X1 2 0  1 0 1 X2 5 3 8 0  4 X3 2  0 3 5 3 X4 7 0 6  3 0 X5 0 2 0  1 0 X6   0 3 0 5 Рис. 11. Матрица окончательного решения В.П. Симоненко, А.М. Сергиенко ISSN 1681–6048 System Research & Information Technologies, 2016, № 3 50 Таким образом, условия задачи динамического планирования с ограни- чениями реального времени для НПВС формально преобразуются в матрицу поиска, которая обрабатывается с использованием алгоритма поиска макси- мального паросочетания с быстрым получением эффективного плана. ЗАКЛЮЧЕНИЕ Предложенный в работе метод преобразования исходной информации при- водит решение задачи распределения заявок по вычислительным ресурсам с ограничениями реального времени к классической задаче комбинаторной математики — поиска максимального паросочетания во взвешенном дву- дольном графе. Быстрое решение такой задачи позволяет выполнять дина- мическое планирование в современных параллельных ВС. Дальнейшее ус- корение составления расписания можно получить, применив алгоритм адаптивного планирования, предложенный в работе [7], который основан на улучшении алгоритма поиска максимального паросочетания во взвешенном двудольном графе. ЛИТЕРАТУРА 1. Papadimitriou C.H. Combinatory optimization, algorithm and complexity / C.H. Pa- padimitriou, K. Steiglitz. — New Jersey: Prentice-Hall. —1982. — 496 p. 2. 2. Berge C. Theorie des graphes et ses application / C. Berge. — Paris: Dunod. — 1958. — 275 p. 3. Зыль С. Операционная система реального времени QNX: от теории к практике. — 2-изд. / С. Зыль. — СПб.: БХВ — Петербург, 2004. — 192 с. ISBN 5-94157-486-Х 4. Зыль С. QNX Momentics. Основы применения / С. Зыль. — СПб.: БХВ- Петербург, 2004. — 256 с.: ил. ISBN 5-94157-430-4 5. Кёртен Р. Введение в QNX/Neutrino 2 / Р. Кёртен . — СПб.: Петрополис. — 2001. — 512 C. ISBN 5-94656-025-9. 6. Ослэндер Д.М. Управляющие программы для механических систем: Объектно- ориентированное проектирование систем реального времени / Д.М. Ослэн- дер, Дж.Р. Риджли, Дж.Д. Рингенберг. — М.: Бином. Лаборатория зна- ний. — 2004. — 416 c. ISBN 5-94774-097-4. 7. Симоненко В.П. Улучшенный алгоритм назначения для планировщиков зада- ний в неоднородных распределенных вычислительных системах / В.П. Симоненко, А.М. Сергиенко, А.В. Симоненко // Системні дослідження та інформаційні технології. — 2016. — № 2. — С. 20–35. 8. Kauffman A. Introduction to a la combinatorque en vue des applications / A. Kauff- man. — Paris: Dunod, 1968. Поступила 25.05.2016

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

Репозитарії

Схожі ресурси