250308 스케줄링 엔티티의 실행시간 관리하기 & 스케줄러 초기화 (6.3~6.4)

6.3 CFS(Completely Fair Scheduling)

SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE 정책을 사용하는 태스크를 처리하는 스케줄러

6.3.5 스케줄링 엔티티의 실행시간 관리하기

• 실제 실행시간 : exec_start, sum_exec_start
• 가상 실행시간 : vruntime, min_vruntime

6-38 kernel/sched/fair.c update_curr

current task 의 sched_entity 와 run queue 의 런타임 정보 갱신

static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    curr->exec_start = now; // 마지막 실행 시간
    curr->sum_exec_runtime += delta_exec; // 총 실행 시간

    curr->vruntime += calc_delta_fair(delta_exec, curr); // load weight 에 따라 delta 값이 달라짐.
    update_min_vruntime(cfs_rq);
}

6-39 kernel/sched/fair.c calc_delta_fair

load weight 가 클수록 delta 는 작아짐 (vruntime 이 적게 추가되기 때문에 더 많이 돌게됨)

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

    return delta;
}

// sched.h
#if 0 /* BITS_PER_LONG > 32 -- currently broken: it increases power usage under light load  */
# define SCHED_LOAD_RESOLUTION    10
# define scale_load(w)        ((w) << SCHED_LOAD_RESOLUTION)
# define scale_load_down(w)    ((w) >> SCHED_LOAD_RESOLUTION)
#else
# define SCHED_LOAD_RESOLUTION    0
# define scale_load(w)        (w)
# define scale_load_down(w)    (w)
#endif

#define SCHED_LOAD_SHIFT    (10 + SCHED_LOAD_RESOLUTION)
#define SCHED_LOAD_SCALE    (1L << SCHED_LOAD_SHIFT)

6-40 kernel/sched/fair.c __calc_delta

• (delta * weight) / loadweight 인데 나누기를 계산하지 못함.
• (delta * weight * loadwegiht.inv) >> WMULT_SHIF

#define WMULT_CONST    (~0U) // 0xFFFF
#define WMULT_SHIFT    32

static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
    u64 fact = scale_load_down(weight);
    int shift = WMULT_SHIFT; // 32 위 define 에 따라서 inv 를 32비트 기준으로 하기 때문

    __update_inv_weight(lw);
    // lw.weight 가 겁나크면 Inv_weight = 1
    // lw.weight 가 겁나작으면 inv_weight = 0xFFFF
    // lw.weight 가 적당하면 inv_weight = 0xFFFF / lw.weight

    if (unlikely(fact >> 32)) { // fact 가 32비트보다 큰 경우 한칸씩 shift 해줌
        while (fact >> 32) {
            fact >>= 1;
            shift--;
        }
    }

    /* hint to use a 32x32->64 mul */
    fact = (u64)(u32)fact * lw->inv_weight; // weight * loadweight.inv

    while (fact >> 32) {
        fact >>= 1;
        shift--;
    }

    return mul_u64_u32_shr(delta_exec, fact, shift); // a * b >> shift
}

struct load_weight {
    unsigned long weight;
    u32 inv_weight;
};

static void __update_inv_weight(struct load_weight *lw)
{
    unsigned long w;

    if (likely(lw->inv_weight)) // 캐싱. weight 가 변경될때 갱신해줘야함
        return;

    w = scale_load_down(lw->weight); // w >> SCHED_LOAD_RESOLUTION

    if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST)) // w 가 겁나 큰 경우
        lw->inv_weight = 1;
    else if (unlikely(!w)) // w 가 작은경우
        lw->inv_weight = WMULT_CONST;
    else // 적당한 경우일때는 inverse
        lw->inv_weight = WMULT_CONST / w;
}

// 여기서 inv_weight 가 갱신됐었다.
static void set_load_weight(struct task_struct *p)
{
    load->weight = scale_load(sched_prio_to_weight[prio]); // 우선순위가 높을수록 높은 weight 를 사용. (이후 스케줄링에서 다룸)
    load->inv_weight = sched_prio_to_wmult[prio];
}

6.3.6 타임 슬라이스 관리하기

6-41 kernel/sched/fair.c sched_slice

entity 가 사용할 수 있는 time slice 계산하기.

CFS 런큐에 속한 entity 의 time sllice 의 합은, CFS 런큐의 스케줄링 레이턴시와 같다.

