TLBs And Page Tables

Frames and Pages

TLB and Page Table Simulation

Virtual addresses are split up this way:

15		8	7		0
VPN			offset

Suppose our (partial) page table looks like this:

VPN (Index)	Valid	PFN/ Disk Block
0	1	1
1	0	5
2	1	7
3	1	8
4	1	2
5	1	6

Our four entry TLB looks like this:

Valid	Tag (VPN)	PFN
0
1	4	2
1	2	7
1	5	6

Note that the valid bit here means the entry in this cache is valid. It is not the valid bit for the page table entry. Any page not in memory that gets referenced is brought into memory and its valid bit gets set. Thus any page with an entry in the TLB is automatically in memory and not on disk.

Suppose the CPU references the virtual address 0x0506. The page offset is 0x06 and the VPN is 0x05. The TLB has a hit and the PFN is 0x06. Hence the physical address is 0x0606.

Suppose the CPU references the virtual address 0x02F0. The page offset is 0xF0 and the VPN is 0x02. The TLB has a hit and the PFN is 0x07. Hence the physical address is 0x07F0.

Suppose the CPU references the virtual address 0x00F0. The page offset is 0xF0 and the VPN is 0x00. The TLB has a miss, so we have to look at the page table entry at index 0x00 to find the PFN. The PFN is 0x01. Hence the physical address is 0x01F0. Of course the TLB must be updated:

Valid	Tag (VPN)	PFN
1	0	1
1	4	2
1	2	7
1	5	6

Suppose the CPU references the virtual address 0x0104. The page offset is 0x04 and the VPN is 0x01. The TLB has a miss, so we have to look at the page table entry at index 0x01 to find the PFN. The valid bit is not set so a page fault occurs while disk block 0x05 is brought into memory, say into frame 0. The PFN is 0x00. Hence the physical address is 0x0004. Of course the page table and the TLB must be updated:

Partial page table:

VPN (Index)	Valid	PFN/ Disk Block
0	1	1
1	1	0
2	1	7
3	1	8
4	1	2
5	1	6

TLB:

Valid	Tag (VPN)	PFN
1	0	1
1	1	0
1	2	7
1	5	6

We used a LRU replacement policy, so the entry for the VPN 4 gets replaced.