Virtual memory & Page fault
Virtual memory
메인 메모리의 크기는 물리적으로 한정되어 있으며, 따라서 메인 메모리의 크기보다 크기가 큰 프로세스는 실행할 수가 없다. 이를 해결하기 위해 등장한 메모리 관리 기법이 바로 가상 메모리(Virtual memory)이다.
가상 메모리는 보조기억장치(HDD 등)의 일부를 마치 주기억장치, 즉 메모리처럼 활용하도록 함으로써 실제 주기억장치보다 더 큰 메모리 영역을 제공하는 방법이다. 즉, 주기억장치의 속도와 보조기억장치의 용량이라는 장점을 모두 얻을 수 있도록 하는 방법인 것이다.
Demand paging
가상 메모리의 핵심은 어떤 프로세스가 동작할 때 메모리에 해당 프로세스 전체가 올라가지 않아도 되고, 실행에 필요한 일부분만 메모리에 올라간다는 것이다. 즉, 프로세스의 데이터 중 현재 실행을 위해 필요한 중요 부분만을 메모리에 적재하고 나머지 덜 중요한 부분은 가상 메모리(보조기억장치)에 옮겨 둠으로써 메모리의 효율성을 높이는 것이다. 이를 요구 페이징(Demand paging)이라 한다.
이름에서 알 수 있듯 요구 페이징 기법에서 프로세스를 나누는 방식이 앞서 메모리 할당 포스트에서 살펴본 페이징 기법이다.
- 페이징(Paging)
프로세스의 주소 공간을 고정된 크기의 페이지 단위로 나누어 메모리의 프레임에 불연속적으로 할당하는 방법이다. 페이지와 프레임을 대응시키는페이지 매핑(Page mapping)을 위한페이지 테이블(Page table)이 필요하며, 여기에는 각 페이지의 번호와 해당 페이지가 할당된 프레임의 시작 물리 주소가 저장된다.
그리고 페이징 기법에서는 프로세스의 구분 단위인 페이지와 실제 물리적 메모리 공간의 구분 단위인 프레임을 매칭하며, 이때 페이지에 주어지는 주소가 논리적 주소(Logical address), 프레임에 할당되는 주소가 물리적 주소(Physical address)이다. 앞서 주소 바인딩에서 정리했던 개념이 이렇게 활용되는 것.
Page fault
요구 페이징 방식을 통해 현재 실행에 필요한 페이지만을 메모리에 적재하고, 나머지 덜 중요한 페이지는 보조기억장치의 '가상 메모리 공간'에 저장해 두게 된다. 따라서 CPU가 프로그램을 실행하면서 현재 필요로 하는 페이지가 물리적 메모리에 존재하지 않는 경우도 발생한다. 이를 페이지 폴트(Page fault)라고 한다.
페이지 폴트의 발생 과정을 간단히 정리하면 다음과 같다.
- CPU가 물리 메모리를 확인하고 필요한 페이지가 없으면 OS에 트랩을 발생시킨다.
- OS는 CPU의 동작을 일시 정지하고 페이지 테이블을 확인한다.
- 만약 스왑 영역(가상 메모리 등)에 페이지가 존재하지 않는다면 프로세스를 중단한다.
- 스왑 영역에 페이지가 존재하고 단지 물리 메모리에 적재되지 않은 것이라면, 즉
페이지 폴트이면 현재 물리 메모리에 비어 있는 프레임이 있는지 확인한다. - 해당 페이지를 스왑 영역에서 가져와 비어 있는 프레임에 적재하고, 페이지 테이블을 리셋하여 정보를 갱신한다.
- 다시 CPU를 동작시킨다.
여기서 4번 과정을 살펴보자. 만약 스왑 영역에서 페이지를 가져오려고 할 때 물리 메모리에 비어 있는 공간이 없다면 어떻게 될까? 프로세스를 멈출 수는 없으므로 OS는 희생 프레임(Victim frame)을 골라 이를 가상 메모리에 저장하고, 그렇게 만들어진 빈 공간에 필요한 페이지를 적재한다. 그리고 이 과정에서 페이지 교체 알고리즘(Page replacement algorithm)이 사용된다.
Page replacement algorithm
페이지 교체 알고리즘(Page replacement algorithm)은 페이지 폴트의 발생 비율을 줄이는 것을 목표로 한다. 따라서 가까운 미래에 참조될 가능성이 '가장 낮은' 페이지를 선택해서 내보내는 것이 성능을 향상시킬 수 있는 방법이 된다.
First In First Out(FIFO)
- 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘
- 구현은 간단하나 페이지의 향후 참조 가능성을 고려하지 않으므로 성능은 낮음
- Belady's anomaly(or FIFO anomaly) 현상 발생 가능
Belady's anomaly
프레임의 개수가 많아져도 페이지 폴트가 줄어들지 않고 오히려 늘어나는 현상
Optimal(OPT)
- 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 기법
- 페이지 폴트 발생이 가장 적고 Belady's anomal 현생도 발생하지 않음
- 프로세스가 앞으로 참조할 페이지를 미리 알아야 하므로 실제로 구현하는 것은 거의 불가능함
Least Recently Used(LRU)
- 가장 오랫동안 사용하지 않은 페이지를 교체
- 성능이 좋은 편으로 많은 운영체제가 채택하는 알고리즘
- 각 페이지마다 카운터나 스택을 두어 사용 시마다 계수를 카운트함
- 계수기나 스택과 같은 별도의 하드웨어가 필요하며, 시간적 오버헤드 발생
Least Frequently Used(LFU)
- 참조 횟수가 가장 적은 페이지를 교체
- 교체 대상이 여러 개일 경우 LRU에 따라 페이지를 교체
- 초기에 집중적으로 사용되었으나 이후 참조되지 않은 페이지가 있는 경우 해당 참조 기록으로 인해 페이지가 메모리에 남아 있는 문제가 발생
Most Frequently Used(MFU)
- LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘
Not Used Recently(NUR)
- 하드웨어적인 자원을 통해 LRU 또는 LFU 알고리즘의 오버헤드를 줄인 방식
- LRU와 같이 가장 최근에 참조되지 않은 페이지를 교체하나, 쵸게되는 페이지의 참조 시점이 가장 오래되었음을 보장하지는 않음
- 최근 사용 여부 확인을 위해 참조 비트와 변형 비트를 사용
- 참조 비트 : 페이지가 호출되지 않았을 때는 0, 호출되었을 때는 1로 저장
- 변형 비트 : 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때는 1로 지정
- 우선 고려 대상은 참조 비트이며, 참조 비트가 0인 페이지가 없을 경우 변경 비트를 참조
Second Chance Replacement(SCR)
- 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로, FIFO의 단점을 보완하는 기법
- 각 페이지마다 참조 비트를 두고, FIFO를 이용하여 페이지 교체 수행 중 참조 비트가 0일 경우에는 교체하고, 참조 비트가 1일 경우에는 참조 비트를 0으로 지정한 후 FIFO 리스트의 맨 마지막으로 이동시켜 다음 순서를 기다리게 하는 방식
페이지 교체 방식
- Global 교체 : 메모리상의 모든 프로세스 페이지에 대해 교체하는 방식
- Local 교체 : 메모리상의 자기 프로세스 페이지에 대해서만 교체하는 방식
Local 교체 방식을 채택하면 각 프로세스가 모두 희생 프레임을 선정해 교체를 진행해야 하므로 비효율적일 수 있다. 따라서 일반적으로는 Global 교체가 더 효율적이다.
참고 자료
