가상 메모리

배경

앞서 살펴본 메모리 관리 알고리즘은

실행 중인 코드가 반드시 물리 메모리에 존재해야 한다는 기본 요구 조건을 만족시키기 위한 방법.

이 요구 조건을 가장 쉽게 만족시키는 방법은 전체 프로세스를 메모리에 올리는 방식.

동적 적재는 전체 프로세스를 한꺼번에 메모리에 올려야 한다는 제약을 일부 완화하지만, 

일반적으로 프로그래머에게 특별한 주의와 추가 작업을 요구하는 방식.

실행 중인 코드가 반드시 물리 메모리에 있어야 한다는 조건은 일견 타당해 보이지만, 

실제 프로그램 전체가 항상 동시에 필요한 것은 아닌 구조.

프로그램에는 잘 발생하지 않는 오류 상황을 처리하는 코드가 포함될 수 있으며, 

이런 코드는 실제로 거의 실행되지 않는 경우가 많음.

배열, 리스트, 테이블은 필요 이상으로 크게 선언될 수 있으며, 실제 사용되는 부분은 그중 일부일 수 있음.

또한 프로그램 안의 옵션이나 기능 중 일부는 거의 사용되지 않을 수 있고, 

전체 프로그램이 필요한 경우에도 모든 부분이 동시에 요구되지는 않는 구조.

프로그램의 일부만 메모리에 올려 실행할 수 있다면 여러 이점 존재.

첫째, 프로그램은 물리 메모리 크기에 의해 더는 제한받지 않고 매우 큰 가상 주소 공간을 기준으로 작성 가능.

둘째, 각 프로그램이 더 작은 메모리를 차지하므로 더 많은 프로그램을 동시에 수행할 수 있고, 

응답 시간과 반환 시간의 증가 없이 CPU 이용률과 처리율 향상 가능.

셋째, 프로그램을 메모리에 올리고 스왑하는 데 필요한 I/O 횟수가 줄어들어 프로그램이 더 빠르게 실행되는 효과.

가상 메모리는 실제 물리 메모리 개념과 개발자의 논리 메모리 개념을 분리하여, 

프로그램 크기가 물리 메모리 크기에 의해 제한되지 않도록 만드는 기법.

사용 가능한 물리 메모리보다 큰 주소 공간을 프로그램에 제공함으로써, 

프로그래머가 메모리 크기에 관한 한계를 덜 신경 쓰고 문제 자체에 집중할 수 있게 하는 추상화.

프로세스의 가상 주소 공간은 그 프로세스가 메모리에 저장되는 논리적 관점.

전통적으로 프로세스는 특정 논리 주소에서 시작하여 연속적인 주소 범위로 구성되는 방식.

가상 주소 공간은 보통 주소 0에서 시작하며, 연속적으로 존재하는 것처럼 보이는 구조.

프로세스 안에서 텍스트, 데이터, 힙, 스택 같은 영역은 논리 주소 공간 안에 배치되는 영역.

가상 메모리 시스템은 스택이 아래쪽으로 성장하고 힙이 위쪽으로 성장하도록 두 영역을 배치할 수 있는 구조.

스택과 힙 사이에는 사용되지 않는 큰 구멍이 생길 수 있으며, 

이러한 공간은 실제 물리 페이지가 할당되지 않은 희소 주소 공간.

희소 주소 공간은 힙이나 스택이 성장할 때만 실제 페이지를 할당하면 되므로 메모리 사용을 줄이는 효과.

가상 메모리는 둘 이상의 프로세스가 파일과 메모리를 공유할 수 있게 하는 장점.

프로세스들은 공유 라이브러리의 물리 페이지를 각자의 가상 주소 공간에 매핑하여 

동일한 라이브러리 코드를 공유할 수 있는 구조.

공유 메모리 영역을 통해 서로 통신할 수도 있으며,

이 영역은 각 프로세스의 가상 주소 공간에 매핑되지만 실제로는 같은 물리 페이지를 가리키는 구조.

fork 시스템 콜을 통한 프로세스 생성 과정에서도 가상 메모리 기법은 페이지 공유를 통해 생성 속도를 높일 수 있는 역할.

이 장에서는 가상 메모리 시스템의 구현 방법 중 가장 일반적인 요구 페이징 방식을 중심으로 설명.

 

요구 페이징

요구 페이징은 실행 프로그램을 보조저장장치에서 메모리로 적재할 때 필요한 페이지만 적재하는 방식.

프로그램 전체를 물리 메모리로 가져오지 않고, 실제 실행에 필요한 페이지가 요구될 때만 메모리로 가져오는 구조.

필요한 페이지를 미리 모두 읽는 것이 아니라, 페이지가 실제로 참조될 때까지 적재를 지연하는 기법.

요구 페이징 시스템은 스와핑과 유사하지만, 전체 프로세스가 아니라 개별 페이지 단위로 동작하는 구조.

스왑퍼가 전체 프로세스를 다룬다면, 페이저는 프로세스의 개별 페이지를 다루는 구성 요소.

요구 페이징은 가상 메모리의 주요 이점 중 하나를 실현하는 핵심 메커니즘이며, 

효율적으로 동작하려면 페이지가 메모리에 있는지 없는지를 구분할 수 있는 하드웨어 지원 필요.

 

기본 개념

요구 페이징의 기본 개념은 필요할 때만 페이지를 메모리에 적재한다는 것.

페이지가 필요하지 않으면 절대 메모리에 올라오지 않고, 메모리에 없는 페이지에 접근하는 순간 페이지 폴트 발생.

이를 지원하려면 페이지 테이블 항목에 유효·무효 비트가 필요.

유효 비트는 해당 페이지가 합법적이며 현재 메모리에 존재한다는 의미.

무효 비트는 해당 페이지가 프로세스의 주소 공간에 속하지 않거나, 

합법적이지만 현재 메모리에 올라와 있지 않다는 의미.

메모리에 올라와 있지 않은 페이지에 접근하면 페이지 테이블 항목의 무효 비트 때문에 페이지 폴트 트랩 발생.

페이지 폴트는 운영체제가 필요한 페이지를 적재하지 않았기 때문에 발생하는 트랩.

페이지 폴트가 발생하면 운영체제는 먼저 해당 메모리 참조가 유효한지 검사하는 과정.

프로세스 내부 테이블이나 PCB와 함께 유지되는 정보를 확인하여 참조가 합법적인지 판단하는 흐름.

참조가 무효한 페이지에 대한 접근이면 프로세스는 중단되는 구조.

참조는 유효하지만 페이지가 아직 메모리에 없다면 보조저장장치에서 해당 페이지를 찾아야 하는 상황.

운영체제는 가용 프레임을 찾고, 해당 프레임으로 페이지를 읽어 들이는 디스크 작업을 요청.

디스크 읽기가 끝나면 페이지 테이블과 내부 테이블을 수정하여 해당 페이지가 이제 메모리에 존재함을 표시하는 과정.

중단되었던 명령어는 다시 시작되고, 프로세스는 마치 페이지가 처음부터 메모리에 있었던 것처럼 계속 실행되는 구조.

극단적으로 프로세스가 시작될 때 아무 페이지도 메모리에 올리지 않을 수 있으며,

이를 순수 요구 페이징이라고 부르는 개념.

순수 요구 페이징에서는 첫 번째 명령어 접근부터 페이지 폴트를 발생시킬 수 있는 구조.

명령어 하나를 실행하는 데 여러 페이지 폴트가 발생할 수도 있음.

명령어 페이지, 피연산자 페이지, 결과 저장 페이지가 서로 다르면 

한 명령어 처리에 여러 페이지가 필요할 수 있는 상황.

그러나 대부분의 프로그램은 참조 지역성 때문에 요구 페이징이 실제로는 효율적으로 동작 가능.

한 번 참조한 페이지 주변의 페이지를 다시 참조할 가능성이 높고, 

