Hierarchical Memory Simulation with Cache

Overview

This project extends the basic message storage system with a cache layer and page replacement algorithms. Messages are stored both in cache (for fast access) and on disk (for persistence).

Configuration

• Message Size: 512 bytes (configurable in config.h)
• Cache Size: 16 messages (configurable in config.h)
• Replacement Policies: RANDOM and LIFO

Build and Run

# Build all programs
make all

# Run original demo (no cache)
make run-demo

# Run original tests (no cache)
make test

# Run cache tests
make test-cache

# Run performance benchmark (1000 random accesses)
make run-benchmark

# Clean up
make clean

Files

Core Implementation

• config.h - System configuration (cache size, message size)
• message.h/c - Basic message storage (disk only)
• cache.h/c - Cache implementation with replacement algorithms
• message_cache.h/c - Integration layer (cache + disk)

Test and Benchmark Programs

• demo.c - Original demonstration (no cache)
• test_message.c - Original tests (no cache)
• test_cache.c - Cache functionality tests
• benchmark.c - Performance evaluation (1000 accesses)

Build System

• Makefile - Build all programs

Design Decisions

Part 1: Caching Strategy

Data Structure: Simple array-based cache with linear search

• Why: Easy to implement, sufficient for small cache (16 slots)
• Alternative (not used): Hash table would be faster but more complex

Cache Behavior:

• Store: Write to both cache and disk
• Retrieve: Check cache first, load from disk on miss
• Lookup: Linear search through valid cache slots

Part 2: Page Replacement Algorithms

RANDOM Replacement:

• Randomly selects a victim when cache is full
• Simple, no tracking overhead
• Performance depends on luck

LIFO Replacement:

• Evicts most recently inserted message
• Tracks insertion order with counter
• Predictable behavior

Why these algorithms:

• Assignment requirement
• Simple to implement
• Good for learning concepts

Part 3: Testing Strategy

Test 1 - Basic Functionality:

• Store and retrieve small number of messages
• Verify cache hits

Test 2 - Cache Overflow:

• Store more messages than cache size
• Verify replacement works

Test 3 - Policy Comparison:

• Compare RANDOM vs LIFO on same workload
• Observe different behaviors

Test 4 - Repeated Access:

• Access same messages multiple times
• Verify high hit ratio

Part 4: Performance Metrics

The benchmark program measures:

• Cache hits per 1000 accesses
• Cache misses per 1000 accesses
• Hit ratio = hits / total accesses

Test configuration:

• 100 total messages stored
• 16 message cache (16% cache ratio)
• 1000 random accesses

Expected results:

• Hit ratio depends on access pattern
• With random access and small cache, expect ~16-20% hit ratio
• RANDOM and LIFO may perform differently

Running the Benchmark

make run-benchmark

Output shows:

• Progress during 1000 accesses
• Total hits and misses
• Hit ratio percentage
• Comparison between RANDOM and LIFO

Memory Management

• All messages properly allocated and freed
• No memory leaks (verify with make test-memory)
• Cache uses fixed-size array (no dynamic allocation)

Notes

• Fixed message size simplifies cache implementation
• No internal fragmentation concerns (fixed size)
• Index file used for fast disk lookups
• Statistics tracked globally for easy access