Ⅰ. 태스크 분산 처리를 위한 자료구조 설계와 구현

• 태스크 부하 분산 (Task Load Balancing)
  • 태스크를 여러 코어로 나누어 처리하는 기법이다.

1. 스케줄러, 태스크 풀, 태스크 자료구조 수정

• 스케줄러 자료구조를 코어의 최대 개수만큼 할당한 코드

  // 스케줄러의 상태를 관리하는 자료구조
  typedef struct kSchedulerStruct
  {
      // 자료구조 동기화를 위한 스핀락
      SPINLOCK stSpinLock; 
      
      // 현재 수행 중인 태스크
      TCB* pstRunningTask;
      
      // 현재 수행 중인 태스크가 사용할 수 있는 프로세서 시간
      int iProcessorTime;
      
      // 실행할 태스크가 준비중인 리스트, 태스크의 우선 순위에 따라 구분
      LIST vstReadyList[ TASK_MAXREADYLISTCOUNT ];
  
      // 종료할 태스크가 대기중인 리스트
      LIST stWaitList;
      
      // 각 우선 순위별로 태스크를 실행한 횟수를 저장하는 자료구조
      int viExecuteCount[ TASK_MAXREADYLISTCOUNT ];
      
      // 프로세서 부하를 계산하기 위한 자료구조
      QWORD qwProcessorLoad;
      
      // 유휴 태스크(Idle Task)에서 사용한 프로세서 시간
      QWORD qwSpendProcessorTimeInIdleTask;
  
      // 마지막으로 FPU를 사용한 태스크의 ID
      QWORD qwLastFPUUsedTaskID;
  
      // 부하 분산 기능 사용 여부
      BOOL bUseLoadBalancing;
  
      // TCB 전체를 16바이트 배수로 맞추기 위한 패딩
      char vcPadding[ 10 ];
  } SCHEDULER;
  
  // 스케줄러를 코어의 수만큼 할당
  static SCHEDULER gs_vstScheduler[ MAXPROCESSORCOUNT ];
  

• 스핀락이 추가된 태스크 풀 자료구조의 코드

  typedef struct kTCBPoolManagerStruct
  {
      // 자료구조 동기화를 위한 스핀락
      SPINLOCK stSpinLock;
      
      // 태스크 풀에 대한 정보
      TCB* pstStartAddress;
      int iMaxCount;
      int iUseCount;
      
      // TCB가 할당된 횟수
      int iAllocatedCount;
  } TCBPOOLMANAGER;
  

• 수정된 태스크(TCB) 자료구조의 코드

  • 프로세서 친화도 필드는 태스크를 어느 코어에서 실행할지 결정하는 필드이다.

    (해당 필드에 APIC ID가 설정되면, 해당 코어에서만 실행된다)

  typedef struct kTaskControlBlockStruct
  {
      // 다음 데이터의 위치와 id
      LISTLINK stLink;
  
      // 플래그
      QWORD qwFlags;
  
      // 프로세스 메모리 영역의 시작과 크기
      void* pvMemoryAddress;
      QWORD qwMemorySize;
  
      //==========================================================================
      // 이하 스레드 정보
      //==========================================================================
      // 자식 스레드의 위치와 ID
      LISTLINK stThreadLink;
      
      // 부모 프로세스의 ID
      QWORD qwParentProcessID;
  
      // FPU 콘텍스트는 16의 배수로 정렬되어야 하므로,
      // 앞으로 추가할 데이터는 현재 라인 아래에 추가해야 함
      QWORD vqwFPUContext[ 512 / 8];
  
      // 자식 스레드의 리스트
      LIST stChildThreadList;
  
      // 콘텍스트
      CONTEXT stContext;
      
      // 스택의 어드레스와 크기
      void* pvStackAddress;
      QWORD qwStackSize;
  
      // FPU 사용 여부
      BOOL bFPUUsed;
  
      // 프로세서 친화도
      BYTE bAffinity;
  
      // 현재 태스크를 수행하는 코어의 로컬 APIC ID
      BYTE bAPICID;
  
      // TCB 전체를 16바이트 배수로 맞추기 위한 패딩
      char vcPadding[ 9 ];
  } TCB;
  

