2

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?

user3211186
  • 115
  • 2
  • 13
  • A page fault occurs when the requested page is not in memory and needs to be paged in. This may or may not cause another page to be dropped. – Blorgbeard May 26 '14 at 22:51
  • So according to that, a page fault will occur even in the first entry, where all the frames are free? Basically, the only time when a page fault WONT occur is if the frame is already paged in. – user3211186 May 26 '14 at 22:53
  • Yes, that's right. Any time a page is requested that isn't in memory, a page fault occurs. The LRU algorithm determines which page to throw out when memory is full. That's the only way that it influences when page faults occur - if it throws out a page that is later requested then that's going to be another page fault. – Blorgbeard May 26 '14 at 22:57
  • Thank you. This makes it very clear. Your comment is actually the answer I needed, so what do I do now with my question here on stackoverflow? Do I answer it myself? – user3211186 May 26 '14 at 23:00
  • You can do that, absolutely. Writing up an answer might even help you solidify your understanding some more. – Blorgbeard May 26 '14 at 23:23

1 Answers1

3

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.

user3211186
  • 115
  • 2
  • 13