메모리 할당과 단편화

메모리 할당과 단편화

이번 시간에 메모리 할당과 단편화에 대해서 배워보자.

메모리 할당

메모리 할당은 프로세스를 메모리에 할당하는 것을 의미한다. 메모리 공간을 할당할 때 빈곳이 여러개라면, 어디에 할당을 해야할지 정해야 한다.

공간을 할당한다는 것은 메모리를 어떻게 분할(partition)할 것인지와 연관이 있는데 두 가지 방식이 있다.

고정 분할

고정 분할은 말 그대로 메모리를 똑같은 고정된 크기로 분할하는 것을 의미한다. 각 분할마다 하나의 프로세스를 가진다. 고정 분할 방식을 사용하면 내부 단편화가 발생할 수 있다.

가변 분할

가변 분할은 메모리의 어떤 부분이 사용되고 있고, 어떤 부분이 사용되고 있지 않은가를 파악할 수 있는 테이블을 유지하여 관리하는 기법이다. 초기에 모든 메모리 공간은 한 개의 큰 사용 가능한 블록으로 간주된다. 이 경우 한 개의 공간(hole)이 있다고 간주한다. 이 hole 이라는 개념은 메모리 할당에서 자주 등장하는 단어이다.

• 프로세스가 시스템에 들어오면 입력 큐(input queue)에 넣는다.
• 운영체제는 각 프로세스가 메모리를 얼마나 요구하며, 또한 사용 가능한 메모리 공간이 어디에 얼마나 있는지를 고려하여 메모리 공간을 할당한다.

가변 분할에서 일반적으로 메모리는 다양한 크기 공간(hole)들이 존재한다. 프로세스가 공간(hole)을 필요로 할 때 운영체제는 이 공간들 중 적절한 것을 찾아내야 한다.

따라서, 프로세스가 메모리를 할당받기 위해 어떤 식으로 적절하게 찾아줄것인지가 중요하다. 여기서 세 가지 개념이 등장한다.

최초 적합

최초 적합(First Fit)은 최초로 발견되는 가용 가능한 hole 에 할당하는 방법을 의미한다.

최적 적합

• 최적 적합(Best Fit)
  • 가장 적합한 가용 가능한 hole 을 찾아서 할당하는 방법을 의미한다.
  • 리스트가 크기 순으로 정렬되어 있지 않으면 전 리스트를 검색해야 한다.
    • 가장 적합한 리스트를 찾기 위해서 검색이 필수다.
  • 외부 단편화의 발생이 가장 적은 곳을 찾아서 할당하는 방법을 의미한다.

최악 적합

• 최악 적합(Worst Fit)
  • 무조건 그냥 제일 큰 공간에 할당한다.
  • 최악 적합의 아이디어는 할당해주고 남은 자유 공간(free hole)은 충분히 커서 다른 프로세스들의 위해서 유용하게 사용될 수 있다는 것이다.
  • 말 그대로 최악이다.

모의 실험결과 First Fit 과 Best Fit 이 Worst Fit 보다 속도나 메모리 사용률 측면에서 더 좋다고 결과가 나왔다.

그럼 First Fit 과 Best Fit 중에서 뭐가 더 낫냐? 속도 측면으로만 봤을 땐 당연히 First Fit 이 빠르다. 적합한 hole 을 찾기 위해 검색이 필요 없기 때문이다.

First Fit 을 쓰던 Best Fit 을 쓰던 딱 맞는 크기가 아니면 외부 단편화(External Fragmentation)는 발생한다. 외부 단편화가 발생한다는 것은 결국 메모리 낭비이다. 따라서 새로운 방법을 만드는데 그것이
페이징(Paging) 이다.

프로세스 단위의 스와핑도 그랬고, 메모리 공간 할당도 프로세스 크기별로 할당하였다.

단편화

앞서 배운 외부 단편화(External Fragmentation)는 공간 중 일부가 사용 못하게 되는 부분을 의미한다.
단편화의 크기에 따라서 최초 적합이 더 좋을 수도 있고, 최적 적합이 더 좋을 수도 있다. 어쨋든 둘 중 어떤 알고리즘을 사용하더라도 외부 단편화 문제를 피할 수는 없다.

최초 적합에서 50% 규칙(50-percent rule)이라는 말이 있다. N 개의 블록이 할당되었을 때 0.5N 개의 블록이 단편화 때문에 손실될 수 도 있다는 통계적인 분석에서 나온말이다.

메모리 공간을 낭비하는 현상인 단편화는 내부에서도 발생할 수 있는데, 이것을 내부 단편화라고 한다. 내부 단편화는 고정 분할방식에서 발생한다.

외부 단편화는 가변 분할 방식에서 발생할 수 있다는 것을 위에서 배웠다.

내부 단편화는 다음과 같은 상황에서 발생한다.

예를들어 Process-1 이 요구하는 메모리 공간을 딱 6등분 한다고 가정하자. 근데 한 블록의 크기는 균등하게 5등분한 블록보다 조금 클 수 있다. Process-1 자체가 정확히 6등분 된다는 보장이 없다. 몇 등분을 하던, 한 블록에 대해서 자유 공간(free hole)이 생길 가능성이 있다는 것이다.

근데, 외부 단편화와 비교해보면 그래도 내부 단편화가 자유 공간이 훨씬 적게 발생할 거라는 것을 알 수 있다.

따라서, 외부 단편화 문제를 해결하기 위해서 고정 분할 방식을 이용한 페이징(Paging)이 등장한 것이다.

References

• 운영체제 9th edition
• https://jhnyang.tistory.com/264