Bế tắc (Deadlock)

1. Tổng quan

Bế tắc (Deadlock) là trạng thái trong đó hai hoặc nhiều tiến trình (hoặc luồng, giao dịch) chờ đợi vô hạn tài nguyên mà bên kia đang chiếm giữ, không bên nào có thể tiến triển và bị dừng vĩnh viễn.

Khi đa chương trình và xử lý song song trở nên phổ biến, việc nhiều luồng thực thi cùng chia sẻ các tài nguyên hữu hạn như CPU, bộ nhớ, thiết bị vào/ra, bản ghi cơ sở dữ liệu đã trở thành chuyện thường ngày. Để chia sẻ tài nguyên hiệu quả, cần có loại trừ tương hỗ (mutual exclusion) — cho một luồng giữ tài nguyên trước và buộc các luồng khác tạm chờ — và chính sự "chờ đợi" này khi đan xen vào nhau sẽ tạo ra vòng chờ khiến không ai có thể tiến lên. Bế tắc không đơn thuần là suy giảm hiệu năng mà dẫn thẳng đến sự cố tính sẵn sàng làm dừng một phần hoặc toàn bộ hệ thống, nên đây là chủ đề cốt lõi bắt buộc phải xử lý khi thiết kế hệ điều hành, cơ sở dữ liệu và hệ thống phân tán.

Bế tắc đặc biệt khó xử lý vì nó phát sinh một cách không tất định (non-deterministic). Cùng một đoạn mã, tùy thứ tự lập lịch, thời điểm và tải, có lúc chạy qua bình thường, có lúc lại treo cứng. Đây là "Heisenbug" điển hình: không tái hiện được trong môi trường kiểm thử nhưng thỉnh thoảng bùng phát khi mức đồng thời cao trong môi trường vận hành, vì vậy không chỉ phát hiện và khôi phục sau sự việc mà phòng ngừa ở giai đoạn thiết kế cũng rất quan trọng. Từ góc nhìn Kỹ sư chuyên nghiệp Quản lý Thông tin, cần hiểu chính xác điều kiện phát sinh và giải thích được sự đánh đổi giữa bốn chiến lược xử lý — phòng ngừa, tránh, phát hiện, khôi phục — trong bối cảnh thực tiễn.

Cần phân biệt bế tắc với đói tài nguyên (Starvation). Bế tắc là tất cả các luồng liên quan chờ nhau và dừng vĩnh viễn, còn đói tài nguyên là tình trạng chỉ một luồng cụ thể liên tục bị đẩy lùi và không nhận được tài nguyên, trong khi các luồng còn lại vẫn tiến triển bình thường. Livelock cũng là đối tượng cần phân biệt. Livelock là trạng thái các luồng không dừng lại nhưng chỉ liên tục nhường nhau mà không có tiến triển thực chất. Cả ba hiện tượng đều có triệu chứng tương tự là "công việc không kết thúc", nhưng nguyên nhân và cách giải quyết khác nhau nên cần phân biệt chính xác ở giai đoạn chẩn đoán.

Mức độ ảnh hưởng của bế tắc càng lớn khi quy mô hệ thống càng lớn. Thực tế, bế tắc phát sinh dồn dập vào thời điểm tập trung các giao dịch khóa đồng thời nhiều tài nguyên như trừ tồn kho trong thương mại điện tử, chuyển khoản trong tài chính, giữ chỗ trong hệ thống đặt vé. Khi đó nhiều giao dịch bị rollback và thử lại dây chuyền, độ trễ phản hồi tăng vọt, và trường hợp xấu nhất lan thành sự cố khiến toàn bộ dịch vụ gần như ngừng hoạt động. Vì vậy bế tắc phải được xem là mối quan tâm ở cấp kiến trúc gắn trực tiếp với tính sẵn sàng của hệ thống, chứ không phải lỗi của một tiến trình đơn lẻ.

2. Bốn điều kiện cần để phát sinh bế tắc

Bế tắc chỉ phát sinh khi bốn điều kiện sau đồng thời cùng thỏa mãn (điều kiện Coffman, 1971). Nghĩa là chỉ cần phá vỡ một trong số đó thì bế tắc về nguyên tắc không thể xảy ra, và đây là cơ sở lý thuyết của chiến lược phòng ngừa (Prevention).

