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.

Does this answer your question? [Reader/Writer Locks in C++](https://stackoverflow.com/questions/244316/reader-writer-locks-in-c) — J..., Nov 16 '20 at 17:50
A lock that gives priority to writers. Once a thread starts waiting on a write lock no more read locks will be given out. Once all read locks have been released the write lock is granted. — Martin York, Nov 16 '20 at 17:52
@MartinYork, Is there anything in the stl that will do this? The linked post has a C++17 implimentation that I believe will still starve the write thread and I'd rather use existing pretested stuff than impliment my own read write locks. — Brian Yeh, Nov 16 '20 at 18:02
@J... No not really. There are several incorrect answers in the thread and it's just focusing on what kind of mutex and lock to use. I'm already using shared locks here the problem is thread starvation given many many read threads and one write thread. Specifically I'm looking for a simple straightforward prebuilt solution from the stl if that even exists. — Brian Yeh, Nov 16 '20 at 18:09
It amazes me to learn that the standard does not define any way to specify a "policy" for resolving `std::shared_mutex` conflicts and, that it does not require a default policy that would put new readers into the queue behind waiting writers (i.e., what @MartinYork described above.) Oh well! It's not the first time I've been amazed by the C++ standard. — Solomon Slow, Nov 16 '20 at 20:09

Surt · Answer 1 · 2020-11-16T18:13:11.507

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

Martin York · Accepted Answer · 2020-11-18T21:40:19.093

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

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

2 Answers2