가상 메모리 키워드 공부 3

4. 스왑

세그멘테이션 또는 페이징을 적용하여 동적 재배치에 비해 내부 단편화를 줄였다.
그럼에도 불구하고 실제 시스템에서는 여러 프로세스들이 사용하는 페이지를 모두 물리 메모리에 탑재하기에는 물리 메모리 공간이 모자란 경우가 대부분이다.
이런 물리 메모리 공간의 한계를 극복하기 위해 메모리 계층에 물리 메모리보다 낮은 계층을 추가한다. 물리 메모리가 모자라거나 사용되지 않을 것이라고 판단되는 페이지를 하위 계층에 저장(스왑 swap, swap out) 하는데 보조 저장장치가 이 역할을 담당한다.
스왑을 사용함으로써 프로세스들에게 물리 메모리의 크기를 신경쓰지 않아도 되게했고(가상 주소 공간 전체를 사용할 수 있다), 이는 프로그래밍의 편리함으로 이어진다.

4-1. 스왑 공간

스왑한 페이지들을 저장할 공간을 스왑 공간 swap space라고 한다.
운영체제마다 파티션 혹은 파일의 형태로 이런 스왑 공간을 할당한다.
운영체제는 필요할 경우 스왑 공간에서 물리 메모리로 페이지를 이동시켜야 하므로 물리 메모리의 페이지 위치(물리 주소, 페이지 테이블로 저장하는) 뿐만 아니라 스왑 공간에 있는 페이지들의 디스크 주소 또한 저장해야 한다.
페이지들은 물리 메모리 또는 디스크에 위치[^다만]할 것이고, 프로세스의 메모리 접근 시 페이지가 저장된 위치를 확인해 디스크에 있다면 물리 메모리로 옮긴 후 접근하게 된다. 이런 방식으로 물리 메모리의 공간 한계를 극복할 수 있다.

[^다만]: 디스크에 위치한 페이지들이 반드시 스왑 공간에 있는 것은 아니다. 코드 세그먼트같은 경우 디스크로 스왑되더라도 스왑 공간이 아닌 실행파일 위치에 존재한다.

4-2. Present Bit

스왑을 사용하기 위해서는 PTE에 Present bit이 필요하다.
Present bit는 물리 메모리에 PTE에 해당하는 페이지가 존재하는 지를 나타내는 부호로 만약 0(없음)이라면 페이지가 디스크에 존재한다는 의미이다.

메모리를 참조하는 순서를 살펴보면:

1. TLB 조회
2. TLB 미스
3. PTBR를 이용해 페이지 테이블에 접근
4. Present bit가 0이면 페이지 폴트 발생
5. 페이지 폴트 핸들링
6. (메모리 접근)명령어 재실행

4-3. 페이지 폴트

TLB 미스는 시스템에 따라 하드웨어 또는 운영체제가 핸들링했던 반면 페이지 폴트는 거의 대부분 운영체제가 처리한다. 페이지 폴트 처리를 위해서는 스왑 공간의 구성 방식, 디스크 접근 등 하드웨어가 파악하기 힘든 정보들을 모두 알아야 하기 때문이다. 또한 스왑된 페이지에 대한 페이지 폴트 시에는 디스크에 접근해야 하는데 디스크에 접근하는 시간 자체가 워낙 길기 때문에, 하드웨어가 처리하도록 함에 따른 시간 절약 효과가 크지 않기 때문이기도 하다.

페이지 폴트 처리 방식

1. 요청된 페이지가 메모리에 없고(present bit가 0), 디스크로 스왑되었다면 페이지 폴트가 발생한다.
2. 먼저 페이지를 탑재할 물리 메모리 프레임을 확보해야 한다. 만약 메모리에 탑재할 공간이 없다면, 하나 이상의 페이지들을 스왑 아웃시켜야 한다. 어떤 페이지들을 교체할 지에 대한 정책(페이지 교체 정책 page-replacement policy)은 후술.
3. 운영체제는 디스크[^위치는]에서 해당 페이지를 찾아 메모리에 탑재한다. (메모리로 페이지를 전송할 때에는 DMA를 이용한다.)
4. 페이지 테이블을 갱신한다. PTE의 present bit를 1로 수정하고 PFN에 페이지가 탑재된 프레임의 번호를 저장한다.
5. 페이지 폴트를 처리하고 난 뒤에는 페이지 폴트가 발생한 명령어를 재실행한다.
6. TLB 미스가 발생하고(따라서 페이지 폴트를 처리할 때 TLB를 갱신하도록 할 수도 있다.) 페이지 테이블을 조회하면 이제 present bit가 1일 것이고 PFN을 얻어낼 수 있다.
7. TLB를 갱신하고, 명령어를 다시 한 번 재실행하면 TLB 히트가 발생하면서 메모리에 접근할 수 있게 된다.

