Bảng trang nghịch đảo (Inverted Page Table - IPT) có một mục cho mỗi khung trang vật lý. Mục thứ f (frame f) chứa cặp (pid, page) nghĩa là khung f đang giữ trang page của tiến trình pid.
Cho IPT gồm F mục (frame 0..F−1) và Q truy vấn. Mỗi truy vấn gồm (pid, page): hãy tra trong IPT xem trang đó nằm ở khung nào.
pid và page cho ra số khung.Kích thước trang là 2^P byte. Nếu tìm thấy khung f, địa chỉ vật lý của offset o trong trang là f · 2^P + o. Để đơn giản, mỗi truy vấn lấy offset = 0, nên địa chỉ vật lý = f · 2^P (hoặc -1 nếu không thấy).
In ra Q dòng, mỗi dòng là số khung tìm được (hoặc -1).
Ví dụ: IPT 3 khung: f0=(1,5), f1=(2,3), f2=(1,9). Truy vấn (1,9)->khung 2. (2,3)->khung 1. (3,0)->-1.
Dòng đầu: F P (số khung, số bit offset). Tiếp theo F cặp (pid page) cho các khung 0..F−1. Tiếp theo Q (số truy vấn). Tiếp theo Q cặp (pid page).
1 ≤ F ≤ 100000; 1 ≤ Q ≤ 100000; 0 ≤ pid, page; 0 ≤ P ≤ 40.
Q dòng, mỗi dòng là số khung tìm được hoặc -1.
Ví dụ:
Đầu vào:
3 12
1 5 2 3 1 9
3
1 9 2 3 3 0
Đầu ra:
2
1
-1
Giải thích:
Đang tải editor...