Multiple Processor System(Multicore System)의 Cache 효율 높이기

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

참고 1 : http://softwarecommunity.intel.com/articles/eng/2760.htm

참고 2 : http://minjang.egloos.com/1848130

들어가기 전에...

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

• 

OS 개발에 관한 서적

하위 페이지에 있는 자료들은 OS를 개발하면서 관련된 자료들을 일부 정리해 놓은 것이다. OS 개발에 대한 보다 자세한 내용은 "64비트 멀티코어 OS 원리와 구조"를 참고하기 바란다.

   <64비트 멀티코어 OS 원리와 구조>

0.시작하면서...

 이 글은 Multiple Processor System에서 발생할 수 있는 Shared Cache의 문제를 어떻게 해결할 수 있는지를 설명하는 문서이다. 참고 자료의 내용 중에 테스트 가능한 부분만 요약하고 추가적인 내용을 덧붙였으니, 원문이 궁금하면 참고 1(http://softwarecommunity.intel.com/articles/eng/2760.htm) 문서를 보면 된다.

1.Processor, Core, Cache

 최근의 Processor는 Core를 2개 이상 탑재하는 방식으로 제작되고 있으며, 그에 따라 Cache의 중요성이 점점 높아지고 있다. CPU 업계를 이끌어 나가는 INTEL과 AMD는 Cache 구성에 대해 서로 다른 정책을 펴고 있으나, 공통적으로 Cache의 크기를 점차 넓혀가는 추세이다.

 Processor에 포함된 Core가 많고 Cache의 크기가 커지면 커질수록 성능이 배로 좋아질 것 같지만, 실제로는 각 Cache Level(L1, L2, L3)간의 동기화 문제가 발생하기때문에 정비례하지 않는다. 다시말하면 Core 0와 Core 1이 동일한 Data에 접근하거나 같은 Cache Line에 있는 데이터에 접근해서 Read/Write를 하게 될 경우, 각 Cache Level의 Data를 Syncronization(동기화)해야하기 때문에 성능이 저하되는 것이다. 이에대한 자세한 내용은 다음 장에서 살펴보자.

 아래는 2개의 Core를 가지는 Processor 2개를 연결한 그림이다. Processor 0에 L2 Cache가 Core 0와 Core 1에 공통으로 사용되고 있으며, L1 Cache는 각 Core에 할당되어 공유되지 않음을 볼 수 있다. L1 Cache 공유되지 않기 때문에 위에서 언급했던 L1 Cache와 L2 Cache간에 Syncronization 문제가 발생하게 된다.

<2 Dual Core Processor>

 그럼 지금부터 Cache를 효율적으로 사용할 수 있는 몇가지 방법에 대해 알아보자.

2.Cache Optimization Tip

2.1 Processor Affinity

  Multithread 프로그램의 경우, 개별 Thread는 개별 Core에 할당되서 동시에 실행될 수 있다. Core에 할당되는 Thread는 Scheduling Algorithm에 따라 달라지며, 하나의 Core에서 실행되거나 여러 Core를 돌며 실행될 수 있다. Thread A가 Core A와 Core B에서 교대로 실행되는 경우, Thread A가 사용하는 Data를 매번 L2 Cache에서 L1 Cache로 옮겨오는 최악의 상황이 발생할 수 있으며 그로 인해 성능이 저하될 수 있다.

 이러한 경우 Thread를 특정 Core에 할당해서 실행함으로써 Overhead를 줄일 수 있다. 또한 각 Thread가 Data를 공유하지 않는다면, 개별 Thread를 특정 Core에서만 수행되도록 할당함으로써 성능을 높이는 것이 가능하다.

 Windows 환경과 Linux 환경에서는 아래의 2가지 API를 사용해서 Thread와 Process의 Processor Affinity를 설정할 수 있다.

1. // Windows API
2. BOOL SetProcessAffinityMask(
     HANDLE hProcess,
     DWORD_PTR dwProcessAffinityMask
   );
   DWORD_PTR SetThreadAffinityMask(
     HANDLE hThread,
     DWORD_PTR dwThreadAffinityMask
   );
3. // Linux API
4. /* Get the CPU affinity for a task */
   extern int sched_getaffinity(
     pid_t pid,
5.   size_t cpusetsize,
6.   cpu_set_t *cpuset
7. );
8. /* Set the CPU affinity for a task */
   extern int sched_setaffinity(
     pid_t pid,
9.   size_t cpusetsize, 
     const cpu_set_t *cpuset
10. );

 하지만 Affinity가 좋은 점만 있는 것은 아니다. 할당된 Core에 Load가 몰리는 경우, Scheduling 순서를 기다리느라(Waiting Queue에 대기) 오히려 더 지연 될 수 있으니 주의해야 한다.

2.2 Cache Blocking(Data Tiling)

 Cache Blocking 또는 Data Tiling 기법은 Loop를 수행할 때, Loop에서 사용되는 Data가 Cache Line에 존재하도록하는 기법이다. 만약 Data Block이 크다면, Cache에 Load된 Data가 Loop시에 한번만 사용되고 버려지고 현상이 반복될 수 있다. 이러한 최악의 상황은 Cache의 Hit Ratio를 떨어뜨리며 성능을 저하시키는 요인이 된다. 이러한 현상을 해결하는 좋은 방법은 Data를 Tile 처럼 잘게 쪼개서 작은 Loop로 처리하는 것이다.

 아래의 그림과 같이 (A)와 같이 큰 Data를 사용하는 Loop를 (B)처럼 작은 Data를 사용하는 Loop로 나눔으로써, Data Block을 Cache에 올려 성능을 높일 수 있다.

<Cache Blocking(Data Tiling)>

2.3 Hold Approach

 Hold Approach는 빈번하게 Read/Write하는 것을 Local Copy를 사용하여 줄임으로써 Cache 효율을 높이는 방법이다. Thread Local Storage나 Local Variable을 사용하여 작업한 후, 결과를 Reporting하는 것이 이에 해당한다. 아래의 그림은 Hold Approach를 그림으로 표현한 것이다.

<Holding Approach>

 좌측의 (A)와 같이 빈번하게 Read/Write하던 것을 Local Copy를 통해 (B)와 같이 줄여서 효율을 높일 수 있다.

2.4 Avoid False Sharing

 False Sharing이란 Multiple Processor System의 유명한 문제이다. 각 Core에서 수행중인 Thread간의 공유하는 Data가 없지만, 동일한 Cache Line에 있는 Data를 접근함으로써 매번 Evict와 Load가 반복되는 현상이다. 실제로는 Cache Coherency Problem(협업 문제)가 전혀 발생하지 않지만, Cache의 정보가 변경되었으므로 어쩔 수 없이 L1 Cache의 내용을 L2 Cache에 옮기고 다시 다른 Core의 L1 Cache로 옮겨야 한다. 아래의 그림은 Flase Sharing을 그림으로 표현한 것이다.

<False Sharing>

 Core 0의 Thread 0와 Core 1의 Thread 1은 서로 공유하는 Data가 없지만 동일한 Cache Line에 위치함으로 Evict와 Load가 반복되게 된다.

 이러한 False Sharing을 피하는 방법은 아래와 같다.

• 공유되지 않는 Data는 다른 Cache Line에 둔다. 즉 Padding Data를 두거나 다른 Memory Address에 할당한다. 단, 너무 많은 Cache Line을 할당하지 않도록 Data를 잘 묶어서 적당히 배열한다.
• Hold Approach와 마찬가지로 Data를 Local 영역에 저장하고 필요할때만 Read/Write하여 Evit/Load 회수를 줄인다.
• Thread의 Affinity를 설정하여 Thread 0와 Thread 1이 동일한 Core에서 수행되도록 한다.

3.Test

 아래는 Cache Optimazation Test에 사용한 간단한 코드이다. 윈도우즈 환경에서 VC++ 6.0으로 테스트했으며 Release 모드에서 Optimization 옵션은 Debug 모드와 같이 사용하지 않는 것으로 설정하고, 8Byte Aling, MultiThread DLL을 사용하도록 설정했다.

 테스트에 사용된 PC는 INTEL Core 2 Duo 2.6GHz에 4G의 RAM으로 구성되어있다.

3.1 Affinity & Cache Blocking Test

 아래는 Affinity와 Cache Blocking을 테스트하는 간단한 코드이다.

1. #include <windows.H>
   #include <stdio.H>
   #include <tchar.H>
2. #define UNIT      32
   #define MULTIPLE  200000
   #define MAX_DATA  UNIT * MULTIPLE
   #define MAX_LOOP  200
3. // 계산할 데이터가 들어있는 배열
   volatile int g_iData[ MAX_DATA ] = { 1, 2, };
4. // 실제 메인 함수
   int main(int argc, char* argv[])
   {
       DWORD dwSum;
       int i;
       int j;
       int k;
       int l;
       DWORD dwStartTime;
       DWORD dwEndTime;
       DWORD dwTimeSum;
5.     // Processor High Priority로 만든다.
       SetPriorityClass( GetCurrentProcess(), HIGH_PRIORITY_CLASS );
6.     // Affinity 설정
       SetProcessAffinityMask( GetCurrentProcess(), 0x1 );
7.     // 카운팅 시작
       dwSum = 0;
       dwTimeSum = 0;
       printf( "Start Processing...\n" );
       for( l = 0 ; l < 20 ; l++ )
       {
           dwStartTime = GetTickCount();
          
           // Normal Loop
           for( j = 0 ; j < MAX_LOOP ; j++ )
           {
               for( i = 0 ; i < MAX_DATA ; i++ )
               {
                   dwSum += g_iData[ i ];
               }
           }
8.         /*
           // Cache Blocking
           for( k = 0 ; k < MULTIPLE ; k++ )
           {
               for( j = 0 ; j < MAX_LOOP ; j++ )
               {
                   for( i = k * UNIT ; i < ( k + 1 ) * UNIT ; i++ )
                   {
                       dwSum += g_iData[ i ];
                   }
               }
           }
           */
          
           //결과 출력
           dwEndTime = GetTickCount() - dwStartTime;
           dwTimeSum += dwEndTime;
           printf( "%d Time = %d ms\n", l + 1, dwEndTime );
       }
9.     printf( "Average Time = %0.2f\n", dwTimeSum / 20.0 );
       return 0;
   }

아래는 위의 코드를 이용해서 테스트한 결과이다.

• Normal Loop

  • Affinity 미사용

    • Average Time = 4225.00

    • Average Time = 4201.55

  • Affinity 1 사용 - 하나의 Core에서만 동작시킴

    • Average Time = 4275.00

    • Average Time = 4256.25

• Cache Blocking

• • Affinity 미사용

    • Average Time = 3836.70
    • Average Time = 3818.70

  • Affinity 1 사용 - 하나의 Core에서만 동작시킴

  • • Average Time = 3875.80

    • Average Time = 3860.90

 테스트 결과 Data Block 크기가 클수록, 즉 Cache Evit가 발생할 확률이 높으면 높을수록 Cache Blocking의 효과가 커졌다. Processor Affinity 부분은 오히려 Affinity를 적용한 결과가 근소하게 더 느리게 나왔다. 이것은 Thread가 Core를 옮겨다니며 Cache를 Reflesh하는 시간 보다 할당 받은 Core의 Wait Queue에서 대기하는 시간이 더 길기 때문에 발생한 듯하다. 이 결과는 어디까지나 테스트 프로그램의 결과이고, 만약 더 큰 Data에 접근하고 보다 복잡한 코드로 이루어져 있다면 충분히 달라질 수 있는 부분이다.

3.2 Affinity & Avoid False Sharing Test

 아래는 Affinity와 False Sharing을 테스트하는 간단한 코드이다.

1. #include <windows.H>
   #include <stdio.H>
   #include <tchar.H>
2. // 각 스레드에서 사용하는 전역 변수
   volatile int g_iData1 = 0;
   volatile int g_iData2 = 0;
3. // Cache line을 맞추기위해 정의한 구조체
   // 강제로 공간을 할당한다.
   typedef struct dataStruct
   {
       volatile int iData1;
       int viData[32];
       volatile int iData2;
   } DATA;
4. // Cache line 정렬용 구조체
   DATA g_stData = { 0, {0,}, 0 };
5. // 테스트 Thread 1
   DWORD CALLBACK TestThread1( void* pData )
   {
       /*
       // 지역변수 사용
       int i;
       int iTemp;
6.     iTemp = g_iData1;
7.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
       {
           iTemp = iTemp + 1;
       }
       g_iData1 = iTemp;
       return g_iData1;
       */
8.     /*
       // 바로 접근
       int i;
9.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
       {
           g_iData1 = g_iData1 + 1;
       }
       return g_iData1;
       */
       // False Sharing
       int i;
10.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
        {
            g_stData.iData1 = g_stData.iData1 + 1;
        }
        return g_stData.iData1;
    }
     
    // 테스트 Thread 1
    DWORD CALLBACK TestThread2( void* pData )
    {
        /*
        // 지역변수 사용
        int i;
        int iTemp;
11.     iTemp = g_iData2;
12.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
        {
            iTemp = iTemp + 1;
        }
        g_iData2 = iTemp;
        return g_iData2;
        */
13.     /*
        // False Sharing
        int i;
14.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
        {
            g_iData2 = g_iData2 + 1;
        }
        return g_iData2;
        */
15.     // False Sharing
        int i;
16.     for( i = 0 ; i < 0x1FFFFFFF ; i++ )
        {
            g_stData.iData2 = g_stData.iData2 + 1;
        }
        return g_stData.iData2;
    }
     
    // 실제 메인 함수
    int main(int argc, char* argv[])
    {
        HANDLE vhThread[2];
        int i;
        DWORD dwStartTime;
        DWORD dwEndTime;
        DWORD dwTimeSum;
17.     // Processor High Priority로 만든다.
        SetPriorityClass( GetCurrentProcess(), HIGH_PRIORITY_CLASS );
18.     dwTimeSum = 0;
        printf( "Start Processing...\n" );
        for( i = 0 ; i < 20 ; i++ )
        {
            // Thread 생성
            vhThread[0] = CreateThread( NULL, 0, TestThread1, ( LPVOID ) 0, CREATE_SUSPENDED, NULL );
            vhThread[1] = CreateThread( NULL, 0, TestThread2, ( LPVOID ) 0, CREATE_SUSPENDED, NULL );
19.         // Affinity 설정
            SetThreadAffinityMask( vhThread[ 0 ], 0x1 );
            SetThreadAffinityMask( vhThread[ 1 ], 0x1 );
20.         // 카운팅 시작
            dwStartTime = GetTickCount();
            ResumeThread( vhThread[ 0 ] );
            ResumeThread( vhThread[ 1 ] );
21.         // Thread 종료
            WaitForMultipleObjects( 2, vhThread, TRUE, INFINITE );
22.         //결과 출력
            dwEndTime = GetTickCount() - dwStartTime;
            printf( "%d Time = %d ms\n", i + 1, dwEndTime );
            dwTimeSum += dwEndTime;
        }
23.     printf( "Average Time = %0.2f\n", dwTimeSum / 20.0 );
        return 0;
    }

 아래는 위의 코드를 이용해서 각 옵션으로 테스트한 결과이다.

• Global Variable에 직접 접근

  • Affinity 미사용

    • Average Time = 2841.40
    • Average Time = 2842.20

  • Affinity 1, 1 사용 - 하나의 Core에서만 동작시킴

    • Average Time = 2653.15
    • Average Time = 2651.55

  • Affinity 1, 2 사용 - 각각 Core에 할당해서 동작시킴

    • Average Time = 2842.95
    • Average Time = 2843.75

• Cache Line 정렬을 통한 Avoid False Sharing

  • Affinity 미사용

    • Average Time = 1514.10
    • Average Time = 1514.80

  • Affinity 1, 1 사용 - 하나의 Core에서만 동작시킴

    • Average Time = 3043.75
    • Average Time = 3042.20

  • Affinity 1, 2 사용 - 각각 Core에 할당해서 동작시킴

    • Average Time = 1520.30
    • Average Time = 1519.55

• Local Variable을 사용한 Hold Approach

• • Affinity 미사용

    • Average Time = 1330.50
    • Average Time = 1332.00

  • Affinity 1, 1 사용 - 하나의 Core에서만 동작시킴

    • Average Time = 2671.85
    • Average Time = 2672.65

  • Affinity 1, 2 사용 - 각각 Core에 할당해서 동작시킴

  • • Average Time = 1335.95
    • Average Time = 1335.95

 위의 굵은 숫자는 가장 해당 파트에서 가장 빠른 수행 결과를 나타낸 것이다. 결과는 당연히 Local Variable(Hold Approach)을 사용하는 것이 가장 빠르게 나왔다. 첫번째 Global Variable에 직접 접근하는 결과에서는 두 Thread 모두 Core 0에 할당해서 수행한 결과가 제일 빨랐다. 이는 Thread 수행 시에 발생하는 Cache Evit/Load가 상당하기 때문에 발생한 결과인 듯 하다. 다른 테스트의 경우는 하나의 Core에 할당한 결과가 가장 느렸다.

 이 테스트에서 눈 여겨볼 것은 Avoid False Sharing 테스트이다. Cache Line 정렬을 사용한 것과 하지 않은 것의 차이가 거의 1.8 배의 속도 차이가 난다. 다시 말하면 Data Structure를 손보는 것 만으로도 MultiCore 환경에서의 Performance를 1.8배 향상 시킬 수 있는 것이다. Performance가 중요시되는 프로그램이라면 Cache Line 정렬은 충분히 고려해 볼만 하다.

4.결론

 Processor Affinity는 윈도우즈 환경에서 기대만큼 큰 효과를 발휘하지 못했지만, Cache Blocking과 Hold Aproach 및 Avoid False Sharing 기법은 충분히 효과적인 것으로 나타났다. Processor Affinity가 윈도우즈 환경에서 큰 효과를 발휘하지 못하는 것은 윈도우즈의 Scheduler가 Affinity를 어느정도 보장해주며, Wait Queue에서 대기하는 시간이 Cache Evit & Laod 시간보다 더 길기 때문인 것으로 추측된다.

 테스트 결과 Cache Blocking과 Avoid False Sharing은 성능 향상에 충분한 효과가 있는 것으로 나타났다. Cache Blocking과 Avoid Flase Sharing은 Data Structure와 밀접한 관련이 있으며, 이는 Data Structure를 Cache-Friendly 하게 설계하는 것이 Multiple Processor의 성능을 향상시키는 좋은 포인트임을 말해주는 것이다. 따라서 Multiple Processor System에서 Cache-Friendly한 Data Structure를 사용하면 프로그램의 성능을 일정 수준 이상 높일 수 있다.

5.마치면서...

 이미 우리는 Multiple Processor의 시대에 살고 있다. 프로그래머에게 또 하나의 장을 열어준 Multiple Processor System, Multiple Processor-Friendly한 Architecture로 프로그램의 Performance를 높이자.

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

참고. OS 프레임워크(Framework) 주요 함수들

원본 :  http://kkamagui.springnote.com/pages/348969

들어가기 전에...

0.시작하면서...

 커널 제작시 많이 쓰이는 함수들의 목록을 정리하였다.

1.화면 표시 관련

2.키(Keyboard) 입력 관련

3.스케줄링(Scheduling) 관련

4.유틸리티(Utility) 관련

5.포트 입출력(Port In/Out) 관련

.

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

참고. 멀티 태스킹(Multi tasking) 구현 방법

들어가기 전에...

1.멀티 태스킹(Multitasking)이란?

 멀티 태스킹을 구현하는 방법을 간단하게 설명하면 기존에 실행 중인 태스크의 컨텍스트(Context)를 저장하고 실행할 태스크의 컨텍스트를 복원하는 것이다. 솔찍히 이게 전부인데... 실제 코드로 구현하게되면 두가지 방법 정도로 나누어진다.

 프레임워크에서는 하드웨어적인 방법을 사용하지 않고 일일이 레지스터를 저장하고 복원하는 방법을 선택했다. 이유는 내가 하드웨어적인 방법은 이미 해봤기 때문이다.(ㅡ_ㅡa..).

 자 그럼 소프트웨어적으로 어떻게 구현하는지 알아보자. 우리가 해야 할 일이 결국 현재 동작중이던 것을 저장했다가, 다시 복원하는 것 아닌가? 그럼 현재 동작중인 태스크라는 것은 무엇이란 말인가?

 작은 범위에서 동작중인 상태라 하면 CPU의 각 레지스터의 상태정보라고 생각 할 수 있고, 좀더 큰 범위에서 보자면 메모리의 내용까지도 포함할 수 있을 것 같다.

 메모리의 내용까지 포함하면 일이 점점 커지므로 일단 CPU의 레지스터 정보를 저장하는 것으로 하고 어디에다 저장할 것인지를 생각해 보자.

 가장 쉽게 생각할 수 있는 것이 바로 스택이다. 스택은 프로그램의 실행에서는 빠져서는 안되는 공간이며, 역시 인터럽터 처리 시에도 스택의 역할은 중요하다(에러코드의 저장이라던지, 아니면 부분적인 컨택스트의 저장이라던지 하는 부분...).

 그럼 스택만 사용하나? 꼭 그런것은 아니다. 별도의 공간에 컨텍스트를 저장하는 공간을 만들어서 거기다 저장하고 복원하는 방법이 있다.

 어느 것이 더 좋은지 굳이 따지자면 별도의 공간에 컨텍스트를 저장하는 것이 조금 더 나은 방법인 것 같다. 왜냐하면 스택같은 경우 스택의 오버플로우 같은 상황에서 컨택스트 스위칭이 되면 결과는 예측 할 수 없기 때문이다.

 하지만 스택을 사용하는 방법은 비교적 코드가 간단하기 때문에, 프레임워크에서는 스택에 저장하기로 했다.(컨텍스트를 관리하는 별도 공간이 필요없는 점도 큰 역할을 했다.)

2.스택(Stack)에 저장되는 레지스터의 값 및 위치

 그럼 어떻게 저장할까? 아래 그림은 프레임워크에서 레지스터를 저장하는 것을 표시한 것이다.

<초기상태>

 위 처럼 모든 레지스터를 스택의 바닥(bottom)부터 레지스터를 차곡 차곡 쌓아서 올린다. 태스트를 처음 생성했을 때는 태스크가 복원되자 마자 Task 함수의 처음으로 이동해야 하므로 스택의 포인터는 top에서 4byte아래인 태스크 엔트리 포인트(Start)를 가리키게 하고 스택의 맨 꼭대기는 태스크가 종료됬을 때, 호출될 마감 함수의 엔트리 포인트를 넣어둔다. 이렇게 함으로써 태스크의 첫 실행이 가능하다.

 그렇다면 한참을 실행하는 도중에 태스크가 저장되면 어떻게 될까? 스택의 top만 다르고 동일하다.

<실행 도중>

 레지스터를 저장하는 시작 영역을 스택의 바닥으로 고정하였는데, 이렇게 하면 컨택스트를 저장하고 복원하는 루틴이 간단해진다. 복원은 저장의 역순으로 하면 되니 생략한다.

3.구현

 자 그럼 이제 어떻게 저장하고 복원하는 알아봤으니 실제 코드를 보자.

 아래의 코드는 Task를 정의한 구조체이다. 스택만 존재하는 것을 알 수 있다. 별도의 정보가 필요하면 스택 영역 뒤에 붙이면 된다.

1. 
   // Task에 대한 정보 저장
   typedef struct kTaskStruct
   {
       // cs, ds, ss, es, fs, gs에서
       // EAX, ECX, EDX, EBX, ESP, EBP, ESI, EDI 순으로 Push 한다.
       // Stack의 14DWORD를 Register를 저장하는데 사용한다.
       DWORD vdwStack[ MAX_STACKSIZE ];
   1. // 별도의 추가적인 데이터가 필요하면 여기에 삽입하면 된다. 
   2. // 여기!!
2. } TASK, *PTASK;

 아래의 코드는 실제로 스위칭을 시도하는 어셈블리어 코드이다.

1. ;Task Switching을 수행한다.
   _kSwitchTask :
    cli
2.  push eax
    ; General Register
    ; ESP, EBP, EAX, EBX, ECX, EDX, ESI, EDI의 순서로 Push한다.
    ; Current Task
    mov eax, dword [ss:esp + 8]
    
    ; esp의 계산
    push ebx
    mov ebx, esp
    add ebx, 8
    mov dword [eax + 52], ebx
    pop ebx
3.  mov dword [eax + 48], ebp
    mov dword [eax + 40], ebx
    mov dword [eax + 36], ecx
    mov dword [eax + 32], edx
    mov dword [eax + 28], esi
    mov dword [eax + 24], edi
    ; eax를 집넣는다.
    mov ebx, eax
    pop eax
    mov dword [ebx + 44], eax
4.  ; Segment Register
    ; cs, ds, ss, es, fs, gs의 순서로 Push한다.
    mov ax, cs
    mov dword [ebx + 20], eax
    mov ax, ds
    mov dword [ebx + 16], eax
    mov ax, ss
    mov dword [ebx + 12], eax
    mov ax, es
    mov dword [ebx + 8], eax
    mov ax, fs
    mov dword [ebx + 4], eax
    mov ax, gs
    mov dword [ebx + 0], eax
5. 
    ; Next Task
    mov eax, dword [ss:esp + 8]
    mov esp, eax
6.  ; segment register
    pop eax
    mov gs, ax
    pop eax
    mov fs, ax
    pop eax
    mov es, ax
    pop eax
    mov ss, ax
    pop eax
    mov ds, ax
    ; cs의 값은 지금 쓰지 않는다.
    pop eax
7.  ; General Register
    pop edi
    pop esi
    pop edx
    pop ecx
    pop ebx
    pop eax
    pop ebp
    pop esp
8.  sti
    ret

 어셈블리어를 잘 모르는 사람은 약간 낯설겠지만 위에 나온 인덱스만 봐도 순서대로 저장하는구나 정도는 알 수 있을 것이다. 여기서 눈여겨 봐야할 것이 cli와 sti인데, cli는 인터럽터를 불가시키는 명령이고 sti는 인터럽터를 가능시키는 명령이다.

 왜 이렇게 하는 것일까? 그것은 혹시나 태스크를 저장하는 과정에서 다시 스위칭이 일어나서 다시 또 저장하게 되고 그 저장하는 와중에 또 스위칭이 일어나는 계층적으로 계속 저장되는 상황이 오면 스택이 계속 깊어지기때문에 그것을 막기위해서 넣어놨다.(사실 그렇게 많이 깊어지지는 않는다. 워낙 간단한 코드라서 ㅡ_ㅡ;;; 시간이 별로 안걸리기 때문이다.),

또 다른 이유는 타이머 인터럽트 내와 유저 코드 내에서 마음 껏 호출 하기 위해서이다. 인터럽터 불가로 하지 않으면 유저 코드에서 스위칭하는 동안에 타이머 인터럽트에 의해서 다시 스위칭 될 수 있다.

3.1 기존 태스크 스위칭의 문제점

 그런데 무엇인가 이상한 생각이 들지 않는가? 태스크 스위칭 루틴에서 보면 인터럽트를 조작하는 부분에서 이상한 느낌이 들지 않는가? 만약 복원되는 태스크의 인터럽트 가능/불가 상태가 불가로 저장된 상태였다면? 복원된 후에는 가능으로 바뀐다는 이야기? @0@)/~~!!

 그렇다. 이 방식의 문제는 일단 태스크가 복원되고 나면 인터럽터가 가능이 된다는 문제가 있다. 그럼 어떻게 해야 될까? 간단한 해결방법은 인터럽트 및 각종 상태에 대한 정보를 가지고 있는 FLAG 레지스터의 값도 같이 저장했다가 복원하면 된다.

 이 방법을 사용하기 위해서 스택에 저장하는 컨텍스트 부분과 스위칭 어셈블리어 함수 부분에 약간의 수정을 해주어야 한다.

