Deadlock là gì? Cách phát hiện và phương pháp xử lý tốt nhất

Các tài nguyên trong quá trình hoạt động vô tình xảy ra các hiện tượng lỗi? Hiện tượng này được gọi là Deadlock, là tình trạng xung đột các tài nguyên của hệ điều hành trên các thiết bị máy tính. Vậy Deadlock có đặc điểm và các hướng khắc phục như thế nào? Bài viết sau đây BKHOST sẽ cùng bạn tìm hiểu thông tin chi tiết về Deadlock.

Deadlock là gì?

Deadlock là tình trạng thường xuyên xảy ra trên mọi thiết bị máy tính hay hệ thống phân tán có các quy trình hoạt động tài nguyên. Cụ thể đó là hai quá trình đang ở trong trạng thái chờ tài nguyên đã được tổ chức sẵn. Vấn đề của Deadlock được hiểu đơn giản giống như câu chuyện con gà và quả trứng.

Ví dụ:

Ví dụ với ba quá trình P1, P2, P3 và ba tài nguyên R1, R2, R3:

Nếu P1 yêu cầu R2 của P2 thì cần phải chờ cho P2 giải phóng tài nguyên và tạo ra R3. Tương tự như vậy đối với P1 và P3. Vì thế mà nó thường xuyên xảy ra các tình trạng Deadlock trong hệ điều hành.

Điều kiện cần thiết cho Deadlock

Bốn điều kiện cơ bản nhất của Deadlock:

• Điều kiện loại trừ lẫn nhau trong Deadlock làm ngăn chặn thao tác chia sẻ tài nguyên giữa các quy trình cùng một lúc.
• Điều kiện giữ và chờ tài nguyên mới trong Deadlock.
• Điều kiện không có trưng dụng tài nguyên, tức là một tài nguyên sẽ không thể lấy lại từ một tiến trình trừ khi tài nguyên đó được giải phóng.
• Điều kiện chờ đợi vòng tròn là một chu trình tiến trình này giữ và chờ các tài nguyên bởi các tiến trình khác.
  Ví dụ: Tiến trình 1 sẽ lấy R1 và chờ R2, tiến trình 2 sẽ lấy R2 và chờ R3…

Phòng ngừa Deadlock

Để có thể phòng ngừa Deadlock hệ điều hành sẽ ngăn chặn các điều kiện có thể gây ra như sau:

Không loại trừ lẫn nhau

Không loại trừ lẫn nhau tức là nhiều quá trình có thể đồng thời truy cập vào một tài nguyên. Tuy nhiên, hậu quả là các tài nguyên sẽ bị mất kiểm soát và làm hỏng tất cả các quá trình thực hiện truy cập. Vì vậy, phương pháp này không thực sự khả thi đối với các hệ điều hành.

Không giữ và đợi

Có một số giải pháp để lấy các tài nguyên cần thiết trước khi bắt đầu quá trình truy cập. Tuy nhiên, bởi vì mỗi quá trình sẽ cần một tài nguyên riêng biệt để có thể bắt đầu nên phương pháp này cũng không đem lại hiệu quả. Hơn nữa, bởi vì mỗi quá trình sẽ không thể xác định số lượng tài nguyên cần sử dụng và thời gian để giải phóng chúng khỏi quá trình.

Hoặc nếu một quá trình muốn có thêm tài nguyên thì cần phải giải phóng các tài nguyên hiện tại. Phương pháp này có thể hạn chế tình trạng giữ và chờ đợi nhưng đôi khi lại gây ra hiện tượng thiếu hụt tài nguyên.

Loại bỏ không có trưng dụng

Bởi vì CPU không thể trưng dụng một số tài nguyên từ quy trình nên dễ gây ra hiện tượng Deadlock. Giải pháp nhanh nhất đó là loại bỏ không có trưng dụng để lấy tài nguyên trong quá trình chờ.

Bỏ chờ đợi vòng tròn

Để khắc phục tình trạng hai hoặc nhiều quá trình bị mắc kẹt trong trạng thái chờ tài nguyên, các giá trị là số nguyên số sẽ được gán cho tài nguyên của quy trình theo thứ tự tăng hoặc giảm nhất định.

Trường hợp tài nguyên tăng dần thì chỉ cho phép truy cập vào tài nguyên bổ sung mới nếu giá trị số nguyên là cao hơn so với trước đó. Còn nếu giá trị số nguyên thấp hơn thì sẽ tiến hành giải phóng tài nguyên cũ để nhận tài nguyên mới. Đối với trường hợp tài nguyên giảm dần thì quá trình sẽ ngược lại.

Tránh Deadlock

Hệ điều hành sẽ tránh các Deadlock bằng cách duy trì lịch sử tài nguyên tối đa cần thiết cho một quá trình trước khi được thực thi. Đồng thời trạng thái của hệ thống cũng sẽ được kiểm tra để phân bổ tài nguyên cho các quy trình.

Trạng thái an toàn của hệ đệ điều hành có khả năng phân phối các tài nguyên cần thiết cho quá trình mà không gây ra tình trạng Deadlock. Còn trạng thái không an toàn là khi hệ điều hành không có khả năng đó.

Thuật toán đồ thị phân bổ tài nguyên (RAG)

RAG có thể dự đoán Deadlock trong một hệ điều hành bằng chế độ xem hình ảnh của các tài nguyên được phân bổ hoặc có sẵn. Bởi nếu tìm ra số lượng tài nguyên được phân bổ và cần thiết cho mỗi quá trình thì dễ dàng ngăn chặn tình trạng Deadlock xảy ra.

Giống với các đồ thị khác, RAG cũng được thiết kế bao gồm hai đỉnh dạng hình chữ nhật là quá trình và tài nguyên, còn hai cạnh dạng hình tròn là gán và yêu cầu.

