How to prevent deadlock in dining philosopher c++

Question

I'm trying to fix a deadlock in the dining philosophers problem. I already have a code-skeleton that was provided by my teacher.

I tried to fix the problem using try_lock()

chopstick[(i+1)%5].try_lock(); 

but this didn't fix my problem and I did get the following error message when i did run it: error "unlock of unowned mutex".

I also tried to fix the problem by doing the following changes which I saw in a youtube video

chopstick[i].lock();

to

chopstick[min(i,(i+1)%5)].lock();

and also

chopstick[(i+1)%5].lock();

to

chopstick[max(i,(i+1)%5)].lock();

This i the skeleton that i was provided.

#include <windows.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <thread>
#include <mutex>
#include <time.h>

using namespace std;

thread task[5];
mutex chopstick[5];
int stop = false;

void go(int i) {
    while (!stop) {

        chopstick[i].lock();

        cout << i << ": takes: " << i << endl;
        chrono::milliseconds dur(20);
        this_thread::sleep_for(dur); //Leads to deadlock immediately
        chopstick[(i + 1) % 5].lock();

        cout << i << ": eating" << endl;

        chrono::milliseconds dur2(rand() % 200 + 100);
        this_thread::sleep_for(dur2);

        chopstick[(i + 1) % 5].unlock();
        chopstick[i].unlock();
    }
}
int main() {
    srand(time(NULL));

    for (int i = 0; i < 5; ++i) {
        task[i] = (thread(go, i));
    }
    for (int i = 0; i < 5; i++) {
        task[i].join();
    }

}

I understand the dining philosophers in theory but i can't manage ti fix this problem. I do not really understand what I'm doing wrong. Can someone please explain what i'm doing wrong and help me fix it?

Answer 1

The easiest way to fix the deadlock is to use the std::lock(l1, l2) which was invented just for this purpose.

Change:

    chopstick[i].lock();

    cout << i << ": takes: " << i << endl;
    chrono::milliseconds dur(20);
    this_thread::sleep_for(dur); //Leads to deadlock immediately
    chopstick[(i + 1) % 5].lock();

to:

    std::lock(chopstick[i], chopstick[(i + 1) % 5]);

    cout << i << ": takes: " << i << endl;

That is a straight-forward solution that ignores exception safety, which is fine for getting your first dead-lock avoidance lesson down.

To make it exception-safe, the mutexes need to be wrapped in the RAII device: std::unique_lock:

    unique_lock<mutex> left{chopstick[i], defer_lock};
    unique_lock<mutex> right{chopstick[(i + 1) % 5], defer_lock};
    lock(left, right);

    cout << i << ": takes: " << i << endl;

And then you should also remove the explicit unlock statements, since the destructors of left and right will take care of that.

Now if anything throws an exception within go, the destructors for left and right will unlock the mutexes as the exception propagates out.

To learn more about what is going on under the hood of std::lock to avoid deadlock, see: http://howardhinnant.github.io/dining_philosophers.html

Performance Test

Here's a quick & easy test to compare the use of std::lock against the more traditional advice of "order your mutexes".

#ifndef USE_STD_LOCK
#   error #define USE_STD_LOCK as 1 to use std::lock and as 0 to use ordering
#endif

#include <atomic>
#include <chrono>
#include <exception>
#include <iomanip>
#include <iostream>
#include <mutex>
#include <thread>

std::thread task[5];
constexpr auto N = sizeof(task)/sizeof(task[0]);
std::mutex chopstick[N];
std::atomic<bool> stop{false};
unsigned long long counts[N] = {};

using namespace std::chrono_literals;

void
go(decltype(N) i)
{
    auto const right = (i + 1) % N;
    decltype(right) const left = i;
    while (!stop)
    {
#if USE_STD_LOCK
        std::lock(chopstick[left], chopstick[right]);
#else
        if (left < right)
        {
            chopstick[left].lock();
            chopstick[right].lock();
        }
        else
        {
            chopstick[right].lock();
            chopstick[left].lock();
        }
#endif
        std::lock_guard<std::mutex> l1{chopstick[left],  std::adopt_lock};
        std::lock_guard<std::mutex> l2{chopstick[right], std::adopt_lock};
        ++counts[i];
        std::this_thread::sleep_for(1ms);
    }
}

void
deadlock_detector(std::chrono::seconds time_out)
{
    std::this_thread::sleep_for(time_out);
    std::cerr << "Deadlock!\n";
    std::terminate();
}

int
main()
{
    for (auto i = 0u; i < N; ++i)
        task[i] = std::thread{go, i};
    std::thread{deadlock_detector, 15s}.detach();
    std::this_thread::sleep_for(10s);
    stop = true;
    for (auto& t : task)
        t.join();
    std::cout << std::right;
    for (auto c : counts)
        std::cout << std::setw(6) << c << '\n';
    auto count = std::accumulate(std::begin(counts), std::end(counts), 0ULL);
    std::cout << "+ ----\n";
    std::cout << std::setw(6) << count << '\n';
}

