Livelock: Là gì, Ví dụ, Sự khác biệt với Deadlock

Livelock là gì?

A livelock là tình huống trong đó yêu cầu về một khóa độc quyền bị từ chối nhiều lần vì nhiều khóa chia sẻ chồng chéo tiếp tục can thiệp lẫn nhau. Các quy trình liên tục thay đổi trạng thái, điều này càng ngăn cản chúng hoàn thành nhiệm vụ. Điều này càng ngăn cản họ hoàn thành nhiệm vụ.

Ví dụ về Livelock

Ví dụ 1:

Một ví dụ dễ hiểu nhất về Livelock là hai người gặp mặt nhau ở một hành lang và cả hai đều tránh sang một bên để người kia đi qua. Cuối cùng, họ di chuyển từ bên này sang bên kia mà không đạt được bất kỳ tiến triển nào khi họ di chuyển theo cùng một cách vào thời điểm đó. Ở đây, họ không bao giờ vượt qua nhau.

Ví dụ 2:

Bạn có thể thấy trong hình trên, mỗi quy trình trong số hai quy trình nhất định cần hai tài nguyên và chúng sử dụng sổ đăng ký nhập phiếu thăm dò nguyên thủy để cố gắng lấy được các khóa cần thiết cho chúng. Nếu nỗ lực thất bại, phương pháp sẽ hoạt động trở lại.

Quy trình A giữ tài nguyên Y
Tiến trình B giữ tài nguyên X
Quy trình A yêu cầu tài nguyên X
Quy trình B yêu cầu tài nguyên Y

Giả sử, quy trình A chạy trước và lấy tài nguyên dữ liệu X, sau đó quy trình B chạy và lấy tài nguyên Y, bất kể quy trình nào chạy trước, không có quy trình nào tiến triển thêm.

Tuy nhiên, cả hai quá trình đều không bị chặn. Chúng sử dụng hết tài nguyên CPU nhiều lần mà không đạt được bất kỳ tiến triển nào nhưng cũng dừng bất kỳ khối xử lý nào.

Vì vậy, tình trạng này không phải là một bế tắc bởi vì không có một tiến trình nào bị chặn mà chúng ta phải đối mặt với tình huống tương đương với bế tắc, đó là LIVELOCK.

Điều gì dẫn đến Livelock?

Livelock xảy ra khi tổng số quy trình được phép trong một hệ thống cụ thể phải được xác định bằng tổng số mục trong bảng quy trình. Do đó, các khe bảng quy trình nên được gọi là Tài nguyên hữu hạn.

Bế tắc là gì?

Bế tắc là tình huống xảy ra trong hệ điều hành khi bất kỳ tiến trình nào đi vào trạng thái chờ vì một tiến trình chờ khác đang giữ tài nguyên được yêu cầu. Bế tắc là một vấn đề phổ biến trong xử lý đa luồng, trong đó một số tiến trình chia sẻ một loại tài nguyên loại trừ lẫn nhau cụ thể được gọi là khóa mềm hoặc phần mềm.

Ví dụ về bế tắc

Một ví dụ thực tế là giao thông chỉ đi theo một hướng.
Ở đây, một cây cầu được coi là một nguồn tài nguyên.
Vì vậy, khi Deadlock xảy ra, có thể dễ dàng giải quyết nếu một xe lùi lại (Ngăn chặn tài nguyên và khôi phục).
Có thể phải có nhiều xe phải lùi lại nếu xảy ra tình trạng kẹt xe.
Vì vậy, nạn đói là có thể.

Đói là gì?

Đói là tình huống trong đó tất cả các quy trình có mức độ ưu tiên thấp bị chặn và các quy trình có mức độ ưu tiên cao vẫn tiếp tục. Trong bất kỳ hệ thống nào, các yêu cầu về tài nguyên có mức độ ưu tiên cao/thấp luôn diễn ra linh hoạt. Qua đó, cần có một số chính sách để quyết định ai sẽ được hỗ trợ khi nào.

Sử dụng một số thuật toán, một số tiến trình có thể không nhận được dịch vụ mong muốn mặc dù chúng không bị bế tắc. Starvation xảy ra khi một số luồng khiến tài nguyên được chia sẻ không khả dụng trong thời gian dài.

Ví dụ về nạn đói

Ví dụ, một đối tượng cung cấp một phương thức đồng bộ có khả năng mất nhiều thời gian để trả về. Nếu một luồng sử dụng phương thức này thường xuyên, các luồng khác cũng cần truy cập đồng bộ thường xuyên vào cùng một đối tượng thường sẽ bị chặn.

Sự khác biệt giữa Deadlock, Starvation và Livelock

Bế tắc là tình huống xảy ra trong hệ điều hành khi bất kỳ tiến trình nào chuyển sang trạng thái chờ vì tài nguyên được yêu cầu đang bị một tiến trình chờ khác giữ.
Ngược lại, livelock gần giống với deadlock, ngoại trừ việc trạng thái của các tiến trình liên quan đến livelock luôn thay đổi lẫn nhau, không có tiến trình nào tiến triển.
Vì vậy, Livelock là một trường hợp duy nhất về tình trạng thiếu tài nguyên.

Tổng kết

Định nghĩa: Livelock là tình huống trong đó yêu cầu về một khóa độc quyền bị từ chối liên tục vì nhiều khóa dùng chung chồng chéo tiếp tục can thiệp lẫn nhau.
Livelock xảy ra khi tổng số quy trình được phép trong một hệ thống cụ thể phải được xác định bằng tổng số mục trong bảng quy trình
Bế tắc là tình huống xảy ra trong hệ điều hành khi bất kỳ tiến trình nào chuyển sang trạng thái chờ vì có một tiến trình chờ khác đang giữ tài nguyên được yêu cầu.
Một ví dụ thực tế là giao thông chỉ đi theo một hướng.
Một ví dụ về Livelock là hai người gặp mặt nhau ở một hành lang và cả hai đều tránh sang một bên để người kia đi qua.
Đói là tình huống trong đó tất cả các quy trình có mức độ ưu tiên thấp bị chặn và các quy trình có mức độ ưu tiên cao vẫn tiếp tục.