c++ - programa - problemas clasicos de sincronizacion
Miles de bloqueos lector/escritor en un solo proceso (3)
Actualmente estoy diseñando una aplicación de servidor C ++ multiplataforma (Linux / Windows) con un patrón de sincronización a gran escala. Yo uso internamente boost :: thread como una abstracción de los subprocesos específicos del sistema operativo. Mi problema es proteger una matriz de datos, cada elemento de la matriz está protegido por un bloqueo de lector / escritor independiente .
Mi matriz contiene 4096 elementos . Teniendo en cuenta la solución del problema "escritores prioritarios lectores-escritores" que se presenta en el " Pequeño libro de semáforos " (página 85), mi aplicación necesitaría 5 semáforos por elemento de matriz. Esto da un total de aproximadamente 20000 semáforos (o, de manera equivalente, 20000 mutexes + 20000 variables de condición).
Una especificidad adicional de mi aplicación es que, en un momento determinado, la mayoría de los semáforos no están activos (normalmente hay alrededor de 32 subprocesos de "clientes" en espera / señalización en los miles de semáforos). Tenga en cuenta que dado que todo el servidor se ejecuta en un solo proceso, utilizo semáforos livianos basados en subprocesos ( no semáforos entre procesos).
Mi pregunta es doble:
¿Se recomienda crear un total de 20000 semáforos en Linux y en Windows para un único proceso? Bueno, por supuesto, supongo que este no es el caso ...
Si no se recomienda esta práctica, ¿qué técnica podría utilizar para reducir el número de semáforos reales, por ejemplo, para crear un conjunto de N "semáforos emulados" en la parte superior de 1 semáforo real ? Supongo que esta sería una solución interesante, porque la mayoría de mis semáforos están inactivos en un momento dado.
¡Gracias por adelantado!
Resumen de las respuestas hasta el momento
- No se recomienda el uso de miles de semáforos, especialmente desde una perspectiva multiplataforma. Y así, incluso si no son semáforos entre procesos (todavía consumen identificadores en Windows).
- Una forma directa de resolver mi problema es dividir mi matriz en, por ejemplo, 64 subcampos de 16 elementos, y asociar cada uno de estos subarreglos con un solo bloqueo de lectura / escritura . Desafortunadamente, esto introduce mucha contención (1 escritor bloquearía las lecturas a 15 elementos).
Buscando en el código fuente de Boost, he encontrado que:
- La implementación de "boost :: mutex" no envuelve objetos CRITICAL_SECTION bajo Windows (pero CreateEvent y ReadWriteBarrier),
- "boost :: shared_mutex" usa CreateSemaphore en Windows (que son objetos pesados e interprocesos), y
- "boost :: shared_mutex" no ajusta "pthread_rwlock_t" en Linux.
Las razones para esto no me parecen claras. En particular, el uso de objetos entre procesos para "boost :: shared_mutex" en Windows me parece no óptimo.
Resumen de las preguntas abiertas hasta el momento
- ¿Cómo puedo crear un conjunto de N "semáforos emulados" en la parte superior de 1 semáforo real, manteniendo la contención entre los semáforos emulados lo más pequeño posible?
- ¿Cómo se comparan "boost :: mutex" y "boost :: shared_mutex" con sus contrapartes nativas (CRITICAL_SECTION y pthread_rwlock_t)?
Esto no es recomendado No deberías hacer esto porque en Windows consumiría 1 Handle Object por semáforo. Un proceso solo puede administrar una cantidad específica de objetos Handles. Thread / Process y otros objetos de Windows pueden necesitar usar objetos Handle y se bloquearán si no pueden. Esto es similar en Linux con el concepto de descriptor de archivo.
Divida sus 4096 elementos en 30 conjuntos (por ejemplo) de 140 elementos y asigne a cada grupo 140 un solo semáforo. Luego 30 hilos (en este ejemplo) intentarán acceder a esos 30 conjuntos y se sincronizarán en función de cada semáforo de 140 grupos.
Te diré lo que pienso desde la perspectiva de Windows. Tengo mucha experiencia en escribir aplicaciones de servidor para Windows.
En primer lugar, no hay ningún problema para crear semáforos de 20k para un solo proceso. Es un objeto kernel bastante liviano. Incluso semáforos "entre procesos".
Veo sin embargo otro problema con su diseño. Debe saber que cada operación que realice en un objeto kernel (como semáforo / mutex) implica una pesada transacción en modo kernel (también conocida como llamada al sistema). Cada llamada puede costar alrededor de 2k ciclos de CPU, incluso si no hay colisiones en absoluto.
De modo que puede encontrarse en una situación en la que la mayor parte del tiempo del procesador se gasta en la invocación de los métodos de sincronización.
Por el contrario, para sincronizar los hilos, uno puede usar operaciones entrelazadas. Cuestan mucho menos (en general, decenas de ciclos de CPU).
También hay un objeto llamado sección crítica . Es una especie de híbrido del operando entrelazado y un objeto kernel (que se usa si hay una colisión real). Debería verificar por cuánto tiempo generalmente bloquea sus elementos. Si generalmente se trata de bloqueos de corta duración, solo use las secciones críticas, olvídese de los sofisticados bloqueos de lectura y escritura.
Si, no obstante, maneja bloqueos de larga duración y necesita un bloqueo de lectura y escritura, y ve que gasta una gran cantidad de CPU en la transacción en modo kernel, considere crear su propio híbrido (o intente encontrarlo) como la implementación de dicho bloqueo.
En Linux definitivamente no debes implementar los bloqueos tú mismo, pero usa posix_rwlock_t .
Tener una matriz de 4096 elementos de este tipo no debería presentar ningún problema en particular. Las estructuras de bloqueo POSIX se implementan de manera bastante eficiente en Linux. En particular, utilizan operaciones atómicas cuando es posible en la "ruta rápida" y solo entran en las llamadas al sistema (especialmente para un FUTEX) cuando hay congestión en ese bloqueo particular. Por lo tanto, si lo implementa con cuidado, de modo que cualquier hilo solo contenga 1 o 2 bloqueos a la vez, la restricción en Linux solo vendrá dada por su número total de hilos de trabajo y no por la cantidad de objetos en sí.