¿Qué es un semáforo?

Un semáforo es un concepto de programación que se usa con frecuencia para resolver problemas de subprocesos múltiples. Mi pregunta a la comunidad:

¿Qué es un semáforo y cómo se usa?

Piense en los semáforos como gorilas en un club nocturno. Hay un número dedicado de personas que están permitidas en el club a la vez. Si el club está lleno, nadie puede ingresar, pero tan pronto como una persona se vaya, otra persona puede ingresar.

Es simplemente una forma de limitar el número de consumidores para un recurso específico. Por ejemplo, para limitar el número de llamadas simultáneas a una base de datos en una aplicación.

Aquí hay un ejemplo muy pedagógico en C # :-)

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace TheNightclub
{
    public class Program
    {
        public static Semaphore Bouncer { get; set; }

        public static void Main(string[] args)
        {
            // Create the semaphore with 3 slots, where 3 are available.
            Bouncer = new Semaphore(3, 3);

            // Open the nightclub.
            OpenNightclub();
        }

        public static void OpenNightclub()
        {
            for (int i = 1; i <= 50; i++)
            {
                // Let each guest enter on an own thread.
                Thread thread = new Thread(new ParameterizedThreadStart(Guest));
                thread.Start(i);
            }
        }

        public static void Guest(object args)
        {
            // Wait to enter the nightclub (a semaphore to be released).
            Console.WriteLine("Guest {0} is waiting to entering nightclub.", args);
            Bouncer.WaitOne();          

            // Do some dancing.
            Console.WriteLine("Guest {0} is doing some dancing.", args);
            Thread.Sleep(500);

            // Let one guest out (release one semaphore).
            Console.WriteLine("Guest {0} is leaving the nightclub.", args);
            Bouncer.Release(1);
        }
    }
}

El artículo Mutexes y semáforos desmitificados por Michael Barr es una gran introducción breve sobre lo que hace que los mutexes y semáforos sean diferentes, y cuándo deben y no deben usarse. He extraído varios párrafos clave aquí.

El punto clave es que los mutexes deben usarse para proteger los recursos compartidos, mientras que los semáforos deben usarse para la señalización. Por lo general, no debe usar semáforos para proteger los recursos compartidos, ni mutexes para la señalización. Hay problemas, por ejemplo, con la analogía de los rebotes en términos de uso de semáforos para proteger los recursos compartidos; puede usarlos de esa manera, pero puede causar problemas para diagnosticar errores.

Si bien los mutexes y los semáforos tienen algunas similitudes en su implementación, siempre deben usarse de manera diferente.

La respuesta más común (pero no obstante incorrecta) a la pregunta planteada en la parte superior es que los mutexes y los semáforos son muy similares, con la única diferencia significativa de que los semáforos pueden contar más de uno. Casi todos los ingenieros parecen entender adecuadamente que un mutex es un indicador binario utilizado para proteger un recurso compartido al garantizar la exclusión mutua dentro de las secciones críticas del código. Pero cuando se les pide que amplíen la forma de utilizar un "semáforo de conteo", la mayoría de los ingenieros, que varían solo en su grado de confianza, expresan algo de la opinión del libro de texto de que se utilizan para proteger varios recursos equivalentes.

...

En este punto, se hace una analogía interesante utilizando la idea de las llaves del baño como protección de los recursos compartidos: el baño. Si una tienda tiene un solo baño, una sola llave será suficiente para proteger ese recurso y evitar que varias personas lo usen simultáneamente.

Si hay varios baños, uno podría tener la tentación de usarlos y hacer varias llaves, esto es similar a un semáforo mal utilizado. Una vez que tenga una llave, no sabrá qué baño está disponible, y si sigue este camino, probablemente terminará usando mutexes para proporcionar esa información y asegurarse de no tomar un baño que ya esté ocupado .

