storing mutexes in a vector/deque c++

Question

I would like to store a variable number of mutexes in a container like vector or deque.

In one of the use cases, I need to reliably and deadlock-free lock all of the mutexes. I would also like to have exception safety guarantee, that if an exception is thrown, all of the mutexes are as if no locking occured.

I am trying to do something like:

std::vector<std::mutex> locks_(n);
std::vector<std::lock_guard<std::mutex> > guards(n);
for(int i = 0; i < n; i++) {
    std::lock_guard<std::mutex> guard(locks_[i]);
    guards.emplace_back(std::move(guard));
}

but it doesn't compile, giving me:

/usr/include/c++/4.8/ext/new_allocator.h:120:4: error: use of deleted function ‘std::lock_guard<_Mutex>::lock_guard(const std::lock_guard<_Mutex>&) [with _Mutex = std::mutex]’

I guess there might also be a problem when lock_guards are destroyed, because the order must be reversed as compared to construction, but the standard saves us with:

The delete-expression will invoke the destructor (if any) for the object or the elements of the array being deleted. In the case of an array, the elements will be destroyed in order of decreasing address (that is, in reverse order of the completion of their constructor; see 12.6.2).

Are there any potential pitfalls with this approach and how can one make it work?

Edit

actually I am wrong, it seems vector does not guarantee a particular order of destruction. See this question: Order of destruction of elements of an std::vector

Edit2

Q: What if the use case is:

All the mutexes are locked/unlocked in any order by different threads (however each of those threads uses only 1 mutex at a time), but at some point I need to lock all of the mutexes in a safe manner in another thread.

Answer 1

With a firm and low upper bound on n you could reasonably do something like this:

#include <iostream>
#include <mutex>
#include <vector>

int
main()
{
    constexpr unsigned n_max = 5;
    unsigned n;
    std::cout << "Enter n: ";
    std::cin >> n;
    if (std::cin.fail())
        throw "oops";
    if (n > n_max)
        throw "oops";
    std::vector<std::mutex> mutexes(n);
    std::vector<std::unique_lock<std::mutex>> locks;
    for (auto& m : mutexes)
        locks.emplace_back(m, std::defer_lock);
    switch (locks.size())
    {
    case 0:
        break;
    case 1:
        locks.front().lock();
        break;
    case 2:
        std::lock(locks[0], locks[1]);
        break;
    case 3:
        std::lock(locks[0], locks[1], locks[2]);
        break;
    case 4:
        std::lock(locks[0], locks[1], locks[2], locks[3]);
        break;
    case 5:
        std::lock(locks[0], locks[1], locks[2], locks[3], locks[4]);
        break;
    default:
        throw "oops";
    }
}

It isn't that pretty. But it is easy to reason about and thus reliable.

Notes:

1. You need to use std::lock(m1, m2, ...) to reliably lock more than one mutex, or re-invent an algorithm such as std::lock to avoid deadlock. One such alternative algorithm is if you can guarantee that everyone always locks the mutexes in mutexes in the same order (say by index), then you don't need std::lock at all, just loop thru and lock `em.

2. lock_guard is problematic to put in vector one at a time as vector<T>::emplace_back requires T to be move constructible. That is one of the reasons why unique_lock works here and lock_guard doesn't. mutexes gets away with holding non-movable mutexes because it constructs the vector all at once instead of adding to it with emplace_back.

3. In this example locks holds references into mutexes. Make sure you don't have lifetime issues between these two containers (mutexes must outlive locks).

4. If you need to add non-movable items to the end of a sequence, switch to deque, that will work where vector won't.

5. Unlocking order doesn't matter, don't worry about it. Locking order matters only if different threads might lock in different orders. If all threads always lock in the same order, don't worry about it. But if all threads always lock in the same order, consider replacing the n mutexes with a single mutex, as that sounds equivalent.

6. The code above assumes that somehow different threads might be locking in a different order, and perhaps a subset of mutexes. And obviously it won't scale to large n.

With Edit2 in the question, I believe this code to be viable. It will reliably work with different threads locking mutexes in different orders. Each thread should form its own local copy of locks and send that through the switch. If a thread for some reason needs its locks to be a subset of mutexes, or to build it in a different order, no problem. That is what this solution is designed for.

Plug

If you are interested in the algorithm behind std::lock, here are performance tests for a variety of potential implementations of it, including test code that you can run on your own platform:

Dining Philosophers Rebooted

If you find that your implementation of std::lock is suboptimal, have a talk with your implementor. :-)

Answer 2

It is ok to construct the lock_guards with new and putting them into unique_ptrs?

Then the vector would hold std::unique_ptr<std::lock_guard<std::mutex>> instead of just std::lock_guard<std::mutex>:

std::vector<std::mutex> locks_(n);
std::vector<std::unique_ptr<std::lock_guard<std::mutex>>> guards(n);
for (int i = 0; i < n; i++) {
  typedef std::lock_guard<std::mutex> LockGuardType;
  std::unique_ptr<LockGuardType> guard(new LockGuardType(locks_[i]));
  guards.emplace_back(std::move(guard));
}

That should compile fine.