La importancia del tiempo



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

Asignación de prioridades

Hemos considerado hasta ahora la asignación óptima de prioridades fijas para tareas que cumplan:



    • Periodo igual al deadline RMA

    • Deadline menor al periodoDMA

Todavía no hemos contemplado una posibilidad, que el deadline sea mayor periodo. Para asignar prioridades en este caso Ausdley desarrolló un algoritmo heurístico [AUS91B]. Este algoritmo nos proporciona si el sistema es planificable una asignación de prioridades con el cual lo sea, si bien puede ocurrir que existan otras asignaciones mejores. En el caso de que el sistema no sea planificable el algoritmo nos lo muestra.


Este test se basa en que si una tarea i cumple su plazo con la prioridad más baja del sistema, y existe un orden de prioridades admisible para todo el sistema, entonces hay un orden de prioridades que garantiza el sistema es planificable donde i tiene prioridad menor.


Algoritmo de asignación de prioridades:



Procedure asignación_prioridades(System: in out Task_set; N:in Natural; planificable:out booleam) is




Begin
for k in 1..N loop
for next in k in 1..N loop
Cambia(system,k,next)

Test(Sistem, k, planifiacble);

exit when planificable;

end loop
exit when not planificable

end loop
end asignacion_prioridades;



Explicación del algoritmo:

Las tareas se ordenan según la prioridad, así la 1 es la de menor prioridad, y N es la que más.

Partimos de una asignación arbitraria del sistema (System), el cual damos al programa. Comprobamos si existe alguna asignación con 1 con menor prioridad, de forma que el sistema sea planificable ( el Test de true), si es así el algoritmo nos devuelve dicha asignación. Si no es planificable comprobamos con 2, así sucesivamente hasta N. El programa nos devuelve el primero que sea planificable, independientemente de si es optimo o no. En el caso de que no sea planificable de con ninguna asignación el programa nos devuelve el valor de planificable como false.
Ejemplo: System 1, 2,3 (1la menos prioritaria, y 3 la más prioritaria) y la unica ordenación posible para que el sistema sea planificable es 3, 2,1 (3 la menos prioritaria, y 1 la más prioritaria).


  • K=1 1. System=(1, 2,3)

  • Next=1, no cambia nada system= (1, 2,3), Test( system,1)false

  • Next=2,cambia 1 y 2 system= (2, 1,3), Test( system,2)false

  • Next=3,cambia 2 y 3 system= (3, 1,2), Test( system,3)True




  • K=21. System= (3, 1,2)

  • Next=2, no cambia nada system= (3, 1,2), Test( system,1)false

  • Next=3 ,cambia 1 y 2 system= (3, 2,1), Test( system,2)True




  • K=31. System= (3, 2,1)

  • Next=3, no cambia nada system= (3, 2,1), Test( system,1)True

El programa nos devuelve el sistema ordenado según sus prioridades (3, 2,1) y planificable=true



2.2.4 Planificación dinámica mediante prioridades dinámicas.
Estas políticas de planifiación, al igual que las anteriores se refieren a la asignación de prioridades paa la utilización de los recursos compartidos, en especial el procesador.
Los planificadores con prioridades dinámicas son más complicados de implementar y de analizar de forma teórica los tiempos de respuesta de peor caso, que los de prioridades estáticas. La utilización de estos y no los de prioridades fijas es debido a que consiguen que sistemas no planificables mediante prioridades fijas, si lo sean bajo prioridades dinámicas, consiguiendo utulizaciones más amplias del procesador.
Los planificadores dinámicos se encentran en auge, y se empiezan a desarrollar sus bases teóricas desde hace poco tiempo. Si bien estas teorías tienen que superar algunos de los principales problemas que hace que su utilización sea menor al de prioridades fijas. Las principales causas son [RIP96]:


  • No son estables bajo sobrecargas. De forma que si alguna tarea consume más tiempo del estimado, no hay forma de saber cual es la tarea que perderá su plazo.

  • La mayoría de sistemas operativos en la actualidad no disponen de planificadores basados en prioridades dinámicas..

  • Dificultad de implementación de sistemas con prioridades dinámicas frente a la implementación estática.

El principal algoritmo de planificación dinámica es el EDF (Earliest Deadline First) [LIU73]. También tiene importancia otro algoritmo el LLF(Least Laxity First) [AUD90].


