1. 정의 및 역사
- 스케줄러는 어떤 프로세스를 어떤 순서로 얼마나 오랫동안 실행할 것인지 정책에 따라 결정한다.
- 스케줄러는 시스템의 최대 사용률을 끌어내 사용자에게 여러 프로세스가 동시에 실행되고 있는 듯한 느낌을 제공해야 한다.
- 스케줄러는 비선점형 스케줄러와 선점형 스케줄러로 나뉜다.
- 선점형 스케줄러는 일정한 timeslice 동안 전적으로 프로세서 자원을 사용할 수 있고, 시간이 지나면 다음으로 우선순위가 높은 프로세스에 선점된다.
- 1991년 리눅스 첫 버전부터 2.4 버전까지는 단순한 스케줄러를 제공했다.
- 2.5 버전부터 대대적인 스케줄러 개선작업을 통해 O(1) 스케줄러라는 이름의 새로운 스케줄러를 구현했다. Timeslice 동적 계산이 O(1)에 수행되며 프로세서마다 별도의 wait queue를 구현해 성능향상을 이뤄냈다.
- 그러나 O(1) 스케줄러는 서버 시스템에는 이상적이었지만, 대화형 서비스를 제공하는 데스크톱 시스템에서는 성능이 안 좋았다. 그래서 2.6.23 버전부터 CFS(Completely Fair Scheduler)라는 새로운 스케줄러를 도입했다.
2. 스케줄러 구성요소
I/O 중심 프로세스 vs 프로세서 중심 프로세스
- I/O 중심 프로세스: I/O 요청 후 기다리는 데 대부분의 시간을 사용하는 프로세스 (i.e. 대부분의 GUI 애플리케이션은 사용자의 키보드, 마우스 입력을 기다림)
- 프로세서 중심 프로세스: 선점될 때까지 대부분의 시간을 코드를 실행하는 데 사용하는 프로세스. 더 긴 시간동안 덜 자주 실행하도록 스케줄링 해야 한다. (i.e. ssh-keygen 등)
스케줄링 정책
- 정책(Policy)은 스케줄러가 무엇을, 언제 실행할 것인지를 정하는 것을 의미한다.
- 정책은 두 가지 목적을 갖고 있다.
- 프로세스 응답시간(latency)을 빠르게 하기
- 시스템 사용률(Throughput)을 최대화 하기
- 정책은 낮은 우선순위 프로세스는 최대한 공정하게, 높은 우선순위 프로세스는 최대한 빠르게 선택해서 실행할 책임이 있다.
우선순위
- 일반적으로 선점형 우선순위 스케줄링은
- 우선순위가 높은 프로세스가 낮은 프로세스를 선점해 먼저 실행하고
- 우선순위가 같은 프로세스 끼리는 round-robin으로 돌아가며 실행한다.
- 리눅스 커널 프로세스 스케줄링은 두 가지 별개의 우선순위 단위를 갖고 있다.
- Nice
- 20~+19 사이의 값을 가지며 값이 클수록 우선순위가 낮다.
- Timeslice의 비율을 조절할 때도 사용된다.
- 실시간 우선순위
- 0~99 사이의 값을 가지며 값이 클수록 우선순위가 크다.
- 모든 real-time(실시간) 프로세스는 일반 프로세스보다 우선순위가 높다.
- Nice
Timeslice
- Timeslice는 선점 당하기 전까지 프로세스가 작업을 얼마나 오랫동안 실행할 수 있는지를 의미한다.
- 너무 길면 대화형 프로세스의 성능이 떨어진다.
- 너무 짧으면 빈번한 context-switching으로 인해 전체 시스템의 성능이 떨어진다.
- CFS는 프로세스별로 timeslice를 설정하지 않고 프로세스별로 프로세서 할당 ‘비율’을 지정한다.
- 그래서 프로세스에 할당되는 CPU time은 시스템의 부하와 nice값에 대한 함수로 O(1)로 결정된다.
- CFS는 모든 프로세스가 공정하게 골고루 실행됨을 보장하기 위해 새 프로세스가 현재 실행 중인 프로세스보다 낮은 비율의 CPU time을 사용했다면, 현재 프로세스를 선점하고 즉시 실행한다.
예시
간단한 예시를 통해 일반적인 스케줄러 정책의 동작과 CFS의 동작을 알아보자.
문서 편집기(A, I/O 중심)와 동영상 인코더(B, 프로세서 중심) 두 가지 프로세스가 있다.
-
일반적으로 A가 더 우선순위가 높고 더 많은 CPU time을 할당한다.
- 작업량이 많아서가 아니라, 필요한 순간에 항상 CPU time을 얻기 위해서
- 사용자가 키보드를 눌러 A가 깨어날 때 B를 선점해야 더 좋은 대화형 성능을 보장할 수 있다.
- B가 실행시간 제약이 없기 때문이다. (지금 실행되든 0.5초 뒤에 실행되는 critical 하지 않음)
-
리눅스의 CFS는 위와 조금 다르게 동작한다.
- A는 일정 비율(B와 같은 nice 값을 가진다면 50%)의 CPU time을 보장받는다.
- A는 사용자 입력을 기다리느라 할당받은 50%의 CPU time을 대부분 사용하지 못한다. 하지만, B는 할당받은 50%의 CPU time을 전부 활용한다.
- 사용자가 키보드를 눌러 A가 깨어날 때, CFS는 A가 아주 적은 CPU time만 사용했다고 알아차린다.
- A가 B보다 CPU time 비율이 적으므로 B를 선점하도록 한 뒤 사용자 입력을 빠르게 처리하고 다시 대기모드로 들어간다. 나머지 시간은 B가 온전히 사용할 수 있다.
3. 리눅스 스케줄링 알고리즘
스케줄러 클래스
- 리눅스 스케줄러는 모듈화 되어있어 각 프로세스를 각기 다른 알고리즘으로 스케줄링 할 수 있다.
- 이러한 형태를 ‘스케줄러 클래스’라고 말하며 각 클래스에는 우선순위가 있다.
<kernel/sched.c>에는 기본 스케줄러가 구현되어있다.- CFS는 리눅스의 일반 프로세스용 스케줄러 클래스이며
<kernel/sched_fair.c>에서 구현되어있다.
UNIX의 프로세스 스케줄링
- 전통적인 유닉스의 프로세스 스케줄링 방법에 대해서 알아보자.
- 앞서 말했듯, 유닉스는 nice 값을 기반으로 우선순위를 결정하고 정해진 timeslice 동안 프로세스를 실행한다. 높은 우선순위 프로세스스는 더 자주 실행되니 더 긴 timeslice를 할당받을 것이다.
- 하지만, 이 방법에는 몇 가지 문제가 있다.
-
Context-switching 최적화가 어렵다.
- Nice에 timeslice를 대응하기 위해 각 nice 값에 할당할 timeslice의 절대값을 정해야 한다. (i.e. nice값 0 = timeslice 100ms, +19 = timeslice 5ms)
- 어떤 두 프로세스가 있다.
- Nice 0인 프로세스 + Nice 19인 프로세스: 전자가 100ms 수행된 뒤 후자가 선점해 5ms를 수행하므로 105ms에 context swtiching이 2회 발생한다.
- Nice 19인 프로세스 2개: 10ms에 context switching이 2회 발생한다.
- Nice 0인 프로세스 2개: 200ms에 context switching이 2회 발생한다.
- 잦은 context switching이 발생하고 우선순위가 낮은 프로세스는 잘 실행되지 않는다.
-
상대적인 nice값 차이로 문제가 발생한다.
- Nice 0인 프로세스는 100ms, Nice 1인 프로세스는 95ms를 할당받는다고 가정하자.
- 두 프로세스의 timeslice 차이는 겨우 5%로, 큰 차이가 없다.
- Nice 18인 프로세스는 10ms, Nice 19인 프로세스는 5ms를 할당받는다고 가정하자.
- 두 프로세스의 timeslice 차이는 무려 50%로 굉장한 차이가 발생한다.
- 즉, ‘nice 값을 1 증가하거나 낮추는 행위’는 기존 nice값에 따라 의미가 달라지게 된다!
-
아키텍처에 의존적이다.
- Nice값에 따라 timeslice의 절대값을 할당하기 위해 시스템 클럭의 일정 배수로 timeslice를 설정해야 한다.
- 시스템의 프로세서 아키텍처에 따라 1-tick은 가변적이므로 timeslice 또한 영향을 받는다.
- 즉, nice값 1 차이가 1ms 차이일 수도, 10ms 차이일 수도 있다는 문제가 있다.
여러 복잡한 문제를 해결할 수 없다.
- 대화형 프로세스의 반응성을 개선하기 위해서는 사용자의 키 입력에 대한 인터럽트 발생 시 바로바로 반응할 수 있도록 우선순위를 높여 sleep-wake 과정 속도를 증가해야 한다.
- 하지만, 한 프로세스만 불공정하게 CPU time을 할당할 수 밖에 없는 방법론적인 허점이 존재한다.
- 이러한 문제는 UNIX의 스케줄링 방법이 선형적이고 단순하기 때문에 발생한다.
공정(Fair) 스케줄링 (CFS)
-
CFS는 wait 중인 n개의 프로세스 각각에 1/n 비율의 CPU time을 할당해 모두 동일한 시간 동안 실행된다.
- CFS는 실행 가능한 전체 프로세스 n개와 nice값에 대한 함수를 이용해 개별 프로세스가 얼마 동안 실행할 수 있는지 동적으로 계산한다. 이때, nice값은 CPU time 비율의 가중치로 사용된다.
- Nice값이 높을수록(우선순위가 낮을수록) 프로세스는 낮은 가중치를 받아 낮은 비율을 할당받는다.
-
목표 응답시간(Targeted Latency): CFS가 설정한 응답시간의 목표치이며, 실행이 완료된 프로세스가 다음 번에 자신의 순서가 돌아오기까지 기다려야 하는 최대 시간을 의미한다.
- 낮을수록 반응성이 좋아져 완전 멀티태스킹에 가까워진다.
- 낮을수록 context switching 비용은 높아져 전체 시스템 성능은 낮아진다.
- 목표 응답시간 20ms인 시스템에
- 우선순위 동일 프로세스 2개 있다면? 각각 20 ÷ 2 = 10ms씩 실행된다.
- 우선순위 동일 프로세스 5개 있다면? 각각 20 ÷ 5 = 4ms씩 실행된다.
- 우선순위 동일 프로세스 20개 있다면? 각각 20 ÷ 20 = 1ms씩 실행된다.
-
최소 세밀도(Minimum Granularity): 각 프로세스에 할당되는 CPU time의 최소값을 의미한다.
- 프로세스 개수가 늘어나면, 각 프로세스에 할당되는 CPU time은 점점 0에 수렴한다.
- Context switching이 전체 수행시간에서 큰 비율을 차지하게 되므로 최소치를 정해놓아야 한다
- 기본값은 1ms다.
-
CFS에선, 오로지 nice값의 상대적인 차이만이 각 프로세스의 timeslice에 영향을 준다.
- 앞서 UNIX 스케줄링의 문제점 1번에서 언급했지만, nice값과 timeslice가 선형관계일 때, context switching이 언제(10ms? 105ms? 200ms?) 발생할지 예측할 수 없다는 문제가 있었다.
- 목표 응답시간 20ms인 시스템에 두 프로세서 A, B가 있을 때,
- A(nice: 0), B(nice: 5) 이라면, A는 15ms, B는 5ms를 할당받는다.
- A(nice: 10), B(nice: 15) 이라면, 똑같이 A는 15ms, B는 5ms를 할당받는다
- Nice값의 절대값이 CFS의 결정에 영향을 미치지 않는것에 집중하자.
-
CFS는 프로세스 개수가 많이 늘어나서 최소 세밀도 이하로 내려갈 경우에는 공정성을 보장하지 못한다.
- 완전히 공정하진 않지만, 각 프로세스에 공정한 CPU time 비율을 나눠준다는 점에서 ‘Fair’하다.
- 최소한 목표 응답시간 n에 대해 n개 프로세스 까지는 공정성을 보장할 수 있다.
4. CFS 구현
시간 기록 (Time Accounting)
-
모든 프로세스 스케줄러는 각 프로세스의 실행시간(the time that a process runs)을 기록해야 한다.
-
시스템 클럭 1-tick이 지날 때마다 이 값은 1씩 감소하며, 0이 될 때 다른 프로세스에 의해 선점된다.
-
각 프로세스(task)의 스케줄러 관련 정보는
task_struct내에sched_entity구조체 타입 se 멤버변수에 저장된다.sched_entity구조체 내부는 아래와 같이 구성되어있다.struct sched_entity {/* For load-balancing: */struct load_weight load;struct rb_node run_node;u64 deadline;u64 min_deadline;struct list_head group_node;unsigned int on_rq;u64 exec_start;u64 sum_exec_runtime;u64 prev_sum_exec_runtime;// 가상실행시간, 프로세스가 실행한 시간을 정규화한 값이며 CFS는 실행 대기 프로세스 중 가상실행시간이 가장 낮은 프로세스를 다음 실행 프로세스로 선택한다.u64 vruntime;...} -
프로세스의 실행시간은
vruntime멤버변수에 저장된다. -
이 변수의 갱신은
kernel/sched_fair.c소스코드 내uptate_curr()함수에서 담당한다.- 이 함수는 시스템 타이머에 의해 주기적으로 호출된다.
- now -
curr->exec_start로 이전에 기록된 시간으로부터 현재 얼마나 지났는지 차이를 계산해 delta_exec에 저장한다. - vruntime을 갱신하기 위해
__update_curr()함수를 호출한다.
-
__update_curr()함수에서는calc_delta_fair()함수를 호출해 현재 실행 중인 프로세스 개수를 고려해 가중치를 계산한 뒤 vruntime을 갱신한다. -
위와 같은 방식으로 vruntime 값은 특정 프로세스의 실행시간을 정확하게 반영한다.
static void update_curr(struct cfs_rq *cfs_rq) { // 현재 함수의 실행시간을 계산에 delta_exec에 저장struct sched_entity *curr = cfs_rq->curr;u64 now = rq_of(cfs_rq)->clock;unsigned long delta_exec;if (unlikely(!curr))return;/** Get the amount of time the current task was running* since the last time we changed load (this cannot* overflow on 32 bits):* 지난번 갱신 시점 이후 현재 작업이 실행된 시간을 구한다. (32bit를 넘을 수 없음)**/delta_exec = (unsigned long)(now - curr->exec_start);if (!delta_exec)return;/** 계산된 실행값을 __update_curr함수에 전달한다,* __update_curr함수는 전체 실행중인 프로세스 갯수를 고려해 가중치를 계산한다.* 이 가중치 값을 추가하여 현재 프로세스의 vruntime에 저장한다.*/__update_curr(cfs_rq, curr, delta_exec);curr->exec_start = now;if (entity_is_task(curr)) {struct task_struct *curtask = task_of(curr);trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);cpuacct_charge(curtask, delta_exec);account_group_exec_runtime(curtask, delta_exec);}}/* 현재 작업의 실행시간 통계를 갱신한다. 해당 스케줄링 클래스에 속하지 않는 작업은 무시한다.* 시스템 타이머를 통해 주기적으로 실행되며, 프로세스가 실행 가능 상태로 바뀌거나 대기상태가 되어 실행이 중단되어도* 호출된다.*/static inline void __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,unsigned long delta_exec){unsigned long delta_exec_weighted;schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));curr->sum_exec_runtime += delta_exec;schedstat_add(cfs_rq, exec_clock, delta_exec);delta_exec_weighted = calc_delta_fair(delta_exec, curr);curr->vruntime += delta_exec_weighted;update_min_vruntime(cfs_rq);}
프로세스 선택
- CFS는 다음번에 실행될 프로세스를 결정할 때 ‘가장 낮은 비율로 CPU time을 실행한’ 프로세스로 결정한다, 즉 가장 낮은 vruntime을 가진 프로세스를 선택한다.
- CFS의 핵심은 매 context switching 시 실행 가능한 프로세스 중 가장 낮은 vruntime을 가진 프로세스를 찾아 선택하는 것이다.
- 빠른 탐색을 위해 self-balancing BST로 유명한 ‘Red-Black Tree’ 자료구조를 사용한다.
- 따라서 다음 작업을 선택할 때는 가장 왼쪽에 있는 node를 선택하면 된다.
/*** CFS가 다음에 실행해야 할 프로세스를 반환하는 함수*/static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq) { struct rb_node *left = cfs_rq->rb_leftmost; # rb_leftmost 캐시된 가장 왼쪽 노드 포인터
if (!left) return NULL;
return rb_entry(left, struct sched_entity, run_node); }스케줄러 진입 위치 (Scheduler Entry Point)
- 스케줄러의 main 함수는
kernel/sched.c에 정의된 void__sched schedule(void)함수다. - 가장 우선순위가 높은 스케줄러 클래스의 가장 우선순위가 높은 프로세스를 찾아 다음 프로세스로 선택한다.
schedule()함수 내부에서pick_next_task()함수를 호출한다.
// https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/sched/core.c#L5983/* * Pick up the highest-prio task: */static inline struct task_struct *__pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf){ const struct sched_class *class; struct task_struct *p;
/* * Optimization: we know that if all tasks are in the fair class we can * call that function directly, but only if the @prev task wasn't of a * higher scheduling class, because otherwise those lose the * opportunity to pull in more work from other CPUs. */ if (likely(!sched_class_above(prev->sched_class, &fair_sched_class) && rq->nr_running == rq->cfs.h_nr_running)) {
p = pick_next_task_fair(rq, prev, rf); if (unlikely(p == RETRY_TASK)) goto restart;
/* Assume the next prioritized class is idle_sched_class */ if (!p) { put_prev_task(rq, prev); p = pick_next_task_idle(rq); }
return p; }
restart: put_prev_task_balance(rq, prev, rf);
for_each_class(class) { p = class->pick_next_task(rq); if (p) return p; }
BUG(); /* The idle class should always have a runnable task. */}- if 문은 최적화를 위한 구문이다.
- 일반적으로 프로세스는 CFS를 스케줄러 클래스로 사용하는 경우가 많다.
- 즉, 현재 실행 중인 프로세스 개수와 CFS 스케줄러 클래스 사용 프로세스 개수가 동일할 가능성이 높다.
- 이런 경우에는 CFS 스케줄러 클래스 내부에 정의된
pick_next_task()함수를 실행하도록 한다. - 이 함수는
kernel/sched_fair.c에pick_next_task_fair()에 정의되어있다. - CFS의
pick_next_task()는pick_next_entity()를 호출하고 이어서__pick_next_entity()를 호출한다. - for 문은 가장 우선순위가 높은 스케줄러 클래스의 가장 우선순위가 높은 프로세스를 찾는다.
- 가장 높은 우선순위부터 돌아가며 스케줄러 클래스 내
pick_next_task()함수를 호출한다.
Sleeping and Waking Up
-
프로세스가 sleep 또는 block 상태로 들어간 데에는 여러 가지 이유가 있지만, 커널 동작은 같다.
- 프로세스는 자신의 state가 ‘대기 상태’(
TASK_(UN)INTERRUPTIBLE)임을 표시한다. - CFS 스케줄러 클래스의 RBTree에서 자기 자신을 제거한다.
schedule()함수를 호출해 새 프로세스를 선택해 실행한다.
- 프로세스는 자신의 state가 ‘대기 상태’(
-
이러한 프로세스들은 ‘Wait Queue(대기열)’에 들어가서 특정 조건이 발생하기를 기다린다.
// https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/include/linux/wait.h#L40struct wait_queue_head { spinlock_t lock; struct list_head head;};typedef struct wait_queue_head wait_queue_head_t;- 대기열은
<linux/wait.h>헤더파일에wait_queue_head_t구조체로 표현한다.- 대기열은
DECLARE_WAITQUEUE()매크로를 이용해 정적으로 만들 수 있다.
- 대기열은
// https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/include/linux/wait.h#L48#define __WAITQUEUE_INITIALIZER(name, tsk) { \ .private = tsk, \ .func = default_wake_function, \ .entry = { NULL, NULL } }
#define DECLARE_WAITQUEUE(name, tsk) \ struct wait_queue_entry name = __WAITQUEUE_INITIALIZER(name, tsk)- 대기열은
init_waitqueue_head()함수를 이용해 동적으로 만들 수도 있다.
// https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/sched/wait.c#L8#define init_waitqueue_head(wq_head) \ do { \ static struct lock_class_key __key; \ \ __init_waitqueue_head((wq_head), #wq_head, &__key); \ } while (0)- [주의] Sleep과 wake는 동일 프로세스에 대한 일종의 경쟁상태(race condition)를 유발할 위험이 있다.
-
특정 단발성 wake 조건을 기다리는 프로세스가 sleep에 들어가기 전에 해당 조건이 발생했다면? 해당 sleep 프로세스는 영원히 wake 할 일이 없을 것이다.
-
따라서 아래와 같은 과정으로 sleep-wake을 처리할 것을 권장한다.
```cadd_wait_queue(q, &wait);while (!condition) {prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE);if (signal_pending(current)) {/* handle signal */}schedule();}finish_wait(&q, &wait);```1. `add_wait_queue()` 를 이용해 프로세스를 대기열에 추가한다.2. `prepare_to_wait()` 함수는 프로세스의 state를 `TASK_INTERRUPTIBLE`로 변경한다.3. `schedule()` 함수는 다른 프로세스가 먼저 실행되도록 해준다.원하는 wake-up 조건이 발생했다면, while-loop를 빠져나와 state를 `TASK_RUNNING`으로 변경하고 `fininsh_wait()` 함수를 호출해 대기열에서 프로세스를 제거한다. -
위와 같은 구조에서는 sleep 전 wake-up condition이 먼저 발생하더라도 기능에만 문제가 생기게 되고, 해당 프로세스가 영원히 sleep 상태에 빠질 위험은 예방할 수 있다.
-
5. Context switching
schedule()함수는 다음에 실행될 프로세스를 결정한 뒤<kernel/sched.c>에 정의된context_switch()함수를 호출한다.context_switch()함수는<asm/mmu_context.h>에 정의된switch_mm_irqs_off()함수를 호출한다. 이 함수는 CPU의 메모리 관련 레지스터를 masking 해서 가상메모리 매핑을 새로운 프로세스로 변경한다.context_switch()함수는<asm/system.h>에 정의된switch_to()함수를 호출한다. 이 함수는 인라인 어셈블리를 이용해서 현재 프로세스의 TCB(Task Control Block)를 저장하고, 다음 프로세스의 TCB를 복원한다.
// https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/sched/core.c#L5320/* * context_switch - switch to the new MM and the new thread's register state. */static __always_inline struct rq *context_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next, struct rq_flags *rf) { prepare_task_switch(rq, prev, next);
/* * For paravirt, this is coupled with an exit in switch_to to * combine the page table reload and the switch backend into * one hypercall. */ arch_start_context_switch(prev);
/* * kernel -> kernel lazy + transfer active * user -> kernel lazy + mmgrab_lazy_tlb() active * * kernel -> user switch + mmdrop_lazy_tlb() active * user -> user switch * * switch_mm_cid() needs to be updated if the barriers provided * by context_switch() are modified. */ if (!next->mm) { // to kernel enter_lazy_tlb(prev->active_mm, next);
next->active_mm = prev->active_mm; if (prev->mm) // from user mmgrab_lazy_tlb(prev->active_mm); else prev->active_mm = NULL; } else { // to user membarrier_switch_mm(rq, prev->active_mm, next->mm); /* * sys_membarrier() requires an smp_mb() between setting * rq->curr / membarrier_switch_mm() and returning to userspace. * * The below provides this either through switch_mm(), or in * case 'prev->active_mm == next->mm' through * finish_task_switch()'s mmdrop(). */ switch_mm_irqs_off(prev->active_mm, next->mm, next); lru_gen_use_mm(next->mm);
if (!prev->mm) { // from kernel /* will mmdrop_lazy_tlb() in finish_task_switch(). */ rq->prev_mm = prev->active_mm; prev->active_mm = NULL; } }
/* switch_mm_cid() requires the memory barriers above. */ switch_mm_cid(rq, prev, next);
prepare_lock_switch(rq, next, rf);
/* Here we just switch the register state and the stack. */ switch_to(prev, next, prev); barrier();
return finish_task_switch(prev);}- 커널은
need_resched플래그를 이용해서 언제 스케줄링이 필요한지 판단한다. - 사용자 공간으로 돌아가거나, 인터럽트 처리를 마칠 때마다 커널은
need_resched플래그를 확인한다. 설정되어있다면schedule()함수를 호출해 최대한 빨리 새 프로세스로 전환한다. need_resched플래그는 각 프로세스의 task_struct 속 thread_info 속 flags 멤버변수에 포함되며TIF_NEED_RESCHED라는 이름으로 선언되어있다.
// https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/include/linux/sched.h#L2261static __always_inline bool need_resched(void) { return unlikely(tif_need_resched());}- need_resched 플래그는 각 프로세스의 task_struct 속 thread_info 속 flags 멤버변수에 포함되며
TIF_NEED_RESCHED라는 이름으로 선언되어있다.
6. 선점
- 리눅스 커널은 2.6 버전 이상부터 사용자 공간 뿐만 아니라, 커널도 선점될 수 있는 ‘완전 선점형’이다.
- 실행 중인 작업이 lock 돼있지 않다면 커널은 언제나 선점될 수 있다.
thread_info구조체에는preemp_count라는 멤버변수가 있다. 이 변수는 프로세스가 lock을 설정 할 때마다 1 증가하고 lock을 해제할 때마다 1 감소한다.- 즉, 해당 프로세스의
preemp_count가 0이면, 해당 프로세스는 선점 가능한 상태라고 판단한다. - 정리하자면, 커널은 need_resched 플래그 활성화 + 현재 프로세스의 preemp_count == 0일 경우 더 우선순위가 높은 프로세스를 찾은 뒤 선점을 허용하고
schedule() -> context_switch()함수를 호출한다.
### 7. 실시간 스케줄링 정책
- 리눅스 커널은 FIFO와 Round-robin 두 가지 실시간 스캐줄링 정책으로 soft 실시간성을 제공한다.
- 실시간 프로세스는 일반 프로세스보다 우선순위가 높아 항상 먼저 실행된다.
- 그러므로, 더 높은 우선순위 실시간 프로세스가 없다면, 양보 없이 무한히 계속 실행될 수도 있다.
- 반면, Round-robin 정책(SCHED_RR)은 정해진
timeslice만큼만 실행된 뒤, 우선순위가 같은 다른 실시간 프로세스를 돌아가며 실행한다. - 리눅스의 실시간 우선순위는
task_struct의rt_priority멤버변수에 저장하며,0 ~ MAX_RT_PRIO-1사이의 값을 가지며, 기본값은 0 ~ 99다.
참고
