НИР:Планирование задач в системах реального времени — различия между версиями
Материал из Кафедра Автоматики и телемеханики
Mvk (обсуждение | вклад) |
Mvk (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
В системах автоматизации и управления, к которым, в частности, относятся системы автоматизации и управления (САиУ), часто надо осуществлять планирование задач [[НИР:Реальное время|реального времени]], что предполагает разделение процессорного времени между этими задачами при условии соблюдения [[НИР:Ограничения реального времени|ограничений реального времени]]. | В системах автоматизации и управления, к которым, в частности, относятся системы автоматизации и управления (САиУ), часто надо осуществлять планирование задач [[НИР:Реальное время|реального времени]], что предполагает разделение процессорного времени между этими задачами при условии соблюдения [[НИР:Ограничения реального времени|ограничений реального времени]]. | ||
| − | С общих позиций, ''проблема планирования'' задач реального времени состоит в обеспечении такого выполнения этих задач, которое гарантирует соблюдение всех | + | |
| + | == Определение проблемы планирования задач в системах реального времени == | ||
| + | С общих позиций, ''проблема планирования'' задач реального времени состоит в обеспечении такого выполнения этих задач, которое гарантирует соблюдение всех [[НИР:Ограничения реального времени|ограничений реального времени]] этих задач. | ||
| + | |||
| + | Более формальное определение приводится в книге <ref>Buttazzo G. Hard Real-Time Computing Systems. – Springer. 2011. – 521 p.</ref> и состоит в следующем (приводится с небольшими уточнениями). | ||
| + | |||
| + | Имеется множество из <math>~n</math> задач <math>~\Gamma=\{\tau_1,\tau_2,...,\tau_n\}</math>, множество из <math>~m</math> процессоров <math>~P=\{P_1,P_2,...,P_m\}</math>, а также множество из <math>~q</math> видов [[НИР:разделяемые ресурсы|разделяемых ресурсов]] <math>~R=\{R_1,R_2,...,R_q\}</math>. | ||
| + | |||
| + | [[НИР:Ограничения предшествования|Ограничения предшествования]] между задачами могут быть заданы в виде [http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 направленного ациклического графа]. | ||
| + | |||
| + | С каждой задачей могут связаны [[НИР:ограничения реального времени|ограничения реального времени]]. | ||
| + | |||
| + | Тогда '''проблема планирования''' - это проблема назначения (за счет распределения по временной шкале) процессоров из <math>~P</math> и ресурсов из <math>~R</math> всем задачам из <math>~\Gamma</math>, обеспечивающего завершение (или выполнение) всех задач согласно заданным ограничениям. | ||
== Пример проблемы планирования задач реального времени == | == Пример проблемы планирования задач реального времени == | ||
Версия 01:12, 15 января 2012
В системах автоматизации и управления, к которым, в частности, относятся системы автоматизации и управления (САиУ), часто надо осуществлять планирование задач реального времени, что предполагает разделение процессорного времени между этими задачами при условии соблюдения ограничений реального времени.
Определение проблемы планирования задач в системах реального времени
С общих позиций, проблема планирования задач реального времени состоит в обеспечении такого выполнения этих задач, которое гарантирует соблюдение всех ограничений реального времени этих задач.
Более формальное определение приводится в книге [1] и состоит в следующем (приводится с небольшими уточнениями).
Имеется множество из 
задач 
, множество из 
процессоров 
, а также множество из 
видов разделяемых ресурсов 
.
Ограничения предшествования между задачами могут быть заданы в виде направленного ациклического графа.
С каждой задачей могут связаны ограничения реального времени.
Тогда проблема планирования - это проблема назначения (за счет распределения по временной шкале) процессоров из 
и ресурсов из 
всем задачам из 
, обеспечивающего завершение (или выполнение) всех задач согласно заданным ограничениям.
Пример проблемы планирования задач реального времени
Поясним проблему планирования задач реального времени на следующем простом примере.
Пусть на однопроцессорном контроллере в составе САиУ выполняются две задачи реального времени, обозначаемые 
, для двух независимых контуров управления (см. рис. 1).
(Д - датчик; ИУ - исполнительное устройство).
Каждая 
-я задача должна периодически формировать запросы (
), и запросу требуется время выполнения (здесь для простоты оно считается постоянным) для формирования очередного воздействия на объект (см. рис. 2). В случае отдельного процессора для каждой задачи проблем не возникает, и они выполняются, как показано на рис. 2.
в случае отдельных процессоров.Однако при общем процессоре возникает взаимовлияние.
Пусть для разделения процессорного времени между задачами применяется концепция планирования с фиксированными приоритетами (ПФП).
Пусть начальные смещения (
) и периоды (
) менять нельзя, тогда в рамках ПФП остается лишь менять приоритеты (
).
Поэтому существуют только два варианта планирования: (
выше 
), ( ниже ), приводящие к двум вариантам выполнения задач (см. рис. 3).
в случае общего процессора.Согласно ПФП запрос задачи с более высоким приоритетом прерывает выполнение запроса задачи с более низким приоритетом. На рисунке окружностью отмечается момент (
) появления запроса 
в очереди запросов, а прерывание запроса обозначается линией над соответствующей временной осью.
При этом 1-й вариант на рис. 3 приводит к значительному нарушению строгой периодичности для 
: видно, что 
, где 
- начало выполнения .
Простое изменение приоритетов приводит ко 2-му варианту на рис. 3, который обеспечивает строгую периодичность для , и небольшое нарушение периодичности для 
.
Пусть известно, что такое небольшое нарушение для оказывается допустимым. Тогда решением проблемы планирования будет 2-й вариант на рис. 3 с соответствующими значениями 
, 
.
Однако в приведенном простом примере имеется всего два варианта планирования, и проблема планирования сводится к выбору одного из этих двух вариантов.
В общем случае проблема планирования совокупности периодических задач жесткого реального времени в случае концепции ПФП сводится к выбору такой совокупности 
, которая обеспечивает соблюдение ограничений реального времени для всех задач.
Возможность изменения 
в заданных диапазонах, а также наличие 
вариантов назначения приоритетов для задач приводят к тому, что полный перебор вариантов становится практически нереализуемым. Нетрудно показать, что указанная проблема планирования является NP-трудной [2].
Поэтому естественный подход к ее решению – это разработка эффективных эвристических алгоритмов, которые за приемлемое время с высокой вероятностью находят значения , обеспечивающие подходящий вариант планирования.
В данном очень простом примере была рассмотрена проблема планирования для концепции ПФП. Но существуют другие концепции планирования задач реального времени, и для каждой из них характерны свои специфические особенности проблемы планирования.
Примечания
