¿Qué es el candado de reentrante y el concepto en general?

Siempre me confundo. ¿Alguien podría explicar qué significa Reentrant en diferentes contextos? ¿Y por qué querría utilizar reentrante frente a no reentrante?

Digamos primitivas de bloqueo pthread (posix), ¿son reentrantes o no? ¿Qué errores deben evitarse al usarlos?

¿Es reentrante mutex?

Bloqueo de reentrada

Un bloqueo reentrante es aquel en el que un proceso puede reclamar el bloqueo varias veces sin bloquearse a sí mismo. Es útil en situaciones en las que no es fácil hacer un seguimiento de si ya ha agarrado un candado. Si un candado no es reentrante, puede tomar el candado y luego bloquearlo cuando vaya a tomarlo nuevamente, bloqueando efectivamente su propio proceso.

La reentrada en general es una propiedad del código en la que no tiene un estado central mutable que pueda corromperse si se llama al código mientras se está ejecutando. Tal llamada podría ser realizada por otro subproceso, o podría realizarse de forma recursiva mediante una ruta de ejecución que se origina en el código mismo.

Si el código se basa en un estado compartido que podría actualizarse en medio de su ejecución, no es reentrante, al menos no si esa actualización pudiera romperlo.

Un caso de uso para el bloqueo reentrante

Un ejemplo (algo genérico y artificial) de una aplicación para un bloqueo de reentrante podría ser:

• Tiene algunos cálculos que involucran un algoritmo que atraviesa un gráfico (quizás con ciclos). Un recorrido puede visitar el mismo nodo más de una vez debido a los ciclos o debido a múltiples rutas al mismo nodo.

• La estructura de datos está sujeta a acceso concurrente y podría actualizarse por alguna razón, tal vez por otro hilo. Debe poder bloquear nodos individuales para hacer frente a posibles daños en los datos debido a las condiciones de carrera. Por alguna razón (tal vez rendimiento) no desea bloquear globalmente toda la estructura de datos.

• Su cálculo no puede retener información completa sobre los nodos que ha visitado, o está utilizando una estructura de datos que no permite que las preguntas de "¿he estado aquí antes?" Se respondan rápidamente.
  
  Un ejemplo de esta situación sería una implementación simple del algoritmo de Dijkstra con una cola de prioridad implementada como un montón binario o una búsqueda en amplitud usando una lista enlazada simple como cola. En estos casos, escanear la cola en busca de inserciones existentes es O (N) y es posible que no desee hacerlo en cada iteración.

En esta situación, hacer un seguimiento de las cerraduras que ya ha adquirido es caro. Suponiendo que desea realizar el bloqueo en el nivel de nodo, un mecanismo de bloqueo reentrante alivia la necesidad de saber si ha visitado un nodo antes. Puede bloquear ciegamente el nodo, quizás desbloqueándolo después de sacarlo de la cola.

Mútex reentrante

Un simple mutex no es reentrante ya que solo un hilo puede estar en la sección crítica en un momento dado. Si toma el mutex y luego intenta tomarlo de nuevo, un mutex simple no tiene suficiente información para saber quién lo tenía anteriormente. Para hacer esto de forma recursiva, necesita un mecanismo en el que cada hilo tenga un token para poder saber quién ha tomado el mutex. Esto hace que el mecanismo de exclusión mutua sea algo más caro, por lo que es posible que no desee hacerlo en todas las situaciones.

IIRC, la API de subprocesos POSIX, ofrece la opción de mutex reentrantes y no reentrantes.

Un bloqueo de reentrante le permite escribir un método Mque bloquea el recurso Ay luego llama de forma Mrecursiva o desde un código que ya tiene un bloqueo A.

Con un candado para no reentrantes, necesitaría 2 versiones de M, uno que bloquee y otro que no, y lógica adicional para llamar al correcto.

El bloqueo reentrante se describe muy bien en este tutorial .

El ejemplo del tutorial es mucho menos elaborado que el de la respuesta sobre cómo atravesar un gráfico. Un bloqueo reentrante es útil en casos muy simples.

El qué y el por qué del mutex recursivo no debería ser algo tan complicado como se describe en la respuesta aceptada.

Me gustaría anotar mi entendimiento después de investigar un poco en la red.

Primero, debe darse cuenta de que cuando se habla de mutex , los conceptos de subprocesos múltiples definitivamente también están involucrados. (mutex se usa para la sincronización. No necesito mutex si solo tengo 1 hilo en mi programa)

En segundo lugar, debe conocer la diferencia entre un mutex normal y un mutex recursivo .

Citado de APUE :

(Un mutex recursivo es a) Un tipo de mutex que permite que el mismo hilo lo bloquee varias veces sin desbloquearlo primero.

La diferencia clave es que dentro del mismo hilo , volver a bloquear un bloqueo recursivo no conduce a un punto muerto ni bloquea el hilo.

¿Significa esto que el bloqueo recusivo nunca provoca un interbloqueo?
No, todavía puede causar interbloqueo como mutex normal si lo ha bloqueado en un hilo sin desbloquearlo e intenta bloquearlo en otros hilos.

Veamos un código como prueba.

1. mutex normal con interbloqueo

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t lock;


void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

salida:

thread1
thread1 hey hey
thread2

ejemplo común de interbloqueo, no hay problema.

2. mutex recursivo con interbloqueo

Simplemente descomente esta línea
error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
y comente la otra.

salida:

thread1
thread1 hey hey
thread2

Sí, el mutex recursivo también puede causar un punto muerto.

3. mutex normal, volver a bloquear en el mismo hilo

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

pthread_mutex_t lock;


void func3(){
    printf("func3\n");
    pthread_mutex_lock(&lock);
    printf("func3 hey hey\n");
}

void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    func3();
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    sleep(2); 
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

salida:

thread1
func3
thread2

Deadlock in thread t1, in func3.
(Utilizo sleep(2)para que sea más fácil ver que el interbloqueo se debe en primer lugar a la reubicación func3)

4. mutex recursivo, volver a bloquear en el mismo hilo

De nuevo, descomente la línea recursiva mutex y comente la otra línea.

salida:

thread1
func3
func3 hey hey
thread1 hey hey
thread2

Deadlock in thread t2, in func2. ¿Ver? func3termina y sale, el rebloqueo no bloquea el hilo ni conduce a un punto muerto.

Entonces, última pregunta, ¿por qué la necesitamos?

Para función recursiva (llamada en programas multiproceso y desea proteger algunos recursos / datos).

Por ejemplo, tiene un programa de varios subprocesos y llama a una función recursiva en el subproceso A. Tiene algunos datos que desea proteger en esa función recursiva, por lo que utiliza el mecanismo mutex. La ejecución de esa función es secuencial en el subproceso A, por lo que definitivamente volvería a bloquear el mutex en recursividad. El uso de mutex normal provoca interbloqueos. Y se inventa el mutex resursivo para resolver esto.

Vea un ejemplo de la respuesta aceptada ¿ Cuándo usar mutex recursivo? .

Wikipedia explica muy bien el mutex recursivo. Definitivamente vale la pena leerlo. Wikipedia: Reentrant_mutex