¿Cómo hacer un locking de lectura múltiple / escritura simple desde primitivas de sincronización más básicas?

Hemos encontrado que tenemos varios lugares en nuestro código donde las lecturas simultáneas 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 al leer esos datos. Entonces, lo que necesitaríamos es un mutex de lectura múltiple / escritura simple. Sé que esto puede construirse sobre primitivas más simples, pero antes de probarme en esto, prefiero pedir el conocimiento existente:

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

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

Advertencias:

  • Esto necesita tener un rendimiento razonable. (Lo que tengo en mente requeriría dos operaciones de locking / deslocking por acceso. Ahora bien, eso podría no ser lo suficientemente bueno, pero necesitar 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 atrapados en una plataforma embebida bastante antigua (variante patentada de VxWorks 5.5), con un comstackdor bastante antiguo (GCC 4.1.2) e impulso 1.52, excepto en la mayoría de las partes de boost que dependen de POSIX, porque POSIX no está completamente implementado en esa plataforma. Las primitivas de locking disponibles básicamente son varios tipos de semáforos (binarios, contadores, etc.), sobre los cuales ya hemos creado mutexes, variables de condiciones y monitores.

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

Parece que solo tienes mutex y condition_variable como primitivas de sincronización. por lo tanto, escribo un locking lector-escritor aquí, que muere de hambre a los lectores. usa un mutex, dos conditional_variable y tres integer.

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. 

Muere 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 hayan terminado 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 lk(shared); while( waiting_writers != 0 ) readerQ.wait(lk); ++active_readers; lk.unlock(); } void ReadUnlock() { std::unique_lock lk(shared); --active_readers; lk.unlock(); writerQ.notify_one(); } void WriteLock() { std::unique_lock lk(shared); ++waiting_writers; while( active_readers != 0 || active_writers != 0 ) writerQ.wait(lk); ++active_writers; lk.unlock(); } void WriteUnlock() { std::unique_lock 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; }; 

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 locking exclusivo, establecerá exclusive_waiting_blocked = false al unlock , estableciendo así el mutex en un estado incoherente. Después de eso, es probable que el mutex sea una manguera.

N2406 , que primero propuso std::shared_mutex contiene una implementación parcial, que se repite a continuación con syntax 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 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 lk(mut_, try_to_lock); if (lk.owns_lock() && state_ == 0) { state_ = write_entered_; return true; } return false; } void shared_mutex::unlock() { { lock_guard _(mut_); state_ = 0; } gate1_.notify_all(); } // Shared ownership void shared_mutex::lock_shared() { unique_lock 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 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 _(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 la publicación de un antiguo grupo de noticias de Alexander Terekhov. No mata de hambre ni a los lectores ni a los escritores.

Hay dos “puertas”, gate1_ y gate2_ . Los lectores y escritores deben pasar gate1_ y pueden bloquearse al tratar de hacerlo. Una vez que un lector pasa el gate1_ , ha bloqueado el mutex. 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 pasada la gate1_ , un escritor aún no tiene 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 un escritor puede 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 los lectores como para los escritores, sin dejar de tener hambre.

El “estado” mutex se mantiene intencionalmente en una sola palabra para sugerir que el uso parcial de átomos (como optimización) para ciertos cambios de estado es una posibilidad (es decir, para un “camino rápido” no reconocido). Sin embargo, esa optimización no se demuestra aquí. Un ejemplo sería si un hilo de escritor podría cambiar atómicamente state_ from 0 to write_entered luego obtiene el locking 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 lo hace parecer esta simple descripción.

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 User-space RCU :

URCU es similar a su contraparte Linux-kernel, proporcionando un reemplazo para el locking de escritor-escritor, entre otros usos. Esta similitud continúa cuando los lectores no se sincronizan directamente con los actualizadores de RCU, lo que hace que las rutas de los códigos de lectura de RCU sean extremadamente rápidas, permitiendo además que los lectores de RCU avancen útil incluso cuando se ejecutan al mismo tiempo que los actualizadores de RCU, y viceversa.

Como siempre, la mejor solución dependerá de los detalles. Puede que lo que está buscando sea un locking de lectura / escritura , pero otros enfoques, como read-copy-update como se sugirió anteriormente, podrían ser una solución, aunque en una plataforma incrustada anterior, la memoria extra utilizada podría ser un problema. Con las 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.

Hay algunos buenos trucos que puedes hacer para ayudar.

