Методика повышения эффективности статического планирования для мультипроцессорных систем жесткого реального времени тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Докучаев, Андрей Николаевич

• Докучаев, Андрей Николаевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Докучаев, Андрей Николаевич

ОГЛАВЛЕНИЕ

Основные термины и условные сокращения

Введение

1. Анализ существующих подходов к планированию задач в системах жесткого реального времени и моделей распределения вычислительных ресурсов

1.1. Обзор подходов к планированию задач в системах жесткого реального времени

1.1.1. Классификация алгоритмов планирования задач реального времени

1.1.2. Классическая теория частотно-монотоннного анализа

1.1.3. Развитие идей частотно-монотонного анализа для мультипроцессорных систем реального времени

1.2. Модели распределения вычислительных ресурсов при статическом мультипроцессорном планировании

1.2.1. Традиционные модели распределения вычислительных ресурсов

1.2.2. Современные модели распределения вычислительных ресурсов

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

2.1. Постановка задачи повышения эффективности планирования

2.1.1. Уточнение классификации объектов планирования

2.1.2. Анализ применимости уточненной классификации для решения поставленной задачи

2.2. Системные основы оценки эффективности планирования

2.2.1. Подходы к моделированию задач реального времени

2.2.2. Методы анализа выполнимости планирования в мультипроцессорных системах жесткого реального времени

2.3. Разработка методов распределения вычислительных ресурсов мультипроцессорных систем реального времени

2.3.1. Поиск методов эффективного статического мультипроцессорного планирования

2.3.2. Разработка методов анализа выполнимости объектов планирования

Выводы по главе 2

3. Исследование особенностей применения разработанной методики в реальных системах жесткого реального времени

3.1. Уточнение методов анализа выполнимости объектов планирования для применения в реальных системах

3.1.1. Влияние переключений исполнительных ресурсов на оценку эффективности планирования

3.1.2. Взаимодействие объектов планирования

3.1.3. Устранение допущений в формировании моделирующих объектов при неравномерном распределении принудительных вытеснений

3.2. Анализ характеристик предложенных методов

Выводы по главе 3

4. Практическое использование разработанной методики

4.1. Решение производственных задач с использованием методики повышения эффективности распределения вычислительных ресурсов

4.2. Внедрение результатов диссертационного исследования

Выводы по главе 4

Заключение

Список использованных источников

Приложение 1. Свидетельство о государственной регистрации программы для эвм

Приложение 2. Акты о внедрении

\

ОСНОВНЫЕ ТЕРМИНЫ И УСЛОВНЫЕ СОКРАЩЕНИЯ

Deadline - крайний (предельный) срок завершения исполнения задачи.

EDF - алгоритм планирования «ближайший предельный срок первым».

Global Scheduling - глобальное мультипроцессорное планирование.

IEC - международная электротехническая комиссия.

ISO - международная организация по стандартизации.

Laxity - запас времени.

Laxity-driven scheduling - планирование, основанное на вычислении запаса времени (преимущественно с динамическими приоритетами).

LLF - алгоритм планирования «задача с наименьшим запасом времени первая».

Partitioned Scheduling - раздельное мультипроцессорное планирование.

POSIX (от англ. Portable Operating System Interface for Unix) — стандарт, регламентирующий переносимые интерфейсы ОС семейства Unix.

RM-US, SM-US, RMZL, FPZL - алгоритмы глобального мультипроцессорного планирования.

RMA (от англ. Rate-Monotonic Analysis) - частотно-монотонный анализ.

RMFF, RMNF, RMBF, FFDUF, RM-FFDU, RMST, RMGT, RMFF-WC, RMNF-WC, RMBF-WC, RMDP - алгоритмы раздельного мультипроцессорного планирования.

RMS - алгоритм частотно-монотонного планирования.

RTA (от англ. Response Time Analysis) - анализ времени <}тклика.

Время выполнения задачи в худшем случае (от англ. Worst-Case Execution Time) - характеристика задачи, определяющая требуемое ей количество ресурсов исполнительного ресурса в отсутствии вытеснений.

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

Задача - объект планирования; задание - экземпляр задачи.

Интерференция задачи - характеристика степени влияния высокоприоритетных задач на задачи с меньшим приоритетом.

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

Критический сценарий - наихудший сценарий выполнения высокоприоритетных задач и возникновения событий перепланирования.

Миграция - способность задачи потреблять ресурсы различных ИР.

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

Независимость задач - отсутствие взаимодействия и борьбы за ресурсы (за исключением исполнительного ресурса) между задачами.

Оптимальное планирование - планирование, обеспечивающее выполнимость каждой задачи для любой выполнимой данным классом методов системы задач.

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

Перепланирование - событие переключения исполнительного ресурса.

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

Приоритет - численная характеристика "важности" задачи.

Симметричное мультипроцессирование (от англ. Symmetric Multiprocessing), асимметричное мультипроцессирование (от англ. Asymmetric Multiprocessing) - архитектуры мультипроцессорных ЭВМ.

СРВ - Система Реального Времени.

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

Введение диссертации (часть автореферата) на тему «Методика повышения эффективности статического планирования для мультипроцессорных систем жесткого реального времени»

ВВЕДЕНИЕ

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

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

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

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

К моменту проведения данного диссертационного исследования сформировалось три основных подхода к решению задачи планирования в мультипроцессорных СРВ:

1. динамическое планирование (распределение вычислительных ресурсов с использованием динамических приоритетов задач) - подход, характеризующийся проведением основных мероприятий планирования непосредственно во время эксплуатирования системы посредством изменения приоритетов;

2. раздельное статическое планирование - подход характеризуется разделением всех задач на группы и их закрепление за различными исполнительными ресурсами с назначением фиксированных* приоритетов, заданных еще на этапе проектирования;

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

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

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

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

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

«

