Cómo sincronizar el acceso a muchos objetos

Question

Tengo un grupo de subprocesos con algunos subprocesos (por ejemplo, tantos como núcleos) que funcionan en muchos objetos, digamos miles de objetos. Normalmente le daría a cada objeto un mutex para proteger el acceso a sus partes internas, lo bloquearé cuando estoy trabajando y luego lo liberaré. Cuando dos hilos intentan acceder al mismo objeto, uno de los hilos tiene que esperar.

Ahora quiero ahorrar algunos recursos y sea escalable, ya que puede haber miles de objetos, y aún así sólo una mano llena de hilos. Estoy pensando en un diseño de clase donde el subproceso tiene algún tipo de objeto mutex o de bloqueo, y asigna el bloqueo al objeto cuando se debe acceder al objeto. Esto ahorraría recursos, ya que solo tengo tantos objetos de bloqueo como thread.

Ahora viene la parte de programación, donde quiero transferir este diseño a código, pero no sé exactamente por dónde empezar. Estoy programando en C++ y quiero usar clases de Boost siempre que sea posible, pero las clases auto escritas que manejan estos requisitos especiales están bien. ¿Cómo implementaría esto?

Mi primera idea fue tener un :: objeto mutex boost por hilo, y cada objeto tiene un boost :: shared_ptr que inicialmente está desarmado (o NULL). Ahora cuando quiero acceder al objeto, lo bloqueo creando un objeto scoped_lock y lo asigno a shared_ptr. Cuando el shared_ptr ya está configurado, espero en el bloqueo actual. Esta idea suena como un montón de condiciones de carrera, así que de alguna manera la abandoné. ¿Hay alguna otra forma de lograr este diseño? Una forma completamente diferente?

Editar: La descripción anterior es un poco abstracta, así que permítanme agregar un ejemplo específico. Imagine un mundo virtual con muchos objetos (piense> 100.000). Los usuarios que se muevan en el mundo podrían moverse por el mundo y modificar objetos (por ejemplo, disparar flechas contra monstruos). Cuando solo uso un hilo, estoy bien con una cola de trabajo donde las modificaciones a los objetos están en cola. Sin embargo, quiero un diseño más escalable. Si hay 128 procesadores centrales disponibles, quiero usar los 128, así que use esa cantidad de hilos, cada uno con colas de trabajos. Una solución sería usar separación espacial, p. usa un candado para un área Esto podría reducir el número de bloqueos utilizados, pero estoy más interesado si hay un diseño que ahorre la mayor cantidad de bloqueos posible.

Answer 1

Puede usar un conjunto de exclusión mutua en lugar de asignar un mutex por recurso o un mutex por subproceso. Como se solicitan mutexes, primero verifique el objeto en cuestión. Si ya tiene un mutex etiquetado, bloquee en ese mutex. De lo contrario, asigne un mutex a ese objeto y señálelo, sacando el mutex del grupo. Una vez que el mutex está desmarcado, borre la ranura y devuelva el mutex al grupo.

Answer 2

Si te sigo correctamente ....

struct table_entry { 
    void * pObject;  // substitute with your object 
    sem_t sem;   // init to empty 
    int  nPenders; // init to zero 
}; 

struct table_entry * table; 

object_lock (void * pObject) { 
    goto label;     // yes it is an evil goto 

    do { 
     pEntry->nPenders++; 
     unlock (mutex); 
     sem_wait (sem); 
label: 
     lock (mutex); 
     found = search (table, pObject, &pEntry); 
    } while (found); 

    add_object_to_table (table, pObject); 
    unlock (mutex); 
} 

object_unlock (void * pObject) { 
    lock (mutex); 
    pEntry = remove (table, pObject); // assuming it is in the table 
    if (nPenders != 0) { 
     nPenders--; 
     sem_post (pEntry->sem); 
    } 
    unlock (mutex); 
} 

Lo anterior debería funcionar, pero tiene algunos inconvenientes potenciales, tales como ...

1. Una posible cuello de botella en la búsqueda.
2. Hilo de hambre. No hay garantía de que un hilo determinado salga del bucle do-while en object_lock().

Sin embargo, dependiendo de su configuración, estas posibles desventajas podrían no ser importantes.

Espero que esto ayude.

Answer 3

Dudo que haya alguna forma limpia de lograr su diseño. El problema de asignar el mutex al objeto parece que modificará el contenido del objeto, por lo que necesita un mutex para proteger el objeto de varios subprocesos que intentan asignar mutexes al mismo tiempo, para mantener su primera asignación de mutex seguro, necesitarías otro mutex para proteger al primero.

Personalmente, creo que lo que estás tratando de curar no es un problema en primer lugar. Antes de dedicar mucho tiempo a tratar de solucionarlo, realizaba un poco de prueba para ver qué (si es que algo) pierde con solo incluir un Mutex en cada objeto y terminar con él. Dudo que tengas que ir más allá de eso.

Si necesita hacer más que eso, yo pensaría en tener un grupo de objetos seguro para subprocesos, y cada vez que un subproceso quiere operar en un objeto, tiene que obtener la propiedad de ese grupo. La llamada para obtener propiedad liberaría cualquier objeto actualmente propiedad del subproceso solicitante (para evitar interbloqueos) y luego le otorgaría la propiedad del objeto solicitado (bloqueando si el objeto es actualmente propiedad de otro subproceso). El administrador del grupo de objetos probablemente funcionaría en un hilo por sí mismo, serializando automáticamente todos los accesos a la administración del grupo, para que el código de administración del grupo pudiera evitar tener que bloquear el acceso a las variables que le dicen quién posee ese objeto y demás.

