Cerradura, mutex, semáforo ... ¿cuál es la diferencia?

He escuchado estas palabras relacionadas con la programación concurrente, pero ¿cuál es la diferencia entre ellas?

Un bloqueo permite que solo un hilo entre en la parte que está bloqueada y el bloqueo no se comparte con ningún otro proceso.

Un mutex es lo mismo que un bloqueo, pero puede ser de todo el sistema (compartido por múltiples procesos).

Un semáforo hace lo mismo que un mutex pero permite que ingrese x cantidad de subprocesos, esto puede usarse, por ejemplo, para limitar la cantidad de tareas intensivas de CPU, IO o RAM que se ejecutan al mismo tiempo.

Para una publicación más detallada sobre las diferencias entre mutex y semáforo, lea aquí .

También tiene bloqueos de lectura / escritura que permiten un número ilimitado de lectores o 1 escritor en un momento dado.

Hay muchas ideas falsas con respecto a estas palabras.

Esto es de una publicación anterior ( https://stackoverflow.com/a/24582076/3163691 ) que encaja excelente aquí:

1) Sección crítica = Objeto de usuario utilizado para permitir la ejecución de un solo hilo activo de muchos otros dentro de un proceso . Los otros hilos no seleccionados (@ adquiriendo este objeto) se ponen a dormir .

[Sin capacidad de interproceso, objeto muy primitivo].

2) Mutex Semaphore (también conocido como Mutex) = Objeto Kernel utilizado para permitir la ejecución de un solo hilo activo de muchos otros, entre diferentes procesos . Los otros hilos no seleccionados (@ adquiriendo este objeto) se ponen a dormir . Este objeto admite propiedad de subprocesos, notificación de terminación de subprocesos, recursión (múltiples llamadas 'adquirir' del mismo subproceso) y 'evitación de inversión de prioridad'.

[Capacidad entre procesos, muy segura de usar, una especie de objeto de sincronización de 'alto nivel'].

3) Contando el semáforo (también conocido como semáforo) = Objeto del núcleo utilizado para permitir la ejecución de un grupo de subprocesos activos de muchos otros. Los otros hilos no seleccionados (@ adquiriendo este objeto) se ponen a dormir .

[La capacidad entre procesos, sin embargo, no es muy segura de usar porque carece de los siguientes atributos 'mutex': ¿notificación de terminación de subproceso, recursión ?, ¿'evitación de inversión de prioridad' ?, etc.].

4) Y ahora, hablando de 'spinlocks', primero algunas definiciones:

Región crítica = Una región de memoria compartida por 2 o más procesos.

Lock = Una variable cuyo valor permite o niega la entrada a una 'región crítica'. (Podría implementarse como una simple 'bandera booleana').

Ocupado esperando = Prueba continua de una variable hasta que aparezca algún valor.

Finalmente:

Spin-lock (también conocido como Spinlock) = Un bloqueo que utiliza la espera ocupada . (La adquisición de la cerradura se realiza mediante xchg u operaciones atómicas similares ).

[Sin hilos en reposo, se utiliza principalmente en el nivel del núcleo solamente. Ineficaz para el código de nivel de usuario].

