페이지 교체 알고리즘 - LRU

페이지 교체 알고리즘 

• 사회의 자원은 한정되어 있고 그 한정된 자원을 효율적으로 사용하기 위해 각종 법과 규칙이 존재합니다. 눈에 확연히 보이지 않아 무한할 것만 같은 컴퓨터 자원도 사실은 제한이 확실하며 그 한도내에서 최고의 효율을 얻기 위해 여러 알고리즘이 존재 합니다. 이 알고리즘을 페이지 교체 알고리즘 이라고 부릅니다.
• 컴퓨터는 보통 주기억 장치인 램과 보조기억 장치인 하드나 ssd 등의 대용량 기억장치를 가지고 있습니다. 램이 속도가 빠르기 때문에 보조기억장치로 부터 데이터를 램에 저장해놓고 램에 있는 데이터를 가지고  빠르게 연산을 합니다. 이 때 램을 같은 크기의 블록으로 구성해서 운용하는데 이 블록을 페이지 라고 부릅니다.
• 만약 cpu 가 계산을 할 때 필요한 데이터가 페이지에 있다면 cache hit 라고 부르며, 없을 경우에는 보조기억장치로부터 데이터를 페이지로 옮겨온 후에 계산을 하는데 이 때를 cache miss 라고 부릅니다. 당연히 hit 일 때 시간이 miss 일 때 시간보다 단축됩니다.
• hit 일 때와 miss 일 때 시간이 차이가 나기 때문에 보다 빠른 연산을 위해선 페이지에 여러 정보중에 어떤 정보를 오래 저장해 놓아야 하는지가 매우 중요한 문제가 됩니다. 램의 자원이 같더라도 어떤 방식의 알고리즘을 사용하느냐에 따라 10초만에 일을 마칠 수도 1분만에 일을 마칠 수도 있기 때문입니다.
• 페이지 교체 알고리즘에는 대표적으로 다음과 같은 종류의 알고리즘 들이 있습니다.
• FIFO ( First In First Out )
• OPT ( OPTimal Page Replacement )
• LRU ( Least Recently Used )
• Count-Based
• LFU ( Least Frequently Used )
• MFU ( Most Frequently Used )

LRU ( Least Recently Used ) - 이론 

• LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다. 페이지에서 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다. 이 알고리즘의 기본 가설은 가장 오랫동안 사용하지 않았던 데이터는 앞으로도 사용할 확률이 적다는 것입니다.

• LRU 알고리즘을 구현하기 위한 첫 번째 방법은 페이지에 저장된 데이터가 언제 사용되었는지를 알 수 있게하는 부분을 구현해서 제일 오랫동안 참조되지 않은 데이터를 제거하는 방법입니다.

• 두 번째 방법은 페이지에 데이터를 큐형식으로 저장하는 방식입니다. 페이지 내에 필요한 데이터가 존재한다면 데이터를 페이지 내에서 제거하고 맨 위로 다시 올리고, 만약 데이터가 존재하지 않는다면 바로 입력하여 맨 아래에 있는 데이터를 삭제하는 과정을 통해 LRU 를 구현할 수 있습니다.

LRU ( Least Recently Used ) - 예제 

• LRU 알고리즘의 상태 변화과정을 나타낸 표 입니다. 페이지 크기가 3이라고 가정하고 0 부터 4 까지의 숫자들이 참조되는 경우를 그렸습니다. 황색 표시는 페이지가 교체 되는 상황이고 연두색은 페이지에 데이터가 존재하여 갱신되는 경우 입니다. 

• 구현과정에서 주의해야할 부분은 7번, 9번 그리고 8번, 10번 정도 입니다. 7번 9번은 페이지에 저장되는 값들은 바뀌지 않지만 최근에 참조되었다는 부분을 알 수 있게 구현해야하며, 8번 10번은 7, 9번이 반영되어 3이 최근에 사용 되었음을 인지한 상태로 다른 페이지를 변경해 주어야 하는 것을 구현해야 합니다.

LRU ( Least Recently Used ) - 구현 

• 간단한 LRU 를 파이썬으로 구현해 보았습니다. 이 코드는 카카오 신입 공채 1차 코딩 테스트에 나온 문제를 위한 코드 이기 때문에 과정만 참조하는 것을 추천합니다.

def calc_cache(cache, string, cache_size):

    try:

        if len(cache) > cache_size:

            if cache.count(string) == 0:

                cache.pop()

                cache[0] += 1

            elif cache.count(string) == 1:

                cache.remove(string)

        else:

            if cache.count(string) == 0:

                cache[0] += 1

        cache.insert(1, string)

    except:

        cache[0] = len(cities)

    finally:

        return cache

• 캐쉬(페이지)를 의미하는 리스트와 참조할 데이터들, 그리고 캐쉬의 크기를 나타내는 변수들이 함수의 파라메터로 사용됩니다.

• 캐쉬 사이즈가 0 일 경우를 예외처리를 해준 부분 입니다.

• 캐쉬에 저장된 값들의 개수가 캐쉬 사이즈 보다 큰 경우와 작은 경우로 나누어 진행하는데, 작은 경우는 캐쉬[0] 의 숫자를 1 증가시키고 참조할 데이터를 넣습니다. 캐쉬[0]은 캐쉬에 데이터가 몇번 없었는지를 의미하는 수 입니다.

• 캐쉬에 저장된 값들의 개수가 캐쉬 사이즈 보다 큰 경우에는 그 참조값이 캐쉬에 있는지 없는지를 구별해서 진행합니다. 있는 경우에는 그 참조값을 캐쉬에서 제외하고 새로 입력하고, 없는 경우에는 맨 마지막 값을 지우고 새 값을 입력합니다.

• 모든 과정을 마친 뒤에는 cache 리스트를 리턴합니다.