Scheduler -3- (Preemption & Context Switch)

 

멀티 태스킹

arm 아키텍처에서 각 cpu core들은 한 번에 하나의 스레드를 동작시킬 수 있다. (특정 아키텍처에서 cpu core 당 2 개 이상의 h/w 스레드를 지원하기도한다. 예: 인텔의 하이퍼스레드 등) 사용자가 요청한 여러 개의 태스크를 동시에 처리하기 위해 각 태스크들을 일정 주기 시간을 분할하여 스케줄하는 방법을 사용한다.

 

다음 그림과 같이 시간 분할하여 스케줄한 예를 보여준다. (1 core 시스템에서 디폴트 스케줄 레이턴시: 6ms)

  • cpu#0 코어에서 3개의 태스크를 구동한 예:
    • 3개의 태스크 각 A, B, C 태스크가 각자 지정된 로드 weight 비율로 6ms 스케줄링 레이튼시 간격으로 스케줄 처리하는 것으로 멀티태스킹을 수행한다.
  • cpu#1 코어에서 1개의 태스크를 구동한 예:
    • 1개의 태스크는 경쟁하는 태스크가 없으므로 계속 동작한다. sleep 하는 구간에서는 idle 태스크가 대신 동작한다.
  • cpu#2 코어에서 10개의 태스크를 구동한 예:
    • 8개를 초과하는 태스크의 경우 디폴트 스케줄링 레이튼시를 초과하므로 지정된 최소 할당 시간(0.75ms) x 태스크 수를 산출하여 스케줄링 레이턴시를 산출하여 처리한다.

 

Preemption

한 개의 태스크가 cpu 시간을 독차지하지 못하게 제어를 할 필요가 있어 다음과 같은 순간에 다른 태스크의 전환을 수행한다.

 

1) 양보

다음 그림과 같이 유저/커널 태스크의 구분 없이 모든 preemption 모드에서 schedule() 함수가 동작하는 경우 다음 수행하여야 할 태스크를 선택한다.

 

2) 유저 선점

다음 그림과 같이 유저 태스크 동작 중 인터럽트에 의해 선점 요청이 이루어진 경우 인터럽트 복귀 시 리스케줄을 수행한다.

  • 타이머 인터럽트에서 현재 태스크의 런타임이 다 소진되었거나, 기타 장치 인터럽트에서 우선 처리할 태스크가 있는 경우 요청된다.

3) 커널 선점
  • CONFIG_PREEMPT_NONE
    • 커널 스레드가 스스로 양보하지 않으면 preemption되지 않는다. 커널 태스크를 만들어 사용하는 경우 일반적으로 태스크를 설계 시 적절한 위치에서 종종 양보(yield or sleep)를 해야 한다.
  • CONFIG_PREEMPT_VOLOUNTRY
    • 커널 스레드가 양보하지 않으면 preemption되지 않는 것은 동일하다. 단 커널 API의 곳곳에 preemption point를 두었고 이 곳에서 리스케줄 요청 플래그를 확인하고 직접 양보를 수행한다.
  • CONFIG_PREEMPT
    • 유저 선점과 동일하게 동작한다.

 

다음 그림은 커널 선점에 대해 3개의 preemption 모델별 처리 차이를 보여준다.

 

런타임 소진에 따른 스케줄(유저 선점 예)

유저 태스크에 주어진 로드 weight 비율만큼의 산출된 런타임이 다 소진된 경우 이를 체크하기 위해 타이머 인터럽트가 필요하다.

  • hrtick을 사용하는 시스템에서는 산출된 런타임에 맞춰 타이머 인터럽트를 생성하고 그 때마다 런타임 소진을 체크하므로 just하게 스케줄할 수 있다
    • armv7, armv8 smp 디폴트: CONFIG_SCHED_HRTICK을 사용한다. (rpi2, rpi3)
    • 디폴트: hrtick feature를 사용하지 않는다. (rpi2, rpi3)
  • periodic tick을 사용하는 시스템에서는 매 틱마다 런타임 소진을 체크한다.  런타임을 초과하여 사용한 런타임은 나중에 그 만큼 빼고 처리된다.
    • periodic tick은 엄밀히 런타임 소진 또는 vruntime이 가장 작은 태스크로 스케줄링이된다.

 

다음 그림은 유저 태스크들을 대상으로 hrtick과 legacy periodic 틱을 사용하는 두 개의 예를 보여준다.

 

CONFIG_PREEMPT 커널 옵션을 사용한 경우에는 커널 태스크가 동작 시 런타임 소진에 의해 선점 요청을 하면 위의 유저 태스크 상황과 동일하게 동작한다. 그러나 다른 커널 옵션을 사용하는 경우 양보 코드 및 preemption point에 의지하여 선점을 하는 것에 주의해야 한다.

 

preemption이 일어나는 것을 막아야 할 때?

  • preemption은 동기화 문제를 수반한다.
  • critical section으로 보호받는 영역에서는 preemption이 발생하면 안되기 때문에 이러한 경우 preempt_disable()을  사용한다.
  • preempt_disable() 코드에서는 단순히 preempt 카운터를 증가시킨다.
  • 인터럽트 발생 시 preempt 카운터가 0이 아니면 스케쥴링이 일어나지 않도록 즉 다른 스레드로의 context switching이 일어나지 않도록 막는다.
  • 물론 interrupt를 원천적으로 disable하는 경우도 preemption 이 일어나지 않는다.

 

리눅스 preemption 모델의 특징

리눅스는 유저 모드에서는 태스크에 할당받은 time slice에 대해 모두 소진하기 전이라도 다른 태스크에 의해 preemption 되어 현재 태스크가 sleep될 수 있다. 하지만 커널 스레드나 커널 모드에서는 다음과 같이 4가지의 preemption 모델에 따라 동작을 다르게 한다.

PREEMPT_NONE:

  • 반응 속도(latency)는 최대한 떨어뜨리되 배치 작업을 우선으로 하여 성능에 최적화 시켜 서버에 적합한 모델이다.
  • 100hz → 250/1000hz의 낮은 타이머 주기를 사용.
  • context switching을 최소화

 

PREEMPT_VOLUNTARY:

  • Voluntary Kernel Preemption (Desktop)
  • 오래 걸릴만한 api 또는 드라이버에서 중간 중간에 preemption point를 두어 리스케줄 요청한 태스크들을 먼저 수행할 수 있도록 preemption 될 수 있게 한다. (중간 중간 필요한 preemption point에서 스케줄을 변경하게 한다.)
  • 어느 정도 반응 속도(latency)를 높여 키보드, 마우스 및 멀티미디어 등의 작업이 가능하도록 하고 성능도 일정부분 보장하게 하도록한 데스크탑에 적합한 모델이다.
  • preemption points
    • 커널 모드에서 동작하는 여러 코드에 explicit preemption points를 추가하여 종종 reschedule이 필요한지 확인하여 preemption이 사용되어야 하는 빈도를 높힘으로 preemption latency를 작게하였다.
    • 이러한 preemption 포인트의 도움을 받아 급한 태스크의 기동에 필요한 latency가 100us 이내로 줄어드는 성과가 있었다.
    • preemption point는 보통 1ms(100us) 이상 소요되는 루틴에 보통 추가한다.
    • 현재 커널에 거의 천 개에 가까운 preemption point가 존재한다.

 

PREEMPT:

  • Preemptible Kernel (Low-Latency Desktop)
  • 커널 모드에서도 언제나 preemption을 허용하여(인터럽트 및 preemption disable 시 제외) 거의 대부분의 시간동안 우선 순위가 높은 태스크가 먼저 수행되도록 스케줄링 된다. 따라서 이 옵션을 사용하는 경우에는 preemption point가 필요없으므로 동작하지 않는다.
  • 반응 속도(latency) 빨라야 하는 대략 밀리세컨드의 latency가 필요한 네트웍 장치등의 임베디드 시스템에서 적합한 모델이다

 

PREEMPT_RT:

  • 아직 mainline에 등록되지 않았다.
  • 따라서 Real-tIme OS 기능이 필요한 경우 Real-time OS를 연구하는 그룹에서 유지보수하는 리눅스를 사용해야 한다. (계속되고 있는 프로젝트)
  • 사실 full preempt kernel에 대한 고민이 kernel mainliner들에게 있다. 바로 성능 저하인데 이 때문에 아직까지 mainline에 올리지 못하는 이유이기도 하다. (참고: Optimizing preemption | LWN.net)
    • 예) Linux 3,7.0-rt 과 같이 뒤에 rt가 붙어 있다.
  • 인터럽트 수행중에도 preemption이 가능하다.

 

커널 버전에 따른 preemption 기능

preempt4

  • 커널 버전 2.4까지 user mode만 선점이 가능했었다. (user mode에서 동작중인 process가 system call API를 호출하여 kernel mode로 진입하여 동작 중인 경우에는 선점 불가능)
  • 버전 2.6에 이르러 kernel mode도 선점이 가능해졌다.  (드라이버 수행 중 또는 system call API를 호출하여 kernel mode에 있는 경우에도 다른 태스크로의 선점이 가능해졌다)
    • preemption 모델 중 CONFIG_PREEMPT_NONE 제외
    • kernel mode에서 선점이 가능해졌지만 리눅스가 원래 Real-Time OS 설계가 아닌 관계로 big kernel lock(2중, 3중 critical section 등 사용)으로 인해 필요한 때 인터럽트 응답성이 빠르지 않았다. 물론 현재는 big kernel lock을 다 제거하여 사용하지 않는다.
    • 인터럽트 latency를 줄이기 위해 인터럽트 핸들러를 top-half, bottom-half 두 개의 파트로 나누었다. (Two part interrupt handler | 문c)
  • Real-time 리눅스 커널 패치 PREEMPT_RT가 적용되면서 critical section 및 인터럽트 수행중에서도 preemption이 지원되었다.
    •  SMP 환경에서는 spinlock으로 제어되는 critical section에서 CPU들의 동시 접근 효율이 떨어지면서 문제가 되므로 이를 해결하기 위해 spinlock은 RT 리눅스에서는 preempt_disable을 하지 않도록 mutex를 사용한다. 물론 반드시 preemption이 disable되어야 하는 경우를 위해 그러한 루틴을 위해 raw_spin_lock에서 처리되게 이전하였다.

 

RT(Real-Time) Linux

  • 실시간으로 스케쥴링이 필요한 업무가 생기면서 리눅스에 Real Time 기능이 필요하여 RT(Real Time) 리눅스가 구현되고 있다.
  • RT 리눅스 시스템을 지원하게 되면서 preemption이 빠르게 일어날 수 있도록 lock, interrupt 관련 함수들이 복잡하게 수정되었다.
  •  두 개의 패치
    • 1) PREEMPT_RT 패치
      • 전부는 아니지만 많은 코드가 이미 linux mainline에 통합되었다.
      • spinlocks와 local_irq_save()는 더이상 h/w interrupt를 disable하지 않는다.
      • spinlocks는 더이상 preemption을 disable하지 않는다.
      • raw_로 시작하는 spinlocks와 local_irq_save()는 기존 방식을 사용한다.
      • semaphore와 spinlocks는 priority inheritance를 승계한다.
    • 2) Linux(realtime) extensions
      • Priority Scheduling
      • Real-Time signals
      • Clocks and Timers
      • Semaphores
      • Message Passing
      • Shared Memory
      • Asynchronous and Synchronous I/O
      • Memory Locking
    • 그외
      • Threaded Interrupt
      • RT-Mutexes (based priority inheritance protocol)
      • BKL(Big Kernel Lock)-free(2.6.37)

 

RT Mutex based Priority inheritance protocol

Preemption Point 구현

CONFIG_PREEMPT_VOLUNTARY 커널 옵션을 사용하는 preemption 모델에서 사용하는 preemption point의 대표적인 함수이다.

might_sleep()

include/linux/kernel.h

# define might_sleep() do { might_resched(); } while (0)

CONFIG_PREEMPT_VOLUNTARY 커널에서 preemption point로 동작하여 리스케줄 요청이 있으면서 preemption 가능한 경우 스케줄하여 태스크 선점을 양보한다.

  • 현재 태스크는 슬립되고 다음 실행할 태스크가 선택되어 스케줄되고 실행된다.
  • 커널에서 1ms 이상 소요되는 경우 voluntary preemption 모델을 사용하는 커널을 위해 잠시 우선순위가 높은 태스크를 위해 스스로 양보하고 선점당할 수 있는 포인트를 제공하기 위해 사용된다.
#ifdef CONFIG_PREEMPT_VOLUNTARY
# define might_resched() _cond_resched()
#else
# define might_resched() do { } while (0)
#endif

CONFIG_PREEMPT_VOLUNTARY 커널에서 preemption point로 동작하여 리스케줄 요청이 있는 경우 스케줄한다.

  • CONFIG_PREEMPT_NONE preemption 모델에서는 커널 preemption을 지원하지 않으므로 preemption 포인트를 제공하지 않는다.
  • CONFIG_PREEMPT preemption 모델의 경우는 커널 preemption이 실시간으로 지원되기 떄문에 preemption 포인트가 필요없다.

다음 그림은 might_sleep()을 호출 할 때 voluntary 커널에서 스케줄 함수를 호출하는 과정을 보여준다.

 

_cond_resched()

kernel/sched/core.c

int __sched _cond_resched(void)
{
        if (should_resched()) {
                preempt_schedule_common();
                return 1;
        }
        return 0;
}
EXPORT_SYMBOL(_cond_resched);

리스케줄 요청이 있으면서 preemption 가능한 경우 스케줄을 수행하고 true(1)를 반환한다. 리스케줄 요청이 없는 경우 false(0)를 반환한다.

 

should_resched()
/*              
 * Returns true when we need to resched and can (barring IRQ state).
 */
static __always_inline bool should_resched(void)
{
        return unlikely(!preempt_count() && tif_need_resched());
}

preempt 카운터가 0이어서 preemption이 가능하고 리스케줄 요청이 있는 경우 true를 반환한다.

 

tif_need_resched()

include/linux/thread_info.h

#define tif_need_resched() test_thread_flag(TIF_NEED_RESCHED)

현재 스레드에 리스케줄 요청이 기록되어 있는지 여부를 반환한다. 리스케줄 요청=true(1)

include/linux/thread_info.h

#define test_thread_flag(flag) \
        test_ti_thread_flag(current_thread_info(), flag)

현재 스레드에 요청 flag 비트가 설정된 경우 true(1)를 반환한다.

 

need_resched()

include/linux/sched.h

static __always_inline bool need_resched(void)
{
        return unlikely(tif_need_resched());
}

현재 스레드에 리스케줄 요청이 기록되어 있는지 여부를 반환한다. 리스케줄 요청=true(1)

 

Preempt Count

현재 스레드의 preemption 허용 여부를 nest 하여 증/감하는데 이 값이 0이 될 때 preemption 가능한 상태가 된다.

preempt_count()

include/asm-generic/preempt.h

static __always_inline int preempt_count(void)
{
        return current_thread_info()->preempt_count;
}

현재 태스크의 preempt 카운터를 반환한다.

preemption 카운터가 0이되면 preemption이 가능해진다. preemption 카운터의 각 비트를 묶어 preemption을 mask하는 용도로 나누어 구성한다. 어느 한 필드라도 비트가 존재하면 preemption되지 않는다.

 

include/linux/preempt_mask.h

/*
 * We put the hardirq and softirq counter into the preemption
 * counter. The bitmask has the following meaning:
 *
 * - bits 0-7 are the preemption count (max preemption depth: 256)
 * - bits 8-15 are the softirq count (max # of softirqs: 256)
 *
 * The hardirq count could in theory be the same as the number of
 * interrupts in the system, but we run all interrupt handlers with
 * interrupts disabled, so we cannot have nesting interrupts. Though
 * there are a few palaeontologic drivers which reenable interrupts in
 * the handler, so we need more than one bit here.
 *
 * PREEMPT_MASK:        0x000000ff
 * SOFTIRQ_MASK:        0x0000ff00
 * HARDIRQ_MASK:        0x000f0000
 *     NMI_MASK:        0x00100000
 * PREEMPT_ACTIVE:      0x00200000
 */
#define PREEMPT_BITS    8
#define SOFTIRQ_BITS    8
#define HARDIRQ_BITS    4
#define NMI_BITS        1

#define PREEMPT_SHIFT   0
#define SOFTIRQ_SHIFT   (PREEMPT_SHIFT + PREEMPT_BITS)
#define HARDIRQ_SHIFT   (SOFTIRQ_SHIFT + SOFTIRQ_BITS)
#define NMI_SHIFT       (HARDIRQ_SHIFT + HARDIRQ_BITS)

#define __IRQ_MASK(x)   ((1UL << (x))-1)

#define PREEMPT_MASK    (__IRQ_MASK(PREEMPT_BITS) << PREEMPT_SHIFT)
#define SOFTIRQ_MASK    (__IRQ_MASK(SOFTIRQ_BITS) << SOFTIRQ_SHIFT)
#define HARDIRQ_MASK    (__IRQ_MASK(HARDIRQ_BITS) << HARDIRQ_SHIFT)
#define NMI_MASK        (__IRQ_MASK(NMI_BITS)     << NMI_SHIFT)

#define PREEMPT_OFFSET  (1UL << PREEMPT_SHIFT)
#define SOFTIRQ_OFFSET  (1UL << SOFTIRQ_SHIFT)
#define HARDIRQ_OFFSET  (1UL << HARDIRQ_SHIFT)
#define NMI_OFFSET      (1UL << NMI_SHIFT)

#define SOFTIRQ_DISABLE_OFFSET  (2 * SOFTIRQ_OFFSET)

#define PREEMPT_ACTIVE_BITS     1
#define PREEMPT_ACTIVE_SHIFT    (NMI_SHIFT + NMI_BITS)
#define PREEMPT_ACTIVE  (__IRQ_MASK(PREEMPT_ACTIVE_BITS) << PREEMPT_ACTIVE_SHIFT)

다음 그림은 preempt 카운터의 각 비트에 대해 표시하였다.

 

다음 그림은 preempt_count와 관련된 조작 함수와 조회 함수 들을 보여준다.

 

Preempt Enable & Disable

preempt_enable()

include/linux/preempt.h

#ifdef CONFIG_PREEMPT_COUNT
#ifdef CONFIG_PREEMPT
#define preempt_enable() \
do { \
        barrier(); \
        if (unlikely(preempt_count_dec_and_test())) \
                __preempt_schedule(); \
} while (0)

#else
#define preempt_enable() \
do { \
        barrier(); \
        preempt_count_dec(); \
} while (0)
#define preempt_check_resched() do { } while (0)
#endif
#else
#define preempt_enable()                        barrier()
#endif

다음과 같이 preempt 카운터 및 preemption 모델에 따라 다음과 같이 동작한다.

  • CONFIG_PREEMPT_COUNT 사용 및 preemption 모델에 따른 기능
    • CONFIG_PREEMPT
      • preemption 카운터를 감소시키고 그 값이 0이되는 경우 이후부터 아무 때나 preemption을 허용가능하게 한다.
      • 호출 즉시 리스케줄 요청이 있는 경우 스케줄 호출한다.
    • CONFIG_PREEMPT_VOLUNTARY
      • preemption 카운터가 0이되면 preemption point 마다 리스케줄 요청이 있는 경우 스케줄한다.
    • CONFIG_PREEMPT_NONE 사용
      • preemption 카운터를 감소시킨다.
      • preemption 카운터가 0이되어도 preemption point에서 아무것도 수행하지 않는다.
  • CONFIG_PREEMPT_COUNT 미사용
    • preemption 기능을 사용하지 않는다.

 

다음 그림은 preempt_enable()이 preemption 모델에 따라 수행되는 경로를 보여준다.

preempt_count_dec_and_test()

include/linux/preempt.h

#define preempt_count_dec_and_test() __preempt_count_dec_and_test()

preemption 카운터를 감소시키고 그 값이 0이 되어 preemption 가능하고 리스케줄 요청이 있는 경우 true를 반환한다.

 

include/asm-generic/preempt.h

static __always_inline bool __preempt_count_dec_and_test(void)
{
        /*
         * Because of load-store architectures cannot do per-cpu atomic
         * operations; we cannot use PREEMPT_NEED_RESCHED because it might get
         * lost.
         */
        return !--*preempt_count_ptr() && tif_need_resched();
}

preempt_count_dec()

include/linux/preempt.h

#define preempt_count_dec() preempt_count_sub(1)
#define preempt_count_sub(val)  __preempt_count_sub(val)

preemption 카운터를 1 만큼 감소시킨다.

 

preempt_count_sub()

include/linux/preempt.h

#define preempt_count_sub(val)  __preempt_count_sub(val)

preemption 카운터를 val 값 만큼 감소시킨다.

 

include/asm-generic/preempt.h

static __always_inline void __preempt_count_sub(int val)
{
        *preempt_count_ptr() -= val;
}

preemption 카운터를 val 값 만큼 감소시킨다.

 

preempt_disable()

include/linux/preempt.h

#ifdef CONFIG_PREEMPT_COUNT
#define preempt_disable() \ 
do { \
        preempt_count_inc(); \
        barrier(); \
} while (0)
#else
/*
 * Even if we don't have any preemption, we need preempt disable/enable
 * to be barriers, so that we don't have things like get_user/put_user
 * that can cause faults and scheduling migrate into our preempt-protected
 * region.
 */
#define preempt_disable()                       barrier()
#endif

preempt 카운터 및 preemption 모델에 따라 다음과 같이 동작한다.

  • CONFIG_PREEMPT_COUNT 사용
    • preemption 카운터를 증가시킨다.
    • preemption 모델과 관계 없이 이후부터 preemption을 허용하지 않는다.
  • CONFIG_PREEMPT_COUNT 미사용
    • preemption 기능을 사용하지 않는다.

 

다음 그림은 preempt_disable()이 preempt 카운터 사용 여부에 따라 수행되는 경로를 보여준다.

preempt_count_inc()

include/linux/preempt.h

#define preempt_count_inc() preempt_count_add(1)

preemption 카운터를 1 만큼 증가시킨다.

 

preempt_count_add()

include/linux/preempt.h

#define preempt_count_add(val)  __preempt_count_add(val)

preemption 카운터를 val 값 만큼 증가시킨다.

 

include/asm-generic/preempt.h

static __always_inline void __preempt_count_add(int val)
{
        *preempt_count_ptr() += val;
}

preemption 카운터를 val 값 만큼 증가시킨다.

 

스케줄

schedule()

kernel/sched/core.c

asmlinkage __visible void __sched schedule(void)
{
        struct task_struct *tsk = current;

        sched_submit_work(tsk);
        do {
                __schedule();
        } while (need_resched());
}
EXPORT_SYMBOL(schedule);

현재 태스크를 sleep하고 다음 태스크를 스케줄한다. 현재 태스크가 깨어난 후 여전히 리스케줄 요청이 있는 경우 다시 루프를 돈다.

 

__preempt_schedule()

kernel/sched/core.c

#define __preempt_schedule() preempt_schedule()

 

preempt_schedule()

kernel/sched/core.c

/*
 * this is the entry point to schedule() from in-kernel preemption
 * off of preempt_enable. Kernel preemptions off return from interrupt
 * occur there and call schedule directly.
 */
asmlinkage __visible void __sched notrace preempt_schedule(void)
{
        /*
         * If there is a non-zero preempt_count or interrupts are disabled,
         * we do not want to preempt the current task. Just return..
         */
        if (likely(!preemptible()))
                return;

        preempt_schedule_common();
}
NOKPROBE_SYMBOL(preempt_schedule);
EXPORT_SYMBOL(preempt_schedule);

preemption이 가능한 경우에만 현재 태스크를 sleep하고 다른 태스크를 가져와 실행하기 위해 스케줄한다.

 

preemptible()

include/linux/preempt_mask.h

#ifdef CONFIG_PREEMPT_COUNT
# define preemptible()  (preempt_count() == 0 && !irqs_disabled())
#else
# define preemptible()  0
#endif

preemption이 가능한 상태인지 여부를 알아온다. true(1)=preemption 가능한 상태

  • CONFIG_PREEMPT_COUNT 커널 옵션을 사용하지 않는 경우에는 항상 preemption을 할 수 없다.

 

preempt_schedule_common()

kernel/sched/core.c

static void __sched notrace preempt_schedule_common(void)
{
        do {
                __preempt_count_add(PREEMPT_ACTIVE);
                __schedule();
                __preempt_count_sub(PREEMPT_ACTIVE);

                /*
                 * Check again in case we missed a preemption opportunity
                 * between schedule and now.
                 */
                barrier();
        } while (need_resched());
}

리스케줄 요청이 있는 동안 루프를 돌며 스케줄을 수행한다.

  • 코드 라인 4에서 스케줄링을 수행하기 위해 preemption 카운터 중 가장 높은 비트를 설정하여 preemption 되지 않도록 막는다.
  • 코드 라인 5에서 현재 태스크는 preemption되어 슬립되고 리스케줄하여 다음 진행할 태스크를 pickup하여 실행시킨다.
  • 코드 라인 6에서 한동안 preemption되어 슬립되었다가 여기서 깨어나게 되면 조금 전에 증가시켰던 비트를 감소시킨다.
  • 코드 라인 13에서 리스케줄 요청이 남아 있는 경우 계속 루프를 돈다.

 

__schedule()

kernel/sched/core.c

/*
 * __schedule() is the main scheduler function.
 *
 * The main means of driving the scheduler and thus entering this function are:
 *
 *   1. Explicit blocking: mutex, semaphore, waitqueue, etc.
 *
 *   2. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
 *      paths. For example, see arch/x86/entry_64.S.
 *
 *      To drive preemption between tasks, the scheduler sets the flag in timer
 *      interrupt handler scheduler_tick().
 *
 *   3. Wakeups don't really cause entry into schedule(). They add a
 *      task to the run-queue and that's it.
 *
 *      Now, if the new task added to the run-queue preempts the current
 *      task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
 *      called on the nearest possible occasion:
 *
 *       - If the kernel is preemptible (CONFIG_PREEMPT=y):
 *
 *         - in syscall or exception context, at the next outmost
 *           preempt_enable(). (this might be as soon as the wake_up()'s
 *           spin_unlock()!)
 *
 *         - in IRQ context, return from interrupt-handler to
 *           preemptible context
 *
 *       - If the kernel is not preemptible (CONFIG_PREEMPT is not set)
 *         then at the next:
 *
 *          - cond_resched() call
 *          - explicit schedule() call
 *          - return from syscall or exception to user-space
 *          - return from interrupt-handler to user-space
 *
 * WARNING: all callers must re-check need_resched() afterward and reschedule
 * accordingly in case an event triggered the need for rescheduling (such as
 * an interrupt waking up a task) while preemption was disabled in __schedule().
 */

CONFIG_PREEMPT 커널 옵션을 사용하는 preemptible 커널인 경우 커널 모드에서도 preempt가 enable 되어 있는 대부분의 경우 preemption이 가능하다. 그러나 그러한 옵션을 사용하지 않는 커널은 커널 모드에서 preemption이 가능하지 않다. 다만 다음의 경우에 한하여 preemption이 가능하다.

  • CONFIG_PREEMPT_VOLUNTARY 커널 옵션을 사용하면서 cond_resched() 호출 시
  • 명확히 지정하여 schedule() 함수를 호출 시
  • syscall 호출 후 유저 스페이스로 되돌아 갈 때
    • 유저 모드에서는 언제나 preemption이 가능하다. 때문에 syscall 호출하여 커널에서 요청한 서비스를 처리한 후 유저로 돌아갔다 preemption이 일어나면 유저 모드와 커널 모드의 왕래만 한 번 더 반복하게 되므로 overhead가 생길 따름이다. 그래서 유저 스페이스로 돌아가기 전에 preemption 처리를 하는 것이 더 빠른 처리를 할 수 있다.
  • 인터럽트 핸들러를 처리 후 다시 유저 스페이스로 되돌아 갈 때
    • 이 전 syscall 상황과 유사하게 이 상황도 유저 스페이스로 돌아가기 전에 처리해야 더 빠른 처리를 할 수 있다.

 

__schedule()

kernel/sched/core.c

static void __sched __schedule(void)
{
        struct task_struct *prev, *next;
        unsigned long *switch_count;
        struct rq *rq;
        int cpu;

        preempt_disable();
        cpu = smp_processor_id();
        rq = cpu_rq(cpu);
        rcu_note_context_switch();
        prev = rq->curr;

        schedule_debug(prev);

        if (sched_feat(HRTICK))
                hrtick_clear(rq);

        /*
         * Make sure that signal_pending_state()->signal_pending() below
         * can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)
         * done by the caller to avoid the race with signal_wake_up().
         */
        smp_mb__before_spinlock();
        raw_spin_lock_irq(&rq->lock);

        rq->clock_skip_update <<= 1; /* promote REQ to ACT */

        switch_count = &prev->nivcsw;
        if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
                if (unlikely(signal_pending_state(prev->state, prev))) {
                        prev->state = TASK_RUNNING;
                } else {
                        deactivate_task(rq, prev, DEQUEUE_SLEEP);
                        prev->on_rq = 0;

                        /*
                         * If a worker went to sleep, notify and ask workqueue
                         * whether it wants to wake up a task to maintain
                         * concurrency.
                         */
                        if (prev->flags & PF_WQ_WORKER) {
                                struct task_struct *to_wakeup;

                                to_wakeup = wq_worker_sleeping(prev, cpu);
                                if (to_wakeup)
                                        try_to_wake_up_local(to_wakeup);
                        }
                }
                switch_count = &prev->nvcsw;
        }

        if (task_on_rq_queued(prev))
                update_rq_clock(rq);

        next = pick_next_task(rq, prev);
        clear_tsk_need_resched(prev);
        clear_preempt_need_resched();
        rq->clock_skip_update = 0;

        if (likely(prev != next)) {
                rq->nr_switches++;
                rq->curr = next;
                ++*switch_count;

                rq = context_switch(rq, prev, next); /* unlocks the rq */
                cpu = cpu_of(rq);
        } else
                raw_spin_unlock_irq(&rq->lock);

        post_schedule(rq);

        sched_preempt_enable_no_resched();
}