Степень научной разработанности проблемы. Теоретические вопросы распределения вычислительных ресурсов в системах жесткого реального времени посредством механизма планирования, а также основы классической теории частотно-монотонного анализа были широко исследованы в работах С. Liu, I. Layland, А. Мок, J.P. Lehman, L. Sha, D.Y. Ding, M. Joseph, P. Pandya, E. Bini, G. Buttazzo, R. Rajkumar, J.P. Lehoczky, M. Borger, M. Klein, R.A. Veltre; J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Andersson, S. Baruah,

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

трудах S.K. Dhall, C.L. Liu, B.B. Никифорова, L. Sha, T. Abdelzaher, К. Arzen, В. Andersson, S. Baruah, J. Jonsson, S. Funk, J. Goossens, R.I. Davis, A. Burns, E. Bini, G.C. Buttazzo, J.P. Lehman, D.Y. Ding, T.P. Baker, M. Cirinei, M. Bertogna, G. Lipari, Nan Guan, M. Stigge, Wang Yi, Ge Yu. В том числе ими были предложены математические модели и методы, позволяющие проводить анализ эффективности алгоритмов планирования СРВ, а также синтезировать модели систем задач реального времени.

В работах В. Andersson, S.A. Baruah, J. Jonsson, T.P. Baker, L. Lundberg произведен анализ применимости глобальных дисциплин планирования в мультипроцессорных СРВ, а также предложены методы анализа выполнимости математического обеспечения подобных систем. Кроме того, в данных работах приводится ряд контраргументов, направленных против применения раздельного статического планирования для решения задачи распределения вычислительных ресурсов в мультипроцессорных СРВ.

Объект исследования. Объектом исследования является мультипроцессорная событийно-управляемая СРВ.

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

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

»

Задачи исследования:

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

2. Выбор и научное обоснование математической модели объекта планирования мультипроцессорной СРВ, а также ее уточнение.

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

4. Разработка методики анализа эффективности планирования мультипроцессорных СРВ.

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

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

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

*

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

СРВ, что позволило разработать более эффективные процедуры распределения вычислительных ресурсов, в том числе:

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

2. Разработаны процедуры планирования, отличающиеся от известных подходов тем, что используют математическую модель задачи, предложенную в настоящем диссертационном исследовании. Исследование данных методов позволило установить, что распределение вычислительных ресурсов между объектами планирования осуществляется эффективнее, нежели любыми известными алгоритмами, относящимися к классу глобальных статических дисциплин.

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

и задач его составляющих, уже на этапе проектирования

*

мультипроцессорных событийно-управляемых СРВ.

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

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

I

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

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

вычислительной техники, распределенных ЛВС (функционирующих

*

посредством сетевых протоколов реального времени), встраиваемых систем, а также систем жесткого реального времени.

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

На защиту выносятся следующие научные результаты диссертационного исследования:

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

»

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

3. Методика анализа эффективности планирования, позволяющая производить анализ выполнимости СРВ на этапе проектирования за счет использования информации о разрабатываемой системе.

4. Методы устранения допущений в математической модели задачи, позволяющие применять на практике предложенные в настоящей диссертационной работе процедуры планирования.

Внедрение. Разработанные в рамках настоящего диссертационного исследования процедуры и методы планирования и анализа использованы в ОАО «Концерн «НПО «Аврора» в составе математического и программного обеспечения систем управления корабельными техническими средствами.

Предложенные способы повышения эффективности распределения ресурсов мультипроцессорных СРВ при обработке поступающего потока запросов на планирование внедрены на предприятии ООО «СВД Встраиваемые Системы» в виде программного модуля диспетчеризации (ПМД). По результатам практического использования ПМД в рамках производственной деятельности предприятия принято решение о включении данного модуля в состав «Защищенной операционной системы реального времени «Нейтрино» (КПД. 10964-01)», соответствующей требованиям к средствам вычислительной техники (СВТ) по 3 классу защиты информации от несанкционированного доступа (НСД), 2 уровню контроля отсутствия не декларированных возможностей (НДВ), а также соответствию реальных и декларированных возможностей (РДВ) - сертификат МО РФ №1740 от 20.12.2011.

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

1. на II общероссийской молодежной научно-технической конференции «Молодежь, Техника, Космос» (г. Санкт-Петербург, БГТУ,

2010 г.);

2. на III общероссийской молодежной научно-технической конференции «Молодежь, Техника, Космос» (г. Санкт-Петербург, БГТУ,

2011 г.);

3. на I международной научно-практической конференции «Применение инновационных технологий в научных исследованиях» (г. Курск, ЮЗГУ, 2010 г.);

4. на II международной научно-практической конференции «Применение инновационных технологий в научных исследованиях» (г. Курск, ЮЗГУ, 2011 г.);

5. на VIII международной научно-технической конференции «Современные инструментальные системы, информационные технологии и инновации» (г. Курск, ЮЗГУ, 2010 г.);

6. на IX всероссийской научно-практической конференции «Молодежь и современные информационные технологии» (г. Томск, ТПУ, 2011 г.).

Публикации. По теме диссертационного исследования опубликовано 14 работ, включая 5 статей в журналах, включенных в перечень ведущих изданий, рекомендованных ВАК и Министерством образования РФ, 7 работ в материалах международных и общероссийских научных конференций, а также 1 свидетельство о государственной регистрации программы для ЭВМ.

Структура и объем диссертации. Диссертация состоиу из введения, четырех глав, заключения и списка литературы, включающего 118 наименований (включая 6 работ автора), а также из двух приложений. Основная часть работы содержит 131 страницу, 20 рисунков и 15 таблиц.

1. АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ К ПЛАНИРОВАНИЮ

ЗАДАЧ В СИСТЕМАХ ЖЕСТКОГО РЕАЛЬНОГО ВРЕМЕНИ И МОДЕЛЕЙ РАСПРЕДЕЛЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ РЕСУРСОВ

1.1. Обзор подходов к планированию задач в системах жесткого

реального времени

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

