Indice - uaMaria Isabel Alfonso Galipienso. 2006 9 Caracterización de las tareas (II) Prioridad →...

1

1Maria Isabel Alfonso Galipienso. 2006

Tema 3Scheduling

IntroducciónCaracterización de tareas

PlanificadoresAnálisis de planificabilidad

Tareas aperiódicasUso de recursos

Modelo extendido


Indice

IntroducciónCaracterización de tareasPlanificadoresAnálisis de planificabilidadTareas aperiódicasUso de recursosModelo extendido

2


Introducción (I)

Un sistema de tiempo real debe ser PREDECIBLECapacidad del sistema para poder determinar con antelación las características de respuesta del mismo

Existen muchas secuenciaciones posibles de las tareas, pero solamente algunas de ellas cumplen las restricciones temporales del sistema

Un esquema de scheduling proporcionaUn algoritmo para determinar el orden de uso de los recursos del sistema (procesadores) PLANIFICADORUna forma de predecir el tiempo de respuesta del sistema en el peor de los casos cuando se aplica el algoritmo de scheduling TEST DE PLANIFICABILIDAD


Introducción (II)El sistema debe:

Procesar las actividades periódicas:Requeridas a intervalos regularesCompletar el trabajo antes de un plazo (deadline)

Responder a eventos esporádicos:Requeridos a intervalos irregularesCompletar el trabajo antes de un plazo (deadline )Minimizar la respuesta temporal media

Garantizar que los requerimientos temporales críticos se cumplen durante una sobrecarga transitoria

Garantizar la consistencia de recursos compartidos, como estructuras de datos y dispositivos de I/O

3


Introducción (III)

Scheduler

Ejecutivo cíclico Prioridades

Estáticas Dinámicas

Rate MonotonicRM

DeadlineMonotonic

DM

Fixed-PriorityScheduling

FPS

EarliestDeadline First

EDF

+ Tests de PlanificabilidadFactores de utilización

Tiempos de respuesta


Indice


4


Notación estándar

C: Tiempo de ejecución en el peor de los casos (WCET)D: Deadline del proceso (tarea)I : Tiempo de interferencia para el procesoJ: Release jitter para el procesoN: Número de procesos en el sistemaP: Prioridad asignada al procesoR: Tiempo de respuesta en el peor de los casos T: Periodo del procesoU: Factor de utilización de cada proceso (igual a C/T)


Caracterización de las tareas (I)

Tiempo de respuesta (R)

Deadline (D)

Periodo (T)

T = 10C = 3I = 5

Interferencia (I) Interferencia (I) R = 8D = 9

Determinan sus restricciones temporales de ejecución τi =(Ci, Ti, Di, Ii, Ri)

5


Caracterización de las tareas (II)

Prioridad → P

τ1 = {20,100,100) τ2 = {40,150,150) τ3 = {100,300,300)

1

τi = (Ci, Ti, Di)τi = (Ci, Ti, Di)

3T1

T2

T3

3

2

1

τ1

τ2

τ3

T1

T2

T3 3

2

1τ1

τ2

τ3

2T1

T2

T3

3

2

1

τ1

τ2

τ3


Modelo de procesos básico (I)

(A1) Conjunto fijo de tareas

(A2) Tareas periódicas con periodos conocidos

(A3) Tareas independientes

(A4) Se ignora overhead del procesador (cambios de contexto, etc. tienen coste 0)

(A5) Los periodos son iguales a los deadlines (Ti =Di)

(A6) Tiempo de cómputo (C) conocido y fijo

6


Otras asunciones

Cada tarea se invoca periódicamente mediante la ocurrencia de un evento particularUna tarea es “lanzada” (released) cuando estápreparada para ejecución

Una tarea puede ser interrumpida (preeempted) si una tarea de mayor prioridad está preparada para su ejecución

Instante crítico (máxima carga del procesador)


Indice


7


Planificadores (schedulers)

Un planificador proporciona un algoritmo de uso de recursos del sistema por parte de los procesos

Planificador óptimoSi puede planificar todos los conjuntos de procesos que cualquier otro puede

Planificacion INTERRUMPIBLE (Preemptivescheduling)

Instante crítico: cuando todos los procesos son activados simultáneamente (máxima carga del procesador)


Planificadores estáticos

