Page faults in LRU algorithm

lru page-fault page-replacement
user3211186 picture user3211186 · May 27, 2014 · Viewed 7.2k times · Source

I'm having trouble with understanding something from my programming lecture. I know that page replacement algorithms have page faults.

In the LRU algorithm, when does a page fault occur? Is it when there are no more free frames left? Is it when a frame is already there, but already used too?

I have this picture in my lecture presentations (I cropped just the important part since the original is in another language):

enter image description here

The question in this picture is "Having only 4 frames, when will a page fault occur if the LRU algorithm is used?" And as I can see there is an x on the first 3 lines. That's why I'm asking if a page fault occurs when there are free frames left? Or does a page fault occur only in the red X's, when we need to "kick out" a frame?

Answer

user3211186 picture user3211186 · May 27, 2014

A page fault occurs when the page isn't already in one of the frames.

So if there are some free frames left and we need to enter a new page - a page fault will occur because the page isn't already in one of the frames. This means a page fault will keep occuring until we come across the same page (number) that is already in one of the frames. That's why there is an 'x' in the first 3 lines of the picture. And there is no 'x' on the fourth line because the page was already in one of the frames.

AND a page fault occurs if all of the frames are already with pages and the new page we are entering isn't already in one of the frames, we need to "kick out" a frame in order to free up one frame for the new page. This can be done in different algorithms, like Least Recently Used, First-In First-Out etc. That's why in the picture, some of the 'X's are red, because a page fault occured AND we kicked out a frame.

Thanks to @Blorgbeard for helping with my answer.

Related questions

How would you implement an LRU cache in Java?

Please don't say EHCache or OSCache, etc. Assume for purposes of this question that I want to implement my own using just the SDK (learning by doing). Given that the cache will be used in a multithreaded environment, which datastructures …

Read More
LRU cache design

Least Recently Used (LRU) Cache is to discard the least recently used items first How do you design and implement such a cache class? The design requirements are as follows: 1) find the item as fast as we can 2) Once a …

Read More
What is the difference between LRU and LFU

What is the difference between LRU and LFU cache implementations? I know that LRU can be implemented using LinkedHashMap. But how to implement LFU cache?

Read More