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] NRU — phân lớp R/M đếm page fault

    NRU (Not Recently Used) — đếm page fault

    NRU phân loại trang theo hai bit: R (referenced) và M (modified). Mỗi tham chiếu là đọc (R) hoặc ghi (W). Khi cần thay trang, chọn trang có lớp nhỏ nhất, với class = 2*R + M (lớp 0 = không R, không M là ưu tiên loại nhất).

    Thuật toán

    • f frame. Mỗi trang giữ [R, M].
    • Với thao tác thứ i (page, typ):
      1. Nếu page đã có trong frame: đặt R=1; nếu typ='W' đặt M=1.
      2. Nếu chưa có → fault. Còn chỗ trống: nạp với R=1, M=1 nếu ghi (ngược lại 0). Nếu đầy: chọn nạn nhân là trang có class = 2R+M nhỏ nhất; nếu bằng nhau chọn trang nạp sớm nhất. Thay bằng trang mới.
      3. Sau mỗi clear thao tác (i+1 chia hết cho clear): xóa bit R của mọi trang (mô phỏng ngắt định kỳ).

    In tổng số page fault.

    Ví dụ

    f=1, các thao tác (1,R) (2,R), clear=10. Nạp 1 (fault). Nạp 2: frame đầy, loại 1 (fault). Tổng 2.

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

      Dòng 1: f. Dòng 2: m. m dòng: page type với type ∈ {R, W}. Dòng cuối: clear — chu kỳ xóa bit R.

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

      1 ≤ f ≤ 100; 1 ≤ m ≤ 5000; 1 ≤ clear ≤ 1000; 0 ≤ page ≤ 10^5.

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

      Tổng số page fault.

    Ví dụ:

    Đầu vào:

    1
2
1 R
2 R
10

    Đầu ra:

    2

    Giải thích:

    f=1. Thao tác 1 (1,R): fault, nạp 1. Thao tác 2 (2,R): frame đầy, loại 1, nạp 2 (fault). clear=10 chưa kích hoạt. Tổng 2 fault.

    Đang tải editor...