🐸 Fanxiang Zhou 🐸
Concurrency(4) Learning Locking Issues

Concurrency(4) Learning Locking Issues


Dining Philosophers Problem

The “Dining Philosophers” is a classic problem of concurrency and synchronization. The problem describes five philosophers sitting around a circular table, alternating between thinking and eating. Between each philosopher is a pair of forks, and they must use these forks to eat. To eat, a philosopher must pick up both the forks to his left and right. If he cannot obtain both at the same time, he must wait. In this scenario, the following issues may arise:

  1. Deadlock : If every philosopher picks up the forks to his left, then they all will wait for the fork on their right. None of them will release the fork they already hold. This forms a cycle of waiting, leading to a deadlock.
  2. Starvation : It’s possible that a particular philosopher consistently fails to acquire forks due to the actions of the others, causing him to never get a chance to eat. 
// five philosophers with five forks
constexpr int PHILOSOPHER_COUNT = 5;
std::vector<std::mutex> forks(PHILOSOPHER_COUNT);

void philosopher(int id) {
    while (true) {
        // thinking
        std::this_thread::sleep_for(std::chrono::milliseconds(500));
        // lock the fork on the left
        forks[id].lock();
        std::cout << "Philosopher " << id << " takes the left fork." << std::endl;
        // thinking again
        std::this_thread::sleep_for(std::chrono::milliseconds(500));
        // lock the fork on the right
        forks[(id + 1) % PHILOSOPHER_COUNT].lock();
        std::cout << "Philosopher " << id << " takes the right fork." << std::endl;
        // eating
        std::cout << "Philosopher " << id << " is eating." << std::endl;
        std::this_thread::sleep_for(std::chrono::milliseconds(500));
        forks[(id + 1) % PHILOSOPHER_COUNT].unlock();
        forks[id].unlock();
    }
}

int main() {
    std::vector<std::jthread> philosophers;
    for (int i = 0; i < PHILOSOPHER_COUNT; i++)
        philosophers.emplace_back(philosopher, i);
    return 0;
}

Deadlock

  • What is Deadlock?
    • A deadlock is a situation in a system where two or more threads cannot proceed with their execution because each thread is waiting for other threads to release resources.
  • When would it happen? Four necessary conditions for deadlock:
    1. Mutual Exclusion : A resource can be held by only one thread at any given moment.
    2. Hold and Wait : A thread holds onto its current resources while requesting new ones.
    3. No Preemption : Resources can only be released voluntarily by the thread that holds them, not forcibly taken away.
    4. Circular Wait : There’s a set of threads where each thread is waiting for the next thread in the set to release a resource. In the aforementioned philosophers’ problem, a deadlock can occur because all philosophers hold their left fork and are unable to obtain their right fork.

Thread Priority

  • What is meant by thread priority?
    • The priority of a thread is a number assigned to it by the operating system
    • A thread with high priority will be scheduled to run more often
    • A thread with low priority will sleep or be interrupted more often
  • Does C++ support thread priority?
    • C++ does not directly support thread priority
    • Thread priority can be set by calling an operating system API
    • The native_handle member function of the std::thread object will return the data which is needed for this call

Resource Starvation

  • What is meant by resource starvation?
    • Resource starvation occurs when a thread cannot get the resources it needs to run
  • Give some examples
    • Deadlock and livelock, in which threads cannot obtain locks they need
    • Insufficient operating system resources which prevent threads from starting
    • In a badly designed scheduler, a low priority thread does not run often enough because higher priority threads monopolize the processor

Livelock

  • What is livelock?
    • A thread is livelocked when it is able to run, but cannot make any progress
  • How does livelock differ from deadlock?
    • In deadlock, the thread cannot run at all
  • Briefly describe a situation where livelock can occur
    • Livelock can occur when trying to avoid deadlock
    • Instead of blocking indefinitely when they cannot get a lock, the threads wait and retry
    • If the lock is not available, the threads will retry indefinitely
    • The threads are able to run, but cannot make any progress

Deadlock Avoidance

We are goint to use serverl methos to avoid the death lock in the Dining Philosophers Problem

try_lock() 

void philosopher(int id) {  
    while (true) {  
        // thinking  
        std::this_thread::sleep_for(std::chrono::milliseconds(500));  
        // try to lock the fork on the left  
        if (forks[id].try_lock()) {  
            std::cout << "Philosopher " << id << " takes the left fork." << std::endl;  
            // thinking again  
            std::this_thread::sleep_for(std::chrono::milliseconds(500));  
            // try to lock the fork on the right  
            if (forks[(id + 1) % PHILOSOPHER_COUNT].try_lock()) {  
                std::cout << "Philosopher " << id << " takes the right fork." << std::endl;  
                // eating  
                std::cout << "Philosopher " << id << " is eating." << std::endl;  
                std::this_thread::sleep_for(std::chrono::milliseconds(500));  
  
                forks[(id + 1) % PHILOSOPHER_COUNT].unlock();  
            }  
            forks[id].unlock();  
        }  
    }  
}

