c++ - Garantías de progreso sin bloqueo

multithreading algorithm

Question

Como anécdota, descubrí que muchos programadores creen erróneamente que "sin bloqueo" simplemente significa "programación concurrente sin mutexes". Por lo general, también hay un malentendido correlacionado de que el propósito de escribir código sin bloqueo es un mejor rendimiento concurrente. Por supuesto, la definición correcta de sin bloqueo en realidad se trata de garantías de progreso . Un algoritmo sin bloqueo garantiza que al menos un subproceso pueda avanzar sin importar lo que estén haciendo otros subprocesos.

Esto significa que un algoritmo sin bloqueo nunca puede tener código donde un subproceso depende de otro subproceso para continuar. Por ejemplo, el código sin bloqueo no puede tener una situación en la que el subproceso A establece un indicador, y luego el subproceso B sigue en bucle mientras espera que el subproceso A desactive el indicador. Un código como este básicamente está implementando un bloqueo (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 sin bloqueo o no, porque la noción de "hacer progresos" a veces me parece subjetiva.

Uno de estos casos está en la biblioteca de concurrencia (bien considerada, afaik), liblfds . Estaba estudiando la implementación de una cola limitada de múltiples productores / consumidores en liblfds: la implementación es muy sencilla, pero realmente no puedo decir si debería calificar como sin bloqueo.

El algoritmo relevante está en lfds711_queue_bmm_enqueue.c . Liblfds utiliza barreras atómicas y de memoria personalizadas, pero el algoritmo es lo suficientemente simple como para que yo lo describa en un párrafo más o menos.

La cola en sí es una matriz contigua acotada (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 de ABA).

El algoritmo PUSH es el siguiente:

1. CARGA write_index el write_index
2. Intente reservar un espacio en la cola en write_index % queue_size utilizando un bucle write_index que intenta 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 real usa atómicos personalizados y barreras de memoria, por lo que para mayor claridad sobre este algoritmo, lo he traducido brevemente a atómicos estándar de C ++ (no probados) 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 hacer POP de un elemento del espacio en read_index no podrá hacerlo hasta que observe que el número de sequence_number del espacio es igual a read_index + 1 .

Bien, entonces no hay mutexes aquí, y el algoritmo probablemente funciona bien (es solo un CAS para PUSH y POP), pero ¿está libre de bloqueo? La razón por la que no está claro para mí es porque la definición de "hacer progresos" 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 el espacio nunca puede ser POP hasta que el hilo de empuje llegue a actualizar el número de secuencia. Esto significa que un subproceso POP que desea mostrar un valor depende de que el subproceso PUSH 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 "hacer progresos".

En general, los algoritmos verdaderamente sin bloqueo implican una fase en la que un subproceso anticipado realmente intenta ASISTIR al otro subproceso para completar una operación. Entonces, para estar verdaderamente libre de bloqueos, creo que un hilo POP que observa un PUSH en progreso necesitaría intentar completar el PUSH, y luego 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 EMPUJE 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 queda dormido durante 1,000 años, o de lo contrario queda programado en el olvido, el hilo POP no puede hacer nada excepto informar continuamente que la cola está VACÍA.

Entonces, ¿se ajusta esto a la definición de sin bloqueo? Desde una perspectiva, puede argumentar que el hilo POP siempre puede progresar, porque siempre puede informar que la cola está VACÍA (que es al menos alguna 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 PUSH concurrente.

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

Answer 1

"Sin bloqueo" es una propiedad del algoritmo , que implementa algunas funcionalidades . La propiedad no se correlaciona con una forma, cómo un programa utiliza la funcionalidad dada.

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 bloqueos .

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

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

Answer 2

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

Una estructura no tiene bloqueo si solo se puede suspender indefinidamente cualquier subproceso en cualquier punto, mientras que los subprocesos restantes dejan la estructura utilizable.

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 subproceso que ha logrado incrementar m_write_increment , pero aún no ha escrito s.sequence_number deja el contenedor en lo que pronto será un estado inutilizable. Si tal hilo es eliminado, 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 s.sequence_number asociado), pero básicamente funciona como un mutex por elemento. Por lo tanto, el fracaso solo se hace evidente para los escritores una vez que hayas recorrido un bucle y un nuevo escritor intente obtener el mutex, pero de hecho, todos los escritores posteriores no han podido insertar su elemento en la cola ya que ningún lector lo verá.

Ahora, esto no significa que esta sea una mala implementación de una cola concurrente. Para algunos usos, puede comportarse principalmente como si estuviera libre de bloqueo. Por ejemplo, esta estructura puede tener la mayoría de las propiedades útiles de rendimiento de una estructura verdaderamente libre de bloqueo, pero al mismo tiempo carece de algunas de las propiedades útiles de corrección . Básicamente, el término sin bloqueo generalmente implica un conjunto completo de propiedades, solo un subconjunto de las cuales generalmente será importante para un uso particular. Miremos uno por uno y veamos cómo funciona esta estructura. Los clasificaremos en términos generales en categorías funcionales y de rendimiento.

Actuación

Rendimiento incontenible

El rendimiento no pretendido o "mejor de los casos" es importante para muchas estructuras. Si bien necesita una estructura concurrente para la corrección, generalmente intentará diseñar su aplicación para que la contención se mantenga al mínimo, por lo que el costo no contenido a menudo es importante. Algunas estructuras sin bloqueo ayudan aquí, al reducir la cantidad de costosas operaciones atómicas en la ruta rápida no syscall , o 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 ( memory_order_acquire load y memory_order_release store) ¹ , y un poco más de gastos generales.

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 también tienen una sobrecarga no despreciable.

Por lo tanto, espero que esta cola funcione razonablemente bien en la ruta rápida no prevista.

Rendimiento contenido

Una ventaja de las estructuras sin bloqueo es que a menudo permiten una mejor escala cuando una estructura está muy contenta. Esto no es necesariamente una ventaja inherente : algunas estructuras basadas en bloqueos con múltiples bloqueos o bloqueos de lectura-escritura pueden exhibir escalas que coinciden o exceden algunos enfoques sin bloqueos, pero generalmente es el caso que las estructuras sin bloqueos exhiben una escala mejor que Una alternativa simple de un candado para gobernarlos a todos.

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

Tenga en cuenta que una cola es generalmente 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 sin contención si se accede a diferentes elementos.

Inmunidad de cambio de contexto

Una ventaja de rendimiento de las estructuras sin bloqueo que está relacionada con la definición central 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 subprocesos ejecutables >> núcleos disponibles), un subproceso puede desconectarse durante cientos de milisegundos o segundos. Durante este tiempo, los mutadores concurrentes bloquearán e incurrirán en costos de programación adicionales (o girarán, lo que también puede producir un mal comportamiento). Aunque tal "programación desafortunada" puede ser rara, cuando ocurre, todo el sistema puede incurrir en un pico de latencia grave.

