Virtual memory uses a page table to track the mapping of virtual addresses to physical addresses. To speed up this translation, modern processors implement a cache of the most recently used translations, called the translation lookaside buffer (TLB).

The following list is a stream of virtual addresses as seen on a system. Assume 4-KiB pages and a four-entry fully associative TLB with LRU replacement policy. If pages must be brought in from disk, give them the next largest unused page number. That is, the page coming in from disk (a page fault) will go to the next page in physical memory. At the start of this scenario, the largest page in memory is 12, so that page fault would go to page 13.

With a 4-KiB page, the lower 12 bits of the virtual address are just the offset within the page, and can be ignored. Assume that this is a 32 bit OS. The sequence of memory addresses is:

0x0FFF

0x7A28

0x3DAD

0x3A98

0x1C19

0x1000

0x22D0

The initial TLB looks like this:

Valid Bit	Tag	Physical Page #	LRU
1	B	C	2
1	7	4	1
1	3	6	0
0	4	9	3

The initial page table looks like:

Index	Valid	Physical page, or on disk
0	1	5
1	0	Disk
2	0	Disk
3	1	6
4	1	9
5	1	11
6	0	Disk
7	1	4
8	0	Disk
9	0	Disk
10	1	3
11	1	12

Fill out the following table to summary how well our TLB does:

Address	Result (H, M, PF)
0x0FFF
0x7A28
0x3DAD
0x3A98
0x1C19
0x1000
0x22D0

Fill out the TLB to show its state after the above virtual addresses have been accessed:

Valid Bit	Tag	Physical Page #	LRU

Fill out the page table to show its state after the above virtual addresses have ben accessed:

Index	Valid	Physical page, or on disk
0
1
2
3
4
5
6
7
8
9
10
11