try_lock() vs. Regular lock()

  • Non-blocking : Unlike the typical lock() method, try_lock() is non-blocking. It attempts to acquire the lock, but if the lock is currently held by another thread, it returns immediately without waiting.
  • Return Value : The try_lock() method returns a boolean value indicating the success of the attempt. A return value of true signifies that the lock was successfully acquired, while false indicates the opposite.
  • Why it Helps Avoid Deadlocks : The key advantage of using try_lock() is its behavior when acquiring multiple locks. If a thread tries to acquire all the required locks using try_lock() and any of the attempts fail, it can immediately release all the locks it managed to acquire. This avoids situations where other threads are blocked, potentially leading to deadlocks. Consider the earlier discussed Dining Philosophers problem. If all the philosophers use try_lock() to attempt to pick up their forks:
  • A philosopher who can pick up his left fork but not his right one immediately would release his left fork.
  • This strategy ensures that at any given moment, if a philosopher can’t acquire both forks he needs, he won’t be holding onto any fork, leaving a chance for other philosophers. One downside to this approach is that it might lead to “starvation”, where some philosophers might have to wait for an extended period to get both forks simultaneously. However, from a deadlock standpoint, try_lock() provides an effective mitigation.

std::unique_lock and std::adopt_lock 

void philosopher(int id) {  
    while (true) {  
        // thinking  
        std::this_thread::sleep_for(std::chrono::milliseconds(500));  
        int left_fork = id, right_fork = (id + 1) % PHILOSOPHER_COUNT;  
        if (id == PHILOSOPHER_COUNT - 1)  // To avoid deadlock, the last philosopher picks the right fork first  
            std::swap(left_fork, right_fork);  
        // Lock the forks atomically using std::lock to prevent deadlock
        std::lock(forks[left_fork], forks[right_fork]);
        std::unique_lock<std::mutex> left_lock(forks[left_fork], std::adopt_lock);  
        std::unique_lock<std::mutex> right_lock(forks[right_fork], std::adopt_lock);  
        std::cout << "Philosopher " << id << " takes the LEFT and RIGHT forks then EATING.\n";  
        std::this_thread::sleep_for(std::chrono::milliseconds(500));  
        // when left_lock and right_lock go out of scope, the associated mutexes are automatically released  
    }  
}

This strategy can be implemented more elegantly using std::unique_lock and std::adopt_lock . std::unique_lock provides a flexible way to manage the lifecycle of a mutex lock, while std::adopt_lock is a locking strategy that indicates that the lock is already locked, and we want std::unique_lock to “adopt” the existing lock.

scoped_lock 

void philosopher(int id) {  
    while (true) {  
        // thinking  
        std::this_thread::sleep_for(std::chrono::milliseconds(500));  
        int left_fork = id, right_fork = (id + 1) % PHILOSOPHER_COUNT;  
        // Here we use scoped_lock to lock both left and right forks  
        std::scoped_lock lock(forks[left_fork], forks[right_fork]);  
        std::cout << "Philosopher " << id << " takes the LEFT and RIGHT forks then EATING.\n";  
        std::this_thread::sleep_for(std::chrono::milliseconds(500));  
        // No need to manually unlock the forks, scoped_lock will do it automatically  
    }  
}

After C++17, std::scoped_lock was introduced as a convenient way to lock multiple mutexes and ensure that deadlocks do not occur. std::scoped_lock accepts multiple mutexes at construct time and locks them for their lifetime. These mutexes are automatically unlocked when std::scoped_lock is destroyed.

Livelock of Dining Philosophers Problem

void philosopher(int id) {
    while (true) {
        // thinking
        std::this_thread::sleep_for(std::chrono::milliseconds(500));
        // try to pick up left fork
        if (forks[id].try_lock()) {
            std::cout << "Philosopher " << id << " takes the left fork." << std::endl;
            // Wait a bit before trying for the right fork
            std::this_thread::sleep_for(std::chrono::milliseconds(10));
            // try to pick up right fork
            if (forks[(id + 1) % PHILOSOPHER_COUNT].try_lock()) {
                std::cout << "Philosopher " << id << " takes the right fork." << std::endl;
                // eating
                std::cout << "Philosopher " << id << " is eating." << std::endl;
                std::this_thread::sleep_for(std::chrono::milliseconds(500));
                forks[(id + 1) % PHILOSOPHER_COUNT].unlock();
            }
            forks[id].unlock();
        }
    }
}

If all philosophers took the same action and their attempts were all nearly synchronized, then each philosopher might repeatedly pick up and put down a fork, and no one would actually be able to pick up two forks at the same time to eat. In this code, the philosopher tries to pick up the left fork, then waits a little, and then tries to pick up the right fork. But since their attempts are almost synchronized and the time interval between picking up the forks is very short, no philosopher may be able to pick up both forks at the same time. As a result, they fall into a pattern of constantly trying and failing to pick up both forks. This is the living lock.

© 2023 🐸 Fanxiang Zhou 🐸