• 운영체제 10장 - 가상 메모리 (1) - 기본
• 운영체제 10장 - 가상 메모리 (2) - 요구 페이징, copy-on-write
• 운영체제 10장 - 가상 메모리 (3) - 메모리 교체 알고리즘

에서 이어지는 글입니다.

가상 메모리

10.5 프레임의 할당

제한된 가용 프레임을 어떻게 프레임에 할당해줄 것인가. 각 프로세스는 몇 프레임씩을 할당 받아야 하는가.

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

프레임 수가 줄어들면 페이지 폴트율은 증가하고 프로세스 실행은 늦어지게 된다. 명령어 수행이 완료되기 전에 페이지 폴트가 발생하면 그 명령어는 재실행 되어야 한다. 따라서 하나의 명령어가 참조하는 모든 페이지는 동시에 메모리에 올라와 있어야 그 명령어의 수행이 끝날 수 있게 된다.

최소 프레임 수는 컴퓨터 아키텍처에 의해 정의된다. 최소 프레임 수는 아키텍처에 의해 정의되는 반면, 최대 수는 사용 가능한 물리 메모리 양에 의해 정의된다.

아키텍처의 명령어 집합에서 가장 많은 바이트가 필요한 명령어는 무엇인가.

10.5.2 할당 알고리즘

• 균등 할당 : 전체 가용 프레임 수 / 프로세스 수
• 비례 할당 : 프로세스의 크기 비율에 맞추어 할당

* 다중 프로그래밍 정도가 높아지면 각 프로세스는 프레임을 덜 받게 되고, 다중 프로그래밍 정도가 낮아지면 각 프로세스는 프레임을 더 넉넉히 받게 된다. (다중 프로그래밍 정도가 높아진다는 것은 더 많은 프로세스를 사용할 수 있다는 것이므로. 어떻게 보면 당연한 설명임)
* 이 두가지 방법은 우선순위를 고려하지 않음.

10.5.3 전역 대 지역 할당

• 전역 교체
  • 프로세스가 교체할 프레임을 다른 프로세스에 속한 프레임을 포한한 모든 프레임을 대상으로 함.
  • 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스를 희생시켜 더 많은 프레임을 할당받을 수 있음.
  • 다른 프로세스의 상황에 따라 실행 시간이 달라질 수 있음.
• 지역 교체
  • 프로세스가 자기에게 할당된 프레임 중에서만 교체될 희생자를 선택.
  • 각 프로세스에 할당된 프레임의 수는 바뀌지 않음.
  • 자기 자신의 페이징 형태에 따라서만 영향을 받음.
  • 메모리가 낭비될 수 있다.

* 일반적으로 전역 교체가 지역 교체 알고리즘보다 더 좋은 시스템 성능을 보여주기 때문에 더 많이 사용된다.

전역 페이지 교체 정책

가용 메모리 양을 최소 임계값 이상으로 유지. (항상 충분한 여유 메모리가 남아있도록 하기위해 노력함)
임계값 아래로 떨어지면 시스템의 모든 프로세스에서 페이지를 회수하기 시작하는 커널 루틴(리퍼 커널 루틴)이 촉발.

리퍼 커널 루틴은 일반적으로 LRU 근사 형태의 알고리즘(2차 기회 알고리즘)을 사용함.
하지만 그래도 최소 임계값 이상으로 유지할 수 없는 경우에는 더 순수한 FIFO를 사용함.

Linux의 경우 사용 가능한 메모리양이 매우 낮은 수준으로 떨어지면 OOM 킬러 라고하는 루틴이 종료할 프로세스를 선택하여 메모리를 회수한다.

10.5.4 비균등 메모리 접근

모든 메인 메모리는 동등하게 또는 적어도 동일하게 접근된다는 것을 가정해왔다. 여러개의 CPU를 가진 NUMA 시스템에서는 이것은 사실이 아니다. CPU는 자신의 로컬 메모리에 더 빠르게 접근할 수 있다.

NUMA 시스템은 메인 메모리에 대한 모든 액세스가 동일하게 취급되는 시스템보다 예외 없이 느리다. 하지만 더 많은 CPU를 수용할 수 있으므로 더 높은 수준의 처리량과 병렬 처리를 달성할 수 있다.

