2007. 11. 14. 06:02
     

Part17. Tutorial5-메모리 동적할당 기능에 동기화 기능을 추가해 보자

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

 

들어가기 전에...

0.시작하면서...

 앞서 이미 동적할당 기능을 버디 블럭(Buddy Block) 알고리즘으로 구현했다. 하지만 아직 멀티 태스킹 환경에서 안전하게 동작하기 위해서는 무엇인가 부족하다. 멀티 태스크 환경에서 실행했던 화면에 문자를 찍는 예제처럼, 메모리 영역이라는 자원을 가지고 서로 경쟁하는 상황이다.

 이 문제를 동기화 객체중에 하나인 바이너리 세머포어(Binary Semaphore)를 이용해서 해결해 보자.

 

1.보호 or 임계 영역(Critical Section)의 결정

 동적 메모리 할당 함수에서 경쟁관계가 발생하는 범위는 어디서 어디까지일까? 어디까지를 보호하면 될까?

 보호는 공통으로 사용하는 자원에 대해서 범위를 결정해야 한다. 동적 메모리 할당에서 공통으로 사용하는 구조체는 gs_stMemory이고 따라서 구조체를 변경하는 부분은 다 보호해야 한다.

 보호하는 영역의 크기와 성능간에는 멀티 태스킹 환경일때 밀접한 관계가 있는데, 보호하는 영역이 넓으면 코드의 로직이 간단해 지는 반면 병렬 수행 능력이 떨어지므로 전체적인 성능이 저하된다. 보호하는 영역은 좁을수록 좋으니 신중이 결정하도록 하자.

 

2.AllocMemory() 함수 분석

 AllocMemory() 함수를 직접 보면서 보호할 범위를 찾아보자.

  1.  /**
        메모리를 할당한다.
    */
    void* AllocMemory( int iSize )
    {
        int iAlignSize;
        int iOffset;
        int iRelAddress;
        int iSizeArrayOffset;
  2.     // 크기를 못구하면 에러다.
        iAlignSize = GetAlignSize( iSize );
        if( iAlignSize == 0 )
        {
            DEBUGPRINT( "HERE" );
            return NULL;
        }
  3.     // 메모리 블럭 하나를 얻는다.
        iOffset = AllocBuddy( iAlignSize );
        if( iOffset == -1 )
        {
            return NULL;
        }
       
        // START Address에서의 상대적인 위치를 계산하여 Size Array에 크기를 넣어둔다.
        // 나중에 Free할때 사용하기 위해서다.
        iRelAddress = iAlignSize * iOffset;
        iSizeArrayOffset = iRelAddress / MEMORY_ALLOC_MIN_SIZE;
        gs_stMemory.vdwSizeArray[ iSizeArrayOffset ] = iAlignSize;
  4.     return ( void* ) ( iRelAddress + MEMORY_START_ADDRESS );
    }

 

 중간에 보면 AllocBuddy() 함수를 호출하고 그 값을 받아서 gs_stMemory의 값을 수정하는 코드를 볼 수 있다. 동기화를 가장 쉽게 하려면 위의 AllocMemory() 함수 전체를 Lock/Unlock 으로 보호하면 된다. 하지만 효율적이지 못한 방법임을 우리는 잘 알고 있다(아닌가? 나만 알고있나? ㅡ,.ㅡ;;;).

 좀 더 생각하보면 AllocBuddy()에서 값을 할당받은 후 아래는 그 값으로 계산하여 설정하는 것이기 때문에 AllocBuddy() 함수만 보호하면 될 것 같다는 생각이 든다.

 음... 그럼 조금만 더 생각해 보자. AllocBuddy() 함수에서 실제로 gs_stMemory에 접근하는 부분을 찾아 세분화하면 더 좁게 만들 수 있다.

  1. /**
        버디 블록 알고리즘으로 메모리를 할당한다.   
            정렬된 크기가 들어와야 한다.
    */
    int AllocBuddy( int iAlignSize )
    {
        int iListIndex;
        int iFreeOffset;
  2.     iListIndex = GetListIndexOfMatchSize( iAlignSize );
        if( iListIndex == -1 )
        {
            return -1;
        }
  3.     // 해당 Index에 Bitmask를 검색해서 Free한 곳이 있는가 본다.
        iFreeOffset = FindFreeOffsetInMask( iListIndex );
        // 만약 최대크기의 listIndex인데도 없으면 실패한다.
        if( ( iFreeOffset == -1 ) && ( iListIndex == MEMORY_MAX_BITMASKLISTCOUNT -1 ) )
        {
            return -1;
        }
        else if( iFreeOffset != -1 )
        {
            SetFlagInMask( iListIndex, iFreeOffset, MEMORY_ALLOC );
            return iFreeOffset;
        }

  4.     
        // 여기까지 오면 해당 Bitmask에 빈곳이 없고 최대크기의 bitmask도 아니라는
        // 이야기이므로 2배 크기에서 할당가능한가 확인한다.
        iFreeOffset = AllocBuddy( iAlignSize * 2 );
        if( iFreeOffset == -1 )
        {
            return -1;
        }
  5.     // Free Offset이 할당되었으면 2배 크기를 요청했으므로 하나는 리턴하고
        // 다른 하나는 bitmask에 연결해야 한다.
        // 2 * iFreeOffset을 하면 하위의 첫번째 빈 블럭을 찾을 수 있다.
        // 첫번째 블럭은 할당하고 두번째 블럭은 Free 상태로 둔다.
        SetFlagInMask( iListIndex, 2 * iFreeOffset, MEMORY_ALLOC );
        SetFlagInMask( iListIndex, ( 2 * iFreeOffset ) + 1, MEMORY_FREE );

  6.     
        return ( iFreeOffset * 2 );
    }

 

 위의 코드에서 FindFreeOffsetInMask() 함수를 이용해서 빈 블럭을 얻어오는 부분과 SetFlagInMask() 함수 이용해서 마스크를 설정하는 부분만 손 보면 될 것 같다. 저 두 부분에 Lock/Unlock을 추가 하도록 하자.

 