/*
 * We calculate the wall-time slice from the period by taking a part
 * proportional to the weight.
 *
 * s = p*P[w/rw]
 */
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq); // 6-42

    for_each_sched_entity(se) { // 상위 그룹을 찾아가면서
        struct load_weight *load;
        struct load_weight lw;

        cfs_rq = cfs_rq_of(se);
        load = &cfs_rq->load; // rq 의 load

        if (unlikely(!se->on_rq)) { // 아직 enqueue 되지 않았다면
            lw = cfs_rq->load;

            update_load_add(&lw, se->load.weight); // 내 weight 를 더해준 다음에 slice 를 계산한다.
            load = &lw;
        }
        slice = __calc_delta(slice, se->load.weight, load); // (slice * se 의 weight / 그룹의 load)
    }
    return slice;
}

6-42 kernel/sched/fair.c __sched_period

/*
 * The idea is to set a period in which each task runs once.
 *
 * When there are too many tasks (sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *
 * p = (nr <= nl) ? l : l*nr/nl
 */
static u64 __sched_period(unsigned long nr_running) // 돌고있는 task 수
{
    // sched_nr_latency. deafult = 8.
    if (unlikely(nr_running > sched_nr_latency))
        return nr_running * sysctl_sched_min_granularity; // 태스크 개수만큼 크게 주고, 계산하면서 점점 작아짐
    else
        return sysctl_sched_latency; // task 가 적은 경우 미리 정해진 주기
}

• sched_vslice : load weight 가중치를 사용하여 타임 슬라이스를 변환

6-43 kernel/sched/fair.c update_sysctl

• 레이턴시 계산하는 변수 값을 cpu 개수에 맞게 설정

  sysctl_sched_tunable_scaling {
  SCHED_TUNABLESCALING_NONE, // factor = 1
  SCHED_TUNABLESCALING_LINEAR, // factor = cpu
  SCHED_TUNABLESCALING_LOG, // factor = 1 + log(cpu)
  }
  

