페이지 교체 알고리즘 (FIFO, LRU, LFU, OPT)란? 개념과 비교 분석

페이지 교체 알고리즘 (FIFO, LRU, LFU, OPT)

 

1. 페이지 교체 알고리즘이란?

 운영체제(OS)에서 한정된 메모리(RAM)를 효율적으로 사용하기 위해 가상 메모리(Virtual Memory) 개념을 적용한다. 가상 메모리는 물리적 메모리(RAM)가 부족할 경우, 하드디스크(SSD/HDD)의 일부를 임시 메모리(Swap Space)로 사용하여 실행을 지속할 수 있도록 돕는다. 

 하지만, RAM의 크기가 제한되어 있기 때문에 새로운 프로세스가 실행될 때 필요한 데이터를 저장할 공간이 부족하면 기존 데이터를 삭제해야 한다. 이때, **어떤 데이터를 삭제하고 새로운 데이터를 저장할지를 결정하는 방법이 "페이지 교체 알고리즘(Page Replacement Algorithm)"**이다.

 

✅ 페이지 교체 알고리즘의 필요성

• 효율적인 메모리 관리: RAM이 가득 찬 경우, 불필요한 데이터를 제거하고 필요한 데이터를 저장
• 프로세스 실행 속도 향상: CPU가 자주 사용하는 데이터를 RAM에서 빠르게 접근할 수 있도록 최적화
• 페이지 폴트(Page Fault) 최소화: RAM에 없는 데이터를 불러오기 위해 디스크(가상 메모리) 접근이 자주 발생하면 속도가 느려지므로 이를 줄이는 것이 중요

1-1. 페이지(Page)와 페이지 폴트(Page Fault)란?

✅ 페이지(Page)란?
 운영체제에서 프로세스가 사용하는 메모리를 일정 크기의 블록으로 나눈 단위를 페이지(Page)라고 한다. CPU는 페이지 단위로 메모리를 관리하며, 필요한 페이지가 RAM에 존재하지 않으면 하드디스크에서 불러와야 함

 

✅ 페이지 폴트(Page Fault)란?
 페이지 폴트란, CPU가 요청한 페이지가 RAM에 존재하지 않아 가상 메모리에서 데이터를 불러와야 하는 상황을 의미한다. 페이지 폴트가 자주 발생하면 CPU가 데이터를 기다리느라 속도가 느려지고, 전체적인 시스템 성능이 저하됨

 

📌 페이지 폴트 발생 과정 예시
1️⃣ CPU가 특정 데이터를 요청
2️⃣ 해당 데이터가 RAM에 존재하지 않음 (페이지 폴트 발생)
3️⃣ 운영체제가 가상 메모리(하드디스크)에서 데이터를 RAM으로 로드
4️⃣ CPU가 데이터를 읽고 실행

➡ 페이지 폴트가 많을수록 성능이 저하되므로, 이를 최소화하는 것이 페이지 교체 알고리즘의 핵심 목표

1-2. 페이지 교체 알고리즘이 필요한 이유

 운영체제에서는 한정된 RAM을 효율적으로 관리하기 위해 페이지 교체 알고리즘을 적용한다. 새로운 데이터를 로드할 때 기존 데이터를 제거해야 하는데, 무작위로 삭제하면 중요한 데이터까지 지워질 가능성이 높음. 따라서, 어떤 데이터를 유지하고 어떤 데이터를 삭제할지를 결정하는 전략이 필요

 

✅ 페이지 교체 알고리즘이 중요한 이유

• RAM이 한정된 크기를 가지므로, 불필요한 데이터를 제거하고 필요한 데이터를 유지하는 것이 중요
• 잘못된 데이터 삭제 시, 자주 사용되는 데이터를 다시 불러와야 하므로 성능이 저하됨
• 페이지 폴트를 최소화하여 시스템 성능을 최적화하는 것이 목표

1-3. 페이지 교체 알고리즘의 동작 방식

 페이지 교체 알고리즘은 기본적으로 CPU가 요청한 페이지가 RAM에 없을 경우, 어떤 페이지를 삭제하고 새로운 페이지를 로드할지를 결정하는 방식을 의미한다.

 

✅ 페이지 교체 알고리즘이 동작하는 과정
1️⃣ CPU가 특정 데이터를 요청
2️⃣ 데이터가 RAM에 존재하는지 확인 (캐시 히트 여부 검사)
3️⃣ 존재하지 않으면 페이지 폴트 발생
4️⃣ 운영체제가 새로운 데이터를 RAM에 로드할 공간을 확보하기 위해 기존 데이터를 삭제할 페이지 선택
5️⃣ 페이지 교체 알고리즘을 적용하여 가장 적절한 페이지를 제거
6️⃣ 새로운 데이터를 RAM에 저장하고, CPU가 데이터에 접근하도록 설정

 

📌 실생활 예시: "책장 정리"

• 책장에 책을 보관할 공간이 한정되어 있는데, 새로운 책을 넣기 위해 오래된 책을 제거해야 함
• 어떤 책을 버릴지 결정하는 방식이 페이지 교체 알고리즘과 동일한 개념
  • FIFO(선입선출): 가장 오래된 책을 버림
  • LRU(오랫동안 안 읽은 책을 버림)
  • LFU(잘 안 읽는 책을 버림)
  • OPT(앞으로 가장 필요 없는 책을 버림)