graph TD
    A["Phát sinh bế tắc"] --- B["Loại trừ tương hỗ (Mutual Exclusion)"]
    A --- C["Giữ và chờ (Hold and Wait)"]
    A --- D["Không trưng dụng (No Preemption)"]
    A --- E["Chờ vòng tròn (Circular Wait)"]
    B --> F["Chỉ phát sinh khi 4 điều kiện đồng thời thỏa mãn"]
    C --> F
    D --> F
    E --> F

A. Loại trừ tương hỗ (Mutual Exclusion). Tài nguyên tại một thời điểm chỉ được một luồng sử dụng độc quyền. Các tài nguyên không thể chia sẻ đồng thời như máy in, bản ghi DB đang bị khóa ghi thuộc loại này. Tài nguyên có thể chia sẻ ở chế độ chỉ đọc (khóa chia sẻ) không thỏa điều kiện này nên không gây bế tắc. Nói cách khác, loại trừ tương hỗ là thuộc tính bản chất của tài nguyên nên là điều kiện khó loại bỏ nhân tạo nhất.

B. Giữ và chờ (Hold and Wait). Là tình huống một luồng đang chiếm giữ một tài nguyên nào đó, đồng thời yêu cầu thêm và chờ một tài nguyên khác mà luồng khác đang giữ. Chẳng hạn tiến trình P1 giữ tài nguyên A và yêu cầu B, còn P2 giữ B và yêu cầu A thì hai bên sẽ níu nhau. Có thể phá điều kiện này bằng cách buộc giành toàn bộ tài nguyên cần thiết ngay từ đầu.

C. Không trưng dụng (No Preemption). Tài nguyên mà một luồng đang chiếm giữ không thể bị tước đoạt cưỡng bức cho đến khi luồng đó tự nguyện trả lại. Nếu luồng có ưu tiên cao có thể thu hồi cưỡng bức tài nguyên của luồng ưu tiên thấp (trưng dụng), thì dù vòng chờ có hình thành vẫn có thể gỡ bế tắc bằng thu hồi tài nguyên. Tuy nhiên, những tài nguyên dễ lưu và khôi phục trạng thái như CPU, bộ nhớ thì dễ trưng dụng, còn những tài nguyên mà trưng dụng sẽ phá vỡ tính nhất quán như máy in đang in dở hay giữa chừng một giao dịch DB thì khó trưng dụng.

D. Chờ vòng tròn (Circular Wait). Là điều kiện khi vẽ quan hệ chờ thành đồ thị thì hình thành một vòng (chu trình). Một vòng lặp khép kín dạng P1→P2→P3→…→P1 được tạo ra, trong đó mỗi luồng chờ tài nguyên mà luồng kế tiếp đang giữ. Dù ba điều kiện trên thỏa mãn, chỉ cần không có vòng này thì bế tắc không xảy ra, nên trong thực tế phương pháp được dùng nhiều nhất là "buộc mọi luồng chỉ giành tài nguyên theo cùng một thứ tự" để chặn vòng từ gốc.

Điểm quan trọng là bốn điều kiện này đều là điều kiện cần, và chỉ khi có đủ cả bốn thì mới trở thành điều kiện đủ. Chỉ cần một điều kiện không thỏa thì bế tắc tuyệt đối không phát sinh. Đó chính là lý do chiến lược phòng ngừa tập trung vào "phá một trong bốn". Ví dụ, dữ liệu thuần chỉ đọc không có loại trừ tương hỗ, tác vụ batch giành toàn bộ tài nguyên cần thiết ngay từ đầu, tài nguyên có thể trưng dụng bất kỳ lúc nào như CPU, và mã chỉ lấy khóa theo số thứ tự toàn cục — mỗi trường hợp phá vỡ một điều kiện nên về cấu trúc không bị bế tắc.

Có thể hiểu bốn điều kiện này theo cấu trúc phân tầng: ba điều kiện đầu (loại trừ tương hỗ, giữ và chờ, không trưng dụng) tạo ra môi trường có khả năng bế tắc, còn điều kiện cuối cùng — chờ vòng tròn — là cò súng thực sự kích hoạt bế tắc. Một ví dụ thực tế: trong logic chuyển khoản ngân hàng, nếu luồng chuyển từ tài khoản A→B và luồng chuyển B→A mỗi bên lấy khóa tài khoản đối phương trước, sẽ tạo ra vòng chờ điển hình. Trong thực tiễn, điều này được ngăn bằng sắp thứ tự tài nguyên — khóa tài khoản có số nhỏ hơn trước.

3. Đồ thị cấp phát tài nguyên (Resource Allocation Graph)

