가상 메모리

가상 메모리(Virtual Memory)

메모리 관리는 한정된 물리 메모리(RAM) 자원을 여러 프로세스가 효율적이고 안전하게 나눠 쓰도록 관리하는 기술입니다. 가상 메모리(Virtual Memory) 는 이 메모리 관리 기법의 정점으로, 현대 운영체제가 페이징(Paging) 및 세그먼테이션 기법을 기반으로 구현한 핵심 개념입니다.

가상 메모리의 핵심 목표는 두 가지입니다.

• 불연속 할당 : 프로세스를 물리 메모리에 연속적으로 배치할 필요 없이, 조각내어(주로 페이징) 효율적으로 관리합니다.
• RAM보다 큰 프로그램 실행 : 당장 실행에 필요한 부분만 RAM에 올리고(by 동적 로딩), 나머지는 디스크(스왑 공간) 에 둠으로써, 물리 RAM 크기보다 더 큰 프로그램도 실행할 수 있게 합니다.

이를 통해 OS는 각 프로세스에게 “물리 메모리의 크기에 구애받지 않는, 거대하고 독립적인 자신만의 주소 공간” 을 제공하는 것처럼 추상화합니다.

요구 페이징(Demand Paging)

요구 페이징은 가상 메모리 시스템을 페이징 기법으로 구현하는 가장 보편적인 방식입니다. 이는 가상 메모리의 ‘동적 로딩’ 버전에 해당합니다.

즉, 프로세스 시작 시 모든 페이지를 RAM에 올리는 것이 아니라, 해당 페이지가 ‘실제로 요청(Demand)될 때’ 비로소 디스크에서 RAM으로 가져옵니다. (Lazy Loading)

요구 페이징의 작동 원리

1. 프로세스가 실행되면, OS는 해당 프로세스의 페이지 테이블을 생성하여 메모리에 올립니다.
2. 이때, 페이지 테이블의 모든 항목(Page Table Entry)에는 “해당 페이지가 아직 물리 메모리에 없음”을 나타내는 ‘Invalid’ 비트가 설정됩니다. (어떤 페이지도 RAM에 올라오지 않은 상태)
3. CPU가 프로세스의 가상 주소(명령어)에 접근을 시작합니다.
4. 만약 CPU가 참조하려는 페이지가 ‘Invalid’로 표시되어 있다면(즉, 메모리에 없다면), 하드웨어(MMU)는 페이지 폴트(Page Fault) 라는 트랩(Trap)을 발생시킵니다.

페이지 폴트 (Page Fault)

페이지 폴트는 “프로세스가 참조하는 페이지가 현재 물리 메모리에 없는 경우” 발생하는 일종의 소프트웨어 인터럽트입니다.

이는 오류가 아니라, OS에게 “필요한 페이지를 디스크에서 RAM으로 가져와달라”고 요청하는 정상적이고 핵심적인 신호입니다. 필요한 데이터를 디스크에서 가져오는 작업(I/O)은 특권 명령이므로, 프로세스가 직접 수행할 수 없어 인터럽트를 통해 운영체제(커널)에게 작업을 위임하는 것입니다.

페이지 폴트 처리 과정 (Handler)

페이지 폴트가 발생하면, CPU는 제어권을 OS 커널의 ‘페이지 폴트 핸들러’ 로 넘깁니다. 핸들러는 다음 순서로 작업을 처리합니다.

1. OS가 이 요청이 유효한 접근인지(단지 RAM에 없는 것인지), 아니면 잘못된 주소 접근(Segmentation Fault)인지 확인합니다.
2. (유효하다면) 디스크(스왑 공간) 에서 해당 페이지의 위치를 찾습니다.
3. 물리 메모리(RAM)에서 빈 프레임을 찾습니다.
4. (페이지 교체 발생 지점) 만약 빈 프레임이 없다면, 즉 메모리가 꽉 차 있다면, OS는 페이지 교체 알고리즘을 실행하여 RAM에 있는 기존 페이지 중 하나를 ‘희생양(Victim)’으로 골라 디스크로 쫓아내고(Page-out), 그 자리를 확보합니다.
5. 디스크 I/O를 발생시켜 요청된 페이지를 빈 프레임으로 읽어옵니다(Page-in). (이 작업은 매우 느립니다.)
6. 페이지 테이블을 갱신합니다. (해당 페이지의 비트를 ‘Invalid’ → ‘Valid’로 변경하고, 프레임 번호를 기록합니다.)
7. 페이지 폴트를 유발했던 명령어를 재시작합니다. (이제 해당 페이지가 ‘Valid’ 상태이므로 정상적으로 실행됩니다.)

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

