실시간 태스크 스케줄링 (FIFO, RR, DEADLINE)

reference:

• "리눅스 커널 내부구조" / 백승재, 최종무
• "Operating Systems: Three Easy Pieces" / Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau

스케줄링 동작원리
컴퓨터 시스템의 가장 중요한 자원 중 하나인 CPU를 어떤 태스크가 사용하도록 할 것인가는 중요하다. 공정해야 여러 태스크들이 공평하게 자신의 작업을 수행할 수 있으며, 효율적이어야 가장 높은 처리율(throughput)을 낼 수 있을 것이다. 또한 가장 급한 태스크를 한가한 태스크보다 먼저 수행될 수 있도록 해준다면 높은 반응성을 보일 것이다.

task_struct 구조체는 policy, prio, rt_priority 등의 필드가 존재한다.
policy 필드는 이 태스크가 어떤 스케줄링 정책을 사용하는지를 나타낸다. 리눅스의 태스크는 실시간 태스크와 일반 태스크로 나뉘며, 실시간 태스크를 위해 3개, 일반 태스크를 위해 3개, 총 6개의 스케줄링 정책이 존재한다.

구체적으로 실시간 태스크를 위해 SCHED_FIFO, SCHED_RR, SCHED_DEADLINE 정책이 사용된다. 일반 태스크를 위해선 SCHED_NORMAL 정책이 사용되며 이와 더불어 중요하지 않은 일을 수행하는 태스크가 CPU를 점유하는 것을 막기 위해 가장 낮은 순위로 스케줄링되는 SCHED_IDLE 정책, 사용자와 상호 작용이 없는 CPU 중심의 일괄 작업(batch job) 태스크를 위한 SCHED_BATCH 정책이 존재한다.

실시간 태스크란

실시간 태스크란 SCHED_FIFO, SCHED_RR, SCHED_DEADLINE 정책을 사용하는 태스크를 의미한다. 즉, 실시간 태스크를 생성하는 별도의 함수가 존재하는 것이 아니라 sched_setscheduler() 등의 함수를 통해 태스크의 스케줄링 정책을 위 세 가지 중 하나로 바꾸게 되면 실시간 태스크가 되는 것이다.

실시가 태스크는 우선순위 설정을 위해 task_struct 구조체의 rt_priority 필드를 사용한다. 0~99까지의 우선순위를 가질 수 있으며, 태스크가 수행을 종료하거나, 스스로 중지하거나, 혹은 자신의 타임 슬라이스를 다 쓸때까지(이 경우 SCHED_RR에 해당) CPU를 사용한다. 즉, RR이라면 동일 우선순위를 가지는 태스크가 복수개인 경우 타임 슬라이스 기반으로 스케줄링된다. 만약, 동일 우선순위를 가지는 RR 태스크가 없는 경우라면 FIFO와 동일하게 동작된다. 또한 실시간 정책을 사용하는 태스크는 고정 우선순위를 가지게된다. 따라서 우선순위가 높은 태스크가 낮은 태스크보다 먼저 수행된다는 것을 보장한다.

우선순위가 가장 높은 태스크 찾는 방법

FIFO 혹은 RR 스케줄링 정책을 사용하는 실시간 태스크 중 우선순위가 가장 높은 태스크를 찾는 효율적 방법은 비트맵을 사용하는 것이다.
이전에 언급한 모든 태스크들이 연결된 이중 연결 리스트를 순서대로 탐색하여 시스템에 존재하는 실시간 태스크(FIFO나 RR을 스케줄링 정책으로 사용하고 있는) 중 가장 높은 우선순위의 태스크를 골라내면 된다. 하지만 선형적으로 증가하는 시간(시간복잡도: O(n))으로 인해 스케줄링에 소모되는 시간을 예측할 수 없는 문제가 발생한다.(이것이 바로 과거 리눅스 커널 버전 2.4의 스케줄러 였음.)

비트맵 사용

FIFO 혹은 RR 정책을 사용하는 실시간 태스크들이 가질 수 있는 모든 우선순위 레벨(0~99)을 표현할 수 있는 비트맵(rt_prio_array.bitmap)을 준비한다.
태스크가 생성되면 비트맵에서 그 태스크의 우선순위에 해당하는 비트를 1로 설정한 뒤, 태스크의 순선위에 해당되는 큐(rt_prio_array.queue)에 삽입된다.
스케줄링 시점이 되면 커널은 비트맵에서 가장 처음으로 set되어 있는 비트를 찾아 낸뒤(가장 높은 우선순위를 찾아낸 뒤), 그 우선순위 큐에 매달려 있는 태스크를 선택한다.
고청된 크기의 비트맥에서 최우선 비트를 찾아내는 것은 상수시간 안에 가능하다.

DEADLINE 정책

DEADLINE 정책은 잘 알려진 실시간 태스크 스케줄링 기법 중 하나인 EDF(Earliest Deadline First) 알고리즘을 구현한 것이다. 앞서의 실시간 태스크 스케줄링 정책(FIFO, RR)은 우선순위를 기반하여 스케줄링 대상을 선정하는데 반해, DEADLINE 정책은 deadline이 가장 가까운(즉 가장 급한) 태스크를 스케줄링 대상을 선정한다.

리눅스의 DEADLINE 정책에서는 '완료시간'(언제까지 반드시 수행이 완료되어야 함을 뜻하는)을 deadline, '작업량'을 runtime, 주기성을 period라 한다.
정상적인 동작을 위해서는 태스크의 runtime과 deadline은 '현재 시간 + runtime < deadline'의 조건을 만족해야 하며, DEADLINE 정책을 사용하는 태스크들의 runtime 합은 CPU의 최대 처리량을 넘어서는 안된다.

결국 새로운 태스크가 DEADLINE 정책을 사용하려 할 때 DEADLINE 정책을 사용하는 기존 태스크들의 runtime, period를 이용해 해당 태스크의 성공적인 완료 여부를 확정적(deterministic)으로 결정할 수 있다는 의미. 이러한 확정성은 실시간 스케줄링 기법의 가장 중요한 요소 중 하나.

스케줄링 과정

DEADLINE 정책을 사용하는 각 태스크들은 deadline을 이용하여 RBTree(Red-Black Tree)에 정렬되어 있으며, 스케줄러가 호출되면 가장 가까운 deadline을 가지는 태스크를 스케줄링 대상으로 선정한다. 즉 DEADLINE 정책을 사용하는 태스크이 경우 우선순위는 의미가 없으며, FIFO, RR 등 기존의 우선순위 기반 스케줄링 정책 대비 기아 현상(starvation) 등의 문제에 효율적이다.

주기성을 가지는(periodic) 실생활의 많은 프로그램(영상, 음성, 스트리밍 등)과 제약 시간을 가지는 많은 응용 프로그램들에 효과적으로 적용 가능.