PDF de programación - PROGRAMACION CONCURRENTE - II.3 Sincronización basada en memoria compartida: Semáforos

PROGRAMACION CONCURRENTE

II.3 Sincronización basada en memoria compartida:

Semáforos

J.M. Drake

Notas:

1

Procesos concurrentes y memoria compartida.

Si los diferentes procesos de un programa concurrente tienen
acceso a variables globales o secciones de memoria
comunes, la transferencia de datos a través de ella es una vía
habitual de comunicación y sincronización entre ellos.
Las primitivas para programación concurrente basada en
memoria
de
sincronización entre procesos y de exclusión mutua utilizando
la semántica de acceso a memoria compartida.
En esta familias de primitivas, la semántica de las sentencias
hace referencia a la exclusión mutua, y la implementación de
la sincronización entre procesos resulta de forma indirecta.

compartida

resuelven

los

problemas

Procodis’08: II.3- Semáforos José M.Drake

2

Notas:

2

Mecanismos basados en memoria compartida

Semáforos: Son componentes pasivos de bajo nivel de
abstracción que sirven para arbitrar el acceso a un recurso
compartido.

Secciones críticas: Son mecanismos de nivel medio de
abstracción orientados a su implementación en el contexto de
un lenguaje y que permiten la ejecución de un bloque de
sentencias de forma segura.

Monitores: Son módulos de alto nivel de abstracción
orientados a la gestión de recursos que van a ser usados
concurrentemente.

Procodis’08: II.3- Semáforos José M.Drake

3

Notas:

Los mecanismos de sintronización que se introducen en este tema son tres:
* Los semáforos que fueron introducidos inicialmente por Dijkstra (1968). Son
componentes de muy bajo nivel de abstracción, de fácil comprensión y con una gran
capacidad funcional. Por el contrario, son unos componentes que por su bajo nivel de
abstracción resultan muy peligrosos de manejar y frecuentemente son causa de muchos
errores.
* Las secciones críticas condicionales (Brinch Hansen, 1972) son unos mecanismos
introducidos como componentes de los lenguajes de programación concurrente. Tienen
un nivel de abstracción mucho mas alto que los semáforos, y en consecuencia son más
fáciles y seguros de manejar.
* Los monitores fueron introducidos por Hoare (1974), y son unos módulos de
programación de alto nivel de abstracción que resuelven internamente, el acceso de
forma segura a una variable o a un recurso compartido por múltiples procesos
concurrentes.

3

Definición de semáforo.

Un semáforo es un tipo de datos.

Como cualquier tipo de datos, queda definido por:
Conjunto de valores que se le pueden asignar.
Conjunto de operaciones que se le pueden aplicar.

Un semáforo tiene asociada una lista de procesos, en la que
se incluyen los procesos suspendidos a la espera de su cambio
de estado.

Procodis’08: II.3- Semáforos José M.Drake

4

Notas:

Un semáforo es un tipo abstracto de dato, y como tal, su definición requiere especificar
sus dos atributos básicos:

* Conjunto de valores que puede tomar.
* Conjunto de operaciones que admite.

Un semáforo tiene también asociada una lista de procesos, en la que se incluyen todos
los procesos que se encuentra suspendidos a la espera de acceder al mismo.

4

Valores de un semáforo.

En función del rango de valores que puede tomar, los semáforos se
clasifican en:
Semáforos binarios: Pueden tomar solo los valores 0 y 1.

var mutex: BinSemaphore;

Semáforos general: Puede tomar cualquier valor Natural (entero no

negativo).
var escribiendo: Semaphore;

Un semáforo que ha tomado el valor 0 representa un semáforo cerrado, y
si toma un valor no nulo representa un semáforo abierto.

Mas adelante demostraremos que un semáforo General se puede
implementar utilizando semáforos Binarios.

Los sistemas suelen ofrecer como componente primitivo semáforos
generales, y su uso, lo convierte de hecho en semáforo binario.

Procodis’08: II.3- Semáforos José M.Drake

5

Notas:

Un semáforo puede tomar valores enteros no negativos ( esto es, el valor 0 o un valor
entero positivo). La semántica de estos valores es: 0 semáforo cerrado, y >0 semáforo
abierto.

En función del rango de valores positivos que admiten, los semáforos se pueden
clasificar en:

* Semáforos binarios: Son aquellos que solo pueden tomar los valores 0 y 1.
* Semáforos generales: Son aquellos que pueden tomar cualquier valor no negativos.

Frecuentemente, el que un semáforo sea binario o general, no es función de su
estructura interna sino de como el programador lo maneja.

5

Operaciones seguras de un semáforo.

Un semáforo

var p: semaphore;

admite dos operaciones seguras:
wait(p): Si el semáforo no es nulo (abierto) decrementa en uno el
valor del semáforo. Si el valor del semáforo es nulo (cerrado), el
thread que lo ejecuta se suspende y se encola en la lista de procesos en
espera del semáforo.