페이지 폴트 처리 과정에서 가장 비용이 큰 부분은 5단계, 즉 디스크 I/O(Page-in) 작업입니다. 디스크 접근 속도는 RAM 접근 속도보다 수만 배에서 수백만 배 느립니다.

만약 메모리 공간이 부족(4단계)하여 페이지 교체(Page-out) 까지 발생한다면, 디스크 쓰기(Write)와 디스크 읽기(Read)가 연달아 발생하므로 성능 저하는 더욱 심각해집니다.

따라서 가상 메모리 시스템의 전체 성능은 “어떤 페이지를 디스크로 쫓아낼지(페이지 교체)” 를 얼마나 현명하게 결정하느냐에 달려있습니다. 이것이 바로 다음에 다룰 페이지 교체 알고리즘이 중요한 이유입니다.

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

가상 메모리 시스템은 페이지 폴트(Page Fault)가 발생했을 때 물리 메모리(RAM)에 빈 프레임이 있어야 새 페이지를 디스크에서 가져올 수 있습니다. 만약 빈 프레임이 없다면, OS는 페이지 교체 알고리즘을 사용하여 메모리에 있는 기존 페이지 중 하나를 ‘희생양(Victim)’으로 선택해 디스크로 쫓아내고(Page-out) 그 자리를 확보합니다.

이 알고리즘의 궁극적인 목표는 미래의 페이지 폴트 발생 횟수를 최소화하는 것입니다.

FIFO(First-In, First-Out)

가장 간단한 알고리즘으로, “가장 먼저 메모리에 들어온(가장 오래된) 페이지를 가장 먼저 교체” 합니다. 페이지가 메모리에 들어온 순서를 큐(Queue) 자료구조로 관리합니다. OS가 해야 할 일이 적어 구현이 매우 간단하고 직관적입니다.

• 페이지가 얼마나 ‘자주’ 사용되는지는 전혀 고려하지 않고, 단지 ‘오래됐다’는 이유만으로 교체합니다. 이로 인해, 시스템 부팅 직후부터 계속 사용되는 핵심 커널 페이지가 쫓겨날 수도 있습니다.
• 벨라디의 역설 (Belady’s Anomaly) : 이 알고리즘의 비효율성을 보여주는 대표적인 현상입니다. 물리 메모리 프레임의 수를 늘려주었음에도 불구하고(즉, RAM을 증설했음에도) 오히려 페이지 폴트가 더 증가할 수 있습니다.

OPT(Optimal Page Replacement)

“미래에 가장 오랫동안 사용되지 않을 페이지를 교체” 하는, 이론적으로 가장 효율적인 알고리즘입니다. 이 알고리즘은 페이지 폴트 횟수를 최소화할 수 있음이 보장됩니다.

• 이름 그대로 ‘최적(Optimal)’이지만, OS가 미래에 어떤 페이지가 참조될지 예측하는 것은 불가능합니다.
• 실제 시스템에서 구현하기 위한 것이 아니라, 다른 (실제 구현 가능한) 알고리즘들의 성능을 평가하기 위한 ‘이론적 기준선(Benchmark)’ 으로 사용됩니다.

LRU(Least Recently Used)

OPT가 ‘미래’를 본다면, LRU는 ‘과거’ 를 기반으로 미래를 예측합니다. 즉, “가장 오랫동안 사용되지 않은(가장 최근에 참조되지 않은) 페이지를 교체” 합니다.

“가장 최근에 사용된 페이지는 가까운 미래에도 다시 사용될 것이다”라는 참조의 지역성(Locality of Reference) 원리에 기반하며, OPT 알고리즘에 근접하는 매우 좋은 성능을 보여줍니다.

• 이 알고리즘을 완벽하게 구현하려면, 메모리에 접근할 때마다 모든 페이지의 참조 시간을 기록하거나, 페이지의 순서를 연결 리스트(Linked List)로 계속 재정렬해야 합니다. 이는 막대한 하드웨어 비용 또는 소프트웨어 오버헤드를 발생시켜 현실적으로 구현하기 어렵습니다.

