Cómo distribuir procesos a lo largo del tiempo obteniendo el número mínimo de "colisiones"

Question

Estoy desarrollando un programador para un sistema integrado. Este planificador llamará a cada proceso cada X milisegundos; esta vez se puede configurar por separado para cada proceso, por supuesto.

Todo está codificado y llama a cada proceso como debería; el problema que estoy enfrentando es la siguiente: Imagínese me puse 4 procesos que se llamará cada 10, 15, 5 y 30 milisegundos respectivamente:

A: 10ms 
B: 15ms 
C: 5ms 
D: 30ms 

El resultado de llamar con el tiempo será:

     A   | 
     A B A  B   | 
    C C C C C C C  | processes being called 
         D   | 
---------------------------------- 
0 5 10 15 20 25 30 35... ms 

El problema es que cuando se alcanzan los 30 ms, todos los procesos se convocan en el mismo momento (uno tras otro) y esto puede retrasar la ejecución correcta desde aquí.

Esto se puede resolver agregando un retraso a cada proceso (pero preservando su frecuencia de llamada), por lo que las frecuencias dejan de ser múltiplos entre sí. Mi problema es que no sé cómo calcular el retraso para aplicar a cada proceso, por lo que se minimiza el número de colisiones.

¿Hay algún algoritmo conocido para esto o alguna guía matemática?

Gracias.

Answer 1

Dado un conjunto de intervalos, puede encontrar el momento en el que las horas de inicio coincidirían (suponiendo que no hay compensaciones) al encontrar el least common multiple mencionado por Jason en un comentario a su publicación. Puede encontrar el LCM haciendo la factorización prima de los intervalos para un conjunto de tareas.

Parece que el greatest common divisor (o el máximo factor común GCF) podría ser el número más útil para calcular. Ese número le dará un intervalo en el que se repite sucederá. En su ejemplo, el MCD es 5. Con un MCD de 5, es posible agregar un desplazamiento inicial de 1, 2, 3, etc. a cada tarea para evitar la superposición de las horas de inicio. Por lo tanto, con un MCD de 5, puede tener hasta 5 tareas que tienen tiempos de inicio que nunca se superpondrían. Con un FCM de 20, puede tener hasta 20 tareas programadas sin superposición de horas de inicio.Si dos (o más) tareas son relativamente primarias (GCF = 1), entonces se producirá una superposición sin importar qué compensación use para esas tareas si los intervalos nunca cambian.

Answer 2

No hay una solución perfecta para esto, colisionarán de vez en cuando. Sugiero que se agregue un valor aleatorio pequeño (0,01-0,1ms) a la duración del ciclo, por lo que a la larga rara vez se llamarán al mismo tiempo.

Alternativamente, si tiene una granularidad de programador de 5 ms, el primer subproceso se llama siempre a X + 1 ms, el segundo a X + 2, etc., de modo que siempre se garantiza 1 ms de ejecución ininterrumpida (si tiene 10 subprocesos, entonces será X + 0.5, X + 1, X + 1.5). Pero esto podría ser bastante complicado de implementar.

Answer 3

Este tipo de problema se relaciona directamente con el dominio de la programación en tiempo real y los algoritmos de programación. Tomé una clase sobre este tema en la universidad, y si mal no recuerdo, Rate-monotonic scheduling es el tipo de algoritmo que estás buscando.

La idea es asignar prioridades a los trabajos que son inversamente proporcionales a su período, es decir, cuanto menor sea el período, mayor será la prioridad. Pero esto funciona mejor si puede interrumpir sus trabajos y reanudarlos más tarde.

Existen otras alternativas, como EDF (earliest deadline first), pero estos son algoritmos de programación dinámica (es decir, las prioridades se asignan durante la ejecución).

Answer 4

La solución fácil es cambiar el horario en el que llama a las subrutinas. Es decir. en lugar de 5, 10, 15 y 30 ms, ¿puedes vivir, p. con 5, 15, 15 y 30? A continuación, puede utilizar el siguiente patrón: (proc A = 5 ms, B, C = 15 ms proc, D proc = 30 ms):

AAAAAAAAAAAAAAAAAAAA ... 
B B B B B B B ... 
    C C C C C C C ... 
    D  D  D  ... 

Estoy seguro de que se puede generalizar esta idea, pero funciona solo si puedes cambiar los intervalos estáticos.

Si no puede cambiar los intervalos, y también es necesario obedecer estrictamente, entonces te son una especie de fuera de suerte ya que no existen parámetros para cambiar :)