La eficiencia de usar un pthread_rwlock cuando hay muchos lectores

Question

Mientras estoy buscando la página man de la función pthread_rwlock_unlock, noté que el func devolverá EPERM si el hilo que llama no tiene la propiedad de un rwlock.

Como el rdlock permite que varios hilos obtengan el bloqueo, debe existir una estructura de datos como un enlace o matriz para almacenar el propietario de un rwlock específico.

Aquí viene la pregunta:

El rwlock está diseñado para lograr eficiencia en la operación de lectura es mucho más frecuente que las operaciones de escritura, pero si hay gran número de diferentes hilos consiguió el bloqueo de lectura, cada vez que llamo a pthread_rwlock_unlock(), lleva tiempo averiguar el tiempo en que el hilo de llamada es un propietario válido. ¿cuál es la complejidad de tiempo de este escenario ..

Muchas gracias chicos :)

Answer 1

n.m ha proporcionado una buena respuesta. Su suposición de estructuras para mantener la propiedad del bloqueo es incorrecta en la implementación de Linux etiquetada y es similar al método de conteo n.m. toca sobre.

Aquí es una versión editada del tipo de pthread_rwlock_t /usr/include/bits/pthreadtypes.h

struct 
    { 
    int __lock; 
    unsigned int __nr_readers; 
    unsigned int __readers_wakeup; 
    unsigned int __writer_wakeup; 
    unsigned int __nr_readers_queued; 
    unsigned int __nr_writers_queued; 
    int __writer; 
    int __shared; 
    unsigned int __flags; 
    } __data; 

Se puede ver los campos de recuentos. También pthread_rwlock_unlock.c no devuelve EPERM y la mayor parte del trabajo gira en torno a la verificación de la propiedad del escritor en pthread_rwlock_wrlock.c y pthread_rwlock_rdlock.c.

Puede probar esto con un pequeño programa para declarar e inicializar un bloqueo y luego simplemente desbloquearlo.

Por lo tanto, la complejidad del tiempo parece ser lo suficientemente constante como para constar en esta implementación, pero se gana al rescatar algunas funciones que puede haber pensado o quería tener.

Answer 2

Tenga en cuenta que la aplicación no está obligado a devolver EPERM. El resultado de desbloquear el bloqueo de otra persona no está definido, como lo especifica el estándar.

Es fácil de lograr O (1) si el bloqueo solo almacena un recuento de uso en lugar de una lista de hilos propietarios. Si la implementación insiste en verificar la propiedad del bloqueo, puede hacer que el hilo recuerde los bloqueos que posee. El número de tales bloqueos normalmente debería ser pequeño. Incluso si no lo es, normalmente se adquieren múltiples bloqueos en el orden LIFO, por lo que el caso común está cubierto por una pila de bloqueos propios en el hilo.