[OSTEP 가상화(virtualization)]빈 공간 메모리 관리

📝서론 : 세그먼트의 단점

이번 장에서는 세그먼트에서 발생한 빈 공간인 외부 단편화 관리에 대해 알아볼 것이다. 

빈 공간을 어떻게 관리할까?
- 가변 크기의 요구를 충족시켜야 할 때, 빈 공간은 어떻게 관리하지?
- 단편화를 최소하하기 위해 어떤 전략을 사용하지?
- 여러 대안들의 시간과 공간적 오버헤드는 얼마지?

 

📝시작 전 가정

• malloc() 과 free() 에서 제공하는 것과 같은 기본 인터페이스를 가정한다.
• 힙의 빈 공간을 관리하기 위해 링크드리스트를 사용한다.
  • 물론, 빈 공간을 표현할 수 있는 자료구조면 어떤 것이든 가능하다.
• 클라이언트에게 할당된 메모리는 다른 위치로 재배치될 수 없다고 가정 한다.

 

 

📝20.2 저수준 기법들

분할(splitting) 및 병합(coalescing)에 대해 알아보자

 

분할과 병합

빈 공간 리스트는 힙에 있는 빈 공간들의 집합이다. 30바이트의 힙이 있다고 가정하자.

이 힙의 빈 공간 리스트에는 2개의 원소가 있다. 하나는 첫 번째 10바이트의 빈 세그먼트를 설명하고 다른 하나는 나머지 빈 세그먼트를 표현한다.

그렇다면 빈 공간 리스트는 아래 그림처럼 표현할 수 있다.

• 10 바이트가 들어올 시 : 앞 빈 공간 혹은 뒤 빈 공간을 선택
• 10 바이트 초과시 : 요청 실패
• 10 바이트보다 작으면 : ?

여기 10바이트를 초과하는 모든 요청을 실패하여 NULL을 반환한다. 10 바이트에 대한 요청은 둘 중 하나 선택하면 되기에 쉽게 충족된다. 그렇다면 10바이트보다 작은 요청은 어떻게 될까?

 

분할(splitting)

메모리에 1바이트만 요청했다고 가정하자. 이 경우 할당기는 분할로 알려진 작업을 수행한다.

요청을 만족시킬 수 있는 빈 청크를 찾아 이를 둘로 분할한다. 첫 번째 청크는 호출ㅈ자에게 반환되고, 두 번째 청크는 리스트에 남게 된다. 따라서 위의 예에서 1바이트 요청이 발생하면 리스트의 두 번째 원소를 사용하여 요청을 충족시킨다면 아래와 같다.

기본적인 리스트이 모습은 바뀌지 않고 빈 공간이 20이 아니라 21에서 시작한다는 것과 길이가 9가 된 것을 확인할 수 있다.

 

분할에 당연히 동반되는 기법은 빈 공간의 병합(coalescing) 이다.

다시 예시를 확인해보자 만약 free(10)을 호출하여 힙 중간의 공간을 반환한다면 아래 리스트처럼 된다.

이렇게 되면 힙 전체가 비어있지만, 청크가 3개로 나누어져 있기에 20바이트 요청은 실패한다.

이를 해결하기 위해 메모리 청크가 반환될 때 빈 공간들이 합쳐진다. 

• 메모리 청크를 반환할 때 해제되는 청크의 주소와 바로 인접한 빈 청크의 주소를 살피게 된다.

📝할당된 공간의 크기 파악

malloc 라이브러리는 해제되는 메모리 영역의 크기를 신속하게 파악하기 위해 추가 정보를 헤더 블럭에 저장한다.

 헤더 블럭은 메모리에 유지되며 보통 해제된 청크 바로 직전에 위치한다.

 

예시를 한번 봅시다. 이번에는 ptr이 가리키는 크기 20바이트의 할당된 블럭을 검토합니다. 

