운영체제 정리(5) - 메모리 관리와 페이징, 세그먼테이션

 

페이징과 세그먼테이션

페이징과 세그먼테이션은 가상 메모리를 물리 메모리로 매핑하는 데 사용하는 메모리 관리 전략이다. 이를 이해하려면 먼저 가상 메모리를 이해해야 한다.

가상 메모리

가상 메모리는 실제 물리 메모리(RAM)의 용량 한계를 극복하기 위해 탄생한 기술이다. 운영체제는 각 프로그램(프로세스)에게 실제 메모리 크기와 무관하게 자신만의 무한한 메모리 공간(가상 주소 공간)을 사용하고 있는 것처럼 느끼게 한다. 사용하는 입장에서는 프로세스 전체가 큰 메모리 공간을 차지하며 실행되고 있는 것처럼 사용하지만, 실제로는 프로그램 실행에 당장 필요한 부분만 보조 저장 장치에서 물리 메모리로 옮겨와 사용한다. 이렇게 필요한 시점에 필요한 부분만 적재(demand paging)하는 방식으로 물리 메모리를 효율적으로 사용하며, 여러 개의 큰 프로그램이 동시에 실행될 수 있도록 한다.

이때, 가상의 주소를 실제 물리 메모리의 주소로 변환해 주는 매핑(Mapping) 전략이 필요한데, 이것이 바로 페이징과 세그먼테이션이다.

페이징(Paging)

페이징은 메모리 관리를 단순화하기 위해 모든 공간을 동일한 크기의 고정된 조각으로 나누는 전략이다.

• 나누는 단위: 프로그램의 가상 메모리 공간은 페이지(Page)라는 고정 크기로, 물리 메모리 공간은 프레임(Frame)이라는 동일한 고정 크기로 나뉜다.
• 매핑 방식: 운영체제는 각 페이지를 물리 메모리의 사용 가능한 임의의 프레임에 대응시킨다. 순서와 관계없이 빈 프레임이면 어디든 들어갈 수 있다.
• 장점: 메모리 단편화 문제 중 외부 단편화 문제가 발생하지 않는다.
• 단점: 페이지 크기보다 데이터가 작아 남는 공간이 생기는 내부 단편화는 발생할 수 있다.

세그먼테이션(Segmentation)

세그먼테이션은 페이징과 달리 메모리를 프로그램의 논리적인 의미 단위로, 가변적인 크기로 나누는 전략이다.

• 나누는 단위: 프로그램을 코드(Code), 데이터(Data), 스택(Stack), 함수(Function), 배열(Array) 등 의미 있는 단위인 세그먼트(Segment)로 나눈다. 각 세그먼트의 크기는 가변적이다.
• 매핑 방식: 각 세그먼트는 물리 메모리 내의 충분한 크기의 연속적인 빈 공간에 할당된다.
• 장점: 사용자에게 친숙한 논리적 구조를 제공하며, 메모리 보호나 공유가 용이하다. 내부 단편화는 거의 발생하지 않는다.
• 단점: 세그먼트 크기가 가변적이므로, 메모리 할당과 회수가 반복되면 외부 단편화 문제가 발생할 수 있다.

 

 

현대의 운영체제는 외부 단편화 해결, 관리 로직과 구현의 단순성, 그리고 높은 효율성으로 인해 페이징(Paging)을 주된 메모리 관리 방식으로 채택한다. 세그먼테이션은 메모리 보호나 논리적 공유 같은 보조적인 역할로 페이징과 결합하여 사용하기도 한다.(페이지드 세그먼테이션)

페이징과 세그먼테이션은 모두 한정된 물리 메모리 공간을 효율적으로 사용하기 위한 전략이지만, 가상 메모리 시스템에서는 필요한 페이지(또는 세그먼트)를 디스크에서 물리 메모리로 적재하고 다시 디스크로 내보내는 과정이 빈번하게 발생한다. 이처럼 메모리에 매핑된 페이지가 자주 교체됨에 따른 디스크 I/O 오버헤드가 발생한다.

