Персональные инструменты

НИР:Планирование задач в системах реального времени — различия между версиями

Материал из Кафедра Автоматики и телемеханики

Перейти к: навигация, поиск
 
(не показано 40 промежуточных версии этого же участника)
Строка 1: Строка 1:
−
В системах автоматизации и управления (САиУ) для отдельного вычислительного устройства (ВУ) часто надо осуществлять планирование задач реального времени (РВ), что предполагает разделение процессорного времени между этими задачами при условии соблюдения ограничений РВ (см. рис. 1).
+
В системах автоматизации и управления, к которым, в частности, относятся системы автоматизации и управления (САиУ), часто надо осуществлять планирование задач [[НИР:Реальное время|реального времени]], что предполагает разделение процессорного времени между этими задачами при условии соблюдения [[НИР:Ограничения реального времени|ограничений реального времени]].
  
−
Рассмотрим пример.  
+
Об основных направлениях исследований в области планирования задач реального времени можно узнать из монографий <ref name="Kopetz2011">Kopetz H. Real-Time Systems: Design Principles for Distributed Embedded Applications. - Springer, 2011. - 376 p.</ref><ref name="Buttazzo2011">Buttazzo G. Hard Real-Time Computing Systems. – Springer, 2011. – 521 p.</ref>, а также обзоров <ref>Sha L., Abdelzaher T., Årzén K. E., Cervin A., Baker T., Burns A., Buttazzo G., Caccamo M., Lehoczky J., Mok A. K. Real-Time Scheduling Theory: A Historical Perspective // Real-Time Systems 28, 2004. – P. 101–155.</ref><ref>Кавалеров М.В. Современное состояние исследований и практических внедрений, связанных с проблемами планирования задач реального времени в системах управления, контроля и измерения // Труды Третьей российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» [Электронный ресурс]: труды и пленарные доклады участников конференции УКИ’12. – М.: ИПУ РАН, 2012. – C. 1360–1372. URL: http://cmm.ipu.ru/sites/default/cmm12cd/cmm12CDImage.zip (дата обращения 17.10.2012).</ref>.
  
−
Пусть на однопроцессорном контроллере в составе САиУ выполняются две задачи РВ, обозначаемые <math>\tau_1,\,\tau_2</math>, для двух независимых контуров управления.
+
== Определение проблемы планирования задач в системах реального времени ==
 +
С общих позиций, '''проблема планирования''' задач реального времени состоит в обеспечении такого выполнения этих задач, которое гарантирует соблюдение всех [[НИР:Ограничения реального времени|ограничений реального времени]] этих задач.
 +
 
 +
В монографии <ref name="Kopetz2011" /> приводится следующее определение проблемы планирования.
 +
{{Определение|
 +
Система [[НИР:Жесткое реальное время|жесткого реального времени]] должна выполнять множество задач реального времени, соперничающих за ресурсы, так, чтобы все критичные (с точки зрения времени) задачи укладывались в отведенные им крайние сроки. Для выполнения каждой задачи требуются вычислительные ресурсы, ресурсы данных и прочие ресурсы, например, устройства ввода-вывода. Тогда '''проблема планирования''' - это проблема такого распределения указанных ресурсов, которое обеспечивает соблюдение всех требований реального времени.
 +
}}
 +
Немного более детализированное определение используется в монографии <ref name="Buttazzo2011" />. С небольшой переформулировкой и уточнением его можно воспроизвести здесь следующим образом.
 +
{{Определение|
 +
Имеется множество из <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>, которое обеспечивает завершение (или выполнение) всех задач согласно заданным ограничениям.
 +
}}
 +
Указанные определения являются довольно общими. В более конкретных условиях формулировка проблемы планирования становится более детализированной и более удобной для решения. Поясним это на следующем простом примере.
 +
 +
== Пример проблемы планирования задач реального времени ==
 +
 
 +
Пусть на однопроцессорном контроллере в составе САиУ выполняются две задачи реального времени, обозначаемые <math>\tau_1,\,\tau_2</math>, для двух независимых контуров управления (см. рис. 1).
 
[[Файл:Две задачи, выполняемые на контроллере.png|frame|слева|Рис. 1. Две задачи, выполняемые на контроллере<br /> (Д - датчик; ИУ - исполнительное устройство).]]
 
[[Файл:Две задачи, выполняемые на контроллере.png|frame|слева|Рис. 1. Две задачи, выполняемые на контроллере<br /> (Д - датчик; ИУ - исполнительное устройство).]]
 +
 +
