[CSE]  Advanced Operating Systems 
 COMP9242 2002/S2 
UNSW

PRINTER Printer-Friendly Version
Administration               
- Notices
- Course Intro
- Consultations
# On-line Survey (closed)
- Survey Results
 
Work
- Lectures
- Milestone 0
- Project Admin
- Project Spec
- Project FAQ
- Exam
 
Documentation
- ASysT Lab
- L4 source browser
- Sulima ISA Simulator
R4x00 ISA Summary 
MIPS R4700 ReferenceMIPS R4000 User Manual 
- Network Driver
- GT64111
 
Related Info
- Aurema OS Prize
- OS Hall of Fame
 
History
- 2000
- 1999
- 1998
 
Staff
- Gernot Heiser (LiC)

 
Valid HTML 4.0!
next up previous
Next: Non-Uniform Memory Architecture (NUMA) Up: 10-smp Previous: Cache Consistency

Subsections

Hardware cache coherency


  • Ensure consistency of all caches and RAM.

Write-invalidate protocols:
 Ensure that:
  • only a single cached copy of the data exist at the time of a store,
  • dirty lines will propagate to memory prior to being read into any other cache.
Write-update protocols:
 Update all cached copies at the time of a store.

  • Note: Similar (software) protocols are used in distributed systems.

Write-through invalidate protocol

Two versions:

  1. All stores write through the cache.
    • RAM is always consistent with cache.
    • No dirty cache lines ever.
  2. Cache snoops bus for write cycles and invalidates any copies.
Normal bus arbitration resolves race conditions.

  • Can cache spin locks, Decker works...
  • Cannot use write-back caching.
  • Need bus cycle for each store ==> limited scalability.

Write-once protocol

Works with write-back caches:

  • First store to clean line writes through cache.
  • Store to uncached line allocates in cache.
  • Further stores to same line only write to cache.
  • Cache snoops bus for write cycles and invalidates any copies.
Normal bus arbitration resolves race conditions.

  • Introduces new state for a cache line: reserved.

Write-once state diagram:

cc-w1

  • Note: Store miss can occur from any state, not only invalid:
  • The line may have held different valid or dirty data.

MESI protocol

Named after initials of states: Modified-Exclusive-Shared-Invalid.

  • Like write-once, except that a load miss on a line which is
    not in any cache goes directly to the exclusive state.

  • Snoop load hits require cache to assert it has the line.

Used in many modern SMP architectures.

Write-invalidate protocols:

  • Based on the assumption that shared data is likely to remain shared.

  • Basic protocol similar to MESI, but:
    • stores to shared data update all copies,
    • updating cache assert share status,
    • move to exclusive state if no other CPU holds copy.

  • MIPS R4000 update protocol includes additional modified-shared state, which updates other caches but not RAM.

Wastes bus cycles if lines cease to be shared.

H/W cache coherency issues

  • On miss may read data from other cache (faster).

  • Some architectures (MIPS R4000) offer choice of protocols.
    • Must chose most appropriate one for application.

  • Cache coherency is based on cache lines.
    • Potential of false sharing.

  • H/W coherency generally restricted to physical caches.
    • No problem with L2 cache.
    • Use inclusion property for L1 cache: \(L_1 \subset L_2\).


next up previous
Next: Non-Uniform Memory Architecture (NUMA) Up: 10-smp Previous: Cache Consistency
Gernot Heiser 2002-10-11