Leggi il mutex di scrittura in C++

Question

Questa è una domanda di intervista. Come implementate un mutex di lettura/scrittura? Ci saranno più thread di lettura e scrittura su una risorsa. Non sono sicuro di come farlo. Se ci sono informazioni necessarie, per favore fatemelo sapere.

Aggiornamento: non sono sicuro che la mia affermazione sopra sia valida/comprensibile. Ma quello che voglio veramente sapere è come implementare più letture e più scritture su un singolo oggetto in termini di mutex e altri oggetti di sincronizzazione necessari?

Answer 1

Check out Dekker's algorithm.

algoritmo di Dekker è la prima nota corretta soluzione al problema reciproca esclusione concorrente programmazione. La soluzione è attribuita al matematico olandese Th. J. Dekker di Edsger W. Dijkstra nel suo manoscritto su processi sequenziali cooperanti . Consente a due thread di condividere una risorsa monouso senza il conflitto , utilizzando solo la memoria condivisa per la comunicazione .

Si noti che l'algoritmo di Dekker utilizza una tecnica spinlock (non una busy waiting).
(Th. La soluzione di J. Dekker, citato da E. W. Dijkstra nel suo EWD1303 paper)

Answer 2

La risposta breve è che è sorprendentemente difficile da rotolare il proprio blocco di lettura/scrittura. È molto facile perdere un problema di temporizzazione molto sottile che potrebbe causare un deadlock, due thread che pensano di avere un blocco "esclusivo", ecc.

In poche parole, è necessario tenere un conteggio del numero di lettori attivi in qualsiasi momento particolare. Solo quando il numero di lettori attivi è zero, si dovrebbe concedere un accesso in scrittura del thread. Ci sono alcune scelte progettuali sul fatto che i lettori o gli scrittori abbiano la priorità. (Spesso, si vuole dare agli scrittori la priorità, partendo dal presupposto che la scrittura viene eseguita meno frequentemente.) La parte (sorprendentemente) difficile consiste nel garantire che nessuno scrittore abbia accesso quando ci sono lettori, o viceversa.

C'è un eccellente articolo MSDN, "Compound Win32 Synchronization Objects" che consente di creare un blocco lettore/scrittore. Inizia semplice, poi diventa più complicato per gestire tutti i casi d'angolo. Una cosa che si è distinta è che hanno mostrato un campione che sembrava perfettamente buono, quindi avrebbero spiegato perché non avrebbe funzionato. Se non avessero indicato i problemi, forse non l'avresti mai notato. Vale la pena leggere.

Spero che questo sia utile.

Answer 3

Questa sembra una domanda piuttosto difficile per un'intervista; Non vorrei "implementare" un mutex in lettura/scrittura, nel senso di scriverne uno da zero - ci sono soluzioni disponibili molto più disponibili. La cosa sensata del mondo reale sarebbe usare un tipo di mutex esistente. Forse quello che volevano davvero sapere era come useresti un simile tipo?

Answer 4

Afaik è necessaria un'istruzione atomica di confronto e swap oppure è necessario disabilitare gli interrupt. Vedi Compare-and-swap su wikipedia. Almeno, è così che un sistema operativo lo implementerebbe. Se si dispone di un sistema operativo, posizionarsi su di esso e utilizzare una libreria esistente (ad esempio boost).