Каждая  <math>~i</math>-я задача должна периодически формировать запросы <math>(\tau_{i,1},\,\tau_{i,2},\,...)</math>, и запросу требуется время выполнения (здесь для простоты оно считается постоянным) для формирования очередного воздействия на объект (см. рис. 2). В случае отдельного процессора для каждой задачи проблем не возникает, и они выполняются, как показано на рис. 2.
 +
 +
[[Файл:Пример выполнения задач в случае отдельных процессоров.png|frame|слева|Рис. 2. Пример выполнения задач <math>\tau_1,\,\tau_2</math> в случае отдельных процессоров.]]
 +
 +
Однако при общем процессоре возникает взаимовлияние.
 +
 +
Пусть для разделения процессорного времени между задачами применяется [[НИР:Планирование с фиксированными приоритетами|концепция планирования с фиксированными приоритетами (ПФП)]].
 +
 +
Пусть [[НИР:Начальное смещение периодической задачи РВ|начальные смещения]] <math>(O_1,\,O_2)</math> и [[НИР:Период задачи РВ|периоды]] <math>(T_1,\,T_2)</math> менять нельзя, тогда в рамках [[НИР:Планирование с фиксированными приоритетами|ПФП]] остается лишь менять [[НИР:Приоритеты задач РВ|приоритеты]] <math>(\pi_1,\,\pi_2)</math>.
 +
 +
Поэтому существуют только два варианта планирования: <math>~(\pi_1</math> выше <math>~\pi_2)</math>, <math>~(\pi_1</math> ниже <math>~\pi_2)</math>, приводящие к двум вариантам выполнения задач (см. рис. 3).
 +
 +
[[Файл:Примеры выполнения задач в случае одного процессора.png|frame|слева|Рис. 3. Варианты планирования задач <math>\tau_1,\,\tau_2</math> в случае общего процессора.]]
 +
 +
Согласно [[НИР:Планирование с фиксированными приоритетами|ПФП]] запрос задачи с более высоким приоритетом прерывает выполнение запроса задачи с более низким приоритетом. На рисунке окружностью отмечается момент <math>~(r_{i,j})</math> [[НИР:Появление запроса задачи РВ|появления запроса]] <math>~\tau_{i,j}</math>  в очереди запросов, а прерывание запроса обозначается линией над соответствующей временной осью.
 +
 +
При этом 1-й вариант на рис. 3 приводит к значительному нарушению строгой периодичности для <math>~\tau_2</math>: видно, что {{nobr|<math>~r_{2,3}\neq{}s_{2,3}</math>,}} где <math>~s_{2,3}</math> - [[НИР:Начало выполнения запроса задачи РВ|начало выполнения]] <math>~\tau_2</math>.
 +
 +
Простое изменение приоритетов приводит ко 2-му варианту на рис. 3, который обеспечивает строгую периодичность для  <math>~\tau_2</math>, и небольшое нарушение периодичности для  <math>~\tau_1</math>.
 +
 +
Пусть известно, что такое небольшое нарушение для <math>~\tau_1</math> оказывается допустимым. Тогда решением проблемы планирования будет 2-й вариант на рис. 3 с соответствующими значениями <math>~(O_1,\,T_1,\,\pi_1)</math>, <math>~(O_2,\,T_2,\,\pi_2)</math>.
 +
 +
Однако в приведенном простом примере имеется всего два варианта планирования, и ''проблема планирования'' сводится к выбору одного из этих двух вариантов.
 +
 +
В общем случае ''проблема планирования'' совокупности [[НИР:Периодические задачи РВ|периодических]] задач [[НИР:Жесткое реальное время|жесткого реального времени]] в случае [[НИР:Планирование с фиксированными приоритетами|концепции ПФП]] сводится к выбору такой совокупности {{nobr|<math>~\{O_i,\,T_i,\,\pi_i|i\in\left[1,n\right]{}\}</math>,}} которая обеспечивает соблюдение ограничений реального времени для ''всех'' <math>~n</math> задач.
 +
 +
Возможность изменения  <math>~O_i,\,T_i</math> в заданных диапазонах, а также наличие <math>~n!</math> вариантов назначения приоритетов для <math>~n</math>  задач приводят к тому, что полный перебор вариантов может стать практически труднореализуемым.
 +
