• 태스크에 우선순위를 할당한다.
• 우선순위에 따라, 태스크를 실행하는 빈도를 조절함으로써 태스크의 수행 속도를 보장한다.

Ⅰ. 태스크 우선순위와 멀티레벨 큐 스케줄러 알고리즘

1. 태스크 우선순위와 큐 스케줄링 정책

• 멀티레벨 큐 스케줄러
  • 우선순위에 따라, 구분된 여러개의 큐를 사용하여 태스크를 수행하는 스케줄러이다.
  • 기존 라운드 로빈 스케줄러와 달리, 태스크가 대기하는 공간이 여러개이다.
• MINT OS는 태스크의 우선순위를 가장 높음, 높음, 중간, 낮음, 가장 낮음 5단계로 구분한다.
  • 가장 높음 단계 태스크
  • 우선순위가 가장 높으며, 다른 태스크보다 프로세서를 많이 할당받는다.
  • 태스크의 수행 시간을 보장한다.
  • 긴급하거나 주기적으로 수행되어야 하는 태스크에 사용된다.
  • 높음 ~ 가장 낮음 단계는 수행 시간 보장받고 싶은 정도에 따라 우선순위를 설정하면 된다.

Ⅱ. 멀티레벨 큐 스케줄러 업그레이드

1. 스케줄러 자료구조 업그레이드

• MINT64 OS의 멀티레벨 큐 스케줄러는 5개의 준비큐와 1개의 대기큐로 구성된다.

  • 5개의 준비 큐: 실행할 태스크를 선택하는데 사용된다.
  • 대기 큐: 종료될 태스크가 대기하는 큐로, 태스크 종료 기능을 구현하는데 사용된다.

• 수정된 스케줄러 자료구조와 매크로의 코드

  • 준비 큐와 대기 큐로 사용하는 리스트와 우선순위별로 태스크를 수행하는 횟수를 저장하는 영역을 추가하였다.

  // 준비 리스트의 수
  #define TASK_MAXREADYLISTCOUNT 5
  
  // 태스크의 우선순위
  #define TASK_FLAGS_HIGHEST     0
  #define TASK_FLAGS_HIGH        1
  #define TASK_FLAGS_MEDIUM      2
  #define TASK_FLAGS_LOW         3
  #define TASK_FLAGS_LOWEST      4
  
  typedef struct kSchedulerStruct
  {
      // 현재 수행 중인 태스크
      TCB* pstRunningTask;
  
      // 현재 수행 중인 태스크가 사용할 수 있는 프로세서 시간
      int iProcessorTime;
  
      // 실행할 태스크가 준비 중인 리스트, 태스크의 우선순위에 따라 구분
      LIST vstReadyList[ TASK_MAXREADYLISTCOUNT ];
  
      // 종료할 태스크가 대기 중인 리스트
      LIST stWaitList;
  
      // 각 우선순위별로 태스크를 실행할 횟수를 저장하는 자료구조
      int viExecuteCount[ TASK_MAXREADYLISTCOUNT ];
  } SCHEDULER;
  

• TCB의 플래그 필드에서 우선순위를 추출하고 변경하는 매크로

  • 태스크 속성을 나타내는 64비트 크기의 플래그 필드에서 하위 8비트를 할당하여 우선순위를 나타내는 필드로 사용한다.

  #define GETPRIORITY( x )            ( ( x ) & 0xFF )
  #define SETPRIORITY( x, priority )  ( ( x ) = ( ( x ) & 0xFFFFFFFFFFFFFF00 ) | \\ ( priority ) )
  

2. 스케줄러 함수 업그레이드