현재 태스크를 슬립시키고 다음 태스크를 선택하여 스케줄한다.

  • 코드 라인 8에서 스케줄 전에 preemtion 되지 않도록 disable 한다.
  • 코드 라인 11에서 per-cpu인 rcu_sched_data.passed_quiesce에 1을 대입하여 rcu 정지 상태에 진입했음을 알린다.
  • 코드 라인 14에서 스케줄 타임에 체크할  항목과 통계를 수행한다.
  • 코드 라인 16~17에서 스케줄 클럭에 high-resolution 타이머를 사용한 경우 hrtick 타이머가 동작중이면 정지시킨다.
  • 코드 라인 27에서 런큐의 clock_skip_update는 RQCF_REQ_SKIP(1) 플래그에서 RQCF_ACT_SKIP(2) 단계로 전환한다.
  • 코드 라인 29에서 기존 태스크의 context 스위치 횟수를 알아온다.
  • 코드 라인 30에서 기존 태스크가 러닝 상태가 아니면서 preemption 카운터 비트 중 PREEMPT_ACTIVE가 설정되지 않은 경우
    • schedule() 함수가 호출되어 진입된 경우 PREEMPT_ACTIVE가 설정되지 않는다.
  • 코드 라인 31~32에서 낮은 확률로 기존 태스크의 시그널 처리가 필요한 경우 태스크 상태를 러닝 상태로 바꾼다.
    • 태스크가 SIGKILL 요청을 받았거나 인터럽터블 상태의 태스크가 시그널 처리를 요청받은 경우
  • 코드 라인 33~34에서 시그널 처리가 필요 없으면 태스크를 deactivation(dequeue) 하고 기존 태스크가 런큐에서 동작하지 않음을 표시한다.
    • DEQUEUE_SLEEP 플래그를 주어 이 태스크가 cfs 런큐에서 완전히 빠져나가는 것이 아니라 다시 엔큐됨을 알린다.
  • 코드 라인 41~47에서 기존 태스크가 워크큐 워커인 경우 슬립시킨다. 깨어난 후 to_wakeup 태스크가 런큐에 없는 경우 엔큐 처리 한다.
  • 코드 라인 51~52에서 기존 태스크가 런큐에 있는 경우 런큐 클럭을 갱신한다.
  • 코드 라인 54~57에서 다음 처리할 태스크를 가져오고 기존 태스크의 리스케줄 요청 플래그를 클리어한다. 런큐의 clock_skip_update는 다시 클리어 단계로 전환한다.
    • x86 아키텍처에서만 clear_preempt_need_resched() 함수를 처리한다.
  • 코드 라인 59~65에서 높은 확률로 다음 처리할 태스크가 기존 태스크가 아닌 경우 런큐의 context 스위치 카운터를 증가시키고 현재 처리하는 태스크를 지정한다. 마지막으로 context 스위칭을 수행한다.
  • 코드 라인 69에서 스케줄 완료 후 처리할 일을 수행한다.
  • 코드 라인 71에서 preempt 카운터를 감소시킨다. 카운터가 0이 되면 preemption이 가능해진다.

 

schedule_debug()

kernel/sched/core.c

/*
 * Various schedule()-time debugging checks and statistics:
 */
static inline void schedule_debug(struct task_struct *prev)
{
#ifdef CONFIG_SCHED_STACK_END_CHECK
        BUG_ON(unlikely(task_stack_end_corrupted(prev)));
#endif                     
        /*
         * Test if we are atomic. Since do_exit() needs to call into
         * schedule() atomically, we ignore that path. Otherwise whine
         * if we are scheduling when we should not.
         */
        if (unlikely(in_atomic_preempt_off() && prev->state != TASK_DEAD))
                __schedule_bug(prev);
        rcu_sleep_check();

        profile_hit(SCHED_PROFILING, __builtin_return_address(0));

        schedstat_inc(this_rq(), sched_count);
}

스케줄 타임에 체크할  항목과 통계를 수행한다.

  • 코드 라인 6~8에서 스택이 손상되었는지 체크한다.
  • 코드 라인 14~15에서 preempt 카운터의 PREEMPT_ACTIVE 비트를 제외한 값이 PREEMPT_CHECK_OFFSET(1)이 아니면서 태스크가 TASK_DEAD 상태가 아니면 “BUG: scheduling while atomic:” 에러 메시지를 출력하고 디버깅을 위해 스택 덤프를 한다.
  • 코드 라인 16에서 rcu sleep을 체크한다.
  • 코드 라인 18에서 SCHED_PROFILING을 동작시킨 경우 수행한다.
  • 코드 라인 20에서 rq->sched_count를 1 증가시킨다.

 

task_stack_end_corrupted()

include/linux/sched.h

#define task_stack_end_corrupted(task) \
                (*(end_of_stack(task)) != STACK_END_MAGIC)

스택의 마지막 경계에 기록해둔 매직 넘버(0x57AC6E9D)가 깨져서 손상되었는지 여부를 알아온다. true(1)=스택 손상

 

hrtick_clear()

kernel/sched/core.c

/*
 * Use HR-timers to deliver accurate preemption points.
 */

static void hrtick_clear(struct rq *rq)
{
        if (hrtimer_active(&rq->hrtick_timer))
                hrtimer_cancel(&rq->hrtick_timer);
}

CONFIG_SCHED_HRTICK 커널 옵션을 사용하여 스케줄 클럭에 high-resolution 타이머를 사용한 경우 hrtick 타이머가 동작중이면 정지시킨다.

 

signal_pending_state()

include/linux/sched.h

static inline int signal_pending_state(long state, struct task_struct *p)
{       
        if (!(state & (TASK_INTERRUPTIBLE | TASK_WAKEKILL)))
                return 0;
        if (!signal_pending(p))
                return 0;
        
        return (state & TASK_INTERRUPTIBLE) || __fatal_signal_pending(p);
}

태스크가 SIGKILL 요청을 받았거나 인터럽터블 상태의 태스크가 시그널 처리를 요청받은 경우 true를 반환한다.

  • 상태가 인터럽터블이면서 wakekill 상태가 아닌 경우 곧바로 false를 반환한다.
  • 태스크가 시그널 펜딩 상태가 아니면 false를 반환한다.
  • 상태가 인터럽터블이거나 요청 태스크로 fatal(SIGKILL) 시그널 요청이 온경우 true를 반환한다.

 

signal_pending()

include/linux/sched.h

static inline int signal_pending(struct task_struct *p)
{       
        return unlikely(test_tsk_thread_flag(p,TIF_SIGPENDING));
}

요청 태스크의 sigpending 플래그 설정 여부를 반환한다.

 

fatal_signal_pending()

include/linux/sched.h

static inline int fatal_signal_pending(struct task_struct *p)
{
        return signal_pending(p) && __fatal_signal_pending(p);
}

요청 태스크로 fatal(SIGKILL) 시그널이 요청되었는지 여부를 반환한다.

 

__fatal_signal_pending()

include/linux/sched.h

static inline int __fatal_signal_pending(struct task_struct *p)
{
        return unlikely(sigismember(&p->pending.signal, SIGKILL));
}

요청 태스크로 SIGKILL 시그널이 요청되었는지 여부를 반환한다.

  • SIGKILL 시그널
    • 태스크를 죽일 떄 요청한다.

 

task_on_rq_queued()

kernel/sched/sched.h

static inline int task_on_rq_queued(struct task_struct *p)
{
        return p->on_rq == TASK_ON_RQ_QUEUED;
}

태스크가 현재 런큐에서 동작중인지 여부를 반환한다.

 

clear_tsk_need_resched()

include/linux/sched.h”

static inline void clear_tsk_need_resched(struct task_struct *tsk)
{
        clear_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
}

요청 태스크에서 리스케줄 요청 플래그를 클리어한다.

 

다음 스케줄할 태스크 선택

pick_next_task()

kernel/sched/core.c

/*
 * Pick up the highest-prio task:
 */
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
        const struct sched_class *class = &fair_sched_class;
        struct task_struct *p;

        /*
         * Optimization: we know that if all tasks are in
         * the fair class we can call that function directly:
         */
        if (likely(prev->sched_class == class &&
                   rq->nr_running == rq->cfs.h_nr_running)) {
                p = fair_sched_class.pick_next_task(rq, prev);
                if (unlikely(p == RETRY_TASK))
                        goto again;

                /* assumes fair_sched_class->next == idle_sched_class */
                if (unlikely(!p))
                        p = idle_sched_class.pick_next_task(rq, prev);

                return p;
        }

again:
        for_each_class(class) {
                p = class->pick_next_task(rq, prev);
                if (p) {
                        if (unlikely(p == RETRY_TASK))
                                goto again;
                        return p;
                }
        }

        BUG(); /* the idle class will always have a runnable task */
}

다음 스케줄할 최우선 순위의 태스크를 알아온다. (stop -> dl -> rt -> fair -> idle 스케줄러 순)

  • 코드 라인 14~15에서 기존 태스크의 스케줄러가 CFS 스케줄러이고 런큐에서 동작중인 태스크 모두가 CFS 스케줄러에서만 동작하는 경우
  • 코드 라인 16~18에서 CFS 스케줄러의 pick_next_task() 함수를 호출하여 CFS 스케줄러에서 가장 빠르게 처리해야 할 태스크를 알아온다. 만일 낮은 확률로 RETRY_TASK 결과를 가져온 경우 again 레이블로 이동한다.
  • 코드 라인 21~22에서 낮은 확률로 태스크가 선택되지 않은 경우 idle 스케줄러로 요청한다.
  • 코드 라인 24에서 선택된 태스크를 리턴한다.
  • 코드 라인 28에서 stop 스케줄러부터 idle 스케줄 클래스까지 순서대로 돌며 다음 태스크를 가져와서 반환한다. 실패하는 경우 마지막 idle 스케줄러까지 반복한다.

 

다음 그림은 런큐에서 태스크가 수행될 때의 스케줄 순서를 보여준다.

  • 마지막 idle-task 스케줄러 이전까지 수행시킬 task가 없는 경우 부트 프로세스 중에 처음 사용했던 idle 태스크가 사용된다.

 

스케줄 마무리

post_schedule()

kernel/sched/core.c

/* rq->lock is NOT held, but preemption is disabled */
static inline void post_schedule(struct rq *rq)
{
        if (rq->post_schedule) {
                unsigned long flags;

                raw_spin_lock_irqsave(&rq->lock, flags);
                if (rq->curr->sched_class->post_schedule)
                        rq->curr->sched_class->post_schedule(rq);
                raw_spin_unlock_irqrestore(&rq->lock, flags);

                rq->post_schedule = 0;
        }
}

런큐에 post 스케줄이 설정된 경우  현재 태스크에 해당하는 클래스의 post_schedule()을 호출한다.

  • 다음 2개의 스케줄러에 (*post_schedule) 후크 구현이 되어 있다.
    • post_schedule_dl()
      • 현재 런큐에서 동작중인 2개 이상의 dl 태스크들 중 현재 비실행중인 dl 태스크들을 다른 cpu에서 선점하여 실행시킬 수 있게한다.
    • post_schedule_rt()
      • 현재 런큐에서 동작중인 2개 이상의 rt 태스크들 중 현재 비실행중인 rt 태스크들을 다른 cpu에 선점하여 실행시킬 수 있게한다.

 

sched_preempt_enable_no_resched()

include/linux/preempt.h

#define sched_preempt_enable_no_resched() \
do { \
        barrier(); \
        preempt_count_dec(); \
} while (0)

preempt 카운터를 1 감소시킨다.

 

Context Switch

다음과 같은 이름으로도 불리고 동일한 동작을 의미한다. (Interrupt Context Switch는 별개)

  • Process Context Switch
  • Thread Context Switch
  • Task Context Switch
  • CPU Context Switch

 

context_switch()

kernel/sched/core.c

/*
 * context_switch - switch to the new MM and the new thread's register state.
 */
static inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
               struct task_struct *next)
{
        struct mm_struct *mm, *oldmm;

        prepare_task_switch(rq, prev, next);

        mm = next->mm;
        oldmm = prev->active_mm;
        /*
         * 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);

        if (!mm) {
                next->active_mm = oldmm;
                atomic_inc(&oldmm->mm_count);
                enter_lazy_tlb(oldmm, next);
        } else
                switch_mm(oldmm, mm, next);

        if (!prev->mm) {
                prev->active_mm = NULL;
                rq->prev_mm = oldmm;
        }
        /*
         * Since the runqueue lock will be released by the next
         * task (which is an invalid locking op but in the case
         * of the scheduler it's an obvious special-case), so we
         * do an early lockdep release here:
         */
        spin_release(&rq->lock.dep_map, 1, _THIS_IP_);

        context_tracking_task_switch(prev, next);
        /* Here we just switch the register state and the stack. */
        switch_to(prev, next, prev);
        barrier();

        return finish_task_switch(prev);
}

새로운 태스크로 context 스위칭한다. 만일 새로운 태스크가 유저 태스크인 경우 가상 공간을 바꾸기 위해 mm 스위칭도 한다.

  • 코드 라인 10에서 다음 태스크로 context 스위치하기 전에 할 일을 준비한다.
  • 코드 라인 19에서 context 스위치 직전에 아키텍처에서 할 일을 수행한다.
    • 현재 x86 아키텍처만 수행한다.
  • 코드 라인 21~25에서 다음 태스크의 mm이 없는 경우 즉, 다음 태스크가 커널 태스크인 경우 기존 태스크의 active_mm을 사용한다. 그런 후 기존 태스크의 mm 카운터를 1 증가시키고 lazy tlb 모드로 진입한다.
    • arm과 arm64 아키텍처는 lazy_tlb 모드를 사용하지 않는다.
  • 코드 라인 26~27에서 다음 태스크가 유저 태스크인 경우 다음 태스크가 사용하는 가상 공간을 사용하기 위해 mm 스위칭을 한다.
    • mm 스위칭을 위해 관련 CONTEXTIDR 및 TTBR0 레지스터를 새 태스크의 mm을 사용하여 설정한다. 단 인터럽트 처리 중인 경우 mm 스위칭을 지연시킨다.
  • 코드 라인 29~32에서 이전 태스크의 mm이 없는 경우 즉, 이전 태스크가 커널 태스크인 경우 active_mm에 null을 대입한다. 런큐의 prev_mm에 이전 태스크의 active_mm을 대입한다.
  • 코드 라인 41에서 디버깅을 위해 context 트래킹 정보를 기록한다.
  • 코드 라인 43에서 다음 태스크로 context 스위칭을 수행한다.
  • 코드 라인 46에서 context 스위치 완료 후 할 일을 수행한다

 

다음 그림과 같이 6개의 초기 태스크가 생성되었다고 가정한다.

 

다음 그림과 같이 초기 태스크인 init_task부터 각 커널 태스크들과 유저 태스크들이 스케줄링 되면서 active_mm이 변화하는 모습과 각 별표에서 mm 스위칭이 발생하는 것을 알 수 있다.

  • 참고로  가장 주소 환경은 처음 init_task를 제외하고 항상 유저 태스크인 경우만 mm 스위칭이 발생하는데 이 때 mm을 사용한다.
  • 커널 태스크로 전환된 경우 이전에 사용했던 유저 가상 주소를 active_mm을 통해 전달받아 사용한다.
    • 처음 init_mm 제외

 

Context 스위치 전에 준비할 일과 종료 후 할 일

prepare_task_switch()

kernel/sched/core.c

/**
 * prepare_task_switch - prepare to switch tasks
 * @rq: the runqueue preparing to switch
 * @prev: the current task that is being switched out
 * @next: the task we are going to switch to.
 *
 * This is called with the rq lock held and interrupts off. It must
 * be paired with a subsequent finish_task_switch after the context
 * switch.
 *
 * prepare_task_switch sets up locking and calls architecture specific
 * hooks.
 */
static inline void 
prepare_task_switch(struct rq *rq, struct task_struct *prev,
                    struct task_struct *next)
{
        trace_sched_switch(prev, next);
        sched_info_switch(rq, prev, next);
        perf_event_task_sched_out(prev, next);
        fire_sched_out_preempt_notifiers(prev, next);
        prepare_lock_switch(rq, next);
        prepare_arch_switch(next);
}

다음 태스크로 context 스위치하기 전에 할일을 준비한다.

  • 코드 라인 19에서 디버그용 스케줄 정보를 기록한다.
  • 코드 라인 20에서 디버그용 perf 이벤트에 대한 출력을 한다. (PERF_COUNT_SW_CONTEXT_SWITCHES)
  • 코드 라인 21에서 curr->preempt_notifiers에 등록된 notifier들에 대해 ops->sched_out() 함수를 호출한다.
  • 코드 라인 22에서 다음 태스크가 런큐에서 동작함을 알린다. (next->on_cpu = 1)
  • 코드 라인 23에서 아키텍처에서 지원하는 경우 context 스위치 전에 할 일을 수행하게 한다.
    • arm, arm64 아키텍처는 해당 사항 없다.

finish_task_switch()

kernel/sched/core.c

/**
 * finish_task_switch - clean up after a task-switch
 * @prev: the thread we just switched away from.
 *
 * finish_task_switch must be called after the context switch, paired
 * with a prepare_task_switch call before the context switch.
 * finish_task_switch will reconcile locking set up by prepare_task_switch,
 * and do any other architecture-specific cleanup actions.
 *
 * Note that we may have delayed dropping an mm in context_switch(). If
 * so, we finish that here outside of the runqueue lock. (Doing it
 * with the lock held can cause deadlocks; see schedule() for
 * details.)
 *
 * The context switch have flipped the stack from under us and restored the
 * local variables which were saved when this task called schedule() in the
 * past. prev == current is still correct but we need to recalculate this_rq
 * because prev may have moved to another CPU.
 */
static struct rq *finish_task_switch(struct task_struct *prev)
        __releases(rq->lock)
{
        struct rq *rq = this_rq();
        struct mm_struct *mm = rq->prev_mm;
        long prev_state;

        rq->prev_mm = NULL;

        /*
         * A task struct has one reference for the use as "current".
         * If a task dies, then it sets TASK_DEAD in tsk->state and calls
         * schedule one last time. The schedule call will never return, and
         * the scheduled task must drop that reference.
         * The test for TASK_DEAD must occur while the runqueue locks are
         * still held, otherwise prev could be scheduled on another cpu, die
         * there before we look at prev->state, and then the reference would
         * be dropped twice.
         *              Manfred Spraul <manfred@colorfullife.com>
         */
        prev_state = prev->state;
        vtime_task_switch(prev);
        finish_arch_switch(prev);
        perf_event_task_sched_in(prev, current);
        finish_lock_switch(rq, prev);
        finish_arch_post_lock_switch();

        fire_sched_in_preempt_notifiers(current);
        if (mm)
                mmdrop(mm);
        if (unlikely(prev_state == TASK_DEAD)) {
                if (prev->sched_class->task_dead)
                        prev->sched_class->task_dead(prev);

                /*
                 * Remove function-return probe instances associated with this
                 * task and put them back on the free list.
                 */
                kprobe_flush_task(prev);
                put_task_struct(prev);
        }

        tick_nohz_task_switch(current);
        return rq;
}

context 스위치 완료 후 할 일을 수행한다. (prepare_task_switch() 함수와 한 쌍을 이룬다.)

  • 코드 라인 41에서 s390 아키텍처에서만 vtime 관련하여 수행한다.
  • 코드 라인 42에서 기존 태스크의 스위칭 완료 시 아키텍처별로 수행할 일을 한다.
  • 코드 라인 43에서 디버깅을 위해 perf event 출력을 한다.
  • 코드 라인 47에서 스케줄 in 되는 경우 현재 태스크의 preempt_notifiers 체인 리스트에 등록된 notifier  함수를 호출한다.
  • 코드 라인 48~49에서 런큐의 prev_mm이 있는 경우 mm을 사용하지 않는다. (참조 카운터가 0이되면 할당 해제한다.)
  • 코드 라인 50~60에서 낮은 확률로 기존 태스크 상태가 TASK_DEAD 인 경우 기존 태스크를 사용하지 않는다. (참조 카운터가 0이되면 할당 해제한다) 만일 기존 태스크의 스케줄러에 (*task_dead)가 준비된 경우 호출한다.
    • dl 스케줄러를 사용하는 경우 task_dead_dl() 함수를 호출하여 total_bw에서 dl_bw를 감소시키고 dl 타이머를 중지시킨다.
  • 코드 라인 62에서 시스템이 nohz full이 지원되어 동작하고 있는 경우 nohz full 상태를 체크하여 필요 시 다시 tick 스케줄링을 재개한다.
/*
 * For v7 SMP cores running a preemptible kernel we may be pre-empted
 * during a TLB maintenance operation, so execute an inner-shareable dsb
 * to ensure that the maintenance completes in case we migrate to another
 * CPU.
 */
#if defined(CONFIG_PREEMPT) && defined(CONFIG_SMP) && defined(CONFIG_CPU_V7)
#define finish_arch_switch(prev)        dsb(ish)
#endif

armv7 아키텍처를 사용한 SMP 시스템이 CONFIG_PREEMPT preemption 모델을 사용하는 경우 inner-share 영역의 지연된 캐시, TLB 및 BP 조작 작업을 완료할 때까지 대기한다.

 

fire_sched_in_preempt_notifiers()

kernel/sched/core.c

static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
{
        struct preempt_notifier *notifier;

        hlist_for_each_entry(notifier, &curr->preempt_notifiers, link)
                notifier->ops->sched_in(notifier, raw_smp_processor_id());
}

스케줄 in 되는 경우 현재 태스크의 preempt_notifiers 체인 리스트에 등록된 notifier  함수를 호출한다.

다음 그림은 현재 태스크의 preempt_notifiers 체인리스트에 virt/kvm/kvm_main.c – vcpu_load() 함수가 등록되어 호출되는 것을 보여준다.

 

mmdrop()

include/linux/sched.h

/* mmdrop drops the mm and the page tables */
static inline void mmdrop(struct mm_struct * mm)
{
        if (unlikely(atomic_dec_and_test(&mm->mm_count)))
                __mmdrop(mm);
}

메모리 디스크립터 mm의 참조 카운터를 감소시키고 0인 경우 mm을 할당 해제한다.

 

__mmdrop()

kernel/fork.c

/*
 * Called when the last reference to the mm
 * is dropped: either by a lazy thread or by 
 * mmput. Free the page directory and the mm.
 */     
void __mmdrop(struct mm_struct *mm)
{
        BUG_ON(mm == &init_mm);
        mm_free_pgd(mm);
        destroy_context(mm);
        mmu_notifier_mm_destroy(mm);
        check_mm(mm);
        free_mm(mm);
}
EXPORT_SYMBOL_GPL(__mmdrop);

메모리 디스크립터 mm을 할당 해제한다.

  • 코드 라인 9에서 mm에 연결된 페이지 테이블을 할당 해제한다.
  • 코드 라인 10에서 mm의 context 정보를 해제한다.
    • arm 아키텍처는 아무것도 수행하지 않는다.
  • 코드 라인 11에서 mm->mmu_notifier_mm을 할당 해제한다.
  • 코드 라인 12에서 mm에 문제가 있는지 체크하고 문제가 있는 경우 alert 메시지를 출력한다
  • 코드 라인 13에서 mm을 할당 해제한다.

 

mm_free_pgd()

kernel/fork.c

static inline void mm_free_pgd(struct mm_struct *mm)
{
        pgd_free(mm, mm->pgd); 
}

 

check_mm()

kernel/fork.c

static void check_mm(struct mm_struct *mm)
{       
        int i;
        
        for (i = 0; i < NR_MM_COUNTERS; i++) {
                long x = atomic_long_read(&mm->rss_stat.count[i]);

                if (unlikely(x))
                        printk(KERN_ALERT "BUG: Bad rss-counter state "
                                          "mm:%p idx:%d val:%ld\n", mm, i, x);
        }

        if (atomic_long_read(&mm->nr_ptes))
                pr_alert("BUG: non-zero nr_ptes on freeing mm: %ld\n",
                                atomic_long_read(&mm->nr_ptes));
        if (mm_nr_pmds(mm))
                pr_alert("BUG: non-zero nr_pmds on freeing mm: %ld\n",
                                mm_nr_pmds(mm));

#if defined(CONFIG_TRANSPARENT_HUGEPAGE) && !USE_SPLIT_PMD_PTLOCKS
        VM_BUG_ON_MM(mm->pmd_huge_pte, mm);
#endif 
}

mm에 문제가 있는지 체크하고 문제가 있는 경우 alert 메시지를 출력한다.

  • 코드 라인 5~11에서 3개의 MM 카운터 수만큼 루프를 돌며 rss_stat 카운터 값이 0 보다 큰 경우 alert 메시지를 출력한다.
  • 코드 라인 13~15에서 mm->nr_ptes가 0 보다 큰 경우 alert 메시지를 출력한다.
  • 코드 라인 16~18에서 mm에 pmds가 0 보다 큰 경우 alert 메시지를 출력한다.
  • 코드 라인 20~22에서 mm->pmd_huge_pte 수가 0 보다 큰 경우 emergency 메시지를 덤프한다.

 

include/linux/mm_types.h

enum {
        MM_FILEPAGES,
        MM_ANONPAGES,
        MM_SWAPENTS,
        NR_MM_COUNTERS
};

 

free_mm()

kernel/fork.c

#define free_mm(mm)     (kmem_cache_free(mm_cachep, (mm)))

mm 슬랩 캐시에 메모리 디스크립터 mm을 할당 해제 한다.

 

mm 스위칭

switch_mm()

arch/arm/include/asm/mmu_context.h

/*
 * This is the actual mm switch as far as the scheduler
 * is concerned.  No registers are touched.  We avoid
 * calling the CPU specific function when the mm hasn't
 * actually changed.
 */
static inline void
switch_mm(struct mm_struct *prev, struct mm_struct *next,
          struct task_struct *tsk)
{
#ifdef CONFIG_MMU
        unsigned int cpu = smp_processor_id();

        /*
         * __sync_icache_dcache doesn't broadcast the I-cache invalidation,
         * so check for possible thread migration and invalidate the I-cache
         * if we're new to this CPU.
         */
        if (cache_ops_need_broadcast() &&
            !cpumask_empty(mm_cpumask(next)) &&
            !cpumask_test_cpu(cpu, mm_cpumask(next)))
                __flush_icache_all();

        if (!cpumask_test_and_set_cpu(cpu, mm_cpumask(next)) || prev != next) {
                check_and_switch_context(next, tsk);
                if (cache_is_vivt())
                        cpumask_clear_cpu(cpu, mm_cpumask(prev));
        }
#endif
}

지정한 태스크의 가상 주소로 전환하기 위해 mm 스위치한다.

  • 코드 라인 19~22에서 캐시 작업에 브로드캐스트가 필요한 아키텍처이고 태스크에 대한 cpu 비트맵이 비어 있지 않고 해당 cpu 비트만 클리어 되어 있는 경우 명령 캐시 전체를 flush 한다.
    • arm 아키텍처에서 UP 시스템이나 armv7 이상인 경우 해당 사항 없다.
  • 코드 라인 24~25에서 태스크에 대한 cpu 비트맵이 클리어된 상태이거나 다음 태스크에 사용할 mm이 기존 태스크의 mm과 동일하지 않은 경우 mm 스위칭을 수행한다.
  • 코드 라인 26~27에서 캐시가 vivt 타입인 경우 기존 태스크에 대한 cpu 비트맵에서 현재 cpu 비트를 클리어한다.

 

cache_ops_need_broadcast()

arch/arm/include/asm/smp_plat.h

#if !defined(CONFIG_SMP) || __LINUX_ARM_ARCH__ >= 7
#define cache_ops_need_broadcast()      0
#else
static inline int cache_ops_need_broadcast(void)
{
        if (!is_smp())
                return 0;

        return ((read_cpuid_ext(CPUID_EXT_MMFR3) >> 12) & 0xf) < 1;
}
#endif

캐시 작업에 브로드캐스트가 필요한 아키텍처인지 여부를 알아온다. true(1)=브로드캐스트 필요

  • 다음과 같이 armv6 이하 SMP 아키텍처에서 브로드캐스트가 필요한 SMP 아키텍처가 있다.
  • MMFR3.Maintenance broadcast가  레지스터는 다음과 같다.
    • 0b0000: 캐시, TLB 및 BP 조작 모두 local cpu에만 적용된다.
    • 0b0001: 캐시, BP 조작은 명령에 따라 share cpu들에 적용되지만 TLB는 local cpu에만 적용된다.
    • 0b0010: 캐시, TLB 및 BP 조작 모두 명령에 따라 share cpu들에 적용된다.

 

check_and_switch_context()

CONFIG_CPU_HAS_ASID 커널 옵션을 디폴트로 사용할 수 있는 armv7 아키텍처는 아래 코드를 사용한다.

arch/arm/mm/context.c

void check_and_switch_context(struct mm_struct *mm, struct task_struct *tsk)
{                                          
        unsigned long flags;
        unsigned int cpu = smp_processor_id();
        u64 asid;
                
        if (unlikely(mm->context.vmalloc_seq != init_mm.context.vmalloc_seq))
                __check_vmalloc_seq(mm);

        /*
         * We cannot update the pgd and the ASID atomicly with classic
         * MMU, so switch exclusively to global mappings to avoid
         * speculative page table walking with the wrong TTBR.
         */
        cpu_set_reserved_ttbr0();

        asid = atomic64_read(&mm->context.id);
        if (!((asid ^ atomic64_read(&asid_generation)) >> ASID_BITS)
            && atomic64_xchg(&per_cpu(active_asids, cpu), asid))
                goto switch_mm_fastpath;

        raw_spin_lock_irqsave(&cpu_asid_lock, flags);
        /* Check that our ASID belongs to the current generation. */
        asid = atomic64_read(&mm->context.id);
        if ((asid ^ atomic64_read(&asid_generation)) >> ASID_BITS) {
                asid = new_context(mm, cpu);
                atomic64_set(&mm->context.id, asid);
        }
                
        if (cpumask_test_and_clear_cpu(cpu, &tlb_flush_pending)) {
                local_flush_bp_all();
                local_flush_tlb_all();
        }
 
        atomic64_set(&per_cpu(active_asids, cpu), asid);
        cpumask_set_cpu(cpu, mm_cpumask(mm));
        raw_spin_unlock_irqrestore(&cpu_asid_lock, flags);

switch_mm_fastpath:
        cpu_switch_mm(mm->pgd, mm);
}

mm 스위칭을 위해 관련 CONTEXTIDR 및 TTBR0 레지스터를 새 태스크의 mm을 사용하여 설정한다. 단 인터럽트 처리 중인 경우 mm 스위칭을 지연시킨다.

  • 코드 라인 7~8에서 init_mm의 vmalloc 정보가 갱신되어 현재 태스크의 vmalloc 시퀀스와 다른 경우 init_mm의 페이지 테이블 중 vmalloc 주소 공간에 해당하는 매핑 테이블 엔트리들만 현재 태스크의 vmalloc 영역을 가리키는 엔트리에 복사한다.
  • 코드 라인 15에서 classic MMU를 사용하면서 atomic하게 유저 페이지 테이블 지정 및 ASID 설정을 atomic하게 할 수 없다. 따라서 먼저 커널 페이지 테이블로 전환한다. 이렇게 커널 페이지 테이블로 전환하면 유저 페이지와 관계 없는 글로벌 매핑 페이지만을 사용하므로 ASID의 효력이 없게하여 잘못된 페이지 테이블 워킹을 방지하는 효과가 있다.
  • 코드 라인 17~20에서 mm 스위칭할 태스크의 32bit asid 값을 읽어 asid의 256 발급(generation) 단위(0, 0x100, 0x200, 0x300, …)에 속하면 switch_mm_fast로 이동한다.
    • asid를 atomic하게 읽어온 값의 최하위 8비트를 제외한 값이 최근에 발급한 대역과 같은 경우 fastpath 처리한다.
    • 예) asid_generation=0x300, mm->context.id=0x340
      • 각각 8비트를 우측 shift한 결과가 같으므로 fastpath
    • 예) asid_generation=0x400, mm->context.id=0x3f0
      • 각각 8비트를 우측 shift한 결과가 다르므로 slowpath
  • 코드 라인 22~28에서 스핀락을 걸고 다시 한 번 asid 값을 읽었을 때 최하위 8비트를 제외한 값이 최근에 발급한 번호 대역과 다른 경우 새로운 asid를 발급해온다.
    • 참고로 태스크가 생성될 때 마다 태스크의 context.id는 1씩 증가된다.
    • asid_generation은 0부터 시작하여 태스크가 0x100번대의 asid가 출현하는 경우 0x100씩 증가한다.
  • 코드 라인 30~33에서 현재 cpu에 대해 tlb 플러시가 펜딩된 상태인 경우 플러시 처리를 수행한다.
  • 코드 라인 35~37에서 현재 cpu의 active_asids에 asid 값을 저장해두고 mm->cpu_vm_mask_var에 현재 cpu 비트를 설정한다.
  • 코드 라인 40에서 mm 스위칭을 수행한다.
    • TTBR0 레지스터에 pgd를 대입하고 CONTEXTIDR에서 8비트의 asid 값만 변경한다.

 