프로그램은 일정 시간 동안 일부 페이지 집합을 집중적으로 사용하는 경향.

요구 페이징을 지원하기 위해서는 페이지 테이블, 보조저장장치, 명령어 재시작 기능이 필요.

페이지 테이블에는 유효·무효 비트 또는 보호 비트가 있어 페이지가 메모리에 있는지 확인 가능해야 하는 조건.

보조저장장치는 메모리에 없는 페이지를 저장하는 공간이며, 보통 빠른 디스크나 NVM 장치가 사용되는 구조.

명령어 재시작은 페이지 폴트 처리 후 중단되었던 명령어를 정확히 다시 실행할 수 있게 하는 기능.

페이지 폴트가 명령어 수행 중간에 발생하더라도 운영체제는 필요한 페이지를 가져온 후 

해당 명령어를 다시 실행해야 하는 구조.

명령어가 여러 메모리 위치를 참조하거나 일부 위치를 수정한 뒤 페이지 폴트가 발생할 수 있으므로,

 명령어 재시작은 중요한 하드웨어·운영체제 요구 사항.

 

가용 프레임 리스트

페이지 폴트가 발생하면 운영체제는 보조저장장치에서 읽어 온 페이지를 넣을 메모리 프레임이 필요.

운영체제는 이러한 목적을 위해 사용 가능한 물리 메모리 프레임들을 연결한 가용 프레임 리스트를 유지.

페이지 폴트가 발생하면 가용 프레임 리스트에서 프레임을 하나 꺼내 페이지를 적재하고, 

사용된 프레임은 리스트에서 제거되는 구조.

시스템이 시작될 때 사용 가능한 모든 메모리는 가용 프레임 리스트에 들어가는 상태.

이 리스트는 페이지 폴트 처리뿐 아니라 프로세스 생성 과정에서도 사용되는 자료구조.

운영체제는 보안과 안정성을 위해 새로 할당되는 프레임을 0으로 채우는 경우가 많음.

이 기법은 zero-fill-on-demand라고 부르는 방식.

zero-fill-on-demand 프레임은 할당되기 전 이미 0으로 채워져 있어 

이전 내용이 새 프로세스에 노출되지 않는 장점.

일부 시스템은 별도의 zero-fill 리스트를 유지하여 필요한 순간 빠르게 0으로 초기화된 프레임을 제공하는 구조.


 

요구 페이징의 성능

요구 페이징은 메모리 접근 시간에 큰 영향을 줄 수 있는 기법.

대부분의 경우 페이지 폴트가 발생하지 않으면 메모리 접근은 일반적인 메모리 접근 시간과 거의 같음.

하지만 페이지 폴트가 발생하면 보조저장장치 접근과 운영체제 처리 비용이 추가되는 구조.

유효 접근 시간은 페이지 폴트 확률에 따라 결정되는 값.

페이지 폴트 확률을 p, 메모리 접근 시간을 ma, 페이지 폴트 시간을 page fault time이라고 하면 

유효 접근 시간은 대략 (1 - p) × ma + p × page fault time이라는 구조.

페이지 폴트 처리 시간은 인터럽트 처리, 페이지 읽기, 프로세스 재시작이라는 세 가지 주요 요소로 구성.

운영체제는 페이지 폴트를 감지하고, 트랩을 처리하며, 페이지가 어디에 있는지 찾고, 가용 프레임을 확보하는 과정 수행.

그 뒤 보조저장장치에서 페이지를 읽고, 페이지 테이블을 갱신하고, 중단된 명령어를 다시 시작하는 흐름.

보조저장장치에서 페이지를 읽는 시간은 보통 가장 큰 비용.

기계적 디스크에서는 탐색 시간, 회전 지연 시간, 전송 시간이 포함되므로 

페이지 폴트 처리 시간이 매우 길 수 있음.

페이지 폴트 비율이 매우 낮아도 메모리 접근 시간은 크게 증가할 수 있는 구조.

예를 들어 메모리 접근 시간이 200ns이고 페이지 폴트 처리 시간이 8ms라면, 

아주 작은 페이지 폴트 확률도 유효 접근 시간을 크게 증가시키는 요인.

따라서 요구 페이징 시스템의 성능은 페이지 폴트율을 매우 낮게 유지하는 데 크게 의존.

페이지 폴트율을 낮추기 위해서는 참조 지역성을 활용하고, 적절한 페이지 교체와 프레임 할당이 필요.

스왑 공간을 파일 시스템보다 빠르게 관리하면 페이지 폴트 처리 시간을 줄일 수 있는 장점.

일부 시스템은 프로세스 시작 시 프로그램 전체 이미지를 스왑 공간에 복사한 뒤, 

이후 요구 페이징을 스왑 공간에서 수행할 수 있는 구조.

파일 시스템에서 바로 요구 페이징을 수행할 수도 있으나, 

일반 파일 시스템의 오버헤드가 페이지 폴트 처리 성능에 영향을 줄 수 있음.

Linux와 BSD UNIX 계열은 실행 파일에서 요구 페이징을 수행하고, 

수정된 페이지는 스왑 공간으로 기록하는 방식 사용.

모바일 시스템에서는 스와핑 대신 파일 시스템 기반 적재와 앱 종료 정책을 조합하는 경우가 많음.

 

쓰기 시 복사

쓰기 시 복사 copy-on-write는 프로세스 생성 시 부모와 자식이 처음부터 모든 페이지를 복사하지 않고 

페이지를 공유하도록 하는 기법.

fork 시스템 콜을 사용하면 자식 프로세스는 부모 프로세스의 주소 공간 복사본을 가져야 하는 구조.

그러나 대부분의 경우 자식 프로세스는 곧바로 exec 시스템 콜을 호출하여 새로운 프로그램을 실행하므로, 

전체 페이지 복사는 낭비가 될 수 있는 상황.

쓰기 시 복사는 부모와 자식이 같은 페이지를 공유하도록 하고, 

둘 중 하나가 공유 페이지에 쓰기를 시도할 때만 실제 복사본을 만드는 방식.

처음에는 부모와 자식의 페이지 테이블이 같은 물리 페이지를 가리키고, 

해당 페이지들은 쓰기 시 복사 페이지로 표시되는 구조.

공유 페이지에 쓰기를 시도하면 페이지 폴트가 발생하고, 

운영체제는 그 페이지의 복사본을 새로운 프레임에 만든 뒤 쓰기를 허용.

쓰기 시 복사는 실제로 수정되는 페이지만 복사하므로 프로세스 생성 비용을 크게 줄이는 장점.

수정되지 않는 페이지는 계속 부모와 자식이 공유할 수 있는 구조.

이 기법은 공유 페이지를 읽기 전용으로 설정하고, 쓰기 시도 때 트랩을 발생시켜 구현 가능.

새로운 복사 페이지가 필요할 때는 가용 프레임 리스트에서 프레임을 얻어 사용하는 흐름.

가용 프레임을 빠르게 확보하기 위해 zero-fill-on-demand 기법이 함께 사용될 수 있음.

쓰기 시 복사는 Windows, Linux, macOS 등 여러 운영체제에서 프로세스 생성 최적화에 사용되는 방식.

Linux, macOS, BSD UNIX 계열은 fork와 유사하지만 

부모 프로세스가 자식 종료 또는 exec 전까지 일시 중단되는 vfork 시스템 콜도 제공.

vfork는 자식이 부모의 주소 공간을 그대로 사용하므로 쓰기 시 복사도 수행하지 않는 구조.

vfork는 매우 빠르지만 자식이 부모 주소 공간을 수정하면 위험하므로 제한된 방식으로 사용해야 하는 기법.

 

페이지 교체

요구 페이징에서는 프로세스가 실제로 필요한 페이지만 메모리에 올라오므로 물리 메모리 요구량을 줄일 수 있음.

하지만 여러 프로세스가 동시에 실행되면서 물리 메모리보다 많은 페이지가 필요해지는 상황 가능.

