Semáforos en Sincronización de Procesos – Part 1

Semáforo fue propuesto por Dijkstra en 1965, que es una técnica muy importante para administrar procesos concurrentes mediante el uso de un valor entero simple, que se conoce como semáforo. Semaphore es simplemente una variable entera que se comparte entre subprocesos. Esta variable se utiliza para resolver el problema de la sección crítica y lograr la sincronización de procesos en el entorno de multiprocesamiento. 
Los semáforos son de dos tipos:

1. Semáforo binario: 
   esto también se conoce como bloqueo mutex. Solo puede tener dos valores: 0 y 1. Su valor se inicializa en 1. Se utiliza para implementar la solución de problemas de sección crítica con múltiples procesos.
2. Semáforo de conteo: 
   su valor puede variar en un dominio sin restricciones. Se utiliza para controlar el acceso a un recurso que tiene varias instancias.

Ahora veamos cómo lo hace.

Primero, mire dos operaciones que se pueden usar para acceder y cambiar el valor de la variable del semáforo.
 

Algún punto con respecto a la operación P y V:

1. La operación P también se denomina operación de espera, suspensión o inactividad, y la operación V también se denomina operación de señal, activación o activación.
2. Ambas operaciones son atómicas y los semáforos siempre se inicializan en uno. Aquí atómico significa que la variable en la que la lectura, la modificación y la actualización ocurren al mismo tiempo/momento sin preferencia, es decir, entre la lectura, la modificación y la actualización no se realiza ninguna otra operación que pueda cambiar la variable.
3. Una sección crítica está rodeada por ambas operaciones para implementar la sincronización de procesos. Vea la imagen de abajo. La sección crítica del Proceso P se encuentra entre las operaciones P y V.
    

Ahora, veamos cómo implementa la exclusión mutua. Sean dos procesos P1 y P2 y un semáforo s se inicializa como 1. Ahora, si supongamos que P1 ingresa en su sección crítica, entonces el valor del semáforo s se convierte en 0. Ahora, si P2 desea ingresar a su sección crítica, esperará hasta que s > 0, esto solo puede suceder cuando P1 termina su sección crítica y llama a la operación V en los semáforos. 

De esta manera se logra la exclusión mutua. Mire la imagen a continuación para obtener detalles sobre cuál es el semáforo binario.
 

Implementación de semáforos binarios:

struct semaphore {
    enum value(0, 1);
 
    // q contains all Process Control Blocks (PCBs)
    // corresponding to processes got blocked
    // while performing down operation.
    Queue<process> q;
 
} P(semaphore s)
{
    if (s.value == 1) {
        s.value = 0;
    }
    else {
        // add the process to the waiting queue
        q.push(P)
        sleep();
    }
}
V(Semaphore s)
{
    if (s.q is empty) {
        s.value = 1;
    }
    else {
 
        // select a process from waiting queue
        Process p=q.front();
          // remove the process from wating as it has been sent for CS
          q.pop();
        wakeup(p);
           
       
    }
}

La descripción anterior es para semáforos binarios que pueden tomar solo dos valores 0 y 1 y garantizar la exclusión mutua. Hay otro tipo de semáforo llamado semáforo contador que puede tomar valores mayores que uno.

Ahora supongamos que hay un recurso cuyo número de instancias es 4. Ahora inicializamos S = 4 y el resto es igual que para el semáforo binario. Cada vez que el proceso quiere ese recurso, llama a P o espera a la función y cuando termina, llama a V o función de señal. Si el valor de S se vuelve cero, entonces un proceso debe esperar hasta que S se vuelva positivo. Por ejemplo, suponga que hay 4 procesos P1, P2, P3, P4 y todos ellos llaman a la operación de espera en S (inicializado con 4). Si otro proceso P5 quiere el recurso, debe esperar hasta que uno de los cuatro procesos llame a la función de señal y el valor del semáforo se vuelva positivo.

Limitaciones:

1. Una de las mayores limitaciones del semáforo es la inversión de prioridad.
2. Interbloqueo, suponga que un proceso está tratando de despertar a otro proceso que no está en estado de suspensión. Por lo tanto, un interbloqueo puede bloquearse indefinidamente.
3. El sistema operativo tiene que realizar un seguimiento de todas las llamadas a esperar y señalar el semáforo.

Problema en esta implementación del semáforo:
el principal problema con los semáforos es que requieren una espera ocupada. Si un proceso está en la sección crítica, otros procesos que intentan ingresar a la sección crítica estarán esperando hasta que la sección crítica no esté ocupada por ningún proceso.
Cada vez que un proceso espera, verifica continuamente el valor del semáforo (mire esta línea mientras (s == 0); en la operación P) y desperdicia el ciclo de la CPU.

También existe la posibilidad de «bloqueo de giro», ya que los procesos continúan girando mientras esperan el bloqueo.

 Para evitar esto, se proporciona otra implementación a continuación.

Implementación del semáforo de conteo:
 

struct Semaphore {
    int value;
 
    // q contains all Process Control Blocks(PCBs)
    // corresponding to processes got blocked
    // while performing down operation.
    Queue<process> q;
 
} P(Semaphore s)
{
    s.value = s.value - 1;
    if (s.value < 0) {
 
        // add process to queue
        // here p is a process which is currently executing
        q.push(p);
        block();
    }
    else
        return;
}
 
V(Semaphore s)
{
    s.value = s.value + 1;
    if (s.value >= 0) {
 
        // remove process p from queue
        Process p=q.pop();
        wakeup(p);
    }
    else
        return;
}

En esta implementación, cada vez que el proceso espera, se agrega a una cola de espera de procesos asociados con ese semáforo. Esto se hace a través del bloqueo de llamadas al sistema() en ese proceso. Cuando se completa un proceso, llama a la función de señal y se reanuda un proceso en la cola. Utiliza la llamada al sistema wakeup().