cpu_set_reserved_ttbr0()

arch/arm/mm/context.c

static void cpu_set_reserved_ttbr0(void)
{
        u32 ttb;
        /*
         * Copy TTBR1 into TTBR0.
         * This points at swapper_pg_dir, which contains only global
         * entries so any speculative walks are perfectly safe.
         */
        asm volatile(
        "       mrc     p15, 0, %0, c2, c0, 1           @ read TTBR1\n"
        "       mcr     p15, 0, %0, c2, c0, 0           @ set TTBR0\n"
        : "=r" (ttb));
        isb();
}

커널 페이지 테이블(pgd)의 물리 주소가 담겨 있는 TTBR1 레지스터를 읽어 TTBR0에 복사한다.

 

CONFIG_CPU_HAS_ASID 커널 옵션을 사용하지 않는 경우의 코드이다.

arch/arm/include/asm/mmu_context.h

static inline void check_and_switch_context(struct mm_struct *mm,
                                            struct task_struct *tsk)
{
        if (unlikely(mm->context.vmalloc_seq != init_mm.context.vmalloc_seq))
                __check_vmalloc_seq(mm);

        if (irqs_disabled())
                /*
                 * cpu_switch_mm() needs to flush the VIVT caches. To avoid
                 * high interrupt latencies, defer the call and continue
                 * running with the old mm. Since we only support UP systems
                 * on non-ASID CPUs, the old mm will remain valid until the
                 * finish_arch_post_lock_switch() call.
                 */
                mm->context.switch_pending = 1;
        else
                cpu_switch_mm(mm->pgd, mm);
}

mm 스위칭을 위해 관련 CONTEXTIDR 및 TTBR0 레지스터를 새 태스크의 mm을 사용하여 설정한다. 단 인터럽트 처리 중인 경우 mm 스위칭을 지연시킨다.

  • 코드 라인 4~5에서 init_mm의 vmalloc 정보가 갱신되어 현재 태스크의 vmalloc 시퀀스와 다른 경우 init_mm의 페이지 테이블 중 vmalloc 주소 공간에 해당하는 매핑 테이블 엔트리들만 현재 태스크의 vmalloc 영역을 가리키는 엔트리에 복사한다.
  • 코드 라인 7~15에서 인터럽트 처리 중인 경우 mm 스위칭을 지연시킨다.
  • 코드 라인 16~17에서 mm 스위칭을 위해 CONTEXTIDR.ASID를 mm->context.id로 갱신하고 TTBR0 레지스터에는 pgd_phys + TTB 속성 플래그를 기록한다.

 

새로운 asid 발급

new_context()

arch/arm/mm/context.c

static u64 new_context(struct mm_struct *mm, unsigned int cpu)
{
        static u32 cur_idx = 1;
        u64 asid = atomic64_read(&mm->context.id);
        u64 generation = atomic64_read(&asid_generation);

        if (asid != 0) {
                /*
                 * If our current ASID was active during a rollover, we
                 * can continue to use it and this was just a false alarm.
                 */
                if (is_reserved_asid(asid))
                        return generation | (asid & ~ASID_MASK);

                /*
                 * We had a valid ASID in a previous life, so try to re-use
                 * it if possible.,
                 */
                asid &= ~ASID_MASK;
                if (!__test_and_set_bit(asid, asid_map))
                        goto bump_gen;
        }

        /*
         * Allocate a free ASID. If we can't find one, take a note of the
         * currently active ASIDs and mark the TLBs as requiring flushes.
         * We always count from ASID #1, as we reserve ASID #0 to switch
         * via TTBR0 and to avoid speculative page table walks from hitting
         * in any partial walk caches, which could be populated from
         * overlapping level-1 descriptors used to map both the module
         * area and the userspace stack.
         */
        asid = find_next_zero_bit(asid_map, NUM_USER_ASIDS, cur_idx);
        if (asid == NUM_USER_ASIDS) {
                generation = atomic64_add_return(ASID_FIRST_VERSION,
                                                 &asid_generation);
                flush_context(cpu);
                asid = find_next_zero_bit(asid_map, NUM_USER_ASIDS, 1);
        }

        __set_bit(asid, asid_map);
        cur_idx = asid;

bump_gen:
        asid |= generation;
        cpumask_clear(mm_cpumask(mm));
        return asid;
}

현재 asid 발급 대역에서 태스크에 사용할 새로운 asid를 찾아 반환한다. 만일 256개를 모두 사용한 경우 tlb 플러싱을 한 후 새로운 대역에서 발급한다. 대역은 256 단위로 증가한다.

  • 코드 라인 7~22에서 256개로 구성된 asid_map에서 asid를 256으로 나눈 나머지에 해당하는 해당 비트가 비어있어 배치가 가능한 asid인 경우 해당 비트를
    설정하고 bump_gen으로 이동한다.
  • 코드 라인 33에서 256개의 asid 비트맵 중에서 비어있는 번호를 찾는다.
  • 코드 라인 34~39에서 256개가 모두 할당되어 비어 있는 번호가 없으면 최근 발급한 번호에 256을 더해 새로운 대역번호를 설정한다.  그런 후 tlb 및 icache(vivt 타입만) 플러싱을 수행한다.
    • 태스크가 생성될 때 마다 커널은 32비트를 사용하는 asid를 1씩 증가하여 구분한다. 그러나 armv7 아키텍처는 asid의 식별에 8비트만 사용가능하다. 따라서 asid의 대역이 바뀌는 경우 구분할 수 없기 때문에 tlb 캐시와 vivt 캐시 타입을 사용하는 icache를 모두 플러쉬하고 새로운 대역에서 시작하게 한다.

 

cpu_switch_mm()

arch/arm/include/asm/proc-fns.h

#define cpu_switch_mm(pgd,mm) cpu_do_switch_mm(virt_to_phys(pgd),mm)

 

cpu_do_switch_mm()

arch/arm/include/asm/proc-fns.h & arch/arm/include/asm/glue-proc.h

#ifdef MULTI_CPU
#define cpu_do_switch_mm                processor.switch_mm
#else
#define cpu_do_switch_mm                __glue(CPU_NAME,_switch_mm)
#endif
  • armV7 아키텍처는 MULTI_CPU를 사용하고 processor.switch_mm 후크는 cpu_v7_switch_mm() 함수를 가리킨다.

 

cpu_v7_switch_mm()

arch/arm/mm/proc-v7-2level.S

/*
 *      cpu_v7_switch_mm(pgd_phys, tsk)
 *
 *      Set the translation table base pointer to be pgd_phys
 *
 *      - pgd_phys - physical address of new TTB
 *
 *      It is assumed that:
 *      - we are not using split page tables
 */
