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

Изобретение относится к области вычислительной техники. Технический результат заключается в возможности исполнения без помех двух задач с разделением времени, даже если шкалы времени двух задач являются разными. Раскрыт способ выполнения без помех двух задач с разделением времени, даже если шкалы времени двух задач являются разными, содержащий этапы, на которых: каждую задачу автономно раскладывают на соответствующую повторяющуюся последовательность последовательных неоднородных фреймов на шкале времени, связанной с соответствующей задачей, причем каждый фрейм связан с элементарной операцией, имеющей одну исполнительную потребность, и определяет дату начала, после которой операция начинается, дату конечного срока, до которой операция завершается, и запас времени, равный длительности фрейма за вычетом исполнительской потребности элементарной операции; для каждого текущего фрейма повторяющихся последовательностей первой из двух задач выполняют этап проверки, содержащий подэтапы, на которых: определяют группу последовательных фреймов повторяющейся последовательности второй из двух задач, причем каждый фрейм указанной группы перекрывает текущий фрейм, и проверяют, что элементарная операция текущего фрейма может быть исполнена между двумя последовательными элементарными операциями указанной группы последовательных фреймов, соблюдая при этом даты начала и конечного срока элементарной операции текущего фрейма и элементарных операций указанной группы последовательных фреймов; если на этапе проверки определено, что элементарная операция текущего время может быть исполнена, разрешают выполнение обеих задач и элементарные операции обеих задач планируют в зависимости от следующих случаев, оцениваемых по каждой дате из группы ключевых дат, содержащих сроки исполнения, даты начала и концы элементарных операций: если можно запустить элементарную операцию каждой задачи, выполняют ту элементарную операцию, которая имеет более короткий срок исполнения; и если можно запустить элементарную операцию только одной из двух задач, ее выполняют только в том случае, если ее исполнительная потребность меньше времени, остающегося до даты начала следующего фрейма повторяющейся последовательности другой из двух задач и увеличенного на запас времени, связанный с указанным следующим фреймом. 2 н. и 8 з.п. ф-лы, 13 ил.

 

Область техники

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

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

В критических реально-временных системах, то есть в системах, которые не могут допускать никакого нарушения сроков из-за задержки в выполнении операции, задачи часто выполняют в соответствии с методами статического планирования. При этом автономно составляют статическое временное распределение потребности в использовании исполнительных ресурсов, что позволяет выявить временную независимость задач между собой в том, что касается использования ресурсов и, в частности, процессора. Такой подход описан, например, в статье [“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].

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

Раскрытие изобретения

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

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

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

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

Согласно варианту осуществления, этап проверки содержит следующие этапы:

• для каждого фрейма Fa_i первой повторяющейся последовательности оценивают следующие условия для каждого фрейма Fb_j второй повторяющейся последовательности:

[A.1] Da_i ≤ Tb_j+1

[B.1] Da_i ≤ Rb_j +Tb_j+1 и Db_j ≤ Ta_i, и

[C.1] Db_j ≤ Ta_i,

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

• повторяют оценки условий, переставляя местами фреймы Fa_i и Fb_j;

• разрешают выполнение задач, если для любой пары (i, j) удовлетворены все три условия [A.1], [B.1] и [C.1].

Согласно варианту осуществления, этап проверки содержит следующие этапы:

• если условие [A.1] является ошибочным, оценивают следующие условия:

[A.2] Da_i ≤ Tb_j+1 + Rb_j + Tb_j+2

и Da_i + Db_j+1 ≤ Ta_i + Tb_j+1

• если условие [B.1] является ошибочным, оценивают следующие условия:

[B.2] Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и Db_j + Da_i + Db_j+1 ≤ Ta_i + Tb_j+1

• если условие [C.1] является ошибочным, оценивают следующее условие:

[С.2] Db_j ≤ Ta_i + min[Tb_j-Da_i, Ra_i, Ra_i-1]

• разрешают выполнение задач, если условия [A.1] или [A.2], и [В.1] или [В.2], и [С.1] или [С.2] удовлетворены для любой пары (i,j).

Согласно варианту осуществления, шкалы времени, определяющие продолжительность фреймов, могут изменяться таким образом, что запас времени Т и резервное время R меняются на коэффициент от 1 до za для фреймов Fa и на коэффициент от 1 до zb для фреймов Fb, при этом этап проверки содержит следующие этапы:

• если условие [A.1] является ошибочным, оценивают следующее условие:

[A.2] Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и min[q₁(zb⋅(Tb_j+Rb_j) + (zb-1)Db_j),Da_i] + Db_j+1 ≤ Ta_i

где q₁ = (Da_i-Tb_j+1)/(Tb_j+Rb_j);

• если условие [B.1] является ошибочным, оценивают следующее условие:

