[Windows]heap에 관한 화제

출처 : http://www.geocities.jp/i96815/windows/win11.html

개요

이 기사에서는 Windows 에 있어서의 힙 메모리의 사용법과 주의점에 대해 기재한다.
·         heap란 무엇인가
·         프로세스 heap과 private 힙
·         단편화
·         MP Heap

---

heap란 무엇인가

Win32의 메모리 할당 함수를 크게 2종류로 분류한다. 하나는 VirtualAlloc계 또 하나를 HeapAlloc계로 한다.

VirtualAlloc 계	가상 메모리의 직접적인 할당.  VirtualAllocEx 등.
HeapAlloc 계	Heap으로 부터의 메모리 할당.  GlobalAlloc, LocalAlloc 등도 이쪽에 포함한다. 그리고 CRT (C Runtime)의 할당은 이쪽 위에 구축된다.

표. 메모리 할당의 분류

VirtualAlloc 계에서는 페이지 단위로 메모리를 조작한다. 이 때문에(액세스권의 설정 면에서)유연하지만 작은 메모리블록의 할당에는 적합하지 않다. HeapAlloc 계에서는 미리 어느 정도의 가상 메모리 영역을 예약해 두어 프로그램으로부터 요구가 있는 대로 그 예약된 영역으로부터 메모리를 잘라와 메모리 블록을 확보한다. 작은 메모리 블록을 다 수 할당하려면 이쪽의 방법 쪽이 효율이 좋다. Windows의 heap 매니저는 이러한 동작을 실현할 수 있도록 프로그램과 가상 메모리 매니저의 사이에 끼어들어 메모리 할당을 고속으로 실시한다.

DEP
Windows XP SP2 로부터 HeapAlloc 에 의해 할당할 수 있는 메모리(페이지)의 속성이 바뀌어 할당할 수 있는 메모리 블록에서는 실행 가능한 것은 없어졌다.  만약 실행하려고 하면 액세스 위반이 발생한다. 이 테크놀러지를 Data Execution Prevention (DEP) 이라고 한다. 자세하게는MS의 사이트를 참조.

여기서 시험삼아 heap을 사용하지 않고 가상 메모리로부터 직접 메모리를 할당했을 경우와 heap을 이용했을 경우로 할당이 속도에 어느 정도의 속도 차이가 발생하는지 비교해 본다. 사용한 샘플 코드는 이쪽.

perftest.zip

[샘플 코드, makefile 프로젝트]

Heap을 사용하는 경우는 HeapAlloc API 를 사용하고 heap을 사용하지 않는 경우는 VirtualAlloc API 를 사용 메모리를 할당 한다 (heap은 프로세스 heap를 사용하기로 한다). 할당 바이트수를 16, 32, 64, ... , 8192 과 같이 바꾸어 각각의 사이즈의 메모리 블록을 10000개 할당한다. 게다가 각각의 블록에는 x 이라고 하는 문자를 기입한다. 이 결과 다음과 같이 되었다. 물색의 막대 그래프가 HeapAlloc, 보라색의 막대 그래프가 VirtualAlloc 이다.
※ 테스트기는 Windows XP CPU: Mobile Intel(R) Pentiun(R) 4 CPU 2.8GHz HT, RAM: 1.37GB

이 테스트에서는 할당 바이트수가 1~2kb 미만에서는 특히 HeapAlloc과 VirtualAlloc의 속도 차이를 현저 것을 알 수 있다. 보통 할당 수가 10000 개 이기 때문에 HeapAlloc에 의한 할당 에서는 512 바이트 이하 에서는 계측 불능(1ms 이하)였다. 계측 할 수 있도록 하기 위한 할당 수를 늘리려고 시도했지만 같은 조건에서는 VirtualAlloc에 의한 할당이 실패하기 때문에 10000 개인 채로 했다.  어쨌든 이것으로 작은 메모리 블록을 많이 할당하는 테스트에서는 HeapAlloc은 빠른(VirtualAlloc 보다) 다는 것은 확인 할 수 있다.

---

프로세스 heap과 Private heap

프로세스의 기동 시에는 heap은 기본으로 하나 준비된다. 이것은 프로세스 heap (혹은 디폴트 heap, 프로세스 디폴트 heap 등 이라고도 말하지만 모두 같은 것) 으로 불린다.  GetProcessHeap API 에 의해 프로세스 heap의 핸들을 취득할 수가 있다.

·         GetProcessHeap

자신의 프로그램으로부터 프로세스 heap를 계속 이용하는 일도 가능하지만 퍼포먼스의 관점으로부터 heap을 독자적으로 작성해 그것을 이용하는 편이 좋은 경우가 있다. 자기 부담으로 만든 heap을 Private heap 이라고 부른다. Private heap은 HeapCreate API 로 작성할 수 있다. 작성한 heap은 HeapDestroy 으로 파기할 수 있다.

·         HeapCreate

·         HeapDestroy

