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] Banker nhiều loại tài nguyên — chuỗi an toàn

    Thuật toán Banker với M loại tài nguyên và N tiến trình. Cho:

    • Vector Available[M]: số tài nguyên còn rảnh mỗi loại.
    • Ma trận Max[N][M]: nhu cầu tối đa.
    • Ma trận Allocation[N][M]: đang được cấp.

    Need[i][j] = Max[i][j] − Allocation[i][j].

    Thuật toán tìm chuỗi an toàn:

    1. Work = Available; Finish[i] = false cho mọi i.
    2. Lặp: tìm tiến trình i có Finish[i] = false và Need[i] ≤ Work (mọi loại). Nếu nhiều tiến trình thoả, chọn ID nhỏ nhất.
    3. Nếu tìm được: Work += Allocation[i], Finish[i] = true, thêm i vào chuỗi. Lặp lại.
    4. Nếu không còn tiến trình nào thoả: dừng.

    Nếu tất cả Finish = true → trạng thái an toàn, in chuỗi an toàn (các ID cách nhau dấu cách). Ngược lại in UNSAFE.

    Lưu ý: do luôn chọn ID nhỏ nhất thoả mãn ở mỗi bước, chuỗi an toàn là duy nhất và xác định.

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

      Dòng đầu: N M. Tiếp theo M số là Available. Tiếp theo N×M số là ma trận Max (theo hàng). Tiếp theo N×M số là ma trận Allocation. Dữ liệu có thể trải nhiều dòng.

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

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

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

      Chuỗi an toàn (các ID tiến trình từ 0, cách nhau dấu cách), hoặc UNSAFE.

    Ví dụ:

    Đầu vào:

    5 3
3 3 2
7 5 3 3 2 2 9 0 2 2 2 2 4 3 3
0 1 0 2 0 0 3 0 2 2 1 1 0 0 2

    Đầu ra:

    1 3 0 2 4

    Giải thích:

    Need = Max-Alloc. Bắt đầu Work=(3,3,2). P1 có Need(1,2,2)≤Work nên chạy đầu (ID nhỏ nhất thoả). Chọn ID nhỏ nhất ở mỗi bước được chuỗi 1 3 0 2 4 → an toàn.

    Đang tải editor...