[OS10] Virtual Memory

Virtual Memory는 기본적으로 데이터를 실제 메모리에 모두 올리는 것이 아니라 보조 기억장치를 사용해서 실제 메모리 용량이 더 큰 것처럼 사용할 수 있게 해준다.

Demand Paging

Paging 을 요구하는 시점에 Paging을 하는 것이다. 프로세스에서 사용할 메모리 페이지를 프로세스 생성 시 모두 할당하지 않고 필요할 때마다 동적으로 할당한다는 뜻이다.

page 가 세컨더리 스토리지로 내려가고 메모리에 올라가는 것을 Swaping 이라 한다. Demand pageing 은 Locality 때문에 성능이 좋다.

아래의 page table 은 프로세스가 해당 메모리 참조 가능 여부를 valid/invalid 로 구현한 것이다. valid 는 모두 메모리에 존재한다는 뜻이므로 프로세스가 처음 생성될 때는 모두 invalid 로 시작한다. page 가 참조되는 시점에 해당 page 를 메인 메모리에 올리며 valid 로 변경한다.

• valid : 참조할 수 있으며 해당 page 가 메모리에 존재한다.
• invalid : 해당 page가 세컨더리에 존재(page fault)하거나 참조할 수 없다.

---

page table에 0,2,5 번만 valid 는 아래와 같이 두 가지로 해석할 수 있다.

1. 실행한지 얼마 안되어 0, 2, 5 번만 참조되어 메모리에 올라왔다.
2. 오래 실행되었으며, 0, 2, 5번의 locality가 우수해 자주 사용되어 올라와있고, 나머지는 자주 사용되지 않아 세컨더리 스토리지에 존재한다.

현재 CPU의 명령어를 실행하는 과정을 나타냈으며 메인 메모리에 해당 페이지가 없는 경우이다.

Translation을 위해 메모리를 참조하였지만 TLB miss 가 발생, 다시 page table 을 참조했지만 존재하지 않아 해당 페이지를 참조할 수 없는 Page fault 가 일어난다. 더 이상 실행할 수 없으니 OS가 실행되어 세컨더리 스토리지에서 해당 페이지를 읽어와 frame에 집어넣고 명령어를 restart 한다.

실제 명령어의 실행 과정을 보자면 아래와 같다.

1. TLB 히트되어 바로 참조하는 경우가 99% 이다.
2. TLB miss 로 Page table을 참조하는 경우로 MMU가 주체로써 하드웨어적으로 작동한다.
3. Page table에서 page fault가 일어나는 경우로 이 때만 OS가 처리하며 극히 적은 확률이다.

아래 그림에서는 copy-on-Write에 의해 Demand paging이 구현되어있다. 유닉스에서 프로세스 생성은 fork()로 이루어지는 데, process 1을 fork() 해서 동일한 프로세스인 process2가 만들어진다.

이때 두 프로세스는 복사 시점에서는 동일하기 때문에, 실제로 P1과 P2가 달라지는 순간 페이지 단위로 Copy한다. 달라지는 순간 page C 를 생성해 연결하는 방식이다.

Page Replacement

세컨더리 스토리지에서 페이지를 읽어 메모리에 올리려는데 Free Frame이 없다면 어떤 Frame을 내리고(Victim) 올려야할까?? 정답은 Page fault 수를 줄이는 방향으로 가는 것 이다. 당연하게도 할당된 free frame의 수와 page fault는 반비례하게 발생한다.

변경할 페이지를 선택하는 것에 여러 알고리즘이 존재한다. 하지만 기본적으로 많이 사용되는 것은 메모리에 남겨놓는 것이 좋고 오래 동안 사용되지 않았으면 앞으로도 사용되지 않을 가능성이 높다는 것을 이미 알고 있다. 따라서 Locality 에 따라 페이지를 선택할 수 있다.

1. FIFO 가장 오래전에 올라온 프레임이 내려간다. 가장 공평한 방법이다.

아래와 같이 참조되는 페이지가 나열되어있을 때 1, 2, 3 을 프레임에 넣은 후 4 는 자리가 없기 때문에 가장 오래전에 올라온 1을 내리고 들어간다. 같은 과정으로 3 프레임에서는 총 9 번의 fault 가 일어난다.

4 프레임에서는 총 10번의 fault 가 일어난다. 이유는 1, 2, 3, 4 를 프레임에 집어넣고 1, 2이 바로 사용되었지만 1이 가장 오래전에 들어왔다는 이유로 5로 대체되는 것을 볼 수 있다.

1. Optimal

FIFO 에서 계속해서 바로 다음에 사용될 프레임을 내리게되니 바로 다시 올려야하는 문제점이 발생한다. 따라서 사용할 프레임을 보고 page fault가 가장 적게 일어나도록 더 이상 안쓰이는 프레임을 내리는 방법이다. 이론적으로 당연히 가장 우수하겠지만, 현실적으로 뒤에 어떤 순서로 참조될지 아는 것이 불가능하다.

