안녕하세요.

저는 이번에 ARM 커널 스터디 A 팀에 참여하고 있는 이동표라고 합니다.

스케줄링 관련해서 여기저기 찾아본 내용과 제 생각을 덧붙여서 이해한 바를 좀 적어보았습니다.

brainstorming 형식으로 적었으니 혹시 틀린 부분이 있다면 고수님들의 훈훈한 지적을 부탁드립니다. ^^

1. 스케줄러는 kernel thread 같이 별도의 thread 나 process 가 존재하는 것이 아니라 

   kernel 의 스케줄링 알고리즘이 적용되어 있는 component(커널함수)를 말한다.

   몇 가지의 조건이 만족되면 그 때 schedule() 함수가 호출되는데 이 때 스케줄링 관련한

   모든 처리가 이루어진다.

2. CFS 기법은 비실시간 정책인 SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE 에만 사용되며 (Red-Black Tree 이용)

    실시간 정책인 SCHED_RR 과 SCHED_FIFO 는 비트맵 우선순위 배열 기법을 이용한다.

    CFS 스케줄러가 나오기 전 O(1) 스케줄러에서는 실시간/비실시간 모든 정책이 비트맵 우선순위 기법을 이용하였다.

3. 스케줄링 방식에 따라 각각 다른 함수를 사용하는데 이는 sched_class 에 공통 function pointer 로 구현되어 있다.

   즉, enqueue_task, dequeue_task, yield_task 등의 함수가 실시간/비실시간 스케줄러별로 다르게 등록될 수 있으나

   인터페이스는 같게 사용하기 위한 것이다.

    struct sched_class {

        ...

        void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);

        void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);

        void (*yield_task) (struct rq *rq);

        ...

    };

4. runqueue 는 CPU 마다 하나씩 존재하며 struct rq 자료구조를 사용한다.

    이러한 runqueue 에는 CFS 기법을 위한, 즉 비실시간 정책들을 위한 cfs_rq 자료구조와

    실시간 정책들을 위한 rt_rq 자료구조가 포함된다.

    실시간 스케줄링의 경우는 priority 가 0~99 이므로 rt_rq 에는 100 개의 비트맵 배열이 존재한다.

    실시간 스케줄링에서는 스케줄링 시마다 비트맵 배열에서 우선순위가 높은 놈을 선택하여 스케줄링한다.

    실시간 스케줄링에서는 항상 고정 우선순위를 가지므로(nice 에 의해 변경불가), 항상 우선순위가 높은 것이 먼저 수행되는 것이 

    보장되는 것이다.

5. task 에 대한 스케줄링 정책 및 priority 는 사용자에 의해 변경될 수 있다. (아래 함수 또는 nice, renice 명령어)

   nice() , setpriority() , sched_setscheduler(), sched_setparam, pthread_setschedparam 와 같은 

   다양한 함수들이 제공된다.

   즉, 만약 사용자가 프로그램에서 위의 함수들을 통해 자신의 정책과 우선순위를 변경하였다면

   그 즉시 자신의 task 가 지정한 priority list 의 앞쪽에 매달리게 된다. (POSIX 버전에 따라 뒤에 달리는 경우도 있는 듯)

6. task  마다  task_struct 에 priority 와 policy 관련 필드를 가진다.

   ㅇ priority 관련 필드

      - prio : 동적우선순위로 실행 중 스케줄러에 의해 바뀔 수 있는 값. 보통은 static_prio 와 같은 값

      - static_prio : 정적우선순위로 프로세스 실행 시 정해짐 - task 의 time slice 를 결정

      - normal_prio : 혹시 prio 가 변경될 경우 원래 값 보관용

      - rt_priority : realtime task 에서만 사용 (0~99)

   ㅇ policy 관련 필드

      - policy : 실시간(SCHED_RR, SCHED_FIFO), 비실시간(SCHED_NORMAL-예전에는 SCHED_OTHER, SCHED_BATCH, SCHED_IDLE)

7. priority 가 왜 0 ~ 139 까지일까 ?

   sched.h 에 다음과 같이 정의되어 있다.

   #define  MAX_USER_RT_PRIO   100

   #define  MAX_RT_PRIO        MAX_USER_RT_PRIO

   #define  MAX_PRIO           (MAX_RT_PRIO  +  40) // 140

   #define  DEFAULT_PRIO       (MAX_RT_PRIO  +  20) // 120

   #define  NICE_TO_PRIO(nice) (MAX_RT_PRIO  +  (nice)  +  20)  // 100 + nice 값 + 20

   실시간을 위한 값이 100(0~99)으로 고정되어 있고, Priority 의 최대값은 거기에서 40 을 더한 값(140)으로 고정되어 있다.

   즉, 실시간과 비실시간을 모두 합쳐서 140 이 최대값이다.

   위에서 NICE_TO_PRIO 매크로를 보면 nice 값을 통해 priority 값을 계산할 수 있다.

   사용자가 변경하지 않는한 default nice 값이 0 이기 때문에 비실시간 task 의 default priority 값은 120 이다.

   즉, 우리가 nice 값을 -20 ~ 19 까지 변경할 수 있고, default nice 값은 0 이므로

   비실시간 task 의 priority 의 default 값은 120 이고 최대는 140 인 것이다.

   즉, 아무리 nice 값을 변경해봐야 실시간 스케줄링의 우선순위를 뛰어넘을 수는 없다.

8. SCHED_FIFO 스케줄링 관련

   ㅇ SCHED_FIFO task 가 runnable 이 되면 즉시 현재 running 중인 비실시간 task 를 선점한다.

   ㅇ time slice 개념이 없는 단순한 run queue list 알고리즘을 사용한다.

   ㅇ 우선순위가 높은 다른 task 에 의해 선점된 task 는 자신의 우선순위 용 run queue list 의 

      맨 앞에 매달려 있다가 선점한 task 가 block(sleep 이나 I/O) 상태가 되면 다시 수행한다.

   ㅇ 새로운 SCHED_FIFO task 가 runnable 상태가 되면 자신의 우선순위에 해당하는 list 의 맨끝에 매달린다.

   ㅇ sched_setscheduler(), sched_setparam() 등의 함수를 호출하면 run queue 의 맨앞에 매달리고,

      만약 수행중인 같은 우선순위의 task 가 있다면 이를 선점한다.

      (POSIX 버전에 따라 끝에 달리는 경우도 있는 듯...)

   ㅇ sched_yield() 를 호출하면 queue list 의 맨 끝에 매달린다.

9. SCHED_RR 스케줄링 관련

   ㅇ SCHED_FIFO 에 대한 위의 모든 내용이 거의 동일하지만, 각각의 task 가 자신의 maximum time quantum 만큼만

      실행이 허용된다는 것이 다른 점이다.

   ㅇ time quantum 이 다 되면 queue list 의 맨뒤로 매달린다.

   ㅇ 우선순위가 높은 다른 task 에 의해 선점당했을 경우 해당 task 가 끝난 후 바로 이어서 남은 time quantum 동안 실행된다.

10. pthread_yield 또는 sched_yield 호출 시 O(1) 스케줄링의 경우는 해당 task 가 active queue 에서 

    expire queue 로 이동하고, CFS 스케줄링의 경우에는 RB Tree 의 적당한 위치로 매달린다.

    (yield 호출한다고 wait queue 로 가는 것이 아님)

11. fork 및 thread creation 함수에 의해 자식 task 가 생기면 자식 task 는 부모의 우선순위를 이어받는다.

감사합니다.