Un semáforo es la herramienta incorrecta para proteger varios de los mismos recursos, pero así es como muchas personas piensan en él y lo usan. La analogía del gorila es claramente diferente: no hay varios del mismo tipo de recurso, en cambio, hay un recurso que puede aceptar múltiples usuarios simultáneos. Supongo que se puede usar un semáforo en tales situaciones, pero rara vez hay situaciones del mundo real en las que la analogía realmente se cumple: es más frecuente que haya varios del mismo tipo, pero aún recursos individuales, como los baños, que no se pueden usar de esta manera.

...

El uso correcto de un semáforo es para señalizar de una tarea a otra. Un mutex está destinado a ser tomado y liberado, siempre en ese orden, por cada tarea que use el recurso compartido que protege. Por el contrario, las tareas que usan semáforos señalan o esperan, no ambas. Por ejemplo, la Tarea 1 puede contener código para publicar (es decir, señal o incremento) un semáforo particular cuando se presiona el botón de "encendido" y la Tarea 2, que activa la pantalla, queda en ese mismo semáforo. En este escenario, una tarea es el productor de la señal de evento; El otro el consumidor.

...

Aquí se hace un punto importante de que los mutexes interfieren con los sistemas operativos en tiempo real de manera incorrecta, causando una inversión de prioridad donde una tarea menos importante puede ejecutarse antes de una tarea más importante debido al uso compartido de recursos. En resumen, esto sucede cuando una tarea de menor prioridad usa un mutex para tomar un recurso, A, luego intenta tomar B, pero se detiene porque B no está disponible. Mientras está esperando, aparece una tarea de mayor prioridad y necesita A, pero ya está atada, y por un proceso que ni siquiera se está ejecutando porque está esperando B. Hay muchas formas de resolver esto, pero la mayoría de las veces se soluciona alterando el mutex y el administrador de tareas. El mutex es mucho más complejo en estos casos que un semáforo binario,

...

La causa de la confusión moderna generalizada entre mutexes y semáforos es histórica, ya que se remonta a la invención de 1974 del Semáforo ("S" mayúscula, en este artículo) por Djikstra. Antes de esa fecha, ninguno de los mecanismos de sincronización y señalización de tareas a prueba de interrupciones conocidos por los informáticos era escalable de manera eficiente para su uso en más de dos tareas. El revolucionario, seguro y escalable Semaphore de Dijkstra se aplicó tanto en la protección de la sección crítica como en la señalización. Y así comenzó la confusión.

Sin embargo, más tarde se hizo evidente para los desarrolladores de sistemas operativos, después de la aparición del RTOS preventivo basado en prioridades (p. Ej., VRTX, ca. 1980), la publicación de trabajos académicos que establecen RMA y los problemas causados ​​por la inversión de prioridad, y un documento sobre prioridad protocolos de herencia en 1990 3, se hizo evidente que los mutexes deben ser más que simples semáforos con un contador binario.

Mutex: intercambio de recursos

Semáforo: señalización

No use uno para el otro sin una cuidadosa consideración de los efectos secundarios.

Mutex: acceso de miembro exclusivo a un recurso

Semáforo: acceso de n miembros a un recurso

Es decir, se puede usar un mutex para sincronizar el acceso a un contador, archivo, base de datos, etc.

Un sempahore puede hacer lo mismo pero admite un número fijo de llamadas simultáneas. Por ejemplo, puedo ajustar las llamadas de mi base de datos en un semáforo (3) para que mi aplicación multiproceso llegue a la base de datos con un máximo de 3 conexiones simultáneas. Todos los intentos se bloquearán hasta que se abra uno de los tres espacios. Hacen cosas como hacer estrangulamiento ingenuo realmente, muy fácil.

Considere un taxi que puede acomodar a un total de 3 personas ( traseras ) +2 ( delanteras ), incluido el conductor. Entonces, a semaphorepermite solo 5 personas dentro de un automóvil a la vez. Y a mutexsolo permite 1 persona en un solo asiento del automóvil.

Por lo tanto, Mutexes permitir el acceso exclusivo a un recurso ( como un subproceso del sistema operativo ) mientras que Semaphorees permitir el acceso a n número de recursos a la vez.

@Craig:

