Назначение и планирование заданий в распределенных системах реального времени тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Скородумов Юрий Михайлович

• Скородумов Юрий Михайлович
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Скородумов Юрий Михайлович

Введение

Глава 1 Анализ современных подходов при назначении и планировании заданий в распределенных системах реального времени

1.1 Проблема организации вычислений в распределенных системах

1.2 Подходы к организации вычислений в распределенной системе с совмещением процедур назначения и планирования заданий

1.3. Планирование при заданном размещении заданий по процессорам распределенной системы

1.4 Выводы

Глава 2 Методы назначения заданий на процессоры и каналы обмена в распределенных системах реального времени

2.1 Назначение заданий в безызбыточных системах

2.2 Назначение заданий в избыточных распределенных системах

2.3 Анализ эффективности алгоритмов назначения заданий

2.4 Выводы

Глава 3 Методы планирование заданий в распределенных системах реального времени

3.1 Постановка проблемы flow shop-планирования

3.2 Специальные классы flow shop-систем

3.3 Планирования заданий с одинаковой последовательностью посещений процессоров

3.4 Планирование заданий с разной последовательностью

посещений процессоров

3.5 Анализ эффективности алгоритмов планирования

3.6 Выводы

Глава 4 Результаты апробации методов назначения и планирования заданий в системе освещения обстановки

4.1 Анализ алгоритмического и программного обеспечения

4.2 Назначение и планирование заданий в вычислительном комплексе ГАК СОО

4.3 Назначение заданий в подсистемах СОО

4.4 Программные средства поддержки и исследования процедур назначения и планирования заданий

4.5 Выводы

Заключение

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

Введение диссертации (часть автореферата) на тему «Назначение и планирование заданий в распределенных системах реального времени»

Введение

Актуальность и степень научной разработанности темы диссертации.

Проблемы проектирования систем реального времени (СРВ) широко обсуждаются в современной научно-технической литературе как в России, так и за рубежом. Этот класс систем достаточно многообразен. К нему относятся системы обработки информации, управления подвижными объектами и технологическими линиями, навигации, связи, теле- и радиовещания. Примерами таких систем могут служить инерциальные и интегрированные навигационные системы, гравиметрические комплексы, системы освещения обстановки подводных аппаратов. Обычно СРВ принято характеризовать рядом определяющих особенностей. Среди них периодичность входного потока данных и, как следствие, периодичность всего вычислительного процесса. При этом период выбирается адекватным скорости протекания анализируемых и управляемых процессов. Кроме того, обычно отмечают необходимость привязки некоторых событий в процессах управления и обработки информации к заданным точкам или интервалам на временной оси посредством назначения директивных сроков или интервалов. Важно отметить, что современные СРВ отличаются высокой сложностью программного обеспечения, что заставляет в большинстве случаев с целью увеличения производительности обращаться к концепции распределенных вычислений. Можно утверждать, что процесс проектирования и эксплуатации СРВ обладает существенными особенностями и подчас ставит перед их разработчиками сложные вопросы, связанные, в частности, с организацией вычислений. Непременными составляющими этой проблемы являются назначение выполняемых заданий на процессоры и их планирование.

Проблемам назначения и планирования заданий в научно-технической литературе посвящено большое число публикаций. Основополагающие результаты были получены в работах Liu C.L., Layland J.W., Coffman E.G., Cottet F., Stankovic J. A., Martello S., Toth P., Keller H., Топоркова В.В., Костенко В.А. и

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

Объектом исследования являются бортовые интегрированные системы обработки информации и управления в реальном времени.

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

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

Для достижения этой цели были решены следующие задачи:

- анализ современных методов назначения и планирования заданий;

- разработка и исследование алгоритма назначения заданий на процессоры распределенных СРВ, в том числе и для избыточных систем;

- разработка и исследование алгоритмов планирования заданий на основе концепции разрешимых классов систем;

- разработка алгоритмов и программных средств для исследования эффективности и поддержки процедур назначения и планирования заданий распределенных СРВ;

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

Методология и методы исследования. Для решения поставленных задач использовались методы теории графов, дискретной математики, теории алгоритмов и теории надежности.

Научная новизна

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

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

3. Предложен комбинированный подход к назначению и планированию заданий для распределенных СРВ с разной последовательностью посещений процессоров, отличающийся от известных низкой вычислительной сложностью, а также использованием комбинации алгоритма сетевого упорядочивания и РКС-алгоритма.

Практическая значимость

1. Предложенные алгоритмы назначения и планирования заданий позволяют сокращать затраты на поиск эффективных вариантов реализации СРВ.

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

3. Предложенные решения были применены при разработке в АО «Концерн «ЦНИИ «Электроприбор» систем навигации и освещения обстановки подводных аппаратов.

Основные положения, выносимые на защиту:

- Алгоритм для назначения заданий на процессоры распределенных вычислительных СРВ, в том числе избыточных.

- Метод планирования заданий для распределенных СРВ с одинаковой последовательностью посещений для двух критериев.

