Quartz 🪬

Deadlock Handling

4 min read

Các cách giải quyết deadlock:

  1. Ngăn hoặc tránh deadlock.
  2. Cho phép xảy ra deadlock nhưng sau đó phát hiện deadlock và phục hồi hệ thống để thoát ra khỏi deadlock.
  3. Xem như deadlock không tồn tại:
    • Nếu có deadlock xảy ra thì có thể giảm hiệu suất của hệ điều hành.
    • Có thể khiến hệ thống ngưng hoạt động và khởi động lại.

Deadlock Prevention

Chúng ta ngăn deadlock bằng cách đảm bảo ít nhất 1 trong 4 điều kiện cần của nó không xảy ra.

Prevent Mutual Exclusion

Ngăn mutual exclusion bằng hai cách sau:

  • Đối với tài nguyên không thể chia sẻ (chẳng hạn như máy in): không thể thực hiện. Ví dụ: tiến trình in tài liệu cần phải được hoàn thành thì tài nguyên của nó mới được hoàn trả.
  • Đối với tài nguyên có thể chia sẻ (chẳng hạn như tập tin read-only): không cần thiết.

Prevent No Preemption

Cho phép lấy lại tài nguyên đã cấp phát cho tiến trình.

  • Timeout prevention: đặt ra một thời gian timeout. Khi hết thời gian này, tài nguyên của tiến trình sẽ bị thu hồi.

Prevent Hold and Wait

Ngăn hold and wait bằng hai cách sau:

  1. Mỗi tiến trình yêu cầu tất cả các tài nguyên mà nó cần một lần duy nhất. Nếu có đủ tài nguyên thì hệ thống sẽ cấp phát và sẽ được thực thi, nếu không đủ tài nguyên thì tiến trình sẽ bị blocked.
  2. Tiến trình phải trả lại tài nguyên mà nó đang giữ khi yêu cầu thêm tài nguyên mới.

Khuyết điểm của hai cách trên:

  • Hiệu suất sử dụng tài nguyên thấp.
  • Tiến trình có thể bị starvation.

Prevent Circular Wait

Ngăn circular wait bằng cách gán cho mỗi tài nguyên một số thứ tự nào đó. Chẳng hạn như:

  • Băng từ là 1
  • Đĩa cứng là 5
  • Máy in là 12

Sử dụng các cách sau:

  1. Tiến trình chỉ có thể được cấp phát các tài nguyên theo thứ tự tăng dần. Ví dụ, nếu tiến trình được cấp phát quyền sử dụng máy in (12) thì nó sẽ không thể sử dụng băng từ (1) hay đĩa cứng (5) được nữa.
  2. Tiến trình cần phải trả lại các tài nguyên có thứ tự lớn hơn tài nguyên mà nó yêu cầu. Ví dụ nếu tiến trình đang giữ tài nguyên là máy in (12) và yêu cầu sử dụng đĩa cứng (5) thì nó cần phải trả lại quyền sử dụng máy in.

Deadlock Avoidance

Các tiến trình cần cung cấp thông tin về tài nguyên tối đa mà nó cần để hệ thống cấp phát tài nguyên một cách thích hợp. Cách làm này đảm bảo hiệu suất sử dụng tài nguyên cao hơn deadlock prevention.

Resource Allocation State

Hệ điều hành sẽ điều khiển trạng thái cấp phát tài nguyên để đảm bảo hệ thống không rơi vào deadlock. Có hai trạng thái:

  • Safe: nếu tồn tại một chuỗi an toàn (safe sequence).
  • Unsafe: nếu không tồn tại một chuỗi an toàn

Một chuỗi các tiến trình được gọi là một chuỗi an toàn nếu với mọi yêu cầu tài nguyên tối đa của tiến trình được thỏa bởi:

  • Tài nguyên mà hệ thống đang khả dụng (available).
  • Tài nguyên mà tất cả các tiến trình (j < i) đang giữ.

Nếu tiến trình yêu cầu tài nguyên đang khả dụng và việc cấp phát không dẫn đến trạng thái unsafe thì hệ điều hành sẽ cấp phát ngay.

Algorithms

Để tránh deadlock thì ta có thể dùng Banker’s algorithm.

Deadlock Detection and Recovery

Để phát hiện deadlock thì có thể dùng wait-for graph hoặc resource allocation graph (xem thêm Deadlock Detection).

Các giải pháp phục hồi deadlock:

  • Báo cho người vận hành hệ thống để xử lý.
  • Phá deadlock bằng các cách sau:
    • Chấm dứt tất cả các tiến trình bị deadlock. Một số tiêu chí để chọn tiến trình cần được chấm dứt:
      • Độ ưu tiên tiến trình.
      • Thời gian đã thực thi và thời gian còn lại.
      • Loại tài nguyên đã sử dụng.
      • Tài nguyên mà tiến trình cần để thực thi.
    • Lấy lại tài nguyên. Lưu ý:
      • Cần lưu lại trạng thái của tiến trình bị thu hồi tài nguyên để chạy tiếp khi cần.
      • Để tránh starvation, phải đảm bảo không có tiến trình nào mà luôn bị lấy lại tài nguyên khi có deadlock xảy ra.

Resources

Backlinks