Win32 Bloqueo de lectura / escritura usando solo secciones críticas

Question

Tengo que implementar un bloqueo de lectura / escritura en C ++ usando la API Win32 como parte de un proyecto en el trabajo. Todas las soluciones existentes usan objetos del núcleo (semáforos y mutexes) que requieren un cambio de contexto durante la ejecución. Esto es demasiado lento para mi aplicación.

Me gustaría implementar uno usando solo secciones críticas, si es posible. El bloqueo no tiene que ser seguro para el proceso, solo para subprocesos. ¿Alguna idea sobre cómo hacer esto?

Answer 1

No creo que esto se pueda hacer sin usar al menos un objeto de nivel de núcleo (Mutex o Semáforo), porque necesita la ayuda del núcleo para hacer que el proceso de llamada se bloquee hasta que el bloqueo esté disponible.

Las secciones críticas proporcionan bloqueo, pero la API es demasiado limitada. p.ej. no puede tomar un CS, descubrir que hay un bloqueo de lectura disponible pero no un bloqueo de escritura, y espere a que el otro proceso termine de leer (porque si el otro proceso tiene la sección crítica, bloqueará a otros lectores, lo cual es incorrecto, y si entonces, su proceso no se bloqueará, sino que girará, quemando ciclos de CPU.

Sin embargo, lo que puede hacer es usar un bloqueo de giro y recurrir a un mutex siempre que haya contención. La sección crítica se implementa de esta manera. Tomaría una implementación de sección crítica existente y reemplazaría el campo PID con un lector & amp; escritor cuenta.

Answer 2

Si puede apuntar a Vista o superior, debe usar el SRWLock . Son ligeros como las secciones críticas, completamente en modo de usuario cuando no hay contención.

El blog de Joe Duffy tiene algunas entradas recientes sobre la implementación de diferentes tipos de bloqueos de bloqueo de lector / escritor. Estas cerraduras giran, por lo que no serían apropiadas si pretendes hacer mucho trabajo mientras sostienes la cerradura. El código es C #, pero debe ser sencillo de portar a nativo.

Puede implementar un bloqueo de lector / escritor utilizando secciones y eventos críticos; solo necesita mantener el estado suficiente para señalar el evento solo cuando sea necesario para evitar una llamada innecesaria en modo kernel.

Answer 3

Antigua pregunta, pero esto es algo que debería funcionar. No gira en la contienda. Los lectores incurren en un costo adicional limitado si tienen poca o ninguna disputa, porque SetEvent se llama perezosamente (mira el historial de edición para una versión más pesada que no tenga esta optimización).

#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);
}

Puede disminuir el costo para los lectores utilizando una sola CRITICAL_SECTION :

• countLock se reemplaza por writerLock en rdlock y rdunlock

• rwlock- > waitingWriter = FALSE se elimina en wrunlock

• el cuerpo de wrlock ha cambiado a

  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.  */
  

Sin embargo, esto pierde justicia, por lo que prefiero la solución anterior.

Answer 4

Eche un vistazo al libro " Programación concurrente en Windows " ; que tiene muchos ejemplos de referencia diferentes para bloqueos de lector / escritor.

Answer 5

Consulte spin_rw_mutex de bloques de creación de hilos ...

de Intel

  

spin_rw_mutex está estrictamente en tierra de usuario   y emplea spin-wait para bloquear

Answer 6

Esta es una vieja pregunta, pero tal vez alguien lo encuentre útil. Desarrollamos un de código abierto RWLock de código abierto para Windows de alto rendimiento que automáticamente usa Vista + SRWLock Michael mencionó si está disponible, o de lo contrario recurre a una implementación de espacio de usuario.

Como un bono adicional, hay cuatro diferentes "sabores" (aunque puedes seguir con el básico, que también es el más rápido), cada uno con más opciones de sincronización. Comienza con el RWLock () básico que no es reentrante, se limita a la sincronización de un solo proceso y no intercambia los bloqueos de lectura / escritura a un RWLock IPC de proceso cruzado completo con reingreso soporte y lectura / escritura de elevación.

Como se mencionó, cambian dinámicamente a los bloqueos delgados de lectura y escritura de Vista + para obtener el mejor rendimiento cuando sea posible, pero no tiene que preocuparse por eso, ya que recurrirá a una implementación totalmente compatible en Windows XP y sus gustos.

Answer 7

Si ya conoce una solución que solo usa mutexes, debería poder modificarla para usar secciones críticas.

Desarrollamos el nuestro usando dos secciones críticas y algunos contadores. Se adapta a nuestras necesidades: tenemos un recuento de escritores muy bajo, los escritores tienen prioridad sobre los lectores, etc. No tengo libertad para publicar el nuestro, pero puedo decir que es posible sin mutexes y semáforos.

Answer 8

Aquí está la solución más pequeña que se me ocurrió:

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

Y pegado literalmente:

/** 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 9

Mira mi implementación aquí:

https://github.com/coolsoftware/LockLib

VRWLock es una clase C ++ que implementa escritor único - lógica de múltiples lectores.

Mire también el proyecto de prueba TestLock.sln.

UPD. A continuación se muestra el código simple para lector y escritor:

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 clase VRWLock admite el recuento de giros y el recuento de referencias específicas de subprocesos que permite liberar bloqueos de subprocesos terminados.

Answer 10

Escribí el siguiente código usando solo secciones críticas.

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

Para realizar un spin-wait, comente las líneas con Sleep (0).