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

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

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

Перейти к: навигация, поиск
 
(не показано 28 промежуточных версии этого же участника)
Строка 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>.
  
−
Поясним проблему планирования задач реального времени на следующем примере.
+
== Определение проблемы планирования задач в системах реального времени ==
 +
С общих позиций, '''проблема планирования''' задач реального времени состоит в обеспечении такого выполнения этих задач, которое гарантирует соблюдение всех [[НИР:Ограничения реального времени|ограничений реального времени]] этих задач.
 +
 
 +
В монографии <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).
 
Пусть на однопроцессорном контроллере в составе САиУ выполняются две задачи реального времени, обозначаемые <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.
+
Каждая  <math>~i</math>-я задача должна периодически формировать запросы <math>(\tau_{i,1},\,\tau_{i,2},\,...)</math>, и запросу требуется время выполнения (здесь для простоты оно считается постоянным) для формирования очередного воздействия на объект (см. рис. 2). В случае отдельного процессора для каждой задачи проблем не возникает, и они выполняются, как показано на рис. 2.
  
 
[[Файл:Пример выполнения задач в случае отдельных процессоров.png|frame|слева|Рис. 2. Пример выполнения задач <math>\tau_1,\,\tau_2</math> в случае отдельных процессоров.]]
 
[[Файл:Пример выполнения задач в случае отдельных процессоров.png|frame|слева|Рис. 2. Пример выполнения задач <math>\tau_1,\,\tau_2</math> в случае отдельных процессоров.]]
Строка 16: Строка 35:
 
Пусть для разделения процессорного времени между задачами применяется [[НИР:Планирование с фиксированными приоритетами|концепция планирования с фиксированными приоритетами (ПФП)]].
 
Пусть для разделения процессорного времени между задачами применяется [[НИР:Планирование с фиксированными приоритетами|концепция планирования с фиксированными приоритетами (ПФП)]].
  
−
Пусть [[НИР:Начальное смещение периодической задачи РВ|начальные смещения]] (<math>O_1,\,O_2</math>) и [[НИР:Период задачи РВ|периоды]] (<math>T_1,\,T_2</math>) менять нельзя, тогда в рамках [[НИР:Планирование с фиксированными приоритетами|ПФП]] остается лишь менять [[НИР:Приоритеты задач РВ|приоритеты]] (<math>\pi_1,\,\pi_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).
+
Поэтому существуют только два варианта планирования: <math>~(\pi_1</math> выше <math>~\pi_2)</math>, <math>~(\pi_1</math> ниже <math>~\pi_2)</math>, приводящие к двум вариантам выполнения задач (см. рис. 3).
  
−
[[Файл:Примеры выполнения задач в случае одного процессора.png|frame|слева|Рис. 2. Пример выполнения задач <math>\tau_1,\,\tau_2</math> в случае отдельных процессоров.]]
+
[[Файл:Примеры выполнения задач в случае одного процессора.png|frame|слева|Рис. 3. Варианты планирования задач <math>\tau_1,\,\tau_2</math> в случае общего процессора.]]
  
−
Согласно [[НИР:Планирование с фиксированными приоритетами|ПФП]] запрос задачи с более высоким приоритетом прерывает выполнение запроса задачи с более низким приоритетом. На рисунке окружностью отмечается момент (<math>~r_{i,j}</math>) [[НИР:Появление запроса задачи РВ|появления запроса]] <math>~\tau_{i,j}</math>  в очереди запросов, а прерывание запроса обозначается линией над соответствующей временной осью.
+
Согласно [[НИР:Планирование с фиксированными приоритетами|ПФП]] запрос задачи с более высоким приоритетом прерывает выполнение запроса задачи с более низким приоритетом. На рисунке окружностью отмечается момент <math>~(r_{i,j})</math> [[НИР:Появление запроса задачи РВ|появления запроса]] <math>~\tau_{i,j}</math>  в очереди запросов, а прерывание запроса обозначается линией над соответствующей временной осью.
  
−
При этом 1-й вариант на рис. 3 приводит к значительному нарушению строгой периодичности для <math>~\tau_2</math>: видно, что <math>~r_{2,3}\neq{}s_{2,3}</math>, где <math>~s_{2,3}</math> - [[НИР:Начало выполнения запроса задачи РВ|начало выполнения]] <math>~\tau_2</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>.  
 
Простое изменение приоритетов приводит ко 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>,}} обеспечивающие подходящий вариант планирования, когда такие варианты существуют. Необходимость разработки подобных алгоритмов становится особенно актуальной в случае систем, в которых планирование должно выполняться в процессе функционирования, например, при наличии возможности динамического добавления новой задачи.
 +
 +
В данном очень простом примере была рассмотрена проблема планирования для [[НИР:Планирование с фиксированными приоритетами|концепции ПФП]]. Но существуют другие концепции планирования задач реального времени, и для каждой из них характерны свои специфические особенности проблемы планирования.
 
{{-}}
 
{{-}}
 
== Примечания ==
 
== Примечания ==

Текущая версия на 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»
.