Deadlock
"Tê liệt vĩnh viễn"

7.1 Deadlock là gì?

Deadlock = tình huống 2+ process/thread đợi nhau vĩnh viễn — không ai chạy được nữa. Hệ thống "đứng hình" ở phần đó.

Ví dụ kinh điển

// Thread 1
pthread_mutex_lock(&A);   // chiếm A
sleep(1);
pthread_mutex_lock(&B);   // đợi B (đang bị Thread 2 giữ)

// Thread 2
pthread_mutex_lock(&B);   // chiếm B
sleep(1);
pthread_mutex_lock(&A);   // đợi A (đang bị Thread 1 giữ)

// → Cả 2 thread đợi nhau mãi mãi. DEADLOCK.

7.2 4 điều kiện Coffman — phải có ĐỦ 4 mới deadlock

Edward Coffman (1971) chứng minh deadlock xảy ra khi và chỉ khi đủ 4 điều kiện:

1. Mutual Exclusion (loại trừ lẫn nhau): Tài nguyên chỉ cấp được cho 1 process tại 1 thời điểm (vd mutex, file lock).
2. Hold & Wait: Process đang giữ ít nhất 1 resource và đang chờ resource khác (đang bị process khác giữ).
3. No Preemption: Resource không thể bị "cướp" — chỉ process đang giữ mới giải phóng được.
4. Circular Wait: Có vòng tròn chờ đợi: P1 → P2 → ... → Pn → P1.

7.3 Resource Allocation Graph (RAG)

Cách trực quan để phát hiện deadlock: vẽ graph với:

• Node P = process; R = resource
• Cạnh P → R: process P đang đợi resource R
• Cạnh R → P: resource R đang được P giữ

Có cycle trong graph = có khả năng deadlock (single instance) hoặc deadlock chắc chắn (1 instance / resource).

7.4 Prevention — phá 1 trong 4 điều kiện

Phá Mutual Exclusion

Không thể cho mutex/lock — vì bản chất chúng là exclusive. Có thể với một số resource (vd file đọc-only).

Phá Hold & Wait

Bắt process xin tất cả resource cùng lúc hoặc không xin gì.

// Thay vì
pthread_mutex_lock(&A);
pthread_mutex_lock(&B);

// Dùng try_lock_all hoặc xin từ đầu
if (try_lock_both(&A, &B)) {
    // ok, thành công
} else {
    // không có gì, thử lại sau
}

Nhược: utilization thấp (process giữ resource lâu mà không dùng), có thể starve.

Phá No Preemption

Cho phép "cướp" resource từ process. Khó với mutex/file. Khả thi với CPU, memory page.

Phá Circular Wait — phổ biến nhất, hiệu quả nhất

Áp đặt thứ tự tổng trên các resource. Process phải lock theo thứ tự tăng dần.

// Tất cả thread phải lock A trước B (theo thứ tự id)
// Thread 1
lock(A); lock(B); ... unlock(B); unlock(A);
// Thread 2 (đáng lẽ lock B rồi A → fix lại):
lock(A); lock(B); ... unlock(B); unlock(A);

// Đảm bảo: không có circular dependency vì mọi thread cùng order

Đây là Lock Ordering — kỹ thuật prevention phổ biến nhất trong production.

7.5 Avoidance — Banker's Algorithm

Trước khi cấp resource cho process, kiểm tra xem việc cấp có dẫn đến state có thể deadlock không. Nếu có nguy cơ → từ chối cấp ngay cả khi resource đang free.

Banker's Algorithm (Dijkstra)

Mỗi process khai báo trước nhu cầu tối đa mỗi loại resource. OS theo dõi:

• Allocation[i]: process i đang giữ bao nhiêu
• Max[i]: tối đa cần
• Need[i] = Max[i] - Allocation[i]: còn cần
• Available: resource còn dư

Khi có request, OS chạy Safety Check: thử cấp giả + xem có sequence hoàn thành mọi process được không. Nếu có → "safe state" → cấp. Nếu không → từ chối.

Trong thực tế ít dùng vì đòi hỏi biết trước max need (khó), và overhead chạy safety check mỗi lần. Mostly academic.

7.6 Detection & Recovery

Cho phép deadlock xảy ra, định kỳ chạy thuật toán phát hiện (vd RAG cycle), recovery khi phát hiện.

Detection

