페이지 교체 알고리즘

페이지가 부재하여 새로운 페이지를 할당하기 위하여 사용하는 알고리즘이다. 페이지 부재가 발생하여 새로운 페이지를 적재해야 하는데 사용하고 있는 캐시가 꽉 차 있을 경우 어떤 페이지를 제거할 지 선택할 때 사용한다.

LRU(Least Recently Used)

이름에서 유추할 수 있듯이 페이지 제거 대상이 가장 오래된 페이지이다. 가장 오래된 페이지는 앞으로도 사용할 확률이 적다는 가정 하에 사용한다.

구현

• 빨강 형광펜: MISS
• 하늘 형광펜: HIT
• 캐시의 위부터 최신순

CODE

cacheSize = 3
reference = [4, 2, 3, 4, 5, 6, 5, 4, 7]
cache = []
for ref in reference:
  if not ref in cache:
    if len(cache) < cacheSize:
        cache.append(ref)
     else:
        cache.pop(0)
        cache.append(ref)
  else:
    cache.pop(cache.index(ref))
    cache.append(ref)

참고

링크텍스트