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

Область техники, к которой относится изобретение

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

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

Уровень техники

В критических системах реального времени задачи часто смоделированы в виде периодических действий, приводящих к реализации многозадачной системы, основываясь на постоянной стратегии приоритетов для планирования задач, обеспечивая гарантии на достижение производительности. Такая система описана, например, в статье [((Scheduling algorithms for Multiprogramming in a hard real-time environment)), C. Liu, J. Layland, журнал ACM, том 20, №1, стр. 46-61].

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

Другие подходы, такие как те, что описаны в статьях [«Giotto: A Time-Triggered Language for Embedded Programming)), Thomas A. Henzinger, Benjamin Horowitz и Christoph Meyer Kirsch, EMSOFT 2001, стр. 166-184, 2001, Springer-Verlag] и [«A method and a technique to model and ensure timeliness in safety critical real-time Systems», C. Aussagues, V. David, Fourth IEEE International Conference on Engineering of Complex Computer Systems, 1998], предлагают более гибкие модели задач для описания каждой задачи в виде последовательности временных действий. Задача, таким образом, оформляется в виде графа процессов с временными ограничениями, где процессы могут, если требуется, быть условными, как предложено в патенте США №7,299,383.

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

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

Сущность изобретения

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

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

a) присваивают каждому процессу потребность в аппаратном ресурсе и временное ограничение;

b) выделяют для каждого процесса временной интервал, имеющий продолжительность, соответствующую временному ограничению процесса;

c) идентифицируют точку ветвления, в которой принимается решение о выполнении одного или другого из двух альтернативных процессов;

d) выделяют для двух альтернативных процессов общий временной интервал;

e) присваивают общему временному интервалу потребность в ресурсе, соответствующую большей из потребностей в ресурсах двух альтернативных процессов;

f) повторяют этапы с этапа с) для каждой точки ветвления;

g) организуют получающиеся временные интервалы в шаблоне выполнения, связанном с задачей; и

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

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

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

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

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

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

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

Краткое описание чертежей

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

Фигура 1 представляет собой пример графа задач реального времени, соответствующего гибкой модели задач, имеющей альтернативы ветвления с идентичными временными ограничениями;

Фигуры 2А и 2В показывают частичную трассировку выполнения одной из возможных последовательностей обработки графа на Фигуре 1 и трассировку выполнения параллельной задачи;

Фигуры 3А-3С показывают преобразования графа на Фигуре 1 и получающийся статический шаблон выполнения;

Фигура 4 представляет собой пример графа задач реального времени, соответствующего гибкой модели задач, имеющей альтернативы ветвления с различными временными ограничениями;

Фигуры 5А-5С показывают преобразования графа на Фигуре 4 для первой альтернативы временных ограничений и получающийся статический шаблон выполнения;

Фигуры 6А-6С показывают преобразования графа на Фигуре 4 для второй альтернативы временных ограничений; и

Фигуры 7А и 7В иллюстрируют этапы оптимизации для шаблона выполнения на Фигуре 5С.

Описание вариантов выполнения изобретения

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

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

Каждая дуга (или процесс) графа помечается информацией x+Ν, где x представляет собой индикатор потребности в ресурсе, а N - индикатор временного ограничения. Потребность в ресурсе x может быть выражена в виде времени, а именно времени, требуемого для завершения процесса при условии, что он имеет все аппаратные ресурсы. Временное ограничение может быть целым числом, определяющим единицы времени. Таким образом, выражая x и N в одной и той же единице времени, значения x и N выбираются так, что x≤N. Если x=Ν, процесс требует все аппаратные ресурсы во всем временном интервале, определенном временным ограничением, так, что никакой другой процесс не может выполняться параллельно в том же интервале. (Вычисление потребностей в ресурсах и временных ограничений не является объектом настоящего раскрытия и не будет подробно описано.)

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

Считается, что граф или задача соответствует «гибкой модели» в том, что она включает в себя произвольно организованные ветвления и циклы. Так как каждое ветвление определяется динамически во время выполнения и непредсказуемым образом, последовательность выполнения процессов обычно является апериодической. Последствия будут понятны далее.

Фигура 2А показывает примерную трассировку выполнения графа на Фигуре 1. На временной оси показаны перекрещенные узлы во время выполнения на этапах, определенных временными ограничениями процессов. Таким образом, узлы размещены в фиксированных точках синхронизации, где операционная система запускает соответствующие процессы.

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

