Garantías de progreso sin locking

Como anécdota, descubrí que muchos progtwigdores creen erróneamente que “sin locking” simplemente significa “progtwigción concurrente sin muteos”. Por lo general, también existe un malentendido correlacionado de que el propósito de escribir código sin candado es para un mejor rendimiento simultáneo. Por supuesto, la definición correcta de “sin cerrojo” se trata en realidad de garantías de progreso . Un algoritmo sin lockings garantiza que al menos un hilo pueda avanzar, independientemente de lo que hagan otros hilos.

Esto significa que un algoritmo sin lockings nunca puede tener un código donde un hilo depende de otro hilo para poder continuar. Por ejemplo, el código de locking no puede tener una situación en la que el hilo A establece un indicador, y luego el hilo B sigue girando mientras espera que el hilo A deshaga el indicador. Un código como ese es básicamente implementar un locking (o lo que yo llamaría un mutex disfrazado).

Sin embargo, otros casos son más sutiles y hay algunos casos en los que honestamente no puedo decir si un algoritmo califica como libre de lockings o no, porque la noción de “progresar” a veces me parece subjetiva.

Uno de estos casos se encuentra en la biblioteca de concurrencia (bien considerada, afaik), liblfds . Estaba estudiando la implementación de una cola acotada de múltiples productores / consumidores múltiples en liblfds; la implementación es muy sencilla, pero realmente no puedo decir si debería calificar como libre de locking.

El algoritmo relevante está en lfds711_queue_bmm_enqueue.c . Liblfds usa elementos atómicos personalizados y barreras de memoria, pero el algoritmo es lo suficientemente simple como para describirlo en un párrafo más o menos.

La cola en sí es una matriz contigua limitada (ringbuffer). Hay un read_index y write_index compartidos. Cada ranura en la cola contiene un campo para datos de usuario, y un valor de número de sequence_number , que es básicamente como un contador de época. (Esto evita problemas ABA).

El algoritmo PUSH es el siguiente:

  1. Atómicamente CARGAR el write_index
  2. Intente reservar un espacio en la cola en write_index % queue_size utilizando un lazo write_index que intente establecer write_index en write_index + 1 .
  3. Si CompareAndSwap es exitoso, copie los datos del usuario en la ranura reservada.
  4. Finalmente, actualice el sequence_index en la ranura haciéndolo igual a write_index + 1 .

