[OS] 메모리관리 - 가상메모리, 페이지 교체

가상 메모리

프로그램이 실행 되기 위해서는 프로세스의 전체 주소공간이 메모리에 적재되어있지 않아도 된다.
그렇기 때문에 OS는 프로그램을 실행하기 위해 필요한 부분만을 적재하고 나머지는 Swap Area에서 필요할 때 마다 Swap in 과 Swap out을
반복한다.
그렇기 때문에 프로그램은 물리 메모리의 크기에 제약이 없이 자신만의 가상 메모리를 갖고 0번지 부터 갖을 수 있다.
각 프로세스마다 가상 메모리 공간을 갖고 이 중 일부는 실제로 물리 메모리에 적재가 되어있다.
물리적 메모리는 하드웨어가 관리하지만 가상 메모리는 운영체제가 관여한다.

Demand Paging (요구 페이징)

프로그램을 실행할 때 모든 페이지를 메모리에 적재하는 것이 아니라 필요한 부분만을 메모리에 적재하는 기법이다.
그렇기 때문에 메모리 사용량의 감소, I/O 양의 감소, 빠른 응답시간, 더 많은 사용자 수용등의 효과를 기대할 수 있다.

프로그램의 전체 페이지가 물리 메모리에 적재되어있지 않기 때문에 올라가 있지 않은 페이지들은 Swap Area에서 대기하고 있는다.
그렇기 때문에 실제로 적재 되어있는지, 아니면 Swap Area에 있는지 판단하기 위해서 Valid-invalid bit을 사용한다.
페이지가 참조가 되어 물리 메모리에 적재가 되면 유효비트로 바뀌고, Swap Area로 스왑아웃 될 때 invalid bit으로 바뀐다.

참조하고자 하는 페이지가 존재하지 않아 invalid bit으로 되어있다면 Page Fault가 발생하고 CPU의 제어권은 OS로 넘어간다.

Page Fault의 처리

Page Fault를 처리하기에 앞서서 OS는 우선 CPU가 요구하는 페이지에 대한 상태를 확인하게 된다.
만약 사용되지 않는 주소나 접근권한 위반이라면 해당 프로세스를 Abort 시킨다.

그렇지 않다면 디스크로부터 부재 페이지를 읽어와 빈 프레임에 할당하여 적재한다. 하지만 빈 프레임이 없다면 기존의 메모리에 있는 페이지 중 하나를 디스크로 쫓아내야하는데 이 과정을 Swap out이라고 한다.

디스크에서 메모리로 페이지를 적재하는 과정은 상당한 오버헤드가 있기 때문에 페이지 부재를 발생시킨 프로세스는 CPU를 빼앗기게 된다.

Page Replacement Algorithm

페이지 부재가 생겨서 디스크로부터 페이지를 읽어와 메모리에 적재해야 하는 상황에서 물리 메모리가 꽉 차 있다면 페이지를 디스크로 쫓아내고 해당 프레임에 페이지를 교체해야하는 작업이 필요하다.

이 작업은 상당한 오버헤드를 발생시키기 때문에 Page Fault Rate를 최소화 하는 것이 중요하다. 그것이 바로 교체 알고리즘이다.

Optimal Algorithm(최적 알고리즘) 은 현실 시스템에 구현하기는 불가능하지만 다른 교체 알고리즘의 성능에 대한 Upperbound를 제공한다.
가장 최적의 알고리즘 이기 때문에 측정표로 사용할 수 있다.
이 알고리즘에서는 미래에 참조될 Page를 알고 있다고 가정하고 교체 될 페이지를 가장 먼 미래에 참조될 페이지를 선정하게 된다.

이 알고리즘은 가장 적은 페이지 폴트를 보장한다.

1. First in First out (FIFO): 향후 참조 될 Page를 고려하지 않고 선입선출의 방식으로 먼저 들어온 Page를 내쫓는 알고리즘이다.
이 알고리즘의 단점으로는 비효율적인 상황이 발생할 수 있다는 점이다.
그 이유는 만약 가장 먼저 들어온 페이지가 계속 참조될 상황이 있다면 Page를 교체하지 않는 것이 효율적이다.
하지만 FIFO 알고리즘에서는 그러한 상황은 고려하지 않고 무조건 처음 들어온 Page를 교체하기 때문이다.

또한 이 알고리즘에서는 프레임의 수를 늘리면 오히려 Page Fault가 더 발생하여 성능이 나빠지는 경우가 발생한다.

2. Least Recently Used (LRU): LRU 알고리즘은 가장 오래전에 참조된 페이지를 쫓아낸다.
메모리는 시간 지역성의 특성이 있다. 즉 최근 참조된 페이지는 향후 다시 참조될 가능성이 크다는 뜻이다. 또한 페이지 교체가 많이 일어나면 일어날수록 성능 저하가 일어나기 때문에 참조되지 않을 것 같은 페이지를 교체하는 것이 바람직하다.

LRU에서는 미래에 어떤 Page를 참조할지 모르기 때문에 과거에 참조한 Page를 통해서 제일 오래전에 참조된 페이지를 쫓아낸다.

