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

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

Предположения:

  • Все задачи взяты из дистрибутива, где X процент задач требует меньше, чем R cpu-seconds
  • Все задачи имеют одинаковый срок. Если задача занимает больше времени, чем 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-секунд, будет завершена вовремя.

Ответы

Ответ 1

Я не эксперт в жестком режиме реального времени, но это то, что ваш алгоритм мне нравится.

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

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

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

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

НТН,
asoundmove.

Ответ 2

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