가상 메모리

다중 프로그래밍을 실현하기 위해서는 많은 프로세스들을 동시에 메모리에 올려두어야 한다. 가상 메모리는 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법이며, 프로그램이 물리 메모리보다 커도 된다는 주요 장점이 있다.

가상 메모리 개발 배경

과거에는 실행되는 코드의 전부를 물리 메모리에 올려야 했고, 실행하고자 하는 코드가 메모리보다 클 경우에는 아예 실행할 수 없었다. 또한 여러 프로그램이 동시에 메모리에 올라가는 것은 용량 문제나 페이지 스위칭 등의 성능 이슈가 발생하였다. 가끔만 사용되는 코드 또한 물리 메모리에 올라가 메모리 공간을 차지하는 것을 보고, 프로그램 전체를 메모리에 올리지 않아도 실행시킬 수 있겠다는 아이디어가 탄생한다.

프로그램의 일부만을 메모리에 올려도 실행이 가능하게 되면 다음과 같은 이점들을 챙길 수 있게 된다.

• 물리 메모리 크기에 제약받지 않게 된다.
• 더 많은 프로그램들을 동시에 실행할 수 있게 된다. 이에 따라 응답시간은 유지되고, CPU 이용율과 처리율은 높아진다.
• swap에 필요한 입출력이 줄어들기 때문에 프로그램들이 빠르게 실행된다.

가상 메모리가 하는 일

가상 메모리는 실제의 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한 것으로 정리할 수 있다. 이로써 작은 메모리를 가지고도 얼마든지 큰 가상 주소 공간을 프로그래머에게 제공할 수 있다.

가상 주소 공간

한 프로세스가 메모리에 저장되는 논리적인 모습을 가상 메모리에 구현한 공간이다. 프로세스가 요구하는 메모리 공간을 가상 메모리에서 제공함으로써 현재 직접적으로 필요치 않은 메모리 공간은 실제 물리 메모리에 올리지 않는 것으로 물리 메모리를 절약할 수 있다.

• Ex) 한 프로그램이 실행되기 위해 100KB의 논리 메모리가 필요하고, 실행까지 필요한 메모리 공간(Heap, Stack, Code, Data)의 합이 40KB일 경우, 실제 물리 메모리에는 40KB만 올라가 있고, 나머지 60KB 만큼은 필요시에 물리 메모리에 요구한다.
  

프로세스간의 페이지 공유

• 시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있도록 한다. 각 프로세스들은 공유 라이브러리를 자신의 가상 주소 공간에 두고 사용하는 것처럼 인식하지만, 라이브러리가 올라가 있는 물리 메모리 페이지들은 모든 프로세스에 공유되고 있다.
• 프로세스 간의 메모리 공유를 가능하게 하고, 프로세스들은 공유 메모리를 통해 통신할 수 있다. 이 또한, 각 프로세스들은 각자 자신의 주소 공간처럼 인식하지만, 실제 물리 메모리는 공유되고 있다.
• fork()를 통한 프로세스 생성 과정에서 페이지들이 공유되는 것을 가능하게 한다.

Demand Paging (요구 페이징)

프로그램 실행 시작 시 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신, 초기에 필요한 것들만 적재하는 전략을 요구 페이징이라 한다. 이는 가상 메모리 시스템에서 많이 사용된다. 가상 메모리는 대개 페이지로 관리되는데, 요구 페이징을 사용하는 가상 메모리에서는 실행 과정에서 필요해질 때 페이지들이 적재된다. 한 번도 접근되지 않은 페이지는 물리 메모리에 적재되지 않는다.

프로세스 내의 개별 페이지들은 페이저(pager)에 의해 관리된다. 페이저는 프로세스 실행에 실제 필요한 페이지들만 메모리로 읽어와 사용되지 않을 페이지를 가져오는 시간 낭비와 메모리 낭비를 줄여준다.

Page Fault Trap (페이지 부재 트랩)

페이지 교체

요구 페이징에서 언급된대로 프로그램 실행 시 모든 항목이 물리 메모리로 올라가지 않기 때문에 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 page fault(페이지 부재)가 발생하게 되면, 원하는 페이지를 보조저장장치에서 가져온다. 그러나 이때 물리 메모리가 모두 사용 중이라면, 페이지 교체가 이뤄져야 한다. (또는 OS가 프로세스를 강제 종료한다.)

기본적인 방법

물리 메모리가 모두 사용 중일 경우(물리 메모리에 자리가 없는 경우)의 메모리 교체 흐름이다.
1. 디스크에서 필요한 페이지의 위치를 찾는다.
2. 빈 페이지 프레임을 찾는다.
-> 페이지 교체 알고리즘을 통해 희생될 (victim) 페이지를 고른다.
-> 희생될 페이지를 디스크에 기록하고, 관련 페이지 테이블을 수정한다.
3. 새롭게 비워진 페이지 테이블 내 프레임에 새 페이지를 읽어오고, 프레임 테이블을 수정한다.
4. 사용자 프로세스 재시작.

간단하게 정리하면 필요한 페이지의 부재로 디스크에서 페이지를 가져올 때, 물리 메모리에 자리가 부족할 경우, 물리 메모리 상에서 희생 페이지를 알고리즘을 통해 선택하고, 희생 페이지를 디스크로 옮긴 후, 그 자리에 필요한 페이지를 올리게 된다.

페이지 교체 알고리즘

FIFO 페이지 교체 (First In First Out Page Replacement)

가장 간단한 페이지 교체 알고리즘으로 FIFO(First-In-First-Out)이 있다. 먼저 물리 메모리에 들어온 순서대로 페이지 교체 시점에 먼저 나가게 된다.

장점