Выделяют системы жесткого реального времени, и системы мягкого реального времени. Э. Таненбаум в труде «Современные операционные системы» (2010) определяет эти классы систем следующим образом: системы жесткого реального времени характеризуются строгими сроками проведения операций, в отличие от систем мягкого реального времени, в которых это условие носит рекомендательный характер [23]. Нарушение крайнего срока завершения операции в системах жесткого реального времени является критической ошибкой.

Другим предъявляемым к СРВ требованием является обеспечение предсказуемого [1] поведения. Оно включает в себя влияние таких факторов, как: ограничение времени переключения исполнительного ресурса [21] при перепланировании, минимизация задержек, обусловленных вызовами обработчиков прерываний и системными вызовами ядра ОС РВ. Под обеспечением предсказуемого поведения в узком смысле можно понимать наличие математических методов, позволяющих оценить способность системы гарантировать своевременность обработки как внешних, так и внутрисистемных событий даже в случае их наихудшего фазирования. Это наглядно иллюстрируется лаконичным определением СРВ, предложенным в труде М. Тиммермана: "Система реального времени - это такая система, которая предсказуемо реагирует на непредсказуемые внешние события" [113].

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

Одним из основных ресурсов, за обладание которым соревнуются задачи в системе жесткого реального времени (СРВ) является исполнительный ресурс (ИР). В СРВ с несколькими ИР (мультипроцессорных СРВ) проблема распределения вычислительных ресурсов между задачами особенно актуальна, поскольку именно их распределение между исполнительными ресурсами есть обязательное условие параллелизма задач [38]. В данной работе не рассматривается распараллеливание на уровне инструкций (например, архитектура УЫЖ [36]) и параллелизм данных [38]. Процедура эффективного предоставления вычислительных ресурсов задачам носит название планирования (в ряде

источников также можно встретить термин диспетчеризация). На практике задача распределения ресурсов может рассматриваться как с позиции планирования системных потоков (в большинстве ОС РВ [9; 12], поддерживающих многопоточность, они являются единицами планирования), так и с позиции исследования выделенной задачи, например, применяя методы формальной верификации для определения временных параметров выполнения различных фрагментов математического обеспечения [13].

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

1.1.1. Классификация алгоритмов планирования задач реального времени

Существует множество различных видов дисциплин планирования, применяющихся в СРВ. Одна из известных систем классификаций опирается на понятия приоритет и миграция [62].

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

ресурсами. Данное явление именуется миграцией задач при перепланировании, причем под перепланированием понимается процедура переназначения ресурсов ИР. Стоит отметить, что перепланирование в СРВ крайне частое событие, возникающее, например, при изменениях состояний потоков, вызовах ядра операционной системы, возникновении прерываний. Потоки могут находиться в различных состояниях, их количество и число уровней приорита определяется архитектурой СРВ. Так, например, в ОС РВ Fx Works потоки могут принимать 9 состояний при числе уровней приоритета 256 [1], в свою очередь в ОС РВ QNX потоки могут принимать одно из 21 состояния при 256 уровнях приоритета (64 уровня для непривилегированных потоков) [20]. Согласно стандарту POSIX, принятому международной организацией по стандартизации ISO совместно с международной электротехнической комиссией IEC (стандарт принят под названием ISO/IEC 9945) допустимый диапазон приоритетов должен включать не менее 32 различных значений [3].

Авторы классификации [62] выделяют следующие виды дисциплин планирования: по степени допустимой миграции - алгоритмы с полной миграцией, с частичной миграцией и алгоритмы без миграции; по виду управления приоритетами - алгоритмы со статическими приоритетами, алгоритмы с частично-динамическим назначением приоритетов и алгоритмы с динамическим назначением приоритетов.

Полная миграция задач между исполнительными ресурсами (все экземпляры задачи могут свободно мигрировать между ИР) становится возможной при симметричном мультипроцессировании [65; 109] - при использовании архитектуры мультипроцессорных вычислительных систем, позволяющей ИР совместно использовать общую память. Планирование без миграции (все экземпляры задачи выполняются на выделенном ИР) осуществимо в системах с асимметричным мультипроцессированием -архитектурой вычислительных систем, при которой применимы специализированные ИР различных типов. Ограниченная миграция

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

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

Считается, что алгоритм планирования применяет частично-динамическое управление приоритетами при выполнении условия: если в определенный момент времени задача Xi имеет больший приоритет, чем задача Xj, то это соотношение должно сохраняться на всем интервале существования задач [62]. Примером метода, реализующего данный принцип, является EDF планирование [90; 91]. Суть метода заключается в следующем: чем ближе крайний срок завершения задачи, тем выше ее приоритет, причем, перерасчет приоритетов производится динамически на протяжении всего времени функционирования СРВ. Крайним сроком завершения задачи называется момент времени, до наступления которого задача должна выполнить весь объем необходимых ей вычислений. Данный вид планирования сложнее в реализации и привносит дополнительные

расходы, затрачиваемые на детектирование событий перепланирования и повышения приоритетов. Кроме того, в отличие от статического планирования, частично-динамическое и динамическое планирование менее предсказуемо и в меньшей степени поддается контролю [90]. По этой причине в коммерческих ОС РВ его поддержка отсутствует. Известно [68], что алгоритм EDF оптимален для ОС РВ с единственным ИР.

Третьим и наиболее ресурсоемким видом планирования в рассматриваемой системе классификации является планирование с динамическими приоритетами. Он характеризуется отсутствием ограничений на изменение или соотношение приоритетов задач. Одним из ярких представителей данного семейства методов считается LLF [95] (и его развитие LLREF [64]). Динамическое управление приоритетами в общем случае удовлетворяет принципу: приоритет задачи с наименьшим запасом времени динамически повышается в процессе выполнения СРВ. Очевидно, при подобном подходе к решению задачи планирования неизбежно возникает необходимость точного определения моментов времени, когда той или иной задаче необходимо повысить приоритет. Не исключается в данном случае возникновение ситуации, при которой задача, ожидающая повышения приоритета, исчерпывает весь имеющийся запас времени, и несвоевременное принятие решения способно помешать ее успешному завершению. В данном аспекте вопрос своевременного определения событий перепланирования оказывается не на последнем месте для данного класса дисциплин. Также стоит отметить, что эффективность распределения ресурсов данными методами может оказываться выше, чем у методов статического планирования.