ENTRY(cpu_v7_switch_mm)
#ifdef CONFIG_MMU
        mov     r2, #0
        mmid    r1, r1                          @ get mm->context.id
        ALT_SMP(orr     r0, r0, #TTB_FLAGS_SMP)
        ALT_UP(orr      r0, r0, #TTB_FLAGS_UP)
#ifdef CONFIG_ARM_ERRATA_430973
        mcr     p15, 0, r2, c7, c5, 6           @ flush BTAC/BTB
#endif
#ifdef CONFIG_PID_IN_CONTEXTIDR
        mrc     p15, 0, r2, c13, c0, 1          @ read current context ID
        lsr     r2, r2, #8                      @ extract the PID 
        bfi     r1, r2, #8, #24                 @ insert into new context ID
#endif
#ifdef CONFIG_ARM_ERRATA_754322
        dsb     
#endif
        mcr     p15, 0, r1, c13, c0, 1          @ set context ID
        isb
        mcr     p15, 0, r0, c2, c0, 0           @ set TTB 0
        isb
#endif
        bx      lr
ENDPROC(cpu_v7_switch_mm)

mm 스위칭을 위해 CONTEXTIDR.ASID를 mm->context.id로 갱신하고 TTBR0 레지스터에는 pgd_phys + TTB 속성 플래그를 기록한다.

  • 코드 라인 14에서 mm->context.id 값을 읽어 r1에 대입한다.
  • 코드 라인 15에서 pgd 물리 주소가 담긴 r0에 TTB 플래그를 추가한다.
  • 코드 라인 16~18에서 Cortex-A8 (r1p0..r1p2) 칩의 erratum을 위해 BP(Branch Prediction)를 flush한다.
  • 코드 라인 19~23에서 CONTEXTIDR 레지스터값 >> 8 비트한 값이 PROCID이고 이 값을 r1의 상위 24비트에 대입한다.
    • r1 bits[31:8] <- CONTEXTIDR.PROCID
  • 코드 라인 24~26에서 ARMv7 아키텍처에서 ASID 스위칭을 하는 경우 잘못된 MMU 변환이 가능하여 erratum을 위해 dsb 명령을 수행한다.
  • 코드 라인 27~28에서 CONTEXTIDR에서 ASID 값이 교체된 r1 값을 CONTEXTIDR에 기록하고 isb 명령을 통해 명령 파이프를 비운다.
  • 코드 라인 29~30에서 TTBR0 레지스터에 pgd 주소 및 TTB 플래그가 담긴 r0 레지스터를 기록하고 isb 명령을 통해 명령 파이프를 비운다.

 

arch/arm/mm/proc-v7-2level.S

/* PTWs cacheable, inner WB not shareable, outer WB not shareable */
#define TTB_FLAGS_UP    TTB_IRGN_WB|TTB_RGN_OC_WB
          
/* PTWs cacheable, inner WBWA shareable, outer WBWA not shareable */
#define TTB_FLAGS_SMP   TTB_IRGN_WBWA|TTB_S|TTB_NOS|TTB_RGN_OC_WBWA
  • TTBR0 레지스터에 pgd 물리 주소를 지정할 때 위의 플래그와 같이 지정하여 사용한다.

 

#define TTB_S           (1 << 1)
#define TTB_RGN_NC      (0 << 3)
#define TTB_RGN_OC_WBWA (1 << 3)
#define TTB_RGN_OC_WT   (2 << 3)
#define TTB_RGN_OC_WB   (3 << 3)
#define TTB_NOS         (1 << 5)
#define TTB_IRGN_NC     ((0 << 0) | (0 << 6))
#define TTB_IRGN_WBWA   ((0 << 0) | (1 << 6))
#define TTB_IRGN_WT     ((1 << 0) | (0 << 6))
#define TTB_IRGN_WB     ((1 << 0) | (1 << 6)) 

 

다음 그림은  armv7 아키텍처의 context 스위칭 시 CONTEXTIDR 레지스터와 TTBR0 레지스터가 변경되는 모습을 보여준다

 

mmid 매크로

arch/arm/mm/proc-macros.S

/*
 * mmid - get context id from mm pointer (mm->context.id)
 * note, this field is 64bit, so in big-endian the two words are swapped too.
 */
        .macro  mmid, rd, rn
#ifdef __ARMEB__
        ldr     \rd, [\rn, #MM_CONTEXT_ID + 4 ]
#else
        ldr     \rd, [\rn, #MM_CONTEXT_ID]
#endif
        .endm

mm->context.id를 rd에 반환한다. (rn에 mm)

 

참고로 다음 코드는 arm64에서의 mm 스위칭 코드이다. CONTEXTIDR 없이 64비트의 ttbr0_el1 레지스터에 페이지 테이블의 물리주소(pgd_phys)를 대입하되 최상위 16비트는 asid를 지정한다. (16비트의 asid + 48비트의 pgd_phys)

arch/arm64/mm/proc.S

/*
 *      cpu_do_switch_mm(pgd_phys, tsk)
 *
 *      Set the translation table base pointer to be pgd_phys.
 *
 *      - pgd_phys - physical address of new TTB
 */
ENTRY(cpu_do_switch_mm)
        mmid    x1, x1                          // get mm->context.id
        bfi     x0, x1, #48, #16                // set the ASID
        msr     ttbr0_el1, x0                   // set TTBR0
        isb
alternative_if_not ARM64_WORKAROUND_CAVIUM_27456
        ret
        nop
        nop
        nop
alternative_else
        ic      iallu
        dsb     nsh
        isb
        ret
alternative_endif
ENDPROC(cpu_do_switch_mm)

 

 

mm 스위칭 전 vmalloc 복제

__check_vmalloc_seq()

arch/arm/mm/ioremap.c

void __check_vmalloc_seq(struct mm_struct *mm) 
{
        unsigned int seq;

        do {
                seq = init_mm.context.vmalloc_seq;
                memcpy(pgd_offset(mm, VMALLOC_START),
                       pgd_offset_k(VMALLOC_START),
                       sizeof(pgd_t) * (pgd_index(VMALLOC_END) -
                                        pgd_index(VMALLOC_START)));
                mm->context.vmalloc_seq = seq;
        } while (seq != init_mm.context.vmalloc_seq);
}

init_mm의 vmalloc 정보가 갱신되었기 때문에 다음 태스크로 스위칭 되기 전에 init_mm->pgd의 vmalloc 엔트리들을 mm->pgd로 갱신한다.

  • 코드 라인 5에서 init_mm의 vmalloc 시퀀스 번호를 알아온다.
  • 코드 라인 6~9에서 vmalloc address space에 해당하는 init_mm의 페이지 테이블 엔트리들을 mm의 페이지 테이블로 복사한다.
  • 코드 라인 10~11에서 vmalloc 시퀀스 번호도 갱신한다. 이렇게 갱신하는 동안 또 변경이 일어나면 루프를 돌며 다시 갱신한다.

 

다음 그림은 갱신된 커널의 vmalloc 엔트리들을 내 태스크의 페이지 테이블로 갱신하는 모습을 보여준다.

 

context 스위칭

switch_to()

arch/arm/include/asm/switch_to.h

/*
 * switch_to(prev, next) should switch from task `prev' to `next'
 * `prev' will never be the same as `next'.  schedule() itself
 * contains the memory barrier to tell GCC not to cache `current'.
 */
#define switch_to(prev,next,last)                                       \
do {                                                                    \
        last = __switch_to(prev,task_thread_info(prev), task_thread_info(next));        \
} while (0)

cpu context 스위칭을 통해 다음 스레드로 전환한다.

 

다음 그림과 같이 태스크가 생성되는 경우 할당되는 context 관련된 컴포넌트들을 알아본다.

 

__switch_to()

arch/arm/kernel/entry-armv.S

/*
 * Register switch for ARMv3 and ARMv4 processors
 * r0 = previous task_struct, r1 = previous thread_info, r2 = next thread_info
 * previous and next are guaranteed not to be the same.
 */
ENTRY(__switch_to)
 UNWIND(.fnstart        )
 UNWIND(.cantunwind     )
        add     ip, r1, #TI_CPU_SAVE
 ARM(   stmia   ip!, {r4 - sl, fp, sp, lr} )    @ Store most regs on stack
 THUMB( stmia   ip!, {r4 - sl, fp}         )    @ Store most regs on stack
 THUMB( str     sp, [ip], #4               )
 THUMB( str     lr, [ip], #4               )
        ldr     r4, [r2, #TI_TP_VALUE]
        ldr     r5, [r2, #TI_TP_VALUE + 4]
#ifdef CONFIG_CPU_USE_DOMAINS
        ldr     r6, [r2, #TI_CPU_DOMAIN]
#endif
        switch_tls r1, r4, r5, r3, r7
#if defined(CONFIG_CC_STACKPROTECTOR) && !defined(CONFIG_SMP)
        ldr     r7, [r2, #TI_TASK]
        ldr     r8, =__stack_chk_guard
        ldr     r7, [r7, #TSK_STACK_CANARY]
#endif
#ifdef CONFIG_CPU_USE_DOMAINS
        mcr     p15, 0, r6, c3, c0, 0           @ Set domain register
#endif
        mov     r5, r0
        add     r4, r2, #TI_CPU_SAVE
        ldr     r0, =thread_notify_head
        mov     r1, #THREAD_NOTIFY_SWITCH
        bl      atomic_notifier_call_chain
#if defined(CONFIG_CC_STACKPROTECTOR) && !defined(CONFIG_SMP)
        str     r7, [r8]
#endif
 THUMB( mov     ip, r4                     )
        mov     r0, r5
 ARM(   ldmia   r4, {r4 - sl, fp, sp, pc}  )    @ Load all regs saved previously
 THUMB( ldmia   ip!, {r4 - sl, fp}         )    @ Load all regs saved previously
 THUMB( ldr     sp, [ip], #4               )
 THUMB( ldr     pc, [ip]                   )
 UNWIND(.fnend          )
ENDPROC(__switch_to)

cpu context 스위칭을 통해 다음 스레드로 전환한다.

  • 코드 라인 9~10에서 기존 thread_info->cpu_context에 r4 레지스터 부터 대부분의 레지스터들을 백업한다.
  • 코드 라인 14~18에서 레지스터 r4, r5, r6에 순서대로 thread_info의 tp_value[0], tp_value[1] 및 cpu_domain 값을 가져온다.
  • 코드 라인 19에서 process context 스위칭을 위해 TLS 스위칭을 한다.
  • 코드 라인 20~24에서 SMP가 아닌 시스템에서 CONFIG_CC_STACKPROTECTOR 커널 옵션을 사용하는 경우 다음 thread_info->task->stack_canary 값을 r7 레지스터에 읽어오고 r8 레지스터에는 __stack_chk_guard 주소 값을 읽어온다.
  • 코드 라인 25~27에서 도메인 레지스터에 cpu_domain 값을 설정한다.
  • 코드 라인 28에서 r5 레지스터에 이전 태스크를 가리키는 r0 레지스터를 잠시 백업해둔다.
  • 코드 라인 29에서 r4 레지스터에 다음 thread_info->cpu_context 값을 대입한다.
  • 코드 라인 30~32에서  thread_notify_head 리스트에 등록된 notify 블럭의 모든 함수들을 호출한다. 호출 시 THREAD_NOTIFY_SWITCH 명령과 다음 thread_info 포인터 값을 전달한다.
  • 코드 라인 33~35에서 다음 태스크의 stack_canary 값을 __stack_chk_guard 전역 변수에 저장한다.
  • 코드 라인 37에서 r5에 보관해둔 이전 태스크 포인터 값을 다시 r0에 대입한다.
  • 코드 라인 38에서 다음 thread_info->cpu_context 값을 가리키는 r4를 통해서 r4 레지스터 부터 대부분의 레지스터들을 회복한다.
    • 마지막에 읽은 pc 레지스터로 점프하게 된다.

 

arch/arm/include/asm/tls.h

#define switch_tls      switch_tls_v6k

armv6 및 armv7 아키텍처 이상의 경우 tls 레지스터를 가지고 있고 switch_tls_v68 매크로 함수를 호출한다.

 

switch_tls_v6k 매크로

arch/arm/include/asm/tls.h

.       .macro switch_tls_v6k, base, tp, tpuser, tmp1, tmp2
        mrc     p15, 0, \tmp2, c13, c0, 2       @ get the user r/w register
        mcr     p15, 0, \tp, c13, c0, 3         @ set TLS register
        mcr     p15, 0, \tpuser, c13, c0, 2     @ and the user r/w register
        str     \tmp2, [\base, #TI_TP_VALUE + 4] @ save it
        .endm

process context 스위칭을 위해 TLS 스위칭을 한다.

  • Thread ID 레지스터를 읽어서 이전 thread_info.tp_value[1]에 백업하고 TLS 레지스터에 tp 값과 Thread ID 레지스터에 tpuser 값을 설정한다.
  • 코드 라인 2에서 Thread ID 레지스터 용도의 TPIDRURW(User 읽기/쓰기) 레지스터 값을 tmp2에 대입한다. (tmp2 <- ThreadID)
  • 코드 라인 3에서 TLS 레지스터 용도의 TPIDRURO(User 읽기 전용) 레지스터에 tp 값을 저장한다. (TLS <- tp)
  • 코드 라인 4에서 Thread ID 레지스터 용도의 TPIDRURW(User 읽기/쓰기) 레지스터에 tpuser 값을 저장한다. (ThreadID <- tpuser)
  • 코드 라인 5에서 기존 Thread ID 값을 thread_info->tp_value[1]에 저장한다.

 

다음 그림은 process context 스위칭을 위해 TLS를 스위칭하는 모습을 보여준다.

 

스레드 Notifier

atomic_notifier_call_chain()

kernel/notifier.c

int atomic_notifier_call_chain(struct atomic_notifier_head *nh,
                               unsigned long val, void *v)
{
        return __atomic_notifier_call_chain(nh, val, v, -1, NULL);
}
EXPORT_SYMBOL_GPL(atomic_notifier_call_chain);
NOKPROBE_SYMBOL(atomic_notifier_call_chain);

notify 체인 리스트에 등록된 notify 블럭의 모든 함수들을 호출한다.

/**
 *      __atomic_notifier_call_chain - Call functions in an atomic notifier chain
 *      @nh: Pointer to head of the atomic notifier chain
 *      @val: Value passed unmodified to notifier function
 *      @v: Pointer passed unmodified to notifier function
 *      @nr_to_call: See the comment for notifier_call_chain.
 *      @nr_calls: See the comment for notifier_call_chain.
 *
 *      Calls each function in a notifier chain in turn.  The functions
 *      run in an atomic context, so they must not block.
 *      This routine uses RCU to synchronize with changes to the chain.
 *
 *      If the return value of the notifier can be and'ed
 *      with %NOTIFY_STOP_MASK then atomic_notifier_call_chain()
 *      will return immediately, with the return value of
 *      the notifier function which halted execution.
 *      Otherwise the return value is the return value
 *      of the last notifier function called.
 */
int __atomic_notifier_call_chain(struct atomic_notifier_head *nh,
                                 unsigned long val, void *v,
                                 int nr_to_call, int *nr_calls) 
{
        int ret;

        rcu_read_lock();
        ret = notifier_call_chain(&nh->head, val, v, nr_to_call, nr_calls);
        rcu_read_unlock();
        return ret;
}
EXPORT_SYMBOL_GPL(__atomic_notifier_call_chain);
NOKPROBE_SYMBOL(__atomic_notifier_call_chain);

rcu로 보호받으며 notify 체인 리스트에 등록된 notify 블럭의 모든 함수들을 nr_to_call  수 만큼 호출하고 성공적으로 호출된 횟수를 출력 인수 nr_calls에 저장한다.

  • val 값과 v 포인터 값이 notifier_call 함수에 전달된다.

 

contextidr_notifier_init()

arch/arm/mm/context.c

static int __init contextidr_notifier_init(void)
{
        return thread_register_notifier(&contextidr_notifier_block);
}
arch_initcall(contextidr_notifier_init);

Context 스위치마다 CONTEXTID.ASID 레지스터에 pid 값을 알아와서 기록하게 하도록 notify 블럭을 등록한다.

 

thread_register_notifier()

arch/arm/include/asm/thread_notify.h

static inline int thread_register_notifier(struct notifier_block *n)
{
        extern struct atomic_notifier_head thread_notify_head;
        return atomic_notifier_chain_register(&thread_notify_head, n);
}

스레드 notify 체인 블럭에 notify 블럭을 등록한다.

  • 다음 커널 코드에서 notify 블럭을 등록하여 사용하고 있다.
    • mm/context.c – contextidr_notifier_init() <- THREAD_NOTIFY_SWITCH 명령
    • arch/arm/nwfpe/fpmodule.c – fpe_init() <- THREAD_NOTIFY_FLUSH 명령
    • vfp/vfpmodule.c – vfp_init() <- THREAD_NOTIFY_SWITCH, FLUSH, EXIT, COPY 명령
    • 그 외 xscale 아키텍처 및 thumbee에서도 사용한다.

 

arch/arm/mm/context.c

static struct notifier_block contextidr_notifier_block = {
        .notifier_call = contextidr_notifier,
};

 

contextidr_notifier()

arch/arm/mm/context.c

#ifdef CONFIG_PID_IN_CONTEXTIDR
static int contextidr_notifier(struct notifier_block *unused, unsigned long cmd,
                               void *t)
{
        u32 contextidr;
        pid_t pid;
        struct thread_info *thread = t;

        if (cmd != THREAD_NOTIFY_SWITCH)
                return NOTIFY_DONE;

        pid = task_pid_nr(thread->task) << ASID_BITS;
        asm volatile(
        "       mrc     p15, 0, %0, c13, c0, 1\n"
        "       and     %0, %0, %2\n"
        "       orr     %0, %0, %1\n"
        "       mcr     p15, 0, %0, c13, c0, 1\n"
        : "=r" (contextidr), "+r" (pid)
        : "I" (~ASID_MASK)); 
        isb();

        return NOTIFY_OK;
}
#endif

커널에서 하드웨어 트레이스 툴을 사용할 때 사용되며 CONTEXTID.ASID 레지스터에 pid 값을 알아와서 기록한다.

  • 코드 라인 9~10에서 THREAD_NOTIFY_SWITCH 명령이 아니면 이 루틴과는 해당 사항이 없으므로 NOTIFY_DONE을 반환한다.
  • 코드 라인 12에서 두 번째 인수로 받은 t 값을 사용하여 thread_info->task->pid 값을 읽어온다.
  • 코드 라인 13~19에서 CONTEXTID 레지스터의 ASID 필드(bits[7:0])만 클리어하고 pid 값을 더해 기록한다.

 

/*      
 * These are the reason codes for the thread notifier.
 */
#define THREAD_NOTIFY_FLUSH     0
#define THREAD_NOTIFY_EXIT      1
#define THREAD_NOTIFY_SWITCH    2
#define THREAD_NOTIFY_COPY      3

 

task_pid_nr()

include/linux/sched.h

static inline pid_t task_pid_nr(struct task_struct *tsk)
{
        return tsk->pid;
}

태스크의 pid 값을 반환한다.

 

#ifdef CONFIG_CPU_HAS_ASID
#define ASID_BITS       8
#define ASID_MASK       ((~0ULL) << ASID_BITS)
#define ASID(mm)        ((unsigned int)((mm)->context.id.counter & ~ASID_MASK))
#else   
#define ASID(mm)        (0)
#endif
  • ASID_MASK=0xffff_ff00

 

activate & deactivate 태스크

activate_task()

kernel/sched/core.c

void activate_task(struct rq *rq, struct task_struct *p, int flags)
{
        if (task_contributes_to_load(p))
                rq->nr_uninterruptible--;

        enqueue_task(rq, p, flags);
}

uninterruptible 태스크 상태이면서 suspend 된 것은 아닌 경우 런큐의 nr_uninterrtible 카운터를 감소시키고 태스크를 런큐에 추가한다.

 

task_contributes_to_load()

include/linux/sched.h

#define task_contributes_to_load(task)  \
                                ((task->state & TASK_UNINTERRUPTIBLE) != 0 && \
                                 (task->flags & PF_FROZEN) == 0)

uninterruptible 태스크 상태이면서 suspend 된 것은 아닌 경우 true를 반환한다. (active 태스크가 cpu load에 기여한다)

  • 시스템 suspend 시 frozen 플래그가 설정된다.

 

enqueue_task()

kernel/sched/core.c

static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
{
        update_rq_clock(rq);
        sched_info_queued(rq, p);
        p->sched_class->enqueue_task(rq, p, flags);
}

런큐 클럭을 갱신시키고 요청 태스크의 스케줄러에 있는 (*enqueue_task) 후크에 연결된 함수를 호출하여 런큐에 추가한다.

  • 각 스케줄러마다 다음의 함수를 호출한다.
    • stop 스케줄러 – enqueue_task_stop()
    • deadline 스케줄러 – enqueue_task_dl()
    • rt 스케줄러 – enqueue_task_rt()
    • cfs 스케줄러 – enqueue_task_fair()
    • idle 스케줄러 – enqueue_task_idle()

 

deactivate_task()

kernel/sched/core.c

void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
{
        if (task_contributes_to_load(p))
                rq->nr_uninterruptible++;

        dequeue_task(rq, p, flags);
}

uninterruptible 태스크 상태이면서 suspend 된 것은 아닌 경우 런큐의 nr_uninterrtible 카운터를 증가시킨 후 태스크를 런큐에 내린다.

 

dequeue_task()

kernel/sched/core.c

static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
{
        update_rq_clock(rq);
        sched_info_dequeued(rq, p);
        p->sched_class->dequeue_task(rq, p, flags);
}

런큐 클럭을 갱신시키고 요청 태스크의 스케줄러에 있는 (*dequeue_task) 후크에 연결된 함수를 호출한다.

  • 각 스케줄러마다 다음의 함수를 호출한다.
    • stop 스케줄러 – dequeue_task_stop()
    • deadline 스케줄러 – dequeue_task_dl()
    • rt 스케줄러 – dequeue_task_rt()
    • cfs 스케줄러 – dequeue_task_fair()
    • idle 스케줄러 – dequeue_task_idle()

 

태스크 슬립

msleep()

kernel/time/timer.c

/**
 * msleep - sleep safely even with waitqueue interruptions
 * @msecs: Time in milliseconds to sleep for
 */
void msleep(unsigned int msecs)
{
        unsigned long timeout = msecs_to_jiffies(msecs) + 1;

        while (timeout)
                timeout = schedule_timeout_uninterruptible(timeout);
}

요청한 밀리세컨드+1 만큼 sleep한다.

  • 현재 태스크를 TASK_UNINTERRUPTIBLE 상태로 바꾸고 lowres 타이머에 요청한 밀리세컨드로 타이머를 설정한 후 preemption 하도록 스케줄한다.

 

schedule_timeout_uninterruptible()

kernel/time/timer.c

signed long __sched schedule_timeout_uninterruptible(signed long timeout)
{
        __set_current_state(TASK_UNINTERRUPTIBLE);
        return schedule_timeout(timeout);
}
EXPORT_SYMBOL(schedule_timeout_uninterruptible);

현재 태스크를 TASK_UNINTERRUPTIBLE 상태로 바꾸고 lowres 타이머를 사용하여 청한 밀리세컨드로 타이머를 설정한 후 preemption 하도록 스케줄한다.

  • 지정된 시간이 지나기 전에 schedule_timeout() 함수가 끝날 수 없다.

 

schedule_timeout_interruptible()

kernel/time/timer.c

signed long __sched schedule_timeout_interruptible(signed long timeout)
{
        __set_current_state(TASK_INTERRUPTIBLE);
        return schedule_timeout(timeout);
}
EXPORT_SYMBOL(schedule_timeout_interruptible);

현재 태스크를 TASK_INTERRUPTIBLE 상태로 바꾸고 lowres 타이머를 사용하여 청한 밀리세컨드로 타이머를 설정한 후 preemption 하도록 스케줄한다.

  • 지정된 시간이 지나기 전에 schedule_timeout() 함수가 끝나고 돌아올 수 있다.

 

schedule_timeout()

kernel/time/timer.c – 1/2

/**
 * schedule_timeout - sleep until timeout
 * @timeout: timeout value in jiffies
 *
 * Make the current task sleep until @timeout jiffies have
 * elapsed. The routine will return immediately unless
 * the current task state has been set (see set_current_state()).
 *
 * You can set the task state as follows -
 *
 * %TASK_UNINTERRUPTIBLE - at least @timeout jiffies are guaranteed to
 * pass before the routine returns. The routine will return 0
 *
 * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
 * delivered to the current task. In this case the remaining time
 * in jiffies will be returned, or 0 if the timer expired in time
 *
 * The current task state is guaranteed to be TASK_RUNNING when this
 * routine returns.
 *
 * Specifying a @timeout value of %MAX_SCHEDULE_TIMEOUT will schedule
 * the CPU away without a bound on the timeout. In this case the return
 * value will be %MAX_SCHEDULE_TIMEOUT.
 *
 * In all cases the return value is guaranteed to be non-negative.
 */

 

kernel/time/timer.c – 2/2

signed long __sched schedule_timeout(signed long timeout)
{
        struct timer_list timer;
        unsigned long expire;

        switch (timeout)
        {
        case MAX_SCHEDULE_TIMEOUT:
                /*
                 * These two special cases are useful to be comfortable
                 * in the caller. Nothing more. We could take
                 * MAX_SCHEDULE_TIMEOUT from one of the negative value
                 * but I' d like to return a valid offset (>=0) to allow
                 * the caller to do everything it want with the retval.
                 */
                schedule();
                goto out;
        default:
                /*
                 * Another bit of PARANOID. Note that the retval will be
                 * 0 since no piece of kernel is supposed to do a check
                 * for a negative retval of schedule_timeout() (since it
                 * should never happens anyway). You just have the printk()
                 * that will tell you if something is gone wrong and where.
                 */
                if (timeout < 0) {
                        printk(KERN_ERR "schedule_timeout: wrong timeout "
                                "value %lx\n", timeout);
                        dump_stack();
                        current->state = TASK_RUNNING;
                        goto out;
                }
        }

        expire = timeout + jiffies;

        setup_timer_on_stack(&timer, process_timeout, (unsigned long)current);
        __mod_timer(&timer, expire, false, TIMER_NOT_PINNED);
        schedule();
        del_singleshot_timer_sync(&timer);

        /* Remove the timer from the object tracker */
        destroy_timer_on_stack(&timer);

        timeout = expire - jiffies;

 out:
        return timeout < 0 ? 0 : timeout;
}
EXPORT_SYMBOL(schedule_timeout);

lowres 타이머를 사용하여 요청한 밀리세컨드로 타이머를 설정한 후 preemption 하도록 스케줄한다. 함수를 빠져나갈 때에는 TASK_RUNNING 상태를 보장한다.

  • 코드 라인 6~17에서 MAX_SCHEDULE_TIMEOUT 값으로 요청한 경우 타이머 설정없이 스스로 preemption 되도록 양보한다.
    • TASK_RUNNING 상태에서 스케줄된 경우 런큐에서 다음 수행 대기 중인 태스크로 스위치된다. 동작할 다음 태스크가 없으면 자신의 태스크가 다시 곧바로 스케줄되어 계속 진행하게 된다.
    • 그 외의 상태에서 호출하는 경우는 런큐에서 디큐되고 다음 수행 대기 중인 태스크로 스위치된다. 동작할 다음 태스크가 없으면 idle 스케줄러가 동작한다.
    • 외부에서 wakeup_process() 또는 try_to_wake_up()등의 함수에 의해 태스크를 런큐에 다시 엔큐하여 깨어나게한다음 out 레이블로 이동한 후 함수를 빠져나간다.
  • 코드 라인 18~33에서 음수 값으로 타이머를 설정한 경우 에러 메시지를 출력하고 태스크를 TASK_RUNNING 상태로 바꾼 후 함수를 빠져나간다.
  • 코드 라인 35~38에서 low-res 타이머를 사용하여 타이머를 설정한다.
  • 코드 라인 39에서 스케줄 함수를 호출하여 스스로 preemption 되도록 양보한다.
  • 코드 라인 40에서 가동 시켰던 타이머를 제거한다.
  • 코드 라인 43에서 타이머 디버그 용도로 트래킹 중인 오브젝트를 제거한다.
  • 코드 라인 45~48에서 남은 jiffies 단위의 타이머 만료 시간을 반환한다. 0 미만인 경우 0을 반환한다.

 

process_timeout()

kernel/time/timer.c

static void process_timeout(unsigned long __data)
{
        wake_up_process((struct task_struct *)__data);
}

태스크를 깨운다.

  • 타이머에의 의해 호출되며 interruptible 또는 uninterruptible 상태의 태스크를 깨워 다시 런큐에 엔큐시킨다.

 

Wait for Blocked I/O

wait queue와 wait event에 대한 내용은 별도의 페이지에서 분석하기로 하고 관련된 문서는 다음을 먼저 참고한다.

 

태스크 깨우기

/**
 * wake_up_process - Wake up a specific process
 * @p: The process to be woken up.
 *
 * Attempt to wake up the nominated process and move it to the set of runnable
 * processes.
 *
 * Return: 1 if the process was woken up, 0 if it was already running.
 *
 * It may be assumed that this function implies a write memory barrier before
 * changing the task state if and only if any tasks are woken up.
 */
int wake_up_process(struct task_struct *p)
{
        WARN_ON(task_is_stopped_or_traced(p));
        return try_to_wake_up(p, TASK_NORMAL, 0);
}
EXPORT_SYMBOL(wake_up_process);

요청한 태스크가 TASK_INTERRUPTIBLE 또는 TAKS_UNINTERRUPTIBLE 상태인 경우 깨운다. 깨운 경우 1을 반환하고, 이미 깨어나 동작 중인 경우 0을 반환한다.

 

try_to_wake_up()

kernel/sched/core.c – 1/2

/**
 * try_to_wake_up - wake up a thread
 * @p: the thread to be awakened
 * @state: the mask of task states that can be woken
 * @wake_flags: wake modifier flags (WF_*)
 *
 * Put it on the run-queue if it's not already there. The "current"
 * thread is always on the run-queue (except when the actual
 * re-schedule is in progress), and as such you're allowed to do
 * the simpler "current->state = TASK_RUNNING" to mark yourself
 * runnable without the overhead of this.
 *
 * Return: %true if @p was woken up, %false if it was already running.
 * or @state didn't match @p's state.
 */
static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
{
        unsigned long flags;
        int cpu, success = 0;

        /*
         * If we are going to wake up a thread waiting for CONDITION we
         * need to ensure that CONDITION=1 done by the caller can not be
         * reordered with p->state check below. This pairs with mb() in
         * set_current_state() the waiting thread does.
         */
        smp_mb__before_spinlock();
        raw_spin_lock_irqsave(&p->pi_lock, flags);
        if (!(p->state & state))
                goto out;

        success = 1; /* we're going to change ->state */
        cpu = task_cpu(p);

        if (p->on_rq && ttwu_remote(p, wake_flags))
                goto stat;

태스크의 상태가 요청한 state 마스크에 포함된 경우 태스크를 깨운다. 깨운 경우 1을 반환하고, 이미 깨어나 동작 중인 경우 0을 반환한다.

  • 코드 라인 30~31에서 태스크 상태가 바뀐 경우 out 레이블로 이동하여 실패 결과로 함수를 빠져나간다.
  • 코드 라인 36~37에서 태스크가 이미 런큐에 있는 경우 태스크를 TASK_RUNNING 상태로 바꾸고 preemption 가능한지 체크한 후 stat 레이블로 이동한다.

 

kernel/sched/core.c – 2/2

#ifdef CONFIG_SMP
        /*
         * If the owning (remote) cpu is still in the middle of schedule() with
         * this task as prev, wait until its done referencing the task.
         */
        while (p->on_cpu)
                cpu_relax();
        /*
         * Pairs with the smp_wmb() in finish_lock_switch().
         */
        smp_rmb();

        p->sched_contributes_to_load = !!task_contributes_to_load(p);
        p->state = TASK_WAKING;

        if (p->sched_class->task_waking)
                p->sched_class->task_waking(p);

        cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags);
        if (task_cpu(p) != cpu) {
                wake_flags |= WF_MIGRATED;
                set_task_cpu(p, cpu);
        }
#endif /* CONFIG_SMP */

        ttwu_queue(p, cpu);
stat:
        ttwu_stat(p, cpu, wake_flags);
out:
        raw_spin_unlock_irqrestore(&p->pi_lock, flags);

        return success;
}
  • 코드 라인 13~17에서 태스크를 TASK_WAKING 상태로 바꾸고 해당 태스크의 스케줄러에 해당하는 task_waking에 연결된 함수를 호출한다.
    • cfs 스케줄러만 관련 함수를 제공한다. -> task_waking_fair()
  • 코드 라인 19~23에서 wake 밸런싱을 통해 태스크가 깨어나 동작할 cpu를 알아온다. 알아온 cpu가 태스크의 기존 cpu로부터 변경된 경우 태스크에 바뀐 cpu를 지정한다.
  • 코드 라인 25에서 태스크를 알아온 cpu의 런큐에서 깨운다.
  • 코드 라인 27에서 관련 stat을 갱신한다.

 

ttwu_remote()

kernel/sched/core.c

/*
 * Called in case the task @p isn't fully descheduled from its runqueue,
 * in this case we must do a remote wakeup. Its a 'light' wakeup though,
 * since all we need to do is flip p->state to TASK_RUNNING, since
 * the task is still ->on_rq.
 */
static int ttwu_remote(struct task_struct *p, int wake_flags)
{
        struct rq *rq;
        int ret = 0;

        rq = __task_rq_lock(p);
        if (task_on_rq_queued(p)) {
                /* check_preempt_curr() may use rq clock */
                update_rq_clock(rq);
                ttwu_do_wakeup(rq, p, wake_flags);
                ret = 1;
        }
        __task_rq_unlock(rq);

        return ret;
}

태스크가 이미 런큐에 있는 경우 태스크를 TASK_RUNNING 상태로 바꾸고 preemption 가능한지 체크한다. 런큐에 태스크가 있었으면 1을 반환한다.

 

ttwu_do_wakeup()

kernel/sched/core.c

/*
 * Mark the task runnable and perform wakeup-preemption.
 */
static void
ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
        check_preempt_curr(rq, p, wake_flags);
        trace_sched_wakeup(p, true);

        p->state = TASK_RUNNING;
#ifdef CONFIG_SMP
        if (p->sched_class->task_woken)
                p->sched_class->task_woken(rq, p);

        if (rq->idle_stamp) {
                u64 delta = rq_clock(rq) - rq->idle_stamp;
                u64 max = 2*rq->max_idle_balance_cost;

                update_avg(&rq->avg_idle, delta);

                if (rq->avg_idle > max)
                        rq->avg_idle = max;

                rq->idle_stamp = 0;
        }
#endif
}

태스크를 러너블(TASK_RUNNING) 상태로 변경하고 wake-up preemption을 수행한다.

  • 코드 라인 7에서 preemption이 필요하면 리스케줄 요청을 하도록 체크한다.
  • 코드 라인 9~12에서 태스크를 TASK_RUNNING 상태로 바꾸고 해당 태스크의 스케줄러에 해당하는 task_woken에 연결된 함수를 호출한다.
    • dl 및 rt 스케줄러만 관련 함수를 제공한다.
      • task_woken_dl()
        • 다른 dl 태스크가 동작 중이고 요청한 dl 태스크가 동작 중이 아닌 경우 밸런싱을 위해 필요 시 push 한다.
      • task_woken_rt()
        • 다른 rt 태스크가 동작 중이고 요청한 rt 태스크가 동작 중이 아닌 경우 밸런싱을 위해 필요 시 push 한다.
  • 코드 라인 14~24에서 idle 동안의 시간과 기존 avg_idle의 차이 기간의 1/8만 avg_idle에 추가한다. 단 max_idle_balance_cost의 2배를 초과하지 못하게 제한한다.

 

update_avg()

kernel/sched/core.c

static void update_avg(u64 *avg, u64 sample)
{
        s64 diff = sample - *avg;
        *avg += diff >> 3;
}

avg += (sample – avg) / 8 를 산출한다.

 

ttwu_queue()

kernel/sched/core.c

static void ttwu_queue(struct task_struct *p, int cpu)
{
        struct rq *rq = cpu_rq(cpu);

#if defined(CONFIG_SMP)
        if (sched_feat(TTWU_QUEUE) && !cpus_share_cache(smp_processor_id(), cpu)) {
                sched_clock_cpu(cpu); /* sync clocks x-cpu */
                ttwu_queue_remote(p, cpu);
                return;
        }
#endif

        raw_spin_lock(&rq->lock);
        ttwu_do_activate(rq, p, 0);
        raw_spin_unlock(&rq->lock);
}

태스크를 요청한 cpu의 런큐에서 깨운다.

  • 코드 라인 6~10에서 TTWU_QUEUE(디폴트=true) feature가 설정되었고 요청한 cpu와 현재 cpu가 같은 캐시를 공유하지 않으면 요청한 cpu의 런큐의 wake_list에 태스크를 추가하고 IPI를 통해 리스케줄 요청을 한다.
  • 코드 라인 14에서 태스크를 런큐에 엔큐하고 러너블 상태로 변경한 후 wake-up preemption을 수행한다.

 

ttwu_do_activate()

kernel/sched/core.c

static void
ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags)
{
#ifdef CONFIG_SMP
        if (p->sched_contributes_to_load)
                rq->nr_uninterruptible--;
#endif

        ttwu_activate(rq, p, ENQUEUE_WAKEUP | ENQUEUE_WAKING);
        ttwu_do_wakeup(rq, p, wake_flags);
}

태스크를 런큐에 엔큐하고 러너블 상태로 변경한 후 wake-up preemption을 수행한다.

  • 코드 라인 5~6에서 태스크(uninterruptible)가 로드에 참여한 경우 nr_uninterruptible을 1 감소시킨다.
  • 코드 라인 9에서 태스크를 런큐에 엔큐하여 동작시킨다.
  • 코드 라인 10에서 태스크를 러너블(TASK_RUNNING) 상태로 변경하고 wake-up preemption을 수행한다.

 

ttwu_activate()

kernel/sched/core.c

static void ttwu_activate(struct rq *rq, struct task_struct *p, int en_flags)
{
        activate_task(rq, p, en_flags);
        p->on_rq = TASK_ON_RQ_QUEUED;

        /* if a worker is waking up, notify workqueue */
        if (p->flags & PF_WQ_WORKER)
                wq_worker_waking_up(p, cpu_of(rq));
}

태스크를 런큐에 엔큐하여 동작시킨다.

  • 코드 라인 3~4에서 태스트를 런큐에 엔큐한다.
  • 코드 라인 7~8에서 태스크가 워커이고 이미 깨어나 동작중인 경우 워커풀에서 nr_running을 1 증가시킨다.

 

wq_worker_waking_up()

kernel/workqueue.c

/**
 * wq_worker_waking_up - a worker is waking up
 * @task: task waking up
 * @cpu: CPU @task is waking up to
 *
 * This function is called during try_to_wake_up() when a worker is
 * being awoken.
 *      
 * CONTEXT:
 * spin_lock_irq(rq->lock)
 */     
void wq_worker_waking_up(struct task_struct *task, int cpu)
{
        struct worker *worker = kthread_data(task);

        if (!(worker->flags & WORKER_NOT_RUNNING)) {
                WARN_ON_ONCE(worker->pool->cpu != cpu);
                atomic_inc(&worker->pool->nr_running);
        }
}

워커가 이미 깨어나 동작중인 경우 워커풀에서 nr_running을 1 증가시킨다.

  • 코드 라인 14에서 워커 스레드를 알아온다.
  • 코드 라인 16~19에서 워커 스레드가 동작중인 경우 워커풀의 nr_running 카운터를 1 증가시킨다.

 

try_to_wake_up_local()

kernel/sched/core.c

/**
 * try_to_wake_up_local - try to wake up a local task with rq lock held
 * @p: the thread to be awakened
 *
 * Put @p on the run-queue if it's not already there. The caller must
 * ensure that this_rq() is locked, @p is bound to this_rq() and not
 * the current task.
 */
static void try_to_wake_up_local(struct task_struct *p)
{
        struct rq *rq = task_rq(p);

        if (WARN_ON_ONCE(rq != this_rq()) ||
            WARN_ON_ONCE(p == current))
                return;

        lockdep_assert_held(&rq->lock);

        if (!raw_spin_trylock(&p->pi_lock)) {
                raw_spin_unlock(&rq->lock);
                raw_spin_lock(&p->pi_lock);
                raw_spin_lock(&rq->lock);
        }

        if (!(p->state & TASK_NORMAL))
                goto out;

        if (!task_on_rq_queued(p))
                ttwu_activate(rq, p, ENQUEUE_WAKEUP);

        ttwu_do_wakeup(rq, p, 0);
        ttwu_stat(p, smp_processor_id(), 0);
out:
        raw_spin_unlock(&p->pi_lock);
}

 

check_preempt_curr()

kernel/sched/core.c

void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
        const struct sched_class *class;

        if (p->sched_class == rq->curr->sched_class) {
                rq->curr->sched_class->check_preempt_curr(rq, p, flags);
        } else {
                for_each_class(class) {
                        if (class == rq->curr->sched_class)
                                break;
                        if (class == p->sched_class) {
                                resched_curr(rq);
                                break;
                        }
                }
        }

        /*
         * A queue event has occurred, and we're going to schedule.  In
         * this case, we can save a useless back to back clock update.
         */
        if (task_on_rq_queued(rq->curr) && test_tsk_need_resched(rq->curr))
                rq_clock_skip_update(rq, true);
}

태스크를 현재 태스크가 preemption될 필요가 있는지 체크하고 그런 경우 리스케줄 요청 플래그를 설정한다.

  • 코드 라인 5~6에서 요청한 태스크가 현재 런큐에서 동작 중인 태스크에서 동작하는 스케줄러와 같다면 해당 스케줄러에 preemption 체크를 요청한다.
    • stop 스케줄러: check_preempt_curr_stop()
    • cfs 스케줄러: check_preempt_wakeup()
    • dl 스케줄러: check_preempt_curr_dl()
    • rt 스케줄러: check_preempt_curr_rt()
    • ilde 스케줄러: check_preempt_curr_idle()
    • 예) rq->curr가 cfs 태스크이고 요청한 태스크도 cfs 동일한 경우 check_preempt_wakeup() 함수를 처리한다.
  • 코드 라인 7~16에서 그렇지 않은 경우 stop 스케줄러부터 현재 런큐에서 동작중인 태스크의 스케줄러까지 순회하며 순회 중인 스케줄러가 요청한 태스크의 스케줄러와 동일한 경우 리스케줄 요청 플래그를 설정한 후 루프를 벗어난다.
    • 결국 런큐에서 동작하는 스케줄러보다 태스크의 스케줄러 우선 순위보다 더 빠른 경우 리스케줄 요청을 한다.
      • stop -> deadline -> rt -> cfs -> idle 스케줄러 순으로 리스케줄 한다.
    • 예) rq->curr가 cfs 태스크이고 요청한 태스크는 우선 순위가 더 빠른 rt 태스크인 경우 무조건 리스케줄 요청한다.
  • 코드 라인 22~23에서 런큐에서 현재 동작 중인 태스크에 리스케줄 요청 플래그가 설정되어 있는 경우 런큐 clock을 잠시 갱신하지 못하게 skip 플래그를 설정한다.

 

스케줄 Features

다음은 rpi3의 스케줄 features를 보여준다.

/sys/kernel/debug# cat sched_features
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY CACHE_HOT_BUDDY WAKEUP_PREEMPTION NO_HRTICK NO_DOUBLE_TICK LB_BIAS NONTASK_CAPACITY TTWU_QUEUE RT_PUSH_IPI NO_FORCE_SD_OVERLAP RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD

 

구조체

thread_info 구조체

arch/arm/include/asm/thread_info.h

/*
 * low level task data that entry.S needs immediate access to.
 * __switch_to() assumes cpu_context follows immediately after cpu_domain.
 */
struct thread_info {
        unsigned long           flags;          /* low level flags */
        int                     preempt_count;  /* 0 => preemptable, <0 => bug */
        mm_segment_t            addr_limit;     /* address limit */
        struct task_struct      *task;          /* main task structure */
        struct exec_domain      *exec_domain;   /* execution domain */
        __u32                   cpu;            /* cpu */
        __u32                   cpu_domain;     /* cpu domain */
        struct cpu_context_save cpu_context;    /* cpu context */
        __u32                   syscall;        /* syscall number */
        __u8                    used_cp[16];    /* thread used copro */
        unsigned long           tp_value[2];    /* TLS registers */
#ifdef CONFIG_CRUNCH
        struct crunch_state     crunchstate;
#endif
        union fp_state          fpstate __attribute__((aligned(8)));
        union vfp_state         vfpstate;
#ifdef CONFIG_ARM_THUMBEE
        unsigned long           thumbee_state;  /* ThumbEE Handler Base register */
#endif
};
  • flags
    • 플래그들
  • preempt_count
    • preemption 카운터로 이 값이 0일 경우에만 preemption이 가능하다.
    • 본문 참고
  • addr_limit
    • 접근 제한 주소
  • task
    • 현재 태스크
  • exec_domain
    • 실행 도메인
  • cpu
    • 동작 중인 cpu 번호
  • cpu_domain
    • cpu 도메인
    • DACR 레지스터 참고
    • 0=no access, 1=user, 3=manager
  • cpu_context
    • cpu context 시 사용하는 cpu 레지스터 정보 저장 장소
  • syscall
    • 시스템 콜(swi) 시 사용하는 syscall 번호
  • used_cp[]
    • 코프로세서 인스트럭션 체크 시 사용
  • tp_value[]
    • TLS 주소 저장
  • fpstate
    • undefined 명령 처리 시 사용하는 fp(부동 소숫점 처리기) 상태
    • 이 값을 사용하여 FP 모듈의 USR 시작 주소로 진입할 수 있게한다.
  • vfpstate
    • undefined 명령 처리 시 사용하는 vfp(부동소숫점 연산 처리기) 상태
    • 이 값을 사용하여 VFP 모듈의 USR 시작 주소로 진입할 수 있게한다.

 

cpu_context_save 구조체

arch/arm/include/asm/thread_info.h

struct cpu_context_save {
        __u32   r4;
        __u32   r5;
        __u32   r6;
        __u32   r7;
        __u32   r8;
        __u32   r9;
        __u32   sl;
        __u32   fp;
        __u32   sp;
        __u32   pc;
        __u32   extra[2];               /* Xscale 'acc' register, etc */
};

cpu context 스위치시 레지스터가 저장되는 장소

참고

 

Scheduler -1- (Basic)

 

태스크란?

  • 프로세스
    • 일반적인 정의는 프로그램이 실행중인 상태이다.
    • OS 커널이 부트업되어 준비된 경우 유저 레벨에서 디스크로부터 application을 로드하여 자원(메모리, 파일, 페이징, 시그널, 스택, …)을 할당하여 동작시킬 수 있는 최소 단위이다.
    • 유저 레벨에서 요청하여 OS 커널이 준비하고 생성한다.
    • 특별히 OS 커널은 그 자체가 하나의 커널 프로세스라고도 할 수 있다.
      • 커널 프로세스는 부트업타임에 생성되고 종료 직전까지 소멸되지 않으며 스케줄링 단위에는 포함되지 않는 특성으로 인해 존재 유무가 확연히 드러나지 않는다.
  • 스레드
    • 일반적인 정의는 프로세스에서 실행 단위만 분리한 상태이다.
    • 아키텍처를 다루는 문서에서 사용하는 스레드는 하드웨어 스레드를 의미하며 명령들을 수행할 수 있는 최소단위 장치인 core 또는 virtual core이다.
      • 예) core 당 2개의 하이퍼 스레드(x86에서의 virtual core)를 가진 4 core의 하드웨어 스레드는 총 8개이다.
    • OS 레벨에서의 스레드는 Process 내부에서 생성되는 더 작은 단위의 소프트웨어 스레드를 의미한다.
      • 커널 코드에서는 사용위치에 따라 스레드가 하드웨어 스레드를 의미할 수도 있고 소프트웨어 스레드를 의미할 수도 있으므로 적절히 구분해서 판단해야 한다.
    • 리눅스 버전 2.6에서 전적으로 커널이 스레드를 관리하고 생성한다. 따라서 이 기준으로 설명하였다.
      • 최종적으로 Red-hat팀이 개발한 NPTL(Native POSIX Thread Library)을 채용하였다.
      • 유저 스레드라고 불려도 커널이 생성하여 관리하는 것에 주의해야 한다. 리눅스 커널 2.6 이전에는 프로세스를 clone하여 사용하거나 유저 라이브러리를 통해 만들어 사용한 진짜 유저 스레드이다.
      • 참고: Native POSIX Thread Library | Wikipedia
    • 프로세스가 할당 받은 자원을 공유하여 사용할 수 있다. 단 스택 및 TLS(Thread Local Storage) 영역은 공유하지 않고 별도로 생성한다.
    • 유저 스레드는 유저 프로세스 또는 상위 스레드로 부터 생성된다.
    • 특별히 커널 스레드는 유저 레벨이 아닌 OS 커널 레벨에서만 생성 가능하다.
  • 태스크
    • 프로세스나 스레드를 리눅스에서 스케줄링 할 수 있는 최소 단위가 태스크이다.
    • 유저 태스크에서 스케줄링에 대한 비율을 조정하는 경우 nice 값을 사용하여 각 태스크의 time slice를 산출해낸다.
      • 내부 자료 구조에서는 task_struct가 태스크를 나타내고 그 내부에 스케줄 엔티티 구조체를 포함하며 이 스케줄 엔티티를 사용하여 time slice를 계산한다.
        • 태스크에는 스케줄러별로 사용할 수 있도록 3 개의 스케줄 엔티티인 sched_entity, sched_rt_entity 및 sched_dl_entity가 있다.
      • cgroup을 사용한 그룹 스케줄링을 하는 경우에는 스케줄 엔티티가 태스크 그룹(group scheduling)에 연결되어 time slice를 계산한다.
    • 유닉스와 다르게 리눅스의 경우 별도의 설정이 없는 경우 프로세스와 스레드가 동일한 태스크 표현을 사용하고 스케줄링 비율은 동일하다.

 

 

 

멀티태스킹 (time slice, virtual runtime)

동시에 2개의 태스크를 하나의 CPU에서 구동을 시키면 이론적으로는 그 CPU에서 50%의 파워로 2 개의 태스크그가 동시에 병렬로 동작해야 하는데 실제 하드웨어 CPU는 한 번에 하나의 태스크 밖에 수행할 수 없으므로 시간을 분할(time slice) 한 그 가상 시간(virtual runtime) 만큼 교대로 수행을 하여 만족시킨다.

 

우선순위

Priority

  • 커널에서 분류하여 사용하는 우선순위로 0~139까지 총 140 단계가 있다.
    • priority 값이 작을수록 높은 우선순위로 time slice를 많이 받는다.
  • 0~99까지 100 단계는 RT 스케줄러에서 사용한다.
  • 100~139까지의 40단계는 CFS 스케줄러에서 사용한다.
    • Nice로 변환되는 영역이다.

 

Nice

  • POSIX 표준이 지정하였다. 일반적인 태스크에서 지정할 수 있는 -20 ~ +19 까지 총 40단계가 있다.
    • nice 값이 가장 작은 -19가 우선 순위가 더 높고 time slice를 많이 받는다.
    • priority 값으로 변환 시 100 ~ 139의 우선순위를 갖는다.
      • RT 스케줄러에서 사용하는 priority 0 ~ 99값보다 커서 RT 스케줄러보다는 항상 낮은 우선 순위를 갖는다.
    • root 권한이 아닌 유저로 프로세스나 스레드가 생성되면 스케줄링 단위인 태스크의 nice 값은 0으로 시작된다.
  • 2003년에 +19 레벨의 time slice는 1ms(1 jiffy)와 동일하게 설정을 하였으나 그 후 HZ=1000인 시스템(데스크탑)에서 time slice가 너무 적어 5ms로 변경하였다.

 

스케줄러

커널에 디폴트로 5개의 스케줄러가 준비되어 있고 사용자 태스크는 스케줄 정책을 선택하는 것으로 각각의  스케줄러를 선택할 수 있다. 단 stop 스케줄러 및 Idle-task 스케줄러는 커널이 자체적으로만 사용하므로 사용자들은 선택할 수 없다.

  • Stop 스케줄러
  • Deadline 스케줄러
  • RT 스케줄러
  • CFS 스케줄러
  • Idle Task 스케줄러

 

스케줄 정책

  • SCHED_DEADLINE
    • 태스크를 deadline 스케줄러에서 동작하게 한다.
  • SCHED_RR
    • 같은 우선 순위의 태스크를 default 0.1초 단위로 round-robin 방식을 사용하여 RT 스케줄러에서 동작하게 한다.
  • SCHED_FIFO
    • 태스크를 FIFO(first-in first-out) 방식으로 RT 스케줄러에서 동작하게 한다.
  • SCHED_NORMAL
    • 태스크를 CFS 스케줄러에서 동작하게 한다.
  • SCHED_BATCH
    • 태스크를 CFS 스케줄러에서 동작하게 한다. 단 SCHED_NORMAL과는 다르게 yield를 회피하여 현재 태스크가 최대한 처리를 할 수 있게 한다.
  • SCHED_ILDE
    • 태스크를 CFS 스케줄러에서 가장 낮은 우선순위로 동작하게 한다. (nice 19보다 더 느리다. nice=20)

 

CFS 스케줄러

  • linux v2.6.23부터 사용하기 시작하였다.
  • timeline(다음 태스크 실행할 마감 시간)으로 정렬한 RB 트리를 사용
    • p->se.vruntime을 키로 소팅된다.
    • 기존에 사용하던 active, expired 배열은 사용하지 않는다.
  • 3가지 스케줄 정책에서 사용된다.
    • SCHED_NORMAL
    • SCHED_BATCH
    • SCHED_IDL
  • 기존 O(1) 스케줄러는 jiffies나 hz 상수에 의존하여 ms 단위를 사용하였으나 cfs 스케줄러는 ns 단위로 설계되었다.
  • 통계적 방법을 사용하지 않고 deadline 방식으로 관리한다.
  • CFS bandwidth 기능을 사용할 수 있다.
  • 예) ksoftirqd나 high 우선 순위 워크큐의 워커로 동작하는 kworker 태스크들은 CFS 스케줄러에서 nice -20으로 동작한다.

 

리얼타임(RT) 스케줄러

  • sched_rt_period_us
    • 실행 주기 결정 (초기값: 1000000 = 1초)
    • 이 값을 매우 작은 수로 하는 경우 시스템이 처리에 응답할 수 없다.
      • hrtimer보다 작은 경우 등
  • sched_rt_runtime_us
    • 실행 시간 결정 (초기값: 950000 = 0.95초)
    • 전체 스케줄 타임을 100%로 가정할 때 95%에 해당하는 시간을 RT 스케줄러가 이용할 수 있다.
  • 2가지 스케줄 정책에서 사용된다.
    • SCHED_FIFO
      • cfs 스케줄러에서 사용하는 weight 값 및 time slice라는 개념이 없다. 스스로 슬립하거나 태스크가 종료되기 전 까지 계속 동작한다.
    • SCHED_RR
      • SCHED_FIFO와 거의 동일하다. 같은 우선 순위의 태스크가 존재하는 경우에만 디폴트 0.1초 단위로 라운드 로빈 방식으로 순회하며 동작한다.
  • 0번부터 99번까지 100개의 우선 순위 리스트 배열로 관리된다.
  • RT bandwidth 기능을 사용할 수 있다.
  • 예) migration, threaded irq 및 watchdog 태스크들은 rt 스케줄러에서 동작한다.

 

Deadline 스케줄러

  • 1가지 스케줄 정책에서 사용된다.
    • SCHED_DEADLINE
  • 아직 사용자 드라이버에서는 잘 활용되고 있지 않다.

 

런큐

  • CPU 마다 하나 씩 사용된다.
  • 런큐에는 각 스케쥴러들이 사용된다.
  • CPU에 배정할 태스크들이 스케줄 엔티티 형태로 런큐에 enqueue 된다.
  • 태스크가 처음 실행될 때 가능하면 부모 태스크가 위치한 런큐에 enqueue 된다.
    • 같은 cpu에 배정되는 경우 캐시 친화력이 높아서 성능이 향상된다.

 

 

Time Slice

CFS에서의 weight

CFS 스케쥴러에서 사용하는 nice 우선순위에 따라서 weight 값이 부여된다.

  • nice가 0인 태스크에 대한 weight 값을 1024 기준 값으로 하였다.
    • 실수 1.0의 weight 값을 2진 정수로 표현할 때 2^10=1024를 사용하였다.
    • 정밀도는 10진수로 표현하는 경우 1.000에 해당하는 소숫점 3자리를 커버한다.
    • 64비트 시스템에서는 scale 1024를 적용하여 nice 0에 대한 값이 2^20=1,048,576을 사용하여 정밀도를 더 높였다.
  • nice 값이 1씩 감소할 때마다 10%의 time slice 배정을 더 받을 수 있도록 25%씩 weight 값이 증가된다.
  • 참고로 가장 우선 순위가 낮은 idle 스케줄러에서 사용하는 idle 태스크의 경우 time slice를 가장 적게 받는 3으로 배정하여 고정하였다.

 

다음 테이블은 nice -> weight의 빠른 산출을 위해 미리 계산하여 만들어둔 테이블이다.

다음 테이블은 nice -> wmult의 빠른 산출을 위해 미리 계산하여 만들어둔 테이블이다.

  • time slice를 계산할 때 나눗샘 대신 곱셈으로 처리하려고 weight 값을 inverse한 값을 사용한다.
  • 성능향상을 목적으로 커널은 x / weight = y와 같은 산술식을 사용하여야 할 때 나눗셈을 피해서 아래 테이블 값을 사용하여 x * wmult >> 32로 y 값을 산출한다.
    • 예) ‘4096 / 1024 = 4′ 와 ‘4096 * 4194304 >> 32 = 4’에 대한 결과는 서로 동일한 결과를 얻을 수 있음을 알 수 있다.

 

아래 그림과 같이 weight가 25% 증가 시 실제 cpu 점유율이 기존에 비해 10%가 증가됨을 확인할 수 있다.

  • 단 2개 태스크를 비교할 때의 기준이고 3개 이상의 태스크를 비교할 때에는 똑같이 10%가 증가되지 않음을 확인할 수 있다.

 

다음 그림은 5개의 task에 대해 각각의 nice 값에 따른 weight 값과 그 비율을 산출하였다.

 

스케줄링 latency 와 스케일 정책

런큐에서 동작하는 태스크들이 한 바퀴 돌도록 사용할 periods(ns)는 다음 변수를 사용하여 산출된다.

  • rq->nr_running
    • 런큐에서 동작중인 태스크 수
  • factor
    • 스케일링 정책에 따른 비율이다. (rpi2: factor=3)
  • sched_latency_ns
    • 최소 스케줄 기간으로 디폴트 값(6000000) * factor(3) = 18000000(ns)
    • “/proc/sys/kernel/sched_latency_ns”
  • sched_min_granularity
    • 태스크 하나 당 최소 스케쥴 기간으로 디폴트 값(750000) * factor(3) = 2250000(ns)
    • “/proc/sys/kernel/sched_min_granularity_ns”
  • sched_wakeup_granularity_ns
    • 태스크의 wakeup 기간으로 디폴트 값(1000000) * factor(3) = 3000000(ns)
    • “/proc/sys/kernel/sched_wakeup_granularity_ns”
  • sched_nr_latency
    • sched_latency_ns를 사용할 수 있는 태스크 수
    • 이 값은 sched_latency_ns / sched_min_granularity 으로 자동 산출된다.

 

스케줄링 latency 산출식

산출은 nr_running와 sched_nr_latency를 비교한 결과에 따라 다음 두 가지 중 하나로 결정된다.

  • sysctl_sched_latency(18ms) <- 조건: nr_running <= sched_nr_latency(8)
  • sysctl_sched_min_granularity(2.25ms) * nr_running <- 조건: nr_running > sched_nr_latency(8)

 

다음 그림은 rpi2(cpu:4) 시스템에서 하나의 cpu에 태스크가 5개 및 10개가 구동될 떄 각각의 스케줄링 기간을 산출하는 모습을 보여준다.

 

cpu 수에 따른 스케일링 정책

스케일링 정책에 따른 비율이며 cpu 수에 따른 스케일 latency에 변화를 주게된다.

  • SCHED_TUNABLESCALING_NONE(0)
    • 항상 1을 사용하여 스케일이 변하지 않게 한다.
  • SCHED_TUNABLESCALING_LOG(1)
    • 1 + ilog2(cpus)과 같이 cpu 수에 따라 변화된다. (디폴트)
    • rpi2: cpu=4개이고 이 옵션을 사용하므로 factor=3이 적용되어 3배의 스케일을 사용한다.
  • SCHED_TUNABLESCALING_LINEAR(2)
    • online cpu 수로 8 단위로 정렬하여 사용한다. (8, 16, 24, 32, …)

 

태스크별 Time Slice

개별 태스크가 수행한 시간을 산출한다.

  • 런큐별 스케줄링 latency 1 주기 기간을 각 태스크의 weight 비율별로 나눈다.

 

VRuntime

태스크의 vruntime은 개별 태스크 실행 시간을 누적시킨 값을 런큐의 RB 트리에 배치하기 위해 로드 weight을 반대로 적용한 값이다. (우선 순위가 높을 수록 누적되는 weight 값을 반대로 작게하여 vruntime에 추가하므로 RB 트리에서 먼저 우선 처리될 수 있게 한다)

누적시 추가될 virtual runtime slice는 다음과 같이 산출된다.

vruntime slice = time slice * wieght-0 / weight

 

다음 그림은 4개의 태스크가 idle 없이 계속 실행되는 경우 각 태스크의 vruntime은 산출된 vruntime slice 만큼 계속 누적되어 실행되는 모습을 보여준다.

cfs_rq->min_vruntime

cfs 런큐에 새로운 태스크 또는 슬립되어 있다가 깨어나 엔큐되는 경우 vruntime이 0부터 시작하게되면 이러한 태스크의 vruntime이 가장 낮아 이 태스크에 실행이 집중되고 다른 태스크들은 cpu 타임을 얻을 수 없는 상태가 된다. (starvation problem) 따라서 이러한 것을 막기 위해서 cfs 런큐에 새로 진입할 때 min vruntime 값을 기준으로 사용하게 하였다.

  • cfs_rq->min_vruntime 값은 현재 태스크와 cfs 런큐에 대기중인 태스크들 중 가장 낮은 수가 스케줄 틱 및 필요 시마다 갱신되어 사용된다.
  • cfs 런큐에 진입 시에 min_vruntime 값을 더해서 사용하고 cfs 런큐에서 빠져나갈 때에는 min_vruntime 값만큼 감소시킨다.
  • cfs 런큐에 진입 시에 vruntime에 대해 약간의 규칙을 사용한다.
    • 새 태스크가 cfs 런큐에 진입
      • min_vruntime 값 + vruntime slice를 더해 사용
      • fork된 child 태스크가 먼저 실행되는 옵션을 사용한 경우 현재 태스크가 우선 처리되도록 vruntime과 swap한다.
    • idle 태스크가 깨어나면서 cfs 런큐에 진입
      • min_vruntime 값 사용
    • 기타 여러 이유로 cfs 런큐에 진입(태스크 그룹내 이동, cpu migration, 스케줄러 변경)

 

다음 그림은 min_vruntime이 vruntime이 가장 낮은 curr 태스크가 사용하는 vruntime 값으로 갱신되는 모습을 보여준다.

 

CFS Group Scheduling

  • cgroup의 cpu 서브시스템을 사용하여 커널 v2.6.24에서 소개되었다.
  • 계층적 스케줄 그룹(TG: Task Group)을 설정하여 사용자 프로세스의 utilization을 조절할 수 있다.
    • 태스크의 로드 weight 값을 관리하기 위해 스케줄 엔티티를 사용하는데 태스크용 스캐줄 엔티티와 태스크 그룹용 스케줄 엔티티(tg->se[])로 나뉜다.
  • 스케줄 그룹의 CFS bandwidth 기능을 사용하면 배정받은 시간 범위내에서의 utilization 마저도 조절할 수 있다.

 

다음 그림은 그룹 스케줄링의 유/무에 대해 비교를 하였다.

  • 우측의 경우 루트 그룹을 만들고 그 아래에 두 개의 스케줄 그룹을 만들면 디폴트로 각각 하위 두 그룹이 50%씩 utilization을 나누게 된다.
  • 태스크 그룹을 사용하는 경우 각 태스크 그룹마다 cpu 수 만큼 cfs 런큐가 있고 그 그룹에 속한 태스크나 태스크 그룹은 각각의 스케줄 엔티티로 본다.
    • 우측의 경우 5개의 태스크용 스케줄 엔티티가 모두 1024의 weight 값을 갖는다고 가정할 때 root 그룹은 2개의 그룹용 스케줄 엔티티에 대한 분배를 결정하고, 각 group에서는 그룹에 소속된 task용 스케줄 엔티티에 대한 분배를 결정한다.
    • 우측의 경우 root 그룹에 2 개의 task가 추가로 실행되는 경우 root 그룹은 총 4개의 스케줄 엔티티에 대한 분배를 수행한다. (태스크 그룹용 스케줄 엔티티 2개 + 태스크용 스케줄 엔티티 2개)
      • group-1에 해당하는 각 태스크는 6.25%를 할당받는다.
      • group-2에 해당하는 태스크는 25%를 할당받는다.
      • 그림에는 표현되지 않았지만 루트 그룹에 새로 추가된 task 6와 task 7은 각각 25%를 할당받는다.

 

다음 그림은 그룹 스케줄링을 적용 시 time slice 적용 비율이 변경된 것을 보여준다.

  • 루트 그룹 밑에 두 개의 태스크 그룹을 만들고 각각 20%, 80%에 해당하는 share 값을 설정한 경우 그 그룹 아래에서 동작하는 태스크들의 utilization을 다음과 같이 확인할 수 있다.

 

CPU Bandwidth for CFS

태스크 그룹에 할당된 time slice를 모두 사용하지 않고 일정 비율만 사용하게 하여 cpu가 스로틀링(cpu를 쉬엄 쉬엄) 할 수 있게 할 수도 있고 반대로 더 많은 cpu 할당을 받을 수 있게 할 수도 있다.

 

다음 그림은 Task 5가 할당받은 80%의 time slice 비율에서 설정된 band width에 따라 좌측은 cpu를 절반만 쓰고 스로틀링(슬립하며 쉰다) 할 수 있고, 우측은 두 개의 cpu에서 동시에 동작하게 설정된 모습을 보여준다.

  • 즉 smp 시스템에서 quota와 period가 설정된 경우 해당 스케줄 엔티티가 사용하는 시간 범위내에서 cpu 수에 따라 각 core 마다 스로틀이 발생함을 보여준다.

 

CFS Scheduling Domain

스케줄링 그룹(sched_group)에 많은 cpu 로드가 발생하면 각 스케줄링 도메인을 통해 로드 밸런스를 수행하게 한다.

  • 계층적 구조를 통해 cpu affinity에 합당한 core를 찾아가도록 한다.

 

스케줄링 도메인은 디바이스 트리 및 MPIDR 레지스터를 참고하여 cpu가 on/off 될 때마다 cpu topology를 변경하고 이를 통해 스케줄링 도메인을 구성한다.

  • 디바이스 트리 + MPIDR 레지스터 -> cpu on/off -> cpu topology 구성 변경 -> 스케줄링 도메인

 

cpu 토플로지의 단계는 다음과 같다.

  • cluster
  • core
  • thread

 

스케줄링 도메인의 단계는 다음과 같다.

  • DIE 도메인
    • cpu die (package)
  • MC 도메인
    • 멀티 코어
  • SMT 도메인
    • 멀티 스레드(H/W)

 

다음 그림은 스케줄링 도메인과 스케줄링 그룹을 동시에 표현하였다. (arm 문서 참고)

  • 참고로 아래 그림의 스케줄링 그룹(sched_group)과 그룹 스케줄링(task_group)은 다른 기능이므로 주의한다.

 

 

스케줄 Tick

scheduler_tick()

kernel/sched/core.c

/*
 * This function gets called by the timer code, with HZ frequency.
 * We call it with interrupts disabled.
 */
void scheduler_tick(void)
{       
        int cpu = smp_processor_id();
        struct rq *rq = cpu_rq(cpu);
        struct task_struct *curr = rq->curr;

        sched_clock_tick();

        raw_spin_lock(&rq->lock);
        update_rq_clock(rq);
        curr->sched_class->task_tick(rq, curr, 0);
        update_cpu_load_active(rq);
        raw_spin_unlock(&rq->lock);

        perf_event_task_tick();

#ifdef CONFIG_SMP
        rq->idle_balance = idle_cpu(cpu);
        trigger_load_balance(rq);
#endif
        rq_last_tick_reset(rq);
}

tick 마다 스케줄 관련 처리를 수행하고 로드 밸런스 주기가 된 경우 SCHED softirq를 호출한다.

  • 코드 라인 8~9에서 현재 cpu의 런큐 및 현재 태스크를 알아온다.
  • 코드 라인 11에서 안정되지 않은 클럭을 사용중인 경우 per-cpu sched_clock_data 값을 현재 시각으로 갱신한다.
    • 현재 x86 및 ia64 아키텍처에서만 unstable 클럭을 사용한다.
  • 코드 라인 14 런큐 클럭 값을 갱신한다.
  • 코드 라인 15에서 현재 태스크의 스케줄링 클래스의 (*task_tick)에 등록된 콜백 함수를 호출한다.
    • task_tick_fair(), task_tick_rt(), …
  • 코드 라인 16에서 현재 런큐의 cpu_load[] 값을 갱신한다.
  • 코드 라인 19에서 perf 관련 처리를 수행한다.
  • 코드 라인 22에서 현재 cpu가 idle 상태인지 여부를 런큐에 기록한다.
  • 코드 라인 23에서 로드 밸런스 주기마다 SCHED_SOFTIRQ를 발생시킨다.
    • 최대 주기는 core 수 * 0.1초
  • 코드 라인 25에서 커널이 nohz full 옵션을 사용하는 경우 현재 jiffies를 런큐의 last_sched_tick에 기록해둔다.

 

런큐 클럭 갱신

update_rq_clock()

kernel/sched/core.c

void update_rq_clock(struct rq *rq)
{
        s64 delta;

        lockdep_assert_held(&rq->lock);

        if (rq->clock_skip_update & RQCF_ACT_SKIP)
                return;

        delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
        if (delta < 0)
                return;
        rq->clock += delta;
        update_rq_clock_task(rq, delta);
}

런큐 클럭 값을 갱신한다.

  • 코드 라인 7~8에서 스케줄 진행 중인 경우 불필요한 스케줄 클럭을 갱신하지 않도록 빠져나간다.
  • 코드 라인 10~12에서 현재 스케줄 클럭과 런큐에 마지막 사용한 클럭과의 차이를 delta에 대입한다.
  • 코드 라인 13~14 런큐의 클럭에 delta를 추가 반영한다.
  • 코드 라인 14에서 irq_delta 값을 산출하여 런큐의 인터럽트 소요 클럭에 추가하여 갱신한다. irq_delta 값 만큼 인수로 전달받은 delta 값도 감소시킨 후 런큐의 클럭 태스크에 delta 값을 더해 갱신한다.

 

sched_clock_cpu()

kernel/sched/clock.c

/*
 * Similar to cpu_clock(), but requires local IRQs to be disabled.
 *
 * See cpu_clock().
 */
u64 sched_clock_cpu(int cpu)
{
        struct sched_clock_data *scd;
        u64 clock;

        if (sched_clock_stable())
                return sched_clock();

        if (unlikely(!sched_clock_running))
                return 0ull;

        preempt_disable_notrace();
        scd = cpu_sdc(cpu);

        if (cpu != smp_processor_id())
                clock = sched_clock_remote(scd);
        else
                clock = sched_clock_local(scd);
        preempt_enable_notrace();

        return clock;
}

stable 클럭을 사용하는 경우 스케줄 클럭(사이클)을 반환해온다. (arm 및 arm64 아키텍처는 stable 클럭을 사용한다.)

 

update_rq_clock_task()

kernel/sched/core.c

static void update_rq_clock_task(struct rq *rq, s64 delta)
{
/*              
 * In theory, the compile should just see 0 here, and optimize out the call
 * to sched_rt_avg_update. But I don't trust it...
 */     
#if defined(CONFIG_IRQ_TIME_ACCOUNTING) || defined(CONFIG_PARAVIRT_TIME_ACCOUNTING)
        s64 steal = 0, irq_delta = 0;
#endif
#ifdef CONFIG_IRQ_TIME_ACCOUNTING
        irq_delta = irq_time_read(cpu_of(rq)) - rq->prev_irq_time;

        /*
         * Since irq_time is only updated on {soft,}irq_exit, we might run into
         * this case when a previous update_rq_clock() happened inside a
         * {soft,}irq region.
         *
         * When this happens, we stop ->clock_task and only update the
         * prev_irq_time stamp to account for the part that fit, so that a next
         * update will consume the rest. This ensures ->clock_task is
         * monotonic.
         *
         * It does however cause some slight miss-attribution of {soft,}irq
         * time, a more accurate solution would be to update the irq_time using
         * the current rq->clock timestamp, except that would require using
         * atomic ops.
         */
        if (irq_delta > delta)
                irq_delta = delta;

        rq->prev_irq_time += irq_delta;
        delta -= irq_delta;
#endif
#ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
        if (static_key_false((&paravirt_steal_rq_enabled))) {
                steal = paravirt_steal_clock(cpu_of(rq));
                steal -= rq->prev_steal_time_rq;

                if (unlikely(steal > delta))
                        steal = delta;

                rq->prev_steal_time_rq += steal;
                delta -= steal;
        }
#endif

        rq->clock_task += delta;

#if defined(CONFIG_IRQ_TIME_ACCOUNTING) || defined(CONFIG_PARAVIRT_TIME_ACCOUNTING)
        if ((irq_delta + steal) && sched_feat(NONTASK_CAPACITY))
                sched_rt_avg_update(rq, irq_delta + steal);
#endif
}

irq_delta 값을 산출하여 런큐의 인터럽트 소요 클럭에 추가하여 갱신한다. irq_delta 값 만큼 인수로 전달받은 delta 값도 감소시킨 후 런큐의 클럭 태스크에 delta 값을 더해 갱신한다.

  • rq->clock과 다른 점은 현재 시각에서 irq 소요 시간을 뺀 실제 태스크에 소모한 시간만을 사용한 클럭이 rq->clock_task이다.
  • irq 소요 시간 측정 관련 코드 분석은 생략

 

스케줄링 클래스별 틱 처리

  • Real-Time 스케줄링 클래스
    • task_tick_rt()
  • Deadline 스케줄링 클래스
    • task_tick_dl()
  • Completly Fair 스케줄링 클래스
    • task_tick_fair()
  • Idle-Task 스케줄링 클래스
    • task_tick_idle()
  • Stop-Task 스케줄링 클래스
    • task_tick_stop()

 

참고

 

Scheduler -2- (cpu load & PELT)

 

Scheduler -2- (cpu load)

 

커널 v3.11-rc1에서 kernel/sched/core.c의 cpu 로드 관련 함수 들을 kernel/sched/proc.c 로 옮겼고,

다시 커널 v4.2-rc1에서 kernel/sched/loadavg.c 파일로 옮겼다. 아래 코드는 커널 v4.0 기준이므로 kernel/sched/proc.c 파일에 존재한다.

 

추세 관련 사전 산술 지식

주식 시장에서 주가 흐름에 단순이동평균(SMA), 가중이동평균(WMA), 지수이동평균(EMA) 등을 사용하여 기간별 평균흐름을 나타내는데 먼저 머리를 정리하기 위해 다음과 같은 방법이 있음을 미리 산출해보자.

  • 예) 최근 6일간 종가(raw data): 1020, 1030, 1000, 1010, 1020, 1060일 때
    • 3일 단순 이동 평균(SMA: Simple Moving Average)
      • 과거 데이터와 최근 데이터를 고르게 반영
      • = (1010 + 1020 + 1060) / 3
      • = 1030
    • 3일 가중 이동 평균(WMA; Weighted Moving Average)
      • 최근 데이터에 높은 가중치를 주는 방법 (예: w1=1/6, w2=2/6, w3=3/6)
      • = 1010 * w1 + 1020 * w2 + 1060 * w3
      • = 168 + 340 + 530
      • = 1038
    • 3일 지수 이동 평균(EMA: Exponential Moving Average 또는 EWMA: Exponential Weighted Moving Average)
      • 최근 데이터에 더 높은 가중치를 주는 방법으로 전일 지수 이동 평균 값과 금일 값만 사용하여 간단히 계산한다.
      • 평활계수(Exponential Percentage) k는 다음과 같이 기간 n을 사용하여 산출한다.
        • ‘k=2/(n+1)’
        • 예: n=2일, k=2/(n+1)=0.666666…
        • 예: n=3일, k=2/(n+1)=0.5
        • 예: n=10일, k=2/(n+1)=0.181818…
      • =전일 지수 이동 평균 값 * (1-k) + 금일 값 * (k)
      • =1010 * 0.5 + 1060 * 0.5
      • =1035

 

리눅스 커널에서는 cpu 로드 산출에 필요한 모든 raw 데이터를 저장하지 않는다. 따라서 조금 다른 방법으로 지수 평활법(ES: Exponential Smoothing) 중 하나인 지수 감소 평균(EDA)을 사용한다. 먼저 1개의 cpu가 있는 시스템에서 태스크 1개가 동작 중인 경우 cpu 로드 값은 1.0이 된다. cpu가 4개가 동작하는 시스템에서는 이 값을 4로 나누게 되므로 0.25의 cpu 로드 값이 된다. 단 cpu 로드 값 1.0에 대응하여 리눅스 코드에서 사용되는 cpu load 값은 1024 및 2048이 사용되고 있다. (고정 소숫점 1.0 = 1,024 또는 2,048)

  • 지수 감소 평균(EDA: Exponential Decaying Average, EDMA: Exponential Damped Moving Average)
    • ‘기존 cpu 로드 값 * k + 새 cpu 로드 값 * (1 – k)’이고 ‘k=exp^(-1/n)’ (n=기간)
    • 리눅스 구현 로직에서는 avenrun[] 및 cpu_load[] 산출에 대한 k 값은 각각의 구현 항목에서 살펴본다.

 

cpu 로드 산출식

지정된 기간에 어떠한 일을 cpu가 쉬지 않고 일을 한 경우 그 값을 1.0이라고 한다. 만일 지정된 기간에 절반 동안 idle 상태에 빠져 있으면 0.5라고 한다. 그런데 밀려 있는 일이 있으면 그 량만큼 더해 산정하여 1을 초과하게 된다.

예) 1분 동안 같은 양의 작업을 10개를 수행하는 cpu가 있다 할 때 1분 동안 30개의 작업이 주어지면 10개는 처리를 하고 20개는 처리하지 못한 상태가 된다. 이러한 경우 cpu 로드는 3.0이라 한다.

예) 위와 동일한 조건으로 cpu가 2개 준비된 경우 cpu 로드는 1.5라 한다.

 