• 스케줄러 초기화 함수 업그레이드

  • 초기화 함수는 스케줄러의 초깃값을 설정한다.
  • 준비 리스트, 대기 리스트, 큐별 태스크 실행 횟수를 초기화하도록 수정한다.

  void kInitializeScheduler( void )
  {
  		int i;
  
  		// 태스크 풀 초기화
  		kInitializeTCBPool();
  
  		// 준비 리스트와 우선순위별 실행 횟수를 초기화하고 대기 리스트도 초기화
  		for( i = 0 ; i < TASK_MAXREADYLISTCOUNT ; i++ )
  		{
  				kInitializeList( &( gs_stScheduler.vstReadyList[ i ] ) );
  				gs_stScheduler.viExecuteCount[ i ] = 0;
  		}
  		kInitializeList( &( gs_stScheduler.stWaitList ) );
  
  		// TCB를 할당받아 실행 중인 태스크로 설정하여, 부팅을 수행한 태스크를 저장할 TCB를 준비
  		gs_stScheduler.pstRunningTask = kAllocateTCB();
  }
  

• 태스크 선택 함수 업그레이드

  • MINT64 OS의 큐 스케줄링 정책 : 현재 큐의 모든 태스크가 1회씩 실행되었을 때, 프로세서를 하위 우선순위 큐로 양보하는 것이다. 이와 같이 처리하려면 2가지 정보가 필요하다.

    ① 현재 큐에 있는 태스크의 개수

    ② 현재 큐의 태스크를 수행한 횟수

  • 문제점

    : 특정 시점에서 모든 큐가 태스크를 1회씩 수행하여, 하위 우선순위 큐로 프로세서를 양보한다면 큐에 태스크가 있음에도 불구하고 태스크가 선택되지 않는 문제가 발생할 수 있다.

  • 해결방안 : 큐에 태스크가 있는데도, 태스크가 선택되지 않은 경우 태스크를 선택하는 코드를 한 번 더 수행한다.

  • 수정된 태스크 선택 함수의 코드 ( 큐에서 태스크를 검사하는 코드를 루프로 감싸서, 최대 2번까지 수행하도록 하였다. )

    TCB* kGetNextTaskToRun( void )
    {
        TCB* pstTarget = NULL;
        int iTaskCount, i, j;
    
        // 큐에 태스크가 있으나 모든 큐의 태스크가 1회씩 실행된 경우, 모든 큐가 프로세서를 양보하여
        // 태스크를 선택하지 못할 수 있으니 NULL일 경우 한 번 더 수행
        for( j = 0; j < 2 ; j++)
        {
            // 높은 우선순위에서 낮은 우선순위까지 리스트를 확인하여 스케줄링할 태스크를 선택
            for( i = 0 ; i < TASK_MAXREADYLISTCOUNT ; i++ )
            {
                iTaskCount = kGetListCount( & ( gs_stScheduler.vstReadyList[ i ]));
    
                // 만약 실행한 횟수보다 리스트의 태스크 수가 더 많으면 현재 우선순위의 태스크를 실행
                if ( gs_stScheduler.viExecuteCount[ i ] < iTaskCount )
                {
                    pstTarget = ( TCB* ) kRemoveListFromHeader(
                                            &( gs_stScheduler.vstReadyList[ i ] ));
                    gs_stScheduler.viExecuteCount[ i ]++;
                    break;
                }
                // 만약 실행한 횟수가 더 많으면, 실행 횟수를 초기화하고 다음 우선순위로 양보
                else{
                    gs_stScheduler.viExecuteCount[ i ] = 0;
                }
            }
    
            // 만약 수행할 태스크를 찾았으면 종료
            if( pstTarget != NULL ){
                break;
            }
        }
        return pstTarget;
    }
    

• 태스크 등록 함수 업그레이드

  • 준비리스트에 우선순위에 맞춰, 태스크를 삽입하도록 수정한다.

  • 우선순위는 TCB 자료구조에 있는 플래그 필드의 하위 8비트를 통해 알 수 있으므로, 이를 읽어 해당 우선순위의 큐에 삽입하도록 수정한다.

  • 수정된 태스크 등록 함수의 코드

    BOOL kAddTaskToReadyList( TCB* pstTask )
    {
    		BYTE bPriority;
    
    		bPriority = GETPRIORITY( pstTask -> qwFlags );
    		if( bPriority >= TASK_MAXREADYLISTCOUNT )
    		{
    				return FALSE;
    		}
    
    		kAddListToTail( &( gs_stScheduler.vstReadyList[ bPriority ] ), pstTask );
    		return TRUE;
    }
    