[B.2] Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и Db_j + min[q₁(zb⋅Tb_j + (zb-1)Db_j) + zb⋅Rb_j, Da_i] + Db_j+1 ≤ Ta_i

где q1 = (Da_i - Rb_j - Tb_j+1)/Tb_j;

• если условие [C.1] является ошибочным, оценивают следующее условие:

[С.2] Db_j ≤ Ta_i + min[Tb_j-Da_i, Ra_i, Ra_i-1]

• разрешают выполнение задач, если условия [A.1] или [A.2], и [В.1] или [В.2], и [С.1] или [С.2] удовлетворены для любой пары (i,j).

Согласно варианту осуществления, этап проверки содержит следующие этапы:

• если условие [B.1] является ошибочным, перед условием [В.2] оценивают следующее условие:

[B.1.1] Da_i ≤ Tb_j + Rb_j + Tb_j+1

и Db_j-1 ≤ T₁ + min[Tb_j-1 + Db_j-1 + Rb_j-1 - T₁ - Da_i-1, Ra_i-2]

где q1 = (Da_i - Rb_j - Tb_j+1)/Tb_j и T₁ = Ta_i-1 - (1-q₁)Tb_j + Ra_i-1

• разрешают выполнение задач, если условия [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 являются нулевыми.

Например, на фиг. 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).

Операция Da₁ начинается спустя одну единицу после начала соответствующего фрейма. В конце операции Da₁ пока нельзя запустить операцию Da₂, но уже можно запустить операцию Db₁. В конце операции Db₁ ни одна операция пока не готова для исполнения. Выжидают начала фрейма Fa₂, в данном случае срок Еа₁, чтобы начать операцию Da₂. В конце операции Da₂ операция Db₂ готова для исполнения, но ее нельзя запустить. Действительно, если операцию Db₂ запустить сразу, она закончится точно в срок Еа₃, поэтому до этого срока нельзя исполнить операцию Da₃. В этом случае ожидают начало фрейма Fa₃, чтобы запустить операцию Da₃. Наконец, после завершения операции Da₃ можно запустить операцию Db₂.

На фиг. 3В сохранены те же параметры, за исключением того, что операция Da₁ начинается спустя три единицы после начала фрейма. Операции Db₁ и Da₂ оказываются задержанными на две единицы по сравнению с фиг. 3А, но с соблюдением условий соответствующих фреймов. Операция Da₂ завершается точно в свой срок Еа₂.

На фиг. 3С сохранены те же параметры, за исключением того, что операция Da₁ начинается спустя четыре единицы после начала фрейма. Операции Db₁ и Da₂ оказываются задержанными на три единицы по сравнению с фиг. 3А. Операцию Db₁ можно еще исполнить с соблюдением ее конечного срока Eb₁, но операция Da₂ нарушает свой срок Ea₂.

Первым этапом, общим для рассматриваемых в данном случае методов, является составление, - для двух задач, предназначенных для выполнения с разделением времени, - двух повторяющихся последовательностей RSFa и RSFb, которые могут проходить в условиях фиг. 3А или 3В, независимо от временного смещения между моментами начала последовательностей. Это составление является статическим, то есть происходит автономно для программиста.

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

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

Третьим этапом является планирование операций двух последовательностей на реально-временной системе. Как показано на фигурах, недостаточно чередовать операции первой последовательности с операциями второй последовательности или запускать операцию, как только она оказывается готовой к исполнению. Планирование осуществляют в зависимости от следующих случаев, оцениваемых для каждой ключевой даты. Ключевыми датами являются моменты начала фреймов двух последовательностей, конечные сроки и концы операции. Если интервалы резервного времени R (фиг. 2) являются нулевыми, как в представленных примерах, конечные сроки совпадают с началами фрейма. Для данной ключевой даты, связанной с первой из последовательностей, текущий фрейм второй последовательности называют «параллельным фреймом».

1) Ни одну операцию нельзя запустить. Этот случай возникает, когда одна операция уже находится в ходе исполнения (как в момент конечного срока Еb₁ на фиг. 3А) или в конце операции, которая исполнялась между операцией параллельного фрейма и ее конечным сроком, как в случае операции Db₁ на фиг. 3А.

2) Можно запустить две операции. Как правило, этот случай возникает, когда начинается фрейм и когда одна операция находится в стадии выжидания в параллельном фрейме, как в момент конечного срока Еа₂ на фиг. 3А и 3В. В этом случае исполняют операцию с самым коротким сроком (Da₃ на фиг. 3А и 3В). Такой случай возникает также, когда два параллельных фрейма начинаются одновременно.