- Комбинированный подход к назначению и планированию заданий для распределенной вычислительной СРВ с разной последовательностью посещений на основе алгоритма сетевого упорядочивания и РКС-алгоритма.

Степень достоверности и апробация работы. Достоверность научных и практических результатов подтверждается использованием корректных математических приемов, сопоставлением аналитических результатов и данных, полученных в ходе математического моделирования и экспериментальных исследований, критическим обсуждением результатов работы на научно-технических конференциях. Материалы диссертации докладывались и обсуждались на 6-й и 8-й Всероссийских мультиконференциях по проблемам управления (Дивноморское, 2013; 2015), на XIX Международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации» (Алушта, 2013), на XXVШ и XXIX конференциях памяти выдающегося конструктора гироскопических приборов Н.Н. Острякова (Санкт-Петербург, 2012; 2014), на XII Всероссийском совещании по проблемам управления (Москва, 2014), на Всероссийской конференции по проблемам управления в технических системах (Санкт-Петербург, 2015). Практическая апробация результатов диссертационной работы осуществлена при

разработке цифровых вычислителей в АО "Концерн "ЦНИИ "Электроприбор" в части алгоритмических и программных средств для поддержки процедур назначения и планирования заданий и исследования эффективности полученных решений.

Публикации. По материалам диссертации опубликовано 19 работ, из них 4 публикации в ведущих рецензируемых изданиях, рекомендуемых ВАК Минобразования и науки РФ, 11 докладов и 4 реферата докладов на всероссийских и международных конференциях.

Структура и объем диссертации. Диссертация состоит из введения, четырех разделов, заключения и списка использованных источников, содержащего 97 наименований. Объем работы составляет 124 страницы, включая 35 рисунков и 16 таблиц.

Глава 1

Анализ современных подходов при назначении и планировании

заданий в распределенных системах реального времени

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

1.1 Проблема организации вычислений в распределенных системах

Обычно под организацией вычислений понимается распределение ресурсов, таких как процессоры, каналы обмена, память и т.п. между исполняемыми задачами (программами) [34, 35]. В зависимости от постановки проблемы все множество задач может быть разбито на независимые группы, задачи в которых связанны отношением предшествования. Такие группы задач далее будем называть заданиями. При организации вычислений необходимо решить две основные проблемы, а именно, проблемы назначения и планирования. Содержание процедуры назначения состоит в соотнесении с каждым процессором некоторого списка решаемых на нем задач. Она предшествует любым вычислениям в многопроцессорных системах. Как правило, к современным вычислительным системам предъявляются высокие требования по производительности, и вследствие этого в них используются распределенные (многомашинные) или многопроцессорные архитектуры. Под планированием понимается поиск наилучшей упорядоченности для выполняемых заданий,

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

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

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

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

Вопросам организации вычислений в научно-технической литературе уделяется большое внимание [5-7, 12, 46, 49, 53, 55, 57, 72]. Обычно проблемы назначения и планирования обсуждаются в оптимизационной постановке, а методы их решения принадлежат разделу дискретной математики и являются предметом комбинаторной оптимизации [57]. Рассмотрим различные известные постановки проблемы. При этом воспользуемся универсальной формальной записью проблемы, предложенной в [63] :

о/р/у, (1.1)

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

Р / т-ггвв (¿р) / ^ /Ьтах (2.1),

где Р обозначает однотипность процессоров в системе, тгее - графы заданий имеют древовидную структуру или же представлены графом общего вида (¿р), запись ^ / Ьтах - задает директивные сроки заданий и устанавливает

критерием оптимизации минимум максимального отклонения от них. Другой пример:

P / in-tree (sp) / Cmax , (3.1)

где Cmax устанавливает критерием оптимизации минимум времени выполнения плана (всех заданий в системе).

Примеры, представленные выражениями (2.1) и (3.1), соответствуют рассматриваемым далее в теоретическом и прикладном плане проблемам.

1.2 Подходы к организации вычислений в распределенной системе с совмещением процедур назначения и планирования заданий

Известно, что проблемы (2.1) и (3.1) относятся к классу NP-трудных [46, 57], что означает экспоненциальный рост вычислительной сложности решения при линейном росте размерности задачи. В теории вычислительной сложности известны два направления, связанных с решением NP-трудных комбинаторных задач, нацеленные на поиск оптимальных и приближенных решений соответственно. В рамках первого направления используются в общем случае переборные алгоритмы, характеризующиеся экспоненциальной вычислительной сложностью. Второму направлению соответствуют приближенные алгоритмы, позволяющие сравнительно быстро получать удовлетворительные решения, не являющиеся оптимальными. Их иногда называют конструктивными и оптимизационными эвристиками. Применение приближенных алгоритмов оправдано при необходимости быстрой оценки выполнимости вычислений в системе, разработке прототипов вычислительных систем, а также для получения опорных решений при поиске оптимальных результатов [57].

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

