Paging Simulator

First In First Out

The FIFO algorithm is the simplest virtual memory algorithm. Its behavior is exactly like that of a FIFO queue when it comes to replacement. When a page is referenced, it checks if that page is already in memory. If it is then it moves on to the next page in the queue. If a page is not in memory, then it checks if there are any free frames. If so, it is added to memory. This is counted as a page fault. If a page is not in memory and there are no free frames, then FIFO is put to work. The oldest page in memory is removed and then the new page is added. The oldest page is found at the head of the queue. This is counted as a page fault.

Least Recently Used

The LRU algorithm improves slightly upon FIFO by removing the page in memory which was used the farthest back in time. This is based on the idea that recent behavior may be a good predictor of future behavior. When a page is referenced, it checks if that page is in memory. If it is, then it is moved to the tail of the queue. Because the frame queue is dequeued at the head, adding a recently used page to the tail creates a sort of priority queue by use times. If a page is not in memory and there is a free frame, it is added to the tail. This is counted as a page fault. If a page is not in memory and there are no free frames, the head is dequeued and the new page is enqueued at the tail. Also, a page fault.

Optimal Page Replacement

This algorithm is only possible in a hypothetical environment such as this simulation. Future page references are used to tell the algorithm which pages to remove from memory. The page which is in memory but either used farthest in the future or not again is removed from memory. When a page is referenced, it will check if it is in memory. If so it will move to the next page. If the page is not in memory and there is a free frame, it is added to the tail. This is another page fault. If a page is not in memory and there are no free frames, OPT iterates through each page in memory and through all future page references to assign each page in memory a priority number. The priority number is the soonest that page is referenced from the current page. If it is not referenced again, it receives a priority of -1. The first page to receive a priority of -1 is chosen as the victim. If there are no pages with a priority of -1, then the highest integer priority number is the victim. The page fault counter is incremented.

Overall, FIFO and LRU were surprisingly similar in this simulation. The best performer, the 1024 page size, only had 7 fewer page faults in LRU than in FIFO. On average, LRU only had about 3 fewer page faults over all 4 series than FIFO. This speaks to the fact that LRU is an improvement over FIFO, but only slightly. Also, LRU’s assumption that recent past behavior is a good indicator of future behavior is probably not true during this simulation. The page numbers appeared to be random. LRU would likely perform much better than FIFO during a practical scenario. FIFO also did not appear to suffer from Belady’s anomaly.

Based on LRU’s surprisingly average performance, this seems to suggest that designing a program to run around the working set would be advantageous. At the beginning of a new working set there would be a period of many page faults, but once the majority of it is in memory it will stay there using the LRU algorithm. This would work well for productivity software where a user needs to stay inside a program for a longer period of time.