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 ¡
Productor gana
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
produce msg. P (existe msg.)
X P (espacio disponible) P (acceso s buffer)
P (acceso a buffer) extrae msg.
* deposita msg V (acceso a buffer)
V (acceso a buffer) V (espacio disponible)
X V (existe msg) Consume msg.
Solución a la exclusión mutua X –
- Solución de la sincronización
- Buffer lleno Espacio disponible=N, existe msg=0.
Casos críticos
- Buffer vacío
No hay comentarios:
Publicar un comentario