Lời mở đầu

Ở phần trước chúng ta đã tìm hiểu về Đồng bộ hóa tiến trình trong hệ điều hành. Trong đó có 2 giải pháp là Semaphore và Monitor. Dù dùng bất cứ giải pháp nào cũng sẽ có tỉ lệ xẩy ra vấn đề tắc nghẽn hệ thống (deadlock).

Hai tiến trình trong ảnh trên đang bị deadlock bởi vì sau lượt chạy đầu thì $P_0$ đang nắm giữ $S$, $P_1$ thì nắm giữ $Q$.

Đến lượt chạy thứ hai thì $P_0$ chờ $Q (wait(Q))$, còn $P_1$ chờ $S (wait(S))$. Trong khi cả hai đang nắm giữ phần mà đối phương đang cần.

Thế là hai tiến trình rơi vào trang thái chờ đợi vô hạn và đây gọi là deadlock.

Đây là ví dụ tiêu biểu và dễ hiểu nhất về deadlock trong OS. Mục tiêu của bài viết này sẽ là giới thiệu các khái niệm liên quan và các giải pháp cho vấn đề này.

Các nguyên nhân dẫn đến Deadlock

Các tiến trình sẽ sử dụng một tài nguyên theo cách sau:

• Yêu cầu tài nguyên
• Sử dụng tài nguyên
• Giải phóng tài nguyên

Và tình trạng deadlock sẽ diễn ra giống như trong phần mở đầu của bài viết có nói.

Deadlock sẽ xẩy ra nếu 4 điều kiện sau đồng thời thỏa mãn:

1. Mutual Exclusion: Chỉ có một tiến trình được sử dụng một loại tài nguyên nhất định trong một lúc nhất định, tài nguyên sẽ không thể chia sẻ.
2. Hold and Wait: Có một tiến trình đang giữ một tài nguyên và nó đang chờ đợi một tài nguyên nào đó.
3. No Preemption: Tài nguyên đang được một tiến trình nắm giữ thì sẽ không thể bị hệ thống thu hồi và trưng dụng giữa chừng.
4. Circular Wait: Xuất hiện chu trình trong đồ thị cấp phát tài nguyên như trên ảnh sau:

Những phương pháp để xử lý khi gặp Deadlock:

1. Phòng ngừa việc deadlock cho hệ thống.
2. Cho phép deadlock xẩy ra và ta sẽ bắt đầu chữa bệnh trong hệ thống.
3. Mặc kệ việc deadlock xẩy ra và giao việc xử lý cho người dùng hệ thống. Đây là cách hiệu quả và đơn giản nhất được áp dụng cho nhiều hệ điều hành, bao gồm cả UNIX.

1. Ngăn ngừa Deadlock:

Ta sẽ bảo đảm hệ thống không đáp ứng đủ 4 điều kiện xẩy ra deadlock nêu ở trên.

1. Mutual Exclusion: Không yêu cầu cho các tài nguyên dùng chung, cần phải có với các tài nguyên không dùng chung.
2. Hold and Wait: Phải đảm bảo rằng một tiến trình không được nắm bất cứ tài nguyên nào trước khi nó thực hiện một yêu cầu. Điều này dẫn đến hiệu quả kém và có thể gây ra hiện tượng starvation.
3. No Preemption: Hệ thống phải có cơ chế chống độc quyền và có thể thu hồi tài nguyên từ bất cứ tiến trình nào.
4. Circular Wait: Hệ thống phải tìm ra một thứ tự cấp phát tài nguyên mà không xẩy tạo ra một chu trình.

Do đó ta có một số kết luận cơ bản sau:

• Nếu đồ thị cấp phát tài nguyên của hệ thống không xuất hiện các chu trình thì sẽ không có deadlock.
• Nếu đồ thị cấp phát tài nguyên của hệ thống có xuất hiện một chu trình thì:
  • Nếu mỗi loại tài nguyên chỉ có đúng một thể hiện -> bị deadlock.
  • Nếu mỗi loại tài nguyên đều có nhiều hơn một thể hiện -> có thể bị deadlock.