3. Least Frequently Used (LFU): LFU는 페이지 참조 횟수로 쫓아낼 페이지를 결정한다.
만약 참조 횟수가 동일한 페이지가 있다면 임의의 페이지를 하나 선정한다. 혹은 성능향상을 위해 가장 오래된 페이지를 쫓아내기도 한다.

LRU 알고리즘은 횟수와 관계없이 가장 마지막으로 참조한 페이지를 지운다. 그렇기 때문에 참조를 많이 한 페이지임에도 불구하고 다른 페이지들보다 상대적으로 제일 오래전에 참조했다면, 횟수와 관계없이 쫓겨나게 된다.

LFU 알고리즘은 LRU와 다르게 횟수를 카운팅 하기 때문에 시간의 참조는 중요하지 않다. 즉, 이제 슬슬 참조를 많이 하게 될 페이지가 나타날 수 있는데, 횟수를 따지기 때문에 해당 페이지가 쫓겨날 수 있다.

LFU & LRU 구현

LRU는 가장 오래전에 참조된 페이지를 쫓아내기 때문에 이중 링크 리스트를 사용해서 O(1) 만에 교체할 페이지를 찾을 수 있다.
LFU는 참조 횟수가 중요하기 때문에 다른 페이지들과의 비교가 필요하기 때문에 최악의 경우 모든 페이지들과 비교를 해야해서 O(n)의 시간 복잡도를 갖는다.

하지만 힙을 사용해서 구현하여 사용한다면 O(log n)의 시간 복잡도를 가질 수 있다.

Page Frame Allocation

프로세스가 여러개 수행될 때 프로세스마다 몇개의 프레임을 할당 할 것인지 결정을 해야한다.
페이지 할당 방법은

1. Equal Allocation
2. Proportional Allocation
3. Priority Allocation
   이 있다.

Thrashing & Working Set & Page Fault Frequency

프로세스가 원할하게 수행되기 위해서는 일정한 수준 이상의 페이지가 메모리에 올라가 있어야한다.
필요 이하로 프레임이 할당된다면 페이지 부재율이 높아지게 된다.
예를 들어 반복문인 상황에서는 해당 부분에 대한 페이지를 모두 메모리에 적재하는 것이 유리하다. 그렇지 않다면 매 반복마다 페이지 부재가 일어나고 심각한 오버헤드가 발생하기 때문이다.

이렇게 페이지 부재율이 높아져 CPU 사용률이 현저하게 떨어지는 상황을 Thrashing 이라고 한다.

프로세스의 수를 무작정 늘리게 된다면 각 프로세스에게 할당되는 메모리의 양이 현저하게 줄어들게 된다. 즉, 페이지 부재율이 높아지는 것이다.
페이지 부재가 발생한다면 Disk I/O 작업을 하러가야하는데, 부재율이 높기 때문에 해당 작업을 많이 하게 된다. 즉 CPU 사용률이 떨어진다.
결국 OS는 CPU 사용률이 낮기 때문에 다른 프로세스를 적재하게 되는데 이렇게 된다면 페이지 부재율은 더욱 높아지고 페이지 Swap in, Swap out을 반복하면서 CPU는 일을 하지 않게 된다.

Working Set
프로세스는 특정 주소영역을 집중적으로 탐색하는 특성이 있다.
이렇게 탐색된 페이지들의 집합은 Locality Set이라고 한다.
Working Set 알고리즘은 지역성 집합을 사용하여 이 집합이 동시에 메모리에 올라갈 수 있도록 보장한다.
즉 프로세스가 원할히 수행되기 위해 필요한 페이지들의 집합을 Working Set이라 하고 Working Set이 전부 메모리에 동시에 올라갈 수 있을때만 메모리를 할당하는 방식이다.

그말은 한번에 올라가지 못하는 경우에는 전부 Swap Area로 Swap out 당한다는 것이다.

Working Set 알고리즘에서 중요한 것은 윈도우의 크기다. 윈도우의 크기가 너무 크면 MPD가 감소하며, CPU 이용률이 떨어질 수 있다.
반대로 윈도우 사이즈가 너무 작다면 Locality Set을 모두 수용할 수 없게 된다.
그렇기 때문에 윈도우 사이즈를 결정하는 것이 해당 알고리즘의 핵심이다.

Working set의 윈도우 크기는 시간에 따라 변하기 때문에 프로세스가 메모리를 많이 필요할 때에는 많이 할당, 적게 필요할 때에는 사이즈를 줄이며 동적 프레임 할당을 가능하게 한다.

Page Fault Frequency
해당 알고리즘에서는 페이지 부재율을 계산하여 해당 값을 토대로 페이지 할당량을 결정하는 것이다.
미리 정해진 Upper bound를 넘게 된다면 페이지 부재율이 높다고 판단하여 프레임을 더 할당하고
반대로 Lower bound 이하로 떨어지게 된다면 프레임이 필요 이상으로 많다고 간주하여 할당된 프레임의 수를 줄인다.