Las estructuras sin bloqueo evitan esto, ya que no existe una "región crítica" en la que un subproceso se pueda cambiar de contexto y, posteriormente, bloquee el progreso de otros subprocesos.

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 subproceso en la región crítica entre la actualización de m_write_index y la escritura del número de secuencia, otros subprocesos pueden continuar push elementos a la cola siempre que no se envuelvan completamente al elemento en progreso desde 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 se cambia de contexto y la plenitud promedio, la cola lo hará aparecen rápidamente vacías para todos los hilos de consumo, incluso si hay muchos elementos agregados 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 detenerse por completo cuando esto ocurre. A este respecto, ¡la cola no se ve muy libre de bloqueo!

Aspectos Funcionales

Terminación de hilo asíncrono

En ventaja de las estructuras sin bloqueo, son seguras para su uso por subprocesos que pueden cancelarse asincrónicamente o pueden terminar excepcionalmente en la región crítica. Cancelar un hilo en cualquier punto deja la estructura es un estado consistente.

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

Acceso a la cola desde interrupción o señal

Una ventaja relacionada es que las estructuras sin bloqueo 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 es principalmente compatible con este caso de uso. Incluso si la señal o la interrupción se produce cuando otro subproceso está en la región crítica, el código asincrónico puede push un elemento a la cola (que solo se verá más tarde al consumir subprocesos) y aún puede sacar un elemento de la cola.

