Reader/Writer Locks in C++

reader/writer lock in pthread

When a thread acquires a lock, other threads trying to acquire the same lock will be suspended until the first thread releases the lock.

What is happening here is that your reader thread starts, acquires the lock, and enters the for/poll loop.

The writer thread starts, tries to acquire the lock which was already taken by the reader thread, and remains blocked on pthread_rwlock_wrlock.

What you actually want to do is to put your lock/unlock right before and after the code where you access your shared variable.

thread_rwlock_rdlock(p);
newx = ACCESS_ONCE(x);
thread_rwlock_unlock(p);
...
thread_rwlock_wrlock(p);
ACCESS_ONCE(x)++;
thread_rwlock_unlock(p);

Reader/Writer implementation in C

Don't think of the locks as "reader lock" and "writer lock".

Because you need to allow multiple concurrent readers, readers cannot hold a mutex. (If they do, they are serialized; only one can hold a mutex at the same time.) They can take one for a short duration (before they begin the access, and after they end the access), to update state, but that's it.

Split the timeline for having a rwlock into three parts: "grab rwlock", "do work", "release rwlock".

For example, you could use one mutex, one condition variable, and a counter. The counter holds the number of active readers. The condition variable is signaled on by the last reader, and by writers just before they release the mutex, to wake up a waiting writer. The mutex protects both, and is held by writers for the whole duration of their write operation.

So, in pseudocode, you might have

Function rwlock_rdlock:
    Take mutex
    Increment counter
    Release mutex
End Function

Function rwlock_rdunlock:
    Take mutex
    Decrement counter
    If counter == 0, Then:
        Signal_on cond
    End If
    Release mutex
End Function

Function rwlock_wrlock:
    Take mutex
    While counter > 0:
        Wait_on cond
End Function

Function rwlock_unlock:
     Signal_on cond
     Release mutex
End Function

Remember that whenever you wait on a condition variable, the mutex is atomically released for the duration of the wait, and automatically grabbed when the thread wakes up. So, for waiting on a condition variable, a thread will have the mutex both before and after the wait, but not during the wait itself.

Now, the above approach is not the only one you might implement.

In particular, you might note that in the above scheme, there is a different "unlock" operation you must use, depending on whether you took a read or a write lock on the rwlock. In POSIX pthread_rwlock_t implementation, there is just one pthread_rwlock_unlock().

Whatever scheme you design, it is important to examine it whether it works right in all situations: a lone read-locker, a lone-write-locker, several read-lockers, several-write-lockers, a lone write-locker and one read-locker, a lone write-locker and several read-lockers, several write-lockers and a lone read-locker, and several read- and write-lockers.

For example, let's consider the case when there are several active readers, and a writer wants to write-lock the rwlock.

The writer grabs the mutex. It then notices that the counter is nonzero, so it starts waiting on the condition variable. When the last reader -- note how the order of the readers exiting does not matter, since a simple counter is used! -- unlocks its readlock on the rwlock, it signals on the condition variable, which wakes up the writer. The writer then grabs the mutex, sees the counter is zero, and proceeds to do its work. During that time, the mutex is held by the writer, so all new readers will block, until the writer releases the mutex. Because the writer will also signal on the condition variable when it releases the mutex, it is a race between other waiting writers and waiting readers, who gets to go next.

How to implement a reader/writer lock in C++14

C++14 has the read/writer lock implementation std::shared_timed_mutex.

Side-note: C++17 added the simpler class std::shared_mutex, which you can use if you don't need the extra timing functions (like shared_timed_mutex::try_lock_for and shared_timed_mutex::try_lock_until).

However, before using a read/writer lock, be aware of the potentially harmful performance implications. Depending on the situation, a simple std::mutex might be faster.

A readers/writer lock... without having a lock for the readers?

What you're describing is very similar to double instance locking and left-right concurrency control.

In terms of progress guarantees, the difference between the two is that the former is lock-free for readers while the latter is wait-free. Both are blocking for writers.

Reader/Writer Locks in C++

Newer versions of boost::thread have read/write locks (1.35.0 and later, apparently the previous versions did not work correctly).

They have the names shared_lock, unique_lock, and upgrade_lock and operate on a shared_mutex.

Race condition while trying to use Readers Writer Lock

The two options you give are suboptimal in most scenarios, since one prevents multiple readers from checking at the same time (and presumably, after a while, readers are much more common than writers), while the other is impossible; even if you switch "atomically" from reader lock to writer lock, two different readers could both determine a value X is not present, both request an upgrade to write lock, the first one writes X then unlocks, while the second waits its turn then writes X again and you end up violating the uniqueness invariant.

The real answer depends on the common usage patterns:

1. If writing is more likely to happen than reading in general (concurrent reading is uncommon), then you just drop the reader/writer lock and use a simple mutex. Reader/writer locks often have overhead that isn't worth it if you aren't regularly using concurrent readers, and even if the overhead is trivial (sometimes it is; Windows' SRW Locks used solely in "exclusive" (writer) mode where recursive acquisition isn't needed is as fast or faster than critical sections), if the program logic becomes more complicated, or you need to constantly switch from read to write locks and back, the additional logic and acquisition/release overhead can cost more than just a single lock and unlock with exclusive access.

2. If you have other frequently used code which reads but never writes, and readers that might need to write are less common and regularly have to write, then use the solution you suggested; keep the reader/writer lock, but have the "might write" code lock for write from the beginning; it eliminates concurrency in the "might write" code path, but "only read" users can operate concurrently.