Answer 4

Personalmente, esto es lo que haría. Tiene una cantidad de objetos, todos probablemente tengan una clave de algún tipo, digamos nombres. Así que toma la siguiente lista de nombres de las personas:

Bill Clinton 
Bill Cosby 
John Doe 
Abraham Lincoln 
Jon Stewart 

Así que ahora debe crear una serie de listas: una por cada letra del alfabeto, por ejemplo. Bill y Bill irían en una lista, John, Jon Abraham, solos.

Cada lista se asignaría a un hilo específico - el acceso tendría que pasar por ese hilo (tendría que ordenar las operaciones a un objeto en ese hilo - un gran uso de los funtores). Entonces sólo tiene dos lugares para bloquear:

thread() { 
     loop { 
     scoped_lock lock(list.mutex); 
     list.objectAccess(); 
     } 
} 

list_add() { 
     scoped_lock lock(list.mutex); 
     list.add(..); 
} 

Mantener las cerraduras a un mínimo, y si usted todavía está haciendo un montón de bloqueo, se puede optimizar el número de iteraciones a realizar en los objetos en sus listas de 1 a 5, para minimizar la cantidad de tiempo dedicado a la adquisición de bloqueos. Si su conjunto de datos crece o está codificado por número, puede hacer cualquier cantidad de datos segregados para mantener el bloqueo al mínimo.

Answer 5

Me parece que necesita una cola de trabajo. Si el bloqueo en la cola de trabajo se convirtiera en un cuello de botella, podría cambiarlo para que cada hilo tuviera su propia cola de trabajo, entonces algún tipo de planificador le daría al objeto entrante el hilo con la menor cantidad de trabajo por hacer. El siguiente nivel es el robo de trabajo donde los hilos que se han quedado sin trabajo miran las colas de trabajo de otros hilos. (Ver la biblioteca de bloques de creación de hilos de Intel)

Answer 6

Sin saberlo, lo que estabas buscando es Software Memoria transaccional (STM).

Los sistemas STM se administran internamente con los bloqueos necesarios para garantizar las propiedades de ACI (atómico, consistente, aislado). Esta es una actividad de investigación. Puede encontrar muchas bibliotecas de STM; en particular, estoy trabajando en Boost.STM (La biblioteca aún no se ha probado, y la documentación no está actualizada, pero puedes jugar con ella). También hay algunos compiladores que están introduciendo TM en compiladores de Intel, IBM y SUN. Usted puede obtener el borrador de la especificación de here

La idea es identificar las regiones críticas de la siguiente manera

transaction { 
    // transactional block 
} 

y dejar que el sistema STM para gestionar los bloqueos necesarios en la medida en que asegura las propiedades de ACI.

El enfoque Boost.STM permite escribir cosas como

int inc_and_ret(stm::object<int>& i) { 
    BOOST_STM_TRANSACTION { 
    return ++i; 
    } BOOST_STM_END_TRANSACTION 
} 

Se puede ver a la pareja BOOST_STM_TRANSACTION/BOOST_STM_END_TRANSACTION como una forma de determinar un bloqueo de ámbito implícita.

El costo de esta pseudo transparencia es de 4 bytes de metadatos para cada objeto stm ::.

Incluso si esto está lejos de su diseño inicial, realmente creo que es lo que estaba detrás de su objetivo y el diseño inicial.

Answer 7

Aquí tenemos un interés en un modelo similar. Una solución que hemos considerado es tener un bloqueo global (o compartido) pero utilizado de la siguiente manera:

• Un indicador que se puede establecer atómicamente en el objeto. Si configura el indicador, entonces es dueño del objeto.
• Realiza su acción y luego restablece la variable y la señal (transmisión) una variable de condición.
• Si la adquisición falló, espere en la variable de condición. Cuando se transmite, verifica su estado para ver si está disponible.

Aunque parece que debemos bloquear el mutex cada vez que cambiemos el valor de esta variable. Por lo tanto, hay un montón de bloqueo y desbloqueo, pero no es necesario mantener el bloqueo durante un período prolongado.

Con un candado "compartido" tiene una cerradura que se aplica a varios elementos. Utilizaría algún tipo de función "hash" para determinar qué variable mutex/condición se aplica a esta entrada en particular.

Answer 8

Responda la siguiente pregunta en la publicación de @ JohnDibling.

¿implementó esta solución? Tengo un problema similar y me gustaría saber cómo resolvió liberar el mutex en el grupo. Quiero decir, ¿cómo sabes que cuando liberas el mutex, puedes volver a ponerlo en cola de forma segura si no sabes si hay otro hilo reteniéndolo?

por @LeonardoBernardini

---

Actualmente estoy tratando de resolver el mismo tipo de problema. Mi enfoque es crear tu propia estructura mutex (llámala counterMutex) con un campo de contador y el campo mutex de recursos reales. Por lo tanto, cada vez que intente bloquear el counterMutex, primero incrementa el contador y luego bloquea el mutex subyacente. Cuando hayas terminado con esto, reduces el coutner y desbloqueas el mutex, luego de eso revisa el contador para ver si es cero lo que significa que ningún otro hilo está tratando de adquirir el bloqueo. Si es así, vuelva a colocar el counterMutex en la piscina. ¿Hay una condición de carrera al manipular el contador? Tu puedes preguntar. La respuesta es no. Recuerde que tiene un mutex global para garantizar que solo un hilo pueda acceder al coutnerMutex a la vez.