Sincronización.
En procesos concurrentes, la ejecución de un proceso se desarrolla en forma asíncrona respecto a los otros. Sin embargo cuando dos, o más procesos necesitan entrar en región crítica, es necesario que exista una sincronización entre ellos a fin de garantizar que al menos uno y solo un proceso entrará en región crítica.
Si una actividad desea impedir que otra acceda a ciertos datos compartidos, mientras no se cumpla una determinada condición, debemos sincronizar las actividades con dicha condición. Por tanto, la sincronización es un elemento necesario para asegurar la exclusión mutua.
Existen tres algoritmos diseñados para este fin, son los siguientes:
- Espera Activa.
- Espera no Activa
- Mecanismos de Hardware.
Algoritmo de Espera activa.
Estos algoritmos establecen la espera de entrada a la región crítica con un bucle que será roto en el momento en que se cumpla una determinada condición. Se, les llama así por que el proceso no queda bloqueado en su ejecución, sino que constantemente compite por el procesador. Entre los distintos algoritmos de este tipo existentes podemos citar:
. Espera con mutex. Algoritmo que utiliza un switch (MUTEX) a través del cual se produce la sincronización.
. Alternancia. Ligeramente mejor que el anterior, utiliza también una
variable turno para realizar el sincronismo entre los
Procesos.
. Algoritmo de DEKKER. Resuelve el problema mediante la solución propuesta
por DEKKER, basando su funcionamiento en una
Tabla unidimensional de dos elementos lógicos
(Switches).
Algoritmo de Espera no activa.
Son los algoritmos que establecen la espera para entrar en la región crítica bloqueando, el proceso, haciendo que deje de competir por el procesador hasta que se cumpla la condición de desbloqueo.
Entre estos algoritmos existen los siguientes:
. Semáforos: Para eliminar los problemas que se producen con los algoritmos de espera activa, fundamentalmente los referidos a la sobrecarga que producen en el sistema, Dijkstra(1965) diseño un mecanismo basado en una variable entera utilizada como contador de peticiones de entrada a una sección crítica. Esta variable es compartida por todos los procesos del sistema. Este nuevo tipo de variable se denominó semáforo, por su capacidad de gestionar el tráfico de los proceso que desean acceder a datos compartidos.
Con este sistema, cuando un proceso intente entrar en una región crítica mientras otro está accediendo a los datos compartidos, se bloqueará de igual manera que cuando un proceso accede a un recurso que está ocupado.
Un semáforo se define como una variable entera que puede inicializarse y su valor no debe ser negativo y solo puede ser manipulada por las operaciones P y V.
. Operaciones P y V. Estas operaciones son indivisibles, es decir que cuando un proceso ejecuta una de ellas no puede ser interrumpida.
Operación V: Esta operación consiste en incrementar en uno el valor del semáforo sobre el que actúa, también es conocida como signal. Es una operación de liberación.
Así, si se tiene un semáforo S, V de S V(S) o signal(S) causara S=S+1. V(MUTEX) - libera
Operación P: Bloqueo, decrementa en uno el valor del semáforo sobre el que actúa siempre y cuando el valor del semáforo es >=0 (positivo) también se le conoce en la literatura inglesa como Wait. Por ejemplo si tenemos P(S), Wait(S) si S=S-1. P(MUTEX) - Espera el proceso.
De las definiciones anteriores se puede observar que el valor de un semáforo esta relacionado con el número de veces que se ejecutan, dichas operaciones es decir, el valor del semáforo S es igual a su valor inicial más número de operaciones V menos número de operaciones P realizadas por ese semáforo.
VAL(S) = C(S) + NV(S) - NP(S) NP( ) <= NV( ) +1
VALOR VALOR INICIAL
Por definición se tiene que el valor del semáforo debe ser mayor que cero, VAL(S)>0. En el caso cuando el valor del semáforo es cero que relación nos queda:
NP(S) = C(S) + NV(S)
Es importante señalar que la relación anterior será siempre valida independientemente del número de operaciones P y V ejecutadas sobre el semáforo.
. Regiones críticas: Son sistemas que permiten establecer protecciones contra una mala utilización de los usuarios. Para ello sólo permiten que los datos compartidos se puedan acceder desde determinadas regiones quedando transparentes desde el resto.
Tiene inconvenientes relacionados con la sincronización y no permite que varias actividades puedan realizar operaciones de lectura simultánea.
. Regiones criticas condicionales: Es una mejora del método anterior tratando de resolver algunos problemas de sincronización que se presentan.
. Monitores: Uno de los problemas en los mecanismos anteriores es que el programador tiene que proporcionar de forma explícita el modo de sincronización. Para evitarlo B. Hansen y C.A.R. Hoare desarrollarón un nuevo mecanismo denominado Monitor, que debe ser soportado por el lenguaje correspondiente.
Un monitor permite compartir, segura y eficientemente, datos entre varias actividades, garantizando la exclusión mutua, sin necesidad de que el programador tenga que suministrarla explícitamente.
Se basa en dos premisas: la primera es la abstracción de datos consistente en una técnica capaz de separar las operaciones a ejecutar sobre los datos, de los detalles de diseño propio de los mismos (los lenguajes Modula y Ada soportan este tipo de estructuras). La segunda es que realizan la exclusión mutua de forma implícita.
La finalidad más útil de los monitores es reunir todas las funciones que operan sobre un conjunto de datos compartidos en un sólo módulo, de manera que todos los accesos a esos datos estarán forzados a utilizar dichas funciones.
. Contadores de eventos: Es un mecanismo para sincronizar actividades sin que sea necesario forzar la exclusión mutua, ya sea por que no deseamos limitar la concurrencia de las actividades, o simplemente porque no lo necesitamos. Se basa en una variable entera que cuenta determinadas operaciones.
. Mensajes: Mecanismo que permite intercambiar información necesaria durante el desarrollo normal de un proceso en ejecución. Es más un mecanismo de cooperación que de sincronización.
Existen dos tipos de comunicación entre procesos:
- Directa: Envió y recepción de mensajes entre si; de manera que se asocia un enlace vi direccional único entre cada dos procesos.
- Indirecta: Mensajes enviados y recibidos a través de mail boxees o buzones de correo. Con este método cada proceso puede estar relacionado con tantos buzones como desee consiguiendo comunicarse con tantos procesos como sea necesario.
Mecanismos de Hardware
Son instrucciones hardware que aseguran la exclusión mutua. Entre las más utilizadas son las siguientes:
. Deshabilitar interrupciones.
Se puede forzar la exclusión mutua deshabilitando las interrupciones mientras haya alguna actividad en la región crítica. De este modo, dicha actividad no podrá ser interrumpida y, por tanto, no se podrá producir ningún cambio de proceso. La habilitación y deshabilitación se realiza con una instrucción máquina, es una operación rápida.
. Instrucción TEST-AND-SET.
Forza la exclusión mutua. La ventaja es que no puede ser interrumpida por que no muchas computadoras la poseen.
. Lock.
Se basa en la instrucción anterior y permite el acceso a la región crítica a un proceso en caso de no existir otra actividad dentro de su región crítica, no permitiendo en caso contrario.
¿Como resolver la exclusión mutua usando semáforos?.
Para resolver el problema de debe hacer lo siguiente:
1.- Identificar todas las regiones críticas.
2.- Definir tantos semáforos como regiones críticas se tengan, dichos semáforos se
inicializarán con 1.
3.- C/U de las regiones críticas será antecedida por la operación P y precedida por la
operación V.
Ejemplo: MUTEX es el semáforo
Región crítica.
Con lo anterior solo un proceso podrá entrar a la región crítica con lo que se esta asegurando la exclusión mutua.
MUTEX = 1
* Que pasa si se tiene:
A) P(MUTEX) Entra el proceso, se decrementa en uno el semáforo
SECCION CRITICA pero no libera, por lo tanto hay un dead lock, no
P(MUTEX) hay sincronización entre procesos ni exclusión
mutua
B) V(MUTEX) Sale el proceso se incrementa en uno el semáforo
SECCION CRITICA libera el proceso, por lo tanto no hay dead lock, no
V(MUTEX) origina proceso de exclusión mutua.
C) V(MUTEX) Sale el proceso se incrementa en uno el semáforo
SECCION CRITICA pero no libera, por lo tanto no hay dead lock.
P(MUTEX)
D) P(MUTEX) Entra el proceso consume y libera, por lo tanto no
SECCION CRITICA hay dead lock, y da solución a la exclusión mutua
V(MUTEX) y a la sincronización.
Pregunta. * Varios procesos actualizan en forma concurrente a una lista ligada.
a) Que problema se puede producir.
R.- Se puede producir un problema de sincronización y no hay exclusión mutua.
b) Es un problema de exclusión mutua.
R.- Exclusión mutua.
c) Como resolver el problema.
R.- Dando solución a la exclusión mutua.
* Si las operaciones P y V no fueran atómicas, la exclusión mutua seria violada.
R.- Si por que los procesos pueden tomar el mismo valor y no se incrementa dos veces sino solo una.
Problemas clásicos de sincronización.
Este tipo de problemas constituyen ejemplos de una amplia clase de problemas de control de concurrencia. Estos problemas se utilizan para probar casi todos los esquemas de sincronización propuestos. En las soluciones se emplean semáforos para la solución.
* El problema de buffer limitado.
Supongamos que el depósito consiste en n buffers, cada uno capaz de almacenar un elemento. El semáforo MUTEX proporciona la exclusión mutua para los accesos al depósito de buffers y se le asigna un valor inicial de 1. Los semáforos vacíos y llenos cuentan el número de buffers vacíos y llenos, respectivamente. El semáforo vacío recibe 1 un valor inicial n; al semáforo lleno se le asigna el valor inicial 0.
* El problema de los lectores y escritores.
Un objeto de datos (como un archivo o un registro) va a ser compartido por varios procesos concurrentes. Algunos de estos procesos sólo quieren leer el contenido del objeto compartido, mientras que otros quieren actualizarlos (o sea, leerlo y escribirlo), hacemos una distinción entre estos dos tipos de procesos refiriéndonos a los procesos interesados sólo en leer como lectores y escritores y a los demás como escritores. Obviamente, el que dos lectores tengan acceso simultáneo al objeto de datos compartido no tendrá ningún efecto adverso; sin embargo, si un escritor y otro proceso (ya sea lector o escritor) tiene acceso simultáneo al objeto compartido, puede surgir el caos.
Para asegurar que no surjan estas dificultades, es necesario que los escritores tengan acceso exclusivo al objeto compartido. A este problema de sincronización se le conoce como problema de los lectores y escritores, el cual es ha utilizado para probar casi todas las nuevas primitivas de sincronización.
* El problema de los filósofos comensales.
Cinco filósofos pasan su vida comiendo u pensando. Los filósofos comparten una mesa circular rodeada por cinco sillas, una para cada uno de ellos. En el centro de la mesa se encuentra una fuente de arroz, y también sobre la mesa hay cinco palillos chinos. Cuando un filósofo piensa, no interactúa con sus colegas. Ocasionalmente, un filósofo tiene hambre y trata de coger los dos palillos que están más cerca de él (los palillos colocados entre él y sus vecinos de la derecha y de la izquierda). Un filósofo sólo puede coger un palillo a la vez y, obviamente, no puede ser el que esta en la mano de un vecino. Cuando un filósofo ambiento tiene sus dos palillos al mismo tiempo come sin soltarlos. Cuando termina de comer, coloca ambos palillos sobre la mesa y comienza a pensar otra vez.
* Problema del productor consumidor.
En un contexto de procesos concurrentes, se tiene un conjunto de procesos productores de mensajes y otro conjunto de procesos consumidores de mensajes. La zona donde se depositarán y recogerán los mensajes es un buffer de tamaño n (n localidades).
Tanto productores como consumidores ejecutaran cíclicamente los siguientes algoritmos.
Productor consumidor.
El recurso que se va a compartir es el buffer por lo tanto la sección critica será el acceso y manipulación de dicho buffer.
* Para resolver el problema de exclusión mutua será necesario definir un semáforo para controlar el acceso al buffer,
. Definición de un semáforo para controlar el accedo a buffer.
- Cuando el consumidor se apodera del buffer P ( ) !Sorpresa esta vacío ¡
se apodera del buffer
¡¡¡sorpresa el buffer esta lleno!!!
no va a poder depositar
y por lo tanto va a liberar el buffer
nunca hace V( ).
- Productor consumidor utilizando espera activa, figura # 22.
Productor Consumidor
Produce msg. Lock (existe msg.)
Lock (espacio disponible) Lock (acceso a buffer)
Lock (acceso a buffer) extrae msg.
Deposita msg. Unlock (acceso a buffer)
Unlock (acceso a buffer) Unlock (espacio disponible)
Unlock (existe msg.) Consume msg.
Problema de sincronización. La sincronización entre productor y consumidor es necesaria debido a lo siguiente: Los productores no deben depositar mensajes si el buffer se encuentra lleno y los consumidores no deben accesar el buffer cuando este se encuentre vació.
Para resolver el problema de definirá un semáforo que defina el espacio disponible y será inicializado con un valor igual a n y un semáforo que defina la existencia de mensaje el cual será inicializado con un 0.
Productor Consumidor
Solución a la exclusión mutua X –
- Solución de la sincronización
Casos críticos
- Buffer vacío
No hay comentarios:
Publicar un comentario