프로세스가 페이지 폴트를 일으키면 프로세스가 실행 중인 CPU에 최대한 가까운 프레임을 할당한다. (캐시 적중률을 높이고 메모리 접근 시간을 감소시키기 위함) linux에서는 각 numa 노드에 대해 별도의 가용 프레임 리스트가 있어 스레드는 자신이 실행중인 노드에서 메모리를 할당받는 것을 보장한다.

10.6 스래싱

과도한 페이징 작업을 스래싱(thrashing)이라고 부른다.
어떤 프로세스가 실제 실행보다 더 많은 시간을 페이징에 사용하고 있다면 스래싱이 발생했다고 한다.

쓰로틀링과는 다르다.
쓰로틀링은 시스템이나 장치에서 일부 동작을 제한하거나 조절하여 안정성을 유지하는 기술이다.
예시: 프로세서 쓰로틀링은 CPU의 속도를 낮추어 발열을 제어하거나 전력 소비를 줄이는 등의 목적으로 사용됩

10.6.1 스래싱의 원인

초기의 페이징 시스템에서는 다음과 같은 상황이 발생했었다.
운영체제는 CPU의 이용률(utilization)을 감시한다. CPU 이용률이 낮아지면 새로운 프로세스를 시스템에 더 추가해서 다중 프로그래밍의 정도를 높인다. 이러한 상황에서 전역 페이지 교체 알고리즘을 통해 어떤 프로세스의 페이지인지에 대한 고려 없이 교체를 수행한다. 프로세스가 새로운 실행 단계로 진입하여 더 많은 프레임이 필요하다고 가정하자. 그러면 페이지 폴트가 발생하면서 다른 프로세스들로부터 프레임들을 가져오게 된다. 그런데 교체된 페이지들이 해당 프로세스에서 필요로 하는 것이였다면, 다시 페이지 폴트를 발생시키고 다른 프로세스에서 프레임을 가져온다. 이러면 준비 큐가 비게 되고, 프로세스들은 페이지를 기다리게 된다. 그러면 CPU 이용률은 떨어진다.

요약하면 서로 빈 프레임이 필요하다보니 계속 요청하게 되는 상황에서 스래싱이 발생한다는 것

스래싱을 방지하기 위해서는 각 프로세스가 필요로 하는 최소한의 프레임 개수를 보장해야 한다. 이를 위해 지역성 모델(locality model)을 기반으로 실제로 사용하고 있는 프레임의 수가 몇 개인지 알아본다.

지역성 모델이란 프로세스가 실행될 때에는 항상 어떤 특정한 지역에서만 메모리를 집중적으로 참조함을 말한다.
지역이란 집중적으로 함께 참조되는 페이지들의 집합을 의미한다.

실행중인 프로그램은 여러 개의 지역으로 구성되어 있고, 이 지역들은 서로 겹쳐질 수도 있다.

시간 a 에서 지역성은 페이지 집합 (18, 19, 20, 21, 22, 23, 24, 29, 30, 33) 이다. 시간 b 에서 지역성은 페이지 집합 (18, 19, 20, 24, 25, 26, 27, 28, 29, 31, 32, 33) 으로 변경된다.

지역성 모델은 캐싱 기법의 기본 원리이기도 하다.

필요로 하는 지역성의 크기보다 적은 프레임을 할당하게 되면, 프로세스는 접근해야 하는 모든 페이지를 메모리에 유지할 수 없기 때문에 지속해서 페이지 폴트를 발생시키게 된다.

10.6.2 작업 집합 모델

델타(Δ, 변화량을 나타내는 기호) 만큼의 페이지 참조를 관찰하여 그 안에 들어있는 서로 다른 페이지들의 집합을 작업 집합(working set) 이라고 부른다.

델타 값을 선택하면 운영체제는 각 프로데스의 작업 집합을 감시하면서 프로세스에 충분한 프레임을 할당한다.

이러한 방법은 가능한 최대의 다중 프로그래밍의 정도를 유지하면서도 스래싱을 방지할 수 있게 해준다.

10.6.3 페이지 폴트 빈도

스래싱이란 페이지 폴트율이 높은 것을 의미한다.
페이지 폴트 빈도를 이용하여 상한과 하한을 정해놓고 그에 따라 프레임 수를 조율한다.

10.6.4 현재 관행

현실적으로 스래싱과 그에 따른 스와핑을 성능에 영향을 미친다.
가장 좋은 회피 방법은 가능한 한 충분한 물리 메모리를 장착하는 것이다.

10.7 메모리 압축

페이징의 대안은 메모리 압축이다.

