Shared locks from multiple threads can starve a single thread looking for an exclusive lock

Question

Let's say I have several threads reading from shared memory. All of these threads repeatedly grab a shared lock on a shared mutex to access this memory.

Let's say I have one thread that writes to this shared memory that grabs an exclusive lock.

Given enough read threads there may never be a point in time where that one write thread is able to grab the exclusive lock as the shared lock is constantly held by several threads at any point in time.

What is the easiest most straightforward pattern to solve this issue? I'm looking for an easy straightforward way to solve this issue preferably with the STL.

An example implementation in C++ will be helpful as well.

Answer 1

This should work.

Its not sophisticated and does not provide any gurantees on order if you have more than one writter. But it should work.

#include <condition_variable>
#include <mutex>

class RWLock
{
    std::mutex                  lock;
    std::condition_variable     writeWaiters;
    std::condition_variable     readWaiters;

    int                         waitingWriters;
    int                         currentWriters;
    int                         currentReaders;

    public:
        RWLock()
            : waitingWriters(0)
            , currentWriters(0)
            , currentReaders(0)
        {}

    private:
        friend class RGuard;
        void readLock()
        {
            std::unique_lock<std::mutex>     guard(lock);
            readWaiters.wait(guard, [&]{return waitingWriters == 0;});
            ++currentReaders;
        }
        void readUnLock()
        {
            std::unique_lock<std::mutex>     guard(lock);
            --currentReaders;
            if (currentReaders == 0) {
                writeWaiters.notify_one();
            }
        }
    private:
        friend class WGuard;
        void writeLock()
        {
            std::unique_lock<std::mutex>     guard(lock);
            ++waitingWriters;

            writeWaiters.wait(guard, [&]{return (currentReaders != 0 || currentWriters != 0);});
            ++currentWriters;
        }
        void writeUnLock()
        {
            std::unique_lock<std::mutex>     guard(lock);
            --waitingWriters;
            --currentWriters;
            if (waitingWriters != 0) {
                writeWaiters.notify_one();
            }
            else {
                readWaiters.notify_all();
            }
        }
}
class RGuard
{
    RWLock&     lock;
    public:
        RGuard(RWLock& lock)
            : lock(lock)
        {
            lock.readLock();
        }
        ~RGuard()
        {
            lock.readUnLock();
        }
};
class WGuard
{
    RWLock&     lock;
    public:
        WGuard(RWLock& lock)
            : lock(lock)
        {
            lock.writeLock();
        }
        ~WGuard()
        {
            lock.writeUnLock();
        }
};

int main()
{
    RWLock  lock;
    RGuard  guardR(lock);
    WGuard  guardW(lock);
}

Answer 2

My prefered solution is CsLibGuarded, you can chose your cost.

I have used the lr_guarded so that writes modifies one copy while reads continue on the other side, then when the write is done, all new reads go to the modified side and so on. The write can then modify the other side too after all readers have left.

(untested code)

using MapType = std::map<std::string, std::shared_ptr<ComplicatedObject>>;
lr_guarded<MapType> map;

void MyCache::insert(std::string key, std::shared_ptr<ComplicatedObject> element) {
 m_cache.modify(
 [&key, &element]
 (MapType & map) {
 map.emplace(key, element);
 });
}