Teoría EDF (Earliest Deadline First)
La teoría EDF es una técnica de análisis de sistemas con prioridades dinámicas, que asigna prioridades según la tarea activa con el plazo de ejecución (deadline) más próximo en un tiempo t. Así la tarea más prioritaria en un tiempo t dado, será aquella tarea activa cuyo deadline este más próximo al instante actual. Según el instante de tiempo en que nos encintremos variará la prioridad, al contrario que RMA y DMA de aquí que sea de prioridad dinámica.
En sistemas monoprocesadores en donde las tareas sean expulsables y periódicas con deadline igual al periodo (D=T) se ha comprobado [AUD90] y [RIP96] que es un algoritmo óptimo.
Veamos un ejemplo que no es planificable RMA y si lo es EDF:



RMA EDF



Fuera de plazo







Teoría LLF (Least Laxity First)
La teoría LLF( primero el más holgado) es otra teoría de prioridades dinámica. En este caso la asignación de prioridad en un tiempo de t, se elige conforme aquella que tenga menor holgura, y no la aquella que tenga más temprano su deadline. De esta forma en un tiempo t la tarea activa que ejecute será aquella cuya holgura sea menor. Donde definimos como holgura a la diferencia entre el tiempo hasta el deadline, menos el tiempo de ejecución restante: L(t)=(D-t)-C(t).
Esta teoría es más difícil aun de implementar que EDF y se dispone de menos fundamentación teórica. En la tesina sólo estudiaremos EDF para prioridades dinámicas.

2.3 Iteración entre tareas e inversión de prioridades

Hemos hablado en este apartado de las políticas de planificación para el uso de los recursos, haciendo hincapié en el procesador. Aunque es el más importante, no tiene porque ser el único recurso compartido, otro dispositivos muy comunes pueden ser discos duros, acceso a sensores. Muchas veces ocurre que, aunque pueda elegirse una planificación basada en prioridades, no son expulsores, es decir una vez que una tarea los toma no lo dejará hasta que finalice su ejecución.


La situación ocurrida cuando una tarea de mayor prioridad tiene que esperar su ejecución ha que finalice la suya otra tarea de menor prioridad, se denomina inversión de prioridad. Generando un incremento en el tiempo de respuesta de esta tarea, denominado término de bloqueo.
La sección de código que ejecuta haciendo uso del recurso compartido se conoce como sección crítica. Para garantizar el acceso exclusivo de la tarea que ejecuta la sección crítica los dispositivos utilizan normalmente semáforos.
Tendremos no solo considerar el bloqueo en los tiempos de respuesta, sino que establecer mecanismos que nos limiten el bloqueo, pues este puede ser mayor a la ejecución de la tarea, incluso teóricamente infinito. Un ejemplo clásico de estas inversión de prioridad no acotadas es el bloqueo mutuo, en que dos tareas están interbloqueadas esperando ambas que la otra libere un recurso que necesita para seguir ejecutando.
Ejemplo1:

Vemos un ejemplo de bloqueo mayor que el valor de la sección crítica, el cual debemos evitar o reducir mediante los denominados protocolos de sincronización de tiempo real.





La tarea 1 necesita el recurso x, que tiene la tarea 4, hasta que este recurso no sea ejecutado por 4. Pero como 4 es la menos prioritaria, sufre interferencias por 3 y por 2, que a su vez hace que aumente el bloqueo de la tarea 1. Si no tenemos ningún protocolo, el bloqueo que en principio debería de ser la ejecución de dx, aumenta con la ejecución de 1 y 2.


Ejemplo2:
En este ejemplo vamos a ver un bloqueo mutuo, que genera bloqueo infinito:


Tiene bloqueado recurso “y.” Quiere el “x”



ay

ay



Tiene bloqueado el recurso”x”. Quiere el recurso “y”

bx, by

ay,axy


b





bx



2.3.1 Protocolos de sincronización
Para disminuir el efecto de los bloqueos, y evitar que ocurran bloqueos no acotados, existen una serie de protocolos que modifican las prioridades de las tareas. Los más importantes y usados son:


  1. Protocolo de no expulsión: no se permiten las expulsiones durante la ejecución de la ejecución de la sección crítica. Es equivalente a ejecutar las secciones críticas con la mayor prioridad del sistema. Este protocolo minimiza la duración de las secciones críticas y evita los bloqueos mutuos. El problema que conlleva es que interfiere en la ejecución de todas las tareas, incluidas las que no cogen el recurso, lo que genera bloqueos innecesarios.

Aplicándolo al ejemplo anterior, tendremos que los bloqueos serán:




Bloqueoeo