리눅스에서는 TASK_RUNNING 및 TASK_UNINTERRUPTIBLE 상태에 있는 태스크, 즉 active 태스크의 수를 어느 일정 기간 범위에서 주어진 간격으로 probe한 값을 사용하며 지수 평활법으로 연결하여 cpu 로드 값을 산출한다.

 

A. 글로벌 로드 평균 (1min ~ 15min)

최근 1분, 5분, 15분 간의 평균 cpu 로드 값을 산출하여 avenrun[]에 저장하고 글로벌 로드 평균(global load average)라고도 불린다.

  • “uptime” 명령의 load average 필드의 3개의 값을 참고한다.
  • 또한 “/proc/loadavg” 파일을 확인하여 최초 3개의 값을 통해서도 확인할 수 있다.
$ uptime
 20:41:18 up  1:09,  2 users,  load average: 0.57, 0.15, 0.11
$ cat /proc/loadavg 
0.55 0.28 0.16 1/318 2112
  • nr_active = 각 cpu의 런큐에 있는 running 및 uninterruptible 태스크의 수를 더한다.
  • avenrun[0] = avenrun[0]*e1 + nr_active*(1-e1) + 0.5      <- 1분
  • avenrun[1] = avenrun[1]*e2 + nr_active*(1-e2) + 0.5      <- 5분
  • avenrun[2] = avenrun[2]*e3 + nr_active*(1-e3) + 0.5      <- 15분

 

B. 런큐 로드 평균 (1 tick ~ 16 ticks)

  • 매 tick 마다 평균 cpu 로드를 산출하여 rq->cpu_load[5]에 저장하고 로드밸런스를 위해 사용된다.
  • rq->cpu_load[]에 5개의 cpu 로드가 저장되는데 각각의 기간은 2배씩 커진다.
    • cpu_load[0] <- 1 tick 기간
    • cpu_load[1] <- 2 ticks 기간
    • cpu_load[1] <- 4 ticks 기간
    • cpu_load[3] <- 8 ticks 기간
    • cpu_load[4] <- 16 ticks 기간
  • “/proc/sched_debug” 파일을 확인하여
# cat /proc/sched_debug 
Sched Debug Version: v0.11, 4.4.11-v7+ #888
ktime                                   : 4393169013.219659
sched_clk                               : 4393169057.443466
cpu_clk                                 : 4393169057.443935
jiffies                                 : 439286901

sysctl_sched
  .sysctl_sched_latency                    : 18.000000
  .sysctl_sched_min_granularity            : 2.250000
  .sysctl_sched_wakeup_granularity         : 3.000000
  .sysctl_sched_child_runs_first           : 0
  .sysctl_sched_features                   : 44859
  .sysctl_sched_tunable_scaling            : 1 (logaritmic)

cpu#0
  .nr_running                    : 0
  .load                          : 0
  .nr_switches                   : 145928196
  .nr_load_updates               : 57706792
  .nr_uninterruptible            : -324009
  .next_balance                  : 439.286901
  .curr->pid                     : 0
  .clock                         : 4393169054.864143
  .clock_task                    : 4393169054.864143
  .cpu_load[0]                   : 81
  .cpu_load[1]                   : 41
  .cpu_load[2]                   : 21
  .cpu_load[3]                   : 11
  .cpu_load[4]                   : 6

 

C. PELT(Per Entity Lod Tracking)

  • 러너블 로드 평균(runnable load average) 및 블럭드 로드 평균(blocked load average)라고도 불린다.
  • 커널 v3.8부터 사용되었고 cpu_load와 같이 로드밸런스를 위해 사용된다.
  • task가 enqueue/dequeue 될 때마다 갱신한다.
  • 단위 기간은 1ms(1024us)이고 로드는 단위 시간마다 decay된다.
    • 현재 시간으로부터 단위 기간이 점점 흘러가는 경우 점점 decay 되는 양이 커진다.
    • = + × + × + × + ⋯
    • 32번째 단위 시간에 대해 decay 값은 절반으로 한다.
      • y^32=0.5
      • y=0.5^(1/32)
      • y = 약 0.97857206
# cat /proc/sched_debug 

(...생략...)

cfs_rq[0]:/autogroup-677
  .exec_clock                    : 0.000000
  .MIN_vruntime                  : 0.000001
  .min_vruntime                  : 1599.476675
  .max_vruntime                  : 0.000001
  .spread                        : 0.000000
  .spread0                       : -121602963.722830
  .nr_spread_over                : 0
  .nr_running                    : 0
  .load                          : 0
  .load_avg                      : 7
  .runnable_load_avg             : 3
  .util_avg                      : 7
  .removed_load_avg              : 0
  .removed_util_avg              : 0
  .tg_load_avg_contrib           : 7
  .tg_load_avg                   : 7

 

A. 글로벌 로드 평균 – avenrun[] 산출 – (1, 5, 15분)

글로벌 로드 평균은 매 스케줄 틱에서 호출되지만 산출 주기(calc_load_update: 기본 5초)에 한 번씩 갱신한다. 엄밀히 말하자면 산출 주기가 도래하면 그 후 10틱의 시간이 지난 후에 갱신한다.

calc_global_load()

kernel/sched/loadavg.c

/*
 * calc_load - update the avenrun load estimates 10 ticks after the
 * CPUs have updated calc_load_tasks.
 */
void calc_global_load(unsigned long ticks) 
{
        long active, delta;

        if (time_before(jiffies, calc_load_update + 10))
                return;

        /*
         * Fold the 'old' idle-delta to include all NO_HZ cpus.
         */ 
        delta = calc_load_fold_idle();
        if (delta)
                atomic_long_add(delta, &calc_load_tasks);

        active = atomic_long_read(&calc_load_tasks);
        active = active > 0 ? active * FIXED_1 : 0;

        avenrun[0] = calc_load(avenrun[0], EXP_1, active);
        avenrun[1] = calc_load(avenrun[1], EXP_5, active);
        avenrun[2] = calc_load(avenrun[2], EXP_15, active);

        calc_load_update += LOAD_FREQ;

        /*
         * In case we idled for multiple LOAD_FREQ intervals, catch up in bulk.
         */
        calc_global_nohz();
}

