[OS] Virtual Memory Management

현대 컴퓨터 시스템에서 가상 메모리는 제한된 물리 메모리를 효율적으로 사용하는 핵심 기술이다. 가상 메모리 관리(Virtual Memory Management)란, 프로그램이 실제로 사용할 수 있는 메모리보다 더 큰 주소 공간을 사용할 수 있도록 운영체제가 가상 주소를 물리주소로 매핑하고, 필요한 페이지만 실제 메모리에서 적재하는 과정을 조율하는 것이다.

가상 메모리의 핵심 목적은 두 가지이다. 하나는 효율적인 메모리 사용이고, 다른 하나는 멀티프로그래밍의 향상이다. 실제로 대부분의 프로그램은 전체 코드와 데이터를 실행 중에 모두 사용하는 것이 아니라, 일부분만을 자주 접근한다. 이를 프로그램의 메모리 사용 패턴이라 하며, 이 특성 덕분에 가상 메모리는 전체 프로그램을 모두 메모리에 올리지 않고도 실행이 가능하다.

The Memory Use Patterns 프로그램의 메모리 사용 패턴

프로그램은 일반적으로 전체 코드를 사용하는 것이 아니라, 실행 중 일부분만 반복적으로 접근하는 경향을 보인다. 예를 들어, 자바 같은 언어에서 사용하는 예외 처리 루틴이나, 100x100 크기의 배열 중 실제로 사용하는 부분이 10x10에 불과한 경우 여기에 해당한다. 또는 특정 기능은 프로그램 내 존재하지만 거의 사용되지 않기도 한다.

이러한 상황에서 프로그램의 모든 데이터를 메모리에 올리는 것은 낭비이다. 사용되지 않는 코드를 위해 메모리를 소비하는 것은 물리 메모리의 낭비를 초래하며, 동시에 다른 프로그램이 사용할 수 있는 공간을 제한하게 된다. 따라서 효율적인 실행을 위해 실제로 필요한 부분만 메모리에 적재하는 기법이 필요하다.

Demand Paging: 수요 기반 페이징

이러한 문제를 해결하기 위해 도입된 기법이 바로 Demand Paging이다. Demand Paging은 이름 그대로 프로그램이 페이지를 '요구'할 때에만 해당 페이지를 메모리에 로드하는 방식이다. 프로그램 실행 초기에 전체 프로그램을 메모리에 올리는 대신, 실행 도중 특정 코드나 데이터가 실제로 접근될 때까지 기다렸다가 그때서야 필요한 페이지만 메모리에 적재한다.

이 방식은 프로그램이 물리 메모리보다 더 큰 가상 주소 공간을 사용할 수 있게 해준다. 그 결과, 운영체제는 더 많은 프로그램을 동시에 실행할 수 있고, 디스크로부터 전체 프로그램을 읽어오는 I/O 비용도 줄어든다. 즉, 멀티프로그래밍의 수준이 향상되며, 전체 시스템의 반응성과 자원 활용률도 개선된다.

Demand Paging의 동작 절차는 다음과 같다.

1. 프로그램이 아직 메모리에 없는 페이지에 접근하면, 해당 페이지는 디스크나 백업 저장소에 저장되어 있다.

2. 이때 페이지 폴트가 발생하고, 운영체제는 디스크로부터 해당 페이지를 메모리의 빈 프레임에 적재한다.

3. 이후 페이지 테이블의 항목을 갱신하여, 가상 페이지가 어떤 물리 프레임에 매핑되었는지를 기록한다.

4. 페이지 테이블 내의 해당 항목은 유효(valid) 상태로 변경되어, 다음 접근 시에는 다시 디스크 접근 없이 메모리에서 처리할 수 있게 된다.

이처럼 Demand Paging은 필요할 때만 메모리를 할당하는 지연 적재(lazy loading) 전략을 통해 메모리 낭비를 줄이고, 시스템 전체의 자원 관리를 유연하게 만든다.

Page Fault: 페이지 폴트

