multithreading - threads - ¿Qué es un semáforo?

python thread wait example

Question

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 lo usas?

Answer 1

@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 tiene acceso a ese recurso. Esto evita que dos subprocesos 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 accedan a un recurso.

Answer 2

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. Así que piense en el semáforo como un conjunto de llaves disponibles para los baños (los recursos del sistema) a los que pueden solicitar acceso los diferentes procesos (asistentes del baño).

Ahora imagina dos procesos intentando ir al baño al mismo tiempo. Esa no es una buena situación y se usan semáforos para prevenir esto. Desafortunadamente, el semáforo es un mecanismo voluntario y los procesos (los que nos visitan en el baño) pueden ignorarlo (es decir, incluso si hay llaves, alguien puede patear la puerta).

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

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

Answer 3

Considere, un taxi que puede acomodar a un total de 3 ( atrás ) +2 ( frente ) personas, incluido el conductor. Entonces, un semaphore permite solo 5 personas dentro de un automóvil a la vez. Y un mutex permite solo 1 persona en un solo asiento del auto.

Por lo tanto, Mutex debe permitir el acceso exclusivo a un recurso ( como un subproceso del sistema operativo ), mientras que un Semaphore es permitir el acceso de n cantidad de recursos a la vez.

Answer 4

El artículo Mutexes y semáforos desmitificados por Michael Barr es una breve introducción a lo que hace que los mutex 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 se deben usar las exclusiones mutuas para proteger los recursos compartidos, mientras que los semáforos se deben usar para la señalización. Por lo general, no debe usar semáforos para proteger los recursos compartidos, ni mutex para la señalización. Hay problemas, por ejemplo, con la analogía de bouncer en cuanto al uso de semáforos para proteger los recursos compartidos. Puede usarlos de esa manera, pero puede causar problemas para diagnosticar errores.

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

La respuesta más común (pero sin embargo incorrecta) a la pregunta planteada en la parte superior es que los mutex y los semáforos son muy similares, con la única diferencia significativa de que los semáforos pueden contar más alto que uno. Casi todos los ingenieros parecen entender correctamente 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 de código. Pero cuando se les pide que amplíen la forma de usar un "semáforo de recuento", 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 que las llaves del baño protegen los recursos compartidos: el baño. Si una tienda tiene un solo baño, entonces una sola llave será suficiente para proteger ese recurso y evitar que varias personas lo utilicen simultáneamente.

Si hay varios baños, uno podría tener la tentación de teclearlos por igual y hacer varias llaves; esto es similar a un semáforo que se usa de forma incorrecta. Una vez que tenga una llave, no sabrá realmente cuál es el baño 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 esta es la forma en que muchas personas lo piensan y lo utilizan. La analogía de bouncer es claramente diferente: no hay varios del mismo tipo de recurso, sino que 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 donde la analogía realmente se sostiene, es más frecuente que haya varios del mismo tipo, pero aún así recursos individuales, como los baños, que no se pueden usar de esta manera.

...

El uso correcto de un semáforo es para la señalización de una tarea a otra. Un mutex está destinado a ser tomado y liberado, siempre en ese orden, por cada tarea que utiliza el recurso compartido que protege. Por el contrario, las tareas que usan semáforos señalan o esperan, no ambos. Por ejemplo, la Tarea 1 puede contener código para publicar (es decir, señal o incremento) de un semáforo en particular cuando se presiona el botón "encendido" y la Tarea 2, que activa la pantalla, se inclina 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 una observación importante de que las interferencias mutuas interfieren con los sistemas operativos en tiempo real de manera incorrecta, lo que provoca una inversión de prioridad donde una tarea menos importante puede ejecutarse antes que una tarea más importante debido al intercambio de recursos. En resumen, esto sucede cuando una tarea de prioridad más baja usa un mutex para tomar un recurso, A, luego intenta tomar B, pero está en pausa porque B no está disponible. Mientras espera, 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 a B. Hay muchas maneras de resolver esto, pero a menudo se corrige alterando el mutex y el administrador de tareas. El mutex es mucho más complejo en estos casos que un semáforo binario, y el uso de un semáforo en tal caso causará inversiones de prioridad porque el administrador de tareas no está al tanto de la inversión de prioridad y no puede actuar para corregirlo.

...

La causa de la confusión moderna generalizada entre mutex y semáforos es histórica, ya que se remonta a la invención de 1974 del Semáforo (capital "S", en este artículo) por Djikstra. Antes de esa fecha, ninguno de los mecanismos de sincronización y señalización de tareas seguros para interrupciones conocidos por los científicos informáticos era escalable de manera eficiente para ser utilizado por más de dos tareas. El revolucionario semáforo de Dijkstra, seguro y escalable, 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 prioridad (por ejemplo, VRTX, ca. 1980), la publicación de documentos académicos que establecen RMA y los problemas causados ​​por la inversión de prioridad, y un documento sobre prioridad los protocolos de herencia en 1990, 3 se hizo evidente que las mutexes deben ser más que solo semáforos con un contador binario.

Mutex: compartir recursos

