Egloos | Log-in
F/OSS study
F/OSS study
[Linux] Completely Fair Scheduler
Linux: 2.6.34


CFS(Completely Fair Scheduler)는 2.6.23 이후로
리눅스의 기본 스케줄러로 사용되고 있는 알고리즘이다.

모든 우선순위 값에 대한 배열을 이용해 run queue를 구현한 기존의 O(1) 스케줄러에 비해
red-black tree를 사용하는 CFS는 기본 성능은 O(log N)으로 느려졌지만
대부분의 경우에서 이는 거의 영향을 주지 않기 때문에
여러 corner case들을 공정하게 처리해주는 CFS가 대신 도입되었다.
real time process의 경우에는 아직도 O(1) 스케줄러가 (약간 변형되어) 사용된다.

CFS의 기본 원리는 이름에서 알 수 있듯이 모든 프로세스를 공평하게 실행하는 것이다.
프로세스 우선순위나 sleep을 통해 자발적으로 CPU를 반환하는 경우를 고려하지 않는다면
CFS가 관리하는 모든 프로세스는 동일한 시간동안 실행하고 CPU를 반환한다.

프로세스의 우선순위를 반영하기 위해 각 프로세스는 (정확히 말하면 sched_entity 구조체는)
load_weight 구조체를 이용하여 자신의 우선순위에 따른 load 값을 저장하고 있다.

sched.h:
struct load_weight {
    unsigned long weight, inv_weight;
};

weight는 load 즉, 우선순위에 대한 가중치이고 inv_weight는 이의 역수(1/weight)에 해당하는 값이다.
weight 값은 nice를 통해 지정할 수 있는 우선순위에 대응하는 값이며 (nice level 0일 때: 1024)
sched.c 파일의 prio_to_weight[] 배열에 저장되어 있다.
참고로 nice (우선순위) 값의 1 차이는 weight 값의 1.25 배 차이이며
이는 프로세스가 CPU를 사용하는 시간에 10% 정도 영향을 준다.

inv_weight 값은 단지 계산을 간편하게 하기 위한 목적으로 도입된 것으로
가중치 계산을 위한 나눗셈을 피하기 위해 미리 정해진 충분히 큰 수(2^32)에 나눗셈을 미리 계산해 둔 값이다.
이도 마찬가지로 sched.c 파일의 prio_to_wmult[] 배열에 저장되어 있다.

이렇게 우선순위에 따른 load를 계산해 두었다면 주어진 값에 대한 자신의 몫을 계산하는 작업은
아래의 calc_delta_mine() 함수를 통해 이루어진다.
(생략한 부분은 inv_weight를 새로 계산하는 부분이다.)

sched.c:
static unsigned long
calc_delta_mine(unsigned long delta_exec, unsigned long weight,
        struct load_weight *lw)
{
    u64 tmp;

    ...

    tmp = (u64)delta_exec * weight;
    /*
     * Check whether we'd overflow the 64-bit multiplication:
     */
    if (unlikely(tmp > WMULT_CONST))
        tmp = SRR(SRR(tmp, WMULT_SHIFT/2) * lw->inv_weight,
            WMULT_SHIFT/2);
    else
        tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);

    return (unsigned long)min(tmp, (u64)(unsigned long)LONG_MAX);
}

먼저 함수의 매개 변수를 살펴보면, delta_exec는 계산하고자 하는 기준값이며
weight는 자신이 차지하는 가중치이고, lw는 전체에 대한 가중치이다.

즉, 기본적인 산수는 (delta_exec * weight / lw->weight)를 계산하고자 함이다.
하지만 (특정 아키텍처에서는 매우 느린) 나눗셈 연산을 피하기 위해 inv_weight를 이용한다.
먼저 tmp가 WMULT_CONST (= 2^32)보다 작은 간단한 경우를 살펴보기로 하자.

기본적으로 inv_weight = (WMULT_CONST / weight)이기 때문에 다음이 성립한다.

tmp * lw->inv_weight = (delta_exec * weight) * (WMULT_CONST / lw->weight)

