Clever Geek Handbook

Locking reciprocal resource pairs

Consider the following:

// There are guys:
class Guy {
    // Each guy can have a buddy:
    Guy* buddy; // When a guy has a buddy, he is his buddy buddy, i.e:
                // assert(!buddy || buddy->buddy == this);

public:
    // When guys are birthed into the world they have no buddy:
    Guy()
        : buddy{}
    {}

    // But guys can befriend each other:
    friend void befriend(Guy& a, Guy& b) {
        // Except themselves:
        assert(&a != &b);

        // Their old buddies (if any), lose their buddies:
        if (a.buddy) { a.buddy->buddy = {}; }
        if (b.buddy) { b.buddy->buddy = {}; }

        a.buddy = &b;
        b.buddy = &a;
    }

    // When a guy moves around, he keeps track of his buddy
    // and lets his buddy keep track of him:
    friend void swap(Guy& a, Guy& b) {
        std::swap(a.buddy, b.buddy);
        if (a.buddy) { a.buddy->buddy = &a; }
        if (b.buddy) { b.buddy->buddy = &b; }
    }
    Guy(Guy&& guy)
        : Guy()
    {
        swap(*this, guy);
    }
    Guy& operator=(Guy guy) {
        swap(*this, guy);
        return *this;
    }

    // When a Guy dies, his buddy loses his buddy.
    ~Guy() {
        if (buddy) { buddy->buddy = {}; }
    }
};

Everything is fine so far, but now I want this to work when buddies are used on different threads. No problem, just paste std::mutex

in Guy

:

class Guy {
    std::mutex mutex;

    // same as above...
};

Now I just need to lock the mutexes of both guys before I can bind or unpair them.

This is where I am stumped. Here are the failed attempts (using the destructor as an example):

  • Dead end:

    ~Guy() {
    std::unique_lock<std::mutex> lock{mutex};
    if (buddy) {
        std::unique_lock<std::mutex> buddyLock{buddy->mutex};
        buddy->buddy = {};
    }
}

    When two buddies are destroyed at about the same time, it is possible that they each lock their own mutex before trying to lock their deadlocks, resulting in a deadlock.

  • Race condition:

    So, we just need to lock the mutexes in sequential order, either manually or with std::lock

    :

    ~Guy() {
    std::unique_lock<std::mutex> lock{mutex, std::defer_lock};
    if (buddy) {
        std::unique_lock<std::mutex> buddyLock{buddy->mutex, std::defer_lock};
        std::lock(lock, buddyLock);
        buddy->buddy = {};
    }
}

    Unfortunately, to access the friends' mutex, we have to access the buddy

    one that is not protected by any lock at that moment and may be in the process of being modified from another thread, which is a race condition.

  • Doesn't scale:

    Correctness can be achieved with a global mutex:

    static std::mutex mutex;
~Guy() {
    std::unique_lock<std::mutex> lock{mutex};
    if (buddy) { buddy->buddy = {}; }
}

    But this is undesirable for performance and scalability reasons.

So is it possible to do without global locking? How?

+3


source to share


1 answer


Usage is std::lock

not a race condition (per se) and does not risk braking.

std::lock

will use a non-deadlock algorithm to acquire two locks. They will be some kind of (unspecified) try-and-retreat method.

An alternative is to define an arbitrary locking order, for example using the physical address of the objects.

You have correctly ruled out the possibility that the interlocutor is objects by itself, so there is no risk of trying twice to do lock()

the same mutex

.

I say this is not a race condition per se, because what this code will do is to guarantee the integrity that if a has buddy b, then b has buddy a for all a and b.

The fact that one moment after the friendship with two objects they may be unfriendly by another thread, presumably you intend or are addressed by another synchronization.

Note also that when you become friends and may not be friends with new friends, you need to immediately lock ALL objects. These are the two "be" friends and their current friends (if any). Hence, you need to lock 2,3 or 4 mutexes.

std::lock

unfortunately does not accept an array, but there is a version that does it in boost or you need to refer to it manually.

To clarify, I read examples of possible destructors as models. Synchronization on the same locks will be required in all relevant elements (for example befriend()

, swap()

and unfriend()

, if necessary). Indeed, the problem of blocking 2,3 or 4 refers to the element befriend()

.



Also, the destructor is probably the worst example, since, as mentioned in the comment, it is illogical that the object is destroyed, but could be in lock conflict with another thread. Some synchronization certainly has to exist in the broader program to make this impossible, at this point the lock in the destructor is redundant.

Indeed, a construct that ensures that objects Guy

have no interlocutor before destruction looks like a good idea and a debugging prerequisite to check assert(buddy==nullptr)

in the destructor. Unfortunately, this cannot be ruled out as a runtime exception, because throwing exceptions in destructors can lead to program termination ( std::terminate()

).

In fact, the real problem (which may depend on the surrounding program) is how to be unfriendly when making friends. This will require a try-retreat loop:

  • Block a and b.
  • Find out if they have friends.
  • If they are already friends, you're done.
  • If they have other buddies, open a and b and lock a and b and their buddies (if any).
  • Make sure buddies haven't changed if they go again.
  • Adjust the appropriate items.

This is a question for the surrounding program, whether it is at risk of live-blocking, but any try-retreat method has the same risk.

That std::lock()

a and b won't work , and then std::lock()

pals, because that will slow down the risk.

So, to answer the question - yes, it is possible without global locking, but it depends on the surrounding program. It can be in a population of many objects Guy

. But it could be that there are a small number of objects that are fighting fervently (possibly in a large population), which leads to a problem. This cannot be appreciated without understanding the broader application.

One way to solve this problem is lock escalation, which essentially boils down to global locking. In essence, this would mean that if there were too many trips around the retry loop, the global semaphore would be configured to have all threads go into global blocking mode for a while. Some time can be a number of actions or a period of time or until the global blocking debate ends!

So the final answer is, "Yes, it is absolutely possible, if it doesn't work, in this case no."

+2


source






More articles:


All Articles