Veamos a
estudiar algunos problemas de sincronización utilizando semáforos. En concreto,
veremos:
- - ¨¨¨ - -
Repaso:
concepto de semáforo, operaciones, y precauciones.
Una
forma de entender conceptualmente la abstracción semáforo es pensar en él como
un gestor
de token, e.d. un almacén del
número de veces que se produce una condición. La creación de un semáforo
sería entonces la creación de un gestor
de tokens, y el valor de inicialización, vi, incluido en la primitiva crear_inicializar(S,vi)
indicaría el número inicial de tokens (número de condiciones que al programador
le interesa que se reflejen como condiciones iniciales), de que dispone dicho
semáforo.
La
operación wait() se puede ver como
la petición para obtener un token del gestor (preguntar al gestor si se ha
cumplido una de las condiciones que gestiona) y la operación signal() se puede ver como la entrega
de un token al gestor (el gestor incrementa su contador, número de veces que se
ha producido la condición que gestiona). La operación signal() puede provocar si se usa reiteradamente que el número de
tokens que almacene el gestor vaya más allá del valor inicial asignado durante
su creación.
¿Qué
ocurre si un proceso realiza una operación wait(), e.d. solicita un token, pero
el gestor de token no tiene ningún token disponible (contador de token vale
cero)? La operación wait() provocará que el proceso se bloquee cuando no exista
ningún token disponible.
¿Cómo
se desbloquean los procesos bloqueados por causa de la operación wait()? Cuando
se le da un token al gestor (por medio de una operación signal), el gestor comprueba si hay procesos
bloqueados en el semáforo. Si es así, uno de los procesos bloqueados es
desbloqueado y se le asigna el token[1].
La
forma de ver un semáforo como un gestor de token debe considerarse como un
modelo general abstracto para entender las operaciones y no debe confundirse con
una estrategia de implementación.
Hay que
tener en cuenta dos aspectos adicionales:
- Nunca es posible asignar el
mismo token a dos procesos. Las operaciones son atómicas.
- Una vez que se ha creado un
semáforo, sólo podemos realizar las operaciones: wait(), signal() o destruir() sobre el semáforo. NO podemos hacer operaciones del
tipo: consultar el número de tokens de un semáforo, solicitar más de un
token en una operación wait() (por supuesto podemos utilizar dos
operaciones wait() seguidas), solicitar un token y no bloquear al proceso
en el caso de que no haya ninguno disponible.
A
continuación presentamos una sencilla implementación de las operaciones básicas
que permiten utilizar el mecanismo de los semáforos contador y a reglón
seguido, estudiaremos varios problemas de sincronización y su solución
utilizando semáforos.
Un semáforo contador
es una abstracción para resolver problemas de sincronización. Se puede pensar
en un semáforo como un objeto sobre el que se pueden realizar las siguientes
operaciones (se muestra un implementación sencilla en un lenguaje pseudo
algorítmico) :
wait(S):
si S > 0 entonces S := S - 1
sino bloquear proceso
signal(S): si (hay
procesos bloqueados)
entonces desbloquear
uno proceso
sino S := S + 1
crear_inicializar(S,vi): crea e inicializa un semáforo al
valor positivo vi.
destruir(S): elimina un semáforo.
- - ¨¨¨ - -
§
Problema de la exclusión mutua
La
solución es obvia si se piensa en el concepto de semáforo como un gestor de
tokens. Se construye un semáforo con un único token (la condición que gestiona
este token sería el acceso a la sección
crítica de un solo proceso a la vez). Un proceso debe tener el token antes
de que pueda entrar en la sección crítica. Ya que existe un solo token, la
exclusión mutua está garantizada. Cuando un proceso abandona su sección
crítica, devuelve el token al gestor de token (semáforo de exclusión mutua).
P(i)
// Código previo a la sección crítica
wait(me)
// Sección crítica
signal(me)
// Resto de código
La creación
del semáforo, crear_inicializar(me,1),
debe realizarse por un proceso antes de poder usar el semáforo.
§
Problema de precedencia simple
En el problema de precedencia, un proceso no puede progresar
más allá de un cierto punto a menos que ocurra un evento previamente, o se
cumpla alguna condición.
Usando la visión del semáforo como un gestor de token la
solución es simple. Comenzar creando un semáforo con número de tokens igual a
0: crear_inicializar(evento_o_condicion,0)
Cuando un proceso alcanza el punto de sincronización, debe
obtener el token (wait()). El token
se genera cuando ocurre el correspondiente evento o la condición se cumple.
Este evento o condición se producirían en otro proceso.
|
ProcesoA //Sección
de código A1 //Sección
de código A2 signal(resultadoA1yA2); wait(resultadoB2); //Sección
de código A3 |
ProcesoB //Sección
de código B1 wait(resultadoA1yA2) //Sección
de código B2 signal(resultadoB2) |
En este ejemplo, el proceso B no puede realizar los cálculos
de la sección B2 hasta que el proceso A no haya realizado los cálculos de las
secciones A1 y A2 (hasta que se cumpla la condición), por consiguiente tendrá
que obtener el token del semáforo “resultadoA1yA2”
para poder continuar. Dicho token será enviado al semáforo solamente cuando se
cumpla la condición en el proceso A y se utilice signal() sobre dicho semáforo.
A su vez, el proceso A no puede realizar los cálculos de la
sección A3 hasta que el proceso B calcule el resultado en la sección B2. Por
tanto A deberá obtener el token del semáforo “resultadoB2” y esperará hasta que se cumpla la condición en B y se
envíe el token al semáforo.
Debemos tener en cuenta que los semáforos deberán estar
creados e inicializados en un proceso antes de poder usarlos.
Crear_inicializar(resultadoA1yA2,0);
Crear_inicializar(resultadoB2,0);
§
Problema de precedencia con condiciones
Supongamos que existe un puente en el que sólo pueden
circular coches en un sentido. Existen coches que desean cruzar el puente en
los dos sentidos. Denominaremos a los dos tipos de coches (procesos que simulan el comportamiento de los dos tipos de coches
en el sistema): CochesIzqda y CochesDcha.
Deben satisfacerse las siguientes restricciones:
- En
cualquier momento solo se permite que estén cruzando por el puente coches
en un mismo sentido de circulación.
- El
puente es bastante frágil y solo admite el peso de 10 coches
simultáneamente.
Como es usual en bastantes problemas de sincronización,
existe un trozo de código antes de la sección crítica (protocolo de entrada) y
otro código después de la sección crítica (protocolo de salida). El término sección crítica se usa aquí en un
sentido más general indicando un trozo de código sobre el cuál el proceso podrá
progresar dependiendo de una (o varias) condición(-es). En nuestro problema
particular la sección crítica representa el paso por el puente.
La idea básica es mantener un estado entre los procesos
que representan los distintos tipos de usuarios de la sección crítica (CochesIzqda y CochesDcha). El estado se
representa por medio de variables
globales compartidas, que en conjunto, mantienen la información necesaria
sobre el estado del sistema en cualquier instante de tiempo. Ya que el estado
es compartido, cualquier modificación del estado debe hacerse en una sección
crítica separada, utilizando para ello una protección de acceso por medio de la
exclusión mutua vista anteriormente.
La función del protocolo de entrada consiste en mirar el
estado compartido y decidir si el proceso puede progresar o debe esperar. Esta
comprobación vendrá determinada por las restricciones del problema.
Esencialmente este protocolo es un ejemplo de sincronización con precedencia.
La función del protocolo de salida en modificar el estado y
desbloquear a cero, uno o más de los procesos bloqueados dependiendo de las condiciones.
Para mantener el estado del sistema de cara a cubrir las
restricciones del problema necesitamos cuatro variables compartidas:
Cizqda:
Número de coches de la izquierda que están pasando por el puente.
Cdcha:
Número de coches de la derecha que están pasando por el puente.
CizqdaE:
Número de coches de la izquierda que están esperando para pasar.
CdchaE: Número de coches de la derecha que están esperando para pasar.
|
CochesIzqda(i) wait(em); If(Cdcha
> 0 || Cizqda == 10) { CizqdaE++; signal(em); wait(izquierda); }
else { Cizqda++; signal(em); } //
Pasando por el puente wait(em); Cizqda--; If(CIzqdaE
> 0) { CIzqda++; CIzqdaE--; signal(izquierda); }
else if(Cizqda == 0 && CdchaE > 0)
{ contador=
min(CdchaE,10); CdchaE=CdchaE-contador;
Cdcha=Cdcha+contador;
for(i=0;i<contador;i++) signal(derecha); } signal(em); |
CochesDcha(j) wait(em); If(Cizqda
> 0 || Cdcha == 10) { CdchaE++; signal(em);
wait(derecha); } else { Cdcha++; signal(em); } //
Pasando por el puente wait(em); Cdcha--; If(CdchaE
> 0) { Cdcha++; CdchaE--; signal(izquierda); }
else if(Cdcha == 0 && CizqdaE > 0)
{ contador= min(CizqdaE,10); CizqdaE=CizqdaE-contador;
Cizqda=Cizqda+contador;
for(i=0;i<contador;i++) signal(izquierda); } signal(em); |
Usamos un semáforo de exclusión mutua, em, inicializado a 1 para proporcionar acceso mutuamente exclusivo
a estas variables ya que son compartidas por todos los procesos.
Además usamos dos semáforos (izquierda y derecha)
para bloquear a los coches de la izquierda y de la derecha respectivamente caso
de que no puedan progresar debido a no cumplir las restricciones de
sincronización. Ya que los semáforos son utilizados para implementar una
precedencia, los inicializamos a 0.
El protocolo de entrada simplemente comprueba el estado del puente (recurso o sección de código con restricciones de acceso concurrente)
utilizando las variables compartidas y permite que el proceso progrese si las
condiciones son favorables o lo detiene si no lo son. Es importante notar que
antes de bloquear el proceso se libera la exclusión mutua ya que si no
procediésemos de esta forma, ningún otro proceso podría comprobar el estado. Ya
que el protocolo de entrada y el de salida requieren examinar y modificar el
estado compartido, este hecho conduciría a un interbloqueo.
Otro aspecto importante en el que hay que fijarse es que
cuando un proceso se desbloquea, entra directamente en la sección crítica (el
puente), sin examinar de nuevo si el estado es seguro o no, y sin modificar
dicho estado. Nosotros relegamos la responsabilidad de modificar el estado y
comprobar que sea seguro (cumpla las restricciones de sincronización) para
continuar la ejecución de un proceso al protocolo de salida. No obstante
existen otras soluciones al problema que delegarían esta responsabilidad al
protocolo de entrada.
El protocolo de salida está escrito de forma que se
favorecen a los coches del mismo sentido (esto maximiza la utilización del
puente pero puede conducir a inanición en los coches del sentido contrario).
La barbería está regentada por un peluquero, tiene una silla
para pelar a los clientes y N sillas para que esperen los clientes. Si no hay
clientes, el peluquero espera durmiendo a que entren en la peluquería. Cuando
llega un cliente, tiene que despertar al peluquero. Si llegan más clientes
mientras el peluquero está pelando a un cliente se sientan si hay sillas libres
o se van si no pueden sentarse.
|
Cliente(i) wait(em); if (clientesEsperando < N ) {
clientesEsperando++;
signal(clientes); signal(em); wait(peluquero); //Cortándose el pelo } else //No hay sitio para esperar signal(em); |
Peluquero while(1) {
wait(clientes); wait(em);
clientesEsperando-- ; signal
(peluquero);
signal(em) ; //Cortando
el pelo } |
En la solución propuesta utilizamos un semáforo clientes, inicializado a 0, que refleja
el número de clientes que actualmente están esperando para pelarse y el
semáforo peluquero, inicializado a
0, que no permite a un cliente cortarse el pelo hasta que el peluquero esté
libre.
Necesitamos una variable adicional, clientesEsperando inicializada a 0, que almacena el número de
clientes que están esperando actualmente. La razón de usar esta variable se debe
a que no podemos usar más operaciones sobre semáforos que las establecidas en
su definición y los clientes necesitan saber si hay sitio libre o no en la
peluquería, para cumplir la especificación del problema.
El uso de la variable clientesEsperando
por parte de los clientes y el peluquero implica la necesidad de utilizar un
semáforo de exclusión mutua, em,
para evitar las condiciones de carrera a la hora de actualizar dicha variable.
Un cliente entrará a la peluquería y realizará la
comprobación de si hay espacio o no. Esta comprobación se hará en exclusión
mutua, con lo que el resto de procesos cliente que quisieran cortarse el pelo
no podrán hacer nada hasta que el primer cliente libere dicha exclusión mutua.
Si no hay espacio, el cliente se marchará sin pelarse y liberará la exclusión
mutua. Caso de haber espacio, el cliente indicará por medio del semáforo
clientes que hay un cliente esperando para pelarse en la barbería e
incrementará la variable que indica el número de clientes que hay esperando para
pelarse. Posteriormente liberará la exclusión mutua y esperará en el semáforo
peluquero a que éste le atienda.
El proceso peluquero permanece bloqueado mientras no haya
clientes esperando por su corte de pelo. Cuando algún cliente lo despierta
indicando que espera para pelarse, el peluquero, en exclusión mutua, reduce en
uno el número de clientes que esperan y avisa al primer cliente bloqueado en el
semáforo peluquero para que se pele.
En este problema comprobamos que la función de pelarse y la
de ser pelado están perfectamente sincronizadas con los semáforos elegidos.
- - ¨¨¨ - -
Resolución de un problema paso-a-paso.
La siguiente presentación muestra la construcción de una
solución a un problema de sincronizado: