☠️ Deadlocks — Bài toán Triết gia ăn tối

Deadlock xảy ra khi hai hoặc nhiều threads chờ đợi lẫn nhau mãi mãi, không ai có thể tiến triển.

Deadlock là gì?

Real-world Analogy: Ngã tư không đèn

┌─────────────────────────────────────────────────────────────────┐
│                    DEADLOCK VISUALIZATION                        │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│                         🚗 Car B                                 │
│                            │                                    │
│                            ▼                                    │
│               ┌────────────────────────┐                        │
│     🚗 Car A  │                        │ 🚗 Car C               │
│      ───────► │     ☠️ DEADLOCK!      │ ◄───────               │
│               │  Không ai nhường ai   │                        │
│               └────────────────────────┘                        │
│                            ▲                                    │
│                            │                                    │
│                         🚗 Car D                                 │
│                                                                 │
│  Mỗi xe chờ xe bên phải đi trước → Không ai đi được!            │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

4 Điều kiện Coffman (1971)

Deadlock xảy ra khi đồng thời có đủ 4 điều kiện:

Điều kiện	Mô tả	Ví dụ
Mutual Exclusion	Resource chỉ 1 thread dùng tại một thời điểm	Mutex chỉ 1 thread lock được
Hold and Wait	Thread giữ resource và chờ resource khác	Lock mtx1, chờ mtx2
No Preemption	Không thể "cướp" resource từ thread khác	Không thể force unlock mutex
Circular Wait	Chuỗi threads chờ vòng tròn	T1→T2→T3→T1

💡 KEY INSIGHT

Phá vỡ bất kỳ 1 trong 4 điều kiện = Tránh deadlock!

Simple Deadlock Demo

cpp

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mutexA;
std::mutex mutexB;

void thread1() {
    std::cout << "Thread 1: Trying to lock A...\n";
    std::lock_guard<std::mutex> lockA(mutexA);
    std::cout << "Thread 1: Locked A!\n";
    
    // Simulate some work
    std::this_thread::sleep_for(std::chrono::milliseconds(100));
    
    std::cout << "Thread 1: Trying to lock B...\n";
    std::lock_guard<std::mutex> lockB(mutexB);  // ☠️ BLOCKED!
    std::cout << "Thread 1: Locked B!\n";
}

void thread2() {
    std::cout << "Thread 2: Trying to lock B...\n";
    std::lock_guard<std::mutex> lockB(mutexB);
    std::cout << "Thread 2: Locked B!\n";
    
    // Simulate some work
    std::this_thread::sleep_for(std::chrono::milliseconds(100));
    
    std::cout << "Thread 2: Trying to lock A...\n";
    std::lock_guard<std::mutex> lockA(mutexA);  // ☠️ BLOCKED!
    std::cout << "Thread 2: Locked A!\n";
}

int main() {
    std::thread t1(thread1);
    std::thread t2(thread2);
    
    t1.join();
    t2.join();  // ☠️ Program hangs forever!
    
    return 0;
}

Timeline

┌─────────────────────────────────────────────────────────────────┐
│                    DEADLOCK TIMELINE                             │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Time    Thread 1                    Thread 2                   │
│  ─────   ─────────                   ─────────                  │
│  t0      Lock A ✅                                              │
│  t1                                  Lock B ✅                  │
│  t2      Try lock B ⏳ (waiting)                                │
│  t3                                  Try lock A ⏳ (waiting)    │
│  t4      Still waiting...            Still waiting...           │
│  t5      ☠️ DEADLOCK                 ☠️ DEADLOCK                │
│          (T1 holds A, wants B)       (T2 holds B, wants A)      │
│                                                                 │
│         ┌──────┐         waits for          ┌──────┐            │
│         │  T1  │ ──────────────────────────►│  T2  │            │
│         │      │◄──────────────────────────│      │            │
│         └──────┘         waits for          └──────┘            │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🍝 Bài toán Dining Philosophers

Problem Statement

5 triết gia ngồi quanh bàn tròn. Giữa mỗi cặp triết gia có 1 chiếc đũa (chopstick). Để ăn, mỗi người cần cả 2 đũa (trái và phải).