3.2 스택(Stack)의 내용 수정

 스택에 EBP와 EAX 레지스터 사이에 EFLAG 레지스터를 저장하는 공간을 확보한 뒤에 태스크를 생성할때 디폴트의 EFLAG 레지스터 값을 넣어준다.

 아래는 변경된 태스크 설정 함수이다.

1. /**
       TASK 구조체를 설정한다.
   */
   BOOL kSetupTask( PTASK pstTask, void* pfStartAddr, void* pfEndAddr )
   {
       DWORD* pdwStackTop;
2.     // 구조체를 초기화 한다.
       kMemSet( pstTask, 0, sizeof( TASK ) );
3.     // Stack의 Top
       pdwStackTop = ( DWORD* ) ( pstTask->vdwStack + ( MAX_STACKSIZE - 1 ) );
4.     // ESP, EBP, EFLAG, EAX, EBX, ECX, EDX, ESI, EDI 순으로 Push 한다.
       pstTask->vdwStack[ 14 ] = ( DWORD ) ( pdwStackTop - 1 );
       pstTask->vdwStack[ 13 ] = ( DWORD ) ( pdwStackTop - 1 );
       pstTask->vdwStack[ 12 ] = EFLAG_DEFAULT;
5.     // cs, ds, ss, es, fs, gs는 kernel의 기본값으로 설정해 준다.
       pstTask->vdwStack[ 5 ] = GDT_VAR_KERNELCODEDESC;
       pstTask->vdwStack[ 4 ] = GDT_VAR_KERNELDATADESC;
       pstTask->vdwStack[ 3 ] = GDT_VAR_KERNELDATADESC;
       pstTask->vdwStack[ 2 ] = GDT_VAR_KERNELDATADESC;
       pstTask->vdwStack[ 1 ] = GDT_VAR_KERNELDATADESC;
       pstTask->vdwStack[ 0 ] = GDT_VAR_KERNELDATADESC;
6.     // 마지막으로 Stack의 Return Address를 pfAddr로 설정해 준다.
       pdwStackTop[ -1 ] = ( DWORD ) pfStartAddr;
       // 만약 Task 종료 함수가 설정되지 않으면 Default를 설정
       if( pfEndAddr == NULL )
       {
           pdwStackTop[ 0 ] = ( DWORD ) pfEndAddr;
       }
       else
       {
           pdwStackTop[ 0 ] = ( DWORD ) kTaskEnd;
       }
       return TRUE;
   }

3.3 태스크 스위칭 코드 수정

 기존의 코드는 EFLAG에 대한 부분이 없었다. 따라서 이부분에 대한 저장 및 복원에 대한 코드를 추가하고 마지막으로 sti 부분을 제거한다.

1. ;Task Switching을 수행한다.
   _kSwitchTask
    push eax
    ; General Register
    ; ESP, EBP, EAX, EBX, ECX, EDX, ESI, EDI의 순서로 Push한다.
    
    ; Current Task의 저장
    mov eax, dword [ss:esp + 8]
    push ebx
2. ; EFlag의 계산
    pushfd
    mov ebx, dword [ss:esp]
    mov dword [eax + 48], ebx
    add esp, 4
3.  cli
    ; esp의 계산
    mov ebx, esp
    add ebx, 8
    mov dword [eax + 56], ebx
    pop ebx
    mov dword [eax + 52], ebp
    mov dword [eax + 40], ebx
    mov dword [eax + 36], ecx
    mov dword [eax + 32], edx
    mov dword [eax + 28], esi
    mov dword [eax + 24], edi
    ; eax를 집넣는다.
    mov ebx, eax
    pop eax
    mov dword [ebx + 44], eax
4.  ; Segment Register
    ; cs, ds, ss, es, fs, gs의 순서로 Push한다.
    mov ax, cs
    mov dword [ebx + 20], eax
    mov ax, ds
    mov dword [ebx + 16], eax
    mov ax, ss
    mov dword [ebx + 12], eax
    mov ax, es
    mov dword [ebx + 8], eax
    mov ax, fs
    mov dword [ebx + 4], eax
    mov ax, gs
    mov dword [ebx + 0], eax
5. 
    ; Next Task의 복원
    mov eax, dword [ss:esp + 8]
    mov esp, eax
6.  ; segment register
    pop eax
    mov gs, ax
    pop eax
    mov fs, ax
    pop eax
    mov es, ax
    pop eax
    mov ss, ax
    pop eax
    mov ds, ax
    ; cs의 값은 지금 쓰지 않는다.
    pop eax
7.  ; General Register
    pop edi
    pop esi
    pop edx
    pop ecx
    pop ebx
    pop eax
    popfd
    pop ebp
    pop esp
    ret

4.마치면서...

 이상으로 태스크 스위칭에 대해서 알아봤다. 아.. 생각보다 글 쓰는데 시간이 많이든다.. ㅜ_ㅜ

 뭐 여튼 오늘 코드 테스트한 기념으로 스크린샷 한방...

 간단한 Shell과 콘솔 아래쪽에 EdgeDraw Task가 동시에 동작하고 있는 화면이다.

5.첨부

• 참고._MutiTasking.ppt

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

참고. BIOS Call을 사용하는 방법들

들어가기 전에...

0.시작하면서...

 후배들하고 이야기하다가 32bit Mode에서 16bit 코드의 집합으로 되어있는 BIOS Call을 호출하는 방법에 대해서 깜짝 놀랄만한 이야기를 들었다. 대단한 놈들... ㅜ_ㅜ... 완전 감동이다.. ㅜ_ㅜ... 니들은 최고로구나.. ㅜ_ㅜ)/~!!!

 32bit에서 BIOS 함수를 사용하기위해서는 많은 제약이 따르는데, 그럼에도 불구하고 사용하는 이유는 많은 편리한 기능들을 제공하기 때문이다. 그럼 지금부터 2가지 방법에 대해서 알아보자.

방법 1. V86 Task를 이용한다.

 내가 기존에 사용하던 방법은 V86 Mode를 사용하는 것이었다. Interrupt 시에 32bit Interrupt Table을 사용하므로 커널 서비스를 그대로 사용할 수 있는 장점이 있는 반면 16bit BIOS 함수를 사용하기 위해서는 16bit Stack을 조작해야 하는 복잡합이 있다. 특히 스택 조작 부분이 최강 난이도.. @0@)/~

16bit와 32bit에 대한 이해를 바르게 하고 있고 함수 호출에 대한 개념(??)이 제대로 박혀 있어야 fault 없는 동작이 가능하다.

 하나라도 삐끗한다면... 죽음의 재부팅 또는 멈춤 현상이... ㅡ_ㅡ;;;;

 방법을 간단히 설명하면 이러하다. 일단 TSS에 태스크를 생성할 때, EFLAG 레지스터에 V86 FLAG를 설정해 놓고 태스크를 스위칭하여 실행한다. 그 상태에서 인터럽트를 통하여 커널모드에 있는 서비스 루틴을 호출하고 커널모두의 서비스 루틴은 32bit 커널 스택의 상위에 들어있는 16bit 스택을 얻어서 조작한다.

 여기서 중요한 점은 원래 32bit 커널 서비스가 끝나면 당연히 16bit 인터럽트 호출 코드 다음으로 돌아갈껀데, 이 리턴하는 주소를 BIOS Service Routine의 주소로 변경하는 것이다. 그렇게 되면 32bit 커널 서비스를 나갔을 때, BIOS 함수를 호출할 수 있다. 그럼 BIOS 함수를 호출한 뒤에는 어떻게 될까? 당연히 BIOS 함수도 수행을 끝내고 Return 하게 될 것인데... Return Address라고 생각하는 것을 꺼내면 잘못된 주소가 될것이므로 당근 문제가 생긴다. 고로 이 BIOS의 함수를 위해 주소를 인터럽트 호출 루틴 다음으로 넣어줘야 한다. 

 이것이 바로 스택 조작인데 상당한 내공을 필요로 한다. 말로 하니 상당히 어려운데, 이것을 그림으로 보면 조금 더 쉽다.

<V86 모드에서 인터럽트 발생 시>

 위의 그림에서 보면 V86 모드에서 인터럽트가 발생하면 커널 스택에 V86 태스크 스택 포인터와 리턴 어드레스가 들어있는 것을 알 수 있다. 이 값을 이용하여 iretd라는 어셈블리어 명령이 V86 모드로 정상적으로 돌아갈 수 있는 것이다. 이 스택 포인터와 리턴 어드레스를 아래와 같이 조작하면 BIOS 함수를 실행하고 다시 정상적으로 복귀할 수 있다.

<V86 모드에서 BIOS 함수 호출 방법>

 위에서 붉은 색 부분을 유심히 봐야 한다. V86 모드 스택은 스택에 강제로 현재의 FLAG, CS, IP(INT를 호출한 코드의 주소)를 스택에 삽입하여 BIOS함수에서 iret를 호출했을 때 정상적으로 Int xxx 호출한 다음 코드로 돌아갈 수 있도록 준비한다. 이 상태에서 커널 서비스 루틴을 부르면 커널 서비스 루틴은 EIP 레지스터의 값을 수정하여 BIOS 서비스 루틴의 시작을 가리키도록 변경한 후 iretd를 한다.

 iretd를 하는 순간 어떻게 될까? 커널 모드 스택에 있는 값들이 다시 CPU로 복구되므로 당연히 리턴 어드레스에 설정된 BIOS 서비스 루틴으로 EIP가 설정되게 되고 이때 V86 모드의 스택은 FLAG, SS, IP의 값이 들어가있는 상태가 된다. BIOS에서 정상적으로 수행을 끝낸 뒤에 iret를 하게되면 V86 스택에서 값을 꺼내어 CPU에 복구하게 되는데, 이때 강제로 설정한 FLAG, CS, IP(Int xxx 주소)가 복구되므로 다시 V86 Task로 돌아오게 된다.

 이것이 스택 삽질(??)을 하여 BIOS 함수를 호출하는 방법이다. 말은 좀 간단한데... 실제로 해보면.... 수백번 좌절 먹는다.. ㅜ_ㅜ

