[운영체제] LRU(Least Recently Used Algorithm) Algorithm이란? Python 구현

Cache란 컴퓨터 과학에서 사용하는 '데이터를 미리 복사해 놓는 임시 저장 장소'를 말한다.

원래의 메모리에 접근하는 시간이 오래 걸리거나 값을 재 계산하는 시간을 절약하기 위해 사용한다.

캐시에 미리 값을 복사해 놓는 경우에 빠른 속도로 데이터에 접근할 수 있다.

 

물론 캐시도 물리적 메모리 영역을 가지고 있기 때문에, 유한한 공간을 가진다.

제한된 메모리 영역을 효율적으로 이용하기 위해서는 자주 사용하는 데이터는 빠르게 접근할 수 있도록 하고, 오래 사용되지 않은 데이터는 캐시 영역에서 쫓아버리는 방법을 사용한다.

이러한 캐시 메모리를 관리하는 알고리즘을 LRU(Least Recently Used) Algorithm이라고 한다.

해당 알고리즘은 가장 오랫동안 참조되지 않은 데이터는 앞으로도 사용될 확률이 적다는 가정 하에 이루어진다.

운영체제에서는 페이지 교체 알고리즘으로 활용된다.

출처: https://t4tutorials.com/wp-content/uploads/2018/10/Least-Recently-Used-algorithm-page-replacement-operating-systems-OS-1.jpg

위의 순서처럼 [4,6,8,4,2,6]의 순서대로 데이터에 접근하고 Frame의 길이가 3이라고 할 때, 캐시는 3개의 데이터만 저장할 수 있다.

1️⃣ 데이터(페이지)가 교체될 때 마다 캐시에 빈 공간이 있는 지 확인한다.

2️⃣ 만약 빈 공간이 있다면 데이터를 빈 공간에 저장한다.

3️⃣ 빈 공간이 없다면, 가장 오래동안 참조되지 않은 데이터를 삭제한 뒤 해당 위치를 데이터(페이지)로 교체한다.

 

간단한 알고리즘으로, 파이썬을 이용하여 LRU Algorithm을 구현해보았다.

class LRU:
    cacheSize=0
    cacheHitTime=0
    cacheMissTime=0
    cache=[]

    def __init__(self,cacheSize,cacheHitTime,cacheMissTime):
        self.cacheSize=cacheSize
        self.cacheHitTime=cacheHitTime
        self.cacheMissTime=cacheMissTime

    def get(self,data):
        if self.cacheSize==0:
            return self.cacheMissTime
        data=data.lower()
        if data not in self.cache:
            if len(self.cache)==self.cacheSize:
                self.cache.pop(0)
            self.cache.append(data)
            return self.cacheMissTime
        else:
            self.cache.pop(self.cache.index(data))
            self.cache.append(data)
            return self.cacheHitTime

 

LRU 캐시 교체 알고리즘은 프로그래머스의 카카오 공채 기출 문제에서 직접 활용해볼 수 있다.

programmers.co.kr/learn/courses/30/lessons/17680

코딩테스트 연습 - [1차] 캐시