Semáforos
Planificador de procesos: Diagrama de estados simplicado
Para comprender apropiadamente cómo funcionan los semáforos vamos a recordar el diagrama de estados simplificado que emplea el planificador de procesos del sistema operativo.
|---------------| pendiente | | recibido evento ---------> | bloqueado |----------- evento externo | | | | externo | |---------------| | | | | planificador \/ |--------------| retira CPU |---------------| | | -------------------> | | | activo | | preparado | | | <------------------- | | |--------------| |---------------| planificador asigna CPU
La vida de un proceso pasa por tres estados:
- Activo: el proceso está empleando la CPU, por tanto, está ejecutandose. Hay tantos procesos activos como recurso de procesamiento disponible. Por tanto, si el sistema dispone de un único procesador, únicamente puede haber un proceso activo a la vez.
- Preparado: el proceso no está ejecutándose pero es candidato a pasar a estado activo. Es el planificador el que, en base a un criterio de planificación, decide qué proceso selecciona de la lista de procesos preparados para pasar a estado activo.
- Bloqueado: el proceso está pendiente de un evento externo, tales como la espera de finalización de un proceso hijo, una señal, una operación sobre un semáforo o una operación de lectura/escritura.
La transición de activo a preparado y viceversa depende de decisiones tomadas por el planificador del sistema operativo (que emplea algún criterio visto en clases teóricas, tales como el turno rotatorio), el programador no puede interferir en estas decisiones. Mientras que la transición de activo a bloqueado, y de bloqueado a preparado pueden ser controladas por el programador mediante llamadas al sistema.
Semáforos
Los semáforos son un mecanismo de sincronización de procesos inventados por Edsger Dijkstra. Los semáforos nos permiten asistir al planificador del sistema operativo en su toma de decisiones de manera que nos permiten sincronizar la ejecución de dos o más procesos.
Los semáforos son un tipo de datos (TAD) que están compuestos por dos atributos:
- Un contador, que siempre vale >= 0.
- Una lista de procesos, inicialmente vacía.
Son usados para controlar el acceso a ciertas partes de un programa llamadas secciones críticas, en la que se manipulan recursos que deben ser tratados de forma especial.
El valor del semáforo, tanto en su inicialización como a lo largo de la ejecución del proceso, es muy importante ya que será lo que controle el número de procesos accediendo al recurso compartido de manera simultánea.
El tipo mas simple de semáforo es el binario. Pueden tomar como valor 0 o 1 y sólo permite el acceso a un único proceso a la vez.
Los semáforos disponen de dos operaciones básicas que pasamos a describir en pseudocódigo:
down(semáforo s)
{
si s.contador == 0:
proceso a estado bloqueado
añade proceso a s.lista
sino:
s.contador--
}
Nótese que siempre que queramos forzar una transición de un proceso a estado bloqueado, tenemos que hacer que dicho proceso realice una operación down sobre un semáforo cuyo contador vale cero.
up(semáforo s)
{
si hay procesos en s.lista
retira proceso de s.lista
proceso a estado preparado
sino:
s.contador++
}
Nótese que una operación up sobre un semáforo en el que hay procesos en su lista resulta en que se retire uno de los procesos (el que más tiempo lleva en la lista), realizando éste la transición a estado preparado. Es un error frecuente pensar que una operación up resulte en que el proceso retirado de la lista pase a estado activo. Recuerde que las transiciones de estado activo a preparado y viceversa son siempre controladas por el planificador del sistema operativo.
Los semáforos son un mecanismo de esperas no ocupadas, lo que significa que permite sincronizar a los procesos de forma que no se desperdician recursos de CPU cuando un cierto no proceso no tiene actividad a realizar (la espera ocupada, también conocida como espera activa, es en la que se queda comprobando la condición hasta verificarla).
Granularidad: número de recursos controlados por un semáforo
Problemas: El uso de semáforos también tiene algunos inconvenientes, entre los que destacan:
- Facilidad para emplearlos incorrectamente.
- Son independientes del lenguaje de programación, y por tanto no hay comprobación ninguna en tiempo de compilación.
- No hay nada que obligue a usarlos.
- Son independientes del recurso compartido al que intentan regular.
Ejemplo productor-consumidor: Supongamos un proceso que produce y otro que consume lo producido. Lo deseable es que el productor actúe primero, y no más de 1 vez consecutiva, puesto que el consumidor consume de 1 en 1.
Inicializacion | Productor | Consumidor |
---|---|---|
semaforo prod,cons; | while(1){ | while(1){ |
semaforo_create(cons,0); | down (prod); | down (cons); |
semaforo_create(prod,1); | produce(); | consume(); |
up(cons); | up(prod); | |
} | } |