방법 2. 16bit 모드로 전환했다가 다시 32bit 모드로 돌아온다.

 이것이 바로 궁극의 방법.... 16bit 관련 GDT를 모두 가지고 있다가 필요할때 CR0 레지스터와 GDT 스위칭을 통해 16bit <-> 32bit를 서로 전환하는 방법이다. 물론 16bit 모드로 돌아갔으니 32bit 태스크들이 멀티로 동작할 수 없다는 단점이 있으나 아예 다 일시 중지하고 BIOS 서비스를 사용하는 만큼 아주 간단하고 멋진 방법이다. @0@)/~!!

 물론 너무 자주 호출되거나 16bit 모드에서 하는 작업이 시간이 많이 걸리면 전체적으로 성능이 낮아지는 단점이 있지만... 간단한 BIOS 함수 호출 같은 것은 시도해볼만 하다.

 나중에 한번 적용을 고려해보자.

첨부

• 참고.V86.ppt

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

참고. Intel i386 CPU의 16bit->32bit 전환

들어가기 전에...

1.전환방법

 이 글은 INTEL Architecture Manual Volume3, Software Developer's Manual에 나와있는 9.9 Mode Switching 섹션을 정리한 문서이다. 모드 스위칭(Mode Switching)을 하기위한 코드는 그리 길지 않으나, 그 코드를 이해하기 위해서는 여러가지 기반 지식이 필요하다.

 Intel Manual에 따르면 모드 스위칭을 하는 과정은 아래의 순서로 수행하면 된다.

 사실 32bit에서 다시 16bit Mode로 돌아가는 과정도 소개되어있으나, 사용할 일이 없기때문에 생략하고 궁금한 사람은 Intel 메뉴얼을 참조하면 된다.

 Intel Manual의 9.10.2를  보면 STARTUP.asm 코드가 나와있다. 해당 코드에 대한 자세한 설명이 나와있으므로 메뉴얼에 나와있으므로 내가 만든 커널 로더의 코드를 이용해서 해당 부분의 설명을 할까 한다. 코드가 없는 사람은 21 OS 프레임워크 소스 릴리즈에 가서 프레임워크를 다운받아 01Boot/01KLoader 폴더에 파일을 참조하도록 하자.

 Part11. 커널 로더(Kernel Loader) 설명 문서와 내용이 상당히 중복되는데, 한번 더 복습한다는 생각으로 서로 참고하면서 보면 될것 같다.

1. [org 0x00]    <= 코드의 Base 주소를 0x00으로 맞추라는 어셈블리어 디렉티브
   [bits 16]     <= 아래의 코드를 16bit 기계어로 생성하라는 어셈블리어 디렉티브
       start:
           ;   일단 세그먼트의 초기화     <= 세그먼트를 다 Code 세그먼트와 일치시킴
           mov     ax, cs
           mov     ds, ax
           mov     es, ax

 위의 두가지 어셈블리어 디렉티브는 위에 설명된 주석을 참고하자. 다른 디렉티브는 nasm 메뉴얼을 참조하면 다양한 것을 알 수 있다.

1.         ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
           ;   GDT를 설정한다.
           xor     ebx, ebx
           xor     eax, eax
2.         mov     bx, ds         <= 현재 DS의 위치 BASE로 하는 세그먼트를 설정
           shl     ebx, 4
           mov     eax, ebx
           mov     word [codeDesc + 2], ax
           mov     word [dataDesc + 2], ax
           shr     eax, 16
           mov     byte [codeDesc + 4], al
           mov     byte [dataDesc + 4], al
           mov     byte [codeDesc + 7], ah
           mov     byte [dataDesc + 7], ah
           
           ; gdtr 레지스터 설정
           mov     eax, ebx
           add     eax, gdt
3.         mov     [gdtr + 2], eax    <= GDT Table의 값을 설정

  여기서 몇가지 눈여겨 보아야 할 것이 있다. 디스크립터의 형식을 보면 Base Address + 크기 정보로 간략히 표시할 수 있는데, 위의 코드에서 보면 Base Address를 현재 16bit 세그먼트의 값을 4만큼 좌로 쉬프트하여 그 값을 Base로 설정하는 것을 알 수 있다. 세그먼트 레지스터의 값을 4만큼 좌로 쉬프트하는 이유는 세그먼트 레지스터의 주소가 실제 주소로 맵핑될때 아래와 같은 공식으로 계산되기 때문이다.

 즉 세그먼트 레지스터의 값에 16을 곱하고 이 값을 Base로 사용한다는 것이다.

 위 코드에서 GDT 값에 현재 세그먼트의 값을 설정하는 이유는 위에 어셈블리어 디렉티브 명령인 ORG 명령과도 관계가 있다. 일단 ORG 명령의 영향에 대해서 알아 보자.

1. OFFSET    CODE SEQUENCE
2. 0x0000    A:    DW 0x00  <= 여기서 DW는 Word 크기만큼 자리를 할당 하는 어셈블리어 디렉티브
3. 0x0002    MOV   AX, A

  위의 간단한 코드에서 AX 레지스터에 들어가는 값은 과연 얼마일까? 0x0000 일까? 정답은 ORG 명령에 따라서 코드의 시작이 달라지므로 LABEL A의 위치 또한 ORG 명령에 따라 달라진다. 만약 [ORG 0x00] 이라면 저 코드의 AX 레지스터에는 0x0000 이 들어갈 것이다. 하지만 만약 [ORG 0x10] 이라면? AX 레지스터에는 0x0010 이 들어간다는 말씀 @0@)/~ 간단히 생각해서 ORG에 선언된 값 만큼 더해진다고 생각하면 된다.

 부트로더의 코드 시작이 0x0000 이므로 코드내에 LABEL들은 다 0x0000 기반으로  되어있다. 실제 실행 시에  이 코드의 위치는 0x7E00 에 위치에 있고 세그먼트 레지스터를 0x07E0으로 설정했기때문에 자연스레 레이블의 BASE에 0x7E00이 더해지는 효과가 되어 정상적인 동작이 가능하다.

 그럼 만약 [ORG 0x7E00]으로 설정해서 코드를 생성하고 실행할 수 는 없을까? 물론 가능하다. 세그먼트 레지스터의 값을 0x0000으로 설정해서 base가 0이 되도록 하고 GDT의 Code/Data의 Base를 0x0000으로 설정하면 된다. 하지만 여기서 주의해야 할 것은 앞부분에 16bit 코드의 부분이다. 16bit 코드의 경우 접근할 수 있는 코드의 최대 범위는 (Segment Register * 2⁴  + 레지스터의 값)과 같은데 실제 레지스터가 16bit이기 때문에 범위는 0x0000 ~ 0xFFFF 까지이다.

 세그먼트 레지스터의 Base를 0x0000으로 설정한 상태이기 때문에 실제로 접근할 수 있는 영역은 0x0000 ~ 0xFFFF까지 밖에 안된다. 이미 커널 로더가 로딩된 위치가 0x7E00 이므로 여유공간은 0x81FF 정도라는 것에만 유의하면 된다. 커널 로더의 코드가 그리 크지 않다면 별 문제가 되지 않는다는 말씀~ >ㅁ<)/~

 GDT Table의 값까지 설정했으므로 GDT Table의 값을 로드하고 CR0를 변경해서 32bit로 변경하는 코드 부분을 살펴보자.

1.         ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
           ; 인터럽터 불가 설정
           cli
          
           lgdt    [gdtr]     <= GDT Table을 로드
2.         ;   보호모드를 설정하고
           ;   인덱스 2 비트가 Floating Point 비트다.
           ;   Floating Point계산 유닛을 내부 유닛을 사용하도록
           ;   설정한다 그렇지 않으면 7번 인터럽터가 발생한다.
           mov     eax, cr0
           or      eax, 0x80000000      <= 페이징 플래그를 끄는 부분
           xor     eax, 0x80000000
           or      al, 1                <= 32bit 플래그를 설정하는 부분
           or      al, 0x04
           xor     al, 0x04
           mov     cr0, eax             <= 실제로 변경된 플래그를 적용하는 부분
3.         jmp     codeOffset:code_32   <= 32bit 모드로 점프~

 우측에 달린 설명을 읽어보면 각 역할을 알 수 있다. 마지막에 jmp 명령에서 Segment:Offset 형태의 fat jmp를 수행하고 나면 32bit 코드가 된다. 계속해서 마무리 부분을 살펴보자.

1. ;   여기에 진입하면 이미 보호모드다. 이제 리얼모드와는
   ;   상관없고 커널이 시작되면 돌아갈수도 없다.
   [bits 32]
       code_32:
           ;   레지스터를 초기화 하고
           mov     ax, dataOffset    <= 32bit 코드, 레지스터 마무리
           mov     ds, bx
           mov     es, bx
           mov     ss, bx
           mov     gs, bx
           xor     esp, esp
           mov     esp, 0x8ffff
           mov     ebp, 0x8ffff

  위의 코드가 32bit 코드의 시작 부분이고 모드 전환 부분의 마무리 부분이다. 이 아래부터는 각 기능 구현을 위한 32bit 코드들이 나열되고 수행된다.

  원래 GDT 설정 부분을 좀 더 자세히 다룰 생각이었으나, 역시 INTEL 메뉴얼을 그대로 옮겨적는 수준 밖에 되지 않을 것 같아서 코드로 대체했다. 사실 코드를 보면 앞서 설명했듯 그리 어렵지 않다. 하지만 이 코드를 제대로 쓰기위해서는 세그먼트에 대한 이해와 실제 코드가 컴파일 되고 링크되었을 때, 레이블과 변수들의 위치가 어떻게 되는지에 대한 이해, 그리고 GDT에 대한 정확한 이해가 필요하다. 경험한 사람은 알겠지만, 위 항목중에 하나라도 어긋나거나 잘못 이해하게되면 블루스크린의 공포보다 더 무섭다는 블랙스크린의 공포를 뼈져리게 느끼게 된다(글고 헤어나지 못해 GG를 치는 상황까지.. ㅡ,.ㅡ;;;;).

 어쨋든 32bit 모드로 스위칭 했으니 이제 32bit 모드로 계속 전진하도록 하자 @0@)/~ 화이팅~!!!!

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

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

21 OS 프레임워크 소스 릴리즈

들어가기 전에...

 KKAMAGUI OS 프레임워크 설치 환경은 20 작업환경 설치을 참고하면 개발 환경 및 실행 환경을 설치할 수 있다.

 프레임워크의 소스 코드 및 도움말은 아래와 같다.

2007/07/19 02:35:41 수정

 kLock(), kUnlock() 함수를 Intel CPU에서 지원하는 명령을 이용해서 새로 작성했다.

2007/07/11 03:45:30 수정

 make 파일을 간단하게 정리했다. makefile에 대한 사용법은 02 간단한 Make 사용법을 참조하도록 하자.

2007/07/10 06:23:33 수정

 큰 수정 2가지가 있었다. 각 항목은 00 작업일지를 참고하자.

2007/07/09 20:14:58 수정

 Task.c 파일에서 kSetupTask 함수에서 버그가 발생되어 수정했다.

Part18. Tutorial6-간단한 파일시스템을 추가해 보자

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

들어가기 전에...

0.시작하면서...

 이번 Tutorial은 이클립스 버전으로 변경된 OS 프레임워크 1.0.3 버전 소스를 이용해서 진행하도록 하자. 이클립스 버전 프레임워크는 21 OS 프레임워크 소스 릴리즈에 있으니 다운받아서 덮어쓰면된다.

덮어 쓴 뒤에 Tutorial5의 Custom.zip 파일을 다운받아 덮어쓰면 Tutorial 6을 진행할 수 있다.

 이클립스 환경이 없는 사람은 굳이 이클립스를 깔지 않아도 되니 너무 신경쓰지 말자. 이클립스는 단순히 개발 환경을 편리하게 하는 도구일 뿐이다. 이클립스가 없더라도 커맨드 라인에서 make를 입력하여 빌드하고 테스트 할 수 있다.

1.파일 시스템 설계

 우리 주위에는 다양한 파일 시스템이 존재하며 OS에 따라 메인 파일 시스템이 존재한다. 윈도우즈의 경우는 NTFS, Linux 같은 경우는 ext3fs와 같은 파일 시스템을 사용한다. 제대로된 파일 시스템을 설계한다거나, 혹은 NTFS or FAT or ext3 와 같은 파일 시스템을 지원하는 것은 상당량의 지식과 분석이 필요하므로 간단한 파일 시스템 구현을 목표로 하자.

 위에서 언급한 파일 시스템중에 가장 간단한 파일 시스템은 FAT 파일 시스템으로 파일을 링크드 리스트(Linked List)의 형태로 관리한다. 링크를 따라가면 파일을 찾을 수가 있으며, 파일의 생성 역시 링크를 연결하는 것이 전부이다. 자료구조 자체가 아주 간단하므로 윈도우 머신부터 임베디드 시스템까지 널리 사용된다.

 FAT 파일 시스템에 대한 내용은 01 FAT 파일 시스템(File System)를 참고하도록하고 이 FAT 파일 시스템을 기반으로 간단한 파일 시스템을 만들어 보도록 하자.

1.1 파일 시스템 공간(File System Area)

 OS 프레임워크는 하드디스크 or 플로피 디스크와 같은 주변기기 I/O 함수를 거의 제공하지 않는다(적어도 지금까지는 그렇다). 그렇다면 어디에 파일 시스템을 구성할까?

 정답은 "메모리"다. 메모리에 구성된 파일 시스템을 우리는 흔히 "램 디스크(RAM Disk)"라고 부른다. 메모리에 파일 시스템을 생성하기위해서는 공간이 필요한데 동적 할당을 위한 힙으로 4Mbyte ~ 8Mbyte의 주소 공간을 이미 할당했다. 메모리 공간을 연속적으로 할당하면 램의 낭비를 줄일 수 있으므로 램디스크의 공간을 8Mbyte ~ 12Mbyte(4Mbyte의 크기)로 잡자.

 램디스크 영역을 결정했으니 Virtual Box의 램 설정을 12Mbyte 이상으로 설정하면 준비 완료다.

1.2 파일 시스템 메타 데이터(File System Meta Data) 설계

 파일 시스템 공간이 확보되었으니 파일 시스템 관리를 위한 블럭을 설정하고 할당해야 한다. 우리가 만들 간단한 시스템은 FAT 파일 시스템에서 File Allocation Table(FAT) 및 Data Area 영역만 가진 아주 간단한 구조를 가진다. File Allocation Table(FAT)의 각 엔트리(Entry)는 2Byte의 크기를 가지고 각 엔트리는 512byte 크기를 가지는 블럭을 지시한다.

 총 파일 시스템 공간의 크기가 4Mbyte이므로 이것을 512byte(한 섹터의 크기)로 나누면 8192개의 엔트리가 존재한다. 하나의 엔트리당 2Byte 공간을 차지하므로 FAT 공간은 총 16384Byte(16Kbyte)의 크기이다.

 위의 내용을 그림으로 표현하면 아래와 같다.

<File System Architecture>

8Mbyte ~ 8Mbyte + 16Kbyte는 FAT 엔트리를 위한 영역이고 8Mbyte + 16Kbyte ~ 12Mbyte까지는 데이터를 위한 영역이다. 위 그림의 화살표가 의마하는 것은 FAT의 엔트리와 Data Area의 한 블럭이 1:1 대응임을 의미한다. FAT 파일 시스템과 동일한 방식이므로 FAT 파일 시스템의 용어를 사용하여 Data Area의 한 섹터(Sector)를 클러스터(Cluster)라고 부르자.

1.3 디렉토리 및 파일 설계

 파일 시스템에는 루트 디렉토리(Root Directory)라는 것이 존재한다. 이것은 트리(Tree) 형태를 가지는 디렉토리 구조에서 트리의 루트(Root)에 해당하는 것으로 모든 파일 및 폴더의 시작점이다. 우리가 파일에 접근할때 OS로 넘겨주는 절대 경로를 자세히 들여다 보면 루트 디렉토리부터 시작하는 경로를 넘겨준다("C:\ABC\a.txt" or "/home/kkamagui/a.txt"  같은 경로가 절대 경로이다). 저 경로를 받아서 OS에서는 루트 디렉토리부터 차례로 접근하여 파일 또는 폴더를 찾는 것이다.

 그렇다면 디렉토리 구조에서 디렉토리와 파일은 어떻게 다르며 어떻게 구분할까?

 일반적으로 섹터내에 존재하는 데이터라는 관점에서 디렉토리도 파일과 동일하다. 다른점은 파일은 저장한 데이터를 가지지만, 디렉토리는 다른 디렉토리 또는 파일에 대한 정보를 가진다는 점이다.

 위에서 디렉토리와 파일에 대해서 차이점을 간략하게 알아봤으니 디렉토리 구조를 디자인 하자. 디렉토리 또한 파일의 형태이므로 클러스터 단위로 구성되게 되는데, 클러스터 단위(섹터 크기와 동일 = 512Byte)를 엔트리 크기로 나누어서 나머지가 0이되게하면 클러스터 단위로 디렉토리를 처리할 수 있으니 구현이 간단해 진다.

 디렉토리 구조의 경우, 최소한의 데이터를 포함해야 하는데, 그중 하나는 엔트리의 이름이고 나머지 하나는 엔트리의 데이터가 시작되는 클러스터 인덱스다. 클러스터 인덱스의 정보는 FAT 내의 엔트리 인덱스와 일치하므로 클러스터 번호를 이용해서 FAT 내의 엔트리에 접근할 수 있다. 그렇다면 FAT 내의 엔트리가 2Byte로 구성되어있으므로 디렉토리 엔트리 역시 클러스터 인덱스가 2Byte로 구성되어야 하고, 이것을 바탕으로 디렉토리 엔트리는 아래와 같이 구성할 수 있다.

 위와 같이 구성하면 총 16Byte가 필요하다. 512Byte를 16Byte으로 나누면 총 32개의 엔트리로 딱 떨어지므로 적절한 선택인것 같다.

 만약 디렉토리의 엔트리가 32개가 꽉차서 더이상 넣지 못하는 경우라면 어떻게 할까? 새로운 클러스터를 할당받아서 디렉토리 클러스터에 연결하고 새로 할당받은 클러스터에 엔트리를 생성하면 된다. 클러스터를 연결하는 부분은 각자 구현해 보도록하고 지금은 구현을 간단히 하기위해 32개로 제한하자.

1.4 파일 시스템 API

 우리가 설계한 파일 시스템은 FAT와 Data Area간의 연결을 통해 파일 및 디렉토리를 관리하므로 이를 관리하고 사용할 API가 필요하다. Standard C API 수준으로까지 파일 시스템 API를 제공하려면 많은 부분을 고민해야하니 Low Level 수준의 API만 제공하고 추후 업그레이드를 하는 걸로 하자.

 Low Level 수준의 API란 어떤 것일까? 아래와 같은 함수들이 Low Level 함수라고 보면 된다(간략하게 표현했다).

  섹터 인덱스는 0x800000(8Mbyte)를 시작으로 하여 섹터 단위(512Byte) 단위로 전체를 나눈 인덱스를 의미한다. 즉 0 섹터의 시작 주소는 0x800000(8Mbyte) + 512 * 0 이 되고, 1 섹터는 0x800000(8Mbyte) + 512 * 1이 되는 것이다.

 반면에 클러스터의 주소는 Data Area의 다음에 위치하는 공간을 512Byte로 나눈 인덱스를 의미한다. 즉 FAT 영역이 16Kbyte를 차지하므로 0번 클러스터의 시작 주소는 0x800000(8Mbyte) + 16Kbyte + 512 * 0 이 되고 1번 클러스터의 시작 주소는 0x800000(8Mbyte) + 16Kbyte + 512 * 1이 된다.