[^위치는]: 보통 스왑된 페이지의 디스크 상의 위치는 PTE의 PFN비트를 사용한다. 즉, present bit가 1이면 PFN에 물리 메모리 프레임 넘버를 저장하고, present bit가 0이면 PFN에 디스크의 위치를 저장한다.

5. 페이지 교체

지금까지 핀토스에서는 모든 메모리 페이지를 물리 메모리에 할당하여 사용하였다.
하지만 실제 운영체제에서는 프로세스들이 사용하는 메모리의 합이 머신의 실제 물리 메모리 공간보다 큰 경우가 생길 수 있다.(프로세스가 하나인 경우에도 발생할 수 있다. 일반적으로 가상주소공간은 물리 메모리 크기보다 훨씬 더 크기 때문에..)
운영체제는 이런 상황에 대비하기 위해 페이지의 일부만 물리 메모리에 적재한다.
따라서 적재되지 않은 페이지에 접근해 page fault가 발생한 경우 페이지를 적재하게 되고, 필요한 경우 적재된 페이지 중 일부를 적재해제(교체)해야 할 수 있다.

5-1. 교체 알고리즘

교체할 페이지(victim 페이지)를 선택하는 알고리즘을 페이지 교체 알고리즘이라고 한다.

물리 메모리는 디스크에 비해 더 빠른 접근 속도, 더 작은 용량을 가지고 있으므로 모든 페이지들을 디스크에 저장해놓고 사용할 페이지만 메모리에 가져오게 된다. 이런 관계를 고려할 때 물리 메모리는 페이지를 저장하는 캐시로 여길 수 있다.
그러한 관점에서 교체 알고리즘의 목표는 캐시 미스(페이지 폴트)를 최소화하는, 다른 말로 캐시 히트를 최대로 하는 것이라고 할 수 있다.[^교체알고리즘]

[^교체알고리즘]: 교체 알고리즘은 "무엇을 캐시할 것인가"에서 비롯된 결과물이므로 다른 캐시(TLB, cpu 캐시 등)에도 적용될 수 있다.

교체 알고리즘의 성능은 평균 메모리 접근 시간(average memory access time, AMAT)으로 측정될 수 있으며 디스크 접근 시간과 메모리 접근 시간의 접근 횟수에 대한 가중 평균이다.

가장 기본적인 일부 알고리즘만 살펴보자면:

1. 최적 교체 정책
   가장 나중에 접근될 페이지를 교체하는 정책으로, 가장 적은 횟수의 미스를 발생시킨다는 것이 증명되었다.
   그러나 미래에 어떤 페이지가 접근될 지 미리 알 수가 없으므로, 구현이 불가능하며 교체 알고리즘의 성능 상한을 계산하는데 사용된다.
2. FIFO
   가장 먼저 적재된 페이지를 교체 페이지로 한다.
   구현이 간단하고, 한 번만 사용하는 코드의 경우 유리하다.
   그러나 메모리에 적재된 시점만 고려하고 적재 후 얼마나 자주 접근되는지는 전혀 고려하지 않는다.
   따라서 자주 사용되는 페이지를 메모리에 적재된 지 오래되었다는 이유로 교체하는 일이 발생한다.
   적재 가능한 프레임(물리 메모리에서의 블록. 가상메모리의 페이지와 거의 같은 개념)의 수가 늘어날 수록 page fault의 수가 단조적으로 감소할 것 같지만 FIFO알고리즘에서는 그렇지 않은 경우가 간혹 발생한다.
   이를 Belady's Anomaly라고 부른다.
   예제는 검색하면 많이 나오지만 요약하자면 교체 페이지로 해제되었다가 다시 적재되면 교체 대상순위에서 밀려나므로 결과론적으로 미리 해제되었더라면 page fault가 나지 않았을 상황이 종종 있다는 것이다.(개인적으로 이게 이름이 붙을 정도로 중요한 내용인지 모르겠다.)
