운영체제 메모리 관리: 페이징·세그멘테이션과 페이지 교체 알고리즘

제한된 RAM을 프로세스가 함께 쓰는 방식

메모리 관리는 운영체제가 주기억장치(RAM)의 할당과 해제를 제어해 여러 프로세스가 메모리를 공유하도록 하는 기능이다. 다중 프로그래밍 환경에서는 단순히 빈 공간을 배정하는 일을 넘어, 프로세스별 영역 격리와 논리 주소의 물리 주소 변환, 가상 메모리 지원까지 함께 다룬다.

이 과정에서 다루는 목표는 메모리 활용도를 높이고 내부·외부 단편화를 줄이는 것, 프로세스 사이의 메모리 영역을 보호하는 것, 그리고 물리 메모리보다 큰 프로그램도 실행할 수 있게 하는 것이다.

파티션 크기를 미리 정할지, 요청에 맞춰 나눌지

고정 분할은 메모리를 시스템 시작 시 정해 둔 크기의 파티션으로 나눈다. 구현 복잡도와 오버헤드는 낮지만, 프로세스가 파티션보다 작으면 남는 공간이 내부 단편화가 된다. 반대로 파티션보다 큰 프로세스는 실행할 수 없으며, 멀티프로그래밍 정도도 파티션 수에 묶인다.

특성	고정 분할의 특성
파티션 크기	시스템 시작 시 고정
내부 단편화	발생 (프로세스가 파티션보다 작을 때)
외부 단편화	발생하지 않음
구현 복잡도	낮음
멀티프로그래밍 정도	파티션 수에 의해 제한

가변 분할은 프로세스가 요구한 크기에 맞춰 파티션을 동적으로 할당한다. 빈 공간을 선택하는 기준에는 처음 발견한 충분한 공간을 쓰는 First Fit, 요청 크기에 가장 가까운 공간을 고르는 Best Fit, 가장 큰 공간을 쓰는 Worst Fit이 있다. 이 방식은 내부 단편화 문제를 줄이는 대신 외부 단편화가 발생할 수 있으며, 필요하면 압축(Compaction)을 수행한다.

⤢✕

고정 크기 단위로 주소 공간을 매핑하는 페이징

페이징은 프로세스의 논리 주소 공간을 고정 크기 페이지(Page)로 나누고, 물리 메모리는 같은 크기의 프레임(Frame)으로 나누어 대응시키는 방식이다. 페이지 테이블이 논리 페이지와 물리 프레임의 연결을 관리한다.

⤢✕

논리 주소는 페이지 번호(Page Number)와 오프셋(Offset)으로 구성된다. 페이지 번호는 페이지 테이블의 인덱스이고, 오프셋은 페이지 내부 위치를 나타낸다.

구성 요소	비트 수	설명
페이지 번호	log₂(페이지 수)	페이지 테이블 인덱스
오프셋	log₂(페이지 크기)	페이지 내 위치

32비트 주소 체계에서 4KB 페이지를 사용하면 오프셋은 12비트(2^12 = 4096)이고, 페이지 번호는 20비트가 된다.

페이징은 외부 단편화를 없애고 메모리 할당·해제를 단순하게 만들며, 프로세스 사이의 메모리 공유도 페이지 단위로 처리하기 쉽다. 다만 마지막 페이지에서는 내부 단편화가 생길 수 있고, 페이지 테이블을 보관할 메모리와 주소 변환 오버헤드가 필요하다.

프로그램의 논리적 구조를 보존하는 세그멘테이션

세그멘테이션은 프로세스를 코드, 데이터, 스택, 힙처럼 논리적인 세그먼트(Segment)로 나누는 방식이다. 각 세그먼트의 시작 위치와 크기는 세그먼트 테이블로 관리한다.

⤢✕

세그먼트 테이블 엔트리에는 세그먼트의 물리 메모리 시작 주소를 나타내는 Base(기준), 세그먼트 크기인 Limit(한계), 읽기·쓰기·실행 권한을 위한 Protection Bits, 그리고 세그먼트 유효성을 표시하는 Valid Bit이 포함된다.

페이징과 세그멘테이션은 분할 기준과 단편화 특성이 다르다.

특성	페이징	세그멘테이션
분할 단위	고정 크기 (페이지)	가변 크기 (세그먼트)
사용자 관점	투명함	논리적 구조 반영
내부 단편화	발생 가능	발생하지 않음
외부 단편화	발생하지 않음	발생 가능
주소 변환	페이지 테이블	세그먼트 테이블
공유	페이지 단위	논리적 단위

빈 프레임이 없을 때 희생 페이지를 고르는 법

가상 메모리에서 페이지 폴트(Page Fault)가 발생했는데 빈 프레임이 없으면, 물리 메모리에 있는 페이지 가운데 하나를 희생 페이지(Victim)로 골라 교체해야 한다. 교체 알고리즘은 이 선택 기준을 정한다.

FIFO(First-In First-Out)는 메모리에 가장 먼저 적재된 페이지를 내보낸다. 큐(Queue)로 구현할 수 있어 단순하지만, 프레임 수가 늘었는데 페이지 폴트가 증가하는 Belady's Anomaly가 발생할 수 있다.

⤢✕

LRU(Least Recently Used)는 가장 오랫동안 사용되지 않은 페이지를 교체하며, 시간적 지역성(Temporal Locality)을 전제로 한다. 페이지별 사용 시간을 기록하는 카운터 방식은 정확하지만 오버헤드가 크다. 스택 방식은 사용된 페이지를 스택 상단으로 옮기며 갱신 오버헤드가 발생한다. 참조 비트 방식은 참조 비트를 주기적으로 확인하는 근사 LRU 방식이다. LRU는 높은 적중률을 보이고 Belady's Anomaly가 발생하지 않지만, 구현 복잡도가 높고 하드웨어 지원이 필요하다.

LFU(Least Frequently Used)는 참조 횟수가 가장 적은 페이지를 교체한다. 자주 쓰이는 페이지를 보호할 수 있지만, 초기에 집중적으로 사용된 뒤 더 이상 쓰이지 않는 페이지가 오래 남는 문제가 있다. 구현에는 힙(Heap) 자료구조를 활용할 수 있다.

⤢✕

Optimal(OPT)은 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 이론적 최적 알고리즘이다. 최소 페이지 폴트를 보장하지만 미래의 참조를 예측할 수 없으므로 실제 구현은 불가능하다. 대신 다른 알고리즘 성능을 비교하는 기준으로 쓰인다.

동일한 페이지 참조열에서 3개 프레임을 사용한 예시의 참조열은 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1이다.

알고리즘	페이지 폴트 수	특징
FIFO	15	간단하나 성능 보통
LRU	12	좋은 성능, 구현 복잡
LFU	13	빈도 기반, 적응성 부족
Optimal	9	이론적 최적, 구현 불가

워크로드와 비용이 교체 정책을 좌우한다

교체 정책은 순차 접근, 무작위 접근, 반복 패턴 같은 워크로드 특성에 따라 다르게 평가해야 한다. 하드웨어 지원 여부와 CPU 오버헤드 같은 구현 복잡도, 프레임 수와 알고리즘 효율성의 관계, 예측 가능한 응답 시간이 필요한 실시간 요구사항도 함께 고려 대상이다.

페이징과 세그멘테이션은 각기 다른 방식으로 메모리 분할 문제를 다룬다. 현대 운영체제는 두 기법을 결합한 페이지드 세그멘테이션을 사용하기도 하며, LRU는 성능과 구현 가능성의 균형 때문에 널리 사용된다. 실제 시스템에서는 LRU 근사 알고리즘이 적용된다.