운영체제 20. 가상메모리가 무엇인가

가상 메모리가 무엇인가?

어차피 프로세스를 돌릴 때 모든 페이지가 필요하지 않고, 페이지의 일부만 있어도 당장에는 돌릴 수 있다. 따라서 프로세스의 페이지를 일부만 올리면 더 많은 프로세스를 한번에 돌릴 수 있지 않을까?

페이지 적재 여부를 vaild-invaild bit로 표시한다. 적재되지 않은 페이지는 디스크에 저장해둔다. 그렇다면 프로세스를 돌리다 적재되지 않은 페이지가 필요해지면 어떻게 해야할까?

즉 CPU가 명령어를 돌리다 논리 주소를 만나면 MMU에게 떠넘긴다. MMU는 비트를 나눠 \((p, d)\)로 구분한다. \(p\)를 가지고 page table에 접근해야 하는데, 그 page가 invaild하면 Page Fault가 발생한다. 이러면 페이지를 요구(Demand paging)해야 한다.

페이지 요구 과정은 다음과 같다. MMU가 트랩을 건다. 트랩은 인터럽트고, CPU는 인터럽트를 받아 인터럽트 루틴을 수행 후 관련된 ISR을 찾아 실행한다. 관련된 ISR의 역할은 디스크에 있는 Page를 찾아서 비어있는 Frame에 적재하고, page table을 업데이트한다.

두가지 의문점이 떠오른다.

• 디스크에서 페이지가 어디있는지 어떻게 찾는가? 어떤 방식으로 저장되어 있는가?
• 만약 Free Frame이 없으면 어떻게 해야하는가?

디스크에서 페이지가 어디있는지 어떻게 찾는가? 어떤 방식으로 저장되어 있는가?

페이지 테이블에 직접 기록할 수도 있다. valid-invalid bit를 invalid로 설정하고, 디스크에 저장한다. 그리고 페이지 넘버를 저장하는 곳에 디스크 주소를 기록할 수 있다.

만약 Free Frame이 없으면 어떻게 해야하는가?

가장 안중요한 페이지를 찾아서 뺴고 넣어야 한다. 이를 페이지 대치(Page Replacement) 라고 한다.

페이지 대치 과정은 다음과 같다. 먼저 희생양을 결정한다. 희생양을 결정하는 여러 페이지 대치 알고리즘이 존재한다. Dirty Bit를 체크하여 수정사항이 있는지 체크한다. 수정사항이 없으면 그냥 덮어쓴다. 수정사항이 있으면, 디스크에 저장(write-back)해야 한다. 이후 희생양 페이지의 페이지 테이블로 가서 vaild-invaild bit를 invaild로 변경한다. 이제 프레임에 페이지를 넣고, 해당 페이지의 vaild-invaild bit를 vaild로 변경한다.

희생양을 결정하는 페이지 대치 알고리즘이 무엇이 있는가?

가장 최고의 방법은 “앞으로 가장 오랫동안 사용되지 않을 페이지“를 찾아 대치시키면 된다. 이론적으로 페이지가 언제 참조될 지 정보 참조 스트링을 알고 있다면 사용할 수 있다. 사실 그건 알 수 없다. 따라서 대체 방법을 사용할 것이다.

가장 최악의 방법은 “랜덤으로 뽑은 페이지“를 대치하는 것이다. 페이지 알고리즘은 적어도 랜덤으로 뽑은 것보단 좋아야 한다. 즉, 하한선이다.

(1) FIFO 메모리에 올라온지 가장 오래된 페이지를 대치한다. 그러나 오래 올라온 페이지와, 앞으로 오래 사용하지 않을 페이지는 의미가 다르다. 따라서 오히려 더 Page Fault도 늘어날 수 있다.

(2) LRU(Least Recently Used) 오랫동안 사용되지 않은 페이지를 대치한다. 최근에 사용한 페이지는 앞으로 사용할 가능성이 높고, 오랫동안 사용되지 않은 페이지는 앞으로도 안 쓸 가능성이 높다는 지역성(Locality of reference) 아이디어에 근거한다.

그렇다면, 어떻게 오랫동안 사용되지 않을 페이지를 알 수 있는가? 첫번째 방법으로, 페이지 테이블에 시간을 기록해두는 것이다. 페이지 대치가 필요할 때마다 페이지 테이블의 타임 필드를 탐색해 희생할 페이지를 고른다. 이 방법은 메모리 접근 성능이 약 10배정도 느려진다.

두번째 방법으로, LRU 스택을 사용한다. 해당 페이지가 참조될 때마다 스택의 맨 아래로 내린다. 그러면 맨 위의 Page를 대치하면 된다.

사용될 때마다 맨 아래로 내리면, 맨 위의 Page를 대치하면 된다.

