There are many page replacement algorithms, this week we were asked to implement the fifo and lru page replacement algorithms. But, first a little primer.
FIFO Page Replacement
The fifo page replacement algorithm is essentially a queue setup that pushes the first items into the list out first when the list is full, so for example, if you have the numbers 1,2,3 and they are put into the array in that order, when the 4th number comes along your 1 gets pushed out, and you are left with 2,3,4. That simple!
The FIFO page replacement algorithm was pretty simple to implement, all I had to do was create an array that was the size of my frames, then I simply setup a "current pointer" to that array head initially, and a pointer to the tail and head of the array. When we found a frame we didn't do anything. When we didn't find a frame, we simply assigned the data to the current pointer then moved the pointer down the array, when we reached the bottom, we simply moved the pointer to the top and repeat, also we increment our page fault counter. Something interesting to note, supposing we have the next element in the array that matches so we don't have a page count increment, well the next go around, and that one will still get written over. Since this element wasn't recently written, it doesn't get to keep it's status as "new", and still can be written over in the next iteration. This seems a little less then efficient, however perhaps changing it a small bit so that it skips over to the next element would be beneficial.
LRU Page Replacement
The Least Recently Used algorithm basically makes an association for each array with a clock. The book suggests this is easy to implement using a doubly linked list, the other option is counters.
The LRU page replacement algorithm in theory was pretty easy too, and really looking back on it, it really was. I simply decided to make a second "timing" array that matched up with the frame array. This way whenever we did a frame check, we refreshed the matching frame's time, and if the frame wasn't there, we put the new one into the frame array, and then updated our clock. Really I was able to keep a lot of my code from the fifo page replacement and reuse it, as a lot of it was simply "setup" and structure stuff that I could easily reuse.
Caveats
This sounds really simple, but I did have a few problems along the way one of the main problems I ran into was operator precedence. This occurs when you have + and * in a equation, or a ( or something like that, the compiler/processor has to know what to evaluate first, if for example you try to increment a pointer that is routed through an address, like so *ptr, and you attempt to increment *ptr++, you are actually incrementing your address, effectively losing the pointer to your pointer. This is simply fixed by (*ptr)++; since the ( has higher precedence then ++. Another issue I ran into was that using the function clock() just didn't want to cooperate, clock ran just way too fast, so I had to put wait's in there so that it would adjust the clock even minutely so that when we assigned it to the arrays we didn't use the same time on numerous ones. That makes it hard to find the oldest one if they are all matching times.
Good luck and let me know if you have any problems!