Выполнение задачи графа на Фигуре 1 начинается в узле 1, где происходит первое ветвление между двумя альтернативными процессами а и b. Выбирается для выполнения процесс b, приводя к узлу 2. Процесс d выполняется между узлами 2 и 4. В узле 4 происходит новое ветвление между процессом f и процессом g; выбирается для выполнения процесс g, приводя к узлу 3. Процесс с выполняется между узлами 3 и 5. В узле 5 происходит новое ветвление между процессом е и процессом h; выбирается для выполнения процесс h, приводя к узлу 2.

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

Фигура 2В показывает трассировку выполнения задачи, выполняемой параллельно задаче на Фигуре 2А. Эта параллельная задача включает в себя последовательность процессов m, n, h, q и r, имея потребности в ресурсах, определенные теми же метками. Для облегчения понимания эта задача показана с точками синхронизации, выровненными с точками синхронизации задачи на Фигуре 2А, однако с изменениями во временных ограничениях. Для этой задачи, планируемой параллельно с задачей на Фигуре 2А, желательно в любом интервале между точками синхронизации, чтобы сумма потребностей в ресурсах процессов была согласована с временными ограничениями. Возможный набор неравенств, встречаемых в примере, проиллюстрирован под временной осью.

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

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

Здесь раскрыта методика для выполнения статического или автономного планирования задач, соответствующих гибкой модели. Эта методика нацелена на ограничение количества комбинаций планирования так, что они могут быть проверены исчерпывающим образом, используя традиционные инструменты. Желательно установить для каждой задачи, так называемый, статический «шаблон выполнения», который является пригодным для использования инструментом автономного планирования.

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

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

На графе на Фигуре 1 альтернативные процессы, следующие за каждым ветвлением (узлы 1, 4 и 5), имеют одинаковые временные ограничения.

Фигура 3А иллюстрирует первый этап в преобразовании графа на Фигуре 1. Два целевых узла 2 и 3 двух альтернативных процессов а и b объединены в один узел 2_3. Дуги, которые соединяют узлы 2 и 3 с узлами 4 и 5, все соединены с узлом 2_3. Две дуги, которые пошли от узла 1 к узлам 2 и 3, объединены в одну дугу. Эта единственная дуга связана с «двойственным» процессом, представляющим собой любой из процессов а и b, и отмечена а|b+2. Как обозначено этой записью, общее временное ограничение (+2) процессов а и b представляет собой временное ограничение двойственного процесса. Потребность в ресурсе двойственного процесса определяется как соответствующая максимальному значению max(a, b) потребностей в ресурсах процессов а и b.

Может быть отмечено, что процессы c и d, которые не были альтернативами ветвления, становятся альтернативами, возникающими в объединенном узле 2_3. Также может быть отмечено, что альтернативы f, g и е, h, проходящие от каждого из узлов 4 и 5 к узлам 2 и 3, группируются вместе за счет того, что узлы 2 и 3 объединены. На этом этапе эти альтернативы могли бы быть представлены одной дугой, подобной дуге а|b+2.

Фигура 3В иллюстрирует конечный этап преобразования графа на Фигуре 1. Целевые узлы 4 и 5 альтернативных процессов c и d объединены в узел 4_5. Имеются два процесса c и d, имеющие одинаковое временное ограничение (+4), идущие от узла 2_3 к узлу 4_5, и четыре процесса е, f, g и h, имеющие одинаковое временное ограничение (+2), идущие в противоположном направлении. Согласно правилам, применяемым к альтернативным процессам а и b, все дуги от одного и того же исходного узла к одному и тому же целевому узлу и имеющие одинаковое временное ограничение, объединены в одну дугу, присвоенную двойственному процессу, которая сохраняет временное ограничение, и чья потребность в ресурсе устанавливается, соответствующей наибольшей из потребностей в ресурсах дуг, которые объединены. Таким образом, получаются один двойственный процесс c|d+4 от узла 2_3 к узлу 4_5, имеющий потребность в ресурсе max(c, d), и один двойственный процесс e|f|g|h+2 в противоположном направлении, имеющий потребность в ресурсе max(e, f, g, h). Таким образом, возможно удалять все альтернативы в графе для получения графа, имеющего линейный путь, ограниченный циклическим участком для выполнения в цикле.

Фигура 3С иллюстрирует шаблон выполнения, определенный из преобразованного графа на Фигуре 3В, в том же формате, что и трассировка выполнения на Фигуре 2А. Значительная разница между шаблоном и трассировкой заключается в том, что шаблон может быть определен автономно с использованием преобразованного графа на Фигуре 3В.

