La importancia del tiempo



Descargar 237.93 Kb.
Página4/7
Fecha de conversión14.11.2017
Tamaño237.93 Kb.
1   2   3   4   5   6   7

P

media
baja




P alta


Explicación: En t=0 no existe petición aperiódica, con lo que se ejecuta 1 y consume la capacidad del servidor a prioridad máxima, Cs a la vez que aumenta la capacidad con prioridad media. En t=4 el servidor tiene Cs1=1 con prioridad media, pero como no hay pendiente ninguna tarea aperiódica se ejecuta 2 y consume está capacidad la cambia por su prioridad (baja o de background). En t=5 se rellena la capacidad de Cs y como es la de mayor prioridad y hay tarea aperiódica esta se ejecuta con y agota la capacidad de Cs, en este momento si llega otra tarea aperiódica solo puede ejecutar si no hay ninguna otra tarea periódica activa (background)...


A.3. Servidor esporádico

El servidor esporádico es uno de los protocolos de reserva de ancho de banda más importante y utilizados. El servidor esporádico tiene asociado tres parámetros el periodo, T, la capacidad de ejecución, C, y su prioridad, P. El algoritmo difiere del servidor diferido en un pequeña, pero importante idea: la capacidad de ejecución no se rellena periódicamente, rellenándose sólo si se consume. El método de relleno de la capacidad del servidor es lo que diferencia de otros métodos, para entenderlo tendremos que definir los siguientes términos:

- Ps: Nivel de prioridad de la tarea que está ejecutando

- Pi: Nivel de prioridad de la tarea i

- Tarea i en estado activo, cuando PsPi

- Tarea i en estado ocioso, cuando Ps


i

- RT instante donde se restaura la capacidad del servidor esporádico.


Reglas que rigen el comportamiento del servidor esporádico:


  • Cuando ocurre un evento aperiódico, si hay capacidad de ejecución disponible, la tarea aperiódica ejecuta a la prioridad asignada consumiendo la correspondiente capacidad de ejecución

  • Cuando la capacidad de ejecución se agota, la tarea puede continuar ejecutando a nivel de background

  • La planificación de relleno de un servidor que ejecuta a nivel Pi sigue las siguientes reglas:

    • Si el servidor tiene capacidad disponible, RT se inicializa cuando la prioridad Pi pase de Activo a Ocioso(en t) RT=t+Ts. Si se ha consumido la capacidad del servidor RT.

    • La cantidad de relleno es igual al tiempo de ejecución consumido desde la ultima vez que Pi paso de Activo a Ocioso o la capacidad disponible se haya consumido.

  • Cuando se produce el relleno y el servidor esporádico ejecutaba a nivel de background la prioridad del servidor se eleva a su prioridad normal.

Veamos dos ejemplo aclaratorios del comportamiento del servidor esporádico:




Como el servidor esporádico es el único que tiene prioridad máxima, el relleno se realizará T instantes después de que la tarea aperiódica empieza a ejecutar (pasa a estado Activo). El relleno será igual a la capacidad consumida desde que la tarea aperiódica comenzó a ejecutar.



Tanto el servidor esporádico como la tarea 1 tiene prioridad máxima, de forma que el servidor estará en estado Activo cuando tanto él como 1 tomen el procesador. Esto hace que el relleno de la primera activación sea 1 segundo anterior a la activación de la tarea aperiódica.



B) Planificadores de reserva de ancho e banda en EDF



La pujanza en los últimos años de los sistemas de control gobernados por prioridades dinámicas, y en especial en EDF ha hecho que mucho de los planificadores de ancho de banda ideados en RMA se hayan extendido a EDF. Muchas de estas extensiones han sido estudiadas en el articulo [SPU96]. Una de los principales temas de la tesina se centra en estos planificadores de ancho de banda en sistemas EDF.
En este capítulo veremos la extensión de los anteriores algoritmos vistos en RMA y un nuevo algoritmo el TBS [SPU96]. Otro algoritmo importante es el CBS (Constant Bandwidh Server) [ABE99] que será el principal tema de estudio en esta tesina por lo que será tratado en siguientes puntos de la tesina.

B.1) Servidor diferido con EDF.