시스템이 메모리를 초과 할당하면 페이지 폴트 발생 시 가용 프레임이 없을 수 있는 문제.

가용 프레임이 없을 때는 메모리에 있는 기존 페이지 중 하나를 선택하여 내보내고, 

새 페이지를 그 자리에 적재해야 하는 필요.

이 작업이 페이지 교체.

페이지 교체는 요구 페이징의 기본 구조를 유지하면서 실제 물리 메모리보다 큰 가상 메모리를 제공하게 하는 핵심 기법.

교체 과정에서는 

희생 프레임을 선택하고, 필요하면 그 내용을 보조저장장치에 기록한 뒤, 새 페이지를 해당 프레임에 읽어 들이는 흐름.

희생 페이지가 수정되지 않았다면 디스크에 다시 쓸 필요 없이 그냥 버릴 수 있는 구조.

이를 위해 페이지 테이블에는 변경 비트 또는 수정 비트가 사용됨.

수정 비트는 페이지가 메모리에 올라온 뒤 내용이 변경되었는지를 나타내는 정보.

수정된 페이지는 교체 전에 보조저장장치에 기록해야 하지만, 

수정되지 않은 페이지는 다시 읽어올 수 있으므로 기록 없이 제거 가능.

페이지 교체는 논리 메모리와 물리 메모리 사이의 분리를 완성하는 기능.

사용자는 큰 가상 주소 공간을 사용하지만, 

운영체제는 실제 물리 프레임 수에 맞게 페이지를 교체하며 실행을 유지.

이때 중요한 결정은 

각 프로세스에 몇 개의 프레임을 할당할 것인지와 교체가 필요할 때 어떤 페이지를 내보낼 것인지에 대한 문제.

좋은 페이지 교체 알고리즘은 페이지 폴트율을 낮추는 것을 목표로 하는 전략.

페이지 교체 알고리즘의 성능은 참조 문자열을 기준으로 평가 가능.

참조 문자열은 프로세스가 실행 중 접근하는 페이지 번호의 순서.

같은 페이지에 대한 연속 참조는 한 번만 페이지 폴트를 일으키므로, 

알고리즘 평가에서는 페이지 번호의 흐름이 중요한 기준.

프레임 수가 많아질수록 일반적으로 페이지 폴트 수는 감소하는 경향.

 

 

기본적인 페이지 교체

기본 페이지 교체의 흐름은 

페이지 폴트 발생, 보조저장장치에서 필요한 페이지 위치 확인, 

가용 프레임 탐색, 희생 프레임 선택, 희생 페이지 기록, 새 페이지 적재, 페이지 테이블 갱신, 명령어 재시작의 순서.

가용 프레임이 있으면 그 프레임을 바로 사용하면 되는 구조.

가용 프레임이 없으면 페이지 교체 알고리즘을 사용해 희생 프레임을 선택해야 하는 상황.

희생 페이지가 수정되었다면 보조저장장치에 기록해야 하며, 수정되지 않았다면 기록 작업 생략 가능.

디스크 기록과 디스크 읽기가 모두 필요하면 페이지 폴트 처리 시간이 두 배 가까이 증가할 수 있는 구조.

수정 비트는 불필요한 디스크 쓰기를 줄여 페이지 폴트 서비스 시간을 감소시키는 역할.

요구 페이징, 페이지 교체, 프레임 할당은 서로 밀접하게 연결된 메모리 관리 문제.

 

FIFO 페이지 교체

FIFO 페이지 교체 알고리즘은 가장 오래 전에 메모리에 올라온 페이지를 교체 대상으로 선택하는 방식.

FIFO는 first-in first-out의 약자이며, 먼저 들어온 페이지가 먼저 나가는 큐 구조.

운영체제는 페이지가 메모리에 올라온 순서를 기록하고, 교체가 필요하면 큐의 앞쪽 페이지를 제거.

FIFO는 구현이 단순하지만 성능이 항상 좋지는 않은 알고리즘.

오래 전에 들어온 페이지가 여전히 자주 사용되는 페이지일 수 있기 때문.

FIFO에서는 프레임 수가 증가했는데도 페이지 폴트 수가 증가할 수 있는 현상 발생 가능.

이 현상을 Belady의 모순이라고 부르는 개념.

Belady의 모순은 프레임을 더 많이 주면 항상 성능이 좋아질 것이라는 직관이 틀릴 수 있음을 보여주는 사례.

FIFO는 구현은 쉽지만 페이지 사용 빈도나 최근 사용 여부를 고려하지 못하는 한계.

 

 최적 페이지 교체[Optimal Page Replacement]

최적 페이지 교체 알고리즘은 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식.

이 알고리즘은 이론적으로 가장 낮은 페이지 폴트율을 제공하는 기준 알고리즘.

최적 교체는 Belady의 모순이 발생하지 않는 알고리즘.

그러나 미래의 참조 문자열을 미리 알아야 하므로 실제 운영체제에서 구현하기 어려운 방식.

따라서 최적 알고리즘은 주로 다른 페이지 교체 알고리즘의 성능을 비교하는 기준으로 사용.

실제 시스템에서는 최적 교체를 직접 구현하기보다, 이에 가까운 성능을 내는 근사 알고리즘을 사용.

 

LRU 페이지 교체

LRU 페이지 교체 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 선택하는 방식.

LRU는 least recently used의 약자.

이 알고리즘은 과거의 사용 이력이 미래의 사용 가능성을 어느 정도 예측한다는 지역성에 기반.

최근에 사용된 페이지는 가까운 미래에도 다시 사용될 가능성이 높고, 

오랫동안 사용되지 않은 페이지는 가까운 미래에도 사용되지 않을 가능성이 높다는 가정.

LRU는 FIFO보다 일반적으로 더 좋은 성능을 보이며, Belady의 모순도 발생하지 않는 특성.

정확한 LRU를 구현하려면 각 페이지가 마지막으로 사용된 시점을 기록해야 하는 필요.

카운터 방식은 매 메모리 참조마다 시간 값을 증가시키고, 페이지 테이블에 마지막 참조 시간을 저장하는 방식.

교체 시에는 가장 오래된 시간 값을 가진 페이지를 선택하는 구조.

카운터 방식은 정확하지만 메모리 참조마다 페이지 테이블을 갱신해야 하므로 하드웨어 비용이 큰 문제.

스택 방식은 페이지가 참조될 때마다 해당 페이지를 스택 위로 이동시키는 구조.

가장 최근 참조 페이지는 스택 위에 있고, 가장 오래 참조되지 않은 페이지는 스택 아래에 위치하는 방식.

스택 방식도 정확한 LRU 구현이 가능하지만, 참조마다 스택 구조를 갱신해야 하므로 하드웨어와 소프트웨어 비용이 큰 방식.

정확한 LRU는 성능은 좋지만 구현 비용이 높아 대부분의 시스템은 LRU 근사 알고리즘을 사용.

 

LRU 근사 페이지 교체

많은 시스템은 정확한 LRU 구현을 위한 충분한 하드웨어 지원을 제공하지 않으므로 LRU 근사 알고리즘 사용.

대부분의 근사 알고리즘은 페이지 테이블 항목에 참조 비트를 둠.

참조 비트는 페이지가 참조될 때 하드웨어에 의해 1로 설정되는 비트.

운영체제는 참조 비트를 주기적으로 검사하거나 초기화하여 페이지 사용 이력을 추정 가능.

부가적 참조 비트 알고리즘은 

일정 시간 간격마다 각 페이지의 참조 비트를 기록하여 여러 비트의 사용 이력을 만드는 방식.

최근 여러 구간 동안 참조된 기록이 적은 페이지를 교체 대상으로 선택하는 구조.

참조 기록을 오른쪽으로 이동하고 현재 참조 비트를 가장 왼쪽 비트에 넣으면, 

각 페이지의 최근 사용 정도를 근사적으로 비교 가능.

2차 기회 알고리즘은 FIFO를 기반으로 하되 참조 비트가 1인 페이지에게 한 번 더 기회를 주는 방식.

