메모리 할당과 단편화
이번 시간에 메모리 할당과 단편화에 대해서 배워보자.
메모리 할당
메모리 할당은 프로세스를 메모리에 할당하는 것
을 의미한다. 메모리 공간을 할당할 때 빈곳이 여러개라면, 어디에 할당을 해야할지 정해야 한다.
공간을 할당한다는 것은 메모리를 어떻게 분할(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
'CS > OS' 카테고리의 다른 글
세그멘테이션과 페이징 (0) | 2021.12.17 |
---|---|
스와핑 (0) | 2021.12.17 |
주소 바인딩 (0) | 2021.12.17 |
교착상태와 기아상태 (0) | 2021.12.15 |
프로세스 동기화 (0) | 2021.12.10 |