Como último comentario, no estoy seguro, pero puedo apostarles mucho dinero a que los primeros 3 objetos de sincronización anteriores (# 1, # 2 y # 3) hacen uso de esta bestia simple (# 4) como parte de su implementación.

¡Tenga un buen día!.

Referencias

-Conceptos en tiempo real para sistemas integrados por Qing Li con Caroline Yao (CMP Books).

-Modern Operating Systems (3rd) por Andrew Tanenbaum (Pearson Education International).

-Programación de aplicaciones para Microsoft Windows (4to) por Jeffrey Richter (Serie de programación de Microsoft).

Además, puede echar un vistazo a: https://stackoverflow.com/a/24586803/3163691

La mayoría de los problemas se pueden resolver usando (i) solo bloqueos, (ii) solo semáforos, ..., o (iii) una combinación de ambos. Como puede haber descubierto, son muy similares: ambos evitan las condiciones de carrera , ambos tienen acquire()/ release()operaciones, ambos hacen que cero o más hilos se bloqueen / sospechen ... Realmente, la diferencia crucial radica únicamente en cómo se bloquean y desbloquean .

• Un bloqueo (o mutex ) tiene dos estados (0 o 1). Se puede desbloquear o bloquear . A menudo se usan para garantizar que solo un hilo entre en una sección crítica a la vez.
• Un semáforo tiene muchos estados (0, 1, 2, ...). Se puede bloquear (estado 0) o desbloquear (estados 1, 2, 3, ...). A menudo, uno o más semáforos se usan juntos para garantizar que solo un hilo entre en una sección crítica precisamente cuando el número de unidades de algún recurso ha alcanzado / no ha alcanzado un valor particular (ya sea mediante la cuenta regresiva a ese valor o contando hasta ese valor )

Para ambos bloqueos / semáforos, al intentar llamar acquire()mientras la primitiva está en estado 0, se suspende el subproceso de invocación. Para las cerraduras: los intentos de adquirir la cerradura en el estado 1 son exitosos. Para semáforos: los intentos de adquirir el bloqueo en los estados {1, 2, 3, ...} tienen éxito.

Para bloqueos en estado 0, si el mismo subproceso que había llamado anteriormente acquire(), ahora llama a liberación, entonces la liberación es exitosa. Si un subproceso diferente intentó esto, depende de la implementación / biblioteca de lo que sucede (por lo general, el intento se ignora o se produce un error). Para los semáforos en el estado 0, cualquier subproceso puede llamar a la liberación y tendrá éxito (independientemente de qué subproceso utilizado anteriormente se adquiere para poner el semáforo en el estado 0).

De la discusión anterior, podemos ver que las cerraduras tienen una noción de propietario (el único hilo que puede llamar a la liberación es el propietario), mientras que los semáforos no tienen un dueño (cualquier hilo puede llamar a la liberación en un semáforo).

Lo que causa mucha confusión es que, en la práctica, son muchas variaciones de esta definición de alto nivel.

Variaciones importantes a tener en cuenta :

• ¿Cómo debería llamarse el acquire()/ release()? - [Varía masivamente ]
• ¿Su cerradura / semáforo utiliza una "cola" o un "conjunto" para recordar los hilos que esperan?
• ¿Se puede compartir su bloqueo / semáforo con hilos de otros procesos?
• ¿Es su cerradura "reentrante"? - [Usualmente sí].
• ¿Su bloqueo está "bloqueando / no bloqueando"? - [Normalmente, los no bloqueantes se usan como bloqueos de bloqueo (también conocidos como bloqueos giratorios) que provocan una espera ocupada]
• ¿Cómo se asegura que las operaciones sean "atómicas"?

Esto depende de su libro / profesor / idioma / biblioteca / entorno.
Aquí hay un recorrido rápido que señala cómo algunos idiomas responden a estos detalles.

C, C ++ ( pthreads )

• Un mutex se implementa a través de pthread_mutex_t. Por defecto, no se pueden compartir con ningún otro proceso ( PTHREAD_PROCESS_PRIVATE), sin embargo, los mutex tienen un atributo llamado pshared . Cuando se establece, el mutex se comparte entre procesos ( PTHREAD_PROCESS_SHARED).
• Un candado es lo mismo que un mutex.
• Un semáforo se implementa a través de sem_t. De manera similar a los mutexes, los semáforos se pueden compartir entre varios procesos o mantenerlos privados en los hilos de un solo proceso. Esto depende del argumento pshared proporcionado a sem_init.

python ( threading.py )

• Un bloqueo ( threading.RLock) es casi lo mismo que C / C ++ pthread_mutex_ts. Ambos son reentrantes . Esto significa que solo pueden ser desbloqueados por el mismo hilo que lo bloqueó. Es el caso de que los sem_tsemáforos, threading.Semaphoresemáforos y theading.Lockbloqueos no sean reentrantes , ya que es el caso de que cualquier hilo pueda realizar desbloquear / bloquear el semáforo.
• Un mutex es lo mismo que un candado (el término no se usa a menudo en python).
• Un semáforo ( threading.Semaphore) es casi lo mismo que sem_t. Aunque con sem_t, una cola de identificadores de subproceso se utiliza para recordar el orden en que los subprocesos se bloquearon al intentar bloquearlo mientras está bloqueado. Cuando un hilo desbloquea un semáforo, el primer hilo de la cola (si hay uno) se elige para ser el nuevo propietario. El identificador de hilo se saca de la cola y el semáforo se vuelve a bloquear. Sin embargo, con threading.Semaphore, se utiliza un conjunto en lugar de una cola, por lo que no se almacena el orden en el que se bloquearon los subprocesos ; cualquier subproceso en el conjunto puede elegirse como el próximo propietario.

Java ( java.util.concurrent )

• Un bloqueo ( java.util.concurrent.ReentrantLock) es casi lo mismo que C / C ++ pthread_mutex_ty Python threading.RLocken que también implementa un bloqueo reentrante. Compartir bloqueos entre procesos es más difícil en Java debido a que JVM actúa como intermediario. Si un hilo intenta desbloquear un bloqueo que no es de su propiedad, IllegalMonitorStateExceptionse lanza un.
• Un mutex es lo mismo que un bloqueo (el término no se usa a menudo en Java).
• Un semáforo ( java.util.concurrent.Semaphore) es casi lo mismo que sem_ty threading.Semaphore. El constructor de semáforos de Java acepta un parámetro booleano de equidad que controla si se debe usar un conjunto (falso) o una cola (verdadero) para almacenar los hilos en espera.

En teoría, los semáforos a menudo se discuten, pero en la práctica, los semáforos no se usan tanto. Un semáforo solo mantiene el estado de un número entero, por lo que a menudo es bastante inflexible y se necesitan muchos a la vez, lo que dificulta la comprensión del código. Además, el hecho de que cualquier hilo pueda liberar un semáforo a veces no es deseado. En su lugar, se utilizan más primitivas / abstracciones de sincronización orientadas a objetos / de nivel superior, como "variables de condición" y "monitores".

Eche un vistazo al Tutorial de subprocesos múltiples de John Kopplin.

En la sección Sincronización entre subprocesos , explica las diferencias entre evento, bloqueo, exclusión mutua, semáforo, temporizador de espera

Un mutex solo puede ser propiedad de un subproceso a la vez, lo que permite que los subprocesos coordinen el acceso mutuo exclusivo a un recurso compartido

Los objetos de sección crítica proporcionan una sincronización similar a la proporcionada por los objetos mutex, excepto que los objetos de sección crítica solo pueden ser utilizados por los hilos de un solo proceso

Otra diferencia entre un mutex y una sección crítica es que si el objeto de la sección crítica actualmente es propiedad de otro hilo, EnterCriticalSection()espera indefinidamente la propiedad mientras WaitForSingleObject()que, que se usa con un mutex, le permite especificar un tiempo de espera

Un semáforo mantiene un recuento entre cero y algún valor máximo, lo que limita el número de subprocesos que acceden simultáneamente a un recurso compartido.

Intentaré cubrirlo con ejemplos:

Bloqueo: un ejemplo en el que usaría locksería un diccionario compartido en el que se agregan elementos (que deben tener claves únicas).
El bloqueo aseguraría que un hilo no ingrese al mecanismo de código que está verificando que el elemento esté en el diccionario mientras que otro hilo (que está en la sección crítica) ya ha pasado esta verificación y está agregando el elemento. Si otro hilo intenta ingresar un código bloqueado, esperará (se bloqueará) hasta que se libere el objeto.

private static readonly Object obj = new Object();

lock (obj) //after object is locked no thread can come in and insert item into dictionary on a different thread right before other thread passed the check...
{
    if (!sharedDict.ContainsKey(key))
    {
        sharedDict.Add(item);
    }
}

Semáforo: Digamos que tiene un grupo de conexiones, entonces un solo subproceso podría reservar un elemento en el grupo al esperar que el semáforo obtenga una conexión. Luego usa la conexión y cuando se realiza el trabajo, libera la conexión liberando el semáforo.

El ejemplo de código que me encanta es uno de gorila dado por @Patric , aquí va:

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);
        }
    }
}