Demand Paging이 실제로 작동하는 핵심 메커니즘은 페이지 폴트(Page Fault)이다. 페이지 폴트는 현재 CPU가 접근하려믄 가상 주소에 해당하는 페이지가 아직 물리 메모리에 존재하지 않을 때 발생한다. 이는 페이지 테이블의 해당 항목에서 유효 비트(valid bit)가 0으로 설정되어 있다는 신호로 감지된다.

페이지 폴트가 발생하면, 하드웨어(MMU, 메모리 관리 유닛)는 이를 감지하고 예외(Interrupt)를 발생시킨다. 이 예외는 커널로 전달되며, 운영체제는 해당 프로세스를 일시 중단시키고 페이지 폴트 핸들러라는 특수한 예외 처리 루틴을 수행한다.

페이지 폴트의 처리는 다음과 같은 단계로 이뤄진다.

1. 현재 실행 중인 프로세스의 상태(레지스터, PC 등)를 PCB(Process Control Block)에 저장한다.

2. 커널은 디스크에서 요청된 페이지가 저장된 위치를 파악하고, 빈 메모리 프레임을 할당한다.

3. 해당 페이지를 디스크에서 읽어 메모리로 복사한다.

4. 페이지 테이블을 갱신하여, 가상 페이지와 물리 프레임 간의 새로운 매핑을 등록하고 유효 비트를 1로 설정한다.

5. 다시 프로세스의 문맥을 복구하고, 중단되었던 명령어를 정확히 같은 위치에서 재실행한다.

이처럼 페이지 폴트는 일종의 정상적인 예외 처리 흐름이며, 가상 메모리 시스템에서 필수적인 동작이다. 단, 페이지 폴트가 너무 자주 발생하면 시스템 성능에 큰 영향을 줄 수 있다. 이를 방지하려면 페이지 교체 정책이나 프레임 관리가 중요하게 작동하게 된다.

페이지 폴트의 성능 영향

페이지 폴트는 기본적으로 디스크 I/O를 수반하므로, 시스템의 전체 메모리 접근 시간에 심각한 영향을 준다. 이를 수치로 살펴보면 다음과 같다.

• 일반적인 메모리 접근 시간은 10~200 나노초 수준이다.
• 반면, 페이지 폴트가 발생할 경우, 디스크에서 데이터를 읽어오는 데 8밀리초 이상이 소요된다. 이는 수백만 배의 차이다.

이러한 차이를 고려하여 시스템의 실효 메모리 접근 시간(Effective Memory Access Time)은 다음과 같은 공식으로 표현할 수 있다.

Effective Access Time = (1 - p) × ma + p × page_fault_time
ma: 메모리 접근 시간,
p: 페이지 폴트 발생 확률,
page_fault_time: 페이지 폴트 처리 시간

예를 들어, 메모리 접근 시간이 200ns이고, 페이지 폴트 발생률이 0.001(즉, 1000번 중 1번)이라면 다음과 같이 계산이 된다.

Effective Access Time = 0.999 × 200ns + 0.001 × 8,000,000ns =
= 199.8ns + 8000ns ≈ 8200ns (약 8.2 마이크로초)

이는 단 0.1%의 페이지 폴트만으로도 메모리 접근 시간이 40배 이상 느려지는 결과를 가져온다. 따라서, 페이지 폴트를 최소화하는 전략은 가상 메모리 성능을 높이는 데 있어 매우 중요하다.

Page Replacement: 페이지 교체

페이지 폴트는 운영체제가 필요한 페이지를 디스크에서 메모리로 가져오는 작업을 유발한다. 그런데 만약 물리 메모리 내에 사용 가능한 프레임이 더 이상 존재하지 않는 경우, 단순히 새로운 페이지를 적재하는 것이 불가능하다. 이럴 때 운영체제는 이미 메모리에 존재하는 페이지 중 하나를 내보내고 새로운 페이지로 교체해야 한다. 이 과정을 페이지 교체(Page Replacement)라고 한다.

Page Replacement가 필요한 상황

페이지 교체는 일반적으로 다음과 같은 상황에서 발생한다.