по заданному критерию. Для устранения недостатков, связанных со большим временем выполнения, существуют различные параллельные варианты этого алгоритма, а так же ряд других алгоритмов. Среди последних наибольшее распространение получил алгоритм ветвей и границ (Branch and Bound Algorithm) [54, 71, 80, 81].

В основе алгоритма ветвей и границ лежат две процедуры: ветвление и ограничение. Процедура ветвления заключается в разбиении всего множества решений на подмножества и их дальнейшее изучение. Подмножество решений либо отбраковывается, когда оно не содержит решения лучше известного, либо происходит его дальнейшее разбиение на подмножества до тех пор, пока не будет найдено оптимальное решение. Процесс ветвления удобно представлять в виде дерева поиска, где корень - все множество решений, а другие вершины представляют подмножества, на которые было разделено исходное множество. Листья такого дерева обычно отображают конкретные решения (варианты перестановок заданий в плане или их распределений по процессорам), а предшествующие вершины - частичные решения. Пример такого дерева для решения проблемы заданий планирования приведен на рисунке 1.1, где вершины отмечены сформированными к данному шагу перестановками заданий (где т - i-е

задание, i = 1, m). Таким образом, поиск по дереву приводит к решению проблемы. Очевидно, что число вершин в дереве поиска растет экспоненциально с «глубиной» дерева поиска (т.е. размером задачи). Следовательно, необходима вторая часть алгоритма - ограничение, т.е. отсев направлений поиска (подмножеств решений), которые не приведут к решению, лучшему, чем известно на данном этапе поиска. Решения сравниваются между собой по величине используемого критерия, величина которого для некоторой подгруппы решений определяется ее нижней границей. Исходное решение для сравнения может быть найдено с помощью некоторого эвристического алгоритма до запуска алгоритма ветвей и границ, а все последующие будут сформированы уже самим алгоритмом

(если новое решение лучше старого, то оно принимается в качестве эталонного). Алгоритм ветвей и границ дает оптимальное решение за довольно быстрое время, но потребуется экспоненциальное время для доказательства, что это решение оптимально наверняка. Известны также параллельные версии этого алгоритма [54].

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

Приближенные алгоритмы. Класс приближенных алгоритмов можно условно разделить на две группы: оптимизационные и конструктивные эвристики. Первая объединяет в себе методы, основанные на различных стратегиях поиска около-оптимального решения, т.н. алгоритмы ненаправленного поиска (АННП). Во многих АННП используется поиск с набором случайных параметров, таким

образом, эти алгоритмы дают корректное решение с некоторой вероятностью. В отличие от метода ветвей и границ, АННП не исследуют всю область возможных решений, поэтому обычно используются два критерия прекращения работы алгоритма. Первый отражает ситуацию, когда удовлетворяющее решение найдено, второй - если достигнут предел вычислений (время решения или количество итераций). Обычно определяющие поведение АННП параметры подстраиваются от запуска к запуску алгоритма. Среди наиболее часто встречаемых в литературе оптимизационных эвристик можно выделить метод имитации отжига, поиск со списком запретов (taboo search) и генетические алгоритмы.

Метод имитации отжига [5, 48, 70, 90]. Метод основан на случайных перестановках заданий в плане или распределении задач по процессорам, которые изменяют оценку качества получаемого результата (в литературе используется термин «энергия», что связано с особенностями физического процесса, лежащего в основе полхода). Перестановки, приводящие к снижению оценки, допустимы, в то время как перестановки, увеличивающие ее на величину АЕ, возможны с вероятностью, убывающей экспоненциально с ростом приращения АЕ. Перестановки, снижающие качество решения на величину Ау принимаются с вероятностью е'АуУ\ где t - эквивалент температуры (для реального физического процесса). Таким образом, вероятность принятия таких перестановок тем выше, чем больше величина параметра t, т.е. при «остывании» принятие худшего результата менее вероятно. Процедура варьирования параметра t называется cooling schedule, она отличается в зависимости от реализации алгоритмов и, как правило, включает в себя все остальные шаги алгоритма. Для каждого значения этого параметра после определенного количества приемлемых перестановок достигается «термодинамическое равновесие», т.е. состояние локального оптимума.

В [51, 55, 76, 94] метод имитации отжига применялся для систем с жесткими директивными сроками, а пропуск директивного срока отражался как штраф для оценки оптимальности результата. В работах [76], [94] применяли метод для решения задачи назначения, в [51] и [55] - для совместного решения проблем назначения и планирования. В литературе встречаются разные критерии оптимальности для оценки результатов. Так в [76] и [94] используется критерий минимума затрат на информационные обмены, в [51] - минимума общего времени выполнения расписания, а в [55] - критерий минимального джиттера.

