[FreeRTOS] Task의 스케줄링

ㅤ

Context-Switch에 대해서 다루는 이전 글의 내용을 이해했다면, 이제 “Task 간의 전환”은 파악했다. (야스!)

그렇다면 이렇게 만들어진 Task 들에 대해서 커널은 어떻게 급한 Task가 먼저 CPU를 사용하도록 전환시키도록 하여 Real-Time의 특성을 만족시킬까?

ㅤ

미션 : Real-Time을 만족시켜라

여러가지 방법이 있지만, FreeRTOS 에서는 기본적으로 “Preemptive with Time Slicing” 방식을 사용한다.

• 우선순위가 낮은 Task가 실행중일 때, 우선순위가 높은 Task가 실행되고자 하면 선점한다.
• 우선순위가 동일한 Task가 여러개 실행되고자 한다면, Time Slicing 으로 CPU 자원을 동일한 시간만큼 할당받아, 번갈아가며 처리(Round-Robin)한다.

출처: Mastering the FreeRTOS Real Time Kernel, p.119

 

ㅤ

여기에서 중요한 키워드 둘인 Preemption과 Time Slicing에 대해서 먼저 살펴보기 전에, State Machine에 대한 파악이 필요하다. 두 키워드를 설명하는 글을 적다보니 State Machine에 대한 개념 없이는 설명하기 어렵더라.

ㅤ

FreeRTOS의 State Machine

FreeRTOS에서는 크게 4가지 상태로 나뉜다.

• Running : 실제로 CPU를 점유해 처리되고 있는 Task
• Ready : 모든 실행될 준비를 마치고 스케줄러에 의해 간택되기만을 기다리고 있는 Task
• Blocked : 특정 Event의 발생을 기다리는 Task. 만약 Event가 발생하면 처리되기 위해 Ready 목록으로 이동된다.
• Suspended : 스케줄러의 선택을 받지 못하는 상태. 스케줄링 완전 중단 == 잠시동안 State 변경이 멈춘다.

출처: Mastering the FreeRTOS Real Time Kernel, p.93

 

ㅤ

위 그림은 State Machine을 간략히 도표화한 것이다.

ㅤ

Task는 Running 상태에서 실행되다가, 특정 이벤트를 기다리도록 명령을 받으면 Blocked 상태에서 해당 이벤트가 발생하기를 기다린다. 여기에서 이벤트의 종류는 통신을 통한 비동기적인 입력, Delay의 종료, 세마포어나 뮤텍스, 큐를 통한 신호 전달 등이 모두 포함된다. 이러한 이벤트가 발생하면 Ready 상태로 이동해서 언제든지 스케줄러에 의해 선택만 받으면 CPU에서 실행될 수 있다고 스케줄러에게 알린다. 만약 특정한 상황 때문에 Task 들이 스케줄링이 되면 안되는 상황이 있다면 Task를 Suspended 상태에 보내, 잠시 스케줄링의 대상에서 빼버린다. 예를 들면 Critical Section에 들어가면서 현재 실행중인 Task 만 지속해서 실행이 되어야한다거나 하는 상황. Suspended 상태로부터 Resume을 하면 다시 스케줄링이 가능해진다.

ㅤ

Blocked → Suspended → Ready?

그런데, 약간 믿을 수 없는 내용들이 있어서 검증을 좀 해봤다.
Suspended 상태에서 TaskResume()을 하면 항상 Ready로 내려온다고 되어있는데, 어떻게 Blocked 상태인 녀석들까지 Ready가 되는거지..? ㅤ

ㅤ

그 점이 궁금해서 진짜 Blocked → Suspended → Ready 로 가는지 테스트를 해봤다. 처음에는 TCB에서 State를 나타내는 값을 찾아서 UART 로 출력하는 방식으로 디버깅을 하려고 했다가, STM IDE 자체에서 FreeRTOS 전용 Status 값을 확인하는 기능을 제공한다는 것을 검색하다가 알게되었다. 이 기능을 활용해서 어떻게 State가 변경되는지 확인해보자.

ㅤ

검증을 위한 코드는 아래처럼 작성해줬다. 여기에서 vTaskTest는 State의 변화를 Running → Blocked → Suspended → [ ??? ] → Running 과정을 거치도록 작성되었다. 과연 Blocked 상태에서 Suspended 로 이동한 다음 Resume을 하면 어떤 상태로 가게될까?

void vTaskTest(void *pvParameters)
{
    while(1)
    {
        printf("Task: Waiting for semaphore...\r\n");

        // Semaphore를 무한정 대기 (Blocked 상태 진입)
        xSemaphoreTake(xSemaphore, portMAX_DELAY);

        printf("Task: Got semaphore!\r\n");
        vTaskDelay(1000);
    }
}

