Question

List two algorithms commonly used to identify a frame for replacement

Answer 1

1.

First In First Out (FIFO) :

Here, whenever there is a need of replacement, the frame that came into the memory the earliest, is removed/replaced.

For example, let's say the memory can hold a maximum of 3 frames, in slots s1, s2, s3.

Following is a sample sequencing :

• Frame 5 is accessed
  • s1 => frame 5
• Frame 1 is accessed
  • s1 => frame 5
  • s2 => frame 1
• Frame 5 is accessed
  • s1 => frame 5
  • s2 => frame 1
• Frame 14 is accessed
  • s1 => frame 5
  • s2 => frame 1
  • s3 => frame 14
• Frame 18 is accessed
  • s1 => frame 18
  • s2 => frame 1
  • s3 => frame 14

As seen, frame 5 (which came in first amongst all of frames 5, 1, 14) was replaced, and the incoming frame 18 replaced in its place.

2.

Least Recently Used (LRU) :

Here, whenever there is a need of replacement, the frame that has been used least recently, is removed.

We take the same example as above.

Also, we maintain a linked list, where the element on the leftmost side is the oldest (least recently used), and the element on the rightmost is newest (most recently used).

• Frame 5 is accessed
  • s1 => frame 5
  • List : 5
• Frame 1 is accessed
  • s1 => frame 5
  • s2 => frame 1
  • List : 5 -> 1
• Frame 5 is accessed
  • s1 => frame 5
  • s2 => frame 1
  • List : 1 -> 5
• Frame 14 is accessed
  • s1 => frame 5
  • s2 => frame 1
  • s3 => frame 14
  • List : 1 -> 5 -> 14
• Frame 18 is accessed
  • s1 => frame 5
  • s2 => frame 18
  • s3 => frame 14
  • List : 5 -> 14 -> 18

As seen, frame 1 (which was the least recently used frame) was replaced, and the incoming frame 18 replaced in its place.