Chapter 7. Virtual Memory

1. 가상메모리란

프로세스의 모든 영역을 한번에 메모리에 올리는것이 아닌, 필요할 때마다 메모리에 올리는 기법이다. 왜냐하면 프로세스는 전체 코드를 '동시에' 참조하는 경우는 드물기 때문이다. 따라서 필요하지 않은 메모리 공간을 실제 물리 메모리에 올리지 않는다. 이렇게 된다면, 프로그램 크기가 메모리보다 커도 동작할 수 있고, 더 많은 프로그램을 동시에 실행할 수 있어 CPU 이용률과 처리율이 증가했다.

하지만 프로그램 코드를 작게 나누면 그 만큼 디스크와의 Swap이 많아지고 I/O 처리에 따른 속도가 느려질 수 있다.

2. Demand Paging

앞에서 가상메모리는 프로세스의 모든 부분을 미리 로드하는것이 아닌, CPU가 실제 인스트럭션을 읽어갈 때마다 페이지가 메모리상에 로드됨을 말했다.

Demand Paging은 외부 단편화 문제를 해결하는 'Paging'을 활용한다. Page Table의 Valid/Invalid Bit를 두어 현재 페이지가 메모리에 있는지 혹은 디스크에 있는지를 참조한다. 없을 경우(Page Fault) OS에 의해 Page를 가져온다.

보통 메모리를 관리하는데 페이징을 최종적으로 사용하기 때문에, Page Table을 동일하게 사용하여 별도의 인프라를 구축할 필요가 없다.

3. Page Fault

Page Table의 Valid/Invalid Bit를 참조하여, 필요한 코드가 메모리에는 없고 디스크에 있는 경우를 의미한다. 만약 실행 도중 Page Fault가 자주 발생하면 그만큼 Disk에서 Memory로 Page를 가져오는 경우가 많아(I/O) 속도가 느려진다.

만약, Page Fault가 발생하여 필요 페이지를 Disk에서 Memory로 가져올려 하는데, 메모리가 꽉 찰 경우 메모리에서 한 영역을 다시 Disk로 Swap Out해야한다. 이때, Victim을 선정하는 스케줄링은 자주 Swap되지 않는 페이지를 선택해야한다.

 

[그림 1] Page Falut

4. Page Replacement Scheduling

1. FIFO Page Replacement

물리 메모리에 먼저 들어온 페이지 순서대로 먼저 Swap되는 기법이다. 구현하기 쉽고 먼저 사용한 데이터가 나중에 잘 안쓰일 때 좋다. 하지만 오래된 페이지에 주기적으로 중요한 정보가 포함될 수 있다. ex) 전역변수의 경우 성능이 않좋음

 

2. Optimal Page Replacement

앞으로 가장 오랫동안 사용하지 않을 페이지를 찾아 교체 하는것이다. 이는 연구 목적으로 사용되고 알고리즘 중 가장 낮은 Page Fault가 일어나지만 구현 하기 힘들다.

 

3. LRU Page Replacement [Least Recently Used] 多사용

최적 알고리즘과 근사한것으로, 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다. 보통 FIFO 알고리즘보다 우수하고 OPR 알고리즘보다는 좋지 않다. Priority Queue를 이용하여 구현하기도 한다.

 

※ 참고

혹은 Bit를 이용한 알고리즘을 이용하기도한다. 이는Reference Bit (Bit 1개로 사용하는 Counter)를 사용한다. 
맨 처음 각 Page의 reference bit를 0으로 초기화 하고 Page 참조시 bit를 1로 바꾼다. Victime 선정 시 탐색을 하다가 1이면 0으로 바꾸고 0을 만나면 Victime으로 선정한다. 
이는 데이터구조가 간단하여 Memory 절약도 되고 Search의 경우에도 빠른 장점이 있어 Overhead가 적다는 장점이 있다. 하지만 Page를 1번 이상 Reference 한것을 모두 동일하게 봐 정확성이 떨어진다.

 

4. LFU Page Replacement (Least Frequently Used)

참조 횟수가 가장 적은 페이지를 교체하는 방법이다. 어떤 프로세스가 특정 페이지를 집중적으로 사용하다, 다른 기능을 사용하게 되면 더 이상 사용하지 않아도 계속 메모리에 머물게 되어 비효율적이다. 이로인해 자주 사용하지 않는다.

 

5. MFU Page Replacement (Most Frequently Used)

LFU 방식의 반대로 참조 횟수가 가장 작은 페이지가 최근에 메모리에 올라왔고, 앞으로 계속 사용될것으로 예측하는 방식이다. 이는 자주 사용하지 않는다.

 

5. Trashing

Page Replacement가 급격히 증가하면서 성능이 현저히 떨어지는 현상이다. 

1. Page Falult 증가

2. Swap 작업 때문에 CPU 이용률 감소

3. CPU 이용률이 감소하여 Multi Programming을 위해 프로세스를 더 많이 받는다.

4. Page Falut가 더욱 증가

5. Swaping이 더욱 많아진다.

따라서 Process 수를 제한하는 등의 대첵이 필요하다.