void vControlTask(void *pvParameters)
{
    vTaskDelay(2000);

    // Task가 Semaphore 대기중 (Blocked)일 때 Suspend
    printf("Control: Suspending task...\r\n");
    vTaskSuspend(taskTestHandle);

    vTaskDelay(2000);

    // Resume (Blocked로 복귀할까? Ready로 갈까?)
    printf("Control: Resuming task...\r\n");
    vTaskResume(taskTestHandle);

    vTaskDelay(2000);

    // Semaphore를 줘봄
    printf("Control: Giving semaphore...\r\n");
    xSemaphoreGive(xSemaphore);

    while(1) vTaskDelay(1000);
}

ㅤ

(1) 처음 Task를 생성하고 실행하기 직전에는 Ready 상태

ㅤ

(2) 세마포어를 만나서 xTaskTest는 세마포어가 Give 되는 이벤트를 기다리며 Blocked 상태로 갔다.

ㅤ

(3) 이때 Blocked 에서 vTaskSuspend 함수를 통해 Suspended 상태로 보내버렸다.

ㅤ

(4) 대망의 궁금증. 여기에서 vTaskResume 을 하면 어디로 올 것인가? 과연 Ready로 돌아올까? 정답은 다시 Blocked 상태로 내려온다.

ㅤ

(5) 여기에서 Take할 수 있는 Semaphore가 나타나면 이벤트에 의해 Blocked 상태에서 깨어나 Ready → Running 상태로 올라오게된다.

ㅤ

State Machine 다이어그램과는 다르게, Suspended 상태에서 돌아올 때는 Blocked 상태에 있던 Task 들은 Blocked 상태로 돌아간다. 그림에 너무 현혹될 필요는 없었다.

ㅤ

Preemption, 선점

Preemption은 “CPU를 점유중인 Task의 의지와 관계없이 다른 Task가 CPU의 점유권을 가져오는 것”을 말한다. 즉, Task 밀어내기.

ㅤ

새로운 Task 가 생성되거나 후보에 올랐을 때 무조건 Task를 밀어내고 CPU를 차지할 수 있는 것은 아니다. Task들 간에도 상도덕이라는게 있다.

ㅤ

다음은 FreeRTOS에서 Preemption이 발생하는 경우이다.

1. ISR (Interrupt Service Routine) 에서 높은 우선순위의 Task를 깨우는 경우
   • ISR 내에서 호출된 xSemaphoreGiveFromISR, xQueueSendFromISR 같은 함수가 Blocked 상태의 Task 를 깨울 수 있다.
   • 이때 깨어난 Task의 우선순위가 Running 중인 Task의 우선순위보다 높다면 선점!
2. SysTick 인터럽트로 Delay 중이던 높은 우선순위의 Task 가 깨어나는 경우
3. Blocked 되어있던 Task가 Semaphore, Queue 등의 API 호출로 깨어나는 경우
   • 이때 깨어난 Task의 우선순위가 Running 중인 Task의 우선순위보다 높다면 선점!
4. Task의 우선순위가 높아지는 경우

ㅤ

결국 선점은 항상 ‘우선순위’를 중심으로 판단한다. 우선순위가 높다? 그럼 선점한다!

ㅤ

프로젝트 코드를 열심히 분석해봤다면 한 번쯤은 마주쳤을 FreeRTOSConfig.h 파일이 있다. 여기에서 Preemption 관련된 설정이 하나 있는데, 바로 configUSE_PREEMPTION 이라는 매크로 상수가 있다. 이 값이 1이라면 선점 기능을 사용하는 것이고, 0이라면 선점을 사용하지 않는다.

// FreeRTOSConfig.h 파일

#define configUSE_PREEMPTION        1

ㅤ

이 설정은 ioc 파일의 FREERTOS Config Params 에서도 동일하게 확인이 가능하다.

ㅤ

기본적으로 이 설정값이 Enabled 이기 때문에 더 높은 우선순위의 Task에 대해서 선점을 통해 우선 처리가 되도록 스케줄링을 할 수 있었다. 그런데 만약 이 설정을 Disable 시킨다면 선점이 일어나지 않는다. 그러면 CPU를 점유한 Task가 계속 자기 할 일을 수행한다.

• 더 높은 우선순위의 Task가 들어오더라도 현재 Task를 계속 실행함.
• (이후에 나오는 내용이지만) Time-Slicing을 통한 동일 우선순위 Task 간의 전환도 발생하지 않음.
• Task가 스스로 yield를 호출해 CPU 점유를 양보하거나, 세마포어 같은 Blocking API 를 통해 자신의 실행 흐름이 멈추어야만 다른 Task를 실행할 수 있음.
• 이 방식을 협력적 스케줄링 (Co-operative Scheduling) 이라고 한다.