참조 비트가 0이면 해당 페이지를 교체하고, 1이면 0으로 바꾼 뒤 큐의 뒤로 보내는 구조.

2차 기회 알고리즘은 원형 큐와 포인터를 사용하여 시계 알고리즘으로 구현되는 경우가 많음.

포인터는 페이지들을 순환하며 참조 비트를 확인하고, 교체 가능한 페이지를 찾을 때까지 이동.

개선된 2차 기회 알고리즘은 참조 비트와 수정 비트를 함께 사용하여 페이지를 여러 부류로 나누는 방식.

(0, 0)은 최근 사용되지 않았고 수정되지 않은 가장 좋은 교체 후보.

(0, 1)은 최근 사용되지 않았지만 수정된 페이지로, 교체 가능하지만 쓰기 비용이 필요한 후보.

(1, 0)은 최근 사용되었지만 수정되지 않은 페이지.

(1, 1)은 최근 사용되었고 수정된 페이지로, 가장 나중에 교체하는 편이 좋은 후보.

개선된 2차 기회 알고리즘은 가능하면 참조되지 않았고 수정되지 않은 페이지를 먼저 선택하여 I/O 비용을 줄이는 전략.

 

 계수 기반 페이지 교체

계수 기반 페이지 교체 알고리즘은 각 페이지가 참조된 횟수를 세어 교체 대상을 선택하는 방식.

LFU 알고리즘은 가장 적게 사용된 페이지를 교체하는 방식.

LFU는 least frequently used의 약자.

LFU는 참조 횟수가 적은 페이지는 앞으로도 적게 사용될 가능성이 높다는 생각에 기반.

하지만 초기에는 많이 사용되었으나 이후 사용되지 않는 페이지가 계속 높은 참조 횟수를 유지할 수 있는 문제.

MFU 알고리즘은 가장 많이 사용된 페이지를 교체하는 방식.

MFU는 most frequently used의 약자.

MFU는 참조 횟수가 적은 페이지가 최근에 들어와 아직 충분히 사용될 기회가 없었을 수 있다는 생각에 기반.

LFU와 MFU는 일반적으로 실제 시스템에서 널리 쓰이지 않으며, 근사 LRU보다 효과가 떨어지는 경우가 많음.

 

페이지 버퍼링 알고리즘

페이지 버퍼링 알고리즘은 페이지 교체 알고리즘과 함께 사용되어 성능을 높이는 보조 전략.

운영체제는 일정 수의 가용 프레임 풀을 유지하여 페이지 폴트가 발생했을 때 빠르게 새 페이지를 읽어 들일 수 있음.

희생 페이지를 디스크에 기록하기 전에 먼저 가용 프레임에 필요한 페이지를 읽어 들이면 프로세스가 더 빨리 재개 가능.

수정된 희생 페이지는 나중에 배치 방식으로 디스크에 기록할 수 있음.

수정된 페이지 목록을 별도로 유지하면 디스크가 한가할 때 해당 페이지들을 미리 기록하여 수정 비트를 지울 수 있음.

교체 시점에 이미 수정 비트가 지워진 페이지는 디스크 쓰기 없이 바로 제거 가능.

일부 시스템은 가용 프레임 풀에 있는 프레임이 예전 페이지 내용을 유지하도록 하여, 

같은 페이지가 다시 필요할 때 빠르게 복구할 수 있는 효과를 얻음.

이 방식은 페이지를 완전히 지우기 전까지 일종의 캐시처럼 활용하는 전략.

 

응용과 페이지 교체

일부 응용 프로그램은 운영체제의 일반 페이지 교체보다 자신이 직접 저장장치를 관리하는 것이 더 효율적인 경우가 있음.

대표적인 예는 데이터베이스 시스템.

데이터베이스는 자체 버퍼 관리와 I/O 스케줄링을 사용하여 

운영체제의 페이지 교체와 충돌하지 않도록 설계되는 경우가 많음.

운영체제의 파일 시스템 캐시와 데이터베이스 자체 캐시가 같은 데이터를 이중으로 캐시하면 메모리 낭비 발생 가능.

데이터베이스는 특정 페이지가 다시 사용될 시점을 운영체제보다 더 잘 알 수 있으므로, 

자체 캐시 관리가 유리할 수 있음.

일부 운영체제는 raw disk나 direct I/O를 제공하여 응용 프로그램이 파일 시스템 버퍼 캐시를 우회할 수 있게 함.

응용이 직접 I/O를 관리하면 운영체제의 페이지 교체 알고리즘과 응용의 버퍼 관리 정책 사이의 불일치를 줄일 수 있음.

하지만 운영체제의 보호, 동기화, 캐시 기능을 우회하므로 응용 프로그램이 더 많은 책임을 가져야 하는 방식.

 

프레임의 할당

페이지 교체가 가능하려면 각 프로세스에 몇 개의 프레임을 할당할 것인지 결정해야 하는 문제.

사용 가능한 프레임 수가 제한된 상황에서 여러 프로세스가 경쟁하므로, 프레임 할당 정책은 성능에 큰 영향.

가장 단순한 방법은 각 프로세스에 동일한 수의 프레임을 할당하는 균등 할당.

하지만 프로세스마다 크기와 필요 메모리 양이 다르므로 균등 할당이 항상 적절한 것은 아닌 구조.

큰 프로세스는 더 많은 페이지를 사용하므로 더 많은 프레임이 필요할 수 있고, 

작은 프로세스는 적은 프레임만으로도 효율적으로 실행 가능.

프레임 할당은 페이지 폴트율, CPU 이용률, 시스템 처리율과 직접 관련된 문제.

 

최소로 할당해야 할 프레임의 수

각 프로세스에는 최소한으로 필요한 프레임 수가 존재.

최소 프레임 수보다 적게 할당하면 명령어 하나를 완료하는 데 필요한 페이지를 모두 담을 수 없어 

실행 불가능한 상황 발생 가능.

예를 들어 

명령어 자체가 있는 페이지, 피연산자가 있는 페이지, 결과를 저장할 페이지가 모두 필요하면 

적어도 여러 프레임이 필요.

CPU는 페이지 폴트가 발생한 명령어를 다시 시작해야 하므로, 

명령어 수행에 필요한 페이지들이 충분히 메모리에 있어야 하는 조건.

최소 프레임 수는 컴퓨터 구조의 명령어 형식에 따라 달라지는 값.

간단한 명령어 집합에서는 최소 프레임 수가 작을 수 있지만, 

여러 주소를 참조하는 복잡한 명령어에서는 더 많은 프레임 필요.

간접 주소 지정이 여러 단계로 이어지는 구조에서는 한 명령어가 많은 페이지를 참조할 수 있으므로 

최소 프레임 수가 커질 수 있음.

 

할당 알고리즘

m개의 프레임과 n개의 프로세스가 있을 때, 

각 프로세스에 몇 개의 프레임을 나누어 줄 것인지 결정하는 것이 할당 알고리즘.

균등 할당은 모든 프로세스에 m/n개의 프레임을 나누어 주는 방식.

균등 할당은 단순하지만 프로세스 크기 차이를 고려하지 못하는 한계.

비례 할당은 프로세스의 크기나 페이지 수에 비례하여 프레임을 나누어 주는 방식.

프로세스 크기나 페이지 수가 클수록 더 많은 프레임을 받는 구조.

비례 할당은 각 프로세스의 요구량을 반영한다는 장점.

우선순위 할당은 프로세스의 우선순위를 고려하여 프레임을 할당하는 방식.

높은 우선순위 프로세스는 더 많은 프레임을 받아 페이지 폴트를 줄일 수 있고, 

낮은 우선순위 프로세스는 더 적은 프레임을 받을 수 있음.

우선순위 할당은 CPU 스케줄링 정책과 메모리 관리 정책을 함께 고려할 수 있는 방식.

 

전역 대 지역 할당

