Blocco lettura/scrittura Win32 utilizzando solo sezioni critiche

Question

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

Vorrei implementarne uno utilizzando solo le sezioni critiche, se possibile. Il blocco non deve essere sicuro, ma solo sicuro. Qualche idea su come andare su questo?

Answer 1

Non penso che questo possa essere fatto senza utilizzare almeno un oggetto a livello kernel (Mutex o Semaphore), perché è necessario l'aiuto del kernel per rendere il blocco del processo chiamante finché 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 finisca di leggere (perché se l'altro processo ha la sezione critica bloccherà altri lettori che sono sbagliati, e se quindi il processo non bloccherà ma girerà, bruciando i cicli della CPU.)

Tuttavia, ciò che si può fare è usare un blocco di selezione e ricorrere a un mutex ogni volta che c'è un conflitto. La sezione critica è essa stessa implementata in questo modo. Prenderò un'implementazione di sezione critica esistente e sostituirò il campo PID con lettori separati & conteggi scrittore.

Answer 2

Se si è già a conoscenza di una soluzione che solo usa utilizza i mutex, si dovrebbe essere in grado di modificarla per utilizzare invece le sezioni critiche.

Abbiamo eseguito il rollover utilizzando due sezioni critiche e alcuni contatori. Si adatta alle nostre esigenze: abbiamo un conto scrittore 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.

Answer 3

Dai un'occhiata al libro "Concurrent Programming on Windows" che ha molti esempi di riferimento diversi per le serrature di lettore/scrittore.

Answer 4

Partenza il spin_rw_mutex da Intel Thread Building Blocks ...

spin_rw_mutex è rigorosamente in user-land e impiega spin-attesa per il blocco

Answer 5

Se è possibile destinare Vista o maggiore, si dovrebbe usare il built-in SRWLock's. Sono leggeri come sezioni critiche, interamente user-mode quando non ci sono conflitti.

Il blog di Joe Duffy ha alcuni recenti entries sull'implementazione di diversi tipi di blocchi di lettore/scrittore non bloccanti. Queste serrature fanno girare, quindi non sarebbero appropriate se si intende fare un sacco di lavoro mentre si tiene il lucchetto. Il codice è C#, ma dovrebbe essere semplice da portare in nativo.

È possibile implementare un blocco lettore/scrittore utilizzando sezioni ed eventi critici: è sufficiente mantenere uno stato sufficiente per segnalare l'evento solo quando necessario per evitare una chiamata in modalità kernel non necessaria.

Answer 6

Ecco la soluzione più piccola che ho potuto venire con:

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

e incollato testualmente:

/** 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); 
    } 
}; 

Answer 7

vecchia questione, ma questo è qualcosa che dovrebbe funzionare. Non gira su contesa. I lettori possono sostenere costi aggiuntivi limitati 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); 
} 

Si potrebbe diminuire il costo per i lettori, utilizzando un unico CRITICAL_SECTION:

• countsLock è sostituito con writerLock in rdlock e rdunlock

• rwlock->waitingWriter = FALSE viene rimosso in wrunlock

• Il corpo del 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 tutta onestà, quindi preferisco la soluzione di cui sopra.

Answer 8

Questa è una vecchia domanda, ma forse qualcuno la troverà utile. Abbiamo sviluppato una performance ad alte prestazioni, open-source RWLock for Windows, che utilizza automaticamente Vista + SRWLockMichael mentioned se disponibile, o altrimenti ricade su un'implementazione dello spazio utente.

Come bonus aggiuntivo, ci sono quattro diversi "sapori" di esso (anche se è possibile attenersi a quello di base, che è anche il più veloce), ognuno con maggiori opzioni di sincronizzazione. Si inizia con il numero di serie RWLock() che non è rientraneo, limitato alla sincronizzazione a processo singolo e nessuno scambio di blocchi di lettura/scrittura su un RWLock IPC cross-process a pieno titolo con supporto per il reingresso e dislivello di lettura/scrittura.

Come accennato, si passano dinamicamente ai lucchetti Vista + Slim per ottenere le migliori prestazioni quando possibile, ma non ci si deve preoccupare affatto di ciò, poiché ricadrebbe su un'implementazione completamente compatibile su Windows XP e il suo genere.

Answer 9

Guarda la mia applicazione qui:

https://github.com/coolsoftware/LockLib

VRWLock è una classe C++ che implementa solo scrittore - la logica più lettori.

Guarda anche test progetto TestLock.sln.

UPD. Sotto è il codice semplice per il 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 

classe VRWLock supporta conteggio rotazione e conteggio di riferimento specifico filo che permette di rilasciare i blocchi di fili terminati.

Answer 10

Ho scritto il seguente codice utilizzando 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, commentare le linee con Sleep (0).