ㅤ

Time Slicing, 시분할

여기에서 동일한 우선순위에 대한 Time Slicing은 SysTick을 기준으로 한다. (앞서 봤던 SysTick Handler가 하는 일이 바로 이것!!) FreeRTOS에서는 “Time Slice = 1 Tick” 이다.

ㅤ

만약 configTICK_RATE_HZ 의 값이 1000 이라면 1ms 마다 Time Slicing이 발생한다.

ㅤ

이후에 다시 한 번 살펴보겠지만, 스케줄링을 위한 커널을 부팅하는 과정에서 SysTick을 초기화하는 아래 코드를 확인할 수 있다. 여기에서 CTRL 을 비롯한 모든 값들을 넣어주고 있다.

__attribute__(( weak )) void vPortSetupTimerInterrupt( void )
{
    /* Stop and clear the SysTick. */
    portNVIC_SYSTICK_CTRL_REG = 0UL;
    portNVIC_SYSTICK_CURRENT_VALUE_REG = 0UL;

    /* Configure SysTick to interrupt at the requested rate. */
    portNVIC_SYSTICK_LOAD_REG = ( configSYSTICK_CLOCK_HZ / configTICK_RATE_HZ ) - 1UL;
    portNVIC_SYSTICK_CTRL_REG = ( portNVIC_SYSTICK_CLK_BIT | portNVIC_SYSTICK_INT_BIT | portNVIC_SYSTICK_ENABLE_BIT );
}

ㅤ

여기에서 Time Slice가 1 Tick 이라고 했는데, Tick의 간격을 조정하기 위한 값에는 2가지 변수가 사용되고 있다. FreeRTOSConfig.h 에서 이 값들을 확인할 수 있다.

• SYSTICK_CLOCK_HZ : 내부적으로는 SystemCoreCLK 을 사용
  • 이 값은 따라가보면 기본적으로 16M Hz로 되어있는데, 런타임에 실제로 유효한 CORE의 CLK 주파수 (나의 경우 168MHz) 으로 찾아간다.
• TICK_RATE_HZ : 어떤 간격으로 나눌 것인가? 기본적으로 1ms를 간격으로 만들기 위해 1000을 넣어준다.

ㅤ

만약 이 값을 수정해준다면, 내가 원하는 Tick 구간을 만들어줄 수 있을 것이다. 실제로, 2개의 Task가 자신의 LED만 켜는 예시 코드를 만들고 아래처럼 코드를 작성해주면 Tick 간의 간격이 0.1초로 Context-Switch가 수행되는 것을 시각적으로 확인 가능하다!

__attribute__(( weak )) void vPortSetupTimerInterrupt( void )
{
    /* Stop and clear the SysTick. */
    portNVIC_SYSTICK_CTRL_REG = 0UL;
    portNVIC_SYSTICK_CURRENT_VALUE_REG = 0UL;

    portNVIC_SYSTICK_CTRL_REG = ( portNVIC_SYSTICK_CLK_BIT | portNVIC_SYSTICK_INT_BIT | portNVIC_SYSTICK_ENABLE_BIT );
    // Source CLK을 AHB/8 을 지정하기
    portNVIC_SYSTICK_CTRL_REG |= 0x1 << 2;
    // 168MHz / 8 / 2 = 10.5MHz < 최대값인 16.7MHz
    portNVIC_SYSTICK_LOAD_REG = ( configSYSTICK_CLOCK_HZ / configTICK_RATE_HZ ) - 1UL;
}

// 현재 어떤 Task가 CPU를 점유하고 있는지 시각적으로 확인하기 위해,
// 서로의 불을 끄고 자신의 불을 켜는 Task 2개를 실행해보자.
void Task1(void const * argument)
{
    for(;;)
    {
        GPIOB->BSRR = 0x1 << 0;
        GPIOB->BSRR = 0x1 << 7 << 16;
    }
}

void Task2(void const * argument)
{
    for(;;)
    {
        GPIOB->BSRR = 0x1 << 7;
        GPIOB->BSRR = 0x1 << 0 << 16;
    }
}

(그런데, 이렇게 Tick 간격을 늦추는게 의미가 있을지는 잘 모르겠다. 그치만, 이런 방식으로 Tick 간격을 내가 조정할 수 있다는 것은 알아두자. config 파일에서 TICK_RATE_HZ 값을 통해서도 이런 방법으로 변경이 가능하다는 것도 파악해두자.)

ㅤ

ㅤ

이벤트 기반의 Task 관리 (Event-Driven Task)