3. Random
   교체 페이지를 무작위로 선정한다.
   성능이 확률에 의존하나 간단한 구현으로도 쓸만한 성능을 낸다.
   또한 FIFO나 LRU에서 발생할 수 있는 코너 케이스에서의 Anomaly가 존재하지 않고 모든 케이스에 대해서 일정한 성능을 보인다는 장점이 있다.
4. LRU
   Least Recently Used.
   성능 개선을 위해 과거 정보를 이용한 정책이다.
   프로그램의 시간적 지역성을 이용하여 자주 사용된 페이지가 다시 사용될 가능성이 높다는 가정에서 만들어졌다.
   마지막으로 사용한 시점이 가장 오래된 페이지를 교체 페이지로 한다.
   구현은 카운터 방식(마지막 사용 시점 기록), 스택 방식(참조된 페이지를 스택에 저장)이 있다.
   하지만 메모리에 접근할 때마다 카운터 또는 스택 방식으로 정보를 기록해야 하므로 오버헤드 크다는 단점이 있다.
   성능을 개선하기 위한 근사 알고리즘이 많이 등장하였다.
5. Clock
   LRU의 성능을 개선하기 위해 LRU를 근사한 알고리즘 중 하나.
   참조 여부만을 표시하여 오버헤드를 줄였다.
   교체 페이지를 결정해야할 때에는 포인터(clock hand)가 프레임을 순회하며 결정한다.
   참조 비트가 1(참조됨)인 페이지는 참조 비트를 다시 0으로 바꾸고 넘어간다.
   참조 비트가 0(참조안됨)인 페이지를 발견하면 순회를 멈추고 교체 페이지로 결정한다.
   다음 순회 때에는 이전 포인터의 위치에서부터 시작한다.
   즉, 포인터가 한 바퀴 돌아서 다시 같은 프레임을 가리킬 때까지 한 번이라도 참조되었다면 살려놓고 그렇지 않았다면 교체하는 방식이다.

5-2. 갱신된 페이지(Dirty page)와 갱신되지 않은 페이지(Clean page)

디스크에서 물리 메모리로 이동한 뒤 페이지의 내용이 수정된 페이지를 갱신된 페이지라고 한다.
갱신된 페이지와 그렇지 않은 페이지를 구별하는 것이 필요한 이유는

1. 갱신된 페이지는 디스크로 스왑할 때 프레임의 데이터를 디스크에 기록하는 I/O가 발생한다. 만약 페이지 폴트 중 교체 페이지로 결정된 페이지가 갱신된 페이지라면 추가적인 I/O비용이 발생할 것이다.
2. 갱신되지 않은 페이지는 다시 디스크로 스왑할 때 이미 같은 내용의 페이지가 디스크 존재하므로 추가적인 비용이 없다. 따라서 갱신되지 않은 페이지를 교체 페이지로 선호하는 시스템도 존재한다.

이런 구분을 위해서는 modified bit(dirty bit)를 (주로 PTE에) 추가해야 한다.

6. 페이지와 관련된 다른 이야기들

6-1. 페이지 선택

페이지 교체 외에도 언제 페이지를 메모리로 불러들일 지에 대한 정책(페이지 선택 정책) 도 존재한다.
페이지 선택 정책에는 요구 페이징(demand paging)과 선반입(prefetching) 등이 있다.
요구 페이징은 페이지가 실제로 접근될 때 메모리로 읽어 들인다.
선반입은 곧 사용될 것이라고 예측되는 페이지를 미리 메모리로 읽어들인다.

6-2. 디스크 기록 시점

변경된 페이지를 디스크에 반영하는 시점에 대한 정책도 생각해볼 수 있다.
SSD의 대중화로 그 보조 저장장치의 R/W시간이 감소하였으나 여전히 디스크를 사용하는 것은 많은 클럭 손실을 초래한다. 또한 큰 용량을 순차적으로 쓰는 것이 랜덤 쓰기보다 빠르기 때문에 많은 시스템들은 기록해야 할 페이지들을 바로 디스크에 쓰지 않고 메모리에 모았다가 한 번에 디스크에 기록한다.

6-3. 쓰래싱(Thrashing)

가상 메모리에 있어 쓰래싱은 끊임없이 페이지를 교체하여 성능이 크게 저하되는 상황을 말한다.
메모리가 포화상태에 가까울 때나 프로세스가 요구하는 메모리가 가용 물리 메모리보다 클 때에 발생한다.
운영체제는 일부 프로세스를 종료시키는 등으로 대응한다.