페이지 교체 알고리즘에는 어떤 것들이 있나요?

김상욱·2024년 11월 30일

페이지 교체 알고리즘에는 어떤 것들이 있나요?

페이지 교체 알고리즘은 메모리 관리 시 효율적인 페이지 교체를 위해 사용.

FIFO(First In, First Out)
가장 먼저 들어온 페이지를 먼저 내보내는 방식으로 큐를 사용하여 관리하고 구현 쉬움. 단, 오래된 페이지가 여전히 자주 사용되는 경우 제거된 페이지를 다시 로드해야 하므로 페이지 폴트가 증가할 수 있다. 또한 Belady's Anomaly 발생 가능성.
: Belady's Anomaly - 일반적으로 메모리 프레임(Frame)의 수가 증가하면 페이지 폴트가 줄어드는 것이 정상이지만 오히려 증가하는 현상. 프레임이 증가해도 가장 오래된 페이지만 제거하기 때문에 메모리 상태를 고려하지 못하기 때문.

Optimal(OPT)
앞으로 가장 나중에 사용될 페이지를 교체하는 방식
-> 이상적으로 최적의 성능 제공하지만 미래의 참조를 미리 알아야 하므로 실제 구현 불가.

LRU(Least Recently Used)
가장 오랫동안 사용되지 않은 페이지를 교체
-> 과거의 참조를 기반으로 페이지를 교체하여 실질적인 환경에서 좋은 성능 제공. 구현이 복잡하고, 참조 시점을 저장하거나 정렬해야 하므로 오버헤드 발생

LFU(Least Frequently Used)
가장 참조 횟수가 적은 페이지를 교체
-> 사용 빈도를 기준으로 교체하여 성능 향상. 참조 횟수를 지속적으로 관리해야 하므로 이 부분에서 오버헤드.

MFU(Most Frequently Used)
참조 횟수가 가장 많은 페이지를 교체
-> 자주 사용된 페이지는 오히려 앞으로 필요하지 않을 가능성이 있다고 가정. 모든 상황에서 통하지 x

Clock(Second Chance)
FIFO를 개선한 방식으로, 각 페이지에 참조 비트를 두고 교체 여부를 결정. 참조 비트가 0인 페이지를 교체하며, 시계 바늘처럼 순환하며 검사. 단, 참조 비트를 확인하는 추가 작업 필요.
-> 페이지가 이미 메모리에 존재하면 해당 페이지의 참조 비트를 1로 설정 없으면 페이지 폴트가 발생하고 교체 프로세스 -> 현재 시계 바늘(pointer)가 가리키는 페이지의 참조 비트를 확인. 참조 비트가 0이면 해당 페이지를 교체. 참조 비트가 1이면 해당 페이지를 건너뛰고, 참조 비트를 0으로 초기화. 다음 페이지로 이동. -> 이 과정 반복. 교체가 결정된 자리(참조 비트가 0인 페이지)에 새 페이지를 삽입하고 참조 비트를 1로 설정

NRU(Not Recently Used)
참조 비트와 수정 비트를 기반으로 교체할 페이지를 결정. 페이지를 4개의 클래스로(00, 01, 10, 11)로 나누어 교체 순서 결정. 이것도 비트관리 작업 필요.
-> 운영 체제가 일정 주기로 참조 비트를 초기화. 수정 비트는 페이지가 디스크에 쓰여졌는지 여부에 따라 변경 -> 모든 페이지를 참조 비트와 수정 비트 조합에 따라 클래스로 나눔. -> 가장 낮은 클래스부터(0부터)의 페이지를 선택 -> 선택된 페이지를 교체하며 참조 비트와 수정 비트를 초기화. 클래스가 같으면 임의로 선택.

WS(Working Set)
현재 실행 중인 프로세스가 필요한 페이지 집합(Working Set)을 유지하려고 시도. 지역성을 기반으로 동작하며, 특정 기간 동안 참조된 페이지만 유지. 구현 복잡성 증가.
: 지역성이란 프로그램 실행 중 특정 시간에 참조되는 메모리 주소들이 특정 범위에 집중되는 성질.
: 시간적 지역성 : 최근에 참조되는 페이지가 가까운 미래에 다시 참조될 가능성이 높음.
: 공간적 지역성 : 특정 주소가 참조되면 그 주변 주소들도 참조될 가능성이 높음.
: Working Set : 프로세스가 일정 시간 동안 참조한 모든 페이지의 집합

