¿Cuáles son las diversas primitivas de bloqueo disponibles en el kernel de Linux? La tecnología cambia la vida futura

El kernel de Linux ofrece una técnica de sincronización para cada necesidad posible (lo crees, ¡la tienen!).
Es como una canasta de frutas: solo debes saber lo que quieres. Elegir una fruta incorrecta puede arruinar el sabor, ¡así que ten cuidado!

El procesamiento múltiple simétrico (SMP) también ha contribuido enormemente en esta confusión. Esta guía trata de cubrir tanto los sistemas UP (procesador único) como SMP.

Así que comencemos el recorrido, tome su chocolate caliente y siéntese cómodamente para disfrutar del paseo.

Antes de comenzar a buscar frutas, primero comprendamos la canasta sin la cual, todas las frutas caerán.

Desea proteger las regiones críticas y evitar las condiciones de carrera en su código.
¿Qué es una región crítica? Las rutas de código que acceden y manipulan datos compartidos se denominan regiones críticas (también llamadas secciones críticas). Por lo general, no es seguro que múltiples hilos de ejecución accedan al mismo recurso simultáneamente.
Cuando esto ocurre, lo llamamos una condición de carrera, llamada así porque los hilos corrieron para llegar primero.

Considere un recurso compartido simple, un entero global único y una región crítica simple, la operación de simplemente incrementarlo: i ++
Ahora, suponga que hay dos hilos de ejecución, ambos ingresan en esta región crítica y el valor inicial de i es 7. El resultado deseado es similar al siguiente (cada fila representa una unidad de tiempo):

Asegurar que se evite la concurrencia insegura y que no se den condiciones de carrera se llama sincronización.

Es la voluntad de Dios evitar el acceso concurrente durante las regiones críticas, el programador debe actuar como un ángel para garantizar que el código se ejecute atómicamente, es decir, las operaciones se completen sin interrupción como si toda la región crítica fuera una instrucción indivisible. No hacerlo te traerá maldición.

Para aquellos que se preguntan sobre una palabra recientemente agregada en su vocabulario, es decir, concurrencia , quédense conmigo. Otros sabios pueden saltarse esta sección y continuar más.
“Un sistema concurrente es una colección de tareas computacionales interactivas que pueden ejecutarse en paralelo. En el espacio del usuario, la sincronización es necesaria porque los programas se programan de manera preventiva a voluntad del planificador. Debido a que un proceso se puede adelantar en cualquier momento y otro proceso puede programado en el procesador, se puede adelantar involuntariamente un proceso en medio del acceso a una región crítica. Si el proceso recién programado ingresa a la misma región crítica (por ejemplo, si los dos procesos manipulan la misma memoria compartida o escriben en el mismo archivo descriptor), puede ocurrir una carrera. El mismo problema puede ocurrir con múltiples procesos de subproceso único que comparten archivos, o dentro de un solo programa con señales, porque las señales pueden ocurrir de forma asincrónica. Este tipo de concurrencia, en el que dos cosas no suceden realmente en Al mismo tiempo, pero se entrelazan entre sí de manera tal que también podrían llamarse pseudo concurrencia . Si tiene una máquina simétrica de multiprocesamiento, dos procesos s realmente se puede ejecutar en una región crítica exactamente al mismo tiempo. Eso se llama concurrencia verdadera “.

El núcleo tiene causas similares de concurrencia:

Interrupciones: una interrupción puede ocurrir de forma asíncrona en casi cualquier momento, interrumpiendo el código que se está ejecutando actualmente.
Softirqs y tasklets: el núcleo puede generar o programar un softirq o tasklet en casi cualquier momento, interrumpiendo el código que se está ejecutando actualmente.
Preferencia del kernel: debido a que el kernel es preventivo, una tarea en el kernel puede adelantarse a otra.
Reposo y sincronización con el espacio de usuario: una tarea en el núcleo puede dormir y, por lo tanto, invocar al programador, lo que resulta en la ejecución de un nuevo proceso.
Multiprocesamiento simétrico: dos o más procesadores pueden ejecutar el código del kernel exactamente al mismo tiempo.

Habiendo entendido la sincronización y la concurrencia (la canasta), ahora necesitamos una forma de asegurarnos de que solo un hilo manipule el recurso compartido a la vez, un mecanismo para evitar el acceso a un recurso mientras otro hilo de ejecución está en la región marcada.

Este mecanismo es provisto por cerraduras (las frutas).

La regla básica para bloquear es: ¡Proteja los datos, no el código! (nunca olvides esto)

