Comunicacion mediante mensajes Las tareas se pueden comunicar y sincronizar mediante mensajes. Esta forma de comunicacion no necesita de memoria comun. Es posible utilizar buzones como mencanismo de comunicación. Hay tres aspectos de interes: Sincronizacion. Identificacion del proceso emisor y receptor. Estructura de los mensajes
Diagrama de secuencia de mensajes send receive A B B Representan la interacción entre procesos mediante el intercambio de mensajes El tiempo va hacia abajo Buzón
Sincronización en el envío de mensajes El proceso receptor siempre espera si el mensaje no ha llegado todavia. Para el proceso emisor hay tres modelos basicos: Comunicación asíncrona: el emisor continua su ejecución. Comunicación síncrona (cita): el emisor espera a que el receptor reciba el mensaje. Invocación remota (cita extendida): el emisor espera a que el receptor reciba el mensaje, y la respuesta de éste.
Comunicación Asíncrona send receive A El numero de mensajes que pueden enviarse depende del tamaño del buzón. El emisor puede saturar el buzón (si no hay receptcion) y hasta entonces bloquearse. El receptor puede bloquearse si el buzón se encuentra vacio. Buzón B
Comunicación Síncrona send receive A El buzón acepta solo un mensaje Al enviar un mensaje el emisor espera (bloqueado) hasta que el receptor ha recibido el mensaje. Lo mismo ocurre cuando el receptor ejecuta el receive primero. Buzón mensaje A send(m); receive (ack); B receive(m); send (ack); B
Invocación Remota send receive A El buzón acepta solo un mensaje Al enviar un mensaje el emisor espera (bloqueado) hasta que el receptor ha recibido el mensaje. Lo mismo ocurre cuando el receptor ejecuta el receive primero. mensaje A s_send(m);
s_receive (ack); reply bloqueo B s_receive(m); preparar reply s_send(r); B
Estructura de los mensajes El mensaje podria llevar los siguentes campos: Encabezado. Identificador del emisor. Identificador del receptor. Longitud del mensaje Mensaje. Campo de ack. Campo de seguridad
El contenido del mensaje deberia poder ser de cualquier tipo.
Identificación del emisor y el receptor Identificación directa o indirecta: Directa: el emisor identifica explicitamente al receptor send mensaje to proceso Indirecta: se utiliza un intermediario (buzón, canal, tubería, etc) send mensaje to buzón Simetria: Comunicacion simétrica: el emisor identifica al receptor y viceversa. send mensaje to proceso (buzón) receive mensaje from proceso (buzón) Comunicacino Asimétrica: el receptor acepta mensajes de cualquier emisor o buzón.
Problemas con la Interacción entre tareas Cuando dos o mas tareas comparten datos, sen envian mensajes o se sincronizan entre si, puede ocurrir que una tarea tenga que esperar un suceso de otra menos prioritaria Esta situación se denomina bloqueo, y produce una inversión de prioridad indeseable La inversión de prioridad no se puede eliminar completamente, pero es posible limitar su duración
Ejemplo 1 X Y
Ejemplo 1: inversión de prioridad 0 2 4 6 8 10 12 14 16 18 bloqueo a1 ax ay a2 b1 by by b2 c1 d1 dx dx d2
Herencia de prioridad Una forma de reducir la duración de los bloqueos es variar dinámicamente la prioridad de las tareas Cuando una tarea está bloqueando a otra más prioritaria, hereda la prioridad de está La prioridad dinámica de una tarea es el máximo de su prioridad básica las prioridades de todas las tareas bloqueadas por ella La herencia de prioridad es transitiva
Ejemplo 1: herencia de prioridad 0 2 4 6 8 10 12 14 16 18 a1 ax ay a2 b1 by by b2 c1 d1 dx dx d2
Duración máxima de bloqueo Con el protocolo de herencia de prioridad, una tarea se puede bloquear como máximo una vez por cada sección crítica una vez por cada tarea de prioridad inferior La duración total máxima de los bloqueos es
donde K es el número de recursos compartidos C es el tiempo durante el cual la tarea j accede al recurso K(=0 si no usa el recurso) j,k
Ejemplo 1: cálculo de bloqueo B = C + C = 2+4=6 B = C = 4 B = C = 4 B = 0
Una tarea puede bloquearse por recursos a los que no accede (por ejemplo, 2) Una tarea puede sufrir bloqueo aunque no acceda a recursos compartidos (por ejemplo, 3) La tarea de menor prioridad ( 4) no sufre bloqueo 1 2 3 4 2,Y 4, X 4, X 4, X
Tiempo de respuesta con bloqueos Cuando hay bloqueos, la ecuación del tiempo de respuesta queda así: La solución se obtiene mediante la relación de recurrencia
Protocolos de techo de prioridad El techo de prioridad de un recurso es la máxima prioridad de las tareas que lo usan El protocolo del techo de prioridad consiste en: la prioridad dinámica de una tarea es el máximo de su prioridad básica y las prioridades de las tareas a las que bloquea una tarea sólo puede usar un recurso si su prioridad dinámica es mayor que el techo de todos los recursos en uso por otras tareas
Ejemplo 1: techo de prioridad 0 2 4 6 8 10 12 14 16 18 a1 ax ay a2 b1 by by b2 c1 d1 dx dx d2 dx
Propiedades Cuando se usa el protocolo del techo de prioridad en un sistema monoprocesador, Cada tarea se puede bloquear una vez, como máximo, en cada ciclo No puede haber interbloqueos No puede haber bloqueos encadenados Se consigue la exclusión mutua sin mecanismos de protección adicionales La duración máxima del bloqueo es ahora B = max C
lc(i) es el conjunto de recursos que pueden bloquear i felp(f),k lc(i) j,k
Protocolo del techo de prioridadinmediato Con este protocolo, una tarea que accede a un recurso hereda inmediatamente el techo de prioridad del recurso la prioridad dinámica de una tarea es el máximo de su prioridad básica y los techos de prioridad de los recursos que usa Las propiedades son las mismas que las del protocolo del techo de prioridad, y además, si una tarea se bloquea, lo hace al principio del ciclo Es más fácil de implementar que el protocolo básico Es más eficiente ( menos cambios de contexto )
Ejemplo 1: techo de prioridadinmediato 0 2 4 6 8 10 12 14 16 18 a1 ax ay a2 b1 by b2 c1 d1 dx d2
Resumen Un método de planificación tiene dos partes: un algoritmo de reparto de recursos un método de análisis del comportamiento temporal El método clásico se basa en un ejecutivo cíclico el análisis es inmediato (por construcción) es poco flexible y de bajo nivel Un método mejor se basa en el uso de prioridades fijas las prioridades se asignan por orden de período, plazos o de forma arbitraria se puede analizar el tiempo de respuesta de las tareas se pueden analizar tareas con interacción si se usa un protocolo de herencia o techo de prioridad
| Página siguiente |