[운영체제] 페이지 교체 알고리즘 (FIFO, LRU, LFU)

🥤 코카콜라 맛있다 알고리즘 또 먹지!

FIFO / LRU / LFU 페이지 교체 알고리즘 쉽게 이해하기

 

메인 메모리가 넉넉하지 않은 세상에서…
운영체제는 매일 고민합니다.

메모리가 부족한데…
어떤 페이지를 내보낼까…?

 

"코카콜라 맛있다~ 알아맞춰 보세요~ 딩동댕동!" 🥤

하고 랜덤으로 고르면 편하겠지만 😏

 

운영체제는 나름의 기준과 전략에 따라,
신중하게 교체할 페이지(victim page)를 선택하게 됩니다.

 

이때 등장하는 것이 바로 오늘의 주인공.. 

   ✨ 페이지 교체 알고리즘 ✨

 

오늘은 메인 메모리의 공간이 부족할 때
어떤 페이지를 내보낼지 결정하는
FIFO / LRU / LFU
세 가지에 대해 알아보도록 하겠습니다!

---

📌 페이지와 프로세스 차이점 빠르게 알고 넘어가기

운영체제 공부하다 보면

음.. 페이지? 프로세스? 둘이 같은 건가? 🤔 

하며 헷갈릴 때가 있습니다.

 

그래서 빠른 요약 들어갑니다!

✅  프로세스(Process)

• 프로그램이 실행되면서 메모리에 올라온 작업 단위
• 프로세스 하나가 여러 개의 페이지로 구성됨

✅  페이지(Page)

• 프로세스가 사용하는 메모리 공간을 일정한 크기로 자른 조각
• 운영체제는 프로세스를 통째로 메모리에 올리지 않고,필요한 페이지 단위로 메모리에 적재함

즉,

프로세스 = 여러 페이지들의 집합
교체되는 대상은 프로세스가 아니라 그안에 들어있는 페이지 한 조각 ✨

---

🚶‍♂️ FIFO _ "자자, 줄 서세요~"

📌 FIFO 페이지 교체 알고리즘

FIFO는 First In First Out 의 약자로,

가장 먼저 메모리에 적재된 페이지를 먼저 교체 대상으로 선택하는 알고리즘입니다.

 

즉, 

FIFO는 큐 구조로 구현되며, 새로운 페이지가 들어올 때 가장 오래된 페이지를 내보냅니다

 

💡이때, 가장 오래된 페이지는 스왑 영역으로 가게 되는데, 
스왑 영역으로 보낼 대상 페이지를 victim page라고 합니다

 

✅ FIFO 알고리즘 특징

• 단순하며 구현하기가 쉽다.
• 지역성(Locality)을 고려하지 않는다. 
• 사용 패턴 분석을 하는 것이 아니라 단순히 오래된 페이지를 교체한다.
• 메모리를 늘렸을 때 성능이 안 좋아질 수 있다.
• 들어온 순서를 Queue에 저장함으로써 구현할 수 있다.

 

📊 총 페이지 부재 횟수: 7번

---

😴  LRU _ "오래기다렸지?"

📌 LRU 페이지 교체 알고리즘

LRU는 Least Recently Used 의 약자로,

접근된 지 가장 오래된 페이지를 교체하는 알고리즘입니다.

 

💡LRU는 FIFO에 비해 페이지 부재(Page Fault)가 적게 발생할 가능성이 높습니다

FIFO는 자주 쓰이더라도 선입선출에 의해 교체될 수 있는 반면,
LRU는 오래 사용되지 않은 페이지를 우선 교체하기 때문입니다

 

✅ LRU 알고리즘 특징

• LRU 알고리즘은 페이지의 접근 시간을 기준으로 한다.
• 가장 오랫동안 사용하지 않은 데이터는 미래에도 사용하지 않을 확률이 높다고 가정한다.

 

🎯 LRU 페이지 교체 알고리즘 _ 이미지 포인트 설명

1️⃣ 접근순서 4 _ 새로운 페이지 D 요청

   앞선 시점에서 메모리가 가득 차 있기 때문에,
   가장 오랫동안 사용되지 않은 페이지(A) 를 찾아 교체하게 됩니다.
   → 이것이 바로 LRU의 핵심❗

 

2️⃣ 접근순서 5 _ 페이지 B 요청

   페이지 B는 이미 메모리에 존재하므로 페이지 부재(Page Fault)가 발생하지 않습니다.
   LRU는 각 페이지가 참조될 때마다
   접근 순서를 기록하여 페이지를 구분 합니다.

 

📊 총 페이지 부재 횟수: 6번

---

😏 LFU _ 관심이 필요하다고!?

📌 LFU 페이지 교체 알고리즘

LFU는 Least Frequently Used 의 약자로,

참조 횟수가 가장 낮은 페이지를 교체하는 알고리즘입니다.

 

즉,

LFU 알고리즘은 페이지의 접근 빈도를 기준으로 합니다

 

🚫 LFU 알고리즘 단점

• 사용 빈도를 저장해야 하므로 추가적인 저장 공간이 필요하다는 단점이 있다.
• 오래전에 쓰이고, 최근에는 안 쓰이는 페이지도 카운트(참조 횟수)가 높으면 메모리에 계속 남아있는 Aging 문제가 발생할 수 있다.

 

🎯 LFU 페이지 교체 알고리즘 _ 이미지 포인트 설명

1️⃣ 접근 순서 1~3

아직 교체는 일어나지 않고 순서대로 모두 적재됩니다.

→ 모든 페이지의 참조 횟수가 1회로 모두 동일한 상태

 

2️⃣ 접근 순서 4 — 페이지 D 요청

이제 메모리가 꽉 찼기 때문에 교체가 필요합니다.

 

하지만 모두 참조 횟수가 1회로 동일하죠?
이 경우 가장 앞쪽 페이지(A) 를 교체합니다.
→ LFU에서는 빈도가 같을 경우 FIFO 방식으로 처리

 

3️⃣ 접근 순서 6 — 페이지 A 요청

이 시점에서 참조 횟수가 가장 낮은 페이지는 D와 C로 두 개입니다.

LFU는 여기서도 동일한 규칙 적용!
→ 페이지의 참조 횟수가 같을 경우 가장 앞쪽 페이지(D) 를 교체

 

📊 총 페이지 부재 횟수: 5번

---

📝 마무리하며

오늘은 메모리가 부족할 때
운영체제가 어떤 기준으로 누구를 내보낼지 결정하는
FIFO / LRU / LFU 세 가지 알고리즘을 살펴봤습니다!

• FIFO: "먼저 온 사람이 눈치껏 나가자!"
• LRU: “오래기다렸지? 이제 그만 나가줘!”
• LFU: "관심이 필요하다고? 그럼 나가!"

각 알고리즘은 장단점이 있고,
운영체제는 상황에 따라 가장 효율적인 방식을 선택합니다.

 

읽어주신 여러분 모두,
🥤 한여름에 마시는 코카콜라 한 잔처럼 시원한 지식 얻어가셨길 바랍니다.

 

그럼 다음 글에서 또 만나요,

모두 해피코딩! 😄

 

읽어주셔서 감사합니다 🙇