Генетические алгоритмы [62, 74]. В основе этого подхода лежит процесс эволюции генома. Различные решения задачи оптимизации обычно кодируются строками по аналогии с кодированием хромосом. Популяции индивидов ставится в соответствие набор решений. Обычно начальная популяция (исходный набор решений) генерируется случайным образом. Генетические операции (селекция, скрещивание и мутация) направлены на улучшение популяции с точки зрения качества решений. Операция селекции отбирает лучшие решения для следующей популяции. Операция скрещивания производит новые решения (потомки), случайным образом комбинируя части строк, кодирующих исходные решения (родители). Фрагменты строки, кодирующей оптимальное решение, находятся косвенно (не направленно), т.к. операция селекции отбирает лучшие результаты. Операция мутации изменяет случайным образом некоторые решения, чтобы расширить область поиска и избежать остановки в точке локального оптимума.

В работах [42], [64] и [86] генетические алгоритмы применялись для назначения задач в системах реального времени, при этом варианты составления хромосом различались. В [42] и [64] в хромосоме закодирован список задач на каждом из процессоров (и/или расписание для каждого из процессоров), при этом генам ставятся в соответствие задачи. В [86] каждое решение (итоговое назначение), включающее все необходимые данные, закодировано в одну хромосому. Такой подход более компактен и позволяет легче вычислить точку

скрещивания, но затраты на кодирование и декодирование существенно возрастают.

Поиск со списком запретов (taboo search) [60, 61, 71, 82]. Этот подход применительно к задаче минимизации некоторого критерия использует стратегию движения в сторону наибольшего убывания или наименьшего увеличения его значения. Поиск начинается из некоторого начального решения (одного из нескольких возможных, выбранного случайно) и анализирует соседние с ним решения (варианты перестановок). Наилучшее из этих решений выбирается в качестве следующего опорного и т.д. Такая стратегия может привести к циклическому посещению одних и тех же пар решений, если процесс остановится в окрестностях локального оптимума. Для разрешения этой ситуации используется список запретов, в который вносят такие решения. В ряде случаев ограничения могут быть излишне строгими, особенно при сложной топологии пространства поиска, в таком случае выход из ситуации обеспечивает так называемая функция стремления (aspiration function). Эта функция определяет, насколько хорошим должно быть очередное решение, чтобы оно могло быть принято вне зависимости от списка запрещенных решений. Основными настраиваемыми параметрами метода являются длинна списка запретов, способ задания окрестности опорного решения и функция стремления.

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

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

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

Многие известные конструктивные эвристики основаны на методе «планирование по списку» (List Processing, List scheduling), [39, 50, 67, 79, 83, 85, 87]. В основе этих алгоритмов лежит один или несколько упорядоченных списков задач. Различные алгоритмы планирования по списку в основном различаются функцией назначения приоритетов для построения этих списков. Например, в алгоритме EDF [73] приоритеты задач определяются их директивными сроками, таким образом, задача с самым ранним директивным сроком будет иметь самый высокий приоритет. Однако в ситуации многокритериального планирования такие алгоритмы обычно испытывают сложности с удовлетворением разным критериям. Другим недостатком таких алгоритмов является риск формирования неудовлетворительного решения с точки зрения критерия оптимальности. Для повышения качества результата работы алгоритмов применяется подход с возвратом на предыдущие шаги алгоритма с целью применения других стратегий формирования списка. Это приводит к существенному увеличению времени выполнения такого алгоритма, но получение более качественного результата не гарантируется [39, 40, 83].

Список литературы диссертационного исследования кандидат наук Скородумов Юрий Михайлович, 2016 год

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

1. Балашов, В.В. Система автоматического построения циклограммы обменов по шине с централизованным управлением / В.В. Балашов [и др.] // Труды второй Всероссийской научной конференции «Методы и средства обработки информации» / Под ред. Л.Н. Королева. - М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2005.

2. Гергель В.П. Теория и практика параллельных вычислений. М.: Интернет университет информационных технологий; БИНОМ. Лаборатория знаний, 2007. - 423 с.

3. Грузликов, А. М. Оптимизация и диагностирование распределенных вычислительных систем гидроакустических комплексов: дис. ... канд. техн. наук : 05.13.01 : защищена 30.04.15. - Санкт-Петербург, 2015. - 165 с.

4. Дмитриев С.П. Информационная надежность, контроль и диагностика навигационных систем / С.П.Дмитриев, Н.В.Колесов,

A.В.Осипов. - СПб.: ГНЦ РФ - ЦНИИ «Электроприбор», 2003.- 207 с. ISBN 5-900780-46-5.

5. Зорин, Д. А. Алгоритм синтеза архитектуры вычислительной системы реального времени с учетом требований к надежности. / Д. А. Зорин,

B. А. Костенко // Известия Российской академии наук.. Теория и системы управления. - 2012. - № 2. - с. 124-131.

6. Каляев, И.А. Децентрализованные системы компьютерного управления / И.А. Каляев, Э.В. Мельник - Ростов н/Д: Изд. ЮНЦ РАН. -2011. - 196 с.

7. Каляев, И.А. Реконфигурируемые информационно-управляющие системы / И.А. Каляев, Э.В. Мельник // Материалы пленарного заседания 5-й Российской мультиконференции по проблемам управления. - СПб.: ГНЦ РФ ОАО «Концерн «ЦНИИ «Электроприбор». - 2012.

