[OS] 가상 메모리와 페이지 교체

가상 메모리

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

장점

• 프로그램이 물리 메모리보다 커도 된다. (물리 메모리 크기에 제약받지 않는다.)
• 더 많은 프로그램을 동시에 실행할 수 있게 된다.
• CPU 이용률과 처리율이 높아진다.
• swap에 필요한 입출력이 줄어들어 프로그램이 빠르게 실행된다.

요구 페이징

프로그램 실행 시작 시 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신, 초기에 필요한 것들만 적재하는 전략

페이지 교체

요구 페이징에서 언급한 대로 프로그램 실행 시 모든 항목이 물리 메모리에 올라오지 않기 때문에, 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 Page Fault가 발생하면 원하는 페이지를 보조 저장장치에서 가져오게 된다.

만약 물리 메모리가 모두 사용중인 상황이라면, 페이지 교체가 이뤄져야 한다.

물리 메모리가 모두 사용중인 상황에서의 메모리 교체 흐름

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

페이지 교체 알고리즘

FIFO

먼저 물리 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게 되는 알고리즘

장점

이해하기 쉽고 프로그래밍하기 쉽다.
가장 간단한 페이지 교체 알고리즘으로 FIFO의 흐름을 가진다.

단점

오래된 페이지라도 중요한 정보를 포함할 수 있다.
처음부터 활발하게 사용되는 페이지를 교체해서 페이지 부재율을 높이는 부작용을 초래할 수 있다.
Belady의 모순 : 페이지를 저장할 수 있는 페이지 프레임의 개수를 늘려도 페이지 부재가 더 많이 발생하는 모순이 존재한다.

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

앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아서 교체하는 알고리즘

장점

Belady의 모순이 발생하지 않는다.
가장 낮은 페이지 부재율을 보장한다.

단점

구현이 불가능하다.
모든 프로세스의 메모리 참조 계획을 미리 파악할 방법이 없다.

LRU(Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 선택하여 교체하는 알고리즘

특징

FIFO 알고리즘보다 우수하고 OPT 알고리즘보다는 그렇지 못하다.
많이 사용되는 알고리즘

LFU(Least Frequently Used)

참조 회수가 가장 작은 페이지를 교체하는 알고리즘
활발하게 사용되는 페이지는 참조 횟수가 많아질 거라는 가정에서 만들어진 알고리즘이다.

특징

교체 대상 페이지가 여러 개일 경우 LRU 알고리즘을 따라 가장 오래 사용하지 않은 페이지를 교체한다.
OPT 알고리즘을 제대로 근사하지 못해서 잘 쓰이지 않는다.
구현에 상당한 비용이 든다.

문제점

어떤 프로세스가 특정 페이지를 집중적으로 사용하다가, 다른 기능을 사용하게 될 때, 필요 없는 페이지를 계속 메모리에 가지고 있어서 초기 가정에 어긋나는 시점이 발생할 수 있다.

MFU(Most Frequently Used)

가장 많이 사용된 페이지를 교체하는 알고리즘
가장 적게 사용된 페이지가 최근에 올라오고 계속 사용될 것이라는 가정에서 만들어진 알고리즘이다.

특징

OPT 알고리즘을 제대로 근사하지 못해서 잘 쓰이지 않는다.
구현에 상당한 비용이 든다.

참고 사이트

가상 메모리와 페이지 교체
페이지 교체 그림