가상 메모리 : 파편화와 Fit 전략

단편화부터 다룸

• Internal Fragmentation : 내부 단편화
  • 내부 단편화는 할당된 메모리 공간이 프로세스가 실제로 필요로 하는 양보다 커서 발생하는 메모리 낭비 현상이다.
    • 프로세스에 필요한 양보다 더 큰 메모리가 할당되어 사용되지 않는 공간이 생긴다.
    • 할당된 메모리 블록 내부에서 발생하는 낭비를 말하며, 내부가 여기서 이름이 유래 된 것이다.
    • 주로 고정 크기 할당 방식인 페이징에서 발생한다.
    • 예를 들어, 최소 단위는 10KB인 상황에서 3KB만 필요하더라도 할당되면 7KB가 낭비 되는 것.
• External Fragmentation : 외부 단편화
  • 총 남은 메모리는 충분하지만, 연속하지 않은 조각으로 나뉘어 있어 필요한 크기의 메모리를 할당 할 수 없는 현상이다.
    • 메모리의 할당과 해제가 반복되면서 중간중간에 작은 빈 공간이 생성된다.
    • 이러한 분산된 공간들의 총합은 충분하지만, 연속되지 않아서 사용 할 수가 없다.
    • 외부라는 이름은 사용할 수 없는 메모리가 할당된 영역 밖에 있다는 의미에서 유래되었다.
    • 예를 들어, 3KB가 3개 빈 공간 있지만 총 9KB가 있어도 4KB를 할당 할 수가 없다.

페이징은 외부 단편화를 해결하지만 내부 단편화는 여전히 발생시킨다.
세그먼테이션은 내부 단편화를 줄이지만 외부 단편화 문제가 남는다.

메모리 단편화 문제를 해결하는 방법?

다양한 방법이 있다.

[외부 단편화 해결 #1] 후 수습 방법 #1 | 압축, Compaction

• 분산된 빈 공간을 하나로 모으는 방식이다.
• 프로세스를 재배치하여 작은 빈 공간들을 큰 공간으로 통합한다.
• 일종의 Garbage Collection 작업이다.
• 재배치 과정에서 오버헤드가 많이 발생 할 수 있다.

[외부 단편화 해결 #2] 후 수습 방법 #2 | 통합, Coalescing

• 인접한 빈 메모리 블록들을 병합하여 하나의 큰 블록으로 만드는 방법이다.
• 메모리 해제 시, 즉시 주변 빈 블록들과 병합된다는 점에서 상수 시간 병합이라는 장점이 있다.
• 재배치 없이 인접 공간들만 통합하는 점이 다르다.

[외부 단편화 해결 #3] 시스템에서 채택하는 분할 기법 #1 | 페이징, Paging

• 프로세스를 고정 크기 페이지로 나누고 물리 메모리도 같은 크기의 프레임으로 분할한다.
• 불연속적 메모리 할당으로 외부 단편화를 해결한다.
• 페이지 테이블을 통해 가상 주소와 물리 주소를 매핑한다.
• 내부 단편화 문제는 여전히 남는다.

[내부 단편화 해결 #1] 시스템에서 채택하는 분할 기법 #2 | 세그멘테이션, Segmentaition

• 서로 다른 크기의 논리적 단위(세그먼트)로 메모리를 분할한다.
• 프로세스 특성에 맞는 크기로 할당하여 내부 단편화를 감소 시킬 수 있다.
• 외부 단편화 문제 가능성이 있다.

[내부, 외부 단편화 모두 해결 #1] 메모리 풀, Memory Pool

• 필요한 크기의 메모리 블록을 미리 할당 해놓고 필요시 사용하고 반납한다.
• memory pool이라 불리는 동일 사이즈 메모리 블록들을 미리 할당한다.
• 필요한 크기만큼 할당하여 내부 단편화를 방지한다.
• 고정된 크기에서 할당/해제가 이루어져 외부 단편화를 방지한다.
• 메모리 할당/해제가 빈번 할 때 효과적이다.
• 미리 할당으로 인한 메모리 누수 가능성을 염두해야한다.

할당 이전에 적용되는 배치 전략

First-Fit

• 빈 블록 목록의 첫 번째부터 시도하며, 처음으로 크기가 충분한 블록을 찾아 할당하는 원리이다.
• 검색 시간이 비교적 짧고, 빈 블록을 리스트 앞에서 채우니 지역성을 확보하기에도 적합하다.
• 단편화 성과
  • 외부 단편화가 어느정도는 발생한다.
  • 잔여 블록이 많아 힙 후반부에 조각화가 누적 될 수 있다.

Next-Fit

• 검색을 마지막 할당 위치부터 시작하는 부분에 있어 First-Fit과 유사하나 동작 원리는 다르지 않다. 찾지 못하면 앞부분에서 돌아가서 다시 탐색한다.
• First-Fit에 비해 항상 앞만 스캔하는 것이 아니니 탐색 영역이 분산된다. 과도한 전방 조각 집중이 완화되는데 기여한다.
• 단편화 성과
  • First-Fit보다 약간 높은 외부 단편화 경향이 있다.
  • 하지만 항상 맨 앞만 쓰는 편향이 줄어들어, 장기적으로 검색 비용이 일정선에서 안정된다.

Best-Fit

• 빈 블록 중 요청 크기에 가장 근접한 블록을 찾아 할당한다.
• 이론적으로는 외부 단편화를 줄일 수 있다.
• 단편화 성과
  • 외부 단편화는 위의 두 Fit 전략들보다 낮은 편이다.
  • 그러나 너무 작은 잔여 블록이 많이 쌓이면, 내부 단편화와 초소형 조각들 때문에 관리 오버헤드가 증가한다.

Worst-Fit

• 빈 블록 중에서 가장 큰 블록을 골라 일부를 잘라 할당한다.
• 남은 조각 크기가 커서, 이후에 큰 요청을 받아들일 가능성이 증가한다.
• 단편화 성과
  • 뜻 밖에도 외부 단편화가 심해지는 경향성을 가진다.
  • 큰 블록을 계속 잘라쓰다 보면, 중간 크기 조각이 다수 발생하고 오히려 관리가 어려워진다.