c++ multithreading synchronization readwritelock

c++ - ¿Cómo hacer un bloqueo de lectura múltiple/escritura simple a partir de primitivas de sincronización más básicas?



multithreading synchronization (8)

Hemos descubierto que tenemos varios puntos en nuestro código donde las lecturas concurrentes de datos protegidos por un mutex son bastante comunes, mientras que las escrituras son raras. Nuestras mediciones parecen decir que el uso de un mutex simple dificulta seriamente el rendimiento del código que lee esos datos. Entonces, lo que necesitaríamos es un mutex de lectura múltiple / escritura única. Sé que esto se puede construir sobre primitivas más simples, pero antes de intentarlo, prefiero pedir el conocimiento existente:

¿Cuál es una forma aprobada para construir un bloqueo de lectura múltiple / escritura simple a partir de primitivas de sincronización más simples?

Tengo una idea de cómo hacerlo, pero prefiero tener respuestas imparciales con lo que (probablemente erróneamente) se me ocurrió. (Nota: lo que espero es una explicación de cómo hacerlo, probablemente en pseudocódigo, no una implementación completa. Ciertamente puedo escribir el código yo mismo).

Advertencias:

  • Esto debe tener un rendimiento razonable. (Lo que tengo en mente requeriría dos operaciones de bloqueo / desbloqueo por acceso. Ahora, eso podría no ser lo suficientemente bueno, pero la necesidad de muchas de ellas parece irrazonable).

  • Comúnmente, las lecturas son más numerosas, pero las escrituras son más importantes y sensibles al rendimiento que las lecturas. Los lectores no deben matar de hambre a los escritores.

  • Estamos atascados en una plataforma incrustada bastante antigua (variante patentada de VxWorks 5.5), con un compilador bastante antiguo (GCC 4.1.2) y boost 1.52, a excepción de la mayoría de las partes de boost que dependen de POSIX, porque POSIX no está completamente implementado en esa plataforma Las primitivas de bloqueo disponibles son básicamente varios tipos de semáforos (binarios, contables, etc.), además de los cuales ya hemos creado mutexes, variables de condiciones y monitores.

  • Este es IA32, de un solo núcleo.

Las lecturas concurrentes de datos protegidos por un mutex son bastante comunes, mientras que las escrituras son raras

Eso suena como un escenario ideal para la RCU de espacio de usuario :

URCU es similar a su contraparte de kernel de Linux, proporcionando un reemplazo para el bloqueo de lector-escritor, entre otros usos. Esta similitud continúa con los lectores que no se sincronizan directamente con los actualizadores de RCU, lo que hace que las rutas de código del lado de lectura de RCU sean extremadamente rápidas, al tiempo que permite que los lectores de RCU avancen de manera útil incluso cuando se ejecutan simultáneamente con los actualizadores de RCU, y viceversa.

A primera vista, pensé que reconocía esta respuesta como el mismo algoritmo que introdujo Alexander Terekhov. Pero después de estudiarlo, creo que es defectuoso. Es posible que dos escritores esperen simultáneamente en m_exclusive_cond . Cuando uno de esos escritores se despierta y obtiene el bloqueo exclusivo, establecerá exclusive_waiting_blocked = false en el unlock , estableciendo así el mutex en un estado inconsistente. Después de eso, es probable que el mutex esté conectado.

N2406 , que primero propuso std::shared_mutex contiene una implementación parcial, que se repite a continuación con una sintaxis actualizada.

