운영체제론[18]: 가상메모리 - 3

Allocation of Frames

각 프로세스는 필요로 하는 최소한의 프레임 개수가 있다.

예를 들어 IBM 370에서는 SS MOVE 명령어를 처리하기 위해 최소 6개의 페이지가 필요하다.

최대 할당량은 시스템의 총 프레임 수이다.

할당 방식에는 고정 할당(Fixed Allocation)과 우선순위 할당(Priority Allocation)이 사용된다.

 

Fixed Allocation

Equal allocation은 운영체제에 프레임을 할당한 후, 남은 프레임이 100개이고 프로세스가 5개라면 20개씩 나눠주는 방법이다.

 

Proportional allocation은 프로세스의 크기에 따라 할당하는 방식이다. 다중 프로그래밍의 정도와 프로세스 크기가 변할 때 동적으로 변경된다.

 

 

Global allocation vs Local allocation

Global replacement는 프로세스가 모든 프레임 집합에서 교체 프레임을 선택한다.

즉 한 프로세스가 다른 프로세스로부터 프레임을 가져올 수 있다.

프로세스 실행 시간이 크게 달라지지만 처리량이 많아져 일반적으로 사용된다.

 

Local replacement는 자신에게 할당된 프레임 집합에서만 선택한다.

프로세스당 성능이 더 일관되지만 메모리가 충분히 활용되지 않을 수 있다.

 

 

 

Reclaiming Pages

global page replacement 정책을 구현하기 위한 전략으로, 항상 새로운 메모리 요청을 충족시키기에 충분한 여유 메모리를 확보하는 것이다.

모든 메모리 요청은 기다릴 필요 없이 free-frame list에서 해결한다. 즉, free-frame list가 0이 되는 것을 기다리지 않고 페이지 교체를 시작한다.

메모리 요청이 항상 성공할 수 있도록 페이지 교체는 free-frame list가 특정 임계값 이하로 떨어졌을 때 미리 실행한다.

이러한 일을 하는 커널루틴을 reapers라고 한다.

 

 

Non-Uniform Memory Access (NUMA)

메모리 접근 속도가 일관적이지 않은 컴퓨터 메모리 디자인으로, 멀티프로세서 시스템에서 중요하다.

각 프로세서가 자체 메모리를 갖는 구조에서, 그 프로세서가 직접 접근할 수 있는 로컬 메모리에 비해 다른 프로세서의 메모리에 접근하는 것이 더 오래걸린다.

따라서 NUMA 아키텍처에서는 스레드가 예약된 CPU에 가까운 메모리를 할당한다.

또 가능하면 스케줄러가 동일한 시스템 보드에 스레드를 스케줄링하도록 수정한다.

 

이런 문제는 Solaris에서 Igroups(지역성 그룹)을 만들어 해결했다.

Igroups는 CPU/메모리의 law latency를 추적하기 위한 구조이다.

스케줄러와 페이저에서 사용되며, 가능하면 모든 스레드를 한 Igroup 내에서 스케줄링하고 그 프로세스의 모든 메모리를 그 Igroup 내에서 할당한다. 이를 통해 메모리 접근 시간을 최적화하고 시스템의 전반적인 성능을 향상시키는 것이 가능하다.

 

 

 

Thrashing

프로세스가 충분한 페이지를 가지고 있지 않을 때 발생하는 현상

 

page fault 비율이 매우 높아져서 페이지를 가져오기 위해 page fault를 일으키고 기존의 프레임을 교체한다. 그러고 나서 교체된 프레임이 빠르게 다시 필요하게 되면 이 과정이 반복하게 된다.

이렇게 되면 CPU의 이용률이 낮아지고 운영체제는 프로그래밍의 수준을 높여야 한다고 판단한다.

그 결과 시스템에 또 다른 프로세스가 추가되며 프로세스는 페이지를 계속해서 스왑 인아웃하며 바쁘게 동작하게 된다.

위 현상을 스레싱이라 한다.

 

 

 

Demand Paging and Thrashing

demand paging이 작동할 수 있는 이유는 지역성 모델 때문이다. 프로세스는 한 지역성에서 다른 지역성으로 이동(migrate)한다. 지역성 들은 겹칠 수 있다.

 

스레싱이 발생하는 이유는 프로세스의 지역성 크기의 합이 전체 메모리 크기보다 클 때이다. 이런 현상의 영향을 제한하기 위해 지역 또는 우선순위 페이지 교체를 사용할 수 있다.

 