3) Можно запустить только одну операцию. Как правило, этот случай встречается в конце операции (Da₁) или в начале фрейма, когда операция параллельного фрейма завершилась (Еа₁, фиг. 3А). При этом операцию исполняют, только если ее исполнительная потребность меньше или равна времени, оставшемуся до начала следующего параллельного фрейма, увеличенному на запас времени, связанный с этим параллельным фреймом. Например, на фиг. 3А операция Da₂ готова к запуску в срок Еа₁, до начала фрейма Fb₂ остается 3 единицы, и Тb₂ = 4. Операцию Da₂ запускают, так как Da₂ = 4 < 3 + 4.

В противном случае выжидают следующую ключевую дату для повторной оценки ситуации. Например, на фиг. 3А операция Db₂ готова к исполнению в конце операции Da₂. Однако остается одна единица до начала фрейма Fа₃, и Та₃ = 1, отсюда Db₂ = 3 > 1 + 1.

Далее определим критерии совместимости между двумя любыми повторяющимися последовательностями RSFa и RSFb, используемыми для определения планов задания последовательности для реально-временной системы.

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

Такую избыточную проверку трудно осуществить в разумные сроки. Необходимо найти упрощенные критерии, которые можно оценивать «онлайн» на реально-временной системе в момент загрузки планов задания последовательности, сопровождающих исполнительный код задач. Для этого предусматривают три общих предположения позиционирования каждого фрейма одной из последовательностей относительно каждого фрейма другой последовательности. Для каждого предположения проверяют, чтобы операцию рассматриваемого фрейма Fа_i можно было исполнить в свободный интервал, оставленный параллельными фреймами Fb_j, Fb_j-1,…, перекрывающими фрейм Fа_i. Оба фрейма Fа_i и Fb_j считаются совместимыми, если проверка является удовлетворительной для каждого из трех предположений.

• Предположение (А): рассматриваемый фрейм Fа_i начинается, тогда как операция Db_j первого фрейма Fb_j исполнена.

• Предположение (В): операция первого параллельного фрейма находится в стадии исполнения.

• Предположение (С): операция параллельного фрейма не запущена.

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

На фиг. 4А-4С представлены примеры фреймов, которые могут служить для разработки критериев совместимости в соответствии с предположением (А). Рассматриваемый фрейм Fа_i начинается в ходе параллельного фрейма Fb_j, тогда как операция Db_j этого параллельного фрейма завершена. Фрейм Fа_i перекрывает следующий параллельный фрейм Fb_j+1. Все, что известно о начале фрейма Fа_i, это то, что он находится в интервале qTb_j, следующем за концом операции Db_j, где 0 ≤ q ≤ 1.

На фиг. 4А фрейм Fа_i заканчивается перед фреймом Fb_j+1. Операцию Da_i можно было бы запустить сразу по завершении операции Db_j в интервале qTb_j + Tb_j+1. Однако, поскольку q не известно и является любым, рассматривают наихудший из случаев при q=0, то есть когда операция Da_i стартует в начале фрейма Fb_j+1. Таким образом, операцию Da_i можно исполнить, если:

Da_i < Tb_j+1. [A.1]

На фиг. 4В операция Da_i не удовлетворяет условию А.1. Тогда предусматривают исполнение операции Da_i с перекрыванием фреймов Fb_j+1 и Fb_j+2, то есть фрейм Fа_i перекрывает все три фрейма от Fb_j до Fb_j+2. Это требует удовлетворения одновременно условия, чтобы сумма интервалов Тb_j+1 и Тb_j+2 была гарантированно достаточной, и условия гарантированного соблюдения срока Еа_i:

Da_i ≤ Тb_j+1 + Тb_j+2

И

qTb_j + Db_j+1 + Da_i ≤ Da_i + Тa_i, то есть qTb_j + Db_j+1 ≤ Тa_i

Наихудшим случаем при соблюдении срока является q = 1 с переоценкой левого члена неравенства. Таким образом, срок Еа_i соблюдается во всех случаях, если:

Тb_j + Db_j+1 ≤ Тa_i

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

На фиг. 4С показано поведение реальной системы в ситуации фиг. 4А. Поскольку операция Db_j завершена, система, зная параметры фреймов «онлайн», запускает операцию Da_i с самого начала фрейма Fа_i, поскольку:

Da_i ≤ qTb_j + Тb_j+1

то есть если соблюдены условия 3) способа планирования.

Обозначим q₁ предельное значение q для достижения равенства в вышеупомянутом неравенстве:

Da_i ≤ q₁Tbj + Тb_j+1, то есть q₁ = (Da_i - Tb_j+1)/ Tb_j

Если q ≥ q₁, то можно с уверенностью сказать, что исполнение на реальной системе происходит в соответствии с фиг. 4С и что нет необходимости рассматривать ситуацию, показанную на фиг. 4В. При этом наихудшим случаем для фиг. 4В является q = q₁, поэтому:

qTb_j + Db_j+1 ≤ Тa_i, то есть, если заменить q₁ на его значение, Da_i - Тb_j+1 + Db_j+1 ≤ Тa_i, или Da_i + Db_j+1 ≤ Тa_i + Тb_j+1

Выражение, используемое для вычисления значения q₁, не ограничено значением 1. Если оно превышает 1, это не имеет практического смысла. Поэтому потолочным значением для q₁ считается 1.

Следовательно, условиями, вытекающими из ситуации фиг. 4В, являются:

Da_i ≤ Тb_j+1 + Тb_j+2

И [A.2]

qTb_j + Db_j+1 ≤ Тa_i

Условие А.1 проверяется в ситуации, когда фрейм Fа_i перекрывает по меньшей мере два последовательных фрейма Fb. Условие А.2 проверяется в ситуации, когда фрейм Fа_i перекрывает по меньшей мере три последовательных фрейма Fb. Аналогично можно найти условия А.3 и следующие, проверяемые в ситуациях, когда фрейм Fа_i перекрывает по меньшей мере четыре последовательных фрейма Fb или более, но удовлетворение таких условий становится все менее вероятным. Условия А.1 и А.2 (и, в случае необходимости, А.3 и следующие) являются альтернативными, что есть достаточно, чтобы любое из этих условий проверялось, чтобы можно было продолжить подтверждение других предположений.

На фиг. 5А и 5В представлены примеры фреймов, которые могут служить для разработки критериев совместимости в соответствии с предположением (В). Рассматриваемый фрейм Fа_i стартует в ходе параллельного фрейма Fb_j, тогда как операция Db_j этого параллельного фрейма находится в стадии исполнения. В наихудшем случае, как было указано, операция Db_j стартует. Ситуации являются аналогичными ситуациям на фиг.4А и 4В за исключением того, что для проверки соблюдения срока Еа_i учитывают время Db_j.

В соответствии с фиг. 5А:

Da_i ≤ Тb_j+1 и для соблюдения срока Еа_i: Db_j + Da_i ≤ Da_i + Тa_i, то есть Db_j ≤ Тa_i

Следовательно, условиями, вытекающими из ситуации на фиг. 4В, являются:

Da_i ≤ Тb_j+1

И [В.1]

Db_j ≤ Тa_i

В соответствии с фиг. 5В и следуя такому же рассуждению, что и для фиг. 4В, получаем:

Da_i ≤ Тb_j+1 + Тb_j+2

И [В.2]

Db_j + qTb_j + Db_j+1 ≤ Тa_i

Как и для условия А.1, условие В.1 проверяется в ситуации, когда фрейм Fа_i перекрывает по меньшей мере два последовательных фрейма Fb. Условие В.2 проверяется в ситуации, когда фрейм Fа_i перекрывает по меньшей мере три последовательных фрейма Fb. Аналогично можно найти условия В.3 и следующие, проверяемые в ситуациях, когда фрейм Fа_i перекрывает по меньшей мере четыре последовательных фрейма Fb или более, но удовлетворение таких условий становится все менее вероятным. Условия В.1 и В.2 (и, в случае необходимости, В.3 и следующие) являются альтернативными, что есть достаточно, чтобы любое из этих условий проверялось, чтобы можно было продолжить подтверждение других предположений.

На фиг. 6 представлен пример фреймов, которые могут служить для разработки критериев совместимости в соответствии с предположением (С). В рамках предположения (С) считается, что операция Db_j еще не исполнена. Если конечный срок фрейма Fа_i наступает после конечного срока фрейма Fb_j, встречаются те же ситуации, что и ситуации на фиг. 5А и 5В, когда операция Db_j как раз только начинается. Таким образом, в рамках предположения (С) рассматривают только случай, когда конечный срок фрейма Fа_i наступает до конечного срока фрейма Fb_j.

Обе операции Da_i и Db_j готовы для исполнения в начале фрейма Fа_i. Можно предположить, что операция Db_j не была запущена в начале своего фрейма, так как условия 3) планирования не были соблюдены, например, как было указано выше, когда операция Da_i-1 завершается в свой срок в начале фрейма Fа_i. Поскольку срок Еа_i является более коротким, сначала запускают операцию Da_i. Операцию Db_j запускают по окончании операции Da_i. В наихудшем случае в пределах предположения (С) сроки фреймов Fа_i и Fb_j совпадают, и в этом случае получаем:

Db_j ≤ Та_i [C.1]

Это же неравенство получаем, предположив, что операция Db_j стартует в начале фрейма Fа_i, хотя способ планирования этого не предусматривает. Чтобы операция Da_i завершилась до ее срока исполнения, проверяют Db_j + Da_i ≤ Da_i + Тa_i, то есть неравенство, которое было указано выше.

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

