TLB Simulator: LRU Translation Cache

Simulate a tiny Translation Lookaside Buffer (TLB) with LRU replacement.

This is not a full page-table simulator. You only receive a sequence of virtual page numbers. Count how many times the page is already in the TLB.

Function

func TLBHits(capacity int, pages []int) (hits int, misses int)

Rules

• capacity is the maximum number of cached pages.
• If capacity <= 0, every access is a miss.
• On access:
  • If the page is in the cache, it is a hit and becomes most recently used.
  • Otherwise, it is a miss.
  • If the cache is full on a miss, evict the least recently used page.
  • Insert the missed page as most recently used.

Example

capacity = 2
pages    = 1 2 1 3 1 2

Trace:

1 -> miss, cache [1]
2 -> miss, cache [1,2]
1 -> hit,  cache [2,1]
3 -> miss, evict 2, cache [1,3]
1 -> hit,  cache [3,1]
2 -> miss, evict 3, cache [1,2]

Return:

hits = 2
misses = 4

Walkthrough ladder

Invariant

Your cache order should always be least-recently-used on the left and most-recently-used on the right.

State design

For a small simulator, a slice is enough:

cache := []int{}

Searching the slice is acceptable for this learning problem.

Transition

On hit:

remove page from current position
append page at end

On miss:

if full: remove cache[0]
append page at end

Common bug

If you do not move a hit to the most-recently-used position, you implemented FIFO-like behavior, not LRU.