Write a program in C that runs FIFO and LRU page replacement algorithms. Use the page reference sequence in an input file to drive your program. Report the number of page faults and time costs incurred by the page faults. The number of available page frames should be set according to an input of your program. In your program, we assume that demand paging is used. All the memory page frames are unallocated initially, and all the referenced pages are initially in the swap space. Each page is associated with a modify bit $($MB$),$ which indicates whether the page has been modified in memory and needs to be swapped out if being evicted.

The program should accept the following input parameters to specify:

a$.$ The selected replacement algorithm $($FIFO$$ or $$LRU$)$

b$.$ The memory size $($the number of available page frames$).$

c$.$ Time cost for swap$-$in $($time needed to swap in a page from swap space into memory$).$

d$.$ Time cost for swap$-$out $($time needed to swap out a page from memory to swap space$).$

e$.$ The input page reference file that contains the page references reference $($see the format

details below$).$

f$.$ The output trace file that contains detailed output info for each page reference.

Example: $$./$replace LRU $21020$ pageref.txt trace$-$lru.txt

This example command means that the system uses the LRU replacement algorithm, has $2$ free physical page frames in memory, swapping in a page takes $10$ time units, swapping out a page takes $20$ time units, use page references in $$pageref$.$txt$$ as input, and generate an output file $$trace$-$lru.txt$.$

Input Page Reference File Format: Each line contains two fields. The first field is either $$R$$ or $$W$,$ meaning a read or a write to the page, respectively. The second field is the page number. Each line of the input file thus specifies a page reference.

$1$: R $4$

$2$: W $4$

$3$: R $5$

$4$: R $6$

$5$: R $4$

$...$

In the above example, the first line means a read reference to Page #$4,$ and the second line means a write reference to Page #$4.$ Two sample input reference files $($pageref$.$txt and pageref$-$small.txt$)$ are provided online as examples. Output Trace File Format: The program should generate a trace file as output. Each line should contain $6$ fields, following the record line number. The first field is either $$R$$ or $$W$,$ meaning a read or a write to the page, respectively. The second field is the page number, specifying the page being referenced. The third field specifies whether this page reference incurs a page fault $($denoted as $$F$)$ or not $($i$.$e$.,$ a page hit in memory, denoted as $$H$).$ The fourth field specifies the victim page number, if a victim page is evicted. If no victim page being evicted, use $-1$ to indicate that. The last two fields are the swap$-$in time and swap$-$out time for servicing this page reference, respectively.

$1$: R $4$ F $-1100$

$2$: W $4$ H $-100$

$3$: R $5$ F $-1100$

$4$: R $6$ F $41020$

$5$: R $4$ F $5100$

$...$

In the above example, the first line records a read reference to Page #$4,$ which is a miss in memory, causing a page fault. There is no victim page being evicted, and it takes $10$ time units to swap in the target page, but it does not incur any time cost for swapping out a page. The second line records a write reference to Page #$4,$ which is a hit in memory, which does not incur swap$-$in or swap$-$out. The third line records a read reference to page #$5,$ which is a miss in memory and incurs a swap$-$in cost of $10$ time units. The fourth line records a read reference to Page #$6,$ which is a miss in memory and triggers eviction of Page #$4,$ which incurs a swap$-$in operation for loading Page #$6$ and a swap$-$out operation for writing the modified Page #$4$ back to the swap space.

Upon completion of the execution, the program should generate the following output summary information to the standard output.

a$.$ The total number of page references.

b$.$ The total number of page faults on read references.

c$.$ The total number of page faults on write references.

d$.$ The total number of time units for swapping in pages from swap space.

e$.$ The total number of time units for swapping out pages to swap space.

Page fault costs: The program needs to calculate the $$cost$$ of page faults in terms of time units. In the example above, upon a page miss $($the target page is not found in memory$),$ it takes $10$ time units to swap in the page to memory. In the case that needs to evict a victim page, if the victim page has been modified $($written$)$ in memory since it was loaded into memory, it takes $20$ time units to swap out the modified victim page to the swap space; If the victim page is unmodified $($unwritten$),$ there is no need to swap it out. Thus, a modify bit $($MB$)$ is needed for each page frame to keep track of the page status. We assume that all memory page frames are unallocated initially, all pages are initially in the swap space, and either read or write to a page that is not resident in memory incurs a page fault and needs to swap in the page first.