Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Hệ điều hành] Phát hiện bế tắc nhiều thực thể

    Phát hiện bế tắc (Deadlock Detection) với nhiều thực thể (instances) cho mỗi loại tài nguyên. Cho:

    • Available[M]: tài nguyên còn rảnh.
    • Allocation[N][M]: đang cấp.
    • Request[N][M]: đang yêu cầu thêm.

    Thuật toán:

    1. Work = Available. Finish[i] = (Allocation[i] toàn 0) ? → đề này đặt Finish[i] = false cho mọi i ban đầu (xét cả tiến trình giữ tài nguyên). Chính xác: Finish[i] = false với mọi i.
    2. Lặp: tìm i có Finish[i]=false và Request[i] ≤ Work. Nếu nhiều, chọn ID nhỏ nhất.
    3. Nếu tìm được: Work += Allocation[i], Finish[i]=true. Lặp lại.
    4. Nếu không: dừng.

    Các tiến trình còn Finish[i]=false là đang bị bế tắc.

    In ra: dòng đầu là số tiến trình bị bế tắc; dòng hai là danh sách ID các tiến trình bế tắc (tăng dần, cách nhau dấu cách). Nếu không có, dòng hai để trống (in dòng rỗng).

    Ví dụ: hệ không bế tắc → in "0" rồi một dòng rỗng.

    • Định dạng đầu vào:

      Dòng đầu: N M. Tiếp theo M số Available. Tiếp theo N×M số Allocation. Tiếp theo N×M số Request.

    • Ràng buộc đầu vào:

      1 ≤ N ≤ 1000; 1 ≤ M ≤ 20; giá trị ≥ 0.

    • Định dạng đầu ra:

      Dòng 1: số tiến trình bị bế tắc. Dòng 2: danh sách ID bế tắc tăng dần (có thể là dòng rỗng).

    Ví dụ:

    Đầu vào:

    5 3
0 0 0
0 1 0 2 0 0 3 0 3 2 1 1 0 0 2
0 0 0 2 0 2 0 0 0 1 0 0 0 0 2

    Đầu ra:

    0

    Giải thích:

    Work=(0,0,0). P0 Request(0,0,0)≤Work -> Work+=Alloc0=(0,1,0). P2 Request(0,0,0)≤Work -> Work=(3,1,3). Lần lượt mọi tiến trình hoàn thành -> không bế tắc. In 0 và dòng rỗng.

    Đang tải editor...