Является ли этот алгоритм существующим алгоритмом системы реального времени?

Question

Я разработал алгоритм планирования, который обеспечивает вероятностные мягкие гарантии в реальном времени, но он кажется слишком очевидным и простым, чтобы быть новым.Хотя мне было трудно связать это с опубликованными алгоритмами планирования в реальном времени (EDF, спорадический сервер и т. Д.).Является ли следующий алгоритм планирования известным алгоритмом реального времени?

Допущения:

• Все задачи взяты из распределения, где процент X задач требует меньше, чем R cpu-секунд
• Все задачи имеют одинаковый срок исполнения.Если задача длится дольше, чем T секунд, то она является ошибкой для этой задачи
• Прибытия задачи разделены известным минимальным временем между поступлениями, MIN_INTER_ARRIVE_T
• Планировщик имеет набор задач, которыйудерживать максимум H задач в любое время (на каждом временном шаге все задачи в наборе задач достигают одинакового прогресса при одинаковом распределении ресурсов процессора)
• Задачи не могут влиять друг на друга

Гарантия:

• (1) Если для процента X задач требуется меньше R cpu-секунд и (2) R <= T / H, (3) MIN_INTER_ARRIVE_T> = T / H, то по крайней мере Xпроцент задач завершится в течение T секунд

Алгоритм:

• Если задача прибывает и набор задач заполнен, то удалите задачу, которая использовала больше всего ЦП.Предположения гарантируют, что такая задача будет использовать не менее R cpu-секунд.Таким образом, единственными задачами, которые могут быть исключены, будут задачи, которые в любом случае являются неудачными.Любая задача, для которой требуется меньше R cpu-секунд, будет выполнена вовремя.

Answer 1

Я не специалист по жесткому планированию в реальном времени, но именно так ваш алгоритм звучит для меня.

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

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

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

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

hth,
asoundmove.

Answer 2

Это похоже на алгоритм сервера постоянной пропускной способности