현재 우선순위가 높은 Task가 실행중이라고 해도, 이 친구들도 통신 프로토콜을 따르기 위해 잠시 몇 ms 동안 가만히 대기를 해야하거나 자원 점유를 위해 세마포어 등의 Event를 기다리거나 하는 등 Task가 처리할 일이 없는 상황이 찾아온다. 이때 이 CPU가 아무것도 하지 않으면 너무 아까우니깐! 높은 Task의 처리가 지연된 잠깐 사이에 낮은 우선순위의 Task를 CPU로 올려서 처리를 할 수 있다.

ㅤ

이런 Task의 현재 상태를 나타내기 위해서 앞서 봤던 State Machine을 사용한다. 우선순위가 높은 Task의 처리가 지연될 때 Blocked 상태로 내려가게 되고, 이벤트가 발생하면 Ready 상태로 올라와 다시 Scheduler의 선택을 받고 CPU에서 처리되는 Running 상태가 된다.

ㅤ

사실 Task는 대부분의 시간동안 Blocked 상태에서 자신이 실행할 수 있는 환경이 될 때 까지 Event를 기다리다가, 이벤트가 발생하면 Ready 상태가 되고, 스케줄러의 선택을 받아 CPU를 사용할 수 있다.
예) 마우스 커서 움직이기 / 1초마다 후레시 켜고 끄기

ㅤ

이러한 Task 관리 방법을 “Event-Driven Task” 라고 한다.

이벤트 기반의 구조로 스케줄링을 하게되면, 우선순위가 높은 Task라도 Blocked 상태에 있을 때에는 CPU 점유를 양보하기 때문에 우선순위가 낮은 Task가 더 빨리 실행될 기회를 가질 수 있다.

항목	Continuous Task	Event-Driven Task
CPU 점유	항상 Running	이벤트 있을 때만 Running
효율성	낮음 (busy-wait)	높음
전력 소비	많음	적음
우선순위 관리	어려움 (starvation 가능)	용이
실사용 예시	테스트용 루프	실제 시스템 태스크 (센서, 통신 등)

ㅤ

Task의 우선순위 - Priority

FreeRTOS 에서는 각 Task에게 우선순위를 부여하고 있다. Priority가 N 단계 있다고 할 때, 각 0~(N-1) 단계를 가진다. 그럼 우선순위는 몇 단계가 있냐? 하면 이거슨 FreeRTOSConfig.h 에서 찾을 수 있다. (물론 ioc 파일에서도 확인할 수 있다)

현재 나의 기본 FreeRTOS 설정은 7로 되어있다. 즉, 0부터 시작해서 6까지, 총 7단계의 Task가 있다는 이야기.

ㅤ

Priority의 단계는 많을수록 해상도가 높아지니 좋을텐데, 왜 이걸 설정할 수 있게 해뒀을까?

 

의 이유에 대해서는 메모리 사용량이 증가하기 때문이라고 한다. 아니 아무리 커봤자 32단계의 우선순위를 6개의 bit로 표현할 수 있고 각 한 자리당 1bit씩 쓴다고 하더라도 32bit 로 표현이 가능할텐데 이게 왜 용량이 많이 든다는거지? 라고 생각했었는데, StateList에서 메모리 사용량이 늘어난다는 설명에 고개를 끄덕였다. 🆗

ㅤ

FreeRTOS에서는 State 관리를 위해 각 우선순위에 대해서 각각 ReadyList 를 링크드리스트 형태로 관리한다. 이때 만약 7개의 우선순위라면 링크드리스트를 7개만 관리하면 되지만, 32개의 우선순위를 사용한다면 링크드리스트를 32개나 관리해야한다. 물론 필요하다면 더 많은 우선순위를 반드시 써줘야겠지만, 굳이굳이 모먼트라면 최대한 적은 우선순위를 사용해 메모리 사용량을 최적화하려 노력해야한다.

ㅤ

우리의 FreeRTOS CMSIS에서는 7개의 Priority가 설정되어 있고, 이걸 CMSIS에서는 친절하게도 이름을 붙여서 사용하기 쉽게 만들어줬다. 아래 enum 값을 보면 7개의 우선순위 + 에러로, 총 8개의 값을 사용할 수 있다.

cmsis_os.h
/// Priority used for thread control.
/// \note MUST REMAIN UNCHANGED: \b osPriority shall be consistent in every CMSIS-RTOS.
typedef enum  {
  osPriorityIdle          = -3,          ///< priority: idle (lowest)
  osPriorityLow           = -2,          ///< priority: low
  osPriorityBelowNormal   = -1,          ///< priority: below normal
  osPriorityNormal        =  0,          ///< priority: normal (default)
  osPriorityAboveNormal   = +1,          ///< priority: above normal
  osPriorityHigh          = +2,          ///< priority: high
  osPriorityRealtime      = +3,          ///< priority: realtime (highest)
  osPriorityError         =  0x84        ///< system cannot determine priority or thread has illegal priority
} osPriority;

ㅤ