Проверку совместимости двух повторяющихся последовательностей RSFa и RSFb, соответственно содержащих Na и Nb фреймов, можно выразить в виде нижеследующего псевдокода. В этом псевдокоде альтернативные условия сгруппированы в выражениях min(x,y) с левой стороны неравенств и max(x,y) с правой стороны неравенств, а необходимые условия сгруппированы в выражениях min(x,y) с правой стороны неравенств и max(x,y) с левой стороны неравенств. Предусмотрены вышеупомянутые условия А.3 и В.3, чтобы учитывать возможность того, что фрейм Fа_i может перекрыть четыре фрейма от Fb_j до Fb_j+3. Разумеется операции на индексах i и j осуществляют по модулю максимального значения индекса (Na для i и Nb для j), так как последовательности фреймов можно повторять бесконечно.

Для каждого i между 0 и Na-1 рассматривают:

Для каждого j между 0 и Nb-1 рассматривают:

[A.1]

если Da_i ≤ Tb_j+1, то продолжают при [В.1]

[A.2]

q₁: = (Da_i - Тb_j+1)/ Тb_j

если q₁ > 1 или Тb_j = 0, то q₁: = 1

если Da_i ≤ Tb_j+1 + Tb_j+2

и q₁Tb_j + Db_j+1 ≤ Та_i

то продолжают при [В.1]

[A.3]

если Da_i ≤ Tb_j+2 + Tb_j+3

и q₁Tb_j + Db_j+1 + Db_j+2 + min[Tb_j+1, Da_i] ≤ Та_i

то продолжают при [В.1]

неудачное завершение цикла

[В.1]

если Da_i ≤ Tb_j+1

и Db_j ≤ Та_i

то продолжают при [D]

[В.1.1]

q₁: = (Da_i - Тb_j+1)/ Тb_j

если q₁ > 1 или Тb_j = 0, то q₁: = 1 и продолжают при [В.2]

Т₁: Та_i-1 - (1 - q₁) Tb_j

если Db_j-1 ≤ Т₁

то продолжают при [С.1]

[В.2]

если Da_i ≤ Tb_j+1 + Tb_j+2

и Db_j + qTb_j + Db_j+1 ≤ Та_i

то продолжают при [С.1]

[В.3]

если Da_i ≤ Tb_j+2 + Tb_j+3

и Db_j + q₁Tb_j + Db_j+1 min[Tb_j+1, Da_i] + Db_j+2 ≤ Та_i

то продолжают при [С.1]

неудачное завершение цикла

[С.1]

если Db_j ≤ Та_i

то продолжают при [D]

неудачное завершение цикла

[D] Переходят к следующему j

Переходят к следующему i

Для дополнения проверки, как было указано выше, этот цикл повторяют, поменяв местами Fa и Fb.

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

На фиг. 7 представлен пример последовательности фреймов, служащей для определения условия В.1.1. Фреймы Fа_i и Fb_j находятся в тех же условиях, что и на фиг. 4А, но вместо запуска операции в начале фрейма Fb_j+1, предполагается, что ее можно запустить сразу после операции Db_j, и в предыдущих фреймах Fа_i-1 и Fb_j-1 выявляют общие условия, которые позволяют это сделать при q = q₁. Условие В.1.1, как и условие В.1, основано на предположении, что фрейм Fа_i перекрывает два фрейма (Fb_j и Fb_j+1), что соответствует более вероятной ситуации, которую можно встретить, чем ситуацию, в которой фрейм Fа_i перекрывает три фрейма или более.

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

Не равные нулю значения резервного времени R могут, в частности, смягчить условие С.1.

На фиг. 8 представлен пример последовательности фреймов, служащей для определения смягченного условия в случае, когда условие С.1 не удовлетворено, то есть если Db_j > Тa_i. В рамках предположения С предполагают, что операция Db_j еще не запущена в начале фрейма Fа_i. В самом начале фрейма Fа_i запускают операцию Da_i, которая имеет самый короткий конечный срок исполнения. Фрейм Fb_j начинается до фрейма Fа_i, предположительно во время интервала Ra_i-1 фрейма Fа_i-1. Обозначим kRa_i-1 интервал между началом фрейма Fb_j и началом фрейма Fа_i, при 0 ≤ k ≤ 1.

Если операция Db_j не была запланирована в начале фрейма Fb_j, это значит, что:

Db_j > kRa_i-1 + Tа_i.

Обозначим k₁ предельное значение k, при котором Db_j = k₁Ra_i-1 + Tа_i, то есть k₁=(Dbj-Tаi)/Ra_i-1. Если k > k₁, операцию Db_j можно с уверенностью планировать до начала фрейма Fа_i, и этот случай не рассматривается, так как он не соответствует предположению С. В этом случае рассматривают только значения k в пределах от 0 до k₁.