1.5 파일 시스템 기능 요약

2.구현

 파일 시스템이나 메모리 관리 같이 세세한 디버깅이 필요한 부분은 커널을 실행하여 테스트하기가 까다롭다. 특히나 Step By Step 형식으로 접근하기 힘든 커널 디버깅은 복잡한 부분에 대한 분석이 더욱 힘들다. 따라서 알고리즘이 결정되면 Visual C++과 같은 개발툴로 알고리즘을 검증하여 정상 동작함을 확인하고 이것을 포팅하는 것이 효율적이다. 실제로 프레임워크의 동적 메모리 할당 코드와 파일 시스템 코드를 Visual C++로 코딩하여 각 케이스를 모두 테스트한 뒤 포팅하였다.

2.1 Visual C++ 코드

 Visual C++과 프레임워크의 차이라면 같은 역할을 하는 함수의 이름(memset -> kMemSet, memcpy -> kMemCpy 등등)이 다른 점과 주소공간(프레임워크는 8M~12M의 공간 사용, Visual C++에서는 임의의 할당된 메모리 공간 사용)이 다른 점 정도다. 이 정도의 차이는 매크로를 정의하면 쉽게 포팅할 수 있다. 자세한 부분은 첨부에 포함된 Visual C++용 프로젝트 파일을 참고하자.

<Visual C++에서 파일 시스템 코드를 실행한 화면>

2.2 프레임워크 코드

2.2.1 FileSystem.h 수정

 아래는 위에서 언급한 기능들을 정의해 놓은 FileSystem.h 파일이다.

1. /**
       File System Management
           파일 시스템에 대한 처리
2.     Written KKAMAGUI, http://kkamagui.egloos.com
   */
   #ifndef __FILESYSTEM_H__
   #define __FILESYSTEM_H__
3. //#include <windows.h>
   #include "../FW/DefineMacro.h"
4. // 클러스터와 섹터의 크기 정의
   #define SECTORSIZE  512
   #define CLUSTERSIZE SECTORSIZE
5. // 램디스크을 위한 메모리 주소의 시작과 끝
   #define RAMDISK_START_ADDRESS   ( 8 * 1024 * 1024 )
   #define RAMDISK_END_ADDRESS     ( 12 * 1024 * 1024 )
6. // 램디스크 크기 및 기타 데이터
   #define RAMDISK_SIZE            ( RAMDISK_END_ADDRESS - RAMDISK_START_ADDRESS )
   #define RAMDISK_DATA_START_ADDRESS  ( RAMDISK_SIZE / SECTORSIZE * 2 )
   #define RAMDISK_FATENTRYCOUNT       ( RAMDISK_SIZE / SECTORSIZE )
7. // 디렉토리 엔트리의 속성 정의
   #define DIRECTORY_ENTRY_FILE        0x01
   #define DIRECTORY_ENTRY_DIRECTORY   0x02
8. // 디렉토리 엔트리 구조체
   typedef struct directoryEntry
   {
       char vcName[ 11 ];
       BYTE bAttribute;
       WORD wClusterIndex;
       WORD wSize;
   } DIRECTORYENTRY, * PDIRECTORYENTRY;
9. 
   // 함수 목록
   void InitFileSystem( void );
   BOOL MakeFile( char* pcAbsPath, BYTE bAttribute );
   BOOL DeleteFile( char* pcAbsPath );
   BOOL FindDirectoryClusterFromAbsPath( char* pcAbsPath, int* piClusterIndex );
   BOOL ReadCluster( int iClusterIndex, BYTE* pbBuffer );
   BOOL WriteCluster( int iClusterIndex, BYTE* pbBuffer );
10. #endif /*FILESYSTEM_H_*/

  파일 및 디렉토리를 생성하고 삭제하는 기능과 클러스터를 읽고 쓰는 기능을 지원한다. 클러스터에 링크를 연결하는 기능이 구현되어있으나 파일 생성 및 클러스터 링크 기능은 지금 사용하지 않으므로 헤더 파일에 포함시키지 않았다. 현재는 파일 및 디렉토리 엔트리를 디렉토리 구조에 생성하고 삭제하는 기능만 포함되어있으니 추후 필요하면 확장하도록 하자.

 FileSyste.c 파일은 내용이 많으므로 아래 첨부에서 소스를 다운받아 보도록 하자. 위에서 언급한 설계대로 구현 했기 때문에 문서와 같이 보면 크게 어렵지 않을 것이다.

2.2.2 KShell.c/h 수정

 디렉토리를 생성하는 명령 mkdir과 디렉토리를 삭제하는 명령 rmdir, 그리고 디렉토리를 표시하는 명령 ls를 ProcessCommand() 함수에 추가하였다.

1.  /**
       엔터가 쳐졌으면 버퍼의 내용으로 명령어를 처리한다.
   */
   void ProcessCommand(char* vcCommandBuffer, int* piBufferIndex)
   {
       char vcDwordBuffer[ 8 ];
       static DWORD vdwValue[ 10 ];
       static int iCount = 0;
2. ...... 생략 ......
3.     // Directory를 출력한다.
       else if( ( *piBufferIndex > 3 ) &&
                ( kMemCmp( vcCommandBuffer, "ls", 2 ) == 0 ) )
       {
           vcCommandBuffer[ *piBufferIndex ] = '\0';
           PrintDirectory( vcCommandBuffer + 3 );
       }
       // Directory를 만든다.
       else if( ( *piBufferIndex > 6 ) &&
                ( kMemCmp( vcCommandBuffer, "mkdir", 5 ) == 0 ) )
       {
           vcCommandBuffer[ *piBufferIndex ] = '\0';
           MakeFile( vcCommandBuffer + 6, DIRECTORY_ENTRY_DIRECTORY );
       }
       // Directory를  지운다.
       else if( ( *piBufferIndex > 6 ) &&
                ( kMemCmp( vcCommandBuffer, "rmdir", 5 ) == 0 ) )
       {
           vcCommandBuffer[ *piBufferIndex ] = '\0';
           DeleteFile( vcCommandBuffer + 6 );
       }   
   }
4. ...... 생략 ......
5. /**
       디렉토리를 출력한다.
   */
   void PrintDirectory( char* pcPath )
   {
       int iClusterIndex;
       BYTE vbCluster[ CLUSTERSIZE ];
       DIRECTORYENTRY* pstEntry;
       int i;
       char vcBuffer[ 8 ];
6.     kPrintf( "==== Directory = [%s] ====\n", pcPath );
      
       // Path로 Cluster를 찾는다.
       if( FindDirectoryClusterFromAbsPath( pcPath, &iClusterIndex ) == FALSE )
       {
           kPrintf( "Error!!! Can't Find Cluster\n" );
           return ;
       }
7.     // Cluster를 읽는다.
       if( ReadCluster( iClusterIndex, vbCluster ) == FALSE )
       {
           return ;
       }
8.     // 클러스터를 모두 돌면서 Entry를 뽑는다.
       pstEntry = ( DIRECTORYENTRY* ) vbCluster;
       for( i = 0 ; i < ( CLUSTERSIZE / sizeof( DIRECTORYENTRY ) ) ; i++ )
       {
           if( pstEntry->vcName[ 0 ] == '\0' )
           {
               pstEntry++;
               continue;
           }
          
           kPrintf( "%s     ", pstEntry->vcName );
9.         if( pstEntry->bAttribute == DIRECTORY_ENTRY_FILE )
           {
               kPrintf( "%s     ", "FILE" );
           }
           else
           {
               kPrintf( "%s     ", "DIRECTORY" );
           }
10.         kPrintf( "%X    %X\n", pstEntry->wSize, pstEntry->wClusterIndex ); 
            pstEntry++;
        }
        kPrintf( "\n" );
    }

3.Simple File System의 효용성

 앞서 설명했듯이 이 파일 시스템은 작은 용량의 램을 할당받아 저장매체로 사용하는 램디스크이다. 램디스크의 특성상 재부팅하면 내용이 사라진다. 저장매체라면 당연히 그 정보가 남아있어야 하는데, 그러한 관점에서 보면 이 램디스크는 쓸모 없는 것이 아닌가?

 물론 데이터가 유지되지 않는다는 점에서 크게 마이너스지만... 램 디스크의 특성이 그러하듯 매우 빠른 검색과 파일 생성/디렉토리 생성이 가능하다. 그렇기에 새로운 파일 시스템의 테스트용으로 아주 적절하다(같은 수의 파일을 생성했다가 지운다고 가정할때 하드디스크가 빠르겠는가? 램디스크가 빠르겠는가?)

 재부팅 후에 내용이 사라지는 문제도 쉽게 해결할 수 있다. 주기적으로 램디스크의 내용을 하드디스크에 덤프하여 보관하고 OS가 부팅되었을때 하드디스크의 내용을 메모리로 로드하면 된다. 추후 램디스크의 내용이 보관되어야 하거나 지속적으로 관리되어야 하는 경우 위의 방법으로 해결하면 된다. 혹시나 파일 시스템이 너무 간단하여 쓸일이 있을까 하는 사람들을 위해 노파심에 끄적여 보았다. 기능이 부족하다고 생각되면 필요에 맞게 수정하면되니 너무 걱정하지 말자.

4.마치면서...

 이상으로 간단한 파일 시스템을 구현해 보았다.

5.첨부

5.1 프레임워크 1.0.3 이전 버전

5.2 프레임워크 1.0.3 이후 버전

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

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

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

<비트 마스크 덤프1>

<비트 마스크 덤프2>

5.마치면서...

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

6.첨부

6.1 프레임워크 1.0.3 이전 버전

6.2 프레임워크 1.0.3 이후 버전

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

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

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

들어가기 전에...

0.시작하면서...

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

1.메모리 공간 할당

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

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

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

2.메모리 할당 정책

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

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

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

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

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

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

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

 위와 같은 알고리즘을 계속하여 반복하므로 가변 길이의 블럭이 할당과 해제를 반복했을 때 발생하는 단편화(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 블럭 반납-블럭 통합> 

<블럭 통합 완료>

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

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 크기의 비트마스크가 필요하다. 이를 반복하면 각 메모리 블럭당 필요한 바이트 수를 구할 수 있다.

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

1. // 동적 할당을 정보를 저장할 구조체
   // 최대 비트마스크의 크기인 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하여 할당하므로 메모리 할당 요청시에 적당한 크기의 블럭을 찾는 함수
• 비트 마스크를 조작하는 함수
• 버디 블럭 알고리즘으로 블럭을 할당하고 해제하는 함수

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

1. void InitMemory( void );
   void* AllocMemory( int iSize );
   BOOL FreeMemory( void* pvAddress );
2. 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 초기화 함수를 추가한다.

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

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

1. /**
       엔터가 쳐졌으면 버퍼의 내용으로 명령어를 처리한다.
   */
   void ProcessCommand( int* piX, int* piY, char* vcCommandBuffer,
                        int* piBufferIndex)
   {
       char vcDwordBuffer[ 8 ];
       static DWORD vdwValue[ 10 ];
       static int iCount = 0;
2. ...... 생략 ......
3. 
   // 메모리를 할당받는다. 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 );
4.         // 할당된 주소
           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 );
       }
   }
5. ...... 생략 ......
6. /**
       Memory의 상태를 Dump해서 표시한다.
   */
   void DumpMemory( int* piX, int* piY )
   {
       int i;
       int j;
       BYTE* pbMask;
       char vcDwordBuffer[ 8 ];
       int iFindCount;
7.     // 블럭중에 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;
8.         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 부분을 아래와 같이 수정한다.

1. #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 버전 이전

7.2 프레임워크 1.0.3 버전 이후

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

Part15. Tutorial3-동기화(Synchronization) 기능을 추가해 보자

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

들어가기 전에...

0.시작하면서...

 앞서 멀티 태스킹 기능을 추가하면서 동기화가 얼마나 중요한지 느꼈을 것이다. 잘 모르겠다면 커널 크래쉬 화면을 한번 더 보고 오자. 단순히 3개의 태스크만 실행되는 스케줄러를 구현하는데도 동기화 문제가 발생하니, 윈도우와 같이 수백개의 태스크가 동작하는 OS에서 동기화는 PC의 CPU 만큼이나 중요한 문제다.

 효율적인 동기화를 위해 몇가지 동기화 오브젝트를 설계하고 구현해보자.

1.동기화 객체(Synchronization Object)

 이번에 구현해볼 동기화 객체는 세머포어(Semaphore)와 뮤텍스(Mutex)이다. 사실 뮤텍스는 카운트가 1인 바이너리 세머포어와 기능이 비슷하기 때문에 세머포어를 구현하고 그것을 이용해서 뮤텍스를 구현하도록 하자. 뮤텍스는 소유의 개념이 포함되어있어 바이너리 세마포어와는 차이가 있지만  세부적인 내용은 넘어가도록 하자(궁금한 사람은 구글링을 @0@)/~)

 윈도우 프로그래밍을 어느정도 해본 사람, 혹은 스레드 프로그래밍을 어느정도 해본 사람이라면 세머포어와 뮤텍스에 대해서 이미 알고 있을 것이다.

 그래도 혹여나 모르는 사람들이 있을까봐 간단히 용도를 설명하겠다.

 여러 태스크에서 하나의 공유된 자원(글로벌 변수 or IO 장치 등등)에 접근하게되면 서로 경쟁을 하게 된다. 이 공유된 자원을 순차적으로 사용하고 반납하게 되면 자원에 동시에 접근했을 때 발생하는 문제를 해결할 수 있고, 태스크 간의 "순차적인 사용"을 컨트롤 하기위해 세머포어나 뮤택스를 사용한다.

 앞서 Tutorial에서 멀티태스크의 기능을 구현할 때 스케줄러의 예를 보면 잘 알 수 있다. 글로벌 구조체인 gs_stScheduler가 태스크 간에 공유된 자원이었고 무차별하게 접근할때 커널 크래쉬가 발생했다. 이것을 kLock()과 kUnlock() 메소드를 사용하여 태스크 간의 접근을 컨트롤하였고 스케줄러가 정상적으로 동작할 수 있었다. 잘 기억이 안나는 사람은 Part14. Tutorial2-멀티 태스킹(Multi Tasking) 기능을 추가해 보자를 다시 보도록 하자.

2.세머포어(Semaphore) 설계

 세머포어는 크게 카운팅 세머포어(Counting Semaphore)와 바이너리 세머포어(Binary Semaphore)로 나뉘어진다. 두 세머포어의 차이점은 자원에 진입할 수 있는 태스크의 수가 단 한개만 가능한가, 아니면 n개가 가능한가 차이밖에 없다. 세머포어의 사용법은 동기화가 필요한 영역에 진입할 때 On()을 하고 작업을 완료하면 Off()를 호출하는 방식으로 사용하며 On과 Off 사이의 코드는 세머포어의 종류에따라 하나의 태스크만 실행가능하거나 n개의 태스크만 실행할 수 있다.

 세머포어를 깃발과 방으로을 생각하면 이해하기가 좋다. 어떤 방에 들어가는데, 방에 들어가면 입구에 깃발을 하나 올리고 방에서 나오면 깃발을 하나 내린다. 만약 내가 들어갈 차례인데 깃발이 전부 올려져 있으면 누군가 나와서 깃발을 내릴 때까지 기다렸다가 들어가는 방식이다.

 카운팅 세머포어를 구현하기 위해서는 진입 가능한 태스크의 최대 개수, 현재 진입한 태스크의 수를 포함하는 세머포어 자료구조가 필요하다. 이를 아래와 같이 선언하자.

1. // Semaphore 구조체
   typedef struct semaphoreStruct
   {
       BOOL bLock;
       int iMaxTask;
       int iCurTask;
   } SEMAPHORE, * PSEMAPHORE;

 중요하게 볼 부분은 bLock 부분인데, 세머포어의 변수들 또한 공유되는 자원이므로 이 자원을 수정할 수 있는가 판단하는 플래그가 필요하다. 이 플래그가 없으면 어떻게 될까? 세머포어의 변수를 설정하고 비교하는 부분 역시 여러 태스크가 접근할 것이므로 역시 엉망이 될 것이다(커널 크래쉬를 잊지말기를 바란다).

3.구현

3.1 세머포어(Semaphore) 구현

 위에서 세머포어에 대해 간략히 설계했으므로 이제 코드를 작성해 보자. iMaxTask 변수는 최대로 진입 가능한 태스크의 수로 사용하고 iCurTask는 현재까지 진입한 태스크의 수로 사용한다면, 초기화/On/Off 코드는 아래와 같이 쓸 수 있다.

1. /**
       Semaphore를 초기화 한다.
   */
   void InitSemaphore( SEMAPHORE* pstSema, int iMaxTask )
   {
       kMemSet( pstSema, 0, sizeof( SEMAPHORE ) );
       pstSema->iMaxTask = iMaxTask;
   }
2. /**
       Semaphore를 점유한다.
   */
   BOOL OnSemaphore( SEMAPHORE* pstSema )
   {
       // 세머포어 변수에 접근하기위해 접근이 가능한지를 확인하고 접근 가능하면
       // 접근 금지를 설정한 후 변수를 본다.
       while( 1 )
       {
           if( kLock( &( pstSema->bLock ) ) == FALSE )
           {
               SwitchTask();
               continue;
           }
3.         if( pstSema->iCurTask + 1 <= pstSema->iMaxTask )
           {
               break;
           }
           else
           {
               kUnlock( &( pstSema->bLock ) );
               SwitchTask();
           }
       }
4.     pstSema->iCurTask++;
5.     // 세버포어 변수에 대한 접근 금지를 해제한다.
       kUnlock( &( pstSema->bLock ) );
6.     return TRUE;
   }