В момент времени t=0 принимается решение о выполнении одного из альтернативных процессов а и b в узле 1. Какой бы ни была альтернатива, она выполняется в одном интервале, определенном между узлами 1 и 2_3, продолжительность которого совместима с обеими альтернативами. Таким образом, произвольный один из процессов c и d выполняется в следующем интервале, определенном между узлами 2_3 и 4 5. Наконец, один из процессов е, f, g и h выполняется в интервале, определенном между узлами 4_5 и 2_3. Выполнение затем возобновляется в новом цикле R из узла 2_3.

Потребностями в ресурсах, присвоенными для интервалов между узлами 1, 2_3, 4_5 и 2_3, соответственно являются max(a, b), max(с, d) и max(е, f, g, h).

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

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

Более того, шаблон позволяет предсказывать в любое время, как задача развивается с точки зрения ее потребностей в ресурсах и временных ограничений. Более того, циклический участок R шаблона на Фигуре 3С может быть самовольно повторяющимся из первого узла 2 на Фигуре 2А для предсказания потребностей в ресурсах и временных ограничений в любой точке трассировки выполнения, какие бы альтернативы не выполнялись после ветвлений. Единственным недостатком является то, что значение потребности в ресурсе максимизировано вместо того, чтобы быть точным.

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

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

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

Фигура 5А иллюстрирует первый этап преобразования графа на Фигуре 4. В альтернативном процессе, имеющем самое длительное временное ограничение, процессе с, вставляется промежуточный узел 3b. Считается, что дуга, соединяющая узлы 2 и 3b, представляет собой часть c1 процесса с, и ей присваивается то же временное ограничение +1, что и у альтернативного процесса b. Дуга, соединяющая узлы 3b и 4, представляет собой оставшуюся часть с2 процесса с и ей присваивается дополнение +3 временного ограничения процесса с. Потребности в ресурсах частичных процессов c1 и с2 являются такими, что c1+с2=с. Распределение потребности в ресурсе с между потребностями c1 и с2 может быть произвольным. Это распределение может быть оптимизировано, например, для того, чтобы минимизировать отклонения между потребностями в ресурсах альтернативных процессов и их максимизированным значением. Например, если с=2, b=0,8 и d=1, значения c1=0,9 и с2=1,1 производят максимальное отклонение 0,1.

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

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

Предпочтительный подход включает в себя простую модификацию операционной системы. Как проиллюстрировано на Фигуре 5А, двум альтернативным процессам ветвления узла 2 присваивается переменная состояния или флаг В для идентификации альтернативы, принимаемой во время выполнения. Когда выполняемая альтернатива соответствует немодифицированной дуге (b), флаг В остается в его очищенном значении по умолчанию (например, 0). Когда альтернатива соответствует преобразованной дуге (c1), флаг В устанавливается самим процессом или операционной системой. Использование этого флага будет описано более подробно с использованием Фигуры 5С.

Фигура 5B иллюстрирует конечное преобразование графа на Фигуре 5А. Благодаря вставке узла 3b, создавая два альтернативных процесса с одинаковым временным ограничением, целевые узлы 3 и 3b этих альтернативных процессов могут быть объединены согласно методике, описанной в отношении Фигуры 3А. Это создает двойственный процесс b|c1 между узлом 2 и объединенным узлом 3_3b с временным ограничением +1 и потребностью max(b, c1) в ресурсе.

Используя флаг В, двойственный процесс обозначается b(B=0)|c1(B=1).

Процессы d и с2, которые пошли от узлов 3 и 3b к узлу 4, имеющие одинаковое временное ограничение +3, могут быть объединены в один двойственный процесс c2|d с временным ограничением +3 и потребностью max(c2, d) в ресурсе.

Фигура 5С иллюстрирует шаблон выполнения, определенный из преобразованного графа на Фигуре 5В. Этот шаблон является повторяемым согласно последовательности узлов 1, 2, 3_3b, 4.

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

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

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

Если выполняется альтернативный частичный процесс c1, устанавливается флаг В (самим процессом или операционной системой). В этом случае, даже если потребность c1 в ресурсе превышена, сторожевой процесс сообщает об отсутствии ошибки. Флаг В очищается в точке 3_3b так, что сторожевой процесс работает обычным образом от точки 3_3b.

Таким образом, используя флаг В, становится необязательным фактически разделять процесс с на два частичных процесса. Первоначальный процесс с может быть запущен в точке 2, и его выполнение может продолжаться за пределами точки 3_3b без сигнализирования об ошибке. Только если выполнение процесса с превышает потребность c1+с2 в ресурсе, будет сигнализирована ошибка, что соответствует ограничениям первоначального графа. С целью планирования все же считается, что потребность в ресурсе процесса с распределяется на два значения c1 и с2.

