How to Make a Multiple-Read/Single-Write Lock from More Basic Synchronization Primitives

How to make a multiple-read/single-write lock from more basic synchronization primitives?

It seems like you only have mutex and condition_variable as synchronization primitives. therefore, I write a reader-writer lock here, which starves readers. it uses one mutex, two conditional_variable and three integer.

readers - readers in the cv readerQ plus the reading reader
writers - writers in cv writerQ plus the writing writer
active_writers - the writer currently writing. can only be 1 or 0.

It starve readers in this way. If there are several writers want to write, readers will never get the chance to read until all writers finish writing. This is because later readers need to check writers variable. At the same time, the active_writers variable will guarantee that only one writer could write at a time.

class RWLock {
public:
    RWLock()
    : shared()
    , readerQ(), writerQ()
    , active_readers(0), waiting_writers(0), active_writers(0)
    {}

    void ReadLock() {
        std::unique_lock<std::mutex> lk(shared);
        while( waiting_writers != 0 )
            readerQ.wait(lk);
        ++active_readers;
        lk.unlock();
    }

    void ReadUnlock() {
        std::unique_lock<std::mutex> lk(shared);
        --active_readers;
        lk.unlock();
        writerQ.notify_one();
    }

    void WriteLock() {
        std::unique_lock<std::mutex> lk(shared);
        ++waiting_writers;
        while( active_readers != 0 || active_writers != 0 )
            writerQ.wait(lk);
        ++active_writers;
        lk.unlock();
    }

    void WriteUnlock() {
        std::unique_lock<std::mutex> lk(shared);
        --waiting_writers;
        --active_writers;
        if(waiting_writers > 0)
            writerQ.notify_one();
        else
            readerQ.notify_all();
        lk.unlock();
    }

private:
    std::mutex              shared;
    std::condition_variable readerQ;
    std::condition_variable writerQ;
    int                     active_readers;
    int                     waiting_writers;
    int                     active_writers;
};

Multiple-readers, single-writer synchronization lock between processes on Windows with WinAPI/C++

You can use the same algorithm but instead of CriticalSection you can use Mutexes from the WinAPI.

If you use the same name for your Mutex objects you can use them in several processes.

Multiple-Reader, Single-Writer Lock in Boost WITH Writer Block

Found it. I needed unique_lock instead of upgrade_to_unique_lock:

boost::shared_mutex _access;
void reader()
{
    // get shared access
    boost::shared_lock<boost::shared_mutex> lock(_access);
}

void writer()
{
    // wait for old shared access readers to finish
    // but block out new shared access readers
    boost::unique_lock<boost::shared_mutex> uniqueLock(_access);
}

C++11 multiple read and one write thread mutex

Pretty close, couple things to note, in c++ for exception safety and readability, IMO, it is good to use RAII locks. What you really need is a shared_mutex like in boost or coming in c++14.

std::shared_mutex write; //use boost's or c++14 

// One write, no reads.
void write_fun()
{
    std::lock_guard<std::shared_mutex> lock(write);
    // DO WRITE
}

// Multiple reads, no write
void read_fun()
{
    std::shared_lock<std::shared_mutex> lock(write);
    // do read
}

If you don't want to use boost @howardhinmant was do kind as to give a link to a reference implementation

Fast and Lock Free Single Writer, Multiple Reader

You should try using std::atomic first, but make sure that your compiler knows and understands your target architecture. Since you are targeting Cortex-A15 (ARMv7-A cpu), make sure to use -march=armv7-a or even -mcpu=cortex-a15.

The first shall generate ldrexd instruction which should be atomic according to ARM docs:

Single-copy atomicity

In ARMv7, the single-copy atomic processor accesses are:

• all byte accesses
• all halfword accesses to halfword-aligned locations
• all word accesses to word-aligned locations
• memory accesses caused by LDREXD and STREXD instructions to doubleword-aligned locations.

