СПОСОБ ВЫДЕЛЕНИЯ ВРЕМЕНИ ЗАДАЧИ, ПОЗВОЛЯЮЩИЙ ДЕТЕРМИНИРОВАННОЕ УСТРАНЕНИЕ ОШИБОК В РЕАЛЬНОМ ВРЕМЕНИ
TASK TIME ALLOCATION METHOD ALLOWING DETERMINISTIC ERROR RECOVERY IN REAL TIME

Настоящее изобретение относится к многозадачным системам реального времени, содержащим набор независимых от времени задач, синхронизированных посредством одинакового временного базиса, и для которых известны временные ограничения выполнения. Настоящее изобретение относится, в частности, к системам реального времени, требующим высокий уровень производительности в их осуществлении, и критическим системам, для которых требуется высокий уровень гарантии, чтобы использовать аппаратные ресурсы выполнения, выделенные для каждой задачи системы.
Настоящее изобретение применяется, в частности, для подачи команд и систем управления, таких как системы управления, используемые в областях транспортировки (автомобильной, железнодорожной, морской и аэрокосмической), промышленная автоматика, энергетика и другие системы, для которых управляемое распределение ресурсов является важным, как в сетях связи.
В критических системах реального времени задачи часто выполняются согласно способам статического планирования так, чтобы выполнять статическое выделение времени лимитов времени для использования ресурсов выполнения, таких как процессор. Это обеспечивает демонстрацию независимости от времени задач между собой в отношении использования ресурсов, и, в частности, процессора. Эта простая и общепринятая точка зрения не учитывает проблему связей между задачами, которая, в частности, рассмотрена в документах [3], [4], [7], [8]. Однако эта точка зрения создает проблемы осуществления на современных процессорах, которые включают в себя кэш-памяти. Более того, содержание этих кэш-памятей зависит от всей истории выполнения задач и доступных данных. Далее состояние этих памятей влияет на время выполнения операций обработки чередующихся задач. При этих условиях сложно обеспечивать абсолютную верхнюю границу времени выполнения (WCET - наихудшее время выполнения, см. документ [5]) операции обработки. Формальные способы вычисления этих верхних границ, таким образом, приводят к потенциальной значительной переоценке этих верхних границ по сравнению с экспериментальными результатами.
Более того, в некоторых многозадачных системах реального времени необходимо обеспечивать, что задачи не оказывают влияние друг на друга, т.е., что задача не может быть выполнена, или, что ее выполнения не может заканчиваться во время, выделенное для другой задачи. Поиск такого отсутствия взаимовлияния между задачами приводит в некоторых областях к отключению кэш-памятей или очистке всего их содержимого в начале каждого временного окна, выделенного для операции обработки так, чтобы иметь (пустое) состояние, которое является независимым от выполнения предыдущих операций обработки. Однако эта операция очистки кэш-памятей значительно ухудшает производительность многозадачной системы. В дополнение, операция обработки может в некоторых случаях быть разделена на несколько временных окон, что требует очистку кэш-памятей несколько раз во время выполнения операции обработки.
По этим различным причинам разработчики систем реального времени сталкиваются со значительным превышением параметров таких систем. С практической точки зрения, чтобы сделать этот подход менее ухудшающим, выделение времени процессора выполняется на основании потребности во времени выполнения, которая является более короткой, чем «теоретическое» WCET, приводя к допущению определенной частоты ошибок. Основной недостаток этого подхода заключается в отсутствии какой-либо модели, характеризующей закон распределения времени выполнения операции обработки, действительно обеспечивающей оценку частоты ошибок в отношении выделенного лимита времени. В частности, когда допустимая частота ошибок должна быть очень низкой, и, таким образом, возникать в очень редких случаях, невозможно с помощью этого подхода, который основан на слишком малом количестве экспериментальных выборок, демонстрировать, что эти системы имеют детерминированное поведение. В связи с этим для улучшения надежности таких систем, один хорошо известный способ включает выполнение мер устранения ошибок для таких ошибок в лимитах времени выполнения, чтобы уменьшать случаи остаточных ошибок до крайне низкого количества.
Следует отметить, что для преодоления этой значительной проблемы превышения параметров обычно используется неиспользованное время (разница между средним временем выполнения и выделенным лимитом времени) путем повторного выделения его динамически для задач не в реальном времени и некритических задач, выполняемых в качестве неприоритетных фоновых задач (см. документы [2], [7], [8]). Однако это решение не соответствует той же цели и не способствует критическим задачам реального времени.
Таким же образом, для других типов ошибок, допускающих появление во время выполнения критической задачи реального времени, предпочтительно иметь такие детерминированные механизмы обработки ошибок в реальном времени без какого-либо взаимовлияния с другими выполняемыми задачами. Это позволяет устранение ошибок без какого-либо разрыва в потоке выполнения задач и обеспечивает осуществление достаточных действий с достаточными временными ограничениями. Эти проблемы имеют известные решения в асинхронных системах, т.е. без каких-либо ограничений времени выполнения. Однако эти решения не обеспечивают никакой гарантии выполнения в реальном времени, и они не адаптированы к контексту критических задач, где требуется отсутствие взаимовлияния между операциями обработки, включая, разумеется, случай операционной неисправности.
Таким образом, необходимо иметь возможность создания приложения, содержащего набор задач, синхронизированных посредством одинакового временного базиса, при обеспечении эффективного и надежного использования многозадачной системы, на которой выполняются задачи. Дополнительно необходимо иметь возможность выделения достаточного времени для обработки ошибок так, что она может быть выполнена в детерминированное время, совместимое с ограничениями критических систем реального времени без какого-либо риска взаимовлияния с другими задачами. Также может быть необходимо использование неиспользованного выделенного времени для различных оптимизаций, таких как терморегулирование, минимизация энергопотребления или распределение или совместное выполнение некритических задач. Может дополнительно быть необходимо иметь возможность обеспечения верной последовательности обработки задач приложения, выполняемого многозадачной системой, и иметь возможность формальной демонстрации, что эта последовательность является верной.
Некоторые варианты выполнения относятся к способу выполнения задач приложения реального времени на многозадачном компьютере, причем каждая задача содержит по меньшей мере одну операцию обработки, причем способ содержит этапы, на которых: определяют временные окна, каждое из которых связано с выполнением операции обработки задачи приложения, выделяют для каждой операции обработки, имеющей временное окно, лимит времени и запас времени, причем время, выделенное для операции обработки посредством лимита времени и запаса времени, является более коротким, чем продолжительность временного окна, связанного с операцией обработки, во время выполнения приложения многозадачной системой активируют каждую операцию обработки в начале временного окна, с которым она связана, по истечении лимита времени одной из операций обработки активируют режим обработки ошибок, если выполнение операции обработки не завершено, и, если режим обработки ошибок является активным для одной из операций обработки, выполняют процедуру обработки ошибок для операции обработки в режиме обработки ошибок в оставшееся время, выделенное для операции обработки посредством лимита времени и запаса времени.
Согласно одному варианту выполнения способ содержит этапы, на которых: если режим обработки ошибок является активным для одной из операций обработки, продолжают выполнение операции обработки, выполнение которой не завершено по истечении лимита времени, выделенного для операции обработки, при этом отслеживая истечение запаса времени, выделенного для операции обработки, и по истечении запаса времени, выделенного для операции обработки, если выполнение операции обработки не завершено, завершают выполнение операции обработки и выполняют операцию обработки ошибок превышения лимита времени.
Согласно одному варианту выполнения способ содержит этапы, на которых: фрагментируют операции обработки, связанные с временным окном, продолжающимся в течение нескольких временных окон, для обработки других задач приложения, так, что каждое временное окно исключительно связано с операцией обработки или фрагментом операции обработки, выделяют лимит времени для каждого из фрагментов операции обработки так, что сумма лимитов времени всех фрагментов фрагментированной операции обработки равна лимиту времени фрагментированной операции обработки, причем запас времени, связанный с фрагментированной операцией обработки, связан с последним фрагментом фрагментированной операции обработки, и связывают с каждым фрагментом операции обработки переменную состояния, указывающую, является ли он последним фрагментом фрагментированной операции обработки, причем режим обработки ошибок не активируют по истечении лимита фрагмента операции обработки, если переменная состояния, связанная с фрагментом операции обработки, указывает на то, что фрагмент операции обработки не является последним фрагментом фрагментированной операции обработки.
Согласно одному варианту выполнения запас каждой из операций обработки, связанной с лимитом времени, вычисляют путем применения множителя к лимиту времени операции обработки, причем множитель идентичен для всех операций обработки, связанных с лимитом времени.
Согласно одному варианту выполнения множитель определяют так, что задачи приложения могут быть запланированы согласно потребностям во времени операций обработки для временных окон, связанных с операциями обработки, и для признаков компьютера.
Согласно одному варианту выполнения операции обработки выполняют процессором, синхронизированным посредством первого временного базиса, а временные окна, связанные с операциями обработки, определяют во втором временном базисе не регулярном по сравнению с первым временным базисом, причем единица времени во втором временном базисе имеет минимальное значение в первом временном базисе, множитель определяют согласно минимальному значению.
Согласно одному варианту выполнения каждую операцию обработки связывают с переменной состояния, указывающей, выполняет ли она ввод/вывод в отношении процессора, выполняющего операцию обработки, и, если одна из операций обработки связана с переменной состояния, указывающей, что операция обработки не выполняет никакой ввод/вывод, выполнение операции обработки запускают без ожидания начала временного окна операции обработки, как только выполнение предыдущей операции обработки завершено.
Некоторые варианты выполнения также относятся к многозадачной системе реального времени, содержащей многозадачный компьютер, выполняющий приложение реального времени, содержащее несколько задач, причем каждая задача содержит по меньшей мере одну операцию обработки, причем система выполнена с возможностью: сохранения временных окон, каждое из которых связано с выполнением набора операций обработки задач приложения, сохранения для каждой операции обработки, имеющей временное окно, лимита времени и запаса времени, причем время, выделенное для операции обработки посредством лимита времени и запаса времени, является более коротким, чем продолжительность временного окна операции обработки, выполнения операций обработки приложения и по истечении лимита времени одной из операций обработки активации режима обработки ошибок, если выполнение операции обработки не завершено, и, если режим обработки ошибок является активным для одной из операций обработки, выполнения процедуры обработки ошибок для операции обработки в режиме обработки ошибок в оставшееся время, выделенное для операции обработки посредством лимита времени и запаса времени.
Согласно одному варианту выполнения система выполнена с возможностью: если режим обработки ошибок является активным для одной из операций обработки, продолжения выполнения операции обработки, выполнение которой не завершено по истечении ее лимита времени, при этом отслеживая истечение запаса времени, выделенного для операции обработки, и по истечении запаса времени, если выполнение операции обработки не завершено, завершения выполнения операции обработки и выполнения операции обработки ошибок превышения лимита времени.
Согласно одному варианту выполнения система выполнена с возможностью: сохранения того, что некоторые из операций обработки, связанные с временными окнами, фрагментированы, сохранения для каждого фрагмента операции обработки временного окна и лимита времени для выполнения фрагмента операции обработки, сохранения для последнего фрагмента каждой фрагментированной операции обработки в качестве связанного запаса времени запаса времени, связанного с фрагментированной операцией обработки, и сохранения для каждого фрагмента операции обработки переменной состояния, указывающей, является ли фрагмент последним фрагментом фрагментированной операции обработки, и во время выполнение приложения неактивации режима обработки ошибок по истечении лимита фрагмента операции обработки, если переменная состояния, связанная с фрагментом операции обработки, указывает на то, что фрагмент операции обработки не является последним фрагментом фрагментированной операций обработки.
Согласно одному варианту выполнения система выполнена с возможностью определения запаса каждой из операций обработки, связанной с лимитом времени, путем применения множителя к лимиту времени операции обработки, причем множитель идентичен для всех операций обработки, связанных с лимитом времени.
Согласно одному варианту выполнения система содержит процессор, синхронизированный посредством первого временного базиса, для выполнения операций обработки, и принимающий второй временной базис не регулярный по сравнению с первым временным базисом, причем система выполнена с возможностью определения временных окон, связанных с операциями обработки во втором временном базисе, причем единица времени во втором временном базисе имеет минимальное значение в первом временном базисе, множитель определен согласно минимальному значению.
Согласно одному варианту выполнения система выполнена с возможностью: сохранения для каждой операции обработки переменной состояния, указывающей, выполняет ли операция обработки ввод/вывод в отношении процессора системы, выполняющей операцию обработки, и, если одна из операций обработки связана с переменной состояния, указывающей, что операция обработки не выполняет никакой ввод/вывод, запуска выполнения операции обработки, как только выполнение предыдущей операции обработки завершено без ожидания начала временного окна операции обработки.
Некоторые примеры вариантов выполнения настоящего изобретения будут описаны ниже в отношении, но, не ограничиваясь, сопровождающих чертежей, на которых:
Фиг. 1 схематически показывает многозадачный компьютер,
Фиг. 2А и 2В показывают временные диаграммы двух задач,
Фиг. 3 схематически показывает в виде временной диаграммы план планирования двух задач на Фигурах 2А, 2В
Фиг.4 схематически показывает в виде временной диаграммы план нагрузки согласно одному варианту выполнения
Фиг. 5 схематически показывает в виде временной диаграммы план нагрузки согласно другому варианту выполнения,
Фиг. 6А, 6В 7 и 8 показывают этапы, выполняемые ядром реального времени компьютера реального времени согласно различным вариантам выполнения.
Фиг. 1 показывает многозадачный компьютер RTS, содержащий один или более процессоров PRC, схему CLK синхронизации, одну или более энергонезависимых памятей NVM (перезаписываемых или нет), одну или более энергозависимых памятей VM (например, типа RAM - оперативное запоминающее устройство), и одну или более схем РНС сопряжения, выполненных с возможностью управления периферийными блоками (не показаны) и/или приема сигналов от таких блоков. Процессор PRC соединен со схемами CLK, NVM, VM и РНС посредством шины SB адреса и данных. Схема CLK синхронизации также соединена с вводом по прерываниям процессора PRC для запуска прерывания, когда заданная программируемая продолжительность истекла. С этой целью процессор PRC может передавать значение продолжительности через шину SB и активировать схему CLK.
Память NVM хранит программы задач многозадачного приложения и данные, относящиеся к приложению. Память VM хранит переменные данные, используемые в выполнении приложения. Следует отметить, что память NVM может быть опущена, если выполняемые программы передаются компьютеру, когда многозадачное приложение запущено.
Процессор PRC может содержать один или более микропроцессоров или микроконтроллеров, каждый из которых может содержать одно или более ядер или блоков обработки. Процессор PRC также может быть образован из или содержать одну или более схем типа ASIC (интегральная схема специального назначения) или FPGA (программируемая пользователем вентильная матрица). Процессор PRC выполняет ядро реального времени, которое, в частности, содержит функции, необходимые для выполнения многозадачного приложения реального времени, такие как функции для осуществления плана планирования задач, функции для управления контекстами выполнения задач и функции для управление одним или более сторожевыми процессами для отслеживания времени выполнения операций обработки.
Для критического приложения реального времени может быть необходима демонстрация того, что среда выполнения (компьютер RTS) является достаточной, в частности, с точки зрения вычислительной мощности, чтобы соответствовать наихудшим потребностям во времени выполнения всех задач приложения. Независимо от подходов, используемых для планирования задач, эта демонстрация может быть обеспечена формальной верификацией системы уравнений нагрузки (см. документ [1], [2], [3]). Способ, представленный здесь, является независимым от выбора способа планирования и соответственной системы уравнений нагрузки для верификации. Для иллюстрации способа путем примера использовано общее изображение (см. документ [3], например).
Фиг. 2А показывает на временной диаграмме во временном базисе t циклическую задачу А, которая может быть разделена на три операции ТА1, ТА2 и ТА3 обработки, выполняемые повторно. Операция ТА1 обработки выполняется в течение временного окна, обозначенного [0,1[, образованного наиболее ранним временем t=0 начала и наиболее поздним временем t=1 окончания. Временное окно [0,1[, таким образом, имеет продолжительность одной единицы времени. Операция ТА2 обработки выполняется в течение временного окна [1,5[, продолжающегося 4 единицы времени между временем t=1 и t=5. Операция ТА3 обработки выполняется в течение временного окна [5,6[, продолжающегося одну единицу времени между временем t=5 и t=6. Соответственные потребности во времени выполнения операций ТА1, ТА2, ТА3 обработки в каждом из этих временных окон [0,1[, [1,5[, [5,6[обозначены QA1, QA2 и QA3, причем эти потребности определены согласно возможностям целевого многозадачного компьютера.
Фиг. 2В показывает на временной диаграмме в том же временном базисе t циклическую задачу В, которая содержит только одну операцию ТВ обработки, выполняемую повторно в течение временного окна [0,3[, продолжающегося 3 единицы времени между временем t=0 и t=3. Потребность во времени выполнения операции ТВ обработки во временном окне [0,3[обозначена QB.
Для создания плана планирования задач А и В операции обработки задач распределены в течение их соответственных временных окон так, что потребности каждой операции обработки удовлетворяются. Это приводит к фрагментации некоторых операций обработки в течение нескольких более коротких временных окон так, что в каждом рассматриваемом временном окне операции обработки и/или фрагменты операций обработки, связанные с этим временным окном, могут быть полностью выполнены при соблюдении временных ограничений каждой задачи. Другими словами, операции обработки фрагментированы так, что все рассматриваемые временные окна являются смежными (конец одного окна соответствует началу другого окна) и не пересекаются (без какой-либо области общей для двух окон). Это приводит к условиям на фрагментах операций обработки, которые должны быть удовлетворены так, что все задачи приложения могут быть запланированы.
Фиг.3 показывает план планирования задач А и В. Операция ТА2 обработки фрагментирована на две части ТА21 и ТА22 для учета времени t=3 задачи В, которое соответствует началу временного окна для повторной активации операции ТВ обработки, и которое возникает в течение временного окна операции ТА2 обработки. Таким же образом, операция ТВ обработки задачи В фрагментирована в течение временного окна [0,3[ на две части ТВ11 и ТВ12 для учета времени t=1 начала временного окна [1,5[ операции ТА2 обработки задачи А, которое возникает в течении временного окна операции ТВ обработки. Возникновение операции ТВ обработки, связанной с временным окном [3,6[, также фрагментировано на две части ТВ21 и ТВ22 для учета времени t=5 начала временного окна операции ТА3 обработки задачи А, за счет того, что это время возникает в течение временного окна этого возникновения операции ТВ обработки. Эти различные фрагментации двух возникновений операции ТВ обработки необходимы для создания повторяющегося плана планирования задач А и В. Продолжительность повторяющейся последовательности задач А, В, взятых вместе, равна наименьшему общему кратному (LCM) продолжительности повторяющихся последовательностей каждой задачи. В примере на Фигуре 3 задача А связана с временным окном, имеющим продолжительность, составляющую 6 единиц времени, тогда как задача В связана с временным окном, имеющим продолжительность, составляющую 3 единицы времени. Продолжительность повторяющейся последовательности задач А, В равна LCM 6 и 3, т.е. 6 единицам времени, соответствующим двум возникновениям задачи В. Из этой фрагментации следует, что операция ТА1 обработки и фрагмент ТВ11 операции обработки должны быть выполнены во время временного окна [0,1[. Фрагменты ТА21 и ТВ12 операции обработки должны быть выполнены во время временного окна [1,3[. Фрагменты ТА22 и ТВ21 операции обработки должны быть выполнены во время временного окна [3,5[. Операция ТА3 обработки и фрагмент ТВ22 операции обработки должны быть выполнены во время временного окна [5, 6[.
Более того, потребности во времени выполнения фрагментов ТА21 и ТА22 операции обработки соответственно обозначены QA21 и QA22. Подобным образом потребности во времени выполнения фрагментов ТВ11, ТВ12, ТВ21 и ТВ22 операции обработки соответственно обозначены QB11, QB12, QB21 и QB22. В каждом временном окне, показанном на Фигуре 3, уравнение нагрузки (или неравенство) для верификации может быть определено так, что задачи А и В могут быть запланированы. Это уравнение определяет, что сумма потребностей операций обработки или фрагментов операций обработки одного и того же временного окна меньше, чем продолжительность единицы времени временного окна. Таким образом, следующая далее система уравнений нагрузки следует из Фиг. 3:
QA1+QB11≤1 (Е1)
QA21+QB12≤2 (E2)
QA22+QB21≤2 (Е3)
QA3+QB22≤1 (Е4)
Эта система уравнений определяет необходимое и достаточное условие для некоторых алгоритмов планирования, таких как представлены в документах [1] и [3]. Эта система уравнений используется для демонстрации, что определение параметров многозадачного компьютера является верным. Следует отметить, что для алгоритма планирования RMS (частотно-монотонное планирование, см. документ [1], [2]), эта система не определяет достаточное условие во всех случаях, и это условие должно быть откорректировано согласно формуле, указанной в документе [1]. Однако эта корректировка не изменяет никоим образом представленный способ. Способ вычисления потребностей QA21, QA22, QB11, QB12, QB21, QB22 фрагментов определен теорией планирования и не относится к настоящему изобретению, Для более подробного описания документ [3] может быть упомянут для примера.
Согласно одному варианту выполнения новая система уравнений нагрузки получается из системы уравнений нагрузки, образованной ранее, путем введения множителя K, составляющего больше 1, в левую часть неравномерных символов. В примере на Фиг. 3 новая система уравнений нагрузки получена из системы (E1)-(Е4) следующим образом:
K⋅(QA1+QB11)≤1 (Е1')
K⋅(QA21+QB12)≤2 (E2')
K⋅(QA22+QB21)≤2 (Е3')
K⋅(QA3+QB22)≤1 (Е4')
Согласно значению множителя K эта новая система уравнений может иметь или может не иметь решения. В связи с этим максимальный множитель Kx вычислительных потребностей во времени задач определен так, что приложение реального времени (выполняемое заданным компьютером, например, компьютером RTS) может быть запланировано, т.е. так, что новая система уравнений (Е1')-(Е4') имеет решение.
Из исходной системы уравнений (E1)-(Е4) нагрузки каждая потребность может быть заменена такой же потребностью, умноженной на множитель, при обеспечении, что приложение реального времени (выполняемое заданной системой) может быть запланировано. В примере на Фиг. 3, таким образом, обеспечено, что расширенные потребности Kx⋅QA1 и Kx⋅QB11 могут быть запланированы в течение первого временного окна [0,1[, расширенные потребности Kx⋅QA21 и Kx⋅QB12 в течение второго временного окна [1,3[ и т.д.
За пределами используемого примера умножение потребностей на множитель Kx применимо независимо от системы уравнений, полученной путем применения способа планирования (см. в частности, документы [1], [2], [3]). Также следует отметить, что для критических приложений реального времени запасы обычно поддерживают требования и характеристики многозадачного компьютера, на котором должно быть выполнено приложение. Множитель Kx может, таким образом, быть определен из вычислительного запаса времени так, что, например, используется 100% вычислительного ресурса времени компьютера. Например, 20% запас соответствует значению множителя Kx, равному 5/4, а 50% запас соответствует значению множителя Kx, равному 2. Также следует отметить, что концепция запаса часто недостаточно формализована, в отличие от определения множителя Kx, который предусматривает формальный критерий для применения к измеряемым величинам. Умножение вычислительных потребностей во времени на множитель Kx, таким образом, обеспечивает наихудшую гарантию постоянного наличия по меньшей мере запаса, вычисленного для всех операций обработки, а не среднего значения.
В примере, показанном на Фиг. 3, результат определения множителя Kx заключается в том, что максимальная нагрузка достигается в течение по меньшей мере одного временного окна (где kx⋅Q=продолжительность единицы времени временного окна, причем Q представляет собой потребность операций обработки, связанную с временным окном), но необязательно в течение каждого из них в зависимости от значений потребностей.
В результате умножение фактических потребностей операций обработки на множитель Kx (больше 1) обеспечивает получение плана планирования задач, в котором фактическая потребность Qi во времени выполнения каждой операции Ti обработки продлевается путем добавления запаса Mi времени выполнения, равного (Kx-1)⋅Qi. План планирования задач также может содержать время ожидания, соответствующее оставшимся временным окнам, где максимальная нагрузка не достигается.
Для создания плана планирования задач значения фактических потребностей во времени выполнения должны быть известны, и операции обработки должны быть выделены для временных окон. Фактические потребности операций обработки и выделение этих операций обработки для временных окон обеспечивают определение значения множителя Kx. Выбранный способ планирования далее может быть применен. Таким образом, из Фиг. 3 при условии, например, что максимальная нагрузка достигается в течение первого и второго временных окон [0,1[ и [1,3[, получена следующая система уравнений:
Kx⋅(QA1+QB11)=1 (E1ʺ)
Kx⋅(QA21+QB12)=2 (Е2ʺ)
Kx⋅(QA22+QB21)≤2 (Е3ʺ)
Kx⋅(QA3+QB22)≤1 (E4ʺ)
Верификация системы уравнений (E1ʺ)-(Е4ʺ) приводит к плану нагрузки, показанному на Фиг. 4. Фиг. 4 показывает план нагрузки в виде временной диаграммы, в которой представлены временные окна [i,i+1[(с i=0, 1, 2, 3, 4 и 5), причем фактические потребности QA1, QA21, QA22, QA3, QB показаны заштрихованными накрест областями вдоль оси t времени, соответственные запасы MA1, МА21, МА22, МА3, MB времени выполнения показаны заштрихованными областями над осью t времени, и заштрихованными областями под осью t времени, и показано время NA1, NA2 ожидания временных окон, где максимальная нагрузка не достигается. В этом плане нагрузки каждое временное окно связано с одной операцией обработки или фрагментом операции обработки. Учитывая продолжительность единицы времени временных окон, потребности некоторых фрагментов операции обработки могут быть определены. Таким образом, потребности QB12 и QB22 двух возникновений операции ТВ обработки могут быть установлены на QB. Результат заключается в том, что потребности QB12 и QB22 устанавливаются на 0.
2
На плане нагрузки на Фиг. 4 можно увидеть, что операция ТВ обработки связана с двумя разными временными окнами различной продолжительности. Более того, план нагрузки содержит два возникновения операции ТВ обработки, одно, выделенное для временного окна [1,2[, и другое, выделенное для временного окна [3,5[.
1
1
1
2
3
2
,
1
1
1
1
2
3
1
2
1
2
2
2
План нагрузки на Фиг. 4 также поделен на временные интервалы, каждый из которых может быть типа потребности операции обработки, запаса обработки или времени ожидания. Таким образом, последовательные потребности QA1, QB, QA21, QA22, QB и QA3 соответственно связаны с временными интервалами [0,0[, [1,1[, [2,2[, [3,3[, [3,4[и [55[. Последовательные запасы MA1, MB, МА21, МА22, MB, МА3 соответственно связаны с временными интервалами [0,1[, [1,2[, [2,3[, [3,3[, [4,4[и [5,5[. Время NA1, NA2 ожидания соответственно связано с временными интервалами [4,5[и[5,6[.
2
2
2
С точки зрения нагрузки многозадачного компьютера, план нагрузки на Фиг. 4 соответствует уравнениям (E1ʺ)-(Е4ʺ), но можно отметить, что так как некоторые операции обработки фрагментированы, запасы времени выполнения, связанные с потребностями, также могут быть фрагментированы. Таким образом, в вышеуказанном примере потребность QA2 является фрагментированной на две отдельные части QA21 и QA22. То же самое верно для связанных запасов МА21, МА22. Эта фрагментация может приводить к повторному определению временных окон. Более того, переход между расширенной потребностью Kx⋅QA22 фрагмента ТА22 операции обработки и потребностью QB второго возникновения операции ТВ обработки предполагает наличие в это время ограничения временного окна, обозначенного [3] на Фиг. 4. Операция ТА22 обработки, таким образом, связана с временным окном [3,3[. Более того, так как потребность QB второго возникновения операции ТВ обработки продолжается до и после времени [4], это время больше не соответствует ограничению временного окна. Второе возникновение операции ТВ обработки, таким образом, связано с временным окном [3,5[.
1
2
3
3
1
3
Чтобы обеспечивать план статического планирования, обеспечивающий оптимальное использование запасов, выделенных для операций обработки, в частности, для обработки ошибок и в особенности ошибок превышения прогнозируемых потребностей во времени выполнения, план нагрузки может быть перестроен, как показано на Фиг. 5. По сравнению с планом нагрузки на Фиг. 4 план нагрузки на Фиг. 5 преобразован путем группировки вместе запасов МА21 и МА22 времени выполнения, связанных с потребностями QA21 и QA22. С этой целью запас МА21, связанный с фрагментом ТА21, перемещен непосредственно перед запасом МА22, и эти два запаса объединены для образования запаса МА2, равного (Kx-1)⋅QA2. В примере на Фиг. 5 потребности QA21 и QA22 операции ТА2 обработки также могут быть объединены после перемещения запаса МА21, так как они являются смежными. Следует отметить, что возможность группировки вместе потребностей фрагментов операции обработки является не частой из-за того, что приложение реального времени в общем имеет более двух задач. Эта группировка потребностей и запасов также приводит к повторному определению рассматриваемых временных окон, при соблюдении сроков выполнения операций обработки, определенных временными окнами, первоначально выделенными для последних. Более того, за счет группировки потребностей QA21 и QA22, время [3] больше не соответствует ограничению временного окна. Это группировка также приводит к повторному выделению конца времени [3] потребности QA2 для операции ТА2 обработки, так как время [3] больше не соответствует концу потребности или началу запаса. Следует отметить, что временное окно [2,3[, которое далее выделено для операции ТА2 обработки, включено в окно [1,5[, первоначально выделенное для этой операции обработки. Эта группировка, таким образом, приводит к повторному определению временных интервалов между временем [2] и [3]. Таким образом, в примере на Фиг. 5 потребность QA2 операции ТА2 обработки связана с временным интервалом [2,31[, а запас МА2 этой операции обработки связан с интервалом [3,3[.
Таким образом, возможно создавать для набора задач, синхронизированных посредством одинакового временного базиса, план планирования задач, обеспечивающий, что в случае ошибки время, выделенное для обработки ошибки, обеспечено (без превышения во время, выделенное для других операций обработки), обеспечивая операцию обработки ошибки в детерминированное время, совместимое с ограничениями критической системы реального времени, состоящей из многозадачного компьютера, выполняющего приложение реального времени. В случае ошибки в определение параметров многозадачного компьютера из-за изменений времени выполнения операций обработки этот способ обеспечивает улучшенную надежность многозадачной системы реального времени путем уменьшения, насколько возможно, случаев остаточной ошибки до крайне низкого количества, и без взаимодействия с выполнением других задач. Этот способ, таким образом, обеспечивает модульный и композиционный подход к планированию задач приложения реального времени, который уменьшает тестирования, необходимые для проверки определения параметров всего компьютера. Этот способ позволяет производить критические системы реального времени, для которых между всеми задачами требуется независимость от времени (отсутствие взаимовлияния), и упрощать сертификацию таких систем. Этот способ также обеспечивает уменьшение превышения параметров процессора для выполнения, что представляет собой значительное преимущество для встроенных компьютеров, имеющих относительно низкую способность обработки.
Следует отметить, что в общем случае временные интервалы необязательно запланированы, как на Фиг. 4 и 5. Более того, если для каждой операции Ti обработки порядок потребностей Qi, запасов MAi и, возможно, интервалов времени NA ожидания удовлетворяется, временные интервалы, выделенные для других операций обработки плана планирования, могут быть расположены любым образом. Таким образом, некоторые временные интервалы типа лимита различных операций обработки могут являться смежными. Подобным образом некоторые временные интервалы типа запаса различных операций обработки могут являться смежными. Важно только, что временные интервалы лимита и запаса каждой операции обработки включены во временное окно, первоначально выделенное для операции обработки.
Варианты выполнения, показанные на Фиг. 4 и 5, также обеспечивают ограничение длины периодов без остановки выполнения процессора PRC, что может ограничивать рост температуры процессора (с преимуществами с точки зрения надежности и срока службы). Периоды, во время которых процессор не выполняет никаких операций обработки, принадлежащих критическим задачам, также могут быть использованы для выполнения некритических задач, которые очень часто имеют повторяющиеся потребности, такие как управление входами/выходами с низкая задержкой.
В общем говоря, соблюдение выделенных потребностей управляется сторожевым процессом, который обеспечивается, когда операция обработки или фрагмент операции обработки запущен, с временной задержкой, определяющей лимит времени, выделенный для операции обработки или фрагмента операции обработки, который может быть установлен согласно значению потребности операции обработки или фрагмента операции обработки. Таким образом, далее лимиты времени выполнения, выделенные для операций обработки, равны потребностям, которые определены ранее. Сторожевой процесс запускается в конце временной задержки, если операция обработки или фрагмент операции обработки не завершен.
Фиг. 6А, 6В показывают этапы S1-S6 и S10-S14, которые выполняются ядром реального времени компьютера RTS. Этапы S1-S6 на Фиг. 6 постоянно выполняются для активации сторожевого процесса WD так, что он может, возможно, быть запущен в конце каждого временного интервала плана планирования. Этапы S10-S14 на Фиг. 6В выполняются, когда сторожевой процесс WD запущен. Далее выражение «операция обработки» обозначает или операцию обработки, или фрагмент операции обработки. Для выполнения некоторых из этапов на Фиг. 6А, 6В ядро реального времени компьютера RTS имеет таблицы, которые создаются из плана планирования или из плана нагрузки операций обработки задач приложения реального времени. Эти таблицы могут, в частности, содержать список операций обработки приложения, и список параметров, определяющих временные интервалы, выделенные для каждой из операций обработки. В списке операций обработки приложения каждая операция Ti обработки может быть связана с одним или более временными интервалами типа лимита Qi времени и типа запаса Mi времени. В списке временных интервалов каждый интервал связан с операцией обработки или фрагментом операции обработки, с типом (лимитом, запасом или временем ожидания) и с продолжительностью временного интервала и/или с временем начала и временем конца временного интервала.
На Фиг. 6 этап S1 выполняется в начале временного интервала, обозначенного t<j>. Процессор PRC обеспечивает доступ к списку временных интервалов для определения параметров, необходимых для активации сторожевого процесса WD так, что последний запускается в конце временного интервала t<j>, и активирует сторожевой процесс. На этапе S2 процессор PRC определяет тип временного интервала t<j>. Если временной интервал t<j> имеет тип лимита Q, процессор PRC запускает операцию T[t<j>] обработки, связанную с временным интервалом t<j>, на этапе S3. Если временной интервал t<j>имеет тип запаса М, процессор PRC выполняет этап S4. На этапе S4 процессор PRC тестирует индикатор ER(T[t<j>]) ошибки, связанный с операцией T[t<j>] обработки. Если этот индикатор ER(T[t<j>]) ошибки указывает на то, что операция T[t<j>] обработки соответствует ошибке превышения лимита, процессор PRC продолжает выполнение операции T[t<j>] обработки на этапе S5. После выполнения этапов S3, S5 и в том случае, когда операция T[t<j>] обработки не соответствует ошибке превышения лимита, процессор PRC выполняет этап S6 для увеличения индекса j, посредством чего возможен переход к операции обработки следующего временного интервала t<j+l>.
На этапе S10 на Фиг. 6В, который выполняется, когда сторожевой процесс WD, активированный для временного интервала t<j>, запущен (в случае превышения лимита или запаса), процессор PRC определяет, произошел ли запуск сторожевого процесса из-за истечения лимита времени или запаса времени операции обработки путем тестирования типа (Q / М / NA) временного интервала t<j>. Если запуск сторожевого процесса WD произошел из-за истечения лимита времени, выполняется этап S11. Если этот запуск произошел из-за истечения запаса времени, выполняются этапы S12-S14.
На этапе S11 лимит времени, выделенный для операции T[t<j>] обработки, истекает до конца выполнения операции обработки. Процессор PRC далее переходит в режим обработки ошибок, например, путем активации индикатора ER ошибки для операции T[t<j>] обработки. На этапе S12 запас времени, выделенный для операции T[t<j>] обработки, истекает без выполнения завершения операции обработки. Процессор PRC далее останавливает выполнение операции T[t<j>] обработки. На этапе S13 процессор PRC может сохранять, что ошибка превышения лимита времени определена для операции T[t<j>] обработки. На этапе S14 процессор PRC может выполнять общую операцию обработки ошибок, которая обеспечена в ядре реального времени. Эта общая операция обработки ошибок является достаточно короткой такой, чтобы не переходить на следующее временное окно и, таким образом, на время, выделенное для следующей операции обработки, для того, чтобы соблюдать правило отсутствия взаимовлияния между операциями обработки. Также может быть обеспечено выполнение операции обработки ошибок, характерной для приложения, или операции T[t<j>] обработки при превышении лимита во время следующего временного окна, выделенного для операции обработки, также для соблюдения правила отсутствия взаимовлияния между операциями обработки.
Следует отметить, что продолжение выполнения операции обработки в случае ошибки превышения лимита времени следует из простого проектного решения приложения реального времени. В некоторых случаях может быть предусмотрено выполнение других режимов обработки этой ошибки, которые отличаются от ранее описанных, таких как постоянная остановка операции обработки во время ошибки превышения лимита и выполнение альтернативной операции обработки, обеспеченной для операции с ухудшенными характеристиками задачи или системы реального времени, требующей более короткое время выполнения, чем запас времени операции обработки ошибок.
В случае выполнение фрагментированной операции обработки, случай, в котором сторожевой процесс указывает конец лимита, выделенного для первого или промежуточного фрагмента, должен быть отделен от случая, в котором он указывает конец потребности последнего фрагмента операции обработки. В первом случае сторожевой процесс указывает только изменение одной операции обработки на другую при изменении временного окна во время выполнения фрагментированной операции обработки. Во втором случае сторожевой процесс указывает на то, что лимит фрагментированной операции обработки полностью использован, таким образом, нарушение.
Согласно одному варианту выполнения, когда фрагментированные операции обработки остаются в плане планирования, переменная состояния связана с каждой операцией обработки или фрагментом операции обработки для указания является ли он первым фрагментом или промежуточным фрагментом фрагментированной операции обработки, или последний является нефрагментированной операцией обработки, или последним фрагментом фрагментированной операции обработки. Эта переменная состояния используется, чтобы не выделять никакого запаса для фрагмента операции обработки, если он представляет собой первый фрагмент или промежуточный фрагмент, и не создавать никакой ошибки по истечении лимита времени фрагмента операции обработки. Эта переменная состояния может быть автоматически создана для каждой операции обработки или фрагмента, например, при создании выполняемого кода приложения реального времени, и вставлена в таблицы, определяющие план нагрузки приложения.
Эта переменная состояния может быть использована, например, как показано на Фиг. 7. Таким образом, Фиг. 7 показывает этапы S10-S14 на Фиг. 6В и дополнительный этап S15, помещенный между этапами S10 и S11. Этап S15 далее выполняется, когда сторожевой процесс WD запущен при истечении лимита времени операции T[t<j>] обработки. На этапе S15 процессор PRC тестирует переменную LF(T[t<j>]) состояния, указывающую, является ли операция T[t<j>] обработки либо первым фрагментом, либо промежуточным фрагментом фрагментированной операции обработки, либо целой операцией обработки (не фрагментированной), либо последним фрагментом фрагментированной операции обработки. Если переменная LF(T[t<j>]) указывает на то, что выполняемая операция T[t<j>] обработки представляет собой целую операцию обработки или последний фрагмент фрагментированной операции обработки, этап S11, описанный выше, выполняется для активации режима обработки ошибок. В противном случае, режим обработки ошибок не активируется.
Следует отметить, что, так как никакого запаса времени не выделено для первого фрагмента или промежуточного фрагмента фрагментированной операции обработки, весь запас времени, выделенный для фрагментированной операции обработки, выделяется для последнего фрагмента фрагментированной операции обработки.
Согласно одному варианту выполнения переменная состояния связана с каждой операцией обработки или фрагментом операции обработки для указания выполняет или нет последняя входы и/или выходы в отношении процессора PRC. Ввод/вывод означает, например, доступ для записи или чтения для глобальной переменной приложения реального времени в памяти VM или NVM, или передачу сигнала или данных между процессором PRC и периферийным блоком через схему РНС. Эта переменная состояния используется для предопределения операции обработки, не выполняющей никаких входов и/или выходов, без ожидания начала временного окна, с которым он связан. Эта переменная состояния может быть автоматически создана для каждой операции обработки или фрагмента операции обработки, например, при создании выполняемого кода приложения реального времени, и вставлена в таблицы, определяющие план нагрузки и план планирования приложения.
Эта переменная состояния может быть использована, например, как показано на Фиг. 8. Фиг. 8 показывает этапы S1-S6 на Фиг. 6А и два дополнительных этапа S8 и S9, помещенных между этапами S6 и S1. На этапе S8 процессор PRC определяет следующий временной интервал, связанный с операцией Nxt.(T) обработки, и если этот временной интервал имеет тип лимита Q, он тестирует переменную состояния, указывающую наличие входов/выходов в следующей операции Nxt.(T) обработки в плане нагрузки. Если переменная IO(Nxt.(T)) указывает на то, что операция Nxt.(T) обработки не выполняет никакие входы/выходы, процессор PRC выполняет этап S9 для запуска выполнения операции Nxt.(T) обработки на этапах S1-S2-S3 для временного интервала, определенного на этапе S8. В противном случае, этап S1 выполняется для временного окна t<j+1>, которое следует за временным окном, которое только что обработано. Естественно, понятно, что этапы на Фиг. 7 и 8 могут быть выполнены в совокупности, чтобы выполнять обе переменные LF и IO состояния.
Эта конструкция, таким образом, обеспечивает динамическое предсказание операций обработки, запланированных в плане последовательности, и, таким образом, перенесение связанных неиспользованных запасов, что приводит к группировке вместе неиспользованных запасов и любого времени ожидания в один запас для временного окна, связанного с операцией обработки или фрагментом операции обработки, выполняющим входы/выходы, которые не могут быть спрогнозированы. Эта конструкция не отрицает детерминированное поведение системы и вышеупомянутые гарантии операций. Группировка запасов и/или времени ожидания обеспечивает преимущество обеспечения выполнения вспомогательных деятельностей, которые могут содержать выполнение некритических задач или задач не реального времени, которые могут, таким образом, выполняться с меньшим количеством прерываний и, таким образом, меньшим количеством переключений в контексте выполнения. Результат заключается в приросте производительности и, таким образом, энергопотребления и средней температуры процессора. Если процессор входит в режим ожидания во время сгруппированных запасов, то он может входить в режим ожидания в течение длительного времени, что приводит к снижению температуры и энергопотребления в результате продолжительности этого режима ожидания. Эта группировка запасов также обеспечивает уменьшение количества активаций механизмов приведения процессора в режим ожидания. В дополнение, возможность прогнозирования операций обработки обеспечивает лучшее определение параметров системы реального времени и, таким образом, достижение более высокой общей производительности. Следует отметить, что эти преимущества достигаются без влияния на операционную надежность системы реального времени.
В большинстве систем реального времени измерение времени для управления временем выполнения операций обработки и измерение времени, используемое для описания временных ограничений (разбивка времени во временных окнах), основаны на одном и том же источнике, исходя из схемы синхронизации, например, схемы CLK. Однако это условие не является обязательным. Более того, некоторые системы реального времени могут быть синхронизированы для ограничения временных окон нерегулярными внешними событиями (не связанными с сигналом синхронизации). Например, эти внешние события могут быть связаны положением перемещающегося объекта, как угловое положение коленчатого вала, движущегося на переменной скорости, или фазой переменного электрического сигнала, период которого не является строго постоянным.
В традиционном подходе, необходимость использования нерегулярного временного базиса не обеспечивает простое создание последовательности задач, что приводит к использованию алгоритмов динамического планирования. Наоборот, с помощью способа, представленного выше, возможно продолжать точно таким же образом. Потребности во времени и лимиты времени, тем не менее, выражены в единице времени выполнения процессора, определяемой первым сигналом синхронизации, тогда как временные ограничения и, таким образом, последовательность операций обработки выражены в другом временном базисе, определяемом нерегулярным вторым сигналом, таким как сигнал измерения углового положения, например. Однако, так как приложение может быть запланировано, имеется отношение между двумя сигналами, посредством чего возможно определять минимальную продолжительность единицы времени второго сигнала, измеренную с помощью первого сигнала синхронизации. В этом случае значение множителя Kx может, тем не менее, быть вычислено согласно этому минимальному значению. В результате все еще возможно определение запасов потребности путем умножения потребностей на множитель Kx.
Согласно одному варианту выполнения множитель Kx установлен на значение, вычисленное согласно минимальной продолжительности единицы времени, определенной посредством второго сигнала, измеренного с помощью первого сигнала синхронизации. Результат заключается в том, что соответственные продолжительности запасов зафиксированы, тогда как время ожидания изменяется и, в частности, увеличивается, когда единица времени, определенная посредством второго сигнала, смещается от ее минимального значения.
Те же признаки и преимущества, как ранее описанные в отношении производительности и надежности, таким образом, сохраняются независимо от изменений скорости нерегулярного временного базиса, на основе которого определяются ограничения времени выполнения (т.е. временные окна).
Специалисту в этой области техники понятно, что настоящее изобретение допускает различные альтернативные варианты выполнения и различные применения. В частности, изобретение не ограничивается использованием запасов времени для продолжения выполнения операции обработки во время превышения лимита. Более того, другие операции обработки ошибок могут быть обеспечены, такие как выполнение операции обработки ошибок, характерной для операции обработки, например.
Более того, запасы времени, выделенные для операции обработки приложения реального времени, необязательно пропорциональны лимитам времени, выделенным для этих операций обработки. Другие режимы для вычисления соответственных продолжительностей запасов времени могут быть использованы. Важно только, что приложение реального времени может быть запланировано, заданные лимиты и запасы времени выделены, и вычислительные ресурсы времени выделены для приложения. Таким образом, запас, выделенный для каждой операции обработки, может быть конкретно определен согласно операции обработки.
Цитируемые документы
[1] «Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment», C.L. Liu, J.W. Layland, Journal of the Association for Computing Machinery, vol. 20, №. 1, январь 1973, стр. 46-61.
[2] «Foundations of Real-Time Computing: Scheduling and Resource Management», под ред.  M. Van Tilborg, Gary M. Koob, 1991, Kluwer Academic Publishers.
[3] «A Method and a Technique to Model and Ensure Timeliness in Safety Critical Real-Time Systems», , V. David, Fourth IEEE International Conference on Engineering of Complex Computer Systems, 1998.
[4] Заявка на патент WO/2002/039277 или US/2004/0078547.
[5] «The Worst-Case Execution Time Problem - Overview of Methods and Survey of Tools», R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, P. Stenstrom, ACM Transactions on Embedded Computing Systems (TECS), 2007.
[6] «Giotto: A Time-Triggered Language for Embedded Programming», T.A. Henzinger, B. Horowitz, С.M. Kirsch, EMSOFT 2001, стр. 166-184, 2001, Springer-Verlag.
[7] Заявка на патент WO/2006/050967.
[8] Заявка на патент US/2010/0199280.