Private heapdmf 작성하는 동기
heap은 기본적으로 리스트 구조를 하고 있다. 그 리스트의 정합성을 유지하기 위해서 heap은 락을 가진다(heap 락 이라고 한다). 자신의 프로그램으로부터 프로세스 heap을 이용하는 경우 프로세스 heap은 여러 가지 라이브러리로부터 이용되고 있으므로 다른 라이브러리의 호출에 의해 자신의 프로그램으로부터의 호출이 기다리게 될 가능성이 나온다. 이것이 Private heap을 작성하는 동기의 하나이다. 또 하나는 테스트 해 보면 아는 것 이지만 heap은 (정확하게 말하면 현재의 Windows의 거동(挙動)·구현에서는) 한 번 예약한 메모리 영역을 해방하지 않는다.  즉  어떤 시점에 heap A 에서 대량의 메모리 할당이 발생하면 heap A 의 사이즈는 가능한 곳까지 신장한다. 그 후 heap으로부터 할당한 메모리를 HeapFree 등으로 해방해도 그 메모리 블록은 「해방이 끝난 상태」 라고 인식되어 그 heap내에서는 이용 가능하지만 heap 전체는 예약된 채로 된다. 따라서 그 heap에 있어서의 메모리 블록을 할당하는 것은 성공하지만 그 프로세스에서의 가상 메모리 공간은 거대한 heap A 에 점거된 채로 되기 때문에 다른 메모리 조작 함수가 메모리가 부족해 실패할 가능성이 나온다. 이것을 피하기 위해서는 heap을 HeapDestroy로 heap을 파기해야 한다. 이것이 Private heap를 이용하는 동기의 둘 째 이유 이다.

조금 벗어나서 사족 이지만  어딘가의 잡지에서 「한 번 할당한 메모리는 실질적으로 두 번 다시 재이용되지 않는다」 라고 하는 것 같은 것을 읽었지만 그렇지 않다. 시험해 보면 곧바로 그것이 잘못이라고 알 것이다.

---

단편화

Heap으로부터의 메모리 할당에서는 미리 준비한 메모리 영역으로부터 메모리 블록을 잘라 사용한다고 말했다. 해방된 메모리는 재 이용된다. 그러나 단편화(fragmentation)가 진행되어 메모리의 가용 영역이 있는 것에도 불구하고 메모리 할당을 할 수 없을 가능성이 나온다.

위의 그림을 봐 주셨으면 한다.  지금 어느 특정 사이즈의 heap이 있다고 한다(통상은 필요에 따라서 heap 사이즈는 신장하지만 고정 사이즈로 하는 일도 가능).  황녹색의 영역은 빈 영역이며 적색의 부분은 사용중의 메모리 영역이다. 이 상황에서 청색의 사이즈의 메모리를 할당 하고 싶다고 생각한다. 분명하게 녹색의 총량은 청색의 그것보다 많다. 그러나 힙메모리의 할당에는 연속한 영역이 필요(동일 세그먼트(segment) 내) 하기 때문에 청색의 메모리를 할당 하는 것을 실패한다. 이와 같이 메모리가 할당 상황이 벌레가 먹은 상태로 되어 있는 것을 단편화 (fragmentation)라고 한다.

Windows XP 이후 에서는 heap의 단편화가 일어나기 어렵게 메모리 할당을 실시하도록 heap 매니저에 지시할 수가 있다. 이 기능을 LFH (Low Fragmentation Heap) 이라고 한다. LFH은 가본으로는 설정되지 않고 프로그램 중에서 HeapSetInformation API를 호출하는 것으로 유효하게 한다.

    ULONG ulEnableLFH = 2;
   
    HeapSetInformation (
        hHeap,
        HeapCompatibilityInformation,
        &ulEnableLFH,
        sizeof(ulEnableLFH));

보통 CRT에 사용되고 있는 heap도 Private heap이며  LFH는 기본으로는 유효하지 않다.  그러나 _get_heap_handle을 사용해 heap 핸들을 취득해 HeapSetInformation을 사용하면 CRT heap에 대해서도 LFH를 유효하게 할 수 있다.

특히  단편화는 어느 정도 장 시간의 운용에 의해 표면화해 오는 일이 있어 일반적으로 테스트 환경에서는 재현은 어렵다. 단편화를 피하기 위해서 배려 하는 사항으로서는 「생존 기간이 너무나 다른 메모리 블록을 같은 heap로부터 할당하지 않는(전용의 Private heap을 만든다)」「장시간 할당하는 경우는 할당하고 사이즈를 가능한 한 가지런히 한다」 일 등을 들 수 있다.

---

MP Heap

heap의 화제가 되었으므로 모처럼 이므로 MP Heap을 소개해 둔다.  위의  "Private heap을 작성하는 동기" 로 heap 조작은 락의 필요성의 관계로 병렬 조작에서 퍼포먼스 저하의 가능성에 대해 다루었다. 병렬성의 문제에 관한 heap 매니저 래퍼의 구현 예로써 이전의 SDK 샘플에는 MP Heap의 구현 샘플이 부속되어 있었다. 현재에도 아래와 같은 링크로부터 다운로드 가능하다 (또 나의 환경 에서도 빌드 가능했다).

Visual Studio 6.0 Samples
http://www.microsoft.com/downloads/details.aspx?FamilyId=AF0A6060-6566-408F-9F11-EA2C80B8CAA0&displaylang=en

이 샘플 래퍼로 제공 되는 것은 이하와 같은 함수 군이다. 이름으로부터 무엇을 하는 함수인지 상상할 수 있다고 생각한다.

·         MpHeapCreate

·         MpHeapDestroy

·         MpHeapAlloc

·         MpHeapFree

·         MpHeapValidate

·         MpHeapCompact

·         MpHeapReAlloc

·         MpHeapGetStatistics

multi-thread 애플리케이션으로 메모리 할당을 빈번하게 하는 프로그램을 쓰고 있을 때는 검토하는 것도 좋을 것이다. MS 의 사이트에서 검색해 보면 Exchange, SPS, MDAC 등으로 mpheap 라는 이름 이 나온다.

---

참고 자료

Heap: Pleasures and Pains
http://msdn.microsoft.com/library/en-us/dngenlib/html/heap3.asp

David B. Probert, Ph.D., Windows Kernel Internals User-mode Heap Manager
http://www.i.u-tokyo.ac.jp/ss/lecture/new-documents/Lectures/16-UserModeHeap/UserModeHeapManager.pdf