Blocco lettura / scrittura Win32 utilizzando solo sezioni critiche

StackOverflow https://stackoverflow.com/questions/1008726

Domanda

Devo implementare un blocco di lettura / scrittura in C ++ usando l'API Win32 come parte di un progetto al lavoro. Tutte le soluzioni esistenti utilizzano oggetti kernel (semafori e mutex) che richiedono un cambio di contesto durante l'esecuzione. Questo è troppo lento per la mia applicazione.

Vorrei implementarne uno usando solo sezioni critiche, se possibile. Il blocco non deve essere sicuro, ma solo sicuro per i thread. Qualche idea su come procedere?

È stato utile?

Soluzione

Non penso che ciò possa essere fatto senza usare almeno un oggetto a livello di kernel (Mutex o Semaphore), perché è necessario l'aiuto del kernel per rendere il blocco del processo chiamante fino a quando il blocco non è disponibile.

Le sezioni critiche forniscono il blocco, ma l'API è troppo limitata. per esempio. non puoi prendere un CS, scoprire che è disponibile un blocco di lettura ma non un blocco di scrittura e attendere che l'altro processo termini la lettura (perché se l'altro processo ha la sezione critica bloccherà altri lettori che sono sbagliati e se non il tuo processo non si bloccherà ma gira, bruciando i cicli della CPU.)

Tuttavia, ciò che puoi fare è usare un blocco spin e tornare a un mutex ogni volta che c'è contesa. La sezione critica viene implementata in questo modo. Vorrei prendere un'implementazione della sezione critica esistente e sostituire il campo PID con lettore e amp; lo scrittore conta.

Altri suggerimenti

Se è possibile scegliere come target Vista o versione successiva, è necessario utilizzare di SRWLock . Sono leggeri come le sezioni critiche, interamente in modalità utente quando non c'è contesa.

Il blog di Joe Duffy contiene alcune recenti sull'implementazione di diverse tipi di blocchi lettore / scrittore non bloccanti. Questi blocchi ruotano, quindi non sarebbero appropriati se si intende fare molto lavoro mentre si tiene il blocco. Il codice è C #, ma dovrebbe essere semplice da trasferire a nativo.

Puoi implementare un blocco lettore / scrittore usando sezioni ed eventi critici - devi solo mantenere uno stato sufficiente per segnalare l'evento solo quando necessario per evitare una chiamata in modalità kernel non necessaria.

Vecchia domanda, ma questo dovrebbe funzionare. Non ruota in contesa. I lettori hanno un costo aggiuntivo limitato se hanno poca o nessuna contesa, perché SetEvent è chiamato pigramente (guarda la cronologia delle modifiche per una versione più pesante che non ha questa ottimizzazione). 

#include <windows.h>

typedef struct _RW_LOCK {
    CRITICAL_SECTION countsLock;
    CRITICAL_SECTION writerLock;
    HANDLE noReaders;
    int readerCount;
    BOOL waitingWriter;
} RW_LOCK, *PRW_LOCK;

void rwlock_init(PRW_LOCK rwlock)
{
    InitializeCriticalSection(&rwlock->writerLock);
    InitializeCriticalSection(&rwlock->countsLock);

    /*
     * Could use a semaphore as well.  There can only be one waiter ever,
     * so I'm showing an auto-reset event here.
     */
    rwlock->noReaders = CreateEvent (NULL, FALSE, FALSE, NULL);
}

void rwlock_rdlock(PRW_LOCK rwlock)
{
    /*
     * We need to lock the writerLock too, otherwise a writer could
     * do the whole of rwlock_wrlock after the readerCount changed
     * from 0 to 1, but before the event was reset.
     */
    EnterCriticalSection(&rwlock->writerLock);
    EnterCriticalSection(&rwlock->countsLock);
    ++rwlock->readerCount;
    LeaveCriticalSection(&rwlock->countsLock);
    LeaveCriticalSection(&rwlock->writerLock);
}

int rwlock_wrlock(PRW_LOCK rwlock)
{
    EnterCriticalSection(&rwlock->writerLock);
    /*
     * readerCount cannot become non-zero within the writerLock CS,
     * but it can become zero...
     */
    if (rwlock->readerCount > 0) {
        EnterCriticalSection(&rwlock->countsLock);

        /* ... so test it again.  */
        if (rwlock->readerCount > 0) {
            rwlock->waitingWriter = TRUE;
            LeaveCriticalSection(&rwlock->countsLock);
            WaitForSingleObject(rwlock->noReaders, INFINITE);
        } else {
            /* How lucky, no need to wait.  */
            LeaveCriticalSection(&rwlock->countsLock);
        }
    }

    /* writerLock remains locked.  */
}

void rwlock_rdunlock(PRW_LOCK rwlock)
{
    EnterCriticalSection(&rwlock->countsLock);
    assert (rwlock->readerCount > 0);
    if (--rwlock->readerCount == 0) {
        if (rwlock->waitingWriter) {
            /*
             * Clear waitingWriter here to avoid taking countsLock
             * again in wrlock.
             */
            rwlock->waitingWriter = FALSE;
            SetEvent(rwlock->noReaders);
        }
    }
    LeaveCriticalSection(&rwlock->countsLock);
}

void rwlock_wrunlock(PRW_LOCK rwlock)
{
    LeaveCriticalSection(&rwlock->writerLock);
}

Puoi ridurre il costo per i lettori utilizzando un singolo CRITICAL_SECTION :

  • untsLock è sostituito con writerLock in rdlock e rdunlock

  • rwlock- > waitingWriter = FALSE è rimosso in wrunlock

  • il corpo di wrlock è cambiato in 

    EnterCriticalSection(&rwlock->writerLock);
rwlock->waitingWriter = TRUE;
while (rwlock->readerCount > 0) {
    LeaveCriticalSection(&rwlock->writerLock);
    WaitForSingleObject(rwlock->noReaders, INFINITE);
    EnterCriticalSection(&rwlock->writerLock);
}
rwlock->waitingWriter = FALSE;

/* writerLock remains locked.  */

Tuttavia, questo perde in modo equo, quindi preferisco la soluzione di cui sopra.

Dai un'occhiata al libro " Programmazione concorrente su Windows " ; che ha molti esempi di riferimento diversi per i blocchi lettore / scrittore.

Dai un'occhiata a spin_rw_mutex da Thread Building Blocks ...

di Intel
  

spin_rw_mutex è rigorosamente in terra dell'utente   e impiega spin-wait per il blocco

Questa è una vecchia domanda ma forse qualcuno lo troverà utile. Abbiamo sviluppato un open-source RWLock per Windows ad alte prestazioni, che automaticamente usa Vista + SRWLock Michael citato se disponibile, o altrimenti ricade su un'implementazione dello spazio utente.

Come bonus aggiuntivo, ci sono quattro diversi "gusti". di esso (anche se è possibile attenersi a quello di base, che è anche il più veloce), ognuno con più opzioni di sincronizzazione. Inizia con il RWLock () di base che non è rientrante, limitato alla sincronizzazione a processo singolo e senza scambio di blocchi di lettura / scrittura a un RWLock IPC a processo completo a tutti gli effetti con rientro supportare e leggere / scrivere de-elevazione.

Come accennato, si sostituiscono dinamicamente ai blocchi di lettura + scrittura di Vista + slim per le migliori prestazioni quando possibile, ma non devi preoccuparti di tutto ciò poiché tornerà a un'implementazione pienamente compatibile su Windows XP e simili.

Se conosci già una soluzione che solo utilizza i mutex, dovresti essere in grado di modificarlo per utilizzare invece le sezioni critiche.

Abbiamo lanciato il nostro usando due sezioni critiche e alcuni segnalini. Si adatta alle nostre esigenze - abbiamo un numero di scrittori molto basso, gli scrittori hanno la precedenza sui lettori, ecc. Non sono libero di pubblicare i nostri, ma posso dire che è possibile senza mutex e semafori.

Ecco la soluzione più piccola che potrei trovare:

http://www.baboonz.org/rwlock.php

E incollato alla lettera: 

/** A simple Reader/Writer Lock.

This RWL has no events - we rely solely on spinlocks and sleep() to yield control to other threads.
I don't know what the exact penalty is for using sleep vs events, but at least when there is no contention, we are basically
as fast as a critical section. This code is written for Windows, but it should be trivial to find the appropriate
equivalents on another OS.

**/
class TinyReaderWriterLock
{
public:
    volatile uint32 Main;
    static const uint32 WriteDesireBit = 0x80000000;

    void Noop( uint32 tick )
    {
        if ( ((tick + 1) & 0xfff) == 0 )     // Sleep after 4k cycles. Crude, but usually better than spinning indefinitely.
            Sleep(0);
    }

    TinyReaderWriterLock()                 { Main = 0; }
    ~TinyReaderWriterLock()                { ASSERT( Main == 0 ); }

    void EnterRead()
    {
        for ( uint32 tick = 0 ;; tick++ )
        {
            uint32 oldVal = Main;
            if ( (oldVal & WriteDesireBit) == 0 )
            {
                if ( InterlockedCompareExchange( (LONG*) &Main, oldVal + 1, oldVal ) == oldVal )
                    break;
            }
            Noop(tick);
        }
    }

    void EnterWrite()
    {
        for ( uint32 tick = 0 ;; tick++ )
        {
            if ( (tick & 0xfff) == 0 )                                     // Set the write-desire bit every 4k cycles (including cycle 0).
                _InterlockedOr( (LONG*) &Main, WriteDesireBit );

            uint32 oldVal = Main;
            if ( oldVal == WriteDesireBit )
            {
                if ( InterlockedCompareExchange( (LONG*) &Main, -1, WriteDesireBit ) == WriteDesireBit )
                    break;
            }
            Noop(tick);
        }
    }

    void LeaveRead()
    {
        ASSERT( Main != -1 );
        InterlockedDecrement( (LONG*) &Main );
    }
    void LeaveWrite()
    {
        ASSERT( Main == -1 );
        InterlockedIncrement( (LONG*) &Main );
    }
};

Guarda qui la mia implementazione:

https://github.com/coolsoftware/LockLib

VRWLock è una classe C ++ che implementa un singolo writer - logica a più lettori.

Guarda anche il progetto di test TestLock.sln.

UPD. Di seguito è riportato il semplice codice per lettore e scrittore: 

LONG gCounter = 0;

// reader

for (;;) //loop
{
  LONG n = InterlockedIncrement(&gCounter); 
  // n = value of gCounter after increment
  if (n <= MAX_READERS) break; // writer does not write anything - we can read
  InterlockedDecrement(&gCounter);
}
// read data here
InterlockedDecrement(&gCounter); // release reader

// writer

for (;;) //loop
{
  LONG n = InterlockedCompareExchange(&gCounter, (MAX_READERS+1), 0); 
  // n = value of gCounter before attempt to replace it by MAX_READERS+1 in InterlockedCompareExchange
  // if gCounter was 0 - no readers/writers and in gCounter will be MAX_READERS+1
  // if gCounter was not 0 - gCounter stays unchanged
  if (n == 0) break;
}
// write data here
InterlockedExchangeAdd(&gCounter, -(MAX_READERS+1)); // release writer

La classe VRWLock supporta il conteggio degli spin e il conteggio dei riferimenti specifici del thread che consente di rilasciare blocchi di thread terminati.

Ho scritto il seguente codice usando solo sezioni critiche. 

class ReadWriteLock {
    volatile LONG writelockcount;
    volatile LONG readlockcount;
    CRITICAL_SECTION cs;
public:
    ReadWriteLock() {
        InitializeCriticalSection(&cs);
        writelockcount = 0;
        readlockcount = 0;
    }
    ~ReadWriteLock() {
        DeleteCriticalSection(&cs);
    }
    void AcquireReaderLock() {        
    retry:
        while (writelockcount) {
            Sleep(0);
        }
        EnterCriticalSection(&cs);
        if (!writelockcount) {
            readlockcount++;
        }
        else {
            LeaveCriticalSection(&cs);
            goto retry;
        }
        LeaveCriticalSection(&cs);
    }
    void ReleaseReaderLock() {
        EnterCriticalSection(&cs);
        readlockcount--;
        LeaveCriticalSection(&cs);
    }
    void AcquireWriterLock() {
        retry:
        while (writelockcount||readlockcount) {
            Sleep(0);
        }
        EnterCriticalSection(&cs);
        if (!writelockcount&&!readlockcount) {
            writelockcount++;
        }
        else {
            LeaveCriticalSection(&cs);
            goto retry;
        }
        LeaveCriticalSection(&cs);
    }
    void ReleaseWriterLock() {
        EnterCriticalSection(&cs);
        writelockcount--;
        LeaveCriticalSection(&cs);
    }
};

Per eseguire uno spin-wait, commenta le righe con Sleep (0).

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top