|
Semáforo
Método
clásico para restringir o permitir el acceso a
recursos compartidos (por ejemplo, un recurso de
almacenamiento del sistema o variables del código
fuente) en un entorno de multiprocesamiento.
Programa
del sistema operativo que controla el tráfico de
procesos dentro del sistema.
Se
emplean para permitir el acceso a diferentes partes de
programas (secciones críticas) donde se manipulan
variables o recursos que deben ser accedidos de forma
especial. Según el valor con que son inicializados se
permiten a más o menos procesos utilizar el recurso de
forma simultánea.
Un
tipo simple de semáforo es el binario,
que puede tomar solamente los valores 0 y 1. Se
inicializan en 1 y son usados cuando sólo un proceso
puede acceder a un recurso a la vez
Controla
los procesos dentro de memoria en el área de datos
compartidos (lectura, lectura/escritura, escritura).
Trabaja
con dos elementos:
-
señal (despertar)
-
espera (dormir)
Dependiendo
del tipo de operación en el área de datos compartidos,
será el semáforo que se implante.
El
uso de semáforos depende del número de procesos; en
áreas de datos no compartidos no tiene razón de ser.
Monitores
Dentro
de un sistema operativo, un monitor es un programa que
observa y administra los procesos dentro del CPU.
Se
pueden implementar monitores en memoria en áreas de
datos compartidos y no compartidos.
Un
monitor contiene el código relativo a un recurso
compartido en un solo módulo de programa;
Ventajas:
• Mantenimiento más simple
• Menos errores de programación
La
interfaz del monitor es un conjunto de funciones que
representan las diferentes operaciones que pueden
hacerse con el recurso.
La
implementación del monitor garantiza la exclusión
mutua
•
Mediante semáforos o algún otro mecanismo.
•
Implícitamente en los lenguajes concurrentes.
Se
pueden implementar en memoria u otros recursos
compartidos
NOTA:
Dentro de los monitores se implementan los semáforos.
Algoritmo
de Decker
Solución
que garantiza la exclusión mutua al gestionar
elegantemente este proceso.
Utiliza,
además de las banderas de intención de entrar, una
variable turno (proceso favorecido) que resuelve en
caso de conflicto.
Da
la posibilidad de que el otro proceso entre en su
sección crítica una segunda vez si lo hace antes que
el proceso que acaba de dejar el bucle de espera,
asigne el valor cierto a su intención de entrar. Pero
cuando de nuevo tiene el procesador, realiza la
asignación y es su turno, así que se ejecuta.
En
consecuencia, no produce aplazamiento indefinido.
La
solución se desarrolla por etapas. Este método ilustra
la mayoría de los errores habituales que se producen
en la construcción de programas concurrentes.
Primer intento
Cualquier intento de exclusión mutua debe depender de
algunos mecanismos básicos de exclusión en el
hardware. El más habitual es que sólo se puede acceder
a una posición de memoria en cada instante, teniendo
en cuenta esto se reserva una posición de memoria
global llamada turno. Un proceso que desea
ejecutar su sección crítica primero evalúa el
contenido de turno. Si el valor de turno es
igual al número del proceso, el proceso puede
continuar con su sección crítica. En otro caso el
proceso debe esperar. El proceso en espera, lee
repetitivamente el valor de turno hasta que
puede entrar en su sección crítica. Este procedimiento
se llama espera activa.
Después de que un proceso accede a su sección crítica
y termina con ella, debe actualizar el valor de turno para
el otro proceso.
Segundo
intento:
Cada proceso debe tener su propia llave de la sección
crítica para que, si uno de ellos falla, pueda seguir
accediendo a su sección crítica; para esto se define
un vector booleano señal. Cada proceso puede
evaluar el valor de señal del otro, pero no
modificarlo. Cuando un proceso desea entrar en su
sección crítica, comprueba la variable señal
del otro hasta que tiene el valor falso (indica que el
otro proceso no está en su sección crítica). Asigna a
su propia señal el valor cierto y entra en su
sección crítica. Cuando deja su sección crítica asigna
falso a su señal.
Si uno de los procesos falla fuera de la sección
crítica, incluso el código para dar valor a las
variables señal, el otro proceso no se queda
bloqueado. El otro proceso puede entrar en su sección
crítica tantas veces como quiera, porque la variable señal del
otro proceso está siempre en falso. Pero si un proceso
falla en su sección crítica o después de haber
asignado cierto a su señal, el otro
proceso estará bloqueado permanentemente.
Tercer
intento
El segundo intento falla porque un proceso puede
cambiar su estado después de que el otro proceso lo ha
comprobado pero antes de que pueda entrar en su
sección crítica.
Si un proceso falla dentro de su sección crítica,
incluso el código que da valor a la variable señal que
controla el acceso a la sección crítica, el otro
proceso se bloquea y si un proceso falla fuera de su
sección crítica, el otro proceso no se bloquea.
Si ambos procesos ponen sus variables señal a
cierto antes de que ambos hayan ejecutado una
sentencia, cada uno pensará que el otro ha entrado en
su sección crítica, generando así un interbloqueo.
Cuarto
intento
En el tercer intento, un proceso fijaba su estado sin
conocer el estado del otro. Se puede arreglar esto
haciendo que los procesos activen su señal para
indicar que desean entrar en la sección crítica pero
deben estar listos para desactivar la variable señal y
ceder la preferencia al otro proceso.
Existe una situación llamada bloqueo vital, esto no es
un interbloqueo, porque cualquier cambio en la
velocidad relativa de los procesos rompería este ciclo
y permitiría a uno entrar en la sección crítica.
Recordando que el interbloqueo se produce cuando un
conjunto de procesos desean entrar en sus secciones
críticas, pero ninguno lo consigue. Con el bloqueo
vital hay posibles secuencias de ejecución con éxito.
Una
solución correcta
Hay que observar el estado de ambos procesos, que está
dado por la variable señal, pero es necesario
imponer orden en la actividad de los procesos para
evitar el problema de "cortesía mutua". La variable turno del
primer intento puede usarse en esta labor, indicando
que proceso tiene prioridad para exigir la entrada a
su sección crítica.
Algoritmo de
Peterson
Simplifica
el algoritmo de Decker.
El
protocolo de entrada es más elegante con las mismas
garantías de exclusión mutua, imposibilidad de bloqueo
mutuo y de aplazamiento indefinido.
El algoritmo
de Peterson es un algoritmo de programación
concurrente para exclusión mutua, que permite a dos o
más procesos o hilos de ejecución compartir un recurso
sin conflictos, utilizando sólo memoria compartida
para la comunicación.
El algoritmo de Decker resuelve el problema de la
exclusión mutua pero mediante un programa complejo,
difícil de seguir y cuya corrección es difícil de
demostrar. Peterson ha desarrollado una solución
simple y elegante. Como antes, la variable global
señal indica la posición de cada proceso con respecto
a la exclusión mutua y la variable global turno
resuelve los conflictos de simultaneidad.
Considérese el proceso P0. Una vez que ha puesto
señal[0] a cierto, P1 no puede entrar en su sección
crítica. Si P1 esta aun en su sección crítica,
entonces señal[1] = cierto y P0 está bloqueado en su
bucle while. Esto significa que señal[1] es cierto y
turno = 1. P0 puede entrar en su sección crítica
cuando señal[1] se ponga a falso o cuando turno se
ponga a 0. Considérense ahora los siguientes casos
exhaustivos:
- P1
no está interesado en entrar en su sección crítica.
Este caso es imposible porque implica que señal[1] =
falso.
- P1
está esperando entrar en su sección crítica. Este
caso es también imposible porque si turno = 1, P1
podría entrar en su sección crítica.
- P1
entra en su sección crítica varias veces y
monopoliza el acceso a ella. Esto no puede pasar
porque P1 está obligado a dar a P0 una oportunidad
poniendo turno a 0 antes de cada intento de entrar
en su sección crítica.
Así
pues, se tiene una solución posible al problema de la
exclusión mutua para dos procesos. Es más, el
algoritmo de Peterson se puede generalizar fácilmente
al caso de n procesos.
Fundamento del Algoritmo de Peterson
Cuando dos o más procesos secuenciales en cooperación
ejecutan todos ellos asíncronamente y comparten datos
comunes se produce el problema de la sección crítica.
Un proceso productor genera información que es
utilizada por un proceso consumidor. Para que los
procesos productores y consumidores ejecuten
concurrentemente, tenemos que creer un conjunto de
buffers que puedan ser alimentados por el productor y
vaciados por el consumidor.
El consumidor tiene que esperar si todos los buffers
se encuentran vacíos, y el productor tiene que esperar
si todos los buffers están llenos.
Una solución simple al problema de la sección crítica
nos la proporciona Peterson. Esta solución es
básicamente una combinación del Algoritmo que asocia
cada proceso con su variable de cerradura y de una
pequeña modificación del Algoritmo de Alternancia
Estricta.
Arriba
|