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 following code after the line that prints the page number.

$```$

$//$ Check if the page is in the FIFO queue already by iterating

$//$ through the FIFO queue.

$//$ This iterator will either point to where the page is in the queue

$//$ OR point at the end, indicating the page wasn't found.

auto iter $=$ std::find$($fifo$\_$queue.begin$(),$ fifo$\_$queue.end$(),$ page$\_$number$)$;

$//$ If it was found, then iter won't be pointing at the end. Yay!

$//$ If not, push it at the front of the queue.

$//$ If there's no room, pop a page and then push.

if $($iter $==$ fifo$\_$queue.end$())\{$

std::cout $$ "PAGE FAULT! Page not found. Adding missing page...

$"$;

$//$ Push the missing page at the front of the queue.

fifo$\_$queue.push$\_$front$($page$\_$number$)$;

$//$ If the length of the queue exceeds the value assigned

$//$ to num$\_$page$\_$frames, pop the page at the back.

if $($fifo$\_$queue.size$()>$ num$\_$page$\_$frames$)\{$

fifo$\_$queue.pop$\_$back$()$;

$\}$

$\}$

$\}$

return $0$;

$\}$

$```$

Note: the "auto" keyword is used to deduce the datatype of a variable. If your compiler does not support this keyword, replace it with $"$std::list::iterator". Add a new variable to track the number of page faults that occurred using FIFO.

$14//$ FIFO queue

$15//$ And FIFO page fault count

std: :list fifo$\_$queue;

int fifo$\_$page$\_$fault$\_$count $=0$;

for $($int i $=0$; i $<mtext></mtext><mn>2</mn><mn>0</mn>$; i$++)\backslash \{$

Then, after the line that prints out "PAGE FAULT!", add a line of code that increments the page fault count.

$```$

$//$ If it was found, then iter won't be pointing at the end. Yay!

$//$ If not, push it at the front of the queue.

$//$ If there's no room, pop a page and then push.

if $($iter $==$ fifo$\_$queue.end$())\{$

std::cout $$ "PAGE FAULT! Page not found. Adding missing page...

$"$;

fifo$\_$page$\_$fault$\_$count$++$;

$//$ Push the missing page at the front of the queue.

fifo$\_$queue.push$\_$front$($page$\_$number$)$;

$```$

Finally, after the for loop, add a line of code that prints out the number of FIFO page faults.

$```$

$//$ If the length of the queue exceeds the value assigned

$//$ to num$\_$page$\_$frames, pop the page at the back.

if $($fifo$\_$queue.size$()>$ num$\_$page$\_$frames$)\{$

fifo$\_$queue.pop$\_$back$()$;

$\}$

$\}$

$\}$

$//$ Print out page fault counts

std::cout $$ "FIFO page faults: $"$