여기서 WMULT_CONST를 제거하기 위해서는 다시 나눗셈이 필요한데
WMULT_CONST는 2의 제곱이기 때문에 간단히 shift 연산으로 계산이 가능하다.
하지만 shift right 시의 값 버림을 방지하기 위해 미리 반올림을 하는 SRR 매크로로 이용한다.

/*
 * Shift right and round:
 */
#define SRR(x, y) (((x) + (1UL << ((y) - 1))) >> (y))

위의 if 문의 경우에는 SRR 시 shift left에 의해 상위 워드의 정보를 잃어버리지 않기 위해
나눗셈을 두 번에 걸쳐 수행한다.

CFS는 우선순위에 따라 프로세스를 run queue (red-black tree)에 배치하기 위해
가상의 시간인 vruntime을 사용하는데 이는 실제로 프로세스가 실행한 시간에
nice 0에 대한 현재 프로세스의 우선순위 가중치를 역으로(!) 계산한 값이다.
(아래의 calc_delta_mine() 호출 시 se의 load 값이 전달되는 위치에 주목하자.)

static inline unsigned long
calc_delta_fair(unsigned long delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);

    return delta;
}

프로세스의 vruntime 값을 갱신하는 __update_curr() 함수는 다음과 같은 작업을 수행한다.

sched_fair.c:
static inline void
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
          unsigned long delta_exec)
{
    unsigned long delta_exec_weighted;

    ...

    delta_exec_weighted = calc_delta_fair(delta_exec, curr);

    curr->vruntime += delta_exec_weighted;
    update_min_vruntime(cfs_rq);
}

이와 같이 vruntime은 (절대적인) nice 우선순위에 영향을 받기 때문에
우선순위가 낮은 프로세스인 경우 vruntime은 실제보다 더 큰 값을 갖게 되고,
우선순위가 높은 프로세스의 경우 반대로 더 작은 값을 갖게 되어 평준화를 이루게 된다.

CFS의 run queue (cfs_rq)는 기준이 되는 최소 vruntime 값을 유지하며
각 프로세스의 vruntime 값과 이 값의 차이를 key로 하여 red-black tree를 구성한다.
따라서 __update_curr() 실행 시 필요하다면 cfs_rq->min_vruntime 값도 갱신한다.

time slice의 계산도 이와 비슷하지만 약간 차이가 있다.
아래의 __sched_period() 함수는 모든 프로세스에게 주어진 전체 time slice 값을 계산한다.

static u64 __sched_period(unsigned long nr_running)
{
    u64 period = sysctl_sched_latency;
    unsigned long nr_latency = sched_nr_latency;

    if (unlikely(nr_running > nr_latency)) {
        period = sysctl_sched_min_granularity;
        period *= nr_running;
    }

    return period;
}

nr_running은 실행 가능한 프로세스의 개수이며,
sysctl_sched_latency는 round robin으로 모든 프로세스를 한 번씩 수행시킬 시간이고
sysctl_sched_min_granularity는 한 프로세스가 수행될 (최소)시간이다. (모두 ns 단위이다!)
sched_nr_latency는 위의 두 값의 비율로 이루어지는 값으로 프로세스 수에 해당한다.

이렇게 설명하면 복잡하니, 실제 값을 이용하여 알아보면 아래와 같다. (CPU 수에 따른 scaling은 무시한다)

sched_nr_latency = sysctl_sched_latency / sysctl_sched_min_granularity = 5ms / 1ms = 5

즉, 전체 프로세스 수가 5개 이하라면 전체 프로세스를 5ms 주기로 한 번씩 수행시키고
그 보다 많다면 (1ms * 프로세스 수) 만큼의 주기로 수행시키게 된다.

이제 위에서 계산한 전체 시간에 대해 현재 프로세스에게 할당된 시간을 알아내야 한다.
아래는 프로세스의 load (weight)를 통해 이를 수행하는 sched_slice() 함수이다.
(앞서 __update_curr()와 비교하여 calc_delta_mine() 호출 시 se의 위치를 살펴보자.)