Công cụ tiêu biểu để nhận diện bế tắc một cách trực quan là đồ thị cấp phát tài nguyên (RAG). Đặt tiến trình (hình tròn) và tài nguyên (hình chữ nhật) làm đỉnh; khi tiến trình yêu cầu tài nguyên thì vẽ cạnh có hướng tiến trình→tài nguyên (cạnh yêu cầu), khi tài nguyên được cấp cho tiến trình thì vẽ tài nguyên→tiến trình (cạnh cấp phát). Hình dưới đây thể hiện tình huống bế tắc trong đó P1 giữ R1 và yêu cầu R2, còn P2 giữ R2 và yêu cầu R1, tạo thành chu trình (P1→R2→P2→R1→P1).

graph LR
    P1(("P1")) -->|Yêu cầu| R2["R2"]
    R2 -->|Cấp phát| P2(("P2"))
    P2 -->|Yêu cầu| R1["R1"]
    R1 -->|Cấp phát| P1

Quy tắc nhận diện cốt lõi thay đổi theo số thực thể (instance) của tài nguyên. Nếu mỗi tài nguyên chỉ có một thực thể, sự tồn tại của chu trình trong đồ thị là điều kiện cần và đủ của bế tắc. Ngược lại, nếu tài nguyên có nhiều thực thể, chu trình chỉ là điều kiện cần chứ không phải điều kiện đủ của bế tắc. Bởi vì dù có chu trình, nếu có tiến trình sắp trả lại một thực thể khác của tài nguyên đó thì có thể không phải là bế tắc. Vì vậy với khóa chỉ có một thực thể thì phát hiện chu trình đơn giản là đủ, nhưng với nhóm tài nguyên có nhiều thực thể thì cần phát hiện chính xác theo họ thuật toán Banker. Đồ thị chờ (Wait-for Graph) là dạng rút gọn thu gọn (collapse) các đỉnh tài nguyên trong RAG, chỉ giữ lại quan hệ chờ giữa các tiến trình, và là cấu trúc dữ liệu mà bộ phát hiện bế tắc của DBMS thực sự sử dụng.

4. Các kỹ thuật xử lý bế tắc

Ứng phó bế tắc chia thành chiến lược tĩnh ngăn chặn phát sinh (phòng ngừa, tránh) và chiến lược động cho phép phát sinh nhưng ứng phó sau đó (phát hiện, khôi phục). Thêm vào đó là thuật toán đà điểu bỏ qua hoàn toàn, tổng hợp lại theo các trục như sau.

flowchart TD
    S["Chiến lược ứng phó bế tắc"] --> P["Phòng ngừa (Prevention)"]
    S --> A["Tránh (Avoidance)"]
    S --> D["Phát hiện (Detection)"]
    S --> R["Khôi phục (Recovery)"]
    S --> I["Bỏ qua (Ostrich Algorithm)"]
    P --> P1["Chặn trước một trong 4 điều kiện"]
    A --> A1["Xác định trạng thái an toàn trước khi cấp phát<br/>Thuật toán Banker"]
    D --> D1["Phát hiện chu trình trong<br/>đồ thị cấp phát tài nguyên·đồ thị chờ"]
    R --> R1["Kết thúc tiến trình hoặc trưng dụng tài nguyên"]
    I --> I1["Tần suất thấp thì khởi động lại để xử lý"]

A. Phòng ngừa (Prevention). Là chiến lược mạnh nhất, khiến một trong bốn điều kiện cần không thể thỏa mãn ngay từ giai đoạn thiết kế. Loại trừ tương hỗ được nới lỏng bằng cách ảo hóa tài nguyên để có thể chia sẻ như spooling; giữ và chờ được ngăn bằng cách buộc yêu cầu toàn bộ tài nguyên cần thiết một lần hoặc chỉ được yêu cầu khi không giữ tài nguyên nào. Không trưng dụng được phá bằng cách buộc nhả tài nguyên đang giữ khi không lấy được tài nguyên bổ sung, còn chờ vòng tròn được phá bằng cách gán số thứ tự toàn cục cho mọi tài nguyên và chỉ cho phép giành theo thứ tự tăng dần.

Trong bốn cách chặn điều kiện, cách được dùng rộng rãi nhất trong thực tế là sắp thứ tự tài nguyên (chỉ định thứ tự khóa toàn cục) nhằm loại bỏ chờ vòng tròn. Bởi vì loại trừ tương hỗ là bản chất vật lý của tài nguyên nên khó loại bỏ; yêu cầu gộp một lần trong giữ và chờ khiến giữ trước cả những tài nguyên không thực sự dùng, làm hiệu suất sử dụng giảm mạnh; còn thu hồi cưỡng bức trong không trưng dụng dễ phá vỡ tính nhất quán của giao dịch. Ngược lại, loại bỏ chờ vòng tròn chỉ cần một quy tắc "luôn lấy khóa theo thứ tự tăng dần của số thứ tự đã định" nên hiện thực đơn giản, ít tác dụng phụ, và hầu hết hướng dẫn lập trình ứng dụng đều chọn cách này.

