IMPLEMENTACIÓN DEL ALGORITMO DE PRIORIDADES DUALES
EN RT-LINUX
Autor: Luis Antonio Búrdalo RapaAsignatura: Sistemas de Tiempo RealCurso: 2003 - 2004
IMPLEMENTACIÓN DEL ALGORITMO DE PRIORIDADES DUALES EN RT-LINUX
DESCRIPCIÓN DEL ALGORITMO IMPLEMENTACIÓN EJEMPLOS DE EJECUCIÓN MEJORAS MOLONAS
DESCRIPCIÓN DEL ALGORITMO DE PRIORIDADES DUALES
TRES BANDAS DE PRIORIDADES– ALTA > MEDIA > BAJA
CADA TAREA CRÍTICA– 2 PRIORIDADES: BANDA BAJA y BANDA ALTA
CADA TAREA ACRÍTICA– PRIORIDAD BANDA MEDIA
RESTRICCIÓN– TAREAS CRÍTICAS PLANIFICABLES EN BANDA ALTA
DESCRIPCIÓN DEL ALGORITMO DE PRIORIDADES DUALES
Activación de tareas CRÍTICAS en BANDA BAJA– Expulsadas por banda MEDIA y ALTA
INSTANTE DE PROMOCIÓN:– La prioridad de la tarea CRÍTICA pasa a BANDA ALTA
DESCRIPCIÓN DEL ALGORITMO DE PRIORIDADES DUALES
IMPLEMENTACIÓN
Sistema Operativo:– RT-Linux 3.2-pre1-ptm1.0– Linux kernel 2.4.18
Modificaciones– Soporte básico de la política SCHED_DUAL– Cambios de estado en tareas “duales”:
clock_nanosleep(...), rtl_schedule() y findpreemptor(...)
IMPLEMENTACIÓN: Soporte básico
struct sched_param{int sched_priority;int low_priority;int high priority;struct timespec promotion_time;long long absolute_promotion_time;
}
#define SCHED_OTHER 0#define SCHED_FIFO 1#define SCHED_RR 2#define SCHED_DUAL 3
/* Modificacion de las funciones * pthread_setschedparam * pthread_getschedparam */
include/rtl_sched.hinclude/linux/sched.h
typedef struct STRUCT_PTHREAD_ATTR{ ... int policy; ...} pthread_attr_t;
pthread_attr_init(...)pthread_attr_setschedpolicy(...)pthread_attr_getschedpolicy(...)
include/rtl_sched.h
IMPLEMENTACIÓN: clock_nanosleep(...)
int clock_nanosleep(clockid_t clock_id, int flags,const struct timespec *rqtp, struct timespec *rmtp){
/* Prepara todo antes de dormirse */if (self->policy == SCHED_DUAL){
self->sched_param.sched_priority=self->sched_param.low_priority;/* SIEMPRE SE DUERME A BAJA PRIORIDAD!!! */
self->sched_param.absolute_promotion_time = timeout + timespec_to_ns(&self->sched_param.promotion_time);
/* SOLO PARA EVITAR CONVERSIONES ENTRE timespec Y hrtime_t */}
/* Se marca como suspendido y llama a rtl_schedule() * para que entre otra tarea * * A partir de aquí se ejecutara al despertarse */}
schedulers/rtl_sched.c
IMPLEMENTACIÓN: rtl_schedule(...)
int rtl_schedule(){ /* ... */ for (t = sched->rtl_tasks; t; t = t->next) { /* Para cada una de las tareas del sistema: * 1) Comprobar si la tarea esta dormida y le toca despertarse */ /* ... */
if ((t->policy == SCHED_DUAL) && (t->sched_param.sched_priority == t->sched_param.low_priority)){ /* 2) Si la tarea es SCHED_DUAL y esta pendiente de promocion, * comprobar si es hora de promocionarla */ if (now >= t->sched_param.absolute_promotion_time){ t->sched_param.sched_priority=t->sched_param.high_priority; } } /* 3) Quedarse con la tarea activa de mayor prioridad => new_task */ } /* for */
/* ... */
schedulers/rtl_sched.c
IMPLEMENTACIÓN: rtl_schedule(...)
/* ... */ if ( (preemptor = find_preemptor(sched,new_task))) { /* Si el preemptor es SCHED_DUAL, hay que tener en cuenta el instante * en el que va a interrumpir a la siguiente tarea (activacion o promocion?) */ if ((preemptor->policy == SCHED_DUAL) && (preemptor->sched_param.sched_priority) <= new_task->sched_param.sched_priority) { /* Promocion */ (sched->clock)->settimer(sched->clock,preemptor->sched_param.absolute_promotion_time-now); } else { (sched->clock)->settimer(sched->clock, preemptor->resume_time - now); } } else { (sched->clock)->settimer(sched->clock, (HRTICKS_PER_SEC / HZ) / 2); } set_bit (RTL_SCHED_TIMER_OK, &sched->sched_flags);/* ... * Cambio de contexto efectivo si procede, etc... */}
schedulers/rtl_sched.c
IMPLEMENTACIÓN: find_preemptor(...)
/* Solo podra ser preemptor alguien que se despierte con mayor * prioridad o alguien que se promocione a mayor prioridad */inline static struct rtl_thread_struct * find_preemptor(schedule_t *s, struct rtl_thread_struct *chosen){/* ... */ for (t = s->rtl_tasks; t; t = t->next) { /* Para cada una de las tareas del sistema: * 1) Comprobar si la tarea esta dormida y si su activacion puede expulsar * de la cpu a la tarea chosen */ if (test_bit(RTL_THREAD_TIMERARMED, &t->threadflags)) { if (t->sched_param.sched_priority > chosen->sched_param.sched_priority){ if(!preemptor || (t->resume_time < preemption_time)){ /* Por ahora es quien antes se despierta con mayor prioridad que chosen */ preemptor = t; preemption_time=t->resume_time; } } }
schedulers/rtl_sched.c
IMPLEMENTACIÓN: find_preemptor(...)
/* ... */ if ((t->policy == SCHED_DUAL) && (t->sched_param.sched_priority==t->sched_param.low_priority)){ /* Esta tarea SCHED_DUAL esta esperando su promocion: * Se comprueba su prioridad alta para saber si puede ser preemptor */ if (t->sched_param.high_priority > chosen->sched_param.sched_priority){ /* Se comprueba si la promocion es posterior al preemptor */ if(!preemptor || (t->sched_param.absolute_promotion_time < preemption_time)){ /* Es anterior => Se convierte en el nuevo preemptor! */ preemptor = t; preemption_time=t->sched_param.absolute_promotion_time; } } } } /* for */ return preemptor;}
schedulers/rtl_sched.c
EJEMPLO SIMPLE
Dos tareas– T2 SCHED_FIFO Prioridad: 9
– T3 SCHED_DUAL Prioridades: 5 y 10 Tiempo de promoción: 5 mseg
Tarea adicional T1 para soporte de traza
EJEMPLO SIMPLE
EJEMPLO SIMPLE
EJEMPLO SIMPLE
EJEMPLO SIMPLE
OTRO EJEMPLO SIMPLE
Tres tareas– T2 SCHED_FIFO Prioridad 7
– T3 SCHED_DUAL Prioridades: 4 y 10 Tiempo de promoción: 5 mseg
– T3 SCHED_DUAL Prioridades: 5 y 11 Tiempo de promoción: 5 mseg
Tarea adicional T1 para soporte de traza
OTRO EJEMPLO SIMPLE
MEJORAS MOLONAS (1):PRIORIDAD DE LINUX
int change_linux_priority(int priority){ struct rtl_sched_param linux_sched_param; linux_sched_param.sched_priority=priority; pthread_setschedparam( , SCHED_FIFO, &linux_sched_param);
return 0;}
MEJORAS MOLONAS (1):PRIORIDAD DE LINUX
int change_linux_priority(int priority){ struct rtl_sched_param linux_sched_param; linux_sched_param.sched_priority=priority; pthread_setschedparam(pthread_linux(), SCHED_FIFO, &linux_sched_param);
return 0;}
MEJORAS MOLONAS (2):clock_nanosleep_until_promotion
clock_nanosleep_until_promotion(clockid_t clock_id,int flags, struct timespec *rmtp)
Duerme al hilo hasta que llega su instante de promoción PARTES INICIALES – PARTES FINALES
schedulers/rtl_sched.c
MEJORAS MOLONAS (3):change_absolute_promotion_time
change_absolute_promotion_time(hrtime_t nanoseconds, int flags)
Cambia el instante de promoción del hilo:– Adelanta o retrasa el instante– Tiempo absoluto o relativo
schedulers/rtl_sched.c
MEJORAS MOLONAS (3):change_absolute_promotion_time
change_absolute_promotion_time(hrtime_t nanoseconds, int flags)
Cambia el instante de promoción del hilo:– Adelanta o retrasa el instante– Tiempo absoluto o relativo
schedulers/rtl_sched.c
IMPLEMENTACIÓN DEL ALGORITMO DE PRIORIDADES DUALES
EN RT-LINUX
Autor: Luis Antonio Búrdalo RapaAsignatura: Sistemas de Tiempo RealCurso: 2003 - 2004