3.FreeMemory() 함수 분석

 FreeMemory() 함수도 직접 보면서 찾아보도록 하자.

  1. /**
        메모리를 해제한다.
    */
    BOOL FreeMemory( void* pvAddress )
    {
        int iRelAddress;
        int iSizeArrayOffset;
        int iBlockSize;
        int iListIndex;
        int iMaskOffset;
  2.     if( pvAddress == NULL )
        {
            return FALSE;
        }
  3.     // 실제 주소에서 상대적인 주소로 변경하여 할당했던 블럭의 크기를 알아온다.
        iRelAddress = ( ( DWORD ) pvAddress ) - MEMORY_START_ADDRESS;
        iSizeArrayOffset = iRelAddress / MEMORY_ALLOC_MIN_SIZE;
  4.     iBlockSize = gs_stMemory.vdwSizeArray[ iSizeArrayOffset ];
        gs_stMemory.vdwSizeArray[ iSizeArrayOffset ] = 0;
  5.     iListIndex = GetListIndexOfMatchSize( iBlockSize );
        if( IsValidListIndex( iListIndex ) == FALSE )
        {
            return FALSE;
        }
  6.     iMaskOffset = ( iRelAddress / iBlockSize );
  7.     return FreeBuddy( iListIndex, iMaskOffset );
    }

 

 FreeBuddy() 라는 함수가 보인다.  AllocMemory() 함수의 경우와 마찬가지로 좀더 세분화 해보자. 아래는 FreeBuddy() 함수이다.

  1. /**
        List Index의 Mask Offset 위치의 Block을 Free 한다.
    */
    BOOL FreeBuddy( int iListIndex, int iMaskOffset )
    {
        BOOL bFlag;
        int iBuddyOffset;
  2.     // 해당 블럭을 Free한 상태로 만든다.
        SetFlagInMask( iListIndex, iMaskOffset, MEMORY_FREE );
  3.     // 최대 크기 블럭이면 여기서 끝
        if( iListIndex == MEMORY_MAX_BITMASKLISTCOUNT -1 )
        {
            return TRUE;
        }
  4.     // Mask offset이 짝수이면 다음 블럭을 보고 홀수이면 이전블럭을 봐서 Free상태
        // 이면 합쳐서 상위 하나의 블럭을 만들 수 있으므로 상태를 살펴본다.
        if( iMaskOffset % 2 == 0 )
        {
            iBuddyOffset = iMaskOffset + 1;
        }
        else
        {
            iBuddyOffset = iMaskOffset - 1;
        }


  5.   // 해당 Mask의 Flag 값을 얻는다.
        if( GetFlagInMask( iListIndex, iBuddyOffset, &bFlag ) == FALSE )
        {
            return FALSE;
        }
       
        // 이웃이 할당된 상태이면 여기서 끝
        if( bFlag == MEMORY_ALLOC )
        {
            return TRUE;
        }
  6.     // 이웃이 빈 상태이면 둘다 합쳐서 상위 블럭을 만들어 준다.
        SetFlagInMask( iListIndex, iMaskOffset, MEMORY_ALLOC );
        SetFlagInMask( iListIndex, iBuddyOffset, MEMORY_ALLOC );
       
        return FreeBuddy( iListIndex + 1, iMaskOffset / 2 );
    }

 

 Free의 경우는 Alloc의 경우와 약간 다르다. Free의 경우는 Free한 직 후(위의 붉은색 영역) 해당 블럭의 마스크를 변경한 다음 이웃한 블럭을 보고 이웃한 블럭이 Free 된 상태이면 하나로 합하여 위로 올리는 과정을 거친다.

 블럭을 합치는 동안에 Free된 블럭에 대한 할당 요청이 들어오면 어떻게 될까? 그 이후의 블럭을 합치는 과정은 하위 블럭들이 전부 Free 상태라는 가정에서 동작하므로 문제가 발생한다. 따라서 Free 같은 경우는 블럭을 합치는 전체 과정이 보호(함수 전체에 대한 보호)되어야 한다.

 