1. LRU (Least Recently Used) FIFO 에서 4 프레임이 오히려 더 많은 fault 를 가지는 것에 대한 해결책으로 가장 오래전에 사용된 프레임을 찾아 내리는 것이다.

1, 2, 3, 4 를 프레임에 넣고 1, 2 는 방금 사용되었으므로 3이 5와 대체되는 것을 확인할 수 있다.

1. Implementation of LRU 가장 오래 전에 사용되었다는 것을 알기 위해 타임스탬프를 관리한다. 하지만 페이지마다 스탬프를 찍어 저장하면 용량에 문제가 생길 수 있다. 참조되는 순서대로 스택을 저장하는 방법이 있지만 참조될때마다 스택을 바꾸면 오버헤드가 매우 크다는 문제가 있다. 따라서 여기에서는 타임스탬프를 1비트로 줄여 저장한다.

2. Second chance(LRU clock) 값이 1이면 최근에 참조되었다, 0이면 참조되지 않았다는 뜻이다. 주기적으로 비트를 0으로 만들면서 참조될때마다 1로 바꿔준다. 프레임을 포인터로 가르키면서 reference bit가 1이면 0으로 바꾸고 포인터가 넘어간다. 최근 참조되었으니 지금은 바로 교체하지 않고 넘어간다는 뜻이다. 반면 포인터가 reference bit가 0인 프레임에 도착하면 그 프레임을 교체한다.

1. NRU (Not Recently Used) 비트를 두 개 사용한다. R(Reference) M(Modify). (0,0)은 전혀 사용되지 않았으므로 우선순위가 가장 낮고 (1,1)의 우선순위가 가장 높다. (1,0) 과 (0,1) 중에서는 read의 locality가 더 높기 때문에 (1,0)의 우선순위가 더 높다. 모든 페이지는 (0,0) 에서 시작한다.

1. LFU (Least Frequently Used) : 시간 시준이 아니라 횟수 기준으로 카운트하는 방법이다. 최근에 많이 참조될 수록 다시 참조될 확률이 높다. 카운터를 다시 1자리 비트로 관리하면 LRU과 거의 동일하다고 볼 수 있다.

Page Table Entries (PTEs)

아래는 실제 NRU를 사용할 때 page table 을 저장 form 이다.

V : Valid / Invalid R : Reference bit M : Modify bit Prot : 이 페이지가 읽기/쓰기/실행 중에 뭐가 가능한지 나타낸다.

Allocation of Frames

지금까지는 하나의 프로세스에서 사용하는 페이지를 어떻게 Free Frame에 할당할 것인지에 대해 알아보았다. 이제는 하나의 프로세스가 아니라 여러 프로세스들에게 어떻게 Free Frame 을 할당할 것인지 정해야한다. 만약 프로세스가 10개 존재하면 각 프로세스에 어떻게 Free Frame을 할당할 것인가? 동일하게? 크기에 따라? 우선운위에 따라?

A 프로세스의 Frame을 Replace할 때 A 프로세스가 가진 Frame 중에서 Replace (Local replacement) 할 것인가 전체 Frame 중에서 Replace(Global replacement) 할 것인가?? 당연하게도 각 프로세스들은 자신이 처음 할당받은 Free Frame 을 지키면서 Replace 를 해야한다. 즉 Local replacement 사용한다.

Page-Fault Frequency Scheme

프로세스에서 너무 많은 Page fault가 일어나면 할당한 Frame의 개수가 너무 적은 것이고, Page fault가 너무 적게 일어나면 너무 많은 Frame을 할당한 것이다.

Trashing

프로세스가 Page Swaping 만 하느라, 즉 Page fault 가 너무 많이 일어나서 일을 수행하지 못하는 상태이다. 메모리를 추가하거나 프로세스를 줄여야한다. Locality에 의해 자주 사용되는 것들이 메모리의 크기보다 크면 발생한다.

Working-Set

Locality를 알려주는 것이다. 특정 시간 동안 사용된 페이지의 집합으로 작을 수록 Locality가 좋다. 전체 Working-Set Size보다 시스템 메모리가 작으면 Trashing이 발생한다.

Prepaging

1번 page fault 가 일어나면 2번도 일어날 확률이 높으니 메인 메모리에 같이 가져온다.

Page Size

세컨더리 스토리지는 실제 디스크의 헤더의 seek time 등으로 오버헤드가 가장 크다. 따라서 읽어온다면 한 번에 많이 읽어오는 것이 좋다. Page table은 page의 크기가 커야 세컨더리 스토리지에서 읽어오는 횟수가 줄어든다. Loaclity에서도 page 크기가 적당히 커야 사용하기 용이하다. 하지만 page 크기가 큰 것의 단점은 Internal Fragmentation이 커진다는 것이다.

TLB Reach

TLB 가 커버하는 메모리 공간이다. TLB size * Page size 이다.