┌─────────────────────────────────────────────────────────────────┐
│                    DINING PHILOSOPHERS                           │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│                          🧘 P0                                   │
│                        /      \                                 │
│                    🥢0          🥢1                              │
│                    /              \                             │
│                 🧘 P4              🧘 P1                         │
│                  |                  |                           │
│                🥢4                  🥢2                          │
│                  |                  |                           │
│                 🧘 P3 ──── 🥢3 ──── 🧘 P2                        │
│                                                                 │
│  Mỗi philosopher:                                               │
│  1. Think (suy nghĩ)                                            │
│  2. Pick up LEFT chopstick                                      │
│  3. Pick up RIGHT chopstick                                     │
│  4. Eat (ăn)                                                    │
│  5. Put down both chopsticks                                    │
│  6. Repeat                                                      │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

❌ Naive Implementation (Deadlock-prone)

cpp

#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#include <chrono>

const int NUM_PHILOSOPHERS = 5;
std::mutex chopsticks[NUM_PHILOSOPHERS];

void philosopher(int id) {
    int leftChopstick = id;
    int rightChopstick = (id + 1) % NUM_PHILOSOPHERS;
    
    for (int meal = 0; meal < 3; ++meal) {
        // Think
        std::cout << "Philosopher " << id << " is thinking...\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        
        // ⚠️ DEADLOCK RISK: Pick up left, then right
        std::cout << "Philosopher " << id << " picks up left chopstick " 
                  << leftChopstick << "\n";
        std::lock_guard<std::mutex> leftLock(chopsticks[leftChopstick]);
        
        // ⚠️ Nếu tất cả cùng lấy đũa trái đồng thời...
        std::this_thread::sleep_for(std::chrono::milliseconds(10));
        
        std::cout << "Philosopher " << id << " picks up right chopstick " 
                  << rightChopstick << "\n";
        std::lock_guard<std::mutex> rightLock(chopsticks[rightChopstick]);
        
        // Eat
        std::cout << "Philosopher " << id << " is eating (meal " 
                  << meal + 1 << ")\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        
        // Put down (automatic with RAII)
    }
    
    std::cout << "Philosopher " << id << " is done!\n";
}

int main() {
    std::vector<std::thread> philosophers;
    
    for (int i = 0; i < NUM_PHILOSOPHERS; ++i) {
        philosophers.emplace_back(philosopher, i);
    }
    
    for (auto& p : philosophers) {
        p.join();  // ☠️ Có thể hang mãi mãi!
    }
    
    return 0;
}

💡 Solutions

Solution 1: Resource Ordering

Phá vỡ Circular Wait: Luôn lock theo thứ tự cố định.

cpp

void philosopherOrdered(int id) {
    int leftChopstick = id;
    int rightChopstick = (id + 1) % NUM_PHILOSOPHERS;
    
    // ✅ Luôn lock chopstick có ID nhỏ hơn trước
    int first = std::min(leftChopstick, rightChopstick);
    int second = std::max(leftChopstick, rightChopstick);
    
    for (int meal = 0; meal < 3; ++meal) {
        std::cout << "Philosopher " << id << " thinking...\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        
        // Lock theo thứ tự cố định
        std::lock_guard<std::mutex> firstLock(chopsticks[first]);
        std::lock_guard<std::mutex> secondLock(chopsticks[second]);
        
        std::cout << "Philosopher " << id << " eating!\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

Solution 2: std::lock() — Locking mọi thứ cùng lúc

cpp

void philosopherAtomicLock(int id) {
    int left = id;
    int right = (id + 1) % NUM_PHILOSOPHERS;
    
    for (int meal = 0; meal < 3; ++meal) {
        std::cout << "Philosopher " << id << " thinking...\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        
        // ✅ Lock cả 2 atomically, không deadlock
        std::lock(chopsticks[left], chopsticks[right]);
        
        // adopt_lock: mutex đã locked, chỉ quản lý unlock
        std::lock_guard<std::mutex> leftLock(chopsticks[left], std::adopt_lock);
        std::lock_guard<std::mutex> rightLock(chopsticks[right], std::adopt_lock);
        
        std::cout << "Philosopher " << id << " eating!\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

Solution 3: C++17 std::scoped_lock

cpp

void philosopherScopedLock(int id) {
    int left = id;
    int right = (id + 1) % NUM_PHILOSOPHERS;
    
    for (int meal = 0; meal < 3; ++meal) {
        std::cout << "Philosopher " << id << " thinking...\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        
        // ✅ C++17: Simple and safe
        std::scoped_lock lock(chopsticks[left], chopsticks[right]);
        
        std::cout << "Philosopher " << id << " eating!\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

Solution 4: Try-Lock with Backoff

cpp

void philosopherTryLock(int id) {
    int left = id;
    int right = (id + 1) % NUM_PHILOSOPHERS;
    
    for (int meal = 0; meal < 3; ++meal) {
        std::cout << "Philosopher " << id << " thinking...\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        
        while (true) {
            // Try to lock left
            std::unique_lock<std::mutex> leftLock(chopsticks[left], std::try_to_lock);
            if (!leftLock.owns_lock()) {
                std::this_thread::yield();
                continue;
            }
            
            // Try to lock right
            std::unique_lock<std::mutex> rightLock(chopsticks[right], std::try_to_lock);
            if (!rightLock.owns_lock()) {
                // ✅ Release left, back off, try again
                leftLock.unlock();
                std::this_thread::sleep_for(std::chrono::milliseconds(10));
                continue;
            }
            
            // Got both!
            std::cout << "Philosopher " << id << " eating!\n";
            std::this_thread::sleep_for(std::chrono::milliseconds(100));
            break;
        }
    }
}

Solution 5: Arbitrator (Waiter/Conductor)

cpp

std::mutex waiter;  // Central arbitrator

void philosopherWithWaiter(int id) {
    int left = id;
    int right = (id + 1) % NUM_PHILOSOPHERS;
    
    for (int meal = 0; meal < 3; ++meal) {
        std::cout << "Philosopher " << id << " thinking...\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        
        // ✅ Xin phép waiter trước khi lấy đũa
        {
            std::lock_guard<std::mutex> permission(waiter);
            std::lock_guard<std::mutex> leftLock(chopsticks[left]);
            std::lock_guard<std::mutex> rightLock(chopsticks[right]);
            
            std::cout << "Philosopher " << id << " eating!\n";
            std::this_thread::sleep_for(std::chrono::milliseconds(100));
        }
    }
}

⚠️ Arbitrator Drawback

Giảm concurrency — chỉ 1 philosopher eat tại một thời điểm trong ví dụ này.

Best Practices để Tránh Deadlock

1. Lock Ordering

cpp

// Quy ước: Luôn lock theo thứ tự ID tăng dần
// Nếu cần lock A, B, C: luôn theo thứ tự A → B → C

class BankAccount {
    int id_;
    // ...
};

void transfer(BankAccount& from, BankAccount& to, int amount) {
    // ✅ Lock theo thứ tự ID
    BankAccount& first = (from.id_ < to.id_) ? from : to;
    BankAccount& second = (from.id_ < to.id_) ? to : from;
    
    std::scoped_lock lock(first.mutex_, second.mutex_);
    // ... transfer ...
}

2. Dùng std::scoped_lock (C++17)

cpp

// ✅ PREFERRED: Không thể deadlock
std::scoped_lock lock(mutex1, mutex2, mutex3);

3. Avoid Holding Locks khi gọi Unknown Code

cpp

// ❌ Dangerous
void bad() {
    std::lock_guard<std::mutex> lock(mtx);
    callback();  // callback có thể lock mtx → recursive deadlock
}

// ✅ Safe
void good() {
    Data localCopy;
    {
        std::lock_guard<std::mutex> lock(mtx);
        localCopy = sharedData;
    }
    callback(localCopy);  // No lock held
}

4. Lock Timeout

cpp

std::timed_mutex tmtx;

void withTimeout() {
    if (tmtx.try_lock_for(std::chrono::seconds(1))) {
        std::lock_guard<std::timed_mutex> lock(tmtx, std::adopt_lock);
        // ... work ...
    } else {
        // Log và handle failure
        std::cerr << "Lock timeout! Possible deadlock.\n";
    }
}

5. Lock Hierarchy

cpp

// Assign "levels" to mutexes. Only lock lower → higher level.
class HierarchicalMutex {
    std::mutex internal_mutex_;
    unsigned long const hierarchy_value_;
    unsigned long previous_hierarchy_value_;
    static thread_local unsigned long this_thread_hierarchy_value_;
    
    void check_for_hierarchy_violation() {
        if (this_thread_hierarchy_value_ <= hierarchy_value_) {
            throw std::logic_error("Mutex hierarchy violated!");
        }
    }
    
public:
    explicit HierarchicalMutex(unsigned long value) 
        : hierarchy_value_(value), previous_hierarchy_value_(0) {}
    
    void lock() {
        check_for_hierarchy_violation();
        internal_mutex_.lock();
        update_hierarchy_value();
    }
    
    void unlock() {
        this_thread_hierarchy_value_ = previous_hierarchy_value_;
        internal_mutex_.unlock();
    }
    
private:
    void update_hierarchy_value() {
        previous_hierarchy_value_ = this_thread_hierarchy_value_;
        this_thread_hierarchy_value_ = hierarchy_value_;
    }
};

thread_local unsigned long HierarchicalMutex::this_thread_hierarchy_value_ = ULONG_MAX;

Detecting Deadlocks

Tools

Tool	Platform	Command
Helgrind	Linux	`valgrind --tool=helgrind ./app`
ThreadSanitizer	GCC/Clang	`-fsanitize=thread`
Intel Inspector	Cross-platform	GUI tool

Runtime Detection Pattern

cpp

#include <chrono>

bool tryWithTimeout() {
    auto start = std::chrono::steady_clock::now();
    auto timeout = std::chrono::seconds(5);
    
    while (!resource.try_lock()) {
        if (std::chrono::steady_clock::now() - start > timeout) {
            std::cerr << "POTENTIAL DEADLOCK DETECTED!\n";
            return false;  // Or throw exception
        }
        std::this_thread::sleep_for(std::chrono::milliseconds(10));
    }
    
    return true;
}

📚 Tổng kết

┌─────────────────────────────────────────────────────────────────┐
│                  DEADLOCK PREVENTION CHECKLIST                   │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  ✅ Dùng std::scoped_lock cho multiple mutexes                  │
│  ✅ Thiết lập và tuân thủ lock ordering                         │
│  ✅ Minimize lock duration                                      │
│  ✅ Không gọi unknown code khi holding lock                     │
│  ✅ Dùng lock timeout cho critical systems                      │
│  ✅ Test với ThreadSanitizer                                    │
│                                                                 │
│  ❌ TRÁNH:                                                      │
│  ❌ Nested locks với thứ tự không nhất quán                     │
│  ❌ Holding lock trong thời gian dài                            │
│  ❌ Calling callbacks while holding locks                       │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🎯 Module Summary

Chúc mừng! Bạn đã hoàn thành Part 1: Concurrency trong C++:

Topic	Key Takeaway
Threads	`std::thread`, `join()`, `detach()`
Race Conditions	Shared mutable state = 💥
Synchronization	`mutex`, `lock_guard`, `unique_lock`
Deadlocks	Lock ordering, `std::scoped_lock`

Coming in Part 2...

Condition Variables: Waiting for events
Atomic Operations: Lock-free programming
Memory Model: std::memory_order
Thread Pools: Reusing threads efficiently

"Debugging is twice as hard as writing the code in the first place. Debugging concurrent code? That's like debugging while blindfolded in a room where the furniture keeps moving." — Unknown

☠️ Deadlocks — Bài toán Triết gia ăn tối ​

Deadlock là gì? ​

Real-world Analogy: Ngã tư không đèn ​

4 Điều kiện Coffman (1971) ​

Simple Deadlock Demo ​

Timeline ​

🍝 Bài toán Dining Philosophers ​

Problem Statement ​

❌ Naive Implementation (Deadlock-prone) ​

💡 Solutions ​

Solution 1: Resource Ordering ​

Solution 2: std::lock() — Locking mọi thứ cùng lúc ​

Solution 3: C++17 std::scoped_lock ​

Solution 4: Try-Lock with Backoff ​

Solution 5: Arbitrator (Waiter/Conductor) ​

Best Practices để Tránh Deadlock ​

1. Lock Ordering ​

2. Dùng std::scoped_lock (C++17) ​

3. Avoid Holding Locks khi gọi Unknown Code ​

4. Lock Timeout ​

5. Lock Hierarchy ​

Detecting Deadlocks ​

Tools ​

Runtime Detection Pattern ​

📚 Tổng kết ​

🎯 Module Summary ​

Coming in Part 2... ​