Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Notice: Выполняемый файл <code>texvccheck</code> не найден; см. math/README — справку по настройке. in /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php on line 65

Warning: Cannot modify header information - headers already sent by (output started at /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php:65) in /storage/mediawiki-1.24.1/includes/WebResponse.php on line 37

Warning: Cannot modify header information - headers already sent by (output started at /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php:65) in /storage/mediawiki-1.24.1/includes/WebResponse.php on line 37

Warning: Cannot modify header information - headers already sent by (output started at /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php:65) in /storage/mediawiki-1.24.1/includes/WebResponse.php on line 37
НИР:Планирование вычислительных задач в системах реального времени — Кафедра Автоматики и телемеханики
Персональные инструменты

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

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

Версия от 02:37, 19 ноября 2015; Mvk (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

  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. 4,0 4,1 Кавалеров М.В. Современное состояние исследований и практических внедрений, связанных с проблемами планирования задач реального времени в системах управления, контроля и измерения // Труды Третьей российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» [Электронный ресурс]: труды и пленарные доклады участников конференции УКИ’12. – М.: ИПУ РАН, 2012. – C. 1360–1372. URL: http://cmm.ipu.ru/sites/default/cmm12cd/cmm12CDImage.zip (дата обращения 17.10.2012).


.
Warning: Cannot modify header information - headers already sent by (output started at /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php:65) in /storage/mediawiki-1.24.1/includes/WebResponse.php on line 37

Warning: Cannot modify header information - headers already sent by (output started at /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php:65) in /storage/mediawiki-1.24.1/includes/WebResponse.php on line 37

Warning: Cannot modify header information - headers already sent by (output started at /storage/mediawiki-1.24.1/extensions/Math/MathInputCheckTexvc.php:65) in /storage/mediawiki-1.24.1/includes/WebResponse.php on line 37