"
그리운 고향집에 이르느니, 집안 동복이 정답게 반기며,
문 옆 어린것이 오셨나고 빙긋 올려다보네! "
도연명의 귀거래사중에서.
cfs 스케쥴러는 문자그대로 " 완전히 공정한 스케쥴러"라는 뜻입니다.
각각의 프로세스(태스크)에게 동일한 가상 time slice(quantum)가 할당됩니다.
보통의 스케쥴러의 구현에서 각 각의 프로세스에게 10ms의 동일한 time slice를 부여하던 방식과 유사합니다.
이 time slice를 vruntime이라고 하는데 , 중요한 점은 가상이라는(v는 virtual) 점입니다.
프로세스 A 와 B가 실행 큐에 삽입 될 때 , 프로세스들의 vruntime은 큐상의 가장 적은 vrutime으로 초기화 됩니다.
설명의 편의를 위해 가상 런타임의 time slice가 20으로 주어 진다고 가정하면,
각 프로세스의 vrutime의 실행시간이 20에 도달하면 태스크 스위칭(스케쥴링)이 발생합니다.
(단 이 상황은 이상적인 상황이고 실제 코드는 , vruntime으로 판단하지 않고 real time slice를 계산해 스케쥴링이
결정됩니다.)
즉 , timer 인터럽트 핸들러 -> vruntime 증가 -> 가상 실행시간의 증가량이 20을 초과하면 ->스케쥴링 수행
식으로 동작합니다.
여기서 중요한 점은 각 프로세스의 vruntime의 수행시간(slice)은 고정 되어 있으나,
실제 real 수행시간, 즉 real time slice는 각 프로세스의 priority에 따라 다른 값을 갖는 점입니다.
이의 구현을 위해 실제 코드 상에서는 프로세스의 priority에 해당하는 배열을 사용합니다.
리눅스의 priority는 nice라는 값으로 표현되고 , -20 ~ 20의 범위를 갖습니다.( 값이 적을수록 더 큰 priority)
간단한 예를 들면 , int piroty[2]={ 200, 100} 이라는 배열을 설정하고,
nice 값이 0일때 200 , 1일때 100이 할당된다고 가정하겠습니다.
그리고 중요한 개념이 스케쥴링 주기(period)라는 값입니다.
이는 이 주기 동안 스케쥴러상의 실행 큐에 대기 중인 프로세스가 모두 실행되는 시간입니다.
간단히 10ms 라고 할 때,
프로세스 A의 실제 실행 시간은 = ( 실행주기) * (A의 priotiry) / ( A's priority + B's priority) 가 됩니다. ----공식 1
프로세스 A의 nice는 0 -> piority[0] = 200 ,, B: 100이 되며
이를 계산하면
프로세스 A의 실제 수행 시간은 10ms *200/ 200+100) = 6.6ms 가 주어지며
B는 3.3ms 가 주어 집니다.
(여기서는 직관적인 이해를 위해 단순화한 공식을 제시합니다. 추후에 실제 코드상으로 정확한 공식을 제시하겠으나,
단순화한 모델도 실제 공식과 동일한 논리와 개념이 적용됩니다.)
즉 스케쥴러 큐에 대기 중인 프로세스의 priority에 따른 비율에 따라 스케쥴링 주기를 나누어 실제 실행시간이
주어지게 됩니다.
check_preempt_tick()라는 함수가 timer interrupt에서 호출 되는데, 이 함수에서 현재 실행되는 프로세스의
time slice가 다 소진되었는지를 계산합니다.
여기서 중요한 점은 각 프로세스의 실제 실행시간인 time slice는 priority에 따라 가변이지만 , 가상실행 시간은 동일한 값이
주어집니다.
이는 간단한 산수로 되는데,
실제 실행시간은 ( 실행주기) * (A의 priotiry) / ( A's priority + B's priority) 이지만
가상실행 시간은 위의 값에 (A의 priority)를 한 번 더 나눠줘서 process dependent부분을 상쇄시켜 줍니다.
즉
A의 vrutime 증가량 = ( 실행주기) * (A의 priotiry) / ( A's priority + B's priority) / (A의 priotiry)= --공식 2
= ( 실행주기)/ ( A's priority + B's priority)
B의 vrutime 증가량 = ( 실행주기) * (B의 priotiry) / ( A's priority + B's priority) /(B의 priotiry)=
= ( 실행주기)/ ( A's priority + B's priority)
가 되어서 각 프로세스의 vruntime은 동일한 값으로 증가하게 됩니다.
이제 실제 커널상의 구현을 살펴 보겠습니다.
static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
}; 이 변수가 프로세스의 priority에 따른 real time slice를 결정하는 배열입니다.
맨 윗줄의 prio_to_weight[0]은 88761 로 priority가 -20으로 가장 높은 nice 우선순위를 갖는 값입니다.
이제 스케쥴러 런 큐에 priority가 다른 세개의 프로세스 a,b,c가 있고, 각각의 nice(priority)가 -20 , -15 , -16이 존재하는
상황을 살펴 보겠습니다. 그리고 실행주기는 10ms입니다.
a의 실제 실행 시간값( real time slice)는
위의 공식에 의존해 10ms * ( 88761 ) / ( 88761 + 29154 + 36291) 가 됩니다.
커널 코드에 보면 , calc_delt_fair( 실제 수행 시간 )의 함수가 실제수행시간 - > 가상 실행시간(vruntime)의 증가량을
계산하는 함수이며 , 계산의 편의를 위해 공식2에서 priority의 역수를 곱해주어서 , 나누기 연산을 회피하는데,
이를 위해 prio_to_weight[]의 역수를 저장하는 배열 prio_to_wmult[]를 사용합니다.
실제 코드는 normalize를 위해서 redundant한 2*32의 값을 곱하는 계산 과정등이 추가 되는데,
이를 무시해도 지금까지 논의한 사항은 정확합니다.
그리고 check_preempt_tick()함수에서 sched_slice()함수를 호출하는데 , 이 함수가 실제 수행된 시간을 계산하는 함수이며,
공식1 을 가지고 계산한 후 , time slice가 초과되면, scheduling이 실행됩니다.
cfs의 스케쥴러는 현재 실행 큐에서 vruntime이 가장 작은 프로세스를 선택합니다.
이를 위해 red-black트리를 사용해 프로세스를 저장하고 선택합니다.
논의의 편의를 위해서 rb tree는 다른 자료를 통해 익숙하다고 가정하겠습니다.
지금은 직관적인 이해를 위해 단순화한 모델로 설명하겠습니다.
시나리오:: 1 .처음에 프로세스 A가 실행큐에 삽입(rb tree에)되고 vruntime은 0 , nice값은 0 의 값을 갖고 있습니다.
prio_to_weight[]의 실제값은 계산이 지저분해서
prit_to_weight[]={300,200,100}으로 단순화해서 계산하겠습니다.
A의 실제실행시간(real time slice)은 공식 1에 의해
= 10ms* 300/300 = 10ms가 되어 전 주기를 혼자 다 독식합니다.
계산의 편의를 위해 vruntime의 timeslice는 20으로 주어진다고 가정하겠습니다.
2 .A의 vruntime이 10인 상황에서 새로운 프로세스 B가 fork등을 통해 실행큐에 삽입되며고 , nice값 1을 갖는 프로세스일 때
B의 vruntime은 실행큐에서 가장 적은 min_vruntime을 갖게 되고 이는 현재 A 한개 뿐이므로
10을 갖습니다.
B 의 실제실행시간(real time slice)은 공식 1에 의해
= 10ms* ( 200)/(300+200) = 4ms가 되고,
A 는 = 10ms* ( 300)/(300+200) = 6ms로 변화됩니다.
timer 인터럽트에서 , A의 vruntime은 증가하고(1증가라고 가정) , check_preempt_tick()가 호출되고 A의 real 실행시간이 6ms가 되는 시점에 스케쥴링이 발생합니다.
이때 a의 vruntime: 11 b의 vruntime:10이 되어 b가 선택됩니다.
이처럼, cfs상에서 실제 time slice는 현재 큐에 대기중인 프로세스의 수와 priority에 따라 가변적으로 결정됩니다.
그리고 vruntime은 큐상에 존재하는 process들 중 가장 작은 값을 , 새로 실행되는 프로세스에게 부여하는 구조를 갖고,
스케쥴러는 가장 작은 vruntime을 갖는 프로세스를 선택합니다.
왜냐하면 , 완전 공정한 스케쥴러이기 때문이며 , 이는 여러분이 여러 시나리오와 코드를 살펴보면 이해할 수 있습니다.
그리운 고향집에 이르느니, 집안 동복이 정답게 반기며,
문 옆 어린것이 오셨나고 빙긋 올려다보네! "
도연명의 귀거래사중에서.
cfs 스케쥴러는 문자그대로 " 완전히 공정한 스케쥴러"라는 뜻입니다.
각각의 프로세스(태스크)에게 동일한 가상 time slice(quantum)가 할당됩니다.
보통의 스케쥴러의 구현에서 각 각의 프로세스에게 10ms의 동일한 time slice를 부여하던 방식과 유사합니다.
이 time slice를 vruntime이라고 하는데 , 중요한 점은 가상이라는(v는 virtual) 점입니다.
프로세스 A 와 B가 실행 큐에 삽입 될 때 , 프로세스들의 vruntime은 큐상의 가장 적은 vrutime으로 초기화 됩니다.
설명의 편의를 위해 가상 런타임의 time slice가 20으로 주어 진다고 가정하면,
각 프로세스의 vrutime의 실행시간이 20에 도달하면 태스크 스위칭(스케쥴링)이 발생합니다.
(단 이 상황은 이상적인 상황이고 실제 코드는 , vruntime으로 판단하지 않고 real time slice를 계산해 스케쥴링이
결정됩니다.)
즉 , timer 인터럽트 핸들러 -> vruntime 증가 -> 가상 실행시간의 증가량이 20을 초과하면 ->스케쥴링 수행
식으로 동작합니다.
여기서 중요한 점은 각 프로세스의 vruntime의 수행시간(slice)은 고정 되어 있으나,
실제 real 수행시간, 즉 real time slice는 각 프로세스의 priority에 따라 다른 값을 갖는 점입니다.
이의 구현을 위해 실제 코드 상에서는 프로세스의 priority에 해당하는 배열을 사용합니다.
리눅스의 priority는 nice라는 값으로 표현되고 , -20 ~ 20의 범위를 갖습니다.( 값이 적을수록 더 큰 priority)
간단한 예를 들면 , int piroty[2]={ 200, 100} 이라는 배열을 설정하고,
nice 값이 0일때 200 , 1일때 100이 할당된다고 가정하겠습니다.
그리고 중요한 개념이 스케쥴링 주기(period)라는 값입니다.
이는 이 주기 동안 스케쥴러상의 실행 큐에 대기 중인 프로세스가 모두 실행되는 시간입니다.
간단히 10ms 라고 할 때,
프로세스 A의 실제 실행 시간은 = ( 실행주기) * (A의 priotiry) / ( A's priority + B's priority) 가 됩니다. ----공식 1
프로세스 A의 nice는 0 -> piority[0] = 200 ,, B: 100이 되며
이를 계산하면
프로세스 A의 실제 수행 시간은 10ms *200/ 200+100) = 6.6ms 가 주어지며
B는 3.3ms 가 주어 집니다.
(여기서는 직관적인 이해를 위해 단순화한 공식을 제시합니다. 추후에 실제 코드상으로 정확한 공식을 제시하겠으나,
단순화한 모델도 실제 공식과 동일한 논리와 개념이 적용됩니다.)
즉 스케쥴러 큐에 대기 중인 프로세스의 priority에 따른 비율에 따라 스케쥴링 주기를 나누어 실제 실행시간이
주어지게 됩니다.
check_preempt_tick()라는 함수가 timer interrupt에서 호출 되는데, 이 함수에서 현재 실행되는 프로세스의
time slice가 다 소진되었는지를 계산합니다.
여기서 중요한 점은 각 프로세스의 실제 실행시간인 time slice는 priority에 따라 가변이지만 , 가상실행 시간은 동일한 값이
주어집니다.
이는 간단한 산수로 되는데,
실제 실행시간은 ( 실행주기) * (A의 priotiry) / ( A's priority + B's priority) 이지만
가상실행 시간은 위의 값에 (A의 priority)를 한 번 더 나눠줘서 process dependent부분을 상쇄시켜 줍니다.
즉
A의 vrutime 증가량 = ( 실행주기) * (A의 priotiry) / ( A's priority + B's priority) / (A의 priotiry)= --공식 2
= ( 실행주기)/ ( A's priority + B's priority)
B의 vrutime 증가량 = ( 실행주기) * (B의 priotiry) / ( A's priority + B's priority) /(B의 priotiry)=
= ( 실행주기)/ ( A's priority + B's priority)
가 되어서 각 프로세스의 vruntime은 동일한 값으로 증가하게 됩니다.
이제 실제 커널상의 구현을 살펴 보겠습니다.
static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
}; 이 변수가 프로세스의 priority에 따른 real time slice를 결정하는 배열입니다.
맨 윗줄의 prio_to_weight[0]은 88761 로 priority가 -20으로 가장 높은 nice 우선순위를 갖는 값입니다.
이제 스케쥴러 런 큐에 priority가 다른 세개의 프로세스 a,b,c가 있고, 각각의 nice(priority)가 -20 , -15 , -16이 존재하는
상황을 살펴 보겠습니다. 그리고 실행주기는 10ms입니다.
a의 실제 실행 시간값( real time slice)는
위의 공식에 의존해 10ms * ( 88761 ) / ( 88761 + 29154 + 36291) 가 됩니다.
커널 코드에 보면 , calc_delt_fair( 실제 수행 시간 )의 함수가 실제수행시간 - > 가상 실행시간(vruntime)의 증가량을
계산하는 함수이며 , 계산의 편의를 위해 공식2에서 priority의 역수를 곱해주어서 , 나누기 연산을 회피하는데,
이를 위해 prio_to_weight[]의 역수를 저장하는 배열 prio_to_wmult[]를 사용합니다.
실제 코드는 normalize를 위해서 redundant한 2*32의 값을 곱하는 계산 과정등이 추가 되는데,
이를 무시해도 지금까지 논의한 사항은 정확합니다.
그리고 check_preempt_tick()함수에서 sched_slice()함수를 호출하는데 , 이 함수가 실제 수행된 시간을 계산하는 함수이며,
공식1 을 가지고 계산한 후 , time slice가 초과되면, scheduling이 실행됩니다.
cfs의 스케쥴러는 현재 실행 큐에서 vruntime이 가장 작은 프로세스를 선택합니다.
이를 위해 red-black트리를 사용해 프로세스를 저장하고 선택합니다.
논의의 편의를 위해서 rb tree는 다른 자료를 통해 익숙하다고 가정하겠습니다.
지금은 직관적인 이해를 위해 단순화한 모델로 설명하겠습니다.
시나리오:: 1 .처음에 프로세스 A가 실행큐에 삽입(rb tree에)되고 vruntime은 0 , nice값은 0 의 값을 갖고 있습니다.
prio_to_weight[]의 실제값은 계산이 지저분해서
prit_to_weight[]={300,200,100}으로 단순화해서 계산하겠습니다.
A의 실제실행시간(real time slice)은 공식 1에 의해
= 10ms* 300/300 = 10ms가 되어 전 주기를 혼자 다 독식합니다.
계산의 편의를 위해 vruntime의 timeslice는 20으로 주어진다고 가정하겠습니다.
2 .A의 vruntime이 10인 상황에서 새로운 프로세스 B가 fork등을 통해 실행큐에 삽입되며고 , nice값 1을 갖는 프로세스일 때
B의 vruntime은 실행큐에서 가장 적은 min_vruntime을 갖게 되고 이는 현재 A 한개 뿐이므로
10을 갖습니다.
B 의 실제실행시간(real time slice)은 공식 1에 의해
= 10ms* ( 200)/(300+200) = 4ms가 되고,
A 는 = 10ms* ( 300)/(300+200) = 6ms로 변화됩니다.
timer 인터럽트에서 , A의 vruntime은 증가하고(1증가라고 가정) , check_preempt_tick()가 호출되고 A의 real 실행시간이 6ms가 되는 시점에 스케쥴링이 발생합니다.
이때 a의 vruntime: 11 b의 vruntime:10이 되어 b가 선택됩니다.
이처럼, cfs상에서 실제 time slice는 현재 큐에 대기중인 프로세스의 수와 priority에 따라 가변적으로 결정됩니다.
그리고 vruntime은 큐상에 존재하는 process들 중 가장 작은 값을 , 새로 실행되는 프로세스에게 부여하는 구조를 갖고,
스케쥴러는 가장 작은 vruntime을 갖는 프로세스를 선택합니다.
왜냐하면 , 완전 공정한 스케쥴러이기 때문이며 , 이는 여러분이 여러 시나리오와 코드를 살펴보면 이해할 수 있습니다.
덧글