Win32 de leitura / gravação Bloqueio Usando apenas secções críticas

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

Pergunta

Eu tenho que implementar um bloqueio de leitura / escrita em C ++ usando a API Win32 como parte de um projeto no trabalho. Todas as soluções existentes utilizam objetos do kernel (semáforos e semáforos) que exigem uma mudança de contexto durante a execução. Este é demasiado lento para o meu pedido.

Gostaria implementar um usando apenas as seções críticas, se possível. O bloqueio não tem que ser seguro processo, apenas threadsafe. Todas as ideias sobre como ir sobre isso?

Foi útil?

Solução

Eu não acho que isso pode ser feito sem o uso de pelo menos um objeto de nível kernel (Mutex ou Semaphore), porque você precisa da ajuda do kernel para fazer o bloco processo de chamada até que o bloqueio está disponível.

As seções críticas fornecem o bloqueio, mas a API é muito limitada. por exemplo. você não pode pegar um CS, descobrir que um bloqueio de leitura está disponível, mas não um bloqueio de gravação, e esperar que o outro processo para terminar de ler (porque se o outro processo tem a seção crítica ele irá bloquear outros leitores o que é errado, e se não, então o seu processo não irá bloquear, mas rotação, queima de ciclos de CPU.)

No entanto o que você pode fazer é usar um bloqueio de rotação e cair de volta a uma exclusão mútua sempre que houver contenção. A seção crítica é em si implementado desta forma. Gostaria de ter uma implementação seção crítica existente e substituir o campo PID com leitor e escritor contagens separadas.

Outras dicas

Se você pode direcionar Vista ou superior, você deve usar o built-in de SRWLock. Eles são leves como seções críticas, inteiramente user-mode quando não há disputa.

O blog de Joe Duffy tem algum recente entradas na implementação diferente tipos de fechaduras sem bloqueio leitor / gravador. Esses bloqueios fazer rotação, de modo que não seria apropriado se você pretende fazer um monte de trabalho, mantendo o bloqueio. O código é C #, mas deve ser simples para a porta para nativa.

Você pode implementar um bloqueio de leitor / gravador usando seções e eventos críticos -. Você só precisa manter o estado suficiente apenas para sinalizar o evento quando necessário para evitar uma chamada de modo kernel desnecessário

velha questão, mas isso é algo que deve funcionar. Ele não gira em disputa. Leitores incorrer limitados custo extra se eles têm pouca ou nenhuma disputa, porque SetEvent é chamado preguiçosamente (olhada no histórico de edições para uma versão mais pesado que não tem essa otimização). 

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

Você poderia diminuir o custo para os leitores usando uma única CRITICAL_SECTION:

  • countsLock é substituído por writerLock em rdlock e rdunlock

  • rwlock->waitingWriter = FALSE é removido em wrunlock

  • O corpo de wrlock é alterado para 

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

No entanto, este perde na justiça, por isso prefiro a solução acima.

Dê uma olhada no livro " Concurrent Programação no Windows ", que tem muitos diferentes exemplos de referência para bloqueios de leitor / escritor.

Confira o spin_rw_mutex da Intel de Tópico Building Blocks ...

spin_rw_mutex é estritamente de user-terra e emprega spin-espera para bloquear

Esta é uma questão de idade, mas talvez alguém vai encontrar este útil. Nós desenvolvemos um alto desempenho, open-source RWLock para Windows que usa automaticamente Vista + SRWLock Michael mencionado se disponível, ou caso contrário, cai de volta para uma implementação userspace.

Como um bônus adicional, há quatro "sabores" diferentes do mesmo (embora você pode ficar com o básico, que é também o mais rápido), cada um oferecendo mais opções de sincronização. Ele começa com o RWLock() básico, que é não reentrante, limitado à sincronização de processo único, e nenhuma troca de fechaduras de leitura / escrita a um cross-processo de pleno direito IPC rwlock com o apoio re-entrada e leitura / gravação de-elevação.

Como mencionado, eles trocar dinamicamente para as + bloqueios de leitura e escrita fino Vista para melhor desempenho quando possível, mas você não precisa se preocupar com isso em tudo como ele vai cair de volta para uma implementação totalmente compatível no Windows XP e sua laia.

Se você já sabe de uma solução que apenas Usa semáforos, você deve ser capaz de modificá-lo para usar seções críticas em seu lugar.

Nós demais nossa própria utilizando duas seções críticas e alguns contadores. Ele se adapte às nossas necessidades -. Temos uma contagem muito baixa escritor, escritores obter precedência sobre os leitores, etc. Eu não tenho liberdade para publicar o nosso, mas posso dizer que é possível, sem semáforos e semáforos

Aqui é a menor solução que eu poderia vir acima com:

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

E colado textualmente: 

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

Olhe minha implementação aqui:

https://github.com/coolsoftware/LockLib

VRWLock é uma classe C ++ que implementa escritor única -. Vários leitores lógica

Veja também TestLock.sln projeto de teste.

UPD. Abaixo está o código simples para o leitor e 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

VRWLock suportes classe contagem de giro e contagem de referência específicos do segmento que permite liberar bloqueios de linhas interrompidas.

Eu escrevi o seguinte código usando apenas secções 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 executar uma spin-espera, comentar as linhas com Sleep (0).

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top