This must be compiled with USE_STD_LOCK defined:

1. #define USE_STD_LOCK 0 to order your mutexes and lock them in order.
2. #define USE_STD_LOCK 1 to lock your mutexes with std::lock.

The program runs for 10 seconds, with each thread incrementing a distinct unsigned long long as often as possible. But then to make things a little more dramatic, each thread also sleeps for 1ms while holding the locks as well (run without this sleep if you want).

After the 10s, main tells everybody the shift is over and tallies the result for each thread, and the total increments for all of the threads. Higher is better.

Running with optimizations enabled, I get numbers like:

USE_STD_LOCK = 1

  3318
  2644
  3254
  3004
  2876
+ ----
 15096

USE_STD_LOCK = 0

    19
    96
  1641
  5885
    50
+ ----
  7691

Note that the use of std::lock not only results in a much higher cumulative result, but that each thread contributes approximately the same amount to the total. In contrast, "ordering" tends to prefer a single thread, starving the others, in some cases quite severely.

This is on a 4-core Intel core i5. I attribute the difference to having multiple cores so that at least two threads can run concurrently. If this is run on a single core device, I would not expect this difference (I haven't tested that configuration).

I've also instrumented the test with a deadlock detector. This does not impact the results I get. It is intended to allow people to experiment with other locking algorithms, and more quickly determine if the test has locked up. If this deadlock detector bothers you in any way, simply delete it from your test run. I have no desire to debate its merits.

I welcome constructive feedback, either if you get similar results, or different. Or if you think this test is biased one way or the other, and how it might be made better.

C++17 Update

With C++17 and later, there's a more concise way to call std::lock compared to the use of unique_lock/lock_guard. You can use scoped_lock instead which calls std::lock for you under the hood. That is, change:

unique_lock<mutex> left{chopstick[i], defer_lock};
unique_lock<mutex> right{chopstick[(i + 1) % 5], defer_lock};
lock(left, right);

to:

scoped_lock lk{chopstick[i], chopstick[(i + 1) % 5]};

This single line gives you both the deadlock avoidance of std::lock and the exception safety of unique_lock/lock_guard in one convenient package.

Answer 2

There are four (4) conditions which are necessary and sufficient to produce deadlock.

Deadlock Conditions

• Resource mutual exclusion (resources cannot be shared)

The resources considered (requested) must not be shareable. When resources are allowed to be shared, then (sibling) process(es) are not prevented from obtaining resource(s) when needed.

• Resource hold and wait or persistence (partial allocation)

Processes must hold resources already allocated, and wait (attempt to seize) subsequent (requested) resource(s). When process must release held resources when new resource(s) are requested, then deadlock cannot occur because process does not prevent (sibling) process(es) from obtaining resource(s) when needed.

• Resource preemption not allowed (process equality or fairness)

Process cannot have resources taken away when held. Otherwise, higher priority (rank) process would simply take (seize) enough resources to enable process to finish. Many RTOS use this method to prevent deadlock.

• Resource circular order or wait (cycle exists in resource graph)

A circular ordering or cycle (chain) exists in the resources, where the resources cannot be arranged in a partial order (numbered min .. max). When a partial order can be imposed on the resources, then resources can be seized (locked) obeying that strict order, and no deadlock can occur (see the cycle theorem, which states that a "cycle in a resource graph is necessary so that deadlock can occur").

The Dining Philosophers problem (though experiment) is constructed to present all four conditions, and the challenge is to decide which condition(s) to avoid (break). One classic answer is to change the ordering of resources to break the circular wait condition. Each philosopher independently decides how to solve the deadlock.

• Shareable - each Philosopher needs two forks and cannot share.
• Persistent - each Philosopher must keep one fork while taking another.
• No preemption - no Philosopher will take a fork from another.
• Circular order - there is a cycle, so two philosophers collide and deadlock.

There are several well-known solutions:

• Djikstra's solution - number the forks (1 .. N) and all philosophers take forks according to the rule: take lower numbered fork, then higher numbered fork, and release any resources on collision.
• Arbitrator (monitor) - an arbitrator assigns forks, when a philosopher wants to eat, they ask the arbitrator, who serializes their requests, and assigns (doles out) resources (forks) when available.

Djikstra's is the canonical solution - number your forks.

Answer 3

One of the core rules of parallel programming (with locks), is that you should always grab locks in the same order.

In your code, each task takes its lock first, then takes the next lock. One solution is to always grab locks from even indices, and only then grab locks from odd indices. That way, the order in which you grab locks will stay consistent.

Another well-known strategy is the 'backoff' in which you acquire the first lock using lock(), and try_lock() for the subsequent locks, and if one cannot be obtained, you release all the obtained locks and start the sequence all over again. This strategy isn't good in terms of performance, but it's guaranteed it'll work eventually.