페이지 교체 알고리즘, LRU

페이지 교체 알고리즘

이 과정이 조금 더 구체적이었으면 valid bit 0으로 바꾸고~~ FIFO가 왜 채택되지 않는지 이유!

요구 페이징 시스템은 프로세스가 특정 페이지를 요구할 때 해당 페이지를 물리 메모리에 로딩합니다.

메모리에 필요한 페이지가 있을 때는 잘 진행되지만, 없을 경우에는 문제가 생깁니다. 프로세스가 필요로 하는 페이지가 없는 경우 페이지 폴트(page fault)가 발생하고 HDD에서 필요한 페이지를 찾아 빈 프레임에 로딩하는데, 여기서 또 다시 페이지를 올릴 빈 프레임이 없을 경우 문제에 직면할 수 있습니다.

이 때 사용하는 것이 새로 올릴 페이지와 교체할 희생 프레임을 찾는 알고리즘이 페이지 교체 알고리즘입니다.

LRU(Least-Recently-Used)

직역하여 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다.

최적 알고리즘은 실제 구현이 불가능하므로, 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘입니다.

최적 알고리즘은 페이지가 사용될 시간을 미리 알고 있는 것입니다. 미리 아는 것이 불가능하다면, 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측하여 교체하는 것은 가능합니다. 예측 방법으로 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식을 사용하는 것입니다.

LRU는 최적 알고리즘보다 페이지 교체 횟수가 높지만 FIFO 알고리즘보다 효율적입니다.
LRU 알고리즘은 많은 운영체제가 채택하는 알고리즘이며, 좋은 알고리즘이라고 평가 받고 있습니다.

• 4번째 (2,0,1)의 경우 가장 오랫동안 사용하지 않은 1을 3으로 교체합니다.
• 5번째 (2,0,3)의 경우 페이지에 오래 머물러 있던 0이 교체되지 않고 왜 2가 4로 교체되는지 의문을 가질 수 있습니다. 그 이유는 0은 현재 페이지 폴트가 아니고 실제 사용하고 있는 페이지이기 때문입니다. 3 직전에서 0을 참고하고 있다는 뜻입니다.

실제 코딩 테스트에서 사용하는 사례

2018 카카오 공채 1차 캐시

function solution(cacheSize, cities) {
    let answer = 0;
    const cache = [];
    
    while(cacheSize !== 0 && cities.length !== 0){
        const city = cities.shift().toLowerCase();
        const idx = cache.findIndex((x)=>(x === city));
        if(idx === -1){
            if(cache.length >= cacheSize)
                cache.shift();
            answer = answer + 5;
        }
        else{
            cache.splice(idx, 1);
            answer = answer + 1;
        }
        cache.push(city);
    }
    return cacheSize === 0 ? cities.length * 5 : answer;
}

참고자료

bruney.log