cpu 로드 산출 주기(5초) 이후 10 틱이 지난 후에 최근 1분, 5분, 15분 간의 cpu 로드를 산출하여 avenrun[]에 대입한다.

  • 코드 라인 9~10에서 현재 시각(jiffies)이 cpu 로드 산출 주기(5초)+10 이전이면 함수를 빠져나간다.
  • 코드 라인 15~17에서 현재 cpu에 대해 active 태스크 수의 변화분 delta를 얻어와서 calc_load_tasks에 반영한다.
  • 코드 라인 19~20에서 active 태스크가 있는 경우 그 수에 cpu 로드 1.0에 해당하는 값 2048을 곱한다.
    • 예) active=4096인 경우 cpu 로드는 2.0이다.
  • 코드 라인 22~24에서 기존 cpu 로드 값과 avenrun[]과 새 cpu 로드 값인 active 값으로 각각 1분, 5분, 15분에 해당하는 지수 팩터 EXP_n을 사용하여 cpu 로드를 산출한 후 avenrun[]에 대입한다.
  • 코드 라인 26에서 다음 cpu 로드 산출 주기를 위해 5초를 더한다.
  • 코드 라인 31에서 nohz idle로 인해 다음 cpu 로드 산출 주기를 이미 초과한 경우 miss된 cpu 로드 갱신 주기 수만큼 적용하여 cpu 로드를 산출하여 avenrun[]을 다시 갱신한다.
    • 예) 20여초 nohz idle로 인해 cpu 로드를 갱신하지 못한 경우 처음 5초에 해당하는 시간의 cpu 로드가 이미 갱신되었으므로 나머지 3번에 해당하는 cpu 로드를 산출하도록 한다.

 

Fake cpu 로드 계산을 위한 11비트 지수 상수 값

/*
 * These are the constant used to fake the fixed-point load-average
 * counting. Some notes:
 *  - 11 bit fractions expand to 22 bits by the multiplies: this gives
 *    a load-average precision of 10 bits integer + 11 bits fractional
 *  - if you want to count load-averages more often, you need more
 *    precision, or rounding will get you. With 2-second counting freq,
 *    the EXP_n values would be 1981, 2034 and 2043 if still using only
 *    11 bit fractions.
 */
extern unsigned long avenrun[];         /* Load averages */
extern void get_avenrun(unsigned long *loads, unsigned long offset, int shift);

#define FSHIFT          11              /* nr of bits of precision */
#define FIXED_1         (1<<FSHIFT)     /* 1.0 as fixed-point */
#define LOAD_FREQ       (5*HZ+1)        /* 5 sec intervals */
#define EXP_1           1884            /* 1/exp(5sec/1min) as fixed-point */
#define EXP_5           2014            /* 1/exp(5sec/5min) */ 
#define EXP_15          2037            /* 1/exp(5sec/15min) */
  • FSHIFT
    • 11비트 정확도를 사용하는데 필요한 비트 수
  • FIXED_1
    • 11비트 정확도 값 (2048)
    • 고정 소숫점 형태인 cpu 로드 1.0은 리눅스 구현에서는 2048이라는 정수로 표현한다.
  • LOAD_FREQ
    • 디폴트 5초 주기 산출
  • EXP_1
    • 마지막 1분 동안의 cpu 로드를 산출하기 위해 11비트 정확도 값 2048의 약 92%를 적용하여 반영한다.
    • 1/(exp(1/12)) * FIXED_1 = 92.00% * 2048 = 1884
  • EXP_5
    • 마지막 5분 동안의 cpu 로드를 산출하기 위해 11비트 정확도 값 2048의 약 98%를 적용하여 반영한다.
    • 1/(exp(1/60)) * FIXED_1 = 98.35% * 2048 = 2014
  • EXP_15
    • 마지막 15분 동안의 cpu 로드를 산출하기 위해 11비트 정확도 값 2048의 약 99%를 적용하여 반영한다.
    • 1/(exp(1/60)) * FIXED_1 = 99.45% * 2048 = 2037

 

다음 그림은 1분, 5분, 15분에 해당하는 지수 팩터 EXP_1, EXP_5, EXP_15가 어떻게 산출되었는지를 보여준다.

  • k(12) = EXP_1 = 0.9200 (=1884)
  • k(60) = EXP_5 = 0.9835 (=2014)
  • k(180) = EXP_15 = 0.9945 (=2037)

 

다음 그림은 위의 지수 팩터를 사용하여 리눅스에서 구현된 cpu 로드 산출 식이다.

 

다음 그림은 처음 cpu 로드 0.5에서 출발하여 매 5초 마다 cpu 로드가 산출되는 과정을 보여주며 마지막에서는 nohz idle로 인해 20초간 틱이 발생되지 않아 밀려 있는 cpu 로드 계산이 한꺼번에 이루어지는 것을 보여준다.

 

active 태스크 수

cpu 로드를 산출하기 위해 active 태스크 수를 파악해야 한다. active 태스크 수는 러너블(러닝 및 런큐 대기중인) 상태의 태스크 뿐만 아니라 uninterruptible 상태로 슬립 중인 태스크도 포함시킨다. 로드를 산출하는데 uninterruptible 태스크를 포함시키는 이유는 주로 이 uninterruptible 태스크가 I/O 요청에 대한 대기 상태인 경우가 많고 이에 따라 I/O 요청에 대한 로드를 포함하는 것이 합리적인 판단이라서 포함시켰다.  확실히 이와 같은 형태의 글로벌 로드 산출 구현은 정확한 로드를 산출하는 것이 힘들다는 것을 알 수 있다. 그러므로 cpu 글로벌 로드 뿐만 아니라 여러 상태 지표를 동시에 사용하여야 시스템의 로드 상태를 파악할 수 있다.

 

active 태스크 수를 산출할 때 마다 각 cpu의 런큐를 뒤지지 않고 전역 변수 calc_load_tasks에 필요 시마다 전파하여 사용하는 방식을 사용하여 조금이라도 빠르게 산출되게 하였다. nohz idle을 위해 중간 단계에 calc_load_idle[2] 변수를 사용하여 active 태스크의 변동 분 delta를 저장하고 5초마다 로드가 산출될 때 calc_load_idle[2] 배열에서 인덱스를 교대로 사용하여 읽어낸다. 배열의 사용법은 조금 복잡하니 calc_load_fold_idle()에서 더 알아보자.

 

다음 그림은 nohz idle 상태로 진입할 때 active 태스크의 변동분을 저장하는 함수와 5초 주기로 글로벌 로드를 산출하는 함수의 흐름을 보여준다.

 

calc_load_fold_idle()

kernel/sched/loadavg.c

static long calc_load_fold_idle(void)
{
        int idx = calc_load_read_idx();
        long delta = 0;
        
        if (atomic_long_read(&calc_load_idle[idx]))
                delta = atomic_long_xchg(&calc_load_idle[idx], 0);

        return delta;
}

현재 cpu의 런큐에서 다시 계산된 active 태스크 수의 변경된 값 delta를 얻어온다.

  • 코드 라인 3에서 calc_load_idle[] 배열 중 어떤 값을 사용할지 인덱스 값을 알아온다.
  • 코드 라인 6에서 인덱스에 해당하는 calc_load_idle[] 값이 존재하는 경우 이 값을 0으로 초기화하고 저장되었던 값을 반환한다.

 

/*
 * Handle NO_HZ for the global load-average.
 *
 * Since the above described distributed algorithm to compute the global
 * load-average relies on per-cpu sampling from the tick, it is affected by
 * NO_HZ.
 *
 * The basic idea is to fold the nr_active delta into a global idle-delta upon
 * entering NO_HZ state such that we can include this as an 'extra' cpu delta
 * when we read the global state.
 *
 * Obviously reality has to ruin such a delightfully simple scheme:
 *
 *  - When we go NO_HZ idle during the window, we can negate our sample
 *    contribution, causing under-accounting.
 *
 *    We avoid this by keeping two idle-delta counters and flipping them
 *    when the window starts, thus separating old and new NO_HZ load.
 *
 *    The only trick is the slight shift in index flip for read vs write.
 *
 *        0s            5s            10s           15s
 *          +10           +10           +10           +10
 *        |-|-----------|-|-----------|-|-----------|-|
 *    r:0 0 1           1 0           0 1           1 0
 *    w:0 1 1           0 0           1 1           0 0
 *
 *    This ensures we'll fold the old idle contribution in this window while
 *    accumlating the new one.
 *
 *  - When we wake up from NO_HZ idle during the window, we push up our
 *    contribution, since we effectively move our sample point to a known
 *    busy state.
 *
 *    This is solved by pushing the window forward, and thus skipping the
 *    sample, for this cpu (effectively using the idle-delta for this cpu which
 *    was in effect at the time the window opened). This also solves the issue
 *    of having to deal with a cpu having been in NOHZ idle for multiple
 *    LOAD_FREQ intervals.
 *
 * When making the ILB scale, we should try to pull this in as well.
 */
static atomic_long_t calc_load_idle[2];
static int calc_load_idx;

 

nohz idle 영향으로 인해 변경된 해당 cpu의 active 태스크 수 delta 값을 calc_load_idle[2]에 저장을 하는데 저장 위치는 5초 갱신 주기마다 교대로 바뀐다. 이러한 delta 값을 읽어내는 루틴에서는 매 5초 + 10 틱마다 지난 5초 이내에 변동된 delta 값을 읽어낸다. 읽어내는 시점의 10 tick 범위는 다음에 읽도록 한다.

  • calc_load_read_idx() 함수를 통해 calc_load_idx 값의 하위 1비트만 읽어서 0과 1의 인덱스 값으로 calc_load_idle[] 값을읽어온다.
  • 매 5초+10틱에서 calc_load_idx 값을 증가시킨다.
  • calc_load_write_idx() 함수를 통해 calc_load_idx 값의 하위 1비트만 읽어내는데 10 tick 구간은 flip 시킨다. 이렇게 알아온 0과 1의 인덱스 값으로 calc_load_idle[] 값을읽어온다.

 

calc_load()

kernel/sched/proc.c

/*
 * a1 = a0 * e + a * (1 - e)
 */
static unsigned long
calc_load(unsigned long load, unsigned long exp, unsigned long active)
{
        load *= exp;
        load += active * (FIXED_1 - exp);
        load += 1UL << (FSHIFT - 1);
        return load >> FSHIFT;
}

지수 active 태스크 수에 대한 지수 감소 평균(EDA)을 사용하여 산출한다.

 

예) 기존 1,5,15분간 cpu 로드=0.5이고 이번 틱에 active 태스크=2인 상태로 3번의 틱 만큼 진행을 하면

  • 산출 전:
    • avenrun[0]=1024, active=4096
    • avenrun[1]=1024, active=4096
    • avenrun[2]=1024,active=4096
  • 1st 틱:
    • avenrun[0]=(1024 * 1884 + 4096 * (2048-1884) + 1024) / 2048 = 1271
    • avenrun[1]=(1024 * 2014 + 4096 * (2048-2014) + 1024) / 2048 = 1076
    • avenrun[2]=(1024 * 2037 + 4096 * (2048-2037) + 1024) / 2048 = 1041
  • 2nd 틱:
    • avenrun[0]=(1271 * 1884 + 4096 * (2048-1884) + 1024) / 2048 = 1498
    • avenrun[1]=(1076 * 2014 + 4096 * (2048-2014) + 1024) / 2048 = 1127
    • avenrun[2]=(1041 * 2037 + 4096 * (2048-2037) + 1024) / 2048 = 1058
  • 3rd 틱:
    • avenrun[0]=(1498 * 1884 + 4096 * (2048-1884) + 1024) / 2048 = 1707
    • avenrun[1]=(1127 * 2014 + 4096 * (2048-2014) + 1024) / 2048 = 1177
    • avenrun[2]=(1058 * 2037 + 4096 * (2048-2037) + 1024) / 2048 = 1075

 

calc_global_nohz()

kernel/sched/proc.c

/*
 * NO_HZ can leave us missing all per-cpu ticks calling
 * calc_load_account_active(), but since an idle CPU folds its delta into
 * calc_load_tasks_idle per calc_load_account_idle(), all we need to do is fold
 * in the pending idle delta if our idle period crossed a load cycle boundary.
 *
 * Once we've updated the global active value, we need to apply the exponential
 * weights adjusted to the number of cycles missed.
 */
static void calc_global_nohz(void)
{
        long delta, active, n;

        if (!time_before(jiffies, calc_load_update + 10)) {
                /*
                 * Catch-up, fold however many we are behind still
                 */
                delta = jiffies - calc_load_update - 10;
                n = 1 + (delta / LOAD_FREQ);

                active = atomic_long_read(&calc_load_tasks);
                active = active > 0 ? active * FIXED_1 : 0;

                avenrun[0] = calc_load_n(avenrun[0], EXP_1, active, n);
                avenrun[1] = calc_load_n(avenrun[1], EXP_5, active, n);
                avenrun[2] = calc_load_n(avenrun[2], EXP_15, active, n);

                calc_load_update += n * LOAD_FREQ;
        }

        /*
         * Flip the idle index...
         *
         * Make sure we first write the new time then flip the index, so that
         * calc_load_write_idx() will see the new time when it reads the new
         * index, this avoids a double flip messing things up.
         */
        smp_wmb();
        calc_load_idx++;
}

nohz idle로 인해 갱신이 밀려 있는 경우 그 밀려 있는 횟수 만큼 한 번에 산출을 하여 avenrun[]에 대입한다.

  • 코드 라인 14에서 현재 시간(jiffies)이 갱신 주기+10틱보다 뒤에 있는 경우 즉, 갱신이 밀려 있는 경우
  • 코드 라인 18~19에서 몇 번 밀려 있는지 횟수를 산출한다.
    • 예) jiffies와ㅓ calc_load_update의 차이가 21초인 경우 21/5+1 = 정수 5가된다.
  • 코드 라인 21~22에서 현재 active 태스크 수를 읽어와서 그 값에 FIXED_1(2048)을 곱한다.
  • 코드 라인 24~28에서 avenrun[] 값을 갱신하고 갱신 주기도 update한다.
  • 코드 라인 39에서 calc_load_idx를 증가시켜 새로운 인덱스를 사용하도록 한다.

 

calc_load_n()

kernel/sched/proc.c

/*
 * a1 = a0 * e + a * (1 - e)
 *
 * a2 = a1 * e + a * (1 - e)
 *    = (a0 * e + a * (1 - e)) * e + a * (1 - e)
 *    = a0 * e^2 + a * (1 - e) * (1 + e)
 *
 * a3 = a2 * e + a * (1 - e)
 *    = (a0 * e^2 + a * (1 - e) * (1 + e)) * e + a * (1 - e)
 *    = a0 * e^3 + a * (1 - e) * (1 + e + e^2)
 *
 *  ...
 *
 * an = a0 * e^n + a * (1 - e) * (1 + e + ... + e^n-1) [1]
 *    = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e)
 *    = a0 * e^n + a * (1 - e^n)
 *
 * [1] application of the geometric series:
 *
 *              n         1 - x^(n+1)
 *     S_n := \Sum x^i = -------------
 *             i=0          1 - x
 */
static unsigned long
calc_load_n(unsigned long load, unsigned long exp,
            unsigned long active, unsigned int n)
{

        return calc_load(load, fixed_power_int(exp, FSHIFT, n), active);
}

기존 load 값에 새 active 값이 exp(간격)으로 FSHIFT(2048) 정확도로 산출한다.

  • 예) exp=1884(1분 주기), FSHIFT=2048(정확도), load=1024, active=2048, n=4
    • = load * (exp / FSHIFT) + (active * (FSHIFT – exp) / 2048) + 0.5 를 4번 수행
    • = load * (exp^n / 2048^n) + (active * (1 – (exp^n / 2048^n)) + 0.5와 동일
    • = 1024 * (1884^4 / 2048^4) + (active * (1 – (1884^4) / 2048^4) + 0.5
    • = 1896

 

active 태스크 수가 변함 없이 n 번의 횟수만큼 계산되는 결과와 동일하다.

 

fixed_power_int()

kernel/sched/proc.c

/**
 * fixed_power_int - compute: x^n, in O(log n) time
 *
 * @x:         base of the power
 * @frac_bits: fractional bits of @x
 * @n:         power to raise @x to.
 *
 * By exploiting the relation between the definition of the natural power
 * function: x^n := x*x*...*x (x multiplied by itself for n times), and
 * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i,
 * (where: n_i \elem {0, 1}, the binary vector representing n),
 * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is
 * of course trivially computable in O(log_2 n), the length of our binary
 * vector.
 */
static unsigned long
fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n)
{
        unsigned long result = 1UL << frac_bits;

        if (n) for (;;) {
                if (n & 1) {
                        result *= x;
                        result += 1UL << (frac_bits - 1);
                        result >>= frac_bits;
                }
                n >>= 1;
                if (!n)
                        break;
                x *= x;
                x += 1UL << (frac_bits - 1);
                x >>= frac_bits;
        }

        return result;
}

(x^n) / (2^frac_bits)^(n-1) 를 산출한다. 산출 시 n번 만큼 반복하지 않고 O(log2 n)번으로 산출되는 것이 특징으로 n 값이 클 때 효과적이다.

  • 예) x=1884 (EXP_1), frac_bits=11 (11비트 정밀도), n=5
    • = (1884 * 1884 * 1884 * 1884 * 1884) / (2048 * 2048 * 2048 * 2048) = 1,349

 

B. 런큐 로드 평균 – rq->cpu_load[] 산출 – (1, 2, 4, 8, 16 ticks)

update_cpu_load_active()

kernel/sched/proc.c

/*
 * Called from scheduler_tick()
 */
void update_cpu_load_active(struct rq *this_rq)
{
        unsigned long load = get_rq_runnable_load(this_rq);
        /*
         * See the mess around update_idle_cpu_load() / update_cpu_load_nohz().
         */
        this_rq->last_load_update_tick = jiffies;
        __update_cpu_load(this_rq, load, 1);

        calc_load_account_active(this_rq);
}

요청한 런큐의 cpu 로드 active를 갱신한다.

  • 코드 라인 6에서 런큐의 load 평균 값을 알아온다.
  • 코드 라인 10에서 현재 시각(jiffies)으로 cpu 로드가 산출되었음을 기록한다.
  • 코드 라인 11에서 cpu 로드를 산출한다.
  • 코드 라인 13에서 5초 간격으로 전역 calc_load_tasks 값을 갱신한다.
    • 매 스케줄 tick 마다 nr_active를 산출하지 않기 위해 5초 간격으로 nr_active를 산출하여 그 차이 값 만큼만 calc_load_tasks에 반영한다.

 

다음 그림은 런큐의 cpu 로드가 산출되기 위해 처리되는 흐름을 보여준다.

 

get_rq_runnable_load()

kernel/sched/proc.c

#ifdef CONFIG_SMP
static inline unsigned long get_rq_runnable_load(struct rq *rq)
{
        return rq->cfs.runnable_load_avg;
}
#else
static inline unsigned long get_rq_runnable_load(struct rq *rq)
{
        return rq->load.weight;
}
#endif

런큐의 로드 평균 값을 반환한다.

  • enqueue_entity_load_avg(), dequeue_entity_load_avg(), update_entity_load_avg() 함수 등에서 cfs 태스크들의 load 평균이 산출된다.

 

__update_cpu_load()

kernel/sched/proc.c

/*
 * Update rq->cpu_load[] statistics. This function is usually called every
 * scheduler tick (TICK_NSEC). With tickless idle this will not be called
 * every tick. We fix it up based on jiffies.
 */
static void __update_cpu_load(struct rq *this_rq, unsigned long this_load,
                              unsigned long pending_updates)
{
        int i, scale;

        this_rq->nr_load_updates++;

        /* Update our load: */
        this_rq->cpu_load[0] = this_load; /* Fasttrack for idx 0 */
        for (i = 1, scale = 2; i < CPU_LOAD_IDX_MAX; i++, scale += scale) {
                unsigned long old_load, new_load;

                /* scale is effectively 1 << i now, and >> i divides by scale */

                old_load = this_rq->cpu_load[i];
                old_load = decay_load_missed(old_load, pending_updates - 1, i);
                new_load = this_load;
                /*
                 * Round up the averaging division if load is increasing. This
                 * prevents us from getting stuck on 9 if the load is 10, for
                 * example.
                 */
                if (new_load > old_load)
                        new_load += scale - 1;

                this_rq->cpu_load[i] = (old_load * (scale - 1) + new_load) >> i;
        }

        sched_avg_update(this_rq);
}

jiffies 기반 tick 마다 런큐의 cpu 로드를 갱신한다.

  • 코드 라인 11에서 nr_load_updates 카운터를 1 증가시킨다. (단순 카운터)
  • 코드 라인 14에서 cpu_load[0]에는 load 값을 100% 반영한다.
  • 코드 라인 15에서 cpu_load[1] ~ cpu_load[4]까지 갱신하기 위해 루프를 돈다. 루프를 도는 동안 scale 값은 2, 4, 8, 16과 같이 2배씩 커진다.
  • 코드 라인 20~21에서 4개 배열에 있는 기존 cpu 로드값들은 지연 틱 값에 의해 미리 준비된 테이블의 값을 참고하여 decay load 값으로 산출된다.
    • decay_load = old_load * miss 틱을 사용한 decay factor
  • 코드 라인28~29에서 새 로드가 기존 로드보다 큰 경우에 한하여 즉, 로드가 상승되는 경우 올림을 할 수 있도록 새 로드에 scale-1을 추가한다.
  • 코드 라인 31에서 기존 로드에 (2^i-1)/2^i 의 비율을 곱하고 새 로드에 1/(2^i) 비율을 곱한 후 더한다.
    •  i=1:
      • cpu_load[1] = decay_load * 1/2 + new_load * 1/2
    • i=2:
      • cpu_load[2] = decay_load * 3/4 + new_load * 1/4
    • i=3:
      • cpu_load[3] = decay_load * 7/8 + new_load * 1/8
    • i=4
      • cpu_load[4] = decay_load * 15/16 + new_load * 1/16
  • 코드 라인 34에서 런큐의 age_stamp와 rt_avg 값을 갱신한다.

 

 

다음 그림은 cpu_load[]를 산출하는 식이다.

 

다음 그림은 런큐의 cpu_load[] 값이 매 tick 마다 변화되는 모습을 보여준다.

 

decay_load_missed()

kernel/sched/proc.c

/*
 * Update cpu_load for any missed ticks, due to tickless idle. The backlog
 * would be when CPU is idle and so we just decay the old load without
 * adding any new load.
 */
static unsigned long
decay_load_missed(unsigned long load, unsigned long missed_updates, int idx)
{
        int j = 0;

        if (!missed_updates)
                return load;

        if (missed_updates >= degrade_zero_ticks[idx])
                return 0;

        if (idx == 1)
                return load >> missed_updates;

        while (missed_updates) {
                if (missed_updates % 2)
                        load = (load * degrade_factor[idx][j]) >> DEGRADE_SHIFT;

                missed_updates >>= 1;
                j++;
        }
        return load;
}

nohz idle 기능이 동작하여 tick이 발생하지 않은 횟수를 사용하여 미리 계산된 테이블에서 load 값을 산출한다.

  • 코드 라인 11~12에서 miss 틱이 없는 경우 그냥 load 값을 그대로 반환한다.
  • 코드 라인 14~15에서 miss 틱이 idx 순서대로 8, 32, 64, 128 값 이상인 경우 너무 작은 load 값을 반영해봤자 미미하므로 load 값으로 0을 반환한다.
  • 코드 라인 17~18에서 인덱스 값이 1인 경우 load 값을 miss 틱 만큼 우측으로 쉬프트한다.
  • 코드 라인 20~26에서 missed_updates 값의 하위 비트부터 설정된 경우 이 위치에 해당하는 테이블에서 값을 곱하고 128로 나눈다.

 

다음 그림은 idx=2, miss 틱=13이 주어졌고 이에 해당하는 decay 로드 값을 구하는 모습을 보여준다.

 

/*
 * The exact cpuload at various idx values, calculated at every tick would be
 * load = (2^idx - 1) / 2^idx * load + 1 / 2^idx * cur_load
 *
 * If a cpu misses updates for n-1 ticks (as it was idle) and update gets called
 * on nth tick when cpu may be busy, then we have:
 * load = ((2^idx - 1) / 2^idx)^(n-1) * load
 * load = (2^idx - 1) / 2^idx) * load + 1 / 2^idx * cur_load
 *
 * decay_load_missed() below does efficient calculation of
 * load = ((2^idx - 1) / 2^idx)^(n-1) * load
 * avoiding 0..n-1 loop doing load = ((2^idx - 1) / 2^idx) * load
 *
 * The calculation is approximated on a 128 point scale.
 * degrade_zero_ticks is the number of ticks after which load at any
 * particular idx is approximated to be zero.
 * degrade_factor is a precomputed table, a row for each load idx.
 * Each column corresponds to degradation factor for a power of two ticks,
 * based on 128 point scale.
 * Example:
 * row 2, col 3 (=12) says that the degradation at load idx 2 after
 * 8 ticks is 12/128 (which is an approximation of exact factor 3^8/4^8).
 *
 * With this power of 2 load factors, we can degrade the load n times
 * by looking at 1 bits in n and doing as many mult/shift instead of
 * n mult/shifts needed by the exact degradation.
 */
#define DEGRADE_SHIFT           7
static const unsigned char
                degrade_zero_ticks[CPU_LOAD_IDX_MAX] = {0, 8, 32, 64, 128};

idx별로 miss 틱에 대한 반영 비율을 적용할 지 여부를 확인하기 위한 테이블이다.

  • miss 틱 수가 idx에 따른 테이블 값 이상으로 오래된 경우 기존 load 값을 사용할 필요 없다.
  • 예) idx=2, miss 틱=33인 경우 기존 cpu 로드 값을 0으로 간주하게 한다.

 

static const unsigned char
                degrade_factor[CPU_LOAD_IDX_MAX][DEGRADE_SHIFT + 1] = {
                                        {0, 0, 0, 0, 0, 0, 0, 0},
                                        {64, 32, 8, 0, 0, 0, 0, 0},
                                        {96, 72, 40, 12, 1, 0, 0},
                                        {112, 98, 75, 43, 15, 1, 0},
                                        {120, 112, 98, 76, 45, 16, 2} };

idx 별로 miss 틱에 대한 decay_load를 구하기 위한 테이블이다. (각 값은 x/128에 해당하는 분자 값이다.)

  • 예) idx=2, miss 틱=6, load=1024 일 때
    • 분모가 128이고, miss 틱에 대한 비트에 해당하는 72와 40에 해당하는 분자 값을 사용한다.
    • decay_load = 1024 * 72/128 * 40/128 = 1024 * 2880 / 16384 = 180

 

평균 스케쥴 갱신

sched_avg_update()

kernel/sched/core.c

void sched_avg_update(struct rq *rq)
{
        s64 period = sched_avg_period();

        while ((s64)(rq_clock(rq) - rq->age_stamp) > period) {
                /*
                 * Inline assembly required to prevent the compiler
                 * optimising this loop into a divmod call.
                 * See __iter_div_u64_rem() for another example of this.
                 */
                asm("" : "+rm" (rq->age_stamp));
                rq->age_stamp += period;
                rq->rt_avg /= 2;
        }
}

런큐의 age_stamp와 rt_avg 값을 갱신한다.

  • 코드 라인 3에서 평균 스케줄 타임(ns)의 절반을 가져와서 period에 대입한다.
  • 코드 라인 5~14에서 런큐 클럭에서 age_stamp를 뺀 간격이 period보다 큰 경우에 한해 계속 루프를 돌며 age_stamp를 period만큼 더하고 rt_avg 값은 절반으로 나눈다.

 

sched_avg_period()

kernel/sched/sched.h

static inline u64 sched_avg_period(void)
{
        return (u64)sysctl_sched_time_avg * NSEC_PER_MSEC / 2;
}

평균 스케줄 타임(ns)의 절반을 가져온다.

 

5초 간격으로 active 태스크 수 산출

calc_load_account_active()

kernel/sched/proc.c

/*
 * Called from update_cpu_load() to periodically update this CPU's
 * active count.
 */
static void calc_load_account_active(struct rq *this_rq)
{
        long delta;

        if (time_before(jiffies, this_rq->calc_load_update))
                return;

        delta  = calc_load_fold_active(this_rq);
        if (delta)
                atomic_long_add(delta, &calc_load_tasks);

        this_rq->calc_load_update += LOAD_FREQ;
}

로드 산출 주기(5초) 간격으로 active 태스크 수를 전역 calc_load_tasks에 갱신한다.

  • 코드 라인 9~10에서 지정된 5초 만료시간이 안된 경우 함수를 빠져나간다.
  • 코드 라인 12~14에서 기존 active 태스크 수와 현재 산출한 active 태스크 수의 차이를 알아와서 calc_load_tasks에 추가하여 갱신한다.
  • 코드 라인 16에서 다음 산출할 시간을 위해 5초를 더한다.

 

다음 그림은 런큐의 active 태스크 수를 런큐와 전역 변수에 갱신하는 것을 보여준다.

 

calc_load_fold_active()

kernel/sched/proc.c

long calc_load_fold_active(struct rq *this_rq)
{
        long nr_active, delta = 0;

        nr_active = this_rq->nr_running;
        nr_active += (long) this_rq->nr_uninterruptible;

        if (nr_active != this_rq->calc_load_active) {
                delta = nr_active - this_rq->calc_load_active;
                this_rq->calc_load_active = nr_active;
        }

        return delta;
}

요청한 런큐의 기존 active 태스크 수와 현재 산출한 active 태스크 수의 차이를 산출한다.

  • 코드 라인 5~6에서 요청한 런큐의 active 태스크 수를 알아온다.
  • 코드 라인 8~13에서 런큐의 calc_load_active와 다른 경우 이 값을 갱신하고 그 차이를 delta 값으로 하여 반환한다.

 

C. PELT: Per-Entity Load Tracking

엔티티 로드 평균을 산출하는 update_entity_load_avg() 함수는 다음과 같은 함수에서 호출된다.

  • enqueue_entity_load_avg()
    • cfs 런큐에 태스크가 엔큐될 때
  • dequeue_eneity_load_avg()
    • cfs 런큐에서 태스크가 디큐될 때
  • put_prev_entity()
    • 현재 동작 중인 태스크를 런큐의 대기로 돌려질 때
  • entity_tick()
    • 스케줄 틱마다 호출될 때

 

엔큐 시 엔티티 로드 평균 산출

enqueue_entity_load_avg()

kernel/sched/fair.c

/* Add the load generated by se into cfs_rq's child load-average */
static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
                                                  struct sched_entity *se,
                                                  int wakeup)
{       
        /*
         * We track migrations using entity decay_count <= 0, on a wake-up
         * migration we use a negative decay count to track the remote decays
         * accumulated while sleeping.
         *
         * Newly forked tasks are enqueued with se->avg.decay_count == 0, they
         * are seen by enqueue_entity_load_avg() as a migration with an already
         * constructed load_avg_contrib.
         */
        if (unlikely(se->avg.decay_count <= 0)) {
                se->avg.last_runnable_update = rq_clock_task(rq_of(cfs_rq));
                if (se->avg.decay_count) {
                        /*
                         * In a wake-up migration we have to approximate the
                         * time sleeping.  This is because we can't synchronize
                         * clock_task between the two cpus, and it is not
                         * guaranteed to be read-safe.  Instead, we can
                         * approximate this using our carried decays, which are
                         * explicitly atomically readable.
                         */
                        se->avg.last_runnable_update -= (-se->avg.decay_count)
                                                        << 20;
                        update_entity_load_avg(se, 0);
                        /* Indicate that we're now synchronized and on-rq */
                        se->avg.decay_count = 0;
                }
                wakeup = 0;
        } else {
                __synchronize_entity_decay(se);
        }

        /* migrated tasks did not contribute to our blocked load */
        if (wakeup) {
                subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
                update_entity_load_avg(se, 0);
        }

        cfs_rq->runnable_load_avg += se->avg.load_avg_contrib;
        /* we force update consideration on load-balancer moves */
        update_cfs_rq_blocked_load(cfs_rq, !wakeup);
}

