[OS] 여유 공간 관리

빈 공간은 다양한 크기의 작은 조각으로 분할되어 결국 단편화 된다. 빈 공간들의 전체 크기가 요청된것보다 크더라도 하나의 연속된 영역이 존재하지 않으면 요청은 실패할 수 있다.

 

이 경우 빈 공간의 전체 크기는 20바이트이다. 하지만, 10바이트 짜리 두조각으로 나누어져 있다. 결국은 20바이트의 빈 공간이 있지만 실제로는 11바이트 이상의 요청들은 실패하게된다. 이를 해결해보고자 한다.

저수준 기법들

분할과 병합

빈 공간 리스트는 빈 공간들의 집합이다. 이 힙의 빈 공간 리스트에는 2개의 원소가 존재한다.

하나는 10바이트 세그먼트 (바이트 0~9) 다른 하나는 (20~29)

위의 그림에서 10바이트 이상의 요청이 온다면 모두 실패할것이다. 하지만 더 작은 요청이라면 어떻게 될까?

 

분할이 일어난다. 유일하게 변경사은 20이 아닌 21로 시작한다는 점이다.

병합 : 메모리 청크가 반환할때 병합

새로 해제된 빈 공간이 인접해 있다면 하나의 더 큰 빈 청크로 병합한다.

기본 전략

최적 적합(Best Fit)

빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 청크를 찾는다. 그 후 그중에서 가장 작은 크기의 청크를 반환한다.

• Size가 N이상인 가장 작은 hole을 찾아서 할당
• Hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야함 / 성능 저하 유래
• 많은 수의 아주 작은 hole들이 생성됨

최악 적합 (Worst Fit)

가장 큰 빈 청크를 찾아 요청된 크기만큼만 할당

• 가장 큰 hole에 할당
• 역시 모든 리스트를 탐색해야함
• 상대적으로 아주 큰 hole들이 생성됨

최초 적합(First Fit)

간단하게 요청보다 큰 첫번째 블럭을 찾아서 요청만큼 할당

• Size가 N이상인 것 중 최초로 찾아지는 Hole에 할당
• 속도가 빠르다 / 빈 공간 리스트 전체를 탐색할 필요가 없다.

위에서 설명한 기본적인 접근 방식 외에도 메모리 할당을 향상시키기 위한 기술과 알고리즘이 몇가지 존재한다.

그 중 몇가지만 보고자 한다.

그외 전략

개별 리스트

특정 응용 프로그램이 한두 개 자주 요청하는 크기가 있다면, 그 크기의 객체를 관리하기 위한 별도의 리스트를 유지.

장점은 분명하다. 단편화의 가능성을 크기 줄일 수 있고 리스트 검색이 필요하지 않으므로 신속히 처리가 가능하다.

하지만 지정된 크기의 메모리 풀과 일반적인 풀에 얼마만큼의 메모리를 할당해야하는지 정하기 어렵다.

슬랩 할당기

슬랩(Slab): 동일한 크기의 객체들을 저장하기 위한 메모리 블록

캐시(Cache): 특정 객체 타입마다 관리되는 슬랩들의 묶음

슬랩 할당기는 미리 여러 개의 객체를 할당해 두고(pre-allocation), 필요할 때 꺼내 쓰는 방식 (object pool과 유사)

• 운영체제는 슬랩이라는 고정 크기의 메모리 블록을 관리함
• 슬랩 안에는 여러 개의 동일한 크기의 객체들이 미리 생성되어 있음
• 어떤 구조체를 할당할 일이 생기면:
  • 슬랩 캐시에서 초기화된 객체를 하나 꺼내줌
• 사용이 끝나면 해당 객체는 다시 캐시로 반환되며 재사용됨