CF 103192B - 页面置换

Rating: -
Tags: -
Solve time: 1m 2s
Verified: yes

Solution

Problem Understanding

The task models a classic page replacement scenario from operating systems. We are given a sequence of page requests, where each request asks for a page from a fixed universe of pages. Memory has limited capacity, so it can only hold a small number of pages at once. Whenever a requested page is not currently in memory, a page fault occurs, and if memory is full, one existing page must be evicted to make room.

We simulate three different eviction policies over the same request sequence: FIFO removes the page that has been in memory the longest, LRU removes the page that has not been used for the longest time, and OPT removes the page whose next usage is farthest in the future or that is never used again. For each policy, we count how many page faults occur. The output requires us to report which policy achieves the minimum number of faults, and also output that minimum value. If multiple policies tie, any one of them may be printed.

The input size constraints are large enough that a naive simulation per eviction choice must be carefully implemented. The request length can reach up to one hundred thousand, while the number of distinct pages is small enough to allow direct simulation with auxiliary data structures. This combination strongly suggests that each algorithm must be implemented in near linear time per policy, avoiding any repeated full scans of memory state.

A subtle pitfall is in OPT simulation. A naive approach that, at every miss, scans forward to find next uses of all pages in memory would degrade to cubic behavior in the worst case. Another common mistake is forgetting that a page may never be used again, which should make it the best eviction candidate immediately.

Edge cases include sequences where all requests are identical, where memory size is one, and where all pages are distinct so every access is a fault. In these cases, FIFO, LRU, and OPT behave differently in predictable ways, and incorrect handling of "not found again" or incorrect timestamp updates will produce wrong comparisons.

Approaches

A direct simulation of each policy is conceptually straightforward. We maintain a list or set representing current memory content and process requests one by one. On a hit, we update metadata depending on the policy. On a miss, we increment the fault counter and either insert the page if space exists or evict a page according to the rule.

FIFO is the simplest: we maintain a queue of pages in insertion order. Each miss inserts the new page at the back. If memory is full, we remove from the front. This works because FIFO depends only on arrival time and does not require tracking usage patterns beyond insertion order.

LRU extends this idea by tracking last access time for each page. On every access, we update its timestamp. When eviction is needed, we choose the page with the smallest last access time. A naive search over all pages in memory is already fast enough because memory size k is at most 100, so scanning k elements per miss is acceptable.

OPT is the only algorithm requiring future knowledge. For each page currently in memory, we need to know when it will be used next. A naive recomputation that scans forward in the request list for each page at each eviction would be too slow. The key observation is that we can precompute, for each position in the sequence, the next occurrence of each page using a backward sweep or by maintaining next-use pointers. Then each eviction can be decided by comparing precomputed next-use indices in O(k).

Once all three counters are computed, the answer is simply the minimum among them.

Approach	Time Complexity	Space Complexity	Verdict
FIFO Simulation	O(n)	O(m + k)	Accepted
LRU Simulation	O(nk)	O(m + k)	Accepted
OPT with next-use preprocessing	O(nk)	O(n + m)	Accepted

Algorithm Walkthrough

We compute FIFO, LRU, and OPT independently on the same request sequence.

FIFO simulation

Initialize an empty queue and a set for membership tracking.
For each request, if the page is already in the set, do nothing except continue.
If it is not in the set and there is remaining space, insert it into the queue and set.
If it is not in the set and memory is full, remove the front of the queue and also remove it from the set, then insert the new page.

The reason this works is that FIFO’s decision depends only on arrival order, so the queue invariant directly represents eviction priority.

LRU simulation

Maintain a dictionary storing last access time for each page currently in memory.
For each request, if it is already in memory, update its last access time to the current index.
If it is not in memory and there is space, insert it with its current index.
If it is not in memory and memory is full, scan all pages in memory to find the smallest last access time and evict it, then insert the new page.

The correctness comes from the fact that the smallest timestamp always corresponds to the least recently used page under the global sequence order.

OPT simulation

Precompute an array next_pos[i] meaning the next index where page at position i will appear again, or infinity if it never appears again.
Maintain a set of pages currently in memory.
Maintain for each page its next occurrence index.
For each request, update or assign its next occurrence using the precomputed table.
On miss, if memory is full, iterate over pages in memory and choose the one with largest next occurrence index.

The key idea is that future knowledge is reduced to a single precomputed value per position, so each eviction is a local maximum query over k values.

Why it works

At any point in time, FIFO ranks pages by insertion order, LRU ranks pages by last access time, and OPT ranks pages by next use position. Each algorithm maintains a consistent ordering criterion that does not depend on future updates except OPT, which is resolved by preprocessing. The eviction decision is always selecting the extremum under the policy-defined ordering, so the simulated state remains equivalent to the theoretical definition of each policy.

Python Solution

import sys
input = sys.stdin.readline

INF = 10**18

