Part $0-$ Random number generator $(10$ points$)$

To begin writing our paging simulator, we'll need to generate a sequence of memory addresses.

As a program executes, it generates virtual memory addresses for as long as the program runs. To simulate this, we'll be generating addresses using a random number generator.

As a caveat, the addresses generated by a typical program aren't truly random, since in practice, there will always be some group of pages a process will frequently access. As a stand$-$in for this, we'll generate two random numbers and add them together. This forms an uneven distribution, not unlike that of rolling two dice, where there are more ways to roll a $7$ than there are to roll a $2$ or $12.$

Image from Edward D$.$ Collins'webpage

edcollins.com.

$$

Begin with the following RNG shown below.

For ease of understanding, these addresses are for a theoretical base$-10$ computer, with the lower three digits used as the offset and the higher two digits used as the page number. Because numbers are being capped at $10000,$ and two such random numbers are being added together, this means addresses range from $0$ to $19999.$ This means there are $20$ different pages for our simulated program to access: pages $0$ to $19,$ where pages $10$ and $11$ are accessed most frequently.

Modify this program further so instead of the entire address being printed, only the page number is printed.Run this program and take a screenshot of its output.Part $1$: FIFO Page Replacement $(30$ points$)$Now that we have a means of "generating" addresses and getting their corresponding page numbers, we can implement our first page replacement algorithm: FIFO page replacement. Begin by adding the line $"$#include $16,$

Part $1$: FIFO Page Replacement $(30$ points$)$

Now that we have a means of "generating" addresses and getting their corresponding page numbers, we can implement our first page replacement algorithm: FIFO page replacement.

Begin by adding the line $"$#include

Part $2$: LRU page replacement $(30$ points$)$

With FIFO complete, we can now add our next page replacement algorithm: LRU. Before you start, you may want to comment out some of the cout lines being used for debugging, as they may get in the way at this point.First, add another list and page fault counter for LRU. This second queue will be used for the LRU's "stack". $($As mentioned in lecture, this isn't a stack, but we'll permit this abuse of terminology for ease of explanation.$)19-//$ LRU "stack"$20//$ And LRU page fault count$21$std: :list

Part $3$: Benchmarking $(30$ points$)$

From the two screenshots of your program running, take the sequence of page numbers and manually perform optimal page replacement $($OPT$)$ on the two sequences. $($You may use an online tool to verify your results.$)$

For the screenshot taken in part $1,$ you're comparing the performance of FIFO with OPT, with five page frames. For the screenshot taken in part $2,$ you're comparing the performance of both FIFO and LRU with OPT, with five page frames.

For the two sequences of page numbers, did OPT yield a lower page$-$fault count?

$$

Part $4$: Testing only one sequence of addresses $(40$ points$)$ Modify your code so that it has an array $($or alternatively, a vector$)$ of page numbers. You may use one set of page numbers from part $3.$ Your code should look something like what's shown below.

Modity your code so instead of using the RING to generate your page numbers, you instead access the array of page numbers.This modification is so we can test out how adding more page frames affects the number of page faults, which cannot be tested if the page numbers change with each test. First, modify your page frame count to $1.$ How many page faults did you get for both FIFO and LRU?Next, increase the page frame count to $20.$ How many page faults did you get for both FIFO and LRU?Slowly increase the number of page frames by one each time, recording the number of page faults that LRU and FIFO produce. Use this information to fill out the table below$\mathrm{.}123$ dots$20?$FIFOLRU

Hint: you don't need to fill out the entire table! You can stop at the number of page faults you had when you tried $20$ page frames! Because your program visits some pages more than once due to the uneven distribution, $20$ page frames is overkill, and you can get away with fewer page frames. Part $5$: Did you get something weird? $(10$ points$)$ Based on your results, you may think that increasing the number of page frames should reduce the number of page faults. In the study of paging algorithms is Belady's anomaly, which states that an increase in page frames does not necessarily reduce the number of page faults, and in some cases, it may even lead to an increase.

Did you experience Belady's anomaly? Due to the random nature of the RNG$,$ your experiment may or may not have resulted in Belady's anomaly appearing.

If you did experience Belady's anomaly, compare the number of page faults for FIFO and LRU.