LRU 알고리즘과 페이지(Page)

김코·2026년 2월 8일

운영체제

운영체제 메모리 관리에서의 LRU(Least Recently Used) 알고리즘

관리가 필요한 이유

컴퓨터 메모리는 한정되어 있고 컴퓨터는 메모리 자원을 효율적으로 관리해야 한다. 이때 어떤 데이터를 내보낼 것인가는 성능에 있어 매우 중요하다.

필요 사전 개념

메모리 관리에 관한 내용을 보면 '페이지' 개념이 나온다. 이를 책으로 비유해보면 다음과 같다.

메모리: 책상
페이지: 책의 낱장(종이 한 장)
프로세스: 여러 장의 페이지로 이뤄진 책
프레임: 책상 위에 페이지 딱 한 장만 놓을 수 있는 구역

프로그램 크기가 커지면 메모리에 다 들어가지 못한다. 따라서 프로그램을 일정한 단위로 쪼개서 필요한 부분만 메모리에 올린다. 이때 쪼개진 일정한 크기의 조각을 '페이지'라고 부른다.

왜 '페이지'라는 이름일까?

책의 페이지는 크기가 고정이다. OS의 페이지도 마찬가지로 고정된 크기를 갖고 있다. 크기가 같아야 프레임(메모리)의 칸에 맞게 끼워넣을 수 있다.

책의 23페이지를 읽다가 100페이지로 넘어갈 수 있는 것처럼 메모리에 페에지도 여기저기 빈 공간에 흩어져 잇다가 OS가 '페이지 테이블'을 보고 찾아 낼 수 있다.

프레임은?

페이지는 데이터를 잘라놓은 조각인 논리적 단위라면, 프레임은 페이지 하나가 들어갈 수 있는 실제 구멍인 물리적 단위이다.

따라서 프레임 하나에 여러 페이지가 들락날락 하는 것이다. 프레임은 한정되어 있고, 수많은 페이지들이 그 자리를 차지하기 위해 경쟁한다.

LRU 알고리즘 개념

LUR 알고리즘은 페이지 교체 알고리즘 중에 하나이며, 최근에 사용하지 않는 페이지를 가장 먼저 내려 보내는 알고리즘이다. (가장 오랫동안 사용되지 않은 데이터 제거)

여기에 최근에 참조된 데이터는 곧 다시 참조될 가능성이 있고, 반대로 오랫동안 참조되지 않은 데이터는 앞으로도 사용될 가능성이 낮다는 '시간 지역성' 개념이 들어간다.

위의 그림을 보면 페이지 크기는 3이고 0부터 4까지 숫자들이 참조되고 있다.
시간 1에서 참조값 0이 페이지에 들어가고 이후 시간 2,3에서 각각의 참조값이 들어간다.

시간이 4일 때 참조값은 3이지만 페이지가 꽉 차있으므로 가장 오래된 시간1에서의 참조값 0을 밀어내고 그 자리를 시간4의 참조값 3이 차지한다.

시간 7이 되었을 때 참조값 3이 들어가고자 하는데, 이미 시간6에서의 페이지를 보면 3이 존재한다.
이때는 이미 존재하기에 cached hit가 발생해 시간7에서의 참조값 3은 가장 최근 순서가 된다.
추가로 시긴7에서의 참조값 3이 이미 앞에서 있었기 때문에 페이지 부재가 발생하지 않는다

따라서 시간 8에서의 참조값 2가 들어올 때 페이지에서 3이 아닌 4가 교체되어 참조값 2가 그 자리를 차지하게 된다.