3. If reading is much more common than writing (which is the usual use case for something like this if the code provided is the only code that accesses the array; otherwise your array will grow out of control), then perform a double check after "upgrading" to write lock; perform the same scan a second time after upgrading to a write lock to make sure no one grabbed the write lock and added the missing value, then write if the value is still missing. This can be optimized to avoid rescanning if the array only has new values added, with existing values never changing or being deleted. You'd just remember where you left off checking, and scan any new entries added between your original scan and when you acquired the write lock.

The pseudo-code for #3 would look like:

FOR each NUM from X to X' DO:
    IF func(NUM) = true DO:
        RWL_R // lock for reader outside inner loop since repeatedly reading from ARR
        cell = 0
        WHILE cell < ARR.length DO:
            IF ARR[cell] contains NUM DO:
                RWL_U // unlock since no longer reading from ARR
                skip to the next iteration of the first FOR loop
            ENDIF
            cell += 1
        END WHILE

        RWL_U // unlock since no longer reading from ARR
        RWL_W // lock to write to array since for loop ended without finding the same NUM
        // NEW!!! Check newly added cells
        WHILE cell < ARR.length DO:
            IF ARR[cell] contains NUM DO:
                RWL_U // unlock since no longer reading from ARR
                skip to the next iteration of the first FOR loop
            ENDIF
            cell += 1
        END WHILE
        // If we got here, not in newly added cells either, so add to end
        ARR[cell] <- NUM
        RWL_U // unlock since finished writing into array
    END IF
END FOR

How can I implement a C++ Reader-Writer lock using a single unlock method, which can be called be a reader or writer?

Well, define two functions UnlockRead and UnlockWrite.

I believe you do not need both accesses (Write/Read) at the same time in the same place. So what I am proposing is to have two other classes for locking access:

class ReadWriteAccess
{
public:
   ReadWriteAccess(uint32_t maxReaders);
   ~ReadWriteAccess();
   uint32_t GetMaxReaders() const;
   uint32_t GetMaxReaders() const;
   eResult  GetReadLock(int32_t timeout);
   eResult  GetWriteLock(int32_t timeout);
   eResult  UnlockWrite();
   eResult  UnlockRead();

private:
   uint32_t m_MaxReaders;
   Mutex* m_WriterMutex;
   Semaphore* m_ReaderSemaphore;

};

And have separate classes for read and write lock and use RAII to be always on safe side:

class ReadLock
{
public:
    ReadLock(ReadWriteAccess& access, int32_t timeout) : access(access) 
    {
        result = access.GetReadLock(timeout);
    }
    eResult getResult() const { return result; }
    ~ReadLock()
    {
        if (result)
            access.UnlockRead();
    }
private:
    ReadWriteAccess& access;
    eResult  result;
};

and use like this:

T someResource;
ReadWriteAccess someResourceGuard;

void someFunction()
{
    ReadLock lock(someResourceGuard);
    if (lock.getResult())
       cout << someResource; // it is safe to read something from resource
}

Of course, the very similar implementation you can easily write by yourself for WriteLock

---

Since OP insisted in comments to have "one" Unlock - please consider the drawbacks:

Assume it is implemented some kind of stack of last calls to Lock functions:

class ReadWriteLock
{
public:
   ReadWriteLock(uint32_t maxReaders);
   ~ReadWriteLock();
   uint32_t GetMaxReaders() const;
   eResult  GetReadLock(int32_t timeout)
   {
       eResult result = GetReadLockImpl(timestamp);
       if (result)
           lockStack.push(READ);
   }
   eResult  GetWriteLock(int32_t timeout)
   {
       eResult result = GetWriteLockImpl(timestamp);
       if (result)
           lockStack.push(WRITE);
   }
   eResult  Unlock()
   {
       LastLockMode lockMode = lockStack.top();
       lockStack.pop();
       if (lockMode == READ) 
           UnlockReadImpl();
       else
           UnlockWriteImpl();
   }

private:
   uint32_t m_MaxReaders;
   Mutex* m_WriterMutex;
   Semaphore* m_ReaderSemaphore;

    enum Mode { READ, WRITE };
    std::stack<Mode> lockStack;
};

But the above would work only in one-thread application. And one-thread application never need any locks.

So - you have to have multi-thread stack - like:

template <typename Value>
class MultiThreadStack
{
public:
    void push(Value)
    {
       stackPerThread[getThreadId()].push(value);
    }
    Value top()
    {
       return stackPerThread[getThreadId()].top();
    }
    void pop()
    {
       stackPerThread[getThreadId()].pop();
    }
private:
    ThreadId getThreadId() { return /* your system way to get thread id*/; }
    std::map<ThreadId, std::stack<Value>> stackPerThread;
};

So use this MultiThreadStack not std::stack in ReadWriteLock.

But, the std::map above would need ReadWriteLock to lock access to it from multuple threads - so, well, either you know all your threads before you start using this stuff (preregistration) or you end up in the same problem as described here. So my advice - if you can - change your design.

C Reader Writer Threads Lock Unlock

The problem is that your source algorithm relies on the fact that one thread locks the accessMutex lock, and another thread then may unlock it. This is allowable with semaphore-based mutexes, but it is not allowed for pthreads mutexes.

There are semaphores in pthreads, provided by the sem_init(), sem_post() and sem_wait() functions. You could use these to write a direct implementation of the source algorithm, and it should work correctly.

Alternately, pthreads also provides a native read-writer lock type - see the functions pthread_rwlock_init(), pthread_rwlock_rdlock(), pthread_rwlock_wrlock() and pthread_rwlock_unlock(). You could use this for a very simple implementation, but obviously this is missing the point if it's supposed to be a learning exercise.

---

Related Topics