Virtual Memory, LRU, and Page Faults - Homework

Question

I've been working on the following program and it feels like it's missing some information or a) and b) are a bit of a trick:

The loop is executed as part of a program on a virtual memory system that employs 4KB pages. Assume that an LRU replacement algorithm is used to select pages to be replaced in memory when needed. The instruction labeled “Start” begins on a page boundary and the body of the loop contains 4601 pairs of shift instructions (sll & srl).

Start:  addi    $3,$0,32

Loop:   sll $4,$4,1

srl $4,$4,1

...         # previous two instructions are

...         # repeated  4600 times

addi    $3,$3,-1

bne $3,$0,loop

a) How many page faults would occur during the execution of the loop if the memory contains eight 4KB frames?

b) How many page faults would occur during the execution of the loop if the memory contains nine 4KB frames?

Wouldn't a) and b) both be 5 page faults? There are 4602 instructions each time we loop, MIPS instructions are 4B, and the page size is 4KB. 4KB/4B = 1024 instructions per page, so first time through the loop:

instructions 0 - 1023 frame 0 page fault yes

instructions 1024 - 2047 frame 1 page fault yes

instructions 2048 - 3071 frame 2 page fault yes

instructions 3072 - 4096 frame 3 page fault yes

instructions 4096 - 4602 frame 4 page fault yes

So, when we come back into the loop on the second interation, the pages weren't replaced yet by the LRU policy, so we can reference them again. Why would this change whether we have 8 or 9 frames for the 32 loop iterations?

Answer 1

The body of the loop contains 4601 pairs of shift instructions. Along with the addi and bne instructions, there are a total of 9204 instructions per loop.