가상 메모리(Virtual Memory)와 페이지 폴트 알고리즘

본 포스트는 인프런 “[CS 기술면접 2] 말이 트이는 운영체제” 강의를 학습하며 정리한 내용을 다룹니다.

1. 가상 메모리(Virtual Memory)

가상 메모리는 물리 메모리(RAM)의 크기와 독립적으로 프로세스에 가상의 주소 공간을 제공하는 메모리 관리 기법입니다.

프로세스가 사용하는 모든 데이터를 물리 메모리에 한꺼번에 적재할 필요 없이, 실행에 필요한 부분만 RAM에 적재하고 나머지는 디스크 등의 보조 저장 장치에 유지할 수 있습니다.

• 독립적인 주소 공간: 물리 메모리 크기에 직접적으로 제한되지 않는 가상 주소 공간을 프로세스에 제공
• 스왑 공간(Swap Space) 활용: 메모리에 유지할 필요가 없는 페이지를 디스크의 스왑 공간으로 이동시키고, 필요할 때 다시 RAM으로 적재하는 방식으로 메모리 관리

다만 가상 메모리가 실제 RAM의 용량을 증가시키는 것은 아닙니다. 프로세스에 더 큰 주소 공간을 제공하고 필요한 페이지만 물리 메모리에 유지하여 메모리 사용 효율을 높이는 방식입니다.

요구 페이징(Demand Paging)

요구 페이징은 가상 메모리를 구현하는 대표적인 기법으로, 프로세스가 실제로 필요로 하는 페이지만 물리 메모리에 적재하는 방식입니다.

프로세스 실행 시 모든 페이지를 RAM에 올리는 대신, 실행 중 특정 페이지가 필요해지는 시점에 해당 페이지를 메모리로 가져옵니다.

동작 원리

1. 페이지 테이블 초기화: 프로세스가 실행되면 운영체제가 페이지 테이블을 준비하고 각 페이지의 상태를 관리합니다.
2. 메모리 적재 상태 표시: 아직 물리 메모리에 적재되지 않은 페이지는 페이지 테이블에서 메모리에 존재하지 않는 상태로 표시합니다.
3. 페이지 폴트 발생: CPU가 가상 주소에 접근했을 때 해당 페이지가 물리 메모리에 없다면 페이지 폴트(Page Fault)가 발생합니다.
4. 페이지 적재: 운영체제가 필요한 페이지를 디스크 등의 보조 저장 장치에서 물리 메모리로 가져옵니다.
5. 페이지 테이블 갱신: 새롭게 적재된 페이지의 물리 메모리 위치를 페이지 테이블에 반영합니다.
6. 프로세스 실행 재개: 페이지 적재가 완료되면 중단되었던 명령어를 다시 실행하여 정상적으로 메모리에 접근합니다.

요구 페이징에서는 처음부터 모든 페이지를 메모리에 적재하지 않으므로, 초기 메모리 사용량을 줄이고 필요한 페이지를 효율적으로 관리할 수 있습니다.

2. 페이지 폴트(Page Fault)

페이지 폴트는 프로세스가 참조한 가상 메모리 페이지가 현재 물리 메모리에 존재하지 않거나, 해당 접근을 정상적으로 처리할 수 없을 때 발생하는 예외(Exception)입니다.

요구 페이징에서는 필요한 페이지가 물리 메모리에 없는 경우 페이지 폴트가 발생하며, 운영체제가 해당 페이지를 적재하는 작업을 수행합니다.

• 발생 조건: 프로세스가 접근하려는 페이지가 현재 물리 메모리에 존재하지 않는 경우
• 운영체제의 개입: CPU가 페이지 폴트 예외를 발생시켜 운영체제의 예외 처리 루틴으로 제어권 전달
• 페이지 적재: 운영체제가 필요한 페이지를 디스크에서 읽어 물리 메모리에 적재
• 실행 재개: 페이지 테이블을 갱신한 뒤 중단된 명령어를 다시 실행

