가상 메모리

#include <stdio.h>
#include <string.h>
#include <limits.h>

#define N_FRAMES 3
#define N_REFS   13

int refs[N_REFS] = {7,0,1,2,0,3,0,4,2,3,0,3,2};

int lru() {
    int frames[N_FRAMES];
    int lastUsed[N_FRAMES]; // 각 프레임의 마지막 사용 시각
    int faults = 0;

    memset(frames,   -1, sizeof(frames));
    memset(lastUsed, -1, sizeof(lastUsed));

    for (int i = 0; i < N_REFS; i++) {
        int pg  = refs[i];
        int hit = 0;

        /* 1. Hit 확인 */
        for (int f = 0; f < N_FRAMES; f++) {
            if (frames[f] == pg) {
                lastUsed[f] = i;   // 사용 시각 갱신
                hit = 1;
                break;
            }
        }

        if (!hit) {
            faults++;
            /* 2. 빈 프레임 먼저 */
            int slot = -1;
            for (int f = 0; f < N_FRAMES; f++) {
                if (frames[f] == -1) { slot = f; break; }
            }

            /* 3. 빈 프레임 없으면 LRU 교체 */
            if (slot == -1) {
                int minTime = INT_MAX;
                for (int f = 0; f < N_FRAMES; f++) {
                    if (lastUsed[f] < minTime) {
                        minTime = lastUsed[f];
                        slot    = f;
                    }
                }
            }

            frames[slot]   = pg;
            lastUsed[slot] = i;
        }

        /* 상태 출력 */
        printf("ref=%d [%s] frames: ",
               pg, hit ? "HIT  " : "FAULT");
        for (int f = 0; f < N_FRAMES; f++) {
            if (frames[f] >= 0) printf("%d ", frames[f]);
            else              printf("- ");
        }
        printf("\n");
    }
    return faults;
}

int main() {
    int f = lru();
    printf("총 페이지 폴트: %d / %d\n", f, N_REFS);
    return 0;
}

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

/**
 * LinkedHashMap의 accessOrder=true로 LRU 캐시 구현
 * OS 페이지 교체의 사용자 공간 유사체 — HashMap보다 접근 순서 보장
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

    public LRUCache(int capacity) {
        // accessOrder=true: get/put 호출 시 해당 항목을 tail(최근)로 이동
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    // 용량 초과 시 가장 오래된(head) 항목 제거 — 페이지 교체에 해당
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        int[] refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
        int faults = 0;

        for (int pg : refs) {
            boolean hit = cache.containsKey(pg);
            if (!hit) {
                faults++;
                cache.put(pg, "P" + pg);  // 용량 초과 시 자동으로 LRU 제거
            } else {
                cache.get(pg);             // accessOrder=true: 접근 시 tail로 이동
            }
            System.out.printf("ref=%d [%s] frames=%s%n",
                pg, hit ? "HIT  " : "FAULT", cache.keySet());
        }
        System.out.println("총 폴트: " + faults);
    }
}