СПОСОБ СОСТАВЛЕНИЯ И ИСПОЛНЕНИЯ ПЛАНА ЗАДАНИЯ ПОСЛЕДОВАТЕЛЬНОСТИ РЕАЛЬНО-ВРЕМЕННЫХ ЗАДАЧ
METHOD FOR COMPOSING AND EXECUTING REAL-TIME TASK-SEQUENCING PLAN

Область техники
Изобретение относится к критическим реально-временным многозадачным системам, таким как системы контроля-управления, используемые в отраслях транспорта (автомобильного, железнодорожного, морского, авиационного), промышленных автоматов, энергетики, а также другие системы, для которых важное значение имеет контролируемое распределение ресурсов, например, в коммуникационных сетях. Изобретение относится как к реально-временным системам, для которых необходим высокий уровень эффективности в применении, так и к критическим системам, от которых требуется высокий уровень гарантии в том, что касается использования материальных исполнительных ресурсов, выделяемых для каждой задачи системы.
Уровень техники
В критических реально-временных системах, то есть в системах, которые не могут допускать никакого нарушения сроков из-за задержки в выполнении операции, задачи часто выполняют в соответствии с методами статического планирования. При этом автономно составляют статическое временное распределение потребности в использовании исполнительных ресурсов, что позволяет выявить временную независимость задач между собой в том, что касается использования ресурсов и, в частности, процессора. Такой подход описан, например, в статье [“A method and a technique to model and ensure timeliness in safety critical real time systems”, C. Aussaguès, V. David, Fourth IEEE International Conference on Engineering of Complex Computer Systems, 1998] и в патентных заявках WO2006-050967 и
US2010-0199280.
Однако такой тип подхода предполагает рассматривать только единый план задания последовательности, то есть рассматривать только одну шкалу времени для определения сроков. Это затрудняет выполнение задач без помех на одном и том же процессоре с невзаимосвязанными шкалами времени, таких как задача, использующая один синхрогенератор для определения своих сроков, и задача, использующая положение объекта с переменной скоростью для определения своих сроков. Для этого понадобилось бы составить два плана задания последовательности при помощи одной шкалы времени, чтобы иметь возможность объединить их в один план задания последовательности без помех между задачами. На практике это можно реализовать, только если исполнительные ресурсы предусмотрены с избыточными параметрами с целью прогнозирования наихудшего развития каждой ситуации.
В высокоэффективных реально-временных системах, которые не называют «критическими», так как они могут допускать нарушения сроков в определенных пределах, составление двух планов задания последовательности, рассчитываемых по разным шкалам времени, осуществляют при помощи динамических алгоритмов планирования. Такие алгоритмы описаны, например, в [“Scheduling algorithms for multiprogramming in a hard real-time environment”, C. Liu, J. Layland, Journal of the ACM, vol. 20, no. 1, pp. 46-61] и [Foundations of Real-Time Computing: Scheduling and Resource Management”, André M. Van Tilborg, Gary M. Koob, 1991, Kluwer Academic Publishers], а также в [“A method and a technique to model and ensure timeliness in safety critical real time systems”, C. Aussaguès, V. David, Fourth IEEE International Conference on Engineering of Complex Computer Systems, 1998].
С этими алгоритмами неизбежны преобладающие приоритеты, то есть система может прерывать текущую операцию для исполнения более срочной операции. Поскольку планирование является динамическим, невозможно определить число и продолжительность приоритетных перерывов, и каждый перерыв расходует время системы для внесения изменения контекста. Это создает помехи между задачами, поэтому затрудняется параметризация систем, они являются менее предсказуемыми и не воспроизводимыми на сложных архитектурах процессоров. Кроме того, разработчики этих систем сталкиваются с трудностями в правильной регулировке приоритетов задач или сроков в системе с двумя разными шкалами времени. Выбираемые опции, такие как изменение исполнительных потребностей в зависимости от значения прикладных параметров, делает разрабатываемые таким образом системы очень сложными и не контролируемыми.
Раскрытие изобретения
Таким образом, существует потребность в технологии, позволяющей исполнять без помех с разделением времени два плана задания последовательности, даже если шкалы времени двух планов являются разными.
i
Эту потребность можно удовлетворить, предложив способ выполнения двух задач с разделением времени, содержащий этапы, на которых каждую задачу автономно раскладывают на повторяющуюся последовательность последовательных фреймов, в которой каждый фрейм связан с атомарной операцией, имеющей одну исполнительную потребность, и определяет дату начала, с которой операцию можно начать, и дату конечного срока, к которой операцию необходимо завершить, при этой каждый фрейм определяет запас времени, в течение которого можно запустить операцию; для каждого фрейма первой из повторяющихся последовательностей проверяют, что соответствующую операцию можно исполнить между двумя любыми последовательными операциями из группы фреймов второй повторяющейся последовательности с перекрыванием фрейма (Fa) первой повторяющейся последовательности и с соблюдением дат начала и сроков операций; и, если проверка оказалась удовлетворительной, разрешают выполнение обеих задач.
При этом операции обеих задач планируют в зависимости от следующих случаев, оцениваемых по каждой ключевой дате, когда одна ключевая дата наступает при каждом истечении срока исполнения, по каждой дате начала и по каждому концу исполнения операции: если можно запустить две операции, выполняют ту операцию, которая имеет более короткий срок исполнения; и, если, можно запустить только одну операцию, ее выполняют только, если исполнительная потребность меньше времени, остающегося до даты начала следующего фрейма другой последовательности и увеличенного на запас времени, связанный с указанным следующим фреймом другой последовательности.
Согласно варианту осуществления, каждый фрейм дополнительно содержит интервал резервного времени, который может быть нулевым, находящийся после срока исполнения фрейма или перед датой начала фрейма, при этом можно брать интервалы резервного времени любой одной из повторяющихся последовательностей для выполнения операции другой повторяющейся последовательности.
Согласно варианту осуществления, этап проверки содержит следующие этапы:
i
j
• для каждого фрейма Fa первой повторяющейся последовательности оценивают следующие условия для каждого фрейма Fb второй повторяющейся последовательности:
i
j+1
[A.1] Da ≤ Tb
i
j
j+1
j
i
[B.1] Da ≤ Rb +Tb и Db ≤ Ta, и
j
i
[C.1] Db ≤ Ta,
где D, T и R обозначают исполнительную потребность, запас времени и резервное время, индексированные идентификатором повторяющейся последовательности и номером фрейма в последовательности;
i
j
• повторяют оценки условий, переставляя местами фреймы Fa и Fb;
• разрешают выполнение задач, если для любой пары (i, j) удовлетворены все три условия [A.1], [B.1] и [C.1].
Согласно варианту осуществления, этап проверки содержит следующие этапы:
• если условие [A.1] является ошибочным, оценивают следующие условия:
i
j+1
j
j+2
[A.2] Da ≤ Tb + Rb + Tb
i
j+1
i
j+1
и Da + Db ≤ Ta + Tb
• если условие [B.1] является ошибочным, оценивают следующие условия:
i
j+1
j+1
j+2
[B.2] Da ≤ Tb + Rb + Tb
j
i
j+1
i
j+1
и Db + Da + Db ≤ Ta + Tb
• если условие [C.1] является ошибочным, оценивают следующее условие:
j
i
j
i
i
i-1
[С.2] Db ≤ Ta + min[Tb-Da, Ra, Ra]
• разрешают выполнение задач, если условия [A.1] или [A.2], и [В.1] или [В.2], и [С.1] или [С.2] удовлетворены для любой пары (i,j).
Согласно варианту осуществления, шкалы времени, определяющие продолжительность фреймов, могут изменяться таким образом, что запас времени Т и резервное время R меняются на коэффициент от 1 до za для фреймов Fa и на коэффициент от 1 до zb для фреймов Fb, при этом этап проверки содержит следующие этапы:
• если условие [A.1] является ошибочным, оценивают следующее условие:
i
j+1
j+1
j+2
[A.2] Da ≤ Tb + Rb + Tb
1
j
j
j
i
j+1
i
и min[q(zb⋅(Tb+Rb) + (zb-1)Db),Da] + Db ≤ Ta
1
i
j+1
j
j
где q = (Da-Tb)/(Tb+Rb);
• если условие [B.1] является ошибочным, оценивают следующее условие:
i
j+1
j+1
j+2
[B.2] Da ≤ Tb + Rb + Tb
j
1
j
j
j
i
j+1
i
и Db + min[q(zb⋅Tb + (zb-1)Db) + zb⋅Rb, Da] + Db ≤ Ta
i
j
j+1
j
где q1 = (Da - Rb - Tb)/Tb;
• если условие [C.1] является ошибочным, оценивают следующее условие:
j
i
j
i
i
i-1
[С.2] Db ≤ Ta + min[Tb-Da, Ra, Ra]
• разрешают выполнение задач, если условия [A.1] или [A.2], и [В.1] или [В.2], и [С.1] или [С.2] удовлетворены для любой пары (i,j).
Согласно варианту осуществления, этап проверки содержит следующие этапы:
• если условие [B.1] является ошибочным, перед условием [В.2] оценивают следующее условие:
i
j
j
j+1
[B.1.1] Da ≤ Tb + Rb + Tb
j-1
1
j-1
j-1
j-1
1
i-1
i-2
и Db ≤ T + min[Tb + Db + Rb - T - Da, Ra]
i
j
j+1
j
1
i-1
1
j
i-1
где q1 = (Da - Rb - Tb)/Tb и T = Ta - (1-q)Tb + Ra
• разрешают выполнение задач, если условия [A.1] или [A.2], и [В.1] или [В.2], и [С.1] или [С.2] удовлетворены для любой пары (i,j).
Краткое описание чертежей
Варианты осуществления изложены в нижеследующем описании, представленном в качестве не ограничительного примера со ссылками на следующие прилагаемые фигуры:
Фиг. 1 - пример повторяющейся последовательности фреймов, предназначенной для составления плана задания последовательности задачи.
Фиг. 2 - состав фрейма повторяющейся последовательности и различные возможности запуска операции в фрейме.
Фиг. 3А-3С иллюстрируют различные возможности процесса развертывания с разделением времени двух повторяющихся последовательностей фреймов, при этом на фиг.3С представлена ситуация ошибки.
Фиг. 4А-4С иллюстрируют случаи процесса развертывания с разделением времени двух последовательностей в соответствии с первым предположением в разработке критериев подтверждения состава двух последовательностей.
Фиг. 5А 5В иллюстрируют случаи процесса развертывания с разделением времени двух последовательностей в соответствии с вторым предположением в разработке критериев подтверждения состава двух последовательностей.
Фиг. 6 иллюстрирует случай процесса развертывания с разделением времени двух последовательностей в соответствии с третьим предположением в разработке критериев подтверждения состава двух последовательностей.
Фиг. 7 - пример последовательности фреймов, предназначенной для установления другого условия достоверности в ситуации, показанной на фиг. 5А.
Фиг. 8 - дополнительный случай процесса развертывания двух последовательностей в соответствии с третьим предположением, позволяющих разработать альтернативные условия достоверности.
Описание варианта осуществления изобретения
Реально-временную задачу можно рассматривать как последовательность обработок или исполняемых друг за другом элементарных операций, где каждая операция имеет срок исполнения в шкале времени, связанной с задачей. В критической реально-временной системе сроки являются императивными, то есть операция, превысившая свой срок исполнения, приводит, например, к условию ошибки и к остановке системы. Описанные ниже методы применимы к такой системе и позволяют, несмотря ни на что, повысить уровень эффективности за счет того, что в системе можно выполнять с разделением времени несколько задач, даже имеющих невзаимосвязанные между собой шкалы времени.
На фиг. 1 представлено разложение задачи на повторяющуюся последовательность фреймов RSF, где каждый фрейм F связан с одной последовательной операцией задачи. Задачу выполняют посредством цикличного исполнения повторяющейся последовательности RSF.
На фиг. 2 представлена временная структура фрейма F. Начало фрейма соответствует дате, начиная с которой можно начать операцию. Фрейм определяет конечный срок Е, к которому операция должна завершиться. Предполагается, что операция является атомарной, то есть ее нельзя приостановить для исполнения другой операции. Срок Е может быть отделен от конца фрейма интервалом резервного времени R, который является факультативным, то есть может быть нулевым. Интервал времени D является исполнительной потребностью операции, связанной с фреймом. Исполнительная потребность D соответствует, например, числу циклов тактового генератора процессора, необходимому для исполнения операции, и ее можно выразить в фиксированном времени в зависимости от характеристик процессора целевой системы. Интервал Т соответствует запасу времени между началом фрейма и конечным сроком Е исполнения операции.
Как показано на фиг. 2, операция D может начаться в любой момент между началом фрейма, когда интервал Т разделяет конец операции и конечный срок, и временем Т после начала фрейма, когда операция заканчивается точно в срок Е. Для промежуточных ситуаций qT обозначает интервал между концом операции и конечным сроком при 0≤q≤1, и (1-q)Т обозначает дополнительный интервал между началом фрейма и началом операции.
Сумма резервных интервалов R соответствует, например, времени, которое программист выделяет системе для осуществления не реально-временных операций, таких как вводы/выводы.
Таким образом, две задачи, которые необходимо выполнить с разделением времени на критической реально-временной системе, разбивают на повторяющиеся последовательности фреймов. Чтобы можно было выполнять задачи без помех, последовательности составляют таким образом, чтобы каждую операцию одной последовательности можно было в любой момент выполнить между двумя последовательными операциями другой последовательности, соблюдая при этом условия фреймов обеих последовательностей, то есть конечные сроки и моменты начала фрейма.
На фиг. 3А-3С представлены различные ситуации, которые могут встречаться в процессе развертывания двух последовательностей RSFa и RSFb. Для упрощения пояснений предполагается, что резервные интервалы R являются нулевыми.
1
3
1
1
2
2
3
3
1
1
2
1
1
2
2
Например, на фиг. 3А последовательность RSFa содержит три фрейма Fa-Fa с соответствующими параметрами (Da = 3, Ta = 6), (Da = 4, Ta = 1) и (Da = 1, Ta = 1), где значения времени выражены в нормализованных единицах. Последовательность RSFb начинается спустя 3 единицы после начала фрейма Fa и содержит два фрейма Fb и Fb с соответствующими параметрами (Db = 4, Tb = 5) и (Db = 3, Tb = 4).
1
1
2
1
1
2
1
2
2
2
2
3
3
3
3
3
2
Операция Da начинается спустя одну единицу после начала соответствующего фрейма. В конце операции Da пока нельзя запустить операцию Da, но уже можно запустить операцию Db. В конце операции Db ни одна операция пока не готова для исполнения. Выжидают начала фрейма Fa, в данном случае срок Еа, чтобы начать операцию Da. В конце операции Da операция Db готова для исполнения, но ее нельзя запустить. Действительно, если операцию Db запустить сразу, она закончится точно в срок Еа, поэтому до этого срока нельзя исполнить операцию Da. В этом случае ожидают начало фрейма Fa, чтобы запустить операцию Da. Наконец, после завершения операции Da можно запустить операцию Db.
1
1
2
2
2
На фиг. 3В сохранены те же параметры, за исключением того, что операция Da начинается спустя три единицы после начала фрейма. Операции Db и Da оказываются задержанными на две единицы по сравнению с фиг. 3А, но с соблюдением условий соответствующих фреймов. Операция Da завершается точно в свой срок Еа.
1
1
2
1
1
2
2
На фиг. 3С сохранены те же параметры, за исключением того, что операция Da начинается спустя четыре единицы после начала фрейма. Операции Db и Da оказываются задержанными на три единицы по сравнению с фиг. 3А. Операцию Db можно еще исполнить с соблюдением ее конечного срока Eb, но операция Da нарушает свой срок Ea.
Первым этапом, общим для рассматриваемых в данном случае методов, является составление, - для двух задач, предназначенных для выполнения с разделением времени, - двух повторяющихся последовательностей RSFa и RSFb, которые могут проходить в условиях фиг. 3А или 3В, независимо от временного смещения между моментами начала последовательностей. Это составление является статическим, то есть происходит автономно для программиста.
Второй этап представляет собой проверку совместимости двух любых последовательностей, то есть проверяют, что они могут проходить таким образом, чтобы каждую операцию можно быть исполнять с соблюдением ее условий, как на фиг. 3А и 3В.
Эту проверку совместимости можно осуществлять в инструменте разработки, позволяющем программисту составлять последовательности для последовательных испытаний. Предпочтительно ее осуществляют также непосредственно в самой реально-временной системе при загрузке для исполнения планов задания последовательности, определенных двумя повторяющимися последовательностями. При этом систему можно конфигурировать таким образом, чтобы запрещать запуск, если обнаруживается, что последовательности являются несовместимыми.
Третьим этапом является планирование операций двух последовательностей на реально-временной системе. Как показано на фигурах, недостаточно чередовать операции первой последовательности с операциями второй последовательности или запускать операцию, как только она оказывается готовой к исполнению. Планирование осуществляют в зависимости от следующих случаев, оцениваемых для каждой ключевой даты. Ключевыми датами являются моменты начала фреймов двух последовательностей, конечные сроки и концы операции. Если интервалы резервного времени R (фиг. 2) являются нулевыми, как в представленных примерах, конечные сроки совпадают с началами фрейма. Для данной ключевой даты, связанной с первой из последовательностей, текущий фрейм второй последовательности называют «параллельным фреймом».
1
1
1) Ни одну операцию нельзя запустить. Этот случай возникает, когда одна операция уже находится в ходе исполнения (как в момент конечного срока Еb на фиг. 3А) или в конце операции, которая исполнялась между операцией параллельного фрейма и ее конечным сроком, как в случае операции Db на фиг. 3А.
2
3
2) Можно запустить две операции. Как правило, этот случай возникает, когда начинается фрейм и когда одна операция находится в стадии выжидания в параллельном фрейме, как в момент конечного срока Еа на фиг. 3А и 3В. В этом случае исполняют операцию с самым коротким сроком (Da на фиг. 3А и 3В). Такой случай возникает также, когда два параллельных фрейма начинаются одновременно.
1
1
2
1
2
2
2
2
3) Можно запустить только одну операцию. Как правило, этот случай встречается в конце операции (Da) или в начале фрейма, когда операция параллельного фрейма завершилась (Еа, фиг. 3А). При этом операцию исполняют, только если ее исполнительная потребность меньше или равна времени, оставшемуся до начала следующего параллельного фрейма, увеличенному на запас времени, связанный с этим параллельным фреймом. Например, на фиг. 3А операция Da готова к запуску в срок Еа, до начала фрейма Fb остается 3 единицы, и Тb = 4. Операцию Da запускают, так как Da = 4 < 3 + 4.
2
2
3
3
2
В противном случае выжидают следующую ключевую дату для повторной оценки ситуации. Например, на фиг. 3А операция Db готова к исполнению в конце операции Da. Однако остается одна единица до начала фрейма Fа, и Та = 1, отсюда Db = 3 > 1 + 1.
Далее определим критерии совместимости между двумя любыми повторяющимися последовательностями RSFa и RSFb, используемыми для определения планов задания последовательности для реально-временной системы.
При избыточной проверке совместимости необходимо было бы рассмотреть все возможные комбинации положений операций в их фреймах и все возможные положения одной из последовательностей относительно другой с грануляцией цикла тактового генератора, чтобы оценить, можно ли исполнять параллельные операции в соответствии с заданными требованиями.
i
j
j-1
i
i
j
Такую избыточную проверку трудно осуществить в разумные сроки. Необходимо найти упрощенные критерии, которые можно оценивать «онлайн» на реально-временной системе в момент загрузки планов задания последовательности, сопровождающих исполнительный код задач. Для этого предусматривают три общих предположения позиционирования каждого фрейма одной из последовательностей относительно каждого фрейма другой последовательности. Для каждого предположения проверяют, чтобы операцию рассматриваемого фрейма Fа можно было исполнить в свободный интервал, оставленный параллельными фреймами Fb, Fb,…, перекрывающими фрейм Fа. Оба фрейма Fа и Fb считаются совместимыми, если проверка является удовлетворительной для каждого из трех предположений.
i
j
j
• Предположение (А): рассматриваемый фрейм Fа начинается, тогда как операция Db первого фрейма Fb исполнена.
• Предположение (В): операция первого параллельного фрейма находится в стадии исполнения.
• Предположение (С): операция параллельного фрейма не запущена.
Для каждого предположения определяют критерии, не зависящие от относительного положения фреймов. Для этого оценивают снизу неизвестные интервалы времени, служащие для нахождения свободных промежутков для исполнения операций, и оценивают сверху неизвестные интервалы времени, служащие для проверки соблюдения сроков.
i
j
j
i
j+1
i
j
j
На фиг. 4А-4С представлены примеры фреймов, которые могут служить для разработки критериев совместимости в соответствии с предположением (А). Рассматриваемый фрейм Fа начинается в ходе параллельного фрейма Fb, тогда как операция Db этого параллельного фрейма завершена. Фрейм Fа перекрывает следующий параллельный фрейм Fb. Все, что известно о начале фрейма Fа, это то, что он находится в интервале qTb, следующем за концом операции Db, где 0 ≤ q ≤ 1.
i
j+1
i
j
j
j+1
i
j+1
i
На фиг. 4А фрейм Fазаканчивается перед фреймом Fb. Операцию Da можно было бы запустить сразу по завершении операции Db в интервале qTb + Tb. Однако, поскольку q не известно и является любым, рассматривают наихудший из случаев при q=0, то есть когда операция Da стартует в начале фрейма Fb. Таким образом, операцию Da можно исполнить, если:
i
j+1
Da < Tb. [A.1]
i
i
j+1
j+2
i
j
j+2
j+1
j+2
i
На фиг. 4В операция Da не удовлетворяет условию А.1. Тогда предусматривают исполнение операции Da с перекрыванием фреймов Fb и Fb, то есть фрейм Fа перекрывает все три фрейма от Fb до Fb. Это требует удовлетворения одновременно условия, чтобы сумма интервалов Тb и Тb была гарантированно достаточной, и условия гарантированного соблюдения срока Еа:
i
j+1
j+2
Da ≤ Тb + Тb
И
j
j+1
i
i
i
j
j+1
i
qTb + Db + Da ≤ Da + Тa, то есть qTb + Db ≤ Тa
i
Наихудшим случаем при соблюдении срока является q = 1 с переоценкой левого члена неравенства. Таким образом, срок Еа соблюдается во всех случаях, если:
j
j+1
i
Тb + Db ≤ Тa
Однако было бы нереально предусматривать в одном и том же контексте ситуации наихудшего случая с использованием двух предельных значений одной переменной. В реальности, можно исключить определенный диапазон значений для переменной q, если рассматривать поведение реальной системы в ситуации, представленной на фиг. 4А.
j
i
i
На фиг. 4С показано поведение реальной системы в ситуации фиг. 4А. Поскольку операция Db завершена, система, зная параметры фреймов «онлайн», запускает операцию Da с самого начала фрейма Fа, поскольку:
i
j
j+1
Da ≤ qTb + Тb
то есть если соблюдены условия 3) способа планирования.
1
Обозначим q предельное значение q для достижения равенства в вышеупомянутом неравенстве:
i
1
j+1
1
i
j+1
j
Da ≤ qTbj + Тb, то есть q = (Da - Tb)/ Tb
1
1
Если q ≥ q, то можно с уверенностью сказать, что исполнение на реальной системе происходит в соответствии с фиг. 4С и что нет необходимости рассматривать ситуацию, показанную на фиг. 4В. При этом наихудшим случаем для фиг. 4В является q = q, поэтому:
j
j+1
i
1
i
j+1
j+1
i
i
j+1
i
j+1
qTb + Db ≤ Тa, то есть, если заменить q на его значение, Da - Тb + Db ≤ Тa, или Da + Db ≤ Тa + Тb
1
1
Выражение, используемое для вычисления значения q, не ограничено значением 1. Если оно превышает 1, это не имеет практического смысла. Поэтому потолочным значением для q считается 1.
Следовательно, условиями, вытекающими из ситуации фиг. 4В, являются:
i
j+1
j+2
Da ≤ Тb + Тb
И [A.2]
j
j+1
i
qTb + Db ≤ Тa
i
i
i
Условие А.1 проверяется в ситуации, когда фрейм Fа перекрывает по меньшей мере два последовательных фрейма Fb. Условие А.2 проверяется в ситуации, когда фрейм Fа перекрывает по меньшей мере три последовательных фрейма Fb. Аналогично можно найти условия А.3 и следующие, проверяемые в ситуациях, когда фрейм Fа перекрывает по меньшей мере четыре последовательных фрейма Fb или более, но удовлетворение таких условий становится все менее вероятным. Условия А.1 и А.2 (и, в случае необходимости, А.3 и следующие) являются альтернативными, что есть достаточно, чтобы любое из этих условий проверялось, чтобы можно было продолжить подтверждение других предположений.
i
j
j
j
i
j
На фиг. 5А и 5В представлены примеры фреймов, которые могут служить для разработки критериев совместимости в соответствии с предположением (В). Рассматриваемый фрейм Fа стартует в ходе параллельного фрейма Fb, тогда как операция Db этого параллельного фрейма находится в стадии исполнения. В наихудшем случае, как было указано, операция Db стартует. Ситуации являются аналогичными ситуациям на фиг.4А и 4В за исключением того, что для проверки соблюдения срока Еа учитывают время Db.
В соответствии с фиг. 5А:
i
j+1
i
j
i
i
i
j
i
Da ≤ Тb и для соблюдения срока Еа: Db + Da ≤ Da + Тa, то есть Db ≤ Тa
Следовательно, условиями, вытекающими из ситуации на фиг. 4В, являются:
i
j+1
Da ≤ Тb
И [В.1]
j
i
Db ≤ Тa
В соответствии с фиг. 5В и следуя такому же рассуждению, что и для фиг. 4В, получаем:
i
j+1
j+2
Da ≤ Тb + Тb
И [В.2]
j
j
j+1
i
Db + qTb + Db ≤ Тa
i
i
i
Как и для условия А.1, условие В.1 проверяется в ситуации, когда фрейм Fа перекрывает по меньшей мере два последовательных фрейма Fb. Условие В.2 проверяется в ситуации, когда фрейм Fа перекрывает по меньшей мере три последовательных фрейма Fb. Аналогично можно найти условия В.3 и следующие, проверяемые в ситуациях, когда фрейм Fа перекрывает по меньшей мере четыре последовательных фрейма Fb или более, но удовлетворение таких условий становится все менее вероятным. Условия В.1 и В.2 (и, в случае необходимости, В.3 и следующие) являются альтернативными, что есть достаточно, чтобы любое из этих условий проверялось, чтобы можно было продолжить подтверждение других предположений.
j
i
j
j
i
j
На фиг. 6 представлен пример фреймов, которые могут служить для разработки критериев совместимости в соответствии с предположением (С). В рамках предположения (С) считается, что операция Db еще не исполнена. Если конечный срок фрейма Fа наступает после конечного срока фрейма Fb, встречаются те же ситуации, что и ситуации на фиг. 5А и 5В, когда операция Db как раз только начинается. Таким образом, в рамках предположения (С) рассматривают только случай, когда конечный срок фрейма Fа наступает до конечного срока фрейма Fb.
i
j
i
j
i-1
i
i
i
j
i
i
j
Обе операции Da и Db готовы для исполнения в начале фрейма Fа. Можно предположить, что операция Db не была запущена в начале своего фрейма, так как условия 3) планирования не были соблюдены, например, как было указано выше, когда операция Da завершается в свой срок в начале фрейма Fа. Поскольку срок Еа является более коротким, сначала запускают операцию Da. Операцию Db запускают по окончании операции Da. В наихудшем случае в пределах предположения (С) сроки фреймов Fа и Fb совпадают, и в этом случае получаем:
j
i
Db ≤ Та [C.1]
j
i
i
j
i
i
i
Это же неравенство получаем, предположив, что операция Db стартует в начале фрейма Fа, хотя способ планирования этого не предусматривает. Чтобы операция Da завершилась до ее срока исполнения, проверяют Db + Da ≤ Da + Тa, то есть неравенство, которое было указано выше.
i
j
i
j
j
i
j
Таким образом, каждый фрейм Fа сравнивают с каждым фреймом Fb, проверяя, чтобы соблюдались сроки фреймов Fа, но не проверяя соблюдение сроков фреймов Fb. Это является первым прогоном проверки. Второй прогон проверки для дополнения проверки состоит в этом случае в повторении вышеупомянутых операций, сравнивая каждый фрейм Fbс каждым фреймом Fа и проверяя тем самым соблюдение сроков фреймов Fb.
i
j
j+3
Проверку совместимости двух повторяющихся последовательностей RSFa и RSFb, соответственно содержащих Na и Nb фреймов, можно выразить в виде нижеследующего псевдокода. В этом псевдокоде альтернативные условия сгруппированы в выражениях min(x,y) с левой стороны неравенств и max(x,y) с правой стороны неравенств, а необходимые условия сгруппированы в выражениях min(x,y) с правой стороны неравенств и max(x,y) с левой стороны неравенств. Предусмотрены вышеупомянутые условия А.3 и В.3, чтобы учитывать возможность того, что фрейм Fа может перекрыть четыре фрейма от Fb до Fb. Разумеется операции на индексах i и j осуществляют по модулю максимального значения индекса (Na для i и Nb для j), так как последовательности фреймов можно повторять бесконечно.
Для каждого i между 0 и Na-1 рассматривают:
Для каждого j между 0 и Nb-1 рассматривают:
[A.1]
если Da
≤ Tb
, то продолжают при [В.1]
i
j
+1
[A.2]
q
: = (Da
- Тb
)/ Тb
1
i
j
+1
j
если q
> 1 или Тb
= 0, то q
: = 1
1
j
1
если Da
≤ Tb
+ Tb
i
j
+1
j
+2
и q
Tb
+ Db
≤ Та
1
j
j
+1
i
то продолжают при [В.1]
[A.3]
если Da
≤ Tb
+ Tb
i
j
+2
j
+3
и q
Tb
+ Db
+ Db
+ min[Tb
, Da
] ≤ Та
1
j
j
+1
j
+2
j
+1
i
i
то продолжают при [В.1]
неудачное завершение цикла
[В.1]
если Da
≤ Tb
i
j
+1
и Db
≤ Та
j
i
то продолжают при [D]
[В.1.1]
q
: = (Da
- Тb
)/ Тb
1
i
j
+1
j
если q
> 1 или Тb
= 0, то q
: = 1 и продолжают при [В.2]
1
j
1
Т
: Та
- (1 - q
) Tb
1
i
-1
1
j
если Db
≤ Т
j
-1
1
то продолжают при [С.1]
[В.2]
если Da
≤ Tb
+ Tb
i
j
+1
j
+2
и Db
+ qTb
+ Db
≤ Та
j
j
j
+1
i
то продолжают при [С.1]
[В.3]
если Da
≤ Tb
+ Tb
i
j
+2
j
+3
и Db
+ q
Tb
+ Db
min[Tb
, Da
] + Db
≤ Та
j
1
j
j
+1
j
+1
i
j
+2
i
то продолжают при [С.1]
неудачное завершение цикла
[С.1]
если Db
≤ Та
j
i
то продолжают при [D]
неудачное завершение цикла
[D] Переходят к следующему j
Переходят к следующему i
Для дополнения проверки, как было указано выше, этот цикл повторяют, поменяв местами Fa и Fb.
В этом цикле, согласно варианту, по сравнению с тем, что было изложен выше, прежде чем перейти к оценке условия В.2, оценивают условие В.1.1.
i
j
j+1
j
i-1
j-1
1
i
j
j+1
i
На фиг. 7 представлен пример последовательности фреймов, служащей для определения условия В.1.1. Фреймы Fа и Fb находятся в тех же условиях, что и на фиг. 4А, но вместо запуска операции в начале фрейма Fb, предполагается, что ее можно запустить сразу после операции Db, и в предыдущих фреймах Fа и Fb выявляют общие условия, которые позволяют это сделать при q = q. Условие В.1.1, как и условие В.1, основано на предположении, что фрейм Fа перекрывает два фрейма (Fb и Fb), что соответствует более вероятной ситуации, которую можно встретить, чем ситуацию, в которой фрейм Fа перекрывает три фрейма или более.
Как было указано выше, фреймы могут включать в себя резервное время R, которое может брать система для осуществления не реально-временных задач. Такое резервное время можно брать для исполнения реально-временных операций. Его добавляют к запасам времени Т одной последовательности, чтобы способствовать исполнению операций D другой последовательности, но оно может ужесточить условия соблюдения сроков.
Не равные нулю значения резервного времени R могут, в частности, смягчить условие С.1.
j
i
j
i
i
i
j
i
i-1
i-1
i-1
j
i
На фиг. 8 представлен пример последовательности фреймов, служащей для определения смягченного условия в случае, когда условие С.1 не удовлетворено, то есть если Db > Тa. В рамках предположения С предполагают, что операция Db еще не запущена в начале фрейма Fа. В самом начале фрейма Fа запускают операцию Da, которая имеет самый короткий конечный срок исполнения. Фрейм Fb начинается до фрейма Fа, предположительно во время интервала Ra фрейма Fа. Обозначим kRa интервал между началом фрейма Fb и началом фрейма Fа, при 0 ≤ k ≤ 1.
j
j
Если операция Db не была запланирована в начале фрейма Fb, это значит, что:
j
i-1
i
Db > kRa + Tа.
1
j
1
i-1
i
1
i-1
1
j
i
1
Обозначим k предельное значение k, при котором Db = kRa + Tа, то есть k=(Dbj-Tаi)/Ra. Если k > k, операцию Db можно с уверенностью планировать до начала фрейма Fа, и этот случай не рассматривается, так как он не соответствует предположению С. В этом случае рассматривают только значения k в пределах от 0 до k.
i
i
j
i-1
1
Чтобы можно было исполнить Da, необходимо, чтобы Da ≤ Tb - kRa. Наихудшим случаем является k = k, когда получаем:
i
j
1
i-1
1
Da ≤ Tb - kRa, то есть при замене k на его значение:
i
j
j
i
Da ≤ Tb - (Db - Tа), или
j
i
j
i
Db ≤ Tа + Tb - Da
1
Коэффициент k не превышает 1, что можно выразить, как:
j
i
i-1
Db - Tа ≤ Ra, то есть
j
i
i-1
Db ≤ Tа + Ra
i+1
j
i+1
В конечном итоге, чтобы не влиять на исполнение операции Da, операция Db не должна переходить на фрейм Fа. Это соблюдается, если:
j
i
i
Db ≤ Tа + Ra.
Таким образом, подходим к следующему условию, которое является альтернативным условию С.1:
j
i
j
i
Db ≤ Tа + Tb - Da
И
j
i
i-1
Db ≤ Tа + Ra [С.2]
И
j
i
i
Db ≤ Tа + Ra
Следующий псевдокод учитывает резервы времени R.
Для каждого i между 0 и Na-1 рассматривают:
Для каждого j между 0 и Nb-1 рассматривают:
[A.1]
если Da
≤ Tb
, то продолжают при [В.1]
i
j
+1
[A.2]
q
: = (Da
- Тb
)/ Тb
+ Rb
)
1
i
j
+1
j
j
если q
> 1 или Тb
+ Rb
= 0, то q
: = 1
1
j
j
1
если Da
≤ Tb
+ Rb
+ Tb
i
j
+1
j
+1
j
+2
и q
(Tb
+ Rb
) + Db
≤ Та
1
j
j
j
+1
i
то продолжают при [В.1]
[A.3]
если Da
≤ Tb
+ Rb
+ Tb
i
j
+2
j
+2
j
+3
и Db
+ q
(Tb
+ Rb
) + Db
+ min[Tb
+ Rb
, Da
] ≤ Та
j
+1
1
j
j
+1
j
+2
j
+1
j
+1
i
i
то продолжают при [В.1]
неудачное завершение цикла
[В.1]
если Da
≤ Rb
+ Tb
i
j
j
+1
и Db
≤ Та
j
i
то продолжают при [C.2]
q
:= (Da
- Rb
- Tb
)/ Tb
1
i
j
j
+1
j
если q
> 1 или Tb
= 0, то q
:= 1 и продолжают при [В.2]
1
j
1
[В.1.1]
Т
:= Tа
- (1 - q
) Tb
+ Rа
1
i
-1
1
j
i
-1
если Db
≤ Т
+ min[Tb
+ Db
+ Rb
- T
- Da
, Ra
)
j-1
1
j-1
j-1
j-1
1
i-1
1-2
то продолжают при [С.1]
[В.1.2]
если Db
+ Rb
≤ Т
j
-1
j
-1
1
и Da
≤ Tb
+ Rb
+ Tb
i
-1
j
-2
j
-2
j
-1
и Tb
+ Db
+ Rb
+ Tb
+ Db
+ Rb
≤ Ra
+ T
+ Da
j-2
j-2
j-2
j-1
j-1
j-1
i-2
1
i-1
то продолжают при [С.1]
[В.2]
если Da
≤ Tb
+ Rb
+ Tb
i
j
+1
j
+1
j
+2
и Db
+ q
Tb
+ Rb
+ Db
≤ Tа
j
1
j
j
j
+1
i
то продолжают при [С.1]
[В.3]
если Da
≤ Tb
+ Rb
+ Tb
i
j
+2
j
+2
j
+3
и Db
+ q
Tb
+ Rb
+ Db
+ min[Tb
+ Rb
, Da
] + Db
≤ Tа
j
1
j
j
j
+1
j
+1
j
+1
i
j
+2
i
то продолжают при [С.1]
неудачное завершение цикла
[С.1]
если Db
≤ Та
j
i
то продолжают при [D]
[С.2]
если Db
≤ Tа
+ min[Tb
-Da
, Ra
, Ra
]
j
i
j
i
i
i-1
то продолжают при [D]
неудачное завершение цикла
[D] Переходят к следующему j
Переходят к следующему i
i-2
j-2
Условие В.1.2, которое появляется в этом псевдокоде, устанавливают так же, как и условие В.1.1, продолжив исследования на фреймах Fа и Fb.
До сих пор предполагалось, что шкалы времени, позволяющие упорядочить во времени обе задачи, были изохронными, то есть время интервалов одной из последовательностей не менялось относительно времени интервалов другой последовательности. На практике иногда приходится составлять две задачи с использованием не взаимосвязанных шкал времени, таких как задачи, связанные с положениями подвижных элементов, движущихся с переменным скоростями.
Для рассмотрения этого случая вводят коэффициент изменчивости z ≥ 1 для каждой повторяющейся последовательности, соответственно za и zb для последовательностей RSFa и RSFb. Коэффициенты za и zb являются фиксированными и выражают максимальное замедление, которым подвергаются интервалы Т и R в обеих последовательностях. Предположив, что обозначения, используемые в предыдущих отношениях, выражают минимальные значения интервалов, каждое из значений Т и R может принимать два значения: Т или zT и R или zR. Исполнительные потребности D являются фиксированными, так как они зависят только от тактового генератора системы.
В предыдущих отношениях, если интервал служит для нахождения свободного промежутка для исполнения операции, сохраняют его недооцененное значение Т или R. Если интервал служит для проверки соблюдения срока, берут его переоцененное значение zT или zR. При этом получают следующий псевдокод:
Для каждого i между 0 и Na-1 рассматривают:
Для каждого j между 0 и Nb-1 рассматривают:
[A.1]
если Da
≤ Tb
, то продолжают при [В.1]
i
j
+1
[A.2]
q
: = (Da
- Тb
)/ Тb
+ Rb
)
1
i
j
+1
j
j
если q
> 1 или Тb
+ Rb
= 0, то q
: = 1
1
j
j
1
если Da
≤ Tb
+ Rb
+ Tb
i
j
+1
j
+1
j
+2
и min[ q
(zb⋅(Tb
+ Rb
) + (zb-1) Db
), Da
] + Db
≤ Та
1
j
j
j
i
j
+1
i
то продолжают при [В.1]
[A.3]
если Da
≤ Tb
+ Rb
+ Tb
i
j
+2
j
+2
j
+3
и Db
+ min[ q
(zb⋅(Tb
+ Rb
) + (zb-1) Db
, Da
] + Db
+ min[ zb⋅(Tb
+ Rb
)
j
+1
1
j
j
j
i
j
+2
j
+1
j
+1
+ (zb-1) Db
, Da
] ≤ Та
j
+1
i
i
то продолжают при [В.1]
неудачное завершение цикла
[В.1]
если Da
≤ Rb
+ Tb
i
j
j
+1
и Db
≤ Та
j
i
то продолжают при [C.2]
[В.1.1]
q
:= (Da
- Rb
- Tb
)/ Tb
1
i
j
j
+1
j
если q
> 1 или Tb
= 0, то q
:= 1 и продолжают при [В.2]
1
j
1
Т
:= Tа
- (1 - q
) Tb
+ Rа
1
i
-1
1
j
i
-1
если Db
≤ Т
+ min[Tb
+ Db
+ Rb
- T
- Da
, Ra
)
j-1
1
j-1
j-1
j-1
1
i-1
1-2
то продолжают при [С.1]
[В.1.2]
если Db
+ zb⋅Rb
≤ Т
j
-1
j
-1
1
и Da
≤ Tb
+ Rb
+ Tb
i
-1
j
-2
j
-2
j
-1
и zb⋅(Tb
+ Db
+ Rb
+ Tb
+ Db
+ Rb
) ≤ Ra
+ T
+ Da
j
-2
j
-2
j
-2
j
-1
j
-1
j
-1
i
-2
1
i
-1
то продолжают при [С.1]
[В.2]
если Da
≤ Tb
+ Rb
+ Tb
i
j
+1
j
+1
j
+2
и Db
+ min[ q
(zb⋅Tb
+ (zb-1) Db
) + zb⋅Rb
, Da
] + Db
≤ Tа
j
1
j
j
j
i
j
-1
i
то продолжают при [С.1]
[В.3]
если Da
≤ Tb
+ Rb
+ Tb
i
j
+2
j
+2
j
-3
и Db
+ min[ q
(zb⋅Tb
+ (zb-1) Db
)+ zb⋅Rb
, Da
] + Db
+ min[zb⋅(Tb
+ Rb
)
j
1
j
j
j
i
j
+1
j
+1
j
+1
+ (zb-1) Db
, Da
] + Db
≤ Tа
j
+1
i
j
+2
i
то продолжают при [С.1]
неудачное завершение цикла
[С.1]
если Db
≤ Та
j
i
то продолжают при [D]
[С.2]
если Db
≤ Tа
+ min[Tb
- Da
, Ra
, Ra
]
j
i
j
i
i
i+1
то продолжают при [D]
неудачное завершение цикла
[D] Переходят к следующему j
Переходят к следующему i
Для случая 3) описанного выше способа планирования рассматриваемый запас времени является минимальным значением, то есть Т, а не zT.
Представленные принципы были описаны в отношении двух выполняемых с разделением времени задач, но их можно применять для любого числа задач. Действительно, описанный способ позволяет на практике составлять единый план задания последовательности для двух совместимых задач. Полученный таким образом план задания последовательности можно составить опять, используя те же методы, вместе с планом задания последовательности третьей совместимой задачи, и так далее.