El Servidor Diferido en EDF se diferencia respecto al mismo en RMA en que la prioridad no vendrá dada por el parámetro Ps, sino por el deadline Ds del servidor que coincide con el periodo Ts. Así los tres parámetros en el servidor diferido con EDF son (Ts,Ds,Cs), donde Ts=Ds.

Conforme a esto las reglas del servidor trabajando con EDF son las que siguen:



  • La capacidad del servidor comienza siendo Cs y se restaura al comienzo de cada activación j·Ts jIN

  • El deadline de cada activación coincide con el siguiente periodo de relleno.

  • El tiempo de ejecución se consume sólo cuando el servidor se ejecuta.

  • No se conserva capacidad sobrante entre activaciones.

  • Las activaciones de tareas aperiódicas se ejecutan en el procesador si su deadline Ds es anterior al deadline de las demás tareas activas en el procesador y hay capacidad en el servidor.

  • En el caso de que no exista capacidad en el servidor las tareas aperiódicas pueden ejecutarse en segundo plano.

Ejemplo gráfico del Servidor Diferido trabajando en EDF



Tareas

Di

Ti

Ci




Activaciones aperiod

Tiempo ejecución

1

3.5

3.5

1.5




T=2.8

1.7

2

6.5

6.5

0.5




SD

3

3

1






B.2 Intercambio de Propiedades Dinámico (DPE).
El comportamiento del planificador por intercambio de prioridad dinámico es semejante al del planificador en RMA, con diferencia que ahora el deadline es el que decide la prioridad de la tarea. De esta forma los parámetros del DPE son el periodo, Ts, la capacidad Cs y el deadline Ds, que por lo general coincide con el periodo. Con esta variante respecto a RMA las reglas que rigen el DPE son las siguientes:


  • La capacidad se restaura como en el servidor diferido, al comienzo de cada periodo (instante de relleno).

  • Al principio de cada periodo del servidor si hay peticiones aperiódicas pendientes y el servidor es la tarea con menor deadline estas tareas se ejecutan usando la capacidad disponible del servidor.

  • Si no hay ninguna tarea aperiódica pendiente la capacidad se intercambia por el tiempo de ejecución de la tarea periódica activa de mayor prioridad (menor deadline) y se cambia los deadlines, de forma que la capacidad se mantiene con un deadline mayor.

  • Cuando se produce un intercambio de prioridad entre una tarea periódica y el servidor, la tarea periódica se ejecuta con el deadline del servidor mientras el servidor acumula la capacidad con deadline de la tarea periódica.

  • Durante el tiempo que el procesador esta libre (ninguna tarea pendiente de ejecución) se consume la capacidad de la tarea aperiódica almacenada, empezando por aquella que tenga menor prioridad (mayor deadline).

Veamos un ejemplo ilustrativo de estas propiedades que rigen el comportamiento del servidor DPE:

0 2 4 6 8 10 12 14 16 18 20 22 24

0 2 4 6 8 10 12 14 16 18 20 22 24

0 2 4 6 8 10 12 14 16 18 20 22 24

0 2 4 6 8 10 12 14 16 18 20 22 24

6

0 2 4 6 8 10 12 14 16 18 20 22 24



0 2 4 6 8 10 12 14 16 18 20 22 24

Peticiones

Aperiódicas

Cs

τ1

τ2

Cs1

Cs2





Servidor

Cs=3


T=D=8







C

T=D

τ1

2

8

τ2

3

12



B.3 El Servidor Dinámico Esprádico (DSS)

El DSS puede considerarse como el servidor esporádico, planificado para usar en prioridades dinámicas (EDF). De esta forma el mecanismo de restauración de la capacidad se realiza de forma semejante al del servidor esporádico, con la diferencia que ahora asignamos un deadline a la tarea aperiódica, con el fin de dotar al sistema de prioridad dinámica. En las definiciones del DSS estudiadas no se consideran la posibilidad de que este pierda el deadline, con lo que se ha retocado la definición en [SPU96] para considerar esta situación. Veamos las reglas que nos definen este servidor:


El servidor caracterizado por dos parámetros (TDSS,CDSS), el sistema puede encontrase en tres estados:

  1. Estado activo: C>0, tarea aperiódica pendiente de ejecutar. Dos situaciones:

      1. Ejecutando antes de su deadline ri≤ t i

      2. Ejecutando después de su deadline t≥ Di

  2. Estado no activo (idle), cuando C=0 y/o no hay requisito aperiódico.