Donde la tarea 4 cuando toma el recurso x no lo abandona, esto produce que disminuya el bloqueo de 1, que es la tarea que toma también el recurso. Por el contrario, las otras dos tareas 2 y 3, que nunca toman el recurso x se ven bloqueadas al tomar prioridad máxima la sección crítica.


  1. Protocolo de prioridad máxima: la sección crítica se ejecuta a la prioridad techo, que corresponde a la más alta prioridad de las que utilizan dicho recurso. La ventaja sobre el protocolo de no expulsión es que no bloquea a las tareas con mayor prioridad que la prioridad techo del recurso. Este protocolo evita bloqueos mutuos siempre que la tarea no se suspenda durante la ejecución de la sección crítica. Sigue pudiendo producir bloqueos innecesarios a las tareas con menor prioridad que el techo que no comparten el recurso.

Aplicándoselo al ejemplo anterior, en este caso, se comporta de igual forma que el protocolo de no expulsión, al tener techo de prioridad del recurso x prioridad más alta, dada por la tarea 1.



  1. Protocolo de herencia básica: en los protocolos anteriores la sección crítica siempre ejecutaba con una prioridad fija, en este protocolo puede ejecutar a varias prioridades. La prioridad de la sección crítica es la mayor de las prioridades de las tareas que bloquean el recurso. Si durante la ejecución de la sección crítica una tarea de prioridad superior a la sección intenta tomar el recurso, la prioridad de la sección crítica aumenta automáticamente hasta esta prioridad superior. Este protocolo elimina totalmente la inversión de prioridad pero produce bloqueos de peor caso mayores que los protocolos anteriores.

Aplicándolo al ejemplo anterior los bloqueos sufridos son los siguientes:






Cuando la tarea  1 trata de coger el recurso después de ejecutar a la prioridad de 4 cambia a la de 1, ejecutándose la sección crítica, y bloqueando a las tres tareas de prioridad superior.



  1. Protocolo de techo de prioridad : es equivalente al protocolo de herencia básica de prioridad más una regla acerca de la petición a la petición de bloqueo sobre un semáforo libre: una tarea no sólo puede usar un recurso si su prioridad (definida por la herencia básica) es mayor que el techo de todos los recurso en uso por otras tareas

Este protocolo previene el bloqueo mutuo siempre y cumple la propiedad de bloquear como máximo una vez en cada ciclo.
Aplicándolo al ejemplo anterior los bloqueos sufridos son los siguientes:

Cuando 2 trata de ejecutar by, aunque tiene mayor prioridad que 4, el recurso x que está ejecutando 4 tiene mayor techo de prioridad (prioridad de 1) que 2.



2.4 Planificación de eventos no periódicos.

Hasta ahora no hemos considerado en ningún momento como se comporta un sistema cuando alguna de sus tareas no sigue un patrón de llegadas periódico, tareas aperiódicas. Dentro de las tareas aperiódicas podemos diferenciar entre aquellas que el régimen de ocurrencia de eventos está tiene restricciones temporales, o aquellas donde nada podemos decir de su patrón de activaciones, aperiódicas ilimitadas. Las tareas aperiódicas son usadas típicamente para servir procesos con requerimientos aleatorios.


En las tareas con restricciones temporales la limitación de los eventos puede venir dado por dos diferentes patrones:


  • Esporádicas: aunque los eventos se generan a intervalos no regulares, se conoce el tiempo mínimo entre dos activaciones consecutivas de la tarea. Este tiempo mínimo entre llegadas es deseable conocerlo, y se identificará con la letra T, al igual que el periodo de las tareas periódicas.

  • Limitado: los eventos se generan a intervalos no regulares pero tienen garantizada una densidad máxima de ocurrencia. De forma que se puede asegurar que un tiempo T el número máximo de eventos que pueden ocurrir son nmax. Desde el punto de vista de análisis de peor caso podemos considerar este patrón como un conjunto de nmax tareas esporádicas con tiempo mínimo entre llegadas igual a T.

Las tareas aperiódicas ilimitadas pueden generar de forma hipotética un número no finito de activaciones en un momento determinado. Realmente esto nunca podrá ocurrir por las limitaciones físicas del sistema, siendo este tipo de tareas aperiódicas realmente limitadas. Se considerarán así ilimitadas las tareas en las cuales no sea posible conocer la limitación de su patrón de activaciones.


Mientras que las tareas aperiódicas ilimitadas no pueden tener requerimientos temporales (no tienen deadlines), no podemos decir lo mismo de esporádicas y las limitadas las cuales pueden tener un plazo de ejecución más o menos estricto (tiempo real duro o blando).
Cuando tenemos un sistema de tiempo real con tareas periódicas y aperiódicas debemos buscar un política de planificación cuyos objetivos sean los siguientes:


  • Cumplimiento de los plazos de las tareas periódicas, de forma que las aperiódicas no interfieran en dichos plazos

  • Garantizar los tiempos de respuesta de las tareas esporádicas y limitadas con requerimientos de tiempo real

  • Obtener los tiempos de respuesta promedio menores de las tareas aperiódicas y de aquellas sin requerimientos de tiempo real, aumentando la calidad de respuesta del sistema.

