Win32 чтение / запись блокировки, используя только критические разделы

Question

Я должен реализовать блокировку чтения / записи в C ++, используя API Win32 как часть проекта на работе. Все существующие решения используют объекты ядра (семафоры и мьютексы), которые требуют переключения контекста во время выполнения. Это слишком медленно для моего приложения.

Я хотел бы реализовать один, используя только критические секции, если это возможно. Блокировка не должна быть безопасна для процесса, только безопасна для потоков. Есть идеи, как это сделать?

Answer 1

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

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

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

Answer 2

Старый вопрос, но это то, что должно работать. Это не вращается на раздоре. Читатели несут ограниченную дополнительную плату, если у них мало или нет конкуренции, потому что 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.  */
  

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

Answer 3

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

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

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

Answer 4

Проверьте spin_rw_mutex от Intel Thread Building Blocks ...

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

Answer 5

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

Answer 6

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

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

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

Answer 7

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

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).

Answer 8

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

https://github.com/coolsoftware/LockLib

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

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

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

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

Answer 9

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

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

Answer 10

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

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