수정된 프레임을 스왑 공간으로 페이징 아웃하지 않고 여러 프레임을 하나의 프레임으로 압축한다. 이러면 시스템이 페이지 스와핑에 의존하지 않고도 메모리 사용량을 줄일 수 있다.

압축 이전의 가용 프레임 리스트

압축 이후의 가용 프레임 리스트

15, 3, 35 3개의 프레임을 7 이라는 하나의 프레임으로 압축하였다.

모바일 시스템은 일반적으로 표준 스와핑 또는 페이지 스와핑을 지원하지 않는다. 따라서 메모리 압축은 Android 및 iOS를 포함한 대부분의 모바일 운영체제의 메모리 관리 전략의 핵심 부분이다.

메모리 압축을 위해서는 압축된 페이지를 유지하기 위해 사용 가능한 프레임을 할당해야 하지만 압축 알고리즘으로 얻은 메모리 감소에 따라 상당한 메모리를 절약할 수 있다.

책에서는 애플의 WKdm 방식에 대해서 설명한다. 그래서 찾아보니 잘 정리된 블로그가 있어서 링크를 걸어본다. 내용을 보니 소스코드와 논문도 공개되어 있다는 것 같다. 소스코드는 github에도 올라와 있길래 함께 링크를 걸어본다.

• OS X Mavericks의 메모리 압축 (Compressed Memory)
• WKdm 소스코드

10.8 커널 메모리의 할당

커널 메모리는 보통 사용자 모드 프로세스에 할당해 주기 위한 페이지 리스트와는 별도의 메모리 풀에서 할당 받는다. 이유는 다음과 같다.

1. 커널은 다양한 크기의 자료구조를 위해 메모리를 할당받는다. 이 자료구조는 페이지 크기보다 작은 크기를 갖기도 한다. 커널은 메모리를 조심스럽게 사용하고 단편화에 의한 낭비를 최소화하고자 노력한다. 많은 운영체제가 커널 코드나 데이터는 페이징 하지 않는다.

2. 물리 메모리에 직접 접근하는 특정 하드웨어 장치는 물리적으로 연속적인 메모리가 있어야 하는 경우가 있다.

10.8.1 버디 시스템 (Buddy System)

버디 시스템은 물리적으로 연속된 페이지들로 이루어진 고정된 크기의 세그먼트로부터 메모리를 할당한다.

초기 메모리 세그먼트의 크기를 256 KB 라고 가정하자. 이때 21 KB의 메모리를 요구하였다면 아래와 같은 과정으로 진행된다.

21의 가장 가까운 2의 거듭제곱은 32이므로 32KB 세그먼트가 할당된다.

10.8.2 슬랩 할당 (Slab Allocation)

슬랩은 하나 또는 그 이상의 연속된 페이지들로 구성된다. 캐시는 하나 혹은 그 이상의 슬랩들로 구성된다.

슬랩은 세 가지 상태 중 한 상태에 있게 된다.

• Full
• Empty
• Partial: Used, free 객체가 섞여 있음.

슬랩 할당 알고리즘은 먼저 partial 슬랩의 free 객체를 이용해 요청을 처리하려고 시도한다. partial 슬랩이 없으면 empty슬랩으로부터 free 객체를 할당한다. Empty 슬랩도 없는 경우에는 새로운 슬랩이 연속된 물리 메모리에서 할당되어 캐시에 주어진다.

슬랩 할당의 장점은 다음과 같다.

1. 단편화에 의해 낭비되는 메모리가 없다. 커널이 메모리 할당을 요구할 때마다 슬랩 할당기는 정확히 필요한 만큼의 메모리만을 할당한다.
2. 메모리 요청이 빠르게 처리된다. 따라서 할당과 해제가 빈번한 자료 구조 객체를 관리하는데 효율적이다.

단, 내부 단편화는 해결되어도 외부 단편화는 있을 것.

슬랩에 대한 부분은 아래 블로그에서 잘 정리해둔것 같다. Slab Allocator(슬랩 할당자)

위에서 생각했던 단편화에 대한 부분도 다뤄져 있었다.
kmalloc() 함수를 호출하여 동적 메모리를 54바이트 크기로 할당을 받으려고 한다. 이 때 커널은 “kmalloc-64” 슬랩 캐시를 지정한다. “kmalloc-64” 슬랩 캐시가 미리 할당해 놓은 64바이트 사이즈의 slub object를 할당해준다. 그럼 나머지 10바이트는 어떻게 될까? 나머지 10바이트는 버리게 된다. 동적 메모리 할당 속도를 위해 어느 정도 메모리 파편화가 생기게 된다.