• Build RAG, tìm cycle (DFS) → có cycle = (có thể) deadlock
• Linux: lockdep tool trong kernel detect lock ordering bug
• Database: thread monitor đếm thời gian wait, detect cycle qua lock graph

Recovery

1. Process termination: kill 1 process trong cycle
2. Resource preemption: cướp resource từ 1 process, rollback nó

Database (MySQL/PostgreSQL): phát hiện deadlock → chọn 1 transaction "victim" (thường ưu tiên kill transaction trẻ hơn, ít cost rollback hơn) → rollback nó. App nhận error, retry.

7.7 Lock Ordering — best practice trong production code

Đây là kỹ thuật thực tế nhất để phòng deadlock. Quy tắc:

// Sai: thứ tự lock khác nhau
void transfer(Account *from, Account *to, int amount) {
    lock(&from->mutex);
    lock(&to->mutex);
    // ...
}
// transfer(A, B) lock A→B
// transfer(B, A) lock B→A
// → 2 thread chạy song song → DEADLOCK

// Đúng: lock theo address
void transfer(Account *from, Account *to, int amount) {
    Account *first  = (from < to) ? from : to;
    Account *second = (from < to) ? to : from;
    lock(&first->mutex);
    lock(&second->mutex);
    // ...
    unlock(&second->mutex);
    unlock(&first->mutex);
}

Timeout-based Detection

// pthread_mutex_timedlock — fail nếu không lock được trong T giây
struct timespec ts = {.tv_sec = 5};
if (pthread_mutex_timedlock(&mutex, &ts) != 0) {
    // có thể đang deadlock — log + retry với strategy khác
    handle_potential_deadlock();
}

Many DB drivers, distributed systems dùng timeout làm "phao cứu sinh".

7.8 Deadlock vs Livelock vs Starvation

Sự khác biệt: deadlock = không ai chạy; livelock = tất cả chạy nhưng vô ích; starvation = một số chạy, một số bị bỏ rơi.

7.9 Database Deadlock

DB như MySQL/PostgreSQL có lock cấp row/table. Hai transaction có thể deadlock:

-- Tx1
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
-- (chiếm row 1)
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
-- (đợi row 2)

-- Tx2 (chạy đồng thời)
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 2;
-- (chiếm row 2)
UPDATE accounts SET balance = balance + 50 WHERE id = 1;
-- (đợi row 1) → DEADLOCK

DB tự xử lý ra sao?

• DB engine định kỳ check deadlock (mỗi vài giây hoặc on-demand)
• Build wait-for graph, detect cycle
• Chọn "victim" transaction, rollback. App nhận error: "Deadlock detected"
• App nên retry transaction sau vài ms

// Pattern retry trong code
async function transferWithRetry(from, to, amount, retries = 3) {
  for (let i = 0; i < retries; i++) {
    try {
      return await db.transaction(async (tx) => {
        await tx.query('UPDATE accounts ... WHERE id = ?', [from]);
        await tx.query('UPDATE accounts ... WHERE id = ?', [to]);
      });
    } catch (e) {
      if (e.code === 'ER_LOCK_DEADLOCK' && i < retries - 1) {
        await new Promise(r => setTimeout(r, 50 * (i + 1)));
        continue;
      }
      throw e;
    }
  }
}

Phòng tránh DB deadlock

• Always lock rows in same order (vd ORDER BY id)
• Giữ transaction ngắn — ít chiếm lock lâu
• Dùng SELECT FOR UPDATE sớm để chiếm lock đầu
• Tránh transaction phức tạp với nhiều bảng

Bài tập

Tổng kết chương 7

• ✅ Deadlock = 2+ process đợi nhau vĩnh viễn, không ai tiến triển
• ✅ 4 điều kiện Coffman: Mutual Exclusion + Hold&Wait + No Preemption + Circular Wait. Phá 1 = an toàn.
• ✅ Resource Allocation Graph (RAG): cycle → deadlock
• ✅ Phòng tránh: Prevention (phá điều kiện), Avoidance (Banker's), Detection + Recovery
• ✅ Lock Ordering là kỹ thuật phổ biến nhất trong production
• ✅ Deadlock (stuck) ≠ Livelock (chạy vô ích) ≠ Starvation (bỏ rơi)
• ✅ DB deadlock: tự detect + kill victim transaction → app retry
• ✅ Best practice code: lock theo address, dùng try_lock với timeout