Как отмечено выше, после вставки промежуточного узла 3b процессы с2 и d имеют одинаковое временное ограничение. Эти значения были выбраны для упрощения объяснений. В общем случае временные ограничения будут различными. В этом случае достаточно повторить технологию, используемую для процесса с, как показано путем примера ниже.

Фигуры 6А-6С иллюстрируют этапы преобразования графа на Фигуре 4 для другого значения временного ограничения процесса d, здесь +6 вместо +3.

Фигура 6А соответствует этапу на Фигуре 5А. Разница лишь в значении временного ограничения процесса d.

На фигуре 6 В узлы 3 и 3b были объединены. Узлы 3_3b и 4 соединены двумя дугами с2+3 и d+6, имеющими различные временные ограничения.

На Фигуре 6С узел 4 разделен на два узла, один 4', образующий цель процесса с2+3, и другой 4'', образующий цель процесса d+6. Каждый из узлов 4' и 4'' соединен с узлом 1 процессом е+1.

С этого этапа процедура этапа на Фигуре 6А или 5А повторяется путем вставки промежуточного узла в процессе, имеющем наибольшее временное ограничение d+6, для создания двух альтернативных процессов, имеющих одинаковое временное ограничение с2+3 и d1+3, и т.д., для преобразования графа в циклический граф или граф, ограниченный циклическим участком.

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

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

Фигуры 7А и 7В иллюстрируют методику для нормализации длины временных интервалов и для укорочения шаблонов.

Фигура 7А иллюстрирует этап обработки шаблона на Фигуре 5С в качестве примера. Он стремится в циклическом участке шаблона разделять более длительные интервалы на несколько более коротких интервалов, чья длина представляет собой наибольший общий делитель интервалов циклического участка. В шаблоне на Фигуре 7А интервал между узлами 3_3b и 4 длиной 3 разделен на три интервала длиной 1. Это равносильно вставке промежуточных переходных узлов 4а и 4b в дуге c2|d графа.

Таким образом, двойственный процесс c2|d разделяется на три частичных двойственных процесса [c2|d]0-[c2|d]2 с одинаковым временным ограничением 1. Первоначальная потребность в ресурсе процесса c2|d max(c2, d) распределяется среди трех частичных процессов с весами р0, p1 и р2 так, что р0+p1+р2=1.

В отношении промежуточного узла 3b на Фигуре 5А промежуточные узлы 4а и 4b становятся точками синхронизации, от которых сторожевой процесс контролирует время выполнения процессов. Для исключения фактического разделения процесса c2|d предпочтительно использование флага S, который подобно флагу В указывает сторожевому процессу на исключение сообщения об ошибке, если процесс превышает его потребность в ресурсе. Флаг S устанавливается, безусловно, с начала процесса c2|d (таким образом, в основном с начала любого из процессов с и d) и далее очищается в последней промежуточной точке (4b) синхронизации.

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

Фигура 7В иллюстрирует этап для укорочения нормализованного шаблона выполнения на Фигуре 7А. Вторая половина шаблона была наложена на первую половину так, что узлы 4а, 4b и 4 соответственно объединяются с узлами 1, 2 и 3_3b. Таким образом, остаются только три временных интервала продолжительности 1. В первом временном интервале любой из процессов а и [c2|d]1 может быть выполнен, таким образом, по существу любой из процессов а, с и d при использовании флагов В и S. Во втором временном интервале любой из процессов b, c1 и [c2|d]2 может быть выполнен, таким образом, по существу любой из процессов b, с и d. В последнем временном интервале любой из процессов е и [c2|d]0 может быть выполнен, таким образом, по существу любой из процессов е, с и d.

Потребности в ресурсах для этих интервалов следуют тем же правилам определения, что и для альтернативных процессов. Они соответственно равны max{а, p1⋅max(c2,d)}, max{b, c1, р2⋅max(с2, d)}, и max{е, р0⋅max(с2, d)}.

Для рассмотренного примерного шаблона, который является полностью циклическим с четным числом интервалов, размер шаблона может быть уменьшен вдвое. В произвольной ситуации шаблон включает в себя линейный участок, за которым следует циклический участок (Фигуры 3B, 3C), который может включать в себя нечетное число интервалов. Способ наложения относится к нормализованному циклическому участку. Это применимо, даже если нормализованный циклический участок имеет нечетное число интервалов - более того, наложение может быть частичным, что выполняется в незначительной мере в ущерб уменьшению размера шаблона.