Las diversas soluciones hardware al problema de
la seccion critica, basadas en las instrucciones TestAndSet () y Swap (), son
complicadas de utilizar por los programadores de aplicaciones. Para superar
esta dificultad, podemos usar una herramienta de sincronizacion denominada
semaforo.
Un semaforo S es una variable entera a la que,
dejando aparte la inicializacion, solo se accede mediante dos operaciones atomicas
estandar: wait () y signal (). Originalmente, la operacion wait () se
denominaba P (del termino holandes proberen, probar); mientras que signal( )
denominaba originalmente V (verhogen, incrementar). La definicion de wait () es
la que sigue:
wait (S) {
while S <= 0
;??? // no-op
S--;
}
La definicion de signal () es:
signal(S) {
S++;
}
Todas las modificaciones del valor entero del
semaforo en las operaciones wait () y signal () deben ejecutarse de forma
indivisible. Es decir, cuando un proceso modifica el valor del semaforo, ningun
otro proceso puede modificar simultaneamente el valor de dicho semaforo.
Ademas, en el caso de wait(), la prueba del valor entero de S (S <- 0), y su
posible modificacion (S - -) tambien se deben ejecutar sin interrupcion.
Utilizacion
Los sistemas operativos diferencian a menudo
entre semaforos contadores y semaforos binarios. El valor de un semaforo
contador puede variar en un dominio no restringido, mientras que el valor de un
semaforo binario solo puede ser 0 01. En algunos sistemas, los semaforos
binarios se conocen como cerrojos mutex, ya que son cerrojos que proporcionan
exclusion mutua.
Podemos usar semaforos binarios para abordar el
problema de la seccion critica en el caso de multiples procesos. Los n procesos
comparten un semaforo, mutex, inicializado con el valor 1. Cada proceso P; se
organiza como se muestra en la Figura 6.9.
Los semaforos contadores se pueden usar para
controlar el acceso a un determinado recurso formado por un numero finito de
instancias. El semaforo se inicializa con el numero de recursos disponibles.
Cada proceso que desee usar un recurso ejecuta una operacion wait () en el
semaforo (decrementando la cuenta). Cuando un proceso libera un recurso,
ejecuta una operacion signal()(incrementando la cuenta). Cuando la cuenta del
semaforo llega a 0, todos los recursos estaran en uso. Despues, los procesos
que deseen usar un recurso se bloquearan hasta que la cuenta sea mayor que 0.
Tambien podemos usar los semaforos para
resolver diversos problemas de sincronizacion. Por ejemplo, considere dos
procesos que se esten ejecutando de forma concurrente: P1 con una instruccion
S1 y P2 con una instruccion S2. Suponga que necesitamos que S2 se ejecute solo
despues de que Sl se haya completado. Podemos implementar este esquema dejando
que P1 Y P2 compartan un semaforo comun synch, inicializado con el valor 0, e
insertando las instrucciones:
s1;
signal(synch);
en el proceso P1, y las instrucciones
wait(synch); S2;
en el proceso P2. Dado que synch se inicializa
con el valor 0, P2 ejecutara S2 solo despues de que P1 haya invocado signal (
synch), instruccion que sigue a la ejecucion de S1.
do
waiting(mutex);
???????????? // seccion critica
signal(mutex);
??????????? // seccion restante
}while (TRUE);
??? Implementacion
La principal desventaja de la definicion de
semaforo dada aqui es que requiere una espera activa. Mientras un proceso esta
en su seccion critica, cualquier otro proceso que intente entrar en su seccion
critica debe ejecutar continuamente un bucle en el codigo de entrada. Este
bucle continuo plantea claramente un problema en un sistema real de
multiprogramacion, donde una sola CPU se comparte entre muchos procesos.
La espera activa desperdicia ciclos de CPU que
algunos otros procesos podrian usar de forma productiva. Este tipo de semaforo
tambien se denomina cerrojo mediante bucle sin fin (spinlock), ya que el
proceso "permanece en un bucle sin fin" en espera de adquirir el
cerrojo. (Los cerrojos mediante bucle sin fin tienen una ventaja y es que no
requieren ningun cambio de contexto cuando un proceso tiene que esperar para
adquirir un cerrojo.
Los cambios de contexto pueden llevar un tiempo
considerable. Por tanto, cuando se espera que lo-s cerrojos se mantengan
durante un periodo de tiempo corto, los cerrojos mediante bucle sin fin pueden
resultar utiles; por eso se emplean a menudo en los sistemas multiprocesador,
donde una hebra puede "ejecutar un bucle" sobre un procesador
mientras otra hebra ejecuta su seccion critica en otro procesador).
Para salvar la necesidad de la espera activa,
podemos modificar la definicion de las operaciones de semaforo wa i t () y s i
gna 1(). Cuando un proceso ejecuta la operacion wa i t () y determina que el
valor del semaforo no es positivo, tiene que esperar. Sin embargo, en lugar de
entrar en una espera activa, el proceso puede bloquearse a si mismo. La
operacion de bloqueo coloca al proceso en una cola de espera asociada con el
semaforo y el estado del proceso pasa al estado de espera. A continuacion, el
control se transfiere al planificador de la CPU, que selecciona otro proceso
para su ejecucion.
Un proceso bloqueado, que esta esperando en un
semaforo S, debe reiniciarse cuando algun otro proceso ejecuta una operacion
signal (). El proceso se reinicia mediante una operacion wakeup () , que cambia
al proceso del estado de espera al estado de preparado. El proceso se coloca en
la cola de procesos preparados. (La CPU puede o no conmutar del proceso en
ejecucion al proceso que se acaba de pasar al estado de preparado, dependiendo
del algoritmo de planifigacion de la CPU.)
Para implementar semaforos usando esta
definicion, definimos un semaforo como una estructura "C":
typedef struct {
int value;
struct process *list;
}semaphore;
Cada semaforo tiene un valor (value) entero y
una lista de procesos list. Cuando un proce
so tiene que esperar en un semaforo, se anade a
la lista de procesos. Una operacion signa1 () elimina un proceso de la lista de
procesos en espera y lo despierta.
La operacion de semaforo wait () ahora se puede
definir del siguiente modo:
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
anadir este proceso a S->list;
block();
}
}
La
operacion de semaforo signal () ahora puede definirse asi:
signal(semaphore *S) {
S->value++;}
if (S->value <= 0) {
eliminar un proceso P de S->list;
wakeup(P);
}
}
La operacion block () suspende al proceso que
la ha invocado. La operacion wakeup () reanuda la ejecucion de un proceso
bloqueado P. Estas dos operaciones las proporciona el sistema operativo como
llamadas al sistema basicas.
Observe que, aunque bajo la definicion clasica
de semaforos con espera activa, el valor del semaforo nunca es negativo, esta
implementacion si que puede tener valores negativos de semaforo. Si el valor
del semaforo es negativo, su modulo es el numero de procesos en espera en dicho
semaforo. Este hecho resulta de conmutar el orden de las operaciones de
decremento y de prueba en la implementacion de la operacion wait ().
La lista
de procesos en espera puede implementarse facilmente mediante un campo de
enlace en cada bloque de control de proceso (PCB). Cada semaforo contiene un
valor entero y un puntero a la lista de bloques PCB. Una forma de anadir y
eliminar procesos de la lista de manera que se garantice un tiempo de espera
limitado consiste en usar una cola FIFO, donde el semaforo contenga punteros a
ambos extremos de la cola. Sin embargo, en general, la lista puede utilizar
cualquier estrategia de gestion de la cola. El uso correcto de los semaforos no
depende de la estrategia concreta de gestion de la cola que se emplee para las
listas de los semaforos.
El
aspecto critico de los semaforos es que se deben ejecutar atomicamente: tenemos
que garantizar que dos procesos no puedan ejecutar al mismo tiempo sendas
operaciones waitO y signal () sobre el mismo semaforo. Se trata de un problema
de seccion critica. En un entorno de un solo procesador (es decir, en el que
solo exista una CPU), podemos solucionar el problema de forma sencilla
inhibiendo las interrupciones durante el tiempo en que se ejecutan las
operaciones wait () y signal (). Este esquema funciona adecuadamente en un
entorno de un solo procesador porque, una vez que se inhiben las
interrupciones, las instrucciones de los diferentes procesos no pueden
intercalarse: solo se ejecuta el proceso actual hasta que se reactivan las
interrupciones y el planificador puede tomar de nuevo el control.
En un entorno multiprocesador, hay que
deshabilitar las interrupciones en cada procesador; si no se hace asi, las
instrucciones de los diferentes procesos (que esten ejecutandose sobre
diferentes procesadores) pueden intercalarse de forma arbitraria. Deshabilitar
las interrupciones en todos los procesadores puede ser una tarea compleja y, ademas,
puede disminuir seriamente el rendimiento. Por tanto, los sistemas SMP deben
proporcionar tecnicas alternativas de bloqueo, como por ejemplo cerrojos
mediante bucle sin fin, para asegurar que las operaciones wait () y signa l ()
se ejecuten atomicamente.
Es
importante recalcar que no hemos eliminado por completo la espera activa con
esta definicion de las operaciones wait () y signal (); en lugar de ello, hemos
eliminado la espera activa de la seccion de entrada y la hemos llevado a las
secciones criticas de los programas de aplicacion. Ademas, hemos limitado la
espera activa a las secciones criticas de las operaciones wait() y signal (), y
estas secciones son cortas (si se codifican apropiadamente, no deberian tener
mas de unas diez instrucciones). Por tanto, la seccion critica casi nunca esta
ocupada y raras veces se produce este tipo de espera; y, si se produce, solo
dura un tiempo corto. En los programas de aplicacion, la situacion es
completamente diferente, porque sus secciones criticas pueden ser largas
(minutos o incluso horas) o pueden estar casi siempre ocupadas. En tales casos,
la espera activa resulta extremadamente ineficiente.
Interbloqueos e inanicion
La implementacion de un semaforo con una cola
de espera puede dar lugar a una situacion en la que dos o mas procesos esten
esperando indefinidamente a que se produzca un suceso que solo puede producirse
como consecuencia de las operaciones efectuadas por otro de los procesos en
espera. El suceso en cuestion es la ejecucion de una operacion signal ().
Cuando se llega a un estado asi, se dice que estos procesos se han
interbloqueado.
Para ilustrar el concepto, consideremos un
sistema que consta de dos procesos, Po y Pl, con acceso cada uno de ellos a dos
semaforos, S y Q, configurados con el valor 1:
Po ?????????????????? Pi
wait (S)?????????? ?wait (Q);
wait (Q)?????????? wait (S);
signal (S)?????? signal (Q);
signal (Q)?????? signal (S);
Suponga que Po ejecuta wait(S) y luego P1
ejecuta wait(Q). Cuando Po ejecuta wait(Q), debe esperar hasta que P1 ejecute
signal (Q). De forma similar, cuando P1 ejecuta wait (S), tiene que esperar
hasta que Po ejecute signal(S). Dado que estas operaciones signal() no pueden
ejecutarse, Po y Pl se interbloquean.
Decimos que un conjunto de procesos esta en un
estado de interbloqueo cuando todos los procesos del conjunto estan esperando
un suceso que solo puede producirse como consecuencia de las acciones de otro
proceso del conjunto. Los sucesos que mas nos interesan aqui son los de
adquisicion y liberacion de recursos, pero tambien hay otros tipos de sucesos
que pueden dar lugar a interbloqueos, como veremos en el Capitulo 7. En ese
capitulo describiremos varios mecanismos para tratar los problemas de
interbloqueo.
Otro problema relacionado con los interbloqueos
es el del bloqueo indefinido o muerte por inanicion, una situacion en la que
algunos procesos esperan de forma indefinida dentro del semaforo. El bloqueo
indefinido puede producirse si anadimos y eliminamos los procesos a la lista
asociada con el semaforo utilizando un esquema LIFO (last-in, first-out).