#define SET_SYSCTL(name)
(sysctl_##name = (factor) * normalized_sysctl_##name)
SET_SYSCTL(sched_min_granularity);
SET_SYSCTL(sched_latency);
SET_SYSCTL(sched_wakeup_granularity);
#undef SET_SYSCTL

## 6.4 쓰케줄러 초기화하기

### 6.4.1 sched_init 스케줄러 초기화하기S(Completely Fair Scheduling)

SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE 정책을 사용하는 태스크를 처리하는 스케줄러

### 6.3.5 스케줄링 엔티티의 실행시간 관리하기
 - 실제 실행시간 : exec_start, sum_exec_start
 - 가상 실행시간 : vruntime, min_vruntime

#### 6-38 kernel/sched/fair.c update_curr

current task 의 sched_entity 와 run queue 의 런타임 정보 갱신

```c++

static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    curr->exec_start = now; // 마지막 실행 시간
    curr->sum_exec_runtime += delta_exec; // 총 실행 시간

    curr->vruntime += calc_delta_fair(delta_exec, curr); // load weight 에 따라 delta 값이 달라짐.
    update_min_vruntime(cfs_rq);
}

6-39 kernel/sched/fair.c calc_delta_fair

load weight 가 클수록 delta 는 작아짐 (vruntime 이 적게 추가되기 때문에 더 많이 돌게됨)

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

    return delta;
}

// sched.h
#if 0 /* BITS_PER_LONG > 32 -- currently broken: it increases power usage under light load  */
# define SCHED_LOAD_RESOLUTION    10
# define scale_load(w)        ((w) << SCHED_LOAD_RESOLUTION)
# define scale_load_down(w)    ((w) >> SCHED_LOAD_RESOLUTION)
#else
# define SCHED_LOAD_RESOLUTION    0
# define scale_load(w)        (w)
# define scale_load_down(w)    (w)
#endif

#define SCHED_LOAD_SHIFT    (10 + SCHED_LOAD_RESOLUTION)
#define SCHED_LOAD_SCALE    (1L << SCHED_LOAD_SHIFT)

6-40 kernel/sched/fair.c __calc_delta

• (delta * weight) / loadweight 인데 나누기를 계산하지 못함.
• (delta * weight * loadwegiht.inv) >> WMULT_SHIF

#define WMULT_CONST    (~0U) // 0xFFFF
#define WMULT_SHIFT    32

static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
    u64 fact = scale_load_down(weight);
    int shift = WMULT_SHIFT; // 32 위 define 에 따라서 inv 를 32비트 기준으로 하기 때문

    __update_inv_weight(lw);
    // lw.weight 가 겁나크면 Inv_weight = 1
    // lw.weight 가 겁나작으면 inv_weight = 0xFFFF
    // lw.weight 가 적당하면 inv_weight = 0xFFFF / lw.weight

    if (unlikely(fact >> 32)) { // fact 가 32비트보다 큰 경우 한칸씩 shift 해줌
        while (fact >> 32) {
            fact >>= 1;
            shift--;
        }
    }

    /* hint to use a 32x32->64 mul */
    fact = (u64)(u32)fact * lw->inv_weight; // weight * loadweight.inv

    while (fact >> 32) {
        fact >>= 1;
        shift--;
    }

    return mul_u64_u32_shr(delta_exec, fact, shift); // a * b >> shift
}

struct load_weight {
    unsigned long weight;
    u32 inv_weight;
};

static void __update_inv_weight(struct load_weight *lw)
{
    unsigned long w;

    if (likely(lw->inv_weight)) // 캐싱. weight 가 변경될때 갱신해줘야함
        return;

    w = scale_load_down(lw->weight); // w >> SCHED_LOAD_RESOLUTION

    if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST)) // w 가 겁나 큰 경우
        lw->inv_weight = 1;
    else if (unlikely(!w)) // w 가 작은경우
        lw->inv_weight = WMULT_CONST;
    else // 적당한 경우일때는 inverse
        lw->inv_weight = WMULT_CONST / w;
}

// 여기서 inv_weight 가 갱신됐었다.
static void set_load_weight(struct task_struct *p)
{
    load->weight = scale_load(sched_prio_to_weight[prio]); // 우선순위가 높을수록 높은 weight 를 사용. (이후 스케줄링에서 다룸)
    load->inv_weight = sched_prio_to_wmult[prio];
}

6.3.6 타임 슬라이스 관리하기

6-41 kernel/sched/fair.c sched_slice

entity 가 사용할 수 있는 time slice 계산하기.

CFS 런큐에 속한 entity 의 time sllice 의 합은, CFS 런큐의 스케줄링 레이턴시와 같다.

/*
 * We calculate the wall-time slice from the period by taking a part
 * proportional to the weight.
 *
 * s = p*P[w/rw]
 */
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq); // 6-42

    for_each_sched_entity(se) { // 상위 그룹을 찾아가면서
        struct load_weight *load;
        struct load_weight lw;

        cfs_rq = cfs_rq_of(se);
        load = &cfs_rq->load; // rq 의 load

        if (unlikely(!se->on_rq)) { // 아직 enqueue 되지 않았다면
            lw = cfs_rq->load;

            update_load_add(&lw, se->load.weight); // 내 weight 를 더해준 다음에 slice 를 계산한다.
            load = &lw;
        }
        slice = __calc_delta(slice, se->load.weight, load); // (slice * se 의 weight / 그룹의 load)
    }
    return slice;
}

6-42 kernel/sched/fair.c __sched_period

/*
 * The idea is to set a period in which each task runs once.
 *
 * When there are too many tasks (sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *
 * p = (nr <= nl) ? l : l*nr/nl
 */
static u64 __sched_period(unsigned long nr_running) // 돌고있는 task 수
{
    // sched_nr_latency. deafult = 8.
    if (unlikely(nr_running > sched_nr_latency))
        return nr_running * sysctl_sched_min_granularity; // 태스크 개수만큼 크게 주고, 계산하면서 점점 작아짐
    else
        return sysctl_sched_latency; // task 가 적은 경우 미리 정해진 주기
}

• sched_vslice : load weight 가중치를 사용하여 타임 슬라이스를 변환

6-43 kernel/sched/fair.c update_sysctl

• 레이턴시 계산하는 변수 값을 cpu 개수에 맞게 설정

  sysctl_sched_tunable_scaling {
  SCHED_TUNABLESCALING_NONE, // factor = 1
  SCHED_TUNABLESCALING_LINEAR, // factor = cpu
  SCHED_TUNABLESCALING_LOG, // factor = 1 + log(cpu)
  }
  

#define SET_SYSCTL(name)
(sysctl_##name = (factor) * normalized_sysctl_##name)
SET_SYSCTL(sched_min_granularity);
SET_SYSCTL(sched_latency);
SET_SYSCTL(sched_wakeup_granularity);
#undef SET_SYSCTL

## 6.4 쓰케줄러 초기화하기

### 6.4.1 sched_init 스케줄러 초기화하기

#### kernel/sched/core.c sched_init 1

- root 태스크 그룹 초기화
1. 자신만의 entity 나 cfs 런큐를 가지고 있지 않다. (enqueue 할 상위 run queue  가 없음)
2. 대신 possible cpu 의 CFS 런큐를 가리키고 있다.

```c++
void __init sched_init(void)
{
    alloc_size += 2 * nr_cpu_ids * sizeof(void **);

    if (alloc_size) {
        // sched_entity[possible cpu], cfs_rq[possible_cpu]
        ptr = (unsigned long)kzalloc(alloc_size, GFP_NOWAIT);

        root_task_group.se = (struct sched_entity **)ptr;
        ptr += nr_cpu_ids * sizeof(void **);

        root_task_group.cfs_rq = (struct cfs_rq **)ptr;
        ptr += nr_cpu_ids * sizeof(void **);
    }

    task_group_cache = KMEM_CACHE(task_group, 0); // task_group 생성하는 slab cache. 이후 group 추가시 사용
    list_add(&root_task_group.list, &task_groups); // 모든 Taskgroup 연결하는 task_groups 에 root 추가
    INIT_LIST_HEAD(&root_task_group.children);
    INIT_LIST_HEAD(&root_task_group.siblings);

    for_each_possible_cpu(i) {
        struct rq *rq;

        rq = cpu_rq(i); // per-cpu
        init_tg_cfs_entry(&root_task_group, &rq->cfs, NULL, i, NULL); // 6-45
        // pseudo
        // root_tg.cfs_rq[i] = cpu[i].rq
        // root_tg.sched_entity[i] = null
        // cpu[i].tg = root_tg;
    }
}

6-45 kernel/sched/fair.c init_tg_cfs_entry

void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
            struct sched_entity *se, int cpu,
            struct sched_entity *parent)
{
    struct rq *rq = cpu_rq(cpu); // cpu index ->cpu rq