The latter shall generate ldrd instruction which should be atomic on targets supporting Large Physical Address Extension:

In an implementation that includes the Large Physical Address Extension, LDRD and STRD accesses to 64-bit aligned locations are 64-bit single-copy atomic as seen by translation table walks and accesses to translation tables.

--- Note ---

The Large Physical Address Extension adds this requirement to avoid the need to complex measures to avoid atomicity issues when changing translation table entries, without creating a requirement that all locations in the memory system are 64-bit single-copy atomic.

You can also check how Linux kernel implements those:

#ifdef CONFIG_ARM_LPAE
static inline long long atomic64_read(const atomic64_t *v)
{
    long long result;

    __asm__ __volatile__("@ atomic64_read\n"
"   ldrd    %0, %H0, [%1]"
    : "=&r" (result)
    : "r" (&v->counter), "Qo" (v->counter)
    );

    return result;
}
#else
static inline long long atomic64_read(const atomic64_t *v)
{
    long long result;

    __asm__ __volatile__("@ atomic64_read\n"
"   ldrexd  %0, %H0, [%1]"
    : "=&r" (result)
    : "r" (&v->counter), "Qo" (v->counter)
    );

    return result;
}
#endif

Read-write lock with only one underlying lock?

You are not using a single lock.
You are using a lock and a condition variable

self.read_lock = t.Condition(t.Lock())

A condition variable is a concurrency primitive too. A more complex one than a lock.

note : please do not call a condition variable object read_lock

edit:
Your code seems correct to me, as it solves the First readers-writers problem. As you said it may starve writer. This is not a small issue. The logic behind reader writer is that there may be a lot more reads than writes

An additional lock allow to solve the Second readers-writers problem, where a writer doesn't starve. Indeed, readers have to wait when there is a writer waiting for the resource.

Synchronization for multiple readers, single writer?

There is a class for that purpose in RTL(sysutils) : TMultiReadExclusiveWriteSynchroniser

It is very easy to use. You don't need to strictly categorize your threads like reader or writer. Just call "BeginRead" or "BeginWrite" in a thread for starting a thread safe operation. Call "EndRead" or "EndWrite" for finishing the operation.

Cross-process read-write synchronization primative in .NET?

No. As Richard noted above, there is no such out of the box mechanism in .NET.
This is how to implement it using a mutex and a semaphore.

Method #1 is described in http://www.joecheng.com/blog/entries/Writinganinter-processRea.html, quoting:

// create or open global mutex
GlobalMutex mutex = new GlobalMutex("IdOfProtectedResource.Mutex");
// create or open global semaphore
int MoreThanMaxNumberOfReadersEver = 100;

GlobalSemaphore semaphore = new GlobalSemaphore("IdOfProtectedResource.Semaphore", MoreThanMaxNumberOfReadersEver);

public void AcquireReadLock()
{
  mutex.Acquire();
  semaphore.Acquire();
  mutex.Release();
}

public void ReleaseReadLock()
{
  semaphore.Release();
}

public void AcquireWriteLock()
{
  mutex.Acquire();
  for (int i = 0; i < MoreThanMaxNumberOfReadersEver; i++)
    semaphore.Acquire(); // drain out all readers-in-progress
  mutex.Release();
}

public void ReleaseWriteLock()
{
  for (int i = 0; i < MoreThanMaxNumberOfReadersEver; i++)
    semaphore.Release();
}

An alternative would be:

Read locking - as above. Write locking as follows (pseudocode):

- Lock mutex
- Busy loop until the samaphore is not taken AT ALL:
-- wait, release.
-- Release returns value; 
-- if value N-1 then break loop.
-- yield (give up CPU cycle) by using Sleep(1) or alternative
- Do write
- Release mutex

It must be noted that more efficient approach is possible, as here: http://en.wikipedia.org/wiki/Readers-writers_problem#The_second_readers-writers_problem
Look for the words "This solution is suboptimal" in the article above.

---

Related Topics