페이지 교체 범위를 어떻게 정할 것인지에 따라 전역 교체와 지역 교체로 구분.

전역 교체는 한 프로세스가 페이지 폴트를 발생시켰을 때 

다른 프로세스에 할당된 프레임까지 교체 대상으로 삼을 수 있는 방식.

지역 교체는 페이지 폴트를 일으킨 프로세스가 자기에게 할당된 프레임 안에서만 교체 대상을 선택하는 방식.

전역 교체는 전체 시스템 관점에서 더 유연하게 프레임을 재분배할 수 있는 장점.

하지만 한 프로세스가 다른 프로세스의 프레임을 빼앗아 성능을 예측하기 어렵게 만들 수 있는 단점.

지역 교체는 프로세스별 프레임 수를 안정적으로 유지하므로 성능 예측이 쉬운 편.

하지만 어떤 프로세스는 프레임이 남고 다른 프로세스는 부족한데도 서로 조정할 수 없어 전체 효율이 떨어질 수 있음.

전역 교체를 사용하는 시스템에서는 프로세스가 사용할 수 있는 메모리 양이 외부 요인에 따라 달라질 수 있는 구조.

일부 시스템은 사용 가능한 메모리가 임계값 아래로 떨어지면 페이지 회수 정책을 실행.

 

페이지 회수는 가용 메모리가 부족할 때 커널이 페이지를 회수하여 가용 프레임 리스트를 채우는 과정.

Linux 같은 시스템에서는 가용 메모리가 낮아지면 

회수 프로세스가 실행되어 페이지를 스캔하고 회수 가능한 페이지를 확보하는 구조.

메모리가 극도로 부족하면 일부 프로세스는 메모리 부족 상태로 종료될 수 있음.

이러한 상황은 out-of-memory [OOM]으로 표현되는 상태.

 

비균등 메모리 접근

비균등 메모리 접근 NUMA는 메모리 접근 시간이 CPU와 메모리의 위치에 따라 달라지는 구조.

다중 처리기 시스템에서 각 CPU 또는 CPU 그룹은 자기와 가까운 지역 메모리에 더 빠르게 접근할 수 있음.

다른 CPU에 연결된 원격 메모리에 접근하면 시간이 더 오래 걸리는 특성.

NUMA 시스템에서는 단순히 빈 프레임을 할당하는 것만으로는 충분하지 않음.

프로세스가 실행되는 CPU에 가까운 메모리를 할당해야 성능 향상 가능.

스케줄러가 프로세스를 어느 CPU에서 실행할지 결정하고,

 메모리 관리자가 어느 노드의 프레임을 할당할지 결정하는 과정이 서로 연결되는 구조.

스레드가 다른 CPU로 자주 이동하면 메모리 지역성이 깨지고 원격 메모리 접근이 증가할 수 있는 문제.

Linux는 NUMA를 고려하기 위해 프로세스와 메모리의 위치 관계를 추적하고, 

가능한 한 지역 메모리를 사용하도록 하는 정책 사용.

Solaris도 CPU와 메모리의 지역성을 고려하기 위해 lgroup 같은 구조를 사용하는 방식.

 

스래싱

스래싱은 프로세스가 실제 실행보다 페이지 교체에 대부분의 시간을 소비하는 상태.

프로세스에 할당된 프레임이 너무 적으면 필요한 페이지 집합을 유지할 수 없어 계속 페이지 폴트를 발생시키는 상황.

페이지 폴트가 많아지면 운영체제는 페이지를 읽고 쓰는 데 시간을 쓰고, CPU는 대기하는 시간이 증가.

이 상태가 심해지면 CPU 이용률은 급격히 떨어지고 시스템 성능은 크게 저하됨.

스래싱이 발생하면 프로세스는 실행되지 않는 것이 아니라, 

실행을 위해 필요한 페이지를 계속 가져오느라 실질적인 진행을 거의 하지 못하는 상태.

 

스래싱의 원인

스래싱은 프로세스가 필요한 최소 프레임보다 적은 프레임을 받을 때 발생하기 쉬움.

운영체제가 CPU 이용률이 낮다고 판단하여 새로운 프로세스를 더 많이 메모리에 들이면 다중 프로그래밍 정도 증가.

하지만 이미 메모리가 부족한 상태에서 프로세스를 더 추가하면 

각 프로세스에 할당되는 프레임 수가 줄어들고 페이지 폴트가 증가.

페이지 폴트가 증가하면 프로세스들은 I/O 대기 상태가 되고, CPU 이용률은 더 낮아짐.

운영체제가 이를 다시 다중 프로그래밍 부족으로 오해하고 더 많은 프로세스를 추가하면 스래싱이 악화되는 순환 발생.

전역 페이지 교체 알고리즘은 한 프로세스의 페이지 폴트가 다른 프로세스의 페이지를 빼앗게 만들 수 있으므로 

스래싱을 확산시킬 수 있음.

지역 교체 알고리즘은 한 프로세스의 스래싱이 다른 프로세스에 직접 영향을 주는 것을 줄일 수 있지만, 

전체 메모리 부족 문제를 완전히 해결하지는 못하는 구조.

스래싱을 방지하려면 각 프로세스가 현재 사용하는 페이지 집합을 유지할 수 있을 만큼 충분한 프레임을 보장해야 하는 필요.

프로그램은 실행 중 특정 시점에 일부 페이지 집합만 집중적으로 참조하는 경향이 있으며, 

이를 지역성이라고 함.

지역성은 프로그램 구조와 자료구조에 의해 결정되는 경향.

프로세스가 한 지역성에서 다른 지역성으로 이동하면 필요한 페이지 집합도 바뀌는 구조.

운영체제는 프로세스의 지역성을 이해하고, 

해당 지역성에 필요한 페이지들이 메모리에 유지되도록 해야 페이지 폴트를 줄일 수 있음.

 

작업 집합 모델

작업 집합 모델은 

프로세스가 일정 시간 동안 실제로 사용하는 페이지들의 집합을 기준으로 메모리 요구량을 판단하는 방식.

작업 집합은 working set이라는 개념.

작업 집합 창은 최근 Δ개의 페이지 참조를 포함하는 구간.

특정 시점의 작업 집합은 최근 Δ개의 참조 안에 등장한 서로 다른 페이지들의 집합.

Δ가 너무 작으면 전체 지역성을 충분히 포함하지 못하는 문제.

Δ가 너무 크면 여러 지역성을 한꺼번에 포함하여 실제 필요한 것보다 큰 작업 집합을 계산할 수 있는 문제.

각 프로세스의 작업 집합 크기를 WSS라고 하면, 시스템 전체 수요 D는 모든 프로세스의 WSS 합.

D가 사용 가능한 프레임 수보다 작거나 같으면 각 프로세스의 작업 집합을 메모리에 유지할 수 있는 상태.

D가 사용 가능한 프레임 수보다 크면 일부 프로세스는 필요한 페이지를 유지할 수 없어 스래싱 가능.

운영체제는 

D가 너무 커지면 일부 프로세스를 중단하거나 스왑 아웃하여 나머지 프로세스의 작업 집합을 보장할 수 있음.

작업 집합 모델은 지역성을 기반으로 스래싱을 방지하려는 전략.

그러나 정확한 작업 집합을 계산하려면 각 페이지 참조를 추적해야 하므로 구현 비용이 큰 한계.

실제 시스템에서는 참조 비트와 주기적 인터럽트를 사용해 작업 집합을 근사적으로 추정 가능.

 

페이지 폴트 빈도

페이지 폴트 빈도 PFF는 프로세스의 페이지 폴트율을 관찰하여 프레임 수를 조절하는 방식.

페이지 폴트율이 너무 높으면 그 프로세스가 프레임을 더 필요로 한다는 의미.

반대로 너무 낮으면 그 프로세스가 필요 이상으로 많은 프레임을 갖고 있을 수 있다는 의미.

운영체제는 상한과 하한을 설정하고, 

