💭 메모리 페이지 교체 알고리즘 | 🚀 정처기 실기 대비 문제 풀이 방법 포함

📝 페이지 교체 알고리즘 정리

💡 정처기 실기 대비를 위한 주관식 문제는 포스팅 마지막에 있습니다. 각 알고리즘의 페이지 부재 횟수를 직접 계산해 보세요.

❗️페이지 교체 알고리즘은 가상 메모리 시스템에서 사용됩니다. 한정된 물리 메모리(RAM)를 실제 프로세스가 요구하는 메모리보다 훨씬 큰 것처럼 보이게 하는 기술이죠.

🧠 페이지와 페이지 부재, 왜 알아야 할까?

컴퓨터가 프로그램을 실행하려면 해당 프로그램의 코드와 데이터가 물리 메모리(RAM) 에 올라와 있어야 합니다. 하지만 RAM의 크기는 한정되어 있고, 여러 프로그램을 동시에 실행하다 보면 공간이 부족해집니다. 이때 운영체제는 가상 메모리라는 기술을 사용합니다.

1. 페이지(Page)란?

페이지는 가상 메모리를 사용하는 시스템에서 메모리를 관리하는 고정된 크기의 블록입니다. 하드 디스크와 같은 보조기억장치에 있는 프로그램의 코드와 데이터를 일정한 크기로 나누어 놓은 것이죠. RAM 역시 페이지와 동일한 크기의 프레임(Frame) 으로 나누어 관리합니다.

• 핵심: 프로세스는 페이지 단위로 나뉘고, 이 페이지들이 RAM의 프레임에 적재(loading)되어야 실행될 수 있습니다.

2. 페이지 부재(Page Fault)란?

프로세스가 특정 페이지를 사용하려고 할 때, 해당 페이지가 RAM(물리 메모리)에 없는 경우를 페이지 부재(Page Fault) 라고 합니다.

페이지 부재가 발생하면 다음과 같은 과정이 일어납니다.

1. CPU는 운영체제(OS)에 제어권을 넘깁니다.
2. 운영체제는 보조기억장치에서 필요한 페이지를 찾습니다.
3. RAM에 비어있는 프레임이 있다면 해당 페이지를 가져옵니다.
4. 만약 비어있는 프레임이 없다면? 기존에 있던 페이지 중 하나를 보조기억장치로 내보내고(swap-out), 그 공간에 새로운 페이지를 가져옵니다(swap-in).

이때 "어떤 페이지를 내보낼 것인가?"를 결정하는 규칙이 바로 페이지 교체 알고리즘입니다.

---

🔄 주요 페이지 교체 알고리즘

페이지 교체 알고리즘의 목표는 페이지 부재 횟수를 최소화하여 시스템 성능을 높이는 것입니다. FIFO, LRU, LFU가 대표적인 알고리즘입니다.

1. FIFO (First-In, First-Out)

가장 간단한 알고리즘으로, RAM에 가장 먼저 들어온 페이지를 가장 먼저 내보내는 방식입니다. 마치 줄을 서서 먼저 온 사람이 먼저 나가는 것과 같습니다.

• 장점: 구현이 매우 간단합니다.
• 단점: 자주 사용되는 페이지임에도 불구하고 먼저 들어왔다는 이유만으로 교체될 수 있어 비효율적일 수 있습니다. (이를 Belady의 모순(Belady's Anomaly) 이라고도 합니다. 프레임 수를 늘렸는데도 페이지 부재가 더 많이 발생하는 현상)

2. LRU (Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다. "최근에 사용된 페이지는 가까운 미래에도 다시 사용될 것이다"라는 시간 지역성(Temporal Locality) 아이디어를 기반으로 합니다.

• 장점: FIFO에 비해 페이지 부재율이 낮고, 일반적으로 좋은 성능을 보입니다.
• 단점: 각 페이지의 최근 사용 시간을 기록하고 유지해야 하므로, 운영체제의 부담이 크고 구현이 복잡합니다.

3. LFU (Least Frequently Used)

참조 횟수가 가장 적은 페이지를 교체하는 알고리즘입니다. "과거에 많이 사용된 페이지는 앞으로도 많이 사용될 것이다"라는 가정에 기반합니다.

• 장점: LRU가 잡아내지 못하는 장기적인 참조 패턴을 고려할 수 있습니다.
• 단점:
  • 참조 횟수를 계산하기 위한 오버헤드가 큽니다.
  • 초기에 많이 사용되었지만 더 이상 사용되지 않는 페이지가 계속 메모리에 남아있을 수 있습니다.
  • 참조 횟수가 동일한 페이지가 여러 개일 경우, 어떤 것을 교체할지 결정하기 위한 추가적인 규칙(e.g., FIFO)이 필요합니다.

---

📝 정처기 실기 대비 문제

문제 1 - FIFO

문제 풀이

밀어내기 식으로 푸세요. 큐 자료구조를 떠올리면 좋습니다. 새로운게 들어오면 새로운 게 위에 들어가고, 가장 아래에 있는 걸 밀어내듯이 풀면 헷갈리지 않습니다.

참조	2	3	2	1	5	2	4	5	3	2	5	2
1	2	3	3	1	5	2	4	4	3	3	5	2
2		2	2	3	1	5	2	2	4	4	3	5
3				2	3	1	5	5	2	2	4	3
부재	O	O	X	O	O	O	O	X	O	X	O	O

• 페이지 부재 횟수: 9번

---

문제 2 - LRU

문제 풀이

가장 오래전 사용한 것을 맨 아래로 보내는 식으로 푸세요. 새로운 게 들어오면 새로운 게 위에 들어가고, 가장 아래에 있는 걸 밀어내듯이 풀면 헷갈리지 않습니다. 만약, 기존에 존재하는 페이지라면 위치를 맨 위로 올리면 됩니다.

참조	2	3	2	1	5	2	4	5	3	2	5	2
1	2	3	2	1	5	2	4	5	3	2	5	2
2		2	3	2	1	5	2	4	5	3	2	5
3				3	2	1	5	2	4	5	3	3
부재	O	O	X	O	O	X	O	X	O	O	X	X

• 페이지 부재 횟수: 7번

---

문제 3 - LFU

문제 풀이

해당 페이지가 몇번 참조되었는지 기록하면서 푸는게 좋습니다. (예 : 2-1 은 2번 페이지가 1번 참조되었음을 의미합니다.)

참조 횟수가 동일할 경우 FIFO 규칙을 따르므로, FIFO를 풀듯이 새로 들어온 페이지를 위에 넣으세요.

참조	2	3	2	1	5	2	4	5	3	2	5	2
1	2-1	3-1	3-1	1-1	5-1	5-1	4-1	4-1	3-1	3-1	3-1	3-1
2		2-1	2-2	3-1	1-1	1-1	5-1	5-2	5-2	5-2	5-3	5-3
3				2-2	2-2	2-3	2-3	2-3	2-3	2-4	2-4	2-5
부재	O	O	X	O	O	X	O	X	O	X	X	X

• 페이지 부재 횟수: 6번

➡️ 다음 읽으면 좋은 포스팅

• 🤖 프로세스 스케줄링 알고리즘 | 🚀 정처기 실기 대비 문제 풀이 방법 포함
• 정처기 실기 2025년 2회 이론 문제 예상 | ⚡️ 벼락치기 팁 정리