Чтобы можно было исполнить Da_i, необходимо, чтобы Da_i ≤ Tb_j - kRa_i-1. Наихудшим случаем является k = k₁, когда получаем:

Da_i ≤ Tb_j - k₁Ra_i-1, то есть при замене k₁ на его значение:

Da_i ≤ Tb_j - (Db_j - Tа_i), или

Db_j ≤ Tа_i + Tb_j - Da_i

Коэффициент k₁ не превышает 1, что можно выразить, как:

Db_j - Tа_i ≤ Ra_i-1, то есть

Db_j ≤ Tа_i + Ra_i-1

В конечном итоге, чтобы не влиять на исполнение операции Da_i+1, операция Db_j не должна переходить на фрейм Fа_i+1. Это соблюдается, если:

Db_j ≤ Tа_i + Ra_i.

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

Db_j ≤ Tа_i + Tb_j - Da_i

И

Db_j ≤ Tа_i + Ra_i-1 [С.2]

И

Db_j ≤ Tа_i + Ra_i

Следующий псевдокод учитывает резервы времени R.

Для каждого i между 0 и Na-1 рассматривают:

Для каждого j между 0 и Nb-1 рассматривают:

[A.1]

если Da_i ≤ Tb_j+1, то продолжают при [В.1]

[A.2]

q₁: = (Da_i - Тb_j+1)/ Тb_j + Rb_j)

если q₁ > 1 или Тb_j + Rb_j = 0, то q₁: = 1

если Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и q₁ (Tb_j + Rb_j) + Db_j+1 ≤ Та_i

то продолжают при [В.1]

[A.3]

если Da_i ≤ Tb_j+2 + Rb_j+2 + Tb_j+3

и Db_j+1 + q₁ (Tb_j + Rb_j+1) + Db_j+2 + min[Tb_j+1 + Rb_j+1, Da_i] ≤ Та_i

то продолжают при [В.1]

неудачное завершение цикла

[В.1]

если Da_i ≤ Rb_j + Tb_j+1

и Db_j ≤ Та_i

то продолжают при [C.2]

q₁:= (Da_i - Rb_j - Tb_j+1)/ Tb_j

если q₁ > 1 или Tb_j = 0, то q₁:= 1 и продолжают при [В.2]

[В.1.1]

Т₁:= Tа_i-1 - (1 - q₁) Tb_j + Rа_i-1

если Db_j-1 ≤ Т₁ + min[Tb_j-1 + Db_j-1 + Rb_j-1 - T₁ - Da_i-1, Ra_1-2)

то продолжают при [С.1]

[В.1.2]

если Db_j-1 + Rb_j-1 ≤ Т₁

и Da_i-1 ≤ Tb_j-2 + Rb_j-2 + Tb_j-1

и Tb_j-2 + Db_j-2 + Rb_j-2 + Tb_j-1 + Db_j-1 + Rb_j-1 ≤ Ra_i-2 + T₁ + Da_i-1

то продолжают при [С.1]

[В.2]

если Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и Db_j + q₁Tb_j + Rb_j + Db_j+1 ≤ Tа_i

то продолжают при [С.1]

[В.3]

если Da_i ≤ Tb_j+2 + Rb_j+2 + Tb_j+3

и Db_j + q₁Tb_j + Rb_j + Db_j+1 + min[Tb_j+1 + Rb_j+1, Da_i] + Db_j+2 ≤ Tа_i

то продолжают при [С.1]

неудачное завершение цикла

[С.1]

если Db_j ≤ Та_i

то продолжают при [D]

[С.2]

если Db_j ≤ Tа_i + min[Tb_j -Da_i, Ra_i, Ra_i-1]

то продолжают при [D]

неудачное завершение цикла

[D] Переходят к следующему j

Переходят к следующему i

Условие В.1.2, которое появляется в этом псевдокоде, устанавливают так же, как и условие В.1.1, продолжив исследования на фреймах Fа_i-2 и Fb_j-2.

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

Для рассмотрения этого случая вводят коэффициент изменчивости 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_i ≤ Tb_j+1, то продолжают при [В.1]

[A.2]

q₁: = (Da_i - Тb_j+1)/ Тb_j + Rb_j)

если q₁ > 1 или Тb_j + Rb_j = 0, то q₁: = 1

если Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и min[ q₁ (zb⋅(Tb_j + Rb_j) + (zb-1) Db_j), Da_i] + Db_j+1 ≤ Та_i

то продолжают при [В.1]

[A.3]

если Da_i ≤ Tb_j+2 + Rb_j+2 + Tb_j+3