이러한 I/O 오버헤드와 물리 메모리를 효과적으로 관리하기 위해 운영체제는 페이지를 교체할 때 어떤 페이지를 교체할지 결정해야 한다. 이때 페이지를 교체하는 기준에 따라 여러 가지 페이지 교체 알고리즘(Page Replacement Algorithm)을 사용할 수 있으며, 주요 알고리즘은 다음과 같다.

 

 

 

페이지 교체 알고리즘

 

FIFO (First-In, First-Out) 알고리즘

가장 단순한 방식으로, 물리 메모리에 가장 먼저 들어온 페이지를 가장 먼저 내보내는 방식이다. 큐(Queue)를 사용하여 페이지의 진입 순서를 관리하며, 새로운 페이지가 들어와야 할 때 큐의 맨 앞에 있는(가장 오래된) 페이지를 희생양(Victim)으로 선택한다.

• 장점: 구현이 매우 간단하고 오버헤드가 적다.
• 단점: 가장 오래된 페이지가 앞으로 자주 사용될 페이지일 수 있다. 즉, 지역성(Locality)을 고려하지 못해 효율성이 떨어질 수 있으며, 페이지 프레임 수를 늘렸는데도 오히려 페이지 부재(Page Fault) 횟수가 증가하는 벨라디의 모순(Belady's Anomaly)이 발생할 수 있다.

OPT (Optimal Page Replacement) 알고리즘

최적 페이지 교체 알고리즘은 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 미리 교체하는 방식이다. 미래를 예측하여 가장 이상적인 성능을 보여준다.

• 장점: 페이지 부재 횟수를 최소화하는 가장 효율적인 알고리즘이다.
• 단점: 실제 구현이 불가능하다. 운영체제가 프로세스의 미래 메모리 접근 패턴을 알 수 없기 때문이다. 이 알고리즘은 주로 다른 알고리즘들의 성능을 평가하는 벤치마크 용도로 사용된다.

LRU (Least Recently Used) 알고리즘

OPT의 현실적인 대안으로, 시간적 지역성(Temporal Locality)을 활용하는 알고리즘이다. "가장 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이다" 라는 가정에 근거하여, 가장 오랫동안 참조되지 않은 페이지를 교체한다.

• 장점: OPT 다음으로 좋은 성능을 보인다. 지역성 원칙에 잘 부합한다.
• 단점: 페이지별 사용 시각을 계속 기록하거나 스택/큐를 관리해야 하므로 하드웨어적인 지원이 필요하며, 구현 오버헤드가 FIFO보다 크다.

LFU (Least Frequently Used) 알고리즘

빈도 기반으로 교체 대상을 선정한다. 참조 횟수가 가장 적은 페이지를 교체하는 방식이다. "참조 횟수가 적은 페이지는 앞으로도 사용 빈도가 낮을 것이다"라는 가정에 기반한다.

• 장점: 한 번 집중적으로 사용되고 그 후 사용되지 않는 페이지를 잘 걸러낼 수 있다.
• 단점: 사용 빈도가 높은 초기에 집중적으로 사용된 후 더 이상 사용되지 않는 페이지가 메모리에 계속 남아있을 수 있다. 참조 횟수를 카운트해야 하므로 오버헤드가 발생한다.

클럭(Clock) 알고리즘 (2차 기회 알고리즘)

LRU의 구현 복잡성을 개선한 현실적인 알고리즘이다. FIFO와 유사하게 원형 큐를 사용하지만, 각 페이지에 참조 비트(Reference Bit)를 두어 교체 기회를 한 번 더 준다.

 

• 동작 방식 : 교체 시계 바늘이 가리키는 페이지의 참조 비트를 확인한다.
  - 참조 비트가 1이면 (최근에 사용됨), 0으로 바꾸고 다음 페이지로 넘어간다 (기회 부여).
  - 참조 비트가 0이면 (최근에 사용 안 됨), 해당 페이지를 교체한다.
• 장점: FIFO와 LRU의 장점을 결합하여 구현이 간단하면서도 성능이 우수하다. 현대 운영체제에서 널리 사용되거나 변형된 형태로 채택된다.