개요
운영체제를 공부하면서 느꼈던 건 “소프트웨어의 전반적인 흐름을 중요하는데 매우 중요한 지식” 이라는 점입니다. 따라서 이에 대한 내용을 다 같이 공유하고 싶어 “도움이 되었으면 좋겠어요” 시리즈를 시작하게 되었습니다.
1. Trashing이란?
Trashing은 메모리 영역에 접근할 때 메모리에 Page Fault가 높은 것을 의미합니다.
Trashing이 발생하는 과정은 다음과 같습니다.
1.
프로세스가 점점 많아짐에 따라 비어 있는 프레임의 수가 감소한다.
2.
특정 시점에서 동작 중인 프로세스가 요구하는 메모리가 가용 가능한 물리 메모리보다 많아진다.
3.
Page Fault가 발생하고 Page in/out을 처리하는 동안 CPU는 사용하지 않게 된다.
4.
CPU 사용률 (Utilization)이 낮아짐에 따라 CPU Scheduler는 이를 한가하다고 판단하여 더 많은 프로세스를 실행하려고 한다.
5.
악순환이 반복된다.
위 그래프를 보시면 특정 시점에 trashing이 발생하고 사용률이 급격하게 떨어지는 것을 확인할 수 있습니다.
2. Trashing의 근본적인 원인
사실 Trashing은 모든 프로세스가 하나의 물리적 메모리 공간을 공유하기 때문에 발생하게 됩니다.
위 말을 이해하기 위해서는 Global Replacement과 Local Replacement를 이해해야 합니다.
Global Replacement
process selects a replacement frame from the set of all frames.
Local Replacement
each process selects the victim frame from only its own set of allocated frames
간단하게 요약해서 두 Replacement 기법의 차이는 자신의 프로세스에 할당된 프레임 내에서 해결하냐, 전체적인 프레임 세트에서 해결하냐의 차이입니다.
그렇다면 Local Replacement로 Page Falut를 해결할 수 있을까요?
해결할 수 없습니다. 예를 들어, 시스템의 메모리가 부족한 순간에 어떤 한 프로세스는 메모리를 많이 확보하고 있다 하더라도, 메모리를 확보하지 못한 다른 프로세스에서 Page Fault가 지속적으로 발생할 수 있기 때문입니다.
3. Trashing을 해결하는 법
Working Set
Trashing을 해결하기 위해서는 Working Set 이라는 개념을 도입해야 합니다,
Working Set은 어느 시점에 특정 프로세스가 접근하는 페이지 들의 집합입니다. 쉽게 말해서 프로세스의 작업을 구성할 때 자주 참조되는 페이지를 묶어서 처리한다고 생각하면 됩니다. (이 때 지역성의 원리가 사용됩니다)
하지만 Working set의 전체 프레임이 할당된 페이지 프레임보다 크다면 여전히 Trashing이 발생하게 됩니다.
Page Fault Frequency (PFF)
이는 프로세스의 Page Fault Rate를 주기적으로 조사하고 해당 값에 근거하여 각 프로세스에 할당되는 프레임 양을 동적으로 예측하는 알고리즘입니다.
현재 페이지 부재와 직전 페이지 부재 사이의 시간을 관찰하여 상한 값(upper bound)을 초과하거나 하한 값(lower bound) 미만이 되면 운영체제가 메모리에 올라가 있는 프로세스의 수를 조절합니다.
4. Kernel Memory 할당
시스템의 물리 메모리가 부족할 때에는 커널이 관리하는 페이지 프레임 중에서 할당합니다.
커널 메모리 할당과 관련해서 알아볼 방법은 두 가지가 있습니다.
Buddy System
이는 메모리에 물리적으로 연속된 페이지로 구성된 고정된 크기의 세그먼트를 할당하는 방법을 의미합니다.
절차는 다음과 같습니다.
1.
메인 메모리는 항상 2^N size로 할당한다.
2.
사용할 수 있는 가장 큰 메모리부터 시작해서 Binary로 절반씩 쪼개나가면서 아래 조건을 만족시키는 공간을 찾는다.
3.
만약 프로세스 메모리 크기가 K라고 하면, 2^(U-1) < K <= 2^U 를 만족시키는 U를 찾고, 2^U 만큼의 공간에 프로세스를 할당한다. 예를 들어, 프로세스 크기가 1000B이면, 512B < 1000B < 1024B이기 때문에 1024B 사이즈의 메모리에 할당하는 것이다.
4.
프로세스가 종료되고, 만약 같은 Parent를 갖는 Buddy 공간이 비어있다면 Merge한다.
하지만 내부 단편화가 발생할 여지가 있습니다.
Slab Allocation
이는 커널에서 사용하는 동적 메모리 할당자입니다.
메모리 풀 구조를 가지고 있어서 미리 고정된 크기의 메모리 블록들을 할당해 놓습니다.
커널은 Slab, Slub, Slob 중 하나를 선택하여 빌드되어 사용됩니다.
Slab
2007~2008년까지 default로 사용됨처음 생성된 slab은 full 리스트에서 관리되다가 object가 하나라도 사용되는 경우, 그 slab은 partial 리스트로 이동되어 관리됨. 다 사용하는 경우 다시 이동되어 empty 리스트에서 관리됨
Slub
현재까지 defualt로 사용됨처음 생성된 slub은 object 사용 개수가 0으로 시작하고 partial 리스트로만 관리됨
Slob
적은 메모리 자원을 가진 시스템에서 사용됨속도는 느리지만 메모리 소모가 가장 적음
슬랩 구조
•
슬랩 cache : 커널에서 자주 요청하는 크기에 대한 동적 메모리를 미리 확보하고 관리하는 주체
•
슬랩 object : 슬랩 cache가 할당해 놓은 메모리 블록 (유저모드에서 사용되는 malloc()의 chunk와 비슷한 개념)
•
슬랩 page : 슬랩 object로 구성된 page
Alloc이라고 되어 있는 슬랩 object들은 할당이 되어 있는 상태이고, Free라고 되어 있는 슬랩 object들은 해제되어 있는 상태입니다.
이때, Free된 슬랩 object들은 freelist라는 리스트 자료구조로 관리됩니다.
•
유저공간에서 free된 chunck들이 bins 리스트로 관리되는 것과 비슷한 개념
위 그림을 보면 freelist가 첫 free 슬랩 object를 가리키고, 각 free object끼리 순서대로 연결되어 있습니다.
참고로 page의 단위는 4KB 입니다.
슬랩 캐시
1개 이상의 슬랩 page가 모여 슬랩 cache가 구성됩니다.
즉, 슬랩 cache 내의 모든 object 들은 동일한 사이즈만을 제공합니다.