static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);

    for_each_sched_entity(se) {
        struct load_weight *load;
        struct load_weight lw;

        cfs_rq = cfs_rq_of(se);
        load = &cfs_rq->load;

        if (unlikely(!se->on_rq)) {
            lw = cfs_rq->load;

            update_load_add(&lw, se->load.weight);
            load = &lw;
        }
        slice = calc_delta_mine(slice, se->load.weight, load);
    }
    return slice;
}

먼저 se->on_rq가 0인 경우는 현재 프로세스가 CPU에서 실행 중인 경우이다.
CFS는 실행 중인 프로세스를 run queue에서 제거하므로 전체 시간 및 load 계산 시
이를 다시 추가해서 계산해 주어야 한다.
또한 지금은 설명을 단순하게 하기 위해 group scheduling은 고려하지 않으므로
for_each_sched_entity 부분은 단 한 번만 수행된다고 생각하기로 하자.

이는 프로세스마다 (load에 따라) 공평하게 계산하여 주어진 시간이므로
이상적인(ideal) 실행 시간으로 생각할 수 있으며 타이머 인터럽트 핸들러에서는
프로세스의 실행 시간이 이상적인 실행 시간보다 큰 경우 스케줄링을 요청한다.
이를 처리하는 함수는 다음과 같다.

static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    unsigned long ideal_runtime, delta_exec;

    ideal_runtime = sched_slice(cfs_rq, curr);
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    if (delta_exec > ideal_runtime) {
        resched_task(rq_of(cfs_rq)->curr);
        ...
        return;
    }

    ...
}

이제 nice 값에 따라 CPU 자원이 어떻게 분배되는지 한 번 계산해 보기로 하자.
간단한 예제를 위해 다음과 같은 프로세스가 5개 있고, __sched_period가 10ms를 반환한다고 가정한다.

niceweightWp/Wttime slice (ms)W0/Wpvruntime (ms)
-1095480.675 6.75 0.107 0.72
-5 3121 0.221 2.21 0.328 0.72
0 1024 0.072 0.72 1 0.72
5 335 0.024 0.24 3.057 0.73
10 110 0.008 0.08 9.309 0.74
total141381.00010.00  


먼저, Wp는 해당 프로세스의 weight 값, Wt는 시스템 전체의 weight 값을 의미하며
W0는 nice 0인 프로세스의 weight (NICE_O_LOAD)를 의미한다.
weight 값을 보면 nice 5 단계 당 약 3 배 정도 CPU를 더 사용할 수 있음을 짐작할 수 있다.

nice -10인 프로세스는 전체 load의 67.5%를 차지하므로
10ms 중에서 6.75ms의 시간 동안 실행될 것이다.
반대로 weight의 역비는 0.107이므로 vruntime은 6.75 * 0.107 = 0.72가 된다.
위의 표에서 보듯이 실제 할당된 time slice는 프로세스의 weight에 비례하지만
vruntime은 모든 프로세스에서 거의 동등하게 나타나는 것을 볼 수 있다.

하지만 타이머 인터럽트는 HZ 주기로 발생하므로
weight가 낮은 프로세스의 실제 time slice 값이 이 보다 작게 할당되었어도
(별다른 외부 요인이 없는 경우) 1 tick 만큼의 시간 동안 실행될 수는 있겠지만
이 경우 vruntime에 훨씬 큰 값이 반영될 것이므로 CFS run queue의 뒤쪽에 놓일 것이고
그 만큼 오랜 시간이 지난 후에야 다시 CPU를 획득할 수 있을 것이다.

