CODEWITHSUNDEEP
c++multithreadinglockingmutex
JMRC
JMRC

Reputation: 1514

Simple read/write lock implementation without starvation

I've built a read/write lock and have been testing it without encountering any problems. It was made to avoid writer starvation, but I believe it works against reader starvation as well. I've seen alternatives online, but was wondering if this is a solid implementation.

If you use a normal shared mutex, new read actions can still be queued, which will prevent write actions from ever being processed while there is any read action present. This will cause starvation. I used a second mutex which will be locked by the write process and prevents any new read processes to be queued. Thank you!

class unique_priority_mutex
{
public:

    void lock_shared(void)
    {
        // If there is a unique operation running, wait for it to finish.
        if( this->_is_blocked ){
            // Use a shared lock to let all shared actions through as soon as the unique action finishes.
            std::shared_lock<std::shared_mutex> l(this->_unique_mutex);
        }

        // Allow for multiple shared actions, but no unique actions.
        this->_shared_mutex.lock_shared();
    }

    void unlock_shared(void)
    {
        this->_shared_mutex.unlock_shared();
    }

    void lock(void)
    {
        // Avoid other unique actions and avoid new shared actions from being queued.
        this->_unique_mutex.lock();

        // Redirect shared actions to the unique lock.
        this->_is_blocked = true;

        // Perform the unique lock.
        this->_shared_mutex.lock();
    }

    void unlock(void)
    {
        this->_shared_mutex.unlock();
        this->_is_blocked = false;
        this->_unique_mutex.unlock();
    }

    std::shared_mutex _shared_mutex;
    std::shared_mutex _unique_mutex;
    std::atomic<bool> _is_blocked = false;
};

Upvotes: 0

Views: 805

Answers (1)

mevets
mevets

Reputation: 10445

If I understand your code right, then this is equivalent:

1    my_shared_lock(Lock *p) {
2        if (p->_is_blocked) {
3             exclusive_lock(&p->x);
4        }
5        shared_lock(&p->s);
6    }
7    
8    my_exclusive_lock(Lock *p) {
9        exclusive_lock(&p->x);
10       p->_is_blocked = 1;
11       shared_lock(&p->s);
12   }

If you have two threads executing, and this displays their progress:

T1:   1  2  4  5
T2: 8 9     10 11

The key being that the test on line 2 may execute in one thread in between the execution of lines 9 and 10 in another; so line 3 is skipped. Then T1 thinks it has my_shared_lock and T2 thinks it has my_exclusive_lock simultaneously, which is worse than starvation.

Upvotes: 0

Related Questions