2. 태스크 풀 초기화, 할당, 해제 함수 수정

• 수정된 태스크 풀 초기화 함수의 코드

  //  태스크 풀 초기화
  static void kInitializeTCBPool( void )
  {
      int i;
  
      kMemSet( &( gs_stTCBPoolManager ), 0, sizeof( gs_stTCBPoolManager ) );
      
      // 태스크 풀의 어드레스를 지정하고 초기화
      gs_stTCBPoolManager.pstStartAddress = ( TCB* ) TASK_TCBPOOLADDRESS;
      kMemSet( TASK_TCBPOOLADDRESS, 0, sizeof( TCB ) * TASK_MAXCOUNT );
  
      // TCB에 ID 할당
      for( i = 0 ; i < TASK_MAXCOUNT ; i++ )
      {
          gs_stTCBPoolManager.pstStartAddress[ i ].stLink.qwID = i;
      }
      
      // TCB의 최대 개수와 할당된 횟수를 초기화
      gs_stTCBPoolManager.iMaxCount = TASK_MAXCOUNT;
      gs_stTCBPoolManager.iAllocatedCount = 1;
  
  		// 스핀락 초기화
  		kInitilaizeSpinLock( &gs_stTCBPoolManager.stSpinLock );
  }
  

• 수정된 태스크 할당 함수와 해제 함수의 코드

  // TCB를 할당 받음
  static TCB* kAllocateTCB( void )
  {
      TCB* pstEmptyTCB;
      int i;
      
      // 동기화 처리
      kLockForSpinLock( &gs_stTCBPoolManager.stSpinLock );
  
      if( gs_stTCBPoolManager.iUseCount == gs_stTCBPoolManager.iMaxCount )
      {
          // 동기화 처리
          kUnlockForSpinLock( &gs_stTCBPoolManager.stSpinLock );
          return NULL;
  
      }
  
      for( i = 0 ; i < gs_stTCBPoolManager.iMaxCount ; i++ )
      {
          // ID의 상위 32비트가 0이면 할당되지 않은 TCB
          if( ( gs_stTCBPoolManager.pstStartAddress[ i ].stLink.qwID >> 32 ) == 0 )
          {
              pstEmptyTCB = &( gs_stTCBPoolManager.pstStartAddress[ i ] );
              break;
          }
      }
  
      // 상위 32비트를 0이 아닌 값으로 설정해서 할당된 TCB로 설정
      pstEmptyTCB->stLink.qwID = ( ( QWORD ) gs_stTCBPoolManager.iAllocatedCount << 32 ) | i;
      gs_stTCBPoolManager.iUseCount++;
      gs_stTCBPoolManager.iAllocatedCount++;
      if( gs_stTCBPoolManager.iAllocatedCount == 0 )
      {
          gs_stTCBPoolManager.iAllocatedCount = 1;
      }
  
      // 동기화 처리
      kUnlockForSpinLock( &gs_stTCBPoolManager.stSpinLock );
      
      return pstEmptyTCB;
  }
  
  // TCB를 해제함
  static void kFreeTCB( QWORD qwID )
  {
      int i;
      
      // 태스크 ID의 하위 32비트가 인덱스 역할을 함
      i = GETTCBOFFSET( qwID );
      
      // TCB를 초기화하고 ID 설정
      kMemSet( &( gs_stTCBPoolManager.pstStartAddress[ i ].stContext ), 0, sizeof( CONTEXT ) );
      
      // 동기화 처리
      kLockForSpinLock( &gs_stTCBPoolManager.stSpinLock );
  
      gs_stTCBPoolManager.pstStartAddress[ i ].stLink.qwID = i;
      
      gs_stTCBPoolManager.iUseCount--;
  
      // 동기화 처리
      kUnlockForSpinLock( &gs_stTCBPoolManager.stSpinLock );
  }
  

3. 스케줄러 초기화 함수 수정

