[Memory management] Swapping

💡Swapping

OS가 memory의 address space 중 현재 그닥 필요하지 않은 부분 (page)을 hard disk drive에 보관해둠으로써, 
memory 공간의 부족을 완화하는 것이다.

 

swap space

: main memory에 있던 일정한 크기의 page들이 disk 내로 옮겨지는 공간 

 

- 이 공간은 page 단위로 구획돼있어야 한다.

 

 

Present Bit in PTE(Page Table Entry)

 

👇present bit

 

page fault와 page replacement

 

▶Page fault

: physical memory에 존재하지 않는 page에 접근하려 할 때 발생

 

▶Page replacement

아래 순서로 일어난다.

1.
load instruction이 수행됨 
2. 
present bit이 0이어서 page fault 발생 
3.
OS는 아직 swap space에 있는 해당 page를 가져다놓을 memory 공간을 찾으려 함
빈 공간이 없으면, replacement algorithm을 통해 memory의 page를 evict하여 새 page를 위한 공간을 마련
handler는 아직 swap space에 있는 page를 read하기 위한 I/O request (오래걸림)를 일으킴 
4.
I/O request가 satisfy되어, page가 memory에 들어옴 
5.
OS는 page table을 update함
6.
OS는 page fault 때문에 멈춘 instruction을 재시도함
비로소 HW는 원하는 데이터에 access 

 

replacement policies: 어떤 page를 내쫓을지 결정하는 알고리즘

goal

: cache miss 횟수 최소화

 

- AMAT

 

1. Optimal

: 가장 나중에 access될 page를 쫓아내 replace한다.

 

- "이론적으로" 가능한 최고의 성능을 낸다.

- stack property O

stack property란

'메모리 크기 = N일 때' 메모리 내의 page 집합 ⊂ '메모리 크기 = N+1일 때' 메모리 내의 page 집합 인 성질.

즉, 어떤 메모리 크기일 때 메모리에 들어있던 page들이, 메모리 크기를 늘려도 여전히 메모리에 들어있는 것 
→ 메모리 크기를 '늘릴 때' page fault는 '늘어나지 않음'  
→ 메모리 크기 증가에 따른 성능 개선이 보장됨

- stack 방식 기반의 알고리즘들은 모두 stack property를 만족한다. 
∵ 각 page에 priority가 부여돼있음

 

- 문제점: 이 방식은 "가장 나중에서야 access될 page가 누구인가?"를 언제나 잘 예측함을 전제로 하지만, 이건 실제로는 너무 어렵다.

- 그러나, 다른 policy들을 위한 "optimal한 성능을 가진 비교대상"으로서는 유효하다.

 

2. FIFO

: 가장 예전에 cache에 들어왔던 page를 evict

- page가 cache에 들어올 때 queue에 놓이며, replacement하는 때 queue의 tail의 page가 evict됨 

 

- 문제점

˚ page의 importance를 고려하지 않는다. 들어온지 제일 오래된 놈이면, 얼마나 recently/frequently access됐는지는 상관없이 무조건 쫓아내기 때문이다. 

˚ NO stack property (= Belady's anomaly)

 

3. Random

: random으로 고른 page를 evict. 

 

- 문제점: NO stack property (Belady's anomaly)

 

4. LRU: historical algorithm

: least-recently-used page를 evict. 

- recency를 근거로 함: 최근에 access된 page일수록, 또다시 access될 확률 높음

 

 

완벽한 LRU를 위해서는, 각 page들의 recency를 지속적으로 파악하기 위해 모든 memory reference마다 어떤 처리가 필요하므로, 굉장히 소모적이고 성능 저하가 크다. 

다행히, 이런 엄격한 방법까지 아니어도, clock algorithm과 같은 approximation만으로도 의미있는 성능이 나온다.

 

clock algorithm

아래 순서로 일어난다.

모든 page을 circular list에 배열한다.
clock hand는 아무렇게나 고른 page에서부터 시작한다.
replacement할 때, OS는 현재 clock hand가 가리키는 page의 use-bit에 따라 아래를 실행한다.
1이면 → 최근에 사용된 page임 → 귀하신 page니까 안 내쫓음, 대신 use-bit을 0으로 설정함, clock hand는 다음 page 가리킴
0이면 → 최근에 안쓰인 page임 →  이걸 내쫓음 → 끝! 

 

- use-bit: page가 reference되면 이것의 use-bit은 1으로 설정됨 (by HW). 추후 필요시 0으로 clear됨 (by OS)

 

considering dirty page

기본적으로, application이 어떤 데이터를 필요로 하면, 그 데이터는 원래 있던 disk로부터 RAM으로 load(copy)되는 거고,

application이 만약 RAM 상의 이 데이터 page를 modify하여도, disk의 원래 데이터에 바로 반영되는 건 아니므로, RAM에서와 disk에서의 차이가 발생한다.

그러니, RAM 상에서 어떤 page를 그냥 evict하면 안되고, 이 page가 혹시 modify된 즉  dirty page라면 별도로 처리해야 한다.

 

아래 순서로 일어난다.

각 page는 dirty bit을 가지며 (by HW), 메모리에 처음 load될 때는 0으로 설정된다.
어떤 page가 modify되면, 그 page의 dirty bit은 1로 설정된다.
replacement 시 OS는 어떤 page를 evict하기 전에 dirty bit을 확인한 뒤,
0이면 → 그냥 evict,
1이면 → 우선 이 page를 disk에서의 원래 위치에 write부터 하고, 그 뒤 RAM에서 evict한다.

 

- stack property O

: page는 reference될 때 stack top으로 이동하므로, frame의 개수가 n일 때 stack의 상위 n개의 page는 즉 n개의 가장 최근에 사용된 page인 것이다. 

따라서, frame의 개수가 n+1로 늘어나더라도, 마찬가지로 stack의 상위 n+1개의 page는 n+1개의 가장 최근에 사용된 page이므로, n일 때의 page set을 포함한다.

 

workload example

- locality가 없이, 즉 page reference가 random으로 일어나는 경우?

: 어떤 알고리즘이든 성능이 같다. (OPT는 이론적인 이상적 값이므로 논외)

 

- 20%의 page에서 80%의 reference가 일어나고 (→ hot pages),

나머지 80%의 page에서 20%의 reference가 일어나는 (→ cold pages) 경우?

: clock algorithm의 성능이 정석 LRU에 거의 가까울 정도로 좋다.

 

 

page selection policies: page를 메모리에 언제 가져올지 결정하는 알고리즘

1. prefetching

: 어떤 page가 곧 사용될 거라 추측하고, 미리 가져옴  

 

 

page를 disk에 어떻게 write할지 결정하는 알고리즘

1. clustering(grouping)

 

: 한번에 하나씩 write하는 게 아니라, 여러 개의 write 수행을 모았다가 한꺼번에 처리 

 

- 보다 효율적

 

thrashing

메모리가 oversubscribe되고, 실행 중인 프로세스들의 메모리 요구량이 available한 physical memory보다 큰 상황

 

- thrasing 동안에 utilization이 갑자기 안 좋아짐

: 실제 processing보다도 paging swapping하는 데 CPU가 더 많이 쓰이기 때문

 

- 해결: 최근의 일부 Linux에서는 이 경우 out-of-memory killer를 실행하여, memory를 많이 쓰는 프로세스를 kill한다.