PDF de programación - Master en Computación - Plataformas de Tiempo Real - POSIX Avanzado y Extensiones - Tema 5. Planificación a Nivel de Aplicación

1



Master en Computación

Plataformas de Tiempo Real

POSIX Avanzado y Extensiones

Tema 1. Ficheros y entrada/salida
Tema 2. Gestión de Interrupciones en MaRTE OS
Tema 3. Monitorización y control avanzado del tiempo de ejecución
Tema 4. Planificación EDF

Tema 5. Planificación a Nivel de Aplicación

Plataformas de Tiempo Real

Tema 5. Planificación a nivel de aplicación

© M. Aldea, M. González

Mayo-2014

Tema 5. Planificación a nivel de aplicación
5.1. Motivación
5.2. Descripción del Modelo: Estructura de un Planificador
5.3. Creación de Planificadores de Aplicación
5.4. Acciones de planificación
5.5. Creación de threads planificados
5.6.
5.7. Protocolos de Sincronización
5.8. Ejemplo: Planificador EDF

Invocación del planificador

© M. Aldea, M. González

Mayo-2014

2

5.1 Motivación

Plataformas de Tiempo Real

Tema 5. Planificación a nivel de aplicación

5.1 Motivación
Las políticas de planificación definidas en el POSIX no son
suficientes para todos los tipos de aplicaciones

• Las prioridades dinámicas permiten un mejor aprovechamiento

de los recursos

• Los sistemas dinámicos (multimedia) requieren algoritmos de

planificación flexibles

Existen muchas políticas basadas en prioridades dinámicas

• Resultaría imposible estandarizarlas todas

Nuestra propuesta al POSIX:

• Interfaz que permita a las aplicaciones definir sus propios

algoritmos de planificación

Plataformas de Tiempo Real

© M. Aldea, M. González

Mayo-2014

3

Tema 5. Planificación a nivel de aplicación

5.2 Descripción del Modelo:

Estructura de un Planificador

5.2 Descripción del Modelo: Estructura de un Planificador

Sistema Operativo

Invoca

Retorna
Acciones de
Planificación

Planificador del sistema
Basado en prioridades fijas

Sched. Data
Estado Interno:
cola de tareas
cola de eventos,
...

Planificador
de Aplicación

Init

New Thread

Ready

Explicit Call

Block

Task Notification

Signal
Timeout

...

Plataformas de Tiempo Real

Tema 5. Planificación a nivel de aplicación

© M. Aldea, M. González

Mayo-2014

4

5.2 Descripción del Modelo: Estructura de un Planificador

Descripción del Modelo:

Ordenación por “urgencia”

Noción abstracta de “urgencia” (un número entero):

• Urgencia asignada a los threads por su planificador
• Permite mapear cualquier parámetro de planificación (plazo,

holgura, valor, QoS, etc.)

• En cada cola de prioridad los threads se ordenan según el valor

de su "urgencia"

T1

T2

URG: 45

URG: 35

T3

T4

URG: 25

URG: 10

T5

URG: 35

Plataformas de Tiempo Real

Tema 5. Planificación a nivel de aplicación

© M. Aldea, M. González

Mayo-2014

5.3 Creación de Planificadores de Aplicación

5.3 Creación de Planificadores de Aplicación
#include <sched.h>
int posix_appsched_scheduler_create
(const posix_appsched_scheduler_ops_t *scheduler_ops,
void * sched_data,
int priority,
posix_appsched_scheduler_id_t *sched_id);
• scheduler_ops: operaciones del planificador
• sched_data: datos internos del planificador (serán pasados
como parámetro a todas sus operaciones)
• priority: prioridad a la que se ejecutan las operaciones del
planificador
• sched_id: identificador del planificador

Plataformas de Tiempo Real

© M. Aldea, M. González

Mayo-2014

5

6

Tema 5. Planificación a nivel de aplicación

5.3 Creación de Planificadores de Aplicación
Creación de Planificadores de Aplicación (cont.)

Estructura posix_appsched_scheduler_ops_t:
typedef struct {
void (*init) (void * sched_data);
void (*new_thread) (void * sched_data, pthread_t thread,
posix_appsched_actions_t * actions);
void (*thread_ready) (void * sched_data, pthread_t thread,
posix_appsched_actions_t * actions);
void (*explicit_call) (void * sched_data, pthread_t thread,
int user_event_code,
posix_appsched_actions_t * actions);
void (*signal) (void * sched_data, siginfo_t siginfo,
posix_appsched_actions_t * actions);
void (*notification_for_thread)(void * sched_data,
pthread_t thread,
posix_appsched_actions_t * actions);
void (*timeout) (void * sched_data,
posix_appsched_actions_t * actions);
... // hay más operaciones primitivas
} posix_appsched_scheduler_ops_t;

Plataformas de Tiempo Real

Tema 5. Planificación a nivel de aplicación

© M. Aldea, M. González

Mayo-2014

7

5.4 Acciones de planificación

5.4 Acciones de planificación
Desde sus operaciones, los planificadores pueden notificar al SO
las acciones que desean realizar sobre sus tareas:
• aceptar o rechazar una tarea (sólo desde new_thread)
• activar una tarea
• activar una tarea con el valor de urgencia deseado
• suspender una tarea
• activar una tarea en un instante futuro
• programar una notificación para un instante futuro

Plataformas de Tiempo Real

Tema 5. Planificación a nivel de aplicación

© M. Aldea, M. González