7. /**
       Semaphore를 해제한다.
   */
   BOOL OffSemaphore( SEMAPHORE* pstSema )
   {
       // 세머포어 변수에 접근하기위해 접근이 가능한지를 확인하고 접근 가능하면
       // 접근 금지를 설정한 후 변수를 본다.
       while( 1 )
       {
           if( kLock( &( pstSema->bLock ) ) == FALSE )
           {
               SwitchTask();
               continue;
           }
8.         if( pstSema->iCurTask > 0 )
           {
               break;
           }
           else
           {
               kUnlock( &( pstSema->bLock ) );
               SwitchTask();
           }
       }
9.     pstSema->iCurTask--;
10.     // 세버포어 변수에 대한 접근 금지를 해제한다.
        kUnlock( &( pstSema->bLock ) );
11.     return TRUE;
    }

  초기화하는 함수는 쉽게 이해가될테니 넘어가고 OnSemaphore()와 OffSemaphore() 함수를 보자. 낯이 익은 함수가 보이지 않는가? kLock()과 kUnlock() 함수가 여러번 나오는데, 이 함수는 Atomic하게 동작하는 함수로 아래와 같은 역할을 한다.

 위의 함수 설명과 세머포어 코드를 같이 보면 전체적인 흐름을 이해하는데 문제가 없을 것이다. 위의 코드를 순서대로 나열하면 아래와 같다.

 여기서 잠깐... 세머포어를 구현하는데 꼭 필요한 것이 Atomic Operation이라는 것을 알았다. 그러면 어떻게 Atomic Operation을 구현할 수 있을까? Atomic함을 보장하기위해서 필요한 것은 무엇일까?

 그것은 명령을 수행할 때 도중에 인터럽트되지 않고 처리를 끝내는 것이다. 아래와 같이 인터럽터를 Disable 함으로써 간단히 Atomic Operation을 구현할 수 있다(Single CPU라고 가정한다).

1. ;  BYTE *pbFlag : 옛날버전
   ;     인터럽터를 Disable 시키고, 플래그를 검사하여
   ;  플래그의 값이 0 이면 1로 증가시키고 1을 리턴하고,
   ;  플래그의 값이 1 이면 0을 리턴한다.
   _kLockOld:
     push    ebp
2.   mov     ebp, esp
     push    ebx
     pushfd
3.   ; 플래그의 포인터를 얻는다.
     mov     ebx, dword [ss:ebp + 8]
     ; 인터럽터 Disable
     cli
     mov  al, byte [ds:ebx]
     cmp  al, 0
     ; 일단 FALSE를 셋팅해 놓고
     mov  eax, 0x00000000
     jne  kLockExit
4.   mov  byte [ds:ebx], 0x01
     mov  eax, 0x01
5.  kLockExit:
     popfd
     pop     ebx
     pop     ebp
     retn
6. ;  BYTE *pbFlag : 옛날 버전
   ;     인터럽터를 Disable 시키고 플래그를 검사하여
   ;  플래그의 값이 1 이면 0로 감소시키고 1을 리턴하고
   ;  플래그의 값이 0 이면 0을 리턴한다.
   _kUnlockOld:
     push    ebp
7.   mov     ebp, esp
     push    ebx
     pushfd
8.   ; 플래그의 포인터를 얻는다.
     mov      ebx, dword [ss:ebp + 8]
     ; 인터럽터 Disable
     cli
     mov  al, byte [ds:ebx]
     cmp  al, 1
     ; 일단 FALSE를 셋팅해 놓고
     xor      eax, eax
     jne  kUnLockExit
9.   mov  byte [ds:ebx], 0
     mov  eax, 0x01
10.  kUnLockExit:
      popfd
      pop  ebx
      pop      ebp
      retn

  주석에 표시된대로 더 이상 사용되지 않는다(프레임워크 처음 릴리즈시 버전). 위에서 보듯 인터럽트를 불가로 설정하고 다시 인터럽터 관련 플래그(EFLAG) 레지스터를 복원하는 방식으로 Atomic을 보장했다. 하지만 이 방법의 문제점은 너무 자주 인터럽트를 불가로 설정하기 때문에 인터럽트 처리가 지연될 수 있다.

 Intel Architecture Manual의 Volume 2 Instruction Set을 보면 Atomic한 처리를 위한 명령어들이 나와있다. lock 명령과 xchg, cmpxchg 명령이 그것이다.

 cmpxchg mem, reg 명령어의 역할은 아래와 같다(자세한 설명은 Intel Architecture Volume 2, Instruction Set 문서를 참고하도록 하자).

 아래는 lock, cmpchg를 이용해서 수정한 코드다.

1. ;  BYTE *pbFlag :
   ;  플래그의 값이 0 이면 1로 증가시키고 1을 리턴하고,
   ;  플래그의 값이 1 이면 0을 리턴한다.
   _kLock:
     push    ebp
     mov     ebp, esp
     push ebx
2.   mov  al, 0
     mov  ah, 1
3.   mov  ebx, dword [ss:ebp + 8 ]
     ; 메모리의 값이 al과 같으면 ah를 메모리에 넣고 zf를 1로 셋팅
     lock cmpxchg byte [ds:ebx], ah
     je  LOCKSUCCESS
     mov  eax, 0
     jmp  LOCKEND
4. LOCKSUCCESS:  
     mov  eax, 1
     jmp  LOCKEND
5. LOCKEND:
     pop ebx
     pop ebp
     retn
6. ;  BYTE *pbFlag : 옛날 버전
   ;     인터럽터를 Disable 시키고 플래그를 검사하여
   ;  플래그의 값이 1 이면 0로 감소시키고 1을 리턴하고
   ;  플래그의 값이 0 이면 0을 리턴한다.
   _kUnlock:
     push ebp
     mov ebp, esp
     push ebx
7.   mov  al, 1
     mov  ah, 0
8.   mov  ebx, dword [ss:ebp + 8 ]
     ; 메모리의 값이 al과 같으면 ah를 메모리에 넣고 zf를 1로 셋팅
     lock cmpxchg byte [ds:ebx], ah
     je  UNLOCKSUCCESS
     mov  eax, 0
     jmp  UNLOCKEND
9. UNLOCKSUCCESS:  
     mov  eax, 1
     jmp  UNLOCKEND
10. UNLOCKEND:
      pop ebx
      pop ebp
      retn

3.2 KShell.c/h 수정

 자 그럼 이제 세머포어를 사용해보자. kShell.c 파일을 아래와 같이 수정한다.

1. SEMAPHORE gs_stSema;      <= 세머포어 구조체 정의
2. /**
       KShell 의 Main
   */
   void Shell()
   {
       InitScheduler();
       InitSemaphore( &gs_stSema, 1 );   <= 세머포어 초기화, 하나의 태스크만 실행가능하도록 설정
3.     // 새로운 태스크 등록
       AddTask( EdgeDraw );
       EnableScheduler( TRUE );
      
       ShellLoop();
4.     while( 1 );
   }
5. /**
       글로벌 변수에서 값을 읽어서 문자를 찍어주는 함수
   */
   int gs_iX = 0;
   int gs_iY = 0;
   void Print( BYTE bCh )
   {
       int i;
6.     printchxy( gs_iX, gs_iY, bCh );
      
       // 약간의 Delay를 위해 사용
       kIdle();
7.     printchxy( gs_iX, gs_iY, ' ' );
   }
8. /**
       테두리를 그려주는 태스크
   */
   void EdgeDraw( void )
   {
       int i;
       int j;
       BYTE bCh;
       int k;
       char vcBuffer[ 8 ];
       int iTID;
9.     i = 0;
       j = 0;
       bCh = 0;
       iTID = GetCurrentTID();
      
       kDToA( vcBuffer, iTID );
10.     for( k = 0 ; k < 50000 ; k++ )
        {
            printxy( 0, 23 - iTID, "=EdgeDraw Task Work=" );
            printxyn( 20, 23 - iTID, vcBuffer, 8 );
11.         // 콘솔 테두리를 돌면서 .을 찍는다.
            for( i = 30 ; i < 79 ; i++ )
            {
                // Semaphore 대기
                OnSemaphore( &gs_stSema );
                gs_iX = i;
                gs_iY = 23 - iTID;
                Print( bCh );
                bCh++;
                OffSemaphore( &gs_stSema );
                SwitchTask();
            }
        }
    }

  위에 파란색 부분을 보면 Print() 함수가 새로 정의되었는데, 글로벌 변수 gs_iX, gs_iY에서 값을 읽어 화면에 한 문자를 출력했다가 일정시간 뒤에 다시 공백으로 지우는 역할을 하는 함수이다. EdgeDraw()에서 수정된 부분은 OnSemaphore()/OffSemaphore() 함수를 사용하고 그 안에 글로벌 변수 X,Y에 값을 설정한 후 Print() 함수를 호출한 부분이다.

 각 태스크가 공유 자원인  gs_iX 및 gs_iY에 접근하여 값을 설정하고 Print() 함수를 호출하여 다시 공유자원의 값을 사용하는 구조이다. 이것을 빌드하여 이미지를 만든 다음 Virtual Box에서 실행한 상태에서 starttask 명령을 3번정도 입력하여 화면을 지켜보자.

<Start Task With Semaphore>

  위와 같은 화면이 표시될 것이다. starttask를 3번 사용하여 총 4개의 task를 생성하였고 각각의 태스크는 문자를 보여주고 지워졌다가 다시 다른 문자를 보여주는 아주 깔끔한 화면을 보여준다. 세머포어가 동시에 수행될 수 있는 태스크의 수를 1개로 하여 생성되었기때문에 글로벌 변수에 값을 설정하고 화면에 값을 출력하기까지 다른 태스크가 끼어들지 못하여 이러한 결과가 나온 것이다.

 하지만  OnSemaphore()와 OffSemaphore() 함수를 주석처리하고 다시 실행해보자.

<Start Task Without Semaphore>

 절대 일부러 합성한 화면이 아님을 미리 알려둔다. 글로벌 변수에 값을 설정하고 Print() 함수를 호출하는 과정에서 중간 중간에 태스크 스위칭이 되어 다른 태스크가 끼어든 결과이다. 정상적으로 문자가 출력되지 않고 또한 제대로 지워지지도 않는다.

 예제로 들기에는 약간 부족한 면이 있지만 이것으로 세머포어의 역할이나 구현에 대해서 어느정도 감을 잡았으리라 생각된다.

4.뮤텍스(Mutex)

 뮤텍스는 바이너리 세머포어와 비슷하다. 다만 다른점은 뮤텍스는 소유의 개념이 있어서 On 시에 태스크 ID를 저장해 두고 Off 시에 태스크 ID를 비교해서 On을 수행한 태스크만 처리가 가능하다.

 그럼 어떤 방식으로 뮤텍스를 구현할 수 있을까?  아래와 같이 구현하면 된다.

• OnMutex() : 위에서 보았던 세머포어 구조체에 TID 필드를 추가하고 OnMutex() 함수를 만든뒤 바이너리 세머포어와 동일하게 구현한다. 그리고 마지막에 TID를 보관한다.
•  OffMutex() : 가장  먼저 TID를 비교하여 OnMutex()를 실행한 태스크인지 비교한뒤 바이너리 세머포어의 Off 함수와 동일하게 구현한다.

 크게 어렵지 않은 부분이므로 각자 구현해 보도록 하자.

5.마치며...

 이제 동기화 객체도 생성되었으니 멀티 태스킹 프로그래밍을 마음껏 할 수 있다(정말?? ㅡ,.ㅡ;;;). 부담없이 태스크를 만들고 돌려보자. @0@)/~

6.첨부

6.1 프레임워크 1.0.3 이전 

6.2 프레임워크 1.0.3 이후

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

Part14. Tutorial2-멀티 태스킹(Multitasking) 기능을 추가해 보자

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

들어가기 전에...

0.시작하면서...

 프레임워크에서 태스크 스위칭(Task Switching)을 구현하는 방법에 대한 내용은 참고. Multi Tasking 구현 방법에 설명해 놓았으니 참고하도록 하고, 여기서는 간단한 스케줄러를 구현하는 것을 목표로 하자.

1.태스크 스위칭(Task Switching) 관련 함수

 00Kernel/Custom/KShell.c 파일을 열어보면 기본적인 태스크 스위칭 코드가 포함되어있다.

1. // Task를 저장한다.
   TASK vstTask[ 2 ];char g_vcPrompt[8] = "[FRAME] ";
   int g_iCurrentTask;
   BOOL g_bScheduleStart = FALSE;
2. /**
       Timer Callback에서 수행되는 Scheduling 함수
   */
   void Scheduler( void )
   {
       if( g_bScheduleStart == FALSE )
       {
           return ;
       }
       g_iCurrentTask = abs( 1 - g_iCurrentTask );
       kSwitchTask( &( vstTask[ abs( 1- g_iCurrentTask ) ] ),
           &( vstTask[ g_iCurrentTask ] ) );
   }
3. /**
       KShell 의 Main
   */
   void Shell()
   {
       // Task 설정 kSetupTask( &( vstTask[ 0 ] ), ShellLoop, NULL );kSetupTask( &( vstTask[ 1 ] ), EdgeDraw, NULL );    g_iCurrentTask = 0;
       g_bScheduleStart = TRUE;
4.     ShellLoop();
   }

 위의 파란색 부분이 스위칭에 관련된 부분이다. Shell() 함수와 Scheduler() 함수를 보면 2개의 태스크를 설정하고 두 태스크를 번갈아가면서 호출하는 것을 알 수 있다. 여기서 눈여겨 봐야 하는 함수 2개는 kSetupTask()와 kSwitchTask() 이다(참고. 프레임워크 주요 함수들 내용 참고). 

• kSetupTask() : 태스크 구조체와 태스크의 엔트리 포인트, 그리고 태스크 종료 시 호출될 함수의 엔트리 포인트를 받아서 태스크를 설정하는 역할 수행. 태스크 구조체를 생성하는 함수
• kSwitchTask() : 현재 수행중인 태스크를 저장할 태스크 구조체와 다음에 실행할 태스크를 로드할 태스크 구조체를 받아서 두개를 스위칭하는 역할 수행. 태스크 스위칭을 수행하는 함수

 kSetupTask() 함수의 마지막 파라메터는 NULL로 설정가능한데, 디폴트 태스크 종료 핸들러를 부르겠다는 의미로 사용된다.

 디폴트로 설정된 태스크 종료 함수는 kEndTask()로 설정되어있고 아래와 같다.

1. /**
       Task의 종료 처리
   */
   void kTaskEnd( void )
   {
       // 필요한 뭔가를 하자
       while( 1 ) ;
2. }

 만약 위의 무한 루프 코드를 삭제하면 어떻게 될까? 그럼 kTaskEnd() 함수에서 return을 하게되는데 이때 스택은 Top이 Bottom을 지나가게되고 알 수 없는 곳으로 점프하여 이상한 코드를 실행하게 될 것이다. 운이 좋으면 수십초 정도 지나서 Fault가 발생할 것이고, 운이 나쁘면 점프한 즉시 Fault가 발생하여 커널이 정지 된다. @0@)/~ 

 이런 수습이 불가능한 상황을이 되기전에 막아야 하므로, 디폴트 핸들러는 무한 루프를 실행하여 다른 곳으로 가지 못하게 한다.

2.간단한 스케줄러 설계

 자 이제 간단한 스케줄러에 대한 이야기를 해보자. 우리가 만들 스케줄러는 아래와 같다.

 그럼 이제 구현을 위해 수정해야할 부분을 하나하나 살펴보자.

3.구현

3.1 Task.c/h 파일 수정

 일단 태스크 구조체를 조금 수정해서 태스크를 링크드 리스트의 형태로 만들 수 있도록 하자. FW/Task.h 파일을 열어서 TASK 구조체가 아래와 같이 되어있는 지 확안하고 그렇지 않다면 수정하자.

1. // Task에 대한 정보 저장
   typedef struct kTaskStruct
   {
       // Stack의 15DWORD를 Register를 저장하는데 사용한다.
       DWORD vdwStack[ MAX_STACKSIZE ];
2.     int iTID; 
3.     struct kTaskStruct* pstNext;
   } TASK, *PTASK;

 언제나 그렇듯이 파란색 부분이 주의깊게 볼 부분이다. 태스크 구분을 위한 iTID를 추가하고 다음 태스크 구조체를 연결하기위한 pstNext 부분을 추가했다.

 아래 함수는 FW/Tash.c 파일에 포함된 함수인데, 태스크 구조체, 태스크 시작 엔트리 포인트, 태스크 종료 엔트리 포인트를 받아서 태스크 구조체를 설정하는 함수이다. Task가 종료되었을 때 불리는 함수를 설정하는 부분에 버그가 있어서 붉은색 부분을 수정했다. 붉은색 부분을 확인하자.

1. /**
       TASK 구조체를 설정한다.
   */
   BOOL kSetupTask( PTASK pstTask, void* pfStartAddr, void* pfEndAddr ){
       DWORD* pdwStackTop;
2.     // 구조체를 초기화 한다.
       kMemSet( pstTask, 0, sizeof( pstTask->vdwStack ) );
3.     // Stack의 Top
       pdwStackTop = ( DWORD* ) ( pstTask->vdwStack + ( MAX_STACKSIZE - 1 ) );
4.     // ESP, EBP, EFLAG, EAX, EBX, ECX, EDX, ESI, EDI 순으로 Push 한다.
       pstTask->vdwStack[ 14 ] = ( DWORD ) ( pdwStackTop - 1 );
       pstTask->vdwStack[ 13 ] = ( DWORD ) ( pdwStackTop - 1 );
       pstTask->vdwStack[ 12 ] = EFLAG_DEFAULT;
5.     // cs, ds, ss, es, fs, gs는 kernel의 기본값으로 설정해 준다.
       pstTask->vdwStack[ 5 ] = GDT_VAR_KERNELCODEDESC;
       pstTask->vdwStack[ 4 ] = GDT_VAR_KERNELDATADESC;
       pstTask->vdwStack[ 3 ] = GDT_VAR_KERNELDATADESC;
       pstTask->vdwStack[ 2 ] = GDT_VAR_KERNELDATADESC;
       pstTask->vdwStack[ 1 ] = GDT_VAR_KERNELDATADESC;
       pstTask->vdwStack[ 0 ] = GDT_VAR_KERNELDATADESC;
6.     // 마지막으로 Stack의 Return Address를 pfAddr로 설정해 준다.
       pdwStackTop[ -1 ] = ( DWORD ) pfStartAddr;
       // 만약 Task 종료 함수가 설정되지 않으면 Default를 설정
       if( pfEndAddr != NULL )
       {
           pdwStackTop[ 0 ] = ( DWORD ) pfEndAddr;
       }
       else
       {
           pdwStackTop[ 0 ] = ( DWORD ) kTaskEnd;
       }
       return TRUE;
   }

3.2 Scheduler.c/h 파일 추가

 Custom/Scheduler.c/h 파일은 스케줄러의 구현이 들어갈 파일이다. KShell.c 파일에 스케줄러를 구현해도 되지만 코드가 길어지고 쉘과는 크게 관계 없는 부분이므로 따로 구현하는게 좋다.

 아래의 코드는 Scheduler.h에 포함된 스케줄러 관련 구조체이다. 스케줄러의 태스크 관리 부분은 태스크의 pstNext 필드를 이용하여 링크드 리스트(Linked List)를 이용해서 구현했다.

1. // 개수를 너무 크게 설정하면 4M 이상으로 넘어가버린다.
   // 그렇게 되면 커널 스택이 데이터를 덮어쓰게 되서 문제가 발생하므로 적당히 조절해야한다.
