[OS-반효경] Virtual Memory

저번 포스팅에서는 메모리 관리에 대해 알아보았습니다. 논리 주소를 물리 주소로 변환하는 과정은 하드웨어(MMU, TLB 등)가 담당했고, 운영체제는 페이지 테이블을 통해 각 프로세스의 주소 공간을 물리 메모리에 매핑했습니다.

하지만 물리 메모리는 제한적이기 때문에, 프로세스의 모든 페이지를 항상 메모리에 적재해 할 수는 없습니다. 이 문제를 해결하기 위해 운영체제는 가상 메모리를 사용하며, 대표적인 구현 방식 중 하나가 필요한 페이지만 메모리에 적재하는 Demand Paging입니다.

Demand Paging

Demand Paging은 프로세스의 모든 페이지를 한 번에 메모리에 올리는 대신, 실제로 해당 페이지에 대한 접근이 발생했을 때만 필요한 페이지를 메모리에 적재하는 방식입니다. 이 방식을 사용하면 당장 사용되지 않는 페이지를 미리 적재하지 않아도 되므로, 불필요한 디스크 I/O를 줄이고 메모리 사용 효율을 높일 수 있습니다.

그림은 Demand Paging 상황을 보여줍니다. 프로세스의 가상 주소 공간(page 0~7)은 페이지 테이블로 물리 메모리의 프레임에 매핑됩니다. 이때 페이지 테이블의 각 엔트리는 매핑된 프레임 번호와 valid/invalid bit를 포함합니다. v는 해당 페이지가 현재 메인 메모리에 존재함을, i는 메모리에 없고 디스크(backing store)에 있음을 의미합니다.

예시로 A(page 0), C(page 2), F(page 5)만 물리 메모리(frame 4, 6, 9)에 올라와 있고 나머지는 i 상태입니다. i인 페이지에 대한 CPU 접근이 발생하면 page fault가 발생합니다. 운영체제는 backing store에서 해당 페이지를 읽어 메모리에 적재한 뒤, 페이지 테이블 엔트리를 v로 갱신합니다.

Page Fault

Page Fault는 프로그램이 접근하려는 가상 메모리 페이지가 물리 메모리에 없을 때 발생하는 인터럽트입니다. → MMU가 trap을 발생시킴

위 사진은 page fault 처리 흐름을 단계별로 보여줍니다.

1. 프로세스가 load M처럼 특정 페이지를 참조

2. 해당 페이지 엔트리가 i라서 MMU가 trap을 발생시키고 OS로 제어가 넘어감

3. OS는 그 페이지가 backing store에 존재함을 확인

4. 빈 프레임을 확보한 뒤, backing store에서 페이지를 읽어 물리 메모리로 적재

5. 페이지 테이블 엔트리를 프레임 번호로 갱신하고 valid를 v로 바꾼다.

6. 중단됐던 명령을 재시작하여 정상 실행을 이어감

Page Replacement

지금까지는 빈 프레임 이 존재한다는 가정하에 page fault를 처리했습니다. 하지만 실제 물리 메모리가 가득 차서 더 이상 빈 프레임을 확보할 수 없는 경우가 많습니다.

이때는 필요한 페이지를 올리기 위해, 현재 메모리에 올라와 있는 페이지 중 하나를 희생(victim)으로 선택해 내보내고 그 자리에 새 페이지를 적재해야 합니다.
이 과정을 Page Replacement라고 합니다.

교체 대상 페이지를 잘못 고르면 page fault가 자주 발생해 성능이 급격히 떨어질 수 있으므로, 어떤 페이지를 내보낼지 결정하는 Replacement Algorithm이 중요합니다.

Replacement Algorithm

대표적인 알고리즘은 다음과 같습니다.

Optimal Algorithm

Optimal Algorithm은 앞으로 가장 늦게 다시 참조될 페이지를 victim으로 선택해 교체하는 방식입니다. 이론적으로 page fault 횟수를 최소화하므로, Page Replacement 알고리즘의 최적 기준(upper bound)으로 사용됩니다.

다만 실제 시스템에서는 미래의 참조 순서를 알 수 없기 때문에, Optimal Algorithm은 직접 구현하기보다는 다른 알고리즘의 성능을 비교할 때 기준으로 활용됩니다.

FIFO(First-In First-Out) Algorithm

FIFO는 메모리에 가장 먼저 들어온 페이지를 가장 먼저 교체하는 방식입니다.

FIFO는 페이지의 최근 사용 여부를 고려하지 않기 때문에, 자주 사용되는 페이지가 오래 전에 들어왔다는 이유만으로 교체될 수 있습니다. 또한 프레임 수를 늘렸는데도 page fault가 증가하는 Belady’s Anomaly가 발생할 수 있습니다.

LRU(Least Recently Used) Algorithm

