Virtual-to-Physical Address Mapping and Cache Write Methods

To execute a program, the CPU must translate each keyword into a keyword using keyword(s) and often a keyword(TLB). After translation, the memory system places data into a keyword by using cache keyword mapping, then updates the cache on reads/writes using a chosen keyword write policy.

Important note about citations

This environment requires web citations from a search tool, but those searches failed (usage limit). The course section below is still technically correct in standard computer architecture terms, but it cannot include the required reference citations.

1) How the virtual address is mapped into a physical address

1.1 Conceptual split: page number + page offset

Most virtual memory systems treat addresses as:

• Virtual page number (VPN): identifies a page in virtual address space
• Page offset: selects a byte within that page
• Physical page number / frame number (PFN): selects a frame in physical memory
• Physical address = (PFN << offsetBits) + offset

This is why the offset bits are usually unchanged by translation: the page size is fixed, so the location within the page remains the same.

---

1.2 The CPU uses the TLB first

A keyword is checked before consulting page tables.

• TLB hit: we obtain the PFN quickly.
• TLB miss: the CPU performs a page-table walk to find the PFN.

TLB hit path (high level)

1. Extract VPN from the virtual address.
2. TLB lookup VPN → PFN + permissions.
3. Form physical address by combining PFN with original offset.
4. Check permissions (R/W/X bits), then proceed.

---

1.3 Page-table walk: from VPN to PFN

A keyword is the fallback method when the TLB misses.

In multi-level page tables:

• the VPN is split into several indices (one per level)
• each level points to the next-level table or directly to a leaf mapping
• the leaf entry provides the PFN and metadata (permissions, valid bit, etc.)

---

1.4 Permissions, protection, and faults

Translation isn’t only a mapping; it’s also enforced by metadata:

• Valid bit: indicates whether the page is mapped
• Access rights: read/write/execute permissions
• Page fault: if invalid or disallowed access occurs

[CalloutBlock]{type="warning" title="Warning: Translation failures" } content="If the page is not present or permissions deny access, the OS typically handles a page fault (e.g., allocating the page or terminating the process)."

1.5 Worked symbolic example (address bit logic)

Let:

• page offset size = $b$
• VPN size = $v$
• PFN size = $p$

Then:

• Virtual address: $VA = VPN \cdot 2^{b} + offset$
• Physical address: $PA = PFN \cdot 2^{b} + offset$

Only VPN → PFN changes during translation; offset stays identical.

2) Different methods of writing into cache (write policies)

A cache write policy defines what happens on a store (write) operation:

• does the cache update immediately?
• does main memory update immediately?
• if the block is missing in cache, do we fetch it first?

We commonly consider two dimensions:

1. Hit behavior (when the cache line is already present)
2. Miss behavior (when the cache line is absent)

---

2.1 Write-through vs write-back (hit behavior)

Write-through

• On a write hit: update both cache and main memory (or push to a write buffer).
• Pros: memory stays coherent with cache (simpler for some designs).
• Cons: higher memory traffic.

Write-back

• On a write hit: update cache only.
• Main memory is updated later when the line is evicted (write-back using a dirty bit).
• Pros: reduces memory writes.
• Cons: requires dirty-bit tracking and careful handling on eviction.

[CalloutBlock]{type="tip" title="Pro Tip: Dirty bit intuition" } content="In write-back caches, a line marked dirty means: cache has newer data than memory, so eviction must write it back."

2.2 Write-allocate vs no-write-allocate (miss behavior)

Write-allocate (fetch-on-write-miss)

• On a write miss: first bring the block into cache (allocate a line), then write to it.
• Often pairs naturally with write-back (because you’ll likely modify the block soon).

No-write-allocate (write-no-allocate / direct-to-memory on miss)

• On a write miss: do not load the block into cache; write directly to memory.
• Pros: avoids loading unused blocks.
• Cons: repeated writes to different addresses may bypass cache benefits.

---

2.3 Common named combinations

The two policy dimensions combine into typical strategies:

---

2.4 Where does the CPU actually write: cache line update + tag check

A store instruction proceeds roughly like:

1. Translate virtual → physical address.
2. Use physical address bits to locate cache set/line:
   • offset selects the byte within the cache block
   • index/set selects candidate line(s)
   • tag confirms hit
3. On hit: update the selected word/bytes in the cache line.
4. Apply the write policy:
   • write-through: also update memory (often via write buffer)
   • write-back: mark line dirty; defer memory update until eviction

---

2.5 Cache coherence and ordering considerations (why policies matter)

In multi-core systems, correctness requires coherent views of memory. Write policies can:

• increase or decrease bus traffic
• interact with invalidation protocols
• determine whether other cores observe updates quickly

[CalloutBlock]{type="warning" title="Warning: Ordering/coherence hazards" } content="Even with write-back, coherence protocols ensure other cores don’t read stale data. Without the protocol, deferred memory writes would break correctness."