$//$ Implement LRU page replacement algorithm for the page table

$//$ Implement FIFO page replacement algorithm for the TLB

#include

#include

#include

#include

#define PAGES $256$

#define PAGE$\_$MASK $255$

#define PAGE$\_$SIZE $256$

#define OFFSET $8$

#define OFFSET$\_$MASK $255$

#define FRAME$\_$SIZE $256$

#define BUFFER$\_$SIZE $10$

int main $($int argc, char$**$ argv$)\{$

FILE$*$ addressesFile $=$ fopen$($argv$[1],"$r$")$;

FILE$*$ backingStore $=$ fopen$("$BACKING$\_$STORE.bin", $"$rb$")$;

FILE$*$ outputFile $=$ fopen$("$outputPart$1.$txt$","$w$")$;

int pageTable$[$PAGES$]$;

int tlb$[16][2]$;

int totalAddresses $=0,$ pageFault $=0,$ tlbHits $=0,$ frames $=$ atoi$($argv$[2])$;

char buffer$[$BUFFER$\_$SIZE$]$; $//$ Buffer for reading logical addresses from file

signed char memory$[$FRAME$\_$SIZE $*$ frames$]$; $//$ Physical memory

unsigned char freePage $=0$; $//$ Free page is the next frame to be used for page replacement in the page table and TLB

$//$ Initialize page table

for $($int i $=0$; i $<$ PAGES; i$++)\{$

pageTable$[$i$]=-1$;

$\}$

$//$ Initialize TLB

for $($int i $=0$; i $<16$; i$++)\{$

tlb$[$i$][0]=-1$;

tlb$[$i$][1]=-1$;

$\}$

$//$ Use First$-$In$-$First$-$Out $($FIFO$)$ for page replacement in the TLB$.$

int fifo $=0$;

$//$ Read logical addresses from file

while $($fgets$($buffer$,$ BUFFER$\_$SIZE, addressesFile$)!=$ NULL$)\{$

int logicalAddress $=$ atoi$($buffer$)$;

int pageNumber $=($logicalAddress $>>$ OFFSET$)$ & PAGE$\_$MASK;

int offset $=$ logicalAddress & OFFSET$\_$MASK;

int frameNumber $=-1$;

int tlbIndex $=-1$;

$//$ Check TLB

for $($int i $=0$; i $<16$; i$++)\{$

if $($tlb$[$i$][0]==$ pageNumber$)\{$

frameNumber $=$ tlb$[$i$][1]$;

tlbIndex $=$ i;

tlbHits$++$;

break;

$\}$

$\}$

$//$ TLB miss

if $($frameNumber $==-1)\{$

$//$ Check page table

frameNumber $=$ pageTable$[$pageNumber$]$;

$//$ Page fault

if $($frameNumber $==-1)\{$

pageFault$++$;

$//$ Load page from backing store

fseek$($backingStore$,$ pageNumber $*$ PAGE$\_$SIZE, SEEK$\_$SET$)$; $//$ Seek to page number in backing store file

fread$($memory $+$ freePage $*$ FRAME$\_$SIZE, sizeof$($signed char$),$ FRAME$\_$SIZE, backingStore$)$; $//$ Load page into free frame

frameNumber $=$ freePage; $//$ Update frame number

pageTable$[$pageNumber$]=$ frameNumber; $//$ Update page table

freePage $=($freePage $+1)\%$ frames; $//$ Increment free page

$\}$

$//$ Update TLB

tlb$[$fifo$][0]=$ pageNumber;

tlb$[$fifo$][1]=$ frameNumber;

fifo $=($fifo $+1)\%16$;

$\}$

int physicalAddress $=($frameNumber $<<$ OFFSET$)|$ offset;

signed char value $=$ memory$[$frameNumber $*$ FRAME$\_$SIZE $+$ offset$]$;

fprintf$($outputFile$,$ "Virtual address: $\%$d Physical address: $\%$d Value: $\%$d

$",$ logicalAddress$,$ physicalAddress, value$)$;

totalAddresses$++$;

$\}$

fprintf$($outputFile$,$ "Number of Translated Addresses $=\%$d

$",$ totalAddresses$)$;

fprintf$($outputFile$,$ "Page Faults $=\%$d

Page Fault Rate $=\%\mathrm{.}3$f

$",$ pageFault, $($float$)$pageFault $/$ totalAddresses$)$;

fprintf$($outputFile$,"$TLB Hits $=\%$d

TLB Hit Rate $=\%\mathrm{.}3$f$",$ tlbHits, $($float$)$tlbHits $/$ totalAddresses$)$;

fclose$($addressesFile$)$;

fclose$($backingStore$)$;

fclose$($outputFile$)$;

return $0$;

$\}$

The code above is meant to take in a logical address and output the physical address and corresponding value using a page table and tlb$.$ The page table above uses FIFO.

Please edit the above code so that the page table uses LRU, instead of FIFO and the tlb uses FIFO.

The output should be correct like this when the number of frames $=128$:

Virtual address: $62616$ Physical address: $27288$ Value: $0$

Virtual address: $15436$ Physical address: $9804$ Value: $0$

Virtual address: $17491$ Physical address: $8787$ Value: $20$

Virtual address: $53656$ Physical address: $8344$ Value: $0$

Virtual address: $26449$ Physical address: $18769$ Value: $0$

Virtual address: $34935$ Physical address: $19575$ Value: $29$

Virtual address: $19864$ Physical address: $21400$ Value: $0$

Virtual address: $51388$ Physical address: $21692$ Value: $0$

Virtual address: $15155$ Physical address: $4915$ Value: $-52$

Virtual address: $64775$ Physical address: $22023$ Value: $65$