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

semaphore java

Question

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

Answer 1

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, mutex, semáforo, temporizador waitable.

Un mutex puede ser propiedad de solo un hilo a la vez, lo que permite que los hilos coordinen el acceso mutuamente exclusivo a un recurso compartido

Los objetos de la sección crítica proporcionan una sincronización similar a la proporcionada por los objetos de exclusión mutua, excepto que los objetos de la sección crítica solo pueden ser usados ​​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 pertenece actualmente a otro subproceso, EnterCriticalSection() espera indefinidamente la propiedad mientras que WaitForSingleObject() , que se usa con un mutex, le permite especificar un tiempo de espera

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

Answer 2

Hay muchas ideas erróneas con respecto a estas palabras.

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

1) Sección crítica = Objeto de usuario utilizado para permitir la ejecución de solo un subproceso activo de muchos otros dentro de un proceso . Los otros hilos no seleccionados se ponen en suspensión .

[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 se ponen en suspensión . Este objeto admite la propiedad de subprocesos, la notificación de terminación de subprocesos, la recursión (múltiples llamadas ''adquirir'' desde el mismo subproceso) y ''evitación de inversión de prioridad''.

[Capacidad de proceso, muy seguro de usar, una especie de objeto de sincronización de ''alto nivel''].

3) Counting Semaphore (también conocido como Semaphore) = objeto Kernel utilizado para permitir la ejecución de un grupo de subprocesos activos de muchos otros. Los otros hilos no seleccionados se ponen en suspensión .

[Sin embargo, la capacidad de procesamiento 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.

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

Espera ocupada = prueba continua de una variable hasta que aparezca algún valor.

Finalmente:

Spin-lock (también conocido como Spinlock) = un bloqueo que usa la espera ocupada . (La adquisición del bloqueo se realiza mediante xchg o operaciones atómicas similares).

[Sin hilo durmiendo, se usa 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 apostar algunos grandes dólares a que los primeros 3 objetos de sincronización anteriores (# 1, # 2 y # 3) utilizan esta simple bestia (# 4) como parte de su implementación.

¡Tenga un buen día!.

Referencias:

Conceptos de tiempo real para sistemas integrados de Qing Li con Caroline Yao (libros CMP).

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

-Programación de aplicaciones para Microsoft Windows (4) por Jeffrey Richter (Microsoft Programming Series).

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

Answer 3

Intentaré cubrirlo con ejemplos:

Bloqueo: un ejemplo en el que usaría el lock sería un diccionario compartido en el que se agregan elementos (que deben tener claves únicas).
El bloqueo garantizaría que un subproceso no ingrese al mecanismo del código que comprueba si el elemento está en el diccionario, mientras que otro subproceso (que está en la sección crítica) ya pasó 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 hilo podría reservar un elemento en el grupo esperando que el semáforo obtenga una conexión. A continuación, utiliza la conexión y, cuando finaliza el trabajo, libera la conexión liberando el semáforo.

El ejemplo de código que amo es uno de los guardabosques dados 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 bastante Semaphore(1,1) y se usa a menudo en todo el mundo (en toda la aplicación, podría decirse que el lock es más apropiado). Uno usaría Mutex global cuando elimine un nodo de una lista accesible globalmente (lo último que quiere es que otro hilo haga algo mientras está eliminando el nodo). Cuando adquiera Mutex si un subproceso diferente intenta adquirir el mismo Mutex , se pondrá en suspensión hasta que el MISMO subproceso que lo adquirió lo libere.

Un buen ejemplo sobre la creación de exclusión mutua global es de @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();
        }
    }
}

entonces 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 tiempo.

Answer 4

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

• Un bloqueo (o mutex ) tiene dos estados (0 o 1). Puede ser desbloqueado o bloqueado . A menudo se utilizan 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, ...). Uno o más semáforos a menudo se usan juntos para asegurar que solo un hilo ingrese a una sección crítica precisamente cuando la cantidad de unidades de algún recurso ha alcanzado / no ha alcanzado un valor particular (ya sea contando hacia atrás hasta ese valor o contando hasta ese valor ).

Para ambos bloqueos / semáforos, intentar llamar a acquire() mientras la primitiva está en el estado 0 hace que se suspenda el subproceso de invocación. Para bloqueos: los intentos de adquirir el bloqueo en estado 1 tienen éxito. Para los semáforos: los intentos de adquirir el bloqueo en los estados {1, 2, 3, ...} tienen éxito.

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