El comportamiento no es tan completo como una verdadera estructura sin bloqueo: imagine un controlador de señal con una forma de decirle a los hilos restantes de la aplicación (que no sea el interrumpido) que se detengan y que luego drene todos los elementos restantes de la cola. Con una verdadera estructura sin bloqueo, esto permitiría que el manejador de señal drene por completo todos los elementos, pero esta cola podría no hacerlo en el caso de que un hilo se interrumpiera o se desconectara en la región crítica.

¹ 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 atómica o cercado para las otras operaciones. ARM reciente también puede adquirir y liberar de manera bastante eficiente.

Answer 3

Hice una verificación formal de este mismo código usando Spin hace un par de años para un curso de prueba de concurrencia y definitivamente no está libre de bloqueo.

El hecho de que no haya un "bloqueo" explícito no significa que esté libre de bloqueo. Cuando se trata de razonar sobre las condiciones de progreso, piénselo desde la perspectiva de un hilo individual:

• Bloqueo / bloqueo: si otro subproceso se programa y esto puede bloquear mi progreso, entonces está bloqueando.

• Sin bloqueo / sin bloqueo: si finalmente puedo progresar en ausencia de contención de otros subprocesos, entonces es como máximo sin bloqueo.

• Si ningún otro hilo puede bloquear mi progreso indefinidamente, entonces no tendrá que esperar.

Answer 4

La mayoría de las veces las personas usan sin cerradura cuando realmente quieren decir sin cerradura. sin bloqueo significa una estructura de datos o algoritmo que no usa bloqueos, pero no hay garantía para el progreso hacia adelante. También revise esta pregunta . Por lo tanto, la cola en liblfds no tiene bloqueos, pero como mencionó BeeOnRope, no está libre de bloqueos.

Answer 5

Soy el autor de liblfds.

El OP es correcto en su descripción de esta cola.

Es la estructura de datos única en la biblioteca que no está libre de bloqueo.

Esto se describe en la documentación de la cola;

http://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Queue_%28bounded,_many_producer,_many_consumer%29#Lock-free_Specific_Behaviour

"Sin embargo, debe entenderse que esto no es en realidad una estructura de datos sin bloqueo".

Esta cola es una implementación de una idea de Dmitry Vyukov (1024cores.net) y solo me di cuenta de que no estaba libre de bloqueos mientras hacía que el código de prueba funcionara.

Para entonces estaba funcionando, así que lo incluí.

Tengo algún pensamiento para eliminarlo, ya que no está libre de bloqueo.

Answer 6

Un hilo que llama a POP antes de que se complete la próxima actualización en secuencia NO se "bloquea efectivamente" si la llamada POP devuelve FALSE inmediatamente. El hilo puede salir y hacer otra cosa. Yo diría que esta cola califica como sin bloqueo.

Sin embargo, no diría que califica como una "cola", al menos no el tipo de cola que podría publicar como cola en una biblioteca o algo así, porque no garantiza muchos de los comportamientos que normalmente puede esperar de una cola. En particular, puede EMPUJAR y elemento y luego intentar y FALLAR a POP, porque algún otro hilo está ocupado empujando un elemento anterior.

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

Sin embargo, para muchas aplicaciones, me preocuparía la posibilidad de que los hilos de los consumidores se mueran de hambre mientras que un hilo del productor está vacío. Tal vez liblfds hace algo al respecto?