[운영체제/OS] Frames Allocation Algorithm, Kernel Memory Allocation

동시에 동작하는 여러 프로세스에게 제한된 가용 메모리를 효과적으로 할당해야 합니다.

그래서 각 프로세스에게 할당되는 메모리 프레임 수를 정해야 합니다. (독점이나 starvation 등의 문제 방지)

 

-프로세스당 최소한의 프레임 수

프로세스에 할당되는 프레임 수가 감소하면 page fault 발생 확률이 늘어나 성능 감소.

명령어 실행 완료 전에 page fault가 발생하면 그 명령어 재실행 필요.

-프로세스당 최대한의 프레임 수

물리 메모리에 의해 결정된다.(답이 없고 OS가 프로세스에 무리없도록 알아서 할당)

 

Allocation Algorithm

-Equal Allocation(동등 할당) : 100 frames을 5 프로세스에게... 각 프로세스에게 20 프레임 할당

  나눗셈으로 남는 애들은 buffer pool에 넣어둔다.

-Proportional Allocation(비례 할당) : 프로세스의 크기에 비례하게 프레임 할당

  s = 프로세스 pi의 사이즈

  S = 총 s의 합

  m = 프레임 총 개수

  ai = 프로세스 pi에 할당하는 프레임 수  = si/S * m

-Priority Allocation : 가중치에 따라 가중치 큰 애에겐 큰 값 곱하고, 가중치 작은 애에겐 작은 값 곱한다.

 

Global vs Local Allocation

-Global Replacement : 일반적으로 더 많이 사용한다.

전체 프레임에서 replacement frame을 프로세스가 고른다. 자주 사용하는 프로세스들을 위해 효율적이지만 독점의 문제가 발생할 수 있다.

-Local Replacement : 각 프로세스는 각 할당된 프레임 set에서만 고를 수 있다. 자주 사용하는 프로세스들이 계속된 page fault와 replacement가 발생할 수 있다.

 

Non-Uniform Memory Access (NUMA)

메모리로의 각 접근 속도가 다르다. 

가장 최적의 수행은 CPU에 가까운 메모리를 할당해주는 것입니다.

 

 

Thrashing

 프로세스가 swap in out으로 인해 바빠질 때 발생하는 문제입니다.

허용 가능한 메모리를 초과한 경우 page fault가 발생합니다. 이것이 빈번해지면 page fault 비율은 상당히 높아지죠.

이는 낮은 CPU 성능으로 이어집니다. 

Demand Paging 기법은 Locality 기반의 모델이기에 반복적으로 참조가 될 수 있습니다. 자기에게 할당된 physical 프레임 set에서 골라야하기 때문입니다.

이때 "locality의 총 크기 > 전체 메모리 크기" 하면 thrashing이 발생합니다.

 

Working-set Model

OS는 thrashing이 발생 안 하도록 예의주시하는데 이를 위해 쓰는 모델입니다.

일정 period 시간 간격동안 프로세스가 x개

WSSi(working set of Process Pi) = 최근시간에 참조된 페이지의 총 개수

D = WSSi의 총 합 = 총 demand frames (locality값)

만약 D > m (total memory size) --> thrashing 발생  (D<m이라면 더 생성해도된다)

그러므로 프로세스 개수를 줄여야한다. 프로세스 중 하나를 suspend나 swap out.

 

Working set을 추적해서 최적으로 만드는 것이 OS의 역할입니다.

예를 들어 10000 instructions일 때, ref bit가 1이면 페이지 참조된 것이고 0이면 참조되지 않은 것이다.

정확성을 높이려면 reference bits개수를 늘인다.

 

Page-Fault Frequency

PFF가 너무 낮으면 프로세스는 frames을 잃는다. 다른애한테 주려면 global replacement 시스템에서만 가능하다.

PFF가 너무 높으면 프로세스는 frames을 더 할당한다.

 

working sets and page fault rates

프로세스가 처음 실행될 땐 demand paging에 의해 page fault가 게속 발생하며, physical memory로 다 불러온 후에는 page fault가 점점 줄어듭니다.

 

Kernel Memory 할당

커널 메모리는 보통 사용자 모드 프로세스와 달리 별도의 메모리 풀에서 할당하는 정책을 사용합니다.

커널은 다양한 자료구조를 사용합니다.

사용자 모드 프로세스의 페이지와 달리, 물리 메모리에 직접 접근하는 장치는 물리적으로 연속적인 메모리를 필요로 하는 경우가 있습니다.

 

Buddy System Allocator

256kB는 물리적으로 연속적인 페이지입니다. 이 쪼개진 조각들을 buddy라고 합니다.

장점: 나중에 할당 후 phy mem 반납시 용이하다. 256kB를 원상 복구할때 연속적 모으기를 통해 용이하다.

단점: 외부단편화 발생 가능.

 

 

Slab Allocator

슬랩(Slab)은 하나 또는 그 이상의 연속된 페이지들로 구성됩니다.

캐쉬(Cache)는 하나 혹은 그 이상의 슬랩으로 구성됩니다.

각 커널 구조마다 캐쉬가 존재합니다. 

리눅스 슬랩 상태는 Full(슬랩모두사용), Empty(슬랩사용x), Partial(슬랩일부사용)

 

Slab Allocator

Full인데 slab을 더 써야한다면 추가적인 slab을 할당해줍니다. Partial Slab 할당 후 Empty Slab을 할당해줍니다.