1 Replies - 1448 Views - Last Post: 14 April 2012 - 09:40 AM

#1 Learn4Life  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 14-April 12

Paging with TLB

Posted 14 April 2012 - 01:00 AM

In a system where paging is supported by a TLB, the CPU makes 9 consecutive memory accesses. The page numbers of the 9 logical addresses, in chronological order, are

9 8 4 5 9 6 4 7 5

The cache can hold a maximum of 4 page-table entries. The cache is initially empty.

When the cache is full, page-table entries enter and leave the cache in FIFO order. Calculate the hit-ratio of the cache for the given sequence of 9 logical addresses.

My first approach was at the beginning the page table looks like:
0 9
1 8
2 4
3 5

The next page is 9, but 9 is already in the table so no page fault, right? Then page 1 with value 8 is replaced with value 6, page 2 is not changed since 4 is already in the table. Now the last page is replaced with the value 7 and the table looks like this know:
0 9
1 6
2 4
3 7

The next access is then for value 5, which results in TLB miss, so page 1 replaces 6 --> 5. I can't figure out what the TLB hit ratio is. My thought was I made 9 memory accesses where 3 resulted in a TLB miss, so my hit ratio should be 3/9. I am not certain if this is right, so it would be nice to get your opinion to that. Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: Paging with TLB

#2 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,534
  • Joined: 05-May 05

Re: Paging with TLB

Posted 14 April 2012 - 09:40 AM

You are correct about the hit ratio.

Quote

Then page 1 with value 8 is replaced with value 6


I don't agree. After getting past the first 4 page faults and filling the TLB, the first entry to be evicted should be the mapping for 9. It was the first entry to enter the TLB, and since the page algorithm is FIFO, it should be the first to go.

Quote

Now the last page is replaced with the value 7 and the table looks like this know:


Same thing. The mapping for 8 was the second to enter the TLB, so it should be evicted next. Here's the sequence of events (in sequential ascending order) I came up with before looking at what you had. I too got a 30% hit rate.

The first four are all page faults

9 -> miss   TLB = 9
8 -> miss   TLB = 9, 8  
4 -> miss   TLB = 9, 8, 4
5 -> miss   TLB = 9, 8, 4, 5; full

4 -> hit
6 -> miss   page fault: evict 9; TLB = 6, 8, 4, 5
4 -> hit
7 -> miss   page fault; evict 8; TLB = 6, 7, 4, 5
5 -> hit

hits/accesses = 3/9 = .30  

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1