메모리 페이지 교체 알고리즘

페이지 교체 알고리즘 정리

페이지 교체 알고리즘은 가상 메모리 시스템¹에서 물리 메모리(RAM)의 프레임이 부족할 때, 어떤 페이지를 보조기억장치로 내보낼지 결정하는 알고리즘입니다.

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

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

1. 페이지(Page)란?

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

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

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

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

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

1. CPU는 운영체제(OS)에 제어권을 넘깁니다.
2. 운영체제는 보조기억장치(HDD, SSD)에서 필요한 페이지를 찾습니다.
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)이 필요합니다.

정보처리기사 실기 대비 문제