이 방법도 스택 업데이트 오버헤드가 존재한다. 따라서 시간 값이나 스택을 사용하지 않고 비슷한 효과를 내는 LRU 근사 알고리즘을 사용한다.

(3) LRU 근사(approximation) 첫번째로, 페이지 테이블에 참조 비트를 도입한다. 참조 비트는 초기값은 0이지만 참조 시에 1로 설정되는 비트값이다. 이것만 사용하면 문제가 된다. 참조 비트가 딱 하나면 0이면 그것을 대치하면 된다. 그러나 0이 여러개면? 그리고 참조 비트가 모두 1이면? 어떤 것을 대치해야 하는가?

따라서 참조 바이트를 사용한다. 두번째 방법이다. 페이지마다 참조 바이트를 가지고 있다. 타이머 인터럽트가 발생할 때마다 참조 바이트를 한칸씩 오른쪽로 Shift하고, 맨 앞에 참조 비트를 복사한다. 이후 참조 비트를 0으로 초기화한다. 이러면 참조 바이트가 클수록 가장 최근에 참조가 많이 되는 페이지고, 참조 바이트가 작을 수록 참조가 덜 되는 페이지와 같다. 그러나 8회 이전의 참조 상황은 비교할 수 없다는 한계점이 존재한다.

세번째 방법은 2차 기회 알고리즘이다. LRU와 근접하다. 방법은 다음과 같다. Page Fault가 발생하면, 페이지 순서대로 참조 비트를 검사한다. 참조 비트가 1이면, 0으로 바꾸고 넘어간다. 즉 기회를 한번 부여한다. 이를 0을 찾을 때까지 사이클을 반복한다. 0을 찾으면 바로 페이지를 대치한다.

이것이 가능한 이유가 무엇인가? 이전 Page Fault가 발생한 시간동안에도 0으로 바꿔둔게 아직도 0이라면 오랫동안 사용하지 않은 Page와 같다는 것에 근거한다. 그러나 Page Fault가 자주 발생하면 이 근거가 무색해진다는 한계점이 존재한다. 또, 최악의 경우 모든 페이지의 참조 비트가 1이어서 한바퀴를 다 돈 경우, 임의의 페이지를 선택하는 것과 다름없다.

따라서 네번째 방법은 개선된 2차 기회 알고리즘이다. 참조 비트 뿐 아니라 오염 비트까지 사용하자. 다음과 같이 등급을 매긴다.

• 1 - \((0,0)\): 참조되지도 않고 변경되지도 않은 것
• 2 - \((0, 1)\): 참조되지 않았으나 그 전에 변경된 것
• 3 - \((1, 0)\): 참조되었으나 변경되지 않은 것
• 4 - \((1, 1)\): 참조도 되고 변경도 된 것

모든 페이지의 등급을 비교하여, 가장 낮은 First Page가 대치된다. 당연히 참조도 안되고 수정도 안된게 가장 먼저 대치되어야 한다. 그리고 참조가 되진 않았지만 수정된게 두번째로 대치된다. 참조가 되었지만 수정된 적은 없는게 세번째로 대치된다. 마지막으로 참조도 되고 수정도 된게 가장 활발히 사용중인 Page와 같다.

가상 메모리 기법의 장단점이 무엇인가?

한정된 메모리에 더 많은 프로세스를 올릴 수 있따. 이는 CPU 사용율과 처리율(Throughput)을 올린다. 그러나 Page-Fault 오버헤드가 존재하여 성능이 프로세스를 모두 적재하는것보다 조금 떨어진다. 만약 페이지 요구를 너무 많이 해버리면 메모리 속도가 아니라 하드디스크 속도로 돌게 된다. 이런 현상을 스레싱(Thrashing) 이라 한다. 스레싱이란 메모리가 부족하여 Page Fault가 끊임 없이 발생하고, 프로세스를 실행하는 시간보다 페이지 대치하는 시간이 더 길어지는 상태를 뜻한다. CPU 이용률은 나락가고, 시스템은 멈춘 것처럼 보인다.

Page fault rate를 줄이는 방법이 무엇이 있을까?

Page fault가 발생하면 발생 안하는 것보다 오버헤드가 발생한다. 그리고 Page를 넣을 곳이 없어 대치해야 한다면, 오버헤드가 더 크다.

그러면 이렇게 하면 되지 않을까?

1. 페이지 대치가 안일어나도록 늘 빈 프레임을 만들어둔다.
2. 페이지 Fault가 일어날 때마다 하나만 올리는게 아니라, 관련된 페이지를 뭉탱이로 올린다.

1번 방법을 사전 대치라 한다. 미리 페이지 대치 알고리즘을 실행시켜둬서 항상 빈 프레임을 만들어두는 것이다. 미리 언제 알고리즘을 실행하는가? 프레임이 꽉 찼을때 실행하면 된다. 알고리즘을 몇 번 실행하는가? 적당히 필요한만큼 실행한다고 한다..