페이지 폴트율이 상한을 넘으면 프레임을 추가하고 하한보다 낮으면 프레임을 회수할 수 있음.

페이지 폴트 빈도 방식은 작업 집합 모델보다 구현이 단순한 편.

그러나 전체 가용 프레임이 부족하면 프레임을 더 주고 싶어도 줄 수 없으므로, 일부 프로세스를 중단하거나 스왑 아웃해야 하는 상황 가능.

PFF는 스래싱을 감지하고 대응하는 실용적 기준으로 사용 가능.

 

현재 관행

현대 운영체제는 스래싱을 완전히 제거하기보다 여러 정책을 조합하여 완화하는 방향.

스래싱이 발생하면 시스템은 일부 프로세스의 실행을 줄이거나, 페이지 회수를 수행하거나, 프로세스를 종료할 수 있음.

대부분의 시스템은 전역 페이지 교체와 LRU 근사 알고리즘, 작업 집합 또는 페이지 폴트율 기반의 정책을 조합.

실제 시스템에서는 메모리 부족 상태를 단순한 알고리즘 하나로 해결하기 어렵기 때문에, 커널 회수 스레드, OOM 처리, 우선순위 기반 회수 같은 다양한 방법 사용.

 

메모리 압축

페이징의 대안 또는 보완책 중 하나가 메모리 압축.

메모리 압축은 수정된 프레임을 보조저장장치로 내보내는 대신 압축하여 메모리 안에 보관하는 방식.

이 방식은 페이지 아웃 I/O를 줄이고, 느린 저장장치 접근을 피할 수 있는 장점.

운영체제는 가용 프레임 리스트에서 프레임을 확보하려 할 때, 

수정된 프레임을 바로 디스크에 쓰지 않고 압축 리스트로 이동시킬 수 있음.

압축된 여러 프레임은 하나의 물리 프레임 안에 함께 저장될 수 있음.

압축된 페이지가 다시 필요해지면 운영체제는 해당 페이지를 압축 해제하여 메모리로 복원.

메모리 압축은 디스크 I/O보다 CPU 압축·해제 비용이 더 저렴할 때 효과적인 방식.

Android와 iOS 같은 모바일 운영체제는 스와핑 대신 메모리 압축을 활용할 수 있음.

Windows와 macOS도 메모리 압축을 사용하여 메모리 부족 상황에서 성능 저하를 줄이는 구조.

압축 알고리즘은 압축률과 압축 속도 사이의 절충을 가짐.

높은 압축률은 더 많은 메모리를 절약하지만 CPU 시간이 더 많이 들 수 있고, 

빠른 압축은 성능은 좋지만 절약되는 메모리가 적을 수 있음.

 

커널 메모리의 할당

사용자 프로세스에 대한 페이지 할당과 달리, 커널 메모리 할당은 별도의 요구 사항을 가짐.

커널은 다양한 크기의 자료구조를 자주 생성하고 제거하므로 효율적인 작은 단위 할당이 필요.

일부 커널 자료구조는 물리적으로 연속된 메모리가 필요할 수 있음.

장치 드라이버나 DMA 작업은 연속된 물리 프레임을 요구할 수 있으므로 일반 페이징 방식만으로는 충분하지 않은 경우 존재.

커널 메모리 할당은 내부 단편화를 줄이면서도 빠른 할당과 해제를 제공해야 하는 문제.

이 절에서는 버디 시스템과 슬랩 할당이라는 두 가지 커널 메모리 할당 방식 설명.

 

버디 시스템

버디 시스템은 물리적으로 연속된 고정 크기 세그먼트에서 메모리를 할당하는 방식.

메모리는 2의 거듭제곱 크기 단위로 분할됨.

요청 크기를 만족하는 가장 작은 2의 거듭제곱 블록을 찾아 할당하는 구조.

예를 들어 11KB 요청은 16KB 블록으로 할당되는 방식.

사용 가능한 큰 블록이 있으면 필요한 크기가 될 때까지 계속 절반으로 나눔.

블록이 해제되면 인접한 같은 크기의 버디 블록이 비어 있는지 확인하고, 가능하면 두 블록을 합쳐 더 큰 블록으로 만드는 병합 수행.

이 병합 과정은 coalescing이라고 부르는 개념.

버디 시스템의 장점은 인접한 빈 블록을 빠르게 병합하여 큰 연속 메모리를 만들 수 있다는 점.

단점은 요청 크기보다 큰 2의 거듭제곱 블록이 할당되므로 내부 단편화가 발생할 수 있다는 점.

 

슬랩 할당

슬랩 할당은 커널 객체를 효율적으로 할당하기 위한 메모리 관리 방식.

슬랩은 하나 또는 여러 개의 연속된 페이지로 구성되는 메모리 덩어리.

캐시는 특정 종류의 커널 객체를 저장하기 위한 공간.

예를 들어 프로세스 디스크립터, 파일 객체, 세마포어 같은 커널 자료구조마다 별도의 캐시가 존재할 수 있음.

각 캐시는 하나 이상의 슬랩으로 구성되고, 슬랩 안에는 같은 크기의 객체들이 배치되는 구조.

슬랩은 full, empty, partial의 세 상태를 가질 수 있음.

full 슬랩은 모든 객체가 사용 중인 상태.

empty 슬랩은 모든 객체가 free인 상태.

partial 슬랩은 일부 객체가 사용 중이고 일부 객체가 free인 상태.

객체 요청이 들어오면 슬랩 할당기는 먼저 partial 슬랩에서 free 객체를 찾아 할당하려는 구조.

partial 슬랩이 없으면 empty 슬랩에서 객체를 할당하고, 필요하면 새로운 슬랩을 생성.

슬랩 할당의 장점은 커널 객체를 매번 새로 초기화하지 않고 재사용할 수 있다는 점.

캐시에 이미 생성된 객체가 남아 있으므로 할당과 해제가 빠르고, 내부 단편화도 줄일 수 있음.

또한 같은 종류의 객체들이 같은 캐시에 모여 있어 하드웨어 캐시 효율도 향상 가능.

Solaris에서 처음 도입된 슬랩 할당은 이후 Linux에서도 다양한 형태로 사용.

Linux에는 SLAB, SLOB, SLUB 할당기가 있으며, SLUB는 현대 Linux에서 널리 사용되는 방식.

 

기타 고려 사항

페이징 시스템의 성능은 페이지 교체 알고리즘과 할당 정책만으로 결정되지 않음.

프리페이징, 페이지 크기, TLB reach, 역 페이지 테이블, 프로그램 구조, I/O 잠금 같은 요소도 성능에 중요한 영향.

이 절은 페이징 시스템 설계에서 추가로 고려해야 할 사항들에 대한 설명.

 

프리페이징

순수 요구 페이징에서는 프로세스가 시작될 때 많은 페이지 폴트가 발생할 수 있음.

프로세스가 처음 실행되거나 스왑 인될 때 작업 집합에 속한 페이지들이 아직 메모리에 없기 때문.

프리페이징은 앞으로 필요할 것으로 예상되는 여러 페이지를 미리 메모리에 가져오는 기법.

목적은 페이지 폴트 수를 줄이는 것.

예를 들어 프로세스가 스왑 아웃되기 전 작업 집합을 알고 있다면, 

다시 스왑 인할 때 그 작업 집합 페이지들을 한꺼번에 읽어 올 수 있음.

여러 페이지를 한 번에 읽으면 I/O 효율이 좋아질 수 있다는 장점.

하지만 미리 읽은 페이지가 실제로 사용되지 않으면 불필요한 I/O와 메모리 낭비가 되는 단점.

프리페이징이 효과적이려면 미리 가져온 페이지 중 상당수가 실제로 사용되어야 하는 조건.

사용될 가능성이 낮은 페이지를 많이 가져오면 요구 페이징보다 오히려 성능이 나빠질 수 있음.

 

페이지 크기