LFU(Least Frequently Used)

“참조 횟수가 가장 적은 페이지를 교체” 하는 방식입니다. 각 페이지마다 참조 횟수를 세는 카운터(Counter)를 두며, 자주 사용되는 페이지(카운터가 높은 페이지)를 우선적으로 유지합니다.

• 과거의 참조 횟수 누적: 프로그램 초기에 1,000번 참조되었지만 지금은 전혀 쓰이지 않는 페이지가, 최근에 100번 참조된 페이지보다 락(Lock)에 걸려 메모리에 계속 남아있을 수 있습니다.
• LRU와 마찬가지로 카운터를 관리하는 오버헤드가 발생합니다.

Second-Chance(Clock Algorithm)

이 알고리즘은 LRU의 뛰어난 성능과 FIFO의 낮은 오버헤드를 절충한, 현실적인 LRU 근사(Approximation) 알고리즘입니다. 대부분의 현대 OS가 이와 유사한 방식을 채택합니다.

하드웨어의 지원을 받는 1비트짜리 참조 비트(Reference Bit) 를 사용합니다. 페이지가 참조(읽기/쓰기)되면, 하드웨어가 자동으로 이 비트를 1로 설정합니다.

• 구현 (시계 형태)
  1. 모든 페이지 프레임을 원형 큐(Circular Queue) 형태로 관리하며, ‘시곗바늘(Pointer)’이 특정 프레임을 가리킵니다.
  2. 페이지 교체가 필요하면, 시곗바늘이 가리키는 프레임의 참조 비트를 확인합니다.
  3. If (참조 비트 == 1): “최근에 사용되었음”. 이 페이지는 ‘두 번째 기회(Second Chance)’를 받습니다. 비트를 0으로 바꾸고 시곗바늘을 다음 프레임으로 이동합니다. (교체 연기)
  4. If (참조 비트 == 0): “최근에 사용되지 않았음”. 이 페이지가 ‘희생양’입니다. 이 페이지를 교체하고 시곗바늘을 다음 프레임으로 이동합니다.

비트를 1에서 0으로 바꾸고 한 바퀴 도는 동안, 최근에 사용되지 않은(비트=0) 페이지만 교체되므로 LRU와 매우 유사하게 동작합니다. 구현이 비교적 간단하면서도 FIFO보다 페이지 폴트를 획기적으로 줄일 수 있습니다.

스레싱(Thrashing)

가상 메모리 시스템의 성능이 급격하게 저하되어, CPU가 실제 ‘작업(연산)’은 거의 수행하지 못하고 페이지 교체(디스크 I/O)만 하느라 시스템 전체가 마비 상태에 이르는 현상을 의미합니다.

• 물리 메모리(RAM)에 너무 많은 프로세스(혹은 너무 큰 프로세스)가 동시에 올라와 과도한 경쟁(Over-commitment) 을 할 때 발생합니다.
• 각 프로세스가 실제 실행에 최소한으로 필요한 페이지 집합(Working Set) 조차 RAM에 유지하지 못하게 됩니다.

악순환의 고리

1. 프로세스 A가 실행되려 하니 페이지 1이 필요해 페이지 폴트가 발생합니다.
2. OS가 페이지 2를 디스크로 쫓아내고 페이지 1을 가져옵니다.
3. CPU가 프로세스 A의 다음 명령어를 실행하려 하니 페이지 2가 필요해 또 페이지 폴트가 발생합니다.
4. OS가 페이지 3을 쫓아내고 페이지 2를 가져옵니다.
5. 다음 순간 페이지 3이 필요해 또 페이지 폴트가… (반복)
   • 결과 : CPU 이용률은 0%에 수렴하고, 디스크 I/O만 100%가 되는 최악의 상황이 발생합니다.

• 해결책
  • OS는 이 ‘스레싱’ 상태를 감지해야 합니다. (페이지 폴트율을 모니터링)
  • 스레싱이 감지되면, OS는 다중 프로그래밍 정도(Multiprogramming Degree) 를 낮추어야 합니다. 즉, 현재 실행 중인 프로세스 중 일부를 강제로 ‘중지(Suspend)’ 상태로 만들거나(디스크로 통째로 Swap-out), 새 프로세스가 시작되는 것을 막아 메모리 경쟁을 줄여야 합니다.