그런데 엣? 분명 우선순위의 범위는 0~ 이였는데 여기에는 음수값이 들어있다. 오잉? 이라는 생각이 들 수 있지만, 이건 os 계층의 enum 이므로 (이름부터가 osPriority) 사실 FreeRTOS랑 전혀 관계가 없다. 내부적으로 osPriority를 FreeRTOS의 우선순위로 바꿔주는 함수를 호출해서 사용하고 있기 때문에 큰 문제는 되지 않는다.

 

/* Convert from CMSIS type osPriority to FreeRTOS priority number */
static unsigned portBASE_TYPE makeFreeRtosPriority (osPriority priority)
{
  unsigned portBASE_TYPE fpriority = tskIDLE_PRIORITY;

  if (priority != osPriorityError) {
    fpriority += (priority - osPriorityIdle);
  }

  return fpriority;
}

ㅤ

우선순위가 0인 Idle Task

Idle Task는 FreeRTOS가 자동으로 생성해주는 특별한 Task 이다. (요 녀석은 우선순위로 osPriorityIdle 을 가지는 Task를 부르는 이름이 아니다!)

• 가장 낮은 우선순위(0)를 가짐
• 커널의 부팅과 함께 자동으로 내부적으로 생성됨
• Ready상태의 다른 Task가 없다면 실행됨

ㅤ

이 Idle Task가 필요한 이유는 Cortex-M 같은 프로세서는 항상 무언가를 실행하는 상태여야 하기 때문에, 수행할 Task가 없는 상황에서 처리할 무언가(책상에 앉아서 동그라미 그리기)를 제공해주기 위해 Idle Task를 만들었다.

• 처리할 Task가 없더라도 CPU는 Fetch - Decode - Execute 3가지 Step을 반복할 수 있어야 한다.
• 이 Idle Task가 없으면 시스템이 뻗어버릴 수 있다.

ㅤ

이게 실제로 생성되는지 확인할 수 있는 코드는 이후에 KernelStart 를 다루는 글에서 다룰 에정이다.

ㅤ

아니 그럼 무언가 처리하지 않고 대기할 수 있는 프로세서도 있다는 말일까..?
→ 조금있다가 확인하겠지만, 그냥 CPU CLK을 끊어버리고 저전력 Sleep 상태로 들어가버리는 경우도 있다…!

ㅤ

우리가 사용하는 FreeRTOS 에서는 IdleTask에서 아무것도 하지 않는 것은 아니였다!

• 삭제된 Task가 있다면 메모리 할당을 해제한다.
• config 에 따라서 다양한 동작을 수행한다.
  • 협력적 Scheduling을 사용하고 있었다면 다른 Task에게 자리를 양보하기
  • 일하는 Idle Task 에게 자리 양보하기
  • Hook을 통한 작업 처리
• 설정을 한 경우, Idle 시간을 계산해서 아예 CPU의 CLK을 끊어버리는 저전력 모드도 가능하다!

static void prvIdleTask(void* pvParameters )
{
    /* Stop warnings. */
    ( void ) pvParameters;

    /** THIS IS THE RTOS IDLE TASK - WHICH IS CREATED AUTOMATICALLY WHEN THE
    SCHEDULER IS STARTED. **/

    for( ;; )
    {
        // 삭제된 Task 의 메모리 해제 등을 수행
        prvCheckTasksWaitingTermination();

// 옵션 1
        #if ( configUSE_PREEMPTION == 0 )
        {
            // 선점을 안쓰고 있다면 Idle Task는 항상 다른 Task에게 CPU를 양보하기 위해 노력
            taskYIELD();
        }
        #endif /* configUSE_PREEMPTION */

// 옵션 2
        #if ( ( configUSE_PREEMPTION == 1 ) && ( configIDLE_SHOULD_YIELD == 1 ) )
        {
            // 만약 다른 Idle 우선순위를 갖는 Task가 또 있다면
            // 해당 Task에게 바로 양보하기 (어차피 이 Task는 아무것도 안하니깐)
            if( listCURRENT_LIST_LENGTH( &( pxReadyTasksLists[ tskIDLE_PRIORITY ] ) ) > ( UBaseType_t ) 1 )
            {
                taskYIELD();
            }
        }
        #endif /* ( ( configUSE_PREEMPTION == 1 ) && ( configIDLE_SHOULD_YIELD == 1 ) ) */

// 옵션 3
        // IDLE HOOK을 사용하겠다고 설정한 경우
        // Idle Task 에서 vApplicationIdleHook 함수가 호출된다.
        // 이 함수의 구현은 내가 직접 정의해줄 수 있다.
        #if ( configUSE_IDLE_HOOK == 1 )
        {
            extern void vApplicationIdleHook( void );

            vApplicationIdleHook();
        }
        #endif /* configUSE_IDLE_HOOK */

// 옵션 4
        // 만약 저전력모드가 설정되어 있다면 (Sleep, Stop, Standby)
        #if ( configUSE_TICKLESS_IDLE != 0 )
        {
        TickType_t xExpectedIdleTime;

            // Idle에 진입하여 머물게될 예상 시간
            xExpectedIdleTime = prvGetExpectedIdleTime();

            // 만약 이 값이 Sleep 진입 Threashold 보다 길다면 
            // Task 스케줄링을 잠시 멈추고, 일정 시간동안 프로세서를 잠재우기
            // == CPU로 들어가는 CLK을 차단해버림 (정지)
            if( xExpectedIdleTime >= configEXPECTED_IDLE_TIME_BEFORE_SLEEP )
            {
                vTaskSuspendAll();
                {
                    // 지금부터 대기할 시간을 계산해서
                    // Sleep 에 들어갔다가 시간이 되면 나오기!
                    xExpectedIdleTime = prvGetExpectedIdleTime();
                    if( xExpectedIdleTime >= configEXPECTED_IDLE_TIME_BEFORE_SLEEP )
                    {
                        portSUPPRESS_TICKS_AND_SLEEP( xExpectedIdleTime );
                    }
                }
                ( void ) xTaskResumeAll();
            }
        }
        #endif /* configUSE_TICKLESS_IDLE */
    }
}