페이지 크기는 페이징 시스템 성능에 여러 방향으로 영향을 주는 중요한 요소.

크기가 작으면 내부 단편화가 줄고 필요한 데이터만 더 세밀하게 가져올 수 있어 메모리 낭비를 줄일 수 있음.

하지만 같은 가상 주소 공간을 표현하기 위해 더 많은 페이지 테이블 항목이 필요하므로, 

페이지 테이블이 커지고 주소 변환 오버헤드가 증가하는 단점.

반대로 크기가 크면 페이지 테이블 크기는 줄고 I/O 전송 효율도 높아질 수 있으며,

 한 번의 디스크 읽기로 더 많은 데이터를 가져올 수 있음.

그러나 큰 페이지는 내부 단편화를 증가시키고, 실제로 필요하지 않은 데이터를 함께 가져올 가능성을 높이는 단점.

작은 페이지는 지역성을 더 정밀하게 추적할 수 있으므로 불필요한 페이지 전송을 줄일 수 있음.

반면 큰 페이지는 페이지 폴트 횟수를 줄이고 TLB 효율을 높일 수 있음.

결국 페이지 크기가 너무 작으면 페이지 폴트가 자주 발생하고, 

너무 크면 불필요한 데이터 전송과 내부 단편화가 커지는 절충 관계.

현대 시스템은 보통 여러 페이지 크기를 지원하여 일반 페이지와 거대 페이지를 상황에 따라 사용할 수 있게 하는 구조.

 

TLB Reach

TLB 적중률은 전체 가상 메모리 참조 중 TLB에서 주소 변환을 수행할 수 있는 비율.

이 비율은 TLB 항목 수와 각 항목이 커버하는 페이지 크기에 영향을 받음.

TLB reach는 TLB에서 접근할 수 있는 전체 메모리 공간의 크기이며, TLB 항목 수와 페이지 크기를 곱한 값.

예를 들어 TLB 항목 수가 같다면 페이지 크기를 크게 할수록 TLB reach 증가.

TLB reach가 작으면 프로세스의 작업 집합이 TLB에 모두 들어가지 못해 TLB 미스가 증가할 수 있음.

TLB 미스가 많아지면 주소 변환 오버헤드가 커지고 성능 저하 발생.

TLB reach를 늘리는 방법 중 하나는 TLB 크기를 키우는 것.

하지만 TLB는 빠른 연관 메모리로 구현되므로 크기를 키우면 비용과 전력 소모가 증가하는 문제.

다른 방법은 페이지 크기를 키우거나 여러 페이지 크기를 지원하는 방식.

예를 들어 페이지 크기를 4KB에서 16KB로 늘리면 같은 TLB 항목 수에서도 TLB reach가 4배 증가.

Linux는 기본 페이지 크기 외에도 huge page를 제공하여 큰 메모리 영역을 적은 TLB 항목으로 매핑할 수 있는 구조.

ARMv8은 여러 페이지 크기와 region을 지원하며, 

연속 비트를 통해 여러 인접 블록을 하나의 TLB 항목처럼 취급할 수 있는 기능 제공.

여러 페이지 크기를 지원하려면 운영체제가 각 페이지 테이블 항목의 크기와 의미를 관리해야 하므로 복잡성 증가.

하지만 적절히 활용하면 TLB reach를 늘리고 성능 손해를 줄일 수 있는 장점.

 

역 페이지 테이블

역 페이지 테이블은 가상 주소 변환에 필요한 물리 메모리 양을 줄이기 위한 방식.

물리 프레임마다 하나의 항목만 가지므로, 프로세스별 전체 페이지 테이블보다 메모리 사용량이 적음.

그러나 각 프로세스의 전체 가상 주소 공간 정보를 유지하지 않으므로, 

참조된 페이지가 현재 메모리에 없을 때 문제가 커질 수 있음.

요구 페이징 시스템에서는 페이지가 메모리에 없더라도 그 페이지가 보조저장장치 어디에 있는지 알아야 하는 필요.

이를 위해 각 프로세스는 하나씩 확장된 페이지 테이블을 유지할 수 있음.

확장된 페이지 테이블은 페이지 폴트 시에만 참조되며,

 페이지가 메모리에 없는 경우 필요한 위치 정보를 제공하는 역할.

역 페이지 테이블은 일반 페이지 테이블보다 메모리 사용량을 줄일 수 있지만, 

페이지 폴트 처리와 주소 변환 구조가 더 복잡해질 수 있는 방식.

 

프로그램 구조

요구 페이징은 사용자에게 투명하게 설계되었지만, 프로그램 구조는 성능에 큰 영향을 줄 수 있음.

사용자나 컴파일러가 페이지 참조의 지역성을 고려하면 페이지 폴트 수를 크게 줄일 수 있음.

예를 들어 128 × 128 배열이 행 중심으로 저장되어 있고 페이지 크기가 128워드라면, 

행 방향 접근과 열 방향 접근은 매우 다른 페이지 폴트 수를 만들 수 있음.

행 중심 저장 배열을 열 방향으로 접근하면 각 접근이 다른 페이지를 건드릴 수 있어 페이지 폴트가 매우 많아짐.

반대로 행 방향으로 접근하면 한 페이지 안의 여러 원소를 연속적으로 사용하므로 페이지 폴트가 크게 감소.

자료구조와 프로그램 구조를 잘 선택하면 지역성을 향상시키고 작업 집합의 페이지 수를 줄일 수 있음.

스택은 한쪽 끝에서 집중적으로 접근되므로 지역성이 높은 자료구조.

해시 테이블은 참조가 넓게 분산되기 쉬워 지역성이 나쁠 수 있는 자료구조.

컴파일러와 로더도 페이징 성능에 영향을 줄 수 있음.

코드와 데이터를 분리하고, 자주 함께 호출되는 루틴을 같은 페이지에 배치하면 페이지 폴트 감소 가능.

서로 자주 호출하는 함수들을 같은 페이지에 배치하는 방식은 페이지 간 참조를 줄이는 효과.

반대로 거의 함께 사용되지 않는 루틴이 같은 페이지에 있으면 불필요한 코드가 함께 메모리에 올라올 수 있음.

이러한 문제는 bin-packing 문제와 유사하며, 특히 큰 페이지 크기를 사용하는 경우 중요.

 

 I/O 상호 잠금과 페이지 잠금

요구 페이징을 사용할 때 일부 페이지는 메모리에 반드시 고정되어야 하는 경우가 있음.

대표적인 예는 I/O 작업에 사용되는 버퍼.

I/O는 종종 별도의 I/O 처리기나 DMA 장치에 의해 수행되며, 장치는 메모리 안의 특정 버퍼 주소로 데이터를 전송.

어떤 프로세스가 I/O 요청을 하여 자신의 페이지가 I/O 버퍼로 사용되는 동안, 

그 페이지가 교체되어서는 안 되는 상황.

만약 페이지가 I/O 완료 전에 교체되면 장치는 잘못된 메모리 위치에 데이터를 쓰거나, 

다른 프로세스의 페이지를 손상시킬 수 있음.

이 문제를 해결하는 방법 중 하나는 I/O를 사용자 공간이 아닌 시스템 공간의 버퍼에서 수행하는 것.

운영체제가 사용자 페이지와 시스템 버퍼 사이에서 데이터를 복사하면, 

실제 장치 I/O는 고정된 커널 버퍼를 대상으로 수행 가능.

그러나 이 방식은 추가 복사 비용을 발생시키는 단점.

다른 해결책은 페이지를 메모리에 잠그는 것.

잠금 비트는 특정 페이지가 교체 대상에서 제외되어야 함을 나타내는 비트.

잠긴 페이지는 페이지 교체 알고리즘이 선택하지 않도록 보호되는 구조.

잠금 비트는 커널 페이지, 장치 I/O 버퍼, 데이터베이스 버퍼처럼 반드시 메모리에 있어야 하는 영역에 사용 가능.