LRU는 가장 오랫동안 참조되지 않은 페이지를 victim으로 선택해 교체하는 방식입니다.

LRU는 일반적으로 FIFO보다 page fault가 적지만, 참조 정보를 계속 갱신해야 하므로 오버헤드가 크다는 단점이 있습니다. 그래서 실제 시스템에서는 LRU를 그대로 쓰기보다는 LRU 근사 알고리즘(Clock Algorithm)을 많이 사용합니다.

LFU(Least Frequently Used) Algorithm

LFU는 참조 횟수가 가장 적은 페이지를 victim으로 선택해 교체하는 방식입니다.

LFU는 과거의 누적 참조 횟수가 계속 남는다는 문제가 있습니다. 초반에 많이 쓰였던 페이지가 이후에는 거의 사용되지 않아도, 카운터가 커서 메모리에 오래 남을 수 있습니다. 그래서 실제로는 일정 주기마다 카운터를 감소시키는 Aging 같은 보정 기법을 함께 사용하기도 합니다.

LRU와 LFU 알고리즘의 구현

LRU는 페이지들을 최근 사용 순서대로 관리하기 위해 연결 리스트를 사용합니다. 가장 최근에 참조된 페이지는 MRU 쪽에 두고, 가장 오래 참조되지 않은 페이지는 LRU 쪽에 배치합니다. 어떤 페이지가 참조되면 해당 노드를 리스트에서 꺼내 MRU 위치로 이동시키며, 교체가 필요하면 LRU 끝에 있는 노드를 제거합니다. LRU는 페이지를 교체하기 위한 비교가 필요 없기 때문에 $O(1)$ 복잡도를 가집니다.

LFU는 각 페이지의 참조 횟수를 기준으로 교체 대상을 고르기 때문에, count가 작은 페이지가 우선되도록 힙으로 관리합니다. 페이지가 참조될 때마다 해당 페이지의 count를 증가시키고, 힙에서 위치를 재조정합니다. 교체가 필요하면 힙의 루트에 있는 가장 작은 count 페이지를 victim으로 선택합니다. 이 과정에서 힙 재정렬이 발생하므로 갱신/삭제의 시간 복잡도는 보통 $O(\log n)$ 입니다.

LFU를 단순히 연결 리스트로 구현하면 victim을 찾기 위해 전체를 순회해야 하므로 $O(n)$ 시간이 걸립니다.
그래서 일반적으로는 최소 참조 횟수를 빠르게 선택할 수 있도록 힙 구조를 사용합니다.

페이지 교체는 page fault가 발생할 때 수행되므로, victim을 고르는 과정이 오래 걸리면 page fault 처리 시간이 그대로 늘어납니다. 결국 전체 실행 시간이 증가하기 때문에, 실제 시스템에서는 victim을 빠르게 선택할 수 있는 자료구조와 알고리즘을 주로 사용합니다.

Clock Algorithm

Clock Algorithm은 LRU를 그대로 구현하기 어렵기 때문에, LRU를 근사 하기 위해 사용하는 Page Replacement 기법입니다. 각 페이지 프레임에 Reference Bit(R bit)를 두고, 이를 원형 큐(시계) 형태로 관리합니다.

동작 방식은 다음과 같습니다.

1. 페이지가 참조되면 해당 프레임의 R bit = 1로 설정
2. 교체가 필요하면 포인터(시계 바늘)가 가리키는 프레임부터 검사
3. R bit = 0 이면 최근에 참조되지 않았다고 보고, 그 프레임을 victim으로 선택해 교체
4. R bit = 1 이면 ‘한 번의 기회’ 주기 위해 R bit를 0으로 바꾸고, 포인터를 다음 프레임으로 이동
5. 위 과정을 반복하다가 R bit가 0인 프레임을 만나면 교체

즉, 최근에 참조된 페이지(R=1)는 바로 교체되지 않고 한 바퀴를 돌면서 기회를 얻고, 오래 참조되지 않은 페이지(R=0)가 먼저 교체됩니다. 포인터가 원형으로 한 칸씩만 이동하므로 구현이 단순하고, 평균적으로 빠르게 victim을 찾을 수 있습니다.

Page Frame의 Allocation

page fault가 발생했을 때 어떤 페이지를 교체할지를 알아봤습니다. 이제는 각 프로세스에 프레임을 얼마나 줄지를 정리해보겠습니다.

물리 메모리는 프레임 개수가 한정되어 있고, 동시에 여러 프로세스가 실행되기 때문에 운영체제는 프로세스마다 사용할 수 있는 프레임 수를 적절히 나눠줘야 합니다. 프레임을 너무 적게 주면 page fault가 자주 발생해 성능이 떨어지고, 너무 많이 주면 다른 프로세스가 사용할 메모리가 부족해집니다.

일반적으로는 다음과 같은 방식으로 프레임을 할당합니다.

