0x09. 가상 메모리

배경: 프로그램 전체를 메모리에 올려야 할까?

명령어를 실행하려면 해당 명령어가 물리 메모리에 존재해야 한다. 그렇다면 프로그램 전체를 메모리에 올려야 실행할 수 있을까?

실제로 프로그램에는 거의 사용되지 않는 부분이 많다.

• 에러 처리 코드
• 필요 이상으로 큰 배열이나 리스트
• 드물게 호출되는 루틴

따라서 대안은 프로그램의 일부분만 메모리에 올려서 실행하는 것이다. 프로그램을 부분적으로 적재할 수 있다면 다음과 같은 이점이 생긴다.

• 프로그램이 물리 메모리 크기에 제약받지 않는다
• 더 많은 프로그램을 동시에 실행할 수 있다
• 프로그램 적재와 스왑에 필요한 I/O가 줄어든다

가상 메모리란?

가상 메모리(Virtual Memory) 는 논리 메모리를 물리 메모리로부터 분리하는 기법이다. 핵심은 페이징(Paging) + 스와핑(Swapping, Disk) 의 결합이다.

현재 메인 메모리에 없는 내용도 주소를 통해 참조할 수 있으며, 하드웨어와 OS가 필요한 메모리를 보조 저장장치에서 자동으로 적재한다.

가상 메모리의 장점을 정리하면 다음과 같다.

• 프로그램의 일부만 적재하면 실행 가능하다 (적재 단위: 페이지)
• 논리 주소 공간이 물리 주소 공간보다 훨씬 클 수 있다 (디스크를 활용한 스와핑)
• 주소 공간을 여러 프로세스가 공유할 수 있다 (페이지 공유)
• 효율적인 프로세스 생성이 가능하다 (예: Copy-on-Write)
• 더 많은 프로그램을 동시 실행할 수 있다 (프로그램당 적재 크기가 줄어드므로)
• 프로세스 적재/스왑에 필요한 I/O가 감소한다 (전체 스와핑이 아니라 4KB~4MB 단위의 페이지만 처리)

가상 주소 공간

가상 주소 공간(Virtual Address Space) 은 프로세스가 메모리에 저장되는 방식을 논리적으로 바라본 것이다.

• 일반적으로 주소 0에서 시작하여 연속적인 주소로 구성된다
• 물리 메모리는 페이지 프레임 단위로 구성되며, MMU가 논리 주소를 물리 주소로 매핑한다
• 프로그래머는 메모리 관리를 직접 신경 쓸 필요가 없다
• 가상 주소 공간은 희소(sparse) 할 수 있다 (중간에 빈 공간이 존재)

구현 기법

가상 메모리의 대표적 구현 기법은 요구 페이징(Demand Paging) 이다. 페이징과 스와핑을 결합한 방식이다.

요구 페이징 (Demand Paging)

요구 페이징은 스와핑을 결합한 페이징 시스템과 유사하다. 핵심은 게으른 스와퍼(Lazy Swapper) 또는 페이저(Pager) 라 불리는 방식으로, 꼭 필요한 페이지만 스와핑한다는 점이다.

페이지는 프로그램 실행 중 요구될 때만 적재된다. 이를 위해서는 해당 페이지가 메모리에 있는지 디스크에 있는지 구분하는 하드웨어 지원이 필요하다.

유효/무효 비트를 가진 페이지 테이블

각 페이지에는 유효/무효 비트(Valid/Invalid Bit) 가 존재한다.

• 유효(Valid): 해당 페이지가 유효하며 물리 메모리에 존재한다
• 무효(Invalid): 해당 페이지가 프로세스의 논리 주소 공간에 존재하지 않거나, 존재하지만 물리 메모리에 적재되지 않은 상태다

프로그램이 페이지에 접근하려 할 때:

• 유효 페이지: 정상적으로 실행이 진행된다
• 무효 페이지: OS에 페이지 폴트(Page Fault) 트랩이 발생한다 (하드웨어 인터럽트)

페이지 폴트 처리

페이지 폴트가 발생하면 OS는 다음 절차를 수행한다.

1. 내부 테이블을 확인하여 참조가 유효한지 판단한다
2. 참조가 무효(존재하지 않음) 이면 프로세스를 종료한다
3. 참조가 유효(미적재) 이면 페이지를 적재한다
   • 빈 프레임을 찾는다
   • 원하는 페이지를 빈 프레임에 읽어 들인다 (load)
   • 페이지 테이블을 갱신한다
   • 페이지 폴트를 일으킨 명령어를 재시작한다