1. 프로세스 실행 중 페이지 폴트 발생
2. 커널이 디스크에 있는 페이지를 불러오려 하지만, 메모리에 빈 프레임이 없음
3. 운영체제는 교체 대상 페이지를 선택해야 하며, 이를 위한 정책이 필요하다.

이 과정은 다음의 세 가지 방식 중 하나로 해결할 수 있다.

• 프로세스 종료 : 가장 단순한 방식으로, 현재 페이지 폴트를 일으킨 프로세스를 종료시켜 그 프로세스가 점유한 모든 프레임을 해제한다. 하지만 이는 현실적인 해결책이 아니므로 보통 사용되지 않는다.
• 프로세스 스와핑(Swapping) : 실행 대기 중인 다른 프로세스를 디스크로 내보내고, 해당 프로세스가 사용하던 모든 페이지를 해제하여 공간을 확보한다. 스와핑은 큰 비용이 들기 때문에 필요한 경우에만 제한적으로 사용된다.
• 페이지 교체(Page Replacement) : 현재 메모리에 존재하는 하나의 페이지만 선택적으로 제거하여 그 자리에 새로운 페이지를 적재하는 방식이다. 이는 가장 일반적인 방법으로, 대부분의 운영체제가 채택한다.

페이지 교체 절차

페이지 교체가 이루어지는 순서는 다음과 같다.
1. 커널은 메모리에서 교체할 페이지를 결정한다. 이를 위해 페이지 교체 알고리즘이 사용된다.
2. 해당 페이지가 수정된 적이 있다면, 디스크에 기록(페이지 아웃)하고, 그렇지 않다면 그냥 패기한다.
3. 새로운 페이지를 디스크에서 읽어 해당 프레임에 적재한다.
4. 페이지 테이블을 갱신하여, 교체된 페이지를 "유효하지 않음" 상태로 표시하고, 새로 적재한 페이지를 "유효" 상태로 설정한다.

이 과정은 효율적인 교체 정책이 없으면 성능 저하를 유발한다. 특히 잘못된 페이지가 교체되면 곧바로 다시 페이지 폴트가 발생할 수 있어 시스템의 효율성을 떨어뜨릴 수 있다.

수정 비트(Modify or Dirty Bit)의 활용

페이지 교체 과정에서 또 하나의 중요한 요소는 수정 비트(Modify 또는 Dirty bit)이다. 이 비트는 해당 페이지가 메모리에서 변경되었는지 여부를 나타낸다.

• 페이지가 메모리에 있는 동안 변경된 경우, 수정 비트는 1로 설정된다. 이 경우, 해당 페이지를 디스크에 저장해야 손실 없이 교체할 수 있다.
• 반면, 수정되지 않은 페이지는 디스크의 복사본과 동일하므로 다시 저장할 필요 없이 폐기할 수 있다.

이 기능은 페이지 교체 시간과 I/O 부하를 줄이는 데 효과적이다. 수정 비트가 없다면 모든 페이지는 교체 전 디스크에 다시 저장되어야 하므로 불필요한 디스크 쓰기가 발생하게 된다.

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

가상 메모리 시스템에서 실행 중인 프로세스가 페이지 폴트를 일으켰을 때, 메모리에 여유 프레임이 없다면 운영체제는 기존의 어떤 페이지를 제거하고 새로운 페이지를 적재해야 한다. 이때 어떤 페이지를 제거할지를 결정하는 방식이 페이지 교체 알고리즘(Page Replacement Algorithm)이다.

페이지 교체 알고리즘은 시스템의 성능에 직접적인 영향을 준다. 페이지 폴트가 자주 발생하면 성능이 급격히 저하되므로, 페이지 폴트 발생률(Page-fault rate)을 최소화하는 것이 중요한 목표이다. 알고리즘의 효율성은 주어진 참조 문자열(reference string)에 따라 측정되며, 이는 프로세스가 실행 중 접근하는 메모리 주소들의 순서를 나타낸다. 예를 들어 1,2,3,4,1,2,5,1,2,3,4,5와 같은 참조 문자열을 사용해 알고리즘을 비교하고 평가할 수 있다.

FIFO(First-In, First-Out) Page Replacement