3.구현

3.1 Memory.c/h 수정

 동적 메모리 할당 및 해제를 위한 동기화 오브젝트를 하나 만들자. 그리고 메모리 초기화를 할때 같이 초기화 하자.

  1. MEMORY gs_stMemory;
    SEMAPHORE gs_stSema;
  2. /**
        메모리를 초기화 한다.
    */
    void InitMemory( void )
    {
        // 동기화 오브젝트 초기화
        InitSemaphore( &gs_stSema, 1 );
     
        // 모두 할당 안된 것으로 설정한다.
        kMemSet( &gs_stMemory, 0x00, sizeof( gs_stMemory ) );
       
        // 제일 큰 블럭 하나만 Free한 상태이다.
        gs_stMemory.vvbBitMask[ MEMORY_MAX_BITMASKLISTCOUNT - 1 ][ 0 ] = MEMORY_FREE;
    }

 

 앞서 구분했던 영역에 동기화 코드를 삽입한다.

  1. /**
        버디 블록 알고리즘으로 메모리를 할당한다.   
            정렬된 크기가 들어와야 한다.
    */
    int AllocBuddy( int iAlignSize )
    {
        int iListIndex;
        int iFreeOffset;
  2.     iListIndex = GetListIndexOfMatchSize( iAlignSize );
        if( iListIndex == -1 )
        {
            return -1;
        }
       
        OnSemaphore( &gs_stSema );
        // 해당 Index에 Bitmask를 검색해서 Free한 곳이 있는가 본다.
        iFreeOffset = FindFreeOffsetInMask( iListIndex );
        // 만약 최대크기의 listIndex인데도 없으면 실패한다.
        if( ( iFreeOffset == -1 ) && ( iListIndex == MEMORY_MAX_BITMASKLISTCOUNT -1 ) )
        {
            OffSemaphore( &gs_stSema );
            return -1;
        }
        else if( iFreeOffset != -1 )
        {
            SetFlagInMask( iListIndex, iFreeOffset, MEMORY_ALLOC );
            OffSemaphore( &gs_stSema );
            return iFreeOffset;
        }
        OffSemaphore( &gs_stSema );
        
        // 여기까지 오면 해당 Bitmask에 빈곳이 없고 최대크기의 bitmask도 아니라는
        // 이야기이므로 2배 크기에서 할당가능한가 확인한다.
        iFreeOffset = AllocBuddy( iAlignSize * 2 );
        if( iFreeOffset == -1 )
        {
            return -1;
        }
       
        OnSemaphore( &gs_stSema );
        // Free Offset이 할당되었으면 2배 크기를 요청했으므로 하나는 리턴하고
        // 다른 하나는 bitmask에 연결해야 한다.
        // 2 * iFreeOffset을 하면 하위의 첫번째 빈 블럭을 찾을 수 있다.
        // 첫번째 블럭은 할당하고 두번째 블럭은 Free 상태로 둔다.
        SetFlagInMask( iListIndex, 2 * iFreeOffset, MEMORY_ALLOC );
        SetFlagInMask( iListIndex, ( 2 * iFreeOffset ) + 1, MEMORY_FREE );
        OffSemaphore( &gs_stSema );
        
        return ( iFreeOffset * 2 );
    }

 

  1.  /**
        메모리를 해제한다.
    */
    BOOL FreeMemory( void* pvAddress )
    {
        int iRelAddress;
        int iSizeArrayOffset;
        int iBlockSize;
        int iListIndex;
        int iMaskOffset;
        BOOL bRet;
  2.     if( pvAddress == NULL )
        {
            return FALSE;
        }
  3.     // 실제 주소에서 상대적인 주소로 변경하여 할당했던 블럭의 크기를 알아온다.
        iRelAddress = ( ( DWORD ) pvAddress ) - MEMORY_START_ADDRESS;
        iSizeArrayOffset = iRelAddress / MEMORY_ALLOC_MIN_SIZE;
  4.     // 만약에 할당되어있지 않으면 Free하면 안된다.
  5.     // 버그가 있어서 수정한 부분이다.
  6.     if( gs_stMemory.vdwSizeArray[ iSizeArrayOffset ] == 0 )
        {
            return FALSE;
        }
  7.     iBlockSize = gs_stMemory.vdwSizeArray[ iSizeArrayOffset ];
        gs_stMemory.vdwSizeArray[ iSizeArrayOffset ] = 0;
  8.     iListIndex = GetListIndexOfMatchSize( iBlockSize );
        if( IsValidListIndex( iListIndex ) == FALSE )
        {
            return FALSE;
        }
  9.     iMaskOffset = ( iRelAddress / iBlockSize );
  10.     OnSemaphore( &gs_stSema );
        bRet = FreeBuddy( iListIndex, iMaskOffset );
        OffSemaphore( &gs_stSema );
       
        return bRet;
    }

 

