Boost shared_lock. Read preferred?

Question

I was checking out the boost library(version 1.45) for a reader/writer lock. When I ran my tests on it, it seemed like the shared_ptr was preferring my reader threads, i.e. when my writer tried to take the lock for its operation, it didn't stop any subsequent reads from occurring.

Is it possible in boost to change this behavior?

using namespace std;
using namespace boost;

mutex outLock;
shared_mutex workerAccess;
bool shouldIWork = true;

class WorkerKiller
{
public:   

    void operator()()  
    {
        upgrade_lock<shared_mutex> lock(workerAccess); 
        upgrade_to_unique_lock<shared_mutex> uniqueLock(lock);

        cout << "Grabbed exclusive lock, killing system" << endl;
        sleep(2);
        shouldIWork = false;
        cout << "KILLING ALL WORK" << endl;  
    }  

private:  
};

class Worker
{  
public:   

    Worker()
    {  
    }  

    void operator()()  
    {
        shared_lock<shared_mutex> lock(workerAccess); 

        if (!shouldIWork) {
            outLock.lock();
            cout << "Workers are on strike.  This worker refuses to work" << endl;
            outLock.unlock();
        } else {
            sleep(1);

            outLock.lock(); 
            cout << "Worked finished her work" << endl;
            outLock.unlock(); 
        }
    }  
};  

int main(int argc, char* argv[])  
{  
    Worker w1;
    Worker w2;
    Worker w3;
    Worker w4;
    WorkerKiller wk;

    boost::thread workerThread1(w1);
    boost::thread workerThread2(w2);

    boost::thread workerKillerThread(wk);

    boost::thread workerThread3(w3);
    boost::thread workerThread4(w4);

    workerThread1.join();
    workerThread2.join();
    workerKillerThread.join();
    workerThread3.join();

    return 0;
}

And here is the output every time:

Worked finished her work
Worked finished her work
Worked finished her work
Worked finished her work
Grabbed exclusive lock, killing system
KILLING ALL WORK

My Requirement

If the writer tried to grab an exclusive lock, I'd like for all previous read operations to finish. And then all subsequent read operations to block.

You might want to post some test code - my psychic debugging skills are weak :-) — Bukes, Aug 22 '12 at 22:48

Howard Hinnant · Accepted Answer · 2015-01-10T23:32:40.123

I'm a little late to this question, but I believe I have some pertinent information.

The proposals of shared_mutex to the C++ committee, which the boost libs are based on, purposefully did not specify an API to give readers nor writers priority. This is because Alexander Terekhov proposed an algorithm about a decade ago that is completely fair. It lets the operating system decide whether the next thread to get the mutex is a reader or writer, and the operating system is completely ignorant as to whether the next thread is a reader or writer.

Because of this algorithm, the need for specifying whether a reader or writer is preferred disappears. To the best of my knowledge, the boost libs are now (boost 1.52) implemented with this fair algorithm.

The Terekhov algorithm consists of having the read/write mutex consist of two gates: gate1 and gate2. Only one thread at a time can pass through each gate. The gates can be implemented with a mutex and two condition variables.

Both readers and writers attempt to pass through gate1. In order to pass through gate1 it must be true that a writer thread is not currently inside of gate1. If there is, the thread attempting to pass through gate1 blocks.

Once a reader thread passes through gate1 it has read ownership of the mutex.

When a writer thread passes through gate1 it must also pass through gate2 before obtaining write ownership of the mutex. It can not pass through gate2 until the number of readers inside of gate1 drops to zero.

This is a fair algorithm because when there are only 0 or more readers inside of gate1, it is up to the OS as to whether the next thread to get inside of gate1 is a reader or writer. A writer becomes "prioritized" only after it has passed through gate1, and is thus next in line to obtain ownership of the mutex.

I used your example compiled against an example implementation of what eventually became shared_timed_mutex in C++14 (with minor modifications to your example). The code below calls it shared_mutex which is the name it had when it was proposed.

I got the following outputs (all with the same executable):

Sometimes:

Worked finished her work
Worked finished her work
Grabbed exclusive lock, killing system
KILLING ALL WORK
Workers are on strike.  This worker refuses to work
Workers are on strike.  This worker refuses to work

And sometimes:

Worked finished her work
Grabbed exclusive lock, killing system
KILLING ALL WORK
Workers are on strike.  This worker refuses to work
Workers are on strike.  This worker refuses to work
Workers are on strike.  This worker refuses to work

And sometimes:

Worked finished her work
Worked finished her work
Worked finished her work
Worked finished her work
Grabbed exclusive lock, killing system
KILLING ALL WORK

I believe it should be theoretically possible to also obtain other outputs, though I did not confirm that experimentally.

In the interest of full disclosure, here is the exact code I executed:

#include "../mutexes/shared_mutex"
#include <thread>
#include <chrono>
#include <iostream>

using namespace std;
using namespace ting;

mutex outLock;
shared_mutex workerAccess;
bool shouldIWork = true;

class WorkerKiller
{
public:   

    void operator()()  
    {
        unique_lock<shared_mutex> lock(workerAccess); 

        cout << "Grabbed exclusive lock, killing system" << endl;
        this_thread::sleep_for(chrono::seconds(2));
        shouldIWork = false;
        cout << "KILLING ALL WORK" << endl;  
    }  

private:  
};

class Worker
{  
public:   

    Worker()
    {  
    }  

    void operator()()  
    {
        shared_lock<shared_mutex> lock(workerAccess); 

        if (!shouldIWork) {
            lock_guard<mutex> _(outLock);
            cout << "Workers are on strike.  This worker refuses to work" << endl;
        } else {
            this_thread::sleep_for(chrono::seconds(1));

            lock_guard<mutex> _(outLock);
            cout << "Worked finished her work" << endl;
        }
    }  
};  

int main()  
{  
    Worker w1;
    Worker w2;
    Worker w3;
    Worker w4;
    WorkerKiller wk;

    thread workerThread1(w1);
    thread workerThread2(w2);

    thread workerKillerThread(wk);

    thread workerThread3(w3);
    thread workerThread4(w4);

    workerThread1.join();
    workerThread2.join();
    workerKillerThread.join();
    workerThread3.join();
    workerThread4.join();

    return 0;
}

Yeah I just came back to this question to post this same answer. You are indeed correct. Boost uses a fair implementation now and you can't really control which one gets selected. Thanks so much for your detailed explanation. — anoneironaut, Dec 03 '12 at 06:28
The bloomington paper seems missing from the new site at http://howardhinnant.github.io/. I don't know how to fix that one :) — sehe, Jan 10 '15 at 21:42
Is this guaranteed by the standard? Maybe I'm looking in the wrong places, but I can't find any mention in the draft C++17 standard of this property that (assuming no lock is held indefinitely) each waiting thread will eventually be presented to the operating system as schedulable. (The closest is a note that C++ threads are intended to correspond 1-to-1 with OS threads.) The Terekhov algorithm is all well and good, but what (beside good sense) prevents a C++ implementation from using something dumber (and non-fair) for shared_mutex? Or even a non-fair implementation of a plain mutex? — Chris Pacejo, Jan 21 '19 at 05:32
@ChrisPacejo: Nothing. It is a Quality Of Implementation issue. Similar for `condition_variables`. Their `wait` functions could spin, continually waking spuriously. But generally vendors try to do right by their customers. — Howard Hinnant, Jan 21 '19 at 13:43

score 1 · Answer 2 · edited May 23 '17 at 12:02

1

A google search of "boost shared lock starvation" turned up this link:

Example for boost shared_mutex (multiple reads/one write)?

It looks like "upgrade" might be the key. See also:

edited May 23 '17 at 12:02

Community

1
1

answered Aug 22 '12 at 22:47

paulsm4

114,292
17
138
190

Hi Paul. I took a look at those articles. They were great reads but I'm still a little big lost on whether or not I can set these mutexes as Write preferred. The last article seems to outline a mutex model that boost is similar too but has key differences. In that model it is definitely write preferred. But in boost it seems to be OS specific? I found this information in the 1.35 documentation as well: http://www.boost.org/doc/libs/1_34_0/doc/html/thread/concepts.html#thread.concepts.read-write-scheduling-policies.inter-class. In addition I tried raising the priority of my writer. – anoneironaut Aug 27 '12 at 20:05
@HowardHinnant I tried to [fix this link](http://stackoverflow.com/posts/12082441/revisions). Maybe you could review it – sehe Jan 10 '15 at 21:35

Boost shared_lock. Read preferred?

2 Answers2

Linked