Ở deadlock ta thấy lỗi tiến-độ tệ nhất: chương trình treo cứng. Và ta có một liều thuốc — trylock + backoff, không ôm khóa mà chờ. Nhưng đây là chỗ dễ tự mãn: "hết deadlock rồi, không treo nữa, vậy là an toàn". Sai. Có ít nhất hai lỗi tiến-độ khác không treo mà vẫn hỏng: livelock (chạy hết CPU mà không tiến) và starvation (hệ tiến nhưng một luồng bị bỏ đói). Tôi đo cả hai — một cái tái hiện mạnh, một cái không tái hiện như tưởng, và cả hai kết quả đều dạy điều gì đó.
Ba lỗi tiến độ, ba dấu hiệu
Phân biệt rõ ba anh em này quan trọng vì chúng biểu hiện khác nhau, nên chẩn đoán khác nhau:
- Deadlock: các luồng bị chặn, mỗi luồng chờ tài nguyên luồng kia giữ (chờ vòng tròn). Dấu hiệu: chương trình treo, và CPU gần 0% — mọi luồng ngủ trong nhân, không ai làm gì.
- Livelock: các luồng không bị chặn, chúng vẫn chạy — nhưng cứ phản ứng lẫn nhau nên không tiến. Hình ảnh kinh điển: hai người trong hành lang hẹp, cả hai cùng bước sang trái để nhường, va nhau; cùng bước sang phải, lại va; mãi mãi. Dấu hiệu: CPU 100% nhưng công việc không nhích — tệ hơn deadlock ở chỗ nó trông như đang bận rộn làm việc.
- Starvation (bỏ đói): hệ thống vẫn tiến — nhưng một luồng cụ thể gần như không bao giờ tới lượt. Dấu hiệu: thông lượng tổng ổn, nhưng một luồng có độ trễ khổng lồ hoặc không xong.
Tôi đo cả livelock và starvation trong container gcc:13 (10 lõi).
Đo (a): livelock — chạy hết CPU mà phí 5 lần
Tôi dựng livelock kiểu "nhường nhau lịch sự": hai luồng, mỗi luồng đặt ý định muốn vào vùng tới hạn; nếu thấy luồng kia cũng muốn, nó rút ý định, lùi (backoff), rồi thử lại. Nếu cả hai lùi đồng nhịp, chúng cứ thấy nhau muốn và cứ nhường mãi. Tôi so backoff cố định (đồng nhịp) với backoff ngẫu nhiên, đo số lần vào vùng tới hạn trong 500 ms:
backoff ĐỒNG NHỊP (cố định) : 9,2 triệu lần vào
backoff NGẪU NHIÊN : 47,3 triệu lần vào
ngẫu nhiên / đồng nhịp : 5,1×
Backoff đồng nhịp chỉ đạt 9,2 triệu so với 47,3 triệu của ngẫu nhiên — phí 5,1 lần. Điểm mấu chốt: trong suốt 500 ms đó, cả hai luồng chạy hết CPU — không luồng nào ngủ, không có treo. Nhưng 80% công của chúng bị đốt vào việc nhường nhau và va lại, không phải việc thật. Cách chữa — ngẫu nhiên hóa backoff — phá vỡ sự đồng nhịp: khi mỗi luồng lùi một khoảng khác nhau, một luồng sẽ tình cờ thử lại trước luồng kia và lọt qua. Đây chính là lý do các giao thức mạng (Ethernet, TCP) dùng exponential backoff ngẫu nhiên.
Một điều tôi phải báo trung thực: tôi không ép được livelock hoàn toàn (0 tiến độ) trên scheduler thật này. Vì hệ điều hành liên tục chuyển ngữ cảnh với chút jitter, hai luồng không bao giờ giữ được đồng nhịp tuyệt đối — nên chúng vẫn nhích được (9,2 triệu, không phải 0). Livelock hoàn hảo cần sự đồng bộ chặt hơn thực tế cho phép. Nhưng cơ chế thì rõ ràng và đo được: đồng nhịp phí 5 lần, và trong một hệ ghép chặt hơn (hoặc scheduler kém may mắn hơn) nó có thể về gần 0. Đúng tinh thần đo lường: báo cái đo được (phí 5×), và trung thực về cái không ép được (0 tuyệt đối).
Đo (b) và (c): starvation — mutex công bằng, rwlock thì không
Với starvation, tôi định chỉ ra một luồng bị bỏ đói khi nhiều luồng tranh một khóa. Đo trước với mutex thường: 8 luồng cùng giành một mutex trong 500 ms, đếm số lần mỗi luồng lấy được khóa:
8 luồng, một mutex:
luồng 0..7: 3,04tr, 3,08tr, 3,04tr, 3,05tr, 3,06tr, 3,10tr, 3,11tr, 3,17tr
max / min = 1,0× -> CÔNG BẰNG, không ai bị bỏ đói
Bất ngờ: không có starvation. Cả 8 luồng lấy khóa xấp xỉ đều nhau (max/min chỉ 1,0×). Mutex của glibc trên máy này công bằng dưới workload này — nó không để một luồng liên tục cướp khóa. Đây là một kết quả âm thành thật: điều tôi tưởng sẽ thấy (bỏ đói) không xảy ra, vì cài đặt cụ thể đủ công bằng.
Nhưng starvation có thật — tôi tìm đúng chỗ nó xuất hiện: rwlock với dòng reader liên tục bỏ đói writer. Read-write lock cho nhiều reader song song; nếu reader đến liên tục, luôn có ít nhất một reader giữ khóa đọc, và một writer (cần độc quyền) không bao giờ chen vào được. Đo 6 reader liên tục + 1 writer trong 500 ms:
tổng đọc : 2.555.790
tổng ghi : 70..91 (ba lần chạy)
tỉ lệ đọc/ghi : ~30.000×
writer chờ lâu nhất : ~30 ms cho MỘT lần ghi
Writer bị bỏ đói nặng: trong khi reader lấy khóa 2,5 triệu lần, writer chỉ lọt vào ~80 lần — tỉ lệ 30.000 lần, và có lần writer phải chờ 30 mili giây chỉ để ghi một lần. Hệ thống vẫn tiến (2,5 triệu lượt đọc), nhưng writer gần như đứng im. Đây là starvation thật: không treo, thông lượng cao, mà một luồng bị đói. Cách chữa: dùng rwlock ưu tiên writer (chặn reader mới khi có writer đang chờ), hoặc một khóa công bằng/FIFO.
Một lần tôi đo hớ: "không treo" không bằng "mọi luồng đều tiến"
Tôi vào đo với hai niềm tin. Thứ nhất: "hết deadlock (không treo) là an toàn". Sai — livelock chạy hết CPU mà lãng phí 5 lần không hề treo, và starvation rwlock để writer chờ 30 ms không hề treo. Thứ hai, tinh vi hơn: "trylock tránh được deadlock nên nó là giải pháp an toàn". Đo hớ ở đây: trylock + backoff đúng là phá deadlock (như phần trước), nhưng nếu backoff đồng nhịp, chính nó tạo ra livelock — đổi một lỗi tiến-độ này lấy một lỗi khác. trylock không phải viên đạn bạc.
Bài học đo lường: "không treo" chỉ là một phần của "đúng" — tiến độ còn đòi hỏi mọi luồng đều nhích, và đủ nhanh. Ba lỗi tiến-độ có ba dấu hiệu khác nhau (deadlock: treo + CPU im; livelock: kẹt + CPU bận; starvation: hệ chạy + một luồng đói), nên khi một hệ đồng thời "có vẻ chạy mà chậm bất thường", phải nhìn đúng dấu hiệu để chẩn đoán đúng bệnh. Và như hai kết quả trái ngược của tôi cho thấy — livelock khó ép hoàn toàn, mutex glibc lại công bằng bất ngờ — tính đúng và công bằng phụ thuộc cài đặt cụ thể, nên phải đo trên chính hệ của bạn, đừng suy từ lý thuyết hay từ một máy khác.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: ngẫu nhiên hóa mọi retry/backoff. Bất cứ khi nào nhiều tác nhân cùng thử-lại một thao tác có thể xung đột (lấy khóa, kết nối lại, gửi lại gói tin), đừng để chúng lùi cùng một khoảng — thêm jitter ngẫu nhiên. Đây là cách phá đồng nhịp, tránh livelock, và là lý do exponential backoff luôn kèm ngẫu nhiên trong mọi giao thức nghiêm túc.
Hệ quả thứ hai: chú ý công bằng, đừng chỉ chú ý thông lượng. Một hệ có thông lượng tổng cao vẫn có thể để một luồng (một request, một loại tác vụ) chết đói — như writer sau dòng reader. Nếu độ trễ đuôi (p99, worst-case) quan trọng, hãy chọn khóa/hàng đợi công bằng (FIFO) hoặc ưu tiên đúng, và đo phân phối giữa các luồng, không chỉ tổng.
Hệ quả thứ ba là tinh thần đo lường: "chạy được" chưa đủ — kiểm mọi luồng đều tiến. Con số mang theo: ngoài deadlock (treo, CPU im) còn hai lỗi tiến-độ KHÔNG treo: livelock (chạy hết CPU mà không tiến — backoff đồng nhịp phí 5,1× so ngẫu nhiên, 9,2 vs 47,3 triệu; ngẫu nhiên hóa để chữa) và starvation (hệ tiến nhưng một luồng đói — rwlock để 6 reader bỏ đói writer, đọc/ghi ~30.000×, writer chờ tới 30ms; dùng khóa công bằng để chữa). 'Không treo' KHÔNG bằng 'mọi luồng đều tiến'. Trung thực: livelock hoàn toàn khó ép trên scheduler thật, và mutex glibc ở đây lại công bằng — công bằng tùy cài đặt.
Thử ba mươi giây
Nhìn một chỗ trong code của bạn có retry khi gặp xung đột — thử lại một giao dịch, kết nối lại một socket, giành lại một khóa. Hỏi: khi nhiều luồng/tiến trình cùng thử lại, chúng lùi bao lâu trước khi thử lại? Nếu tất cả lùi cùng một khoảng cố định, chúng có thể đồng nhịp và va nhau mãi (livelock) — thêm một chút ngẫu nhiên vào khoảng chờ là xong. Rồi nhìn một khóa/hàng đợi nhiều luồng dùng chung và hỏi: có luồng nào có thể bị bỏ qua mãi không? — ví dụ một tác vụ ưu tiên thấp sau dòng tác vụ ưu tiên cao, hay một writer sau dòng reader. Nếu có, đó là starvation tiềm ẩn, và độ trễ đuôi của luồng đó sẽ tệ dù hệ "vẫn chạy". Ba mươi giây đó nhắc bạn rằng "không treo" chỉ là mức tối thiểu — một hệ đồng thời đúng phải để mọi luồng tiến, công bằng, không ai bị bỏ lại.