페이지 폴트는 일반적인 하드웨어 인터럽트와 구분되는 동기적 예외입니다. CPU가 특정 메모리 주소에 접근하는 명령어를 실행하는 과정에서 발생한다는 특징이 있습니다.

페이지 폴트로 인한 성능 저하

페이지 폴트가 발생하면 운영체제가 필요한 페이지를 물리 메모리에 적재해야 합니다. 하지만 물리 메모리에 사용 가능한 공간이 부족하다면, 새로운 페이지를 적재하기 위해 기존 페이지 중 일부를 메모리에서 내보내야 할 수 있습니다.

• 메모리 공간 부족: 새로운 페이지를 적재할 빈 프레임이 없는 경우 기존 페이지를 교체해야 하는 상황 발생
• 디스크 접근 비용: 필요한 페이지를 보조 저장 장치에서 가져오는 작업은 RAM 접근보다 시간이 오래 소요
• 페이지 교체 필요성: 어떤 페이지를 내보내는지에 따라 이후 페이지 폴트 발생 횟수와 시스템 성능에 영향

따라서 운영체제는 페이지 교체 알고리즘을 사용하여 메모리에서 내보낼 페이지를 결정합니다.

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

페이지 교체 알고리즘은 물리 메모리의 공간이 부족할 때 어떤 페이지를 메모리에서 내보낼지 결정하는 기법입니다.

페이지 폴트가 발생했지만 사용 가능한 물리 메모리 프레임이 없다면, 운영체제는 기존 페이지 중 하나를 선택하여 새로운 페이지로 교체해야 합니다. 이때 어떤 페이지를 선택하느냐에 따라 이후 페이지 폴트 발생 횟수가 달라질 수 있습니다.

FIFO(First-In, First-Out)

FIFO는 가장 먼저 메모리에 적재된 페이지를 가장 먼저 교체하는 알고리즘입니다.

운영체제는 페이지가 메모리에 들어온 순서를 관리하며, 일반적으로 큐(Queue) 자료구조를 사용하여 구현할 수 있습니다.

• 교체 기준: 물리 메모리에 가장 먼저 적재된 페이지 선택
• 동작 방식: 페이지가 적재된 순서를 큐로 관리하고, 가장 오래전에 들어온 페이지부터 교체

장점

• 알고리즘의 동작 방식이 직관적이며 구현이 간단

단점

• 페이지의 실제 사용 빈도를 고려하지 않아 자주 사용되는 페이지도 오래전에 적재되었다는 이유로 교체될 가능성
• Belady's Anomaly(벨라디의 역설) 발생 가능
  • 물리 메모리의 프레임 수를 늘렸음에도 페이지 폴트 발생 횟수가 오히려 증가하는 현상

OPT(Optimal Page Replacement)

OPT는 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘입니다.

미래의 페이지 참조 순서를 알고 있다는 가정하에, 현재 메모리에 존재하는 페이지 중 가장 늦게 다시 사용될 페이지를 선택합니다.

• 교체 기준: 미래에 가장 늦게 참조될 페이지 선택
• 동작 방식: 앞으로 발생할 페이지 참조 순서를 바탕으로 가장 오랫동안 사용되지 않을 페이지를 교체

미래의 페이지 참조 순서를 정확히 알아야 하므로 일반적인 실제 시스템에서는 구현할 수 없는 이상적인 알고리즘입니다.

장점

• 주어진 페이지 참조 순서와 프레임 수에서 페이지 폴트 발생 횟수 최소화

단점

• 미래의 페이지 참조 순서를 정확히 알 수 없어 실제 운영체제에서 그대로 구현 불가능

LRU(Least Recently Used)

LRU는 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다.

OPT가 미래의 페이지 참조를 기준으로 교체 대상을 선택한다면, LRU는 과거의 페이지 참조 기록을 기준으로 교체 대상을 결정합니다.

• 교체 기준: 가장 최근에 참조된 시점이 오래된 페이지 선택
• 동작 방식: 페이지의 최근 참조 기록을 관리하고 가장 오랫동안 사용하지 않은 페이지를 교체

