Skip to main content

Memory characteristics and LRU replacement

Short answer

Memory characteristics: location, capacity, unit of transfer, access method, performance, physical type, volatility, and organization. LRU replacement evicts the block unused for the longest time by tracking usage order. In a 4-block cache with accesses 2,3,2,1,5,2,4,5,3,2,5,2, hits=6, misses=6, hit ratio=0.5.

Explain the major characteristics of memory. Explain the LRU (Least Recently Used) replacement policy with example.

Characteristics of memory

CharacteristicMeaningExamples
LocationWhere the memory is: internal (registers, cache, main memory), external (disk, tape)CPU registers, RAM, HDD
CapacitySize: words or bytes for internal, bytes for external8 GB RAM, 1 TB disk
Unit of transferData moved in one access: word for internal, block for externalWord, block, record
Access methodSequential (tape), direct (disk), random (RAM), associative (cache tag search)Tape, disk, RAM, cache
PerformanceAccess time (latency), memory cycle time, transfer rate = 1 / cycle timeDRAM access: tens of ns
Physical typeSemiconductor, magnetic, optical, magneto-opticalRAM, HDD, CD
Physical characteristicsVolatile or non-volatile; erasable or non-erasableRAM volatile, ROM non-volatile
OrganisationPhysical arrangement of bits into wordsInterleaved memory banks

LRU replacement policy

LRU (Least Recently Used) replaces the cache block that has not been used for the longest time. It uses temporal locality: a block used recently is likely to be used again soon. The hardware keeps an age (or use) counter for each line; on each access the age of the used line is reset and others are increased.

  • Hit: the block is in the cache; no replacement. The block becomes the most recently used.
  • Miss with free line: the block is loaded into a free line and becomes the most recently used.
  • Miss with cache full: the least recently used block is removed and the new block is loaded.

Example: cache of 4 blocks, reference string 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2

Ref  Result            Cache (most recent first)
2    Miss              [2]
3    Miss              [3, 2]
2    Hit               [2, 3]
1    Miss              [1, 2, 3]
5    Miss              [5, 1, 2, 3]
2    Hit               [2, 5, 1, 3]
4    Miss (evict 3)    [4, 2, 5, 1]
5    Hit               [5, 4, 2, 1]
3    Miss (evict 1)    [3, 5, 4, 2]
2    Hit               [2, 3, 5, 4]
5    Hit               [5, 2, 3, 4]
2    Hit               [2, 5, 3, 4]

Hits = 6, misses = 6, hit ratio = 6/12 = 0.50. When 4 was referenced the cache was full and the least recently used block was 3, so 3 was evicted; when 3 came back, block 1 was the least recently used, so 1 was evicted.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Organization and Architecture chapter 6 questions →