Hết deadlock chưa phải hết lỗi: livelock đốt sạch CPU và writer chờ 30ms sau dòng reader

Hai người đi ngược chiều trong một hành lang hẹp, mặt đối mặt. Có ba cách hỏng. Cả hai cùng đứng im chờ người kia nhường trước — không ai nhúc nhích, hành lang tắc trong im lặng: đó là deadlock. Cả hai cùng lịch sự bước sang trái để nhường, va nhau; cùng bước sang phải, lại va; cứ nhảy qua nhảy lại đồng nhịp mãi mãi — trông thì bận rộn tíu tít mà chẳng ai qua được: đó là livelock. Còn cách thứ ba khó thấy hơn: một dòng người đông cứ ào ào đi qua, và một cụ già chống gậy đứng bên chờ một khe trống để chen vào — dòng người vẫn tiến, nhưng cụ thì gần như không bao giờ tới lượt: đó là starvation (bỏ đói). Hết deadlock không có nghĩa là hết hỏng.

Ở 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ì. (Hai người đứng im.)
• 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. 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. (Hai người nhảy tránh nhau mãi.)
• 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. (Cụ già không chen được vào dòng người.)

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 — đúng hai người trong hành lang. 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 (một người khựng lại nửa nhịp là hết va). Đâ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 — đúng cụ già trước dòng người. Đ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ôi trường đo: container gcc:13 trên host ARM AArch64, 10 lõi, số lấy sau warmup. Con số tuyệt đối và mức công bằng đổi theo cài đặt libc/scheduler; điều bền vững: backoff đồng nhịp phí nhiều lần so ngẫu nhiên, và dòng reader liên tục bỏ đói writer trong rwlock không ưu tiên writer.)

Hai niềm tin đối nghịch, cùng sai

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.

Hai niềm tin gặp nhau ở một bài học: "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ề đến code hằng ngày

Điều đầ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. Bài viết kinh điển của AWS "Exponential Backoff and Jitter" chỉ ra đúng điều này: exponential backoff không kèm jitter vẫn để các client đồng nhịp và va nhau; thêm jitter mới thực sự giãn tải — nên mọi thư viện retry nghiêm túc (AWS SDK, gRPC, Kafka client) đều có jitter mặc định.

Điều 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 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 và đo phân phối giữa các luồng, không chỉ tổng.

Chỗ này cái nút "công bằng hay không" được các thư viện phơi ra thành lựa chọn tường minh, và biết chúng cứu bạn khỏi đúng bug starvation vừa đo. Java cho ReentrantLock(true) và ReentrantReadWriteLock(true) ở chế độ fair — cấp khóa theo thứ tự FIFO thay vì để ai nhanh tay cướp; và tài liệu ReentrantReadWriteLock cảnh báo thẳng rằng chế độ non-fair (mặc định) có thể bỏ đói writer đúng như tôi đo. Go giải bài này ngay trong thiết kế sync.RWMutex: tài liệu ghi rõ một lời gọi Lock() đang chờ sẽ chặn các reader mới giành khóa đọc — tức Go ưu tiên writer để chống chính cái starvation này, khác hành vi reader-ào-ạt tôi tái hiện bằng rwlock C. Ở tầng database, cùng câu chuyện: hàng đợi khóa/giao dịch cần công bằng để một transaction ưu tiên thấp không kẹt mãi sau dòng transaction khác, và retry sau deadlock cũng phải kèm jitter kẻo cả đàn client cùng thử lại một nhịp. Mẫu số chung: "hệ vẫn chạy" che giấu một luồng đang chết đói, và công cụ để chữa là một cờ fairness hoặc một chút ngẫu nhiên — thứ bạn phải chủ động bật, không tự có.

Muốn tự soi thì 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? — 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". Vài phút đó 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.