그러나 local page replacement algorithm도 스레싱을 완전히 해결할 수는 없는데, 어떤 프로세스가 스레싱이 발생하면, paging device가 바빠지므로 다른 프로세스는 스레싱이 아니더라도 EAT가 나빠지게 된다.

 

 

 

Working-Set Model

working-set이란 Δ시간동안 조회된 페이지의 집합이다.

 

Δ = working set window = 고정된 수의 페이지 참조

 

10000개의 명령어가 있다고 할 때,

WSSi (working-set size of Process Pi) = 최근 Δ 단위시간동안 참조된 페이지의 총 개수

 

Δ가 너무 작으면 전체 지역성을 포괄하지 못할 수 있다.

Δ가 너무 크면 여러 지역성을 포괄하게 될 수 있다.

Δ가 무한대면 전체 프로그램을 포괄하게 된다.

 

여기서 D는 모든 working-set size의 합이고, 이는 총 demand frame의 근사치를 나타내며 이것은 지역성의 근사치를 나타낸다.

따라서 m이 메모리 프레임 수라고 할 때, D > m이면 스레싱이 발생한다.

D > m 일 때의 정책으로, 프로세스를 종료하거나 swap out 할 수 있다.

 

working set은 timer와 reference bit를 사용하여 근사치를 계산할 수 있다.

 

예를 들어, D=10000이라고 하자.

5000 단위시간마다 타이머 인터럽트가 발생한다.

각 페이지에 대해 메모리에 2개의 비트가 유지된다. (1 reference bit + 2 history bit)

타이머 인터럽트마다 모든 참조 비트의 값을 복사하고 0으로 설정한다.

각각의 복사한 페이지의 메모리에 대해, 비트 중 하나가 1인 경우, 이는 working set에 있는 페이지이다.

정확도를 높이기 위해선 타이머 인터럽트 주기와 비트의 개수를 늘리면 된다.

 

 

 

Page Fault Frequency

페이지폴트의 빈도를 계산하는 것이 WSS보다 더 직접적인 접근 방식이다.

허용 가능한 페이지 폴트 빈도 (PFF) 비율을 설정하고 로컬 교체 정책을 사용한다.

 

실제 비율이 너무 낮으면 프로세스는 프레임을 잃는다.

실제 비율이 너무 높으면 프로세스는 프레임을 얻는다.

 

page fault의 빈도는 working set과 비례한다.

프로세스의 작업 집합과 페이지 폴트 비율은 시간이 지남에 따라 변화한다.

시간에 따라 피크와 골짜기가 나타난다.

 

 

 

Allocating Kernel Memory

커널 메모리는 사용자 메모리와 다르게 처리된다.

free-memory pool에서 할당되는데, 다양한 크기의 구조체를 위해 메모리를 요청하고, I/O와 같은 일부 커널 메모리는 연속적이여야 한다.

다양한 크기의 메모리가 필요하기에, 페이징 시스템과 잘 맞지 않는다.

 

 

 

Buddy System

버디시스템은 메모리 할당 방법중 하나로, 고정 크기의 세그먼트(물리적으로 연속적인 페이지로 구성)에서 메모리를 할당한다.

이 시스템은 2의 거듭제곱 크기 단위로 요청을 만족시키는 power-of-2 allocator를 사용한다.

 

예를 들어, 커널이 21KB를 요청할 경우 사용 가능한 청크가 256KB가 있다고 하자.

256KB는 각각 128KB, 128KB로 나누어지고, 128KB는 64KB, 64KB는 32KB(21KB가 들어가기에 적절한 크기)로 나누어진다.

 

이 시스템은 사용되지 않는 청크를 빠르게 더 큰 청크로 병합할 수 있다. 하지만 메모리에 내부 조각이 생길 수 있다.

 

 

 

Slab Allocator

커널 메모리를 위한 다른 전략, 잦은 할당과 해제로 인한 메모리 조각을 줄이는데 효과적이다.

Slab : 하나 이상의 물리적으로 연속적인 페이지

Cache : 하나 이상의 slab으로 구성됨

 

각각의 고유한 커널 데이터 구조에 대해 하나의 캐시만 존재한다.

각 캐시는 객체로 채워지고, 이 객체는 해당 데이터 구조의 인스턴스이다.

 

캐시가 처음 생성될 때는 모든 객체가 free로 표시된다. 데이터 구조가 저장될 때 해당 객체는 used로 표시된다.

만약 slab이 모두 사용중인 객체로 가득 차있다면, 다음 객체는 비어있는 slab에서 할당된다. 비어있는 slab이 없다면 새로운 slab이 할당된다. 즉, slab을 새로 만든다.

 