3

2



Activo.I

Activo II

Pasivo

1

4


Situaciones:


  1. Activo I Activo II. Esto ocurre en el tiempo T=Di, donde la capacidad del servidor es mayor que cero, y tenemos requisitos aperiódicos pendientes




  1. Activo IPasivo. Ocurre cuando en t




    1. Se agota la capacidad CDSS=0

    2. Deja de haber requisitos aperiódicos pendientes de ejecución.




  1. PasivoActivo I. Ocurre cuando :

    1. Hay requisitos aperiódicos pendientes de ejecución anteriores y la capacidad se hace mayor que cero C>0

    2. La capacidad es mayor que cero y llega un nuevo requisito

aperiodico.

    1. Las dos caso: Se hace C>0 y llega en el mismo instante requisito aperiódico

  1. Activo IIPasivo. Iden 2) pero t>Di

Ejemplos gráficos


1)

Activo2


CDSS=3

TDSS=7

ActivoI

DDSS



3

2

1



Tarea periodica
Tarea aperiódica(DSS)
2 y 3)

Tarea periodica
Tarea aperiódica(DSS)
Aa activoI

5

Pasivo



CDSS=3

TDSS=7

ActivoI

DDSS



3

2

1


Tarea periodica


Tarea aperiódica(DSS)

3

Pasivo



CDSS=3

TDSS=7

ActivoI

DDSS



3

2

1



ActivoII
4)

Reglas del servidor:




  1. La capacidad del servidor al tiempo t=0 es de CDSS y su deadline es de t=TDSS

  2. La capacidad del servidor disminuye de la misma forma que se ejecuta la tarea aperiódica cuando el sistema está activo

  3. Las tareas aperiódicas sólo pueden ejecutarse si de entre todas las tareas activas es la de mayor prioridad (menor deadline).

  4. Si tA es el instante donde el procesador pasa a estar activo, la capacidad del servidor se restituye en tA+TDSS, si el servidor está pasivo en este instante. En el caso de que el servidor esté activo (se convierte en activoII) se rellena después de este instante cuando el servidor pase a estar pasivo.

  5. El deadline de los requerimientos aperiódicos ocurridos entre el instante tA hasta que el servidor pasa a estar pasivo se sitúa en tA+TDSS.

  6. Si llega algún requerimiento aperiódico, estando el sistema en situación ActivoII, o no finaliza la tarea aperiódica anterior, el deadline del procesador se sitúa TDSS después del anterior.

Veamos gráficamente, esta última situación:




2

3

3



2

1


TDSS

DDSS

ActivoI

ActivoII

CDSS=3

TDSS=7




B.4 Servidor de Ancho de Banda Total (TBS)
El servidor TBS, a diferencia de los anteriores, no es una extensión a prioridades dinámicas de algún servidor aperiódico RMA. El funcionamiento de este servidor es totalmente distinta al de los anteriores. Está caracterizado por un único parámetro, la utilización, Us. Las reglas de este servidor son sencillas y se basan en generar el deadline de la tarea apereriódica que llega en el tiempo t=rk, que recibe un deadline:


  • dk=max(rk,dk-1)+ Ck/Us (con Ck tiempo de ejecución tarea aperiodica)

  • d0=0

Este tipo de planificadores se denominan “libre” (Idle), que se caracterizan por poder ejecutar un tiempo ilimitado las tareas aperiódicas si el procesador no se encuentra ocupado (ya que no tiene capacidad Cs), mientras que los demás (“no libres”) como el DSS que sólo pueden ejecutar como máximo t·(Cs/Ts) en un tiempo t .


Veamos un ejemplo ilustrativo para poder comprender el funcionamiento del servidor TBS:






C

T=D

τ1

2

8

τ2

3

12

Servidor capacidad Us=0.5


0 2 4 6 8 10 12 14 16 18 20 22 24

0 2 4 6 8 10 12 14 16 18 20 22 24

6

0 2 4 6 8 10 12 14 16 18 20 22 24



Peticiones

Aperiódicas

τ1

τ2

6/0.5=12




Compartir con tus amigos:
1   2   3   4   5   6   7


La base de datos está protegida por derechos de autor ©composi.info 2017
enviar mensaje

    Página principal