리눅스 커널 스케줄러(Scheduler)

리눅스 커널 책보고 자료찾아보면서 이해한대로 정리해본 것.
참고로 CFS 기법은 kernel 2.6.23 부터 추가되었다고 함.

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 는 부모의 우선순위를 이어받는다.