페이지 고정은 pinning이라고도 부르며, 운영체제가 일부 페이지를 물리 메모리에 고정할 수 있게 하는 기능.

잠금 기능은 악용될 수 있으므로 사용자 프로세스가 임의로 많은 페이지를 잠그지 못하도록 제한이 필요.

페이지 잠금은 우선순위 역전과 유사한 문제도 만들 수 있음.

낮은 우선순위 프로세스가 잠근 페이지 때문에 높은 우선순위 프로세스가 필요한 프레임을 얻지 못하는 상황 가능.

잠금 비트는 한 번 설정되고 해제되지 않으면 가용 프레임을 영구적으로 줄일 수 있으므로 신중하게 관리해야 하는 정보.

Solaris는 잠금 힌트 기능을 제공하되, 

가용 페이지 풀이 너무 작거나 개별 프로세스가 지나치게 많은 페이지 잠금을 요청하면 이를 무시할 수 있는 정책 사용.

 

운영체제의 예

Linux

Linux는 요구 페이징을 사용하여 가상 메모리를 관리하고, 

copy-on-write를 통해 프로세스 생성 시 페이지 복사를 지연하는 방식.

페이지 교체는 LRU 근사 알고리즘과 전역 페이지 교체 정책을 조합하는 구조.

메모리를 관리하기 위해 active_list와 inactive_list라는 두 가지 페이지 리스트를 유지.

active_list에는 사용 중이고 최근 참조된 페이지가 들어가는 구조.

inactive_list에는 최근 참조되지 않았고 회수할 수 있는 페이지가 들어가는 구조.

각 페이지에는 참조 여부를 나타내는 accessed 비트가 존재.

페이지가 참조되면 accessed 비트가 설정되고, 페이지는 active_list 쪽으로 이동할 수 있음.

시간이 지나며 참조되지 않는 페이지는 active_list의 뒤쪽으로 이동하고, 결국 inactive_list로 내려갈 수 있음.

inactive_list의 페이지가 다시 참조되면 active_list로 되돌아가는 구조.

두 리스트는 상대적 균형을 유지해야 하며,

active_list가 inactive_list보다 훨씬 커지면 일부 페이지가 inactive_list로 이동하여 회수 대상이 됨.

Linux 커널은 주기적으로 또는 메모리 부족 시 kswapd를 통해 페이지 회수를 수행.

kswapd는 inactive_list에서 페이지를 검사하고 가용 프레임 리스트로 회수하는 역할.

Linux는 클러스터링을 사용하여 페이지 폴트가 발생한 페이지뿐 아니라 인접 페이지도 함께 읽어 들일 수 있음.

클러스터링은 메모리 참조 지역성을 활용하여 이후 페이지 폴트를 줄이려는 전략.

데이터 페이지의 경우 클러스터는 여러 페이지로 구성될 수 있고, 다른 페이지 폴트의 클러스터 크기는 더 작을 수 있는 구조.

 

Windows

Windows 10은 Intel IA-32, x86-64, ARM 아키텍처에서 실행되는 운영체제.

32비트 시스템에서는 기본적으로 2GB 사용자 주소 공간과 2GB 커널 주소 공간을 사용하며, 

설정에 따라 사용자 주소 공간을 3GB까지 확장 가능.

32비트 시스템은 4GB 물리 메모리를 지원하는 구조.

64비트 시스템에서 Windows 10은 매우 큰 가상 주소 공간과 물리 메모리를 지원.

Windows 10은 

공유 라이브러리, 요구 페이징, copy-on-write, 페이징, 메모리 압축 등 대부분의 가상 메모리 기능을 구현.

가상 메모리 관리는 클러스터링이 가미된 요구 페이징을 바탕으로 이루어지는 방식.

Windows 가상 메모리 관리의 주요 단위는 작업 집합.

작업 집합은 프로세스가 현재 메모리에 유지하고 있는 페이지들의 집합.

Windows는 프로세스 생성 시 최소 작업 집합과 최대 작업 집합을 지정.

작업 집합 최소값은 프로세스가 메모리에 유지하는 것이 보장된 최소 페이지 수.

메모리가 충분하면 프로세스는 작업 집합 최대값까지 페이지를 가질 수 있음.

프로세스가 hard working-set limits를 갖지 않으면 작업 집합이 상황에 따라 유동적으로 조정 가능.

사용 가능한 메모리가 충분하면 프로세스 작업 집합은 증가할 수 있고, 메모리가 부족하면 감소할 수 있음.

Windows는 지역 페이지 교체와 전역 페이지 교체를 조합하여 LRU 근사 클록 알고리즘을 사용.

가상 메모리 관리자는 가용 페이지 프레임 리스트를 유지하고, 메모리가 충분한지 감시하는 임계값을 사용.

가용 메모리가 임계값보다 낮아지면 자동 작업 집합 트리밍을 수행.

자동 작업 집합 트리밍은 여러 프로세스의 작업 집합에서 페이지를 제거하여 가용 메모리를 확보하는 과정.

프로세스의 작업 집합이 최소값보다 큰 경우, 사용하지 않은 페이지들이 작업 집합에서 제거되어 가용 메모리로 이동 가능.

유휴 상태이거나 우선순위가 낮은 프로세스의 페이지가 먼저 제거될 가능성.

Windows는 충분한 메모리가 확보될 때까지 작업 집합 트리밍을 계속 수행할 수 있음.

 

Solaris

Solaris는 가용 페이지 리스트를 유지하고, 페이지 폴트 발생 시 이 리스트에서 페이지를 확보해 할당하는 구조.

커널은 항상 충분한 가용 공간을 확보하고 있어야 하는 정책.

가용 페이지 리스트에는 lotsfree라는 파라미터가 있으며, paging을 시작하는 임계값 역할.

lotsfree는 보통 물리 메모리 크기의 일정 비율로 설정되는 값.

커널은 가용 공간의 크기가 lotsfree보다 작아지면 pageout 프로세스를 실행.

pageout 프로세스는 페이지를 스캔하며 회수 가능한 페이지를 찾는 역할.

Solaris의 pageout 알고리즘은 수정된 클록 알고리즘과 유사한 방식.

pageout은 모든 페이지를 두 번 도는 것처럼 동작하며, 첫 번째 바늘은 페이지의 참조 비트를 0으로 설정.

일정 시간 뒤 두 번째 바늘은 참조 비트가 여전히 0인 페이지를 회수 가능 페이지로 판단.

수정된 페이지는 보조저장장치에 기록되고, 깨끗한 페이지는 가용 프레임 리스트에 추가 가능.

다른 프로세스에서 해당 페이지를 다시 참조하면 가용 리스트에서 제거되어 다시 사용되는 구조.

pageout 알고리즘은 scanrate라는 페이지 검사 속도를 조절.

scanrate는 초당 검사하는 페이지 수.

가용 메모리가 충분하면 scanrate는 slowscan에 가까운 낮은 값.

가용 메모리가 부족해지면 scanrate는 fastscan에 가까운 높은 값으로 증가.

 

desfree는 시스템이 유지하려는 최소 가용 메모리의 양.

가용 공간이 desfree보다 적으면 pageout은 더 빠르게 실행되어 가용 메모리를 확보하려는 구조.

30초 동안 desfree를 유지하지 못하면 커널은 프로세스 스와핑을 시작할 수 있음.

Solaris는 일반적으로 오래 idle 상태였던 프로세스부터 스왑 대상으로 선택.

커널이 minfree 이상의 가용 공간을 확보하지 못하면, 새 페이지 요청이 있을 때마다 pageout 프로세스를 실행시킬 수 있음.

Solaris의 페이지 스캐너는 여러 프로세스가 공유하는 라이브러리 페이지는 건너뛸 수 있음.

또한 프로세스에 할당된 페이지와 일반 데이터 파일에 할당된 페이지를 구분하여 관리.

프로세스 페이지 중 중요한 페이지는 우선순위 페이징으로 다뤄질 수 있는 구조.