ㅤ

ㅤ

State 의 관리 방법

FreeRTOS에서는 Linked List를 기반으로 모든 Task의 State를 관리한다. 각각의 상태마다 별도의 List가 존재하며, Task는 State가 변화하면 기존의 List에서 해당 List로 이동한다.

ㅤ

typedef struct xLIST
{
    volatile UBaseType_t uxNumberOfItems;   // List에 있는 항목 수
    ListItem_t * pxIndex;                   // List 순회용 포인터
    MiniListItem_t xListEnd;                // List의 끝 마커 (Sentinel)
} List_t;

typedef struct xLIST_ITEM
{
    TickType_t xItemValue;              // 정렬 기준 값 (우선순위 또는 Wake Time)
    struct xLIST_ITEM * pxNext;         // 다음 항목
    struct xLIST_ITEM * pxPrevious;     // 이전 항목
    void * pvOwner;                     // 이 항목을 소유한 객체 (보통 TCB)
    struct xLIST * pxContainer;         // 이 항목이 속한 List
} ListItem_t;

ㅤ

이 자료구조는 Task의 메타데이터를 담는 구조체인 TCB에 포함되어있다.

typedef struct tskTaskControlBlock             /* The old naming convention is used to prevent breaking kernel aware debuggers. */
{
    volatile StackType_t    *pxTopOfStack;    /*< Points to the location of the last item placed on the tasks stack.  THIS MUST BE THE FIRST MEMBER OF THE TCB STRUCT. */

    ListItem_t            xStateListItem;    /*< The list that the state list item of a task is reference from denotes the state of that task (Ready, Blocked, Suspended ). */
    ListItem_t            xEventListItem;        /*< Used to reference a task from an event list. */
    UBaseType_t            uxPriority;            /*< The priority of the task.  0 is the lowest priority. */
    StackType_t            *pxStack;            /*< Points to the start of the stack. */
    char                pcTaskName[ configMAX_TASK_NAME_LEN ];/*< Descriptive name given to the task when created.  Facilitates debugging only. */ /*lint !e971 Unqualified char types are allowed for strings and single characters only. */
    ...
}

ㅤ

각 Task는 FreeRTOS에서 관리하는 Task State List에 자신을 넣었다가 빼면서 State를 관리한다. 즉, 현재 자신이 속해있는 List가 어디인지가 Task의 현재 State 를 나타낸다.

/* Lists for ready and blocked tasks. --------------------
xDelayedTaskList1 and xDelayedTaskList2 could be move to function scople but
doing so breaks some kernel aware debuggers and debuggers that rely on removing
the static qualifier. */

// Ready가 되면 Task는 우선순위에 따라 각자의 Ready List에 들어간다.
PRIVILEGED_DATA static List_t pxReadyTasksLists[ configMAX_PRIORITIES ];
/*< Prioritised ready tasks. */

// 현재 Delayed Task를 관리하기 위해 사용하는 List
PRIVILEGED_DATA static List_t xDelayedTaskList1;                        
/*< Delayed tasks. */

// 현재 Delayed Task를 관리하기 위해 사용하는 List
// Timer가 Overflow가 발생하여 다시 0부터 카운트 할 때까지 기다려야하는 Task를 위한 List
PRIVILEGED_DATA static List_t xDelayedTaskList2;                        
/*< Delayed tasks (two lists are used - one for delays that have overflowed the current tick count. */