Список литературы диссертационного исследования кандидат наук Докучаев, Андрей Николаевич, 2013 год

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Операционные системы реального времени: Препринт 14 [Электронный ресурс] / И.Б. Бурдонов, A.C. Косачев, В.Н. Пономаренко. -Иркутск: Институт системного программирования РАН: сайт, 2006. - Режим доступа: http://www.ispras.ru/ru/preprints/docs/prep_14_2006.pdf. - Загл. с экрана.

2. Вентцель, Е.С. Теория вероятностей и ее инженерные приложения / Е.С. Вентцель, Л.А. Овчаров. - М.: Высшая школа, 2000. - 480 с.

3. Галатенко, В.А. Программирование в стандарте POSIX. Часть 2. Курс лекций. Учебное пособие. / В.А. Галатенко. - М.: Интернет-университет информационных технологий, 2005. - 384 с.

4. Гончар, Д.Р. Алгоритмы управления многопроцессорными системами с неоднородным множеством работ / Д.Р. Гончар, М.Г. Фуругян // Управление большими системами. - 2009. - №. 29 - С. 232-244.

5. Операционные системы реального времени [Электронный ресурс] / Е. Горошко. - Режим доступа: http://www.nsdevice.narod.ru/sprog/qnx/rtos.pdf . - Загл. с экрана.

6. Данилов, М.В. Методы планирования выполнения задач в системах реального времени / М.В. Данилов // Программные продукты и системы. - 2001. - №. 4. - С. 28-35.

7. Докучаев, А.Н. Метод глобальной мультипроцессорной диспетчеризации для встраиваемых систем специального назначения и систем реального времени / А.Н. Докучаев // Горный информационно-аналитический бюллетень (научно-технический журнал). - М.: 2011. - №12. -С. 149-154.

8. Докучаев, А.Н. Задачи ф-типа как средство расширения границ применимости статической диспетчеризации в мультипроцессорных системах реального времени при высокой нагрузке / А.Н. Докучаев //

Системы управления и информационные технологии. - Воронеж, 2011. -№3.2(45).-С. 224-229.

9. Докучаев, А.Н. Защищенная ОС РВ нового поколения: особенности архитектуры и средства защиты информации / А.Н. Докучаев // Автоматизация в промышленности. - Москва, 2012. - №201202. - С. 51-55.

10. Докучаев, А.Н. Особенности диспетчеризации сверхлегких задач в мультипроцессорных вычислительных системах реального времени / А.Н. Докучаев // Информационные технологии. - Москва, 2012. - №2. - С. 14-18.

11. Докучаев, А.Н. К оценке эффективности механизмов диспетчеризации мультипроцессорных систем реального времени с учетом влияния длительных блокировок / А.Н. Докучаев // Программная инженерия.

- Москва, 2012. - №9. - С. 2-7.

12. Докучаев, А.Н. Особенности реализации комплекса средств защиты информации в сертифицированном изделии «Защищенная операционная система реального времени «Нейтрино» (КПДА. 10964-01)» / А.Н. Докучаев, В.А. Третьяков // Системы управления и обработки информации: научн.-техн. сб., ОАО «Концерн «НПО «Аврора». - СПб., 2012.

- №24. - С. 43-46.

13. Зыль, С. Проектирование, разработка и анализ программного обеспечения систем реального времени / С. Зыль. - СПб.: БХВ-Петербург, 2010.-336 с.

14. Кнут, Д. Искусство программирования. Том 1: Основные алгоритмы / Д. Кнут. - Изд. 3-е, перераб. и доп. - М.: Вильяме, 2006. - 720 с.

15. Касперски, К. Техника оптимизации программ. Эффективное использование памяти / К. Касперски. - СПб.: БХВ-Петербург, 2003. - 464 с.

16. Махилев, В. Результаты тестов производительности QNX Neutrino / В. Махилев // Современные технологии автоматизации. - 2012. - № 2. - С. 82-88.

17. Никифоров, В.В. Выполнимость приложений реального времени на многоядерных процессорах /В.В. Никифоров // Труды СПИИРАН. Под общ. ред. P.M. Юсупова. - СПб.: Наука, 2009. - Вып. 8. - С. 255-284.

18. Никифоров, В.В. Планирование заданий в синхронных системах реального времени / В.В. Никифоров // Труды СПИИРАН. - СПб.: СПИИРАН, 2002. - Т. 1, №. 1. - С. 129-144.

19. Никифоров, В.В. Использование многоядерных процессоров для построения систем реального времени /В.В. Никифоров, В.И. Шкиртиль // Известия высших учебных заведений. Приборостроение. - 2007. - Т. 50, №. 10.-С. 26-31.

20. Операционная система реального времени QNX Neutrino 6.3. Системная архитектура. - СПб.: БХВ-Петербург, 2006. - 336 с.

21. Сорокин, С.В. Системы реального времени: операционные системы / С.В. Сорокин // Современные технологии автоматизации. - 1997. -№. 2.-С. 22-31.

22. Сулейманова, A.M. Системы реального времени: учебное пособие / A.M. Сулейманова. - Уфа, Уфимск. гос. авиац. техн. ун-т., 2004. - 292 с.

23. Таненбаум, Э. Современные операционные системы / Э. Таненбаум. - Изд. 3-е, перераб. и доп. - СПб.: Питер, 2010. - 1120 с.

24. Чефранов, А.Г. Проектирование систем реального времени. Учебное пособие / А.Г. Чефранов, Р.В. Троценко. - Таганрог: Изд-во ТРТУ, 2005. - 226 с.

25. Abhilash Thekkilakattil. Reducing the Number of Preemptions in RealTime Systems Scheduling by CPU Frequency Scaling / Abhilash Thekkilakattil, Anju S. Pillai, Radu Dobrin // Proceedings of the 18th International Conference on Real-Time and Network Systems. - France, Toulouse, November, 2010.