FIFO 알고리즘은 메모리에 가장 먼저 들어온 페이지를 가장 먼저 교체하는 방식이다. 운영체제는 메모리에 올라온 순서를 큐(Queue) 형태로 관리하며, 큐의 앞쪽에 위치한 페이지를 제거하게 된다.

• 장점 : 구현이 간단하다.

• 단점 : 오래된 페이지가 아직도 활발히 사용되는 경우에도 교체 대상이 되어, 실제 성능이 낮아질 수 있다. 이러한 현상을 Belady의 이상(Belady's anomaly)라고 한다.

  

Optimal Page Replacement(최적 교체 알고리즘)

최적 알고리즘(OPT)은 가장 이상적인 페이지 교체 알고리즘으로, 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선택한다. 즉, 참조 문자열의 미래를 알고 있다고 가정하고, 가장 늦게 참조될 페이지를 제거한다.

• 장점 : 이론적으로 가장 낮은 페이지 폴트율을 가진다.
• 단점 : 미래의 참조를 예측해야 하므로, 실제 시스템에서는 구현이 불가능하다. 다만 다른 알고리즘의 성능을 평가하기 위한 기준으로 사용된다.

LRU(Least Recently Used) 교체 알고리즘

LRU 알고리즘은 과거의 접근 이력을 기반으로, 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식이다. 이는 "가장 오래 전에 사용된 페이지는 당분간도 사용되지 않을 가능성이 크다"는 시간 지역성(temporal locality)의 원칙에 기반한다.

• 구현 방식
  - 스택 방식 : 페이지를 스택으로 관리하여 참조 시마다 가장 위로 올린다(가장 위에가 가장 최근에 사용된 페이지). 가장 아래에 있는 페이지가 교체 대상이 된다.
  

  • 카운터 방식 : 각 페이지에 마지막으로 참조된 시간을 기록하여 가장 오래된 시간을 가진 페이지를 선택한다.

• 단점 : 참조 시마다 스택을 정렬하거나 시간을 갱신해야 하므로, 구현이 복잡하고 성능 오버헤드가 크다. 이로 인해 실제 하드웨어에서는 잘 지원되지 않는다.

LRU-Approximation Page Replacement

실제 컴퓨터 시스템은 LRU를 완벽히 구현하기 어려우므로, 이를 근사화한 알고리즘들이 사용된다. 대표적인 방식으로 참조 비트(reference bit)를 활용하는 것이다.

• 기본 원리
  - 하드웨어는 각 페이지에 대해 참조 비트를 제공하며, 해당 페이지가 접근될 때 참조 비트를 1로 설정한다.
  • 운영체제는 주기적으로 이 비트를 0으로 초기화하고, 이후 1로 다시 설정된 비트를 통해 어떤 페이지가 최근에 사용되었는지 파악한다.

이 방식은 "최근에 사용되었는가?" 정도의 정보만 알 수 있고, 정확한 참조 순서를 알 수는 없다.

Second-Chance Algorithm

Second-Chance 알고리즘은 FIFO 방식에 참조 비트를 추가하여 성능을 개선한 방식이다. 모든 페이지는 원형 큐(Circular queue)로 관리되며, 교체 대상이 된 페이지의 참조 비트를 검사하여 다음과 같이 처리한다.
1. 참조 비트가 0이면, 해당 페이지는 최근에 사용되지 않았으므로 즉시 교체한다.
2. 참조 비트가 1이면, 페이지에 두 번째 기회를 주고 참조 비트를 0으로 리셋한 뒤 큐의 뒤로 이동시킨다. 그리고 다음 페이지로 넘어간다.

이 과정을 반복하면서 결국 참조 비트가 0인 페이지를 찾을 때까지 진행된다.

• 구현 방식 : 시계 알고리즘(clock algorithm)이라고도 하며, 실제로는 큐 대신 원형 배열과 포인터를 사용해 페이지를 순회한다.
• 장점 : 구현이 간단하면서도 LRU에 가까운 성능을 제공하며, 실제 운영체제에서도 널리 사용된다.

Enhanced Second-Chance Algorithm

기존 Second-Chance 알고리즘은 페이지가 최근에 사용되었는지 여부만을 고려하여 교체 여부를 결정한다. 하지만, 페이지가 수정되었는지 여부도 시스템 성능에 중요한 영향을 미친다. 수정된 페이지는 디스크에 다시 저장(write-back)해야 하므로, 교체 시 더 많은 시간이 걸리고 I/O 병목이 발생할 수 있다.

이 문제를 해결하기 위해 참조 비트(Reference Bit)와 수정 비트(Modified Bit)가 함께 사용된다. 두 비트를 쌍으로 묶어 각 페이지를 네 가지 상태로 분류하고, 그 상태에 따라 교체 우선순위를 다음과 같이 설정한다.

(Reference Bit, Modified Bit)	의미	교체 우선순위
(0, 0)	최근에 사용되지 않았고, 수정되지 않음	가장 적합
(0, 1)	최근에 사용되지 않았지만 수정됨	그다음 우선
(1, 0)	최근에 사용되었고, 수정되지 않음	보류 가능
(1, 1)	최근에 사용되었고, 수정되었음	교체 지양

이 방식은 디스크에 쓰기 작업을 최소화하면서도 자주 사용되지 않는 페이지를 효과적으로 제거할 수 있게 한다.

Counting-Based Page Replacement

카운팅 기반 페이지 교체 방식은 각 페이지에 대해 접근 횟수를 세는 카운터를 관리한다. 이를 통해 자주 또는 거의 사용되지 않는 페이지를 구분하여 교체 대상 페이지를 선정한다.

• LFU(Least Frequently Used) : 접근 횟수가 가장 적은 페이지를 교체한다. 즉, 오랫동안 거의 사용되지 않은 페이지는 앞으로도 사용될 가능성이 적다고 가정한다.
• MFU(Most Frequently Used) : 가장 많이 사용된 페이지를 교체한다. 이는 "가장 많이 사용된 페이지는 방금 들어온 새 페이지일 가능성이 있다."는 논리에 근거한다. 새로 들어온 페이지는 아직 활발히 쓰이지 않을 수도 있기 때문이다.

하지만 이러한 알고리즘들은 다음과 같은 단점이 있다.

• 각 페이지마다 카운터를 관리해야 하므로 추가적인 메모리 공간이 필요하다.
• 모든 페이지 중에서 가장 적절한 카운터 값을 가진 페이지를 탐색하는 비용이 크다.

이러한 비용 때문에 실제 시스템에서는 잘 사용되지 않으며, 실험적이거나 학술적인 목적에 가깝다.

Thrashing

스레싱은 프로세스가 충분한 메모리 프레임을 할당받지 못해 지속적이고 빈번하게 페이지 폴트가 발생하는 현상이다. 이로 인해 메모리에 적재된 페이지가 다른 페이지로 자꾸 교체되며, 이전에 사용하던 페이지가 곧바로 다시 필요해지는 악순환이 발생한다.

예시 시나리오

• 프로세스 P1이 실행되며 필요한 페이지를 메모리에 적재한다.
• 다른 프로세스 P2가 실행되며 프레임을 점유하고, P1의 페이지 일부를 교체한다.
• P1이 다시 실행되면, 이전에 사용하던 페이지가 없어 다시 페이지 폴트가 발생한다. -> 또 교체됨
• 이처럼 서로 반복되면서 계속해서 디스크와 메모리 간의 페이지 교환이 발생하며 CPU는 계산보다 I/O에 대부분의 시간을 소모하게 된다.

해결책 :

• 지역 교체 알고리즘(Local Replacement)
  - 각 프로세스는 자신에게 할당된 프레임 안에서만 페이지 교체를 수행한다.

  • 장점 : 다른 프로세스의 메모리를 침범하지 않아 안정적이다.
  • 단점 : 여전히 각 프로세스가 요구하는 프레임 수를 고려하지 않기 때문에 스레싱 자체를 완전히 해결하지는 못한다.

• 지역성 모델(Locality Model) 활용
  - 운영체제가 프로세스의 지역성(Locality)을 분석하여, 필요한 만큼의 프레임을 제공한다.

  • 지역성이란 프로그램 실행 중 특정 시간 동안 함께 사용되는 페이지들의 집합을 의미한다.
  • 예: 어떤 함수 내에서 페이지 10, 11, 12가 자주 함께 접근된다면, 이들이 하나의 지역성을 구성한다.
  • 운영체제는 이 지역성에 맞춰 프레임을 적절히 배분함으로써 불필요한 페이지 교체를 줄이고 스래싱을 방지할 수 있다.

  Locality Model

  지역성(Locality)은 프로그램이 실행되는 동안 특정 페이지들의 집합이 집중적으로 사용되는 현상을 의미한다. 이 개념은 페이지 교체 알고리즘의 효율을 높이기 위한 핵심 이론으로 작용한다.

  정의 및 예시

  지역성은 프로그램의 구조에 의해 결정되며, 자주 함께 접근되는 메모리 위치들의 집합이다. 예를 들어, 함수 Func0()이 실행될 때, 내부에서 동적 할당을 하고 초기화를 수행하며, 다른 함수 Func1()을 호출한다고 하자. 이 과정에서 연속된 페이지 10, 11, 12가 집중적으로 사용된다면, 이들이 하나의 지역성(Locality)을 형성한다고 볼 수 있다.
  

이 코드 실행 동안 페이지 10(스택), 11(함수 코드), 12(malloc, memset 등)이 함께 사용되며, 이들이 메모리에 없다면 연속적으로 페이지 폴트가 발생하게 된다.

페이지 폴트 최소화

운영체제는 프로세스의 현재 지역성을 파악하고, 그 지역성을 커버할 수 있을 만큼의 프레임을 할당함으로써 페이지 폴트를 줄이고 성능을 향상시킬 수 있다.

지역성의 유형

• 시간적 지역성(Temporal Locality) : 최근에 참조된 데이터가 가까운 시간 내에 다시 참조되는 경향
• 공간 지역성(Spatial Locality) : 인접한 주소의 데이터들이 함께 사용되는 경향

이러한 지역성은 CPU 캐시뿐만 아니라 페이지 교체에서도 중요한 역할을 한다.

Working-Set Model

워킹셋 모델은 프로세스가 실제로 얼마나 많은 페이지를 필요로 하는지를 동적으로 파악하기 위한 방법이다. 이 모델은 지역성을 수치적으로 추정하고, 이에 기반하여 적절한 수의 프레임을 할당하는 데 목적이 있다.

• Δ(델타) : 워킹셋 윈도우(window)라고 하며, 최근에 참조된 페이지 수의 기준이 되는 고정된 참조 수이다. 예를 들어 Δ=10,000이면 최근 10,000번의 메모리 참조를 기준으로 워킹셋을 계산한다.
• 워킹셋(Working Set) : 가장 최근 Δ개의 참조 안에서 접근된 페이지들의 집합. 이는 현재 프로세스가 활동적으로 사용하는 지역성의 근사치라 할 수 있다.

동작 예시

Δ = 10인 경우, 시간 t1에서의 워킹셋이 {1, 2, 5, 6, 7}이라면, t2로 시간이 지나면서 워킹셋이 {3, 4}로 바뀔 수 있다. 이는 프로그램의 지역성이 시간에 따라 변화함을 나타낸다.

시스템에서의 적용
각 프로세스 Pi의 워킹셋 크기를 WSSi라 하면, 시스템 전체의 총 프레임 수요는 다음과 같이 표현된다.

D = Σ WSSᵢ

여기서 D는 모든 프로세스의 워킹셋을 합한 값이고, m은 시스템의 총 프레임 수이다.

• 만약 D > m 이라면, 전체 시스템이 현재 필요한 페이지들을 다 담을 수 없어 스래싱(Thrashing)이 발생한다.
• 이 경우, 운영체제는 일부 프로세스를 일시 중지(suspend)시키고 메모리에서 스왑 아웃하여 D를 감소시킨다.
• 반대로 D < m일 경우, 새로운 프로세스를 실행할 수 있는 여유가 생긴 것으로 판단되어 새로운 프로세스의 시작이 가능해진다.