서론

컴퓨터의 여러 프로세스들이 열심히 돌다보면 메모리가 부족해지는 순간이 올 수도 있을 것입니다. 여러분도 컴퓨터를 사용하다가 갑자기 렉이 걸리면서 마우스가 묵묵부답인 순간들을 본 적이 있듯이 말이죠.

그럴 때를 대비하여 컴퓨터에는 Swapping이라는 기법이 있습니다. 메모리의 특정 부분을 디스크에 빼뒀다가 다시 꼈다가하는 식으로 메모리와 디스크 사이를 swap하는 것이죠.

메모리가 disk를 사용한다는 것은 역으로 생각하면 메모리가 disk의 cache로 동작한다고 볼 수도 있을 것입니다.

그러면 이번 글에서는 이 swapping은 언제, 어디서, 어떻게 일어나는지 한번 알아보겠습니다.

Swap의 역사

예전에는 메모리가 부족했을 때 Overlays라고하는 방법을 썼습니다.

프로그래머가 코드, 데이터의 일부분을 바꾸고 버리고해서 OS의 도움없이 메모리 사용량을 줄인 방법입니다.

그 다음으로는 Process-level swapping으로 아예 프로세스 단위로 메모리에서 swap을 했습니다.

마지막으로는 Page-level swapping으로 프로세스가 아닌 페이지 단위로 메모리에서 swap을 시행합니다.

Where to Swap

page는 기본적으로 두 가지 타입으로 나눌 수 있는데, 이 타입에 따라 swap되는 장소가 다릅니다.

두 타입은 각각 File-backed page과 Anonymous page입니다.

File-backed-page는 말그대로 file이 backing store로 있어서, 만약 메모리에서 페이지를 빼야한다고 하더라도 그냥 해당하는 page table entry를 버리거나, 수정된 내용이 있으면 파일에 적어주면 됩니다.

Anonymous page는 이런 backing store가 없기때문에 디스크의 swap space라는 곳에 저장되게 됩니다. 그러므로 page-out할 때는 메모리에서 디스크의 swap space로 가고, page-in을 할 때 swap space에서 찾아서 메모리로 가져오게 됩니다.

When to Swap

Swap은 메모리가 부족할 때 일어난다는 것은 알겠으나 정확히 언제 일어나게 될까요?

저희가 OS를 만드는 사람들이라고한다면 최소한의 컴퓨터가 메모리는 항상 유지하도록 만드는게 좋겠죠?

이런 최소한의 메모리는 LW(Low Watermark)라고 불립니다.

OS에는 메모리가 LW이하로 남게되면 그때부터 swap을 시작해서 HW(High Watermark)로 표기된 곳까지 메모리를 정리하게됩니다.

What to Swap

메모리에는 정말 많은 정보들이 올라가있죠.

에를 들면 kernel data, kernel code, page tables, user code, user data, user heap/stack, files mmaped … 이렇게 정말 많이 있죠.

하지만 예상하시다시피 swap되는 것은 커널 관련된 데이터들은 아니고 user code/data/heap/stack과 mmap된 파일들이 swap되게 됩니다.

Which Page to replace

이제 이번 글의 핵심적인 부분이 시작됩니다.

어떤 데이터를 언제 어디다 swap할지는 이제 알겠습니다. 그러면 예를 들어 user data를 swap한다고 했을 때 user data의 어떤 page를 스왑해야할까요?

분명히 어떤 전략을 선택해야할 것입니다. 어떤 전략일까요?

그 전략이란 page fault rate(miss rate)를 최소화하는 방법이어야 할 것입니다. 왜냐하면 page fault가 나게되면 디스크에서 page를 읽어와야하는데 이게 메모리에서 읽어오는 것보다 대략 10만배 느리기때문입니다.

OPT(or MIN)

swap을 위한 page를 선택하는 최고의 알고리즘은 Belady의 OPT(optimal replacement policy)입니다.

이 방법은 미래에 가장 긴 시간 동안 쓰이지않을 페이지를 빼는 방법입니다.

그런데 약간 말이 안되는 부분이 있죠? 미래를 알 수는 없으니까요.

그래서 이 방법은 실용적인 방법은 아니고, 새로운 알고리즘을 채택했을 때 그 효율을 비교하기 위해서 사용됩니다.

FIFO

현실적으로 들어갔을 때 제시되는 첫번쨰 방법은 FIFO입니다.

이 방법은 단순히 가장 오래 메모리를 차지하고 있었던 페이지를 빼는 방법입니다.

언뜻보면 나름 합리적이지만 이 방법을 사용하게되면 정말 중요한 페이지를 빼버릴 수도 있다는 단점이 있고, 가장 중요한 Belady's anomaly라는 문제가 있습니다.

Belady’s anomaly라는 것은 메모리 크기가 커졌는데 fault rate도 커지는 비효율적인 상황을 말합니다.