위의 그림처럼 헤더를 유지하며 할당된 공간의 크기를 저장합니다.

또한 해제 속도 향상을 위해 포인터, 무결성 검사를 위한 매직 넘버 같은 기타 정보도 저장합니다.

 

📝빈 공간 리스트 내장

지금까지 우리는 간단한 빈 공간 리스트의 개념을 다루었습니다. 이러한 리스트를 빈 공간에 어떻게 구현할까요?

보통 새로운 노드를 위한 공간이 필요하면 malloc()을 호출합니다. 그러나 해당 라이브러리 루틴에서는 이것이 불가능하기에 대신 빈 공간 내에서 리스트를 구축해야합니다.

하나의 빈 청크만 가진 힙입니다. 해당 힙은 헤더를 제외한 나머지 공간들이 빈 공간 리스트가 됩니다.

여기에 100바이트 메모리 청크를 요청한다면 어떻게 될까요?

 

4KB의 청크에서 힙 + 할당된 바이트가 때질겁니다. 즉 100을 할당한다면 헤더(8바이트) + 100바이트가 때어지며 

남은 빈 공간 리스트는 3980(4088 - 108)이 될 겁니다. 

그렇다면 100바이트씩 할당된 3개의 공간을 넣으면 100 + 헤더(8)이 3개있다는 뜻입니다.

그렇다면 여기서 free() 를 통해 일부 메모리를 반환하면 어떻게 될까요?

위 사진처럼 진행 되기에 중간에 비워버린 100바이트 단편화가 발생한다.

해결책은 아주 간단한데 리스트를 순회하면서 인접한 청크를 병합하면 된다.

 

📝힙의 확장

이제 마지막 주제를 다루자 힙 공간이 부족한 경우 어떻게 해야할까?

가장 쉬운 방법은 단순히 실패를 반환하는 것이다. 이것은 매우 유효한 방법이라 할 수 있다.

 

📝기본 전략

일부 기법에 대해 간략히 살펴보았다.

기본 전략들은 여러분들이 스스로 생각해 낼 수 있을만큼 매우 간단하다.

이상적인 할당기는 속도가 빠르고 단편화를 최소로 해야하지만 불행하게도 할당과 해제 요청 스트림은 무작위, 결국 프로그래머에 의해 결정된다. 어느 특정 전략도 잘 맞지 않는 입력을 만나면 성능이 안좋아진다. 

 

최적 적합(Best Fit)

• 빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾는다.
• 후보자 그룹 중에서 가장 작은 크기의 청크를 반환한다.
• 빈 공간 리스트를 한 번만 순회하면 반환할 정확한 블럭을 찾을 수 있다.
• 항상 전체를 검색하기에 성능 저하가 발생한다.

최악 적합(Worst Fit)

• 빈 공간 리스트를 검색하여 가장 큰 빈 청크를 찾아 요청된 크기 만큼만 반환
• 남은 부분은 빈 공간 리스트에 꼐속 유지한다.
• 수많은 작은 청크 대신에 커다란 빈 청크를 남기려고 하는 시도이다.
• 다시 한 번 항상 빈 공간 전체를 탐색하기에 높은 비용이 든다.

최초 적합(First Fit)

• 첫 번재 블럭을 찾아서 요청만큼 반환한다.
• 장점은 속도가 빠르다는 것이다. 빈 공간 천제를 탐색할 필요가 없기 때문이다. 
• 때때로 리스트의 시작에 크기가 작은 객체가 많이 생길 수 있다. 
• 빈 공간 리스트의 순서를 관리하는 것이 쟁점이다
  • 주소-기반 정렬을 사용하여 순서 관리를 할 수 있다.

다음 적합(Next Fit)

• 항상 리스트의 처음부터 탐색하는 대신 다음 적합 알고리즘은 마지막으로 찾았던 원소를 유지한다.
• 아이디어는 빈 공간 탐색을 리스트 전체에 더 균등하게 분산시키는 것이다.
• 리스트의 첫 부분에서만 단편이 집중적으로 발생하는 것을 방지한다. 