2. #define MAX_TASKCOUNT 30
3.  
4. // 스케줄러 구현을 위한 태스크 정보를 포함한 구조체
   typedef struct SchedulerStruct
   {
       int iTaskCount;
   
       // 리스트의 헤더
       TASK* pstHeader;
   
       // 플래그 변수들
       BOOL bEnableScheduler;
       BYTE bLock;
      
       // 현재 수행중인 태스크 ID
       int iCurrentTID;
   
       // 태스크 저장을 위한 공간
       BOOL vbAlloc[ MAX_TASKCOUNT ];
       TASK vstTask[ MAX_TASKCOUNT ];
   } SCHEDULER,* PSCHEDULER;

 태스크를 추가하고 삭제하는 것에 대한 세부 내용은 그리 어렵지 않으므로 첨부파일을 살펴보도록 하고, 약간의 트릭이 가미된 부분을 중점적으로 살펴보자.

 스캐줄러를 구현할 때마다 고민하는 부분이기도 한데... 구현에 문제가 되는 부분이 태스크가 자신의 ID를 알아내는 방법이다. 태스크가 자신의 ID 즉 TID가 얼마인지 어떻게 알까? 가장 쉬운 방법은 스케줄러가 현재 태스크의 ID를 글로벌 변수 같은데 저장하고 태스크가 그 변수에 접근해서 읽는 것이다.

 이 방식을 사용한다면 태스크 스위칭 시에 글로벌 변수에서 자기 ID를 읽어온 뒤에 다음 태스크를 검색하여 찾고, 스위칭 하기 전에 글로벌 변수에 다음 태스크 번호로 업데이트한 후 스위칭을 완료해야 한다. 왜냐하면 스케줄러가 호출되고 난 뒤는 이미 다른 태스크로 스위칭된 상태이므로 중단되었다가 복원된 태스크가 갑자기 글로벌 변수에 현재 TID를 바꾼다는 것은 기대하기 힘들다.

 그럼 여기서 발생하는 문제!!! 타이머에서 스케줄러 함수를 호출하고 태스크도 수시로 스케줄러 함수를 호출하면 어떻게될까?

 별 다른 처리를 하지 않았다면... 정답은 "엉망이 된다" 이다. ㅡ_ㅡ;;;;  아래 코드를 한번 보자.

1. /**
       다른 태스크를 실행시킨다.
   */
   void SwitchTask( void )
   {
       TASK* pstCurTask;
       TASK* pstNextTask;
2.     pstCurTask = &( gs_stScheduler.vstTask[ GetCurrentTID() ] );
       pstNextTask = pstCurTask->pstNext;
       if( pstNextTask == NULL )
       {
           pstNextTask = gs_stScheduler.pstHeader;
       }
       gs_stScheduler.iCurrentTID = pstNextTask->iTID;
3.     kSwitchTask( pstCurTask, pstNextTask );
4. }

 위의 상황을 실제 코드에서 시뮬레이션 한번 해보자. 커널에 총 3개의 태스크가 존재한다고 생각하고 현재 태스크를 T1이라 하고 T1의 다음 태스크를 T2, T2의 다음 태스크를 T3라고 가정하자.

 태스크가 스케줄러 함수를 호출해서 위의 파란라인까지 실행한다음, 타이머에 의해서 다시 스케줄링이 되면 어떻게 될까? 아직 태스크 스위칭 함수가 호출되지 않은 상태에서 글로벌 변수인 gs_stScheduler.iCurrentTID 값이 T2로 바뀐 상태이므로 타이머에 의해서 스케줄러가 호출되었을 때는 T2의 태스크 구조체에 T1의 태스크를 저장하게 되고 복원되어 실행되는 태스크는 T3가 된다.

 순식간에 T2 태스크가 사라져 버렸다. 그리고 다시는 T2 태스크를 볼 수 없을 것이다.

 실제로 이 코드를 그대로 돌려보면 아래와 같은 기분좋은(??) 크래쉬 화면을 볼 수 있다(General Fault는 코드 실행 시에 발생한 Exception을 의미한다).

<프레임워크 크래쉬 화면>

 정상적으로 실행하기위해서 코드를 어떻게 수정해야 할까? 해결책은 간단하다. 위 코드를 하나의 태스크만 실행하도록 수정하면 된다. 가장 간단한 방법으로는 위 코드의 시작부터 끝까지를 인터럽트 불가로 설정하면 된다. 이렇게 하면 실행에는 문제가 없지만 스위칭을 할때마다 인터럽트가 불가가되니 인터럽트 처리에 문제가 생길 수 있다(인터럽트 지연이 발생한다).

 그럼 다른 방법은 없는걸까? 조금만 더 생각해 보면 인터럽트를 불가해야 하는 부분을 줄일 수 있다. 크게 두가지 부분으로 나눌 수 있는데, 첫번째 부분은 스케줄링 함수를 중복으로 호출하지 못하게 하여 처리할 수 있는 부분이고, 두번째 부분은 인터럽트 불가로 해결해야하는 부분이다.

1. /**
       다른 태스크를 실행시킨다.
   */
   void SwitchTask( void )
   {
       TASK* pstCurTask;
       TASK* pstNextTask;
       DWORD dwFlags;
2.  
3.     // Scheduler를 다른곳에서 호출 못하도록 Lock을 건다.
       if( kLock( &gs_stScheduler.bLock ) == FALSE )
       {
           return ;
       }
4.     pstCurTask = &( gs_stScheduler.vstTask[ GetCurrentTID() ] );
       pstNextTask = pstCurTask->pstNext;
       if( pstNextTask == NULL )
       {
           pstNextTask = gs_stScheduler.pstHeader;
       }
       gs_stScheduler.iCurrentTID = pstNextTask->iTID;
5. 
       // 플래그 레지스터를 저장하고, 인터럽트를 불가로 설정한다.
       dwFlags = kReadFlags32();
       kClearInt();
6.  
7.     kUnlock( &gs_stScheduler.bLock );
8.     kSwitchTask( pstCurTask, pstNextTask );   
       // 플래그 레지스터를 복원하여 이전 인터럽트 플래그를 복구한다.
       kWriteFlags32( dwFlags );
9. }

 위 부분에서 푸른색 부분이 태스크 스위칭을 중복으로 허용하지 않으면 해결할 수 있는 부분이다. 주의해서 볼 것은 붉은 색 부분인데, 이 부분은 인터럽트와 관련된 부분으로 인터럽트 불가를 설정한 뒤 스위칭을 하고 다시 원래의 인터럽트 플래그를 복원하는 코드이다.

 그렇지 않다. 태스크 스위칭 함수를 호출했을 때 복원되고 저장되는 레지스터중에 EFLAG 레지스터(인터럽트나 각종 상태가 저장되어있는 레지스터)가 포함되어 있기 때문이다. 다시 말해 태스크 별로 인터럽트 가능/불가 플래그를 가지고 있으므로 다른 태스크를 복원했을 때 복원한 태스크가 인터럽트 가능 상태였다면 EFLAG 레지스터 복구를 통해 자연스럽게 가능 상태로 설정된다.

 만약 이것을 kUnlock() 함수를 호출해서 태스크 스위칭 불가 플래그를 풀어주는 방법으로 구현한다고 생각해보자. 태스크를 복원했을 때 제일 처음 해야 할일이 kUnlock()을 호출하는 일이기 때문에 여러가지 꼼수를 사용해서 이를 처리해야 하는데 굉장히 복잡하다.(한번 상상을 해보자... 어떻게 구현할 것인지.. ㅡ,.ㅡ;;;).

 플래그(EFLAG) 레지스터는 태스크 스위칭을 하면서 복원되기 때문에 아주 간단하게 인터럽트 불가 영역을 줄이면서 동기화의 문제를 해결할 수 있다.

 뭐 사실 지금 상황에서 인터럽트 불가 영역을 줄이는게 큰 의미가 있겠냐고 의문을 가지는 사람이 있을지도 모르겠다. 스케줄러 전 영역을 태스크 불가로 만들어도 괜찮겠다고 생각하는 사람은 스케줄러 코드가 수십줄이 아니라 수천줄일 때도 괜찮을지 생각해 보기 바란다. 이런 복잡한 스케줄러 코드에서 스케줄러 함수의 시작부터 끝까지 인터럽트를 불가를 한다면? 결과는 상상에 맡기겠다 @0@)/~

 kLock()과 kUnlock() 함수는 Atomic Operation으로 플래그의 값을 변경해주고 그 결과를 리턴값으로 나타내는 함수이다. Atomic Operation은 해당 역할을 끝내기 전에 다른 이유로하여 중단됨이 없다는 것을 보장하는 동작이다. 따라서 세머포어(Semaphore)나 뮤택스(Mutex)와 같은 동기화 객체 구현에 많이 사용된다.

 kClearInt() 함수와 kReadFlags32(), kWriteFlags32() 함수는 플래그(EFLAG) 레지스터와 관련된 함수인데 Intel Architecture에 관련된 부분이라서 자세하게 설명하진 않겠다.  자세한 것은 참고. 프레임워크 주요 함수들과 Part5. Intel Architecture에 대한 소개 문서를 참고하자.

 스케줄러의 전체 파일은 아래에 첨부했다.

3.3 KShell.c/h 파일 수정

 테스트용 코드가 삽입되어있던 부분을 스케줄러 파일로 다 옮기고 간단히 수정한다. 쉘의 전체 파일은 아래의 코드 첨부를 통해 다운 받도록 하자.

1. /**
       KShell 의 Main
   */
   void Shell()
   {
       // 초기화
       InitScheduler();
2.     // 새로운 태스크 등록
       AddTask( EdgeDraw );
3.     EnableScheduler( TRUE );    
       // Shell의 실행
       ShellLoop();
4.     while( 1 );
   }

3.4 makefile 파일 수정(프레임워크 1.0.3 버전 이전)

 프레임워크 1.0.3 버전 이전 사용자는 makefile을 수정해 주어야 한다. Scheduler.c/h 파일을 추가했으니 makefile을 수정하자.

1. # 응용 프로그램 파일
   FW.o : $(CUSTOMDIR)Framework.c
    $(GCC) -o FW.o $(CUSTOMDIR)FrameWork.c
   KShell.o : $(CUSTOMDIR)KShell.c
    $(GCC) -o KShell.o $(CUSTOMDIR)KShell.c
   Sched.o : $(CUSTOMDIR)Scheduler.c $(GCC) -o Sched.o $(CUSTOMDIR)Scheduler.c
2. #Object 파일 이름 다 적기
   #아래의 순서대로 링크된다.
   OBJ = A.o K.o Is.o D.o Int.o Key.o Stdlib.o Task.o FW.o KShell.o Sched.o

 Scheduler.c 파일을 추가했으니 makekernel.bat를 실행해 보자.

4.마치면서...

 이번에 스케줄러 코드를 추가하면서 그 동안 숨겨져왔던 코드들의 버그가 속속들이 드러났다. 디버깅한다고 혼쭐이 났는데... 고생한걸 생각하면 눈물이.. ㅜ_ㅜ...

 기념으로 스크린 샷 하나 올린다. starttask 명령과 showtask 명령이 추가되었다. starttask 함수는 EdgeDraw 태스크를 실행해주는 역할을 하고, showtask 함수는 현재 동작중인 태스크의 개수를 리턴하는 역할을 한다.

<멀티 태스킹 실행 화면>

5.첨부

5.1 프레임워크 1.0.3 버전 이전

 프레임워크 1.0.3 버전 이전 파일이다. 다운 받아서 덮어쓰면 된다(기존 코드의 버그도 같이 수정했다).

5.2 프레임워크 1.0.3 버전 이후

 프레임워크 1.0.3 버전 이후 파일이다. 다운 받아서 덮어쓰면 된다.

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

Part13. Tutorial1-프레임워크에 기능을 추가해 보자

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

들어가기 전에...

0.시작하면서...

 프레임워크를 컴파일-링크해서 이미지를 만든 다음 Virtual Box로 실행하면 까마귀 프레임워크가 시작되었다는 말과 함께 아래에 Edge Task가 돌면서 우측 상단에는 타이머 인터럽트(붉은 색으로 계속 화면에 바뀌어 찍히는 것)가 발생되고 있는 것을 볼 수 있다.

<프레임워크 실행화면>

1.키 입력 및 메시지 출력

 자 그럼 이제 프레임워크에 본격적으로 기능을 몇가지 추가해 보자. 일단 아래에서 돌고 있는 태스크는 무시하고 프레임워크 시작 시에 키 입력을 대기하고 키 입력이 되면 커널 쉘 기능과 태스크를 실행하도록 해보자.

 일단 키 입력을 받아야 하는데, 참고. 프레임워크 주요 함수들의 새창으로 띄워서 보면 키 입력에 관련된 함수를 볼 수 있다. 잘 살펴보면 kGetCh() 라는 함수가 있는데, 이 함수를 이용하면 키를 얻어올 수 있다. 이를 이용해서 키 입력을 대기하였다가 키가 입력이 되면 그 키 값을 화면에 표시하고 정상적으로 쉘과 태스크를 실행하도록 수정해 보자.

 프레임워크 엔트리(void FrameWorkEntry( void )) 함수가 프레임워크에서 처음으로 불리는 함수 이므로 이 부분을 수정하면 된다.

1. 파일명 : Custom/Framework.c
2. void FrameWorkEntry( void )
   {
       BYTE bCh;
3.     // 인사말을 찍는다.
       kPrintxy( 1, 7, "KKAMAGUI OS FrameWork Start" );
4.     // 키 입력을 대기하고 키가 입력되면 키 값을 찍는다.
       kPrintxy( 10, 8, "Wait For Key Input.... Please Input Anythig...");
       bCh = kGetCh();
       kPrintxy( 10, 9, "Your Input Is[ ]" );
       kPrintchxy( 24, 9, bCh );
5.     // 간단한 쉘 실행
       Shell();
   }

 위의 파란색 부분을 추가한 뒤, makekernel.bat, makeimg.bat를 차례로 실행시키거나 프레임워크 1.0.3 버전 이상 사용자라면 make를 실행하여 커널 이미지(disk.img)를 생성하자. 그후 Virtual Box에서 이미지를 실행하면 아래와 같이 나타난다.

<키 입력 전>

 대기 메시지를 표시하고 키 입력을 기다리고 있는 화면이다. 우측 상단에는 타이머 인터럽트가 계속해서 발생함을 표시하고 있다.

 아래는 키 A를 입력한 뒤 화면이다. 입력된 키값(a)이 표시되고  커널 쉘과 태스크가 정상적으로 실행 되었음을 알 수 있다.

<키 입력 후>

2.커널 쉘(Kernel Shell) 기능 추가

 커널 쉘 파일은 콘솔을 구현하기위해 약간 복잡하게 되어있는데, 기능을 추가하기 전에 중요한 부분을 먼저 살펴보자.

 커널 쉘은 키보드에서 값을 입력받아서 엔터까지를 한 라인으로 보고 라인을 분석하여 명령을 실행하는 구조로 되어있다. 아래 함수는 계속해서 키를 입력받고 엔터가 입력이되면 라인을 분석해서 명령을 실행하는 부분이다.

1. /**
       Shell을 처리하는 Loop
   */
   void ShellLoop( void )
   {
       BYTE cCh;
       int iBufferIndex;
       char szCommandBuffer[256];
2.     // 커서를 설정한다.
       kSetCursor( 0, 8 );
       iBufferIndex = 0;
3.     // 커맨드 라인을 출력한다.
       PrintCommandLine();
4.     while(1)
       {
           cCh = kGetCh();
5.         ProcessKeyCode( cCh, szCommandBuffer, &iBufferIndex);
       }
   }
6. /**
       키의 입력이 있으면 키 코드를 받아서 처리하는 함수
   */
   void ProcessKeyCode( BYTE cCh, char* pcCommandBuffer, int* piBufferIndex )
   {
       // 엔터나 Back space 같은 경우는 버퍼에 넣지 않고 특별하게 처리한다.
       if( ( cCh == KEY_ENTER ) || ( cCh == KEY_BSPACE ) )
       {
           ProcessSpecialKey( cCh, pcCommandBuffer, piBufferIndex );
           return ;
       }
7.  // 만약 버퍼가 다 차지 않았으면 화면에 찍고 버퍼에 넣는다.
    if( *piBufferIndex < COMMANDBUFFERSIZE )
    {
           pcCommandBuffer[ *piBufferIndex ] = cCh;
           *piBufferIndex = *piBufferIndex + 1;
           kPrintf( "%c", cCh );
    }
    return ;
   }
8. /**
       특수키에 대한 처리
   */
   void ProcessSpecialKey( BYTE cCh, char* pcCommandBuffer, int* piBufferIndex )
   {
    int iX;
    int iY;
    
    // 만약 리턴이면 스크롤 시켜 본다.
    if( cCh == KEY_ENTER )
    {
     kPrintf( "\n" );
     
     // 버퍼에 든 명령을 실행
     ProcessCommand( pcCommandBuffer, piBufferIndex );
     *piBufferIndex = 0;
     
     // 커맨드라인을 다시 출력한다.
     PrintCommandLine();
    }
    // 만약 백 스페이스 이면 커서를 하나 지우고 뒤로 민다.
    else if( cCh == KEY_BSPACE )
    {
     kGetCursor( &iX, &iY );
     // 버퍼에 데이터가 입력되어 있으면
     // 커서의 위치를 하나 감소하고
     if( *piBufferIndex > 0 )
     {
      if( iX == 0 )
      {
       iX = 79;
       iY = iY - 1;
      }
      else
               {
       iX = iX - 1;
               }
9.    // 문자를 살짝 지워준다.
      kPrintchxy( iX, iY, ' ' );
      kSetCursor( iX, iY );
      *piBufferIndex = *piBufferIndex - 1;
     }
    }
   }
10. /**
        엔터가 쳐졌으면 버퍼의 내용으로 명령어를 처리한다.
    */
    void ProcessCommand(char* vcCommandBuffer, int* piBufferIndex)
    {
        char vcDwordBuffer[ 8 ];
        static DWORD vdwValue[ 10 ];
        static int iCount = 0;
11.     // 화면 지우는 함수
        if( ( *piBufferIndex == 3 ) &&
            ( kMemCmp( vcCommandBuffer, "cls", 3 ) == 0 ) )
        {
    kClearScreen();
        }
    }

 위에서 중요한 부분은 파란색으로 굵게 표시를 했다. 파란색 표시를 죽 따라가면 대충 어떻게 동작하는지에 대해서 알 수 있으므로 자세한 설명은 생략하고, 우리가 기능을 추가하려면 어디를 고쳐야 하는지 알아보자. 위에 붉은 색으로 따로 표시된 ProcessCommand()라는 함수가 있다.

 이 함수의 아래를 보면 Clear Screen(cls) 명령에 대한 처리가 되어있음을 알 수 있다. 라인에 입력된 키 값이 3개이고 그 값이 "cls" 인가를 비교해서 화면을 지우는 간단한 코드이다. 뭔가 감이오지 않는가? 그렇다. 저 곳에 함수를 추가하면 된다.

 자~ 그럼 메모리 총량을 표시하는 "showmem" 이라는 명령을 추가해 보자. 메모리 총량은 참고. 프레임워크 주요 함수들에 보면 kGetTotalRAMSize()라는 함수로 구현되어있다. 이제 명령라인을 추가할 때다.

