페이지 교체 알고리즘(예: LRU, FIFO, LFU)의 설명

페이지 교체 알고리즘(Page Replacement Algorithm)

페이지 교체 알고리즘은 컴퓨터의 메모리 관리 방법 중 하나로, 페이지(프로그램의 메모리 블록)를 RAM(물리 메모리)에 로드할 때, 메모리가 꽉 차 있으면 어느 페이지를 내보내야 할지를 결정하는 방법입니다. 이것은 특히 가상 메모리를 사용하는 시스템에서 중요합니다.

가상 메모리와 페이지 교체

• 가상 메모리: 컴퓨터가 실제 메모리(RAM)보다 더 큰 용량의 메모리를 사용할 수 있게 해주는 기술입니다. 디스크(하드 드라이브)의 일부를 메모리처럼 사용하는데, 자주 사용하지 않는 데이터를 디스크로 보내고, 필요한 데이터를 메모리에 가져오는 방식입니다.
• 페이지: 가상 메모리의 데이터를 일정한 크기로 나눈 블록입니다. 예를 들어, 책을 페이지로 나누듯 데이터를 나눠서 관리합니다.
• 페이지 교체: 메모리가 꽉 찼을 때, 새로운 페이지를 메모리에 넣기 위해 기존 페이지 중 하나를 내보내는 것을 말합니다.

---

1. FIFO (First In, First Out)

• 정의: 가장 먼저 들어온 페이지를 가장 먼저 내보내는 방법입니다.

• 작동 방식: 페이지가 메모리에 들어온 순서를 큐(queue) 형태로 관리하여, 가장 오래된 페이지를 교체합니다.

• 쉽게 말하면: 먼저 들어온 사람이 먼저 나가는 줄서기 방식입니다. 예를 들어, 줄을 서서 영화를 보러 들어가는 사람들을 생각해보세요. 가장 먼저 들어간 사람이 끝나고 가장 먼저 나옵니다.

• 장점: 구현이 쉽고 단순합니다.

• 단점: 가장 먼저 들어온 페이지가 아직 자주 사용될 수 있음에도 불구하고 내보낼 수 있어, 비효율적일 수 있습니다.

• 예시:

  • 메모리 크기: 3페이지
  • 순서: A, B, C가 메모리에 차례대로 들어오고, D가 들어오려면 먼저 들어온 A가 나갑니다.

  less코드 복사페이지 요청 순서: A, B, C, D
  메모리 상태: [A, B, C] → A가 가장 먼저 들어왔으므로 A를 제거
  새로운 메모리 상태: [B, C, D]

---

2. LRU (Least Recently Used)

• 정의: 가장 오랫동안 사용되지 않은 페이지를 교체하는 방법입니다.

• 작동 방식: 각 페이지가 마지막으로 사용된 시간을 기록하여, 가장 오래 사용되지 않은 페이지를 내보냅니다.

• 쉽게 말하면: 친구들이 놀러 왔을 때, 최근에 놀지 않은 장난감을 치우는 것과 비슷해요. 방이 너무 좁아서 새 장난감을 두려면 덜 사용한 장난감을 먼저 치워야 해요.

• 장점: 자주 사용하는 페이지는 메모리에 남겨둘 수 있어, 실제 사용 패턴에 맞게 동작합니다.

• 단점: 사용 시간을 추적하는 것이 복잡하고, 시스템 자원을 많이 사용할 수 있습니다.

• 예시:

  • 메모리 크기: 3페이지
  • 순서: A, B, C가 메모리에 차례대로 들어오고, A가 다시 사용되고, D가 들어오려면 가장 오래 사용되지 않은 B가 나갑니다.

  less코드 복사페이지 요청 순서: A, B, C, A, D
  메모리 상태: [A, B, C] → A가 다시 사용됨
  A 사용 후 상태: [A, B, C]
  D 요청 시 가장 오래 사용되지 않은 B 제거
  새로운 메모리 상태: [A, C, D]

---

3. LFU (Least Frequently Used)

• 정의: 사용 횟수가 가장 적은 페이지를 교체하는 방법입니다.

• 작동 방식: 각 페이지가 사용된 횟수를 기록하여, 사용 횟수가 가장 적은 페이지를 교체합니다.

• 쉽게 말하면: 장난감 중에서 가장 안 쓰는 장난감을 먼저 치우는 것과 같아요. 사용하지 않는 물건부터 정리하는 거죠.

• 장점: 오랫동안 자주 사용된 페이지는 메모리에 남겨둘 수 있어, 효율적입니다.

• 단점: 페이지의 사용 빈도를 추적하고 기록해야 해서, 구현이 복잡하고 시스템 자원을 많이 사용할 수 있습니다. 또한, 최근에 사용 빈도가 급격히 증가한 페이지도 제거될 수 있습니다.

• 예시:

  • 메모리 크기: 3페이지
  • 순서: A, B, C가 들어오고, A가 두 번 사용되고, D가 들어오려면 가장 적게 사용된 B가 나갑니다.

  css코드 복사페이지 요청 순서: A, B, C, A, D
  메모리 상태: [A(1), B(1), C(1)] → A가 한 번 더 사용됨
  A 사용 후 상태: [A(2), B(1), C(1)]
  D 요청 시 사용 횟수가 가장 적은 B 제거
  새로운 메모리 상태: [A(2), C(1), D(1)]

---

페이지 교체 알고리즘의 비교

알고리즘	설명	장점	단점	적합한 경우
FIFO	먼저 들어온 페이지를 먼저 교체	구현이 쉽고 단순	자주 사용되는 페이지도 제거될 수 있음	메모리 관리가 단순한 시스템
LRU	가장 오래 사용되지 않은 페이지 교체	사용 패턴에 맞게 효율적	구현이 복잡, 자원 소모	사용 패턴이 예측 가능한 경우
LFU	사용 빈도가 가장 적은 페이지 교체	오랫동안 자주 사용하는 페이지 유지	사용 횟수 관리가 어려움	장기적인 사용 패턴 분석에 유리한 경우

---

쉽게 요약

• FIFO는 오래된 것부터 내보내는 방식입니다. 쉽게 줄 서기 같은 느낌이에요.
• LRU는 사용하지 않은 지 오래된 것부터 내보내는 방식입니다. 잘 안 쓰는 장난감을 먼저 치우는 거죠.
• LFU는 가장 적게 사용된 것부터 내보내는 방식입니다. 거의 사용하지 않는 물건부터 정리하는 것과 같아요.