Synchronization
Mutex, Semaphore, Monitor

6.1 Race Condition — bug khó tìm nhất

Race condition = kết quả của chương trình phụ thuộc vào thứ tự thực thi của các thread — mà thứ tự đó không xác định được trước.

Ví dụ counter increment

int counter = 0;

void* increment(void* arg) {
    for (int i = 0; i < 1000000; i++) {
        counter++;  // có vẻ atomic, nhưng KHÔNG!
    }
    return NULL;
}

// Tạo 2 thread cùng gọi increment()
// Kỳ vọng: counter = 2,000,000
// Thực tế: counter ~= 1,200,000 (giá trị random!)

Tại sao? counter++ trong CPU thực ra là 3 instruction:

1. LOAD  counter → register   (đọc)
2. ADD   register, 1          (cộng 1)
3. STORE register → counter   (ghi)

Nếu thread A và B đan xen:

Cả 2 thread đều "tăng" counter, nhưng kết quả chỉ tăng 1 thay vì 2. Lost update.

6.2 Critical Section — đoạn cần bảo vệ

Critical Section (CS) = đoạn code truy cập tài nguyên chia sẻ, cần đảm bảo chỉ 1 thread vào tại 1 thời điểm.

3 yêu cầu của giải pháp đồng bộ

1. Mutual Exclusion (loại trừ lẫn nhau): chỉ 1 thread trong CS
2. Progress: nếu không có thread nào trong CS, thread muốn vào không phải đợi vô lý
3. Bounded Waiting: thread đợi không đợi vô hạn (no starvation)

6.3 Mutex — cơ chế phổ biến nhất

Mutex (mutual exclusion) = lock cho phép chính xác 1 thread vào CS. 2 operation chính:

• lock(): nếu mutex đang free → chiếm; nếu đang busy → block đến khi free
• unlock(): trả mutex; OS đánh thức 1 thread đang đợi

Sửa counter bằng mutex

#include <pthread.h>

int counter = 0;
pthread_mutex_t lock;

void* increment(void* arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&lock);
        counter++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main() {
    pthread_mutex_init(&lock, NULL);
    pthread_t t1, t2;
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("counter = %d\n", counter);  // chính xác 2,000,000
}

Đặc điểm Mutex

• Ownership: mutex có "owner" — thread lock phải là thread unlock (recursive mutex thì có thể lock nhiều lần cùng thread)
• Block: thread đợi mutex bị OS đưa vào trạng thái BLOCKED, không tiêu CPU
• Wakeup: khi unlock, OS đánh thức 1 thread đang đợi (FIFO hoặc tuỳ implementation)

6.4 Semaphore — đếm cờ hiệu

Semaphore = biến nguyên N + 2 atomic operation:

• P() hoặc wait(): nếu N > 0 thì N--; nếu N = 0 thì block
• V() hoặc signal(): N++; nếu có thread đang đợi thì wakeup 1

Counting Semaphore

N có thể > 1 — cho phép N thread vào CS đồng thời. Vd: pool có 5 connection, muốn cấp tối đa 5 thread truy cập DB cùng lúc.

sem_t db_pool;
sem_init(&db_pool, 0, 5);  // 5 slots

void* worker(void* arg) {
    sem_wait(&db_pool);    // chiếm 1 slot
    // ... truy cập DB ...
    sem_post(&db_pool);    // trả slot
}

Binary Semaphore

N = 0 hoặc 1. Tương đương Mutex về mặt chức năng nhưng không có ownership.

Mutex vs Semaphore — phân biệt

Quy tắc: "Mutex là cái bạn cầm để vào phòng. Semaphore là số chỗ trống trong bãi đỗ xe."

6.5 Monitor — abstraction cấp cao hơn

Monitor đóng gói data + procedure + lock vào 1 đơn vị. Chỉ 1 thread chạy procedure tại 1 thời điểm. Java dùng monitor qua synchronized keyword.

// Java — synchronized = monitor
class Counter {
    private int count = 0;

    public synchronized void increment() {  // 1 thread tại 1 lúc
        count++;
    }

    public synchronized int get() {
        return count;
    }
}

Monitor có condition variable để thread đợi điều kiện:

class BoundedBuffer {
    private final Queue<Integer> q = new LinkedList<>();
    private final int capacity = 10;

    public synchronized void put(int x) throws InterruptedException {
        while (q.size() == capacity) wait();  // đợi có chỗ
        q.add(x);
        notifyAll();  // báo cho consumer
    }

    public synchronized int take() throws InterruptedException {
        while (q.isEmpty()) wait();
        int x = q.poll();
        notifyAll();
        return x;
    }
}

JS không có monitor built-in, nhưng async/await + Promise tương tự về tinh thần.

6.6 Spinlock — busy waiting

Spinlock: thay vì block (đợi OS đánh thức), thread vào loop liên tục check lock có free chưa. "Spin" = quay tròn.

// Pseudo-code spinlock đơn giản
typedef volatile int spinlock_t;

void lock(spinlock_t *l) {
    while (__sync_lock_test_and_set(l, 1)) {
        // busy wait
    }
}

void unlock(spinlock_t *l) {
    __sync_lock_release(l);
}

Khi nào dùng spinlock?

• Đoạn CS rất ngắn (vài instruction): cost của block + wakeup > cost của spin vài chục ns
• Trong kernel: nơi không thể block (vd interrupt handler)
• Multi-core: chỉ có ý nghĩa khi nhiều CPU — single-core spinlock = lãng phí

Đừng dùng spinlock trong user code thường — block (mutex) tốt hơn 99% trường hợp.

6.7 Read/Write Lock — nhiều reader, một writer

Khi data thường được đọc (vd cache), nhiều reader đọc đồng thời không vấn đề. Chỉ writer mới phải exclusive.

pthread_rwlock_t lock;
pthread_rwlock_init(&lock, NULL);

// Reader: nhiều reader có thể đồng thời
void* reader(void* arg) {
    pthread_rwlock_rdlock(&lock);
    // ... đọc data ...
    pthread_rwlock_unlock(&lock);
}

// Writer: exclusive
void* writer(void* arg) {
    pthread_rwlock_wrlock(&lock);
    // ... ghi data ...
    pthread_rwlock_unlock(&lock);
}

Tốt cho: cache, in-memory database, config object đọc nhiều ghi ít.

6.8 Bài kinh điển 1: Producer-Consumer (Bounded Buffer)

Bài toán: 1 producer sinh data đẩy vào buffer kích thước N. 1 consumer lấy data từ buffer ra xử lý.

• Buffer đầy → producer phải đợi
• Buffer rỗng → consumer phải đợi
• Đảm bảo mutual exclusion khi truy cập buffer

#define N 10
int buffer[N];
int in = 0, out = 0;

sem_t empty;   // số slot trống — init = N
sem_t full;    // số slot đầy — init = 0
pthread_mutex_t mutex;

void* producer(void* arg) {
    while (1) {
        int item = produce();
        sem_wait(&empty);          // đợi có slot trống
        pthread_mutex_lock(&mutex);
        buffer[in] = item;
        in = (in + 1) % N;
        pthread_mutex_unlock(&mutex);
        sem_post(&full);           // báo có slot đầy
    }
}

void* consumer(void* arg) {
    while (1) {
        sem_wait(&full);           // đợi có data
        pthread_mutex_lock(&mutex);
        int item = buffer[out];
        out = (out + 1) % N;
        pthread_mutex_unlock(&mutex);
        sem_post(&empty);          // báo có slot trống
        consume(item);
    }
}

Ý tưởng: 2 semaphore empty/full đảm bảo waiting condition; mutex bảo vệ thao tác trên buffer.

Đây là pattern phổ biến: thread pool, message queue, stream processing — đều có producer-consumer.

6.9 Bài kinh điển 2: Reader-Writer Problem

Nhiều reader đọc shared data. Writer thỉnh thoảng update. Yêu cầu:

• Nhiều reader có thể đọc đồng thời
• Khi writer ghi, không ai khác (reader/writer) được vào

Có 2 biến thể: reader-preferred (writer có thể starve), writer-preferred (reader có thể starve). RWLock thường implement writer-preferred để fair.

// Reader-preferred (đơn giản, có thể starve writer)
int readers = 0;
pthread_mutex_t mutex;     // bảo vệ readers
pthread_mutex_t writelock; // exclusive cho writer

