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] Đếm page fault thuật toán FIFO

    Mô phỏng thuật toán thay trang FIFO (First-In First-Out) và đếm số lỗi trang (page fault).

    Bộ nhớ có cap khung trang (frame). Duyệt chuỗi tham chiếu trang. Với mỗi trang:

    • Nếu trang đã có trong khung → không lỗi (hit).
    • Nếu chưa có → page fault: nếu còn khung trống thì nạp; nếu đầy thì loại trang vào sớm nhất (FIFO) rồi nạp trang mới.

    Thuật toán: dùng một tập trang đang ở trong khung và một hàng đợi ghi thứ tự nạp. Mỗi page fault: nếu đầy, lấy đầu hàng đợi ra (loại), thêm trang mới vào cuối hàng đợi.

    Ví dụ: cap=3, chuỗi 7 0 1 2 0 3 0 4. Số page fault = 6.

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

      Dòng đầu: hai số cap m (số khung, độ dài chuỗi). Dòng sau: m số nguyên — chuỗi tham chiếu trang.

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

      1 ≤ cap ≤ 100; 1 ≤ m ≤ 100000; 0 ≤ số hiệu trang ≤ 1000000.

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

      Một số nguyên: tổng số page fault.

    Ví dụ:

    Đầu vào:

    3 8
7 0 1 2 0 3 0 4

    Đầu ra:

    7

    Giải thích:

    cap=3. 7→fault[7]. 0→fault[7,0]. 1→fault[7,0,1]. 2→fault, loại 7→[0,1,2]. 0→hit. 3→fault, loại 0→[1,2,3]. 0→fault, loại 1→[2,3,0]. 4→fault, loại 2→[3,0,4]. Tổng fault=6.

    Đang tải editor...