8. Колесов, Н.В. Планирование вычислительного процесса в иерархических системах / Колесов Н.В., Толмачева М.В. // Известия Российской академии наук. Теория и системы управления. - 2007. - № 2. -С.5 -12.

9. Колесов, Н.В. Планирование вычислительного процесса в многопроцессорных системах при заданных для решаемых задач директивных сроках / Н.В. Колесов, М.В. Толмачева, П.В. Юхта // Вестник компьютерных и информационных технологий. - 2009. - № 6. - С.31 - 37.

10. Колесов, Н.В. Планирование вычислительного процесса в распределенных системах реального времени с неопределенными длительностями решения задач / Н.В. Колесов, М.В. Толмачева, П.В. Юхта // Известия Российской академии наук. Теория и системы управления. - 2012. - № 4. - С.5 - 12.

11. Колесов, Н.В. Системы реального времени. Планирование, анализ, диагностирование. / Н.В. Колесов, М.В. Толмачева, П.В. Юхта // СПб.: ОАО "Концерн "ЦНИИ "Электроприбор", 2014. - 180 с.

12. Конвей, Р.В. Теория расписаний. / Р. В. Конвей, В. Л. Максвелл, Л. В. Миллер - М.: Наука. - 1975. - 320 с.

13. Кормен, Т.Х., Алгоритмы: построение и анализ. / Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л.: Пер. с англ. - М.: Издательский дом «Вильямс», 2010. - 1296 с.

14. Костенко, В.А. Алгоритм построения расписаний обменов по шине с централизованным управлением и исследование его эффективности / В.А. Костенко, Е.С. Гурьянов // Программирование. - 2005. - № 6. - С.59-62.

15. Кофман, А. Сетевые методы планирования и их применение / А. Кофман, Г. Дебазей. - М.: Прогресс. - 1968. - 182 с.

16. Скородумов, Ю.М. Алгоритм независимого назначения иерархических заданий на процессоры в системе реального времени / Н.В.

Колесов, Ю.М. Скородумов, М.В. Толмачева, П.В. Юхта // Вестник компьютерных и информационных технологий. - 2013. - № 6. - С.28 - 33.

17. Скородумов, Ю.М. Алгоритмы формирования вычислительного процесса в распределенных системах реального времени // Материалы XVII конференции молодых ученых «Навигация и управление движением». -2015. - С.201 - 204.

18. Скородумов, Ю.М. Выбор аппаратной платформы для реализации спец-вычислителя гидроакустического комплекса / Ю.М. Скородумов, П.В. Юхта, А.В. Шафранюк // Материалы XIV конференции молодых ученых «Навигация и управление движением». - 2012. - С.357 - 362.

19. Скородумов, Ю.М. Выполнение заданий в вычислительных системах реального времени // Материалы XV конференции молодых ученых «Навигация и управление движением». - 2013. - С.297 - 302.

20. Скородумов, Ю.М. Графовый подход к назначению заданий в распределенных системах реального времени / А.М. Грузликов, Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева // Известия Российской академии наук. Теория и системы управления. - 2014. - № 4. - С.28 - 38.

21. Скородумов, Ю.М. Назначение заданий при распределенных вычислениях / А.М. Грузликов, Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева // Материалы 7-й Всероссийской мультиконференции по проблемам управления, Дивноморское. - 2013. - Т.4. - С.34 - 37.

22. Скородумов, Ю.М. Использование динамических моделей при мониторинге параллельных вычислений / А.М. Грузликов, Ю.М. Скородумов // Материалы XVI конференции молодых ученых «Навигация и управление движением». - 2014. - С.378 - 383.

23. Скородумов, Ю.М. Комбинированный алгоритм планирования заданий в распределенных системах реального времени / Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева // Материалы 8-й Всероссийской

мультиконференции по проблемам управления, Дивноморское. - 2015. - Т.4. - С.28 - 31.

24. Скородумов, Ю.М. Назначение заданий на процессоры в системах реального времени / Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева, П.В. Юхта // XXVIII Конференция памяти Н.Н. Острякова. - 2012. - С.57.

25. Скородумов, Ю.М. Жадные алгоритмы планирования распределенных вычислений / Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева // XXIX Конференция памяти Н.Н.Острякова. - 2014. - С.360 -366.

26. Скородумов, Ю.М. Нестационарные модели в задачах диагностирования вычислительных систем реального времени / А.М. Грузликов, Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева // Известия Российской академии наук. Теория и системы управления. - 2016. - № 6. -С.78 - 83.

27. Скородумов, Ю.М. Нестационарные модели в задачах диагностирования вычислительных систем / А.М. Грузликов, Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева // XII Всероссийское совещание по проблемам управления, М.: Институт проблем управления им. В.А. Трапезникова РАН. - 2014. - С.7270 - 7281.

