티스토리 뷰
🧠 메모리 관리의 핵심, LRU 알고리즘 완벽 이해
페이지 교체
컴퓨터에서 프로그램을 실행하면 필요한 데이터를 메모리(RAM)에 적재합니다. 메모리는 속도가 빠르지만 용량이 한정적입니다.
실행 도중에 프로그램이 새로운 데이터를 필요로 하는데, 메모리가 이미 가득 차 있다면 어떻게 해야 할까요?
그럴 때는 메모리에 있는 데이터 중 하나를 제거하고 새 데이터를 올립니다.
이 과정을 페이지 교체(Page Replacement)라고 합니다.
페이지 교체 알고리즘
메모리에서 어떤 데이터를 제거할지를 아무렇게나 결정하면 비효율적입니다.
예를 들어 방금 막 사용한 데이터를 제거했다가 바로 다시 필요해진다면 불필요하게 디스크를 또 읽어야 하므로 속도가 느려집니다.
그래서 운영체제는 특정한 기준을 정해 어떤 데이터를 제거할지 결정합니다.
이 기준을 페이지 교체 알고리즘(Page Replacement Algorithm)이라고 합니다.
주요 알고리즘 종류
이 중 LRU는 현실에서 많이 쓰이는 방법입니다.
Optimal 알고리즘
Optimal은 가장 이상적인 방법입니다.
앞으로 프로그램이 어떤 데이터를 언제 요청할지 모두 알고 있다고 가정하고, 그중에서 가장 늦게 사용될 데이터를 제거합니다.
예를 들어 냉장고에 음식을 채워 넣어야 할 때, 앞으로 한 달 동안 가족이 뭘 먹을지 미리 안다면 그중 가장 나중에 먹을 음식을 버리는 것입니다.
하지만 실제로는 앞으로 무슨 데이터를 쓸지 알 수 없기 때문에 현실에서는 사용할 수 없습니다.
LRU 알고리즘
정의
LRU는 Least Recently Used의 약자입니다.
메모리에 있는 데이터 중에서 가장 오래 사용하지 않은 데이터를 제거합니다.
등장 배경
운영체제 연구자들은 프로그램이 데이터를 접근하는 데 일정한 패턴이 있다는 것을 발견했습니다.
최근에 사용한 데이터는 앞으로도 곧 다시 쓸 가능성이 높고, 한동안 사용하지 않은 데이터는 당분간 필요 없을 가능성이 높습니다.
냉장고를 예로 들면, 며칠째 손대지 않은 음식은 앞으로도 안 먹을 가능성이 높아 버리기 적당합니다.
이런 현실적인 특성을 활용해 만든 것이 LRU입니다.
LRU 알고리즘의 동작 방식
LRU는 데이터를 요청할 때마다 그 데이터를 가장 최근에 사용한 것으로 표시합니다.
새로운 데이터를 올려야 하는데 자리가 없다면, 표시된 것 중에서 가장 오래전에 사용된 데이터를 제거합니다.
작동 예시
메모리에 3개의 데이터만 담을 수 있다고 가정합니다.
데이터 요청 순서: A B C A D B
A, B, C가 모두 메모리에 올라간 상태에서 다시 A가 요청되면 이미 메모리에 있으니 아무 것도 제거하지 않습니다.
하지만 D가 요청되면, 메모리에 자리가 없으니 가장 오래전에 사용한 C를 제거합니다.
페이지 부재
정의
페이지 부재(Page Fault)는 프로그램이 요청한 데이터가 메모리에 없을 때 발생합니다.
메모리에 없으니 디스크에서 데이터를 읽어와야 하고, 이 과정은 메모리보다 매우 느립니다.
“필요한 데이터가 메모리에 없어 디스크에서 가져와야 하는 상황”
영향
페이지 부재가 자주 발생하면 프로그램이 느려지기 때문에, 좋은 페이지 교체 알고리즘으로 페이지 부재를 최소화하는 것이 중요합니다.
LRU 알고리즘의 장점
- ✅ 직관적이고 이해하기 쉽다
- ✅ Optimal에 가까운 성능을 낸다
- ✅ 프로그램이 실제로 데이터를 사용하는 패턴과 잘 맞는다
- ✅ 구현 가능한 수준에서 효율적이다
LRU 알고리즘의 예제 문제
문제
프레임 크기: 3칸
데이터 요청 순서:
1 2 3 2 4 1 5 2 4 3 1 2
이때 페이지 부재가 몇 번 발생하는지 계산해보세요.
풀이
총 페이지 부재 횟수: 10회
요약
'정보처리기사 > 페이지 교체 알고리즘' 카테고리의 다른 글
FIFO 페이지 교체 알고리즘 (0) | 2025.07.13 |
---|---|
[페이지 교체]LFU(Least Frequently Used) 방법 정리! (0) | 2025.07.12 |
- Total
- Today
- Yesterday
- Python
- c언어
- DP
- dfs
- 백준
- 그리디알고리즘
- 문제풀이
- 문자열처리
- 문제 풀이
- C++
- 객체지향
- 코딩 테스트
- 파이썬문제풀이
- 파이썬코딩
- 코딩테스트
- 브루트포스
- python 알고리즘
- 코딩
- 프로그래밍
- 알고리즘기초
- c++알고리즘
- 알고리즘 문제풀이
- 동적 계획법
- 그리디
- 파이썬
- C++ 알고리즘
- 동적계획법
- 알고리즘문제풀이
- 그래프 탐색
- 알고리즘
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |