Talk:cpp/named req/Mutex

single total order

The text states:

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

What does this mean?

Does this mean, that if thread_0 locked the mutex; and then thread_1, thread_2, thread_3, etc. call lock() on it in this order, will they obtain the lock on the mutex in this same order??

Run this code

#include <iostream>
#include <mutex>
#include <thread>
#include <atomic>
#include <functional>
#include <cassert>
#include <vector>
 
std::mutex mut;
unsigned cnt;
std::atomic<bool> wait;
 
void func(unsigned i) {
    std::lock_guard<std::mutex> lock(mut);
 
    while (wait) {
        std::this_thread::sleep_for(std::chrono::milliseconds{10});
    }
 
    if (i != cnt) {
        std::cout << "Error: "
                  << "i == " << i << "    cnt == " << cnt << std::endl;
        abort();
    }
    ++cnt;
}
 
int main()
{
    wait = true;
 
    std::vector<std::thread> vec;
    for (unsigned i = 0; i < 20; ++i) {
        vec.emplace_back(std::thread{std::bind(func, i)});
        std::this_thread::sleep_for(std::chrono::milliseconds{3}); // wait briefly, so that above thread runs into lock...
    }
 
    wait = false;
 
 
    for (auto &th : vec) {
        th.join();
    }
    std::cout << "Done. Wakeups of threads, in same order as they were put to sleep." << std::endl;
    return 0;
}

Thanks

Ajneu (talk) 06:50, 12 June 2016 (PDT)

no, that's not what the line refers to. It is saying the mutex acts as (and is often implemented by means of) an atomic memory location: it has its timeline, independent of any thread's timeline. I'll wikilink it to std::memory_order. --Cubbi (talk) 09:29, 12 June 2016 (PDT)

Ok thanks.
Does this then mean, that the order of aquiring the mutex (and continuing code-execution), could be in a different order, than the order in which the threads were put to sleep???

Just consider this as an example: I want to put events into a queue, in the exact order in which they occurred.
Can I just protect by a mutex, or do I need some special code, where the thread "pulls an atomic ticket".

• Here's an example with just a mutex. Will this keep the order???

Run this code

#include <iostream>
#include <mutex>
#include <thread>
#include <queue>
 
void function(unsigned i) {
    std::lock_guard<std::mutex> lock(mut);
 
    my_queue.push(i)
}

• Here's an example with pulling an atomic ticket and keeping appropriate order:

Run this code

#include <mutex>
#include <thread>
#include <limits>
#include <atomic>
#include <cassert>
#include <condition_variable>
#include <map>
 
std::mutex mut;
std::atomic<unsigned> num_atomic{std::numeric_limits<decltype(num_atomic.load())>::max()};
unsigned num_next{0};
std::map<unsigned, std::condition_variable> mapp;
 
void function(int i) {
    unsigned next = ++num_atomic; // pull a ticket
 
    decltype(mapp)::iterator it;
 
    std::unique_lock<std::mutex> lock(mut);
    if (next != num_next) {
        auto it = mapp.emplace(std::piecewise_construct,
                               std::forward_as_tuple(next),
                               std::forward_as_tuple()).first;
        it->second.wait(lock);
        mapp.erase(it);
    }
 
 
    // THE FUNCTION'S INTENDED WORK IS NOW DONE
    // ...
    my_queue.push(i);
    // ...
    // THE FUNCTION'S INDENDED WORK IS NOW FINISHED
 
 
 
    ++num_next;
 
    it = mapp.find(num_next); // this is not necessarily mapp.begin(), since wrap_around occurs on the unsigned                                                                          
    if (it != mapp.end()) {
        lock.unlock();
        it->second.notify_one();
    }
}

Which one does what I want (keep the order)? Is the "mutex" alone good enough, or do I need to "pull the atomic ticket"?

I'm finding it difficult to see clearly on this...

Ajneu (talk) 10:26, 12 June 2016 (PDT)

it may be more efficient to look at programming forums or Q&A websites than this discussion page. For example, here's the StackOverflow discussion of POSIX mutex wake order: http://stackoverflow.com/questions/14947191 (short answer: there isn't any, just as in C++, although POSIX makes an explicit mention of the current scheduling policy as the determining factor).

Thanks. Ajneu (talk) 11:24, 12 June 2016 (PDT)