28. Скородумов, Ю.М. Организация вычислений в распределенных системах реального времени / А.М. Грузликов, Ю.М. Скородумов, М.В. Толмачева // XIX Международный научно-технический семинар «Современные технологии в задачах управления, автоматики и обработки информации», Алушта. - 2013. - С.210 - 211.

29. Скородумов, Ю.М. Планирование вычислений в морских навигационных комплексах / Ю.М. Скородумов, П.В. Юхта // Материалы XXXI отраслевой научно-технической конференции молодых специалистов

«Морское подводное оружие. Морские подводные роботы - вопросы проектирования, конструирования и технологий» . - 2012. - С.71 - 76.

30. Скородумов, Ю.М. Планирование вычислений в распределенных системах реального времени / Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева, П.В. Юхта // XXVIII Конференция памяти Н.Н. Острякова. -2012. - С.58.

31. Скородумов, Ю.М. Планирование распределенных вычислений с минимизацией общего времени выполнения / А.М. Грузликов, Ю.М. Скородумов // Материалы XVI конференции молодых ученых «Навигация и управление движением». - 2014. - С.371 - 377.

32. Скородумов, Ю.М. Смешанное планирование заданий в распределенных системах реального времени / Н.В. Колесов, Ю.М. Скородумов, А.М. Грузликов, М.В. Толмачева // Вестник компьютерных и информационных технологий. - 2016. - № 5. - С.29 - 34.

33. Скородумов, Ю.М. Flow shop-планирование вычислений в распределенных системах реального времени / А.М. Грузликов, Н.В. Колесов, Ю.М. Скородумов, М.В. Толмачева // Материалы Всероссийской конференции по проблемам управления в технических системах, Санкт-Петербрг. - 2015. - С.34 - 38.

34. Столингс, В. Операционные системы. - М.: Изд. Дом «Вильямс», 2002. - 844 с.

35. Таненбаум, Э. Современные операционные системы. - 2-е изд. -СПБ.: Питер, 2002. - 1040 с.

36. Топорков, В.В. Модели распределенных вычислений. - М.: Физматлит, 2004. - 316 с.

37. Топорков, В.В. Совместное планирование и назначение процессов как метод оптимизации архитектурных решений вычислительных систем // Автоматика и телемеханика. - 2001. - № 12. - С. 107-116.

38. Юхта, П. В. Планирование вычислительного процесса в навигационных комплексах : дис. канд. техн. наук : 05.13.11 : защищена 30.04.10. - Санкт-Петербург, 2010. - 151 с.

39. Adan, J. M. Meeting hard real-time constraints using a client-server model of interaction. / J. M. Adan, M. F. Magalhaes, K. Ramamritham // Proceedings of the 7th Euromicro Workshop on Real-time Systems. - 1995. - pp. 286-293.

40. Altenbernd, P. The Slack Method: A New Method for Static Allocation of Hard Real-Time Tasks. / P. Altenbernd, H. Hansson // Real-Time Systems. Kluwer Academic Publishers, Boston. Manufactured in The Netherlands.- 1998. -vol. 15. - pp. 103-130.

41. Baccelli, F. Synchronization and Linearity, web edition. / F. Baccelli [et al.] // John Wiley & Sons, Inc. - 2001. - 501 p.

42. Baccouche, L. Efficient static allocation of real-time tasks using genetic algorithms. / Baccouche, L. // Imag Institute, Laboratoire d'Automatique, Génie Informatique et Signal. - 1995.

43. Beauvais, J.-P. Heuristic for Scheduling Periodic Complex Real-Time Tasks in a Distributed System / J.-P. Beauvais, A. Deplanche // In DCCS'95, 13th IFAC Workshop. - 1995. - pp. 55-60.

44. Beauvais, J.-P. Etude d'algorithmes de placement de taches temps reel complexes dans un systeme reparti / Beauvais, J.-P // PhD thesis, ECN, Universite de Nantes. - 1996.

45. Bocewicz, G. Declarative approach to cyclic steady state space refinement: periodic process scheduling / G. Bocewicz, Z. A. Banaszak // Int. J. Adv. Manuf. Technol. - 2013. - #67. - pp. 137-155.

46. Brucker, P. Scheduling Algorithms./ Brucker P. // Springer. - 2007. -371 p.

47. Campbell, H. G. A Heuristic Algorithm for The n-job, m-machine Scheduling Problem. / H. G. Campbell [et al.] // Management Science. - 1970. -№. 16. - pp. 630-637.

48. Cerny, V. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. // V. Cerny / J. Optimization Theory and Applications. - 1985. - №45. - pp. 41-51,

49. Cheng, A.M.K. Real-Time Systems. Scheduling, Analysis, and Verification / Cheng A.M.K. // John Wiley & Sons, Inc., Hoboken, New Jersey. -2002. - 266 p.

50. Cheng, B.C. Least-space-time-first scheduling algorithm: A policy for complex real-time tasks in multiple processor systems. / B.C. Cheng, A.D. Stoyenko, T.J. Marlowe // Proceedings of the WRTP'94. - 1994.