26. Andersson, B. Static-priority scheduling on multiprocessors / B. Andersson, S. Baruah, J. Jonsson // Proceedings of 22nd IEEE Real-Time Systems Symposium. - London, 2001. - P. 193-202.

27. Andersson, B. Global Static-Priority Preemptive Multiprocessor Scheduling with Utilization Bound 38% / B. Andersson // Proceedings of the 12th International Conference on Principles of Distributed Systems. - Egypt, Luxor, December, 2008. - P. 73-88.

28. Andersson, B. Fixed-priority preemptive multiprocessor scheduling: To partition or not to partition / B. Andersson, J. Jonsson // Proceedings of the 7th International Conference on Real-Time Systems and Applications. - Washington, December, 2000. - P. 337-346.

29. Andersson, B. Some insights on fixed-priority preemptive non-partitioned multiprocessor scheduling / B. Andersson, J. Jonsson // Proceedings of the 21st IEEE Real-Time Systems Symposium (RTSS'00). - Orlando, Florida, November, 2000. - P. 53-56.

30. Andersson, B. The utilization bounds of partitioned and pfair static-priority scheduling on multiprocessors are 50% / B. Andersson, J. Jonsson // Euromicro Conference on Real-Time Systems. - Portugal, July, 2003. - P. 33-40.

31. Andersson, B. Multiprocessor Scheduling with Few Preemptions / B. Andersson, E. Tovar // Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA '06). -Australia, August, 2006. - P. 322-334.

32. Anderson, J. Early-release fair scheduling / J. Anderson, A. Srinivasan // Proceedings of the 12th Euromicro Conference on Real-Time Systems (RTS 2000). -Sweden, June, 2000. - P. 35-43.

33. Anderson, J. Mixed pfair/erfair scheduling of asynchronous periodic tasks / J. Anderson, A. Srinivasan // Proceedings of the 13th Euromicro Conference on Real-Time Systems (ECRTS '01). - The Netherlands, June, 2001. -P. 76.

34. Anderson, J. Mixed pfair/erfair scheduling of asynchronous periodic tasks / J. Anderson, A. Srinivasan // Journal of Computer and System Sciences. -February, 2004. - Vol. 68(1). - P. 157-204.

35. Anderson, J. Pfair scheduling: Beyond periodic task systems / J. Anderson, A. Srinivasan // Proceedings of the 7th International Conference on Real-Time Systems and Applications (RTCSA '00). - Washington, December, 2000. - P. 297-306.

36. An Introduction To Very-Long Instruction Word (VLIW) Computer Architecture [Electronic resource] // NXP Semiconductors: Web site. - Mode of access: www.nxp.com/acrobat_download2/other/vliw-wp.pdf.

37. Arvind Easwaran. Resource Sharing in Global Fixed-Priority Preemptive Multiprocessor Scheduling / Arvind Easwaran, B. Andersson // Proceedings of the 30th IEEE Real-Time Systems Symposium. - Portugal, Polytech. Inst, of Porto, December, 2009. - P. 377-386.

38. Asanovic, K. The Landscape of Parallel Computing Research: A View from Berkeley / K. Asanovic, R. Bodik., B.C. Catanzaro. // Technical Report No. UCB/EECS-2006-183. - Berkeley, University of California, Dec., 2006. - 56 p.

39. Baker, T.P. An Analysis of Fixed-Priority Schedulability on a Multiprocessor / T.P. Baker // Real-Time Systems. - February, 2006. - Vol. 32(1-2).-P. 49-71.

40. Baker, T.P., Cirinei M., Bertogna M. EDZL scheduling analysis / T.P. Baker // Real-Time Systems. - December, 2008. - Vol. 40(3). - P. 264-289.

41. Baker, T.P. Multiprocessor EDF and deadline monotonic schedulability analysis / T.P. Baker // Proceedings of the 24th IEEE Real-Time Systems Symposium. - Washington, 2003. - P. 120-129.

42. Baruah, S. Proportionate progress: a notion of fairness in resource allocation / S. Baruah, N. Cohen, C.G. Plaxton // Algorithmica. - 1996. - Vol. 15(6).-P. 600-625.

43. Baruah, S.K. Partitioned multiprocessor scheduling of sporadic task systems / S.K. Baruah, N. Fisher // Proceedings of the 26th Real-Time Systems Symposium (RTSS '05). - December, 2005. - P. 321-329.

44. Baruah, S.K. The partitioned dynamic-priority scheduling of sporadic task systems / S.K. Baruah, N. Fisher // Real-Time Systems. - August, 2007. -Vol. 36(3).-P. 199-226.

45. Baruah, S.K. The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems / S.K. Baruah, N. Fisher // IEEE Transactions on Computers. - July, 2006. - Vol. 55(7). - P. 918-923.

46. Baruah, S.K. Fast scheduling of periodic tasks on multiple resources / S.K. Baruah, J. Gehrke, C.G. Plaxton // Proceedings of the 9th International Parallel Processing Symposium (IPPS '95). - April, 1995. - P. 280-288.

47. Baruah, S. Rate-monotonic scheduling on uniform multiprocessors / S. Baruah, J. Goossens // IEEE Trans, on Computers. - July, 2003. - Vol. 52(7). - P. 966-970.

48. Baruah, S. Techniques for Multiprocessor Global Schedulability Analysis / S. Baruah // Proceedings of the 28th IEEE International Real-Time Systems Symposium (RTSS '07). - Arizona, December, 2007. - P. 119-128.

49. Bertogna, M. New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors / M. Bertogna, M. Cirinei, G. Lipari // Proceedings of the 9th International Conference on Principles of Distributed Systems. - Pisa, Italy, Decrmber 2005. - P. 306-321.

50. Bertogna, M. Schedulability analysis of global scheduling algorithms on multiprocessor platforms / M. Bertogna, M. Cirinei, G. Lipari // IEEE Transactions on parallel and distributed systems. - April, 2009. - Vol. 20(4). - P. 553-566.

