가상화 - 메모리 가상화 : 물리 메모리 크기의 극복(정책)

가상 메모리를 관리하는 입장에서 비어 있는 메모리가 많을수록 일은 수월해진다.

페이지 폴트가 발생하면 빈 페이지 리스트에서 비어 있는 페이지를 찾아서 페이지 폴트를 일으킨 페이지에게 할당하면 된다.

다만, 불행하게도 빈 메모리 공간이 거의 없으면 일이 복잡해진다. 그런 경우 운영체제는 메모리 압박을 해소하기 위해 다른 페이지들을

강제적으로 페이징 아웃하여 활발히 사용 중인 페이지들을 위한 공간을 확보한다. 내보낼 페이지 선택은 운영체제의 교체 정책에 따른다.

캐시 관리

시스템의 전체 페이지들 중 일부분만이 메인 메모리에 유지된다는 것을 가정하면, 메인 메모리를 일종의 캐시로 생각할 수 있다.

교체 정책의 목표는 캐시 미스의 횟수를 최소화하는 것이다. 즉, 디스크로부터 페이지를 가져오는 횟수를 최소로 만드는 것이다.

간단한 정책 : FIFO와 무작위 선택

간단한 페이지 교체 정책으로는 먼저 들어온 페이지를 먼저 교체하는 방식과 교체할 페이지를 무작위로 선택하는 방식이 있다.

그러나 이런 방식의 교체 정책들은 페이지의 중요도를 고려하지 않은 정책이다.

과거 정보의 사용 : LRU

과거 정보를 사용하여 페이지 교체 정책을 수립할 수 있다.

페이지 교체 정책이 활용할 수 있는 과거 정보 중 하나는 빈도수이다.

어떤 페이지가 여러 차례 접근되었다면 분명히 어떤 가치가 있기 때문일 것이다. 

이를 고려한 교체 정책을 LFU(Least Frequently Used)라고 하며, 가장 적은 빈도로 사용된 페이지를 교체한다.

 

또 다른 과거 정보는 접근의 최근성이다. 

최근에 접근된 페이지일수록 가까운 미래에 접근될 확률이 높을 것이다.

이를 고려한 교체 정책을 LRU(Least Recently Used)라고 하며, 가장 오래전에 사용하였던 페이지를 교체한다.

과거 이력 기반 알고리즘의 구현

LRU 정책을 구현하기 위해서는 어떤 페이지가 가장 최근에 또는 가장 오래전에 사용되었는지를 관리해야 한다.

이를 효과적으로 하는 방법은 하드웨어 지원을 받는 것이다. 

예를 들어, 페이지 접근이 있을 때마다 하드웨어가 메모리의 시간 필드를 갱신하도록 할 수 있다.

그런데 시스템의 페이지 수가 매우 많다고 해보자. 페이지들의 시간 정보 배열을 검색해 가장 오래전에 사용된 페이지를 찾는 것은

굉장히 고비용의 연산이 될 것이다. LRU 정책을 비슷하게 구현할 수 있는 방법이 필요하다.

LRU 정책 근사하기

LRU 정책과 비슷한 수준의 성능을 보이는 다양한 방식들이 존재한다. 

그중 하나는 Use Bit(Reference Bit)를 사용한 시계 알고리즘이다. 실제로 현대의 많은 시스템이 이런 방식을 택하고 있다.

시스템의 각 페이지마다 하나의 Use Bit이 존재한다.

페이지가 참조될 때마다 즉, 읽히거나 기록되면 하드웨어에 의해서 해당 비트가 1로 설정된다.

하드웨어는 이 비트를 0으로 만들지 않는다. 0으로 바꾸는 것은 운영체제가 한다.

시스템의 모든 페이지들이 환형 리스트를 구성한다고 가정하자. 시곗바늘이 특정 페이지를 가리킨다고 해보자.

페이지를 교체해야 할 때, 운영체제는 현재 바늘이 가리키고 있는 페이지의 Use Bit가 1인지 0인지 검사한다.

만약 1이라면 페이지는 최근에 사용되었으며 바람직한 교체 대상이 아니라는 것을 뜻한다.

이후, 페이지의 Use Bit을 0으로 설정하고 시곗바늘은 다음 페이지로 이동한다.

알고리즘은 Use Bit가 0으로 설정되어 있는 즉 최근에 사용된 적이 없는 페이지를 찾을 때까지 반복된다.

완벽한 LRU 만큼은 아니지만 괜찮은 성능을 보인다.

갱신된 페이지의 고려

운영체제가 교체 대상을 선택할 때 메모리에 탑재된 이후에 변경되었는지를 추가적으로 고려할 필요가 있다.

만약에 어떤 페이지가 변경되어 Dirty 상태가 되었다면, 그 페이지를 내보내기 위해서 디스크에 변경 내용을 기록해야 한다.

이는 비용이 비싼 작업이다. 따라서 Dirty 페이지 대신 Clean 페이지를 내보내는 것이 비용 효과적이다.

페이지가 변경될 때마다 Dirty 비트가 1로 설정되므로 페이지 교체 알고리즘에서는 이를 고려하여 교체 대상을 선택하면 된다.

예를 들어, 수정된 시계 알고리즘은 교체 대상을 선택할 때 사용되지 않은 상태이고 깨끗한 페이지를 먼저 찾으면 된다.

또 다른 VM 정책들

VM 시스템은 페이지 교체 정책뿐만 아니라 다양한 정책들을 고민해야 한다.

예를 들어, 언제 페이지를 메모리에 탑재할지 결정해야 한다. 페이지에 실제로 접근할 때, 해당 페이지를 메모리에 탑재하는

요구 페이징(Demand Paging)이 이와 관련한 대표적인 정책이다. 또한, 변경된 페이지를 어떻게 디스크에 반영할지 결정할 필요가 있다.

페이지 변경 시마다 디스크에 반영할 수도 있지만, 디스크 특성 상 반영을 여러 차례에 나누어 진행하는 것보다 한 번에 진행하는 것이

보다 효율적일 수 있기 때문이다. 

쓰래싱(Thrashing)

메모리 사용 요구가 감당할 수 없을 만큼 많고 실행 중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우,

너무 잦은 페이지 교체가 발생할 수 있다. 이와 같은 상황을 쓰래싱이라고 부른다.

몇몇 초기 운영체제들은 쓰래싱이 발생했을 때 일부 프로세스의 실행을 중지시키는 방식으로 해결했다. 

많은 일들을 엉성하게 하는 것보다 더 적은 일을 제대로 하는 것이 낫다는 판단의 해결 책이었다.

일부 최신 시스템들은 메모리 과부하에 대하여 좀 더 과감한 조치를 취한다.

일부 버전의 Linux는 메모리 요구가 초과되면 메모리 부족 킬러를 실행시킨다.

많은 메모리를 요구하는 프로세스를 골라 죽이는 방식으로 메모리 요구를 줄이는 것이다.

그런데 중요 프로세스를 죽일 수 있기에 이 역시 문제가 될 수 있다.