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):
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?
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.