3.2 KShell.c 수정

 이제 멀티 태스킹 환경에서 동작을 시험해 볼 차례이다. KShell.c 파일을 열어서 수정한다.

  1. /**
        테두리를 그려주는 태스크
    */
    void EdgeDraw( void )
    {
        int i;
        int j;
        BYTE bCh;
        int k;
        char vcBuffer[ 8 ];
        int iTID;
        DWORD vdwAllocAddress[ 2 ];
  2.     i = 0;
        j = 0;
        bCh = 0;
        iTID = GetCurrentTID();
        
        kDToA( vcBuffer, iTID );
  3.     for( k = 0 ; k < 50000 ; k++ )
        {
            printxy( 0, 23 - iTID, "=EdgeDraw Task Work=" );
            printxyn( 20, 23 - iTID, vcBuffer, 8 );
  4.         // 콘솔 테두리를 돌면서 .을 찍는다.
            for( i = 30 ; i < 79 ; i++ )
            {
                // Memory Alloc
                vdwAllocAddress[ 0 ] = ( DWORD ) AllocMemory( kRand() % 0x400000 );
                vdwAllocAddress[ 1 ] = ( DWORD ) AllocMemory( kRand() % 0x400000 );
  5.             // Semaphore 대기
                OnSemaphore( &gs_stSema );
                gs_iX = i;
                gs_iY = 23 - iTID;
                Print( bCh );
                bCh++;
                OffSemaphore( &gs_stSema );
                SwitchTask();
  6.             FreeMemory( ( void * ) vdwAllocAddress[ 0 ] );
                FreeMemory( ( void * ) vdwAllocAddress[ 1 ] );
            }
        }
    }

 

4.실행

 이제 태스크를 실행하면 2개의 메모리를 랜덤한 크기로 할당받은 후, 화면에 문자를 출력하고 다시 해제하는 것을 반복할 것이다.

 위의 수정이 다 끝나면 kernelclean.batmakekernel.bat, makeimg.bat 를 차례로 실행시켜서 disk.img 파일을 만든 다음 이것을 실행해 보자. 멀티 태스킹 환경에서 잘 동작하는지 확인하기 위해 커널이 실행되면 starttask 명령을 입력하여 태스크를 여러개 실행한 다음 dumpmem 명령으로 비트마스크를 확인하면 된다. 랜덤하게 메모리가 할당되므로 dumpmem 수행 시 마다 비트맵이 다르게 나옴을 알 수 있다.

multimem1.PNG

<태스크를 여러개 수행시킨 상태>

 

multimem2.PNG

<비트 마스크 덤프1>

 

 multimem3.PNG

<비트 마스크 덤프2>

 

 

5.마치면서...

 이것으로 멀티 태스킹 환경에서 malloc/free를 마음껏 할 수 있게 되었다. 다시 커널 프로그래밍에 빠져보자 >ㅁ<)/~

 

6.첨부

6.1 프레임워크 1.0.3 이전 버전

 

6.2 프레임워크 1.0.3 이후 버전

 

 

 

 

 

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


Android App

Posted by 호기심 많은 kkamagui(까마귀, 한승훈)

댓글을 달아 주세요