¿Este algoritmo es un algoritmo de sistema en tiempo real existente?

Question

He desarrollado un algoritmo de programación que proporciona garantías probabilísticas en tiempo real, pero parece demasiado obvio y simple para ser novedoso. Me ha costado trabajo relacionarlo con los algoritmos de programación publicados en tiempo real (EDF, servidor esporádico, etc.). ¿El siguiente algoritmo de programación es un algoritmo conocido en tiempo real?

Supuestos:

• Todas las tareas se han extraído de una distribución donde porcentaje X de tareas requieren menos de R cpu-segundo
• Todas las tareas tienen el mismo plazo. Si una tarea tarda más de T segundos, entonces es un fracaso para esa tarea
• llegadas de tareas están separados por un conocido de tiempo mínimo entre llegadas, MIN_INTER_ARRIVE_T
• El planificador tiene una taskset que puede contener un máximo de tareas H en cualquier momento (durante cada paso de tiempo, todas las tareas del taskset hacen iguales progreso mediante el intercambio de la CPU por igual)
• tareas no se afectan entre sí

Garantía:

• (1) Si X Educación física rcentaje de tareas requieren menos de cpu-segundo R y (2) R < = T/H, (3) MIN_INTER_ARRIVE_T> = T/H, entonces al menos porcentaje X de tareas terminará dentro de T segundos

Algoritmo :

• Si llega una tarea y el conjunto de tareas está lleno, desaloje la tarea que usó la mayor cantidad de CPU. Las suposiciones garantizan que dicha tarea habrá utilizado al menos R cpu-segundos. Por lo tanto, las únicas tareas que se pueden desalojar serán tareas que son fallas de todos modos. Cualquier tarea que requiera menos de R cpu-seconds se completará a tiempo.

Answer 1

No soy un experto en la programación dura en tiempo real, pero así es como me suena tu algoritmo.

Se lleva muy fuerte parecido con lo que ocurre en los sistemas aeroespaciales. Su sistema se ve más flexible, pero básicamente todo se reduce a saber de antemano que tiene los recursos para ejecutar las tareas que necesita ejecutar.

Los sistemas aeroespaciales integrados críticos prefieren ser deterministas, pero como una protección contra fallas potenciales (las tareas pueden durar más de lo asignado, si se permiten), el motor de tareas interrumpirá esas tareas para permitir que otras tareas se completen. Cualquier ciclo libre que quede a veces se puede usar para completar las tareas interrumpidas, o se considera que la tarea ha fallado.

Tenga en cuenta que sólo se puede fallar tareas que no son críticos, por lo que debe construir sus tareas críticas con cuidado, o tener un sistema de prioridad mediante el cual las tareas críticas tienen la oportunidad de completar no importa qué.

Usted es ahora de vuelta al punto de partida: hay que asegurarse de que los Recursos son suficientes para ejecutar las tareas requeridas por adelantado.

hth,
asoundmove.

Answer 2

Esto parece similar al algoritmo servidor de ancho de banda constante