가상메모리와 페이지 교체 알고리즘

가상 메모리란

메인 메모리의 크기는 한정되어 있기 때문에 물리적인 메모리의 크기보다 큰 프로세스는 어떻게 실행되는 걸까?
가상 메모리란 실제 물리적 메모리(RAM) 보다 더 많은 메모리를 사용할 수 있도록 하는 메모리 관리 기법을 말한다.
즉 가상 메모리는 물리적 메모리와 독립적 논리적 주소 공간을 분리해서 작은 메모리를 가지고 큰 가상주소 공간을 제공하는 것이다.

가상 메모리는 필요한 부분만 메모리에 올림으로써 메모리에 올라가는 프로세스의 크기를 줄이는 요구 페이징 기법을 사용한다.

 

요구 페이징(Demand Paging)이란

가상 메모리는 메모리를 고정된 크기로 나눠서 관리하며 이를 페이지라고 부른다.
요구 페이징이란 프로그램이 실행될 때 모든 페이지를 처음부터 메모리에 적재하는 것이 아니라, 실제로 접근할 때만 메모리에 불러오는 방식이다.

 

요구 페이징의 작동 방식

요구 페이징은 아래 방식으로 작동한다.

1. 프로그램이 실행될 때 전체 프로그램이 메모리에 적재되지 않고, 일부 필수적인 페이지만 로드된다.
2. 프로세스가 특정 페이지에 접근하려고 할 때 해당 페이지가 메모리에 존재하지 않으면 페이지 폴트(Page Fault)가 발생한다.
3. 페이지 폴트가 발생하면 운영체제가 그 페이지를 하드 디스크에서 가져와 메모리에 적재하고, 프로세스의 실행을 재개한다.

 

요구 페이징의 장점

• 효율적인 메모리 사용
  필요한 페이지만 메모리에 적재하므로 메모리 낭비를 줄일 수 있다.
• 빠른 프로그램 시작
  프로그램을 실행할 때 전체를 메모리에 로드하지 않으므로 실행 속도가 빨라진다.
• 메모리 절약
  여러 프로그램을 동시에 실행할 수 있고, 전체 메모리 요구량이 감소한다.

 

요구 페이징의 단점

• 페이지 폴트 오버헤드
  페이지 폴트가 자주 발생하면 디스크 접근이 많아져 성능이 저하될 수 있다.
• 복잡성 증가
  요구 페이징을 구현하려면 추가적인 하드웨어와 소프트웨어 관리가 필요하다.
• 스레싱(Thrashing)
  만약 프로세스가 자주 페이지를 교체해야 하는 경우, 시스템 성능이 크게 떨어지는 현상이 발생할 수 있다. 이것은 메모리 관리가 제대로 되지 않아 대부분의 시간을 페이지 교체에만 사용하게 될 때 일어난다.

 

페이지 교체 알고리즘

페이지 교체 알고리즘은 가상 메모리에서 페이지 폴트가 발생했을 때, 물리 메모리에 새로운 페이지를 적재하기 위해 어떤 페이지를 내보낼지 결정하는 방법이다.
즉, 페이지 폴트 발생을 최소화하는 것이다!

 

FIFO(FIrst-In-First-out) 알고리즘

FIFO(나만 피포라고 부르나) 페이지 교체 알고리즘은 가장 먼저 메모리에 들어온 페이지를 내보내는 방식이다.
너 오래 있었으니까 나가! 인 것이다.

• 장점
  • 이해하기 쉽고 구현이 간단하다.
• 단점
  • 오래된 페이지가 자주 사용되는 페이지일 수도 있다.(되려 페이지 부재율이 높아질 수 있다.)
  • 벨라디의 모순

 

벨라디의 모순이란?

페이지 교체 알고리즘 중 FIFO(First-In-First-Out) 알고리즘을 사용할 때 발생할 수 있는 특이한 현상으로, 메모리 프레임 수가 증가했음에도 불구하고 페이지 폴트 횟수가 오히려 증가하는 현상을 말한다.

페이지 참조 문자열이 다음과 같을 때를 예로 들어보자.

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

이 참조 문자열에 대해 프레임이 3개일 때와 4개일 때를 비교해 보자.

 

1. 프레임이 3개일 때