by namhyung | 2010/05/29 23:49 | Kernel | 트랙백(1) | 덧글(13)
트랙백 주소 : http://studyfoss.egloos.com/tb/5326671
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from at 2014/03/11 00:32
Commented by SY Kim at 2010/06/01 22:18
좋은 글 잘 읽고 갑니다.
Commented by namhyung at 2010/06/02 01:35
항상 친절하게 답글 남겨주셔서 감사합니다.. ^^
Commented at 2010/07/27 14:10
비공개 덧글입니다.
Commented by namhyung at 2010/07/27 21:49
조금이나마 도움이 되셨길 바랍니다.
Commented by CalvinCHAN at 2011/08/17 20:46
요즘 한창 CFS를 분석하고 있습니다. namhyung 님의 글이 많은 도움이 되고 있습니다.^^
Commented by namhyung at 2011/08/18 13:09
좋게 봐 주셔서 감사합니다..
Commented by ydJu at 2011/11/15 04:12
도움 많이 되었습니다. 감사합니다.
Commented by namhyung at 2011/12/04 14:33
도움이 되셨다니 다행입니다.
Commented by smartdolph at 2012/08/06 19:34
CFS스케줄러에서 timeslice 계산을 이해하는데 정말 많은 도움이 되었습니다. 감사합니다.^^
Commented by smartdolph at 2012/08/10 10:12
질문이 있습니다. rb-tree로 구성된 runqueue에 task를 삽입할때 key값으로 time slice를 사용하지 않고 vruntime를 key값으로 사용되는 방식은 확실히 이해하겠습니다. 하지만 코드를 보니 vruntime은 task가 runqueue에서 수행될때마다(시간단위) 그 크기가 증가하는 것으로 확인하였습니다.(update_curr에서..) 혹시나 해서 rb-tree에 삽입하는 코드를 확인하려고 __enqueue_entity(...) 함수를 보니 if( key < entity_key(cfs_rq, entry))라는 구문을 확인하였고, 이는 runqueue에서 가장 오래 기다린 task가 rb-tree의 가장 왼쪽에 배치되는 것을 알 수 있는 코드였습니다. vruntime은 runqueue에서 대기할수록 증가하는데 가장 왼쪽으로 이동한다라..?? 갑자기 햇갈립니다. 정리 좀 부탁드려도 될까요?
Commented by namhyung at 2012/08/12 11:27
entity_key() 함수는 주어진 se (entry)에 대해 cfs_rq->min_vruntime 과의 차이를 계산해 줍니다. 즉, vruntime 값이 작은 task가 왼쪽으로 이동하여 다음 번 스케줄링 시에 먼저 선택되도록 하는 역할입니다. 한 가지 착각하고 계신 부분이 vruntime이 rq에서 대기할수록 증가한다는 부분인 것 같습니다. vruntime은 runtime을 기준으로 계산하는 것이며, 이는 말 그대로 실제로 cpu에서 실행된 시간을 말합니다. update_curr() 함수는 현재 cpu 상에서 실행되고 있는 task (curr)의 (v)runtime 만을 갱신하며, 실행되지 않고 rq 내에서 대기하고 있는 task의 vruntime 값은 변경되지 않습니다.
Commented by smartdolph at 2012/08/20 11:21
자세한 설명댓글 감사드려요~. update_curr()함수는 task가 rq에서 대기할수록 vruntime이 증가되는 것이 아니라, cpu에서 수행될때 vruntime이 증가하는 것이 었군요. 그럼 상대적으로 rq에서 대기한 vruntime값이 작아지는 것이구요..확실히 정리가 되네요 ㅎㅎ 이 부분을 제가 착각하고 있었나 봅니다^^ 감사합니다~
Commented by CalvinCHAN at 2012/12/18 17:10
1년 넘게 만에 다시 들어와서 CFS를 다시 한번 공부하고 갑니다.^^
정말 많은 도움받고 갑니다.

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
block-layer CAaQA3 sed patch SMP computer-architecture synchronization documentation CARM gcc memory C elf perf x86 blktrace script vcs bash binutils git compiler linux scm build emacs kernel algorithm glibc awk
전체보기
이글루 파인더

최근 등록된 덧글
informsi yang bagus dan b..
by agen qnc at 06/22
informasi yang bagus dan b..
by agen qnc at 06/22
informasi yang bagus dan b..
by agen qnc at 06/22
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X