Analizan estáticamente las tareas para determinar sus propiedades temporalesOrden de ejecución fijo determinado off-lineSe puede crear una tabla de ejecución que cubra un tiempo igual al mcm de los periodos de las tareasEjemplos:

Ejecutivo cíclicoPlanificadores de prioridad fija (FPS)

8


Ejecutivo cíclicoSe crea una tabla secuencial de llamadas a procedimientosSe "simula" la ejecución de varias tareas concurrentes utilizando un único procesoVentajas:

No es posible el acceso concurrente a datosNo necesita test de planificabilidad

Inconvenientes:Dificultad de incorporar procesos esporádicos, con largos periodos, o procesos nuevosDificultad de implementación


Ejecutivo cíclico. Ejemplo 1

t

0 5 10 15 20 25 30 35 40 45

Temp_Control pH_Control Level_Control

t

0 5 10 15 20 25 30 35 40 45

Temp_Control pH_Control Level_Control

loopTemp_Control; pH_Control ;Level_Control;PERIOD := PERIOD + T ;delay until PERIOD ;

end loop;

loopTemp_Control ;if ((cnt mod 2) = 0) then

pH _Control ;Level_Control;

end if ;cnt := cnt + 1 ;PERIOD := PERIOD + T ;delay until PERIOD ;

end loop;

9


Ejecutivo cíclico. Ejemplo 2

e cc a b dbbb bd daaa a

loopesperar_interrupción;proc_a; proc_b;proc_c;esperar_interrupción;proc_a; proc_b;proc_d; proc_e;esperar_interrupción;proc_a; proc_b;proc_c;esperar_interrupción;proc_a; proc_b;proc_d;

end loop;Interrupción Interrupción Interrupción Interrupción

TIEMPO

0 25 50 75

Tarea T=D Ca 25 10b 25 8c 50 5d 50 4e 100 2


RM: Rate Monotonicp La prioridad se asigna en función del PERIODOp A menor periodo → mayor prioridad

Ti < Tj ⇒ Pi > Pj

p Es una asignación ÓPTIMA

Fixed Priority Scheduling (FPS)

DM: Deadline Monotonicp La prioridad se asigna en función del DEADLINEp A menor deadline → mayor prioridad

Di < Dj ⇒ Pi > Pj

p Es una asignación ÓPTIMA

10


Ejemplos RM y DM

Tarea T D P

a 20 5

b 15 7

c 10 10

d 20 20

DM

Tarea T P

a 25

b 60

c 42

d 105

e 75

RM

5

4

3

2

1

4

3

2

1


Planificadores dinámicos

Analizan dinámicamente las tareas para determinar sus propiedades temporales

Orden de ejecución determinado on-line

Se obtienen secuenciaciones más flexibles

Comprenden los siguientes pasos:Análisis de factibilidad, scheduling, dispatching.

Ejemplos:EDF

11


Earliest Deadline First (EDF)

Selecciona la siguiente tarea a ejecutar dependiendo de su deadline absoluto

Se elige la tarea con deadline absoluto más cercano

La decisión se realiza en tiempo de ejecución

Es una asignación óptima


Ejemplo EDF

Tarea T=D C

a 5 2

b 7 4

EDF

TIEMPO

0 7 14 21 28 35

200 5 10 25 30 3515a

b

12


Indice



Tests de Planificabilidad

Son métodos utilizados para determinar si el sistema cumplirá con las restricciones establecidasEjemplos:

Utilización de diagramas de tiempo

Test basado en factores de utilización

Test basado en tiempos de respuesta

13


Factores de utilización

Se denomina factor de utilización U de un conjunto Γ de N tareas periódicas a la fracción de tiempo utilizado por el procesador para ejecutar

dicho conjunto de tareas

Existe un valor máximo de U por encima del cual Γ no es planificable

∑=

=N

i i

i

TCU

1


