3.5.1 Khái niệm tắc nghẽn:

Một tập hợp các tiến trình gọi là ở tình trạng tắc nghẽn nếu mỗi tiến trình trong tập hợp đều chờ đợi tài nguyên mà tiến trình khác trong tập hợp đang chiếm giữ. Ví dụ tại một thời diểm, tiến trình 1 đang giữ tài nguyên R1, yêu cầu R2 và tiến trình 2 đang giữ tài nguyên R2, yêu cầu R1, như vây yêu cầu về tài nguyên không thể đáp ứng cho cả hai tiến trình. Khi đó không có tiến trình nào có thể tiếp tục xử lý, cũng như giải phóng tài nguyên cho tiến trình khác sử dụng, tất cả các tiến trình trong tập hợp đều bị khóa vĩnh viễn!

3.5.2 Điều kiện xuất hiện tắc nghẽn

Hệ thống sẽ xuất hiện tắc nghẽn khi và chỉ khi có đủ 4 điều kiện sau:

+ Điều kiện 1: Có sử dụng tài nguyên không thể chia sẻ

Mỗi thời điểm, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình , khi tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên cho tiến trình khác.

+ Điều kiện 2:  Sự chiếm giữ và yêu cầu thêm tài nguyên không thể chia sẻ

Có tiến trình chiếm giữ các tài nguyên trong khi lại chờ được cấp phát thêm tài nguyên bị chiếm giữ bởi tiến trình khác.

+ Điều kiện 3: Không thu hồi tài nguyên từ tiến trình đang giữ chúng

Tài nguyên không thể được thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sử dụng chúng xong.

+ Điều kiện 4: Tồn tại một chu trình trong đồ thị cấp phát tài nguyên

Có ít nhất hai tiến trình chờ đợi lẫn nhau: tiến trình này chờ được cấp phát tài nguyên đang bị tiến trình khác chiếm giữ và ngược lại.

* Các phương pháp xử lý tắc nghẽn

+ Sử dụng một thuật toán cấp phát tài nguyên nào đó mà bảo đảm không bao giờ xảy ra tắc nghẽn.

+ Hoặc cho phép xảy ra tắc nghẽn và tìm cách sữa chữa tắc nghẽn.

+ Hoặc bỏ qua việc xử lý tắc nghẽn, xem như hệ thống không bao giờ xảy ra tắc nghẽn. Thường áp dụng phương pháp này khi hệ thống rất ít khi bị tắc nghẽn và chi phí kiểm tra tắc nghẽn cao (UNIX và WINDOWS sử dụng phương pháp này)

* Ngăn chặn tắc nghẽn

Để không xảy ra tắc nghẽn, cần bảo đảm tối thiểu một trong 4 điều kiện đã nêu ở trên không xảy ra:

+ Điều kiện 1 gần như không thể tránh được điều kiện này vì bản chất tài nguyên gần như cố định.

+ Để điều kiện 2 không xảy ra, thì có thể áp dụng một trong hai nguyên tắc sau :

- Tiến trình phải yêu cầu tất cả các tài nguyên cần thiết trước khi cho bắt đầu xử lý. Phương pháp này gặp khó khăn là hệ điều hành khó có thể biết trước các tài nguyên tiến trình cần sử dụng vì nhu cầu tài nguyên còn phụ thuộc vào quá trình tiến trình thực hiện. Ngoài ra nếu cho tiến trình chiếm giữ sẵn các tài nguyên chưa cần sử dụng ngay thì việc sử dụng tài nguyên sẽ kém hiệu quả.

- Khi tiến trình yêu cầu một tài nguyên mới và bị từ chối, nó phải giải phóng các tài nguyên đang chiếm giữ , sau đó lại được cấp phát trở lại cùng lần với tài nguyên mới. Phương pháp này sẽ gặp khó khăn trong việc bảo vệ tính toàn vẹn dữ liệu của hệ thống.

+ Để điều kiện 3 không xảy ra, hệ điều hành cần cho phép hệ thống được thu hồi tài nguyên từ các tiến trình bị khoá và cấp phát trở lại cho tiến trình khi nó thoát khỏi tình trạng bị khóa. Tuy nhiên với một số loại tài nguyên, việc thu hồi sẽ rất khó khăn vì vi phạm sự toàn vẹn dữ liệu.

+ Để điều kiện 4 không xảy ra, có thể cấp phát tài nguyên theo một sự phân cấp như sau :

Gọi R = {R1, R2,...,Rm} là tập các loại tài nguyên. Các loại tài nguyên được đánh số thứ tự . Ví dụ : F(đĩa) = 2, F(máy in) = 12,…