Aging Alorithm
LRU를 근사화한 알고리즘으로, 각 페이지에 카운터를 사용하여 교체 여부를 결정. 참조 비트를 주기적으로 확인하여 카운터를 갱신. LRU와 유사한 성능을 제공하면서 오버헤드 감소시키지만 구현이 복잡.
-> 모든 페이지는 8비트의 카운터를 가짐. 초기 상태 각 페이지 카운터는 0. -> 운영 체제가 일정 주기마다 참조 비트를 확인하고, 해당 값을 카운터에 반영.
: -> 시프트 연산으로 카운터의 모든 비트를 오른쪽으로 이동(가장 오래된 참조 정보는 사라지고 새 정보가 추가) -> 참조 비트를 가장 왼쪽 비트로 추가 -> 각 페이지의 참조 비트를 0으로 초기화
-> 페이지 교체가 필요할 때, 모든 페이지의 카운터 값을 비교하여 가장 작은 값을 서낵. 해당 페이지를 교체하고 새 페이지의 카운터를 0으로 초기화.

백엔드 개발자가 실습 가능한 방향

운영체제의 페이지 교체 알고리즘을 백엔드 개발자가 실습하려면, 캐싱 시스템 구현 및 알고리즘 최적화와 연결지을 수 있습니다. 아래는 실습 아이디어입니다:

1. 캐싱 시스템 시뮬레이션

캐싱은 페이지 교체와 유사한 원리로 동작합니다. 이를 구현하면 알고리즘을 실습하면서도 실무에 가까운 경험을 쌓을 수 있습니다.

실습 예제:

목표: Java로 FIFO, LRU, LFU 캐싱 전략을 구현.
구현 방법:
1. 캐시 크기를 설정 (예: 3개의 페이지만 유지 가능).
2. 페이지를 요청할 때 캐시가 가득 차면 교체 알고리즘으로 처리.
3. 각 알고리즘별로 교체 과정을 출력.

코드 예제: LRU 캐싱

import java.util.*;

class LRUCache {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true);
    }

    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        if (cache.size() >= capacity && !cache.containsKey(key)) {
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        cache.put(key, value);
    }

    public void displayCache() {
        System.out.println("Cache: " + cache.keySet());
    }

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

        cache.put(1, 100);
        cache.put(2, 200);
        cache.put(3, 300);
        cache.displayCache(); // [1, 2, 3]

        cache.get(1); // Access key 1
        cache.put(4, 400); // Add key 4, evict least recently used key (2)
        cache.displayCache(); // [3, 1, 4]
    }
}

2. 데이터베이스 쿼리 캐싱

Spring과 MyBatis/Hibernate를 사용한 환경에서 쿼리 캐싱을 직접 실습할 수 있습니다.

목표: 쿼리 결과를 캐싱하여 데이터베이스 호출을 줄이고 성능 개선.
연결성: 페이지 교체 알고리즘으로 캐시 관리 최적화 가능.

Spring 실습 아이디어:
1. Spring Cache를 설정하여 쿼리 결과를 캐싱.
2. Redis를 사용해 캐싱 알고리즘을 구현하고, TTL(Time To Live) 설정을 통해 캐시 교체 시점을 설정.
3. Redis의 LRU 정책과 비교 실습.

3. API 응답 캐싱

API 요청 시 자주 사용되는 데이터(예: 인기 게시글, 사용자 랭킹)를 캐싱하는 로직에 페이지 교체 알고리즘을 도입.

실습 예제:

REST API에 LRU 알고리즘을 추가하여 캐싱된 데이터를 반환.
새 데이터가 들어오면 교체 로직으로 처리.

4. 멀티스레드 환경에서의 캐시 관리

페이지 교체 알고리즘을 멀티스레드 환경에서 동작하도록 구현.

Java의 ConcurrentHashMap을 사용하여 동시성 문제를 해결.
다수의 스레드가 캐시를 요청하고 교체하는 시뮬레이션.

실무 활용 가능성

캐싱 시스템:
- Redis, Memcached 등에서 캐싱 최적화.
- API 서버의 데이터 반환 성능 향상.
데이터베이스 최적화:
- DB 쿼리 결과 캐싱 및 교체 알고리즘 도입.
분산 시스템:
- 분산 캐시에서 교체 알고리즘 구현 및 실험.

정리

운영체제에서 사용되는 페이지 교체 알고리즘은 Java 및 Spring 백엔드 개발에서 캐싱 전략과 성능 최적화 측면에서 응용 가능하며, 다음 실습을 통해 학습할 수 있습니다:

Java로 페이지 교체 알고리즘 구현.
Spring과 Redis를 활용한 캐싱 실습.
API 응답 최적화.

이 과정에서 실무에서도 유용한 경험을 쌓을 수 있습니다. 추가적으로 도움이 필요하면 말씀해주세요! 😊

김상욱

이전 포스트

가상 메모리(Virtual Memory)란 무엇인가요?

다음 포스트

페이지 교체 알고리즘에는 어떤 것들이 있나요?