• Equal Allocation: 모든 프로세스에 동일한 개수의 프레임을 할당
• Proportional Allocation: 프로세스 크기(페이지 수)에 비례해 프레임을 할당
• Priority Allocation: 우선순위가 높은 프로세스에 더 많은 프레임을 할당

다음으로는, 프레임을 할당한 뒤 page replacement를 전체 프로세스 기준으로 할지(Global), 각 프로세스 내부에서만 할지(Local)를 살펴보겠습니다.

Global Replacement는 page fault가 발생했을 때 victim을 선택하는 범위를 시스템 전체 프레임으로 두는 방식입니다. 따라서 victim은 다른 프로세스가 사용 중인 프레임에서도 선택될 수 있으며, 프로세스가 보유하는 프레임 수는 실행 중 변할 수 있습니다.

Local Replacement는 victim 선택 범위를 해당 프로세스에 할당된 프레임으로 제한하는 방식입니다. 이 경우 victim은 해당 프로세스의 프레임에서만 선택되며, 프로세스별 프레임 수는 고정됩니다.

Thrashing

Local Replacement에서는 프로세스가 사용할 수 있는 프레임 수가 고정되기 때문에, 할당된 프레임이 부족하면 필요한 페이지를 메모리에 유지하지 못합니다. 이 상태에서 실행을 계속하면 page fault가 반복적으로 발생하고, 그때마다 디스크에서 페이지를 읽어오고 기존 페이지를 내보내는 작업이 계속 수행됩니다.

이처럼 page fault와 page replacement가 과도하게 반복되어 CPU가 실제 연산보다 페이지 교체 처리에 더 많은 시간을 쓰는 상태를 Thrashing이라고 합니다. Thrashing이 발생하면 page fault rate는 증가하고 CPU Utilization은 감소해 시스템 전체 성능이 급격히 저하됩니다.

즉, Thrashing은 프로세스에 할당된 프레임 수가 부족해 page fault가 계속 발생할 때 나타납니다. 이를 완화하기 위해 운영체제는 프로세스별로 필요한 프레임 수를 추정하고, 실행 중에 프레임 할당량을 조정해야 합니다.

대표적인 방법이 Working-Set Model과 PFF Scheme입니다.

Working-Set Model

프로세스는 실행 중 특정 시간 구간에서 일부 메모리 영역의 페이지만 집중적으로 참조하는 경향이 있습니다. 이처럼 일정 시간 동안 집중적으로 참조되는 페이지들의 집합을 locality set이라 하고, Working-Set Model에서는 이를 working set라고 합니다.

Working set은 시점 $t$에서 최근 $\Delta$ 동안 참조된 페이지들의 집합 $W(t,\Delta)$로 표현합니다. 미래 참조를 직접 알 수 없기 때문에 운영체제는 최근 참조 기록(과거)을 기반으로 working set을 추정합니다.

운영체제는 working set 크기에 맞춰 프레임을 할당하고, 전체 working set 합이 물리 메모리를 초과하면 일부 프로세스를 swap out하여 thrashing을 방지합니다.

PFF(Page-Fault Frequency) Scheme

PFF는 프로세스의 page fault 발생 빈도를 측정해 프레임 수를 조절합니다. page fault 빈도가 상한을 넘으면 프레임을 추가로 할당하고, 하한보다 낮으면 프레임을 회수합니다. 즉, page fault rate를 일정 범위로 유지하도록 프레임을 동적으로 조정하는 방식입니다.

Page Size

지금까지 Demand Paging, Page Fault 처리, Page Replacement, 그리고 Thrashing을 줄이기 위한 Working set / PFF까지 살펴봤습니다. 이 모든 동작은 결국 ‘페이지’ 단위로 이뤄지기 때문에, 마지막으로 페이지 크기를 어떻게 정할지를 정리해보겠습니다.

페이지 크기는 작을수록 내부 단편화가 줄고 locality를 더 잘 반영할 수 있지만, 페이지 수가 늘어나 페이지 테이블 크기와 관리 오버헤드가 커집니다. 반대로 페이지 크기가 크면 페이지 테이블 오버헤드는 줄어들지만, 내부 단편화가 늘고 page fault 시 한 번에 읽어오는 데이터가 많아져 I/O 비용이 커질 수 있습니다.

즉, 페이지 크기는 메모리 사용 효율, 페이지 테이블 오버헤드, 그리고 Page Fault 처리 비용 사이의 Trade-Off로 결정하면 됩니다.

Conclusion

이번 포스팅에서는 Demand Paging, Page Fault 처리, Page Replacement, Thrashing 등에 대해 알아 보았습니다. 다음 포스팅은 파일 시스템에 대해 자세히 알아보겠습니다.

References

[1] KCOW 운영체제 반효경 강의

[2] Operating System Concepts(Silberschatz, Galvin and Gagne)

[3] 가상 메모리