순수 요구 페이징(Pure Demand Paging) 에서는 필요하기 전까지 페이지를 메모리에 가져오지 않는다.

이론적으로는 하나의 명령어가 여러 번의 페이지 폴트를 유발할 수 있다. 하지만 실제로 이런 상황은 극히 드물다. 참조의 지역성(Locality of References) 때문이다.

요구 페이징에 필요한 하드웨어 지원은 다음과 같다.

• 페이지 테이블 (유효/무효 비트 지원) -- 페이지 폴트 핸들러
• 보조 메모리 (스왑 공간) -- 디스크
• 명령어 재시작 기능

요구 페이징의 성능

유효 접근 시간(Effective Access Time) 은 다음 공식으로 구한다.

• ma: 메모리 접근 시간 (10~200ns)
• p: 페이지 폴트 확률

페이지 폴트가 발생하면 처리 시간은 대략 다음과 같이 구성된다.

예제: 메모리 접근 시간 200ns, 페이지 폴트 처리 시간 8ms일 때

유효 접근 시간은 페이지 폴트율에 비례한다. 예를 들어 p = 1/1000이면 EAT = 8.2$\mu$s로, 정상 접근 시간(200ns)의 약 40배가 된다.

결론적으로 페이지 폴트율을 최대한 낮게 유지해야 한다.

파일 시스템에서 프로그램 실행

파일 시스템의 프로그램을 실행하는 방법은 두 가지가 있다.

• 옵션 1: 시작 시 파일 전체를 스왑 공간에 복사 (오버헤드 발생). 보통 스왑 공간이 파일 시스템보다 빠르다
• 옵션 2 (권장): 처음에는 파일 시스템에서 요구 페이징으로 적재하고, 이후의 페이징은 스왑 공간에서 수행. 필요한 페이지만 파일 시스템에서 읽으므로 효율적이다

Copy-on-Write (COW)

fork() 시스템 콜은 프로세스를 복제한다. 부모 프로세스의 페이지를 모두 복사해야 하는데, 이를 최적화하는 기법이 Copy-on-Write (COW) 이다.

• 프로세스가 생성될 때 페이지를 실제로 복제하지 않고 공유만 한다 (프로세스 생성 시간 단축)
• 부모나 자식 중 어느 쪽이든 공유 페이지에 쓰기를 하면, 그때 해당 페이지의 복사본이 생성된다

참고로 vfork()는 논리적으로 부모와 메모리를 공유하지만, 현재는 사용되지 않는다(obsolete).

많은 OS는 COW나 스택/힙 확장을 위해 빈 프레임 목록을 유지한다. 여기서 ZFOD(Zero-Fill-On-Demand) 기법이 사용되는데, 빈 프레임의 내용을 최대한 유지하여 디스크 접근을 줄이는 전략이다. 프로세스에 할당하기 전에 해당 페이지를 0으로 초기화한다.

P1이 page C를 수정하기 전:

P1이 page C를 수정한 후:

페이지 교체 (Page Replacement)

요구 페이징에서 발생하는 두 가지 핵심 문제가 있다.

• 페이지 교체(Page Replacement) 알고리즘
• 프레임 할당(Frame Allocation) 알고리즘

약간의 개선만으로도 큰 성능 향상을 얻을 수 있다. 유효 접근 시간이 $(1-p) \times ma + p \times \text{page fault time}$ 이기 때문이다.

페이지 교체의 기본 개념

페이지 폴트가 발생했는데 빈 프레임이 없다면, 현재 사용되지 않는 프레임을 찾아 스왑 아웃(swap out) 해야 한다.

이때 수정 비트(Modify Bit, Dirty Bit) 를 활용하면 쓰기 오버헤드를 줄일 수 있다. 수정 비트가 0이면 해당 프레임은 변경되지 않았으므로 디스크에 다시 쓸 필요가 없다.

프레임 수와 페이지 폴트의 관계

일반적으로 프레임 수가 많을수록 페이지 폴트가 줄어든다. 다만 이 관계가 선형적이지는 않다.

페이지 교체 알고리즘

페이지 교체 알고리즘은 페이지 폴트 처리 시, 어떤 페이지를 교체할지 결정하는 전략이다.

FIFO 페이지 교체

FIFO(First-In, First-Out): 가장 오래된 페이지를 교체 대상으로 선택한다. 구현이 간단하지만 항상 좋은 성능을 보이지는 않는다.

위 예시에서 페이지 폴트 횟수: 15회

