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] ARC — đếm page fault

    ARC (Adaptive Replacement Cache) — đếm page fault

    ARC kết hợp recency (gần đây) và frequency (tần suất) bằng hai danh sách trong cache T1, T2 và hai danh sách ghost B1, B2 (chỉ lưu lịch sử, không lưu trang). Tham số thích nghi p là kích thước mục tiêu của T1. Tổng |T1|+|T2| ≤ c.

    Quy tắc xử lý mỗi tham chiếu x

    1. x ∈ T1: hit → chuyển x xuống cuối T2.
    2. x ∈ T2: hit → đưa x xuống cuối T2.
    3. x ∈ B1 (ghost recency): fault → tăng p (ưu tiên recency), thay trang, đưa x vào T2.
    4. x ∈ B2 (ghost frequency): fault → giảm p, thay trang, đưa x vào T2.
    5. x hoàn toàn mới: fault → có thể loại bỏ ghost cũ, thay trang nếu cache đầy, đưa x vào T1.

    Việc thay trang (replace) chọn nạn nhân từ T1 hay T2 tùy |T1| so với p. In tổng số page fault. (Tuân theo đúng pseudo-code mô tả trong đề; mọi bước xác định.)

    Ví dụ

    c=2, chuỗi 1 2 3 1: nạp 1 (fault), 2 (fault), 3 đẩy 1 ra (fault), 1 quay lại — vì 1 còn trong ghost B1 nên vẫn fault. Tổng 4 page fault.

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

      Dòng 1: c — dung lượng cache (số frame). Dòng 2: m — số tham chiếu. Dòng 3: m số hiệu trang.

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

      1 ≤ c ≤ 100; 1 ≤ m ≤ 10^4; 0 ≤ số_trang ≤ 10^5.

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

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

    Ví dụ:

    Đầu vào:

    2
4
1 2 3 1

    Đầu ra:

    4

    Giải thích:

    Cache 2 frame. Nạp 1,2 (2 fault). Nạp 3 đẩy 1 ra T1 (fault). Tham chiếu 1 lại: 1 nằm trong ghost B1 → fault. Tổng 4.

    Đang tải editor...