10.9 기타 고려 사항

10.9.1 프리페이징

높은 수준의 초기 페이징을 방지 - 필요한 페이지의 일부 또는 전부를 한 번에 메모리에 가져옴

과연 프리페이징을 사용하는 비용이 페이지 폴트를 처리하는 비용보다 적을까? (프리페이징을 통해 가져온 페이지가 많이 사용되지 않는 경우)

10.9.2 페이지 크기

이미 존재하는 시스템에서는 페이지 크기를 바꾸는 것이 거의 불가능하다. 그러나 새 시스템을 개발할 때에는 결정할 수 있다.

1. 페이지는 항상 2의 제곱이고 일반적으로 2^12 ~ 2^22 바이트나 워드 범위이다.
2. 페이지 크기를 감소시키면 페이지의 수가 늘어난다. 그러면 페이지 테이블의 크기가 증가된다.
3. 메모리 사용 효율을 위해서는 작은 페이지가 좋다. 내부 단편화가 발생할 가능성이 줄어든다.
4. 작은 페이지 크기를 갖는 경우 지역성이 향상되어 전체 I/O가 줄어든다. 또한 메모리 총량도 덜 사용하게 된다.
5. 페이지 폴트 횟수를 줄이기 위해서는 큰 페이지가 좋다.

이 문제에 대한 최적의 해결책은 존재하지 않는다. 하지만 시대가 지날수록 크기가 커지는 추세이다.

10.9.3 TLB Reach

TLB의 항목 개수를 늘리면 적중률은 올라간다. 하지만 쉽지 않다. TLB에 사용되는 연관 메모리(Associative Memory)가 비싸고 전력도 많이 소모하기 때문이다. (TLB는 CPU안에 있다.)

TLB Reach: TLB로부터 액세스할 수 있는 메모리 공간의 크기 (TLB에 있는 항목 수 x 페이지 크기)

이상적으로 한 프로세스의 작업 집합이 TLB에 다 들어올 수 있으면 가장 좋다. 그렇지 못하면 프로세스는 TLB에서 해결하지 못하고 페이지 테이블까지 가야하고, 그러면 수행 시간이 매우 느려지게 된다. TLB 크기를 두 배로 늘리면 TLB reach 크기도 두 배 늘어난다.

페이지 크기를 늘릴수도 있다.

10.9.4 역 페이지 테이블

역 페이지 테이블은 가상-물리 주소 변환을 추적하는 데 필요한 물리 메모리의 양을 줄여준다. 하지만 참조된 페이지가 현재 메모리에 없을 때는 문제가 된다. 이를 해결하려면 프로세스마다 확장 페이지 테이블(extended page table)을 유지해야 한다

10.9.5 프로그램 주소

일반적으로 사용자는 페이징 처리에 대해서 모르고 있어도 된다. 하지만 그 특성을 이해하면 성능을 개선할수도 있다.

페이지가 128워드의 크기라고 가정해보자.

int i, j;
int[128][128] data;

for (j = 0; j < 128; j++)
    for (i = 0; i < 128; i++)
        data[i][j] = 0;

위 코드의 경우 128 x 128 = 16,384 번의 페이지 폴트를 초래한다.

int i, j;
int[128][128] data;

for (i = 0; i < 128; i++)
    for (j = 0; j < 128; j++)
        data[i][j] = 0;

i, j의 순서를 바꿔줌으로 페이지 폴트의 수를 128로 감소시킬 수 있다.

자료구조와 프로그래밍 구조를 잘 선택하면 지역성을 향상시키고 페이지 폴트율과 작업 집합의 페이지 수를 줄일 수 있다.

10.9.6 I/O 상호 잠금(Interlock)과 페이지 잠금(locking)

요구 페이징을 사용할 때, 그 페이지의 일부는 메모리에 고정하는 것이 필요할 때가 있다.

• 해결책 1.
  • 사용자 공간에는 직접 I/O를 하지 않는다. 먼저 시스템 메모리로 복사하고 거기서 디스크에 쓰기 작업을 수행하도록 한다.
  • 데이터가 2번 움직여야 하는 오버헤드가 있다.
• 해결책 2.
  • 페이지를 메모리에서 잠금.
  • 잠금 비트를 프레임마다 두고 프레임이 잠기면 교체 고려 대상에서 제외