IMPLEMENTACIÓN DEL ALGORITMO
DE PRIORIDADES DUALES
EN RT-LINUX
Autor:
Luis Antonio Búrdalo Rapa
Asignatura:
Sistemas de Tiempo Real
Curso:
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
–

CADA TAREA CRÍTICA
–

2 PRIORIDADES: BANDA BAJA y BANDA ALTA
CADA TAREA ACRÍTICA
–

ALTA > MEDIA > BAJA
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
include/rtl_sched.h
struct sched_param{
include/linux/sched.h
int sched_priority;
int low_priority;
int high priority;
struct timespec promotion_time;
long long absolute_promotion_time;
}
#define
#define
#define
#define
SCHED_OTHER
SCHED_FIFO
SCHED_RR
SCHED_DUAL
0
1
2
3
include/rtl_sched.h
typedef struct STRUCT_PTHREAD_ATTR{
...
int policy;
...
/* Modificacion de las funciones
} pthread_attr_t;
*
pthread_setschedparam
*
*/
pthread_getschedparam
pthread_attr_init(...)
pthread_attr_setschedpolicy(...)
pthread_attr_getschedpolicy(...)
IMPLEMENTACIÓN: clock_nanosleep(...)
schedulers/rtl_sched.c
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
*/
}
IMPLEMENTACIÓN: rtl_schedule(...)
schedulers/rtl_sched.c
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 */
/* ... */
IMPLEMENTACIÓN: rtl_schedule(...)
schedulers/rtl_sched.c
/* ... */
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...
*/
}
IMPLEMENTACIÓN: find_preemptor(...)
schedulers/rtl_sched.c
/* 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;
}
}
}
IMPLEMENTACIÓN: find_preemptor(...)
schedulers/rtl_sched.c
/* ... */
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;
}
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
–
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
Prioridad 7
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
schedulers/rtl_sched.c
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
MEJORAS MOLONAS (3):
change_absolute_promotion_time
schedulers/rtl_sched.c

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
MEJORAS MOLONAS (3):
change_absolute_promotion_time
schedulers/rtl_sched.c

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
IMPLEMENTACIÓN DEL ALGORITMO
DE PRIORIDADES DUALES
EN RT-LINUX
Autor:
Luis Antonio Búrdalo Rapa
Asignatura:
Sistemas de Tiempo Real
Curso:
2003 - 2004
Descargar

implementación del algoritmo de prioridades duales en rt - GTI-IA