-
[리눅스 커널] Scheduler - introductionLinux/kernel 2023. 11. 10. 16:31
글의 참고
- https://en.wikipedia.org/wiki/O(1)_scheduler
- http://www.wowotech.net/process_management/scheduler-history.html
- https://www.linuxjournal.com/article/6530
- https://en.wikipedia.org/wiki/O(n)_scheduler
- https://www.kernel.org/doc/mirror/lki-single.html
- https://www.xjx100.cn/news/164325.html?action=onClick
글의 전제
- 밑줄로 작성된 글은 강조 표시를 의미한다.
- 그림 출처는 항시 그림 아래에 표시했다.
- v2.4 스케줄러 부분에서 커널 버전이 v2.4.2 와 v2.4.28 가 혼용되어 있음. v2.4.28 로 모두 바꿀 예정.
글의 내용
- Overview
" 이 글은 커널 v2.4 에 사용되던 scheduler 부터 시작해서 최신 커널에서 사용되는 CFS 스케줄러(v2.6.23 버전에 추가 됨) 까지를 거시적인 관점에서 훑어볼 것이다. 먼저, 용어부터 확실히 할 필요가 있어보인다. `process scheduler` 라는 용어는 레거시 용어다. 즉, 현 시대에서 프로세스는 리소스 단위로 사용된다. 실제, 스케줄링 단위는 `스레드` 다. 예를 들어, 대부분의 OS 에서 프로세스와 스레드를 지원할 경우, 프로세스는 단순히 스레드에게 메모리를 할당해주는 `풀` 개념 정도에 불과하다. 그렇다면, 올바른 표현은 `스레드 스케줄러`가 맞다. 그러나, 어감이 익숙하지 않다. 그러므로, 많은 글 에서 사용중 인 `프로세스 스케줄러`, `스케줄러` 혹은 `태스크 스케줄러` 라는 용어를 사용할 것 이다.
" task scheduler 는 운영 체제에서 굉장히 중요한 파트다. 스케줄러는 각 CPU`s 들에게 task 를 할당함으로써, 시스템을 busy 한 상태로 만드는게 주 목적이다. 그런데, task 를 무작정 CPU 에게 할당하지 않는다. 아래와 같이 여러 가지 조건을 고려해서 스케줄링을 하게 된다.
1. time-sharing process 를 목적으로 할 경우, 반드시 스케줄러는 fair 해야 한다.
2. 응답 속도가 빨라야 한다.
3. 시스템이 throughput 이 높아야 한다.
4. power consumption 이 적어야 한다." 위에 내용을 보면, 각 task 의 요구 사항이 모두 다르기 때문에, 분류가 필요하다. 리눅스에서는 크게 2가지 task 로 나눈다.
1. normal process : 앞에서 언급한 (1), (2), (3) 을 고려한다.
2. real-time process : 빠른 응답성이 가장 중요하다." 그런데, normal process 가 고려해야 하는 조건을 잘보면 3 가지 조건을 서로 상충되기가 상당히 어려워보인다. 즉, 조건들이 서로 충돌한다는 것이다. 예를 들어, (1) 과 (2) 를 부합하는 스케줄링 조건을 찾는 것은 쉽지 않다. 그렇다면, normal process 스케줄링 조건을 어떻게 balancing 해야할까? 다시 쪼개야 한다. 즉, normal process 라는 범위가 너무 큰 것이다. 그러므로, 다시 3개로 쪼갠다.
1. ordinary process : time-sharing process 를 기반으로 동작하는 일반적인 프로세스(특수한 목적으로 생성된 프로세스가 아니다).
2. interactive process : user 와 직접 커뮤니케이션 하기 때문에, 마우스 및 키보드 동작을 기다리는데 많은 시간을 소비한다. 그리고, request 에 대해 빠르게 응답해야 한다. 왜냐면, 응답이 느려질 경우, 유저는 시스템이 느려졌다고 판단하기 때문이다. 예를 들어, command shell, text editor, graphical application 등이 있다.
scheduling delay(스케줄러가 선택이 delay 되는 것을 말함) 에 상당히 민감한 프로세스.
3. batch process : user interaction 이 거의 없고, 주로 background 에서 동작한다. 이 계열의 프로세스들은 종종 스케줄러에게 우선 순위에 대한 패널티를 받는 경향이 있다. 왜냐면, 응답을 빨리 하지 않아도 되기 때문이다. batch process 를 예로 들면, database service 등이 있다." 그렇다면, (4) 번은 고려하지 않는 것인가? 리눅스 초기 버전에서는 전혀 고려하지 않았다. 그러나, arm 이 임베디드 시장을 지배하면서, 파워 관련 프로세스 스케줄링인 EAS(`Energy Aware Strategy`) 라는 스케줄링 알고리즘을 내놓은 상황이다. 그러나, 이 글에서는 다루지 않는다.
" 오케이, 이제 task 를 분류하는 것은 끝났다. 그런데, 우리가 태스크를 분류한 이유는 스케줄링을 편하게 하기 위해서였다. 그렇다면, 이제 남은 것은 각 task 를 어떤 기준으로 분류할 것인가가 남았다. 이 때, 분류 기준을 `factor` 라고 한다. 프로세스 스케줄링에서 중요한 factor 는 크게 2 가지로 나뉜다.
1. priority
2. time-slice" 많은 RTOS 들은 priority 를 기반으로 한다. 그래서, RTOS 의 스케줄러들은 항상 가장 높은 우선 순위의 task 를 실행시킨다. 리눅스 커널 에서도 마찬가지다. 만약, 리눅스 커널이 real-time scheduling 을 사용할 경우, prioirity 를 최우선으로 고려한다. 반면에, ordinary process scheduling 에서는 time-slice 를 어떻게 분배하는지를 최우선으로 고려한다. 만약, time-slice 가 너무 크면, 시스템의 반응성이 굉장히 느려진다. 즉, 버벅거리게 된다. 그렇다면, time-slice 를 작게 할당해야 할까? 작게 할당할 경우, 여러 프로세스가 동시 다발적으로 실행되는 것과 같은 착각을 주므로, 시스템 반응성이 좋아보일 수 있다. 그러나, 빈번하게 발생하는 context switching 때문에 시스템 퍼포먼스를 저하시킬 우려가 있다. 헷갈리면 안된다. `시스템 반응성` 과 `시스템 퍼포먼스` 는 엄연히 다르다. 여기서 시스템 퍼포먼스는 throughput 과 동의어로 보면 된다. 즉, 하나의 작업을 얼마나 빨리 끝내는지를 의미한다. time-slice 가 작을 경우, 여러 프로세스가 동시 다발적으로 실행될 가능성이 크다. 그 결과, 유저 입장에서는 마치 성능이 좋아보인다. 예를 들어, 스마트폰에서 멜론, 구글, 유투브, 카톡등을 동시 다발적으로 실행하는 것과 같다. 그런데, time-slice 가 크면, 여러 프로세스가 동시 다발적으로 실행될 가능성이 적다. 그래서, 마치 멀티 태스킹이 되지 않는 것과 같은 현상을 보게된다.
" 리눅스는 범용 운영체제 이기 때문에, 임베디드 디바이스에서도 동작하고, 데스크톱, 서버 워크스테이션에서도 동작하도록 만들어졌다. 리눅스 커널의 스케줄러는 이 모든 field`s 를 수용할 수 있을까? 이제 하나씩 알아보자.
- In v2.4, O(n) scheduler [참고1 참고2 참고3]
" 리눅스 v2.4 때, 태스크 스케줄러는 어떻게 동작할까? 아래 그림은 v2.4 태스크 스케줄러 동작 과정을 보여준다.
1. process
" 아래의 task_struct 는 v2.4 에서 프로세스를 나타내기 위한 자료 구조다. 이 글의 목적은 CFS 를 이해하기 위한 스케줄링 알고리즘의 흐름을 보는 것이다. 그렇기 때문에, 각 필드에 대한 디테일한 설명은 생략하도록 한다.
// include/linux/sched.h - v2.4.28 struct task_struct { .... volatile long need_resched; .... /* * offset 32 begins here on 32-bit platforms. We keep * all fields in a single cacheline that are needed for * the goodness() loop in schedule(). */ long counter; long nice; unsigned long policy; .... int processor; unsigned long cpus_runnable, cpus_allowed;; /* * (only the 'next' pointer fits into the cacheline, but * that's just fine.) */ struct list_head run_list; .... .... unsigned long rt_priority; .... };" v2.4 에서는 2 가지 종류의 process switching 방식이 존재했다(참고로, v2.4 에서는 non-preemptive kernel 만 존재했다)
1. 프로세스가 특정 리소스(하드웨어)를 기다려야 해서 계속 실행을 이어나 갈 수 없을 경우, 자기 스스로 schedule 함수를 호출해서 process switching 을 트리거한다.
2. time slice 를 모두 소진하거나, 자기 일을 모두 마무리해서 yield 할 경우." 위에서 (2) 번에서 주의할 점이 있다. time slice 를 모두 소진했다고 해서, 즉각적으로 scheduling 이 trigger 되는게 아니다. 흔히, `delayed execution` 이라고 해서 즉각적으로 처리하는것이 아닌, 때가 되면 실행되게 만드는 것이다. 구체적인 방법은 `need_resched` 를 SET 함으로써 `해당 프로세스는 선점 되어야 한다` 라는 것을 알리는 지표가 된다. 그리고, re-scheduling 을 체크하는 코드에 도달하면, 해당 프로세스는 다른 프로세스에 의해서 선점된다. 이렇게, `delayed execution` 을 사용하면, 언제 실행될지를 명확하게 보장할 수는 없지만, 로직 코드를 centralization 할 수 있다는 장점이 있다. 예를 들어, scheduling trigger 가 발생하는 곳마다 즉각적으로 schedule() 함수를 호출하는 것은 코드를 상당히 복잡하게 만든다. 그러나, 거기에 flag 변수 하나만 SET 하는 방식으로 두고, 이후에 로직 코드에서 내용을 처리하면, 로직 코드가 한 곳에 모여있기 때문에 유지 보수 측면에서 관리가 수월해진다.
" `p->nice` 필드는 ordinary process`s static priority 를 의미한다. `NICE_TO_TICKS` 매크로는 process`s static priority 를 time slice 로 컨버팅한다. 여기서 컨버팅의 의미는 process`s static priority 가 12 라고 했을 때, 12 우선 순위에 대응하는 time slice 를 의미한다. 즉, process 는 실행되기 위해서는 time slice 를 할당받아야 하는데, 해당 값은 자신의 우선 순위를 기반으로 할당받는다는 것이다. 그리고, 이 time slice 는 `p->counter` 에 저장된다. time slice 의 단위가 tick 이기 때문에, p->counter 에는 tick 개수가 저장된다. 그리고, time slice(p->counter)는 timer interrupt 가 발생할 때 마다, 1씩 감소한다. 그리고 모든 time slice 를 소진하면, next scheduling cycle 이 시작될 때 까지 기다리게 된다.
" `p->policy` 는 scheduling 을 어떤 방식으로 할지를 결정한다. 예를 들어, v2.4 에서는 3 가지 방식의 scheduling policy 를 지원한다.
1. SCHED_OTHER(for ordinary process)
" 이 정책을 사용하는 프로세스들은 runnable real-time process 가 없을 때만 실행된다. 그리고, 선점이 쉽게 되며 우선 순위가 `nice()` 함수에 의해서 동적으로 변경될 수 있다. goodness 의 범위는 1 ~ 999 까지 할당받는다. 그리고, 이 프로세스들은 `rt_priority` 는 0 으로 설정된다.
2. SCHED_RR , SCHED_FIFO(for real-time process)
(2.1) SCHED_FIFO : FCFS 알고리즘을사용하며, static prioiry 는 0 ~ 99 를 할당받는다. 이 scheduling policy 는 동일한 우선 순위의 프로세스가 있어도 작업을 계속 이어나간다. FIFO 프로세스는 자기보다 우선 순위가 높거나, blocked or exited 될 때, CPU 를 free 한다.
(2.2) SCHED_RR : SCHED_FIFO 와 유사하지만, time slice 를 기반으로 동작한다." 스케줄링 정책과는 별개로 SCHED_YIELD 라는 플래그가 존재한다. 이 플래그는 정책은 아니고, 단지 이 플래그가 설정된 프로세스는 자동으로 CPU 를 반납하는데 절차를 밟게된다.
" 스케줄러가 scheduling 을 할 때, 그냥 아무 CPU 에게 task 를 할당하지 않는다. 스케줄러는 태스크의 특성 및 현재 상태를 파악해서 가장 적합한 CPU 에 할당해야 한다. 이 과정에서 사용되는 변수들이 cpu_runnable, cpus_allowed 가 있다. 태스크의 cpus_allowed 변수는 태스크가 실행될 수 있는 CPU 를 의미한다. cpus_runnable 변수는 특정 스레드가 특정 CPU 에서 실행될 수 있는지 판별할 때, 사용된다. 이 값은 프로세스가 어떠한 CPU 에서도 실행되지 않았다면, 모든 비트가 SET 된다. 만약, 프로세스가 특정 CPU 에서 이미 실행중 이라면, 해당 비트가 SET 된다. 그리고, 나머지 비트는 CLEAR 된다.
// kernel/sched.c - v2.4.28 #ifdef CONFIG_SMP #define can_schedule(p,cpu) \ ((p)->cpus_runnable & (p)->cpus_allowed & (1UL << cpu)) #else" 위에서 볼 수 있다시피, `cpus_runnable` 를 직전 실행되었던 CPU 를 찾는데 사용된다. 왜냐면, cache hit rate 를 증가시키기 위해서다. 그렇다면, cpus_runnable 은 언제 설정될까? schedule() 함수에서 next running process 가 확정되면, 해당 프로세스에게 CPU 를 할당한다. 이 때, task_set_cpu 함수가 호출된다.
// include/linux/sched.h - v2.4.28 static inline void task_set_cpu(struct task_struct *tsk, unsigned int cpu) { tsk->processor = cpu; tsk->cpus_runnable = 1UL << cpu; }2. task structure
" v2.4 에서는 process scheduler 는 굉장히 단순한 방식으로 runnable process 를 manage 한다. scheduler 는 ordinary 건 real-time 이건 상관없이, process 가 runnable 상태라면 `runqueue_head` 라는 global linked list 에 연결시킨다. 여기서 굉장히 큰 문제가 하나있다. O(n) scheduler 는 runqueue 를 global linked list 로 `하나만` 선언한 것이다. 예를 들어보자. 시스템이 실행되면, runqueue 에 많은 프로세스들이 inserted & deleted 되어질 것이다. process 가 forked 되면, new child process 는 runqueue 에 inserted 되기도 하고, process 가 blocked 혹은 exited 되면, runqueue 에서 deleted 될 것이다. 이 과정들이 모두 하나의 runqueue 에서 이루어진다. 심지어, SMP 환경이면, 어떻게 될까? 모든 CPU`s 들이 하나의 runqueue 를 두고 race condition 이 발생하게 된다. 이걸 해결하기 위해 spinlock 을 사용하게 되고, 퍼포먼스는 당연히 안좋아진다.
" v2.4 에서는 global runqueue 외에도 모든 프로세스를 가지고 있는 linked list(프로세스 상태와는 전혀 관련없는) 를 하나 가지고 있다. 아래 init_tasks 는 시스템에 존재하는 모든 프로세스들을 연결하는 linked list 다. 이 리스트는 scheduling cycle 이 끝나고 난뒤, 모든 프로세스를 대상으로 time slice 를 재할당한다(심지어, 여기에는 waiting queue 에서 blocked 되어 있는 프로세스도 포함된다).
// kernel/sched.c - v2.4.2 struct task_struct * init_tasks[NR_CPUS] = {&init_task, };3. static priority & dynamic priority
" 일반적으로, static priority 는 task 고유의 값이다. 이 값은 절대로 변하지 않는다. real-time process`s static priority 같은 경우는, rt_priority 필드가 static priority 를 나타내고, ordinary process`static priority 같은 경우는 (20 - nice) 로 표현된다. 그러나, 스케줄러가 스케줄링 할 때는 static priority 을 사용하지 않는다. 대신, dynamic priority 를 비교해서 어떤 프로세스를 스케줄링할 지를 결정한다. 그렇다면, dynamic priority 는 뭐란 말이냐? dynamic priority 는 말 그대로 `변하는 우선 순위` 를 의미한다. 이 값은 static priority 를 기반으로 산출된다.
" dynamic priority 를 계산할 때, `goodness` 함수를 호출된다. 여기서 2가지 케이스가 존재한다.
1. for real-time, dynamic priority : static priority(p->rt_priority) + 1000
" 굉장히 큰 상수값을 더해서 극단적으로 우선 순위를 높였다. 위와 같은 방식으로 우선 순위를 결정하는 이유는 real-time process 와 ordinary process 를 우선 순위를 기준으로 명확히 구별하기 위해서다. 즉, real-time process 가 ordinary process 보다 먼저 스케줄링되게 만든다.
2. for ordinary, dynamic priority
" ordinary process 의 dynamic priority 를 할당받는 과정은 2 단계로 나뉜다.
(2.1) 만약, 프로세스가 주어진 time slice 를 모두 소진하면, dynamic priority 는 0 이다. 이 말은 현재 프로세스 에게는 CPU 를 점유할 기회는 주어지지 않는다는 것과 같다.
(2.2) 만약, 프로세스가 주어진 time slice 를 모두 소진하지 않았다면, dynamic priority 는 `process 의 남아있는 time slice + static priority` 가 된다. 그런데, 아래 코드를 보면, 이 과정이 `20 - p->nice` 로 나와있다. 왜 이렇게 했을까? nice 값은 작아질 수 록 커지기 때문이다. 그런데, 왜 remaining time slice 가 dynamic priority 를 결정하는 factor 가 될까? 일반적으로, remaining time slice 가 많이 남아있다는 것은 아직 처리해야 할 일이 많음을 의미한다. 그런데, 이런 프로세스들이 늦게 스케줄링이 되버리면 throughput 마저도 제대로 나오지 않게 되는 문제가 있다. 그래서 O(n) scheduler 에서는 remaining time slice 가 클 수록, 더 높은 dynamic prioiry 를 할당하도록 설정했다.// kernel/sched.c - v2.4.2 /* * This is the function that decides how desirable a process is.. * You can weigh different processes against each other depending * on what CPU they've run on lately etc to try to handle cache * and TLB miss penalties. * * Return values: * -1000: never select this * 0: out of time, recalculate counters (but it might still be * selected) * +ve: "goodness" value (the larger, the better) * +1000: realtime process, select this. */ static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm) { int weight; .... /* * Non-RT process - normal case first. */ if (p->policy == SCHED_OTHER) { /* * Give the process a first-approximation goodness value * according to the number of clock-ticks it has left. * * Don't do any other calculations if the time slice is * over.. */ weight = p->counter; if (!weight) goto out; .... weight += 20 - p->nice; goto out; } /* * Realtime process, select the first one on the * runqueue (taking priorities within processes * into account). */ weight = 1000 + p->rt_priority; out: return weight; }" O(n) scheduler 는 dynamic priority 를 기반으로 스케줄링을 하고, 가장 우선 순위가 높은 프로세스를 가장 먼저 실행한다. 예를 들어, ordinary process 를 기준으로, static priority 가 높고(반대로, nice 값은 낮다) remaining time slice 가 많다면, 이 프로세스는 먼저 실행될 가능성이 높다. 그런데, 만약 static priority 는 높은데 remaining time slice 가 작을 경우, statis priority 는 낮은데 remaining time slice 가 많이 남은 프로세스보다 우선 순위가 낮을 수 있다. 만약, static priority 도 낮고 remaining time slice 도 낮다면, 볼 것도 없다. 그러나, 만약에 high static priority 를 갖는 프로세스가 remaining time slice 가 없을 경우, low static priority 프로세스도 스케줄링 될 수 있다. 즉, O(n) scheduler 는 기아 현상을 막기 위해 `if (!weight) goto out;` 코드를 작성해놓는 것이라고 볼 수 있다.
" ordinary process`s dynamic priority 를 계산할 때, remaining time slice 와 static priority 말고도, cache 와 TLB 도 scheduling factor 가 된다. 왜냐면, 퍼포먼스 이슈가 있기 때문이다. 예를 들어, processs A 와 process B 가 있다. 둘의 static priority 와 remaining time slice 는 같고, 현재 CPU 에게 할당되기만을 기다리고 있다. 스케줄러는 이 둘중에 하나에게 CPU 를 할당해야 한다. 그런데, 저번 사이클에 process A 가 CPU 를 할당받았다는 소식을 듣게 되었다. 여기서, 스케줄러가 process A 에게 CPU 를 할당할 경우, cache & TLB hit rate 가 증가할 것이다. 즉, 퍼포먼스가 좋아지는 것이다. 그래서, 이와 같은 경우에도 스케줄러는 process A 의 dynamic priority 를 증가시킨다.
" 하나 더 있다. 만약에 현재 실행 중인 프로세스와 동일한 주소 공간을 공유하는 candidate process 가 있다면, 중요한 scheduling factor 가 된다. 2가지 케이스를 살펴보자.
1. running proess 와 candidate process 가 동일 thread group 에 있을 경우(즉, 2개의 스레드가 같은 프로세스내에 있을 경우)
2. candidate process 가 kernel thread 인 경우. 이전 프로세스(여기서 이전 프로세스는 현재 실행 중인 프로세스가 candidate process 에게 선점되어 이전 프로세스가 된 것을 의미한다) 의 주소 공간을 빌려서 사용하는 경우가 많다." (2) 번째 케이스 같은 경우에 user process 가 시스템 콜을 호출하면, kernel thread 에서 user process 에 스택을 사용하는 경우를 의미한다. kernel thread 에서 스택을 사용하고나서 복귀할 때, 어차피 스택 포인터가 다시 user process 가 실행중이던 코드로 복귀하기 때문에, 메모리를 공유해도 크게 문제는 안된다. 물론, 사용가능한 스택의 양이 얼마 남지 않았다면, 그건 문제가 될 수 있다. 어쨋든, 위의 2개의 케이스 모두 process address space 를 switching 하지 않기 때문에, performance 에 이점이 있다고 볼 수 있다.
4. scheduling timing
" v2.4 에서 scheduling timing 은 어떻게 될까? 이 말은 실제적으로 context switch 가 일어난 시점을 의미하는게 아니다. context switch 를 유발시키는 scheduling trigger point 에 대해서 알아보자.
1. process 가 자발적으로 schedule() 함수를 호출한 경우.
2. timer interrupt 가 발생했을 때, 선점한 프로세스(현재 프로세스)의 time slice 가 0 인 경우
3. process 가 wake-up 한 경우(예를 들어, real-time process 가 wake-up 한 경우). wake-up 된 process 를 runqueue 에 들어가서 scheduling 되기를 기다린다. 이 과정은 뒤에서 좀 더 자세히 설명한다.
4. 부모 프로세스가 fork() 함수를 호출하면, 자식 프로세스가 생성된다. 그런데, 이 때 부모 프로세스의 time slice 는 반으로 쪼개져서 부모와 자식이 반반 나눠갖는다. 그런데, 부모 프로세스에게 남은 tick 이 0 일 경우, 자식에게 주게 되어있다. 그렇면, 부모 프로세스의 time slice 는 0 이 되게 된다. 그런데, 부모 프로세스의 time slice 가 0 이 되었다고 즉각적으로 need_resched 를 SET 시키는 것은 아니다. 그렇다면, 어떻게 need_resched 를 SET 할까? 타이머 인터럽트를 기다린다. 즉, 이 이후에 need_resched 가 SET 되는 과정은 (2) 과정으로 넘어간다.
그런데, 만약 부모 프로세스의 time slice 가 1 이 아니라면, 부모와 자식 모두 time slice 가 0 이 아니게 되고, 이 시나리오는 (3) 과정과 유사하게 흘러간다. 왜냐하면, 이 시나리오도 그렇고, (3) 번도 그렇고, 프로세스들이 모두 runqueue 에 들어가서 scheduling 되기를 기다리기 때문이다.
5. CPU[0] 에서 process A 가 실행중이다. 이 때, CPU[0] 에서 context switch 가 발생하면, 예를 들어 process A 가 process B 로 switching 되면, process A 는 더 이상 실행될 기회가 없는걸까? 그렇지 않다. CPU[0] 에서만 process A 가 process B 에게 밀린 것이지 다른 CPU`s 에서는 어떻게 될지 모른다. 예를 들어, CPU[1] 에서 실행중 인 process C 가 process A 보다 우선 순위가 낮다면, 선점될 수 있다. 그리고, CPU[2] 가 만약에 idle 상태라면, process A 는 CPU[2] 에게 할당될 수 있다. 즉, context switch 가 발생했다는 것은 근 미래에 또 다른 context switch 가 발생할 수 있음을 알리는 것과 같다.
6. user process 가 자발적으로 CPU 를 포기한 경우.
7. user process 가 scheduling parameter`s 를 변경한 경우." 위에 케이스들중에서 (1) 번 같은 경우는 자기 스스로 schedule() 함수를 호출해서 context switching 을 직접적으로 발생시킨 경우다. 나머지 케이스들에서는 직접적으로 schedule() 함수를 호출하지 않는다(`6` 번과 같은 경우는 의아할 수 도 있다. 그러나, SCHED_YIELD 플래그만 설정하고, 실제 scheduling 은 나중에 한다). 단지, scheduling trigger 를 발생시킬 수 있는 hint(need_resched 등)를 SET 하고 scheduling trigger point 가 발생하기를 기다린다. v2.4 같은 경우는 preemptive kernel 이 아니었기 때문에, scheduling point trigger point 는 항상 user space 로 복귀하는 시점에 이루어졌다. 예를 들어, 유저 스페이스에서 시스템 콜을 호출하거나 혹은 인터럽트가 발생할 수 있다. 이 때, 해당 작업들이 끝나면, 유저 스페이스로 복귀해야 한다. 바로 이 때, need_resched 를 검사한다는 것이다.
5. process wake-up processing
" 프로세스가 wake-up 하면(`try_to_wake_up`), 해당 프로세스는 a global run-queue 에 추가된다. 런큐에 들어갔으니 바로 실행되는 걸까? 당연히 그렇지 않다. 스케줄러에게 선택이 되어야 비로소 실행된다. 이 과저을 한 번 디테일하게 알아보자. 먼저, wake-up 을 수행하는 프로세스를 waker 라고 정의하고, awakened 된 process 를 wakee 라고 하자. wake-up 은 2 종류가 존재한다.
1. sync wakeup : waker 는 wakee 를 wake-up 시키고 나서, 자신이 곧 sleep state 에 들어갈 것을 알고 있는 경우를 의미한다. 이런 상황에서는 waker 가 근 미래에 자발적으로 schedule() 함수를 호출할 것이기 때문에, try_to_wake_up 함수를 호출하는 시점에 waker 를 preemption 하지 않는 것이 좋다. 그리고, waker 와 wakee 는 동기화 측면에서 서로 공유하는 리소스를 가지고 있다. 즉, 서로 간에 affinity 가 존재한다는 뜻이다. 예를 들어, A 가 공유 리소스인 R 에 대한 lock 을 갖고 있는 상황에서, B 가 R 에 대한 액세스를 요청하면 blocked 상태가 된다. 그리고, 나중에 A 가 R 을 모두 사용하면, R 을 unlock 하고, B 를 wake-up 한다. 여기서 A 와 B 는 R 이라는 공유 리소스 때문에, 서로 간에 affinity 가 존재하게 된다. 이 말은 SMP 환경에서 waker 와 wakee 가 동일한 CPU 에서 실행되면, 종종 performance 측면에서 더 좋은 성능을 내는 경우가 많았다는 뜻이다. 그러나, 만약 try_to_wake_up 함수가 실행되는 과정에서 wakee 가 스케줄링되면, 다른 CPU 에게 할당될 확률이 높다. 바로 여기서, sync wakeup 을 통해서 불필요한 CPU boncing 을 피할 수 있다. 즉, sync wakeup 의 목적은 cache hit rate 를 높이기 위해서, 즉, 동일 CPU 에서 (waker 에서 wakee 로) `동기화(synchronized)` 시키겠다는 것이다.
The sync wakeup differs that the waker knows that it will schedule away soon, so while the target thread will be woken up, it will not be migrated to another CPU - ie. the two threads are ‘synchronized’ with each other. This can prevent needless bouncing between CPUs.
- 참고 : https://www.kernel.org/doc/html/v4.13/driver-api/basics.html
2. non-sync wakeup : 이 케이스는 waker 와 wakee 가 위와 같은 관계(공유 리소스를 공유하는 관계)를 형성하지 않은 경우라고 볼 수 있다. 즉, 서로 전혀 affine 하지 않는 것이다. 이와 같은 경우에는 waker 가 wakee 를 깨운 뒤, 각자 알아서 독립적인 노선을 타게된다. 그래서, waker 는 wakee 를 깨운 뒤, 서로 독립적인 동작이 보장되므로, (waker 는) wakee 를 schedule 하도록 할 수 있다." 위에서 보면 sync wakeup 은 schedule 을 하지 않는 것처럼 보인다. 결론적으로, 그렇지 않다. 예를 들어, waker 가 wakee 를 CPU[0] 에서 wake-up 시켰다. 그런데, wakee 의 cpus_allowed 에 CPU[0] 이 없을 경우, sync wakeup 이건 non-sync wakeup 이건 상관없이, 이 시점에는 schedule 을 해야 한다(reschedule_idle() 함수를 호출한다). 이런 경우에는, waker 와 wakee 가 sync wakeup 이여도 서로 다른 CPU`s 에서 실행된다.
// kernel/sched.c - v2.4.2 /* * This is ugly, but reschedule_idle() is very timing-critical. * We are called with the runqueue spinlock held and we must * not claim the tasklist_lock. */ static FASTCALL(void reschedule_idle(struct task_struct * p)); static void reschedule_idle(struct task_struct * p) { #ifdef CONFIG_SMP .... tsk = target_tsk; if (tsk) { .... tsk->need_resched = 1; if (tsk->processor != this_cpu) smp_send_reschedule(tsk->processor); } return; #else /* UP */ int this_cpu = smp_processor_id(); struct task_struct *tsk; tsk = cpu_curr(this_cpu); if (preemption_goodness(tsk, p, this_cpu) > 1) tsk->need_resched = 1; #endif }" UP 환경에서는 어떨지를 살펴보자. 이 환경에서는 CPU 가 하나이기 때문에, waker 와 wakee 모두 동일 CPU 에서 실행된다. 이 때, CPU 를 누가 선점하냐에 대한 기준은 waker 와 wakee 의 dynamic priority 에 달려있다. 만약, wakee 의 dynamic priority 가 waker 보다 높다면, waker 의 need_resched 플래그를 SET 한다.
" SMP 환경에서는 다수의 CPU 가 존재하기 때문에, waker 와 wakee 는 서로 CPU 점유에 관해서 경쟁할 필요가 없다. 왜냐면, wakee 입장에서는 그냥 다른 CPU 를 선택하면 되기 때문이다. 물론, 막 고르면 안된다. 선택 기준은 아래의 절차를 통해서 결정된다.
1. wakee 가 바로 직전에 실행되었던 CPU 가 idle state 라면, 해당 CPU 에 스케줄링 하는 것이 좋다(cache hit rate 때문에). 그렇지 않다면, 즉, 직전에 실행되었던 CPU 가 idle state 가 아니라면, 가장 적합한 idle CPU 를 찾아야 한다. 여기서 가장 적합하다는 뜻은 가장 최근에 idle state 로 진입한 CPU 를 의미한다.
2. 그런데, 모든 CPU`s 에서 태스크가 실행중 이라면, 즉, idle CPU 가 없다면, 각 CPU`s 에서 현재 실행중 인 태스크들의 dynamic priority 를 비교한다. 그리고, 이 중에서 가장 낮은 dynamic priority 를 갖는 CPU 를 선택한다. 예를 들어, CPU 가 4개 라면, 4개의 CPU 에서 현재 기준으로 실행중 인 프로세스들의 dynamic priority 를 비교해서, 이 중에서 가장 낮은 우선 순위를 갖는 CPU 를 선택하는 것이다.
3. 그런데, 위에서 선택된 가장 낮은 태스크의 dynamic priority 가 wakee 보다 높으면 어떻게 할까? 이럴 경우, wakee 는 scheduling 되지 않는다. 이제는 runqeueu 에 짱박혀서 스케줄러에게 선택되기만을 기다리는 방법뿐이다. 그런데, 만약 높다면? wakee 의 need_resched 플래그를 SET 한다. 이 때, 선점당하는 태스크가 waker 가 아니라면, IPI(smp_send_reschedule()) 를 통해서 CPU 를 선점한다.6. core scheduling algorithm
" v2.4 의 알고리즘은 굉장히 단순하다. 핵심 함수인 schedule() 는 다음과 같다(참고로, v2.4 에서는 `goto` 문이 상당히 많이 사용되고 있다. `goto 문을 왜 사용하지 말라고 할까?` 와 같은 질문을 가지고 있는 사람은 v2.4.2 schedule() 함수를 분석해보자).
// kernel/sched.c - v2.4.2 /* * 'schedule()' is the scheduler function. It's a very simple and nice * scheduler: it's not perfect, but certainly works for most things. * * The goto is "interesting". * * NOTE!! Task 0 is the 'idle' task, which gets called when no other * tasks can run. It can not be killed, and it cannot sleep. The 'state' * information in task[0] is never used. */ asmlinkage void schedule(void) { .... prev = current; .... /* move an exhausted RR process to be last.. */ if (prev->policy == SCHED_RR) goto move_rr_last; .... move_rr_back: .... prev->need_resched = 0; .... repeat_schedule: .... c = -1000; .... list_for_each(tmp, &runqueue_head) { p = list_entry(tmp, struct task_struct, run_list); if (can_schedule(p, this_cpu)) { int weight = goodness(p, this_cpu, prev->active_mm); if (weight > c) c = weight, next = p; } } .... /* Do we need to re-calculate counters? */ if (!c) goto recalculate; .... /* * This just switches the register state and the * stack. */ switch_to(prev, next, prev); .... recalculate: { struct task_struct *p; .... for_each_task(p) p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice); .... } goto repeat_schedule; .... move_rr_last: if (!prev->counter) { prev->counter = NICE_TO_TICKS(prev->nice); move_last_runqueue(prev); } goto move_rr_back; .... return; }" 먼저 현재 동작중 인 프로세스를 prev 에 저장한다. 즉, 위 코드를 분석할 때, prev 가 현재 동작중 인 프로세스라고 보면 된다. 위 코드에서 core scheduling 코드는 다음과 같다.
" runqueue_head 에 시스템에 존재하는 모든 runnable process 들이 연결되어있다. list_for_each 를 통해서 모든 runnable process 들을 탐색한다. 그리고, goodness() 를 통해서 각 프로세스들의 priority 를 비교하고 있다. 마치, MAX 값을 구하기 위한 알고리즘이라고 보면 된다(`if (weight > c)`). 이 루프가 끝나면, next 에는 스케줄링 될 프로세스가 저장되고, c 에는 해당 프로세스의 priority 가 저장된다. 즉, 가장 우선 순위가 높은 프로세스(next)가 실행되는 것이다. process switching 은 복잡하지 않다. 단지, 레지스터와 스택만 교체하는 작업이다. 이 작업은 switch_to() 함수를 통해서 수행된다.
" 시간 복잡도를 계산해보면, 최악의 경우, 리스트를 끝가지 탐색하게 되므로, O(n) 복잡도를 갖는다. v2.4 scheduler 의 이름이 O(n) scheduler 인 이유가 바로 이것때문이다.
" SCHED_RR 정책을 사용하는 프로세스 같은 경우는, schedule() 함수를 호출할 때는 주의할 점이 있다. 만약, time slice 를 모두 소비하면(`if (!prev->counter)), next runnable process 를 선택하기전에 time slice 를 다시 채워놔야 한다. 그런데, 이 구조가 `goto` 문 때문에 복잡해졌다.
" 그리고, 위에 그림을 보면 SCHED_RR 을 사용하는 프로세스의 time slice 가 0 이 되면, global runqueue 맨 뒤에 추가되는 알 수 있다. 즉, 이 말은 runqueue 에 동일한 SCHED_RR 정책을 사용하고 동일한 우선 순위를 갖는 프로세스가 있다면, 그 놈을 먼저 실행하도록 하는 구조를 갖는다. 왜냐면, 현재 SCHED_RR 프로세스는 runqueue 맨 뒤에 추가되기 때문이다. 한 가지 의아한 점이 있다면, SCHED_RR 프로세스에게 time slice 를 할당하는데, nice 값을 사용하고 있다는 것이다(`NICE_TO_TICKS`)
6. time slice processing
" ordinary process 의 time slice 할당 및 처리 과정에 대해서 알아보자.
1. 각 ordinary process 는 static priority 를 기반으로, default time slice 를 할당받는다. 당연히, static priority 가 클 수록, 할당받는 time slice 도 커진다.
2. ordinary process 의 time slice 는 tick interrupt 가 발생할 때 마다, 감소한다. 물론, 실행중 인 ordinary process 를 기준으로 한다(런큐에 있는 ordinary process 의 time slice 를 감소시키면 안된다). 만약, time slice 를 모두 소진하면, 당연히 CPU 점유권을 반납해야 한다.
3. 런큐에 있는 모든 프로세스들의 time slie 를 모두 소진할 경우, scheduling cycle 이 끝났다는 것을 의미한다. 바로 이 시점에 런큐에 있는 모든 프로세스들에게 새로운 time slice 를 할당한다. 그리고, 다시 새로운 scheduling cycle 을 시작한다." 각 프로세스의 time slice 는 어떤 기준으로 할당하는 것일까? time-sharing scheduling 은 기본적으로 tick 을 기반으로 프로세스의 CPU 점유 시간(time slice)을 계산한다. 그리고, 이 tick 은 주기적으로 발생하는 인터럽트다. 예를 들어, tick 의 주기가 10ms 라고 가정하자. 이 때, 5 번째 tick 이 발생했을 때, 소요된 시간은 ms 일까? 50ms 다. 이렇게, tick 이 주기적으로 발생한다는 특징을 이용해서 시간을 계산할 수 있다. 그렇다면, 프로세스의 CPU 점유 시간도 tick 을 통해서 표현할 수 있을 것이다. 프로세스의 time slice 단위를 tick 으로 설정하고, 1 tick 은 가장 작은 time slice 로 설정할 수 있다. 이 말은 우선 순위가 가장 낮은 프로세스의 default time slice 는 `1 tick` 이라는 것을 의미한다(이 때, nice 값은 19 에 대응된다). 만약, 중간 우선 순위(nice == 0)를 갖는 프로세스는 default time slice 로 50ms 를 갖는다. nice 를 tick 을 변환하는 방법은 NICE_TO_TICKS 매크로를 참고하자. 그런데, NICE_TO_TICKS 매크로는 HZ 값에 크게 의존하고 있어서, HZ 값에 따라 결과값이 달라진다. 이게 말이 되는걸까? 프로세스의 우선 순위가 HZ 에 영향을 받는 것이다. 아래의 표를 보자(HZ=100 인 경우, tick 주기는 `10ms` 다. HZ=1000 인 경우, tick 주기는 `1ms` 다).
-20 -10 0 10 19 HZ=100 11 ticks (110ms) 8 ticks (80ms) 6 ticks (60ms) 3 ticks (30ms) 1 ticks (10ms) HZ=1000 81 ticks (81ms) 61 ticks (61ms) 41 ticks (41ms) 21 ticks (21ms) 3 ticks (3ms) " 런큐에 있는 모든 프로세스가 time slice 를 모두 소진하면, 모든 프로세스들의 time slice 를 자신에게 설정된 default time slice 로 재할당해준다고 했다. 코드는 다음과 같다(대략적인 프로세스는 아래 그림에서 설명해놓았다). v2.4 scheduler 는 이와 같이 time slice 재할당을 반복하면서, 스케줄링을 끊임없이 이어나간다.
" time slice 를 재할당하는 부분을 좀 더 구체적으로 설명하자면, for_each_task 매크로는 프로세스가 runnable 이건 아니건 상관없이, 시스템에 존재하는 모든 프로세스를 탐색한다.
// include/linux/sched.h - v2.4.2 #define for_each_task(p) \ for (p = &init_task ; (p = p->next_task) != &init_task ; )// kernel/sched.c - v2.4.2 /* * Init task must be ok at boot for the ix86 as we will check its signals * via the SMP irq return path. */ struct task_struct * init_tasks[NR_CPUS] = {&init_task, };" 이게 재미있는 부분이다. time slice 를 재할당 기준은 런큐의 모든 프로세스가 time slice 를 소진한 경우라고 했다. 그러면, 런큐에 있는 프로세스들에게만 time slice 를 재할당해야 하는 거 아닐까? 여기서 프로세스를 2가지로 분류해보자.
1. ordinary process :
" 런큐에 연결되어 있는 프로세스들 같은 경우는, p->counter 가 0 이라는 것이 확정이다. 그렇기 때문에, 새롭게 할당받는 time slice 는 NICE_TO_TICKS(p->nice) 가 된다.
2. sleeping process
" block-queue 에서 잠자고 있는 프로세스들 같은 경우는, time slice 가 남아있을 것이다. 지금 구조라면, 이런 프로세스들 에게도 time slice 를 추가해주는 꼴이된다. 왜 이런 구조를 만들었을까? 여기서 I/O bound process 를다시 떠올려보자. 자주 잠에 빠진다는 것은 I/O bound process 일 확률이 높고, I/O bound process 는 주로 사용자와 인터렉션한다. 이런 친구들에게는 좀 더 많은 time slice 를 할당해줘야 한다. 그러나, 너무 많은 time slice 를 할당하는 것은 다른 이슈를 만들 수 있기 때문에, 현재 자신이 가지고 있는 time slice 의 절반(`p->count >> 1`)과 own`s default time slice 를 더해서 재할당한다." 그렇다면, 할당받은 time slice 는 언제 감소하는 것일까? update_process_times() 함수는 timer interrupt(tick) 가 발생할 때 마다, 호출되는 함수다. 아래 코드를 보면, tick 이 발생할 때 마다 p->counter 가 1씩 감소하고 있고, 0 이 되면 p->need_resched 를 SET 해서 선점 대상이 되도록 설정한다.
// kernel/timer.c - v2.4.2 /* * Called from the timer interrupt handler to charge one tick to the current * process. user_tick is 1 if the tick is user time, 0 for system. */ void update_process_times(int user_tick) { .... if (p->pid) { if (--p->counter <= 0) { p->counter = 0; p->need_resched = 1; } .... } .... }- In v2.6, O(1) scheduler
1. Why is O(1) scheduler needed ?
" 만약, 스케줄러의 성능 판단을 `심플함` 으로만 판단하면, O(n) 은 의심의 여지가 없이 1등이다. 구조가 단순하니 이해하기도 상당히 쉽다. 그러나, 이 메커니즘은 확장성 및 퍼포먼스 측면에서 굉장히 큰 문제를 가지고 있다. 그리고, O(n) 스케줄러는 7 개의 아주 큰 문제를 가지고 있었다. 이러한 문제 때문에 Ingo Molar's 가 O(1) 스케줄러를 만들었다. 먼저, O(n) 스케줄러의 7 개의 문제에 대해 알아보자.
1.1 time complexiy issue
" 런큐를 전체 탐색한다는 것 자체가 좋지 않다. 시스템에 runnable process 가 적을때는 오버헤드가 크지 않다. 그래서 나름 나쁘지 않다고 생각된다. 그런데, runnable process 가 많아 질수록, 스케줄러가 next runnable process 선택하는데, 계산양이 선형적으로 증가한다. 이 스케줄러의 이름이 O(n) 인 이유가 바로 이것이다.
" 게다가, O(n) scheduler 에서는 런큐에 있는 모든 프로세스의 time slice 가 0 일 경우, re-calculating 과정을 통해 time slice 를 재할당하는 과정이있다. 그런데, 이 과정에서 시스템에 존재하는 모든 프로세스에게 액세스 하다보니 동기화에 드는 비용이 어마무시하게 된다(blocked process 뿐만 아니라, 현재 실행중 인 프로세스까지 time slice 를 수정하기 때문에 동기화 작업이 필요하다).
1.2 SMP scalability issue
" O(n) 스케줄러는 SMP 에 상당히 취약한 구조를 가지고 있다. O(n) 스케줄러는 스케줄링을 기다리는 모든 프로세스를 `하나의` linked list 로 관리한다. 즉, 런큐가 하나인게 문제다. 예를 들어, 다음에 프로세스를 선택하기 위해 스케줄링이 필요할 때, 런큐를 탐색해야 한다. 그리고, 프로세스를 wakeup 하거나 block 할 때도, 런큐에 프로세스를 추가하거나(wakeup), 제거(block)하는 과정이 수행된다. 또, 동기화 측면에서는 런큐가 하나이다보니 spinlock 가 인터럽트를 비활성화는 필수다. 즉, 런큐에 진입하기전에 spinlock 을 잠그고, 로컬 인터럽트를 비활성화한다. 이건 굉장히 심각한 퍼포먼스 문제를 가져온다. CPU 개수가 적을 때는, spinlock 에 의한 오버헤드를 어느 정도 충당할 수 있다고 쳐도, CPU 개수가 증가하면 spinlock 의 오버헤드를 감당하기가 어려워지고, 런큐에서 어마어마한 bottleneck 현상이 집중될 것 이다.
1.3 cache miss issue
" O(n) scheduler 에서 런큐에 들어있는 모든 프로세스들이 자신에게 할당된 time slice 를 모두 소진할 경우, re-scheduling 을 위해서 시스템에 존재하는 모든 프로세스를 대상으로 time slice 를 재할당하는 것을 확인할 수 있었다. 그런데, 이 방식은 흠.. 정말 별로다. 왜냐면, 시스템에 존재하는 모든 프로세스들을 대상으로 한다는 것은 사실 굉장히 무식해 보이는 방식이다. 그리고, 또 time slice re-calculating 작업은 CPU 의 L1 캐쉬를 엉망으로 만든다. 프로세스마다 사용하는 메모리가 모두 다른데, 모든 프로세스의 p->counter 에 접근하는 것은 L1 캐쉬의 데이터를 엉망으로 만들기 충분하다.
1.4 task bouncing issue
" 엄밀히 말해서, 프로세스가 특정 CPU 에게 할당되면, 선점되지 않고 한 번에 작업을 끝내는 것이 가장 좋다. 왜냐면, L1 cache 를 hot 상태를 유지할 수 있기 때문이다. 그래서, 스케줄러는 일반적으로 프로세스를 스케줄링할 때, 현재 CPU 에서 실행되었던 마지막 프로세스를 할당하려는 경향이 있다. 예를 들어, CPU[0] 에서 마지막으로 실행되었던 프로세스가 `A` 라면, A 를 CPU[0] 에게 할당하려고 한다. 그러나, O(n) 스케줄러는 시간이 지남에 따라, process 와 CPU 와의 affinity 를 고려하지 못하고 막무가내로 스케줄링 하는 경우가 많았다.
1.5 real-time performance issue
" O(n) scheduler 에서 ordinary process 와 real-time process 모두 하나의 linked list 에 연결되었다. 이것 때문에, real-time process 를 스케줄링 해야할 때, linked list 에 있는 모든 프로세스를 탐색해야 했다. 일반적으로, real-time process 와 ordinary process 는 서로 다른 scheduling domain 에 존재해야 한다. 그러나, O(n) scheduler 에서는 real-time process 를 선택하기 위해서 런큐에 있는 모든 ordinary process 들까지도 탐색하고 비교해야 한다. 이건 좋지 못한 알고리즘이다.
" 그러나, 위에서 언급 이슈가 real-time performance issue 의 핵심적인 이슈는 아니다. 가장 중요한 performance issue 는 v2.4 에서 리눅스 커널은 preemption 을 지원하지 않았다는 것이다. non-preemptive kernel 에서는 system call 혹은 interrupt 처리 중간에, schedule() 함수를 직접적으로 호출하지 않는 이상 user space 로 return 하는 것은 절대로 불가능하다.
" 그리고, preemption 말고도 또 다른 문제가 있다. 바로, `priority inversion` 문제다. priority inversion 이 발생할 경우, real-time process 는 자신보다 우선 순위가 낮은 process 가 작업을 끝마치기를 기다릴 수 밖에 없다. 예를 들어, H(높은 우선 순위) 와 L(낮은 우선 순위) 태스크가 있다. 여기에, 공유 리소스인 R 까지 추가하자. H 가 공유 리소스 R 을 얻으려고 하는데, L 이 먼저 R 에 대한 lock 을 잠그고 있어서, H 가 blocked 되었다. H의 blocked 상태는 L 이 R 을 unlock 할 때 까지, 지속될 것이다. 그런데, 이 때, 중간 우선 순위를 갖는 M 이 등장했다. 그런데, M 은 L 보다 우선 순위가 높기 때문에, L 을 선점해버렸다(M 은 R 에 의존하지 않는다). 결국, L 이 R 을 unlock 하지 못하게 되므로, H 는 계속 blocked 상태로 남게된다.
Consider two tasks H and L, of high and low priority respectively, either of which can acquire exclusive use of a shared resource R. If H attempts to acquire R after L has acquired it, then H becomes blocked until L relinquishes the resource. Sharing an exclusive-use resource (R in this case) in a well-designed system typically involves L relinquishing R promptly so that H (a higher-priority task) does not stay blocked for excessive periods of time. Despite good design, however, it is possible that a third task M of medium priority becomes runnable during L's use of R. At this point, M being higher in priority than L, preempts L (since M does not depend on R), causing L to not be able to relinquish R promptly, in turn causing H—the highest-priority process—to be unable to run (that is, H suffers unexpected blockage indirectly caused by lower-priority tasks like M).
- 참고 : https://en.wikipedia.org/wiki/Priority_inversion1.6 scheduling delay problem of interactive ordinary process
" O(n) scheduler 는 interactive process 와 batch process 에 차이를 두지 않는다. 단지, 자주 sleep 에 빠지는 process 들에게 더 많은 time slice 를 할당한다. 그러나, 일부 batch process 들은 I/O bound process 다. 예를 들어, database service process 는 일반적으로 background process 이며, scheduling delay 에 예민하지 않다. 그러나, 하드 디스크와 통신해야 하기 때문에, 종종 blocked 이 되곤한다. O(n) scheduler 는 이와 같은 경우에 batch process 에게 더 많은 time slice 를 할당하게 된다. 사실, 이와 같이 동적으로 background proces 의 dynamic priority 를 증가시키는 것은 의미가 없다. 왜냐면, 이 결과로 다른 interactive process 의 scheduling delay 만 증가시키는 결과만 초래하기 때문이다. 또한, interactive process 도 CPU bound 성향을 가질 수 있다. 이런 경우, O(n) scheduler 는 interactive process 의 우선 순위를 낮춰서 적은 time slice 를 할당할 수 도 있다.
1.7 time slice granularity issue
" system load 가 높다는 것은, 런큐의 프로세스 개수가 많다는 것을 의미하고, 이것은 scheduling cycle 이 길어진다는 것을 의미한다. 예를 들어, HZ=100 이고, 런큐에 5개의 프로세스만 있다고 가정하자. 그리고, 이 프로세스들의 nice 값은 모두 0 이다. 그렇면, 각 프로세스들의 time slice 는 60ms 가 된다. 결국, scheduling cycle 은 모두 더한 300ms 가 될 것이다. runnable process 가 많아지는만큼, scheduling cycle 은 더 길어질 것이다. 그런데, 이 많은 프로세스들 중에서 하나의 process 가 time slice 를 모두 소진했다고 치자. 이 process 가 다시 scheduling 될 방법은 next scheduling cycle 을 기다리는 방법밖에 없다. 왜냐면, O(n) scheduler 는 런큐에 있는 모든 프로세스의 time slice 가 0 일 때만, time slice 을 re-calculating 하고 re-scheduling cycle 을 시작하기 때문이다. 결국, scheduling cycle 이 길어질 수 록, system reponse 가 더 안좋아진다고 볼 수 있다.
2. software structure of O(1) scheduler [참고1]
" 아래 그림은 O(1) scheduler 의 소프트웨어 구조를 보여준다.
" O(n) 스케줄러에서는 `global run-queue` 1개 만 존재했다. 이건 SMP 를 전혀 고려하지 않은 구조다. 그래서, O(1) 스케줄러는 Per-CPU 런큐를 도입했다. 그런데 문제가 있다. 런큐가 여러 개다 보니 태스크들이 어떤 런큐에 들어갈지를 고민하기 시작했다. 이 문제를 해결하기 위해 `load balancing` 모듈이 등장했다. 즉, 태스크들을 각 CPU(런큐) 들에게 배치하는 역할을 load balance 모듈이 하는 것이다. 이제 태스크가 runnable 상태가 되면, load balacing 모듈을 거쳐서 적합한 CPU 에게 배치되는 구조가 만들어졌다. 그리고, CPU 에서 어떤 태스크가 실행 될 지는 main scheduler 와 tick scheduler 를 통해서 결정된다.
" per-CPU run-queue 를 도입하면서, O(1) scheduler 는 global run-queue`s spinlock 을 제거할 수 있게됬다. 그리고 global run-queue 에 적용되던 global spinlock 을 각 Per-CPU 로 distribute 함으로써, scheduling delay 를 줄일 수 있게 됬다.
" Per-CPU 를 도입했는데도, spinlock 을 계속 사용해야할까? runqueue 에 액세스하는 process 가 scheduling 과정중에 선점당할 경우에, 다른 CPU 에서 실행될 확률이 있다. 이걸 막기 위한 가장 저렴한 비용은 lock 을 소유하는 것이다. Per-CPU 를 사용하기 때문에, 인터럽트는 막지 않아도 될 것같다. 그러나, 반드시 lock 을 가지고 있어야 한다. 그래야, 인터럽트 or 시스템 콜이 발생하고 하더라도, 복귀 시 lock 을 소유한 이전 프로세스로 복귀할 수 있다.
" O(1) scheduler 는 global access 를 Per-CPU access 로 전환함으로써, 동기화 관련 오버헤드를 많이 감소시켰다. 이렇게 global resource 를 Per-CPU resource 로 나누는 방식은 커널에서 자주 사용되는 방식이다(물론, 메모리 관련 trade-off 가 존재한다). 위와 같이 global 을 Per-CPU 단위로 쪼갬으로써, SMP scalability issue 와 CPU idie issue 가 해결되었다. 게다가, load balancing 모듈에서도 더욱 강력해진 알고리즘이 추가되면서, task boncing issue 또한 해결되었다.
3. run-queue structure of O(1) scheduler
" O(1) scheduler 의 가장 핵심적인 부분은 기존에 있었던 single priority linked list 를 multiple priority linked list 로 바꾸는데 있다. 즉, priority 마다 linked list 가 존재하기 때문에, priority 를 기준으로 독립적인(병렬) 실행이 가능해졌다.
" O(1) scheduler 는 효과적인 process management 를 위해 새로운 run-qeueu 자료 구조를 도입했다. 바로, `prio_array` 자료 구조다. prio_array 는 리눅스 커널에서 사용하는 140 개의 priority 개수에 맞춰서 140 개의 linked list 를 지원한다. 그리고, 태스크를 빠르게 searching 하기 위해 비트맵을 통해 각 priority linked list 가 empty 인지 여부를 체크한다. 거기다, 비트맵마저 탐색할 필요없게 만드는 nr_active 를 사용함으로써(nr_active == 0 이면, 탐색을 아예 할 필요가 없음. 물론 뒤에서 보겠지만, active <-> expired 를 swtiching 하는데 사용), next runnable process 를 searching 하는데 드는 비용을 완전 최적화했다.
" nr_active 는 얼마나 많은 taks`s 들이 현재 run-queue 에 있는지를 나타낸다. ordinary process 들의 priories 범위는 100 ~ 139 이며, 나머지 priories 들은 모두 real-time process 들에게 할당된다. 이걸 통해 알 수 있는 것은 O(1) scheduler 에서, RT process 들과 ordinary process 들은 명확하게 구분될 수 있기 때문에, ordinary process scheduling 절차가 rea-time process scheduling 절차에 영향을 주지 않는다.
// include/linux/sched.h - v2.6.16 #define MAX_USER_RT_PRIO 100 #define MAX_RT_PRIO MAX_USER_RT_PRIO #define MAX_PRIO (MAX_RT_PRIO + 40) ....// kernel/sched.c - v2.6.16 /* * These are the runqueue data structures: */ #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long)) // for 32bit -> 5, for 64bit -> 3 struct prio_array { unsigned int nr_active; unsigned long bitmap[BITMAP_SIZE]; struct list_head queue[MAX_PRIO]; };" O(1) scheduler 의 run-queue 는 2개의 priority queue(struct prio_array) 를 갖는다. 그리고, 런큐에는 각 priority queue(active, expired) 를 가리키는 priority queue potiner 가 각각 존재한다.
1. active queue : time slice 가 남아있는 프로세스들이 모여있음.
2. expired queue : time slice 가 모두 소진된 프로세스들이 모여있음." 시스템이 실행됨에 따라, active queue 에 있는 태스크들 또한 실행된다. 이 때, time slice 를 모두 소진하면 expired queue 로 들어가게 된다. 이러한 과정이 반복되면, expired queue 에는 프로세스들이 점점 증가하고, 어느 시점이 되면 active queue 가 비게(empty) 되는 시점이 온다. 바로 이 때, active queue 와 expired queue 를 교체한다. 그리고, 다시 scheduling process 를 시작한다.
4. Core scheduling algorithm
" O(1) scheduler 에서 next running process 를 선정하는 방법은 심플하다.
// kernel/sched.c - v2.6.16 /* * schedule() is the main scheduler function. */ asmlinkage void __sched schedule(void) { .... array = rq->active; .... idx = sched_find_first_bit(array->bitmap); queue = array->queue + idx; next = list_entry(queue->next, task_t, run_list); .... }" 위에서 볼 수 있다시피, next running process 를 select 하는데 있어서, linked list(active priority queue) 를 전혀 탐색하지 않는다. 단지, active bitmap 만 탐색한다. 심지어, 비트맵 탐색은 for 문을 3 ~ 5번 정도만 돈다. 즉, 상수로 수렴한다. 결국, O(1) 알고리즘이라고 말할 수 있다. 이렇게 빠른 퍼포먼스를 낼 수 있는 이유는 active prioirty queue 만 찾으면 되기 때문이다. 다시 말하지만, O(1) scheduler 에서는 active priority queue 는 탐색하지 않는다.
" 아래 코드는 32-bit arm 에서 active priority queue 를 찾는 코드다. 즉, 비트맵을 탐색해서 active priority queue 를 찾는다. priority 가 140 까지만 존재하기 때문에, 32 비트 기준으로 for 문을 4번만 탐색한다. 그렇면, 128개의 비트를 검색하게 된다. 마지막 12개는 검사 않하나? 만약, for 문이 off 가 4 가 되서 종료되었으면, active prioirty queue 0 ~ 127 까지는 비어있다는 뜻이다. __ffs 는 인자로 받은 정수에서 제일 먼저 SET 된 비트 번호를 반환한다. 당연히, 낮은 비트부터 먼저 탐색한다(x86_64 같은 경우는 64비트이기 때문에 훨씬 심플하다).
// include/asm-arm/bitops.h - v6.5 /* * Find first bit set in a 168-bit bitmap, where the first * 128 bits are unlikely to be set. */ static inline int sched_find_first_bit(const unsigned long *b) { unsigned long v; unsigned int off; for (off = 0; v = b[off], off < 4; off++) { if (unlikely(v)) break; } return __ffs(v) + off * 32; }" 오케이, next running process 를 select 하는 알고리즘은 이해했다. 그런데, 아직 active queue 와 expired queue 를 교체하는 부분을 보지 못했다.
// kernel/sched.c - v2.6.16 /* * schedule() is the main scheduler function. */ asmlinkage void __sched schedule(void) { .... array = rq->active; if (unlikely(!array->nr_active)) { /* * Switch the active and expired arrays. */ .... rq->active = rq->expired; rq->expired = array; array = rq->active; .... } .... }" 너무 심플하다. 현재 runqueue`s active priority queue 의 runnable process 가 없을 경우(`!array->nr_active`), 일을 끝마치지 못한 프로세스를 다시 재활용한다(rq->active = rq->expired). 개인적으로 이런 발상은 굉장히 아름답다. 왜냐면, 동기화 관점에서보면 critical-section 섹션의 사이즈를 굉장히 축소시켜서 find-grained 하기 좋게 만들었고, 퍼포먼스 측면에서는 대량의 프로세스를 단순 포인터 연산 3번 만으로 다시 스케줄링을 할 수 있게 만들었기 때문이다. 정말 멋지다고 생각된다. 참고로, 이와 비슷한 메커니즘으로 RCU 의 `Publish-Subscribe` 메커니즘도 있다.
5. static priority & dynamic priority
" 이전 섹션에서 priority queue 를 다루면서 priority 에 대해 전혀 언급하지 않았다. 그래서, 이 섹션에서는 priority 에 대해 논하도록 한다. 사실, O(1) scheduler 에서 사용하는 priority queue 의 우선 순위는 dynamic priority 다. 이러한 관점에서 O(1) 과 O(n) 은 모두 dynamic priority 를 기반의 스케줄링 알고리즘이다.
" real-time process 같은 경우, rt_priority 멤버 변수에 1(lowest priority) ~ 99(highest priority) 가 저장된다. ordinary process 같은 경우는 static_prio 멤버 변수에 static priority 가 저장된다. 이 값에 범위는 100(highest prioiry) ~ 139(lowest priority) 가 되고, nice 값으로 치면 각각 -20 ~ 19 에 대응한다. dynamic priority 같은 경우는 `prio` 멤버 변수에 저장된다.
// include/linux/sched.h - v2.6.16 struct task_struct { .... int prio, static_prio; .... unsigned long rt_priority; .... };" 실제 스케줄링에서는 dynamic prioirity 가 사용되기 때문에, dynamic priority 는 monotonic 한 특성이 보장되어야 한다. 이게 무슨 말인고 하니, static priority 는 프로세스의 우선 순위에 있어서 monotonicity 를 유지하지 못한다. 예를 들어, real-time process 의 가장 높은 static priority 는 99 고, ordinary process 이 가장 높은 static priority 는 100 이다. 즉, real-time 에서 static priority 는 monotonically 하게 증가하지만, ordinary process 에서 static priority 는 monotonically 하게 감소한다. 이 문제를 해결하기 위해 real-time process 의 dynamic priority 를 계산할 때, 아래와 같은 계산이 수행된다.
p->prio = MAX_USER_RT_PRIO(100) - 1 - p->rt_priority;
" 위와 같은 과정을 통해서 real-time process 의 dynamic priority 또한 monotonically 하게 감소하게 한다. 그렇다면, ordinary process 의 dynamic priority 는 어떻게 구할까? 사실, 이 과정은 굉장히 복잡하다. ordinary process 의 dynamic priority 를 도출해 내려면, average sleep time 을 고려해야 한다. 구체적인 내용은 `effective_prio` 함수를 참고하도록 하자. 결론적으로, ordinary process 의 dynamic priority 는 기존 ordinary process 의 static priority 와 동일하게 100(highest priority) ~ 139(lowest priority) 범위를 갖는다.
" 사실, O(n) 과 O(1) 의 scheduling 메커니즘은 기본적으로 동일하다. 2개 모두 static priority 와 user interaction 을 고려해서 dynamic priority 를 산출해낸다. 이 때, user interaction 이 높으면 dynamic priority 도 증가하고, 반대의 경우에는 낮춘다. 그러나, O(n) 에서는 sleeping process 의 remaining time slice 만 고려해서 dynamic priority 를 구했다면, O(1) 같은 경우는 average sleep time 을 고려해서 dynamic priority 를 산출한다. 이 결과 O(1) scheduler 가 훨씬 우수한 퍼포먼스를 나타낸다.
6. time slice processing
" default time slice 는 `task_timeslice` 함수를 통해서 결정된다. O(1) scheduler 에서 default time slice 는 HZ 와는 전혀 관련이 없다. HZ 값이 뭐가되든, static priority 값이 [-20 ... 0 ... 19] 면, ordinary process 의 default time slice 는 [800ms ... 100ms ... 5ms] 다(priority 를 tick 으로 변환하는 방법은 SCALE_PRIO 매크로를 참고하자). 아래에서 볼 수 있다시피, NICE_TO_PRIO 는 인자로 전달받은 nice 값을 static priority 로 변경한다. 그 범위는 아래에서 보여주듯 100(MAX_RT_PRIO) ~ 139(MAX_PRIO-1) 다.
// kernel/sched.c - v6.5 /* * Convert user-nice values [ -20 ... 0 ... 19 ] * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ], * and back. */ #define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20) .... /* * These are the 'tuning knobs' of the scheduler: * * Minimum timeslice is 5 msecs (or 1 jiffy, whichever is larger), * default timeslice is 100 msecs, maximum timeslice is 800 msecs. * Timeslices get refilled after they expire. */ #define MIN_TIMESLICE max(5 * HZ / 1000, 1) #define DEF_TIMESLICE (100 * HZ / 1000) ...." 위에서 `HZ` 는 1초에 발생한 tick 의 횟수다. 그렇다면, `HZ / 1000` 은 1msec 에 발생한 tick 의 횟수가 된다. 여기에 5 를 곱하면 5msec 동안 발생한 tick 횟수, 100 을 곱하면, 100msec 동안 발생한 tick 의 횟수가 된다. 이 말은 DEF_TIMESLICE 에는 100msec 동안 발생한 tick 횟수가 저장되게 된다는 것이다.
" task_timeslice 함수는 태스크를 전달받아서 우선 순위에 따라 time slice 를 다르게 할당하는 함수다.
// kernel/sched.c - v6.5 /* * task_timeslice() scales user-nice values [ -20 ... 0 ... 19 ] * to time slice values: [800ms ... 100ms ... 5ms] * * The higher a thread's priority, the bigger timeslices * it gets during one round of execution. But even the lowest * priority thread gets MIN_TIMESLICE worth of execution time. */ #define SCALE_PRIO(x, prio) \ max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE) static unsigned int task_timeslice(task_t *p) { if (p->static_prio < NICE_TO_PRIO(0)) return SCALE_PRIO(DEF_TIMESLICE*4, p->static_prio); else return SCALE_PRIO(DEF_TIMESLICE, p->static_prio); }" tick interrupt 가 발생할 때 마다, 현재 task 의 time slice 를 감소시킨다(`--p->time_slice`). time_slice 가 0 이 되면, task 는 active priority queue 에서 제거되고 resched flag 를 표시하고, time slice 를 reset 한다.
// kernel/sched.c - v2.6.16 /* * This function gets called by the timer code, with HZ frequency. * We call it with interrupts disabled. * * It also gets called by the fork code, when changing the parent's * timeslices. */ void scheduler_tick(void) { .... if (!--p->time_slice) { dequeue_task(p, rq->active); set_tsk_need_resched(p); .... p->time_slice = task_timeslice(p); .... } .... }" O(1) scheduler 같은 경우는 각 태스트가 time slice 를 모두 소진하면 즉각적으로 time slice 를 재할당한다. 그리고, 보다시피 태스크들을 모았다가 한 번에 시간을 재할당하는 O(n) scheduler 에서 하던 방식이 없다. 즉, O(1) scheduler 에서는 O(n) scheduler 에서 이슈였던, `한 번에 time slice 처리`, `나중에 time slice 재할당` 하는 2 가지 이슈를 해결했다.
6. how to identify user interactive process
" O(1) scheduler 에서 태스크가 time slice 를 모두 소진하면, expired priority queue 로 들어간다. 만약, 이 태스크를 다시 스케줄링하고 싶다면, active queue 와 expired queue 과 switching 할 때 까지 기다리면 된다. 그러나, 항상 예외라는 것은 존재하기 마련이다.
// kernel/sched.c - V2.6.16 /* * This function gets called by the timer code, with HZ frequency. * We call it with interrupts disabled. * * It also gets called by the fork code, when changing the parent's * timeslices. */ void scheduler_tick(void) { .... if (!--p->time_slice) { .... if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) { enqueue_task(p, rq->expired); if (p->static_prio < rq->best_expired_prio) rq->best_expired_prio = p->static_prio; } else enqueue_task(p, rq->active); } .... }" 위에 보면, TASK_INTERACTIVE 라는 매크로가 보인다. 이 매크로는 태스크가 user-interactive process 인지를 판별한다(참고로, TASK_INTERACTIVE 는 sleep 과 관련이 있다. 왜냐하면, user-interactive proess 는 주로 sleep 에 있는 경우가 많기 때문이다. 그래서, TASK_INTERACTIVE 는 dynamic priority 를 계산하는데 사용될 뿐만 아니라, 이 플래그 설정된 프로세스는 active queue 로 다시 연결될 수 있도록 한다). 만약, 태스크에 TASK_INTERACTIVE 플래그가 SET 되어있으면, 해당 프로세스는 user response 에 대해 민감하다는 것을 의미한다. 그렇다면, 이 프로세스는 expired queue 가 아닌 다시 active queue 로 들어가게 된다. 이런 내용을 보면, O(1) scheduler 는 상당히 user-interactive process 를 편애하는 것 같다. 그런데 만약에, O(1) scheduler 가 user-interactive process 를 너무 편애한 나머지 CPU 점유율을 몽땅 할당할 경우, expired queue 에서 next scheduling 을 기다리고 있는 다른 프로세스들은 어떻게 되는걸까? 그래서, expired queue 의 hunger process 를 나태내기 위해서 `EXPIRED_STARVING` 매크로를 사용한다. 만약, 프로세스가 expired queue 에 너무 오래동안 있으면, 스케줄러가 해당 상황을 인지하게 된다. 그래서, 가능한 빨리 scheduling cycle 을 끝내고 active queue 와 expired queue 를 switching 하기 위해, 비록 time slice 를 모두 소진한 프로세스가 user-interactive process 라도 expired queue 에 저장한다.
7. preemptive kernel [참고1]
" v2.5.4 전까지는 리눅스 커널에 preemptive 가 적용되지 않았다. 이 말은 non-preemptive kernel 에서 프로세스가 만약 커널 레벨에서 동작한다면, 자기 스스로 프로세서 점유를 포기하거나 I/O 를 기다려야 하는 경우에만 context switch 가 발생한다. 이러한 경우가 아니라면, 커널 레벨에서도 동작하는 프로세스를 선점할 수 있는 방법은 존재하지 않는다. 유저 레벨 프로세스는 할당받은 time slice 를 모두 소진하면, CPU 를 회수했다. 즉, 유저 프로세스는 선점을 했다.
" 그리고, non-preemptive kernel 을 사용할 때는 리눅스가 서버 시장에서 한창 떠오를려고 하던 시기였다. 그러다 보니, 리눅스 애플리케이션은 전부 서버 시장을 target 으로 개발되고, non-preemptive kernel 을 사용하더라도 크게 이상할 건 없었다. 그러나, 리눅스가 데스크탑과 임베디드 시장으로 공략하기 시작하면서, user interaction 이 증가했고, non-preemptive kernel 이다 보니 시스템 응답성이 느릴 수 밖에 없었다. 그래서, v2.5 개발 과정에서 리눅스는 preemptive kernel(CONFIG_PREEMPT) 을 도입했다. 이 컨피그의 가장 큰 특징은 새로운 태스크가 실행되기 위해서, 이제 더 이상 user space 로 복귀하는 시점까지 기다릴 필요가 없다는 것이다. 기존의 non-preemptive kernel 은 user space 로 복귀하는 시점에만 scheduling trigger point 를 검사했었다. CONFIG_PREEMPT 는 모든 커널 코드를 preemptible 하게 만들어서, user interactive event 에 대해 low latency 로 반응할 수 있게 해준다. 심지어, 시스템이 부하 상태에 있을 때도, 유저 애플리케이션에게 CPU 제어권이 넘어갈 수 있기 때문에 user experience 가 좋아진다. 대신에, throughput 이 약간 감소하고, context switch 가 자주 발생할 수 있기 때문에 runtime overhead 가 증가하게 된다[참고1].
'Linux > kernel' 카테고리의 다른 글
[리눅스 커널] Synchronization - tranditional locking (0) 2023.11.17 [리눅스 커널] Interrupt - ARMv7 interrupt handling process (0) 2023.11.14 [리눅스 커널] Interrupt - IRQ domain (0) 2023.11.07 [리눅스 커널] Kernel command-line parameters (0) 2023.11.06 [리눅스 커널] Performance - CPU optimization basic (0) 2023.11.06