Алгоритм оценки максимального времени отклика задач в многопроцессорных системах с интервальной неопределенностью длительности выполнения работ

В данной статье предложен алгоритм оценки максимального времени отклика задач (Worst Case Response Time — WCRT) в многопроцессорных системах с планировщиками с приоритетом и вытеснением и интервальной неопределенностью длительности выполнения работ. Между задачами имеются зависимости по данным. Для каждой задачи задан приоритет, период и интервал [BCET, WCET], которому принадлежит время выполнения на процессоре работ этой задачи. Если уменьшение времени выполнения задачи A может привести к увеличению времени отклика задачи B, то задача A называется аномальной задачей для задачи B. Согласно выбранному авторами подходу, для получения оценки WCRT некоторой задачи необходимо выполнить два шага. На первом шаге с помощью предложенного в работе алгоритма осуществляется построение множества задач, аномальных для заданной задачи. Приведено доказательство корректности этого алгоритма. На втором шаге с помощью генетического алгоритма выполняется поиск WCRT. Пространство поиска — множество всевозможных наборов длительностей выполнения аномальных задач. Было разработано инструментальное средство на языке Python3, реализующее предложенный подход. Проведено экспериментальное исследование, в ходе которого предложенный метод сравнивался по точности и скорости с двумя известными методами оценки WCRT: методом, не учитывающим интервальную неопределенность, т.е. предполагающим, что время выполнения всех работ равно WCET, а также с переборным методом. Экспериментальное исследование показало, что в отличие от переборного метода, предложенный метод применим для анализа вычислительных систем реальной размерности, а также позволяет достичь большей точности, чем метод, не учитывающий интервальную неопределенность.