Se dice que el código que está a salvo del acceso simultáneo desde un controlador de interrupciones es a prueba de interrupciones. El código que está a salvo de la concurrencia en máquinas de multiprocesamiento simétrico es seguro para SMP. El código que está a salvo de la concurrencia con la preferencia de kernel es seguro de preferencia. Los mecanismos reales utilizados para proporcionar sincronización y proteger contra las condiciones de carrera en todos estos casos son:

Operaciones atómicas : las operaciones atómicas proporcionan instrucciones que se ejecutan atómicamente, sin interrupción. Los operadores atómicos son instrucciones indivisibles. Por ejemplo, un incremento atómico puede leer e incrementar una variable en uno en un solo paso indivisible e ininterrumpible. El uso de instrucciones atómicas requiere la comprensión de modelos y barreras de memoria. Tenga cuidado con las instrucciones atómicas y las barreras de memoria, ya que son sutiles y rápidas para enojarse.
Spin Locks: este es el bloqueo más común en el kernel de Linux. La idea detrás del bloqueo de giro es ejecutar un ciclo cerrado o una espera ocupada hasta que se libere el bloqueo (esté disponible). Por lo tanto, un bloqueo de giro es un bloqueo que puede mantenerse como máximo un hilo de ejecución.

El núcleo ejecutor no se puede usar para nada más mientras gira.
Los bloqueos de giro se pueden usar en contexto atómico (ISR, softirqs, tasklets) ya que no duermen (lea los últimos dos puntos nuevamente hasta que los recuerde como su propio nombre).
Proporcionan la protección necesaria contra la concurrencia en máquinas de multiprocesamiento. En máquinas de un solo procesador, las cerraduras se compilan y no existen; simplemente actúan como marcadores para deshabilitar y habilitar la preferencia de kernel. Si se desactiva el kernel preventivo, los bloqueos se compilan por completo.
Las cerraduras de giro no son recursivas
Utilice los bloqueos de giro cuando se pueda acceder a los datos compartidos en un contexto atómico para evitar subprocesos / atómicos o atómicos / razas atómicas .
Si se comparte un bloqueo de giro entre un subproceso y un controlador de interrupciones, debe deshabilitar las interrupciones locales (solicitudes de interrupción en el procesador actual) antes de obtener el bloqueo. De lo contrario, es posible que un controlador de interrupciones interrumpa el código del kernel mientras se mantiene el bloqueo e intente volver a adquirirlo. El controlador de interrupciones gira, esperando que el bloqueo esté disponible. Sin embargo, el soporte de bloqueo no funciona hasta que se completa el controlador de interrupciones. Tenga en cuenta que solo necesita deshabilitar las interrupciones en el procesador actual. Si se produce una interrupción en un procesador diferente y gira sobre el mismo bloqueo, no impide que el soporte del bloqueo (que se encuentra en un procesador diferente) finalmente libere el bloqueo. El núcleo proporciona una interfaz que convenientemente desactiva las interrupciones (spin_lock_irqsave / spin_unlock_irqrestore, spin_lock_bh / spin_unlock_bh). Sin embargo, si los datos se comparten entre dos tasklets diferentes, debe obtener un bloqueo de giro normal antes de acceder a los datos en la mitad inferior. No es necesario deshabilitar las mitades inferiores porque un tasklet nunca se adelanta a otro tasklet en ejecución en el mismo procesador. Con softirqs, independientemente de si es el mismo tipo de softirq, si los datos son compartidos por softirqs, deben protegerse con un candado. Los softirq, incluso dos del mismo tipo, pueden ejecutarse simultáneamente en múltiples procesadores del sistema. Sin embargo, un softirq nunca se adelanta a otro softirq que se ejecuta en el mismo procesador, por lo que no es necesario desactivar las mitades inferiores.
No enmascare las interrupciones para proteger los datos compartidos entre el contexto de interrupción y el de no interrupción; en su lugar , use spin-locks.

Cerraduras giratorias de lector-escritor: Las cerraduras giratorias de lector-escritor proporcionan variantes separadas de lector y escritor de la cerradura. Uno o más lectores pueden mantener simultáneamente el bloqueo del lector. El bloqueo del escritor, por el contrario, puede ser mantenido por un escritor sin lectores simultáneos. Los bloqueos de lector / escritor a veces se denominan bloqueos compartidos / exclusivos o concurrentes / exclusivos porque el bloqueo está disponible en forma compartida (para lectores) y exclusivo (para escritores) . Tenga cuidado con el rendimiento de las cerraduras r / w.
Semáforos: los semáforos en Linux son bloqueos inactivos. Cuando una tarea intenta adquirir un semáforo que no está disponible, el semáforo coloca la tarea en una cola de espera y la pone a dormir. El procesador es libre de ejecutar otro código. Cuando el semáforo está disponible, una de las tareas en la cola de espera se despierta para que luego pueda adquirir el semáforo.

