10.9.1 Prepaging
순수 요구 페이징의 명백한 특성 중 하나는 프로세스가 시작될 때 발생하는 페이지 폴트가 많다는 것이다. 이러한 상황은 초기 지역성을 메모리에 저장하려고 할 때 발생한다. prepaging은 이러한 높은 수준의 초기 페이징을 방지하기 위한 시도이다. 전략은 필요한 페이지의 일부 또는 전부를 한 번에 메모리에 저장하는 것이다.
예를 들어, working-set 모델을 사용하는 시스템에서 각 프로세스와 함께 working-set에 있는 페이지 목록을 보관할 수 있다. 사용 가능한 프레임이 부족하여 프로세스를 일시 중단해야 하는 경우, 해당 프로세스의 working set을 기억한다. 프로세스가 재개되어야 하는 경우(I/O가 완료되었거나 충분한 여유 프레임이 생겨서), 프로세스를 다시 시작하기 전에 자동으로 전체 working set을 메모리로 가져온다.
프리페이징은 경우에 따라 이점을 제공할 수 있다. 문제는 프리페이징 사용 비용이 해당 페이지 폴트 처리 비용보다 적은지 여부이다. 프리페이징을 통해 메모리로 다시 가져온 페이지 중 상당수가 사용되지 않을 가능성이 높다.
s개의 페이지가 프리페이징되었고, 이 중 일부 α가 실제로 사용된다고 가정한다 (0≤α≤1). 문제는 만큼 절약된 페이지 폴트 비용이 만큼 불필요한 페이지를 프리페이징하는 비용보다 큰지 작은지이다. α가 0에 가까우면 프리페이징이 실패하고, α가 1에 가까우면 프리페이징이 성공한다.
실행 가능한 프로그램을 미리 페이징하는 것은 어떤 페이지를 가져와야 할지 명확하지 않을 수 있으므로 어려울 수 있다. 파일은 순차적으로 액세스되는 경우가 많으므로 파일을 미리 페이징하는 것이 더 예측 가능할 수 있다. Linux readahead() 시스템 콜은 파일의 내용을 메모리로 미리 가져와서 이후에 해당 파일에 액세스하면 메인메모리에서 수행된다.
10.9.2 Page Size
기존 컴퓨터의 운영 체제 설계자는 페이지 크기를 자유롭게 선택할 수 있는 경우가 거의 없다. 그러나 새 컴퓨터를 설계할 때는 최적의 페이지 크기를 결정해야 한다. 최적의 페이지 크기는 단 하나만 있는 것이 아니다. 다양한 크기를 지원하는 여러 요소가 존재한다. 페이지 크기는 항상 2의 거듭제곱이며, 일반적으로 4,096(212) 바이트에서 4,184,304(222)바이트까지이다.
페이지 크기는 선택의 한 가지 고려 사항은 페이지 테이블의 크기이다. 주어진 가상 메모리 공간에서 페이지 크기를 줄이면 페이지 수가 증가하고, 따라서 페이지 테이블의 크기도 증가한다. 예를 들어, 4MB(222)의 가상 메모리에서는 1,024바이트 크기의 페이지가 4,096개 있지만, 8,192바이트 크기의 페이지는 512개뿐이다. 각 활성 프로세스는 자체 페이지 테이블 사본을 가져야 하므로 큰 페이지 크기가 바람직하다.
하지만 페이지 크기가 작을수록, 메모리 활용도가 높아진다. 프로세스에서 000000번 위치부터 필요한 만큼의 메모리가 할당되면, 프로세스가 페이지 경계에서 정확히 끝나지 않을 가능성이 높다. 따라서 할당 단위가 페이지이므로 최종 페이지의 일부는 할당되어야 하지만, 사용되지 않아 내부 단편화가 발생한다. 프로세스 크기와 페이지 크기가 서로 독립적이라고 가정할 때, 각 프로세스의 최종 페이지 중 평균적으로 절반이 낭비될 것으로 예상할 수 있다. 이 손실은 512바이트 페이지에서는 256바이트에 불과하지만, 8,192바이트 페이지에서는 4,096바이트이다. 따라서 내부 단편화를 최소화하려면 작은 페이지 크기가 필요하다.
또 다른 문제는 페이지를 읽거나 쓰는 데 필요한 시간이다. 섹션 11.1에서 볼 수 있듯이 저장 장치가 HDD인 경우 I/O시간은 탐색, 대기 시간 및 전송 시간으로 구성된다. 전송 시간은 전송된 양(즉, 페이지 크기)에 비례한다. 이는 작은 페이지 크기를 주장하는 것처럼 보이지만, 대기 시간과 탐색 시간은 일반적으로 전송시간을 왜소하게 만든다. 초당 50MB의 전송속도에서 512바이트를 전송하는 데 0.01밀리초 걸린다. 그러나 대기 시간은 약 3밀리초이고 탐색 시간은 5밀리초이다. 따라서 총 I/O시간(8.01밀리초) 중 약 0.1%만 실제 전송에 기인한다. 페이지 크기를 두 배로 늘리면 I/O 시간은 8.02밀리초로 늘어난다. 1,024바이트의 단일 페이지를 읽는 데는 8.02밀리초가 걸리지만, 512바이트의 두 페이지를 읽는 데는 16.02밀리초가 걸린다. 따라서 I/O시간을 최소화하려면 더 큰 페이지 크기가 필요하다.
하지만 페이지 크기가 작을수록, 지역성이 향상되므로 전체 I/O가 감소해야 한다. 페이지 크기가 작을 수록 각 페이지가 프로그램 지역성을 더 정확하게 일치시킬 수 있다. 예를 들어, 크기가 200KB인 프로세스가 있고 실행에 실제로 사용되는 영역이 절반(100KB)이라고 가정하면, 큰 페이지가 하나뿐이라면 전체 페이지, 즉 총 200KB를 가져와야 한다. 반면 1바이트 크기의 페이지가 있다면 실제로 사용되는 100KB만 가져와서 100KB만 전송되고 할당될 수 있다. 따라서 페이지 크기가 작을수록 해상도가 향상되어 실제로 필요한 메모리만 분리할 수 있다. 페이지 크기가 커지면 필요한 것뿐만 아니라 필요 여부에 관계없이 페이지에 있는 다른 모든 것을 할당하고 전송해야 한다. 따라서 페이지 크기가 작을수록 I/O와 할당된 총 메모리가 줄어든다.
하지만 페이지 크기가 1바이트일 때 각 바이트마다 페이지 폴트가 발생한다. 200KB 프로세스가 해당 메모리의 절반만 사용한다면 페이지 크기가 200KB일 때는 페이지 폴트가 한 번만 발생하지만, 페이지 크기가 1바이트일 때는 페이지 폴트가 102,400번 발생한다. 각 페이지 폴트는 인터럽트 처리, 레지스터 저장, 페이지 교체, 페이징 장치 대기열 생성, 테이블 업데이트 등에 필요한 많은 오버헤드를 발생시킨다. 페이지 폴트 발생 횟수를 최소화하려면 큰 페이지 크기가 필요하다.
~참고~
다른 요소들(예: 페이지 크기과 페이징 장치의 sector(하드디스크, 플로피 디스크 등의 자기 디스크 저장 공간을 나누는 최소 단위) 크기 간의 관계)도 고려해야 한다. 이 문제에 대한 완벽한 답은 없다. 앞서 살펴본 바와 같이, 내부 단편화, 지역성 같은 일부 요소는 작은 페이지 크기를 권장하는 반면, 테이블 크기, I/O시간 같은 다른 요소는 큰 페이지 크기를 권장한다. 그럼에도 불구하고, 모바일 시스템에서도 역사적으로 페이지 크기가 커지는 추세이다. 실제로 Operating System Concepts 초판(1983)에서는 페이지 크기의 상한으로 4,096바이트를 사용했으며, 이 값은 1990년에 가장 일반적인 페이지 크기였다. 최신 시스템에서는 훨씬 더 큰 페이지 크기를 사용할 수 있다.
10.9.3 TLB Reach
9장에서 TLB의 적중률을 소개했다.
TLB(Translation Lookaside Buffer)란?
- 가상 주소를 물리 주소로 변환하는 속도를 높이기 위해 사용되는 캐시 메모리.
- 최근에 사용된 가상 주소와 그에 해당하는 물리 주소 정보를 저장하여, 메모리 접근 횟수를 줄이고 시스템 성능을 향상시키는 데 도움을 줌.
TLB의 적중률은 페이지 테이블이 아닌 TLB에서 확인되는 가장 주소 변환의 비율을 나타낸다. 적중률은 TLB의 엔트리 수와 관련이 있으며, 적중률을 높이는 방법은 엔트리 수를 늘리는 것이다. 그러나 TLB를 구성하는 데 사용되는 연관 메모리는 비용이 많이 들고 전력 소모도 많기 때문에 쉬운일이 아니다.
적중률과 관련된 유사한 지표는 TLB 도달 범위이다. TLB 도달 범위는 TLB에서 접근 가능한 메모리 양을 나타내며, 항목 수에 페이지 크기를 곱한 값이다. 이상적으로 프로세스의 작업 집합은 TLB에 저장된다. 그렇지 않은 경우, 프로세스는 TLB가 아닌 페이지 테이블에서 메모리 참조를 확인하는 데 상당한 시간을 소비하게 된다. TLB의 항목 수를 두 배로 늘리면 TLB 도달범위도 두 배로 늘어난다. 그러나 일부 메모리 집약적인 애플리케이션에서는 working set을 저장하기에 여전히 부족할 수 있다.
TLB 도달 범위를 늘리는 또 다른 방법은 페이지 크기를 늘리거나 여러 페이지 크기를 제공하는 것이다. 페이지 크기를 4KB에서 16KB로 늘리면 TLB 도달 범위가 4배로 늘어난다. 그러나 이렇게 하면 그렇게 큰 페이지 크기가 필요하지 않은 일부 애플리케이션의 단편화가 증가할 수 있다. 또는 대부분의 아키텍처는 두 개 이상의 페이지 크기를 지원하며, 운영 체제는 이 지원을 활용하도록 구성할 수 있다. 예를 들어, Linux 시스템의 기본 페이지 크기는 4KB이다. 하지만 Linux는 더 큰 페이지(예: 2MB)를 사용할 수 있는 물리적 메모리 영역을 지정하는 huge page(거대 페이지)도 제공한다.
섹션 9.7에서 언급했듯이 ARMv8 아키텍처는 다양한 크기의 페이지와 영역을 지원한다. 또한, ARMv8의 각 TLB 엔트리는 연속 비트를 포함한다. 특정 TLB 엔트리에 대해 이 비트가 설정되면 해당 엔트리는 연속된(인접한) 메모리 블록을 매핑한다. 연속 블록의 세 가지 가능한 배열을 단일 TLB 항목에 매핑하여 TLB 도달 범위를 늘릴 수 있다:
1. 16 × 4 KB 인접 블록으로 구정된 64KB TLB 항목
2. 32 × 32 KB 인접 블록으로 구성된 1GB TLB 항목
3. 32 × 64 KB 인접 블록 또는 128 × 16 KB 인접 블록으로 구성된 2MB TLB 항목
여러 페이지 크기를 지원하려면 하드췌어가 아닌 운영체제에서 TLB를 관리해야 할 수 있다. 예를 들어, TLB 항목의 필드 중 하나는 해당 항목에 해당하는 페이지 프레임의 크기를 나타내야한다. 또는 ARM 아키텍처의 경우, 항목이 연속된 메모리 블록을 참조함을 나타내야한다. 하드웨어가 아닌 소프트웨어로 TLB를 관리하면 성능이 저하될 수 있다. 그러나 적중률과 TLB 도달 범위가 향상되러 성능 저하를 상쇄할 수 있다.
ARM(Advanced RISC Machine)이란?
- RISC(Reduced Instruction Set Computing) 기반의 프로세서 아키텍처로, 컴퓨터의 CPU를 설계하기 위한 일종의 표준 규격이나 설계도.
- ARMv8은 ARM이 2011년에 발표한 64비트 아키텍처로, AArch64와 AArch32 두 가지 실행 상태를 지원.
10.9.4 Inverted Page Tables
섹션 9.4.3에서 역 페이지 테이블 개념을 소개했다. 이러한 형태의 페이지 관리의 목적은 가상 주소에서 물리 주소로의 변환을 추적하는 데 필요한 물리 메모리의 양을 줄이는 것이다. 물리 메모리 페이지당 하나의 엔트리를 갖는 테이블을 생성하여 이러한 절약을 달성했다. 각 엔트리는 <프로세스 ID, 페이지 번호> 쌍으로 인덱싱된다.
역 페이지 테이블은 각 물리적 프레임에 어떤 가상 메모리 페이지가 저장되어 있는지에 대한 정보를 유지하므로, 이 정보를 저장하는 데 필요한 물리적 메모리의 양을 줄인다. 그러나 역 페이지 테이블은 더 이상 프로세스의 논리적 주소 공간에 대한 완전한 정보를 포함하지 않으며, 참조되는 페이지가 현재 메모리에 없는 경우 이 정보가 필요하다. 요구 페이징은 페이지 폴트를 처리하기 위해 이 정보를 필요로 한다. 이 정보를 사용하려면 프로세스당 하나씩 외부 페이지 테이블을 유지해야 한다. 이러한 각 테이블은 기존의 프로세스별 페이지 테이블과 유사하며 각 가상 페이지의 위치에 대한 정보를 포함한다.
하지만 외부 페이지 테이블이 역 페이지 테이블의 효용성을 무효화할까? 이러한 테이블은 페이지 폴트 발생 시에만 참조되므로 빠르게 사용할 수 있을 필요가 없다. 대신, 필요에 따라 자체적으로 메모리에 페이지 인/아웃된다. 안타깝게도, 페이지 폴트가 발생하면 가상 메모리 관리자가 백업 저장소에서 가상 페이지를 찾는 데 필요한 외부 페이지 테이블을 페이지 인할 때 또 다른 페이지 폴트를 발생시킬 수 있다. 이러한 특수한 경우는 커널에서 신중하게 처리해야 하며 페이지 조회 처리에 지연이 발생한다.
10.9.5 Program Structure
요구 페이징은 사용자 프로그램에 투명하게 설계되었다. 많은 경우 사용자는 메모리의 페이징 특성을 전혀 인지하지 못한다. 그러나 다른 경우에는 사용자(또는 컴파일러)가 기본 요구 페이징을 인지할 경우 시스템 성능을 향상시킬 수 있다.
페이지 크기가 128단어라고 가정하고, 128x128 배열의 각 요소를 0으로 초기화 하는 C 프로그램을 생각해 보면, 다음은 일반적인 코드이다.
배열은 행 우선으로 저장된다. 즉, 배열은 로 저장된다. 128개의 워드로 구성된 페이지의 경우, 각 행은 한 페이지를 차지한다. 따라서 위 코드는 각 페이지에서 한 워드를 0으로 처리하고, 그 후 각 페이지에서 다른 워드를 0으로 처리하는 식으로 진행된다. 운영 체제가 전체 프로그램에 128개 미만의 프레임을 할당하면 실행 결과는 128x128=16,384개의 페이지 폴트가 발생한다.
대조적으로, 코드를 다음과 같이 변경한다고 가정해 보겠다.
이 코드는 다음 페이지를 시작하기 전에 한 페이지의 모든 단어를 0으로 만들어 페이지 폴트 수를 128개로 줄인다.
첫 번째 코드 (j 외곽 / i 내곽) 에서는
- 배열이 행(row) 단위로 메모리에 연속 저장(row‑major)이므로
- data[i][j] 에서 i가 변할 때마다 (즉, 같은 j에 대해 다음 행으로 넘어갈 때마다) 다음 페이지로 접근하게 됩니다.
- 한 행(128단어)이 한 페이지 크기이므로, 128개의 서로 다른 페이지를 돌아가며 한 단어씩 0을 쓰게 되고
- 페이지당 1번만 자유 프레임에 올라가 있다가 내려오면(프레임 수가 부족하면 스왑 아웃) 매번 페이지 폴트가 발생 → 128×128 = 16,384번
두 번째 코드 (i 외곽 / j 내곽) 에서는
- i가 고정된 상태에서 j가 0→127로 증가하므로
- data[i][0]부터 data[i][127]까지 같은 행(= 같은 페이지) 내 연속 주소를 쭉 접근합니다.
- 따라서 한 페이지에 들어 있는 128단어를 한꺼번에 모두 0으로 채우고 나서야 다음 페이지로 이동 → 페이지당 1번씩, 총 128번만 페이지 폴트
데이터 구조와 프로그래밍 구조를 신중하게 선택하면 지역성이 향상되어 페이지 폴트 발생률과 working set의 페이지 수를 줄일 수 있다. 예를 들어, 스택은 항상 최상위 메모리로 접근하기 때문에 지역성이 좋다. 반면 해시 테이블은 참조를 분산시키도촉 설계되어 지역성이 떨어진다. 물론 참조 지역성은 데이터 구조 사용의 효율성을 측정하는 한 가지 지표일 뿐이다. 검색 속도, 총 메모리 참조 횟수, 그리고 접촉된 총 페이지 수 등도 지역성에 중요한 요소이다.
나중에 컴파일러와 로더는 페이징에 상당한 영향을 미칠 수 있다. 코드와 데이터를 분리하고 재진입 가능한 코드를 생성하면 코드 페이지가 읽기 전용이 되어 절대 수정되지 않는다. clean 페이지는 교체하기 위해 페이지 아웃할 필요가 없다. 로더는 페이지 경계를 넘나드는 루틴을 배치하지 않고도 각 루틴을 완전히 한 페이지에 유지할 수 있다. 여러 번 서로를 호출하는 루틴은 같은 페이지에 묶을 수 있다. 이 패키징은 운영 연구의 빈 패킹 문제의 변형이다. 가변 크기의 로드 세그먼트를 고정 크기의 페이지에 패킹하여 페이지 간 참조를 최소화하는 방식이다. 이러한 접근 방식은 페이지 크기가 클 때 유용하다.
빈 패킹(Bin Packing)이란?
특정 용량의 빈(Bin)에 여러 개의 물건들을 최대한 효율적으로 담아내는 문제, 즉, 최소한의 빈을 사용하여 모든 물건을 담는 것을 목표로 하는 것
10.9.6 I/O Interlock and Page Locking
요구 페이징을 사용할 때, 일부 페이지를 메모리에 잠그도록 허용해야 할 때가 있다. 이러한 상황 중 하나는 사용자(가상) 메모리에 대한 I/O가 수행될 때 발생한다. I/O는 종종 별도의 I/O 프로세서에 의해 구현된다. 예를 들어, USB 저장 장치용 컨트롤러에는 일반적으로 전송할 바이트 수와 버퍼용 메모리 주소가 주어진다(그림 10.28).
전송이 완료되면 cpu가 인터럽트된다.
다음과 같은 일련의 이벤트가 발생하지 않도록 해야한다. 프로세스가 I/O요청을 보내고 해당 I/O창지의 큐에 들어간다. 그 사이에 cpu는 다른 프로세스에게 할당된다. 이러한 프로세스들은 페이지 폴트를 발생시키고, 그 중 하나가 전역 교체 알고리즘을 사용하여 대기 중인 프로세스의 메모리 버러가 포함된 페이지를 교체한다. 페이지는 페이지 아웃된다. 얼마 후, I/O요청이 장치 큐의 맨 앞으로 이동하면 지정된 주소로 I/O가 발생한다. 그러나 이 프레임은 이제 다른 프로세스에 속한 다른 페이지에 사용되고 있다.
이 문제에는 두 가지 일반적인 해결첵이 있다. 한 가지 해결책은 사용자 메모리에 I/O를 실행하지 않는 것이다. 대신, 데이터는 항상 시스템 메모리와 사용자 메모리간에 복사된다. I/O는 시스템 메모리와 I/O장치 사이에서만 발생한다. 따라서 테이프에 블록을 쓰려면 먼저 블록을 시스템 메모리에 복사한 다음 테이프에 써야한다. 이러한 추가 복사는 감당할 수 없을 정도로 높은 오버헤드를 초래할 수 있다.
자기 테이프 드라이브(magnetic tape drive): 컴퓨터의 순차 접근식 보조 기억 장치
또 다른 해결책은 페이지가 메모리에 잠기도록 허용하는 것이다. 이 경우, 모든 프레임에 잠금 비트가 할당된다. 프레임이 잠기면 교체 대상으로 선택할 수 없다. 이 방법에서는 블록을 디스크에 쓰기 위해 해당 블록이 포함된 페이지를 메모리에 잠근다. 그러면 시스템은 평소처럼 계속 작동할 수 있다. 잠긴 페이지는 교체할 수 없다. I/O가 완료되면 페이지의 잠금이 해제된다.
잠금 비트는 다양한 상황에서 사용된다. 운영 체제 커널의 일부 또는 전체가 메모리에 잠기는 경우가 많다. 많은 운영체제는 커널이나 메모리 관리를 수행하는 모듈을 포함한 특정 커널 모듈에 의해 발생하는 페이지 폴트를 허용하지 않는다. 사용자 프로세스도 페이지를 메모리에 잠가야 할 수 있다. 데이터베이스 프로세스는 데이터를 어떻게 사용할지 가장 잘 알고 있기 때문에 보조 스토리지와 메모리 간에 블록을 이동하는 등 메모리 덩어리를 관리할 수 있다. 이러한 메모리 페이지 pinning(고정)은 매우 일반적이며, 대부분의 운영 체제에는 애플리케이션이 논리 주소 공간의 특정 영역을 고정하도록 요청할 수 있는 시스템 콜이 있다. 이 기능은 악용될 수 있으며 메모리 관리 알고리즘에 부담을 줄 수 있다. 따라서 애플리케이션은 이러한 요청을 수행하기 위해 특별한 권한이 필요한 경우가 많다.
잠금 비트의 또 다른 용도는 일반적인 페이지 교체와 관련이 있다. 다음과 같은 일련의 이벤트를 생각해보면: 우선순위가 낮은 프로세스에 오류가 발생한다. 교체 프레임을 선택하고, 페이징 시스템은 필요한 페이지를 메모리로 읽어온다. 계속 진행할 준비가 된 낮은 우선순위 프로세스는 준비 큐에 들어가 cpu를 기다린다. 이 프로세스는 우선순위가 낮기 때문에 cpu 스케줄러에 의해 잠시 선택되지 않을 수 있다. 낮은 우선순위 프로세스가 대기하는 동안 높은 우선순위 프로세스가 장애를 일으킨다. 대체 페이지를 찾던 페이징 시스템은 메모리에 있지만 참조되거나 수정되지 않은 페이지를 발견한다. 바로 낮은 우선 순위 프로세스가 방근 가져운 페이지이다. 이 페이지는 완벽한 대체 페이지처럼 보인다. clean해서 따로 쓸 필요도 없고, 오랫동안 사용되지도 않은 것 같다.
우선순위가 높은 프로세스가 우선순위가 낮은 프로세스를 대체할 수 있어야 하는지 여부는 정책적 결정이다. 결국, 우선순위가 높은 프로세스의 이익을 위해 우선순위가 낮은 프로세스의 진행을 지연시키는 것일 뿐이다. 하지만 우선순위가 낮은 프로세스 페이지를 가져오는 데 들인 노력은 헛수고일 뿐이다. 해로 가져온 페이지가 한 번 사용될 수 있을 때까지 교체되는 것을 방지하기로 결정한 경우 잠금 비트를 사용하여 이 메커니즘을 구현할 수 있다. 교체할 페이지가 선택되면 해당 페이지의 잠금 비트가 켜진다. 오류가 발생한 픠로세스가 다시 전송될 때까지 이 비트는 켜진 상태를 유지한다.
잠금 비트를 사용하는 것은 위험할 수 있다: 잠금 비트가 켜졌다가 꺼지지 않을ㅇ 수 있다. 이러한 상황이 발생하면(예: 운영체제 버그로 인해) 잠긴 프레임을 사용할 수 없게된다. 예를 들어, Solaris는 잠금 힌트를 허용하지만, 자유 프레임 풀이 너무 작아지거나 개별 프로세스가 메모리에 너무 많은 페이지를 잠그도록 요청하는 경우 이러한 힌트를 무시해도 된다.