El código fuente actual usa átomos atómicos personalizados y barreras de memoria, por lo que para mayor claridad sobre este algoritmo, lo he traducido brevemente en atómicas estándar de C ++ (no probadas) para una mejor legibilidad, de la siguiente manera:

 bool mcmp_queue::enqueue(void* data) { int write_index = m_write_index.load(std::memory_order_relaxed); for (;;) { slot& s = m_slots[write_index % m_num_slots]; int sequence_number = s.sequence_number.load(std::memory_order_acquire); int difference = sequence_number - write_index; if (difference == 0) { if (m_write_index.compare_exchange_weak( write_index, write_index + 1, std::memory_order_acq_rel )) { break; } } if (difference < 0) return false; // queue is full } // Copy user-data and update sequence number // s.user_data = data; s.sequence_number.store(write_index + 1, std::memory_order_release); return true; } 

Ahora, un hilo que quiere POP un elemento de la ranura en read_index no podrá hacerlo hasta que observe que sequence_number la ranura es read_index + 1 .

De acuerdo, entonces no hay mutexes aquí, y el algoritmo probablemente funciona bien (es solo un CAS para PUSH y POP), pero ¿está libre de lockings? La razón por la que no está claro para mí es porque la definición de “progresar” parece turbia cuando existe la posibilidad de que un PUSH o POP siempre pueda fallar si se observa que la cola está llena o vacía.

Pero lo que es cuestionable para mí es que el algoritmo PUSH esencialmente reserva un espacio, lo que significa que la ranura nunca puede ser POP hasta que el hilo de empuje se pone a actualizar el número de secuencia. Esto significa que un hilo POP que quiere mostrar un valor depende del hilo PUSH que haya completado la operación. De lo contrario, el hilo POP siempre devolverá false porque cree que la cola está VACÍA. Me parece discutible si esto realmente cae dentro de la definición de “progresar”.

En general, los algoritmos verdaderamente sin locking implican una fase en la que un subproceso predeterminado intenta realmente AYUDAR al otro subproceso para completar una operación. Entonces, para estar realmente libre de lockings, creo que un hilo POP que observe un PUSH en progreso realmente necesitaría intentar completar el PUSH, y solo después de eso, realizar la operación POP original. Si el hilo POP simplemente devuelve que la cola está VACÍA cuando hay un PUSH en progreso, el hilo POP está básicamente bloqueado hasta que el hilo PUSH complete la operación. Si el hilo PUSH muere, o se va a dormir durante 1.000 años, o se progtwig de alguna otra forma en el olvido, el hilo POP no puede hacer nada excepto informar continuamente que la cola está VACÍA.

Entonces, ¿esto se ajusta a la definición de estar libre de cerrojo? Desde una perspectiva, puede argumentar que el hilo POP siempre puede progresar, porque siempre puede informar que la cola está VACÍA (que al menos es una forma de progreso, supongo). Pero para mí, esto realmente no está progresando. , ya que la única razón por la que la cola se observa como vacía es porque estamos bloqueados por una operación simultánea PUSH.

Entonces, mi pregunta es : ¿este algoritmo está realmente libre de lockings? ¿O el sistema de reserva del índice es básicamente un mutex disfrazado?

Esta estructura de datos de cola no está estrictamente bloqueada por lo que considero la definición más razonable. Esa definición es algo así como:

Una estructura está libre de cerrojo si solo se puede suspender indefinidamente un hilo en cualquier punto, al mismo tiempo que la estructura puede ser utilizada por los hilos restantes.

Por supuesto, esto implica una definición adecuada de utilizable , pero para la mayoría de las estructuras esto es bastante simple: la estructura debe seguir obedeciendo sus contratos y permitir que los elementos se inserten y eliminen como se esperaba.

En este caso, un hilo que ha tenido éxito en incrementar m_write_increment , pero aún no ha escrito en el número de s.sequence_number deja el contenedor en lo que pronto será un estado inutilizable. Si se elimina ese hilo, el contenedor eventualmente informará tanto “lleno” como “vacío” para push y pop , respectivamente, violando el contrato de una cola de tamaño fijo.

Aquí hay un mutex oculto (la combinación de m_write_index y el asociado en el número de s.sequence_number ), pero básicamente funciona como un mutex por elemento. Por lo tanto, la falla solo se vuelve aparente para los escritores una vez que ha bucleado y un nuevo escritor intenta obtener el mutex, pero de hecho todos los escritores subsiguientes no han podido insertar su elemento en la cola, ya que ningún lector lo verá.

Ahora, esto no significa que esta es una mala implementación de una cola concurrente. Para algunos usos, puede comportarse principalmente como si estuviera libre de locking. Por ejemplo, esta estructura puede tener la mayoría de las propiedades de rendimiento útiles de una estructura verdaderamente libre de locking, pero al mismo tiempo le faltan algunas de las propiedades de corrección útiles . Básicamente, el término “sin cerradura” generalmente implica un conjunto de propiedades, de las cuales solo un subconjunto suele ser importante para un uso particular. Veámoslos uno por uno y veamos cómo funciona esta estructura. Los categorizaremos ampliamente en categorías funcionales y de rendimiento.

Actuación

Rendimiento descontrolado

El rendimiento no reconocido o “mejor caso” es importante para muchas estructuras. Si bien necesita una estructura concurrente para la corrección, por lo general, aún intentará diseñar su aplicación para que la contención se mantenga al mínimo, por lo que el costo no previsto es a menudo importante. Algunas estructuras sin cerrojo ayudan aquí, al reducir la cantidad de costosas operaciones atómicas en el camino rápido no syscall , o al evitar una syscall .

Esta implementación de cola hace un trabajo razonable aquí: solo hay una única operación “definitivamente costosa”: compare_exchange_weak , y un par de operaciones posiblemente costosas (la memory_order_acquire load y memory_order_release store) 1 , y otra pequeña sobrecarga.

Esto se compara con algo como std::mutex que implicaría algo así como una operación atómica para bloquear y otra para desbloquear, y en la práctica en Linux las llamadas pthread tienen una carga no despreciable también.

Por lo tanto, espero que esta cola funcione razonablemente bien en el camino rápido sin límites.

Rendimiento Contended

Una de las ventajas de las estructuras sin cerrojo es que a menudo permiten una mejor escala cuando una estructura es muy disputada. Esto no es necesariamente una ventaja inherente : algunas estructuras basadas en locking con lockings múltiples o lockings de lectura y escritura pueden exhibir escalas que coincidan o excedan algunos enfoques sin locking, pero generalmente es el caso en que las estructuras sin locking exhiben mejor escalamiento que una alternativa simple de one-lock-to-rule-them-all.

Esta cola funciona razonablemente a este respecto. La variable m_write_index es actualizada atómicamente por todos los lectores y será un punto de discusión, pero el comportamiento debe ser razonable siempre que la implementación CAS de hardware subyacente sea razonable.

Tenga en cuenta que una cola generalmente es una estructura concurrente bastante pobre ya que las inserciones y eliminaciones ocurren en los mismos lugares (la cabeza y la cola), por lo que la contención es inherente a la definición de la estructura. Compare esto con un mapa concurrente, donde los diferentes elementos no tienen una relación ordenada particular: dicha estructura puede ofrecer una mutación simultánea eficiente libre de contención si se accede a diferentes elementos.

Inmunidad de cambio de contexto

Una ventaja de rendimiento de las estructuras sin cerrojo que se relaciona con la definición del núcleo anterior (y también con las garantías funcionales) es que un cambio de contexto de un hilo que está mutando la estructura no retrasa a todos los demás mutadores. En un sistema muy cargado (especialmente cuando los hilos ejecutables >> núcleos disponibles), un hilo se puede cambiar durante cientos de milisegundos o segundos. Durante este tiempo, cualquier mutador concurrente bloqueará e incurrirá en costos de progtwigción adicionales (o se producirán cambios que también pueden producir un comportamiento deficiente). A pesar de que tal “progtwigción desafortunada” puede ser rara, cuando ocurre, todo el sistema puede incurrir en un serio pico de latencia.

Las estructuras sin locking evitan esto ya que no existe una “región crítica” en la que un hilo puede cambiar de contexto y posteriormente bloquear el avance por otros hilos.

Esta estructura ofrece protección parcial en esta área, cuyos detalles dependen del tamaño de la cola y del comportamiento de la aplicación. Incluso si se cambia un hilo en la región crítica entre la actualización de m_write_index y la escritura del número de secuencia, otros hilos pueden seguir push elementos a la cola, siempre que no se envuelvan completamente en el elemento en curso de el hilo estancado Los subprocesos también pueden pop elementos, pero solo hasta el elemento en progreso .

Si bien el comportamiento de push puede no ser un problema para las colas de alta capacidad, el comportamiento pop puede ser un problema: si la cola tiene un alto rendimiento en comparación con el tiempo promedio que un subproceso cambia de contexto y la plenitud promedio, la cola aparecen rápidamente vacíos para todos los hilos del consumidor, incluso si hay muchos elementos añadidos más allá del elemento en progreso . Esto no se ve afectado por la capacidad de la cola, sino simplemente por el comportamiento de la aplicación. Significa que el lado del consumidor puede estancarse completamente cuando esto ocurre. ¡A este respecto, la cola no parece estar completamente libre de cerrojo!

Aspectos funcionales

Terminación de hilo asíncrono

Con la ventaja de las estructuras sin cerradura, son seguros para el uso de hilos que pueden ser cancelados de forma asincrónica o pueden terminar de forma excepcional en la región crítica. La cancelación de un hilo en cualquier punto deja la estructura en un estado consistente.

Este no es el caso para esta cola, como se describió anteriormente.

Cola de acceso de interrupción o señal

Una ventaja relacionada es que las estructuras sin cerradura generalmente se pueden examinar o mutar a partir de una interrupción o señal. Esto es útil en muchos casos donde una interrupción o señal comparte una estructura con hilos de proceso regulares.

Esta cola generalmente admite este caso de uso. Incluso si la señal o interrupción se produce cuando otro subproceso se encuentra en la región crítica, el código asíncrono aún puede push un elemento en la cola (que solo se verá más adelante al consumir subprocesos) y aún puede sacar un elemento de la cola.

El comportamiento no es tan completo como una verdadera estructura sin locking: imagina un manejador de señal con una manera de indicar a los subprocesos restantes de la aplicación (que no sea el interrumpido) que permanezcan inactivos y que luego elimine todos los elementos restantes de la cola. Con una verdadera estructura sin cerrojo, esto permitiría que el manejador de señales agote todos los elementos, pero esta cola podría no hacer eso en el caso de que un hilo sea interrumpido o cambiado en la región crítica.


1 En particular, en x86, esto solo usará una operación atómica para el CAS ya que el modelo de memoria es lo suficientemente fuerte como para evitar la necesidad de átomos o cercas para las otras operaciones. Los ARM recientes también pueden adquirir y lanzar de manera bastante eficiente.

Un hilo que llama a POP antes de que se complete la siguiente actualización en secuencia NO se “bloquea efectivamente” si la llamada POP devuelve FALSO inmediatamente. El hilo puede sonar y hacer otra cosa. Yo diría que esta cola califica como libre de locking.

Sin embargo, no diría que califica como una “cola”, al menos no el tipo de cola que podría publicar como una cola en una biblioteca o algo así, porque no garantiza muchos de los comportamientos que normalmente puede esperar de una cola. En particular, puede presionar y elemento y luego tratar de NO FALLARLO, porque otro hilo está ocupado presionando un elemento anterior.

Aun así, esta cola podría ser útil en algunas soluciones sin locking para varios problemas.

Sin embargo, para muchas aplicaciones, me preocuparía la posibilidad de que los subprocesos de los consumidores se mueran de hambre mientras un subproceso de productor se anula. Tal vez liblfds hace algo al respecto?

“Sin locking” es una propiedad del algoritmo , que implementa alguna funcionalidad . La propiedad no se correlaciona con una forma, cómo la funcionalidad dada es utilizada por un progtwig.

Cuando se habla de la función mcmp_queue::enqueue , que devuelve FALSE si la cola subyacente está llena, su implementación (dada en la publicación de preguntas) está libre de lockings .

Sin embargo, la implementación de mcmp_queue::dequeue lockings sería difícil. Por ejemplo, este patrón obviamente no está libre de locking, ya que gira sobre la variable modificada por otro hilo:

 while(s.sequence_number.load(std::memory_order_acquire) == read_index); data = s.user_data; ... return data; 

La mayoría de las veces la gente usa el sistema de locking cuando realmente quieren decir sin cerradura. “sin cerradura” significa una estructura de datos o algoritmo que no usa lockings, pero no hay garantía de progreso hacia adelante. También verifica esta pregunta . Por lo tanto, la cola en liblfds no tiene cerrojo, pero como se menciona en BeeOnRope no está bloqueada.