Mayo-2014

8

5.4 Acciones de planificación

Aceptación y rechazo de una tarea
La operación new_thread es invocada por el SO cuando una tarea
del usuario solicita ser planificada por el planificador
El planificador puede aceptarla o rechazarla

• en base a un test de planificabilidad, porque se ha alcanzado el

número máximo de tareas, ...

Aceptar de una tarea:

#include <pthread.h>
int posix_appsched_actions_addaccept

(posix_appsched_actions_t *sched_actions,
pthread_t thread);

Rechazar una tarea:

int posix_appsched_actions_addreject

(posix_appsched_actions_t *sched_actions,
pthread_t thread);

Plataformas de Tiempo Real

© M. Aldea, M. González

Mayo-2014

9

Tema 5. Planificación a nivel de aplicación

5.4 Acciones de planificación

Activación y suspensión de una tarea
Activar una tarea (sin cambio de urgencia):
int posix_appsched_actions_addactivate
(posix_appsched_actions_t *sched_actions,
pthread_t thread);

Activar una tarea indicando su urgencia:

int posix_appsched_actions_addactivateurg
(posix_appsched_actions_t *sched_actions,
pthread_t thread,
posix_appsched_urgency_t urgency);
• si la tarea ya estaba activa, se cambia su urgencia

Suspender una tarea:

int posix_appsched_actions_addsuspend
(posix_appsched_actions_t *sched_actions,
pthread_t thread);

Plataformas de Tiempo Real

Tema 5. Planificación a nivel de aplicación

© M. Aldea, M. González

Mayo-2014

10

Programación de acciones para el futuro
Programar la activación de una tarea para un instante futuro
indicando su urgencia:

5.4 Acciones de planificación

int posix_appsched_actions_addtimedactivation
(posix_appsched_actions_t *sched_actions,
pthread_t thread,
posix_appsched_urgency_t urg,
const struct timespec *at_time);

Programar la invocación de la operación primitiva
notification_for_thread para un instante futuro:
int posix_appsched_actions_addthreadnotification
(posix_appsched_actions_t *sched_actions,
pthread_t thread,
const struct timespec *at_time);
• at_time basado en el CLOCK_MONOTONIC

Plataformas de Tiempo Real

Tema 5. Planificación a nivel de aplicación

© M. Aldea, M. González

Mayo-2014

11

5.5 Creación de threads planificados

5.5 Creación de threads planificados
Se define una nueva política: SCHED_APP
Aparecen nuevos atributos:

• Planificador de aplicación:
int pthread_attr_setappscheduler
(pthread_attr_t *attr,
posix_appsched_scheduler_id_t scheduler);
• Parámetros de planificación específicos de cada política de
planificación:
int pthread_attr_setappschedparam
(pthread_attr_t *attr,
void * param,
size_t paramsize);

Plataformas de Tiempo Real

© M. Aldea, M. González

Mayo-2014

12

Tema 5. Planificación a nivel de aplicación

5.6 Invocación del planificador

5.6 Invocación del planificador
Un thread planificado puede invocar explícitamente a su
planificador:

int posix_appsched_invoke_scheduler

(int user_event_code);

• Puede utilizarse para notificar al planificador de algún cambio

de estado de la tarea planificada
• Provoca la ejecución de la operación primitiva del planificador
explicit_call

Plataformas de Tiempo Real

Tema 5. Planificación a nivel de aplicación

© M. Aldea, M. González

Mayo-2014

13

5.7 Protocolos de Sincronización

5.7 Protocolos de Sincronización
Protocolo de Baker o “Stack Resource Protocol” (SRP) (“Techo de
prioridad” aplicable a prioridades dinámicas)
+ Mejor tiempo de bloqueo de peor caso
+ Aplicable a multiprocesadores
+ Evita el bloqueo mutuo en monoprocesadores
+ Evita cambios de contexto debidos a la sincronización
- Necesario especificar el techo de cada recurso
Herencia combinada de prioridad y urgencia
- No tiene ninguna de las propiedades anteriores pero...
+ También acota el tiempo de bloqueo de peor caso
+ No requiere indicar techos (bueno en sistemas dinámicos)

Plataformas de Tiempo Real

Tema 5. Planificación a nivel de aplicación

© M. Aldea, M. González

Mayo-2014

14

5.7 Protocolos de Sincronización

Protocolo de Baker
A cada tarea se asigna el nuevo atributo “Nivel de Expulsión”

• Valor relativo a la capacidad de la tareas de expulsar a otras
• También se asigna a los mutexes (Techo)

Nueva regla de planificación:

• Una tarea no puede ejecutar hasta que su nivel de expulsión no

sea estrictamente mayor que el techo del sistema

Necesario combinar la regla con la ordenación por urgencia:

T1

URG:45
PL: 6

T2

URG:20
PL: 3
PL(I): 4

T3

T4

URG:30
PL: 4

URG:10
PL: 1
PL(I):2

URG:35
URG:35
PL: 3
PL: 3

T5

URG: Urgency
PL: Preemption Level
PL(I): Preemption Level (Inherited)

Plataformas de Tiempo Real

© M. Aldea, M. González

Mayo-2014

15

Tema 5. Planificación a nivel de aplicación

5.7 Protocolos de Sincronización

Herencia de Prioridad
Herencia de prioridad (Sha, Rajkumar y Lehoczky, 1990)

• Inicialmente pensado para prioridades fijas
• Puede aplicarse a prioridad