Primero, buen desempeño . VxWorks se destaca por sus muy buenos tiempos de cambio de contexto. Cualquiera que sea la solución de locking que use probablemente involucre semáforos. No me da miedo usar semáforos (en 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 en el rendimiento al evaluar muchos estados de semáforos, etc.

También olvidaría el uso de semáforos POSIX, que simplemente se superpondrán a los semáforos de VxWork. VxWorks proporciona conteo nativo, semáforos binarios y mutex; usar el que se adapta 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, escribe siendo más importante que lo que lee . Cuando he tenido este tipo de requisitos en VxWorks y he estado usando semáforos 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 dispositivo, etc.

VxWorks también resuelve las inversiones prioritarias (el tipo de cosas que Linus Torvalds odia). Por lo tanto, si implementa su locking con un semáforo (s), puede confiar en el progtwigdor del sistema operativo para ayudar a los lectores de menor prioridad si bloquean a 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 posible solución es tener un solo semáforo de conteo de 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, lo que aumenta el recuento en 1. Cada vez que el escritor desea escribir toma el semáforo n (n) = número de lectores) veces, y lo publica n veces cuando finaliza. Finalmente, haga que la tarea del escritor sea de mayor prioridad que cualquiera de los lectores, y confíe en el tiempo de cambio de contexto rápido del sistema operativo y la inversión de prioridad.

Recuerde que está progtwigndo en un sistema operativo en tiempo real, no 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 progtwigdor de VxWorks y todos los controladores de dispositivo se comporten. ¡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 dispositivo!

Para ayudar con las cosas, también considere qué es 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 de TaskSpawn de VxWorks en lugar de pthread_create, entonces tiene la oportunidad de especificar esto. Lo que significa es que si su subproceso / tarea no está haciendo ninguna matemática de punto flotante, y usted ha dicho eso en su llamada a TaskSpawn, los tiempos de cambio de contexto serán aún más rápidos porque el planificador no se molestará en conservar / restablecer el estado de FPU.

Esta es una posibilidad razonable de ser la mejor solución en la plataforma en la que está desarrollando. Está jugando con los puntos fuertes 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 se encuentra comúnmente en otras plataformas.

En tercer lugar, atascado con el viejo GCC y el viejo Boost . Básicamente, no puedo ayudar más allá de sugerencias de bajo valor acerca de llamar WindRiver y discutir comprar una actualización. En términos personales, cuando he estado progtwigndo para VxWorks, he usado la API nativa de VxWork en lugar de POSIX. Ok, entonces el código no es muy portátil, pero ha terminado siendo rápido; POSIX es simplemente una capa sobre 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 al conteo nativo de VxWork y los semáforos mutex. Eso probablemente significa que las capas POSIX no son muy gruesas.

Notas generales sobre la progtwigción de VxWorks

Depuración Siempre intenté usar las herramientas de desarrollo (Tornado) disponibles para Solaris. Este es de lejos 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 subproceso / tarea en el sistema. Usted termina con una ventana de depuración por subproceso, y está depurando individual y autónomamente cada uno. Paso sobre una operación de locking, esa ventana de depuración se bloquea. Mueva el foco del mouse a otra ventana de depuración, pase sobre la operación que liberará el bloque y verá cómo la primera ventana completa su paso.

Usted termina con una gran cantidad de ventanas de depuración, pero es, de lejos, la mejor manera de solucionar problemas de subprocesos múltiples. Se hizo muy fácil escribir cosas bastante complejas y ver problemas. Puede explorar fácilmente las diferentes interacciones dinámicas en su aplicación porque tiene un control simple y todo poderoso de lo que cada hilo está haciendo en cualquier momento.

Irónicamente, la versión para Windows de Tornado no te permitió hacer esto; una miserable y única ventana de depuración por sistema, al igual que cualquier otro IDE antiguo y aburrido como Visual Studio, etc. Nunca he visto que los IDE modernos sean tan buenos como Tornado en Solaris para la depuración de subprocesos múltiples.

HardDrives Si sus lectores y escritores están usando archivos en el disco, considere que VxWorks 5.5 es bastante antiguo. Cosas como NCQ no van a ser compatibles. En este caso, mi solución propuesta (descrita anteriormente) podría realizarse mejor con un solo semáforo mutex para evitar que varios lectores se tropiecen entre sí en su lucha por leer diferentes partes del disco. Depende de lo que hagan exactamente sus lectores, pero si están leyendo datos contiguos de un archivo, esto evitaría agitar el cabezal 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. Fue muy elegante, ningún mensaje fue fragmentado, pero los mensajes importantes lograron que los leones compartieran el ancho de banda disponible.

Un algoritmo para esto basado en semáforos y mutexes se describe en Control simultáneo con lectores y escritores ; PJ Courtois, F. Heymans y DL Parnas; MBLE Research Laboratory; Bruselas, Bélgica .

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

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

Además, vale la pena comprobar 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, hay cierta confusión sobre el comportamiento de este algoritmo, así es como funciona.

Durante un locking 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 correrán para ver cuál comienza.

Durante un locking 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 locking de lectura, los hilos del lector y un hilo del escritor correrán para ver cuál comienza.

Esto podría provocar que los lectores mueran de hambre a los escritores si el contexto del procesador frecuente cambia a un hilo m_shared_cond antes de un m_exclusive_cond notificación, pero sospecho que el problema es teórico y no práctico ya que es el algoritmo de Boost.

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 utilizan estén disponibles para usted, algunas de ellas también son parte de la biblioteca .NET y su código también está disponible.

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