• 태스크 풀 초기화와 스케줄러 자료구조 초기화

  void kInitializeScheduler( void ){
      int i;
      int j;
      BYTE bCurrentAPICID;
      TCB* pstTask;
  
      // 현재 코어의 로컬 APIC ID 확인
      bCurrentAPICID = kGetAPICID();
  
      // Bootstrap Processor만 태스크 풀과 스케줄러 자료구조를 모두 초기화
      if( bCurrentAPICID == 0 ){
          // 태스크 풀 초기화
          kInitializeTCBPool();
  
          // 준비 리스트와 우선순위별 실행 횟수를 초기화하고 대기 리스트와 스핀락을 초기화
          for( j = 0 ; j < MAXPROCESSORCOUNT ; j++ ){
              // 준비 리스트 초기화
              for( i = 0; i < TASK_MAXREADYLISTCOUNT ; i++ ){
                  kInitializeList( &( gs_vstScheduler[ j ].vstReadyList[ i ] ) );
                  gs_vstScheduler[ j ].viExecuteCount[ i ] = 0;
              }
              // 대기 리스트 초기화
              kInitializeList( &( gs_vstScheduler[ j ].stWaitList ) );
  
              // 스핀락 초기화
              kInitializeSpinLock( &( gs_vstScheduler[ j ].stSpinLock ) );
          }
      }
  
      ``` 생략 ```
  }
  

• 부팅 태스크 등록과 기타 필드 초기화

  void kInitializeScheduler( void ){
      int i;
      int j;
      BYTE bCurrentAPICID;
      TCB* pstTask;
  
      // 현재 코어의 로컬 APIC ID 확인
      bCurrentAPICID = kGetAPICID();
  
      // Bootstrap Processor만 태스크 풀과 스케줄러 자료구조를 모두 초기화
      if( bCurrentAPICID == 0 ){
          // 태스크 풀 초기화
          kInitializeTCBPool();
  
          ``` 준비 리스트와 우선순위별 실행 횟수, 대기 리스트, 스핀락을 초기화하는 코드 ```
      }
  
      // TCB를 할당받아 부팅을 수행한 태스크를 커널 최초의 프로세스로 설정
      pstTask = kAllocateTCB();
      gs_vstScheduler[ bCurrentAPICID ].pstRunningTask = pstTask;
  
      // BSP 콘솔 셸이나 AP의 유휴 태스크는 모두 현재 코어에서만 실행하도록
      // 로컬 APIC ID와 프로세서 친화도를 현재 코어의 로컬 APIC ID로 설정
      pstTask->bAPICID = bCurrentAPICID;
      pstTask->bAffinity = bCurrentAPICID;
  
      // Bootstrap Processor는 콘솔 셸을 실행
      if( bCurrentAPICID == 0 ){
          pstTask->qwFlags = TASK_FLAGS_HIGHEST | TASK_FLAGS_PROCESS | TASK_FLAGS_SYSTEM;
      }
      // Application Processor는 특별히 긴급한 태스크가 없으므로 유휴 태스크를 실행
      else{
          pstTask->qwFlags = TASK_FLAGS_LOWEST | TASK_FLAGS_PROCESS | TASK_FLAGS_SYSTEM | TASK_FLAGS_IDLE;
      }
  
      pstTask->qwParentProcessID = pstTask->stLink.qwID;
      pstTask->pvMemoryAddress = ( void* ) 0x100000;
      pstTask->qwMemorySize = 0x500000;
      pstTask->pvStackAddress = ( void* ) 0x600000;
      pstTask->qwStackSize = 0x100000;
  
      // 프로세서 사용률을 계산하는데, 사용하는 자료구조 초기화
      gs_vstScheduler[ bCurrentAPICID ].qwSpendProcessorTimeInIdleTask = 0;
      gs_vstScheduler[ bCurrentAPICID ].qwProcessorLoad = 0;
  
      // FPU를 사용한 태스크 ID를 유효하지 않은 값으로 초기화
      gs_vstScheduler[ bCurrentAPICID ].qwLastFPUUsedTaskID = TASK_INVALIDID;
  }
  

4. 태스크 생성 함수 수정