51. Coli, M., A new method for optimisation of allocation and scheduling in real-time applications. / M. Coli, P. Palazzari // Proceedings of the 7th Euromicro Workshop on Real-time Systems. - 1995. - pp. 262-269.

52. Computer and Job-Shop Scheduling Theory. / E.G. Coffman Jr., editor. // Wiley, New York. - 1976. - 312 p.

53. Cottet F., Scheduling in Real-Time Systems / F. Cottet, J. Kaiser, Z. Mammeri // John Wiley & Sons Ltd. - 2002. -283 p.

54. Crainic, T.G. Parallel branch-and-bound algorithms. / T.G. Crainic, B. Le Cun, C. Roucairol; In E.-G. Talbi, editor // Parallel Combinatorial Optimization, Wiley, Hoboken NJ. - 2006. - pp. 1-28.

55. DiNatale, M. Applicability of simulated annealing methods to real-time scheduling and jitter control / M. DiNatale, J. A. Stankovic // Proceedings of the IEEE Real-Time Systems Symposium. - 1995. - pp. 190-199.

56. Dong, X. An improved NEH-based heuristic for the permutation flowshop problem. / X. Dong, H. H. Ping Chen // Computers and Operations Research. - 2008. - №35(12). - pp. 3962-3968.

57. Drozdowski, M. Scheduling for Parallel Processing / Drozdowski M. // Springer, 2009. - 386 p.

58. Framinan, J.M., Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or owtime in the static permutation flowshop sequencing problem. / J.M. Framinan, R. Leisten, C. Rajendran // International Journal of Production Research. - 2003. - №41, Issue 1. - pp. 121-148.

59. Gao, J. A NEH-based heuristic algorithm for distributed permutation flowshop scheduling problems / J. Gao, R. Chen // Scientific Research and Essays. 2011.- Vol. 6(14). - pp. 3094-3100.

60. Glover, F. Tabu Search. / F. Glover, M. Laguna. // Kluwer Academic, Boston. - 1997.

61. Glover, F. Tabu-search part I. / F. Glover // ORSA Journal on Computing. - 1989. - № 1(3). - pp. 190-206.

62. Goldberg, D.E. Genetic Algorithms in Search, Optimization and Machine Learning. / D.E. Goldberg // Addison Wesley, Reading, MA. - 1989. - 432 p.

63. Graham, R.L. Optimization and approximation in deterministic sequencing and scheduling: A survey. / R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnoy Kan // Annals of Discrete Mathematics - 1979. - № 5. -pp. 287-326.

64. Greenwood, G. An evolutionary strategy for scheduling periodic tasks in real-time systems. / G. Greenwood, C. Lang, S. Hurley // Applied Decision Technologies. - 1995. - pp. 171 -188.

65. Hitchcock, R. B. Timing verification and the timing analysis program. / R. B. Hitchcock // Proceedings of the 19th Design Automation Conference. -1982. - pp. 594-603.

66. Johnson, S.M. Optimal two-and-three-stage production schedules with set-up times included. / S.M. Johnson // Naval Research Logistic Quaterly. - 1954. - vol. 1. - pp. 61- 68,

67. Jonsson, J. The impact of application and architecture properties on realtime multiprocessor scheduling. / Jonsson, J. // Dissertation, Department of Computer Engineering, Chalmers University of Technology, Goteborg, Sweden. -1997.

68. Kalczynski, P. J. An improved NEH heuristic to minimize makespan in permutation flow shops. / P. J. Kalczynski, J. Kamburowski // Computers and Operations Research. - 2008. - №35(9). - pp. 3001-3008.

69. Kim, S. J. A general approach to mapping of parallel computation upon multiprocessor architectures. / S. J. Kim, J. C. Browne // Proceedings of the International Conference on Parallel Processing (ICPP'88), The Pennsylvania State University, University Park, PA, USA, August 1988). Pennsylvania State University Press. - 1988. - Vol. 3. - P. 1-8.

70. Kirkpatrick, S. Optimization by simulated annealing. / S. Kirkpatrick, C.D. Gelatt Jr., M.P. Vecchi. // Science. - 1983. - № 220(4598). - pp. 671-680.

71. Lenstra, J.K. Sequencing by Enumerative Methods. / J.K. Lenstra // Number 69 in Mathematical Centre Tracts. Matematisch Centrum, Amsterdam, 1977. - pp. 252-268.

72. Liu, J.W.S. Real-Time Systems / J.W.S. Liu // Prentice Hall, Englewood Cliffs, NJ. - 2000. - 600p.

73. Liu, C.L. Scheduling algorithms for multiprogramming in a hard realtime environment / C.L. Liu, J.W. Layland // J. ACM. - 1973.- vol. 20, № 1. - pp. 40 -61,

74. Michalewicz, Z. Genetic Algorithms, Data Structures, Evolution Programs. / Z. Michalewicz // Springer, Berlin, Heidelberg. - 1996. - 388 p.