Debido a la naturaleza dormida, los semáforos son muy adecuados para las cerraduras que se mantienen durante mucho tiempo.
No son óptimas para cerraduras que se mantienen por períodos cortos
Debido a que un hilo de ejecución duerme en la contención de bloqueo, los semáforos se deben obtener solo en el contexto del proceso porque el contexto de interrupción no es programable .
No puede mantener un bloqueo de giro mientras adquiere un semáforo, ya que puede que tenga que dormir mientras espera el semáforo, y no puede dormir mientras mantiene un bloqueo de giro.
A diferencia de los bloqueos de giro, el semáforo no deshabilita la preferencia de kernel. Se puede evitar un código que contenga un semáforo.
Pueden permitir un máximo de recuentos de cerraduras simultáneas. En ese caso, se llaman contar semáforos . Cuando la cuenta es igual a uno, se llaman semáforos binarios.
Aunque un semáforo binario proporciona exclusión mutua, pero no use semáforos para la exclusión mutua. Ese es un trabajo mejor manejado por mutexes por dos razones. En primer lugar, los mutexes son más rápidos (al menos del lado del kernel). En segundo lugar, como los mutexes tienen una semántica más precisa, la implementación puede informar automáticamente algunos errores, por ejemplo, desbloquear un mutex antes de bloquearlo. El kernel tiene una opción de configuración para habilitar tales comprobaciones.
El uso principal del semáforo debe ser para la sincronización (entre hilos que se ejecutan en un contexto diferente), no para el bloqueo.
No use semáforos cuando existan alternativas más adecuadas (esto puede sonar duro en los semáforos, pero créame, no quiere que su vida se desperdicie en la reparación de errores inducidos por semáforos).

Semáforos de lector-escritor: Las situaciones en las que se prefieren los semáforos de lector-escritor sobre los semáforos estándar son las mismas que con los bloqueos de giro lector-escritor frente a los bloqueos de giro estándar.
Mutexes: bloqueo para dormir (y a veces adaptativo) que permite la exclusión mutua. Se comporta de manera similar a un semáforo con un recuento de uno, pero tiene una interfaz más simple, un rendimiento más eficiente y restricciones adicionales para su uso.

Solo una tarea puede contener el mutex a la vez. Es decir, el recuento de uso en un mutex es siempre uno.
Quien haya bloqueado un mutex debe desbloquearlo. Es decir, no puede bloquear un mutex en un contexto y luego desbloquearlo en otro. Esto significa que el mutex no es adecuado para sincronizaciones más complicadas entre el núcleo y el espacio de usuario.
Los bloqueos y desbloqueos recursivos no están permitidos.
Un proceso no puede salir mientras se mantiene un mutex
Un mutex no puede ser adquirido por un controlador de interrupciones o la mitad inferior, incluso con
mutex_trylock ().

Variables de finalización: el uso de variables de finalización es una manera fácil de sincronizar entre dos tareas en el núcleo cuando una tarea necesita indicarle a la otra que ha ocurrido un evento. Una tarea espera en la variable de finalización mientras que otra tarea realiza algún trabajo. Cuando la otra tarea ha completado el trabajo, utiliza la variable de finalización para despertar cualquier tarea en espera. ¿Escuchas sonar campanas que suenan a semáforo? En caso afirmativo, (me alegra que todavía esté despierto) tiene razón: la idea es muy parecida. De hecho, las variables de finalización simplemente proporcionan una solución simple a un problema cuya respuesta es, por lo demás, semáforos.
Bloqueos secuenciales: el bloqueo secuencial, generalmente acortado a bloqueo seq, proporciona un mecanismo simple para leer y escribir datos compartidos. Funciona manteniendo un contador de secuencia. Cada vez que se escriben los datos en cuestión, se obtiene un bloqueo y se incrementa un número de secuencia. Antes y después de leer los datos, se lee el número de secuencia. Si los valores son los mismos, una escritura no comenzó en el medio de la lectura. Además, si los valores son pares, una escritura no está en curso. (Tomar el bloqueo de escritura hace que el valor sea extraño, mientras que liberarlo lo hace incluso porque el bloqueo comienza en cero). Los bloqueos Seq son útiles para proporcionar un bloqueo ligero y escalable para usar con muchos lectores y algunos escritores. Sin embargo, las cerraduras Seq favorecen a los escritores sobre los lectores. La adquisición del bloqueo de escritura siempre tiene éxito siempre que no haya otros escritores. Los lectores no afectan el bloqueo de escritura, como es el caso de los bloqueos de giro lector-escritor y los semáforos. Además, los escritores pendientes continuamente hacen que se repita el ciclo de lectura (el ejemplo anterior), hasta que ya no hay escritores que mantengan el bloqueo.
Deshabilitación previa: recuerde que si se mantiene un bloqueo de giro, el núcleo no es preventivo. Deshabilitar
sin embargo, preemption (preempt_disable / preempt_enable) no impide que se ejecuten ISR y tasklets. Además, la desactivación preventiva no debe usarse para evitar condiciones de carrera porque:

La desactivación de preferencia funciona solo en el núcleo actual de la CPU y, por lo tanto, no impide
carreras en sistemas SMP.
Deshabilitar la preferencia tiene un impacto global en la latencia de subprocesos y, por lo tanto, puede afectar en tiempo real.

Barreras: tanto el compilador como el procesador pueden reordenar lecturas y escrituras por razones de rendimiento. Cuando se trata de la sincronización entre múltiples procesadores o con dispositivos de hardware, a veces es un requisito que las lecturas de memoria (cargas) y las escrituras de memoria (almacenes) se emitan en el orden especificado en el código de su programa. Todos los procesadores que ordenan lecturas o escrituras proporcionan instrucciones de la máquina para hacer cumplir los requisitos de pedido. También es posible indicarle al compilador que no reordene las instrucciones en torno a un punto dado. Estas instrucciones se denominan barreras . Le sugiero que guarde un poco de jugo y lea la documentación del núcleo sobre las barreras claramente antes de que tenga la intención de usarlas. (http://kernel.org/doc/Documentat…)

No me digas que todavía estás buscando una fruta para satisfacer tus necesidades.
Si es así, le sugiero que reconsidere su requerimiento. Pero no se desanime, estoy bastante seguro de que hay una salida.

¿Olvidé mencionar que no confiar en las prioridades de hilo para arreglar las condiciones de carrera ? En caso afirmativo, marque este también en su piedra cercana

Irónicamente, las carreras son causadas por la falta de sincronización y los puntos muertos por sincronización excesiva o incorrecta. La programación concurrente es, por lo tanto, una danza delicada entre estas dos trampas y muchos males menores, para ofrecer el conjunto de características requeridas mientras se mantiene la corrección del sistema y se proporciona un rendimiento adecuado.

Se produce un punto muerto cuando cada tarea en un conjunto de tareas se bloquea esperando un recurso propiedad de
Otra tarea en el set. Todas las siguientes condiciones deben ser verdaderas simultáneamente para que exista un punto muerto:

Exclusión mutua: hay varios recursos que no pueden ser utilizados por más de una tarea a la vez.
Retener y esperar: las tareas que ya contienen un recurso pueden bloquear la espera de otro recurso.
Sin preferencia: los recursos no se pueden eliminar por la fuerza de la tarea que los posee.
Solo la tarea propietaria puede liberar recursos.
Espera circular: hay varias tareas que forman una cadena circular donde cada tarea espera en un recurso propiedad de la siguiente tarea en la cadena.

Eliminar cualquiera de las condiciones anteriores es suficiente para evitar puntos muertos. Lo siguiente debería ayudarlo:

Intente limitar el diseño a un solo mutex. Esto elimina la condición de exclusión mutua.
Evite adquirir más de un mutex / recurso a la vez y también evite adquirir bloqueos de forma recursiva. Esto elimina la condición de espera y espera.
Adquiera siempre mutexes en el mismo orden y suéltelos en orden opuesto para evitar ciclos. Esto elimina la condición de espera circular. Definir y documentar la jerarquía de orden de bloqueo.
Cuando pedir mutexes no es una opción, a veces es posible evitar puntos muertos utilizando variantes de “prueba” de las primitivas de bloqueo que devuelven un error si el bloqueo ya está retenido. Esto elimina la condición de espera y espera. La idea es tratar de adquirir el bloqueo desordenado. Si se adquiere la cerradura, todo está bien. Si el bloqueo ya está retenido, se deben tomar algunas medidas de recuperación, por ejemplo, revertir los recursos compartidos a un estado consistente, liberar todos los bloqueos ya retenidos e intentar la adquisición en orden.
Esfuércese por desbloquear antes de llamar a código desconocido.
Evite invocar devoluciones de llamada proporcionadas por el cliente mientras mantiene bloqueos.
Contestación de llamadas de devolución de documentos.
Tenga cuidado con las condiciones de carrera al evaluar la condición de despertador.

Entonces, ya conoce la cesta y los sabores de frutas que tiene. Así que saciate con la fruta que deseas.