shared_mutex lock ordering

Question

I was under the impression a multiple reader / single writer pattern implemented with c++17's std::shared_mutex could potentially never relinquish unique locks if too many shared locks were acquired.

After digging on cppreference, I am unsure that is the case. Specifically :

All lock and unlock operations on a single mutex occur in a single total order

For example, given the following operations on a shared_mutex, I believed the unique_lock may never acquire. Assuming an infinite amount of shared_locks, and that these locks acquire before the first shared_locks release.

shared_lock
shared_lock
shared_lock

unique_lock

shared_lock
[...]
shared_lock

Giving the following characteristics.

{ shared_lock, shared_lock, shared_lock, shared_lock, ..., shared_lock } // never releases

unique_lock

However, if I understand cppreference correctly, once the unique_lock tries to acquire, consecutive shared_locks would block until the unique_lock is released. Giving the following threading characteristics.

{ shared_lock, shared_lock, shared_lock} // simultaneous

unique_lock

{ shared_lock, ..., shared_lock} // waits, then simultaneous

So my question is, does a std::shared_mutex keep ordering between shared and unique locks? Preventing the case where unique_locks are never acquired due to an overwhelming amount of shared_locks being acquired.

edit :

Here is a code example to help understand the problem, and for posterity's sake. On MSVC 2019, shared_mutex is safe and ordering happens as desired. The unique_lock does get processed before the "infinite" amount of shared_locks.

The question now becomes, is this platform dependent?

#include <chrono>
#include <cstdio>
#include <mutex>
#include <shared_mutex>
#include <thread>
#include <vector>

using namespace std::chrono_literals;

std::shared_mutex smtx;

int main(int, char**) {

    std::vector<std::thread> threads;

    auto read_task = [&]() {
        std::shared_lock l{ smtx };
        printf("read\n");
        std::this_thread::sleep_for(1s);
    };

    auto write_task = [&]() {
        std::unique_lock l{ smtx };
        printf("write\n");
        std::this_thread::sleep_for(1s);
    };

    // Create a few reader tasks.
    threads.emplace_back(read_task);
    threads.emplace_back(read_task);
    threads.emplace_back(read_task);


    // Try to lock a unique_lock before read tasks are done.
    std::this_thread::sleep_for(1ms);
    threads.emplace_back(write_task);

    // Then, enque a gazillion read tasks.
    // Will the unique_lock be locked? [drum roll]

    // Would be while(true), 120 should be enough for demo
    for (size_t i = 0; i < 120; ++i) {
        std::this_thread::sleep_for(1ms);
        threads.emplace_back(read_task);
    }

    for (auto& t : threads) {
        t.join();
    }
}

Outputs :

read
read
read
write
read
...
read

The standard lacks functionality equivalent to WaitForMultipleObjects (Windows) which makes a single writer/multiple readers scenario unreliable. Check my [RWMutex](https://www.codeproject.com/Articles/1053865/RWMutex-A-shared-exclusive-recursive-mutex) and [tlock](https://www.codeproject.com/Articles/1186797/tlock-Any-Cplusplus-object-read-write-thread-safe) for Windows — Michael Chourdakis, May 11 '19 at 15:31
@MichaelChourdakis So no, std::shared_mutex isn't "that smart". And one must use other mechanisms (like 2 ring_buffers) to gather and dispatch the correct amount of work. Dealing with the case where too many read tasks would never allow write tasks to execute. — scx, May 11 '19 at 15:36
@MichaelChourdakis Could you elaborate why `std::shared_mutex` would be unreliable for a single writer/multiple reader on a shared object scenario? It would seem that scenario is the whole reason for its existence in the first place. If it were not able to reliably handle that, then that would seem to be a severe defect in the standard. There do not seem to be any open LWG or CWG issues involving reliability of `std::shared_mutex`, so if you know of such an issue there, that should probably be reported immediately… — Michael Kenzel, May 11 '19 at 16:05
Can you write a simulation that tests your concern? English is hard to parse. Certainly it is the case that if shared locks are acquired and they are never released, a unique lock can never be acquired. But that answer seems so obvious that I must be missing what you're really asking. — Howard Hinnant, May 12 '19 at 02:57
@HowardHinnant: There are readers-writer lock implementations that [defer readers](https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock#Priority_policies) to allow writers to (eventually) proceed. The question is whether C++ guarantees the behavior (one way or the other). — Davis Herring, May 12 '19 at 03:33
After examining shared_mutex it seems to me that is safe in a way that it waits for all the readers in a for loop but when a thread exits it's no longer able to re enter. Hence it's safe, although slower. My implementation allows reading threads to re-enter as long as at least one reader hasn't finished, hence the usage of WaitForMultipleObjects, and also supports upgrading. — Michael Chourdakis, May 12 '19 at 07:29

score 2 · Accepted Answer · answered May 12 '19 at 03:50

The std shared_mutex specification does not specify a priority for shared locks nor unique locks. Nor is there any API to set such a priority. One of the original motivations for the lack of specification for priority is the existence of the Alexander Terekhov algorithm as explained here.

A secondary motivation is to explain the lack of reader-writer priority policies in shared_mutex. This is due to an algorithm credited to Alexander Terekhov which lets the OS decide which thread is the next to get the lock without caring whether a unique lock or shared lock is being sought. This results in a complete lack of reader or writer starvation. It is simply fair.

The standard spec does not require the Alexander Terekhov algorithm. However it was at least my hope, that this algorithm would be preferred because of the lack of specification or API for preferring readers over writers or vice-versa.

There are more details about the Alexander Terekhov algorithm and some code which demonstrates its behavior in this SO answer here.

"This results in a complete lack of reader or writer starvation. It is simply fair". So yes, the unique_lock would be processed as expected, and writer threads wouldn't be starved? Would you still like a code example? — scx, May 14 '19 at 16:17

shared_mutex lock ordering

1 Answers1