FIFO의 문제점은 Belady의 모순(Belady's Anomaly) 이다. 프레임 수를 4개로 늘렸는데 오히려 3개일 때보다 페이지 폴트가 더 많이 발생하는 현상이다.

참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

프레임 수를 늘려도 페이지 폴트율이 증가할 수 있다는 것이 Belady의 모순의 핵심이다.

최적 페이지 교체 (Optimal)

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다.

페이지 폴트 횟수: 9회

이론적으로 최적이지만, 미래의 참조 패턴을 알아야 하므로 실제 구현이 불가능하다. 다른 알고리즘의 성능 비교 기준으로 사용된다.

LRU 페이지 교체

LRU(Least Recently Used): 가장 오랫동안 사용되지 않은 페이지를 교체한다.

페이지 폴트 횟수: 12회

LRU는 성능이 좋아 실제로 가장 널리 사용되는 알고리즘이다.

LRU 구현 방법

카운터(논리 클록) 방식

• 각 페이지 테이블 엔트리에 사용 시간 필드(time-of-use field) 를 연결한다
• 페이지가 참조될 때마다 클록 레지스터 값을 해당 필드에 복사한다
• 문제: 메모리 접근이 매우 빈번하므로 오버헤드가 크다

스택 방식

• 페이지 번호의 스택을 유지한다
• 페이지가 참조되면 스택에서 제거한 뒤 맨 위에 다시 넣는다
• 카운터 방식의 대안이지만, 여전히 느리다

LRU 근사 알고리즘

정확한 LRU를 지원하는 하드웨어는 드물다. 하지만 많은 시스템이 각 페이지의 참조 비트(Reference Bit) 를 하드웨어적으로 지원한다. 페이지가 사용되면 1로 설정되므로, 어떤 페이지가 참조되었는지는 알 수 있지만 순서까지는 알 수 없다.

추가 참조 비트 알고리즘 (Additional-Reference-Bit Algorithm)

일정 간격으로 참조 비트를 기록하여 추가적인 순서 정보를 얻는다. 예를 들어 각 페이지에 8비트 바이트를 유지하며 현재 참조 비트 상태를 기록한다.

세컨드 찬스 알고리즘 (Second-Chance Algorithm)

기본적으로 FIFO 알고리즘이지만, 선택된 페이지의 참조 비트가 1이면 기회를 한 번 더 준다. 이때 참조 비트를 0으로 초기화하고 다음 페이지를 검사한다.

페이지 버퍼링 알고리즘

일부 시스템은 빈 프레임 풀(Pool of Free Frames) 을 유지한다. 페이지 교체 알고리즘으로 미리 교체 대상을 결정해두고, 스왑 아웃을 미리 수행해 놓는다. 페이지 폴트가 발생하면 스왑 인만 하면 되므로 빠르다.

• 풀에서 빈 프레임을 선택하고, 각 빈 페이지에 어떤 페이지가 있었는지 기억하여 이전 페이지를 재사용할 수 있다
• OS는 보통 ZFOD(Zero-Fill On Demand) 기법을 적용한다

수정된 페이지 목록도 유지하여, 페이징 장치가 유휴 상태일 때 수정된 페이지를 디스크에 미리 써 둔다.

프레임 할당 (Allocation of Frames)

고정된 양의 빈 메모리를 여러 프로세스에 어떻게 분배할 것인가? 각 프로세스에 몇 개의 프레임을 할당할지가 핵심 문제다.

각 프로세스의 프레임 수가 줄어들면 페이지 폴트율이 증가하여 성능이 저하된다. 최소 프레임 수는 하나의 명령어가 참조할 수 있는 모든 페이지를 담을 수 있을 만큼 충분해야 한다.

균등 할당 (Equal Allocation)

m개의 프레임을 n개의 프로세스에 균등하게 나눈다: 프로세스당 m/n 프레임.

비례 할당 (Proportional Allocation)

프로세스 크기에 비례하여 메모리를 할당한다.

• $a_i$: 프로세스 $p_i$에 할당되는 프레임 수
• $s_i$: 프로세스 $p_i$의 크기
• $S = \sum s_i$: 전체 프로세스 크기의 합

변형으로 우선순위 기반 할당이나, 크기와 우선순위를 조합한 방식도 있다.

전역 교체 vs. 지역 교체

전역 교체(Global Replacement): 프로세스가 다른 프로세스에 할당된 프레임을 포함하여 모든 프레임 중에서 교체 대상을 선택할 수 있다.

• 장점: 메모리 활용이 효율적이다
• 단점: 프로세스 간 경계가 없어 한 프로세스가 다른 프로세스의 성능에 영향을 준다. 자신의 페이지 폴트율을 제어할 수 없다

지역 교체(Local Replacement): 프로세스에 할당된 프레임 수가 변하지 않는다. 자기 프레임 내에서만 교체가 이루어진다.

• 단점: 잘 사용되지 않는 메모리를 다른 프로세스가 활용할 수 없다

실제로는 전역 교체가 더 일반적으로 사용된다.

스래싱 (Thrashing)

프로세스에 충분한 프레임이 없으면 활발히 사용 중인 페이지를 계속 교체하게 되어, 곧바로 다시 페이지 폴트가 발생한다.

스래싱(Thrashing) 이란 프로세스가 실행보다 페이징(스와핑)에 더 많은 시간을 소비하는 상태를 말한다. 즉 디스크 사용 시간이 CPU 사용 시간을 초과하는 것이다.

스래싱이 시작되면 CPU 이용률이 급격히 떨어진다. 이때 다중 프로그래밍 정도(degree of multiprogramming)를 줄여야 한다.

스래싱을 방지하려면 프로세스에 필요한 만큼의 프레임을 제공해야 한다. 그렇다면 얼마나 필요한지 어떻게 알 수 있을까?

지역성 모델 (Locality Model)

지역성(Locality) 은 함께 활발히 사용되는 페이지들의 집합이다. 프로그램은 일반적으로 여러 지역성으로 구성된다.

워킹셋 모델 (Working-Set Model)

워킹셋(Working Set) 은 가장 최근 $\Delta$개의 페이지 참조에 포함된 페이지들의 집합이다. $\Delta$를 워킹셋 윈도우(Working-Set Window) 라 한다.

예를 들어 $\Delta$ = 10인 경우:

• $WSS_i$: 프로세스 $p_i$의 워킹셋 크기(Working Set Size)
• 프로세스 $p_i$에 할당된 프레임이 $WSS_i$보다 적으면 페이지 폴트가 급격히 증가하여 성능이 크게 저하된다

전체 요구량($\sum WSS_i$)이 가용 프레임 수보다 크면 스래싱이 발생한다.

워킹셋과 페이지 폴트율

프로세스의 워킹셋과 페이지 폴트율은 직접적인 상관관계가 있다. 워킹셋은 시간에 따라 변하며, 페이지 폴트율도 시간에 따라 봉우리(peak)와 골짜기(valley)를 그린다.

페이지 폴트 빈도 (PFF)

스래싱을 제어하는 또 다른 방법은 페이지 폴트 빈도(Page-Fault Frequency, PFF) 를 직접 모니터링하여 다중 프로그래밍 정도를 조절하는 것이다.

• PFF가 너무 높으면: 해당 프로세스에 더 많은 프레임을 할당한다
• PFF가 너무 낮으면: 해당 프로세스에서 프레임을 회수한다

메모리 매핑 파일 (Memory-Mapped Files)

메모리 매핑 파일(Memory-Mapped File) 은 가상 주소 공간의 일부를 파일과 논리적으로 연관시키는 기법이다. 디스크 블록을 메모리의 페이지에 매핑한다.

동작 과정은 다음과 같다.

1. 최초 접근 시 요구 페이징에 의해 페이지 폴트 발생
2. 파일의 페이지 크기만큼을 파일 시스템에서 물리 페이지에 읽어온다
3. 이후 접근은 메모리 접근 루틴으로 처리 (디스크 I/O 없음)
4. 파일이 닫힐 때 메모리 매핑된 데이터가 디스크에 기록된다

장점은 read()/write() 시스템 콜의 오버헤드를 줄이고, 파일 공유가 가능하여 더 빠르다는 것이다.

Win32 API의 공유 메모리

파일 매핑(File Mapping)은 파일의 내용을 프로세스의 가상 주소 공간 일부와 연관시키는 것이다.

• 시스템은 이 연관을 유지하기 위해 파일 매핑 객체(File Mapping Object) 를 생성한다
• 파일 뷰(File View) 는 프로세스가 파일 내용에 접근하기 위해 사용하는 가상 주소 공간의 부분이다
• 대용량 데이터 파일을 효율적으로 처리할 수 있다
• 여러 프로세스가 메모리 매핑 파일을 통해 데이터를 공유할 수도 있다

메모리 매핑 I/O (Memory-Mapped I/O)

I/O 장치는 I/O 컨트롤러의 장치 레지스터를 통해 접근된다. 보통은 특수 명령어가 장치 레지스터와 메모리 사이에서 데이터를 전송한다.

메모리 매핑 I/O(Memory-Mapped I/O) 는 메모리 주소의 일정 범위를 장치 레지스터에 매핑하는 방식이다.

• IBM PC에서는 화면의 각 위치가 메모리 위치에 매핑된다
• 직렬/병렬 포트는 장치 레지스터(포트)의 읽기/쓰기를 통해 데이터를 전송한다

프로그래밍 I/O (Programmed I/O, PIO) 예시: 메모리 매핑 I/O를 통해 긴 바이트 문자열을 전송하는 경우

1. CPU가 바이트를 레지스터에 설정하고 제어 레지스터의 비트를 설정하여 데이터가 준비되었음을 알린다
2. 장치가 데이터를 수신하고 제어 레지스터의 비트를 해제하여 다음 바이트를 받을 준비가 되었음을 CPU에 알린다

참고로, 이와 대비되는 방식이 인터럽트 구동 I/O(Interrupt Driven I/O) 이다.

커널 메모리 할당 (Allocating Kernel Memory)

커널 메모리는 외부 단편화(External Fragmentation) 문제를 해결하는 일반적인 페이징을 사용하지 못한다. 커널은 물리적으로 연속된 메모리가 필요한 경우가 많기 때문이다.

버디 시스템 (Buddy System)

버디 시스템(Buddy System) 은 물리적으로 연속된 페이지로 구성된 고정 크기 세그먼트에서 메모리를 할당한다. 2의 거듭제곱 크기로 할당하는 방식이다.

예를 들어, 256KB의 메모리가 있고 21KB가 요청된 경우:

• 장점: 인접한 버디를 쉽게 합칠 수 있다 (병합이 용이)
• 단점: 내부 단편화가 발생한다 (21KB 요청에 32KB 할당)

슬랩 할당 (Slab Allocation)

커널은 일정한 크기의 구조체(struct)를 반복적으로 할당하고 해제한다. 슬랩 할당은 이 특성을 활용한다.

• 동기: 할당 크기(페이지 단위)와 요청 크기(바이트 단위)의 불일치 문제
• Solaris 2.4와 Linux 2.2부터 적용

각 커널 데이터 구조에 대해 캐시(Cache) 를 만든다.

• 슬랩(Slab): 하나 이상의 물리적으로 연속된 페이지로 구성
• 캐시(Cache): 하나 이상의 슬랩으로 구성

기타 고려 사항

선페이징 (Prepaging)

순수 요구 페이징의 문제는 페이지 폴트가 발생해야만 해당 페이지를 읽어온다는 점이다. 이 때문에 대량의 페이지 폴트가 발생할 수 있다.

선페이징(Prepaging) 은 필요할 것으로 예상되는 모든 페이지를 한꺼번에 가져와서 페이지 폴트를 줄이는 기법이다. 워킹셋 모델을 활용한 예측이 대표적이다.

핵심 쟁점: 선페이징의 비용 vs. 페이지 폴트 처리 비용

페이지 크기

역사적 추세를 보면 페이지 크기는 점점 커지고 있다.

TLB 도달 범위 (TLB Reach)

TLB 적중률(TLB Hit Ratio) 을 높이려면 TLB 크기를 늘려야 하지만, 연관 메모리(Associative Memory)는 비싸고 전력 소모가 크다.

TLB 도달 범위(TLB Reach) 는 TLB로 접근 가능한 메모리의 양이다.

TLB 도달 범위가 클수록 적중률이 높아진다. 페이지 크기를 키우면 TLB 도달 범위가 증가하지만, 단편화도 함께 늘어난다.

이를 해결하기 위해 OS가 여러 크기의 페이지를 지원하는 소프트웨어 관리 TLB 방식이 있다. UltraSparc, MIPS, Alpha가 이 방식을 사용하며, PowerPC와 Pentium은 하드웨어 관리 TLB를 사용한다.

프로그램 구조

사용자가 메모리의 내부 구조를 몰라도 프로그램은 동작한다. 하지만 요구 페이징의 특성을 이해하면 성능을 개선할 수 있다.

예를 들어 페이지 크기가 128워드(정수 크기)일 때, 아래 두 코드 중 B가 더 좋은 성능을 보인다.

I/O 인터록 (I/O Interlock)

I/O 전송과 관련된 메모리 공간은 페이지 교체 대상에서 제외해야 한다. I/O가 진행 중인 페이지가 스왑 아웃되면 데이터 무결성이 깨지기 때문이다.

해결 방법은 다음과 같다.

• I/O 전송을 시스템 메모리를 통해서만 수행한다
• 메모리에 페이지를 잠금(Locking) 하여 스와핑 대상에서 제외한다

HGU 전산전자공학부 김인중 교수님의 23-1 운영체제 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.