메모리 할당 문제, 그리고 메모리 단편화

메모리 할당 전략

현재 다음과 같이 메모리가 할당되어 있다고 가정하자.

만약 여기서, 어떤 프로세스가 세 칸의 메모리에 대한 할당을 요청했을 때, OS는 해당 메모리를 위한 빈 공간을 어떻게 지정할 수 있을까?

우리는 이 상황에서 3가지 전략 중 하나를 선택할 수 있다.
지금부터 각각 어떠한 전략인지를 알아보자.

• First-fit
• Best-fit
• Worst-fit

First-fit

• 순서대로 순회하다가, 가장 먼저 만나는 할당가능한 빈 공간을 지정한다.
  • 운이 없으면, 전체 메모리를 전부 순회해야 한다.
• 여기서는 가장 먼저 만나는 빈 공간인 4칸을 선택한다.

Best-fit

• 모든 메모리 블록 중에서, 요청된 크기를 수용할 수 있는 블록 중 가장 작은 블록을 선택한다.
  • 항상 전체 메모리를 전부 순회해야 한다.
• 여기서는 필요한 크기와 정확히 같은 3칸의 빈 공간을 선택한다.

Worst-fit

• 모든 메모리 블록 중에서, 요청된 크기를 수용할 수 있는 블록 중 가장 큰 블록을 선택한다.
  • 항상 전체 메모리를 전부 순회해야 한다.
• 여기서는 가장 넓은 공간인, 5칸의 빈 공간을 선택한다.

성능 차이 - 그렇다면 어떤 전략이 어떨 때 좋을까?

• 시뮬레이션을 통한 연구결과에서, First-fit과 Best-fit이 Worst-fit보다 시간과 메모리 효율 측면에서 좋다는 것이 입증되었다.
• Best-fit과 First-fit 간에는
  • 공간 효율성 측면에서는 어느것이 더 좋다고 말할 수는 없지만,
  • First-fit이 일반적으로 속도가 더 빠르다고 한다.
    (출처-Operating System Concepts, 9.2.2)

우리는 위와 같은 할당 전략을 차용함으로써, 사용하기 쉬운 연속된 메모리를 사용할 수 있게 되었다,
하지만, 위와 같은 전략을 사용하더라도, 다음과 같은 경우에는 빈 공간이 많더라도 빈 공간을 찾을 수 없는 문제가 발생한다. 이러한 문제를 메모리 단편화(Fragmentation)이라고 한다.

메모리 단편화가 발생한 상태.

메모리 단편화(fragmentation)

• 메모리가 파편화되어 흩어져있어
  • 신규 메모리를 할당할 공간이 충분한데도
  • 메모리를 할당할 공간을 찾지 못하는 것을 의미한다.

메모리 단편화의 종류

외부 단편화

외부 단편화가 발생한 상황.

위 그림에서 나온, 회색 할당 요청이 자신이 들어갈 공간을 찾지 못하게 되는 것을 의미한다.

이는 각자가 할당받은 공간 외부에 할당해주지 못하는 남는 공간이 있어 생기는 문제이기에 외부 단편화라고 불린다.

• 해결책 - 메모리 풀

따라서, 메모리를 할당해주기 전, 일정한 단위로 고정적으로 할당을 해주면 해당 외부 단편화 문제를 해결할 수 있다.

하지만, 이렇게 되면 3칸만 필요한 프로세스가 4칸을 할당받게 되고, 이는 할당받은 공간 내부에 할당해주지 못하는 남는 공간이 생기게 된다.

내부 단편화

내부 단편화가 발생한 상황. X표시된 의미없이 사용되지 않는 할당된 공간이 존재한다.

위 그림에서 나온, 사용되지 않는 X표시된 공간이 발생하는 것을 의미한다.

이는 각자가 할당받은 공간 내부에 할당해주지 못하는 남는 공간이 있어 생기는 문제이기에 내부 단편화라고 불린다.

• 해결책
  • 세그멘테이션
  • 가상 메모리 + 페이징
  • 메모리 압축

각 해결책에 대한 내용은, 아래 링크를 참고해주길 바란다.

1. 가상 메모리+페이징, 세그멘테이션이 쓰이지 않는 이유
2. 메모리 압축