¿Qué es el locking y el concepto de Reentrada en general?

Siempre me confundo ¿Alguien explicaría qué significa Reentrant en diferentes contextos? ¿Y por qué querrías usar reentrantes vs. no reentrantes?

Diga las primitivas de locking pthread (posix), ¿son reentrantes o no? ¿Qué peligros deberían evitarse al usarlos?

¿Es mutex re-entrante?

Reentrada de locking

Un locking de reentrada es aquel en el que un proceso puede reclamar el locking varias veces sin bloquearse. Es útil en situaciones en las que no es fácil hacer un seguimiento de si ya has agarrado un candado. Si un candado no es reentrante, puede agarrar el candado, luego bloquearlo cuando vaya a agarrarlo nuevamente, bloqueando efectivamente su propio proceso.

La reentrada en general es una propiedad del código donde no tiene un estado mutable central que podría corromperse si se invoca el código mientras se está ejecutando. Tal llamada podría hacerse por otro hilo, o podría hacerse de manera recursiva mediante un camino de ejecución que se origina desde dentro del código mismo.

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

Un caso de uso para el locking de reentrantes

Un ejemplo (algo genérico y artificial) de una solicitud para un locking de reentrantes podría ser:

  • Tiene algún cálculo que involucra un algoritmo que atraviesa un gráfico (quizás con ciclos en él). 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 algún motivo, quizás por otro hilo. Debe poder bloquear nodos individuales para hacer frente a posibles daños a los datos debido a las condiciones de carrera. Por alguna razón (tal vez el rendimiento) no desea bloquear globalmente toda la estructura de datos.

  • Su computación no puede retener información completa sobre qué nodos ha visitado, o está usando una estructura de datos que no permite que las preguntas “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 de amplitud usando una lista vinculada simple como una cola. En estos casos, escanear la cola para las inserciones existentes es O (N) y es posible que no desee hacerlo en cada iteración.

En esta situación, mantener un registro de los lockings que ya ha adquirido es costoso. Suponiendo que quiera hacer el locking a nivel de nodo, un mecanismo de locking reentrante alivia la necesidad de saber si ha visitado un nodo anteriormente. Puede bloquear el nodo a ciegas, tal vez desbloquearlo después de que lo saque de la cola.

Reexpedición de mutexes

Un mutex simple no es reentrante ya que solo un hilo puede estar en la sección crítica en un momento dado. Si agarras el mutex y luego tratas de agarrarlo de nuevo, un mutex simple no tiene suficiente información para saber quién lo tenía antes. Para hacer esto recursivamente, necesitas un mecanismo donde cada hilo tenga un token para que puedas saber quién ha agarrado el mutex. Esto hace que el mecanismo mutex sea algo más caro, por lo que es posible que no desee hacerlo en todas las situaciones.

IIRC la API de hilos POSIX ofrece la opción de mutexes reentrantes y no reentrantes.

Un locking de reentrantes le permite escribir un método M que pone un locking en el recurso A y luego llama a M recursivamente o desde un código que ya tiene un locking en A

Con un locking no reentrante, necesitaría 2 versiones de M , una que bloquee y otra que no, y lógica adicional para llamar a la correcta.

El locking de reentrada está muy bien descrito en este tutorial .

El ejemplo en el tutorial es mucho menos artificial que en la respuesta sobre atravesar un gráfico. Un locking de reentrada es útil en casos muy simples.