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 từ ma trận

    Cài đặt thuật toán phát hiện bế tắc (deadlock detection).

    Cho n tiến trình, m loại tài nguyên, ma trận Allocation, ma trận Request (yêu cầu hiện tại) và vector Available.

    Thuật toán:

    1. Work = Available. Finish[i] = true nếu Allocation[i] toàn 0 (tiến trình không giữ gì), ngược lại false.
    2. Lặp: tìm i nhỏ nhất có Finish[i] = false và Request[i] ≤ Work. Nếu có: Work += Allocation[i], Finish[i] = true, lặp lại.
    3. Khi không tìm được nữa: các tiến trình có Finish[i] = false đang bế tắc.

    In danh sách ID tiến trình bế tắc (tăng dần, cách nhau dấu cách). Nếu không có → in NO DEADLOCK.

    Ví dụ: n=3,m=1, Alloc [1],[1],[0], Request [0],[1],[1], Avail [0] → NO DEADLOCK.

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

      Dòng 1: n m. n dòng Allocation, n dòng Request, dòng cuối m số Available.

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

      1 ≤ n ≤ 200; 1 ≤ m ≤ 50; 0 ≤ giá trị ≤ 100000.

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

      Danh sách ID bế tắc tăng dần (cách nhau dấu cách) hoặc NO DEADLOCK.

    Ví dụ:

    Đầu vào:

    3 1
1
1
0
0
1
1
0

    Đầu ra:

    NO DEADLOCK

    Giải thích:

    Avail=[0]. Alloc P2 toàn 0 → Finish[2]=true. P0 Request[0]≤0 → Work=[1], Finish[0]=true. P1 Request[1]≤1 → Work=[2], Finish[1]=true. Mọi Finish=true → NO DEADLOCK.

    Đang tải editor...