• 수정된 태스크 생성 함수의 코드

  TCB* kCreateTask( QWORD qwFlags, void* pvMemoryAddress, QWORD qwMemorySize, 
                    QWORD qwEntryPointAddress, BYTE bAffinity )
  {
      TCB* pstTask, * pstProcess;
      void* pvStackAddress;
      BYTE bCurrentAPICID;
  
      // 현재 코어의 로컬 APIC ID를 확인
      bCurrentAPICID = kGetAPICID();
  
      // 태스크 자료구조 할당
      pstTask = kAllocateTCB();
      if( pstTask == NULL ){
          return NULL;
      }
      
      // 임계 영역 시작
      kLockForSpinLock( &( gs_vstScheduler[ bCurrentAPICID ].stSpinLock ) );
  
      // 현재 프로세스 또는 스레드가 속한 프로세스를 검색
      pstProcess = kGetProcessByThread( kGetRunningTask( bCurrentAPICID ) );
      // 만약 프로세스가 없다면 아무런 작업도 하지 않음
      if( pstProcess == NULL ){
          kFreeTCB( pstTask->stLink.qwID );
          // 임계 영역 끝
          kUnlockForSpinLock( &( gs_vstScheduler[ bCurrentAPICID ].stSpinLock ) );
          return NULL;
      }
  
      ``` 프로세스인지 스레드인지 판단하여 정보를 설정하는 코드 ```
  
      // 스레드의 ID를 태스크 ID와 동일하게 설정
      pstTask->stThreadLink.qwID = pstTask->stLink.qwID;
      // 임계 영역 끝
      kUnlockForSpinLock( &( gs_vstScheduler[ bCurrentAPICID ].stSpinLock ) );
  
      // 태스크 ID로 스택 어드레스 계산. 하위 32비트가 스택 풀의 오프셋 역할 수행
      pvStackAddress = ( void* ) ( TASK_STACKPOOLADDRESS + ( TASK_STACKSIZE * GETTCBOFFSET( pstTask->stLink.qwID ) ) );
  
      // TCB를 설정한 후, 준비 리스트에 삽입하여 스케줄링될 수 있도록 함
      kSetUpTask( pstTask, qwFlags, qwEntryPointAddress, pvStackAddress, TASK_STACKSIZE );
  
      // 자식 스레드 리스트를 초기화
      kInitializeList( &( pstTask->stChildThreadList ) );
  
      // FPU 사용 여부를 사용하지 않은 것으로 초기화
      pstTask->bFPUUsed = FALSE;
  
      // 현재 코어의 로컬 APIC ID를 태스크에 설정
      pstTask->bAPICID = bCurrentAPICID;
  
      // 프로세서 친화도를 설정
      pstTask->bAffinity = bAffinity;
  
      // 부하 분산을 고려하여 스케줄러에 태스크를 추가
      kAddTaskToSchedulerWithLoadBalancing( pstTask );
      return pstTask;
  }
  

5. 부하 분산을 고려한 태스크 생성 함수 추가

• 전달된 태스크와 같은 우선순위의 태스크 수가 가장 작은 스케줄러를 반환하는 함수의 코드

  static BYTE kFindSchedulerOfMinumumTaskCount( const TCB* pstTask ){
      BYTE bPriority;
      BYTE i;
      int iCurrentTaskCount;
      int iMinTaskCount;
      BYTE bMinCoreIndex;
      int iTempTaskCount;
      int iProcessorCount;
  
      // 코어의 개수를 확인
      iProcessorCount = kGetProcessorCount();
  
      // 코어가 하나라면 현재 코어에서 계속 수행
      if( iProcessorCount == 1 ){
          return pstTask->bAPICID;
      }
  
      // 우선순위 추출
      bPriority = GETPRIORITY( pstTask->qwFlags );
  
      // 태스크가 포함된 스케줄러에서 태스크와 같은 우선순위의 태스크 수를 확인
      iCurrentTaskCount = kGetListCount( &( gs_vstScheduler[ pstTask->bAPICID ].vstReadyList[ bPriority ] ) );
  
      // 나머지 코어에서 현재 태스크와 같은 레벨을 검사
      // 자신과 태스크의 수가 적어도 2이상 차이 나는 것 중에서 가장 태스크 수가 작은 스케줄러의 ID를 반환
      iMinTaskCount = TASK_MAXCOUNT;
      bMinCoreIndex = pstTask->bAPICID;
      for( i = 0 ; i < iProcessorCount ; i++ ){
          if( i == pstTask->bAPICID ){
              continue;
          }
  
          // 모든 스케줄러를 돌면서 확인
          iTempTaskCount = kGetListCount( &( gs_vstScheduler[ i ].vstReadyList[ bPriority ] ) );
  
          // 현재 코어와 태스크 수가 2개 이상 차이나고 이전까지 태스크 수가 가장 작았던
          // 코어보다 더 작다면 정보를 갱신함
          if( ( iTempTaskCount + 2 <= iCurrentTaskCount ) &&
              ( iTempTaskCount < iMinTaskCount ) ){
                  bMinCoreIndex = i;
                  iMinTaskCount = iTempTaskCount;
              }
      }
  
      return bMinCoreIndex;
  }
  

