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] Deadlock avoidance — đồ thị tài nguyên

    Deadlock Avoidance — phân tích đồ thị tài nguyên

    Cho hệ n tiến trình, r loại tài nguyên. Mỗi tiến trình đang giữ (Allocation) một số tài nguyên và còn cần thêm (Need/Request) một số tài nguyên để hoàn thành. Available là tài nguyên còn rảnh.

    Thuật toán an toàn (Banker)

    1. Work = Available, mọi Finish[i] = false, seq rỗng.
    2. Lặp: tìm tiến trình i chưa hoàn thành mà Need[i] ≤ Work (mọi loại). Duyệt theo chỉ số tăng để tie-break (chọn chỉ số nhỏ nhất thỏa). Nếu có: Work += Allocation[i], Finish[i] = true, thêm i vào seq.
    3. Lặp đến khi không tiến trình nào tiến triển.

    Nếu mọi tiến trình hoàn thành → in SAFE và chuỗi an toàn (chỉ số tiến trình). Ngược lại in UNSAFE.

    Ví dụ

    1 tiến trình, 1 loại tài nguyên, Available=[1], Alloc=[[0]], Need=[[1]]. Need[0]=1 ≤ Work=1 → chạy P0. SAFE, chuỗi 0.

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

      Dòng 1: n r. Dòng 2: r số Available. Tiếp n dòng: ma trận Allocation (r số mỗi dòng). Tiếp n dòng: ma trận Need (r số mỗi dòng).

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

      1 ≤ n ≤ 100; 1 ≤ r ≤ 20; mọi giá trị ≥ 0 và ≤ 10^4.

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

      Nếu an toàn: dòng 1 SAFE, dòng 2 chuỗi an toàn (chỉ số tiến trình cách nhau dấu cách). Ngược lại: UNSAFE.

    Ví dụ:

    Đầu vào:

    1 1
1
0
1

    Đầu ra:

    SAFE
0

    Giải thích:

    n=1,r=1. Available=[1], Alloc P0=[0], Need P0=[1]. Need ≤ Work=1 → chạy P0, Work=1. Tất cả hoàn thành → SAFE, chuỗi `0`.

    Đang tải editor...