FIFO Cache Replacement Algorithm

What is FIFO Replacement?

FIFO (First-In First-Out) is one of the simplest cache replacement algorithms. When the cache becomes full and a new memory block must be inserted, the block that entered the cache first is replaced.

The cache therefore behaves like a queue:

First block inserted  →  First block removed

To implement FIFO, the system must remember the order in which blocks entered the cache.

Example Setup

Consider a fully associative cache with 8 cache lines.

Cache Lines

Line0
Line1
Line2
Line3
Line4
Line5
Line6
Line7

The CPU generates a sequence of memory block requests called a block reference string.

Block Reference String

4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7

Each value represents a RAM block number requested by the CPU.

• If the block is already in cache → Cache Hit
• If the block is not in cache → Cache Miss

FIFO Replacement Process

Initially, the cache is empty, so the first block requests are inserted into the cache until it becomes full.

When a new block arrives and the cache is full, the block that was inserted earliest is replaced.

Example:

Cache is full

Oldest block in cache → replaced
New block → inserted

This process continues for each new request.

Final Result of the Example

After processing the reference string using FIFO:

• Memory block 7 is located in cache line 4.

Answer = Cache Line 4

Cache Performance

For the given reference string:

Cache Misses = 13
Cache Hits   = 4

Compared with the LRU algorithm for the same reference string:

LRU Misses = 12
FIFO Misses = 13

In this specific case, LRU performs slightly better because it produces fewer cache misses.