7-2. Task Scheduling in Linux (2)

중앙대학교 3-2 리눅스 응용 설계 (손용석 교수님) 과목 정리입니다.

Importance of Fair-Share Scheduling

• fairness 보장이 제대로 이루어지지 않으면 server / cloud computing에서 문제가 발생할 수 있다. (다른 user or group에서 starvation이 일어날 수도 있음)
• Fair-share scheduling
  • process 사이에서 자원을 균등하게 분배하는 것이 아닌 user 또는 group 사이에서 자원을 균등하게 분배한다.

Completely Fair Scheduler (CFS)

• Linux kernel의 primary task scheduler
  • process를 실행하기 위한 CPU resource 할당을 처리하고, 전체 CPU 활용률을 극대화하는 동시에 interactive performance를 극대화 하는 것을 목표로 한다.
  • 범용 OS에서 널리 사용되는 fair share scheduling의 첫 번째 구현

Goal of CFS

• 각 task에게 weight에 따라 비례하는 CPU time을 제공하여 fair share scheduling 제공
• 관련된 weight가 있는 task들이 주어지면 fair share scheduler는 각각의 weight에 비례하여 자원을 할당해야 한다.

• N : system의 task 개수
• task의 집합
• W : task의 weight
  • weight가 클 수록 C가 커진다.
• S : 전체 task의 weight 합
• T : task 의 time slice
• C : 하나의 task가 받을 수 있는 CPU Time

• multicaore system에서 CPU 자원을 효율적으로 사용할 수 있다.

Task Priority

Linux priority range

• Nice value (-20 ~ 19, 기본값 0)
  • linux system의 표준 priority range
  • normal task의 priority
  • nice value가 클(작을) 수록 낮은(높은) priority
• Real-time (0 ~ 99)
  • real-time task의 priority
  • 높은 (낮은) real-time priority가 priority가 높다 (낮다).
  • Real-time task는 normal task에 비해 더 높은 priority를 갖는다.

Scheduling Class

• Linux scheduler는 모듈식으로 만들어졌다.
• object-oriented class 계층과 유사
• 각 scheduling 정책은 기존 scheduler 코드와 독립적으로 구현될 수 있다.
• ⇒ scheduling class

Each task belongs to one specific scheduling class

• rt_sched_class : real-time task
• fair_sched_clas : time-sharing (normal) task
• idle_sched_class : swapper (memory swap)과 init task를 위해
• 각 scheduling class는 single linked list에서 서로 연결되어, class를 반복할 수 있습니다.

Task Structure

• task_struct
  • task state, state, process flag, priority 를 나타냄
  • task_struct의 struct_sched class가 추상클래스 같이 구현이 달라질 수 있다.

Run Queue Structure

• 각 core가 각자의 run queue를 갖는다.
  • normal task를 위한 red-black tree
• cfs_rq structure
  • weight_load : load CFS run queue
  • nr_running : run queue의 task 개수

Red-Black Tree

• normal task를 관리하기 위해, CFS는 시간 정렬된 run queue structure로 red-black tree를 사용한다.
• insert / delete : 모두 O(log n) time. 빠르고 효율적임

• 맨 왼쪽 값이 다음 scheduler 값
• virtual runtime 값으로 서버를 ordering 한다.

Nice to Weight Maping

• CFS에서 task의 우선순위를 나타내기 위해 각 task는 weight value를 저장한다.

Virtual Runtime

• weight에 반비례하는 task의 누적 실행 시간

• default Weight와 actual runtime에 비례
• task의 weight에 반비례
• weight가 커지면 Virtual run time 이 줄어든다.

CFS’s virtual runtime

• CFS Scheduler는 virtual runtime이 가장 작은 다음 task를 선택한다.
  • real runtime : task가 실제로 실행된 CPU 시간
  • virtual runtime : task의 load weight를 고려한 시간
• task load weight가 클 수록 virtual runtime이 작아진다.
• task load weight가 1024인 경우 (W0) actual runtime과 virtual runtime이 동일하다.
• virtual runtime은 누적적으로 관리되므로 task의 load weight가 크면 virtual runtime이 느리게 증가한다. load weight가 작으면 virtual runtime이 상대적으로 빠르게 증가한다.

Virtual Runtime Example

• task load weight 비율이 1:2:3
• task CPU time의 비율이 1:2:3

Minimal virtual runtime

• virtual runtime은 계속해서 증가한다.
  • task에 의해 사용된 CPU time은 줄어들 수 없다.
• 새롭게 생성된 task의 virtual runtiem은 0으로 초기화된다.
  • task가 long-running task를 포함한 동일한 run queue에 삽입된 경우, 해당 task가 가장 vruntime이 작다.
  • 따라서 해당 task의 vruntime이 기존 task보다 커질 때까지 새롭게 삽입된 task를 계속 실행 → CPU를 긴 시간동안 독점하는 역차별 발생
• 해당 문제를 방지하기 위해 CFS는 run queue의 minimal virtual runtime을 관리한다.
  • task가 새롭게 생성된 경우, CFS는 task의 vruntime을 min_vruntime에 기반하여 설정한다.

Time Slice

• task가 preempt되지 않고 실행될 수 있는 Time interval
• task t의 time slice는 weight에 비례한다.
  • S : run queue의 실행 가능한 task들의 총 weight
  • L : CFS의 scheduling latency

• nr_running : 실행중인 task의 개수
• sysctl_sched_min_granularity : task를 실행하기 위한 최소 보장되는 time slice (execution time)
• sysctl_sched_latency : 한 번에 모든 task를 실행하는 시간
• sched_nr_latency : 총 task 실행 시간 / 최소 보장 execution time → 최소 보장 시간으로 실행할 경우 최대 몇 개의 task가 실행될 수 있는지

Scheduling latency

• scheduling latency는 실행되는 task의 개수에 따라 결정된다. (nr_running)

sched_nr_latency

• default scheduling latency를 사용할 수 있는 task의 개수
  • sysctl_sched_min_granularity
    • task에 대해 최소로 보장되는 time slice
    • Ex. system이 single core를 가질 때 0.75 ms
  • sysctl_sched_latency
    • 기본 scheduling latency
    • Ex. system이 single core일 때 6ms (default)

600

• Example