    // cpu i 의 런큐 안에 cfs_rq 가 들어있음
    cfs_rq->tg = tg;
    cfs_rq->rq = rq;
    init_cfs_rq_runtime(cfs_rq);

    // root tg 에서도 가리킴. 근데 root tg 의 .se(sched_entity) 가 뭘까? 왜 cpu 갯수만큼 일까? 실행중인 entity 가 나중에 여기로 오나?
    // 그와중에 아래에서는 !se 면 return 임. 나중에 확인해봐야 할듯
    // root_task_group 는 se 를 갖고있지 않다.
    tg->cfs_rq[cpu] = cfs_rq;
    tg->se[cpu] = se;

    /* se could be NULL for root_task_group */
    if (!se)
        return;

    if (!parent) {
        se->cfs_rq = &rq->cfs;
        se->depth = 0;
    } else {
        se->cfs_rq = parent->my_q; // 내 rq 는 부모(group) 의 my_q 를 가리키게 하자
        se->depth = parent->depth + 1;
    }

    se->my_q = cfs_rq; // task group 소유의 CFS 런큐를 설정?
    /* guarantee group entities always have weight */
    update_load_set(&se->load, NICE_0_LOAD);
    se->parent = parent; // 부모 태스크 그룹 entity 설정
}

/*
 * This is the main, per-CPU runqueue data structure.
 *
 * Locking rule: those places that want to lock multiple runqueues
 * (such as the load balancing or the thread migration code), lock
 * acquire operations must be ordered by ascending &runqueue.
 */
struct rq { // cpu 별로 갖고있음
    struct cfs_rq cfs; // rq 안에 cfs_rq 존재
}

struct cfs_rq {
#ifdef CONFIG_FAIR_GROUP_SCHED
    struct rq *rq;    /* cpu runqueue to which this cfs_rq is attached */
    struct task_group *tg;    /* group that "owns" this runqueue */
#end
}

struct task_group {
#ifdef CONFIG_FAIR_GROUP_SCHED
    /* schedulable entities of this group on each cpu */
    struct sched_entity **se;
    /* runqueue "owned" by this group on each cpu */
    struct cfs_rq **cfs_rq;
#endif
}

struct sched_entity {
#ifdef CONFIG_FAIR_GROUP_SCHED
    int            depth;
    struct sched_entity    *parent;
    /* rq on which this entity is (to be) queued: */
    struct cfs_rq        *cfs_rq;
    /* rq "owned" by this entity/group: */
    struct cfs_rq        *my_q;
#endif
}

일반 task 인 경우

• task->se->cfs_rq 는 cpu 의 cfs_rq
• task->se->my_q 는 null

root task group 이 아닌 task group 인 경우.

• tg->se[i] 가 sched_entity
• tg->se[i]->my_q 가 내 cfs_rq
• tg->se[i]->my_q->tg 다시 나를 가리킴

6-46, 6-47 kernel/sched/core.c sched_init 2, 3

    for_each_possible_cpu(i) {
        struct rq *rq;
        // rq 초기화
    }

    autogroup_init(&init_task);

    set_load_weight(&init_task); // swapper 는 nice 0 으로 load weight 1024
    current->sched_class = &fair_sched_class; // swapper 의 스케줄링 클래스를 fair 로 설정
    init_idle(current, smp_processor_id()); // swapper 를 idle trhread 로 사용

    idle_thread_set_boot_cpu(); // per-cpu idl_threads 를 cpu 0 의 idle 쓰레드로 설정
    init_sched_fair_class();

    scheduler_running = 1;
}