def simulate_fifo(req, k):
    from collections import deque
    q = deque()
    s = set()
    faults = 0

    for x in req:
        if x in s:
            continue
        faults += 1
        if len(s) < k:
            s.add(x)
            q.append(x)
        else:
            old = q.popleft()
            s.remove(old)
            s.add(x)
            q.append(x)

    return faults

def simulate_lru(req, k):
    mem = {}
    faults = 0

    for i, x in enumerate(req):
        if x in mem:
            mem[x] = i
        else:
            faults += 1
            if len(mem) < k:
                mem[x] = i
            else:
                victim = min(mem, key=mem.get)
                del mem[victim]
                mem[x] = i

    return faults

def simulate_opt(req, k):
    n = len(req)
    nxt = [n] * n
    last = {}
    for i in range(n - 1, -1, -1):
        x = req[i]
        nxt[i] = last.get(x, n)
        last[x] = i

    mem_next = {}
    faults = 0

    for i, x in enumerate(req):
        if x in mem_next:
            mem_next[x] = nxt[i]
        else:
            faults += 1
            if len(mem_next) < k:
                mem_next[x] = nxt[i]
            else:
                victim = max(mem_next, key=mem_next.get)
                del mem_next[victim]
                mem_next[x] = nxt[i]

    return faults

def main():
    n, m, k = map(int, input().split())
    req = list(map(int, input().split()))

    fifo = simulate_fifo(req, k)
    lru = simulate_lru(req, k)
    opt = simulate_opt(req, k)

    best = min(fifo, lru, opt)

    if best == fifo:
        print("FIFO")
    elif best == lru:
        print("LRU")
    else:
        print("OPT")

    print(best)

if __name__ == "__main__":
    main()

The FIFO part relies on a queue paired with a set so membership checks remain constant time. The LRU part uses a dictionary keyed by page value with timestamps as values, which is sufficient because the memory size is small, so finding a minimum remains efficient.

The OPT implementation is driven by a preprocessing pass that computes next occurrence positions in reverse. This transforms the otherwise expensive “scan forward” operation into a constant-time lookup per request.

Worked Examples

Consider a small sequence where memory size is two and requests are 1 2 3 1 2.

FIFO trace

Step	Request	Memory	Evicted	Faults
1	1	[1]	-	1
2	2	[1,2]	-	2
3	3	[2,3]	1	3
4	1	[3,1]	2	4
5	2	[1,2]	3	5

The FIFO behavior cycles through pages strictly by arrival order, ignoring reuse patterns.

LRU trace

Step	Request	Memory (last used)	Evicted	Faults
1	1	{1:1}	-	1
2	2	{1:1,2:2}	-	2
3	3	{2:2,3:3}	1	3
4	1	{3:3,1:4}	2	4
5	2	{1:4,2:5}	3	5

LRU prefers evicting the page that has not been used for the longest time, which matches timestamp ordering.

OPT trace

Step	Request	Next uses	Memory	Evicted	Faults
1	1	future at 4	[1]	-	1
2	2	future at 5	[1,2]	-	2
3	3	never	[1,3]	2	3
4	1	done	[1,3]	-	3
5	2	never	[2,3]	1	4

OPT consistently avoids evicting pages that will be needed soon, instead discarding those with no future use or farthest reuse.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nk)	Each of FIFO, LRU, OPT scans at most k pages per miss, and k ≤ 100 makes this feasible
Space	O(n + m)	OPT preprocessing stores next-use information and all simulations track current memory state

The constraints guarantee that even triple simulation remains fast enough. The memory size bound k is the key factor that allows simple implementations without advanced data structures.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from solution import main  # assume refactor
    return sys.stdout.getvalue().strip()

# minimal case
assert run("1 1 1\n1\n") == "FIFO\n1"

# all distinct, k=1
assert run("5 5 1\n1 2 3 4 5\n") in ["FIFO\n5", "LRU\n5", "OPT\n5"]

# repeated single page
assert run("5 2 2\n1 1 1 1 1\n") in ["FIFO\n0", "LRU\n0", "OPT\n0"]

# sample-like case
assert run("12 8 4\n6 2 4 1 4 6 3 8 4 5 7 3\n") in [
    "FIFO\n?\n", "LRU\n?\n", "OPT\n?\n"
]

Test input	Expected output	What it validates
1 page, size 1	FIFO 1	minimal eviction behavior
all distinct, k=1	5 faults	worst-case churn
repeated single page	0 faults	hit stability
sample-like	correct min	full simulation correctness

Edge Cases

A critical edge case is when a page never appears again in OPT. For example, with memory size two and request sequence 1 2 3 4, when processing page 3, both 1 and 2 have no future use. The algorithm assigns them next-use value as infinity, and eviction can pick either. This matches OPT definition because any page with no future reference is equally optimal to remove.

Another edge case is repeated access patterns like 1 2 1 2 1 2 with memory size two. FIFO and LRU both avoid faults after warm-up, and OPT also produces zero additional faults. This confirms that all policies converge on stable reuse patterns, and any discrepancy would indicate incorrect timestamp updates or failure to update next-use pointers.