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] Copy-on-write — đếm số bản sao

    Copy-on-Write — đếm số bản sao trang

    Copy-on-write (COW): khi fork, tiến trình con chia sẻ cùng các trang vật lý với cha (chỉ tăng refcount). Chỉ khi một tiến trình ghi vào trang đang chia sẻ (refcount > 1) thì mới tạo bản sao riêng.

    Thuật toán

    • Khởi tạo: cha (tiến trình 0) có npages trang vật lý đánh số 0..npages-1, mỗi trang refcount = 1. Số trang vật lý kế tiếp next_phys = npages.
    • FORK parent child: con sao chép mapping (cùng các trang vật lý), mỗi trang được tăng refcount.
    • WRITE proc vpage: lấy trang vật lý phys mà proc ánh xạ ở trang ảo vpage. Nếu refcount[phys] > 1 → COW: giảm refcount trang cũ, cấp trang vật lý mới next_phys (refcount 1), trỏ mapping của proc sang đó, next_phys += 1, tăng cow_copies. Nếu refcount == 1 → ghi trực tiếp, không sao chép.

    In: số bản sao COW, tổng số trang vật lý đã cấp (next_phys), số trang vật lý còn chia sẻ (refcount > 1).

    Ví dụ

    npages=1. FORK 0 1 → trang 0 refcount=2. WRITE 1 0: refcount>1 → tạo bản sao (trang vật lý 1). cow_copies=1, next_phys=2, không còn trang shared → 0.

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

      Dòng 1: npages. Dòng 2: m. Tiếp m thao tác: FORK parent child hoặc WRITE proc vpage.

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

      1 ≤ npages ≤ 1000; 1 ≤ m ≤ 5000; chỉ số tiến trình/trang ảo hợp lệ.

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

      Dòng 1: số bản sao COW. Dòng 2: tổng số trang vật lý đã cấp. Dòng 3: số trang vật lý còn chia sẻ.

    Ví dụ:

    Đầu vào:

    1
2
FORK 0 1
WRITE 1 0

    Đầu ra:

    1
2
0

    Giải thích:

    npages=1, trang 0 refcount=1. FORK 0 1: con 1 chia sẻ trang 0 → refcount=2. WRITE 1 0: refcount>1 → COW tạo trang vật lý 1. cow_copies=1, next_phys=2, không trang nào còn refcount>1 → shared=0.

    Đang tải editor...