и Db_j+1 + min[ q₁ (zb⋅(Tb_j + Rb_j) + (zb-1) Db_j, Da_i] + Db_j+2 + min[ zb⋅(Tb_j+1 + Rb_j+1)

+ (zb-1) Db_j+1, Da_i] ≤ Та_i

то продолжают при [В.1]

неудачное завершение цикла

[В.1]

если Da_i ≤ Rb_j + Tb_j+1

и Db_j ≤ Та_i

то продолжают при [C.2]

[В.1.1]

q₁:= (Da_i - Rb_j - Tb_j+1)/ Tb_j

если q₁ > 1 или Tb_j = 0, то q₁:= 1 и продолжают при [В.2]

Т₁:= Tа_i-1 - (1 - q₁) Tb_j + Rа_i-1

если Db_j-1 ≤ Т₁ + min[Tb_j-1 + Db_j-1 + Rb_j-1 - T₁ - Da_i-1, Ra_1-2)

то продолжают при [С.1]

[В.1.2]

если Db_j-1 + zb⋅Rb_j-1 ≤ Т₁

и Da_i-1 ≤ Tb_j-2 + Rb_j-2 + Tb_j-1

и zb⋅(Tb_j-2 + Db_j-2 + Rb_j-2 + Tb_j-1 + Db_j-1 + Rb_j-1) ≤ Ra_i-2 + T₁ + Da_i-1

то продолжают при [С.1]

[В.2]

если Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и Db_j + min[ q₁ (zb⋅Tb_j + (zb-1) Db_j) + zb⋅Rb_j, Da_i ] + Db_j-1 ≤ Tа_i

то продолжают при [С.1]

[В.3]

если Da_i ≤ Tb_j+2 + Rb_j+2 + Tb_j-3

и Db_j + min[ q₁ (zb⋅Tb_j + (zb-1) Db_j)+ zb⋅Rb_j, Da_i] + Db_j+1 + min[zb⋅(Tb_j+1 + Rb_j+1)

+ (zb-1) Db_j+1, Da_i] + Db_j+2 ≤ Tа_i

то продолжают при [С.1]

неудачное завершение цикла

[С.1]

если Db_j ≤ Та_i

то продолжают при [D]

[С.2]

если Db_j ≤ Tа_i + min[Tb_j - Da_i, Ra_i, Ra_i+1]

то продолжают при [D]

неудачное завершение цикла

[D] Переходят к следующему j

Переходят к следующему i

Для случая 3) описанного выше способа планирования рассматриваемый запас времени является минимальным значением, то есть Т, а не zT.

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

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

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

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

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

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

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

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

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

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

3. Способ по п. 2, в котором этап проверки содержит этапы, на которых:

для каждого фрейма Fa_i повторяющейся последовательности первой задачи оценивают следующие условия для каждого фрейма Fb_j повторяющейся последовательности второй задачи:

[A.1] Da_i ≤ Tb_j+1,

[B.1] Da_i ≤ Rb_j +Tb_j+1 и Db_j ≤ Ta_i и

[C.1] Db_j ≤ Ta_i,

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

повторяют предыдущий этап, переставив местами фреймы Fa_i и Fb_j;

разрешают выполнение задач, если для любой пары (i, j) соблюдены все три условия [A.1], [B.1] и [C.1].

4. Способ по п. 3, в котором этап проверки содержит этапы, на которых:

если условие [A.1] не соблюдается, оценивают следующее условие:

[A.2] Da_i ≤ Tb_j+1 + Rb_j + Tb_j+2

и Da_i + Db_j+1 ≤ Ta_i + Tb_j+1,

если условие [B.1] не соблюдается, оценивают следующее условие:

[B.2] Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и Db_j + Da_i + Db_j+1 ≤ Ta_i + Tb_j+1,

если условие [C.1] не соблюдается, оценивают следующее условие:

[С.2] Db_j ≤ Ta_i + min[Tb_j-Da_i, Ra_i, Ra_i-1],

разрешают выполнение задач, если условия [A.1] или [A.2], и [В.1] или [В.2], и [С.1] или [С.2] соблюдены для любой пары (i,j).

5. Способ по п. 3, в котором шкалы времени, определяющие продолжительность фреймов, являются переменными, так что запас времени Т и резервное время R изменяются на коэффициент от 1 до za для фреймов Fa и на коэффициент от 1 до zb для фреймов Fb, при этом этап проверки содержит этапы, на которых:

если условие [A.1] не соблюдается, оценивают следующее условие:

[A.2] Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и min[q₁(zb⋅(Tb_j+Rb_j) + (zb-1)Db_j),Da_i] + Db_j+1 ≤ Ta_i,

где q₁ = (Da_i-Tb_j+1)/(Tb_j+Rb_j);

если условие [B.1] не соблюдается, оценивают следующее условие:

[B.2] Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и Db_j + min[q₁(zb⋅Tb_j + (zb-1)Db_j) + zb⋅Rb_j, Da_i] + Db_j+1 ≤ Ta_i,

где q₁ = (Da_i - Rb_j - Tb_j+1)/Tb_j;