Test factores de utilización (RM)

)12(1

1−≤∑

=

NN

i i

i NTC

Dado un conjunto Γ de N tareas periódicas secuenciadas según RM, Γ será

planificable SI:

Se trata de una condición SUFICIENTE

N U1 100 %2 82,8 %3 78,0 %4 75,7 %... ...∞ 69,3%

14


Test factores de utilización (RM). Ejemplo 1

Tarea C T=D

a 20 100

b 40 150

c 100 350

n U(n)1 1.0002 0.8283 0.7794 0.7565 0.743... ...∞ 0.693

Uso total 75.3 % ≤ U(3) = 77.9 %Un 24.7 % de la CPU se puede utilizar para cálculos sin requerimientos temporales, a más baja prioridad.

U

0,2

0,267

0,286

P

3

2

1

0 100 150 300 350 200

a

b

c OK!

RM


Test factores de utilización (RM). Ejemplo 2Tarea C T=D

a 40 80

b 10 40

c 5 20

U

0,50

0,25

0,25

Uso total 100 % P

1

2

3Falla el

test!

0 20 40 60 80 3510 30 50 70

a

b

c OK!

RM

15


Test factores de utilización (DM)

)12(1

1−≤∑

=

NN

i i

i NDC

Dado un conjunto Γ de N tareas periódicas secuenciadas según DM, Γ será

planificable SI:

Se trata de una condición SUFICIENTE


Test factores de utilización (EDF)

11

≤∑=

N

i i

i

TC

Dado un conjunto Γ de N tareas periódicas secuenciadas según EDF, Γ será

planificable SI Y SOLO SI:

Se trata de una condición SUFICIENTE y NECESARIA

16


Test factores de utilización (EDF) Ejemplo 1

Tarea C T=D

a 40 80

b 10 40

c 5 20

U

0,50

0,25

0,25

Uso total 100 %

0 20 40 60 80 3510 30 50 70

a

b

c OK!

EDF


Test factores de utilización (EDF) Ejemplo 2

RM

Tarea C T=D

a 2 5

b 4 7

U

0,40

0,57 Uso total 97 %

0 7 14 21 28 35

200 5 10 25 30 3515

0 7 14 21 28 35

EDF

a

b

a

bFalla!

17


Tiempos de respuesta

Instante crítico de una tarea τi: es el tiempo en el que la activación de dicha tarea da lugar a un tiempo de respuesta máximo para τi

El tiempo máximo de respuesta Ri para una tarea periódica τi se calcula, en su instante crítico, como:

iii ICR +=


Cálculo de Ri

Tiempo máximo de respuesta de una tarea en su instante crítico:

Solución de la ecuación:

jihpj j

iii C

TRCR ⋅⎥⎥⎥

⎤

⎢⎢⎢

⎡+= ∑

∈ )(

jihpj j

ki

iki C

TRCR ⋅⎥⎥

⎤⎢⎢

⎡+= ∑

∈

+

)(

1

18


Test tiempos respuesta (RM)

NiTR ii ..1 , =∀≤

Dado un conjunto Γ de N tareas periódicas secuenciadas según RM, Γ será

planificable SI Y SÓLO SI:



P

1

2

3

Test tiempos respuesta (RM) Ejemplo (I)

Tarea C T=D

a 40 80

b 10 40

c 5 20RM

Tarea c 50 =cR 51 =cR

20 5 10 ≤== cc RR OK!

19


Test tiempos respuesta (RM) Ejemplo (II)

Tarea C T=Da 40 80b 10 40c 5 20

P123

RMTarea b

100 =bR

15510 20105101 =+=⎥⎥⎤

⎢⎢⎡⋅+=bR

40 15 21 ≤== cb RR

15510 20155102 =+=⎥⎥⎤

⎢⎢⎡⋅+=bR

OK!


8020204020805

408010404 =++=⎥⎥

⎤⎢⎢⎡⋅+⎥⎥

⎤⎢⎢⎡⋅+=aR

8020204020755

407510403 =++=⎥⎥

⎤⎢⎢⎡⋅+⎥⎥

⎤⎢⎢⎡⋅+=aR

Test tiempos respuesta (RM) Ejemplo (III)

Tarea C T=Da 40 80b 10 40c 5 20

P123

RMTarea a

400 =aR

6010104020405

404010401 =++=⎥⎥

⎤⎢⎢⎡⋅+⎥⎥

⎤⎢⎢⎡⋅+=aR

OK!

7515204020605

406010402 =++=⎥⎥

⎤⎢⎢⎡⋅+⎥⎥

⎤⎢⎢⎡⋅+=aR

20


Test tiempos respuesta (RM) Ejemplo (IV)

Tarea C T=D

a 40 80

b 10 40

c 5 20

P

1

2

3

0 20 40 60 80 3510 30 50 70

a

b

c

RM

80=aR

15=bR

5=cR


Test tiempos respuesta (DM)

NiDR ii ..1 , =∀≤

Dado un conjunto Γ de N tareas periódicas secuenciadas según DM, Γ será

planificable SI Y SÓLO SI:


21


Resumen tests planificabilidad

Di = Ti Di≤ Ti

Prioridades estáticas

Prioridades dinámicas

RM DM

EDF

)12(1

1−≤∑

=

NN

i i

i NTC

NiDR ii ..1 , =∀≤

NiTR ii ..1 , =∀≤

11

≤∑=

N

i i

i

TC


Cambios de contexto

Tiempo de salvar el contexto de la tarea en ejecución + atención a la interrupción + resolución + selección de la tarea a ejecutar+ recuperación del estado de la tarea

Tarea 1

Tarea 2

Salvar el contexto

Planificar y recuperar el contexto

Csa

Csb

Peor caso: 2 cambios por cada expulsión

22


Cambios de contexto Ejemplo (I)

Cs = 2 ms C1 = 20 + 4 T1 = 100 U1 = 0.24C2 = 40 + 4 T2 = 150 U2 = 0.293C3 =100 + 4 T3 = 350 U3 = 0.297

U = 0.831 > U(3) = 0.779

No cumple el test 1

BIEN100240

24

11

1

1

1

0

1

=≤=+=

==

TCWCW

! BIEN 15068

68241006844

68241004444

44

2

2

2

1

2

}1{

1

22

2

2

}1{

0

22

1

2

2

0

2

=≤==

=⎥⎥⎤

⎢⎢⎡+=

⎥⎥⎥

⎤

⎢⎢⎢

⎡+=

=⎥⎥⎤

⎢⎢⎡+=

⎥⎥⎥

⎤

⎢⎢⎢

⎡+=

==

∑

∑

∈∀

∈∀

TWWTWCW

TWCW

CW

j j

j j

Tarea 1:

Tarea 2:


Cambios de contexto Ejemplo (I)

2644415024024

100240104

2404415019624

100196104

1964415010424

100104104

104

}2,1{

2

33

3

3

}2,1{

1

33

2

3

}2,1{

0

33

1

3

3

0

3

=⎥⎥⎤

⎢⎢⎡+⎥⎥

⎤⎢⎢⎡+=

⎥⎥⎥

⎤

⎢⎢⎢

⎡+=

=⎥⎥⎤

⎢⎢⎡+⎥⎥

⎤⎢⎢⎡+=

⎥⎥⎥

⎤

⎢⎢⎢

⎡+=

=⎥⎥⎤

⎢⎢⎡+⎥⎥

⎤⎢⎢⎡+=

⎥⎥⎥

⎤

⎢⎢⎢

⎡+=

==

∑

∑

∑

∈∀

∈∀

∈∀

j j

j j

j j

TWCW

TWCW

TWCW

CW

350264

2644415026424

100264104

34

33

3

43

=<==

=⎥⎥⎤

⎢⎢⎡+⎥⎥

⎤⎢⎢⎡+=

TWW

W

Cumple el test 2

Cs = 2 ms C1 = 20 + 4 T1 = 100 U1 = 0.24C2 = 40 + 4 T2 = 150 U2 = 0.293C3 =100 + 4 T3 = 350 U3 = 0.297

Tarea 3:

En cambio, con un T3 = 250 no cumpliria el test.

23


Indice



Tareas aperiódicas (I)

Se pueden producir en cualquier instante.Se ejecutan bajo petición explicita mediante una interrupción al sistema

Pueden ser de dos tipos:

Críticas: se transforman en periódicas, con un período que depende de plazo de entrega deseado y la separación.

No Críticas: se pretende ofrecer buenos tiempos de respuesta mediante un servicio aperiódico.

Manejador de interrupciónServidor “background”Servidor por consulta ("polling")Servidor “diferido” ("deferred")

Resolución

24


Rutina de interrupción

0 5 10 15 20 25 30 35 40

0 5 10 15 20 25 30 35 40

Distorsiona totalmenteel esquema de prioridades.

Tiempo de respuesta inmediato

T1: (P1=15, D1=5, C1=1)T2: (P2=8, D2=8, C2=2)T3: (P3=5, D3=15, C3=6)

T1: (P1=15, D1=5, C1=1)T2: (P2=8, D2=8, C2=2)T3: (P3=5, D3=15, C3=6)


Background server

Se puede asumir que las tareas aperiódicas se ejecutan con la prioridad más baja de todas y con una política de FCFS. (Servidor de background)

0 5 10 15 20 25 30 35 40

El problema fundamental es el tiempo de respuesta de las tareas aperiódicas: impredecible

T1: (P1=15, D1=5, C1=1)T2: (P2=8, D2=8, C2=2)T3: (P3=5, D3=15, C3=6)

T1: (P1=15, D1=5, C1=1)T2: (P2=8, D2=8, C2=2)T3: (P3=5, D3=15, C3=6)

T4: (P4=∞ , D4=∞, C4= ∞)T4: (P4=∞ , D4=∞, C4= ∞)

25


Polling server

Se le puede asignar una prioridad mayor y limitarle el tiempo de cómputo (Servidor de consulta). Cada período se rellena el tiempo de cómputo.

La tarea tiene un tiempo de cómputo Cs máximo, un período y una prioridad, con lo que se puede incorporar en el análisis de planificabilidad del sistema.

0 5 10 15 20 25 30 35 40

En el peor caso se comportaráasí

planificable


Deferrable server

0 5 10 15 20 25 30 35 40

Tiempo disponible del servidor

Cs

Mientras al servidor le quede tiempo atiende las peticiones de servicio aperiódico que se presenten. Cuando ya no tiene tiempo, ha de esperar al siguiente período para recargar Cs.Si al final no ha conseguido ejecutarlo se pierde.

Ds_Util_max = ——≤ ln ————CDS

TDS

UP+22UP + 1

Factor de utilización máximo del servidor

26


Tests planificabilidad (RM)

POLLING SERVER

Test para actividades PERIÓDICAS

para m servidores:

Condición suficiente

)1( +≤+ nUUU Sp

⎥⎦⎤

⎢⎣⎡ −⋅+≤+ +

=∑ 12)1( )1(

1

1

n

S

Sn

i i

i nTC

TC

)(1

mnUTC

Um

J Sj

SjP +≤+∑

=

para 1 servidor:


Tests planificabilidad (RM)

DEFERRABLE SERVER

Test para actividades PERIÓDICAS

Condición suficiente

para 1 servidor:

⎟⎟⎠

⎞⎜⎜⎝

⎛+⋅

+≤

122ln

S

SP U

UU

27


Indice


Maria Isabel Alfonso Galipienso. 2006

Uso de recursos

Las tareas interactuan mediante:p Datos protegidosp Directamente (cita)

Pueden producirse bloqueos de tareas:

p bloqueo directo: cuando se llama a otra tarea ocupada

p bloqueo indirecto: una tarea se bloquea por que otra tarea está utilizando el recurso de modo exclusivo

28


Bloqueo de tareas

Las tareas más prioritarias se pueden retrasar debido a otras de menor prioridad

Ejemplo: cuando una tarea de menor prioridad está consumendo un recurso compartido y otra tarea de mayor prioridad es "activada"

Un proceso que espera a otro proceso de menor prioridad, se dice que está bloqueado (inversión de prioridades)


Inversión de prioridades

0 2 4 6 8 10 12 14 16 18

Ejecutando

Q bloqueado

V bloqueado

Bloqueado

InterrumpidoT4 4 EEQVE 4T3 3 EVVE 2T2 2 EE 2T1 1 EQQQQE 0

Tarea Prioridad Sec. ejecución Activación

T4

T3

T2

T1

29


Políticas de planificación

Para limitar el efecto de la inversión de prioridad derivada de un esquema puro de prioridades estáticas se utilizan:

Herencia de prioridades (No es óptimo)Techo de prioridades (OCCP) Techo de prioridades inmediato (ICCP)

La prioridad de un proceso ya no es estática


Herencia de prioridades

Ejecutando

Q bloqueado

V bloqueado

Bloqueado

Interrumpido

T4

T3

T2

T1

0 2 4 6 8 10 12 14 16 18

T4 4 EEQVE 4Tarea Prioridad Sec. ejecución Activación

T3 3 EVVE 2T2 2 EE 2T1 1 EQQQQE 0

30


Herencia de prioridad. Bloqueos (I)

Bloqueo que puede sufrir una tarea i:

uso(k,i) = 1 si el recurso k se utiliza al menos por un proceso con una prioridad < Pi y al menos por un proceso con prioridad ≥ a Pi. En otro caso será 0. C(k) es el tiempo de ejecución de la sección crítica k en el peor caso

Bi = Σ (uso(k,i) C(k))k=1

K


Herencia de prioridad. Bloqueos (II)

∑=

⎟⎠⎞⎜

⎝⎛ −⋅≤+≤≤∀

i

k

i

i

i

k

k iTB

TCnii

1

112,1,

ijihpj j

iiii DC

TRBCRi ≤⋅⎥⎥⎥

⎤

⎢⎢⎢

⎡++=∀ ∑

∈ )(,

Ambos tests son condición suficiente

[ ]ikkj

m

k ilpj

si PSCDB ≥=∑

=∈

)(:max ,1 )(

),min( si

lii BBB =

Test de factores de utilización (Di= Ti):

Test de garantía(Di ≤ Ti):

Cálculo del bloqueo: [ ]∑∈

≥=)(

, )(:maxilpj

ikkjk

li PSCDB

31


Protocolos de techo de prioridad (I)

El techo de prioridad de un recurso compartido es la prioridad de la tarea de más alta prioridad que puede bloquear el recurso.

Ventajas:

Una tarea solamente puede ser bloqueada como mucho una sóla vez durante su ejecución por un proceso de menor prioridad.

No se producen interbloqueos.

Se evitan bloqueos transitivos (transitive blocking)

Se asegura acceso en exclusión mutua a los recursos


OCPP

pCada tarea tiene una prioridad estática asignada por defecto.

pCada recurso tiene definido un techo de prioridad: máxima prioridad de la tarea que lo usa

pCada tarea tiene una prioridad dinámica: máximo entre su propia prioridad estática y cualquiera que herede debido a que bloquea a tareas más prioritarias. La prioridad máxima que puede heredar es la del techo del recurso.

pUna tarea puede bloquear un recurso solamente si su prioridad dinámica es mayor que el techo de cualquier recurso actualmente bloqueado por otras tareas.

32


OCPP.Ejemplo

Ejecutando

Q bloqueado

V bloqueado

Bloqueado

Interrumpido

T4

T3

T2

T1

0 2 4 6 8 10 12 14 16 18




OCPP. Bloqueos (I)

Bloqueo que puede sufrir una tarea i:

Cálculo del tiempo de respuesta Ri = Ci + Bi + IiSe permite un primer bloqueo de un recurso en el sistema

Se asegura que un segundo recurso serábloqueado solamente si no existe un proceso de mayor prioridad que usa ambos recursos

Bi = max (uso(k,i) C(k))k=1

K

33


OCPP. Bloqueos (II)

∑=

⎟⎠⎞⎜

⎝⎛ −⋅≤+≤≤∀

i

k

i

i

i

k

k iTB

TCnii

1

112,1,

ijihpj j

iiii DC

TRBCRi ≤⋅⎥⎥⎥

⎤

⎢⎢⎢

⎡++=∀ ∑

∈ )(

,

Ambos tests son condición suficiente

{ }ikijkjkji PSCPPDB ≥<= )(,max ,,

Test de factores de utilización (Di= Ti):

Test de garantía(Di ≤ Ti):

Cálculo del bloqueo:


ICPP

Cada tarea tiene una prioridad estática por defecto asignada.

Cada recurso tiene un techo de prioridadasignado (máxima prioridad de las tareas que lo usan).

Cada tarea tiene una prioridad dinámica que es igual al máximo entre su prioridad estática y los valores “techo” de cualquier recurso que en ese momento esté bloqueado.

34


ICPP.Ejemplo

Ejecutando

Q bloqueado

V bloqueado

Bloqueado

Interrumpido

T4

T3

T2

T1

0 2 4 6 8 10 12 14 16 18




ICPP. Características

El tiempo de respuesta en el peor de los casos se calcula igual que para OCPP

Es más fácil de implementar que un OCPP

Provoca menos cambios de contexto

Requiere más “cambios” de prioridad (OCPP solamente cambia la prioridad si ocurre un bloqueo real)

35


Indice



Release jitter (I)

La variación máxima en el “lanzamiento” de un proceso se denomina JITTER (J)Las tareas esporádicas suelen sufrir jitter

P. ej. en el caso de una tarea S esporádica que es lanzada por una tarea periódica L desde otro procesador

La segunda ejecuciónde L termina despuésde CL

TL= 20RL= 15CL=1

La primera ejecuciónde L termina en RL

t t+15 t+20

L

t t+15 t+21

SL y S NO comparten un instante crítico

Máxima variación Js = 15

Js

36


Tiempo de respuesta en el peor de los casos:

Ri = Bi + Ci + ∑ Cj

Las tareas periódicas pueden sufrir “jitter”dependiendo de la granularidad del “reloj” del sistemaRi

periódica = Ri + Ji

Release jitter (II)

Ri + Ji

Tjj∈hp(i)


Di puede ser mayor que el periodo Ti

Para cada lanzamiento se define una ventana w(q)

win+1(q) = Bi + (q+1)Ci + ∑ Cj

Ri(q) = win(q) - qTi

El número de lanzamientos está limitado por el valor más pequeño de q que cumple la relación: Ri(q) ≤ Ti

El peor tiempo de respuesta el por lo tanto asociado al máximo valor encontrado para cada q:

Ri = maxq=0,1,2,... Ri(q)

Deadlines arbitrarios

win(q)Tj

j∈hp(i)

37


Deadlines arbitrarios

Si queremos tener en cuenta el efecto del Jitter, modificaremos el análisis anterior incrementando el factor que representa la inferencia

win+1(q) = Bi + (q+1)Ci + ∑ Cj

Si un proceso puede sufrir jitter, entonces dos ventanas consecutivas pueden solapar si el tiempo de respuesta más el jitter es mayor que el periodo

Ri(q) = win(q) - qTi + Ji

win(q)+Jj

Tjj∈hp(i)


Asignación de prioridadesTeorema: Si a un proceso P se le asigna la menor prioridad y es factible,entonces, si existe una ordenación de prioridades factible para el conjunto completo de procesos, existirá una ordenación en la que a P se le asigne la menor prioridadprocedure assign_pri (set: in out process_set; N:natural;

ok: out:boolean);begin

for k in 1..N loopfor next in k..N loop

swap (set, K, next);process_test (set, k, ok);

end loop;exit when not ok;

end loop; end assign_pri;

38


Prioridades en Ada (I)

Hay que asociar prioridades a las tareas.El sistema proporciona lo siguiente una rango de prioridades(0..32) y una por defecto (16).Se definen mediante pragma

task Controller ispragma Priority(10);

end Controller;

task type Productor(pid: INTEGER; prio: System.Priority) ispragma Priority(prio);

end Productor;

Prioridad base


Prioridades en Ada (II)

Prioridad BASE: prioridad asignada mediante "pragmas"Prioridad ACTIVA: es el máximo entre entre la prioridad base y cualquier otra prioridad heredadaFormas de heredar prioridades:

Mediante el uso de objetos protegidosDurante la activación: se hereda la prioridad activa del padreDurante una cita: la tarea que realiza el "accept" hereda la prioridad activa de la tarea que realiza la llamada a la entrada (si es mayor que la propia)

39


Prioridades Ceiling Locking

Los objetos protegidos necesitan mantener la consistencia de sus datosLa exclusión mutua puede garantizarse mediante el uso del modelo de prioridades de AdaCada objeto protegido tiene asignado un techo de prioridadque es mayor o igual que la prioridad más alta de cualquierade las tareas que lo llamanCuando una tarea llama a una operación protegida, suprioridad se convierte automáticamente en la del objetoprotegido

Si una tarea que quiere acceder a un objeto protegido está en ejecuciónentonces el objeto protegido no puede estar ya ocupado


Ceiling Locking (ICCP)

A cada objeto protegido se le asigna una prioridad medianteun pragma

Si se omite el prama, se asume Priority'Last

La excepción Program_Error es lanzada si la tarea quellama tiene una prioridad activa mayor que el techo

Utilizando ceiling locking, una implementación efectiva usaráel hilo de ejecución de la tarea que llama para ejecutar no solamente la operación protegida sino también para ejecutarel código de cualqueir otra tarea que tenga que ser lanzada(activada) como resultado de la llamada

Indice - uaMaria Isabel Alfonso Galipienso. 2006 9 Caracterización de las tareas (II) Prioridad →...

Documents

Transcript of Indice - uaMaria Isabel Alfonso Galipienso. 2006 9 Caracterización de las tareas (II) Prioridad →...