Блокировка чтения/записи Win32 с использованием только критических разделов

Я не думаю, что это можно сделать, не используя хотя бы один объект уровня ядра (мьютекс или семафор), потому что вам нужна помощь ядра, чтобы блокировать вызывающий процесс, пока блокировка не будет доступна.

Критические секции обеспечивают блокировку, но API слишком ограничен. например вы не можете захватить CS, обнаружить, что доступна блокировка чтения, но не блокировка записи, и ждать, пока другой процесс закончит чтение (потому что, если у другого процесса есть критическая секция, он заблокирует других читателей, что неправильно, и если он нет, тогда ваш процесс не будет блокироваться, а вращаться, сжигая циклы ЦП.)

Однако то, что вы можете сделать, это использовать спин-блокировку и возвращаться к мьютексу всякий раз, когда возникает конфликт. Сама критическая секция реализована таким образом. Я бы взял существующую реализацию критической секции и заменил поле PID отдельными счетчиками чтения и записи.

Если вы можете ориентироваться на Vista или более позднюю версию, вам следует использовать встроенный SRWLock. Они легкие, как критические разделы, полностью в пользовательском режиме, когда нет состязаний.

В блоге Джо Даффи есть несколько последних записей о реализации различных типов -блокировка блокировки чтения/записи. Эти замки вращаются, поэтому они не подходят, если вы собираетесь выполнять много работы, удерживая замок. Код написан на C#, но должен быть простым для переноса на родной язык.

Вы можете реализовать блокировку чтения/записи, используя критические разделы и события — вам просто нужно сохранить достаточно состояния, чтобы сигнализировать о событии только тогда, когда это необходимо, чтобы избежать ненужного вызова режима ядра.

Старый вопрос, но это то, что должно работать. Это не крутится на раздорах. Читатели несут ограниченную дополнительную плату, если у них мало или нет состязаний, потому что SetEvent вызывается лениво (посмотрите в истории изменений более тяжелую версию, которая не имеет этой оптимизации).

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

Вы можете уменьшить стоимость для читателей, используя один CRITICAL_SECTION:

• countsLock заменяется на writerLock в rdlock и rdunlock

• rwlock->waitingWriter = FALSE удалено в wrunlock

• тело wrlock изменено на

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

Однако это проигрывает по справедливости, поэтому я предпочитаю вышеуказанное решение.

Взгляните на книгу "Параллельное программирование в Windows", в котором есть множество различных справочных примеров для блокировок чтения/записи.

Ознакомьтесь с spin_rw_mutex из Intel Thread Building Blocks...

spin_rw_mutex находится строго на территории пользователя и использует ожидание вращения для блокировки

Это старый вопрос, но, возможно, кто-то найдет это полезным. Мы разработали высокопроизводительный с открытым исходным кодом RWLock для Windows, который автоматически использует Vista+ SRWLock Майкл упоминается, если доступно, или иным образом возвращается к реализации пользовательского пространства.

В качестве дополнительного бонуса есть четыре разных «вкуса» (хотя вы можете придерживаться основного, который также является самым быстрым), каждый из которых предоставляет больше возможностей синхронизации. Он начинается с базового RWLock(), который не допускает повторного входа, ограничен синхронизацией одного процесса и без переключения блокировок чтения/записи на полноценный межпроцессный блокировку IPC RWLock с поддержкой повторного входа и удалением прав чтения/записи.

Как уже упоминалось, они динамически переключаются на тонкие блокировки чтения-записи Vista+ для достижения наилучшей производительности, когда это возможно, но вам не нужно об этом беспокоиться, так как они вернутся к полностью совместимой реализации в Windows XP и ее род.

Если вы уже знаете решение, которое только использует мьютексы, вы сможете изменить его, чтобы использовать вместо этого критические секции.

Мы накатили свой собственный, используя две критические секции и несколько счетчиков. Это соответствует нашим потребностям - у нас очень мало писателей, писатели имеют приоритет над читателями и т. д. Я не имею права публиковать наши, но могу сказать, что это возможно без мьютексов и семафоров.

Вот самое маленькое решение, которое я мог придумать:

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

И вставил дословно:

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

Я написал следующий код, используя только критические разделы.

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

Чтобы выполнить ожидание вращения, прокомментируйте строки с помощью Sleep(0).

Посмотрите мою реализацию здесь:

https://github.com/coolsoftware/LockLib

VRWLock — это класс C++, который реализует логику одиночного записи — нескольких считывателей.

Смотрите также тестовый проект TestLock.sln.

УПД. Ниже приведен простой код для чтения и записи:

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 поддерживает счетчик циклов и счетчик ссылок для конкретных потоков, что позволяет снимать блокировки завершенных потоков.