엔티티 로드 평균을 갱신한다.

  • 코드 라인 15~32에서 낮은 확률로 decay_count가 0이하인 경우 avg.last_runnable_update에서 음수 decay_count 만큼의 ms 단위의 기간을 감소시키고 decay_count는 0으로 변경한다. 그리고 엔티티 로드 평균을 구하고 wakeup 요청을 0으로 한다.
    • 처음 태스크가 fork된 경우 decay_count 값은 0이하 이다.
  • 코드 라인 33~35에서 스케줄 엔티티의 decay_count가 0을 초과한 경우 엔티티 decay를 동기화시킨다.
    • 스케줄 엔티티의 로드 평균 기여를 ‘cfs 런큐의 decay_counter – 스케줄 엔티티의 avg.decay_count’ 만큼 decay 한다.
  • 코드 라인 38~41에서 decay_count가 0을 초과하였었고, 인수wakeup 요청이 있는 경우 migrate된 태스크들은 blocked 로드에서 기여 값을 감소시키고 엔티티 로드 평균을 구한다.
  • 코드 라인 43에서 스케줄 엔티티에 있는 로드 평균 기여를 cfs 런큐의 러너블 로드 평균에  추가한다
  • 코드 라인 45에서 블럭드 로드를 갱신하고 러너블 평균과 더해 cfs 런큐의 tg_load_contrib와 태스크 그룹의 load_avg 에 추가한다.

 

rq_clock_task()

kernel/sched/sched.h

static inline u64 rq_clock_task(struct rq *rq) 
{
        lockdep_assert_held(&rq->lock);
        return rq->clock_task;
}

런큐의 clock_task 를 반환한다.

 

__synchronize_entity_decay()

kernel/sched/fair.c

/* Synchronize an entity's decay with its parenting cfs_rq.*/
static inline u64 __synchronize_entity_decay(struct sched_entity *se)
{
        struct cfs_rq *cfs_rq = cfs_rq_of(se);
        u64 decays = atomic64_read(&cfs_rq->decay_counter);

        decays -= se->avg.decay_count;
        se->avg.decay_count = 0;
        if (!decays)
                return 0;

        se->avg.load_avg_contrib = decay_load(se->avg.load_avg_contrib, decays);

        return decays;
}

스케줄 엔티티의 로드 평균 기여를 cfs 런큐의 decay_counter – 스케줄 엔티티의 avg.decay_count 만큼 decay 한다.

  • 코드 라인 5~10에서 cfs 런큐의 decay_counter에서 스케줄 엔티티의 decay_count 값을 뺀다. 스케줄 엔티티의 decay_count 값은 0으로 리셋한다. 적용할 decays 값이 없으면 결과 값을 0으로 함수를 빠져나간다.
  • 코드 라인 12에서 스케줄 엔티티의 load_avg_contrib를 decays 만큼 decay한다.
  • 코드 라인 14에서 decays 값으로 함수를 빠져나간다.

 

다음 그림은 cfs 런큐에 소속된 하나의 스케줄 엔티티에 대해 decay할 기간을 적용시킨 모습을 보여준다.

 

디큐 시 엔티티 로드 평균 산출

dequeue_entity_load_avg()

kernel/sched/fair.c

/*
 * Remove se's load from this cfs_rq child load-average, if the entity is
 * transitioning to a blocked state we track its projected decay using
 * blocked_load_avg.
 */
static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
                                                  struct sched_entity *se,
                                                  int sleep)
{
        update_entity_load_avg(se, 1);
        /* we force update consideration on load-balancer moves */
        update_cfs_rq_blocked_load(cfs_rq, !sleep);

        cfs_rq->runnable_load_avg -= se->avg.load_avg_contrib;
        if (sleep) {
                cfs_rq->blocked_load_avg += se->avg.load_avg_contrib;
                se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
        } /* migrations, e.g. sleep=0 leave decay_count == 0 */
}

스케줄 엔티티가 디큐되면서 수행할 로드 평균을 갱신한다. cfs 런큐의 러너블 로드 평균에서 스케줄 엔팉티의 로드 평균 기여를 감소시키고 인수 sleep=1 요청된 경우 cfs 런큐의 블럭드 로드 평균에 추가한다.

  • 코드 라인 10~12에서 디큐 관련 산출을 하기 전에 먼저 스케줄 엔티티의 로드 평균을 산출하고 블럭드 로드 평균까지 갱신한다.
  • 코드 라인 14에서 cfs 런큐의 러너블 로드 평균을 스케줄 엔티티의 로드 평균 기여분만큼 감소시킨다.
  • 코드 라인 15~18에서 인수 sleep=1인 경우 감소 시킨 기여분을 cfs 런큐의 블럭드 로드 평균에 추가하고 cfs 런큐의 decay_counter를 스케줄 엔티티에 복사한다.

 

다음 그림은 dequeue_eneity_load_avg() 함수의 처리 과정을 보여준다.

 

Idle 관련 엔티티 로드 평균 산출

idle 상태로 진입하거나 빠져나올 때마다 러너블 평균을 산출한다.

idle_enter_fair()

kernel/sched/fair.c

/*
 * Update the rq's load with the elapsed running time before entering
 * idle. if the last scheduled task is not a CFS task, idle_enter will
 * be the only way to update the runnable statistic.
 */
void idle_enter_fair(struct rq *this_rq)
{
        update_rq_runnable_avg(this_rq, 1);
}

idle 상태로 진입하기 전에  러너블 평균을 갱신한다.

 

idle_exit_fair()

kernel/sched/fair.c

/*
 * Update the rq's load with the elapsed idle time before a task is
 * scheduled. if the newly scheduled task is not a CFS task, idle_exit will
 * be the only way to update the runnable statistic.
 */
void idle_exit_fair(struct rq *this_rq)
{
        update_rq_runnable_avg(this_rq, 0);
}

idle 상태에서 빠져나오면 러너블 평균을 갱신하고 그 값을 태스크 그룹에도 반영한다.

 

틱 마다 스케줄 엔티티에 대한 PELT 갱신과 preemption 요청 체크

스케줄 틱마다 호출되는 scheduler_tick() 함수와 hr 틱마다 호출되는 hrtick()  함수는 현재 curr에서 동작하는 태스크의 스케줄러의 (*task_tick) 후크 함수를 호출한다. 예를 들어 현재 런큐의 curr가 cfs 태스크인 경우 task_tick_fair() 함수가 호출되는데 태스크와 관련된 스케줄 엔티티부터 최상위 스케줄 엔티티까지 entity_tick() 함수를 호출하여 PELT와 관련된 함수들을 호출하고 스케줄 틱으로 호출된 경우 리스케줄 여부를 체크하고 hr 틱으로 호출되는 경우 무조건 리스케줄 요청한다.

  • 함수 호출 경로 예)
    • 스케줄 틱: scheduler_tick() -> task_tick_fair() -> entity_tick()
      • entity_tick() 함수를 호출할 때 인수 queued=0으로 호출된다.
    • hr 틱: hrtick() -> task_tick_fair() -> entity_tick()
      • entity_tick() 함수를 호출할 때 인수 queued=1로 호출된다.

 

다음 그림은 entity_tick()에 대한 함수 흐름을 보여준다.

entity_tick()

kernel/sched/fair.c

static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
        /*
         * Update run-time statistics of the 'current'.
         */
        update_curr(cfs_rq);

        /*
         * Ensure that runnable average is periodically updated.
         */
        update_entity_load_avg(curr, 1);
        update_cfs_rq_blocked_load(cfs_rq, 1);
        update_cfs_shares(cfs_rq);

#ifdef CONFIG_SCHED_HRTICK
        /*
         * queued ticks are scheduled to match the slice, so don't bother
         * validating it and just reschedule.
         */
        if (queued) {
                resched_curr(rq_of(cfs_rq));
                return;
        }
        /*
         * don't let the period tick interfere with the hrtick preemption
         */
        if (!sched_feat(DOUBLE_TICK) &&
                        hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
                return;
#endif

        if (cfs_rq->nr_running > 1)
                check_preempt_tick(cfs_rq, curr);
}

이 함수는 스케줄 틱 또는 hr 틱을 통해 호출되며 인수로 요청한 엔티티에 대한 로드(PELT) 갱신과 preemption 필요를 체크한다.

  • 코드 라인 7에서 PELT 관련 산출을 하기 전에 사전 준비를 위해 인수로 요청한 스케줄 엔티티의 런타임 통계들을 갱신한다.
  • 코드 라인 12에서 엔티티의 로드 평균 기여값을 갱신한다.
  • 코드 라인 13에서 스케줄 엔티티가 포함된 cfs 런큐의 러너블 로드와 블럭드 로드를 합하여 기여분을 cfs 런큐와 tg에 갱신한다.
  • 코드 라인 14에서 shares * 비율(tg에서 cfs 런큐의 로드 기여값이 차지하는 일정 비율)을 사용하여 스케줄 엔티티의 weight을 갱신하고 cfs 런큐의 로드 weight도 갱신한다.
  • 코드 라인 16~24에서 hrtick을 사용하는 커널에서 hrtick() 함수를 통해 호출된 경우 인수 queued=1로 진입한다. 이 때에는 무조건 리스케줄 요청을 하고 함수를 빠져나간다.
  • 코드 라인 28~30에서 DOUBLE_TICK feature를 사용하지 않는 경우 hrtick을 프로그래밍한다.
    • rpi2: DOUBLE_TICK 기능을 사용하지 않는다.
  • 코드 라인 33~34에서 이 루틴은 hrtick을 제외한 스케줄 틱을 사용할 때에만 진입되는데 러너블 태스크가 2개 이상인 경우 preemption 체크를 수행한다.

 

스케줄 엔티티의 러너블 로드 평균  갱신

 

update_entity_load_avg()

kernel/sched/fair.c

/* Update a sched_entity's runnable average */
static inline void update_entity_load_avg(struct sched_entity *se,
                                          int update_cfs_rq)
{
        struct cfs_rq *cfs_rq = cfs_rq_of(se);
        long contrib_delta;
        u64 now;

        /*
         * For a group entity we need to use their owned cfs_rq_clock_task() in
         * case they are the parent of a throttled hierarchy.
         */
        if (entity_is_task(se))
                now = cfs_rq_clock_task(cfs_rq);
        else
                now = cfs_rq_clock_task(group_cfs_rq(se));

        if (!__update_entity_runnable_avg(now, &se->avg, se->on_rq))
                return;

        contrib_delta = __update_entity_load_avg_contrib(se);

        if (!update_cfs_rq)
                return;

        if (se->on_rq)
                cfs_rq->runnable_load_avg += contrib_delta;
        else
                subtract_blocked_load_contrib(cfs_rq, -contrib_delta);
}

스케줄 엔티티에 대한 러너블 로드 평균을 갱신한다. 인수로 cfs 런큐까지 갱신 요청하는 경우 기여도를 계산하여 cfs 런큐의 러너블 로드 평균도 갱신한다.

  • a) 스케줄 엔티티에 대한 러너블 로드 평균을 산출하기 위한 러너블 평균합(runnable_avg_sum) 및 러너블 평균 기간(runnable_avg_periods) 산출
    • 기존 러너블 평균합을 decay 시킨 값을 old라고 하고,
    • 산정할 기간을 decay한 값을 new라고 할 때
    • se->avg.runnable_avg_sum에는
      • 스케줄 엔티티에 대해 러너블 상태(러닝 포함)의 태스크에 대해서는  new + old 값을 반영하고, 러너블 상태가 아닌 태스크에 대해서는 old 값만 반영한다.
      • 추후 커널 소스에서는 러닝 상태를 별도로 관리한다.
    • se->avg.runnable_avg_periods에는
      • 스케줄 엔티티의 상태와 관계 없이 new + old 값을 반영한다.
  • b) cfs 런큐의 러너블 로드 평균 갱신
    • se->avg.load_avg_contrib

 

  • 코드 라인 13~16에서 스케줄 엔티티가 태스크인 경우 now에 스케줄 엔티티가 가리키는 cfs 런큐의 클럭 태스크 값을 대입하고 그렇지 않은 경우 태스크 그룹용 cfs 런큐의 클럭 태스크 값을 대입한다.
    • 외부에서 최상위 스케줄 엔티티까지 순회하며 이 함수를 호출하는 경우 가장 하위 cfs 런큐를 두 번 호출한다.
  • 코드 라인 18~19에서 엔티티 러너블 평균 갱신을 수행하고 실패한 경우 함수를 빠져나간다.
  • 코드 라인 21에서 엔티티 로드 평균 기여값을 갱신하고 그 delta 값을 controb_delta에 대입한다.
  • 코드 라인 23~24에서 인수 update_cfs_rq가 0인 경우 함수를 빠져나간다.
  • 코드 라인 26~29에서 스케줄 엔티티가 런큐에 있는 경우 러너블 로드 평균 값에 contrib_delta 값을 더하고 그렇지 않은 경우 blocked 로드 기여 값에 contrib_delta 값을 추가한다.

 

다음 그림은 __update_entity_load_avg() 함수가 스케줄 엔티티의 러너블 평균을 구하는 모습을 보여준다.

 

다음 그림은 스케줄 틱이 동작할 때 entity_tick() 함수에서 update_entity_load_avg() 함수를 호출할 때 동작하는 모습을 보여준다.

 

entity_is_task()

kernel/sched/fair.c

/* An entity is a task if it doesn't "own" a runqueue */
#define entity_is_task(se)      (!se->my_q)

스케줄 엔티티가 태스크인지 여부를 반환한다.

  • 태스크인 경우 se->cfs_rq를 사용하고 태스크 그룹을 사용하는 경우 se->my_q를 사용한다.

 

cfs_rq_clock_task()

kernel/sched/fair.c

/* rq->task_clock normalized against any time this cfs_rq has spent throttled */
static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq)
{
        if (unlikely(cfs_rq->throttle_count))
                return cfs_rq->throttled_clock_task;

        return rq_clock_task(rq_of(cfs_rq)) - cfs_rq->throttled_clock_task_time;
}

스로틀 카운트가 있는 경우 cfs->throttled_clock_task를 반환하고 그렇지 않은 경우 cfs_rq->clock_task에서 스로틀 클럭 태스크 시간을 뺀 값을 반환한다.

 

group_cfs_rq()

kernel/sched/fair.c

/* runqueue "owned" by this group */
static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
{
        return grp->my_q;
}

스케줄 엔티티의 런큐를 반환한다.

 

update_rq_runnable_avg()

kernel/sched/fair.c

static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
{
        __update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable);
        __update_tg_runnable_avg(&rq->avg, &rq->cfs);
}

엔티티 러너블 평균을 산출하고 태스크 그룹에 반영한다.

 

스케줄 엔티티의 러너블 평균합 갱신

__update_entity_runnable_avg()

kernel/sched/fair.c

/*
 * We can represent the historical contribution to runnable average as the
 * coefficients of a geometric series.  To do this we sub-divide our runnable
 * history into segments of approximately 1ms (1024us); label the segment that
 * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
 *
 * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
 *      p0            p1           p2
 *     (now)       (~1ms ago)  (~2ms ago)
 *
 * Let u_i denote the fraction of p_i that the entity was runnable.
 *
 * We then designate the fractions u_i as our co-efficients, yielding the
 * following representation of historical load:
 *   u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
 *
 * We choose y based on the with of a reasonably scheduling period, fixing:
 *   y^32 = 0.5
 *
 * This means that the contribution to load ~32ms ago (u_32) will be weighted
 * approximately half as much as the contribution to load within the last ms
 * (u_0).
 *
 * When a period "rolls over" and we have new u_0`, multiplying the previous
 * sum again by y is sufficient to update:
 *   load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
 *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
 */
static __always_inline int __update_entity_runnable_avg(u64 now,
                                                        struct sched_avg *sa,
                                                        int runnable)
{
        u64 delta, periods;
        u32 runnable_contrib;
        int delta_w, decayed = 0;

        delta = now - sa->last_runnable_update;
        /*
         * This should only happen when time goes backwards, which it
         * unfortunately does during sched clock init when we swap over to TSC.
         */
        if ((s64)delta < 0) {
                sa->last_runnable_update = now;
                return 0;
        }

        /*
         * Use 1024ns as the unit of measurement since it's a reasonable
         * approximation of 1us and fast to compute.
         */
        delta >>= 10;
        if (!delta)
                return 0;
        sa->last_runnable_update = now;

엔티티 러너블 평균을 산출한다.

  • rq->runnable_avg_sum
    • 태스크가 런큐에 있거나 동작중 일때의 러너블 평균 합
    • runnable load.on_rq=1
  • rq->runnable_avg_period
    • 태스크의 동작 유무와 관련 없이 러너블 평균 기간

 

  • 코드 라인 37에서 현재 시각 now에서 마지막 러너블 업데이트 갱신 시각을 뺀 값을 delta에 대입한다.
  • 코드 라인 42~45에서 delta가 음수인 경우 시간이 거꾸로 되돌려 졌다고 판단하고 예외 케이스로 last_runnable_update를 갱신하고 함수를 빠져나온다.
    • 부트업 타임에 발생할 가능성이 있다.
  • 코드 라인 51~53에서 PELT(Per Entity Load Tracking)의 스케쥴링 시간 처리 최소 단위는 1024ns(1us)이다 따라서 delta를 최소 단위 us단위로 바꾸고 만일 1us도 안되는 경우 함수를 빠져나간다.
  • 코드 라인 54에서 last_runnable_update에 현재 시각(ns)을 기록한다.

 

        /* delta_w is the amount already accumulated against our next period */
        delta_w = sa->runnable_avg_period % 1024;
        if (delta + delta_w >= 1024) {
                /* period roll-over */
                decayed = 1;

                /*
                 * Now that we know we're crossing a period boundary, figure
                 * out how much from delta we need to complete the current
                 * period and accrue it.
                 */
                delta_w = 1024 - delta_w;
                if (runnable)
                        sa->runnable_avg_sum += delta_w;
                sa->runnable_avg_period += delta_w;

                delta -= delta_w;

                /* Figure out how many additional periods this update spans */
                periods = delta / 1024;
                delta %= 1024;

                sa->runnable_avg_sum = decay_load(sa->runnable_avg_sum,
                                                  periods + 1);
                sa->runnable_avg_period = decay_load(sa->runnable_avg_period,
                                                     periods + 1);

                /* Efficiently calculate \sum (1..n_period) 1024*y^i */
                runnable_contrib = __compute_runnable_contrib(periods);
                if (runnable)
                        sa->runnable_avg_sum += runnable_contrib;
                sa->runnable_avg_period += runnable_contrib;
        }

        /* Remainder of delta accrued against u_0` */
        if (runnable)
                sa->runnable_avg_sum += delta;
        sa->runnable_avg_period += delta;

        return decayed;
}

PELT(Per-Entity Load Tracking)에 사용되는 러너블 평균 합계(sa->runnable_avg_sum)와 러너블 평균 기간(sa->runnable_avg_period)을 갱신한다.

  • 코드 라인 2에서 기존 산출된 평균 기간 runnable_avg_period를 1024us(약 1ms) 단위로 잘라 남는 기간을 delta_w에 대입한다.
  • 코드 라인 3~5에서 delta와 delta_w 값이 1ms 이상인 경우 decay 처리 한다.
    • PELT에서 1 스케쥴링(1ms)이 지나면 과거 로드에 그 기간만큼 decay 요율을 곱해서 산출한다.
  • 코드 라인 12에서 1024(약 1ms) PELT 스케쥴링 단위에서 delta_w를 빼면 남은 기간(us)이 산출된다. 이를 다시 delta_w에 대입한다.
  • 코드 라인 13~15에서 sa->runnable_avg_sum 및 sa->runnable_avg_period에 delta_w 값을 추가하여 PELT 스케줄링 최소 단위로 정렬하게 한다. 만일 인수 runnable이 0인 경우에는 sa->runnable_avg_sum은 갱신하지 않는다.
  • 코드 라인 17에서 delta 값에서 방금 처리한 delta_w를 감소시킨다.
  • 코드 라인 20~21에서 delta에 몇 개의 1ms 단위가 있는지 그 횟수를 periods에 대입한다. 이 값은 decay 횟수로 사용된다. 그리고 delta 값도 나머지 값만 사용한다.
  • 코드 라인 23~24에서 sa->runnable_avg_sum에 periods+1 만큼의 decay 횟수를 적용하여 다시 갱신한다.
  • 코드 라인 25~26에서 sa->runnable_avg_period에 periods+1 만큼의 decay 횟수를 적용하여 다시 갱신한다.
  • 코드 라인 29~32에서 runnable_contrib를 산출하여 sa->runnable_avg_sum 및 runnable_avg_period에 더해 갱신한다. 만일 인수 runnable이 0인 경우에는 sa->runnable_avg_sum은 갱신하지 않는다.
  • 코드 라인 36~40에서 남은 delta를 sa->runnable_avg_sum 및 runnable_avg_period에 더해 갱신하고 decay 여부를 반환한다. 만일 인수 runnable이 0인 경우에는 sa->runnable_avg_sum은 갱신하지 않는다.

 

다음 그림은 갱신 기간이 1ms가 못되어 decay를 수행하지 않는 경우의 모습을 보여준다.

 

다음 그림은 갱신 기간이 1ms를 초과하여 decay를 수행하는 경우의 모습을 보여준다.

 

기존(old) 평균의 감소(decay)

기존 로드 값에 대해 ms 단위의 지나간 기간 만큼의 감쇠 비율(decay factor)로 곱한다. decay 요율은 ‘y^32 = 0.5’를 사용하는데 32ms 이전의 값은 0.5의 감쇠 비율(decay factor)을 사용한다. 이러한 경우 기존 로드 값이 512라고 할 때 4ms의 기간이 지나 감소된 로드 값은 y^4가 된다. 먼저 y에 대한 값을 계산해 보면 y=0.5^(1/32) = 0.978572… 가 산출된다. 이제 결정된 y 값을 사용하여 4ms 기간이 지난 감쇠 비율(decay factor)을 계산해 보면 ‘0.5^(1/32)^4 = 0.917004… ‘와 같이 산출된다.  결국 ‘512 * 0.91700404 = 469’라는 로드 값으로 줄어든다. 리눅스는 소수 표현을 사용하지 않으므로 빠른 연산을 하기 위해 ms 단위의 기간별로 미리 산출해둔 감쇠 비율을 32bit shift 값을 사용한 정수로 mult화 시켜 미리 테이블로 만들어 두고 활용한다. (0.91700404 << 32 = 0xeac0c6e6)

기존 로드 평균 값에 대해 ms 단위의 지나간 기간 만큼 감소(decay)한다.

  • 예) val=0x64, 기간 n=0~63(ms)일 때 산출되는 값들의 변화
    • 산출 식: ((val >> (n / 32)) * 테이블[n % 32]) >> 32
    • 1 = (0x64 * 0xfa83b2da) >> 32 = 0x61
    • 2 = (0x64 * 0xf5257d14) >> 32 = 0x5f
    • 31 = (0x64 * 0x82cd8698) >> 32 = 0x33
    • 32 = (0x32 * 0xffffffff) >> 32 = 0x31
    • 33 = (0x32 * 0xfa83b2da) >> 32 = 0x30
    • 34 = (0x32 * 0xf5257d14) >> 32 = 0x2f
    • 63 = (0x32 * 0x82cd8698) >> 32 = 0x19

 

decay_load()

kernel/sched/fair.c

/*
 * Approximate:
 *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
 */
static __always_inline u64 decay_load(u64 val, u64 n)
{
        unsigned int local_n;

        if (!n)
                return val;
        else if (unlikely(n > LOAD_AVG_PERIOD * 63))
                return 0;

        /* after bounds checking we can collapse to 32-bit */
        local_n = n;

        /*
         * As y^PERIOD = 1/2, we can combine
         *    y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
         * With a look-up table which covers y^n (n<PERIOD)
         *
         * To achieve constant time decay_load.
         */
        if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
                val >>= local_n / LOAD_AVG_PERIOD;
                local_n %= LOAD_AVG_PERIOD;
        }

        val *= runnable_avg_yN_inv[local_n];
        /* We don't use SRR here since we always want to round down. */
        return val >> 32;
}

로드 값 val을 n 기간(ms) 에 해당하는 감소 비율로 줄인다. n=0인 경우  1.0 요율이고, n=32인 경우 0.5 요율이다.

  • 코드 라인 9~10에서 n이 0인 경우 val 값을 그대로 사용하는 것으로 반환한다. (요율 1.0)
  • 코드 라인 11~12에서 n이 1356(32 * 63)을 초과하는 경우 너무 오래된 기간이므로 0을 반환한다.
  • 코드 라인 24~27에서 n이 32 이상인 경우 val 값을 n/32 만큼 시프트 하고 n 값은 32로 나눈 나머지를 사용한다.
  • 코드 라인 29~31에서 미리 계산해둔 테이블에서 n 인덱스에 해당하는 값을 val에 곱하고 32비트 우측 시프트하여 반환한다.

 

미리 만들어진 PELT용 decay factor

kernel/sched/fair.c

/*
 * We choose a half-life close to 1 scheduling period.
 * Note: The tables below are dependent on this value.
 */
#define LOAD_AVG_PERIOD 32
#define LOAD_AVG_MAX 47742 /* maximum possible load avg */
#define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_MAX_AVG */

/* Precomputed fixed inverse multiplies for multiplication by y^n */
static const u32 runnable_avg_yN_inv[] = {
        0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,
        0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
        0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,
        0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9,
        0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80,
        0x85aac367, 0x82cd8698,
};

32ms까지 decay될 요율(factor)이 미리 계산되어 있는 runnable_avg_yN_inv[] 테이블은 나눗셈 연산을 하지 않게 하기 위해 decay 요율마다 mult 값이 다음 수식으로 만들어졌다.

  • n 번째 요율을 계산하는 수식(32bit shift 적용):
    • ‘y^n’은 실수 요율이고 커널에서 사용하기 위해 32비트 shift를 적용하여 정수로 바꾼다.
      • ‘y^k * 2^32’ 수식을 사용한다.  (단 y^32=0.5)
    • y값을 먼저 구해보면
      • y=0.5^(1/32)=0.97852062…
    • 인덱스 값 n에 0부터 32까지 사용한 결과 값은? (테이블 구성은 0~31 까지)
      • 인덱스 n에 0을 주면 y^0 * 2^32 = 0.5^(1/32)^0 * (2^32) = 1.0 << 32 = 0x1_0000_0000 (32bit로 구성된 테이블 값은 0xffff_ffff 사용)
      • 인덱스 n에 1 을 주면 y^1 * 2^32 = 0.5^(1/32)^1 * (2^32) = 0.97852062 << 32 = 0xfa83_b2db
      • 인덱스 n에 2을 주면 y^2 * 2^32 = 0.5^(1/32)^2 * (2^32) = 0.957603281 << 32 = 0xf525_7d15
      • 인덱스 n에 31을 주면 y^2 * 2^32 = 0.5^(1/32)^31 * (2^32) = 0.510948574 << 32 = 0x82cd_8698
      • 인덱스 n에 32을 주면 y^2 * 2^32 = 0.5^(1/32)^31 * (2^32) = 0.5 << 32 = 0x7fff_ffff

 

새(new) 기간에 대한 기여 감소 합계(decay sum)

기존 값이 ms 단위의 지나간 기간 만큼 감쇠 비율(decay factor)을 사용하여 산출한 것에 반해 새 로드 값은 1 ms 단위의 각각의 지나간 기간에 대해 적용한 감쇠 비율을 곱한 값을 모두 더해 산출한다. 예를 들어 3ms의 기간이 흐른 로드 값은 ‘1024*y^3 + 1024*y^2 + 1024*y’ = ‘959 + 980 + 1002 = 2941’이다. (y 값은 ‘0.5^(1/32) = 0.97857206…;) 즉 1ms에 해당하는 1024us의 값이 3ms가 지나면 959us로 작아졌음을 알 수 있다. 리눅스는 빠른 산출을 위해 각 기간 별로 산출된 감쇠 비율에 대한 총합(deacy sum)을 테이블로 만들어 사용한다.

__compute_runnable_contrib()

kernel/sched/fair.c

/*
 * For updates fully spanning n periods, the contribution to runnable
 * average will be: \Sum 1024*y^n
 *
 * We can compute this reasonably efficiently by combining:
 *   y^PERIOD = 1/2 with precomputed \Sum 1024*y^n {for  n <PERIOD}
 */
static u32 __compute_runnable_contrib(u64 n)
{
        u32 contrib = 0;

        if (likely(n <= LOAD_AVG_PERIOD))
                return runnable_avg_yN_sum[n];
        else if (unlikely(n >= LOAD_AVG_MAX_N))
                return LOAD_AVG_MAX;

        /* Compute \Sum k^n combining precomputed values for k^i, \Sum k^j */
        do {
                contrib /= 2; /* y^LOAD_AVG_PERIOD = 1/2 */
                contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD];

                n -= LOAD_AVG_PERIOD;
        } while (n > LOAD_AVG_PERIOD);

        contrib = decay_load(contrib, n);
        return contrib + runnable_avg_yN_sum[n];
}

인수로 받은 1ms 단위 기간의 수 n 만큼 러너블 평균에 기여할 누적값을 산출하여 반환한다.

  • y^32=0.5일 때, 1024 * sum(y^n)에 대한 결과 값을 산출하되 미리 계산된 테이블을 이용한다.
  • 스케쥴링 기간 n은 ms 단위이며 결과는 us단위로 반환된다.
  • 343ms 이상은 최대 47742us 값을 반환한다.

 

  • 코드 라인 12~13에서 n이 32 이하인 경우 미리 계산된 테이블을 사용하여 곧바로 결과 값을 반환한다.
    • 예) n=2 -> 1982
  • 코드 라인 14~15에서 n이 LOAD_AVG_MAX_N(345) 이상인 경우 최대치인 47742를 반환한다.
  • 코드 라인 18~20에서 루프를 돌 때마다 contrib를 절반으로 감소시키며 contrib에 최대치인 테이블 최대치인 23371을 더한다.
  • 코드 라인 22~23에서 LOAD_AVG_PERIOD(32) 만큼씩 n을 줄이며 32를 초과하는 경우 계속 루프를 돈다.
  • 코드 라인 25~26에서 마지막으로 contrib를 가지고 n 만큼 decay한 후 n 번째 테이블 값을 더해 반환한다.

 

