가상메모리란?
실제 메모리보다 메모리가 많아 보이게 하는 기술로, 어떤 프로세스가 실행될 때 메모리에 해당 프로세스 전체가 올라가지 않더라도 실행이 가능하다는 점에 착안하여 고안됨.
- 애플리케이션이 실행될 때, 실행에 필요한 부분만 메모리에 올라가며 애플리케이션의 나머지는 디스크에 남게 된다. 즉, RAM과 디스크를 합쳐 하나의 크고 빠른 메모리처럼 동작하게 하는 것이다.
가상 메모리가 하는 일
가상 메모리는 각 프로세스에게 물리적 메모리 공간보다 큰 가상 주소공간을 제공한다. 이는 하나의 프로세스가 모든 데이터 및 코드를 실제 메모리에 로드하지 않고도 큰 규모의 작업을 수행할 수 있게 한다.
가상 주소 공간
- 한 프로세스가 메모리에 저장되는 논리적인 모습을 구현한 공간. 프로세스가 요구하는 메모리 공간을 가상 메모리에서 제공하여 직접적으로 필요한 부분만을 물리 메모리에 올리고 나머지는 필요시 물리메모리에서 가상메모리에 요구하게 된다.
MMU란?
MMU (Memory-Management Unit)
- logical address를 physical address로 매핑해 주는 Hardware device
- 프로세스가 CPU에서 수행되면서 생성하는 모든 주소에 대해 base register를 더해주어 물리 주소로 변환한다.
- base register와 limit register를 이용하여 메모리를 보호하게 된다.
- MMU를 사용하게 되면, CPU가 각 메모리에 접근하기 이전에 메모리 주소 번역 작업이 수행됨.
요구 페이징 (Demand Paging)
프로그램 전체를 메모리에 적재하는 것이 아닌, 필요할 때 마다 page를 메모리에 올리는 전략
페이지 교체
프로그램이 실행되게 되면 모든 항목이 물리메모리로 올라오지 않는다. 때문에, 동작에 필요한 페이지를 요청하는 과정에서 page fault(필요 페이지가 메모리에 없는 상황)가 발생한다면, 해당 페이지를 디스크에서 가져와야 한다. 하지만, 물리 메모리가 전부 사용중이라면 기존에 사용하던 페이지와 교체해야 한다.
기본적인 방법
물리 메모리가 모두 사용중인 상황에서의 메모리 교체 흐름
- 디스크에서 필요한 페이지의 위치를 찾는다.
- 빈 페이지 프레임을 찾는다.
2-1.페이지 교체 알고리즘을 통해 victim을 고름
2-2. 희생될 페이지를 디스크에 기록하고, 관련 페이지 테이블을 수정 - 새롭게 비워진 페이지 테이블 내 프레임에 새 페이지를 읽어오고, 프레임 테이블을 수정한다.
- 사용자 프로세스 재시작
페이지 교체 알고리즘
FIFO
가장 간단한 알고리즘. 먼저 들어온 것을 먼저 내쫓음
- 장점
- 이해하기 쉬움
- 단점
- Belady의 모순 (FIFO 모순) : 프레임 수를 늘려도 오히려 페이지 부재가 더 많이 발생함
Optimal Page Replacement
다른 알고리즘의 성능에 대한 upper bound를 제공해줌. 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 방법
- 장점
- 알고리즘 중 가장 낮은 페이지 부재율을 보임
- 단점
- 미래를 예측할 수 없기에 구현에 어려움이 있음. 미래의 사용패턴을 정확하게 예측할 수 없기 때문임
LRU (Least Recently Used)
Optimal Page Replacement의 가장 근사 알고리즘. 미래를 모른다면 과거를 보도록 하자.
가장 오래전에 참조된 것을 지우는 방식
LFU (Least Frequently Replacement)
참조 횟수가 가장 적은 페이지를 교체하는 방법. 활발하게 사용되는 페이지는 참조 횟수가 많을 것이라는 가정에서 만들어짐
만약 최저 참조횟수인 page가 여럿이라면?
-
LFU 알고리즘 자체에서는 여러 page 중 임의로 선정하게 된다.
-
성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수 있음
-
장점
- LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영이 가능함
-
단점
- 참조 시점의 최근성을 반영하지 못함
- LRU 보다 구현이 복잡함
LRU와 LFU 알고리즘의 구현
- LRU (시간순서)
- Linked List형태로 구현함
- 새로운 레퍼런스가 들어오면 제일 아래에 매다는 형식
- 즉, 페이지 교체는 제일 위쪽에서 이뤄지기 때문에 시간복잡도는 O(1)
- LFU (참조 횟수)
- Heap을 사용하여 비교하면서 아래쪽으로 내려감
- 시간복잡도는 O(log n) Complete Binary Tree
MFU (Most Frequently Used)
참조 횟수가 가장 적은 페이지가 앞으로 계속 사용될 것이라는 가정에 기반
- 특징
- OPT에 제대로 근사하지 못하여 거의 사용하지 않음.
현대 OS는 LFU나 LRU를 사용할까?
이를 이해하기 위해선 Paging System을 확인해 봐야 한다.
CPU에서 프로세스A가 실행중인 상태를 순서대로 생각해보자.
1. CPU에서 실행되기 위해선 프로세스A의 논리주소에서 매 순간마다 Instruction을 하나씩 읽어와서 실행하게 된다.
2. CPU에서 논리주소를 MMU에게 전달한다.
3. MMU는 page table을 활용해 논리주소 -> 물리주소 로 매핑하여 메모리에서 데이터나 명령을 읽어오게 된다.
위의 순서는 물리메모리에 실제 필요한 page가 있는 경우의 순서이다. 이 과정에서는 운영체제는 관여하지 않는다. MMU 또한 하드웨어적으로 구현되어 있다.
그렇다면 물리메모리에 필요한 Page가 없어 페이지 교체가 이뤄지는 과정을 생각해보자.
1. CPU에서 논리주소를 MMU에 전달한다.
2. MMU는 page table을 활용했지만 invalid-bit를 통해서 실제 물리 메모리에 위치해있지 않음을 파악했다. (page fault 발생)
3. 나머지 page는 디스크에 있기 때문에 프로세스A를 계속해서 실행할 수 없기에 trap이 발생한다.
4. CPU의 제어권이 프로세스 A -> 운영체제로 바뀐다.
5. 운영체제가 디스크에 있는 page를 읽어와서 물리메모리에 올려놓게 된다. (이 과정에서 필요하다면 page replacement가 이뤄지게 된다.)
5번 과정에서 이제 LRU나 LFU의 문제점이 발생하게 된다. 운영체제는 가장 오래됐거나 가장 적게 참조된 페이지를 내쫓아야 한다. 그러나 운영체제는 어떤 페이지가 victim인지 알 수 없다
이 전의 페이지들이 MMU를 통해 매핑이 정상적으로 이뤄질 경우 운영체제에게 CPU가 넘어가질 않음. 그렇기에 운영체제는 알 수 없는 상황이기에 다른 알고리즘을 사용해야 한다
Clock Algorithm (Second chance algorithm, NUR, NRU)
- LRU의 근사 알고리즘
- Reference bit를 사용해서 교체 대상 페이지 선정 (circular list)
- Reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
- 포인터가 이동하는 중에 reference bit 1은 모두 0으로 바꿈
- Reference bit이 0인 것을 찾으면 그 페이지를 교체
- 한바퀴를 돌아와서도 0이면 그때에는 replace 당함 (이 때 운영체제 개입)
Clock Algorithm 개선
- reference bit과 modified bit (drity bit)을 함께 사용
- reference bit = 1 : 최근 참조된 페이지
- modified bit = 1 : 최근 변경된 페이지 (I/O를 동반하는 페이지)
- 만약 modified bit이 1이라면 backing storage에 다시 저장해준 후 쫓아야 함 (일이 더 많음)
- 그러나, 0이라면 메모리에 올라온 이후로 write도 없었기 때문에 쫓아내기만 하면 됨 (훨씬 일이 수월함)
