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되지 않는 페이지를 선택해야합니다.
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가 급격히 증가하면서 성능이 현저히 떨어지는 현상입니다.
- Page Falult 증가
- Swap 작업 때문에 CPU 이용률 감소
- CPU 이용률이 감소하여 Multi Programming을 위해 프로세스를 더 많이 받음
- Page Falut가 더욱 증가
- Swaping이 더욱 많아짐
따라서 Process 수를 제한하는 등의 대책이 필요합니다.