Banker's Algorithm:

Thuật toán này do Edsger Dijkstra nghĩ ra và lấy ý tưởng từ cách hoạt động của nhà Bank.

Yêu cầu hệ thống phải có "thông tin tiên nghiệm" (biết trước tương lai). Mỗi tiến trình khi bắt đầu chạy phải khai báo số lượng tài nguyên tối đa (Maximum) mà nó sẽ cần. Hệ thống sẽ liên tục kiểm tra trạng thái phân bổ tài nguyên để đảm bảo không bao giờ rơi vào tình trạng "chờ đợi vòng tròn" (mọi người cùng khóa tài nguyên của nhau).

Thuật toán Nhà băng: Được đặt tên dựa trên cách một ngân hàng cấp tín dụng. Ngân hàng (Hệ điều hành) chỉ cho vay tiền (cấp tài nguyên) nếu khách hàng (Tiến trình) chứng minh được họ có thể hoàn thành dự án và trả lại toàn bộ tiền. Nếu việc cấp tài nguyên có nguy cơ làm ngân hàng cạn vốn và khách hàng không thể chạy xong, hệ thống sẽ bắt tiến trình đó phải đợi.

Để thuật toán chạy được, hệ thống quản lý 4 cấu trúc dữ liệu chính (giả sử có n tiến trình và m loại tài nguyên):

• Available: Vectơ tài nguyên hiện đang rảnh rỗi (chưa cấp cho ai).
• Max: Ma trận yêu cầu tối đa của từng tiến trình.
• Allocation: Ma trận tài nguyên đã cấp hiện tại cho từng tiến trình.
• Need: Ma trận tài nguyên còn cần thêm để hoàn thành công việc.
  • Công thức: Need = Max - Allocation

Thuật toán An toàn - Safety Algorithm

Làm sao để biết hệ thống có an toàn hay không? Thuật toán sẽ thử tìm một Chuỗi an toàn (Safe Sequence).

1. Hệ thống dùng một vectơ Work (ban đầu bằng Available) và mảng Finish (ban đầu đều là false - chưa ai chạy xong).
2. Hệ thống đi tìm một tiến trình i thỏa mãn 2 điều kiện:
   • Chưa chạy xong (Finish[i] = false).
   • Tài nguyên nó cần thêm nhỏ hơn hoặc bằng tài nguyên đang rảnh: Need[i] <= Work.
3. Nếu tìm thấy, hệ thống cho phép tiến trình đó chạy (giả lập). Chạy xong, nó sẽ trả lại toàn bộ tài nguyên đã giữ.
   • Work = Work + Allocation[i]
   • Finish[i] = true.
4. Lặp lại bước 2. Nếu cuối cùng tất cả tiến trình đều Finish = true, hệ thống ở Trạng thái an toàn.

Ví dụ:

Tài nguyên tổng cộng: A(10), B(5), C(7).

Tài nguyên rảnh (Available): A(3), B(3), C(2).

• Bước 1 - Tính Need: Lấy Max - Allocation. Ví dụ với $P_0$: $Max(7,5,3) - Allocation(0,1,0) = Need(7,4,3)$. Bạn đã tính đúng toàn bộ cột Need.

