Part16. Tutorial4-메모리 동적할당(malloc, free) 기능을 추가해 보자

kkamagui(까마귀, 한승훈) 2007. 11. 14. 06:01

2007. 11. 14. 06:01

Part16. Tutorial4-메모리 동적할당(malloc, free) 기능을 추가해 보자

원문 : http://kkamagui.springnote.com/pages/391653

들어가기 전에...

이 글은 kkamagui에 의해 작성된 글입니다.
마음껏 인용하시거나 사용하셔도 됩니다. 단 출처(http://kkamagui.tistory.com, http://kkamagui.springnote.com)는 밝혀 주십시오.
기타 사항은 mint64os at gmail.com 이나 http://kkamagui.tistory.com으로 보내주시면 반영하겠습니다.
상세한 내용은 책 "64비트 멀티코어 OS 구조와 원리"를 참고하기 바랍니다.

0.시작하면서...

이번에는 프로그래밍에서 빠져서는 안될 부분, 메모리 동적 할당(malloc, free)을 한번 구현해 보자. 이미 동기화 오브젝트에 대한 구현이 끝났기 때문에 멀티 태스킹 환경에서도 잘 동작하는 동적 할당 모듈을 작성할 수 있다. 오늘은 간단히 동적할당에 대해서만 구현하고 동기화는 다음에 따로 구현해보자.

1.메모리 공간 할당

동적할당을 구현하기 위해서는 동적 할당을 위한 공간을 마련해야 하는데, 이전에 봤던 OS 프레임워크의 메모리 레이아웃을 다시 보자(너무 많이봐서 외우는 사람도 있을 것이다 ㅎㅎ).

메모리_레이아웃.PNG

<프레임워크 메모리 레이아웃>

커널 스택의 끝이 0x400000에 위치하므로 4Mbyte 이상의 영역은 비어있다. 이 공간을 동적 할당의 공간으로 사용하자. 그럼 시작 주소는 4M로 정해졌고 이제 영역의 끝을 정해야하는데, 끝 주소를 8M 정도로 하면 괜찮을 듯 하다. 작은 커널이기 때문에 메모리 사용이 그렇게 많지 않을 것이고, 혹여 메모리를 많이 쓴다면 끝 주소를 더 늘리면 되므로 걱정하지 말자. 단 Virtual Box의 메모리도 거기에 맞추어 변경해줘야 하는데 지금은 8Mbyte 이상으로 설정하면 충분하다.

2.메모리 할당 정책

자 이제는 어떤 알고리즘으로 메모리를 할당할까?

생각할 수 있는 제일 간단한 방법은 무조건 고정크기의 블럭을 할당하는 것이다. 즉 프로그램은 크기를 요청할 수 없고, 메모리 할당을 요청하면 특정 크기의 블럭을 할당 받기 때문에 "알아서" 사용해야 한다. 블럭의 크기를 관리할 필요가 전혀 없기때문에 아주 간단하다. 천지 쓸모 없을 것 같은 방법이지만... 실제로 이와 비슷하게 할당 받아서 "잘" 동작하는 어플리케이션이 있다.

대용량 데이터를 처리하는 데이터베이스와 같은 프로그램의 경우, 운영체제로부터 큰 블럭을 할당받고 나름 최적화된 알고리즘으로 나누어 사용한다. 어플리케이션만 똑똑하다면 얼마든지 가능하다는 이야기다. 단점은 어플리케이션 개발자를 혹사 시킬 수도 있다는... ㅡ_ㅡ;;;( 요즘 메모리 관리를 못하는 어설픈 개발자가 어디 한둘이어야... ㅡ_ㅡ;;;;; )

두번째 방법은 블럭 영역을 검색해서 할당하는 방법이다. 제일 딱맞는 크기를 할당해 준다던지, 아니면 첫번째 만난 가능한 공간을 할당해 준다던지 하는 알고리즘으로 할당 가능한 영역을 찾아서 할당해 주는데, Best fit이니 Worst fit 이니 하는 방법들로 널리 알려져있다. 이 방법을 사용하면 가변 크기의 블럭들을 할당하고 해제할때 발생하는 단편화(Fragmentation)을 피하기가 어렵다.

세번째 방법은 좀 더 스마트(Smart)한 방법인데, 익히 버디 블럭(Buddy Block) 알고리즘으로 알려진 방법이다(Linux에서 채택하고 있다). 이름 그대로 친한 친구끼리 어떻게 저떻게 처리하는 알고리즘인데, 아래에서 자세히 알아보자.

3.버디 블럭 알고리즘(Buddy Block Algorithm)

버디 블럭 알고리즘은 크게 아래와 같은 단계로 수행된다(예를 든것이다. 숫자에 너무 연연하지 말자).

초기화 (Initialize)
- 메모리 영역을 적당한 크기로 나눈다(4Kbyte라고 가정하자) . 나누고 나니 n개 생겼다.
- 연속된 4Kbyte 블럭들 2개를 합하면 하나의 8Kbyte 블럭을 만들 수 있다. 이것을 전체 영역에 반복하니 (n/2)개가 생겼다.
- 연속된 8kbyte의 블럭들을 2개 합하면 하나의 16Kbyte의 블럭을 만들 수 있다. 이것을 전체 영역에 반복하니 (n/4)개가 생겼다.
- 계속 반복하다 보니 1개의 XKbyte의 블럭이 생겼다.

메모리 할당 (malloc)
- 4Kbyte 크기의 메모리 할당 요청이 들어왔다.
- 4Kbyte 크기영역 중에 빈 영역이 있는지 확인한다.
- 빈 영역이 있으면 할당해준다.
- 만약 없으면 위의 8Kbyte 블럭을 찾는다.
- 8Kbyte 중에 빈 블럭이 있으면 그 블럭을 4Kbyte의 2개로 나누고 그중 하나를 프로그램에 넘겨주고 나머지 하나는 4Kbyte 블럭에 달아둔다.
- 만약 8Kbyte 영역에 없으면 16Kbyte를 보고 하나 할당해서 4Kbyte를 프로그램에 넘겨주고 나머지 4Kbyte와 8Kbyte를 블럭에 달아둔다.
- 할당 가능할때까지 이를 반복해서 마지막 1개 남은 XKbyte 블럭도 할당 불가능하면 실패한다.

메모리 반납 (free)
- 4Kbyte 크기의 메모리 반납 요청이 들어왔다.
- 4Kbyte 해당 영역에 블럭을 반납하고 앞뒤 블럭의 상태가 Free인가 확인한다.
- 만약 Free라면 4Kbyte + 4Kbyte 블럭을 하나로 합쳐서 상위 8Kbyte 블럭으로 반납한다.
- 8Kbyte 블럭에 반납한 다음 앞뒤 블럭의 상태가 Free인가 확인한다.
- 만약 Free라면 8Kbyte + 8Kbyte 블럭을 하나로 합쳐서 상위 16Kbyte 블럭으로 반납한다.
- 위 과정을 합치는 것이 가능할 때까지 반복한다.

위와 같은 알고리즘을 계속하여 반복하므로 가변 길이의 블럭이 할당과 해제를 반복했을 때 발생하는 단편화(Fragmentation)현상을 어느정도 방지할 수 있다. 실제로 이 방법이 Linux 커널에서 2.4 버전 이전 대 까지 사용된 방법이다. 그 뒤로는 슬랩(Slab) 방식과 혼합해서 사용한다던데... 분석을 열심히하지 않아서 잘... ㅎㅎ...(좋은 자료 있으면 방명록이나 덧글로.. ㅎㅎ)

말로 설명하기 복잡한데, 위의 글을 그림으로보면 이해하기 쉽다. 시스템 전체 메모리가 12Kbyte 정도이고 최초/최대 할당 크기가 1Kbye에서 4Kbyte까지라면 초기 메모리 블럭은 아래와 같은 구성으로 되어있을 것이다(파란색으로 체워진 블럭은 Free 상태의 블럭이다).

<버디 블럭 초기화>

이 상태에서 1KB 블럭을 2개 할당받으면 1Kbyte에 블럭이 없고 2Kbyte에도 블럭이 없기때문에 4Kbyte짜리 블럭 하나를 쪼개 2Kbyte 2개로 나누게 된다. 그 중에 한 블럭을 다시 1Kbyte 2개로 나누게 되고 각각을 할당해 주게 된다. 이때 할당받은 각각의 블럭을 A와 B라고 하자. 이것을 그림으로 표현하면 아래와 같다(붉은색 블럭은 Alloc 상태의 블럭이다).

<1Kbyte 크기의 블럭 2개 할당>

이제 전체 시스템에는 4Kbyte 2개와 2Kbyte 1개가 남은 상태이다. 다시 1Kbyte 하나 할당 받으면 1Kbyte 블럭에는 여유분이 없으므로 2Kbyte 블럭을 1Kbyte 2개의 블럭으로 나누고 그중 하나를 할당하게 된다. 이때 할당받은 블럭을 C라고 하자. 이것을 그림으로 표현하면 아래와 같다.

<1Kbyte 블럭 1개 추가 할당>

어느덧 시간이 흘러 할당한 블럭의 사용이 끝나서 블럭 C를 반납했다. C블럭을 반납하고 나면 바로 옆의 블럭이 Free 상태의 블럭이므로 이 두 블럭을 합하여 상위 2Kbyte 블럭을 만들 수 있다. 이것을 그림으로 표현하면 아래와 같다.

<1Kbyte 블럭 1개 반납>

이제 시스템에는 2Kbyte 1개의 블럭과 4Kbyte 2개의 블럭이 Free 상태로 존재한다. 때마침 할당되었던 A와 B 블럭이 반납되었다. 그러면 각각 반납한 후 서로의 블럭을 합하면 하나의 2Kbyte 블럭을 생성할 수 있으므로 합쳐 2Kbyte 블럭 하나를 구성한다. 이때 다시 우측을 보면 2Kbyte 블럭이 인접하여 존재하므로 다시 이 둘을 합하여 상위의 4Kbyte 블럭을 만들 수 있다. 이 수행이 끝나면 다시 초기상태와 같은 4Kbyte 블럭 3개가 존재하게 된다.

<1Kbyte 블럭 반납>

<1Kbyte 블럭 반납-블럭 통합>

Buddy1(1).PNG

<블럭 통합 완료>

모든 작업이 끝나고 블럭이 초기상태로 복원되었다. 이것으로 메모리 할당과 해제가 끝났다.

4.구현

4.1 00Kernel/Custom/Memory.h/c

버디 블럭 알고리즘은 할당 가능한 메모리의 최소 크기와 최대 크기를 정의해야한다. 우리는 메모리 할당의 최대크기를 4Mbyte(빈 영역의 최대공간)로 하고 최소 크기는 512Byte로 하자. 그럼 최대 크기와 최소 크기 사이가 총 13단계로 나누어지게 된다. 그럼 메모리 공간을 나타내기위한 14개의 영역관리가 필요하다는 결론이 나오는데, 비트 마스트(Bitmask)를 이용해서 관리하자.

버디 블럭을 구현하는 방법은 몇가지가 있는데, 한가지는 링크드 리스트(Linked List)를 이용하는 방법이고, 그 다음 방법은 비트 마스크(Bitmask)를 이용하는 방법이다. 리스트를 사용하는 것이 좀더 쉬울 수 있으나 효율면에서는 비트마스크를 사용하는 것이 좋다. 프레임워크 소스 코드는 비트마스크를 사용하여 구현되었다(리스트를 사용하는 방법은 옛날에 한번 해봤다는 지극히 개인적인 이유.... ㅡ_ㅡ;;;).

비트 마스크를 이용하기로 했으니, 비트마스크의 총 크기를 알아야 한다.

4Mbyte 영역을 512byte 블럭으로 나누면 총 8192개가 나온다. 한 바이트가 8bit이므로 8로 나누면 1024Byte 즉 1Kbyte가 필요하다. 그렇다면 1024byte 블럭은 얼마 크기의 비트마스크가 필요할까? 블럭 크기가 512Byte의 2배이므로 512Byte가 필요하다. 2048byte(2Kbyte)의 블럭은? 256Byte 크기의 비트마스크가 필요하다. 이를 반복하면 각 메모리 블럭당 필요한 바이트 수를 구할 수 있다.

위의 계산방법을 통해 총 필요한 단계와 각 단계에 필요한 비트 마스크 배열의 크기를 계산하고, 블럭 해제시에 사용할 할당된 크기값을 저장하기위한 배열을 추가하여 동적 할당 구조체를 만들자.

// 동적 할당을 정보를 저장할 구조체
// 최대 비트마스크의 크기인 MEMORY_MAX_BITMASKCOUNT개의 크기로
// MEMORY_MAX_BITMASKLISTCOUNT개 만든다.
// 메모리 용량을 줄이고 싶으면 아래를 튜닝하면 된다.
typedef struct memoryStruct
{
DWORD vdwSizeArray[ MEMORY_ALLOC_MAX_SIZE / MEMORY_ALLOC_MIN_SIZE ];
BYTE vvbBitMask[ MEMORY_MAX_BITMASKLISTCOUNT ][ MEMORY_MAX_BITMASKCOUNT ];
} MEMORY, * PMEMORY;

구조체를 만든 다음 함수가 몇가지 필요하다.

버디 블럭 알고리즘이 정해진 블럭의 크기만큼 Align하여 할당하므로 메모리 할당 요청시에 적당한 크기의 블럭을 찾는 함수
비트 마스크를 조작하는 함수
버디 블럭 알고리즘으로 블럭을 할당하고 해제하는 함수

알고리즘이 나름 복잡한 관계로 함수 원형만 추출했다. 구현에 대한 실제 코드는 첨부에서 받을 수 있다.

void InitMemory( void );
void* AllocMemory( int iSize );
BOOL FreeMemory( void* pvAddress );
int AllocBuddy( int iAlignSize );
BOOL FreeBuddy( int iListIndex, int iMaskOffset );
int GetAlignSize( int iSize );
int GetListIndexOfMatchSize( int iSize );
BOOL IsValidListIndex( int iIndex );
BYTE* GetMaskArray( int iListIndex );
int FindFreeOffsetInMask( int iListIndex );
BOOL SetFlagInMask( int iListIndex, int iOffset, BYTE bFlag );
BYTE GetFlagInMask( int iListIndex, int iOffset, BYTE* bFlag );

4.2 00Kernel/Custom/KShell.h/c

이제 실제로 테스트를 해볼 차례다. KShell.c 파일을 열어서 Shell() 함수에 Memory 초기화 함수를 추가한다.

/**
    KShell 의 Main
*/
void Shell()
{
    InitScheduler();
    InitMemory();
    InitSemaphore( &gs_stSema, 1 );
    // 새로운 태스크 등록
    AddTask( EdgeDraw );
    EnableScheduler( TRUE );

    ShellLoop();
while( 1 );
}

그리고 테스트를 위해 ProcessCommand() 함수에 malloc 명령과 free 명령을 추가한다. malloc 명령은 malloc 0x20 과 같이 사용되며 특정 크기의 블럭을 할당 받을 때 사용한다. free 명령은 malloc 명령으로 할당받은 메모리를 그대로 해제하는 역할을 한다(기능을 추가할수록 코드가 점점 길어지는.. ㅡ_ㅡ;;;). 그리고 마지막으로 동적할당 비트 마스크에 대한 정보를 표시하는 DumpMemory() 함수를 추가한다.

/**
    엔터가 쳐졌으면 버퍼의 내용으로 명령어를 처리한다.
*/
void ProcessCommand( int* piX, int* piY, char* vcCommandBuffer,
                     int* piBufferIndex)
{
    char vcDwordBuffer[ 8 ];
    static DWORD vdwValue[ 10 ];
    static int iCount = 0;
...... 생략 ......
// 메모리를 할당받는다. malloc 00000000의 형태여야 한다.
    else if( ( *piBufferIndex > 7 ) &&
             ( kMemCmp( vcCommandBuffer, "malloc", 6 ) == 0 ) )
    {
        // 라인을 변경한다.
        NewLine( piX, piY );
        vcCommandBuffer[ *piBufferIndex ] = '\0';

        // 할당할 크기 16진수
        vdwValue[ iCount ] = kAToD( vcCommandBuffer + 7 );
        kDToA( vcDwordBuffer, vdwValue[ iCount ] );
        printxy( 0, *piY, "size" );
        printxyn( 10, *piY, vcDwordBuffer, 8 );
        // 할당된 주소
        vdwValue[ iCount ] = ( DWORD ) AllocMemory( vdwValue[ iCount ] );
        kDToA( vcDwordBuffer, vdwValue[ iCount ] );
        printxy( 20, *piY, "Address" );
        printxyn( 30, *piY, vcDwordBuffer, 8 );
        iCount++;
    }
    // 메모리를 해제한다.
    else if( ( *piBufferIndex == 4 ) &&
             ( kMemCmp( vcCommandBuffer, "free", 4 ) == 0 ) )
    {
        // 라인을 변경한다.
        NewLine( piX, piY );
        if( iCount > 0 )
        {
            iCount--;
        }
        kDToA( vcDwordBuffer, vdwValue[ iCount ] );
        printxy( 0, *piY, "Address" );
        printxyn( 15, *piY, vcDwordBuffer, 8 );
        FreeMemory( ( void* ) vdwValue[ iCount ] );
    }
    // Bitmask를 덤프한다.
    else if( ( *piBufferIndex == 7 ) &&
             ( kMemCmp( vcCommandBuffer, "dumpmem", 7 ) == 0 ) )
    {
        DumpMemory( piX, piY );
    }
}
...... 생략 ......
/**
    Memory의 상태를 Dump해서 표시한다.
*/
void DumpMemory( int* piX, int* piY )
{
    int i;
    int j;
    BYTE* pbMask;
    char vcDwordBuffer[ 8 ];
    int iFindCount;
    // 블럭중에 Free 한 것을 Dump 한다.
    for( j = 0 ; j < MEMORY_MAX_BITMASKLISTCOUNT ; j++ )
    {
        NewLine( piX, piY );
        kDToA( vcDwordBuffer, MEMORY_ALLOC_MIN_SIZE << j );
        pbMask = gs_stMemory.vvbBitMask[ j ];
        printxyn( 0, *piY, vcDwordBuffer, 8 );
        iFindCount = 0;
        for( i = 0 ; i < MEMORY_MAX_BITMASKCOUNT * 8 ; i++ )
        {
            if( pbMask[ i / 8 ] & ( 0x01 << ( i % 8 ) ) )
            {
                kDToA( vcDwordBuffer, i );
                printxyn( 10 + iFindCount * 10, *piY, vcDwordBuffer, 8 );
                kGetCh();
                NewLine( piX, piY );
            }
        }
    }
}

4.3 00Kernel/makefile 수정

4.3.1 프레임워크 1.0.3 이전 버전

makefile은 깔끔히 정리된 버전을 기준으로 설명한다. 새로운 버전을 받지 않았으면 21 OS 프레임워크 소스 릴리즈에 가면 새로운 makefile을 받을 수 있다.

새로운 makefile에 OBJ 부분을 아래와 같이 수정한다.

#Object 파일 이름 다 적기
#아래의 순서대로 링크된다. 새로운 파일이 생기면 뒤에 다 추가하자
OBJ = Asm.o Kernel.o Isr.o Descriptor.o Interrupt.o Keyboard.o StdLib.o Task.o \
FrameWork.o KShell.o Scheduler.o Synchronize.o Memory.o

4.3.2 프레임워크 1.0.3 이후 버전

프레임워크 1.0.3 버전 이후는 makefile에 다 통합되어있다. Custom 폴더에 Memory.h/c 파일을 넣고 make를 입력하는 것으로 끝이다.

5.Build 및 실행

위의 모든 과정이 끝난 후 makekernel.bat 와 makeimg.bat 또는 make를 실행하면 커널이 build되고 Virtual Box로 결과를 확인할 수 있다. 아래는 실행 후 dumpmem 명령을 통해 비트 마스크의 내용을 확인한 화면이다. 맨 마지막에 0x400000 크기의 블럭이 0x00000000 인덱스에 존재한다. 이것으로 보아 4Mbyte 크기의 블럭이 정상적으로 할당되어 있음을 알 수 있다.

<초기의 메모리 비트마스크>

아래는 0x20 크기의 메모리를 할당 받은 후에 다시 메모리 상태를 본 것이다(다 표시되지는 않았지만 0x200 크기의 블럭부터 상위 0x200000 크기의 블럭까지 모두 하나씩 할당되었음을 알 수 있다).

<0x20 크기의 메모리블럭 할당 후>

하나를 할당받은 후에 다시 반납하여 메모리 상태를 덤프한 것이다. 알고리즘이 정상적으로 동작하여 다시 0x400000 크기의 블럭이 생성되었음을 알 수 있다. 이를 반복해서 테스트하면 된다.

<0x20 메모리 블럭 해제 후>

6.마치면서...

동적 메모리 할당에 대해 구현하면서 멀티 태스킹 시에 발생할 수 있는 문제에 대한 고려는 제외하였다. 동적 할당에 대한 내용만으로도 충분히 복잡하기 때문에, 동기화 부분에 대해서는 다음에 다룰 것이다.

오늘 이후로 커널 코드에서 마음껏 malloc과 free를 사용할 수 있게 되었다. 비록 블럭 단위가 커서 효율성에 문제가 좀 있지만 프로그램을 주의해서 작성한다면 충분히 감당할 수 있는 부분이라 생각한다.

메모리 공간의 낭비가 마음에 걸린다면 동적 할당 알고리즘을 수정하면 된다. 버디 블럭의 크기를 512Byte 이하로 낮추는 것은 비트마스크의 크기가 커지므로 좋은 방법이 아니다. 괜찮은 방법은 아주 작은 메모리 블럭 같은 경우, 4Kbyte 크기를 버디 블럭으로 할당 받은 후 내부적으로 다시 비트 마스크를 사용하여 나누어 사용하는 것이다. 구현은 각자 해보도록 하자.

다음 번에는 멀티 태스크 환경에서 사용할 수 있도록 세머포어를 사용하여 동기화를 해보도록 하자.

7.첨부

7.1 프레임워크 1.0.3 버전 이전

Custom.zip : Custom 폴더의 파일들
makefile : makefile

7.2 프레임워크 1.0.3 버전 이후

Custom_1_0_3.zip

이 글은 스프링노트에서 작성되었습니다.

'OS Kernel > 32bit OS Framework' 카테고리의 다른 글

Part18. Tutorial6-간단한 파일시스템을 추가해 보자 (0)	2007.11.14
Part17. Tutorial5-메모리 동적할당 기능에 동기화 기능을 추가해 보자 (0)	2007.11.14
Part15. Tutorial3-동기화(Synchronization) 기능을 추가해 보자 (0)	2007.11.14
Part14. Tutorial2-멀티 태스킹(Multi Tasking) 기능을 추가해 보자 (0)	2007.11.14
Part13. Tutorial1-프레임워크에 기능을 추가해 보자 (0)	2007.11.14

kkamagui의 작업실