---

2. 주요 페이지 교체 알고리즘 비교

알고리즘	설명	장점	단점
FIFO (First In, First Out)	먼저 들어온 페이지를 먼저 제거	구현이 단순함	최근에 자주 사용하는 페이지도 제거될 가능성이 있음
LRU (Least Recently Used)	가장 오랫동안 사용되지 않은 페이지 제거	최근 사용된 데이터를 유지할 수 있음	실행 속도가 느릴 수 있음 (시간 기록 필요)
LFU (Least Frequently Used)	사용 빈도가 가장 적은 페이지 제거	자주 사용하는 데이터 유지 가능	최근에 많이 사용된 데이터도 제거될 위험이 있음
OPT (Optimal Page Replacement)	앞으로 가장 오랫동안 사용되지 않을 페이지 제거	페이지 폴트 수를 최소화	미래를 예측할 수 없기 때문에 실전 적용이 어려움

 

---

3. FIFO (First In, First Out) 알고리즘

✅ FIFO란?

• 먼저 들어온 페이지를 먼저 제거하는 방식
• 가장 오래된 페이지를 삭제하고, 새로운 페이지를 추가

📌 FIFO 페이지 교체 예제

[페이지 프레임 크기 = 3]

페이지 요청 순서: 1 2 3 4 1 2 5 1 2 3 4 5

1. [1] (Page Fault)
2. [1, 2] (Page Fault)
3. [1, 2, 3] (Page Fault)
4. [2, 3, 4] (Page Fault, 1 제거)
5. [3, 4, 1] (Page Fault, 2 제거)
6. [4, 1, 2] (Page Fault, 3 제거)
...

 

✅ FIFO의 특징

• 구현이 간단하고, 빠르게 동작
• 하지만 자주 사용되는 페이지도 오래되었다는 이유만으로 제거될 수 있음
• Belady's Anomaly(벨라디의 역설): 프레임 개수를 늘려도 페이지 폴트가 감소하지 않을 수 있음

📌 실생활 예시: "식당 대기줄 시스템"

• 먼저 온 손님이 먼저 입장하는 선입선출(First-In, First-Out) 방식

---

4. LRU (Least Recently Used) 알고리즘

✅ LRU란?

• 가장 오랫동안 사용되지 않은 페이지를 제거하는 방식
• 최근에 사용한 페이지는 남겨두고, 오래된 페이지를 삭제

📌 LRU 페이지 교체 예제

[페이지 프레임 크기 = 3]

페이지 요청 순서: 1 2 3 4 1 2 5 1 2 3 4 5

1. [1] (Page Fault)
2. [1, 2] (Page Fault)
3. [1, 2, 3] (Page Fault)
4. [2, 3, 4] (Page Fault, 1 제거)
5. [3, 4, 1] (Page Fault, 2 제거)
6. [4, 1, 2] (Page Fault, 3 제거)
...

 

✅ LRU의 특징

• FIFO보다 더 나은 성능을 제공
• 하지만 최근 사용 여부를 추적해야 하므로, 구현이 복잡하고 추가 메모리 필요

📌 실생활 예시: "스마트폰 최근 사용 앱 목록"

• 최근에 사용한 앱은 리스트 상단에 유지, 오랫동안 사용하지 않은 앱은 리스트에서 사라짐

---

5. LFU (Least Frequently Used) 알고리즘

✅ LFU란?

• 사용 빈도가 가장 적은 페이지를 제거하는 방식
• 자주 사용하는 페이지는 오래 유지되며, 사용 횟수가 적은 페이지가 삭제됨

📌 LFU 페이지 교체 예제

[페이지 프레임 크기 = 3]

페이지 요청 순서: 1 2 3 1 2 4 5 1 2 3 4 5

1. [1] (Page Fault)
2. [1, 2] (Page Fault)
3. [1, 2, 3] (Page Fault)
4. [1, 2, 3] (1, 2 사용 증가)
5. [1, 2, 3] (1, 2 사용 증가)
6. [2, 3, 4] (Page Fault, 1 제거, 사용 빈도 낮음)
...

 

✅ LFU의 특징

• 자주 사용하는 데이터 유지 가능
• 하지만 최근에 급격히 사용된 데이터도 제거될 가능성이 있음

📌 실생활 예시: "자주 가는 웹사이트 북마크"

• 자주 방문한 사이트는 북마크 상단에 유지됨

---

6. OPT (Optimal Page Replacement) 알고리즘

✅ OPT란?

• 미래에 가장 오랫동안 사용되지 않을 페이지를 제거하는 방식
• 이론적으로 가장 적은 페이지 폴트를 발생시킴

📌 OPT 페이지 교체 예제

[페이지 프레임 크기 = 3]

페이지 요청 순서: 1 2 3 4 1 2 5 1 2 3 4 5

1. [1] (Page Fault)
2. [1, 2] (Page Fault)
3. [1, 2, 3] (Page Fault)
4. [1, 2, 4] (Page Fault, 3 제거) -> 향후 사용되지 않음
...

 

✅ OPT의 특징

• 이론적으로 가장 효율적인 알고리즘
• 하지만 미래를 예측할 수 없기 때문에 실전 적용이 어려움