• 이해하기 쉽고 구현도 쉬움.

단점

• 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수도 있음. (초기 변수 등)
• 처음부터 활발하게 사용되는 페이지를 교체해서 페이지 부재율을 높이는 부작용을 초래할 수 있음.
• Belady의 모순: 페이지를 저장할 수 있는 페이지 프레임의 갯수를 늘려도 되려 페이지 부재가 더 많이 발생하는 모순 발생

최적 페이지 교체 (Optimal Page Replacement)

Belady의 모순을 확인한 이후 최적 교체 알고리즘에 대한 탐구가 진행되었고, 모든 알고리즘보다 낮은 페이지 부재율을 보이며 Belady의 모순이 발생하지 않는다. 이 알고리즘의 핵심은 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 것이다. 주로 비교 연구 목적을 위해 사용한다. (실제 구현보다는 다른 알고리즘과 비교하여 이와 비슷한 결과일 수록 좋은 알고리즘임을 평가)

장점

• 알고리즘 중 가장 낮은 페이지 부재율을 보장함.

단점

• 구현의 어려움이 있음. 모든 프로세스의 메모리 참조의 계획을 미리 파악할 방법이 없기 때문.

LRU 페이지 교체 (Least Recently Used Page Replacement)

최적 알고리즘의 근사 알고리즘으로, 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다.

특징

• 대체적으로 FIFO 알고리즘보다 우수하고, 최적 알고리즘보다는 그렇지 못하다.

LFU 페이지 교체 (Least Frequently Used Page Replacement)

참조 횟수가 가장 적은 페이지를 교체하는 방법이다. 활발하게 사용되는 페이지는 참조 횟수가 많아질 거라는 가정에서 만들어졌다.

특징

• 어떤 프로세스가 특정 페이지를 집중적으로 사용하다, 다른 기능을 사용하게 되면 더 이상 사용하지 않아도 계속 메모리에 머물게 되어 초기 가정에 어긋나는 시점이 발생할 수 있음.
• 최적 페이지 교체를 제대로 근사하지 못하기 때문에 잘 쓰이지 않음.

MFU 페이지 교체 (Most Frequently Used Page Replacement)

참조 횟수가 가장 작은 페이지가 최근에 메모리에 올라왔고, 앞으로 계속 사용될 것이라는 가정에 기반한다.

특징

• 최적 페이지 교체를 제대로 근사하지 못하기 떄문에 잘 쓰이지 않음.

정리

가상메모리

프로그램의 실행에 필요한 일정 부분만 물리 메모리에 올리고, 나머지는 디스크에 유지시킨다. 이렇게 하면 많은 프로그램을 물리 메모리에 올릴 수 있게 되는데, 유저 입장에서는 많은 프로그램 전체를 메모리에 모두 올린 것이라고 느끼게 된다.

페이지 공유

가상 메모리는 프로세스 간의 페이지 공유를 가능하게 한다. 물리 메모리에 올라와 공유되고 있는 것을 유저들 입장에서는 자신만의 가상 메모리에 저장된 것 처럼보이도록 하는 것이다.

Demand Paging

가상 메모리는 대개 페이지 단위로 구성된다. 실행에 필요한 페이지만 물리 메모리에 올라가 있는 상태를 Demand Paging이라고 한다. Demand Paging을 사용하는 가상 메모리에서는 실행 과정에서 필요한 페이지를 디스크에서 가져온다. 즉 한번도 사용하지 않은 페이지는 물리 메모리에 올라가지 않는다.

페이지 교체

Demand Paging 과정에서 만약 디스크에서 가져온 페이지가 올라갈 자리가 물리 메모리 상에 없을 경우에는 물리 메모리 상의 다른 페이지를 디스크로 내리고 필요한 페이지를 물리 메모리 상에 올려야 한다. 이를 페이지 교체라고 한다. 페이지 교체는 적용된 알고리즘에 따라서 희생 페이지를 결정하게 된다.

페이지 교체 알고리즘

페이지 교체 알고리즘에는 FIFO, Optimal, LRU, LFU, MFU가 있다.

FIFO

FIFO는 말 그대로 먼저 들어왔던 페이지를 디스크로 내린다. 이 경우, 초기부터 많이 사용하던 페이지가 디스크로 내려가 Page Fault가 발생할 가능성이 생기게 되고, Belady의 모순이 발생한다. Belady의 모순은 물리 메모리의 면적을 넓혀도 Page Fault의 확률이 더 올라가는 것을 말한다.

Optimal

Optimal은 실제로 구현할 수 없다. 보통 다른 교체 알고리즘의 성능을 평가하기 위한 지표로 사용된다. Optimal은 앞으로 해당 페이지가 얼마나 사용되는지의 여부를 통해 가장 사용되지 않을 페이지를 디스크로 내리는 알고리즘이다. 미래는 알 수 없기 때문에 구현 불가능하다.

LRU

LRU는 마지막 접근 시간이 가장 오래된 페이지를 디스크로 내리는 알고리즘으로 Optimal에 어느정도 근사한 알고리즘이다.

LFU

LFU는 가장 조금 접근한 페이지를 디스크로 내리는 알고리즘이다. 이는 특정 페이지를 집중적으로 접근하다가 앞으로 사용하지 않게 되어도 접근 횟수가 높기 때문에 물리 메모리에서 내려오지 않게 된다. Optimal과 거리가 멀기 때문에 잘 사용되지 않는다.

MFU

가장 많이 접근한 페이지를 디스크로 내리는 알고리즘이다. 조금 접근한 페이지일수록 앞으로 더 접근될 것이라는 예측을 기반으로 한다. 이 또한 Optimal과 거리가 멀기 때문에 잘 사용되지 않는다.