Semáforo: señalización

No use uno para el otro sin tener en cuenta los efectos secundarios.

Answer 5

El semáforo también se puede usar como ... semáforo. Por ejemplo, si tiene varios procesos de encolado de datos en una cola, y solo una tarea consume datos de la cola. Si no desea que su tarea consumidora realice un sondeo constante de la cola en busca de datos disponibles, puede usar el semáforo.

Aquí el semáforo no se utiliza como un mecanismo de exclusión, sino como un mecanismo de señalización. La tarea consumidora está esperando en el semáforo. La tarea productora se está publicando en el semáforo.

De esta manera, la tarea consumidora se ejecuta cuando y solo cuando hay datos para ser en cola

Answer 6

Esta es una pregunta antigua, 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 de ar / w lock 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 que las escrituras adquieran permisos en múltiples solicitudes, en tal caso, necesitan un mutex explícito entre ellos.

read más:

Answer 7

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 generalmente un tipo de mecanismo de bloqueo) nos ayudan a lograr la sincronización y la exclusión mutua.

Un semáforo es un constructo 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 contadores.

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

Lo que es importante comprender es que el contador de semáforos realiza un seguimiento del número de tareas que no tienen que bloquear, es decir, 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 se pueden usar los semáforos binarios para resolver la sincronización y la exclusión mutua, esencialmente son 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 hilo A viene primero se ejecuta: llega a sem.P () y espera, ya que el contador es 0 (cerrado). El subproceso B aparece, finaliza B1 y luego libera el subproceso A, que luego completa B2. Así 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 ingresar a la sección crítica al mismo tiempo. Entonces, cada hilo está utilizando el mismo semáforo para proporcionar la exclusión mutua para sus dos secciones críticas. Ahora, ¿es posible tener mayor concurrencia? Depende de las secciones críticas. (Piense en cómo podría uno usar semáforos para lograr la exclusión mutua ... pista pista: ¿necesariamente solo necesito usar un semáforo?)

Contando el semáforo: un semáforo con más de un valor. Echemos un vistazo a lo que esto implica: ¿un bloqueo con más de un valor? Tan abierto, cerrado, y ... hmm. ¿De qué sirve un bloqueo de varias etapas en la exclusión o sincronización mutua?

Tomemos el más fácil de los dos:

Sincronización utilizando un semáforo de recuento: 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 tu semáforo comienza cerrado, te aseguras de que t1 y t2 bloqueen, se agreguen a la lista del semáforo. Luego viene todo t3 importante, termina su negocio y libera t1 y t2. ¿En qué orden son liberados? Depende de la implementación de la lista del semáforo. Podría ser FIFO, podría basarse en alguna prioridad particular, etc. (Nota: piense cómo organizaría sus P y V; s si quisiera que t1 y t2 se ejecutaran en algún orden en 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 mediante el uso de semáforos de conteo: me gustaría que construyas tu propio pseudocódigo para esto (¡te hace entender mejor las cosas!), Pero el concepto fundamental es este: un semáforo de conteo de contador = N permite que N tareas ingresen a la sección crítica libremente . Lo que esto significa es que tiene N tareas (o subprocesos, si lo desea) ingrese a la sección crítica, pero la N + 1a tarea se bloquea (entra en nuestra lista de tareas bloqueadas favoritas), y solo se deja pasar cuando alguien V es el semáforo al menos una vez. Así que 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, ¡sin bloquear a nadie!

Ahora, por qué necesitas una cosa tan estúpida? ¿No es el punto de exclusión mutua no permitir que más de un individuo acceda a un recurso? (Sugerencia Sugerencia ... No siempre tienes un solo disco en tu computadora, ¿verdad ...?)

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

Answer 8

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

ExecutorService executor = Executors.newFixedThreadPool(6);

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

Código de ejemplo de otro article

Answer 9

Mutex: acceso exclusivo de miembros 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 llamantes simultáneos. Por ejemplo, puedo envolver mis llamadas de 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 una de las tres ranuras. Hacen cosas como hacer una aceleración ingenua muy, muy fácil.

Answer 10

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, V , añade 1 a lo natural. La otra operación, P , disminuye el número natural en 1. Ambas actividades son atómicas (es decir, ninguna otra operación puede ejecutarse al mismo tiempo que una V o una P ).

Debido a que el número natural 0 no se puede disminuir, llamar a P en un semáforo que contenga un 0 bloqueará la ejecución del proceso de llamada (/ hilo) hasta un momento en que el número ya no sea 0 y P pueda ejecutarse con éxito (y de manera atómica) .

Como se mencionó 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.

Answer 11

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 tiene acceso a ese recurso. Esto evita que dos subprocesos accedan simultáneamente a un recurso, lo que puede causar problemas.

Answer 12

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 comprueba el semáforo para determinar el estado de los recursos y luego decide cómo proceder.

Answer 13

Piense en los semáforos como en un club nocturno. Hay un número dedicado de personas que se permiten en el club a la vez. Si el club está lleno, a nadie se le permite entrar, pero tan pronto como una persona abandona, 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);
        }
    }
}