75. Nawaz, M. A Heuristic Algorithm for the m-machine, n-job Flow Shop Sequencing Problem / M. Nawaz [et al.] // International Journal of Management Science. -1983. - №. 11. - pp. 91-95

76. Nicholson, M. Allocating and scheduling hard real-time tasks on a point-to-point distributed system / M. Nicholson // Proceedings of Workshop on Parallel and Distributed Real-Time Systems. - 1993.

77. Nowicki, E. A Fast Tabu Search Algorithm for the Permutation Flow-Shop Problem. / E. Nowicki [et al.] // Eur. J. Oper. Res. - 1996. - №. 91. - pp. 160-175.

78. Ogbu, F. A. The Application of the Simulated Annealing Algorithm to the Solution of the n/m/c Subscript Max Flowshop Problem. / F.A. Ogbu [et al.] // Computers Ops Res. - 1990. - №. 17. - pp. 243-253.

79. Palis, M. A. Task clustering and scheduling for distributed memory parallel architectures. / Palis, M. A., Liou, J.-C., & Wei, D. S. L. // IEEE Transactions on Parallel and Distributed Systems. - 1996. - vol. 7(1).- pp. 46-55.

80. Papadimitriou, C.H. Combinatorial Optimization: Algorithms and Complexity / C.H. Papadimitriou, K. Steiglitz // Prentice-Hall, Englewood Cliffs, NJ, 1982. - 528 p.

81. Papadimitriou, C.H. Computational Complexity. / C.H. Papadimitriou // Addison Wesley, Reading, MA, 1994.

82. Porto, S.C.S. A tabu search approach to task scheduling on heterogeneous processors under precedence constraints / S.C.S. Porto, C.R. Celso // Report PUCRioInf-MCC03/93, Pontificia Universidade Catolica do Rio de Janeiro. - 1993.

83. Ramamritham, K. Allocation and scheduling of complex periodic tasks. / K. Ramamritham // Proceedings of the 10th International Conference on Distributed Computing Systems. - 1990. - pp. 108-115.

84. Reeves, C. R. Genetic Algorithms, Path Relinking, and Flow Shop Problem. / C. R. Reeves [et al.] // Evolutionary Computation. - 1998. - №. 6.- pp. 45-60.

85. Ronngren, S. Static multiprocessor scheduling of periodic real-time tasks with precedence constraints and communication costs. / S. Ronngren, B.A. Shirazi // Proceedings of the 28th Annual Hawaii International Conference on System Sciences. - 1995. - pp. 143-152.

86. Sandnes, F. E. A hybrid genetic algorithm applied to automatic parallel controller code generation. / F. E. Sandnes // Proceedings of the 8th Euromicro Workshop on Real-time Systems. - 1996. - pp. 70-75.

87. Santos, J. A heuristic approach to the multitask-multiprocessor assignment problem using the empty-slots method and rate monotonic scheduling. / J. Santos, E. Ferro, J. Orozco, R. Cayssials //Journal of Real-Time Systems. -1997. -vol. 13(2). - pp. 167-199.

88. Sarkar, V. Partitioning and Scheduling Programs for Execution on Multiprocessors / V. Sarkar // The MIT Press, Cambridge, Massachusetts. - 1989. - p. 215.

89. Semanco, P. Hybrid GA-based Improvement Heuristic with Makespan Criterion for Flow-Shop Scheduling Problems. / P. Semanco [et al.] // Communications in Computer and Information Science. - 2011. - №. 220.- pp. 11-18.

90. Simulated Annealing: Theory and Applications. / P.J.M. Laarhoven and E.H.L. Aarts, editors. // D. Reidel, Dordrecht, The Netherlands. - 1987. - 195 p.

91. Skorodumov, Yu.M. Efficiency research of task allocation algorithms in distributed computing systems / A.M. Gruzlikov and Yu.M. Skorodumov // Proceedings of the international conference of young scientists «Automation and control», St. Peterburg, Russia, 21-22 november. - 2013. - p.46.

92. Stankovic, John A. Deadline Scheduling for Real-Time Systems / John A.Stankovic, M. Spuri, K. Ramemritham, G.C. Buttazzo. // Kluwer Academic Publishers, London, 1998. - 273 p.

93. Taillard, E. Benchmarks for basic scheduling problems. European Journal of Operational Research. - 1993. - №64(2). - pp. 278-285.

94. Tindell, K. Allocating real-time tasks (An NP-hard problem made easy). / K. Tindell, A. Burns, A. Wellings // Journal of Real-Time Systems. -1992. - № 4(2) - pp. 145-165.

95. Wang Ji-Bo, Zun-Quan Xia. Scheduling jobs under decreasing linear deterioration. // Information Processing Letters. - 2005. - vol. 94(2). - pp. 63-69.

96. Wang Ji-Bo. Flow shop scheduling problems with decreasing linear deterioration under dominant machines. // Computers and Operations Research. -2007. - vol. 37(7). - pp. 2043-2058.