slab allocator의 장점은 메모리 조각이 없고 메모리 요청 속도가 빠르다. 이는 공통된 크기의 객체를 반복적으로 요청하는 작업에 효율적인 메모리 관리 방법을 제공한다.

 

 

Linux에서 slab allocator를 사용한다.

예시 프로세스 디스크립터는 struct task_struct 타입으로 메모리에 1.7KB를 차지한다.

새로운 task가 생성되면 Slab Allocator는 해당 타입의 캐시에서 새로운 구조체(struct task_struct)를 할당한다. 

 

slab은 세 가지 상태중 하나가 될 수 있다.

1. Full : 모든 객체가 사용 중

2. Empty : 모든 객체가 사용 가능

3. Partial : 일부 객체는 사용 중

 

요청이 발생하면 slab allocator는 다음 순서로 동작한다.

1. Partial slab에서 사용 가능한 객체를 사용

2. 사용가능한 객체가 없다면 Empty slab에서 객체를 사용

3. 만약 Empty slab도 없다면 새로운 Empty slab 생성

 

 

 

Prepaging

프로세스 시작 시 페이지폴트가 많이 발생하는 것을 줄이기 위해 사용되는 기법

프로세스가 참조할 페이지의 전부 또는 일부를 미리 로드한다.

그러나 만약 미리 로드한 페이지가 사용되지 않는다면 I/O와 메모리가 낭비된다.

 

따라서 s페이지를 미리 로드하고 그 중 a만큼 페이지가 실제로 사용된다고 가정했을 때,

비용이 s*a < s(1-a) 인 경우, prepaging은 손해가 된다.

 

실행 파일에 대한 prepaging은 예측하기 어렵지만 데이터 파일에 대한 prepaging은 예측이 가능하고, 순차적 접근의 경우에는 더욱 그렇다.

 

 

 

Page Size

OS 디자이너가 선택할 수 있는 중요한 부분으로, 특히 커스텀 빌드된 CPU에서 실행 중인 경우가 그렇다. 페이지 크기 선택은 다음을 고려해야한다.

Fragmentation(조각) : 작을수록 좋음

Page table size : 클수록 좋음

Resolution(주소 공간의 분해능력) : 작을 수록 좋음

I/O overhead : 크면 횟수 측면에서 좋고, 작으면 양 측면에서 좋음

Number of page faults : 클수록 좋음

Locality : 작을 수록 좋음

TLB size and effectiveness : 클 수록 좋음

 

일반적으로 페이지 크기는 항상 2의 거듭제곱이고, 4KB ~ 4MB 사이에서 결정된다.

 

 

TLB Reach : TLB로 접근 가능한 메모리 양, TLB Size * Page Size

프로세스의 작업 세트(한 시점에서 프로세스가 참조하는 페이지의 집합)가 TLB 내에 모두 저장될 수 있다면 이상적인 상황이다.

그렇지 않으면 페이지 폴트가 빈번하게 발생할 수 있어서 성능이 저하된다.

 

페이지 크기를 늘리면 TLB Reach를 증가시킬 수 있지만, 이는 모든 애플리케이션이 큰 페이지 크기를 필요로 하는 것은 아니므로 내부 조각을 증가시킬 수 있다.

 

따라서 여러 페이지 크기를 제공하면 더 큰 페이지 크기를 필요로 하는 애플리케이션들이 이를 사용할 수 있는 기회를 제공하면서 조각을 증가시키지 않는 방법을 제공할 수 있다. 이렇게 TLB Reach를 증가시키고 메모리 관리 효율성을 유지할 수 있다.

 

 

 

I/O interlock

 

I/O interlock은 페이지가 메모리에서 잠겨야 하는 경우를 나타낸다. 예를 들어서 파일을 디바이스로부터 복사하는 작업이 진행되는 동안 해당 작업에 사용되는 페이지는 입출력 작업이 완료될 때까지 필요하기 때문에 메모리에서 제거되지 않도록 잠겨야 한다.

 

Pinning은 특정 페이지를 메모리에서 제거되지 않도록 고정하는 것을 의미한다. 

 

 

** I/O 버퍼를 사용할 때 페이지가 교체되면 문제가 발생하는 것을 해결하는 방법은 두 가지이다.

1. I/O 를 사용자 메모리가 아닌 커널 영역에서 수행 (double buffering)

2. 페이지 교체가 안되도록 잠금 (pinning)