Mutex Es más o menos Semaphore(1,1)y a menudo se usa a nivel mundial (en toda la aplicación, de lo contrario podría decirse que lockes más apropiado). Uno usaría global Mutexal eliminar un nodo de una lista accesible globalmente (lo último que desea que otro hilo haga algo mientras está eliminando el nodo). Cuando adquiere Mutexsi un subproceso diferente intenta adquirir el mismo Mutex, se suspenderá hasta que el MISMO subproceso que adquirió lo Mutexlibere.

Un buen ejemplo sobre la creación de mutex global es por @deepee

class SingleGlobalInstance : IDisposable
{
    public bool hasHandle = false;
    Mutex mutex;

    private void InitMutex()
    {
        string appGuid = ((GuidAttribute)Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(GuidAttribute), false).GetValue(0)).Value.ToString();
        string mutexId = string.Format("Global\\{{{0}}}", appGuid);
        mutex = new Mutex(false, mutexId);

        var allowEveryoneRule = new MutexAccessRule(new SecurityIdentifier(WellKnownSidType.WorldSid, null), MutexRights.FullControl, AccessControlType.Allow);
        var securitySettings = new MutexSecurity();
        securitySettings.AddAccessRule(allowEveryoneRule);
        mutex.SetAccessControl(securitySettings);
    }

    public SingleGlobalInstance(int timeOut)
    {
        InitMutex();
        try
        {
            if(timeOut < 0)
                hasHandle = mutex.WaitOne(Timeout.Infinite, false);
            else
                hasHandle = mutex.WaitOne(timeOut, false);

            if (hasHandle == false)
                throw new TimeoutException("Timeout waiting for exclusive access on SingleInstance");
        }
        catch (AbandonedMutexException)
        {
            hasHandle = true;
        }
    }


    public void Dispose()
    {
        if (mutex != null)
        {
            if (hasHandle)
                mutex.ReleaseMutex();
            mutex.Dispose();
        }
    }
}

luego use como:

