Page Replacement
A computer has limited memory, so it cannot keep every page in memory at the same time. When a program requests a page that is not currently in memory, a page fault occurs. The system then needs to make space by removing another page. Change the page requests or the number of memory frames and compare how FIFO, LRU and Optimal handle them.
Interactive workspace
When memory is full, LRU removes the page that has not been used for the longest time.
Enter page numbers separated by spaces or commas. Use whole numbers from 0 to 99, with up to 40 requests.
Examples
Memory frames
Step 0 of 20
Requested page
–
Press Next or Play. The first request will appear here.
Frame 1
–Frame 2
–Frame 3
–
Hits so far
0
Faults so far
0
Hit ratio
0%
no requests yet
Step
0/20
Step-by-step explanation
0 of 20 steps
Press Next or Play to see how each page request is handled, one at a time.
History of every request
| Request | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Frame 1 | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · |
| Frame 2 | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · |
| Frame 3 | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · |
| Result | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · | · |
Page faults for these inputs (lower is better)
FIFO
15
5 hits · 25% hit ratio
LRU
12
8 hits · 40% hit ratio
Optimal
fewest9
11 hits · 55% hit ratio
Belady’s anomaly: FIFO faults by number of frames
- 1 frame20
- 2 frames15
- 3 frames15
- 4 frames10
- 5 frames9
- 6 frames6
- 7 frames6
For this particular input, adding more frames does not increase FIFO faults. Try the Belady’s anomaly example to see a case where it does.
Requests
20
LRU faults
12
LRU hits
8
Design diagram: how this demo decides
Click any box to see what it does and why it is built that way.
Start
Next page request
- What it does
- The simulator reads the requests one page at a time. Each request becomes one step.
- Where it lives
- simulate() in src/lib/pageReplacement.ts
- Why it is built this way
- One request is one step, so Next and Back match the data exactly.
Under the hood
From input to screen
The experiment follows this process. Select any box to see what it does and which function or component is behind it.
Pipeline: input, parsing, simulation, steps, visualization
Click any box to see what it does and why it is built that way.
Start
Input
- What it does
- You enter the page requests, choose the number of frames and select FIFO, LRU or Optimal. These inputs are stored in React state.
- Where it lives
- PageReplacementDemo.tsx (text, frameCount, algo)
- Why it is built this way
- Only the values you enter are stored. The rest of the results are calculated from those values, which helps keep everything consistent.
Technical notes
How Page Replacement works
How the algorithm works
Each request represents a page number. If the requested page is already in memory, it is a hit. If it is not in memory, it is a page fault. If an empty frame is available, the page is placed there. If all frames are full, one of the existing pages must be removed.
The three algorithms decide which page to remove in different ways. FIFO removes the page that has been in memory the longest. LRU removes the page that has not been used for the longest time. Optimal removes the page whose next use is farthest in the future. It needs future knowledge, so it is mainly useful as a best-case comparison.
Important steps
- 01Read the next page request.
- 02Check whether the page is already in memory.
- 03If there is a page fault, use an empty frame if possible.
- 04If all frames are full, choose a page to remove.
- 05Load the new page and save the memory state with an explanation.
- 06After all requests are complete, count the hits and faults and compare all three algorithms.
Relevant variables
- N
- Total number of page requests.
- F
- Number of memory frames.
- frames[]
- The page stored in each frame, or an empty value.
- loadOrder
- The order in which frames were filled, used by FIFO.
- lastUsed[]
- The last time each page was used, including hits, used by LRU.
- hits, faults
- Total page hits and page faults.
Time and space complexity
| Algorithm | Time | Space |
|---|---|---|
| FIFO | O(N·F) | O(N·F) |
| LRU | O(N·F) | O(N·F) |
| Optimal | O(N²·F) worst case | O(N·F) |
N is the number of requests and F is the number of frames. The walkthrough stores a copy of the frames after every step, which is why its space usage is O(N·F). The actual working memory is only O(F).
Example input and output
Input
- Requests: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
- Frames: 3
Output
- FIFO: 15 page faults
- LRU: 12 page faults
- Optimal: 9 page faults
Edge cases
- More frames than unique pages: Only the first request for each page causes a fault.
- Belady's anomaly: For the requests 1 2 3 4 1 2 5 1 2 3 4 5, FIFO gives 9 faults with 3 frames but 10 faults with 4 frames.
- One frame: Every time the requested page changes, a page fault occurs.
- Same page requested repeatedly: Only the first request causes a fault. All later requests are hits.
- Invalid input: Letters or more than 40 requests are rejected with a clear error message.
Where the code lives
- Enginesrc/lib/pageReplacement.ts
- Workspacesrc/components/PageReplacementDemo.tsx
- Checkstests/pageReplacement.test.ts