Hasta ahora en las políticas de planificación sólo habíamos considerado tareas periódicas, tendremos que considerar por tanto la posibilidad de la existencia de tareas aperiódicas.
Desde el punto de vista de análisis de peor caso, si las tarea aperiódicas son esporádicas con requerimientos de tiempo real, se consideran como tareas periódicas de periodo T; si tenemos tareas aperiódicas limitadas con parámetros T y nmax, con requerimientos de tiempo real, se consideran como nmax tareas esporádicas de periodo T. El problema surge cuando tenemos tareas sin requerimientos de tiempo real y/o tareas aperiódicas ilimitadas, donde tendremos que considerar una planificación adecuada para tratar estas tareas, además del método de planificación para las tareas con requerimientos de tiempo real .
A fin de simplificar la notación llamaremos tareas aperiódicas tanto a las que son aperiódicas ilimitadas o las tareas que siendo periódicas o no tiene requerimientos de tiempo real, y serán tratadas de igual forma.

La manera de tratar a las tareas aperiódicas varía según sea la planificación de las tareas con requerimientos temporales. Tendremos que distinguir entre la planificación de tareas aperiódicas en sistemas de prioridades fijas y con prioridades dinámicas. Mientras en los sistemas de prioridades fijas el problema es la asignación de una prioridad a las tareas aperiódicas, en los de prioridades dinámicas el problema es la asignación de su deadline. Aun así podemos establecer una clasificación de los métodos de planificación de tareas aperiódicas independientemente de si el sistema está tratado mediante prioridades dinámicas o estáticas:




  • Planificación en segundo plano: las tareas aperiódicas tienen la menor prioridad del sistema(prioridades fijas) o un deadline infinito(prioridades dinámicas). De esta forma las tareas periódicas son siempre aceptadas en el sistema y cumplen sus plazos si así lo hacían sin tareas aperiódicas, ya que éstas se ejecutan sólo si el procesador está libre de alguna tarea periódica. En este método la ejecución de las tareas aperiódicas se retrasan de forma incontrolable.




  • Planificación por interrupciones: los sucesos aperiódicas se tratan inmediatamente después de la interrupción asociada. Es el método obvio para reducir los tiempos de respuesta de las tareas aperiódicas pero las tareas críticas pueden perder sus plazos de ejecución.




  • Planificación por servidor de consulta (polling): se crea una tarea periódica para tratar eventos aperiódicos asociando a dicha tarea un periodo y un tiempo de ejecución. Cuando la tarea de polling se activa comprueba si hay peticiones pendientes y las atiende, sino hay eventos aperiódicos pendientes el tiempo asignado se pierde.




  • Planificación de holgura:la holgura es el tiempo de computo no utilizado por ninguna tarea periódica (la utilización del procesador por tareas periódicas ha de ser menor al 100%). Existen varios algoritmos para detectar la holgura existente, y son desarrollados originalmente para planificación dinámica siendo más complejos de implementar con prioridades fijas. Para planificar la tarea aperiódica de instante de activación ta y de tiempo de computo ca hay que determinar el instante t más cercano tal que ca unidades de holgura estén disponibles entre [ta, t].




  • Planificación con reserva de ancho de banda: Se reserva un tiempo de cómputo para tratar eventos aperiódicos de forma periódica con parámetros Tsy Cs. Otro parámetro adicional es el de la prioridad Ps para planificadores estáticos y el deadline Ds en planificadores dinámicos . El valor de estos parámetros se eligen de forma que las tareas críticas sigan siendo panificables. Si se presenta un suceso de la tarea servida por el servidor de ancho de banda se procesa inmediatamente si hay capacidad disponible hasta que el procesamiento concluya o la capacidad del servidor se agote. Si la capacidad se agota, se suspende el procesamiento o se realiza en se realiza en segundo plano hasta que la capacidad se restituya. Existen diversos planificadores de reserva de ancho de banda que se diferencia en como se restituye el tiempo consumido. Estos sistemas son predecibles y existen algoritmos que nos permiten obtener los tiempos de respuesta de peor caso de las tareas periódicas.

Los tres primeros son métodos simples sólo válidos para sistemas acrílicos, y proporcionan por lo general unos resultados muy pobres. La extracción dinámica de holgura o planificación de holgura es un algoritmo costoso y no siempre garantiza la existencia de la holgura suficiente. Por el contrario la reserva de ancho de banda es predecible y más eficiente que los anteriores.






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