51. Bertogna, M. Response Time Analysis for global scheduled symmetric multiprocessor platforms / M. Bertogna, M. Cirinei // Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS'07). - Arizona, 2007. - P.149-158.

52. Bertogna, M. Real-Time Scheduling Analysis for Multiprocessor Platforms: PhD Thesis. - Pisa, Scuola Superiore Sant'Anna, 2007.

53. Bini, E. Biasing effects in schedulability measures / E. Bini, G.C. Buttazzo // Proceedings of the 16th Euromicro Conference on Real-Time Systems (ECRTS 2004). - Washington, June, 2004. - P. 196-203.

54. Bini, E. Rate Monotonic Analysis: The Hyperbolic Bound / E. Bini, G.C. Buttazzo, G.M. Buttazzo // IEEE Transactions on Computers. - July, 2003. -Vol. 52(7). - P. 933-942.

55. Bini, E. Measuring the Performance of Schedulability tests / E. Bini, G.C. Buttazzo // Real-Time Systems. - May, 2005. - Vol. 30(1-2). - P. 129-154.

56. Bletsas, K. Notional Processors: An Approach for Multiprocessor Scheduling / K. Bletsas, B. Andersson // Proc. of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium. - California, 2009. - P. 3 -12.

57. Borger, M. Real-Time Software Engineering in Ada: Observations and Guidelines / M. Borger, M. Klein, R.A. Veltre. // Tech. Rep. CMU/SEI-89-TR-22. -Pittsburgh, Software Eng. Inst., September, 1989. - P. 17-22.

58. Borger, M. Implementing Priority Inheritance Algorithms in an Ada Runtime System / M. Borger, R. Rajkumar // Tech.Rep.CMU/SEI-89-TR-15, ESDTR-89-23. - Software Engineering Institute, Carnegie Mellon University, 1989. - 54p.

59. Burchard, A. New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems / A. Burchard, J. Liebeherr, Y. Oh, S.H. Son // IEEE Transactions on Computers. - December, 1995. - Vol. 44(12). - P. 1429-1442.

60. Burns, A. A Round Robbin Scheduling Policy for Ada / A. Burns, M. Gonzalez, A.J. Wellings // International Conference on Reliable Software Technologies, Ada-Europe-2003. - Berlin, Heidelberg, 2003. - P. 334-343.

61. Buttazzo, G. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications / G. Buttazzo. - 3rd edition. - Boston, Ma.: Springer, Real-Time Systems Series, 2011. - P. 536.

62. Carpenter, J. Categorization of real-time multiprocessor scheduling problems and algorithms. In Joseph Y. Leung, editor, Handbook on Scheduling Algorithms, Methods, and Models / J. Carpenter, S. Funk, P. Holman. - Florida, Chapman Hall/CRC, 2004. - P. 30.1-30.19.

63. Chao, Y.H. Schedulability issues for EDZL scheduling on real-time multiprocessor systems / Y.H. Chao, S.S. Lin, K.J. Lin // Information Processing Letters. - August, 2008. - Vol. 107(5). - P. 158-164.

64. Cho, H. An Optimal Real-Time Scheduling Algorithm for Multiprocessors / H. Cho, B. Ravindran, E.D. Jensen. // Proceedings of the 27th Real-Time Systems Symposium (RTSS ^06). -Brazil, 2006. - P. 101-110.

65. Davis, R.I. A Survey of Hard Real-Time Scheduling for Multiprocessor Systems / R.I. Davis, A. Burns // ACM Computing Surveys. - October, 2011. -Vol. 43(4).-Article 35.

66. Davis, R.I. FPZL Schedulability Analysis / R.I. Davis, A. Burns // 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'll). - Chicago, April, 2011. - P. 245-256.

67. Davis, R.I. Priority Assignment for Global Fixed Priority Pre-emptive Scheduling in Multiprocessor Real-Time Systems / R.I. Davis, A. Burns // Proceedings of the 30th IEEE Real-Time Systems Symposium (RTSS'09). -Washington, December, 2009. - P. 398-409.

68. Dertouzos, M.L. Control robotics: the procedural control of physical processors / M.L. Dertouzos // Proceedings of the IFIP Congress (IFIP '74). -Stockholm, Sweden, August, 1974. - P. 807-813.

69. Dhall, S.K. On a Real-Time Scheduling Problem / S.K. Dhall, C.L. Liu // Operating Research. - 1978. - Vol. 26(1). - P. 127-140.

70. Dong-Ik Oh. Utilization Bounds for N-Processor Rate MonotoneScheduling with Static Processor Assignment / Dong-Ik Oh, T.P. Bakker //Real-Time Systems. - September, 1998.-Vol. 15(2).-P. 183-192.

71. Douglass, B.P. Doing Hard Time: Developing Real-Time Systems with UML, Objects, Frameworks and Patterns / B.P. Douglass. - Addison-Wesley, 2007. - 766 p.

72. Dsvari, S. On a Periodic Real Time Task Allocation Problem / S. Dsvari, S.K. Dhall // Proc. of the 19th Annual International Conference on System Sciences.-1986.-P. 133-141.

73. Echague, J. Hard real-time preemptively scheduling with high context switch cost / J. Echague, I. Ripoll, A. Crespo // Proc. of the 7th Euromicro Workshop on Real-Time Systems. - Denmark, 1995. - P. 184-190.

74. Fisher, N. The partitioned scheduling of sporadic tasks according to static priorities /N. Fisher, S.K. Baruah, T.P. Baket // Proc. of the 18th EuroMicro Conference on Real-Time Systems (ECRTS'06). - Washington, 2006. - P. 118-127.

75. Funk, S. LRE-TL: An Optimal Multiprocessor Algorithm for Sporadic Task Sets / S. Funk, V. Nadadur // Proceedings of the International conference on Real-Time Networks and Systems (RTNS). - Paris, France, 2009. - P. 159-168.

