operating-system - que - planificacion expropiativa

Programadores de tareas

Question

Tuve una discusión interesante con algunos colegas sobre las mejores estrategias de programación para tareas en tiempo real, pero no todos entendieron bien las estrategias de programación comunes o útiles.

Para su respuesta, elija una estrategia y repase con detalle, en lugar de dar un poco de información sobre varias estrategias. Si tiene algo que agregar a la descripción de otra persona y es breve, agregue un comentario en lugar de una nueva respuesta (si es larga o útil, o simplemente una descripción mucho mejor, entonces use una respuesta)

• ¿Cuál es la estrategia? Describa el caso general (suponiendo que las personas saben qué es una cola de tareas, semáforos, bloqueos y otros fundamentos del sistema operativo fuera del planificador mismo)
• Para qué está optimizada esta estrategia (latencia de tareas, eficiencia, tiempo real, fluctuación de fase, intercambio de recursos, etc.)
• ¿Es en tiempo real, o puede hacerse en tiempo real?

Estrategias actuales:

• Preferencial basado en prioridad
• Reloj más lento de potencia más baja

-Adán

Answer 1

Como se describe en un documento titulado Programación de tareas en tiempo real para sistemas embebidos con energía consciente , Swaminathan y Chakrabarty describen los desafíos de la programación de tareas en tiempo real en dispositivos de baja potencia (integrados) con múltiples velocidades de procesador y perfiles de consumo de energía disponibles. El algoritmo de programación que describen (y se muestra que es solo aproximadamente 1% peor que una solución óptima en las pruebas) tiene una forma interesante de programar tareas que llaman LEDF Heuristic.

Del papel:

La primera fecha límite de baja energía, la primera heurística, o simplemente LEDF, es una extensión del conocido primer algoritmo de límite de tiempo (EDF). La operación de LEDF es la siguiente: LEDF mantiene una lista de todas las tareas liberadas, llamada la "lista lista". Cuando se liberan tareas, se elige ejecutar la tarea con la fecha límite más cercana. Se realiza una comprobación para ver si la fecha límite de la tarea se puede cumplir ejecutándola a la tensión más baja (velocidad). Si se puede cumplir el plazo, LEDF asigna el voltaje más bajo a la tarea y la tarea comienza la ejecución. Durante la ejecución de la tarea, otras tareas pueden ingresar al sistema. Se supone que estas tareas se colocan automáticamente en la "lista lista". LEDF nuevamente selecciona la tarea con la fecha límite más cercana para ser ejecutada. Mientras haya tareas pendientes de ejecución, LEDF no mantiene el procesador inactivo. Este proceso se repite hasta que todas las tareas hayan sido programadas.

Y en pseudo-código:

Repeat forever {
    if tasks are waiting to be scheduled {
        Sort deadlines in ascending order
        Schedule task with earliest deadline
        Check if deadline can be met at lower speed (voltage)
        If deadline can be met,
            schedule task to execute at lower voltage (speed)
        If deadline cannot be met,
            check if deadline can be met at higher speed (voltage)
        If deadline can be met,
            schedule task to execute at higher voltage (speed)
        If deadline cannot be met,
            task cannot be scheduled: run the exception handler!
    }
}

Parece que la programación en tiempo real es un problema interesante y en evolución a medida que los dispositivos pequeños y de baja potencia se vuelven más omnipresentes. ¡Creo que este es un área en la que veremos muchas investigaciones adicionales y espero estar al tanto!

Answer 2

Un esquema común de programación en tiempo real es usar multitarea preventiva basada en prioridades.
Cada tarea tiene asignado un nivel de prioridad diferente.
La tarea de mayor prioridad en la lista de espera será la tarea que se ejecuta. Se ejecutará hasta que ceda la CPU (es decir, demoras, esperas en un semáforo, etc.) o una tarea de mayor prioridad esté lista para ejecutarse.

La ventaja de este esquema es que el diseñador del sistema tiene control total sobre qué tareas se ejecutarán con qué prioridad. El algoritmo de programación también es simple y debe ser determinista.

Por otro lado, las tareas de baja prioridad podrían faltar para la CPU. Esto indicaría un problema de diseño.