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's algorithm - kiểm tra trạng thái an toàn

    Cài đặt phần kiểm tra an toàn của thuật toán Banker để xác định trạng thái hệ thống có an toàn (SAFE) hay không.

    Có n tiến trình và m loại tài nguyên. Cho ma trận Allocation (đang giữ), Max (nhu cầu tối đa) và vector Available (còn rảnh). Tính Need = Max − Allocation.

    Thuật toán an toàn:

    1. Work = Available; Finish[i] = false mọi i.
    2. Lặp: tìm tiến trình i có Finish[i] = false và Need[i] ≤ Work (theo từng tài nguyên). Để output xác định, chọn i nhỏ nhất thoả mãn.
    3. Nếu tìm được: Work += Allocation[i], Finish[i] = true, lặp lại bước 2.
    4. Nếu không tìm được nữa: nếu mọi Finish[i] = true → SAFE, ngược lại UNSAFE.

    Ví dụ: n=5, m=3, dữ liệu kinh điển → in SAFE.

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

      Dòng 1: n m. Tiếp theo n dòng ma trận Allocation (mỗi dòng m số). Tiếp n dòng ma trận Max. Dòng cuối: m số Available. (Đọc theo token.)

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

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

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

      Một chuỗi: SAFE hoặc UNSAFE.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    SAFE

    Giải thích:

    Need = Max-Alloc. Available=[3,3,2]. P1 Need=[1,2,2]≤[3,3,2]→chạy, Work=[5,3,2]. P3 Need=[0,1,1]≤Work→Work=[7,4,3]. P0 Need=[7,4,3]≤Work→Work=[7,5,3]. P2 Need=[6,0,0]≤Work→Work=[10,5,5]. P4 Need=[4,3,1]≤Work→xong. Mọi Finish=true → SAFE.

    Đang tải editor...