3. 태스크 우선순위 제어

• 태스크의 우선순위를 변경하는 가장 간단한 방법

  • TCB의 플래그 필드에 있는 우선순위를 변경하고, 변경한 태스크가 수행되기를 기다리는 것이다.
  • 태스크 수행 후, 다른 태스크 전환시, kAddTaskToReadyList함수가 호출됨으로써 플래그 필드의 우선순위에 따라 큐에 삽입되기 때문이다.
  • 단점: 변경할 태스크가 한 번 수행된 후에, 우선순위가 실제로 적용된다는 점이다.

• MINT64 OS 경우, TCB를 직접 참조할 수 있으며 TCB의 플래그 필드에서 하위 8비트로 우선순위를 구할 수 있다.

  • 해당 우선순위의 큐에서 태스크를 즉시 제거한 후 플래그 필드의 우선순위 값을 변경하고 해당 큐에 삽입하면 우선순위 변경이 완료된다.

• 태스크 우선순위 변경 함수의 코드

  // 준비 리스트에서 태스크를 제거
  TCB* kRemoveTaskFromReadyList( QWORD qwTaskID ){
      TCB* pstTarget;
      BYTE bPriority;
  
      // 태스크 ID가 유효하지 않으면 실패
      if( GETTCBOFFSET( qwTaskID ) >= TASK_MAXCOUNT ){
          return NULL;
      }
  
      // TCB 풀에서 해당 태스크의 TCB를 찾아 실제로 ID가 일치하는가 확인
      pstTarget = &( gs_stTCBPoolManager.pstStartAddress[ GETTCBOFFSET( qwTaskID ) ] );
      if( pstTarget->stLink.qwID != qwTaskID )
      { 
          return NULL;
      }
  
      // 태스크가 존재하는 준비 리스트에서 태스크 제거
      bPriority = GETPRIORITY( pstTarget -> qwFlags );
      pstTarget = kRemoveList( &( gs_stScheduler.vstReadyList[ bPRiority ]), qwTaskID );
      return pstTarget;
  }
  
  // 태스크의 우선순위를 변경
  BOOL kChangePriority( QWORD qwTaskID, BYTE bPriority )
  {
      TCB* pstTarget;
  
      if( bPriority > TASK_MAXREADYLISTCOUNT ){
          return FALSE;
      }
  
      // 현재 실행중인 태스크이면, 우선순위만 변경
      // PIT 컨트롤러의 인터럽트(IRQ 0)가 발생하여 태스크 전환이 수행될 때 변경된
      // 우선순위의 리스트로 이동
      pstTarget = gs_stScheduler.pstRunningTask;
      if(pstTarget -> stLink.qwID == qwTaskID ){
          SETPRIORITY( pstTarget->qwFlags, bPriority );
      }
      // 실행 중인 태스크가 아니면, 준비 리스트에서 찾아서 해당 우선순위의 리스트로 이동
      else{
          // 준비 리스트에서 태스크를 찾지 못하면, 직접 태스크를 찾아서 우선순위를 설정
          pstTarget = kRemoveTaskFromReadyList( qwTaskID );
          if( pstTarget == NULL ){
              // 태스크 ID로 직접 찾아서 설정
              pstTarget = kGetTCBInTCBPool( GETTCBOFFSET( qwTaskID ));
              if( pstTarget != NULL )
              {
                  // 우선순위를 설정
                  SETPRIORITY( pstTarget->qwFlags, bPriority );
              }
          }
          else{
              // 우선순위를 설정하고 준비 리스트에 다시 삽입
              SETPRIORITY( pstTarget->qwFlags, bPriority );
              kAddTaskToReadyList( pstTarget );
          }
      }
      return TRUE;
  }
  

4. 콘솔 셸과 테스트 태스크의 우선순위 지정