티스토리 뷰

반응형
🧠 메모리 관리의 핵심, LRU 알고리즘 완벽 이해

🧠 메모리 관리의 핵심, LRU 알고리즘 완벽 이해



페이지 교체

컴퓨터에서 프로그램을 실행하면 필요한 데이터를 메모리(RAM)에 적재합니다. 메모리는 속도가 빠르지만 용량이 한정적입니다.
실행 도중에 프로그램이 새로운 데이터를 필요로 하는데, 메모리가 이미 가득 차 있다면 어떻게 해야 할까요?
그럴 때는 메모리에 있는 데이터 중 하나를 제거하고 새 데이터를 올립니다.
이 과정을 페이지 교체(Page Replacement)라고 합니다.



페이지 교체 알고리즘

메모리에서 어떤 데이터를 제거할지를 아무렇게나 결정하면 비효율적입니다.
예를 들어 방금 막 사용한 데이터를 제거했다가 바로 다시 필요해진다면 불필요하게 디스크를 또 읽어야 하므로 속도가 느려집니다.
그래서 운영체제는 특정한 기준을 정해 어떤 데이터를 제거할지 결정합니다.
이 기준을 페이지 교체 알고리즘(Page Replacement Algorithm)이라고 합니다.

주요 알고리즘 종류

알고리즘 작동 방식
OPT(Optimal) 앞으로 가장 늦게 쓰일 데이터를 제거
FIFO 메모리에 가장 먼저 들어온 데이터를 제거
LRU 가장 오래 사용하지 않은 데이터를 제거
LFU 사용 횟수가 가장 적은 데이터를 제거
Clock 최근에 사용되지 않은 데이터를 제거

이 중 LRU는 현실에서 많이 쓰이는 방법입니다.



Optimal 알고리즘

Optimal은 가장 이상적인 방법입니다.
앞으로 프로그램이 어떤 데이터를 언제 요청할지 모두 알고 있다고 가정하고, 그중에서 가장 늦게 사용될 데이터를 제거합니다.
예를 들어 냉장고에 음식을 채워 넣어야 할 때, 앞으로 한 달 동안 가족이 뭘 먹을지 미리 안다면 그중 가장 나중에 먹을 음식을 버리는 것입니다.
하지만 실제로는 앞으로 무슨 데이터를 쓸지 알 수 없기 때문에 현실에서는 사용할 수 없습니다.



LRU 알고리즘

정의

LRU는 Least Recently Used의 약자입니다.
메모리에 있는 데이터 중에서 가장 오래 사용하지 않은 데이터를 제거합니다.

등장 배경

운영체제 연구자들은 프로그램이 데이터를 접근하는 데 일정한 패턴이 있다는 것을 발견했습니다.
최근에 사용한 데이터는 앞으로도 곧 다시 쓸 가능성이 높고, 한동안 사용하지 않은 데이터는 당분간 필요 없을 가능성이 높습니다.
냉장고를 예로 들면, 며칠째 손대지 않은 음식은 앞으로도 안 먹을 가능성이 높아 버리기 적당합니다.
이런 현실적인 특성을 활용해 만든 것이 LRU입니다.



LRU 알고리즘의 동작 방식

LRU는 데이터를 요청할 때마다 그 데이터를 가장 최근에 사용한 것으로 표시합니다.
새로운 데이터를 올려야 하는데 자리가 없다면, 표시된 것 중에서 가장 오래전에 사용된 데이터를 제거합니다.

작동 예시

메모리에 3개의 데이터만 담을 수 있다고 가정합니다.
데이터 요청 순서: A B C A D B

요청 메모리 상태 제거 여부
A A
B A B
C A B C
A A B C
D D A B ✅ (C 제거)
B B D A

A, B, C가 모두 메모리에 올라간 상태에서 다시 A가 요청되면 이미 메모리에 있으니 아무 것도 제거하지 않습니다.
하지만 D가 요청되면, 메모리에 자리가 없으니 가장 오래전에 사용한 C를 제거합니다.



페이지 부재

정의

페이지 부재(Page Fault)는 프로그램이 요청한 데이터가 메모리에 없을 때 발생합니다.
메모리에 없으니 디스크에서 데이터를 읽어와야 하고, 이 과정은 메모리보다 매우 느립니다.

“필요한 데이터가 메모리에 없어 디스크에서 가져와야 하는 상황”

영향

페이지 부재가 자주 발생하면 프로그램이 느려지기 때문에, 좋은 페이지 교체 알고리즘으로 페이지 부재를 최소화하는 것이 중요합니다.



LRU 알고리즘의 장점

  • ✅ 직관적이고 이해하기 쉽다
  • ✅ Optimal에 가까운 성능을 낸다
  • ✅ 프로그램이 실제로 데이터를 사용하는 패턴과 잘 맞는다
  • ✅ 구현 가능한 수준에서 효율적이다


LRU 알고리즘의 예제 문제

문제

프레임 크기: 3칸
데이터 요청 순서:
1 2 3 2 4 1 5 2 4 3 1 2

이때 페이지 부재가 몇 번 발생하는지 계산해보세요.

풀이

요청 메모리 상태 페이지 부재
1 1
2 2 1
3 3 2 1
2 2 3 1
4 4 2 3
1 1 4 2
5 5 1 4
2 2 5 1
4 4 2 5
3 3 4 2
1 1 3 4
2 2 1 3

총 페이지 부재 횟수: 10회



요약

항목 내용
페이지 교체 메모리에서 데이터를 제거하고 새 데이터를 적재하는 것
페이지 교체 알고리즘 어떤 데이터를 제거할지 정하는 규칙
Optimal 가장 이상적이지만 현실에서는 불가능
LRU 가장 오래 사용하지 않은 데이터를 제거
장점 직관적, 효율적, 현실적
페이지 부재 메모리에 데이터가 없어 디스크에서 읽어야 하는 상황


반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/10   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함
반응형