다음과 같이 다양한 조건에서 결과값을 알아본다.

  • n=0
    • =runnable_avg_yN_sum[0] =0
  • n=1
    • =runnable_avg_yN_sum[1] =1002
  • n=2
    • =runnable_avg_yN_sum[2] =1982
  • n=10
    • =runnable_avg_yN_sum[10] =9103
  • n=32
    • =runnable_avg_yN_sum[32] =23371
  • n=33
    • =decay_load(23371, 1) + runnable_avg_yN_sum[1] = 22870 + 1002 = 23872
  • n=100
    • = decay_load(23371 + 23371/2 + 23371/4, 4) + runnable_avg_yN_sum[4] = decay_load(40898, 4) +  3880 = 37503 + 3880 = 41383
  • n=343
    • =decay_load(23371 + 23371/2, 23371/4, 23371/8 + 23371/16 + 23371/32, + 23371/64 + 23371/128 + 23371/256 + 23371/512, 23) + runnable_avg_yN_sum[23] = decay_load(23371 + 11685 + 5842 + 2921 + 1460 + 730 + 365 + 182 + 91 + 45, 4) + 3880 = decay_load(46692, 23) + 18340 = 28371 + 18340 = 46711
  • n >= 344
    • =47742 (max)

 

미리 만들어진 PELT용 decay factor sum

kernel/sched/fair.c

/*
 * Precomputed \Sum y^k { 1<=k<=n }.  These are floor(true_value) to prevent
 * over-estimates when re-combining.
 */
static const u32 runnable_avg_yN_sum[] = {
            0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
         9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
        17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
};

runnable_avg_yN_sum[] 테이블은 다음 수식으로 만들어졌다.

  • ‘sum(y^k) { 1<=k<=n } y^32=0.5’은 실수 요율이고 커널에서 사용하기 위해 정수로 바꾸기 위해 산출된 값에 12bit shift를 적용한다.
    • 1024 * Sum(y^k) { 1<=k<=n }  y^32=0.5
  • y값을 먼저 구해보면
    • y=0.5^(1/32)=0.97852062…
  • 인덱스 값 n에 1부터 31까지 사용한 결과 값은?
    • sum(1024 * y^1) { 1<=k<=1 } = 1024 * (y^1) = 1002
    • sum(1024 * y^2) { 1<=k<=2 } =1024 * (y^1 + y^2) = 1002 + 980 = 1,982
    • sum(1024 * y^3) { 1<=k<=3 } =1024 * (y^1 + y^2 + y^3) = 1,002 + 980 + 959=2,941
    • sum(1024 * y^32)=1024 * (y^1 + y^2 + y^3 + … + y^32) = 1,002 + 980 + 959 + … + 512=2,941

 

스케줄링 엔티티 로드 평균 기여 갱신

스케줄링 엔티티의 러너블 로드 평균 값과 러너블 로드 기간의 decay 산출이 완료된 후 아래 함수가 호출된다. 여기에서는 엔티티가 태스크용인지 태스크 그룹용인지에 따라 처리하는 방법이 나뉜다.

  • 태스크용 스케줄 엔티티의 경우 se->avg.load_avg_contrib 값을 산출할 때 로드 weight과 러너블 기간 비율을 곱하여 산출한다.
    • = weight * 러너블 기간 비율(러너블 평균 합 / 러너블 기간 합)
    • = se->load.weight * se->avg.runnable_avg_sum / (se->avg.runnable_avg_period+1)
  • 태스크 그룹용 스케줄 엔티티의 경우 태스크 그룹에 기여하는 정도를 알아보기 위해 nice-0의 weight를 사용하여 러너블 기간 비율을 곱하여 산출한다.
    • = nice-0용 weight * 러너블 기간 비율(러너블 평균 합 / 러너블 기간 합)
    • = 1024 * se->avg.runnable_avg_sum / (se->avg.runnable_avg_period+1)

__update_entity_load_avg_contrib()

kernel/sched/fair.c

/* Compute the current contribution to load_avg by se, return any delta */
static long __update_entity_load_avg_contrib(struct sched_entity *se)
{
        long old_contrib = se->avg.load_avg_contrib;

        if (entity_is_task(se)) {
                __update_task_entity_contrib(se);
        } else {
                __update_tg_runnable_avg(&se->avg, group_cfs_rq(se));
                __update_group_entity_contrib(se);
        }

        return se->avg.load_avg_contrib - old_contrib;
}

스케줄링 엔티티의 로드 평균 기여값을 갱신하고 그 변화값을 반환한다.

  • 코드 라인 4에서 스케줄링 엔티티의 로드 평균 기여 값을 old_contrib에 보관해둔다.
  • 코드 라인 6~7에서 태스크용 스케줄 엔티티인 경우 스케줄 엔티티의 로드 평균 기여값을 갱신한다.
  • 코드 라인 8~11에서 태스크 그룹용 스케줄 엔티티인 경우 스케줄 엔티티의 태스크 그룹용 로드 평균 기여값을 갱신한다.
  • 코드 라인 13에서 스케줄링 엔티티의 로드 평균 기여 값의 변화값을 반환한다.

 

스케줄링 엔티티 로드 평균 기여 갱신 – a) for 태스크용 se

__update_task_entity_contrib()

kernel/sched/fair.c

static inline void __update_task_entity_contrib(struct sched_entity *se)
{
        u32 contrib;

        /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
        contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
        contrib /= (se->avg.runnable_avg_period + 1);
        se->avg.load_avg_contrib = scale_load(contrib);
}

태스크용 스케줄 엔티티의 로드 평균 기여값을 다음과 같이 산출한다.

  • avg.load_avg_contrib = load.weight * avg.runnable_avg_sum / (avg.runnable_avg_period + 1)

 

다음 그림은 위의 태스크용 스케줄 엔티티의 로드 평균 기여값 산출 과정을 보여준다.

 

스케줄링 엔티티 로드 평균 기여 갱신 – b) for 태스크 그룹용 se

__update_tg_runnable_avg()

kernel/sched/fair.c

/*
 * Aggregate cfs_rq runnable averages into an equivalent task_group
 * representation for computing load contributions.
 */
static inline void __update_tg_runnable_avg(struct sched_avg *sa,
                                                  struct cfs_rq *cfs_rq)
{
        struct task_group *tg = cfs_rq->tg;
        long contrib;

        /* The fraction of a cpu used by this cfs_rq */
        contrib = div_u64((u64)sa->runnable_avg_sum << NICE_0_SHIFT,
                          sa->runnable_avg_period + 1);
        contrib -= cfs_rq->tg_runnable_contrib;

        if (abs(contrib) > cfs_rq->tg_runnable_contrib / 64) {
                atomic_add(contrib, &tg->runnable_avg);
                cfs_rq->tg_runnable_contrib += contrib;
        }
}

cfs 런큐와 태스크 그룹용 스케줄 엔티티의 러너블 평균 기여값을 산출한다. 단 변화분이 절대값이 기존 값의 1/64을 초과하는 경우에만 갱신한다. 태스크 그룹은 cpu별로 동작하는 cfs 런큐의 tg_runnable_contrib를 모두 합한 값이다. 이렇게 산출된 러너블 평균은 이어진 다음 함수에서 사용된다.

  • cont = sa->runnable_avg_sum * 1024 / (sa->runnable_avg_period + 1) – cfs_rq->tg_runnable_contrib
  • tg->runnable_avg = cont
  • cfs_rq->tg_runnable_contrib += cont

 

 

__update_group_entity_contrib()

kernel/sched/fair.c

static inline void __update_group_entity_contrib(struct sched_entity *se)
{
        struct cfs_rq *cfs_rq = group_cfs_rq(se);
        struct task_group *tg = cfs_rq->tg;
        int runnable_avg;

        u64 contrib;

        contrib = cfs_rq->tg_load_contrib * tg->shares;
        se->avg.load_avg_contrib = div_u64(contrib,
                                     atomic_long_read(&tg->load_avg) + 1);

        /*
         * For group entities we need to compute a correction term in the case
         * that they are consuming <1 cpu so that we would contribute the same
         * load as a task of equal weight.
         *
         * Explicitly co-ordinating this measurement would be expensive, but
         * fortunately the sum of each cpus contribution forms a usable
         * lower-bound on the true value.
         *
         * Consider the aggregate of 2 contributions.  Either they are disjoint
         * (and the sum represents true value) or they are disjoint and we are
         * understating by the aggregate of their overlap.
         *
         * Extending this to N cpus, for a given overlap, the maximum amount we
         * understand is then n_i(n_i+1)/2 * w_i where n_i is the number of
         * cpus that overlap for this interval and w_i is the interval width.
         *
         * On a small machine; the first term is well-bounded which bounds the
         * total error since w_i is a subset of the period.  Whereas on a
         * larger machine, while this first term can be larger, if w_i is the
         * of consequential size guaranteed to see n_i*w_i quickly converge to
         * our upper bound of 1-cpu.
         */
        runnable_avg = atomic_read(&tg->runnable_avg);
        if (runnable_avg < NICE_0_LOAD) {
                se->avg.load_avg_contrib *= runnable_avg;
                se->avg.load_avg_contrib >>= NICE_0_SHIFT;
        }
}

태스크 그룹용 스케줄 엔티티의 로드 평균 기여값을 갱신한다.

  • 코드 라인 9~11에서 태스크 그룹용 로드 기여값과 shares를 곱하고 태스크 그룹용 로드 평균+1로 나눈 값을 se->avg.load_avg_contrib에 대입한다.
  • 코드 라인 36~40에서 태스크 그룹의 러너블 평균이 nice-0 weight 값인 1024보다 작은 경우에 한해 이 값을 nice-0 weight에 대한 비율로 바꾼 후 위에서 산출한 값을 곱하여 갱신한다.
    • se->avg.load_avg_contrib *= runnable_avg / 1024

 

다음 그림은 태스크 그룹용 스케줄 엔티티의 로드 평균 기여값을 산출하는 수식이다.

 

스케줄링 엔티티 블럭드 로드 갱신

update_cfs_rq_blocked_load()

kernel/sched/fair.c

/*
 * Decay the load contributed by all blocked children and account this so that
 * their contribution may appropriately discounted when they wake up.
 */
static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, int force_update)
{                                             
        u64 now = cfs_rq_clock_task(cfs_rq) >> 20;
        u64 decays;

        decays = now - cfs_rq->last_decay;
        if (!decays && !force_update)
                return;

        if (atomic_long_read(&cfs_rq->removed_load)) {
                unsigned long removed_load;
                removed_load = atomic_long_xchg(&cfs_rq->removed_load, 0);
                subtract_blocked_load_contrib(cfs_rq, removed_load);
        }

        if (decays) {
                cfs_rq->blocked_load_avg = decay_load(cfs_rq->blocked_load_avg,
                                                      decays);
                atomic64_add(decays, &cfs_rq->decay_counter);
                cfs_rq->last_decay = now;
        }

        __update_cfs_rq_tg_load_contrib(cfs_rq, force_update);
}

blocked 로드 평균을 업데이트한다. blocked_load_avg에서 removed_load 만큼을 감소시킨 값을 ms 단위로 decay할 기간만큼 decay 한다.

  • 코드 라인 7에서 현재 클럭 태스크의 시각을 ms 단위로 변환하여 now에 대입한다.
  • 코드 라인 10~12에서 now와 최종 decay 시각과의 차이를 decays에 대입한다. 만일 decays가 0이고 force_update 요청이 없는 경우 함수를 빠져나간다.
  • 코드 라인 14~18에서 removed_load가 있는 경우 0으로 대입하고 기존 값을 blocked 로드 평균에서 감소시킨다.
  • 코드 라인 20~25에서 decays 기간이 있는 경우 blocked_load_avg 값을 decays 만큼 decay 시킨 후 decay_counter에 decays를 추가하고 현재 갱신 시각 now를 last_decay에 저장한다.
  • 코드 라인 27에서 태스크 그룹용 로드 평균 기여를 갱신한다.

 

다음 그림은 blocked_load_avg – removed_load 값을 10ms decay 하는 모습을 보여준다.

 

subtract_blocked_load_contrib()

kernel/sched/fair.c

static inline void subtract_blocked_load_contrib(struct cfs_rq *cfs_rq,
                                                 long load_contrib)
{
        if (likely(load_contrib < cfs_rq->blocked_load_avg))
                cfs_rq->blocked_load_avg -= load_contrib;
        else
                cfs_rq->blocked_load_avg = 0;
}

blocked 로드 평균에서 요청한 로드 기여값을 감소시킨다. 만일 0보다 작아지는 경우 0을 대입한다.

 

__update_cfs_rq_tg_load_contrib()

kernel/sched/fair.c

static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
                                                 int force_update)
{
        struct task_group *tg = cfs_rq->tg;
        long tg_contrib;

        tg_contrib = cfs_rq->runnable_load_avg + cfs_rq->blocked_load_avg;
        tg_contrib -= cfs_rq->tg_load_contrib;

        if (!tg_contrib)
                return;

        if (force_update || abs(tg_contrib) > cfs_rq->tg_load_contrib / 8) {
                atomic_long_add(tg_contrib, &tg->load_avg);
                cfs_rq->tg_load_contrib += tg_contrib;
        }
}

태스크 그룹용 로드 평균 기여를 갱신한다.

  • tmp = cfs_rq->runnable_load_avg + cfs_rq->blocked_load_avg – cfs_rq->tg_load_contrib
    • cfs_rq->tg_load_contrib = tmp
    • tg->load_avg = tmp

 

다음 그림은 태스크 그룹용 스케줄 엔티티의 로드 평균과 로드 기여값을 갱신하는 모습을 보여준다.

 

CFS Shares 갱신으로 인한 로드 weight 재반영

kernel/sched/fair.c

update_cfs_shares()

static void update_cfs_shares(struct cfs_rq *cfs_rq)
{
        struct task_group *tg;
        struct sched_entity *se;
        long shares;

        tg = cfs_rq->tg;
        se = tg->se[cpu_of(rq_of(cfs_rq))];
        if (!se || throttled_hierarchy(cfs_rq))
                return;
#ifndef CONFIG_SMP
        if (likely(se->load.weight == tg->shares))
                return;
#endif
        shares = calc_cfs_shares(cfs_rq, tg);

        reweight_entity(cfs_rq_of(se), se, shares);
}

태스크 그룹의 shares 값에 대한 cfs 런큐의 로드 비율을 적용하여 스케줄 엔티티, cfs 런큐 및 런큐등의 로드 weight을 갱신한다.

  • 코드 라인 7~8에서 cfs 런큐로 태스크 그룹 및 스케줄 엔티티를 알아온다.
  • 코드 라인 9~10에서 스케줄 엔티티가 없거나 cfs 런큐가 스로틀된 경우 함수를 빠져나간다.
  • 코드 라인 11~14에서 UP 시스템에서 태스크 그룹의 shares 값과 스케줄 엔티티의 로드 값이 동일하면 최대치를 사용하는 중이므로 함수를 빠져나간다.
  • 코드 라인 15에서 태스크 그룹의 cfs shares 값에 cfs 런큐 로드 비율이 반영된 로드 weight 값을 산출한다
  • 코드 라인 17에서 산출된 shares 값으로 스케줄 엔티티의 로드 weight 값을 재계산한다.

 

calc_cfs_shares()

kernel/sched/fair.c

static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
{
        long tg_weight, load, shares;

        tg_weight = calc_tg_weight(tg, cfs_rq);
        load = cfs_rq->load.weight;

        shares = (tg->shares * load);
        if (tg_weight)
                shares /= tg_weight; 

        if (shares < MIN_SHARES)
                shares = MIN_SHARES;
        if (shares > tg->shares) 
                shares = tg->shares;

        return shares;
}

태스크 그룹의 cfs shares 값에 대한 cfs 런큐  로드 비율이 반영된 로드 weight 값을 산출한다. (태스크 그룹의 shares * cfs 런큐 로드 weight / 태스크 그룹 weight)

  • 코드 라인 5에서 태스크 그룹의 weight 값을 tg_weight에 대입한다.
  • 코드 라인 6에서 cfs 런큐의 로드 weight 값을 load에 대입한다.
  • 코드 라인 8~10에서 태스크 그룹의 shares 값과 load를 곱한 후 태스크 그룹의 weight 값으로 나눈다.
    • tg->shares * cfs_rq->load.weight / tg_weight
  • 코드 라인 12~17에서 산출된 share 값이 최소 shares(2)보다 작지 않도록 제한하고 태스크 그룹의 shares 값보다 크지 않도록 제한하고 반환한다.
    • 2 <= 계산된 shaers <= tg->shares

 

다음 그림은 태스크 그룹의 shares 값에 대하여 태스크 그룹 대비 cfs 런큐의 로드기여 비율을 반영하여 산출한다.

  • UP 시스템에서는 태스크 그룹 대비 cfs 런큐의 로드 weight 비율을 반영하지 않는다. 따라서 태스크 그룹의 shares 값을 100% 반영한다.

 

calc_tg_weight()

kernel/sched/fair.c

static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq)
{
        long tg_weight;

        /*
         * Use this CPU's actual weight instead of the last load_contribution
         * to gain a more accurate current total weight. See
         * update_cfs_rq_load_contribution().
         */
        tg_weight = atomic_long_read(&tg->load_avg);
        tg_weight -= cfs_rq->tg_load_contrib;
        tg_weight += cfs_rq->load.weight;

        return tg_weight;
}

태스크 그룹의 로드 평균 값을 읽어와서 cfs 런큐의 태스크 그룹 로드 기여 값을 감소시키고 다시 cfs 런큐의 로드 weight 값을 더한 후 반환한다.

  • tg->load_avg – cfs_rq->tg_load_contrib + cfs_rq->load.weight

 

로드 weight 재설정

reweight_entity()

kernel/sched/fair.c

static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
                            unsigned long weight)
{
        if (se->on_rq) {
                /* commit outstanding execution time */
                if (cfs_rq->curr == se)
                        update_curr(cfs_rq);
                account_entity_dequeue(cfs_rq, se);
        }

        update_load_set(&se->load, weight);

        if (se->on_rq)
                account_entity_enqueue(cfs_rq, se);
}

스케줄 엔티티의 로드 weight 값을 변경 시킨다. 스케줄 엔티티가 cfs 런큐에서 이미 동작중인 경우 cfs 런큐와 런큐의 로드 값을 다음 예와 같이 조정한다.

  • 예) se->load.weight 값이 5000 -> 6024로 변경되는 경우
    • cfs_rq->load -= 5000   -> cfs_rq->load += 6024
    • rq->load -= 5000 -> rq->load += 6024 (최상위 스케줄 엔티티인 경우)

 

  • 코드 라인 4~7에서 요청한 스케줄 엔티티가 런큐에 있고 cfs 런큐에서 지금 돌고 있는 중이면 현재 태스크의 런타임 통계를 갱신한다.
  • 코드 라인 8에서 스케줄 엔티티의 로드 weight 값을 cfs 런큐에서 감소시킨다. 또한 최상위 스케줄 엔티티인 경우 런큐의 로드 weight 값을 동일하게 감소시킨다.
  • 코드 라인 11에서 스케줄 엔티티의 로드 weight 값을 갱신한다.
  • 코드 라인 13~14에서 요청한 스케줄 엔티티가 런큐에 있는 경우 스케줄 엔티티의 로드 weight 값을 cfs 런큐에 추가한다. 또한 최상위 스케줄 엔티티인 경우 런큐의 로드 weight 값에 동일하게 추가한다.

 

로드 weight이 재산출되야 하는 상황들을 알아본다.

  • 태스크 그룹의 shares 값을 변경 시 sched_group_set_shares() -> 변경할 그룹부터 최상위 그룹까지 반복: update_cfs_shares() -> reweight_entity()에서 사용된다.
  • 요청 스케줄 엔티티가 엔큐될 때 enqueue_entity() -> update_cfs_shares() -> reweight_entity()
  • 요청 스케줄 엔티티가 디큐될 때 enqueue_entity() -> update_cfs_shares() -> reweight_entity()

 

다음 그림은 스케줄 엔티티의 로드 weight 값이 변경될 때 관련된 cfs 런큐 및 런큐값도 재산출되는 과정을 보여준다.

 

update_load_set()

kernel/sched/fair.c

static inline void update_load_set(struct load_weight *lw, unsigned long w)
{
        lw->weight = w;
        lw->inv_weight = 0;
}

로드 weight 걊을 설정하고 inv_weight 값은 0으로 리셋한다.

 

Account Entity Enqueue & Dequeue

account_entity_enqueue()

kernel/sched/fair.c

static void
account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        update_load_add(&cfs_rq->load, se->load.weight);
        if (!parent_entity(se))
                update_load_add(&rq_of(cfs_rq)->load, se->load.weight);
#ifdef CONFIG_SMP
        if (entity_is_task(se)) {
                struct rq *rq = rq_of(cfs_rq);

                account_numa_enqueue(rq, task_of(se));
                list_add(&se->group_node, &rq->cfs_tasks);
        }
#endif
        cfs_rq->nr_running++;
}

cfs 런큐에 스케줄 엔티티의 로드를 추가한다. 부모 스케줄 엔티티가 없으면 cfs 런큐가 속한 런큐의 로드에도 추가한다.

  • 코드 라인 4에서 cfs 런큐에 스케줄 엔티티의 로드를 추가한다.
  • 코드 라인 5~6에서 부모 스케줄 엔티티가 없으면 cfs 런큐가 속한 런큐의 로드에도 추가한다.
  • 코드 라인 8~13에서 smp 시스템에서 태스크용 스케줄 엔티티인 경우 NUMA 시스템을 위해 런큐의 nr_numa_running 및 nr_preferred_running을 갱신한다. 그런 후 런큐의 cfs_tasks 리스트에 se->group_node를 추가한다.
  • 코드 라인 15에서 런큐의 nr_running 카운터를 1 증가시킨다.

스케줄 엔티티가 cfs 런큐에 엔큐되는 경우 관련 값들을 추가한다.

  • 코드 라인 4에서 스케줄 엔티티의 로드 weight 값을 cfs 런큐에 추가한다.
  • 코드 라인 5~6에서 최상위 스케줄 엔티티인 경우 런큐에도 추가한다.
  • 코드 라인 7~14에서 태스크 타입 스케줄 엔티티인 경우 누마 관련 값도 증가시키고 스케줄 엔티티를 런큐의 cfs_tasks 리스트에 추가한다.
  • 코드 라인 15에서 cfs 런큐의 nr_running을 1 증가시킨다.

 

account_numa_enqueue()

kernel/sched/fair.c

static void account_numa_enqueue(struct rq *rq, struct task_struct *p)
{
        rq->nr_numa_running += (p->numa_preferred_nid != -1);
        rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
}

태스크가 엔큐되고 선호하는 누마 노드로 추가된 경우 다음의 값을 1씩 증가시킨다.

  • rq->nr_numa_running++ (태스크의 권장 누마 노드가 지정된 경우에만)
  • rq->nr_preferred_running++ (태스크의 노드가 권장 누마 노드와 동일한 경우에만)

 

다음 그림은 스케줄 엔티티의 로드 weight 값을 런큐 및 cfs 런큐에 증감시키는 상황을 보여준다.

  • 태스크형 스케줄 엔티티의 경우 cfs_tasks 리스트에 추가/삭제되는 것도 알 수 있다.
  • 런큐의 load.weight 증감은 최상위 엔티티의 load.weight에 대해서만 해당한다.

 

account_entity_dequeue()

kernel/sched/fair.c

static void
account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        update_load_sub(&cfs_rq->load, se->load.weight);
        if (!parent_entity(se))
                update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);
        if (entity_is_task(se)) {
                account_numa_dequeue(rq_of(cfs_rq), task_of(se));
                list_del_init(&se->group_node);
        }
        cfs_rq->nr_running--;
}

스케줄 엔티티가 cfs 런큐에서 디큐되는 경우 관련 값들을 감소시킨다.

  • 코드 라인 4에서 스케줄 엔티티의 로드 weight 값을 cfs 런큐에서 감소시킨다.
  • 코드 라인 5~6에서 최상위 스케줄 엔티티인 경우 런큐에서도 감소시킨다.
  • 코드 라인 7~10에서 태스크 타입 스케줄 엔티티인 경우 누마 관련 값을 감소시키고, 런큐의 cfs_tasks 리스트에서 스케줄 엔티티를 제거하고 초기화한다.
  • 코드 라인 11에서 cfs 런큐의 nr_running을 1 감소시킨다.

 

account_numa_dequeue()

kernel/sched/fair.c

static void account_numa_dequeue(struct rq *rq, struct task_struct *p)
{
        rq->nr_numa_running -= (p->numa_preferred_nid != -1);
        rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
}

태스크가 디큐되고 선호하는 누마 노드로 추가된 경우 다음의 값을 1씩 감소시킨다.

  • rq->nr_numa_running– (태스크의 권장 누마 노드가 지정된 경우에만)
  • rq->nr_preferred_running– (태스크의 노드가 권장 누마 노드와 동일한 경우에만)

 

엔큐 & 디큐 시 엔티티 로드 평균 산출

enqueue_entity_load_avg()

kernel/sched/fair.c

/* Add the load generated by se into cfs_rq's child load-average */
static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
                                                  struct sched_entity *se,
                                                  int wakeup)
{
        /*
         * We track migrations using entity decay_count <= 0, on a wake-up
         * migration we use a negative decay count to track the remote decays
         * accumulated while sleeping.
         *
         * Newly forked tasks are enqueued with se->avg.decay_count == 0, they
         * are seen by enqueue_entity_load_avg() as a migration with an already
         * constructed load_avg_contrib.
         */
        if (unlikely(se->avg.decay_count <= 0)) {
                se->avg.last_runnable_update = rq_clock_task(rq_of(cfs_rq));
                if (se->avg.decay_count) {
                        /*
                         * In a wake-up migration we have to approximate the
                         * time sleeping.  This is because we can't synchronize
                         * clock_task between the two cpus, and it is not
                         * guaranteed to be read-safe.  Instead, we can
                         * approximate this using our carried decays, which are
                         * explicitly atomically readable.
                         */
                        se->avg.last_runnable_update -= (-se->avg.decay_count)
                                                        << 20;
                        update_entity_load_avg(se, 0);
                        /* Indicate that we're now synchronized and on-rq */
                        se->avg.decay_count = 0;
                }
                wakeup = 0;
        } else {
                __synchronize_entity_decay(se);
        }

        /* migrated tasks did not contribute to our blocked load */
        if (wakeup) {
                subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
                update_entity_load_avg(se, 0);
        }

        cfs_rq->runnable_load_avg += se->avg.load_avg_contrib;
        /* we force update consideration on load-balancer moves */
        update_cfs_rq_blocked_load(cfs_rq, !wakeup);
}

스케줄 엔티티가 엔큐될 때 로드 평균을 갱신한다.

  • 코드 라인 15~16에서 낮은 확률로 스케줄 엔티티의 decay_count가 0이하인 경우 스케줄 엔티티의 avg.last_runnable_update를 현재 시각(clock_task)으로 갱신한다.
  • 코드 라인 17~31에서 decay_count가 음수인 경우 스케줄 엔티티의 avg.last_runnable_update(ns)를 decay_count(ms) 만큼 이전으로 감소시킨다. 그리고 update_entity_load_avg()를 호출하여 로드 평균을 갱신하고 decay_count는 0으로 초기화한다.
  • 코드 라인 33~35에서 스케줄 엔티티의 decay_count가 0을 초과한 경우 스케줄 엔티티의 로드 평균 기여를 ‘cfs 런큐의 decay_counter – 스케줄 엔티티의 avg.decay_count’ 만큼 decay 한다.
  • 코드 라인 38~41에서 decay_count가 0을 초과하였었고 인수 wakeup=1이 주어진 경우 블럭드로드 기여를 감소시키고 다시 update_entity_load_avg()를 호출하여 로드 평균을 갱신한다.
  • 코드 라인 43에서 스케줄 엔티티에 있는 로드 평균 기여를 cfs 런큐의 러너블 로드 평균에  추가한다.
  • 코드 라인 45에서 블럭드 로드를 갱신하고 러너블 평균과 더해 cfs 런큐의 tg_load_contrib와 태스크 그룹의 load_avg 에 추가한다.

 

 

구조체

sched_avg 구조체

include/linux/sched.h

struct sched_avg {
        /*
         * These sums represent an infinite geometric series and so are bound
         * above by 1024/(1-y).  Thus we only need a u32 to store them for all
         * choices of y < 1-2^(-32)*1024.
         */
        u32 runnable_avg_sum, runnable_avg_period;
        u64 last_runnable_update;
        s64 decay_count;
        unsigned long load_avg_contrib;
};
  • runnable_avg_sum
    • 러너블 로드라 불리며 러너블(curr + rb 트리에서 대기) 타임 평균을 합하였다.
  • runnable_avg_period
    • Idle 타임을 포함한 전체 시간 평균을 합하였다.
  • last_runnable_update
    • 러너블 로드를 갱신한 마지막 시각
  • decay_count
    • 트래킹 migration에 사용하는 엔티티 decay 카운터로 슬립되어 엔티티가 cfs 런큐를 벗어난 시간을 decay하기 위해 사용된다.
  • load_avg_contrib
    • 평균 로드 기여(weight * runnable_avg_sum / (runnable_avg_period+1))
    • 태스크용 스케줄 엔티티에서는 엔티티의 load.weight이 러너블 평균 비율로 곱하여 산출된다.
    • 태스크 그룹용 스케줄 엔티티에서는 shares 값이 tg에 대한 cfs 비율 및 로드 비율 등이 적용되어 산출된다.

 

task_group 구조체

kernel/sched/sched.h

/* task group related information */
struct task_group {
        struct cgroup_subsys_state css;

#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;
        unsigned long shares;

#ifdef  CONFIG_SMP
        atomic_long_t load_avg;
        atomic_t runnable_avg;
#endif
#endif

#ifdef CONFIG_RT_GROUP_SCHED
        struct sched_rt_entity **rt_se;
        struct rt_rq **rt_rq;

        struct rt_bandwidth rt_bandwidth;
#endif

        struct rcu_head rcu;
        struct list_head list;

        struct task_group *parent;
        struct list_head siblings;
        struct list_head children;

#ifdef CONFIG_SCHED_AUTOGROUP
        struct autogroup *autogroup;
#endif

        struct cfs_bandwidth cfs_bandwidth;
};
  • css
    • cgroup 서브시스템 상태
    • rcu
    • list
    • *parent
      • 부모 태스크 그룹
    • siblings
      • 현재 태스크들
    • children
      • 자식 태스크 그룹
    • cfs_bandwidth
  • cfs 그룹 스케줄링 관련
    • **se
      • 각 cpu에서 이 그룹에 연결된 스케줄 엔티티(cpu 수 만큼)
    • **cfs_rq
      • 각 cpu에서 이 그룹에 연결된 cfs 런큐
    • shares
      • 그룹에 적용할 로드 weight 비율
    • load_avg
      • cfs 런큐의 로드 평균을 모두 합한 값으로 결국 스케줄 엔티티의 로드 평균 기여값을 모두 합한 값이다.
    • runnable_avg
      • cfs 런큐의 러너블 평균을 모두 합한 값으로 결국 스케줄 엔티티의 러너블 평균을 모두 합한 값이다.
  • rt 그룹 스케줄링 관련
    • **rt_se
      • 각 cpu에서 이 그룹에 연결된 rt 스케줄 엔티티(cpu 수 만큼)
    • **rt_rq
      • 각 cpu에서 이 그룹에 연결된 rt 런큐
    • rt_bandwidth
  • autogroup 관련
    • *autogroup

 

참고