• 1 (폴트 발생) → 메모리: [1]
• 2 (폴트 발생) → 메모리: [1, 2]
• 3 (폴트 발생) → 메모리: [1, 2, 3]
• 4 (폴트 발생, 1 교체) → 메모리: [4, 2, 3]
• 1 (폴트 발생, 2 교체) → 메모리: [4, 1, 3]
• 2 (폴트 발생, 3 교체) → 메모리: [4, 1, 2]
• 5 (폴트 발생, 4 교체) → 메모리: [5, 1, 2]
• 1 (이미 메모리에 있음) → 메모리: [5, 1, 2]
• 2 (이미 메모리에 있음) → 메모리: [5, 1, 2]
• 3 (폴트 발생, 5 교체) → 메모리: [3, 1, 2]
• 4 (폴트 발생, 1 교체) → 메모리: [3, 4, 2]
• 5 (폴트 발생, 2 교체) → 메모리: [3, 4, 5]

총 페이지 폴트: 9회

 

2. 프레임이 4개일 때

• 1 (폴트 발생) → 메모리: [1]
• 2 (폴트 발생) → 메모리: [1, 2]
• 3 (폴트 발생) → 메모리: [1, 2, 3]
• 4 (폴트 발생) → 메모리: [1, 2, 3, 4]
• 1 (이미 메모리에 있음) → 메모리: [1, 2, 3, 4]
• 2 (이미 메모리에 있음) → 메모리: [1, 2, 3, 4]
• 5 (폴트 발생, 1 교체) → 메모리: [5, 2, 3, 4]
• 1 (폴트 발생, 2 교체) → 메모리: [5, 1, 3, 4]
• 2 (폴트 발생, 3 교체) → 메모리: [5, 1, 2, 4]
• 3 (폴트 발생, 4 교체) → 메모리: [5, 1, 2, 3]
• 4 (폴트 발생, 5 교체) → 메모리: [4, 1, 2, 3]
• 5 (폴트 발생, 1 교체) → 메모리: [4, 5, 2, 3]

총 페이지 폴트: 10회

이렇게 프레임 수가 3개에서 4개로 늘어났음에도 내보낸 페이지가 자주 사용되는 페이지일 경우 오히려 페이지 폴트가 증가한 것을 확인할 수 있다.
즉, 메모리 크기가 늘어남에도 불구하고 페이지가 폴트가 증가하는 비효율적인 상황이 발생하는 것이다. 

 

 

OPT (Optimal Page Replacement) 알고리즘 - 최적 페이지 교체

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식이다.
FIFO 알고리즘의 벨라디 모순도 일어나지 않고 이론적으로는 가장 효율적인 알고리즘이다.

• 장점
  • 가장 적은 페이지 폴트 발생
• 단점
  • 미래의 메모리 참조를 예측할 수 없기 때문에 실제 시스템에서 구현하기는 어렵다.

 

LRU(Least Recently Used) 알고리즘

과거의 메모리 접근 기록을 바탕으로 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식이다.

• 장점
  • 실제 시스템에서 꽤 효율적으로 작동한다.
• 단점
  • 메모리 접근 시간을 기록해야 하기 때문에 구현이 복잡하다.

 

LFU (Least Frequently Used) 알고리즘

참조 횟수가 가장 적은 페이지를 교체하는 방식이다.
페이지가 얼마나 자주 참조되었는지를 기록하고, 참조 횟수가 가장 적은 페이지를 내보낸다.

활발하게 사용되는 페이지는 앞으로도 참조 횟수가 많아질 거라는 가정에서 만들어졌다.

• 장점
  • 자주 사용되지 않은 페이지를 내보내기 때문에 효율적일 수 있다.
• 단점
  • 어떤 프로세스가 특정 페이지를 집중적으로 사용하다가 더 이상 사용하지 않는데도 계속 메모리에 남아있을 수 있다(초반에 몰빵으로 사용하다가 안 할 수도 있으니 가정에 어긋남)

 

MFU (Most Frequently Used) 알고리즘

LFU의 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 방식이다.
참조 횟수가 가장 적은 페이지가 최근에 메모리에 올라왔고, 앞으로 계속 사용될 것이라는 가정에 기반한다.

 

 

 

 

참고

Virtual Memory