если условие [C.1] не соблюдается, оценивают следующее условие:

[С.2] Db_j ≤ Ta_i + min[Tb_j-Da_i, Ra_i, Ra_i-1];

разрешают выполнение задач, если условия [A.1] или [A.2], и [В.1] или [В.2], и [С.1] или [С.2] соблюдены для любой пары (i,j).

6. Способ по п. 5, в котором этап проверки содержит этапы, на которых:

если условие [B.1] не соблюдается, перед условием [В.2] оценивают следующее условие:

[B.1.1] Da_i ≤ Tb_j + Rb_j + Tb_j+1

и Db_j-1 ≤ T₁ + min[Tb_j-1 + Db_j-1 + Rb_j-1 - T₁ - Da_i-1, Ra_i-2],

где q₁ = (Da_i - Rb_j - Tb_j+1)/Tb_j и T₁ = Ta_i-1 - (1-q₁)Tb_j + Ra_i-1,

разрешают выполнение задач, если условия [A.1] или [A.2], и [В.1] или [В.1.1], и [С.1] или [С.2] соблюдены для любой пары (i,j).

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

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

для каждого фрейма Fa_i повторяющейся последовательности первой из двух задач оценивают следующие условия для каждого фрейма Fb_j повторяющейся последовательности второй из двух задач:

[A.1] Da_i ≤ Tb_j+1,

[B.1] Da_i ≤ Rb_j +Tb_j+1 и Db_j ≤ Ta_i и

[C.1] Db_j ≤ Ta_i,

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

повторяют предыдущий этап, переставив местами фреймы Fa_i и Fb_j;

разрешают выполнение задач, если для любой пары (i, j) соблюдены все три условия [A.1], [B.1] и [C.1]; и

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

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

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

8. Способ по п. 7, в котором этап проверки содержит этапы, на которых:

если условие [A.1] не соблюдается, оценивают следующее условие:

[A.2] Da_i ≤ Tb_j+1 + Rb_j + Tb_j+2

и Da_i + Db_j+1 ≤ Ta_i + Tb_j+1,

если условие [B.1] не соблюдается, оценивают следующее условие:

[B.2] Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и Db_j + Da_i + Db_j+1 ≤ Ta_i + Tb_j+1,

если условие [C.1] не соблюдается, оценивают следующее условие:

[С.2] Db_j ≤ Ta_i + min[Tb_j-Da_i, Ra_i, Ra_i-1],

разрешают выполнение задач, если условия [A.1] или [A.2], и [В.1] или [В.2], и [С.1] или [С.2] соблюдены для любой пары (i,j).

9. Способ по п. 7, в котором шкалы времени, определяющие продолжительность фреймов, являются переменными, так что запас времени Т и резервное время R изменяются на коэффициент от 1 до za для фреймов Fa и на коэффициент от 1 до zb для фреймов Fb, при этом этап проверки содержит этапы, на которых:

если условие [A.1] не соблюдается, оценивают следующее условие:

[A.2] Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и min[q₁(zb⋅(Tb_j+Rb_j) + (zb-1)Db_j),Da_i] + Db_j+1 ≤ Ta_i,

где q₁ = (Da_i-Tb_j+1)/(Tb_j+Rb_j);

если условие [B.1] не соблюдается, оценивают следующее условие:

[B.2] Da_i ≤ Tb_j+1 + Rb_j+1 + Tb_j+2

и Db_j + min[q₁(zb⋅Tb_j + (zb-1)Db_j) + zb⋅Rb_j, Da_i] + Db_j+1 ≤ Ta_i,

где q₁ = (Da_i - Rb_j - Tb_j+1)/Tb_j;

если условие [C.1] не соблюдается, оценивают следующее условие:

[С.2] Db_j ≤ Ta_i + min[Tb_j-Da_i, Ra_i, Ra_i-1];

разрешают выполнение задач, если условия [A.1] или [A.2], и [В.1] или [В.2], и [С.1] или [С.2] соблюдены для любой пары (i,j).

10. Способ по п. 9, в котором этап проверки содержит этапы, на которых:

если условие [B.1] не соблюдается, перед условием [В.2] оценивают следующее условие:

[B.1.1] Da_i ≤ Tb_j + Rb_j + Tb_j+1

и Db_j-1 ≤ T₁ + min[Tb_j-1 + Db_j-1 + Rb_j-1 - T₁ - Da_i-1, Ra_i-2],

где q₁ = (Da_i - Rb_j - Tb_j+1)/Tb_j и T₁ = Ta_i-1 - (1-q₁)Tb_j + Ra_i-1,

разрешают выполнение задач, если условия [A.1] или [A.2], и [В.1] или [В.1.1], и [С.1] или [С.2] соблюдены для любой пары (i,j).