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] Log-structured FS — block log/live/garbage

    Log-structured File System — đếm block log/live/garbage

    Log-structured file system (LFS) ghi mọi cập nhật nối tiếp vào cuối log (mỗi lần ghi tạo một block mới ở cuối). Khi một tệp được ghi lại, block phiên bản cũ trở thành rác (garbage) chờ thu gom.

    Thuật toán

    • log_end = vị trí ghi tiếp theo (ban đầu 0). location[fid] = block hiện tại của tệp.
    • WRITE fid: nếu tệp fid đã có block cũ → block cũ thành rác (garbage += 1). Ghi block mới tại log_end, cập nhật location[fid] = log_end, log_end += 1.
    • READ fid: không thay đổi trạng thái.

    Sau m thao tác, in: tổng số block đã ghi vào log (log_end), số block còn sống (số tệp khác nhau đang có block), số block rác.

    Ví dụ

    Thao tác WRITE 1, WRITE 1. WRITE 1 đầu: ghi block 0, log_end=1. WRITE 1 lần hai: block 0 thành rác, ghi block 1, log_end=2. In 2 (log), 1 (live), 1 (garbage).

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

      Dòng 1: m. Tiếp m thao tác: WRITE fid hoặc READ fid.

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

      1 ≤ m ≤ 10^4; 0 ≤ fid ≤ 10^5.

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

      Dòng 1: tổng số block đã ghi (chiều dài log). Dòng 2: số block còn sống. Dòng 3: số block rác.

    Ví dụ:

    Đầu vào:

    2
WRITE 1
WRITE 1

    Đầu ra:

    2
1
1

    Giải thích:

    WRITE 1: ghi block 0, log_end=1. WRITE 1 lần hai: block 0 cũ thành rác (garbage=1), ghi block 1, log_end=2. live=1 (chỉ tệp 1). In 2 / 1 / 1.

    Đang tải editor...