개별 리스트

 

• 자주 요청되는 특정 크기의 메모리 블록을 위한 별도의 리스트를 유지합니다.
• 장점: 단편화 감소, 빠른 할당/해제.
• 단점: 각 크기별 메모리 풀을 얼마나 할당할지 결정이 필요.

이진 버디 할당기

• 요청을 충족시키기에 충분한 공간이 발견될 때까지 빈 공간을 2개로 계속 분할한다.
• 2의 거듭제곱 크기만 할당할 수 있기 때문에 내부 단편화가 생길 가능성이 높다.
• 병합할 때 너무 편해서 좋다.

📝기타 아이디어

앞에서 설명한 접근 방식들의 문제점은 확장성이다. 빈 공간들의 개수가 늘어남에 따라 리스트 검색이 매우 늘어진다.

더 정교한 할당기는 복잡한 자료 구조를 통해 비용을 줄인다. 단순함과 성능을 교환하는 것

 

현대 시스템은 멀티프로세서 및 멀티쓰레드로 작동되기에 최적화에 대한 노력이 많이 있었다.

 

 

📝요약

📌 세그먼트의 단점 및 빈 공간 관리 개요

• 문제: 가변 크기 메모리 요청에 따른 외부 단편화 발생.
• 목표: 단편화를 최소화하며, 빠르고 효율적인 메모리 할당/해제를 구현하는 것.

---

🔧 1. 저수준 기법: 분할(Splitting)과 병합(Coalescing)

• 분할: 큰 빈 공간에서 일부만 할당 요청 시, 나눠서 일부는 반환, 나머지는 빈 공간 리스트에 유지.
• 병합: 메모리 반환 시 인접한 빈 청크들을 하나로 합쳐 큰 공간을 확보.
• 헤더 블럭: 할당 크기 등 정보를 저장하여 빠른 병합과 무결성 검사에 사용.

---

🧱 2. 빈 공간 리스트 구현

• 기본 개념: 빈 공간들을 리스트로 관리. malloc 내부에서는 malloc 호출이 불가하므로 빈 공간 내부에 리스트 내장.
• 예시: 4KB 힙에서 100바이트씩 3개 할당 후, 중간을 반환 시 단편화 발생 → 병합으로 해결.

---

📈 3. 힙 확장

• 전략: 공간 부족 시 요청 실패 반환이 가장 단순한 대응책.
• 현실: 대부분 동적 힙 확장(syscall 등)을 통해 공간 확보.

---

⚙️ 4. 기본 메모리 할당 전략

전략명 설명 장점 단점

최적 적합 (Best Fit)	가장 작은 적합 공간을 찾아 할당	공간 효율적	리스트 전체 탐색 필요
최악 적합 (Worst Fit)	가장 큰 빈 공간을 찾아 일부만 할당	큰 청크 유지 가능	리스트 전체 탐색 필요
최초 적합 (First Fit)	첫 번째로 맞는 공간을 빠르게 할당	빠름	앞부분 단편화 가능성
다음 적합 (Next Fit)	이전 검색 위치 이후부터 탐색 시작	탐색 분산	균형성은 보장되진 않음
개별 리스트	크기별로 리스트를 구분하여 관리	빠른 접근, 단편화 감소	크기별 리스트 구성 어려움
버디 할당기	2의 거듭제곱 크기로 나누고 병합하여 관리	병합 용이	내부 단편화 가능성 있음

---

🧠 5. 고급 기법 및 확장성 문제

• 단순한 리스트 기반 기법은 확장성에 한계가 있음.
• 해결책: 트리, 힙, 해시 등 정교한 자료구조 활용하여 검색 비용 감소.
• 멀티스레드 환경 고려: 병렬 처리 및 락 최소화를 위한 별도 최적화 필요.