캐시 시뮬레이션 문제는 메모리 계층 구조의 핵심 개념을 검증하는 대표적인 알고리즘 문제입니다. 이 글에서는 C++를 활용해 집합-연관 매핑 방식의 캐시를 모델링하고, LRU(Least Recently Used) 교체 정책을 적용하는 방법을 살펴봅니다.

문제 개요

주어진 메모리 주소 스트림에 대해 캐시 히트/미스를 판정하고, 미스 발생 시 LRU 알고리즘으로 블록을 교체해야 합니다. 쓰기 정책은 write-back 방식을 채택하며, 더티 비트를 통해 메모리와의 동기화 여부를 추적합니다.

핵심 설계 요소

저장소 구성

캐시는 집합(set) 단위로 분할됩니다. 각 집합은 n개의 블록을 수용하며, 전체 N개 집합으로 구성됩니다. 주소 pos의归속 집합은 다음 공식으로 산출됩니다:

set_idx = (pos / blocks_per_set) % N

필요한 자료구조는 다음과 같이 준비합니다:

• group[NN]: 각 집합에 현재 적재된 블록 번호를 보관하는 unordered_set
• history[NN]: 접근 시각과 블록 번호를 저장하는 set<pair<int,int>>, 자동 정렬로 최소값 추출 가능
• last_access[pos]: 블록별 최근 접근 시각 기록
• dirty[pos]: 블록의 수정 여부 표시

교체 로직

집합이 가득 찬 상태에서 미스가 발생하면, history에서 가장 오래된 항목을 제거합니다. 해당 블록이 수정된 적이 있다면 메모리로의 기록이 선행되어야 합니다.

void evict(int set_id) {
    auto oldest = history[set_id].begin();
    int block = oldest->second;
    
    if (dirty[block]) {
        printf("1 %d\n", block);
        dirty[block] = 0;
    }
    
    group[set_id].erase(block);
    history[set_id].erase(oldest);
}

블록 적재

새로운 블록을 캐시에 반입할 때는 메모리로부터 읽어옴을 알리고, 집합 내에 등록합니다.

void load(int set_id, int block) {
    printf("0 %d\n", block);
    group[set_id].insert(block);
}

전체 처리 흐름

각 명령어를 순회하며 다음 절차를 수행합니다:

1. 현재 시각을 증가시키고, 명령 유형과 블록 번호를 해석
2. 쓰기 명령이라면 더티 비트를 설정
3. 목표 집합 인덱스를 계산
4. 해당 블록이 집합 내에 존재하는지 확인
   • 존재(히트): 기존 접근 기록을 history에서 제거
   • 부재(미스): 집합이 꽉 찼으면 evict 호출 후 load 수행
5. 새로운 접근 시각으로 갱신하여 history에 삽입

완성 코드

#include <bits/stdc++.h>
using namespace std;

const int MAX_SETS = 100005;

int ways, num_sets, queries;
int clock_tick;

unordered_set<int> group[MAX_SETS];
set<pair<int,int>> history[MAX_SETS];

unordered_map<int,int> last_access;
unordered_map<int,bool> dirty;

void replace_lru(int sid) {
    auto it = history[sid].begin();
    int victim = it->second;
    
    if (dirty[victim]) {
        cout << 1 << ' ' << victim << '\n';
        dirty[victim] = false;
    }
    
    group[sid].erase(victim);
    history[sid].erase(it);
}

void fetch(int sid, int block) {
    cout << 0 << ' ' << block << '\n';
    group[sid].insert(block);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> ways >> num_sets >> queries;
    
    while (queries--) {
        ++clock_tick;
        
        int op, addr;
        cin >> op >> addr;
        
        if (op == 1) dirty[addr] = true;
        
        int sid = (addr / ways) % num_sets;
        
        if (group[sid].count(addr)) {
            history[sid].erase(history[sid].find({last_access[addr], addr}));
        } else {
            if ((int)group[sid].size() == ways) {
                replace_lru(sid);
            }
            fetch(sid, addr);
        }
        
        last_access[addr] = clock_tick;
        history[sid].insert({clock_tick, addr});
    }
    
    return 0;
}

포인트 정리

set의 정렬 특성을 활용하면 별도의 우선순위 큐 없이도 O(log n)으로 최소값 접근이 가능합니다. 다만 기존 기록을 갱신할 때는 반드시 삭제 후 재삽입하는 과정을 거쳐야 하며, 이 과정에서 잘못된 반복자를 참조하지 않도록 주의해야 합니다.