2번 방법을 사전 적재라 한다. 사용할 페이지에서 다른 페이지에 있는 함수나 상수값을 참조하는 경우, 그것을 따라가 관련된 페이지를 한꺼번에 올릴 수도 있다.

[!tip] 페이지 Fault 발생률과 프레임 개수는 어떤 관계가 있을까?{title} 프레임이 많아질 수록 페이지를 한번에 많이 올릴 수 있으므로 페이지 Fault 발생률이 낮아진다. 반대로 프레임이 적을 수록 페이지를 적게 올릴 수 있으므로 페이지 Fault 발생률이 높아진다. 즉, 페이지 폴트 발생률과 프레임 수는 반비례 관계에 있다.

[!tip] Copy-on-Write 기법이 무엇인가?{title} 데이터 복사 요청이 있을 때 바로 복사하지 않고, 원본을 참조한다. 그리고 복사한 데이터나 원본 데이터의 수정이 발생하면 그때 복사한다.

fork()에서 유용하다. fork()하면 부모 페이지를 통째로 복사해야 한다. 이 과정은 부담된다. 또한 text 영역과 같이 굳이 복사가 필요하지 않은 Context도 존재한다. 따라서 일단 참조하되, 쓰기 요청이 발생할 때 그때 복사하면 된다.

[!tip] Page Fault를 최소화 하기 위한 프로그래밍 팁{title} (1) 2중 루프 순서를 잘 설정한다.

int data[128][128];

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

j부분이 연속적으로 저장되어 있고, i 부분은 띄엄띄엄 저장되어 있다. 즉 최악의 경우 페이지 Fault가 \(128 \times 128\)번 발생한다.

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

이건 페이지 Fault가 대략 \(128\)번 발생한다. \(j\)는 연속된 공간에 저장되어 있으므로 한번 루프는 하나의 페이지에서 해결 가능하다. 이를 잘 고려해야 한다.

(2) 자료구조 선택 배열, 스택에 비해 해시 테이블, Linked List와 같은 자료구조는 Page Fault율이 높다. 데이터가 이곳저곳 흩어져있기 때문이다.

Page Fault를 생각할 것인지, 아니면 그것을 상회하는 장점이 있는지 가치판단을 잘 해서 자료구조를 고르자.

프로세스마다 몇개의 페이지를 올려야 할까?

프로세스의 페이지를 너무 적게 올리면 페이지 Fault가 자주 발생해 Thrashing이 생긴다. 너무 많이 할당하면 한번에 많은 프로세스를 올려야 한다. 어떻게 적당하게 페이지를 올릴까?

(1) 정적 할당 (Static Allocation) 첫번째 방법으로, 그냥 균등하게 분배하자. 프레임이 100개있고, 프로세스가 5개 있으면 각 프로세스는 최대 20개 프레임을 올릴 수 있다. 어떤 프로세스의 크기는 커서 한번에 많이 페이지를 올려야 하는 반면, 어떤 프로세스의 크기는 작아서 적게 올려도 무방한 경우가 있다. 따라서 비효율적이다.

두번째 방법으로, 그렇다면 프로세스 크기에 비례해서 프레임을 주면 되지 않을까? 그러나 프로세스가 크다고 해서 항상 더 많은 메모리는 사용하는건 아니다. 최적 방법이 아니다.

프레임의 전체 개수를 \(m\), 프로세스의 크기를 \(s_{i}\)라 하고, \(S=\sum_{i}s_{i}\)라 하면, \(P_{i}\)에게 할당되는 프레임 개수는 다음과 같다.

\[a_{i} = \frac{s_{i}}{S} \cdot m\]

세번째 방법으로, 우선순위가 높은 프로세스에게 많은 프레임을 부여한다면 어떨까? 우선 순위가 높으면 스케쥴링이 많이 발생할 것이다. 그러나 기아 상태에 빠질 수 있다.

정답은 없다. 만약 정적 할당을 사용해야 한다면 비례랑 우선순위를 적당히 쓰는게 좋지 않을까?

(2) 동적 할당 (Dynamic Allcation) 작업 세트 모델을 사용한다. 작업 세트 모델의 아이디어는, 지역성 원리에 근거한다. 지역성 원리는 특정 시간동안 한정된 수의 페이지에 집중적으로 접근한다는 개념이다. 즉, 집중하는 페이지만 최소한으로 올려두면 최고의 방법이다. 특정 시간(\(\Delta\))동안 집중하는 페이지 집합을 작업 세트(Working Set) 라고 하자. 이 작업 세트를 어떻게 알 수 있을까?