using (new SingleGlobalInstance(1000)) //1000ms timeout on global lock
{
    //Only 1 of these runs at a time
    GlobalNodeList.Remove(node)
}

Espero que esto te ahorre algo de tiempo.

Wikipedia tiene una gran sección sobre las diferencias entre semáforos y mutexes :

Un mutex es esencialmente lo mismo que un semáforo binario y a veces usa la misma implementación básica. Las diferencias entre ellos son:

Los mutex tienen un concepto de propietario, que es el proceso que bloqueó el mutex. Solo el proceso que bloqueó el mutex puede desbloquearlo. En contraste, un semáforo no tiene concepto de dueño. Cualquier proceso puede desbloquear un semáforo.

A diferencia de los semáforos, los mutex proporcionan seguridad de inversión prioritaria. Dado que el mutex conoce a su propietario actual, es posible promover la prioridad del propietario cada vez que una tarea de mayor prioridad comienza a esperar en el mutex.

Los mutex también proporcionan seguridad de eliminación, donde el proceso que contiene el mutex no se puede eliminar accidentalmente. Los semáforos no proporcionan esto.

Tengo entendido que un mutex es solo para usar dentro de un solo proceso, pero a través de sus múltiples hilos, mientras que un semáforo puede usarse en múltiples procesos y en sus correspondientes conjuntos de hilos.

Además, un mutex es binario (está bloqueado o desbloqueado), mientras que un semáforo tiene la noción de contar o una cola de más de una solicitud de bloqueo y desbloqueo.

¿Alguien podría verificar mi explicación? Estoy hablando en el contexto de Linux, específicamente Red Hat Enterprise Linux (RHEL) versión 6, que usa el kernel 2.6.32.

Usar la programación en C en una variante de Linux como un caso base para ejemplos.

Bloquear:

• Por lo general, una construcción binaria muy simple en operación bloqueada o desbloqueada

• Sin concepto de propiedad del hilo, prioridad, secuencia, etc.

• Por lo general, un bloqueo de giro donde el hilo verifica continuamente la disponibilidad de bloqueos.

• Por lo general, se basa en operaciones atómicas, por ejemplo, probar y configurar, comparar e intercambiar, buscar y agregar, etc.

• Por lo general, requiere soporte de hardware para la operación atómica.

Bloqueos de archivo:

• Usualmente se usa para coordinar el acceso a un archivo a través de múltiples procesos.

• Múltiples procesos pueden retener el bloqueo de lectura, sin embargo, cuando un solo proceso mantiene el bloqueo de escritura, ningún otro proceso puede adquirir un bloqueo de lectura o escritura.

• Ejemplo: rebaño, fcntl, etc.

Mutex:

• Las llamadas a funciones Mutex generalmente funcionan en el espacio del kernel y resultan en llamadas al sistema.

• Utiliza el concepto de propiedad. Solo el hilo que actualmente contiene el mutex puede desbloquearlo.

• Mutex no es recursivo (Excepción: PTHREAD_MUTEX_RECURSIVE).

• Usualmente se usa en asociación con variables de condición y se pasa como argumentos a, por ejemplo, pthread_cond_signal, pthread_cond_wait, etc.

• Algunos sistemas UNIX permiten que mutex sea utilizado por múltiples procesos, aunque esto puede no aplicarse en todos los sistemas.

Semáforo:

• Este es un entero mantenido por el núcleo cuyos valores no pueden caer por debajo de cero.

• Se puede usar para sincronizar procesos.

• El valor del semáforo puede establecerse en un valor mayor que 1, en cuyo caso el valor generalmente indica la cantidad de recursos disponibles.

• Un semáforo cuyo valor está restringido a 1 y 0 se conoce como semáforo binario.

Supporting ownership, maximum number of processes share locky maximum number of allowed processes/threads in critical sectionson tres factores principales que determinan el nombre / tipo del objeto concurrente con el nombre general de lock. Dado que el valor de estos factores son binarios (tienen dos estados), podemos resumirlos en una tabla de verdad de 3 * 8.

• X (¿Soporta propiedad?): No (0) / sí (1)
• Y (# procesos de compartición):> 1 (∞) / 1
• Z (# procesos / hilos en CA):> 1 (∞) / 1

  X   Y   Z          Name
 --- --- --- ------------------------
  0   ∞   ∞   Semaphore              
  0   ∞   1   Binary Semaphore       
  0   1   ∞   SemaphoreSlim          
  0   1   1   Binary SemaphoreSlim(?)
  1   ∞   ∞   Recursive-Mutex(?)     
  1   ∞   1   Mutex                  
  1   1   ∞   N/A(?)                 
  1   1   1   Lock/Monitor           

Siéntase libre de editar o expandir esta tabla, la he publicado como una tabla ASCII para que sea editable :)