De la discusión anterior, podemos ver que los bloqueos tienen una noción de propietario (el único hilo que puede llamar liberación es el propietario), mientras que los semáforos no tienen propietario (cualquier secuencia puede llamar 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 se debería llamar la acquire() / release() ? - [Varía massively ]
• ¿Tu bloqueo / semáforo usa una "cola" o un "conjunto" para recordar los hilos en espera?
• ¿Se puede compartir su bloqueo / semáforo con subprocesos de otros procesos?
• ¿Es su bloqueo "reentrante"? - [Generalmente sí].
• ¿Su bloqueo está "bloqueando / no bloqueando"? - [Normalmente, los bloqueos no bloqueados se utilizan como bloqueos de bloqueo (también conocidos como spin-locks) porque están ocupados esperando].
• ¿Cómo se asegura que las operaciones sean "atómicas"?

Estos dependen de su libro / profesor / idioma / biblioteca / medio ambiente.
Aquí hay un recorrido rápido que muestra cómo algunos idiomas responden a estos detalles.

C, C ++ ( pthreads )

• Un mutex se implementa a través de pthread_mutex_t . De forma predeterminada, no se pueden compartir con ningún otro proceso ( PTHREAD_PROCESS_PRIVATE ), sin embargo, el mutex tiene 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 miles de procesos o se pueden mantener privados a 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_t s. Ambos son reentrantes . Esto significa que solo pueden ser desbloqueados por el mismo hilo que lo bloqueó. Es el caso que los semáforos sem_t , los threading.Semaphore semáforos de semáforos y la theading.Lock bloqueos de bloqueo no son reentrantes , ya que es el caso de que cualquier hilo puede desbloquear o bloquear el semáforo.
• Un mutex es lo mismo que un bloqueo (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 , se sem_t una cola de identificadores de hilo para recordar el orden en que los hilos 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 elimina de la cola y el semáforo se bloquea de nuevo. Sin embargo, con threading.Semaphore , se utiliza un conjunto en lugar de una cola, por lo que no se almacena el orden en que se bloquearon los hilos: cualquier hilo del conjunto puede ser elegido como el siguiente propietario.

Java ( java.util.concurrent )

• Un bloqueo ( java.util.concurrent.ReentrantLock ) es casi lo mismo que C / C ++ pthread_mutex_t ''sy Python''s threading.RLock porque también implementa un bloqueo de reentrada. Compartir bloqueos entre procesos es más difícil en Java debido a que la JVM actúa como intermediario. Si un hilo intenta desbloquear un bloqueo que no posee, se lanza una IllegalMonitorStateException .
• 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_t y threading.Semaphore . El constructor para los semáforos de Java acepta un parámetro booleano de imparcialidad que controla si se usa un conjunto (falso) o una cola (verdadero) para almacenar los subprocesos en espera.

En teoría, los semáforos se discuten a menudo, pero en la práctica, los semáforos no se usan mucho. Un semáforo solo mantiene el estado de un entero, por lo que a menudo es bastante inflexible y se necesitan muchos a la vez, lo que causa dificultades para comprender el código. Además, el hecho de que cualquier hilo pueda liberar un semáforo a veces es indeseable. En su lugar, se utilizan más primitivos / abstracciones de sincronización orientados a objetos / de alto nivel, como "variables de condición" y "monitores".

Answer 5

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

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

¿Podría alguien 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.

Answer 6

Un bloqueo permite que solo una hebra ingrese a 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 abarcar todo el sistema (compartido por varios procesos).

Un semaphore hace lo mismo que un mutex pero permite que se ingrese x número de subprocesos, esto puede usarse, por ejemplo, para limitar el número de tareas intensivas de CPU, io o RAM que se ejecutan al mismo tiempo.

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

Answer 7

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

Bloquear:

• Por lo general, un constructo binario muy simple en operación bloqueado o desbloqueado

• No hay concepto de propiedad de hilo, prioridad, secuenciación, etc.

• Por lo general, un bloqueo de giro en el que el hilo comprueba continuamente la disponibilidad de los bloqueos.

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

• Generalmente requiere soporte de hardware para operación atómica.

Bloqueos de archivos:

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

• Varios procesos pueden mantener el bloqueo de lectura, sin embargo, cuando cualquier proceso único 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 de función Mutex generalmente funcionan en el espacio del kernel y dan como resultado 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).

• Generalmente 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 el uso de la exclusión mutua en varios procesos, aunque esto no se puede aplicar en todos los sistemas.

Semáforo:

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

• Se puede utilizar para sincronizar procesos.

• El valor del semáforo se puede establecer 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 un semáforo binario.

Answer 8

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

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

Mutexes tiene un concepto de propietario, que es el proceso que bloqueó el mutex. Sólo el proceso que bloqueó el mutex puede desbloquearlo. En contraste, un semáforo no tiene concepto de propietario. 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 siempre que una tarea de mayor prioridad comience a esperar en el mutex.

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