SME
Operating Systems · Problem type
Page replacement: FIFO and LRU
Use this for “Pages are referenced 1, 3, 1, 2, 4, 3, 1, 4 with 3 frames, all empty at the start. How many page faults does FIFO make, and LRU?”
This is an example. Type your own values to start a new problem.
Reference string
8 numbers · commas between
f
Frames
example
FFIFO
Page faults under FIFO
worked out (not typed)
FLRU
Page faults under LRU
worked out (not typed)
Formulas
FFIFO
=
FIFO
faults
with
f
frames
on
the
n
references
5 = FIFO faults with 3 frames on the 8 references
FLRU
=
LRU
faults
with
f
frames
on
the
n
references
6 = LRU faults with 3 frames on the 8 references
Assumptions
•
Demand paging: a page comes in only when it is referenced, and the frames start empty.
•
FIFO evicts the page loaded first; LRU evicts the page whose last use was longest ago.
•
Every first reference to a page is a fault, so faults are never fewer than the distinct pages.
•
LRU usually faults less than FIFO, but not on every string: on the opening string it faults once more.
Step-by-step
WE KNOW
n = 8, r₁ = 1, r₂ = 3, r₃ = 1, r₄ = 2, r₅ = 4, r₆ = 3, r₇ = 1, r₈ = 4, f = 3
FIND
page faults under FIFO (FFIFO), page faults under LRU (FLRU)
Step 1 · Find page faults under FIFO (FFIFO)
Use FFIFO = FIFO faults with f frames on the n references
Bring each page in on its first use; when every frame is full, the page loaded longest ago goes out.
FFIFO
=
FIFO
faults
with
f
frames
on
r₁
,
r₂
,
r₃
,
r₄
,
r₅
,
r₆
,
r₇
,
r₈
FFIFO = FIFO faults with 3 frames on 1, 3, 1, 2, 4, 3, 1, 4
FIFO 1: page 1, fault; frames 1
FIFO 2: page 3, fault; frames 1, 3
FIFO 3: page 1, hit
FIFO 4: page 2, fault; frames 1, 3, 2
FIFO 5: page 4, fault, 1 out; frames 3, 2, 4
FIFO 6: page 3, hit
FIFO 7: page 1, fault, 3 out; frames 2, 4, 1
FIFO 8: page 4, hit
FFIFO = 5
Step 2 · Find page faults under LRU (FLRU)
Use FLRU = LRU faults with f frames on the n references
Bring each page in on its first use; when every frame is full, the page used longest ago goes out.
FLRU
=
LRU
faults
with
f
frames
on
r₁
,
r₂
,
r₃
,
r₄
,
r₅
,
r₆
,
r₇
,
r₈
FLRU = LRU faults with 3 frames on 1, 3, 1, 2, 4, 3, 1, 4
LRU 1: page 1, fault; frames 1
LRU 2: page 3, fault; frames 1, 3
LRU 3: page 1, hit
LRU 4: page 2, fault; frames 3, 1, 2
LRU 5: page 4, fault, 3 out; frames 1, 2, 4
LRU 6: page 3, fault, 1 out; frames 2, 4, 3
LRU 7: page 1, fault, 2 out; frames 4, 3, 1
LRU 8: page 4, hit
FLRU = 6
Check
Put the numbers back in. Both sides should match.
5 = FIFO faults with 3 frames on 1, 3, 1, 2, 4, 3, 1, 4 ✓
6 = LRU faults with 3 frames on 1, 3, 1, 2, 4, 3, 1, 4 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Memory management
Main lesson
Effective access time with a TLB
Use this for “A TLB lookup takes 10 ns, memory takes 100 ns, and 90% of lookups hit. What is the effective access time?”
Effective access time with page faults
Use this for “Memory takes 100 ns, a page fault takes 8 ms to service, and 1 access in 100 000 faults. What is the effective access time?”