장점

• 최근에 사용된 페이지가 다시 사용될 가능성이 높다는 지역성(Locality)을 활용하여 OPT에 근접한 성능 기대
• 과거의 참조 기록을 기반으로 하므로 실제 구현 가능

단점

• 페이지의 최근 참조 시점을 추적해야 하므로 구현이 복잡하고 추가적인 관리 비용 발생
• 페이지의 전체 참조 횟수를 고려하지 않으므로 과거에 자주 사용된 페이지라도 최근에 사용되지 않았다면 교체 가능

LFU(Least Frequently Used)

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

각 페이지가 얼마나 자주 참조되었는지 기록하고, 참조 횟수가 가장 적은 페이지를 교체 대상으로 선택합니다.

• 교체 기준: 페이지의 누적 참조 횟수가 가장 적은 페이지 선택
• 동작 방식: 페이지마다 참조 횟수를 기록하고 이를 기준으로 교체 대상 결정

장점

• 자주 참조되는 페이지를 메모리에 우선적으로 유지하여 반복적인 페이지 적재 비용 감소

단점

• 과거에 참조 횟수가 높았던 페이지가 최근에는 사용되지 않더라도 메모리에 계속 유지될 가능성
• 최근의 사용 패턴보다 누적 참조 횟수가 우선되어 현재의 페이지 사용 상황을 정확히 반영하지 못할 가능성

Second-Chance(Clock Algorithm)

Second-Chance는 참조 비트(Reference Bit)를 이용하여 최근에 사용된 페이지에 교체를 피할 기회를 한 번 더 제공하는 알고리즘입니다.

FIFO의 단점을 보완하기 위해 페이지의 최근 참조 여부를 고려하며, Clock 알고리즘은 이를 원형 구조와 포인터를 이용하여 구현한 방식입니다.

• 참조 비트 사용: 페이지가 메모리에 적재되거나 접근될 때 참조 비트를 1로 설정
• 원형 구조: 페이지들을 원형으로 관리하고 포인터가 시계 방향으로 이동하면서 참조 비트 확인
• 참조 비트가 1인 경우: 최근에 사용된 페이지로 판단하여 참조 비트를 0으로 변경하고 교체를 연기
• 참조 비트가 0인 경우: 최근에 사용된 기록이 없는 페이지로 판단하여 교체 대상으로 선택

Clock 알고리즘은 실제 페이징 시스템에서 활용되는 페이지 교체 기법 중 하나이며, LRU의 동작을 비교적 간단한 방식으로 근사할 수 있습니다.

장점

• 최근에 참조된 페이지에 추가 기회를 제공하여 FIFO보다 페이지 교체 판단을 개선할 수 있으며, 참조 패턴에 따라 페이지 폴트 감소 가능
• 페이지의 정확한 참조 시간을 기록하지 않고 참조 비트만 확인하므로 비교적 간단한 구현 가능

4. 페이지 교체 알고리즘 비교

각 알고리즘은 페이지의 적재 순서, 미래 참조 시점, 최근 참조 시점, 참조 빈도 등을 기준으로 교체할 페이지를 결정합니다.

이를 물건을 정리하는 상황에 비유하면 다음과 같습니다.

• FIFO: 구매한 지 가장 오래된 물건부터 정리
• OPT: 미래에 가장 늦게 다시 사용할 물건부터 정리
• LRU: 가장 오랫동안 사용하지 않은 물건부터 정리
• LFU: 사용 빈도가 가장 낮은 물건부터 정리
• Second-Chance(Clock): 최근에 사용한 물건에는 정리 대상에서 제외될 기회를 한 번 더 부여

알고리즘	교체 기준	핵심 특징
FIFO	가장 먼저 적재된 페이지	적재 순서
OPT	미래에 가장 늦게 사용될 페이지	미래 참조
LRU	가장 오래 사용하지 않은 페이지	최근 참조 시점
LFU	참조 횟수가 가장 적은 페이지	참조 빈도
Second-Chance	참조 비트가 0인 페이지	최근 참조 여부