¿Qué es un semáforo?

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

¿Qué es un semáforo y cómo lo usas?

Piensa en los semáforos como gorilas en un club nocturno. Hay una cantidad específica de personas 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 podría ingresar.

Es simplemente una manera de limitar la cantidad 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 Semaphores Desmitificado por Michael Barr es una gran introducción corta a lo que hace mutexes y semáforos diferentes, y cuando deberían y no deberían ser utilizados. He extraído varios párrafos clave aquí.

El punto clave es que los mutex deberían usarse para proteger los recursos compartidos, mientras que los semáforos deberían usarse para la señalización. En general, no debe usar semáforos para proteger los recursos compartidos, ni exclusión de señalización. Hay problemas, por ejemplo, con la analogía del gorila en términos del uso de semáforos para proteger los recursos compartidos; puede usarlos de esa manera, pero puede causar errores difíciles de diagnosticar.

Si bien los mutexes y 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 mutexes y semáforos son muy similares, con la única diferencia significativa es que los semáforos pueden contar más de uno. Casi todos los ingenieros parecen entender correctamente que un mutex es una bandera binaria que se utiliza para proteger un recurso compartido al garantizar la exclusión mutua dentro de secciones críticas del código. Pero cuando se le pide que amplíe el uso de un “semáforo de conteo”, la mayoría de los ingenieros, que varían solo en su grado de confianza, expresan cierto sabor de la opinión de los libros de texto que se utilizan para proteger varios recursos equivalentes.

En este punto se hace una analogía interesante usando 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 marcarlos por igual y hacer varias llaves; esto es similar a un semáforo mal utilizado. Una vez que tienes una llave, no sabes realmente qué baño está disponible, y si sigues este camino probablemente termines utilizando mutexes para proporcionar esa información y asegúrate de no tomar un baño que ya está ocupado. .

Un semáforo es la herramienta incorrecta para proteger varios de los recursos esencialmente iguales, pero esta es la cantidad de gente que piensa en él y lo usa. La analogía del gorila es claramente diferente: no hay varios recursos del mismo tipo, sino que hay un recurso que puede aceptar múltiples usuarios simultáneos. Supongo que un semáforo se puede usar en tales situaciones, pero rara vez hay situaciones del mundo real donde la analogía realmente se mantenga, es más frecuente que haya varias 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 la señalización de una tarea a otra. Se pretende que un mutex se tome y se libere, 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ñalizar o incrementar) un semáforo en particular cuando se presiona el botón de “encendido” y la Tarea 2, que despierta la pantalla, funciona 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 los mutex interfieren con los sistemas operativos en tiempo real de una mala manera, causando una inversión de prioridad donde una tarea menos importante puede ser ejecutada antes que una tarea más importante debido al intercambio 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 pausa porque B no está disponible. Mientras está esperando, aparece una tarea de mayor prioridad que necesita A, pero ya está bloqueada, y por un proceso que ni siquiera se está ejecutando porque está esperando B. Hay muchas maneras de resolver esto, pero con frecuencia 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, y usar un semáforo en tal caso causará inversiones de prioridad porque el administrador de tareas no tiene conocimiento de la inversión de prioridad y no puede actuar para corregirla.

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 (capital “S”, en este artículo) por Djikstra. Antes de esa fecha, ninguno de los mecanismos de señalización y sincronización de tareas seguros para interrupciones conocidos por los científicos informáticos era eficientemente escalable para ser utilizado por más de dos tareas. El semáforo revolucionario, seguro y escalable de Dijkstra se aplicó tanto a la protección de secciones críticas como a la señalización. Y así comenzó la confusión.

Sin embargo, más tarde se hizo obvio para los desarrolladores de sistemas operativos, después de la aparición del RTOS preventivo basado en prioridades (por ejemplo, VRTX, alrededor de 1980), publicación de documentos académicos que establecen RMA y los problemas causados ​​por 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 solo 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 miembros exclusivos 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 mis llamadas a la 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 bashs se bloquearán hasta que se abra una de las tres ranuras. Hacen cosas como hacer estrangulamiento ingenuo realmente, muy fácil.

@ 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 solo un hilo. Se puede configurar un semáforo para permitir que un número fijo de subprocesos acceda a un recurso.

Semaphore también se puede usar como un … semáforo. Por ejemplo, si tiene varios procesos que colocan datos en una cola y solo una tarea consume datos de la cola. Si no desea que su tarea de consumo sondee constantemente la cola de datos disponibles, puede usar semáforo.

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

