You just learned about page replacement algorithms and you would like to know which one will be more effective in the operating system that you will develop after graduation. To make it simple, you decided to compare the results of two of those algorithms: FIFO and Second chance. Your mission is to write a small simulation program under the following assumptions: there are a maximum of 100 virtual pages running in a physical memory with 20 frames. You will use a random number generator to determine which one is the next page to be accessed. If the page is already in the physical memory, nothing happens, otherwise if a frame is available then the page will be assigned to that frame and if there are no frames available you will then apply the replacement algorithm to decide which frame to use. To measure the effectiveness of the two algorithms, you will run the simulation for 10,000 pages and report the number of page faults for each algorithm. You will assume that the reference interval happens between two page faults. You will hand in the printout of your source code the output values on the due date (no late work will be accepted). You can use Visual Studio, Cygwin or any other system you may have access to but the programming language must be C or C++
Example: in a four frame physical memory (frames 0 to 3) and 14 page requests in the range 0 to 4. FIFO, shown below, produces 9 page faults (four requests happened at time zero in the order 0,1,2,3, all page faults, then times 5, 7, 8, 9, 10)
Chart: see image.
Using the second chance algorithm, at time 0, there were four page faults in the order 0, 1, 2, 3. At time 5, page O has been referenced (time 2) so it goes to the end of the line (reference erased), same happens with pages 1,2 and 3, so page 0 gets to the front again and is replaced. At time 7, page 0 is back, page 1 has been referenced between time 4 and 6, so it goes to end of line, page 2 is replaced, all pages have their reference bit cleared. Next page fault will be at time 9, the head of the list is page 3, which was not referenced since time 7, so 3 is replaced by 2. At time 10, 3 is back. The head of the line is page 4, which was not referenced, so it is replaced. The result is 8 page faults (four initial ones at time zero and then a time 5, 7, 9, and 10).
You are now an expert on page replacement algorithms. The first conclusion you got was that the randomness of the test invalidates the spatial and temporal locality concepts in such a way that the results of FIFO and Second chance do not allow you to establish which one is better. You decided to try a new one: LRU. Your mission is to modify your simulation program still under the assumptions that there are a maximum of 100 virtual pages running in a physical memory with 20 frames. You will keep using the random number generator to determine which one is the next page to be accessed. As in the previous project, if the page is already in the physical memory, nothing happens, otherwise if a frame is available then the page will be assigned to that frame and if there are no frames available you will then apply the LRU replacement algorithm to decide which frame to use. To measure the effectiveness of the new algorithm, you will run the simulation for 10,000 pages and report the number of page faults. You will assume that the reference interval happens between two page faults. You will hand in the printout of your source code and the output value on the due date (no late work will be accepted). You can use Visual Studio, Cygwin or any other system you may have access to but the programming language must be C or C++.
Example: in a four frame physical memory (frames 0 to 3) and 14 page requests in the range 0 to 4. FIFO, shown below, produced 9 page faults (four requests happened at time zero in the order 0,1,2,3, all page faults, then times 5, 7, 8, 9, 10)
Chart: see image.
Using the LRU algorithm, at time 0, there were four page faults in the order 0, 1, 2, 3. At time 5, page 2 has been least referenced (time 1) so it gets replaced. At time 6 to 8, page 0 and 1 are referenced. Next page fault will be at time 9, and LRU dictates that page 3 must be replaced. At time 10, 3 is back and the least recently used is page 4, so page 4 is replaced. The result is 7 page faults (four initial ones at time zero and then a time 5, 9, and 10).