1. /**
       엔터가 쳐졌으면 버퍼의 내용으로 명령어를 처리한다.
   */
   void ProcessCommand(char* vcCommandBuffer, int* piBufferIndex)
   {
       char vcDwordBuffer[ 8 ];
       static DWORD vdwValue[ 10 ];
       static int iCount = 0;
2.     // 화면 지우는 함수
       if( ( *piBufferIndex == 3 ) &&
           ( kMemCmp( vcCommandBuffer, "cls", 3 ) == 0 ) )
       {
           kClearScreen();
       }
       // 메모리의 정보를 표시한다.
       else if( ( *piBufferIndex == 7 ) &&
                ( kMemCmp( vcCommandBuffer, "showmem", 7 ) == 0 ) )
       {
           kPrintf( "%X\n", kGetTotalRAMSize() );
       }
   }

 위와 같이 수정한 뒤에 빌드하여 커널을 실행하면 아래와 같은 화면이 나타난다(아래 화면은 cls 명령으로 화면을 지운뒤, showmem 명령을 실행한 것이다).

<showmem 명령 실행>

 Virtual Box에 메모리 설정이 8Mbyte로 되어있어서 00000008 이라는 값이 표시되었다.

3.기타

 커널에 기능을 추가하다보면 DWORD의 값을 화면에 출력해야 하는 일이 자주 발생한다. 디버깅 시에도 필수적인 부분인데 kPrintf() 함수를 이용하면 편리하게 할 수 있다.

4.마치면서...

 이번에는 프레임워크에 직접적으로 기능을 추가하는 부분에 대해서 알아보았다. 내가 만든 쉘 코드나 프레임워크 시작 부분이 마음에 들지 않으면 위의 코드를 참조하여 얼마든지 수정해도 된다.

 다른 새로운 기능 추가는 각자의 몫으로 남겨두고 다음에는 멀티태스킹에 대해서 구현해보도록 하자.

5.첨부

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

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

Part12. 커널(Kernel) 및 프레임워크(Framework) 설명

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

들어가기 전에...

0.시작하면서...

 이제야 커널을 설명하게 됬다. 커널을 설명하기까지 참 많은 내용을 다룬 것 같은데, 이번에는 간단히 기능적인 소개만 할 것이므로 편하게 읽으면 된다.

1.FW 폴더 파일 설명

 프레임워크 소스를 열여보면 00Kernel 폴더 아래에 FW 폴더가 있다. 그 안에 세부파일들이 있는데, 이 폴더 아래의 파일들은 프레임워크를 구성하는 핵심 파일들이다.

 각 파일의 역할은 아래와 같다.

2.함수 호출 순서(Call Graph)

2.1 커널 시작 시 함수 호출 순서

 커널이 실행되었을 때, 프레임워크의 엔트리 함수가 불리기까지 과정을 한번 살펴보자.

<커널 시작시 함수 호출 순서>

 Asm.Asm의 kInit() 함수를 시작으로 각 함수가 위와 같은 순서로 호출된다. 맨 마지막에 프레임워크 엔트리 함수를 호출하게 되는데, 프레임워크 엔트리 파일을 수정함으로써 원하는 기능을 추가 할 수 있다.  만약 프레임워크의 기능을 바꾸고 싶으면 위에 흐름을 참조해서 원하는 부분에 기능을 추가하자.

 커널 코드 부분은 C 코드로 되어있고 주석이 어느정도 달려 있으므로 궁금한 사람은 개별적으로 분석하면 된다. 이제 슬슬 커널 프레임워크를 사용해서 커널을 제작하기 시작할텐데, 커널을 제작하면서 많이 쓸만한 함수를 모아서 참고. 프레임워크 주요 함수들에 정리해 두었으니 참고하자.

 이 정도의 함수 정도만 알아도 간단한 커널을 제작하는데 큰 문제가 없을 것이다. 실제로 이보다 훨씬 많은 함수가 있지만 Architecture에 의존적인 부분이 많아서 별로 사용할 일이 없다.

2.2 kInit() 함수의 비밀

 프레임워크에서 가장 먼저 실행되는 함수가 Asm.Asm 파일에있는 kInit() 함수라고 하였다. 다시말하면 1M의 주소에 위치하는 함수가 kInit() 함수라는 말인데, 수많은 함수가 커널 링크 시에 합쳐지는데 어떻게 kInit() 함수를 제일 처음으로 위치시킬 수 있을까? 비밀은 makefile에 있다.

2.2.1 프레임워크 1.0.3 버전 이전

 makefile을 열어보면 아래와 같은 부분을 발견할 수 있다.

1. #Object 파일 이름 다 적기
   #아래의 순서대로 링크된다.
   OBJ = A.o K.o Is.o D.o Int.o Key.o Stdlib.o Task.o FW.o KShell.o
2. Kkernel: $(OBJ)
   ld $(OBJ) -o kkernel.bin --oformat binary -Ttext 0x100000

 위에서 나와있듯 A.o 파일이 가장 처음에 위치시켜 Asm.Asm 파일을 가장 먼저 링크하며, Asm.Asm 파일의 가장 앞에 kInit() 함수를 위치시킴으로써 kInit() 함수를 첫 함수로 링크할 수 있다.

2.2.2 프레임워크 1.0.3 버전 이후

1. ...... 생략 ......
2. #Object 파일 이름 다 적기
   #아래의 순서대로 링크된다. 새로운 파일이 생기면 뒤에 다 추가하자
   #커널에 꼭 필요한 Object 파일들. ASM.o 파일은 항상 제일 앞에 와야한다. 그 이유는
   #커널의 엔트리포인트가 있는 함수이기 때문이다.
   ESSENTIALOBJ = Asm.o Isr.o
3. ...... 생략 ......
4. # 최종 링크
   kernel: $(ESSENTIALOBJ) $(CFILEOBJ)
    @echo "==> Making Kernel..."
    $(LD) $(ESSENTIALOBJ) $(CFILEOBJ) -o kkernel.bin --oformat binary -Ttext 0x100000 @echo "==> Complete"
5. ...... 생략 ......

3.Custom 폴더 파일 설명

 00Kernel 폴더 아래에 Custom 폴더는 프레임워크를 사용해서 만든 간단한 커널 템플릿 파일(Framework.c, Framework.h)이 들어있다. 이 폴더는 프레임워크를 이용해서 기능을 추가할때 사용자가 추가한 파일들을 저장하는 폴더로 주로 작업하는 폴더가 될 것이다. 커널 템플릿 파일은 프레임워크 엔트리 함수와 외부 인터럽트 발생시 그것을 처리하는 콜백 핸들러(Callback Handler)로 구성되어있다.

 아래는 Framework.h 파일의 내부이다. 함수 이름만 봐도 함수의 역할을 추측할 수 있다.

1. void FrameWorkEntry( void );
2. void kIsrTimerCallBack( void );
   void kIsrKeyboardCallBack( void );
   void kIsrMouseCallBack( void );
   void kIsrCom1CallBack( void );
   void kIsrFloppyCallBack( void );
   void kIsrPrimaryHardDiskCallBack( void );
   void kIsrSecondaryHardDiskCallBack( void );

 그리고 아래는 Framework.c 파일의 내부이다.

1.  /**
       Framework 구현 함수
2.     Written KKAMAGUI, http://kkamagui.tistory.com */
3. #include "../FW/DefineMacro.h"
   #include "KShell.h"
4. /**
       Kernel이 시작되었을 때 다른 정리작업을 마치고 제일 처음 부르는 함수
           수정
   */
   void FrameWorkEntry( void )
   {
       // 인사말을 찍는다.
       printxy( 1, 7, "KKAMAGUI OS FrameWork Start" );
5.     // 간단한 쉘 실행
       Shell();
   }
6. /**
       Timer Interrupt의 Callback
           필요한 경우 수정
   */
   void kIsrTimerCallBack( void )
   {
       Scheduler();
   }
7. /**
       Keyboard Interrupt의 Callback
           필요한 경우 수정
   */
   void kIsrKeyboardCallBack( void )
   {
8. }
9. /**
       Serial Com 1 Interrupt의 Callback
           필요한 경우 수정
   */
   void  kIsrCom1CallBack( void )
   {
10. }
11. /**
        Floppy Interrupt의 Callback
            필요한 경우 수정
    */
    void kIsrFloppyCallBack( void )
    {
12. }
13. /**
        Primary HardDisk Interrupt의 Callback
            필요한 경우 수정
    */
    void kIsrPrimaryHardDiskCallBack( void )
    {
14. }
15. /**
        Secondary HardDisk Interrupt의 Callback
            필요한 경우 수정
    */
    void kIsrSecondaryHardDiskCallBack( void )
    {
16. }
17. /**
        Mouse Interrupt의 Callback
            필요한 경우 수정
    */
    void kIsrMouseCallBack( void )
    {
18. }

 프레임워크 엔트리 함수에는 간단히 환영 메시지를 출력하고 커널 쉘(kShell)을 실행하도록 되어있다. 타이머 콜백에는 스케줄러 함수가 등록 되어있는 것을 보아 스케줄러가 동작하고 있다는 것을 추측할 수 있다.

 커널에 기능을 확장하고 싶으면 위와 같이 필요한 부분에 코드를 삽입하여 원하는 기능을 구현할 수 있다.

4.마치면서...

 간단하게 커널과 프레임워크에 대해서 알아봤다. 다음에는 실제 프레임워크 파일을 수정하여 커널에 기능을 추가해보자.

5.첨부

• part12.ppt

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

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

Part11. 커널 로더(Kernel Loader) 설명

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

들어가기 전에...

0.시작하면서...

 커널 로더(Kernel Loader)는 프레임워크 소스 중에서 가장 CPU Architecture에 의존적이고 복잡한 부분이다. 커널 로더를 이해하려면 Intel Architecture에 대한 이해가 필요한데, 일일이 설명하기에 양이 너무 많다. 따라서 부트 로더와 마찬가지로 기능적인 부분으로 나누어 간략히 설명하겠다.

 커널 로더의 소스는 01Boot 폴더에 01Kloader 에 있다. 소스를 같이 참고하도록 하자.

 커널 로더에서 수행하는 순서는 아래와 같다.

 이제 각각의 순서에 대해서 살펴보자.

1.세그먼트 레지스터의 재설정

 부트 로더에서 커널 로더로 실행이 이행되면 세그먼트 레지스터 설정을 따로 할 필요가 없다. 왜냐하면 부트 로더에서 이미 다 설정해서 넘겨주기 때문이다. 하지만 프레임워크의 부트 로더가 커널 로더를 실행하라는 법이 없으므로 다시 세그먼트를 초기화 해준다.

1.          ;   일단 세그먼트의 초기화
           mov     ax, cs
           mov     ds, ax
           mov     es, ax

2.16bit 모드에서 32bit 모드(Protected Mode)로 전환

 32bit 모드는 보호 모드 또는 Protected Mode라고 불리며 일반 16bit 모드와는 달리 여러가지 권한 설정과 영역 보호를 하드웨어적으로 수행할 수 있는 모드이다. 모든 기재를 사용하면 세세한 권한 설정 및 체크가 가능하지만  프레임워크에서는 이를 간단히 설정하여 사용한다.

 앞서 16bit와 32bit 모드간의 차이에 대해서는 Part5. Intel Architecture에 대한 소개에서 설명했으므로 참고하도록 하고, 지금은 전환에 대한 내용만 소개하겠다. 32bit 전환" href="http://kkamagui.springnote.com/pages/363853">참고. Intel i386 CPU의 16bit->32bit 전환 문서도 같이 참고하면 도움이 될 것이다.

2.1 디스크립터(Descriptor) 설정 

 전환을 위해 가정 먼저 해야될 준비는 32bit 모드에서 사용할 코드/데이터/스택 등등의 영역(세그먼트)에 대한 정보를 기술하는 디스크립터(Descriptor)를 생성하는 일이다.

 세그먼트를 세세하게 나누면 유저 모드용/커널 모드용 영역으로 크게 구분하고 다시 각 영역을 코드/데이터/스택 등등의 영역으로 각각 분할하여 처리할 수 있다. 하지만 프레임워크에서는 0 ~ 0xFFFFFFFF 크기의 세그먼트를 잡아서 코드/데이터에 할당하여 이를 간단하게 정의하였다. 이러한 모드를 일반적으로 Flat 모드라고 하는데, 논리주소가 물리주소에 1:1로 대응되고 메모리 관가 편리하므로 간단한 커널에서는 많이 쓰인다.

 자 그럼 실제로 디스크립터를 설정하는 부분에 대해서 살펴보자.

1. gdt:
       ;null describtor
           dw 0
           dw 0
           db 0
           db 0
           db 0
           db 0
       ;새로 옮겨진 커널의 CodeOffset
       kernelCodeOffset equ $ - gdt
           dw 0xffff
           dw 0x0000
           db 0x0000
           db 0x9a
           db 0xcf
           db 0
       ;새로 옮겨진 커널의 DataOffset
       kernelDataOffset equ $ - gdt
           dw 0xffff
           dw 0x0000
           db 0x0000
           db 0x92
           db 0xcf
           db 0
       ;videoMemory
       videoOffset equ $ - gdt
       videoDesc:
           dw 0xffff
           dw 0x8000
           db 0x0b
           db 0x92
           db 0xcf
           db 0
       ;linear모드 데이터
       linearDataOffset equ $ - gdt
       linearDataDesc:
           dw 0xffff
           dw 0
           db 0
           db 0x92
           db 0xcf
           db 0
       ;code describtor
       codeOffset equ $ - gdt
       codeDesc:
           dw 0xffff
           dw 0
           db 0
           db 0x9a
           db 0xcf
           db 0
       ;data 영역의 descriptor
       dataOffset equ $ - gdt
       dataDesc:
           dw 0xffff
           dw 0
           db 0
           db 0x92
           db 0xcf
           db 0
   gdt_end:

 주석이 친절히 달려있으니 해당 디스크립터가 어떤 디스크립터인지 쉽게 파악할 수 있을 것이다 . 위에서 주의해서 볼 것은 디스크립터의 첫번째가 NULL 디스크립터로 전부 0으로 채워 할당한 부분이다. 이 부분은 CPU에 의해 예약된 영역이므로 다른 값으로 초기화 하거나 하면 곤란하다(영영 커널이 부팅되는 모습을 볼 수 없을지도 모른다).

 조금 전에 프레임워크에서 코드와 데이터 2개만 할당해 준다고 했는데, 왜 디스크립터가 6개나 되는 걸까? 주로 사용하는 영역은 코드와 데이터 디스크립터이고 나머지는 부수적으로 사용하는 디스크립터라서 그렇다. 필요에 의해 만든 것이므로 크게 신경쓰지 않아도 된다. 실제 동작을 위해서는 32bit 코드/데이터 디스크립터, 그리고 NULL 디스크립터만 있어도 된다.

 각 필드에 대한 의미나 플래그 값들은 Intel Architecture의 Volume 3을 참조하도록 하고 일단 디스크립터 형태에 대해서 잠깐 보고 넘어가자.

<Segment Descriptor>

 디스크립터는 위와같이 8byte로 이루어져있으며 각 속성(코드/데이터)에 맞게 플래그를 설정해주면 된다. 실제로 이 작업은 굉장히 까다로운 작업이며 약간 실수(??)하면 재부팅을 연발한다. 벗어나는 방법은 잘 설정된 코드를 참조하거나 끊임없는 수정을 통해 적절한 값을 찾는 방법말고는 없다.... ㅡ_ㅜ... 위에 디스크립터 구조와 부트 로더 코드를 보면서 비교하면 설정된 값의 의미를 알 수 있으므로 넘어간다.

 디스크립터의 설정이 끝나고나면 기대하던 16bit -> 32bit 전환의 단계가 남아있다.  전환하는 방법은 아주 간단하며 CR0 레지스터에 플래그 하나를 바꿔주는 것으로 전환은 끝이난다. 하지만 그 전에 전환 준비가 좀 까다롭다.

2.2 Global Descriptor Table Register(GDTR) 설정

 시스템 전체적인 디스크립터의 테이블을 Global Descriptor Table(GDT)이라고 하는데, 단 하나만 존재하는 영역으로써 코드/데이터/스택 등의 세그먼트에 대한 디스크립터나 태스크에 대한 디스크립터 등등을 저장하는 역할을 한다.

 위에서 디스크립터를 연속적으로 할당하여 값을 설정해 주었는데, 이 영역이 바로 GDT가 되는 것이다. GDT가 따로 존재하는 것이 아니고 연속된 메모리 위치에 디스크립터를 생성하면 그것이 GDT가 된다. 이 GDT 영역을 16bit->32bit 전환 전에 GDT Register에 등록해 줘야 하는데 GDTR은 아래와 같은 구조를 가지는 구조체의 주소를 가진다.

<GDTR 구조체>

GDT의 크기와 시작주소를 가지는 간단한 구조체이다. 이 구조체에 값을 설정하고 32bit 모드로 전환했을 때 사용할 디스크립터에 값을 설정하는 코드는 아래와 같다.

1.         ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
           ;   GDT를 설정한다.
           xor     ebx, ebx
           xor     eax, eax
           mov     bx, ds
           shl     ebx, 4
           mov     eax, ebx
           mov     word [codeDesc + 2], ax
           mov     word [dataDesc + 2], ax
           shr     eax, 16
           mov     byte [codeDesc + 4], al
           mov     byte [dataDesc + 4], al
           mov     byte [codeDesc + 7], ah
           mov     byte [dataDesc + 7], ah
          
           ; gdtr 레지스터 설정
           ;lea    eax, [gdt+ebx]
           ;lea 명령은 아래의 2줄과 같다.
           mov     eax, ebx
           add     eax, gdt
2.         mov     [gdtr + 2], eax
3. ...... 생략 ......
4. gdtr:
           dw gdt_end - gdt - 1
           dd gdt

 설정된 gdtr의 값을 GDTR 레지스터에 설정하는 코드는 뒤에 16bit->32bit 모드 전환에서 나온다.

2.3 16bit->32bit 모드 전환

 마지막 작업은 인터럽터를 불가로 설정하고 실제 32bit 모드로 변환해 주는 것이다. 인터럽터를 불가로 설정하는 이유는 32bit 모드에서 인터럽트 처리를 위한 기반 작업(Interrupt Descriptor Table 설정과 같은 것들..)이 되어있지 않기 때문이다. 실제로 이 작업은 커널이 완전히 로딩된 후 설정하는 작업이기 때문에 커널 실행 전까지는 인터럽트 불가 상태로 설정해 놓는다.

 실제 모드를 변경하는 코드는 아래와 같다.