De esta forma, la tarea de consumo se ejecuta cuando y solo cuando hay datos para ser quitados de la cola

Hay dos conceptos esenciales para crear progtwigs simultáneos: sincronización y exclusión mutua. Veremos cómo estos dos tipos de lockings (los semáforos son más generalmente un tipo de mecanismo de locking) nos ayudan a lograr la sincronización y la exclusión mutua.

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

Un semáforo tiene dos partes: un contador y una lista de tareas esperando para acceder a un recurso en particular. Un semáforo realiza dos operaciones: esperar (P) [esto es como adquirir un locking] y liberar (V) [similar a liberar un locking]: estas son las dos únicas operaciones que se pueden 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 locking con dos valores: abierto / cerrado. Un semáforo de conteo tiene múltiples valores para contar.

Lo que es importante entender es que el contador de semáforos realiza un seguimiento del número de tareas que no tienen que bloquear, es decir, pueden progresar. 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 avanzar, y “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 lockings.

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(){ ... sP(); ;// some block of code B2 ... } //thread B{ semaphore &s; B(semaphore &s): s(s){} //constructor foo(){ ... ... // some block of code B1 sV(); .. } 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 terminado 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 hilo B aparece, termina B1 y luego libera el hilo 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(){ ... sP(); //critical section sV(); ... ... sP(); //critical section sV(); ... } 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 subproceso usa 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 en qué otra cosa podría usar semáforos para lograr la exclusión mutua … sugerencia: ¿Necesito necesariamente usar un solo semáforo?)

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

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

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

 thread t1{ ... sP(); //block of code B1 thread t2{ ... sP(); //block of code B2 thread t3{ ... //block of code B3 sV(); sV(); } 

Entonces, si su semáforo comienza cerrándose, usted se asegura de que los bloques t1 y t2 se agreguen a la lista del semáforo. Luego viene todo t3 importante, finaliza su negocio y libera t1 y t2. ¿En qué orden están 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 si desea que se ejecuten t1 y t2 en algún orden particular, y si no estaba al tanto de la implementación del semáforo)

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

Exclusión mutua Uso de semáforos de conteo: me gustaría que construyes tu propio pseudocódigo para esto (¡te hace entender mejor las cosas!), Pero el concepto fundamental es el siguiente: un semáforo de contador = N permite que N tareas ingresen libremente en la sección crítica . Lo que esto significa es que tienes N tareas (o subprocesos, si quieres) ingresas a la sección crítica, pero la N + 1ª tarea se bloquea (va en nuestra lista de tareas bloqueadas favoritas) y solo se deja pasar cuando alguien V es 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!

Ahora Dios, ¿por qué necesitarías una cosa tan estúpida? ¿No es el objective de la exclusión mutua no permitir que más de un chico acceda a un recurso? (Sugerencia Sugerencia … No siempre tiene una unidad en su computadora, ¿verdad …?)

Para pensar : ¿se logra la exclusión mutua teniendo un semáforo de conteo solo? ¿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?

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

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

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 , agrega 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 se puede ejecutar al mismo tiempo que una V o una P ).

Debido a que el número natural 0 no puede disminuirse, al llamar a P en un semáforo que contiene un 0 se bloqueará la ejecución del proceso de llamada (/ hilo) hasta que el número ya no sea 0 y P pueda ejecutarse (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.

Un indicador de hardware o software. En los sistemas de tareas múltiples, un semáforo es tan 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.

Entonces imagina que todos están tratando de ir al baño y que 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 representando el conjunto de claves disponibles para los baños (los recursos del sistema) a los que los diferentes procesos (asistentes del 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 los semáforos se usan para prevenir 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 todavía puede abrir la puerta de una patada).

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

Vea 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 locking de lectura / escritura y no se ha mencionado explícitamente.

Los lockings de 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 locking ar / w pero requiere modificación de metadatos en lectura (en realidad dos veces) que puede convertirse en un cuello de botella, aún significativamente mejor que un mutex o locking.

Otra desventaja es que los escritores pueden iniciarse fácilmente también, 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.

Lea más:

Creé la visualización que debería ayudar a entender la idea. Semáforo controla el acceso a un recurso común en un entorno de subprocesos múltiples. enter image description here

 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 muestra de su artículo

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.