76. Funk, S. LRE-TL: An Optimal Multiprocessor Algorithm for Sporadic Task Sets with unconstrained deadlines / S. Funk, V. Nadadur // Real-Time Systems. - December, 2010. - Vol. 46(3). - P. 332-359.

77. Funk, S. On-line scheduling on uniform multiprocessors / S. Funk, J. Goossens, S.K. Baruah // Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01). - Washington, December, 2001. - P. 183-192.

78. Goossens, J. Priority-driven scheduling of periodic task systems on multiprocessors / J. Goossens, S. Funk, S.K. Baruah // Real-Time Systems. -September, 2003. - Vol. 25(2-3). - P. 187-205.

79. Holman, P. Adapting Pfair scheduling for symmetric multiprocessors / P. Holman, J.H. Anderson // Journal of Embedded Computing. - December, 2005. -Vol. 1(4).-P. 543-564.

80. Joseph, M. Finding response times in a real-time system / M. Joseph, P. Pandya // Computer Journal. - October, 1986. - Vol. 29(5). - P. 390-395.

81. Kato, S. Global Rate-Monotonic Scheduling with Priority Promotion / S. Kato, A. Takeda, N. Yamasaki // Tech. Rep. CMU-ECE-TR10-05. - May, 2010.

82. Kato, S. Semi-Partitioned Scheduling of Sporadic Task Systems on Multiprocessors / S. Kato, N. Yamasaki, Y. Ishikawa // Proc. of the 21st Euromicro Conference on Real-Time Systems. -Ireland, July, 2009. - P. 249-258.

83. Kato, S. Portioned EDF-based Scheduling on Multiprocessors / S. Kato, N. Yamasaki // Proc. of the 8th ACM international conference on Embedded software (EMSOFT '08). - Atlanta, 2008. - P. 139-148.

84. Kato, S. Yamasaki N. Portioned Static-Priority Scheduling on Multiprocessors / S. Kato // Proc. of the 22nd IEEE International Parallel and Distributed Processing Symposium. - Miami, Florida, April, 2008. - P. 1-12.

85. Kato, S. Real-Time Scheduling with Task Splitting on Multiprocessors / S. Kato, N. Yamasaki // Proc. of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems. - Korea, 2007. - P. 441-450.

86. Lakshmanan, K. Partitioned Fixed-Priority Preemptive Scheduling for Multi-core Processors / K. Lakshmanan, R. Rajkumar, J. Lehoczky // Proc. of the 21st Euromicro Conference on Real-Time Systems. - Ireland, 2009. - P. 239-248.

87. Lee, S.K. On-line multiprocessor scheduling algorithms for real-time tasks / S.K. Lee // Proc. of the 9th IEEE Region 10's Annual International Conference: Frontiers of Computer Technology. - August, 1994. - P. 607-611.

88. Lehoczky, J.P. The rate monotonic scheduling algorithm: exact characterization and average case behavior / J.P. Lehoczky, L. Sha, D.Y. Ding // Proc. of the 10th IEEE Real-Time Systems Symposium. - California, 1989.-P. 166-171.

89. Leung, J.Y.T. On the complexity of fixed-priority scheduling of periodic, real-time tasks / J.Y.T. Leung, J. Whitehead // Performance Evaluation (Netherlands). - December, 1982. - Vol. 2(4). - P. 237-250.

90. Lipari, G. EDF Scheduling [Electronic resource] / G. Lipari // Home page of Professor Giuseppe Lipari: Web site. - Mode of access: http://retis.sssup.it/~lipari/courses/str07/edf-handout.pdf.

91. Liu, C. Scheduling Algorithms for Multiprogramming in a Hard RealTime Environment / C. Liu, J. Layland // Journal of the ACM. - January, 1973. -Vol. 20(1).-P. 46-61.

92. Lopez, J.M. Worst-case utilization bound for EDF scheduling on realtime multiprocessor systems / J.M. Lopez, M. Garcia, J. Diaz // Proc. of the 12th Euromicro conference on Real-time systems. - June, 2000. - P. 25-33.

93. Lundberg, L. Analyzing Fixed-Priority Global Multiprocessor Scheduling / L. Lundberg // 8th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02). - San Jose, September, 2002. - P. 145-153.

94. Lundberg, L. Slack-based global multiprocessor scheduling of aperiodic tasks in parallel embedded real-time systems / L. Lundberg, H. Lennerstad // Proc. of the 2008 IEEE/ACS International Conference on Computer Systems and Applications (AICCSA '08). - March, 2008. - P. 465-472.

95. Mok, A. Fundamental Design Problems of Distributed Systems for Hard Real-time Environments: PhD thesis. - Massachusetts Institute of Technology, Cambridge, MA, 1983.

96. Nan Guan. Fixed-Priority Multiprocessor Scheduling: Beyond Liu & Layland Utilization Bound / Nan Guan, M. Stigge, Yi. Wang // Proceedings of the Real-Time Systems Symposium, Work In Progress. - 2010.

97. Nan Guan. Fixed-Priority Multiprocessor Scheduling with Liu & Layland's Utilization Bound / Nan Guan, M. Stigge, Yi. Wang // Proc. of the 16th RealTime and Embedded Technology and Applications. - Sweden, 2010. - P. 165-174.

98. Nan Guan. New Response Time Bounds for Fixed Priority Multiprocessor Scheduling / Nan Guan, M. Stigge, Yi. Wang // Proc. of the 30th IEEE Real-Time Systems Symposium. - Washington, 2009. - P. 387-397.

99. Oh, Y. Fixed Priority Scheduling of Periodic Tasks on Multiprocessor Systems / Y. Oh, S.H. Son //. Technical Report CS-95-16. - Dep. of Computer Science, University Of Virginia, 1995. - 35 p.

100. Oh, Y. Preemptive Scheduling of Periodic Tasks on Multiprocessor: Dinamic Algorithms and Their Performance / Y. Oh, S.H. Son // Tech. Rep. CS-93-26. - Dep. of Computer Science,University Of Virginia, 1993. - 24 p.