Tuy nhiên, RAG chỉ thực sự hiệu quả khi các tài nguyên là cùng ở một phiên bản nhất định. Nếu có nhiều tài nguyên hơn RAG sẽ dễ dàng chuyển sang quá trình vòng tròn và dễ gây ra hiện tượng Deadlock. Vì vậy, có thể sử dụng thuật toán Banker để dự đoán trước Deadlock có thể xảy ra

Ví dụ: Dưới đây là hai quy trình P1, P2 và hai tài nguyên R1. R2.

Theo đồ thị, P1 có R1 và sẽ tiếp nhận R2 được biểu thị bởi đường gạch nối. Còn P2 đang yêu cầu R2 nhưng chưa được hệ điều hành phân bổ bởi R2 được trưng dụng cho P1. Quá trình này sẽ làm giảm hiện tượng Deadlock, tuy nhiên R2 sẽ không được sử dụng dẫn đến việc sử dụng ít tài nguyên hơn.

Thuật toán Banker

Thuật toán Banker còn được sử dụng trong trường hợp tài nguyên có nhiều phiên bản khác nhau cho phép quản lý các tài nguyên không rơi vào tình trạng Deadlock, hết hoặc không an toàn. Thuật toán này được các ngân hàng sử dụng để phân bổ và xử lý các tài khoản vay trong hệ thống của mình.

Thuật toán Banker sẽ tạo ra một chuỗi an toàn bằng cách sử dụng một số dữ liệu có sẵn như các tài nguyên tối đa được yêu cầu và tổng số tài nguyên có sẵn trong hệ điều hành.

Phát hiện và tránh Deadlock

Hệ điều hành sẽ thực hiện một thử nghiệm có Deadlock sắp xảy ra bằng cách sử dụng cơ chế phát hiện Deadlock trong một khoảng thời gian nhất định và thực hiện các cách khắc phục.

Có hai phương pháp phát hiện Deadlock của hệ điều hành:

Sử dụng một số ứng biến như sau.

Đồ thị trên có điểm giống với RAG, hệ điều hành đang tiến hành kiểm tra quá trình hình thành của vòng tuần hoàn hệ thống. Tuy nhiên, vẫn có một số điểm khác ở đồ thị RAG và Wait-for là số đỉnh chứa. Trong khi RAG có hai đỉnh là tài nguyên và quy trình thì Wait-for chỉ có một đỉnh là quá trình.

Sử dụng đồ thị Wait-for được tạo bởi RAG:

Biểu đồ Wait-for không tạo ra vòng tròn nên không xảy ra tình trạng Deadlock trên hệ thống.

Cách sử dụng thuật toán an toàn tương tự như Banker và phù hợp đối với tài nhiên nhiều phiên bản bao gồm ba ma trận chính là phân bổ, có sẵn và yêu cầu hiện tại.

Hệ điều hành bây giờ nếu phát hiện ra bất kỳ Deadlock nào, ngay lập tức sẽ thực hiện các thao tác phục hồi bằng hai cách:

Cách tiếp cận lạc quan

Cách tiếp cận lạc quan hiểu đơn giản đó là hệ điều hành sẽ ưu tiên chọn một số quy trình và hạn chế tài nguyên để tiến hành phân bổ vào các quy trình khác. Tuy nhiên, phương pháp này dễ gây ra hiện tượng không có sự trưng dụng hoặc bị thiếu hụt tài nguyên.

Cách tiếp cận quay trở lại trạng thái an toàn trước khi xảy ra bế tắc. Yêu cầu của phương pháp này đó là hệ điều hành cần có một số lịch sử trạng thái an toàn trước đó. Hạn chế duy nhất đó là không có tham số quyết định để chọn thứ tự lịch sử quy trình.

Cách tiếp cận bi quan

Cách tiếp cận này được thực hiện bằng cách xóa bỏ tất cả các quá trình xảy ra Deadlock để loại bỏ hoặc khởi động lại quy trình, đồng thời cũng gây khá nhiều tốn kém. Hoặc có thể lựa chọn huỷ bỏ một quá trình bị Deadlock đến khi thực sự loại bỏ chúng ra khỏi hệ thống.

Hệ điều hành ở cách tiếp cận này sẽ tiến hành việc loại bỏ quá trình thực hiện ít công việc nhất bằng cách chạy các thuật toán để phát hiện ra Deadlock và loại bỏ chúng.

Sự thiếu hiểu biết về Deadlock

Hệ điều hành sẽ sử dụng phương pháp không nhận biết về Deadlock để xử lý quá trình nhanh chóng hơn. Nếu có vấn đề lỗi nào xảy ra, hệ thống sẽ tự động được khởi động lại để làm mới quá trình. Đây là cách được sử dụng phổ biến trong Linux và hệ điều hành dựa trên Windows.

Tổng kết về Deadlock

Bài viết trên là những thông tin chi tiết về Deadlock và một vài ví dụ minh hoạ cho các hiện tượng xảy ra. Đồng thời, chúng tôi cũng giải thích cho bạn những nguyên lý vận hành để phòng tránh hoặc khắc phục Deadlock.

Nếu bạn có thắc mắc về Deadlock hoặc muốn tìm hiểu thêm những kiến thức khác về lĩnh vực công nghệ thông tin và xử lý dữ liệu, hãy để lại ở bên bình luận bên dưới, BKHOST sẽ trả lời bạn trong thời gian sớm nhất.

P/s: Bạn cũng có thể truy cập vào Blog của BKHOST để đọc thêm các bài viết chia sẻ kiến thức về lập trình, quản trị mạng, website, domain, hosting, vps, server, email,… Chúc bạn thành công.