적당한 \(\Delta\)를 설정하는 것이다. \(\Delta\)가 작으면, 지역을 충분히 포함하지 못한다. \(\Delta\)가 크면 지역이 겹치게 된다.

커널이 작업 세트를 추적하는 방법은 다음과 같다. 먼저 적당한 \(\Delta\) 시간을 설정하여, 그 시간마다 타이머 인터럽트를 발생시킨다. 페이지 테이블의 참조 비트를 확인한다. 1이면 작업 세트에 포함시키고, 0이면 작업 세트에서 제외시킨다. 이후 모든 참조 비트를 0으로 초기화한다. 이를 반복하여 작업 세트를 추적한다.

그럼 작업 세트에서 제외된 페이지는 빼야겠네? 그렇다. 그러나 바로 뺴지는 않는다. 게으른(lazy) 방식으로 뺀다. 예를들어 나중에 페이지 대치가 일어날 때 후보 페이지로 사용될 수 있을 것이다.

이렇게 프로세스마다 작업 세트의 크기를 추적할 수 있다. 우리는 쓰레싱을 막는 것이다. 모든 프로세스의 작업 세트의 합보다 프레임 개수가 작아지면 쓰레싱이 발생한다고 본다. \(W_{i}\)를 작업 세트의 개수, \(m\)을 프레임 개수라고 하면

\[\sum_{i} W_{i} > m\]

조건을 만족하면 쓰레싱 발생을 감지한 것이다. 임의의 프로세스를 중지함으로써 쓰레싱을 예방할 수 있다.

커널 메모리는 사용자 메모리와 어떻게 다른가?

커널도 일종의 프로세스다. 커널도 물리적 메모리 위에 올라와서 동작한다. 그렇다면 커널도 페이징으로 관리될까? 그렇다. 그러나 커널은 사용자 프로세스와 달리 특별한 방법을 사용한다.

그 이유는, 커널 코드는 페이지 대치될 수 없다. 그리고 일부 하드웨어는 물리적으로 연속된 메모리 구조를 필요로 할 수 있다. 그리고 단편화에 의한 낭비를 최소화해야 한다. 커널은 어떻게 페이지를 관리할까?

커널은 따라서 디스크 스와핑을 사용하지 않는다. 핵심 기능이 담긴 페이지는 물리 메모리에 고정되어서, 그 위치에서 변하지 않는다. 커널이 자료구조같은 것을 할당하면 메모리 공간이 필요해진다.

(1) Buddy System 커널이 요청한 메모리를 포함하는 최소 \(2^n\) 크기의 메모리 블럭을 연속적인 공간에 할당해준다. 이게 무슨말이냐? 커널이 \(55KB\) 용량의 자료구조를 할당한다고 치자. 그러면 \(55KB\)를 포함하는 최소 2의 거듭제곱 단위는 \(64KB\)다. 즉 이 \(64KB\) 페이지를 만들어서 연속적으로 할당해준다.

어떻게 구현하는가? 세그먼트를 계속 분할한다. 만약 필요없어지면 반납하여 상위의 세그먼트에 할당한다. 장점은 속도가 빠르며, 외부 단편화가 없다. 단점은 내부 단편화가 발생한다.

(2) 슬랩 할당 (Slab Allocation) 버디 시스템의 페이지 최소 단위는 4KB다. 그러나 크기가 아주 작은 자료구조를 할당하기 위해 4KB를 할당하는건 비효율적이다. 이런 내부 단편화를 해결할 수 있을까?

기본적인 아이디어는 다음과 같다. 크기가 큰 메모리가 필요하면 버디 시스템을 사용한다. 만약 크기가 작거나, 특정 자주 사용하는 타입의 객체는 슬랩에 할당한다.

용어 정리를 해보자. 캐시는 슬랩의 관리자다. 슬랩은 오브젝트를 담는 박스다. 오브젝트는 하나의 객체를 담을 수 있는 최소 단위다.

커널이 특정 크기의 메모리 또는 특정 유형의 자료구조를 할당해달라고 요청한 상황을 생각하자. 특정 크기의 메모리, 또는 자료구조의 캐시로 찾아간다. 캐시는 슬랩을 탐색하여 비어있는 오브젝트가 있는지 본다. 있으면 그 오브젝트의 주소를 반환한다. 없다면, 버디 시스템에게 졸라서 4KB 공간을 하나 받고, 그 페이지를 슬랩화한다. 그리고 메모리 공간을 쪼개서 오브젝트들을 만든다. 그럼 비어있는 오브젝트가 생겼으므로 주소 하나를 반환한다.

객체를 할당할 때 속도가 빠른 캐시에서 뒤져서 바로 꺼내주면 되므로 속도가 빠르다. 그리고 단편화가 크게 줄어든다. 또 같은 종류의 객체들이 인접한 메모리 공간에 몰려있으므로, 지역성이 좋다.