signal(p); Si hay algún proceso en la lista de procesos del semáforo,
activa uno de ellos para que ejecute la sentencia que sigue al wait que
lo suspendió. Si no hay procesos en espera en la lista incrementa en 1
el valor del semáforo.

Procodis’08: II.3- Semáforos José M.Drake

6

Notas:

Los semáforos admiten dos operaciones:
* Operación Wait (P): Si el valor del semáforo no es nulo, esta operación decrementa en
uno el valor del semáforo. En el caso de que su valor sea nulo, la operación suspende el
proceso que lo ejecuta y lo ubica en la lista del semáforo a la espera de que deje de ser
nulo el valor.
* Operación Signal (V): Incrementa el valor del semáforo, y en caso de que haya
procesos en la lista de espera del semáforo, se activa uno de ellos para que concluya su
operación Wait.

Lo importante del semáforo es que se garantiza que la operación de chequeo del valor
del semáforo, y posterior actualización según proceda, es siempre segura respecto a
otros accesos concurrentes.

6

Operación no segura de un semáforo.

Un semáforo

var p: semaphore;

admite una operación no segura:

initial(p, Valor_inicial): Asigna al semáforo p el valor inicial que se

pasa como argumento.

Esta operación es no segura y por tanto debe ser ejecutada en
una fase del programa en la que se tenga asegurada que se
ejecuta sin posibilidad de concurrencia con otra operación
sobre el mismo semáforo.

Procodis’08: II.3- Semáforos José M.Drake

7

Notas:

7

Operación wait.

Pseudocódigo de la operación: wait(p);

if p>0
then p:= p-1;
else Suspende el proceso y lo encola en la lista del semáforo.

Lo característico de esta operación es que está protegida
contra interrupción entre el chequeo del valor del semáforo
y la asignación del nuevo valor.

El nombre de la operación wait es equívoco. En contra de su
significado semántico natural, su ejecución a veces provoca
una suspensión pero en otros caso no implica ninguna
suspensión.

Procodis’08: II.3- Semáforos José M.Drake

8

Notas:

La operación wait lleva a cabo la siguiente secuencia de operaciones:

if Semáforo > 0

then Semaforo:= Semaforo -1
else Suspende al proceso en la lista del semáforo;

La operación wait (como la semántica de su nombre indica) es una potencial causa de
retraso en la ejecución de un proceso. Sin embargo, es importante resaltar que no
siempre que se ejecute una sentencia wait se produce el retraso, sino solo cuando al
ejecutarla, el semáforo este cerrado, esto es tiene el valor 0.

8

Operación signal.

Pseudocódigo de la operación: signal(p);

if Hay algún proceso en la lista del semáforo
then Activa uno de ellos
else p:= p+1;

La ejecución de la operación signal(p) nunca provoca una
suspención del thread que lo ejecuta.

Si hay varios procesos en la lista del semáforo, la operación
signal solo activa uno de ellos. Este se elige de acuerdo con
un criterio propio de la implementación (FIFO, LIFO,
Prioridad, etc.).

Procodis’08: II.3- Semáforos José M.Drake

9

Notas:

9

Ejemplo: Exclusión mutua.
program Exclusion_Mutua;

var mutex: binsemaphore;
process type Proceso;
begin

repeat

wait(mutex);

(* Código de la sección crítica *)

signal(mutex);

forever;

end;

var p, q, r: Proceso;
begin

initial(mutex,1);
cobegin p; q; r; coend;

end;

Procodis’08: II.3- Semáforos José M.Drake

10

Notas:

Se plantea una solución del problema de exclusión mutua entre tres procesos P, Q y R,
respecto de una sección crítica dada. Se va a utilizar un semáforo “Seccion_Libre" para
controlar el acceso a la misma.
El valor del semáforo indica el número de procesos que se encuentran ejecutando la
sección crítica. Cuando toma el valor 0, significa que algún proceso está en su sección
crítica, mientras que cuando toma el valor 1 significa que no hay ningún proceso
ejecutándola. La estructura del programa garantiza que el semáforo es binario, y nunca
puede tomar un valor superior a 1.
De acuerdo con la semántica expuesta, el semáforo debe ser inicializado al valor 1, ya
que al comenzar, ningún proceso se encuentra en la zona crítica.
Cuando uno de los procesos va a iniciar su sección crítica, ejecuta una sentencia wait. Si
no hay otro proceso ejecutando la sección crítica, el proceso accede directamente a
ejecutarla sin necesidad de ninguna espera. En caso contrario, se incorpora a la lista
asociada al semáforo en espera de que le toque su turno de ejecución de la sección
crítica.
Cuando uno de los procesos concluye la ejecución de su sección crítica, ejecuta una
sentencia signal y continua la ejecución de las sentencias posteriores a esta, sin esperar
mayor confirmación. Con la ejecución de la sentencia signal el se