Đồng bộ hóa tiến trình (Process Synchronization) trong C/C++

Đồng bộ hóa tiến trình là kỹ thuật giải quyết vấn đề truy cập đồng thời dữ liệu chia sẻ, gây ra không nhất quán dữ liệu. Tiến trình hợp tác (cooperating process) là tiến trình có thể ảnh hưởng hoặc bị ảnh hưởng bởi tiến trình khác → cần đồng bộ để đảm bảo tính nhất quán.

Vấn đề Critical Section (Khu vực quan trọng)

Mỗi tiến trình có đoạn mã dành riêng gọi là Critical Section. Tại đây, tiến trình thay đổi biến chung, cập nhật bảng, ghi file... Điểm quan trọng: khi một tiến trình đang thực thi trong critical section, không tiến trình nào khác được vào critical section của mình.

Mỗi tiến trình phải xin phép trước khi vào (Entry Section), kết thúc là Exit Section, phần còn lại là Remainder Section.

Ba yêu cầu cho Critical Section:

• Mutual Exclusion (Loại trừ lẫn nhau): Chỉ một tiến trình trong critical section tại một thời điểm.
• Progress (Tiến triển): Nếu không tiến trình nào trong critical section và có tiến trình muốn vào, chỉ những tiến trình không ở remainder section mới được xin vào, và việc chọn không bị trì hoãn vô hạn.
• Bounded Waiting (Chờ có giới hạn): Giới hạn số lần tiến trình khác được vào critical section sau khi một tiến trình xin vào và trước khi yêu cầu đó được chấp nhận.

Hai cách tiếp cận OS xử lý critical section:

• Preemptive Kernel: Cho phép ngắt tiến trình đang chạy ở kernel mode.
• Non-Preemptive Kernel: Không cho ngắt tiến trình ở kernel mode.

Giải pháp Peterson (Peterson's Solution)

Giải pháp phần mềm kinh điển cho critical section, giới hạn 2 tiến trình luân phiên thực thi critical section và remainder section. Cần 2 dữ liệu chia sẻ:

• int turn;
• bool flag[2];

turn == i → tiến trình Pi được vào critical section.
flag[j] == true → tiến trình j sẵn sàng vào critical section.

Peterson đảm bảo cả 3 điều kiện: Mutual Exclusion, Progress, Bounded Waiting.

Đồng bộ phần cứng (Synchronization Hardware)

Dùng 2 lệnh:

• TestAndSet()
• swap()

TestAndSet(): biến chia sẻ lock (0 hoặc 1). 1 = đã khóa, 0 = mở khóa. Tiến trình vào critical section kiểm tra lock, nếu 1 thì chờ đến khi thành 0.

Semaphore (Đồng hồ báo)

Công cụ đồng bộ vượt qua nhược điểm của TestAndSet/Swap. Semaphore S là biến nguyên tử truy cập qua 2 thao tác wait() và signal().

wait(S) {
    while S <= 0; // busy wait
    S--;
}

signal(S) {
    S++;
}

Khi một tiến trình sửa semaphore, tiến trình khác không thể sửa cùng lúc.

Hai loại Semaphore:

• Counting Semaphore: giá trị không giới hạn.
• Binary Semaphore: giá trị 0 hoặc 1. Còn gọi là Mutex Locks. OS dùng để giải quyết critical section đa tiến trình.