아래의 그림을 보게되면 메모리사이즈는 커졌는데 fault rate는 오히려 더 올라가게 되었죠.

LRU

그래서 이제 등장한 것이 LRU(Least Recently Used)입니다.

이는 말그대로 과거에 가장 적게 사용한 페이지를 빼자는 방법입니다.

LRU는 locality가 있을 때, OPT에 근접하는 방법이라는 점에서 현실적으로 효율이 좋습니다.

또한 LRU는 stack 알고리즘인데, 이는 앞서 말씀드린 Belady’s anomaly를 겪지않는 알고리즘이라는 것을 뜻합니다.

그러나 모든 상황에서 좋은 것은 아니고 추후에 볼 Loop를 도는 상황이나 큰 파일이 들어오는 상황에서는 기존에 있던 page table을 다 날려버리므로 비효율적입니다.

Random

마지막으로 random 방법이 있습니다.

이 방법은 랜덤하게 page를 뽑아서 swap을 하는 것인데 특정 workload(cpu에서 돌아가는 job의 특성)에서 FIFO, LRU보다 좋은 성능을 보이기때문에 알아둘 필요가 있습니다.

비교

이렇게 4개의 알고리즘을 알아봤는데 여러 상황들에서 각 알고리즘이 어떤 성능을 보이는지 비교를 해봐야겠죠.

Random Workload

1~100까지의 page가 있을 때 랜덤한 page에 대한 요청이 들어오면 어떻게될까요?

OPT를 제외하고 모든 방법들은 다 동일한 양상을 보일 것입니다.

LRU는 locality에 기반해서 세운 방법인데 page 요청이 랜덤하게 들어온다면 그런 locality가 무너지기때문에 LRU나 다른 방법들이나 성능 차이가 없어지는 것이죠.

80-20 Workload

모든 page 요청 중 80%는 자주 쓰는 page에 대한 요청이고 20%는 그렇지않은 page에 대한 요청이라면 성능이 어떻게 나타날까요?

당연히 앞선 상황과는 반대로 Locality가 존재하므로 LRU가 성능적으로 우위를 보이겠죠?

그래서 아래와 같이 나타나게됩니다.

Looping Workload(50 blocks)

한편 50개의 page만을 가지고 순차적으로 1 2 3 … 50 1 2 3… 이렇게 요청을 하는 workload에 대해서는 어떤 양상을 보일까요?

Cache size가 50이 되기전까지 LRU와 FIFO는 계속해서 page fault가 발생할 것이므로 hit rate가 0이되고, Random만이 어느정도의 성능을 보여줄 것입니다.

LRU 구현

이렇게 보면 지금까지 알아본 방법 중에서는 LRU가 가장 합리적이고 어느정도의 성능도 보장되는 것 같습니다.

그렇다면 LRU를 어떻게 구현할 수 있을까요? 이를 구현하기 위해서는 OS가 어떤 page가 접근되었는지 정보를 알고있어야할 것입니다.

그런데 OS는 이 정보를 알 방법이 없습니다.

유일한 방법은 page에 접근할때마다 page fault를 내서 OS가 그 page에 대한 정보를 알게하는 것인데 이는 너무 낭비가 심합니다.

그래서 사용하는 방법은 clock알고리즘입니다.

page table entry에는 R(reference) bit가 있죠. 특정 페이지를 사용할 때 cpu가 이 r bit를 1로 바꾸게 합니다.

그러면 사용한 페이지는 r bit가 1, 아닌 페이지는 r bit가 0이 되겠죠.

clock 알고리즘이란 page들을 순회하면서 r bit가 1인 페이지는 0으로 리셋하고, r bit가 0인 페이지는 제거합니다.

이렇게 page들을 순회하는 양상이 시계와 같아서 clock 알고리즘입니다.

실제로 이 방법에서 더 나아가서 다음과 같이 운영하기도 합니다.

reference bit와 modified bit에 따라 page들을 여러 클래스로 나누고, class 0, 1, 2, 3순서로 swap이 필요할때 page들을 제거하게 됩니다.

Thrashing

마지막으로 Thrashing이라는 개념이 있습니다.

이는 지금 활발히 돌아가고 있는 프로세스들이 쓰는 메모리의 합이 메모리보다 큰 상황을 의미하는데 이런 경우에는 메모리를 정리해주어야겠죠.

그래서 Android의 경우 LMK(Low Memory Killer)를 운영하여 메모리 양이 너무 부족해지면 프로세스를 죽이게 됩니다.

마무리

이번 글에서는 memory가 부족해질 때 컴퓨터가 어떤 식으로 대처하는지 알아보았습니다.

이런 방법들을 통해 컴퓨터는 실제 메모리보다 더 많은 메모리를 가진 것처럼 보이게되는 것이죠.

이 지식을 기반으로 더 공부해서 리눅스와 같은 운영체제는 스왑을 어떻게 운영하는지 분석해보는 것도 좋겠습니다.

감사합니다.