class shared_mutex { mutex mut_; condition_variable gate1_; condition_variable gate2_; unsigned state_; static const unsigned write_entered_ = 1U << (sizeof(unsigned)*CHAR_BIT - 1); static const unsigned n_readers_ = ~write_entered_; public: shared_mutex() : state_(0) {} // Exclusive ownership void lock(); bool try_lock(); void unlock(); // Shared ownership void lock_shared(); bool try_lock_shared(); void unlock_shared(); }; // Exclusive ownership void shared_mutex::lock() { unique_lock<mutex> lk(mut_); while (state_ & write_entered_) gate1_.wait(lk); state_ |= write_entered_; while (state_ & n_readers_) gate2_.wait(lk); } bool shared_mutex::try_lock() { unique_lock<mutex> lk(mut_, try_to_lock); if (lk.owns_lock() && state_ == 0) { state_ = write_entered_; return true; } return false; } void shared_mutex::unlock() { { lock_guard<mutex> _(mut_); state_ = 0; } gate1_.notify_all(); } // Shared ownership void shared_mutex::lock_shared() { unique_lock<mutex> lk(mut_); while ((state_ & write_entered_) || (state_ & n_readers_) == n_readers_) gate1_.wait(lk); unsigned num_readers = (state_ & n_readers_) + 1; state_ &= ~n_readers_; state_ |= num_readers; } bool shared_mutex::try_lock_shared() { unique_lock<mutex> lk(mut_, try_to_lock); unsigned num_readers = state_ & n_readers_; if (lk.owns_lock() && !(state_ & write_entered_) && num_readers != n_readers_) { ++num_readers; state_ &= ~n_readers_; state_ |= num_readers; return true; } return false; } void shared_mutex::unlock_shared() { lock_guard<mutex> _(mut_); unsigned num_readers = (state_ & n_readers_) - 1; state_ &= ~n_readers_; state_ |= num_readers; if (state_ & write_entered_) { if (num_readers == 0) gate2_.notify_one(); } else { if (num_readers == n_readers_ - 1) gate1_.notify_one(); } }

El algoritmo se deriva de un antiguo grupo de noticias publicado por Alexander Terekhov. No mata de hambre ni a lectores ni a escritores.

Hay dos "puertas", gate1_ y gate2_ . Los lectores y escritores tienen que pasar gate1_ , y pueden bloquearse al intentar hacerlo. Una vez que un lector pasa la gate1_ , ha bloqueado la gate1_ . Los lectores pueden pasar gate1_ siempre que no haya un número máximo de lectores con propiedad, y siempre que un escritor no haya pasado gate1_ .

Solo un escritor a la vez puede pasar gate1_ . Y un escritor puede pasar gate1_ incluso si los lectores tienen la propiedad. Pero una vez pasado gate1_ , un escritor todavía no tiene la propiedad. Primero debe pasar gate2_ . Un escritor no puede pasar gate2_ hasta que todos los lectores con propiedad lo hayan abandonado. Recuerde que los nuevos lectores no pueden pasar gate1_ mientras un escritor está esperando en gate2_ . Y tampoco puede un nuevo escritor pasar gate1_ mientras un escritor está esperando en gate2_ .

La característica de que tanto los lectores como los escritores están bloqueados en gate1_ con gate1_ (casi) idénticos impuestos para gate1_ , es lo que hace que este algoritmo sea justo tanto para lectores como para escritores, sin pasar hambre.

El "estado" mutex se mantiene intencionalmente en una sola palabra para sugerir que el uso parcial de la atómica (como optimización) para ciertos cambios de estado es una posibilidad (es decir, para un "camino rápido" no pretendido). Sin embargo, esa optimización no se demuestra aquí. Un ejemplo sería si un hilo de escritor pudiera cambiar atómicamente el state_ de 0 a write_entered luego obtener el bloqueo sin tener que bloquear o incluso bloquear / desbloquear mut_ . Y unlock() podría implementarse con una tienda atómica. Etc. Estas optimizaciones no se muestran aquí porque son mucho más difíciles de implementar correctamente de lo que esta simple descripción hace que suene.

Ahora que Microsoft ha abierto el código fuente .NET, puede ver su implementación ReaderWRiterLockSlim .

No estoy seguro de que las primitivas más básicas que usan estén disponibles para usted, algunas de ellas también forman parte de la biblioteca .NET y su código también está disponible.

Microsoft ha dedicado mucho tiempo a mejorar el rendimiento de sus mecanismos de bloqueo, por lo que este puede ser un buen punto de partida.

Como siempre, la mejor solución dependerá de los detalles. Un bloqueo de giro de lectura y escritura puede ser lo que está buscando , pero otros enfoques, como la actualización de lectura-copia, como se sugirió anteriormente, podrían ser una solución, aunque en una antigua plataforma integrada, la memoria adicional utilizada podría ser un problema. Con escrituras raras, a menudo organizo el trabajo usando un sistema de tareas de tal manera que las escrituras solo pueden ocurrir cuando no hay lecturas de esa estructura de datos, pero esto depende del algoritmo.

Esta es una respuesta simplificada basada en mis encabezados Boost (llamaría a Boost de una manera aprobada ). Solo requiere Variables de condición y Mutexes. Lo reescribí usando primitivas de Windows porque las encuentro descriptivas y muy simples, pero veo esto como Pseudocódigo.

Esta es una solución muy simple, que no admite cosas como la actualización de mutex o las operaciones try_lock (). Puedo agregarlos si quieres. También saqué algunos adornos como deshabilitar interrupciones que no son estrictamente necesarias.

Además, vale la pena echarle un vistazo a boost/thread/pthread/shared_mutex.hpp (esto se basa en eso). Es legible para los humanos.

class SharedMutex { CRITICAL_SECTION m_state_mutex; CONDITION_VARIABLE m_shared_cond; CONDITION_VARIABLE m_exclusive_cond; size_t shared_count; bool exclusive; // This causes write blocks to prevent further read blocks bool exclusive_wait_blocked; SharedMutex() : shared_count(0), exclusive(false) { InitializeConditionVariable (m_shared_cond); InitializeConditionVariable (m_exclusive_cond); InitializeCriticalSection (m_state_mutex); } ~SharedMutex() { DeleteCriticalSection (&m_state_mutex); DeleteConditionVariable (&m_exclusive_cond); DeleteConditionVariable (&m_shared_cond); } // Write lock void lock(void) { EnterCriticalSection (&m_state_mutex); while (shared_count > 0 || exclusive) { exclusive_waiting_blocked = true; SleepConditionVariableCS (&m_exclusive_cond, &m_state_mutex, INFINITE) } // This thread now ''owns'' the mutex exclusive = true; LeaveCriticalSection (&m_state_mutex); } void unlock(void) { EnterCriticalSection (&m_state_mutex); exclusive = false; exclusive_waiting_blocked = false; LeaveCriticalSection (&m_state_mutex); WakeConditionVariable (&m_exclusive_cond); WakeAllConditionVariable (&m_shared_cond); } // Read lock void lock_shared(void) { EnterCriticalSection (&m_state_mutex); while (exclusive || exclusive_waiting_blocked) { SleepConditionVariableCS (&m_shared_cond, m_state_mutex, INFINITE); } ++shared_count; LeaveCriticalSection (&m_state_mutex); } void unlock_shared(void) { EnterCriticalSection (&m_state_mutex); --shared_count; if (shared_count == 0) { exclusive_waiting_blocked = false; LeaveCriticalSection (&m_state_mutex); WakeConditionVariable (&m_exclusive_cond); WakeAllConditionVariable (&m_shared_cond); } else { LeaveCriticalSection (&m_state_mutex); } } };

Comportamiento

De acuerdo, existe cierta confusión sobre el comportamiento de este algoritmo, así que así es como funciona.

Durante un bloqueo de escritura : tanto los lectores como los escritores están bloqueados.

Al final de un Bloqueo de escritura : los hilos del lector y un hilo del escritor competirán para ver cuál comienza.

Durante un bloqueo de lectura : los escritores están bloqueados. Los lectores también están bloqueados si y solo si un escritor está bloqueado.

En el lanzamiento del último bloqueo de lectura, los hilos del lector y un hilo del escritor competirán para ver cuál comienza.

Esto podría causar que los lectores maten de hambre a los escritores si el procesador con frecuencia cambia de contexto a un subproceso m_shared_cond antes de un m_exclusive_cond durante la notificación, pero sospecho que el problema es teórico y no práctico ya que es el algoritmo de Boost.

Hay algunos buenos trucos que puedes hacer para ayudar.

Primero, buen desempeño . VxWorks es notable por sus muy buenos tiempos de cambio de contexto. Cualquiera que sea la solución de bloqueo que use, probablemente involucrará semáforos. No tendría miedo de usar semáforos (plural) para esto, están bastante bien optimizados en VxWorks, y los rápidos tiempos de cambio de contexto ayudan a minimizar la degradación del rendimiento al evaluar muchos estados de semáforos, etc.

También me olvidaría de usar los semáforos POSIX, que simplemente se colocarán en capas sobre los propios semáforos de VxWork. VxWorks proporciona conteo nativo, semáforos binarios y mutex; usar el que se adapte lo hace todo un poco más rápido. Los binarios pueden ser bastante útiles a veces; publicado muchas veces, nunca exceda el valor de 1.

Segundo, las escrituras son más importantes que las lecturas . Cuando tuve este tipo de requisito en VxWorks y he estado usando un semáforo (s) para controlar el acceso, he usado la prioridad de la tarea para indicar qué tarea es más importante y debería obtener el primer acceso al recurso. Esto funciona bastante bien; literalmente, todo en VxWorks es una tarea (bueno, hilo) como cualquier otra, incluidos todos los controladores de dispositivos, etc.

VxWorks también resuelve las inversiones prioritarias (el tipo de cosas que Linus Torvalds odia). Entonces, si implementa su bloqueo con un semáforo (s), puede confiar en el programador del sistema operativo para generar lectores de menor prioridad si están bloqueando un escritor de mayor prioridad. Puede conducir a un código mucho más simple, y también está aprovechando al máximo el sistema operativo.

Entonces, una solución potencial es tener un solo semáforo de conteo VxWorks que proteja el recurso, inicializado a un valor igual al número de lectores. Cada vez que un lector quiere leer, toma el semáforo (reduciendo el recuento en 1. Cada vez que se realiza una lectura, publica el semáforo, aumentando el recuento en 1. Cada vez que el escritor quiere escribirlo toma el semáforo n (n = número de lectores) veces, y lo publica n veces cuando haya terminado. Finalmente, haga que la tarea del escritor tenga mayor prioridad que cualquiera de los lectores, y confíe en el tiempo de cambio de contexto rápido del SO y la inversión de prioridad.

Recuerde que está programando en un sistema operativo en tiempo real, no en Linux. Tomar / publicar un semáforo nativo de VxWorks no implica la misma cantidad de tiempo de ejecución que un acto similar en Linux, aunque incluso Linux es bastante bueno en estos días (estoy usando PREEMPT_RT hoy en día). Se puede confiar en que el planificador VxWorks y todos los controladores de dispositivo se comportarán. Incluso puede hacer que su tarea de escritor sea la más alta prioridad en todo el sistema si lo desea, ¡incluso más que todos los controladores de dispositivos!

Para ayudar con las cosas, también considere lo que están haciendo cada uno de sus hilos. VxWorks le permite indicar que una tarea está / no está usando la FPU. Si está utilizando rutinas nativas VxWorks TaskSpawn en lugar de pthread_create, entonces tiene la oportunidad de especificar esto. Lo que significa es que si su hilo / tarea no está haciendo matemática de punto flotante, y lo ha dicho como tal en su llamada a TaskSpawn, los tiempos de cambio de contexto serán aún más rápidos porque el programador no se molestará en preservar / restaurar el estado de la FPU.

Esta es una posibilidad razonable de ser la mejor solución en la plataforma en la que está desarrollando. Está jugando con las fortalezas del sistema operativo (semáforos rápidos, tiempos de cambio de contexto rápidos) sin introducir una carga de código adicional para recrear una solución alternativa (y posiblemente más elegante) que comúnmente se encuentra en otras plataformas.

Tercero, atascado con el viejo GCC y el viejo Boost . Básicamente, no puedo ayudar más allá de las sugerencias de bajo valor sobre cómo llamar a WindRiver y discutir comprar una actualización. Personalmente, cuando he estado programando para VxWorks, he usado la API nativa de VxWork en lugar de POSIX. Ok, entonces el código no es muy portátil, pero terminó siendo rápido; POSIX es simplemente una capa encima de la API nativa de todos modos y eso siempre ralentizará las cosas.

Dicho esto, el conteo POSIX y los semáforos mutex son muy similares a los semáforos nativos de conteo y mutex de VxWork. Eso probablemente significa que las capas POSIX no son muy gruesas.

Notas generales sobre la programación para VxWorks

Depuración Siempre intenté utilizar las herramientas de desarrollo (Tornado) disponibles para Solaris. Este es, con mucho, el mejor entorno de depuración de subprocesos múltiples que he encontrado. ¿Por qué? Le permite iniciar múltiples sesiones de depuración, una para cada hilo / tarea en el sistema. Termina con una ventana de depuración por hilo, y está depurando cada uno de forma individual e independiente. Pase por encima de una operación de bloqueo, esa ventana de depuración se bloquea. Mueva el foco del mouse a otra ventana de depuración, pase por encima de la operación que liberará el bloque y observe cómo la primera ventana completa su paso.

Terminas con muchas ventanas de depuración, pero es, con mucho, la mejor manera de depurar cosas de subprocesos múltiples. Lo hizo muy fácil escribir cosas realmente complejas y ver problemas. Puede explorar fácilmente las diferentes interacciones dinámicas en su aplicación porque tenía un control simple y poderoso sobre lo que cada hilo está haciendo en cualquier momento.

Irónicamente, la versión para Windows de Tornado no te permitió hacer esto; una sola ventana de depuración miserable por sistema, como cualquier otro IDE viejo y aburrido como Visual Studio, etc. Nunca he visto que incluso los IDE modernos estén tan cerca de ser tan buenos como Tornado en Solaris para la depuración de subprocesos múltiples.

Discos duros Si sus lectores y escritores están usando archivos en el disco, considere que VxWorks 5.5 es bastante antiguo. Cosas como NCQ no serán compatibles. En este caso, mi solución propuesta (descrita anteriormente) podría hacerse mejor con un solo semáforo de mutex para evitar que varios lectores se tropiecen entre sí en su lucha por leer diferentes partes del disco. Depende de lo que estén haciendo exactamente sus lectores, pero si están leyendo datos contiguos de un archivo, esto evitaría mover la cabeza de lectura / escritura de un lado a otro de la superficie del disco (muy lento).

En mi caso, estaba usando este truco para dar forma al tráfico a través de una interfaz de red; cada tarea enviaba un tipo diferente de datos, y la prioridad de la tarea reflejaba la prioridad de los datos en la red. Era muy elegante, ningún mensaje estaba fragmentado, pero los mensajes importantes lograron que los leones compartieran el ancho de banda disponible.

Parece que solo tiene mutex y condition_variable como primitivas de sincronización. por lo tanto, escribo un bloqueo de lector-escritor aquí, que mata de hambre a los lectores. utiliza un mutex, dos conditional_variable y tres enteros.

readers - readers in the cv readerQ plus the reading reader writers - writers in cv writerQ plus the writing writer active_writers - the writer currently writing. can only be 1 or 0.

Hambre de hambre a los lectores de esta manera. Si hay varios escritores que desean escribir, los lectores nunca tendrán la oportunidad de leer hasta que todos los escritores terminen de escribir. Esto se debe a que los lectores posteriores deben verificar la variable writers . Al mismo tiempo, la variable active_writers garantizará que solo un escritor pueda escribir a la vez.

class RWLock { public: RWLock() : shared() , readerQ(), writerQ() , active_readers(0), waiting_writers(0), active_writers(0) {} void ReadLock() { std::unique_lock<std::mutex> lk(shared); while( waiting_writers != 0 ) readerQ.wait(lk); ++active_readers; lk.unlock(); } void ReadUnlock() { std::unique_lock<std::mutex> lk(shared); --active_readers; lk.unlock(); writerQ.notify_one(); } void WriteLock() { std::unique_lock<std::mutex> lk(shared); ++waiting_writers; while( active_readers != 0 || active_writers != 0 ) writerQ.wait(lk); ++active_writers; lk.unlock(); } void WriteUnlock() { std::unique_lock<std::mutex> lk(shared); --waiting_writers; --active_writers; if(waiting_writers > 0) writerQ.notify_one(); else readerQ.notify_all(); lk.unlock(); } private: std::mutex shared; std::condition_variable readerQ; std::condition_variable writerQ; int active_readers; int waiting_writers; int active_writers; };