void* reader(void* arg) {
    pthread_mutex_lock(&mutex);
    readers++;
    if (readers == 1) pthread_mutex_lock(&writelock);  // chặn writer
    pthread_mutex_unlock(&mutex);

    // đọc data ...

    pthread_mutex_lock(&mutex);
    readers--;
    if (readers == 0) pthread_mutex_unlock(&writelock);
    pthread_mutex_unlock(&mutex);
}

void* writer(void* arg) {
    pthread_mutex_lock(&writelock);
    // ghi data ...
    pthread_mutex_unlock(&writelock);
}

6.10 Bài kinh điển 3: Dining Philosophers

5 triết gia ngồi quanh bàn tròn. Giữa mỗi 2 triết gia có 1 đôi đũa (5 đũa total). Triết gia chỉ ăn khi cầm cả 2 đũa bên trái và bên phải.

Naïve solution dễ dẫn đến deadlock:

void philosopher(int i) {
    while (1) {
        think();
        pick_up(left[i]);   // BUG: nếu cả 5 cùng pick left → deadlock!
        pick_up(right[i]);
        eat();
        put_down(right[i]);
        put_down(left[i]);
    }
}

Giải pháp 1: chỉ cho phép tối đa 4 trong bàn (semaphore)

sem_t seats; sem_init(&seats, 0, 4);  // 4 ghế trên 5 chỗ

void philosopher(int i) {
    while (1) {
        think();
        sem_wait(&seats);      // đợi có ghế
        pick_up(left[i]);
        pick_up(right[i]);
        eat();
        put_down(right[i]);
        put_down(left[i]);
        sem_post(&seats);
    }
}

Giải pháp 2: lock ordering

Triết gia chẵn pick left trước, lẻ pick right trước → không thể tất cả "cầm left chờ right".

Giải pháp 3: chỉ pick khi cả 2 đũa đều free (atomic check)

Cần 1 mutex global hoặc transaction. Phổ biến trong DB (commit only if both rows lockable).

Bài toán này demo: locking 2+ resource dễ gây deadlock; cần kỹ thuật phòng tránh (chương 7).

6.11 Atomic Operations — không cần lock

CPU hiện đại có instruction atomic: Test-And-Set (TAS), Compare-And-Swap (CAS), Fetch-And-Add. Đây là cơ sở của mutex/semaphore.

Compare-And-Swap (CAS)

// Pseudo: atomic, kernel guarantees no other thread interrupts
bool CAS(int *addr, int expected, int new_val) {
    if (*addr == expected) {
        *addr = new_val;
        return true;
    }
    return false;
}

CAS là vũ khí của lock-free programming. Vd: lock-free counter:

void atomic_inc(int *counter) {
    int old, new_val;
    do {
        old = *counter;
        new_val = old + 1;
    } while (!CAS(counter, old, new_val));
}

C11 / C++11 Atomic

#include <stdatomic.h>
atomic_int counter = 0;
atomic_fetch_add(&counter, 1);     // counter++ atomic
atomic_compare_exchange(&counter, &expected, new_val);

JS Atomics (cho SharedArrayBuffer)

const sab = new SharedArrayBuffer(4);
const view = new Int32Array(sab);
Atomics.add(view, 0, 1);          // atomic counter++
Atomics.compareExchange(view, 0, expected, newVal);

Bài tập

Tổng kết chương 6

• ✅ Race condition: 2+ thread cùng đọc/ghi shared data → kết quả phụ thuộc thứ tự
• ✅ Critical Section cần Mutual Exclusion + Progress + Bounded Waiting
• ✅ Mutex: lock có ownership; Semaphore: counter; Monitor: high-level (Java synchronized)
• ✅ Spinlock: busy wait, dùng cho CS ngắn trên multi-core
• ✅ Read/Write lock: nhiều reader hoặc 1 writer
• ✅ Producer-Consumer: 2 semaphore + mutex; pattern phổ biến nhất
• ✅ Reader-Writer: cho cache, config
• ✅ Dining Philosophers: bài học về deadlock với multi-resource lock
• ✅ Atomic operation (CAS): cơ sở của lock-free programming