101. Oh, Y. Tight Performance Bounds of Heuristics for a Real-Time Scheduling Problem / Y. Oh, S.H. Son // Tech. Rep. CS-93-24. - Dep. of Computer Science, University Of Virginia, 1993. - 27 p.

102. Zapata, O.U.P. Analysis of Real-Time Multiprocessor Scheduling Algorithms / O.U.P. Zapata, P. Majia-Alvarez // Proc. of the 24th Real-Time Systems Symposium, Work-in-Progress Session (RTSS'03). -Mexico, 2003.

103. Park, M. Comparison of deadline-based scheduling algorithms for periodic real-time tasks on multiprocessor / M. Park, S. Han, H. Kim // IEICE Transactions on Information Systems. - March, 2005,-Vol. E88-D(3).-P. 658-661.

104. Phillips, C.A. Optimal time-critical scheduling via resource augmentation / C.A. Phillips, C. Stein, E. Torng // Proc. of the ACM Symposium on theory of Computing (STOC'97). - New York, May, 1997. - P. 140-149.

105. QNX6.5 on ARM platform evaluation report [Electronic resource] // Dedicated Systems Portal. - Mode of access: http://download.dedicated-systems.com/4Download/tabid/103/fileshareact/viewfile/Default.aspx?Field=hBLo V4vLh7g|.

106. QNX6.5 on X86 platform evaluation report [Electronic resource] // Dedicated Systems Portal. - Mode of access: http://download.dedicated-systems.com/4Download/tabid/103/fIleshareact/viewfile/Default.aspx?Field=Dt28 9Np+6PA|.

107. QorlQ P4080 Eight-Core Communications Processors [Electronic resource] // Freescale Semiconductor: web site. - Mode of access: http://www.freescale.com/webapp/sps/site/prod_summary .jsp?code=P4080.

108. Rothvoss T. On the computational complexity of periodic scheduling: PhD Thesis. - EPFL (Ecole Polytechnique Federale de Lausanne), Institute of chemical sciences and engineering, 2009.

109. Severance, C. Shared-Memory Multiprocessors - Symmetric Multiprocessing Hardware [Electronic resource] / C. Severance, K. Dowd. - Mode of access: http://cnx.Org/content/m32794/l.3/?format=pdf.

110. Sha, L. Real time scheduling theory: A historical perspective / L. Sha, T. Abdelzaher, K. Arzen et al. // Real-Time Systems. - November-December, 2004. - Vol. 28(2-3). - P. 101-155.

111. Sha, L. Priority Inheritance Protocols: An Approach to Real-Time Synchronization / L. Sha, R. Rajkumar, J.P. Lehoczky // IEEE Transactions on Computers. - September, 1990. - Vol. 39(9). - P. 1175-1185.

112. Srinivasan, A. Deadline-based scheduling of periodic task systems on multiprocessors / A. Srinivasan, S.K. Baruah // Information Processing Letters. -October, 2002. - Vol. 84(2). - P. 93-98.

113. Timmerman, M. RTOS Evaluation Kick Off! / M. Timmerman, B. Van Beneden, L. Uhres // Real-Time Magazine. - 1998. - Vol. 3. - P. 6-10.

114. Wilhelm, R. The Worst-Case Execution Time Problem - Overview of Methods and Survey of Tools / R.Wilhelm, J.Engblohm, A.Ermedahl et al. // ACM Transactions on Embedded Computing Systems. - April, 2008. - Vol. 7(3). -P. 1-53.

115. Yaashuwanth, C. Intelligent time slice for Round Robin In Real Time Operating Systems / C. Yaashuwanth, Dr. R. Ramesh // International Journal of Research and Reviews in Applied Sciences. - February, 2010. - Vol. 2(2). - P. 126-131.

116. Yao, G. Comparative evaluation of limited preemptive methods / G. Yao, G. Buttazzo, M. Bertogna // Proc. of the 15th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA 2010). - Spain, September 2010.-P. 1-8.

117. Yomsi, P.M. Extending rate monotonic analysis with exact cost of preemptions for hard real-time systems / P.M. Yomsi, Y. Sorel // Proc. of the 19th Euromicro Conference on Real-Time Systems. - Italy, 2007. - P. 280-290.

118. Zhu, D. Multiple-Resource Periodic Scheduling Problem: how much fairness is necessary? / D. Zhu, D. Mosse, R.G. Melhem // Proc. of the 24th Real Time Systems Symposium (RTSS'03). - Mexico, December, 2003. - P. 142-151.

ПРИЛОЖЕНИЕ 1. СВИДЕТЕЛЬСТВО О ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ ПРОГРАММЫ ДЛЯ ЭВМ

р о о омМ я Ф:В дер^ПЖ я

Г- 1

» * 1

е\/ -4 - » . » , . .. ч., ' . -, «V? «а*««

V ' V. V... „Л*. ■ ^ $ "к:

ш

о I осллирсч «сннпи (Н'1 и с I цапни нршриччы для О ИМ

№2011617924

«Оценка диснетчери;шр\ ем о с I и ;$адач и мулынпроцсссорных

системах реального времени при использовании методов планирования, базирующихся на принудительных периодических вытеснениях»

I|р,ник»Г> 1,к.ы1с.'ш(ли), Докучаев Андрей Николаевич (1Ш) Лшир(ы) Докучаев Андрей Николаевич (НИ)

(.».т а V. 2011 Г» 1 (»234

,1лга шн пи тяы 17 августа 2011 г.

Лл;нч не |ри[)<>паио и IЧе'с гре »¡им рамм для ОНМ

10 октября 2011 г,

{'цкон/кШпн* 1Ь Фс<Щниыюп i.tif жйы пи мнтеч ¡ектг/а шши иСн тт ним ты, патентам и то/щшьш ямка м

П II ('и ионап

:'Л >У <{ •<{ 'л •?. »>: и( Га Р 5: ш :4 м :л и

д ;С1

1Я л1

¿4

«й 21

т

К!

13 -Я

'>1