1.         ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
           ; 인터럽터 불가 설정
           cli
          
           lgdt    [gdtr]   <= 실제로 이부분이 GDT를 로딩하는 부분이다.
           ;   보호모드를 설정하고
           ;   인덱스 2 비트가 Floating Point 비트다.
           ;   Floating Point계산 유닛을 내부 유닛을 사용하도록
           ;   설정한다 그렇지 않으면 7번 인터럽터가 발생한다.
           mov     eax, cr0
2.         or      eax, 0x80000000
           xor     eax, 0x80000000
           or      al, 1
           or      al, 0x04
           xor     al, 0x04
           mov     cr0, eax
3.         jmp     codeOffset:code_32
4. ;   여기에 진입하면 이미 보호모드다. 이제 리얼모드와는
   ;   상관없고 커널이 시작되면 돌아갈수도 없다.
   [bits 32]
       code_32:
           ;   레지스터를 초기화 하고
           mov     ax, dataOffset
           mov     ds, ax
           mov     es, ax
           mov     ss, ax
           mov     gs, ax
           xor     esp, esp
           mov     esp, 0x8ffff
           mov     ebp, 0x8ffff

 위에서 점프 명령을 이용하는 이유는 코드 영역을 설정하는 CS 레지스터 같은 경우는 일반적인 mov 명령으로 값을 바꿀 수 없기 때문이다. 따라서 far jump 명령을 이용해서 CS의 값을 커널 코드 영역을 가리키는 코드 세그먼트의 값으로 바꾸어 준다.

 32bit 영역으로 이동한 후에는 DS, ES, SS, GS, FS와 같은 데이터 관련 레지스터를 모두 커널 데이터 디스크립터로 변경하여 이후 데이터 접근 시에 문제가 발생하지 않도록 한다. 마지막 작업으로 스택을 설정함으로써 32bit 모드로 진입을 끝낸다.

3.커널 코드 이동

3.1 A20 Line Enable

 이제 남은 작업은 커널 코드를 1M 주소로 이동해서 재배치 하는 작업이다. 굳이 옮기지 않아도 되지만 옮긴 이유는 1M 이하 영역은 BIOS의 코드도 포함되어있고 DMA 관련 데이터 송/수신 시 사용할 영역을 확보한다는 의미도 있다(구버전의 DMA의 경우에는 1M 이상의 메모리에 접근이 불가능 했다).

 커널 코드 이동은 단순이 커널 존재하는 메모리를 1M 영역으로 복사하는 것을 의미하는 것은 아니다. IBM 호환 PC의 경우 16bit 모드일때 Address Line을 다 사용하지 않기 때문에 Address Line을 확장하도록 설정해 줘야 한다. 즉 확장하지 않으면 1M 이상의 메모리로 접근을 해도 이것이 다시 1M 안쪽의 메모리로 Wrapping되어서 접근된다.

 그럼 1M 이상의 메모리로 접근하기위해서는 어떻게 해야 할까? A20 Line을 활성화 하면 된다!!. A20이 무엇인지에 대해서는 http://www.resultspk.net/create_os/os-faq-memory.html#what_is_a20를 참고하도록 하고 1M 이상의 메모리로 접근하기위해 Off 상태로 되어있는 Address Line을 활성화 한다는 정도만 알아놓자.

 아래는 A20을 활성화하는 코드이다.

1. ;   A20 영역을 Enable 시킨다.
   ;   wrapping된 line을 Enable한다.
   enable_A20:
       call    a20wait
       mov     al,0xAD
       out     0x64,al
2.     call    a20wait
       mov     al,0xD0
       out     0x64,al
3.     call    a20wait2
       in      al,0x60
       push    eax
4.     call    a20wait
       mov     al,0xD1
       out     0x64,al
5.     call    a20wait
       pop     eax
       or      al,2
       out     0x60,al
6.     call    a20wait
       mov     al,0xAE
       out     0x64,al
7.     call    a20wait
       ret
8. a20wait:
   .l0:    mov     ecx,65536
   .l1:    in      al,0x64
       test    al,2
       jz      .l2
       loop    .l1
       jmp     .l0
   .l2:    ret
9. 
   a20wait2:
   .l0:    mov     ecx,65536
   .l1:    in      al,0x64
       test    al,1
       jnz     .l2
       loop    .l1
       jmp     .l0
   .l2:    ret

3.2 커널 이동

 이제 커널을 1M 영역으로 복사하면 끝이다. 코드가 좀 복잡하긴 한데, 주된 흐름은 이동 시작 위치와 목적 위치를 설정해주고 부트 로더에 들어있던 커널 이미지 크기만큼 1M 이상의 영역으로 복사하는 것이다.

1.         ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
           ;   뒷 메모리에 있는 커널을 읽어 들여서 점프 한다.
           ;   일단 movsd 명령이 si 와 di의 값을 하나씩 증가시키게 한다.
           ;   df = 0 이면 증가 1 이면 감소
           cld
           ;   그리고 커널을 1M 메모리 영역으로 올린다.
           ;   커널이 위치하는 세그먼트 정보는 0x07c0:0x01fa에 있다.
           mov     ax, linearDataOffset
           mov     es, ax
           xor     eax, eax
           xor     ebx, ebx
           mov     ax, word [es:0x7dfa]
           sub     ax, 1
           mov     bx, 0x0200
           mul     ebx
           ;   커널 시작 섹터에서 0x0200을 곱하고 0xfe00을 더하면
           ;   커널이 시작되는 주소가 나온다.
           ;   거기로 옮기면 된다
           add     eax, 0xfe00
           mov     esi, eax
           ;   그리고 0x07c0:0x01fc에 커널의 섹터수가 들어있으므로
           ;   그것을 읽고 movsd의 명령으로 4byte씩 전송하므로 512/4 = 128
           ;   을 곱하면 movsd의 명령을 실행할 횟수가 나온다.
           xor     eax, eax
           xor     ebx, ebx
           mov     ax, word[es:0x7dfc]
           mov     bx, 0x80
           mul     ebx
           mov     ecx, eax
           ;   그리고 마지막으로 옮길 부분의 Offset을 구하면 1Mbyte의 위치이므로
           ;   0x100000 의 위치로 옮긴다.
           mov     eax, 0x100000
           mov     edi, eax
           ;   마지막으로 세그먼트를 설정한다. 둘다 linear로 설정한다.
           mov     ax, linearDataOffset
           mov     ds, ax
           rep     movsd

 위의 코드가 끝이 나면 1M 위치에 커널이 복사가 완료된 것이다. 이제 1M로 Jump하면 커널이 실행된다.

4.커널 실행

 커널의 실행은 허무할 정도로 간단하다. 아래의 한줄로 끝이난다.

1.         jmp     kernelCodeOffset:0x100000

 그 이후는 커널이 실행되고 프레임워크 초기화를 수행하는 등등의 작업을 한다. 커널 코드가 이동된 곳은 1M(0x100000)의 위치다. 다시말해 커널 코드를 컴파일해서 링크했을 때 1M의 위치에서 실행가능하도록 해야한다.

 어떻게 1M의 위치에서 실행가능한 코드를 만들어낼까? 답은 링크 옵션(Link Option)에 있다. 프레임워크 소스 파일에서 커널을 생성하는 makefile을 열어보면 알겠지만, ld의 옵션중에 코드를 생성할때 특정 위치에서 실행가능하도록 링크하는 옵션이 있다.

 위의 옵션을 사용하면 접근하는 변수, 상수들의 주소가 1M 위치를 Base로 해서 생성되기 때문에 1M의 위치에서 실행가능한 것이다. 만약 커널을 2M 영역으로 이동할 필요가 있다면 위의 부분을 0x200000로 수정하고 부트 로더에서 커널을 이동하는 위치를 1M -> 2M로 수정해 주면 2M의 위치에서 커널을 실행할 수 있다.

5.물리 메모리 크기 확인

 실제 머신에 사용가능한 물리 메모리의 크기를 알면 커널 동작 시에 좀 더 능동적으로 작업을 수행할 수 있다. 물리 메모리의 크기를 아는 방법은 BIOS 함수을 이용해서 구하는 방법이 있으며, 직접 수작업으로 확인하는 방법이 있다.

 수작업으로 확인하는 방법은 메모리를 1M씩 증가시키면서 해당 주소에 1byte 값을 쓰고 다시 읽어서 쓴 값이 정상적인가를 확인하는 방법이다. 만약 물리 메모리가 사용가능하다면 쓰고 읽었을 때 정상적인 값이 나오지만, 사용이 불가능하다면 틀린 값이 나올 것이다. 실제로 Bellona2 OS(http://www.bellona2.com)가 이러한 방식을 택하고 있으며, 프레임워크에서도 직접 체크하는 방식을 따르고 있다.

 아래는 직접 체크하는 코드이다.

1. ;   1M 이후 영역부터 루프를 돌면서 그 결과값을 저장한다.
   ;   결과값을 저장하는것은 0x7c00 즉 부트 섹터 시작 점에 적는다.
   ;   값은 Double Word로 한다.
   checkMemoryAmount :
           push        ebp
           push        eax
           push        ecx
           push        ebx
           push        gs
           push        es
2.         mov     ecx, 0x00
           mov     ebx, 0x000000                  
           mov     ax, linearDataOffset
           mov     gs, ax
           mov     ax, videoOffset
           mov     es, ax
3.     continue :
           add     ebx, 0x100000
           inc     ecx
           ;   메모리 체크 진행상황을 본다.
           ;mov        byte[es:ecx], '.'
           ;   일단 메모리에 무각기로 쓰고
           mov     byte[gs:ebx], 0x03
           ;   다시 메모리에 있는 내용을 비교한다.
           mov     al, byte[gs:ebx]
           cmp     al, 0x03
           je      continue
          
           mov     ebx, 0x7c00
           mov     dword[gs:ebx], ecx
4.         pop     es
           pop     gs
           pop     ebx
           pop     ecx
           pop     eax
           pop     ebp
           ret

6.마치면서...

 이로서 부트 로더와 커널 로더의 설명이 끝이났다. 원래는 CPU 의존적인 부분들이라 설명을 하지 않고 넘어가려 했으나, 그대로 넘어가는 것이 마음에 걸려서 약간 설명을 한다는 것이.... ㅡ_ㅡ;;;;

 역시나 딱딱한 이야기들로 가득찼는데... ㅡ_ㅜ... 다음부터는 프레임워크를 이용하여 커널을 작성하면서 해당 파트에 대한 설명을 하겠다(쓰면서도 지루해 죽을 껏 같았다는.. ㅡ_ㅡ).

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

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

Part10. 부트 로더(Boot Loader) 설명

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

들어가기 전에...

0.시작하면서...

 부트 로더(Boot Loader)는 BIOS로부터 제어를 넘겨받아서 처음으로 실행되는 프로그램이다. 그렇다보니 C Runtime 환경 같은건 전혀 기대할 수 없고 어셈블리어로 구현하는 것이 보통이다.

 부트 로더 코더를 세세하게 설명하면 끝이 없으므로, 간단히 기능적인 관점으로 나누어 설명하겠다.

 부트 로더의 소스는 프레임워크 안에 01Boot 폴더에 00Bootstrap 안에 있다. 소스를 같이 참고하면서 보자.

 부팅이 되고나면 부트 로더에서 해야하는 작업은 크게 세가지다.

 그럼 이제 각각에 대해서 알아보도록하자.

1.코드/데이터/스택 영역 설정 및 초기화

 부트 로더가 제어를 넘겨받았을 때 레지스터의 상태는 BIOS에서 코드 수행시에 사용되던 값이다. 이대로 사용해도 괜찮지만 BIOS가 여러종류가 있고 각 BIOS 마다 코드가 다르므로 레지스터의 값을 예측할 수 없다. 애매한 상황을 피하기위해 각 레지스터의 값을 새로 설정해 준다.

1. jmp 0x07c0:start <== 코드 세그먼트 레지스터를 0x07c0로 설정
   start :
           mov     ax, cs
           mov     ds, ax
           mov     es, ax
           ;   스텍의 설정
           ;   함수 호출을 위해 필수
           mov     ax, 0x0000
           mov     ss, ax
           mov     ax, 0xffff
           mov     sp, ax
           mov     bp, ax

 위와 같이 세그먼트 레지스터를 코드 영역과 같이 설정해 주고 스택을 세그먼트의 끝에서부터 자라도록 설정해준다.

 위에서 jmp 0x07c0:start 코드를 볼 수 있는데, 이 코드는 CS 세그먼트 레지스터에 0x07c0을 설정하고 IP 레지스터에 start의 주소를 설정하는 코드이다. CS 세그먼트 레지스터에 0x07c0을 설정하면 어떤 일이 발생하는 것일까? 16bit 모드에서 세그먼트 레지스터의 역할은 32bit 모드의 역할과 다르다.

 16bit 모드의 세그먼트 레지스터의 역할은 Base 주소 역할만 하는데, 주소 계산 방식은 아래와 같다.

 즉 start 코드가 위치하는 실제 주소는 0x7c00  + start의 주소가 되는 것이다.

 그렇다면 0x7c00 주소는 무엇일까? 0x7c00의 주소는 BIOS가 디스크로부터 한 섹터를 읽어들여 메모리에 복사하는 위치이다. 다시말해 부트 코드가 0x7c00에 위치하며 BIOS가 0x7c00의 주소로 jump해서 부트 코드를 실행한다. 부트 코드가 정상적으로 실행되기 위해서는 0x7c00에서 실행되도록 컴파일 되어야 함은 두말할 필요도 없다.

2.이미지 로딩

2.1 플로피 디스크(Floppy Disk) 분석

 부트 로더의 코드 중에 가장 복잡한 부분이다. 플로피에 저장된 이미지를 모두 로딩하는 역할을 하는 함수인데, 코드를 이해하기 위해서는 플로피 디스크에 대한 지식이 필요하다.

 그럼 간단히 플로피 디스크에 대해 알아보자. 플로피 디스크는 아래와 같은 세가지로 구성된다.

  이것을 그림으로 보면 아래와 같다.

<섹터/트랙/헤드의 구성> 

 고용량의 플로피 디스크(1.44Mbyte)는 양면으로 되어있기 때문에 헤드의 값이 2이다. 일단 섹터/트랙/헤드의 구성에 대해 알아보았으니, 섹터를 읽어 데이터를 로드한다고 가정하고 어떤 순서로 로딩하는지 알아보자.

 플로피 디스크에 데이터를 읽고 쓰는 순서는 어떻게 될까? 0부터 끝까지 계속 데이터를 써내려간다고 가정하면 아래와 같은 순서로 읽고 쓰게 된다.포인트는 섹터 -> 헤드 -> 트랙 순으로 증가하는 값이다.

2.2 플로피 디스크(Floppy Disk) 제어 코드

 위의 일련의 작업을 코드로 옮긴 것이 아래의 코드다.

1. ;   플로피로 부터 커널 로더를 읽어 들인다.
   ReadSector:
       push    bp
       push    es
       pushf
      
       mov     ax, 0xb800
       mov     gs, ax
      
       reset:  ;   reset floppy
           mov     ax, 0
           mov     dl, 0               ;   Drive=0(A Drive)
           int     0x13                ;   명령전송
           jc      reset               ;   문제가 생기면 다시 시도 한다.  
           mov     ax, 0x1000;0x07e0   ;   이미지를 읽어들일 segment
           mov     es, ax
           mov     bx, 0
2.     ;   아래의 부분을 반복한다.
       read:       ;   read 하는 부분
           mov     ah, 2                   ;   bios 명령 포멧 es:bx에 저장한다.
           mov     al, 1                   ;   Load 1 Sector
           mov     ch, byte [TRACKCOUNT]   ;   Cylinder    = 0
           mov     cl, byte [SECTORCOUNT]  ;   Sector 2 부터
           mov     dh, byte [HEADCOUNT]    ;   Head 0
           mov     dl, 0                   ;   Drive 0 (A Drive)
           int     0x13                    ;   명령 전송
           jc      error
3.         ;   그리고 섹터값을 증가시킨다.
           ;   플레그 레지스터를 저장해서 증가 시키는 루틴으로 인해
           ;   플레그의 값이 바뀌는일이 없도록 한다.
           inc     byte [SECTORCOUNT]      ;   섹터를 1 증가한다.
           cmp     byte [SECTORCOUNT], 19  ;   섹터는 0 부터 18 까지 있으므로
           jb      endRead                 ;   작으면 다음 섹터를 읽고
           mov     byte [SECTORCOUNT], 1   ;   같으면 섹터의 크기를 1로 만들고
           inc     byte [HEADCOUNT]        ;   헤드를 하나 증가 시킨다.
           cmp     byte [HEADCOUNT], 2     ;   헤드는 0 에서 1까지 있으므로
           jb      endRead                 ;   작으면 다음 섹터를 읽고
           mov     byte [HEADCOUNT], 0     ;   같으면 헤드를 0 설정
           inc     byte [TRACKCOUNT]       ;   트렉을 하나 증가시킨다.
           cmp     byte [TRACKCOUNT], 80
           jb      endRead
           ;   트렉이 넘어 섰나 체크는 안해도 된다.
           ;   커널이 1.44 메가를 넘길려고...
      
       endRead:
           ;   한섹터가 0x200 이므로 세그먼트 레지스터를 증가 시킨다.
   mov     bx, es
           add     bx, 0x20
           mov     es, bx
           ;   디버깅
           mov     ax, es
           mov     byte [gs:0x00], ah
           mov     byte [gs:0x02], al
           ;   디버깅 끝
      
           ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
           ;   진행상황 표시
           mov     bx, word [LOOPCOUNT]
           mov     byte [gs:402], bl
           mov     byte [gs:403], 0x02
           ;   진행상황 점찍기(일단 주석처리)
           ;mov    bx, word [LOOPCOUNT]
           ;mov    ax, 2
           ;mul    bx
           ;mov    bx, ax
           ;add    bx, 482
           ;mov    byte [gs:bx], '.'
           ;inc    bx
           ;mov    byte [gs:bx], 0x02
           ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
           ;   루프 횟수 계산하기
           mov     bx, 0
           inc     word [LOOPCOUNT]   
           mov     cx, word [LOOPCOUNT]
           cmp     cx, word [ds:0x01f8]
           jb      read
4.     ; 다 읽었으면 Fdd를 Reset 하고 초기화 시켜둔다.
       reset_end:  ;   reset floppy
           mov     ax, 0
           mov     dl, 0           ;   Drive=0(A Drive)
           int     0x13            ;   명령전송
           jc      reset_end       ;   문제가 생기면 다시 시도 한다.  
      
       popf
       pop     es
       pop     bp
       retn

3.커널 로더 실행

  커널 로더를 실행하는 부분은 아주 간단하다. 커널 이미지가 0x10000 주소에 로딩되기 때문에 jump만 하면 된다. 아래는 그 코드이다.

1.         jmp     0x1000:0 ;0x07e0:0

4.마치면서...

 이상으로 부트 로더에 대해서 간단히 알아보았다. 어셈블리어 코드 하나하나를 설명하면 좋겠지만 세부적인 내용이 궁금한 사람은 Intel Architecture Manual을 참고하자. 다음에는 커널 로더에 대해 알아보자.

5.첨부

• Part10.ppt

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

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

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