이전 글까지 Paging을 알아보며, 메모리 관리와 관련된 여러 주제를 살펴볼 수 있었다. 하지만 우리가 아직 생각해보지 않은 문제가 있다.
만약 프로세스에서 요구하는 메모리가 현재 남아있는 물리 메모리의 크기보다 크다면 어떻게 해야할까?
위 그림의 Memory Hierarchy를 보면 힌트를 얻을 수 있다. 운영체제는 현재 크게 필요하지 않은 주소 공간의 일부를 저장할 수 있는 장소가 필요하고, 현대 시스템에서는 이 역할을 하드 디스크 드라이브(HDD)가 주로 담당한다. 그렇기 때문에 이번 장의 제목은 "Beyond Physical Memory"이다.
1. Beyond Physical Memory: Mechanisms
1) Swap Space
운영체제가 여러 개의 프로세스를 동시에 실행할 때, 각 프로세스가 사용하는 메모리 공간이 물리 메모리(RAM)에 모두 적재될 수는 없다.
따라서 운영체제는 HDD에 위치한 Swap Space라는 공간을 사용하여, 현재 사용되지 않는 프로세스의 메모리 일부를 하드 디스크와 같은 저장 장치에 임시로 저장한다.
결과적으로, Swap Space를 통해 운영체제는 실제 물리 메모리의 한계를 넘어, 여러 프로세스가 동시에 큰 가상 메모리 공간을 사용하는 것처럼 보이게 할 수 있는 것이다. 이렇듯 물리 메모리와 Swap Space 사이의 swap in, swap out을 수행하는 Swapping 동작이 반복되며 프로세스가 실행된다.
그림을 보면, 현재 프로세스 0, 1, 2의 페이지가 메모리에 저장되어 있고, Swap Space에는 현재 사용되지 않는 프로세스 0, 1, 2, 3의 페이지가 swap out 되어있는 상태라는 것을 볼 수 있다.
이 때, 운영체제는 Swap Space의 각각의 페이지의 위치를 기억하고 있기 때문에, 필요한 경우 다시 swap in을 수행할 수 있다. 프로세스가 처음 실행될 때, 명령어를 메모리로 읽어오는 동작 또한 swap in이라고 볼 수 있다.
2) Present Bit & Page Fault
스와핑을 위해, 하드웨어는 페이지 PTE를 확인하여 특정 페이지가 물리적 메모리에 있는지, 아니면 디스크에 있는지 확인해야 한다. 이 때 사용되는 값이 Present Bit으로, Present Bit가 1이면 메모리에 존재하는 상태, 0이면 swap out된 상태를 의미한다.
Present Bit가 0인 페이지에 접근하려고 할 때 발생하는 것이 바로 Page Fault인데, 이를 좀 더 명확히 표현하면, 현재 물리 메모리에 존재하지 않는 페이지에 접근하려고 한 경우이다.
3) Page Fault Control Flow
이전 글에서 TLB Miss는 Hardware-managed 방식과 Software-managed 방식이 있다고 설명했는데, Page Fault는 무조건 운영체제가 처리하게 된다.
위의 그림을 통해 Flow를 쉽게 이해할 수 있는데, Page Fault가 발생하면 하드웨어는 트랩을 발생시키고, 운영체제는 Secondary Storage(HDD)에 해당 페이지가 존재하는지 확인한 후, 해당 페이지를 페이지 테이블에 넣는다.
이 때, 운영체제는 디스크에서 페이지를 메모리로 불러오기 위해 물리적 메모리 상에 해당 페이지가 저장될 공간(프레임)을 찾아야 한다. 만약 빈 프레임이 없다면, 운영체제는 Page-Replacement Policy을 실행하여, 메모리에서 어떤 페이지를 내보낼지 결정한다.
📌 Page Replacement가 실제로 발생하는 시점은?
운영체제가 메모리가 완전히 가득 찬 후에 페이지를 교체하여 새로운 페이지를 위한 공간을 확보하는 것은 다소 비현실적이다. 따라서 운영체제는 메모리를 미리 일부 비워 두는 방식으로 더 효율적으로 관리한다.
- Swap Daemon
메모리 부족이 심각해지기 전에(예방), 메모리 공간을 미리 확보하기 위해 백그라운드에서 실행되는 스레드이다. 이 스레드는 페이지를 교체하여 메모리에 여유 공간을 확보하려고 한다.
- Page Daemon
메모리 사용량이 너무 높아지면(해소) 실행되는 백그라운드 스레드이다. 해당 스레드 또한 페이지를 교체하여 여유 공간을 확보하려고 한다.
2. Beyond Physical Memory: Policies
앞선 설명에서 Page-Replacement Policy를 언급했는데, 그렇다면 Replacement Policy를 결정하기 위한 기준과 방법들에는 무엇이 있을까? 알아보자!
✅ The Optimal Replacement Policy
먼저, Optimal Replacement Policy, 즉 최적의 경우를 먼저 가정해보자. 교체 시점으로부터 가장 나중에 접근될 페이지를 교체하는 것이 cache miss를 가장 최소화하므로, 최적이라고 볼 수 있다.
위는 Optimal Replacement Policy를 적용한 예시로, Hit rate는 54.6%이다.
✅ A Simple Policy: FIFO
FIFO(First-In, First-Out)는 간단하고 친숙한 알고리즘으로, 단순히 가장 가장 오래된 페이지를 제거하는 방식이다.
메모리에 페이지가 로드될 때마다, 들어온 순서대로 큐(queue)에 추가되고, 이 순서가 유지된다고 해보자.
페이지 교체가 발생하면, FIFO 알고리즘은 큐의 맨 앞에 있는 페이지, 즉 가장 오래된 페이지(First-in)를 메모리에서 제거한다.
📌 Belady’s Anomaly
Belady’s Anomaly는 FIFO(First-In, First-Out) 페이지 교체 알고리즘에서 발생할 수 있는 예상 밖의 현상이다.
일반적으로 캐시 크기가 커지면 더 많은 페이지를 메모리에 유지할 수 있어 히트율이 증가할 것으로 예상되지만, FIFO 알고리즘에서는 이런 예상과 다르게 동작하는 경우가 있다.
직관적으로 말이 안 되는 것 같지만, 실제로 위의 예시와 같은 경우가 존재한다.
✅ Another Simple Policy: Random
Random Page Replacement 알고리즘은 이름 그대로 랜덤하게 페이지를 교체하는 방식이다. 이 방식은 메모리 압박이 심할 때, 교체할 페이지를 무작위로 선택하여 메모리에서 내보내는 방식이다.
당연하게도, 운이 좋으면 덜 사용되는 페이지가 교체되지만, 운이 나쁘면 중요한 페이지가 교체될 수 있다.
✅ Using History : LRU, LFU
Using History를 통한 페이지 교체는 과거의 페이지 접근 기록을 바탕으로, 앞으로 어떤 페이지가 더 자주 사용될지 예측하여 효율적인 교체를 시도하는 방법이다.
LRU(Least Recently Used) 알고리즘은 가장 오래전에 접근된 페이지를 교체 대상으로 선정한다. 즉, 접근 시간(Recency)을 기준으로 판단한다. 최근에 사용된 페이지를 다시 사용할 가능성이 높지만, 장기적인 사용 패턴을 고려하기 어렵다.
LFU(Least Frequently Used) 알고리즘은 페이지의 사용 횟수를 추적하여, 가장 적게 사용된 페이지를 교체 대상으로 선정한다. 즉, 접근 빈도(Frequency)를 기준으로 판단한다. 장기적인 사용 패턴을 반영할 수 있지만, 추가적인 메모리와 계산이 필요하다.
✅ Approximating LRU (Clock Algorithm)
실제로 LRU를 구현하기 위해서는 "가장 오래 참조되지 않은" 페이지를 찾아야 하는데, 모든 페이지에 대해 순차적으로 순서를 갱신하는 작업은 너무 많은 시간이 소요된다. 하드웨어에서 마지막 사용 시점을 기록하는 방식으로 LRU를 지원할 수도 있지만, 그에 따라 하드웨어를 추가적으로 설계하고 구현하는 비용 또한 비현실적이다.
따라서 "가장 오래 참조되지 않은" 페이지를 찾는 대신, "적당히 오래 참조되지 않은" 페이지를 찾는 방식, 즉 Approximating LRU를 구현할 수 있는데, 책에서 소개하는 알고리즘은 Clock Algorithm이다.
페이지가 참조되었는지 여부를 판단하는 use bit이라는 flag를 추가하여, 페이지가 참조될 때마다 하드웨어는 해당 페이지의 use bit을 1로 만든다.
운영체제는 원형 리스트를 돌며, 현재 페이지의 use bit이 0이면 해당 페이지를 교체하고, 1이면 use bit을 0으로 만든다. use bit이 0인 페이지는, 원형 리스트를 한 바퀴 돌 동안 참조되지 않은 페이지인 것이므로, "적당히 오래 참조되지 않은" 페이지라고 할 수 있다.
위의 80-20 Workload Example을 보면 알 수 있지만, Approximating LRU는 LRU와 유사한 성능을 보여준다! (아래의 Workload Example에 대한 설명을 참고하자.)
📌 Considering Dirty Pages
Modified Bit(Dirty Bit)는 페이지가 메모리에서 수정되었는지를 추적하는 하드웨어 지원 플래그이다. 페이지가 Dirty 상태(1)라면, 해당 페이지가 디스크에 있는 원본 데이터와 일치하지 않는 상태이므로, 페이지를 교체하기 전에 디스크로 다시 기록해야 한다.
따라서 페이지 교체 여부를 정할 때, 디스크 기록 작업이 필요 없는 Clean 페이지를 우선적으로 교체하는 것이 성능상 유리하다!
3. Workload Example
현재까지 알아본 알고리즘의 성능을 평가해보자.
1) The No-Locality Workload
No-Locality Workload는 페이지 참조가 무작위로 이루어지는 상황으로, 특정 페이지를 반복적으로 참조하거나 근처의 페이지를 연속적으로 참조하지 않는 경우이다.
이 경우에는 알고리즘보다는 캐시 사이즈에 따라 히트율이 변화하는 것을 볼 수 있다.
2) The 80-20 Workload
80-20 Workload는 지역성(locality)을 가진 작업 부하로, 80%의 참조가 20%의 페이지에 집중되고, 나머지 20%의 참조는 나머지 80%의 페이지에 분포하는 형태이다.
이 경우, LRU(Least Recently Used)가 핫 페이지를 우선적으로 유지하는 특성 덕분에 히트율이 상대적으로 높은 것을 볼 수 있다.
3) The Looping Sequential
The Looping Sequential Workload는 페이지들이 순차적으로 반복되는 접근 패턴을 나타낸다. 예를 들어, 50개의 고유 페이지가 순차적으로 참조된 후, 다시 처음으로 돌아가서 반복되는 접근 패턴이다.
캐시 사이즈가 충분히 크지 않다면, LRU와 FIFO의 성능은 최악일 수 있다. (지속적으로 가장 오래전에 사용된 페이지를 교체하기 때문)
4. Other VM Policies
✅ Prefetching
Prefetching은 페이지를 미리 가져오는 기법으로, 운영체제가 예상되는 페이지 요청에 대해 사전 대응하여 성능을 최적화하는 정책이다.
예시에서는 Page 1이 접근된 시점에서, Page 2 또한 곧 접근될 것으로 예상하여, Page 2도 같이 메모리로 읽어들이는 상황을 보여주고 있다.
✅ Clustering, Grouping
Clustering 또는 Grouping은 메모리에서 대기 중인 여러 개의 쓰기 작업을 모아서 한 번에 디스크에 기록하는 방법이다. 디스크에 쓰기 작업을 요청할 때, 작은 단위로 여러 번 요청하는 대신, 관련된 여러 페이지나 데이터 블록을 하나의 큰 쓰기 작업으로 묶어서 처리한다.
5. Thrashing
Thrashing은 물리적 메모리 부족으로 인해 시스템 성능이 크게 저하되는 현상이다. 프로세스들이 필요한 페이지를 계속 디스크에서 가져오는 상황(Page Fault)이 반복되어, CPU가 실제 작업을 하지 못하고 페이지 교체에 대부분의 시간을 소비하게 된다.
Thrashing을 해결하기 위해, 실행 중인 각 프로세스가 사용하는 메모리의 크기(working set)를 조정하거나, 실행 중인 프로세스 중 일부를 아예 스케줄링에서 제외(swap out)하여 메모리 수요를 줄이는 방법 등이 있다.
마치며
꽤나 길게 운영체제의 메모리 파트에 대해 다룬 것 같다.
해당 파트를 작성하는 도중 3개월 가까이 공백이 생기기도 했는데, 지금부터는 운영체제 시리즈를 완성하기 전까지는 글 작성을 미루지 않고 달려보려고 한다!
다음 글부터는, 개인적으로 운영체제 공부의 꽃이라고 생각하는 Concurrency 파트로 넘어가도록 하겠다.