// 위 List를 가리키기 위한 Pointer
PRIVILEGED_DATA static List_t * volatile pxDelayedTaskList;                
/*< Points to the delayed task list currently being used. */
PRIVILEGED_DATA static List_t * volatile pxOverflowDelayedTaskList;        
/*< Points to the delayed task list currently being used to hold tasks that have overflowed the current tick count. */

// Suspended 상태 -> Ready로 이동할 Task가 잠시 대기하기 위한 List
PRIVILEGED_DATA static List_t xPendingReadyList;                        
/*< Tasks that have been readied while the scheduler was suspended.  They will be moved to the ready list when the scheduler is resumed. */

// Suspended 상태의 Task를 위한 List
PRIVILEGED_DATA static List_t xSuspendedTaskList;                    
/*< Tasks that are currently suspended. */

// 메모리 정리가 필요해 대기중인 Task List
PRIVILEGED_DATA static List_t xTasksWaitingTermination;                
/*< Tasks that have been deleted - but their memory not yet freed. */
PRIVILEGED_DATA static volatile UBaseType_t uxDeletedTasksWaitingCleanUp = ( UBaseType_t ) 0U;

ㅤ

아래 같은 느낌으로 Task 들의 State를 List를 활용해 관리하고, 이를 활용해 Scheduler가 다음 수행할 Task를 선택하는 방식으로 스케줄링을 수행한다.

• 이 그림에서 높은 우선순위의 Task가 먼저 실행되기 때문에, 낮은 우선순위의 Task들은 위 Task들이 처리되기를 기다린다. (선점)
• 또, 같은 우선순위의 Task에 대해서는 pxIndex가 가리키는 순서대로 차례로 List를 순회하면서 CPU를 점유하게 된다. (Time Slicing - Round Robin)

ㅤ

위 상황에서 ReadyTasksList[2]에 대한 List를 간략하게 그려보면 아래 그림과 같다.

이런 List 구조가 모든 Task State에 대해서 생성되어 있으며, Task 들은 이 List 들에 자신의 ListItem을 이동시키면서 상태를 스케줄러에게 알린다.

ㅤ

스케줄러는 앞서 코드로 작성해둔 다양한 StateList들과 관련된 레지스터들을 보면서 “현재 어떤 Task가 실행의 대상이 되기 가장 적합한가?”를 확인하고 해당 Task를 선택한다.

ㅤ

주의! Ready → Running 전환이 되더라도 Ready List에서 유지된다!

처음에는 Ready 에서 Running으로 Task 가 선택된다면 Ready 목록에서 빼낼 거라고 생각했었다. (이름 상 그게 맞으니깐) 그런데, 몇 가지 이유로 굳이 이렇게 할 필요가 없겠다는 생각이 들었고, 혹시 내 생각이 맞는지 궁금해서 찾아봤다.

• 어차피 Context-Switch에 의해 다시 원래 ReadyList로 돌아오게 된다.
• Running 중 Priority가 변하면서 Ready 상태로 내려가는 것은 드문 일이다.
• 매 Context-Switch 마다 List에서 빼고 넣고 작업을 하는게 매우 비효율적이다. (오버헤드가 크다)

ㅤ

그래서 Ready List에서 Running 으로 Task를 옮기는 대신에 pxCurrentTCB 라는 pointer로 현재 실행중인 Task를 가리키도록 구현되어있다. 즉, Task는 Running 상태가 되더라도 Ready List에서 제거되지 않고 유지되며 + CurrentTCB 포인터가 현재 스케줄러가 선택한 Task의 TCB를 가리키면 Running 이 된다.

ㅤ

Scheduler가 다음 실행할 Task를 찾는 과정

앞서 언급하였듯, 다음 실행될 Task는 pxCurrentTCB 포인터가 새롭게 가리키는 Task이다. 그렇다면 이 Task는 어떻게 선정될까?

ㅤ

이 작업은 vTaskSwitchContext 함수에서 수행된다. (이건 PendSV 인터럽트가 발생하면 PendSV_Handler 에서 호출되는 함수이다)

void vTaskSwitchContext( void )
{
    if( uxSchedulerSuspended != ( UBaseType_t ) pdFALSE )
    {
        // 현재 스케줄링이 중지되어있다면 전환하지 않음
        xYieldPending = pdTRUE;
    }
    else
    {
        xYieldPending = pdFALSE;

        // 오버플로우 검사
        taskCHECK_FOR_STACK_OVERFLOW();

        // 다음 실행할 가장 우선순위가 높은 Task를 선택
        taskSELECT_HIGHEST_PRIORITY_TASK(); 
    }
}

위 함수에서 taskSELECT_HIGHEST_PRIORITY_TASK() 를 통해서 Task가 전환되게 된다. 내부를 한 번 살펴보자! 이는 사실 매크로로, 내부에 더 많은 내용들을 담고있다.