Un semáforo es una forma de bloquear un recurso para garantizar que mientras se ejecuta un fragmento de código, solo este fragmento de código tenga acceso a ese recurso. Esto evita que dos hilos accedan simultáneamente a un recurso, lo que puede causar problemas.

Esto no está restringido a un solo hilo. Se puede configurar un semáforo para permitir que un número fijo de subprocesos acceda a un recurso.

El semáforo también se puede usar como ... semáforo. Por ejemplo, si tiene múltiples procesos en cola de datos a una cola, y solo una tarea consume datos de la cola. Si no desea que su tarea de consumo sondee constantemente la cola para obtener datos disponibles, puede usar el semáforo.

Aquí el semáforo no se usa como mecanismo de exclusión, sino como mecanismo de señalización. La tarea de consumo está esperando en el semáforo. La tarea de producción está publicando en el semáforo.

De esta forma, la tarea de consumo se ejecuta cuando y solo cuando hay datos que se deben retirar.

Hay dos conceptos esenciales para construir programas concurrentes: sincronización y exclusión mutua. Veremos cómo estos dos tipos de bloqueos (los semáforos son más generalmente un tipo de mecanismo de bloqueo) nos ayudan a lograr la sincronización y la exclusión mutua.

Un semáforo es una construcción de programación que nos ayuda a lograr la concurrencia, implementando tanto la sincronización como la exclusión mutua. Los semáforos son de dos tipos, binarios y contando.

Un semáforo tiene dos partes: un contador y una lista de tareas que esperan para acceder a un recurso en particular. Un semáforo realiza dos operaciones: esperar (P) [esto es como adquirir un bloqueo] y soltar (V) [similar a liberar un bloqueo]: estas son las únicas dos operaciones que uno puede realizar en un semáforo. En un semáforo binario, el contador lógicamente va entre 0 y 1. Puede pensar que es similar a un candado con dos valores: abierto / cerrado. Un semáforo cuenta tiene múltiples valores para contar.

Lo importante es comprender que el contador de semáforos realiza un seguimiento de la cantidad de tareas que no es necesario bloquear, es decir, que pueden avanzar. Las tareas se bloquean y se agregan a la lista del semáforo solo cuando el contador es cero. Por lo tanto, una tarea se agrega a la lista en la rutina P () si no puede progresar y se "libera" usando la rutina V ().

Ahora, es bastante obvio ver cómo los semáforos binarios se pueden usar para resolver la sincronización y la exclusión mutua: son esencialmente bloqueos.

ex. Sincronización:

thread A{
semaphore &s; //locks/semaphores are passed by reference! think about why this is so.
A(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
;// some block of code B2
...
}

//thread B{
semaphore &s;
B(semaphore &s): s(s){} //constructor
foo(){
...
...
// some block of code B1
s.V();
..
}

main(){
semaphore s(0); // we start the semaphore at 0 (closed)
A a(s);
B b(s);
}

En el ejemplo anterior, B2 solo puede ejecutarse después de que B1 haya finalizado la ejecución. Digamos que el subproceso A se ejecuta primero, llega a sem.P () y espera, ya que el contador es 0 (cerrado). El subproceso B aparece, termina B1 y luego libera el subproceso A, que luego completa B2. Entonces logramos la sincronización.

Ahora veamos la exclusión mutua con un semáforo binario:

thread mutual_ex{
semaphore &s;
mutual_ex(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
//critical section
s.V();
...
...
s.P();
//critical section
s.V();
...

}

main(){
semaphore s(1);
mutual_ex m1(s);
mutual_ex m2(s);
}

La exclusión mutua también es bastante simple: m1 y m2 no pueden entrar en la sección crítica al mismo tiempo. Por lo tanto, cada subproceso está utilizando el mismo semáforo para proporcionar exclusión mutua para sus dos secciones críticas. Ahora, ¿es posible tener una mayor concurrencia? Depende de las secciones críticas. (Piense de qué otra manera se podrían usar los semáforos para lograr la exclusión mutua. Sugerencia: ¿necesariamente solo necesito usar un semáforo?)

Contando semáforo: un semáforo con más de un valor. Veamos qué implica esto: ¿un candado con más de un valor? Tan abierto, cerrado y ... hmm. ¿De qué sirve un bloqueo de etapas múltiples en exclusión mutua o sincronización?

Tomemos la más fácil de las dos:

Sincronización usando un semáforo de conteo: Digamos que tiene 3 tareas: # 1 y 2 que desea ejecutar después de 3. ¿Cómo diseñaría su sincronización?

thread t1{
...
s.P();
//block of code B1

thread t2{
...
s.P();
//block of code B2

thread t3{
...
//block of code B3
s.V();
s.V();
}

Entonces, si su semáforo comienza cerrado, se asegura de que t1 y t2 bloqueen, se agreguen a la lista de semáforos. Luego viene todo t3 importante, termina su negocio y libera t1 y t2. ¿En qué orden se liberan? Depende de la implementación de la lista de semáforos. Podría ser FIFO, podría basarse alguna prioridad particular, etc. (Nota: piense en cómo organizaría sus P y V; s si desea que t1 y t2 se ejecuten en un orden particular, y si no estaba al tanto de la implementación del semáforo)

(Averigüe: ¿Qué sucede si el número de V es mayor que el número de P?)

Exclusión mutua utilizando semáforos de conteo: me gustaría que construyeras tu propio pseudocódigo para esto (¡te hace entender mejor las cosas!), Pero el concepto fundamental es el siguiente: un semáforo de conteo de counter = N permite que N tareas entren libremente en la sección crítica. . Lo que esto significa es que tiene N tareas (o hilos, si lo desea) ingrese a la sección crítica, pero la tarea N + 1 se bloquea (va a nuestra lista de tareas bloqueadas favoritas), y solo se deja pasar cuando alguien V está en el semáforo al menos una vez. Entonces, el contador de semáforos, en lugar de oscilar entre 0 y 1, ahora va entre 0 y N, permitiendo que N tareas entren y salgan libremente, ¡bloqueando a nadie!

Dios mío, ¿por qué necesitarías algo tan estúpido? ¿No es el punto de exclusión mutua no permitir que más de un hombre acceda a un recurso? (Sugerencia Sugerencia ... No siempre tiene una sola unidad en su computadora, ¿verdad ...?)

Para pensar : ¿Se logra la exclusión mutua teniendo un semáforo contando solo? ¿Qué sucede si tiene 10 instancias de un recurso y entran 10 hilos (a través del semáforo de conteo) e intenta utilizar la primera instancia?

Un semáforo es un objeto que contiene un número natural (es decir, un número entero mayor o igual a cero) en el que se definen dos operaciones de modificación. Una operación, Vagrega 1 a lo natural. La otra operación, Pdisminuye el número natural en 1. Ambas actividades son atómicas (es decir, ninguna otra operación puede ejecutarse al mismo tiempo que a Vo a P).

Debido a que el número natural 0 no se puede disminuir, llamar Pa un semáforo que contiene un 0 bloqueará la ejecución del proceso de llamada (/ thread) hasta algún momento en que el número ya no sea 0 y Ppueda ejecutarse con éxito (y atómicamente).

Como se menciona en otras respuestas, los semáforos se pueden usar para restringir el acceso a un determinado recurso a un número máximo (pero variable) de procesos.

He creado la visualización que debería ayudar a comprender la idea. Semaphore controla el acceso a un recurso común en un entorno de subprocesos múltiples.

ExecutorService executor = Executors.newFixedThreadPool(7);

Semaphore semaphore = new Semaphore(4);

Runnable longRunningTask = () -> {
    boolean permit = false;
    try {
        permit = semaphore.tryAcquire(1, TimeUnit.SECONDS);
        if (permit) {
            System.out.println("Semaphore acquired");
            Thread.sleep(5);
        } else {
            System.out.println("Could not acquire semaphore");
        }
    } catch (InterruptedException e) {
        throw new IllegalStateException(e);
    } finally {
        if (permit) {
            semaphore.release();
        }
    }
};

// execute tasks
for (int j = 0; j < 10; j++) {
    executor.submit(longRunningTask);
}
executor.shutdown();

Salida

Semaphore acquired
Semaphore acquired
Semaphore acquired
Semaphore acquired
Could not acquire semaphore
Could not acquire semaphore
Could not acquire semaphore

Código de muestra del artículo

Una bandera de hardware o software. En los sistemas multitarea, un semáforo es una variable con un valor que indica el estado de un recurso común. Un proceso que necesita el recurso verifica el semáforo para determinar el estado de los recursos y luego decide cómo proceder.

Los semáforos actúan como limitadores de hilo.

Ejemplo: si tiene un grupo de 100 subprocesos y desea realizar alguna operación de base de datos. Si 100 subprocesos acceden a la base de datos en un momento dado, entonces puede haber un problema de bloqueo en la base de datos para que podamos usar el semáforo que permite solo un subproceso limitado a la vez. A continuación, el ejemplo permite solo un subproceso a la vez. Cuando un subproceso llama al acquire()método, obtendrá el acceso y después de llamar al release()método, liberará el acceso para que el siguiente subproceso obtenga el acceso.

    package practice;
    import java.util.concurrent.Semaphore;

    public class SemaphoreExample {
        public static void main(String[] args) {
            Semaphore s = new Semaphore(1);
            semaphoreTask s1 = new semaphoreTask(s);
            semaphoreTask s2 = new semaphoreTask(s);
            semaphoreTask s3 = new semaphoreTask(s);
            semaphoreTask s4 = new semaphoreTask(s);
            semaphoreTask s5 = new semaphoreTask(s);
            s1.start();
            s2.start();
            s3.start();
            s4.start();
            s5.start();
        }
    }

    class semaphoreTask extends Thread {
        Semaphore s;
        public semaphoreTask(Semaphore s) {
            this.s = s;
        }
        @Override
        public void run() {
            try {
                s.acquire();
                Thread.sleep(1000);
                System.out.println(Thread.currentThread().getName()+" Going to perform some operation");
                s.release();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        } 
    }

Así que imagina que todos están tratando de ir al baño y solo hay una cierta cantidad de llaves para el baño. Ahora, si no quedan suficientes llaves, esa persona necesita esperar. Por lo tanto, piense en el semáforo como la representación de ese conjunto de llaves disponibles para los baños (los recursos del sistema) a los que los diferentes procesos (asistentes al baño) pueden solicitar acceso.

Ahora imagine dos procesos tratando de ir al baño al mismo tiempo. Esa no es una buena situación y se utilizan semáforos para evitar esto. Desafortunadamente, el semáforo es un mecanismo voluntario y los procesos (nuestros asistentes al baño) pueden ignorarlo (es decir, incluso si hay llaves, alguien puede simplemente abrir la puerta).

También hay diferencias entre binarios / mutex y contando semáforos.

Consulte las notas de la conferencia en http://www.cs.columbia.edu/~jae/4118/lect/L05-ipc.html .

Esta es una vieja pregunta, pero uno de los usos más interesantes del semáforo es un bloqueo de lectura / escritura y no se ha mencionado explícitamente.

Los bloqueos r / w funcionan de manera simple: consumen un permiso para un lector y todos los permisos para escritores. De hecho, una implementación trivial del bloqueo ar / w pero requiere una modificación de metadatos en la lectura (en realidad dos veces) que puede convertirse en un cuello de botella, aún significativamente mejor que un mutex o bloqueo.

Otro inconveniente es que los escritores también pueden iniciarse con bastante facilidad, a menos que el semáforo sea justo o las escrituras adquieran permisos en múltiples solicitudes, en tal caso necesitan un mutex explícito entre ellos.

Leer más :

Un semáforo es una forma de bloquear un recurso para garantizar que mientras se ejecuta un fragmento de código, solo este fragmento de código tenga acceso a ese recurso. Esto evita que dos hilos accedan simultáneamente a un recurso, lo que puede causar problemas.