Skip to content

Latest commit

 

History

History
116 lines (91 loc) · 4.89 KB

스케줄러 소스 분석.md

File metadata and controls

116 lines (91 loc) · 4.89 KB
Raw

리눅스 커널은 다음과 같이 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():

참고