• Bước 2 - Tìm chuỗi an toàn: (Bắt đầu với Work = 3 3 2)

  1. Lượt 1: Xét xem ai có Need $\le$ Work(3,3,2)? Chỉ có $P_1$ (Need: 1,2,2) và $P_3$ (Need: 0,1,1) thỏa mãn. Theo chữ đỏ, bạn chọn cho $P_1$ chạy trước.
     • $P_1$ chạy xong, trả lại Allocation(2,0,0).
     • Work mới = $(3,3,2) + (2,0,0) = \mathbf{(5,3,2)}$.
  2. Lượt 2: Lúc này Work = 5,3,2. Xem ai có Need $\le$ (5,3,2)? Có $P_3$ và $P_4$. Chữ đỏ chọn $P_3$.
     • $P_3$ chạy xong, trả lại Allocation(2,1,1).
     • Work mới = $(5,3,2) + (2,1,1) = \mathbf{(7,4,3)}$.
  3. Lượt 3: Lúc này Work = 7,4,3. Bất ngờ là lúc này Need của cả $P_0(7,4,3)$, $P_2(6,0,0)$ và $P_4(4,3,1)$ đều nhỏ hơn hoặc bằng Work. Nghĩa là chọn ai tiếp theo cũng được!
     • Trong slide in chữ đen: Họ chọn chuỗi $$.
     • Trong ghi chú chữ đỏ của bạn: Bạn chọn chuỗi $P_1 \rightarrow P_3 \rightarrow \mathbf{P_0 \rightarrow P_2 \rightarrow P_4}$.
     • Cả hai cách đều hoàn toàn đúng! Chỉ cần chỉ ra được ÍT NHẤT một chuỗi để tất cả cùng hoàn thành là hệ thống được chứng minh là An Toàn.
  4. Chọn $P_0$.
     • $P_0$ trả lại Allocation(0,1,0). Work mới = $(7,4,3) + (0,1,0) = \mathbf{(7,5,3)}$.
  5. Chọn $P_2$.
     • $P_2$ trả lại Allocation(3,0,2). Work mới = $(7,5,3) + (3,0,2) = \mathbf{(10,5,5)}$.
  6. Cuối cùng chọn $P_4$.
     • $P_4$ trả lại Allocation(0,0,2). Work mới = $(10,5,5) + (0,0,2) = \mathbf{(10,5,7)}$. (Đúng bằng tổng tài nguyên ban đầu hệ thống có, chứng tỏ giải đúng).

2. Chữa bệnh Deadlock:

Thay vì cẩn thận phòng tránh từ đầu như Thuật toán Nhà băng (Banker's Algorithm), chiến lược này cứ để cho hệ thống chạy tự do, cấp phát tài nguyên thoải mái. Tuy nhiên, định kỳ hệ thống sẽ chạy một thuật toán để "khám sức khỏe" xem: Liệu ngay lúc này có bế tắc nào đang xảy ra không? Và nếu có thì những tiến trình nào đang bị kẹt?

1. Trường hợp mỗi loại tài nguyên chỉ có 1 bản sao

Nếu hệ thống rất đơn giản (mỗi loại tài nguyên như máy in, ổ cứng... chỉ có đúng 1 cái), ta không cần dùng ma trận phức tạp.

• Hệ thống sẽ vẽ một Đồ thị chờ (Wait-for graph).
• Đồ thị này loại bỏ các hộp hình vuông (tài nguyên) đi, chỉ giữ lại các vòng tròn (tiến trình). Mũi tên $P_i \rightarrow P_j$ nghĩa là "Tiến trình i đang phải đứng chờ Tiến trình j nhả tài nguyên ra".
• Cách phát hiện: Rất đơn giản, hệ thống chỉ cần tìm xem trong đồ thị có chu trình (vòng lặp) nào không. Nhìn vào slide 2 (hình b), bạn sẽ thấy $P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow P_4 \rightarrow P_1$ tạo thành một vòng tròn khép kín. Mọi người đều đang đợi nhau $\rightarrow$ Chắc chắn có Deadlock!

2. Trường hợp tài nguyên có nhiều bản sao

Lúc này, đồ thị không còn chính xác nữa, ta phải dùng Thuật toán Phát hiện (Detection Algorithm). Thuật toán này nhìn thoáng qua thì gần như y hệt thuật toán Safety của Banker's Algorithm, nhưng có một điểm khác biệt cốt lõi:

• Banker's dùng ma trận Need (số tài nguyên tối đa có thể cần trong tương lai) để dự đoán.
• Detection Algorithm dùng ma trận Request (số tài nguyên thực tế đang yêu cầu ngay lúc này).

Cách thuật toán chạy:

1. Khởi tạo Work = Available (Tài nguyên đang rảnh rỗi).
2. Đánh dấu Finish: Nếu tiến trình nào chưa được cấp cái gì cả (Allocation = 0), coi như nó xong (Finish = true). Còn lại để false.
3. Tìm một tiến trình chưa xong (Finish = false) và yêu cầu hiện tại của nó hệ thống có thể đáp ứng được ngay (Request <= Work).
4. Nếu tìm thấy, giả sử cấp cho nó, đợi nó chạy xong rồi thu hồi lại toàn bộ tài nguyên nó đang giữ: Work = Work + Allocation.
5. Lặp lại cho đến khi không tìm được ai nữa. Nếu cuối cùng vẫn còn tiến trình có Finish = false, thì hệ thống đang bị Deadlock (và các tiến trình false đó chính là thủ phạm).

Ví dụ:

• Khởi đầu: Available = (0, 0, 0) $\rightarrow$ Work = (0, 0, 0).
• Lượt 1: Tìm ai có Request $\le$ (0, 0, 0). Chỉ có $P_0$ (Request: 0, 0, 0) và $P_2$ (Request: 0, 0, 0) thỏa mãn.
  • Ghi chú đỏ của bạn chọn $P_0$ chạy trước.
  • $P_0$ xong, thu hồi lại Allocation của nó: Work mới = $(0,0,0) + (0,1,0) = \mathbf{(0, 1, 0)}$. (Khớp với dòng số 2 bút xanh của bạn).
• Lượt 2: Với Work = (0, 1, 0), chỉ có $P_2$ thỏa mãn (Request: 0, 0, 0).
  • $P_2$ xong, thu hồi Allocation: Work mới = $(0,1,0) + (3,0,3) = \mathbf{(3, 1, 3)}$. (Khớp với dòng số 4 bút xanh).
• Lượt 3: Với Work = (3, 1, 3), ai có Request $\le$ (3, 1, 3)? Có $P_1$(2,0,2), $P_3$(1,0,0), $P_4$(0,0,2) đều thỏa mãn.
  • Bạn chọn $P_1$.
  • $P_1$ xong, thu hồi Allocation: Work mới = $(3,1,3) + (2,0,0) = \mathbf{(5, 1, 3)}$. (Khớp với dòng số 3 bút xanh).
• Lượt 4: Bạn chọn $P_3$ (Request 1,0,0 $\le$ 5,1,3).
  • $P_3$ xong, thu hồi Allocation: Work mới = $(5,1,3) + (2,1,1) = \mathbf{(7, 2, 4)}$. (Khớp với dòng số 5 bút xanh).
• Lượt 5: Cuối cùng chọn $P_4$ (Request 0,0,2 $\le$ 7,2,4).
  • $P_4$ xong, thu hồi Allocation: Work mới = $(7,2,4) + (0,0,2) = \mathbf{(7, 2, 6)}$. (Khớp với dòng cuối bút xanh).

Kết luận: Chuỗi $$ giúp mọi Finish đều bằng true. Hệ thống không có Deadlock.

Khi nào nên dùng Thuật toán Phát hiện?

Như bạn đã thấy ở phần trước, thuật toán phát hiện Deadlock tốn khá nhiều tài nguyên để tính toán (như duyệt các ma trận). Do đó, Hệ điều hành không thể cứ chạy nó liên tục từng giây được. Việc quyết định khi nào chạy dựa vào:

• Tần suất xảy ra bế tắc: Hệ thống này có hay bị bế tắc không? (Nếu hay bị thì phải quét thường xuyên).

• Mức độ thiệt hại: Sẽ có bao nhiêu tiến trình bị ảnh hưởng và phải bắt đầu lại (roll back) nếu ta phát hiện bế tắc trễ?

• Rủi ro khi quét ngẫu nhiên: Nếu Hệ điều hành chỉ rình rình thỉnh thoảng mới chạy thuật toán một cách tùy hứng (arbitrarily), thì trong khoảng thời gian bỏ ngỏ đó, rất nhiều chu trình bế tắc (cycles) đã kịp hình thành và đan xen chằng chịt vào nhau. Lúc đó, ta dọn dẹp rất mệt và chả biết tiến trình nào thực sự là "kẻ khơi mào" ra mớ bế tắc này.

Các phương án Phục hồi sau Bế tắc (Recovery from Deadlock)

Khi đã bắt được Deadlock, Hệ điều hành phải hành động để phá vỡ vòng lặp chờ đợi này. Có 2 cách tiếp cận chính: Giết tiến trình hoặc Cướp tài nguyên.

A. Đình chỉ/Hủy bỏ Tiến trình (Process Termination)

Đây là cách bạo lực. Chúng ta sẽ "giết" (abort) tiến trình để nó nhả tài nguyên ra. Có 2 lựa chọn:

1. Giết TẤT CẢ các tiến trình đang bị bế tắc: Rất nhanh, dứt điểm ngay lập tức nhưng cực kỳ lãng phí. Bao nhiêu công sức tính toán của các tiến trình từ lúc bắt đầu xem như đổ sông đổ biển.
2. Giết TỪNG TIẾN TRÌNH một: Giết 1 cái $\rightarrow$ quét lại xem hết bế tắc chưa $\rightarrow$ nếu chưa thì giết tiếp. Cách này ít lãng phí công sức hơn, nhưng lại tốn thời gian CPU vì phải chạy lại thuật toán dò tìm nhiều lần.

Vậy nếu giết từng cái, chọn ai làm "nạn nhân" trước? Hệ điều hành sẽ xét các tiêu chí:

• Độ ưu tiên (Priority): Tiến trình quan trọng của hệ thống thì tha, giết mấy tiến trình râu ria trước.
• Thời gian: Nếu một tiến trình đã chạy rất lâu (công sức bỏ ra lớn) và sắp xong rồi thì nên giữ lại. Đứa nào mới chạy thì lôi ra chém.
• Tài nguyên đang giữ: Đứa nào đang "ôm" càng nhiều tài nguyên ngon thì ưu tiên giết để thu hồi được nhiều vốn nhất.
• Tài nguyên đang cần: Đứa nào còn đòi hỏi quá nhiều tài nguyên mới chạy xong thì giết quách cho rồi.
• Interactive hay Batch: Tiến trình đang tương tác trực tiếp với người dùng (như gõ Word, di chuột) thì không nên giết vì sẽ làm máy tính bị đơ, giật cục. Chỉ nên giết các tiến trình ngầm (batch).

B. Tước đoạt Tài nguyên (Resource Preemption)

Đây là cách "nhân đạo" hơn. Tha mạng cho tiến trình, chỉ tạm thời lấy lại (cướp/tước đoạt) tài nguyên đang cấp cho nó để đưa cho đứa khác mượn xài đỡ.

• Chọn nạn nhân (Selecting a victim): Chọn tước tài nguyên của tiến trình nào mà ít gây thiệt hại nhất cho hệ thống (minimize cost).
• Quay lui (Rollback): Tiến trình đang chạy mà bị giật mất tài nguyên (ví dụ đang ghi file mà bị lấy mất ổ cứng) thì không thể chạy tiếp. Hệ điều hành phải ép nó lùi về một "trạng thái an toàn" trước đó (giống như load lại file save game gần nhất) và chờ đến khi có lại tài nguyên thì tiếp tục.
• Chống chết đói (Starvation): Sẽ có rủi ro là Hệ điều hành cứ nhè đầu 1 tiến trình "thấp cổ bé họng" để tước tài nguyên hết lần này đến lần khác, khiến nó mỏi mòn chờ đợi không bao giờ xong. Để tránh việc này, thuật toán phải đếm số lần một tiến trình bị quay lui (number of rollback). Nếu nó bị "ăn hiếp" quá nhiều lần rồi, hệ thống bắt buộc phải tha cho nó và chuyển sang tước tài nguyên của đứa khác.

Tài liệu tham khảo

• Abraham Silberschartz, Peter Baer Galvin, Greg Gagne, Operating System Concepts, 9th Edition.
• Geekforgeeks, Introduction of Deadlock in Operating System. [Trực tuyến]. Có sẵn tại Geekforgeeks (Truy cập 2026).