Нетрудно показать, что указанная проблема планирования является [http://en.wikipedia.org/wiki/NP-hard NP-трудной].
 +
 +
Поэтому естественный подход к ее решению – это разработка эффективных [http://ru.wikipedia.org/wiki/%DD%E2%F0%E8%F1%F2%E8%F7%E5%F1%EA%E8%E9_%E0%EB%E3%EE%F0%E8%F2%EC эвристических алгоритмов], которые за приемлемое время с достаточно высокой вероятностью находят значения  {{nobr|<math>~\{O_i,\,T_i,\,\pi_i|i\in\left[1,n\right]{}\}</math>,}} обеспечивающие подходящий вариант планирования, когда такие варианты существуют. Необходимость разработки подобных алгоритмов становится особенно актуальной в случае систем, в которых планирование должно выполняться в процессе функционирования, например, при наличии возможности динамического добавления новой задачи.
 +
 +
В данном очень простом примере была рассмотрена проблема планирования для [[НИР:Планирование с фиксированными приоритетами|концепции ПФП]]. Но существуют другие концепции планирования задач реального времени, и для каждой из них характерны свои специфические особенности проблемы планирования.
 +
{{-}}
 +
== Примечания ==
 +
{{Примечания}}
 +
 +
__NOEDITSECTION__

Текущая версия на 18:49, 17 октября 2012

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

Об основных направлениях исследований в области планирования задач реального времени можно узнать из монографий [1][2], а также обзоров [3][4].

Определение проблемы планирования задач в системах реального времени

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

В монографии [1] приводится следующее определение проблемы планирования.

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

Немного более детализированное определение используется в монографии [2]. С небольшой переформулировкой и уточнением его можно воспроизвести здесь следующим образом.

Имеется множество из задач , множество из процессоров , а также множество из видов разделяемых ресурсов .

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

С каждой задачей могут связаны ограничения реального времени.

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

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

Пример проблемы планирования задач реального времени

Пусть на однопроцессорном контроллере в составе САиУ выполняются две задачи реального времени, обозначаемые , для двух независимых контуров управления (см. рис. 1).

Рис. 1. Две задачи, выполняемые на контроллере
(Д - датчик; ИУ - исполнительное устройство).

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

Рис. 2. Пример выполнения задач в случае отдельных процессоров.

Однако при общем процессоре возникает взаимовлияние.

Пусть для разделения процессорного времени между задачами применяется концепция планирования с фиксированными приоритетами (ПФП).

Пусть начальные смещения и периоды менять нельзя, тогда в рамках ПФП остается лишь менять приоритеты .

Поэтому существуют только два варианта планирования: выше , ниже , приводящие к двум вариантам выполнения задач (см. рис. 3).

Рис. 3. Варианты планирования задач в случае общего процессора.

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

При этом 1-й вариант на рис. 3 приводит к значительному нарушению строгой периодичности для : видно, что , где - начало выполнения .

Простое изменение приоритетов приводит ко 2-му варианту на рис. 3, который обеспечивает строгую периодичность для , и небольшое нарушение периодичности для .

Пусть известно, что такое небольшое нарушение для оказывается допустимым. Тогда решением проблемы планирования будет 2-й вариант на рис. 3 с соответствующими значениями , .

Однако в приведенном простом примере имеется всего два варианта планирования, и проблема планирования сводится к выбору одного из этих двух вариантов.

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

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

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

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

Примечания

  1. ↑ 1,0 1,1 Kopetz H. Real-Time Systems: Design Principles for Distributed Embedded Applications. - Springer, 2011. - 376 p.
  2. ↑ 2,0 2,1 Buttazzo G. Hard Real-Time Computing Systems. – Springer, 2011. – 521 p.
  3. ↑ Sha L., Abdelzaher T., Årzén K. E., Cervin A., Baker T., Burns A., Buttazzo G., Caccamo M., Lehoczky J., Mok A. K. Real-Time Scheduling Theory: A Historical Perspective // Real-Time Systems 28, 2004. – P. 101–155.
  4. ↑ Кавалеров М.В. Современное состояние исследований и практических внедрений, связанных с проблемами планирования задач реального времени в системах управления, контроля и измерения // Труды Третьей российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» [Электронный ресурс]: труды и пленарные доклады участников конференции УКИ’12. – М.: ИПУ РАН, 2012. – C. 1360–1372. URL: http://cmm.ipu.ru/sites/default/cmm12cd/cmm12CDImage.zip (дата обращения 17.10.2012).


Источник — «http://at.pstu.ru/index.php?title=НИР:Планирование_задач_в_системах_реального_времени&oldid=6601»
.