캐시 메모리

// 직접 매핑(Direct Mapped) 캐시 구현
// 캐시 크기: 4슬롯 / 메모리 블록: 16개
#define CACHE_SIZE  4
#define MEM_SIZE    16

typedef struct {
    int  valid;      // 유효 비트 (데이터가 있으면 1)
    int  dirty;      // Dirty 비트 (Write-Back: 캐시가 메모리와 불일치하면 1)
    int  tag;        // 태그 (어느 메모리 블록인지)
    int  data;       // 실제 데이터
} CacheSlot;

CacheSlot cache[CACHE_SIZE];
int       memory[MEM_SIZE];

// 직접 매핑: 슬롯 인덱스 = 블록 주소 % CACHE_SIZE
int cache_read(int addr) {
    int index = addr % CACHE_SIZE;   // 슬롯 결정
    int tag   = addr / CACHE_SIZE;   // 태그 계산

    if (cache[index].valid && cache[index].tag == tag) {
        /* ✅ Cache Hit — 캐시에서 바로 반환 */
        return cache[index].data;
    }

    /* ❌ Cache Miss — 교체 전 dirty 슬롯이면 메모리에 write-back */
    if (cache[index].valid && cache[index].dirty) {
        int evict_addr = cache[index].tag * CACHE_SIZE + index;
        memory[evict_addr] = cache[index].data; // Write-Back
    }
    cache[index].valid = 1;
    cache[index].dirty = 0;  // 읽기로 적재 → clean
    cache[index].tag   = tag;
    cache[index].data  = memory[addr];
    return cache[index].data;
}

// Write-Through: 캐시와 메모리 동시 갱신 → dirty bit 불필요
void cache_write_through(int addr, int val) {
    int index = addr % CACHE_SIZE;
    int tag   = addr / CACHE_SIZE;

    cache[index].valid = 1;
    cache[index].dirty = 0;  // 항상 메모리와 동기화 → clean
    cache[index].tag   = tag;
    cache[index].data  = val;  // 캐시 갱신
    memory[addr]       = val;  // 메모리 동시 갱신
}

// Write-Back: 캐시만 갱신하고 dirty bit 설정
// 교체 시점에 dirty=1 슬롯만 메모리에 반영
void cache_write_back(int addr, int val) {
    int index = addr % CACHE_SIZE;
    int tag   = addr / CACHE_SIZE;

    cache[index].valid = 1;
    cache[index].dirty = 1;  // 메모리와 불일치 → dirty 표시
    cache[index].tag   = tag;
    cache[index].data  = val;  // 캐시만 갱신
    // memory[addr]는 교체 시 dirty=1 확인 후 반영 (cache_read 참조)
}

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * LRU(Least Recently Used) 캐시 구현
 * LinkedHashMap의 accessOrder=true를 활용해
 * 접근 순서 기반으로 자동 정렬
 */
public class LRUCache<K, V> {

    private final int capacity;
    private final LinkedHashMap<K, V> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // accessOrder=true: get() 호출 시 해당 항목을 맨 뒤로 이동
        this.map = new LinkedHashMap<>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
                return size() > capacity; // 용량 초과 시 가장 오래된 항목 자동 제거
            }
        };
    }

    /** 캐시 조회 — Hit: 값 반환 / Miss: null */
    public V get(K key) {
        return map.getOrDefault(key, null);
    }

    /** 캐시 적재 — 용량 초과 시 LRU 항목 자동 제거 */
    public void put(K key, V value) {
        map.put(key, value);
    }

    /** 현재 캐시 상태 출력 (MRU → LRU 순) */
    public void printCache() {
        System.out.println("Cache: " + map);
    }
}

// 사용 예시
class Main {
    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(4);

        cache.put("A", 10);  cache.printCache(); // [A]
        cache.put("B", 20);  cache.printCache(); // [A, B]
        cache.get("A");       cache.printCache(); // [B, A] ← A가 MRU로
        cache.put("C", 30);  cache.printCache(); // [B, A, C]
        cache.put("D", 40);  cache.printCache(); // [B, A, C, D] ← 풀
        cache.put("E", 50);  cache.printCache(); // [A, C, D, E] ← B 제거(LRU)
    }
}