스케줄러 소스 분석

리눅스 커널은 다음과 같이 5가지 종류의 스케줄러를 운영하고 있다.

1. Stop Scheduler (STOP)
   • stop_sched_class 구조체로 정의된다.
   • 우선순위가 높아서 가장 먼저 처리해야 하는 태스크를 관리한다.
2. DeadLine Scheduler (DL)
   • dl_sched_class 구조체로 정의된다.
   • 마감 시간내에 처리해야 하는 태스크를 관리한다. 마감 시간 내에 일을 완료해야 하므로 우선순위가 Stop 스케줄러 다음으로 높다.
3. RealTime Scheduler (RT)
   • rt_sched_class 구조체로 정의된다.
   • 실제 정해진 시간마다 처리해야 하는 태스크를 관리한다. 약속된 시간을 지켜야하므로 우선 순위가 높은 편이다.
4. Fair Scheduler (CFS)
   • fair_sched_class 구조체로 정의된다.
   • 실제 시간에 얽매이지 않고 태스크에 주어진 우선 순위만큼 공평(Fair)하게 돌아가면서 일하는 태스크들을 관리한다.
5. Idle Scheduler (IDLE)
   • idle_sched_class 구조체로 정의된다.
   • 휴식을 취해도 되는 대기 태스크들을 관리한다. 가장 우선순위가 낮다.

각 스케줄러마다 다른 우선순위를 가진다.

순위	명칭	정책(policy)	prio	실행큐
1	Stop Scheduler			rq->stop
2	DeadLine Scheduler	SCHED_DEADLINE	prio < 0	dl_rq
3	RealTime Scheduler	SCHED_FIFO, SCHED_PR	prio < 100	rt_rq
4	Fair Scheduler	SCHED_NORMAL, SCHED_BATCH	prio >= 100	cfs_rq
5	Idle Scheduler	SCHED_IDLE		rq->idle

구조체

• struct rq
  • rq 구조체는 스케줄링하는 태스트들을 줄세워 관리(enqueue/dequeue)하는 목적으로 사용한다. rq 구조체는 cpu마다 할당되어 있으며 태스크를 연결하는 방식에 따라 cfs_rq, rt_rq, dl_rq 등의 종류가 있다. 각각 CFS, RealTime, DeadLine 스케줄러에서 사용하고, Stop 태스크와 Idle 태스크는 rq->stop, rq->idle에 연결된다.
  • 구조체 내에서 데이터 연결은 Linked List와 Red-Black Tree를 사용한다.
• struct sched_entity
  • sched_entity는 구조체들을 연결하는 역할을 한다.
• struct task_group
  • 지금까지 언급한 구조체들을 그룹으로 묶어서 관리한다. RT와 CFS에서 사용한다.
• struct task_struct
  • 스케줄링하는 대상인 태스크를 만드는 구조체이다.

sched_init()

포인터 메모리 할당

CFS 스케쥴러와 RT 스케쥴러 소스는 컴파일 시점에 선택적으로 조건(#ifdef) 컴파일된다.

ptr에는 CFS 스케쥴러 구조체를 연결하는 포인터들의 크기가 계산된다. CPU 개수인 nr_cpu_ids와 se와 cfs_rq의 타입 크기인 sizeof(void **)를 연산하여 값을 구한다. 이 포인터는 CPU개수별로 생성되기 때문에 nr_cpu_ids를 곱하고, se와 cfs_rq 포인터 변수가 2개이기 때문에 2를 곱한다.

void __init sched_init(void)
{
  unsigned long ptr = 0;
  int i;

  /* Make sure the linker didn't screw up */
  BUG_ON(&idle_sched_class != &fair_sched_class + 1 ||
         &fair_sched_class != &rt_sched_class + 1 ||
         &rt_sched_class   != &dl_sched_class + 1);
#ifdef CONFIG_SMP
  BUG_ON(&dl_sched_class != &stop_sched_class + 1);
#endif

  wait_bit_init();

#ifdef CONFIG_FAIR_GROUP_SCHED
  ptr += 2 * nr_cpu_ids * sizeof(void **);
#endif
#ifdef CONFIG_RT_GROUP_SCHED
  ptr += 2 * nr_cpu_ids * sizeof(void **);
#endif
  if (ptr) {
    ptr = (unsigned long)kzalloc(ptr, GFP_NOWAIT);

#ifdef CONFIG_FAIR_GROUP_SCHED
    root_task_group.se = (struct sched_entity **)ptr;
    ptr += nr_cpu_ids * sizeof(void **);

    root_task_group.cfs_rq = (struct cfs_rq **)ptr;
    ptr += nr_cpu_ids * sizeof(void **);

    root_task_group.shares = ROOT_TASK_GROUP_LOAD;
    init_cfs_bandwidth(&root_task_group.cfs_bandwidth, NULL);
#endif /* CONFIG_FAIR_GROUP_SCHED */
#ifdef CONFIG_RT_GROUP_SCHED
    root_task_group.rt_se = (struct sched_rt_entity **)ptr;
    ptr += nr_cpu_ids * sizeof(void **);

    root_task_group.rt_rq = (struct rt_rq **)ptr;
    ptr += nr_cpu_ids * sizeof(void **);

#endif /* CONFIG_RT_GROUP_SCHED */
  }
    ...
}

---

schedule 실행 과정

1. 어떤 함수를 선점(preempt)해야 하는지 판단
   • preempt 선택을 위한 config 상수
     • none: 필요할 때 schedule 호출
     • voluntary: preempt_enable, might_sleep에서 schedule
     • preempt: ISR이 종료되는 시점에서 schedule
2. scheduler_tick()
   • 약 10ms의 tick_period 주기로 실행, task_tick() 함수들 실행
   • task_tick_fair(): 현재 실행중인 CFS 태스크(curr)를 전달 받아서, 이 태스트가 ideal_runtime만큼 실행되었는지 점검, 더 많이 실행되었다면 resched_curr 함수에서 _TIF_NEED_RESCHED 플래그를 세팅하여 다른 태스트를 스케줄링할 수 있도록 함
   • task_tick_rt():

---

참고

• https://josefbacik.github.io/kernel/scheduler/2017/07/14/scheduler-basics.html