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 LRU

    Mô phỏng thuật toán thay trang LRU (Least Recently Used) và đếm số page fault.

    Khi cần loại trang (khung đầy và xảy ra fault), loại trang lâu nhất chưa được sử dụng. Mỗi lần truy cập một trang (kể cả hit) thì trang đó trở thành "vừa dùng gần nhất".

    Thuật toán: giữ danh sách thứ tự sử dụng, phần tử cuối là trang mới dùng nhất, đầu là ít dùng gần đây nhất.

    • Hit: bỏ trang khỏi vị trí cũ, đưa về cuối.
    • Fault: nếu đầy, loại phần tử đầu; thêm trang mới vào cuối.

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

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

      Dòng đầu: cap m. Dòng sau: m số — chuỗi tham chiếu trang.

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

      1 ≤ cap ≤ 100; 1 ≤ m ≤ 100000; 0 ≤ trang ≤ 1000000.

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

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

    Ví dụ:

    Đầu vào:

    3 8
7 0 1 2 0 3 0 4

    Đầu ra:

    6

    Giải thích:

    cap=3. 7,0,1 fault →[7,0,1]. 2 fault loại 7(ít dùng nhất)→[0,1,2]. 0 hit→[1,2,0]. 3 fault loại 1→[2,0,3]. 0 hit→[2,3,0]. 4 fault loại 2→[3,0,4]. Tổng fault=6.

    Đang tải editor...