ㅤ

#define taskSELECT_HIGHEST_PRIORITY_TASK()                                      \
{                                                                               \
    UBaseType_t uxTopPriority;                                                  \
                                                                                \
    /* Find the highest priority list that contains ready tasks. */            \
    portGET_HIGHEST_PRIORITY( uxTopPriority, uxTopReadyPriority );             \
    listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &( pxReadyTasksLists[ uxTopPriority ] ) );   \
}

ㅤ

2개의 매크로로 구성되어있다. 하나는 가장 높은 우선순위가 얼만지 구하고, 하나는 해당 우선순위에서 그 다음 Task를 찾아 pxCurrentTCB 로 가리키는 역할을 한다.

ㅤ

#define portGET_HIGHEST_PRIORITY( uxTopPriority, uxReadyPriorities )           \
    uxTopPriority = ( 31UL - ( uint32_t ) ucPortCountLeadingZeros( ( uxReadyPriorities ) ) )

이 함수는 Bit 계산을 통해 현재 Ready 상태인 가장 높은 우선순위가 무엇인지 찾는다. Task 번호나 개수 이런건 중요하지 않음. 그냥 가장 높은 우선순위 Index만 찾는다.

ㅤ

이 기능을 하기 위해서 CountLeadingZeros 라는 명령어가 어셈블리에 추가되었다. 매우 중요한 + 성능이 필요한 기능이라 그런가보다. 오호… 이런건 유래가 있는 명령어는 또 처음 본다! 신기해
__asm volatile ( "clz %0, %1" : "=r" ( ucReturn ) : "r" ( ulBitmap ) );

ㅤ

// 상태 List에서 
#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                           \
{                                                                               \
    List_t * const pxConstList = ( pxList );                                    \
                                                                                \
    /* Increment the index to the next item and return the item, ensuring */   \
    /* we don't return the marker used at the end of the list. */              \
    ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;               \
                                                                                \
    if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )                            \
    {                                                                           \
        ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;           \
    }                                                                           \
                                                                                \
    ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                             \
}

여기에서는 앞서 구한 현재 우선순위를 가지고 우선순위 Ready 목록을 선택한 뒤, 해당 목록에서 pxIndex를 넘겨가며 Task의 TCB의 주소를 pxCurrentTCB 에 담는다.

ㅤ

위 과정이 보기 힘드니깐, 함수로 만들면 아래와 같이 정리할 수 있다.

void taskSelectHighestPriorityTask(void) 
{
    UBaseType_t uxTopPriority;

    // 최고 우선순위 찾기
    uxTopPriority = (31UL - (uint32_t)ucPortCountLeadingZeros(uxTopReadyPriority));

    // 해당 우선순위 리스트에서 다음 실행할 태스크 가져오기
    List_t * const pxConstList = &(pxReadyTasksLists[uxTopPriority]);

    // 다음 항목으로 인덱스 이동
    pxConstList->pxIndex = pxConstList->pxIndex->pxNext;

    // 리스트 끝 마커를 건너뛰기
    if ((void *)(pxConstList->pxIndex) == (void *)&(pxConstList->xListEnd))
    {
        pxConstList->pxIndex = pxConstList->pxIndex->pxNext;
    }

    // 현재 TCB 업데이트
    pxCurrentTCB = pxConstList->pxIndex->pvOwner;
}

ㅤ

---

Real-Time 시스템을 만족시키기 위해서 스케줄러는 우선순위를 기반으로 선점 + SysTick 을 기반으로 Time Slicing 으로 Task 들을 실행시킨다. 이 과정에서 다양한 우선순위의 Task 들 중에서 어떤 Task를 그 다음으로 선택할 지에 대해서 결정하는 과정을 알아보았다.

ㅤ

사실 위 과정만으로는 RT 시스템을 만족시키기 어렵다. 항상 동기적인 Task 로 처리하는 이벤트만 발생하는 것이 아니라, 통신의 입력이나 센서 감지 등 비동기적인 Event와 외부 입력이 함께 발생하기 때문이다. 이를 위해서는 Interrupt 기반의 처리 (Interrupt Service Routine) 에 대해서 추가로 보아야 한다.

ㅤ

또, 이렇게 Task 들을 관리해주는 함수들은 다 만들어져있고 구현되어 있는데, 이걸 호출해줄 프로세스(실행 흐름)가 필요하다. 즉, OS의 커널이 필요하다. 이 커널을 RTOS의 부팅과 함께 시작하는 과정에 대해서도 곧 살펴볼 예정이다.

ㅤ

글이 너무 길어져서 이 부분들은 또 추후 아티클로 작성할 예정이다! 커밍쑨!

ㅤ