Tuy nhiên, phòng ngừa chắc chắn bao nhiêu thì cái giá cũng lớn bấy nhiêu. Giữ trước mọi tài nguyên sẽ cần khiến tài nguyên nhàn rỗi ngay cả khi chưa thực sự dùng, làm giảm hiệu suất sử dụng; và trong codebase quy mô lớn với quy tắc thứ tự toàn cục phức tạp, các đường đi vi phạm thứ tự dễ ẩn nấp nên cần kiểm chứng liên tục. Do đó, phòng ngừa đặc biệt hiệu quả trong các hệ thống có loại tài nguyên rõ ràng và phân cấp khóa được tổ chức gọn gàng.

B. Tránh (Avoidance). Là chiến lược cho phép điều kiện có thể gây bế tắc, nhưng mỗi lần cấp phát tài nguyên đều kiểm tra xem việc cấp phát đó có giữ hệ thống ở trạng thái an toàn (safe state) hay không và từ chối cấp phát nguy hiểm. Trạng thái an toàn là trạng thái tồn tại ít nhất một thứ tự cấp phát tài nguyên (chuỗi an toàn) mà mọi tiến trình có thể hoàn tất không bế tắc. Kỹ thuật tiêu biểu là thuật toán Banker (Banker's Algorithm) của Dijkstra.

Nhận thức cốt lõi của chiến lược tránh là không hy sinh hiệu suất sử dụng bằng cách loại bỏ điều kiện như phòng ngừa, mà mỗi thời điểm chỉ kiểm tra "cấp phát như thế này thì còn con đường để mọi tiến trình kết thúc an toàn không" và chỉ buộc chờ vào lúc nguy hiểm. Nhờ vậy không cần giữ dồn tài nguyên trước nên hiệu suất sử dụng cao hơn phòng ngừa. Đổi lại, mỗi tiến trình phải khai báo trước lượng yêu cầu tối đa về tài nguyên cần trong tương lai và mỗi lần cấp phát phải chạy kiểm tra an toàn (mức O(m·n²)), nên phù hợp với hệ thống nhúng và thời gian thực nơi các yếu tố này hạn chế và dự đoán được, hơn là hệ điều hành đa dụng nơi số loại tài nguyên và số tiến trình biến động.

C. Phát hiện (Detection). Không ngăn bế tắc mà cho phép phát sinh, rồi định kỳ kiểm tra trạng thái hệ thống để xác định có bế tắc hay không. Nếu mỗi tài nguyên có một thực thể thì tìm chu trình trong đồ thị chờ (Wait-for Graph), còn nếu có nhiều thực thể thì chạy thuật toán phát hiện tương tự thuật toán Banker. Chu kỳ kiểm tra ngắn thì phát hiện nhanh nhưng chi phí lớn, chu kỳ dài thì phát hiện chậm và trong thời gian đó tài nguyên đang chờ bị lãng phí.

Thời điểm kiểm tra có hai cách. Cách kiểm tra mỗi khi yêu cầu tài nguyên không được đáp ứng ngay sẽ bắt được bế tắc ngay khi phát sinh và dễ xác định tiến trình gây ra, nhưng tần suất kiểm tra cao nên gánh nặng lớn. Ngược lại, cách chỉ kiểm tra theo khoảng thời gian cố định hoặc khi mức sử dụng CPU giảm xuống dưới ngưỡng nhất định có chi phí thấp, nhưng nhiều chu trình có thể đan xen trong một chu kỳ kiểm tra khiến khó xác định tiến trình nào là nguyên nhân gốc. Hệ quản trị cơ sở dữ liệu (DBMS) là ví dụ tiêu biểu dùng phương thức phát hiện này, và trong thực tế còn đặt thêm timeout chờ khóa để phòng khi phát hiện thất bại hoặc chậm trễ.

D. Khôi phục (Recovery). Là giai đoạn thực sự gỡ bỏ bế tắc đã được phát hiện. Có hai cách. Một là kết thúc tiến trình: kết thúc tất cả các tiến trình liên quan đến bế tắc (chắc chắn nhưng tổn thất lớn) hoặc kết thúc từng tiến trình một cho đến khi bế tắc được gỡ. Hai là trưng dụng tài nguyên: chọn nạn nhân (victim), tước tài nguyên và rollback tiến trình đó về điểm an toàn trước đó.

Lựa chọn nạn nhân không phải là giết đại một tiến trình mà là bài toán tối ưu hóa nhằm cực tiểu tổng chi phí. Cần tổng hợp mức ưu tiên, thời gian CPU đã tiêu thụ, khối lượng công việc còn lại, loại và số tài nguyên đang chiếm, chi phí cần cho rollback… để chọn đối tượng "gỡ bế tắc với tổn thất nhỏ nhất". Ví dụ, giết giao dịch vừa bắt đầu với khối lượng công việc ít thì chi phí rollback nhỏ, còn giao dịch chạy lâu sắp hoàn tất thì nên giữ lại.

Lúc này, rủi ro nhất định phải quản lý đồng thời là đói tài nguyên (starvation). Nếu chỉ lấy chi phí rollback làm tiêu chí, cùng một tiến trình chi phí thấp có thể luôn bị hy sinh lặp lại và không bao giờ hoàn tất. Để ngăn điều này, tích lũy số lần bị hy sinh vào hàm chi phí, hoặc dùng kỹ thuật lão hóa (aging) tăng dần mức ưu tiên của tiến trình bị đẩy lùi nhiều lần để bảo đảm tính công bằng — sớm muộn nó cũng chắc chắn hoàn tất.

5. Thuật toán Banker và so sánh các kỹ thuật xử lý

Thuật toán Banker lấy tên từ nguyên lý ngân hàng chỉ cho vay trong phạm vi luôn có thể đáp ứng yêu cầu của mọi khách hàng. Dựa trên lượng yêu cầu tối đa mà mỗi tiến trình khai báo (Max), lượng đang được cấp (Allocation), lượng cần thêm (Need = Max − Allocation) và tài nguyên khả dụng của hệ thống (Available), thuật toán kiểm tra an toàn (Safety Algorithm) xác nhận xem khi chấp nhận một yêu cầu tài nguyên thì chuỗi an toàn có còn tồn tại hay không. Nếu an toàn thì cấp phát, nếu không thì cho tiến trình yêu cầu chờ.

Ví dụ, nếu tổng tài nguyên là 10, yêu cầu tối đa của P1·P2·P3 lần lượt là 7·4·9, lượng đang cấp là 2·2·2, khả dụng là 4, thì Need là 5·2·7. Với khả dụng 4, hoàn tất P2 (Need 2) trước thì thu hồi được 4 tài nguyên, khả dụng thành 6; tiếp theo hoàn tất P1 (Need 5) được khả dụng 8; cuối cùng hoàn tất được P3 (Need 7), nên tồn tại chuỗi an toàn <P2, P1, P3>. Tức là trạng thái này an toàn. Nếu ở trạng thái này có một yêu cầu khiến không còn chuỗi an toàn nào thì yêu cầu đó bị từ chối.

Kỹ thuật	Thời điểm	Yêu cầu thông tin trước	Hiệu suất sử dụng tài nguyên	Áp dụng tiêu biểu
Phòng ngừa (Prevention)	Chặn điều kiện khi thiết kế	Không cần	Thấp	Sắp thứ tự tài nguyên (phân cấp khóa)
Tránh (Avoidance)	Kiểm tra an toàn khi cấp phát	Cần lượng yêu cầu tối đa	Trung bình	Hệ thống nhúng, thời gian thực
Phát hiện·Khôi phục (Detection)	Kiểm tra·gỡ bỏ sau khi phát sinh	Không cần	Cao	Giao dịch DBMS
Bỏ qua (Ostrich)	Không ứng phó	Không cần	Cao nhất	HĐH đa dụng (hiếm khi xảy ra)

Thuật toán Banker tuy thanh lịch về lý thuyết nhưng có giới hạn rõ rệt khi áp dụng thực tế. Thứ nhất, mỗi tiến trình phải biết trước chính xác lượng yêu cầu tài nguyên tối đa, điều khó biết trước với khối lượng công việc tương tác và máy chủ. Thứ hai, nếu số tiến trình và số tài nguyên thay đổi động thì chi phí kiểm tra mỗi lần tăng lên. Thứ ba, không có bảo đảm tài nguyên luôn khả dụng (hỏng hóc, thu hồi) nên có thể không khớp với giả định của hệ thống thực. Vì vậy thuật toán Banker hầu như không được dùng trong HĐH đa dụng, mà được tận dụng làm nền tảng khái niệm trong các lĩnh vực độ tin cậy cao có giới hạn như hàng không, vũ trụ, điều khiển công nghiệp — nơi lượng yêu cầu được đặc tả.

Khái niệm nhất định phải phân biệt ở đây là quan hệ giữa trạng thái an toàn, trạng thái không an toàn và trạng thái bế tắc. Trạng thái an toàn chắc chắn không có bế tắc, nhưng trạng thái không an toàn không đồng nghĩa với bế tắc. Trạng thái không an toàn chỉ là trạng thái "không thể bảo đảm chuỗi an toàn", và tùy mẫu yêu cầu thực tế của các tiến trình, vẫn có thể may mắn kết thúc mà không bế tắc. Tức là trạng thái bế tắc là tập con của trạng thái không an toàn, và chiến lược tránh là kiểm soát cấp phát tài nguyên một cách bảo thủ để không bước chân vào vùng không an toàn này. Vì sự bảo thủ này, chiến lược tránh phải trả giá bằng việc từ chối cả những yêu cầu thực ra sẽ không gây bế tắc, làm giảm hiệu suất sử dụng tài nguyên. Trong ví dụ trên, nếu P3 yêu cầu Need 7 mà khả dụng chỉ có 4 và không có thứ tự nào hoàn tất được, yêu cầu đó gây ra trạng thái không an toàn nên bị từ chối ngay và P3 phải chờ.

Phòng ngừa thì an toàn nhưng đắt, bỏ qua (thuật toán đà điểu) thì rẻ nhưng rủi ro. HĐH đa dụng như Linux, Windows có bế tắc ở mức nhân cực kỳ hiếm và chi phí phòng ngừa/tránh lớn nên phần lớn được thiết kế gần với chiến lược bỏ qua, khi có vấn đề thì để khởi động lại xử lý. Ngược lại, DBMS nơi nhiều giao dịch tranh chấp khóa thì phát hiện và khôi phục là bắt buộc, nên tích hợp sẵn bộ phát hiện bế tắc dựa trên đồ thị chờ, và khi phát hiện bế tắc sẽ tự động chọn giao dịch có chi phí rollback nhỏ nhất làm nạn nhân và rollback dưới dạng deadlock victim.

6. Chuyên sâu: Bế tắc trong thực tiễn

A. Bế tắc cơ sở dữ liệu. DBMS quan hệ thường phát sinh bế tắc trong quá trình bảo đảm tính khả tuần tự bằng khóa hai pha (2PL). Oracle, SQL Server, MySQL (InnoDB) đều phát hiện bế tắc bằng đồ thị chờ, tự động rollback một giao dịch và trả lỗi cho ứng dụng (ví dụ: SQL Server 1205 "deadlock victim"). Có ba nguyên tắc ứng phó thực tiễn. Thứ nhất, thống nhất thứ tự truy cập bảng/dòng trong giao dịch trên toàn ứng dụng để loại bỏ chờ vòng tròn. Thứ hai, giữ giao dịch ngắn và nhỏ để giảm thời gian giữ khóa. Thứ ba, lỗi bế tắc có thể phát sinh một cách bình thường nên cần đưa logic thử lại (retry) vào ứng dụng để bảo đảm khả năng phục hồi. Thực tế có nhiều trường hợp hệ thống chuyển khoản batch khối lượng lớn và trừ tồn kho đã giảm mạnh tần suất bế tắc nhờ áp dụng quy tắc lấy khóa theo thứ tự tăng dần của ID tài khoản/sản phẩm. Ví dụ, có báo cáo về trường hợp cải tiến trong hệ thống thanh toán với hàng nghìn giao dịch chuyển khoản mỗi giây: trước khi thống nhất thứ tự khóa, vào giờ cao điểm phát sinh hàng trăm rollback do bế tắc mỗi phút, nhưng sau khi áp dụng đồng thời quy tắc thứ tự tăng dần theo ID và thử lại 3 lần với backoff lũy thừa, số thất bại cuối cùng do bế tắc giảm xuống gần như bằng 0.

B. Bế tắc luồng trong ứng dụng. Trong các ứng dụng đa luồng như Java, C++, Go, nếu hai luồng lấy hai khóa theo thứ tự ngược nhau thì phát sinh bế tắc. Java cung cấp thông tin chẩn đoán "Found one Java-level deadlock" qua jstack hoặc thread dump, và ngăn chờ vô hạn bằng cách giành khóa có timeout như tryLock(timeout). Biện pháp căn bản vẫn là thứ tự khóa nhất quán (lock ordering). Ngôn ngữ Go khuyến khích giao tiếp dựa trên channel để giảm bản thân khóa trạng thái chia sẻ, nhưng nếu mọi goroutine đều chờ phản hồi channel của nhau thì runtime sẽ phát hiện "all goroutines are asleep - deadlock!" và gây panic.

Các nguyên tắc cụ thể để phòng ngừa bế tắc luồng trong thực tiễn gồm: ① khi cần nhiều khóa thì luôn chỉ giành theo thứ tự toàn cục đã định, ② giảm thiểu đoạn giữ khóa và không gọi dịch vụ bên ngoài trong khi đang giữ khóa, ③ dùng timeout tryLock để biến chờ vô hạn thành giới hạn thời gian, ④ khi có thể thì dùng đối tượng bất biến, truyền thông điệp, collection đồng thời để giảm chính trạng thái khả biến chia sẻ. Các nguyên tắc này là phương pháp thực hành phá vỡ bốn điều kiện đã nói ở trên ở cấp độ mã nguồn.

C. Bế tắc phân tán trong hệ thống phân tán. Trong microservice hoặc giao dịch phân tán, phát sinh bế tắc phân tán (distributed deadlock) — vòng chờ hình thành giữa các tài nguyên rải rác trên nhiều nút, và vì khó quan sát ngay đồ thị chờ toàn cục như với một nút đơn nên việc phát hiện khó hơn nhiều. Để giải quyết, người ta dùng kỹ thuật truy vết cạnh (edge-chasing) trong đó mỗi nút chuyển thông điệp thăm dò (probe) chứa thông tin chờ để lần theo vòng, hoặc các phương thức Wait-Die, Wound-Wait gán dấu thời gian cho giao dịch và hủy giao dịch trẻ hơn. Trong thực tế, tránh bằng dừng theo timeout rồi thử lại và giao dịch bù trừ của mẫu Saga thực tế hơn là phát hiện hoàn hảo.

D. Bản chất bế tắc qua bài toán các triết gia ăn tối. Bài toán các triết gia ăn tối (Dining Philosophers) do Dijkstra đưa ra là ví dụ kinh điển thể hiện cô đọng bế tắc và cách giải quyết. Năm triết gia ngồi quanh bàn tròn, nếu mỗi người cầm nĩa bên trái trước rồi cố cầm nĩa bên phải, thì vào khoảnh khắc tất cả cùng cầm nĩa trái, họ rơi vào vòng chờ (bế tắc) chờ nĩa phải mãi mãi. Lời giải của bài toán này chính là phiên bản thu nhỏ của chiến lược phòng ngừa. ① Cho triết gia số lẻ cầm từ trái, số chẵn cầm từ phải, tạo thứ tự giành tài nguyên bất đối xứng thì chờ vòng tròn bị phá. ② Giới hạn số triết gia có thể ăn đồng thời là N−1 người (semaphore) thì giữ và chờ được nới lỏng. ③ Cho cầm cả hai nĩa một cách nguyên tử cùng lúc thì chính giữ và chờ biến mất. Các vấn đề thực tế như cạn connection pool, thread pool chờ lẫn nhau về bản chất cũng có cấu trúc này nên cùng nguyên lý giải quyết được áp dụng nguyên vẹn.

7. Lưu ý và hàm ý (góc nhìn Kỹ sư chuyên nghiệp)

Lựa chọn chiến lược là sự đánh đổi chi phí-rủi ro. Phòng ngừa và tránh chặn bế tắc từ gốc nhưng hy sinh hiệu suất sử dụng tài nguyên và thông lượng, còn phát hiện, khôi phục, bỏ qua giữ được hiệu năng nhưng chấp nhận sự cố xảy ra. Thực tế là tổng hợp mức yêu cầu tính sẵn sàng của hệ thống (SLA), tần suất tranh chấp tài nguyên, khả năng thử lại để kết hợp các chiến lược khác nhau theo từng tầng — ví dụ, tầng DB áp dụng phát hiện/khôi phục, tầng ứng dụng đồng thời áp dụng phòng ngừa bằng sắp thứ tự khóa.
Phòng ngừa ở giai đoạn thiết kế hiệu quả chi phí hơn ứng phó sau sự việc. Bế tắc khó tái hiện nên chi phí gỡ lỗi trong vận hành rất lớn. Bắt buộc các quy tắc như chuẩn hóa thứ tự giành khóa, tối thiểu hóa giao dịch, bắt buộc timeout bằng hướng dẫn lập trình, công cụ phân tích tĩnh, danh sách kiểm tra review mã ngay từ đầu quá trình phát triển sẽ giảm tổng chi phí sở hữu (TCO).
Thiết kế khả năng phục hồi (resilience) có thể thực tế hơn phòng ngừa hoàn hảo. Trong môi trường phân tán rất khó loại bỏ hoàn toàn bế tắc. Trang bị các cơ chế phục hồi lấy sự cố làm tiền đề như timeout, thử lại, backoff lũy thừa, circuit breaker, giao dịch bù trừ thì có thể khiến hệ thống tự hấp thụ những bế tắc thỉnh thoảng phát sinh.
Phải quản lý tích hợp cùng với đói tài nguyên và livelock. Nếu chỉ chặn bế tắc mà lơ là việc chọn nạn nhân, một giao dịch cụ thể có thể bị rollback lặp lại và rơi vào đói tài nguyên, hoặc chuyển thành livelock khi các bên chỉ liên tục nhường nhau. Cần quản lý tài nguyên tổng thể bao gồm cả tính công bằng (fairness), như phản ánh số lần rollback vào chi phí và dùng kỹ thuật lão hóa (aging) để tăng ưu tiên cho các yêu cầu chờ lâu.
Bảo đảm khả năng quan sát (Observability) là cốt lõi của vận hành. Cần giám sát các chỉ số bế tắc và chờ khóa (ví dụ: lock wait, blocking session của DB, thread dump của ứng dụng) để sớm nắm bắt dấu hiệu bất thường, và nội tại hóa vào quy trình vận hành vòng phản hồi phân tích log bế tắc sau sự việc để loại bỏ nguyên nhân lặp lại.
Trong kỷ nguyên đám mây và container, ranh giới tài nguyên mở rộng nên hình thái bế tắc cũng tiến hóa. Các tài nguyên logic như connection pool, thread pool, khóa phân tán (Redis Redlock, ZooKeeper) trở thành điểm bế tắc mới. Ví dụ, nếu dịch vụ A gọi đồng bộ B và B lại gọi A, sự phụ thuộc vòng này làm cạn thread pool thì dù từng tiến trình vẫn sống, hệ thống thực chất đã rơi vào bế tắc. Các nguyên tắc thiết kế như kiến trúc bất đồng bộ không chặn (non-blocking), cách ly bulkhead, loại bỏ vòng trong đồ thị lời gọi là biện pháp phòng ngừa.
Phải sớm phát hiện bế tắc tiềm ẩn bằng kiểm chứng tự động. Nên làm lộ ra khả năng bế tắc trước khi vận hành bằng công cụ phân tích tĩnh (ví dụ: phát hiện vi phạm thứ tự khóa), công cụ kiểm thử đồng thời, bơm tải qua chaos engineering. Đặc biệt do tính chất khó tái hiện, chỉ độ bao phủ kiểm thử là không đủ, nên cách tiếp cận chứng minh tính không bế tắc (deadlock-freedom) của giao thức đồng thời bằng kiểm chứng hình thức, kiểm tra mô hình (TLA+ …) cũng được dùng trong các hệ thống độ tin cậy cao.

Tài liệu tham khảo

Silberschatz, Galvin, Gagne, "Operating System Concepts" (chương Deadlocks)
E. G. Coffman et al., "System Deadlocks", ACM Computing Surveys, 1971
Microsoft SQL Server Docs — Deadlocks guide: https://learn.microsoft.com/en-us/sql/relational-databases/sql-server-deadlocks-guide
Oracle Database Concepts — Locks and Deadlocks: https://docs.oracle.com/en/database/oracle/oracle-database/
MySQL Reference Manual — Deadlocks in InnoDB: https://dev.mysql.com/doc/refman/8.0/en/innodb-deadlocks.html
E. W. Dijkstra, "Hierarchical Ordering of Sequential Processes" (nguyên bản Dining Philosophers)

Tóm tắt một câu: Bế tắc phát sinh khi bốn điều kiện loại trừ tương hỗ, giữ và chờ, không trưng dụng, chờ vòng tròn đồng thời thỏa mãn; cần kết hợp các chiến lược phòng ngừa, tránh (thuật toán Banker), phát hiện, khôi phục phù hợp với đặc tính hệ thống, đồng thời xử lý bằng thiết kế khả năng phục hồi như sắp thứ tự khóa, timeout và thử lại.