• 부하 분산을 고려하여, 태스크를 등록하는 함수의 코드

  void kAddTaskToSchedulerWithLoadBalancing( TCB* pstTask ){
      BYTE bCurrentAPICID;
      BYTE bTargetAPICID;
  
      // 태스크가 동작하던 코어의 APIC를 확인
      bCurrentAPICID = pstTask->bAPICID;
  
      // 부하 분산 기능을 사용하고, 프로세서 친화도가 모든 코어(0xFF)로
      // 설정되었으면 부하 분산 수행
      if( ( gs_vstScheduler[ bCurrentAPICID ].bUseLoadBalancing == TRUE ) && 
          ( pstTask->bAffinity == TASK_LOADBALANCINGID ) ){
              // 태스크를 추가할 스케줄러를 선택
              bTargetAPICID = kFindSchedulerOfMinumumTaskCount( pstTask );
          }
      // 태스크 부하 분산 기능과 관계 없이 프로세서 친화도 필드에 다른 코어의 APIC ID가
      // 들어 있으면 해당 스케줄러로 옮겨줌
      else if( ( pstTask->bAffinity != bCurrentAPICID ) &&
               ( pstTask->bAffinity != TASK_LOADBALANCINGID ) )
      {
          bTargetAPICID = pstTask->bAffinity;
      }
      // 부하 분산 기능을 사용하지 않으면 현재 스케줄러에 다시 삽입
      else{
          bTargetAPICID = bCurrentAPICID;
      }
  
      // 임계 영역 시작
      kLockForSpinLock( &( gs_vstScheduler[ bCurrentAPICID ].stSpinLock ) );
  
      // 태스크를 추가할 스케줄러가 현재 스케줄러와 다르다면 태스크를 이동
      // FPU는 공유되지 않으므로 현재 태스크가 FPU를 마지막으로 썼다면 FPU 콘텍스트를 
      // 메모리에 저장해야 함
      if( ( bCurrentAPICID != bTargetAPICID ) &&
          ( pstTask->stLink.qwID == gs_vstScheduler[ bCurrentAPICID ].qwLastFPUUsedTaskID ) )
      {
          // FPU를 저장하기 전에 TS 비트를 끄지 않으면 예외 7 (Device Not Available)이 
          // 발생하므로 주의해야 함
          kClearTS();
          kSaveFPUContext( pstTask->vqwFPUContext );
          gs_vstScheduler[ bCurrentAPICID ].qwLastFPUUsedTaskID = TASK_INVALIDID;
      }
  
      // 임계 영역 끝
      kUnlockForSpinLock( &( gs_vstScheduler[ bCurrentAPICID ].stSpinLock ) );
  
      // 임계 영역 시작
      kLockForSpinLock( &( gs_vstScheduler[ bTargetAPICID ].stSpinLock ) );
  
      // 태스크를 수행할 코어의 APIC ID를 설정하고, 해당 스케줄러에 태스크 삽입
      pstTask->bAPICID = bTargetAPICID;
      kAddTaskToReadyList( bTargetAPICID, pstTask );
  
      // 임계 영역 끝
      kUnlockForSpinLock( &( gs_vstScheduler[ bTargetAPICID ].stSpinLock ) );
  }