10. 운영체제 - Memory Virtualization(5)

Swapping

앞서 Memory Virtualization의 단순화를 위해 했던 가정들 중 Address space가 Physical memory 사이즈에 항상 다 들어갈 수 있다는 가정을 없애보자.

프로세스의 주소공간이 physical memory에 fit하지 않더라도 프로세스는 실행될 수 있어야한다.

이를 위해 HDD나 SDD같은 DRAM보다 싸고 큰 저장장치의 일부를 사용하여 조금 느리더라도 프로세스가 죽지 않고 실행될 수 있도록 하는 것이 Swapping 이다.

Swap Space

physical memory에 올라가지 못하고 밀려난 페이지들을 담아두기 위해 페이지와 같은 크기로 디스크에 swap space를 마련해둔다. 

그리고 physical memory에 존재하지 않고 swap space에 존재하는 페이지는 PTE에 표시를 해두어야한다. (present bit)

데이터베이스의 버퍼풀과 같은 캐시의 경우는 성능의 향상을 위해 버퍼풀과 디스크에 모두 데이터가 존재하는 inclusive cache이다. 반면 Swap space에 존재하면 DRAM과 같은 메인메모리에는 데이터가 존재하지 않아도 된다. 이는 공간의 확장을 위한 것으로 exclusive cache이다.

Page fault

Page Fault는 찾는 페이지가 physical memory에 존재하지 않는 경우에 발생한다. 이 경우 OS는 페이지를 physical memory로 가져오는 작업을 수행해야한다.

Page Replacement

OS가 physical memory가 꽉 찰때까지 기다렸다가, 다른 페이지를 메모리로 가져와야할 때 페이지를 교체할 수 있다.

하지만 이것보다는 가용한 메모리를 일정 비율 미리 확보해놓으면 메모리가 꽉 찼을 때 성능이 확 떨어지는 것을 방지할 수 있다.

 

Replacement Policy

Replaement policy는 캐시 미스를 최소화하는 방향으로 설정해야한다.

Tm	메모리 접근 비용
Td	디스크 접근 비용
Phit	캐시에서 데이터를 찾을 확률 (cache hit)
Pmiss	캐시에서 데이터를 찾지 못할 확률 (cache miss)

• AMAT(Average Memory Access Time) = (Phit * Tm) + (Pmiss * Td)

최적의 Replacement policy는 AMAT을 최소화하는 방향으로 가야한다.

Phit = 1 - Pmiss 이고, Tm과 Td는 고정되어 있으므로 결국은 Pmiss를 최소화하는 방향으로 가야한다. 

FIFO

간단한 방법으로, 먼저 들어온 페이지를 먼저 evict하는 방법이 있다.

이 방법은 구현이 간단하지만, 페이지의 중요도를 전혀 고려하지 않는 방법이다.

• Belady's anomaly : FIFO를 사용할 때, 페이지 프레임의 개수를 늘리면 오히려 page fault가 늘어나는 현상

FIFO를 사용하면 위와같은 예상치 못한 문제가 발생할 수 있다. 직관적으로 말이 안되는 것 같지만 위키피디아의 예시를 참고하면 그런 상황이 발생할 수 있는 경우가 있다는 것을 알 수 있다.

Random

혹은 그냥 랜덤으로 페이지를 골라 evict 시킬 수도 있다.

실제로 랜덤으로 돌리면 일부 경우, 최적에 가깝게 결과가 나오는 것을 볼 수 있다.

History

과거의 이력을 통해 evict할 페이지를 선택할 수 있다.

• LRU (Least recently used) : 더 최근에 접근된 페이지는 또 다시 접근될 가능성이 높다고 보고, 가장 예전에 접근되었던 페이지를 evict시키는 방법
• LFU (Least frequently used) : 많이 접근된 페이지는 가치가 있어서 많이 접근되는 것이라 생각하고, 가장 덜 빈번하게 접근된 페이지를 가장 먼저 evict시키는 방법

Workload

Locality가 전혀 존재하지 않고 완전히 랜덤한 페이지를 접근하는 워크로드의 경우에는 어떤 방식을 사용하든 차이가 없다. 

80%의 워크로드는 20%의 페이지에 계속 접근하고, 20% 워크로드는 나머지 80%의 페이지에만 접근하는 워크로드이다.

이 경우 LRU를 사용하면 자주 사용되는 hot page들을 캐시에 들고있을 확률이 높아지므로 성능이 올라간다. 

for문과 같이 순차적으로 연속된 데이터를 접근하는 워크로드의 경우 LRU 는 최악의 성능이 나온다. 계속해서 cache miss가 발생하기 때문이다. 

History 알고리즘의 구현

LRU를 구현하려면 어느 페이지가 언제 마지막으로 사용되었는지 알아야한다.

이를 위해 접근된 정확한 시간을 적어둘 수도 있지만 그러려면 쓸데없이 너무 많은 비트가 사용된다.

따라서 Clock algorithm을 사용하여 해당 방법을 근사할 수 있다.

이전 글 에 Clock 알고리즘에 대한 설명이 나와있다.