L'efficienza dell'utilizzo di pthread_rwlock quando ci sono molti lettori

Question

Mentre sto cercando la pagina man della funzione pthread_rwlock_unlock, ho notato che il func restituirà EPERM se il thread chiamante non ha la proprietà di un rwlock.

Poiché il rdlock consente a più thread di ottenere il blocco, deve esistere una struttura dati come un collegamento o un array per memorizzare il proprietario di uno specifico rwlock.

Qui viene la domanda:

Il rwlock è stato progettato per raggiungere l'efficienza quando l'operazione di lettura è molto più frequente di quanto le operazioni di scrittura, ma se ci sono gran numero di diversi thread ha ottenuto il blocco di lettura, ogni volta che io chiamo a pthread_rwlock_unlock(), ci vuole tempo per scoprire che il thread chiamante è un proprietario valido. qual è la complessità temporale di questo scenario ..

Grazie ragazzi :)

Answer 1

n.m ha fornito una buona risposta. La tua ipotesi di strutture per mantenere la proprietà del blocco è errata sull'implementazione di linux che hai taggato ed è simile al metodo di conteggio n.m. tocca.

Ecco una versione modificata del tipo pthread_rwlock_t da /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; 

È possibile visualizzare i campi di conteggio. Anche pthread_rwlock_unlock.c non restituisce EPERM e la maggior parte del lavoro ruota attorno al controllo della proprietà dello scrittore in pthread_rwlock_wrlock.c e pthread_rwlock_rdlock.c.

È possibile testare questo con un piccolo programma per dichiarare e inizializzare un blocco e quindi basta sbloccarlo.

Quindi la complessità del tempo sembra abbastanza vicina a essere costante in questa implementazione, ma si guadagna con il salvataggio su alcune funzionalità che si potrebbe aver pensato o voluto essere lì.

Answer 2

Nota che l'attuazione non è tenuto a restituire EPERM. Il risultato dello sblocco del blocco di qualcun altro non è definito, come specificato dallo standard.

È facile ottenere O (1) se il blocco memorizza solo un conteggio di utilizzo anziché un elenco di thread proprietari. Se l'implementazione insiste sul controllo della proprietà del blocco, può far sì che il thread ricordi i blocchi che possiede. Il numero di tali blocchi dovrebbe normalmente essere piccolo. Anche se non lo è, i blocchi multipli vengono normalmente acquisiti nell'ordine LIFO, quindi il caso comune è coperto da una pila di blocchi di proprietà nella thread.