Содержание к диссертации
Введение
1. Анализ существующих подходов к планированию задач в системах жесткого реального времени и моделей распределения вычислительных ресурсов 15
1.1. Обзор подходов к планированию задач в системах жесткого реального времени 15
1.1.1. Классификация алгоритмов планирования задач реального времени 17
1.1.2. Классическая теория частотно-монотоннного анализа 22
1.1.3. Развитие идей частотно-монотонного анализа для мультипроцессорных систем реального времени 27
1.2. Модели распределения вычислительных ресурсов при статическом мультипроцессорном планировании 30
1.2.1. Традиционные модели распределения вычислительных ресурсов 30
1.2.2. Современные модели распределения вычислительных ресурсов 35
Выводы по главе 1 42
2. Методика повышения эффективности использования вычислительных ресурсов при статическом планировании мультипроцессорных систем жесткого реального времени 45
2.1. Постановка задачи повышения эффективности планирования 45
2.1.1. Уточнение классификации объектов планирования 46
2.1.2. Анализ применимости уточненной классификации для решения поставленной задачи 53
2.2. Системные основы оценки эффективности планирования 57
2.2.1. Подходы к моделированию задач реального времени 57
2.2.2. Методы анализа выполнимости планирования в мультипроцессорных системах жесткого реального времени 63
2.3. Разработка методов распределения вычислительных ресурсов мультипроцессорных систем реального времени 69
2.3.1. Поиск методов эффективного статического мультипроцессорного планирования 69
2.3.2. Разработка методов анализа выполнимости объектов планирования 75
Выводы по главе 2 87
3. Исследование особенностей применения разработанной методики в реальных системах жесткого реального времени 89
3.1. Уточнение методов анализа выполнимости объектов планирования для применения в реальных системах 89
3.1.1. Влияние переключений исполнительных ресурсов на оценку эффективности планирования 89
3.1.2. Взаимодействие объектов планирования 99
3.1.3. Устранение допущений в формировании моделирующих объектов при неравномерном распределении принудительных вытеснений 105
3.2. Анализ характеристик предложенных методов 112
Выводы по главе 3 118
4. Практическое использование разработанной методики 120
4.1. Решение производственных задач с использованием методики повышения эффективности распределения вычислительных ресурсов 120
4.2. Внедрение результатов диссертационного исследования 130
Выводы по главе 4 132
Заключение 133
Список использованных источников 135
Приложение 1. Свидетельство о государственной регистрации программы для ЭВМ 148
Приложение 2. Акты о внедрении 149
- Классическая теория частотно-монотоннного анализа
- Методы анализа выполнимости планирования в мультипроцессорных системах жесткого реального времени
- Анализ характеристик предложенных методов
- Решение производственных задач с использованием методики повышения эффективности распределения вычислительных ресурсов
Введение к работе
Актуальность исследования. Своевременность реакции на внешние события является достаточно важной характеристикой любого современного программно-аппаратного комплекса. Особое значение данная характеристика приобретает в тех отраслях промышленности, где задержка реакции вычислительных систем может привести к человеческим жертвам, либо же вылиться в значительные экономические издержки. К таким сферам человеческой деятельности можно отнести: медицину, атомную энергетику, нефтяную и горнодобывающую промышленность, оборонно-промышленный комплекс, авиационную и ракетно-космическую промышленность. При данных обстоятельствах становится актуальным применение для решения задач управления подобными техническими средствами систем реального времени (под СРВ здесь и далее подразумеваются исключительно системы жесткого реального времени), характеризующихся повышенными требованиями к своевременности обработки возникающих событий и предсказуемости поведения.
В настоящее время активное развитие получила тенденция использования мультипроцессорной и многоядерной вычислительной техники при проектировании систем управления (СУ). Не являются исключением в данном смысле и СРВ. Появление возможности параллельного исполнения математического обеспечения обусловило начало постепенного перехода от однозадачных и многозадачных СРВ с единственным исполнительным ресурсом (ИР) к системам, поддерживающим распараллеливание потока команд. При этом особую актуальность приобрел вопрос эффективного распределения вычислительных ресурсов между задачами (объектами планирования) на всех исполнительных ресурсах.
Необходимо отдельно отметить, что в качестве исполнительных ресурсов могут рассматриваться как отдельные микропроцессорные средства, так и выделенные узлы ЛВС, занимающиеся выполнением единого математического обеспечения системы реального времени. Для краткости технические средства, имеющие в своем распоряжении несколько исполнительных ресурсов, выполняющих задачи реального времени, предлагается именовать мультипроцессорами.
К моменту проведения данного диссертационного исследования сформировалось три основных подхода к решению задачи планирования в мультипроцессорных СРВ:
-
Динамическое планирования (планирование с использованием динамических приоритетов задач) - подход, характеризующийся проведением основных мероприятий планирования непосредственно во время эксплуатирования системы посредством изменения приоритетов.
-
Раздельное статическое планирование - подход характеризуется закреплением групп задач за различными исполнительными ресурсами с фиксированными приоритетами, заданными на этапе проектирования.
3. Глобальное статическое планирование - при реализации данного подхода все задачи могут потреблять ресурсы произвольных исполнительных ресурсов, при этом приоритеты являются фиксированными и заданными на этапе проектирования.
Необходимо отметить, что большинство коммерческих операционных систем реального времени (ОС РВ), активно применяющихся в отечественной промышленности, не поддерживают методы динамического планирования средствами ядра ОС. В данном аспекте особое значение имеют исследования, направленные на повышение эффективности именно алгоритмов и методов, относящихся к статическому планированию, что позволит использовать их как при проектировании будущих систем, так и в проектах на завершающих стадиях. Для рассматриваемого круга систем под эффективностью понимается численная характеристика, определяющая совокупное число выполнимых процедурой планирования наборов задач при соблюдении временных характеристик всех задач.
Эффективность распределения вычислительных ресурсов ядром ОС РВ определяет производительность всей технической системы. При этом эффективность механизма планирования напрямую зависит от спектра алгоритмов распределения ресурсов, поддерживаемых операционной системой и, в частности, подсистемой планирования. Поскольку мультипроцессорные СРВ могут выступать в качестве составных элементов систем поддержки принятия решений, эффективность управления вычислительными ресурсами в них оказывает непосредственное влияние на системы более высокого уровня.
Наличие отмеченных обстоятельств делает весьма актуальной задачу научного поиска и обоснования применимости новых методов планирования мультипроцессорных СРВ и разработки методик анализа выполнимости задач.
Объект исследования. Объектом исследования является мультипроцессорная событийно-управляемая система жесткого реального времени.
Предмет исследования. Предметом исследования являются процедуры статического планирования событийно-управляемых мультипроцессорных СРВ.
Целью диссертации является создание методики повышения эффективности решения задачи распределения вычислительных ресурсов в мультипроцессорных событийно-управляемых СРВ посредством процедур статического планирования при изменении принципов потребления исполнительных ресурсов и пересмотра классификации задач.
Задачи исследования:
-
Сравнительный анализ алгоритмического и математического аппарата процедур статического мультипроцессорного планирования СРВ для выявления основных недостатков существующих методов.
-
Определение и обоснование выбора математической модели задачи (объекта планирования) мультипроцессорной СРВ, а также ее уточнение.
-
Разработка алгоритмов мультипроцессорного планирования на основе уточненной математической модели объекта планирования.
-
Разработка методики повышения эффективности распределения вычислительных ресурсов мультипроцессорных СРВ, а также методов оценки выполнимости систем задач, реализующих предложенные процедуры планирования.
-
Устранение допущений в исходной модели задачи реального времени и снижение степени их влияния на оценку эффективности планирования, а также уточнение математического аппарата разработанной методики в соответствии с полученными результатами.
-
Экспериментальное подтверждение реализуемости и эффективности предложенных процедур статического мультипроцессорного планирования.
Методы исследования. Методологическую основу исследования составляют методы системного анализа, математический аппарат теории рядов, теории множеств, теории частотно-монотонного анализа и анализа времени отклика. В работе используются методы математического и компьютерного моделирования.
На защиту выносятся следующие научные результаты:
-
Математическая модель задачи реального времени, учитывающая мультипроцессорный характер технического обеспечения событийно-управляемой СРВ и опирающаяся на классификацию задач по объему потребляемых ресурсов.
-
Процедуры глобального статического планирования, учитывающие взаимное влияние объектов планирования с различной степенью ресурсоемкости в событийно-управляемых мультипроцессорных СРВ.
-
Методика анализа эффективности планирования, позволяющая производить оценку выполнимости математического обеспечения СРВ на этапе проектирования за счет использования информации о разрабатываемой системе.
-
Методы устранения допущений математической модели объекта планирования, способствующие практическому применению предложенных методов планирования в реальных системах.
Научная новизна диссертационной работы заключается в разработке научно-методического инструментария, позволившего осуществить исследование математического и алгоритмического аппарата статического планирования мультипроцессорных событийно-управляемых СРВ, что позволило разработать эффективные процедуры распределения вычислительных ресурсов, в том числе:
-
Предложена математическая модель задачи реального времени, учитывающая мультипроцессорный характер технического обеспечения событийно-управляемой системы жесткого реального времени, опирающаяся на классификацию задач по объему потребляемых ресурсов и взаимное влияние объектов с различной степенью ресурсоемкости.
-
Разработаны процедуры планирования задач, отличающиеся от известных использованием модели объекта планирования, предложенной в настоящей работе. Их исследование позволило установить, что распределение
вычислительных ресурсов между задачами осуществляется эффективнее, нежели любыми известными методами, относящимися к классу глобальных статических процедур.
-
Для разработанных процедур планирования предложена методика анализа эффективности распределения вычислительных ресурсов, которая позволяет производить анализ выполнимости задач на этапе проектирования мультипроцессорных событийно-управляемых СРВ.
-
Разработаны методы устранения допущений, заложенных в предложенной математической модели задачи, что позволяет применять на практике процедуры планирования ее использующие при проектировании СУ, выполненных на основе мультипроцессорных событийно-управляемых СРВ.
Практическая ценность работы. Разработанные методы и процедуры планирования могут применяться для решения задачи эффективного распределения вычислительных ресурсов в событийно-управляемых мультипроцессорных СРВ. На основе результатов диссертационной работы появляется возможность повышения эффективности решения задач автоматизации в широком спектре отраслей промышленности, где обосновано использование мультипроцессорной вычислительной техники, встраиваемых систем, а также систем жесткого реального времени.
Внедрение. Разработанные в рамках настоящего диссертационного исследования алгоритмы и методы планирования и анализа использованы в ОАО «Концерн «НПО «Аврора» в составе математического и программного обеспечения систем управления корабельными техническими средствами. Предложенные способы повышения эффективности распределения ресурсов мультипроцессорных и многоядерных СРВ при обработке поступающего потока запросов на планирование внедрены на предприятии ООО «СВД Встраиваемые Системы» в виде программного модуля диспетчеризации (ПМД). По результатам практического использования ПМД в рамках производственной деятельности предприятия принято решение о включении данного модуля в состав «Защищенной операционной системы реального времени «Нейтрино» (КПД. 10964-01)», соответствующей требованиям к средствам вычислительной техники (СВТ) по 3 классу защиты информации от несанкционированного доступа (НСД), 2 уровню контроля отсутствия не декларированных возможностей (НДВ), а также соответствию реальных и декларированных возможностей (РДВ) - сертификат МО РФ №1740 от 20.12.2011.
Достоверность результатов. Достоверность научных положений, результатов и выводов подтверждается корректным использованием математического аппарата, результатами моделирования и экспериментального исследования методики повышения эффективности статического планирования для мультипроцессорных систем жесткого реального времени, обсуждением полученных результатов на научных конференциях, а также результатами использования представленных положений и их внедрения.
Апробация работы. Основные положения и результаты диссертационной работы докладывались на 6 международных и
общероссийских научных конференциях, в том числе на: II общероссийской
молодежной научно-технической конференции «Молодежь, Техника, Космос»
(Санкт-Петербург, 2010 г.); III общероссийской молодежной научно-
технической конференции «Молодежь, Техника, Космос» (Санкт-Петербург,
2011 г.); I международной научно-практической конференции «Применение
инновационных технологий в научных исследованиях» (Курск, 2010 г.); II
международной научно-практической конференции «Применение
инновационных технологий в научных исследованиях» (Курск, 2011 г.); VIII
международной научно-технической конференции «Современные
инструментальные системы, информационные технологии и инновации» (Курск, 2010 г.); IX всероссийской научно-практической конференции «Молодежь и современные информационные технологии» (Томск, 2011 г.).
Публикации. По теме диссертационного исследования опубликовано 14 работ, включая 5 статей в журналах, включенных в перечень изданий, рекомендованных ВАК, 7 работ в материалах международных и общероссийских научных конференций, а также 1 свидетельство о государственной регистрации программы для ЭВМ.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы, включающего 118 наименований. Основная часть работы содержит 131 страницу, 20 рисунков и 15 таблиц.
Классическая теория частотно-монотоннного анализа
Как было отмечено ранее, привлекательность методов статического планирования для разработчиков СРВ обуславливается простотой их реализации. Для удовлетворения требования предсказуемости в рамках планирования со статическими приоритетами в простейшем случае рассматриваются периодические независимые задачи. В классическом труде C.L. Liu и J.W. Layland [91] предлагаются алгоритм планирования RMS и математический аппарат анализа выполнимости системы задач при его использовании. Данная методика получила название частотно-монотонного анализа (ЧМА) [6]. Эффективность применения ЧМА в СРВ с единственным ИР признана [22; 71] такими организациями как USA Department of Defence, NASA и Boening [5]. При рассмотрении множества задач г. =Jr1;...;rwi, где п - число задач, Liu и Layland задались следующими ограничениями [110]:
1. Экземпляры задач т- порождаются с периодом (Г,).
2. Экземпляры задач т. порождаются единовременно в начале периода и имеют крайнее срок завершения (предельное время исполнения — Д-), равный периоду.
3. Все задачи являются независимыми, борьба за ресурсы отсутствует, исключением является ресурс времени доступа к ИР.
4. В любом периоде задачи имеют фиксированное время, требуемое им для выполнения С{, характеризующее время выполнения задачи в худшем случае. Оценка предельного времени выполнения задач является предметом WCET-анализа [114] и в данной работе обсуждаться не будет.
5. Задачи не могут добровольно приостанавливать свое выполнение -передавать исполнительный ресурс следующей задаче.
6. Все задачи являются вытесняемыми.
7. Накладные расходы на перепланирование и переключение ИР полагаются равными нулю.
8. Планирование производится в системе с одним единственным ИР. Данное ограничение оказывает наиболее существенное влияние на применимость ЧМА в мультипроцессорных СРВ.
Процедура планирования RMS назначает приоритеты задачам по принципу: чем меньше период задачи, тем выше ее приоритет. Liu и Layland доказали, что RMS планирование с соблюдением всех крайних сроков осуществимо если выполняется условие [91]
Применение на практике выражения (1.2) при достаточно больших количествах задач становится весьма затруднительным. В данном аспекте Е. Bini, С. Giorgio и С. Buttazzo [64] предложили метод анализа выполнимости, обладающий меньшим пессимизмом, чем (1.1), но менее трудоемкий, чем (1.2). Авторы метода называют его тестом гиперболической границы (от Hyperbolic Bound Test) [64]. Суть метода сводится к следующему: набор из п-периодических задач выполним в рамках процедуры RMS, если выполняется условие: mw,+l 2. В данной работе также предложен метод учета апериодических задач и разделяемых ресурсов в гиперболическом тесте. Для этого вводится задача T„=(C„,T„,D„] опрашивающего сервера, выполняющаяся с максимальным приоритетом. Иными словами Г„ mm(T ...;Tn). В труде M. Borger, М. Klein и R.A. Veltre [57] обобщено влияние переключений ИР на планирование в СРВ методом RMS. При переключении исполнительного ресурса с одной задач и на другую происходит две операции с окружением задачи (сохранение данных вытесняемой задачи и восстановление данных возобновляемой задачи). Авторы предложили расширить параметр Сг временем переключения ИР (Q): С. = С + 2СС. В дальнейшем авторы уточнили влияние планировщика на выполнимость приложений. В данном аспекте они дополнили С. временем выполнения планировщика (Д,), а также интервалом времени блокирования задачи т.,
Подводя итоги всего вышесказанного можно сделать вывод о том, что большинство ограничений, которыми задавались Liu и Layland успешно преодолены. В данном аспекте можно утверждать, что методы ЧМА для СРВ с единственным ИР достаточно хорошо изучены. Таким образом, целесообразность научных изысканий в данном направлении может быть обоснована лишь в редких случаях.
Исследованию мультипроцессорных СРВ и, в частности, мультипроцессорному планированиию посвящено большое число работ как отечественных, так и зарубежных исследователей и ученых. Ряд авторов в своих трудах рассматривает проблему мультипроцессорного планирования с позиции адаптации методов теории ЧМА для применения в новых условиях [41; 81; 84]. Актуальность подобных исследований обусловлена в первую очередь широким распространением многопроцессорной вычислительной техники, применяемой в СРВ и во встраиваемых системах, а также необходимостью прогнозирования и контроля хода выполнения задач. Очевидно, требование обеспечения предсказуемости поведения системы и гарантирования своевременности обработки событий не исчезает с увеличением числа вычислительных устройств.
Методы анализа выполнимости планирования в мультипроцессорных системах жесткого реального времени
Вторым немаловажным механизмом, наличие которого требуется для оценки эффективности планирования, является метод анализа выполнимости набора задач, применимый к конкретной дисциплине.
В зависимости от соотношения периодов задач и их крайних сроков завершений системы задач подразделяются на несколько подвидов. В данной работе интересны лишь два из них: крайние сроки завершения, имеющие ограничение сверху (для них справедливо D. T.), и явно заданные (характеризуются равенством параметров D.=T.). Очевидно, второй подвид является частным случаем первого.
Для методов мультипроцессорного планирования, при организации распределения ресурсов между задачами с неявно заданными крайними сроками справедлива оценка предельного значения времени отклика 7?, [29], выраженная в простой формуле
В работе В.В. Никифорова [17] предложен более эффективный метод оценки времени отклика периодических задач при мультипроцессорном планировании со статическими приоритетами и разрешенной миграцией. Он позволяет оценивать выполнимость задач реального времени при использовании любой дисциплины планирования с не изменяющимися во времени приоритетами. В частности, он может применяться для анализа выполнимости задач, использующих процедуры RM-US и SM-US. Методика вычисления времени отклика заключается в следующем:
1. Время отклика задачи г. соответствует Сг для задач с наивысшими приоритетами, число которых не превышает количество имеющихся ИР (при рекомендуемом упорядочивании задач по возрастанию приоритетов индекс таких задач удовлетворяет условию i m).
2. Время отклика остальных і т низкоприоритетных объектов планирования вычисляется посредством следующего рекуррентного выражения
Тем не менее, наряду с простотой реализации, методы (2.5) и (2.6) обладают существенной долей пессимизма в оценке верхней границы времени отклика [65]. В данном аспекте актуальным становится рассмотрение методик, тесно связанных с понятием интерференции задач [50; 51; 98]. Необходимо отметить, что большинство методов ориентировано на анализ спорадических наборов задач, исследование которых является несколько более сложной задачей, нежели исследование периодических. Так, например, метод [98] предназначен для исследования выполнимости мультипроцессорного планирования на спорадических наборах задач. Но, поскольку он применяется исключительно для анализа методов статического планирования (известно, что на статичность метода не влияет принцип поступления задач), полученные результаты справедливы как для спорадической модели порождения задач, так и для периодической, о чем говорят и сами авторы [98].
Важной особенностью (2.7) и (2.8) является некоторая избыточность в расчете интерференции от экземпляров высокоприоритетных задач, которые были порождены до начала отсчета интервала времени (предшествующие задания), соответствующего наихудшему времени отклика и завершились внутри него. Было доказано [98], что максимальное время отклика экземпляра задачи г. (задания) при глобальном мультипроцессорном статическом планировании достигается в том случае, если он порождается в тот момент, когда все m ИР заняты обслуживанием высокоприоритетных задач и на протяжении предшествующего временного промежутка [t-s,t) хотя бы один ИР не был занят выполнением высокоприоритетного объекта планирования. Таким образом, в полном объеме определен необходимый математический аппарат оценки состоятельности предлагаемой методики, направленной на повышение эффективности использования вычислительных ресурсов в мультипроцессорных системах жесткого реального времени. Очевидно, выражение (2.9) применимо в явном виде не только к предложенным процедурам, но также и к базовым методам планирования (RM-US и SM-US), поскольку данные алгоритмы в общепринятом смысле являются статическими дисциплинами. Что же касается подходов, обозначенных в параграфе 2.1, то анализ времени отклика задач для них оказывается не столь очевидным. Исключением является лишь предложение, основанное на назначении максимальных приоритетов объектам #ътипа. Необходимо также отметить, что метод [48; 98] используется не только при оценке эффективности планирования, но также и на этапе проектирования СРВ для исследования выполнимости конкретной системы задач статическими методами. Для этого оценка времени отклика для каждой задачи не должна превышать крайнего срока завершения. В противном случае можно утверждать о невыполнимости исследуемой системы задач в рамках конкретной процедуры планирования.
Анализ характеристик предложенных методов
Предложенные методы решения задачи повышения эффективности использования вычислительных ресурсов при статического планирования мультипроцессорных СРВ сложным образом зависят от входных данных и исходных условий. Тем не менее, проведем базовый анализ таких характеристик, как: сходимость, вычислительная сложность, ресурсоемкость (требования к используемому объему памяти).
Сходимость. Как известно метод оценки времени отклика (2.21) задач, реализующих принудительные периодические вытеснения, а также его уточненная производная (3.8), используют в качестве базиса метод оценки времени отклика для систем глобального мультипроцессорного статического планирования (2.9). Сходимость исходного метода доказана [98]. Отличия же предложенных методов от базового заключаются в способах вычисления NCI CI1 интерференции вида / . (R.) и 1 . (R.), обусловленных выполнением тяжелых задач т є Q. Исходя из особенностей вычисления данных параметров, можно утверждать, что при учете привнесенных изменений они будут ограничены сверху величиной R.-C-+X. Таким образом, предложенные методы также будут наследовать свойство сходимости.
Необходимость введения в методику оценки эффективности планирования дополнительных параметров, характерных для реальных систем, явилось предпосылкой для разработки алгоритма оценки числа вытеснений задач (алгоритм 3.1), адаптированного для применения в мультипроцессорных СРВ. Сходимость данного алгоритма определяется конечностью объема перебора (будет показана в дальнейшем), а также фиксированным значением параметра tя в (3.1).
Вычислительная сложность. При реализации средствами ЭВМ алгоритма 3.1 и метода оценки времени отклика (3.8) возникает необходимость контроля вычислительных ресурсов, необходимых для анализа выполнимости конкретных систем. Одним из таких ресурсов является время PIP, затрачиваемое на выполнение некоторого алгоритма. Второй параметр характеризует необходимое алгоритму количество памяти. Поскольку разработчикам систем реального времени зачастую приходится искать компромисс между этими величинами, приведем оценки, которые можно использовать на практике.
Определим вычислительную сложность алгоритма оценки времени отклика, основанного на (3.8). Очевидно, что, при необходимости оценки R. для всех задач, первым параметром, определяющим трудоемкость алгоритма, является п. Вторым параметром является число ИР, поскольку известно, что для т наиболее приоритетных задач время отклика может быть оценено с вычислительной сложностью, эквивалентной 0(1).
Рассмотрим СРВ, характеризующуюся т = 4;п = 10. Если не учитывать рекуррентный характер (3.8), для каждой задачи т. должны высчитываться интерференции от N более приоритетных задач (положим трудоемкость данной операции равной 0(1)), где N задается в соответствии с таблицей 3.4
Эксперимент 3.5. Проверим экспериментально справедливость данной оценки. Сгенерируем СРВ с конфигурацией га = 20 и « = 2000. Для данного набора задач будет определяться время выполнения алгоритма оценки времени отклика при поочередной фиксации одного из параметров. На рис. 3.10 представлены результаты эксперимента (график 2), а так же их соотношение с теоретическими ожиданиями (график 1). Таким образом, справедливость предложенной асимптотической оценки (3.9) подтверждается экспериментальными данными.
Ресурсоемкость (требования к используемому объему памяти). С точки зрения нагрузки на оперативную память, рекуррентное выражение (3.8), при реализации средствами ЭВМ, не требует использования большого количества ресурсов. Вычисление времени отклика данным способом может осуществляться средствами, как рекурсивных алгоритмов, так и итеративных. Очевидно, рекурсия обладает повышенными требованиями к ресурсу памяти, особенно. Если же исключить из рассмотрения рекурсию, становится очевидным, что объем данных, необходимых алгоритмы пропорционален числу задач п. Иными словами, требуется лишь информация о привлеченных параметрах, которые, в общем случае, относятся к вещественным числам.
Иначе обстоит дело с алгоритмом 3.1. Здесь, чтобы оценить объем задействованной памяти необходимо иметь представление о мощности множества событий перепланирования е .
Решение производственных задач с использованием методики повышения эффективности распределения вычислительных ресурсов
Разработанная методика была использована при решении ряда производственных задач. В рамках настоящей работы нет возможности уделить внимание каждой из них, тем не менее, в данной главе будут представлены результаты практического использования методики в двух случаях.
Первый пример практического использования методики. Рассмотрим некоторую организацию, занимающуюся промышленной автоматизацией. В составе ряда внедренных САУ применяется технология вычислительных кластеров, выполненных на базе мультипроцессорной техники. Некоторые из подобных распределенных вычислительных систем являются также системами жесткого реального времени, что позволяет рассматривать их в качестве объектов, подлежащих анализу в контексте предложенной методики.
На всех узлах распределенного вычислительного комплекса (ВК, вычислительный кластер) выполняется идентичное по конфигурации математического обеспечения. Ввиду одновременного существования в рамках системы реального времени ресурсоемких вычислительных задач с задачами, обращающимися к аппаратуре, для успешного планирования обоих видов объектов изначально избрана дисциплина SM-US [27]. Опытным путем была получена оценка временных параметров задач, входящих в состав ВК, чье выполнение критично по времени и строго ограничено сверху. Вся собранная информация сведена в таблице 4.1 (из соображений создания запаса вычислительных ресурсов все показатели были принудительно завышены на 10%). В таблице не представлены объекты планирования, не относящиеся к задачам, имеющим требования реального времени. Очевидно, принцип назначения приоритетов задачам, а также критерий их классификации, регламентируются исключительно исходной дисциплиной планирования.
Анализ конфигурации задач СРВ позволяет утверждать, что вычислительная нагрузка на один узел ВК (УВК), при учете количества вычислительных ядер ИР равного т=4, не превышает t/ = 65%. Эмпирически было доказано, что накладные расходы на переключение ИР не превышают со«2% от периода наиболее ресурсоемкой задачи реального времени.
В ходе выполнения работ по удовлетворению требований заказчика возникла необходимость добавления дополнительного УВК, имеющего аналогичный функционал и конфигурацию. При этом отмечалось, что вычислительная нагрузка на выделенный узел далека от максимальной, а также то обстоятельство, что существуют задачи, чье выполнение на различных узлах не допустимо. В данном аспекте было предложено рассмотреть возможность распределения объектов планирования по уже имеющимся УВК.
Поставленная задача была успешно решена с применением разработанной в настоящей диссертационной работе методики. Поскольку методика не предлагает эффективных способов распределения объектов планирования по однотипным мультипроцессорным системам, данная задача решалась методом перебора. Уже на начальной стадии анализа применимости методики выяснилось, что при добавлении к математическому обеспечению УВК любой группы взаимосвязанных задач, объект планирования номер 4 в соответствии с (2.4) классифицируется как задача р-типа. Данное обстоятельство позволяет судить о том, что приемлемых конфигураций распределения задач по УВК, позволяющих использовать дисциплину планирования SM-US, не существует.
Тем не менее, применяя к каждому варианту распределения задач дополнительного УВК по другим узлам, предложенные в работе подходы, выраженные в (3.8), (3.2) и (3.5), совместно с разработанной процедурой планирования SMMS-FP, удалось найти приемлемую конфигурацию ВК. В таблице 4.2 представлена найденная конфигурация, позволяющая распределить все объекты планирования дополнительного УВК при сохранении выполнимости задач ВК на всех узлах.
В таблицах 4.3-4.5 представлены результаты анализа выполнимости математического обеспечения ВК посредством SMMS-FP при появлении дополнительного УВК и распределении его задач по остальным узлам вычислительного кластера в соответствии с конфигурацией, соответствующей таблице 4.2.
Можно заметить, что для всех задач величина времени отклика не превышает величины крайнего срока завершения, равного Т. Таким образом, успешность выполнения математического обеспечения СРВ ВК успешно достигается на всех узлах. Таким образом, применение методики повышения эффективности использования вычислительных ресурсов позволило избежать включения в состав комплекса дополнительного узла, что обуславливает достижение экономического эффекта от применения методики, превышающего 25% от стоимости владения аппаратным обеспечением, составляющим ВК комплекса.
Второй пример практического использования методики. В рамках производственной деятельности того же предприятия, что и в первом примере, был разработан бортовой мультипроцессорный вычислить (СРВ) непилотируемого объекта, в задачи которого в одном из режимов функционирования может входить сбор и анализ в реальном времени большого объема данных. Комплекс (будем условно именовать его БВК) может функционировать в одном из трех режимов: пассивный сбор данных (А1), анализ накопленной информации (А2) и активное сопровождение (A3). Большую часть времени БВК проводит в состояниях А1 и А2, последовательно их сменяя. Очевидно, выполняющееся на нем математического обеспечения РВ в этих состояниях занимается либо сбором информации с периферии и ее накоплением, либо ресурсоемким анализом накопленной статистики.
