[OS(운영체제)] Virtual Memory Swapping

1. Swapping

Swapping이란 먼저 물리적 메모리에 공간(RAM)이 충분하지 않을 때 발생합니다. 즉 실행을 해야 하는 프로세스를 저장 공간의 부족으로 잠시 다른 스토리지에 프로세스를 옮겨두는 방식을 말한다. 예를 들어 물리적 주소가 cache라고 한다면 저장 공간이 적어서 많은 프로세를 동시에 메모리에 저장을 하기가 어려우니 실행 중이지 않은 그런 프로세스를 디스크에 위치시킨다.

 

메모리의 계층으로 본다면 각각의 메모리가 공간의 부족으로 메모리가 더 많은 메모리로 저장하는 그런 위치는 모든 메모리에서 가능하며 이것을 backing store 이라고 이야기한다.

2. Swap

• Memory overlays

이 방식은 가장 원시적인 방법으로 코드나 데이터를 프로그래머가 변경을 해주는 방식이다.

• Process-level swapping

프로세스의 저장 공간이 부족하면 잠시 backing store로 위치시키고 나중에 실행을 할 때 다시 불러온다.

• Page-level swapping

이 방식은 page단위로 메모리에서 backing store로 이동하고 다시 불러온다.

 

2.1 Page-level Swapping

하드웨어가 PTE를 참조하여서 물리적 메모리에 페이지가 있는지를 확인한다. 하지만 메모리에 존재하지 않으면 Page fault를 발생시킨다.

 

• Page fault : 물리적 메모리(RAM)에 페이지가 존재하지 않는 페이지에 접근하려 할때 발생하는데 이것은 backing store로 페이지가 넘어감을 의미하여 디스크에서 다시 물리적 메모리로 페이지를 불러온다.
• Page replacement : page out 되었던 페이지를 다시 불러오기 위해서 공간을 만들어 두고 페이지를 대체하는 과정을 말한다.

2.2 Where to Swap? 

Swap 상황에 발생하는 Swap-in, Swap-out은 모든 Swap space를 통해서 프로세스가 저장된다. 즉 디스크 공간에 Swap이 발생하면 프로세스를 저장이 가능한 위치를 할당을 하면 이 공간의 사이즈는 최대로 얼마나 많은 페이지를 가지고 있을 수 있는지에 대한 중요한 척도가 된다.

 

2.3 When to Swap?

• Lazy approach : 메모리가 가득 차는 상황까지 OS가 대기하여 swap을 진행한다.
• Proactively based on thresholds : OS가 항상 작은 free공간을 가지고 있음을 유지한다. 특징이 되는 부분은 HW(high watermark) , LW(low watermark)라는 두 개의 임계값이 존재하여서 swap daemon이라는 thread를 통해서 모니터링하여서 swap을 관리한다. ( free pages가 LW 보다 작으면 swap out 시킨다, 반데로 HW 보자 크면 swap daemon 작동을 멈춘다)

2.4 What to Swap

 

Not swapped

kernel code, kernel data , page tales for user processes, kernel stack for user processes :항상 메모리에 유지되어야 하는 데이터와 코드가 있다. 이러한 페이지를 메모리에서 스왑 공간으로 이동시키면 시스템의 성능 저하, 불안정성 또는 심각한 시스템 오류가 발생할 수 있기 때문에, 운영 체제는 이러한 페이지를 항상 메모리에 유지한다.

 

Dropped

User code pages : 이 부분은 프로그램이 실행되는 과정에서 디스크에서 코드를 불러오는 게 가능하기 때문에 드롭한다.

 

User data pages , User heap/stack pages : 이 부분은 프로그램이 실행되는 과정에서 변화되는 데이터가 저장이 되는 경우가 있음으로 swapp을 해준다.

 

Files mmap'ed to user processes, Page cache pages : 데이터가 수정이 일어나면 file system으로 간다.

 

 

3. Page Replacement policy

swap 과정에서 발생하는 즉 물리적 메모리에 page가 존재하지 않는 상황일 때 page fault를 발생시키는데 이것은 프로그램 입장에서 굉장히 리스크가 크다. 그 이유는 디스크에 접근해서 swap을 해야 하기 때문에 disk access 코스트가 많이 든다. 작은 miss rate으로도 AMAT(average memory access time)에 큰 영향을 준다.

 

3.1 OPT(or MIN)

Belay's optimal replacement policy를 사용하는데 간단하게 이야기를 하자면 가장 사용한 지 오래된 페이지를 먼저 대체한다. 이는 효율적으로 fault rate을 낮춰주지만 미래를 예측하기는 어려워서 잘 안 맞는 경우가 있다. 

 

3.2 FIFO(First-In First-Out)

이 방식은 말 그대로 제일 먼저 들어온 게 제일 먼저 나가는 방식으로 메모리에 들어온 시간을 체크하여 가장 오래된 페이지 먼저 바꾸는 방식이다. 하지만 이 방식도 문제는 있는데 오래되었다 하더라도 자주 사용을 해야 하는 페이지가 있을 수 있다. 또한 Belay's anomaly 문제처럼 메모리가 늘어나는 상황에서 오히려 fault 비율이 올라가는 문제가 발생한다.(아래의 그림 참조)

 

 Belay's anomaly 

3.3 LRU(Least Recently Used)

LRU에서는 가장 많이 사용되지 않은 페이지를 교체하는 방법이다. stack 알고리즘을 사용하여 Belay's anomaly문제를 해결하지만 페이지에 많이 방문을 했는지를 비교하는 방식을 사용함으로 구현의 어려움이 있다.

Implementing LRU

• Software approach : OS에서는 ordered list를 가지고 있어서 페이지를 참조하면 리스트의 앞쪽으로 이동시키고 메모리에서 탈락되는 상황이면 리스트의 뒤쪽으로 배치한다. 그래서 참조는 느리지만 교체는 빠르게 가능하다.
• Hardware approach : 각각의 page frame마다 timestamp 레지스터를 할당하여서 clock을 측정한다. 그래서 교체는 가장 clock이 많은 걸 교체하고 메모리 참조는 빠르지만 교체는 느리다. 

 

3.4 RANDOM

이 방법은 가장 직관적인 방법으로 랜덤 하게 교체할 페이지를 선택한다. 

3.5 Clock(Second chance)

PTE의 R(reference) bit을 활용하여서 상태를 표시한다. 아래의 그림처럼 서로 연결되어 있어서 참조 비트를 참조하고 R 비스의 상태에 따라서 교체를 할지 안 할지 정한다. 즉 Page fault 가 발생하면 참조 비트를 참조하여 1이면 0으로 교체하고 다음 페이지로 넘어간다. 그리고 0 이면 그 페이지를 교체한다.

4. Swap in method

4.1 Prefetching

OS가 메모리의 locality를 활용하여서 페이지를 읽어올 때 그 옆에 있는 page도 먼저 가지고 오는 방식

4.2 Clustering, Grouping

이 방식 또한 일정 개수의 페이지를 한 번에 메모리에 올리는 방식이다.