scheduler

CFS Bandwidth Control

jsh91 2023. 11. 22. 01:52

 이 글에서는 SCHED_NORMAL에 대한 CPU 대역폭 제어에 대해서만 설명합니다. SCHED_RT 사례는 Real-Time 그룹 스케줄링에서 다룹니다

 

CFS bandwidth control는 CONFIG_FAIR_GROUP_SCHED 확장으로 그룹 또는 계층에서 사용할 수 있는 최대 CPU 대역폭을 지정할 수 있습니다.

 

그룹에 허용되는 bandwidth은 할당량 및 기간을 사용하여 지정됩니다. 주어진 "기간"(microseconds) 내에서 작업 그룹은 CPU 시간의 최대 "할당량" microseconds까지 할당됩니다. 이 할당량은 cgroup의 스레드를 실행할 수 있게 됨에 따라 slice 로 된 per-cpu run queues에 할당됩니다. 모든 할당량이 할당되면 해당 할당량에 대한 추가 요청으로 인해 스레드가 조절됩니다. 조절된 스레드는 할당량이 보충되는 다음 기간까지 다시 실행할 수 없습니다.

 

그룹의 할당되지 않은 할당량은 전체적으로 추적되며, 각 period boundary에서 cfs_quota 단위로 다시 갱신됩니다. 스레드가 이 bandwidth을 소비하므로 수요에 따라 CPU 로컬 "silos"로 전송됩니다. 이러한 각 업데이트 내에서 전송되는 양은 조정 가능하며 "slice"로 설명됩니다.

 

Burst feature

이 기능은 다른 시스템 사용자에 대한 간섭이 증가하는 대가로 미래의 언더런에 대비해 지금 시간을 빌려줍니다. 모두 잘 묶여 있습니다.

* 언더런 : 데이터 전송이나 처리 속도가 예상보다 느려져서 발생하는 상황

 

Traditional (UP-EDF) bandwidth control is something like:

(U = Sum u_i) <= 1

이 식 "(U = Σuᵢ) ≤ 1"은 각각의 uᵢ가 양수이고, 이들의 합이 1 이하임을 나타내는 수학적인 부등식

Σuᵢ는 u₁, u₂, ..., uₙ을 합한 값

 

 

이것은 모든 deadline이 충족되고 시스템이 안정적이라는 것을 보장합니다. 결국 U가 >1이면 walltime의 매초마다 프로그램 시간의 1초 이상을 실행해야 하고 분명히 마감시간을 놓쳐야 하지만 다음 deadline 은 여전히 더 늘어날 것입니다. 무한한 실패를 따라잡을 시간이 없습니다.

* walltime: 실제 시간 경과

 

burst feature는 워크로드가 항상 전체 할당량을 실행하는 것은 아님을 관찰하며, 이를 통해 u_i를 통계적 분포로 설명할 수 있습니다.

 

예를 들어, u_i = {x,e}_i, 여기서 x는 p(95) 및 x+e p(100)입니다(전통적인 WCET). 이것은 효과적으로 u를 더 작게 하여 효율성을 향상시킬 수 있지만(시스템에서 더 많은 작업을 처리할 수 있지만), all the odds line up이 있을 때 마감 시간을 놓치는 비용이 있습니다. 그러나 x가 평균 이상인 한 모든 오버런은 언더런과 쌍을 이루어야 하기 때문에 안정성을 유지합니다

 

* WCET는 "Worst-Case Execution Time"의 약어로, 한 프로그램 또는 코드 세그먼트가 실행되는 데 소요되는 최악의 시간

 

즉, 두 작업이 모두 p(95) 값을 지정하고 p(95)*p(95) = 90.25% 확률로 두 작업이 모두 할당량 내에 있고 모든 작업이 양호하다고 가정합니다. 동시에 p(5)p(5) = 0.25% 확률로 두 작업이 동시에 할당량을 초과할 가능성이 있습니다(guaranteed deadline fail). 그 사이에 임계값이 하나가 초과하고 다른 하나는 보상할 만큼 충분히 부족하지 않은 임계값이 있습니다. 이는 특정 CDF에 따라 달라집니다.

* p(95)×p(95)=0.95×0.95=0.9025

 

동시에, 우리는 deadline가 놓친 최악의 경우는 Sume_i라고 말할 수 있습니다. 즉, (x+e가 실제로 WCET라는 가정 하에서) bounded tardiness( 제한된 지각 )가 있습니다.

 

burst를 사용할 때의 간섭은 deadline의 누락 가능성과 평균 WCET에 의해 평가됩니다. 테스트 결과에 따르면 많은 cgroups 또는 CPU가 과소 사용될 때 간섭이 제한됩니다. 자세한 내용은 다음과 같습니다: https://lore.kernel.org/lkml/5371BD36-55AE-4F71-B9D7-B86DC32E3D2B@linux.alibaba.com/

 

Management

Quota, period and burst are managed within the cpu subsystem via cgroupfs.

 

Note

The cgroupfs files described in this section are only applicable to cgroup v1. For cgroup v2, see Documentation/admin-guide/cgroup-v2.rst.

  • cpu.cfs_quota_us: run-time replenished(보충) within a period (in microseconds)
  • cpu.cfs_period_us: the length of a period (in microseconds)
  • cpu.stat: exports throttling statistics [explained further below]
  • cpu.cfs_burst_us: the maximum accumulated run-time (in microseconds)

 

The default values are:

cpu.cfs_period_us=100ms
cpu.cfs_quota_us=-1
cpu.cfs_burst_us=0

cpu.cfs_quota_us 값이 -1이면 그룹에 대역폭 제한이 없음을 의미하므로 이러한 그룹은 제한되지 않은 대역폭 그룹으로 설명됩니다. 이는 CFS에 대한 기존의 작업 보존 동작을 나타냅니다.

 

cpu.cfs_burst_us보다 작지 않은 임의의 (유효한) 양의 값(들)을 쓰면 지정된 대역폭 제한이 제정됩니다. 할당량 또는 기간에 허용되는 최소 할당량은 1ms입니다. 1s의 주기 길이에 대한 상한도 있습니다. 대역폭 제한이 계층적 방식으로 사용되는 경우 추가적인 제한이 존재하며, 이에 대해서는 아래에서 더 자세히 설명합니다.

 

cpu.cfs_quota_us에 음의 값을 기록하면 대역폭 제한이 제거되고 그룹이 다시 제한되지 않은 상태로 돌아갑니다.

 

cpu.cfs_burst_us 값이 0이면 그룹이 사용되지 않은 대역폭을 축적할 수 없음을 나타냅니다. 이는 CFS에 대한 기존의 대역폭 제어 동작을 변경하지 않습니다. cpu.cfs_quota_us보다 크지 않은 임의의 (유효한) 양의 값을 cpu.cfs_burst_us에 기록하면 사용되지 않은 대역폭에 대한 상한이 제정됩니다

 

그룹의 대역폭 사양을 업데이트하면 제한된 상태에 있는 경우 제한이 해제됩니다

 

System wide settings

효율성을 위해 런타임은 global pool와 CPU 로컬 "silos" 사이에서 일괄 전송됩니다. 이는 대형 시스템의 global accounting 압력을 크게 감소시킵니다. 이러한 업데이트가 필요할 때마다 전송되는 양을 "slice"이라고 설명합니다

 

This is tunable via procfs:

/proc/sys/kernel/sched_cfs_bandwidth_slice_us (default=5ms)

 

 

slice 값이 크면 전송 오버헤드가 감소하는 반면 값이 작으면 세분화된 소비가 가능합니다.

* 오버헤드 : 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말한다

Statistics

A group's bandwidth statistics are exported via 5 fields in cpu.stat.

cpu.stat:

  • nr_periods: Number of enforcement intervals that have elapsed.
  • nr_throttled: Number of times the group has been throttled/limited( 제한됨 )
  • throttled_time: The total time duration (in nanoseconds) for which entities of the group have been throttled.
  • nr_bursts: Number of periods burst occurs.
  • burst_time: Cumulative wall-time (in nanoseconds) that any CPUs has used above quota in respective periods.

This interface is read-only.

 

* nr_periods (Number of enforcement intervals that have elapsed):
설명: 이 값은 제한 조치가 얼마나 자주 발생했는지를 나타냅니다. 즉, 제한을 강제하는 간격이 몇 번 발생했는지를 세는 카운터입니다.


*  nr_throttled (Number of times the group has been throttled/limited):
설명: 이 값은 해당 그룹이 제한되거나 제한을 받은 횟수를 나타냅니다. 즉, 해당 그룹이 CPU 자원을 받지 못하거나 제한을 받은 횟수를 세는 카운터입니다.


*  throttled_time (The total time duration in nanoseconds for which entities of the group have been throttled):
설명: 이 값은 해당 그룹의 엔터티가 제한을 받은 총 시간을 나타냅니다. 제한을 받은 시간의 누적값으로, 해당 그룹이 CPU 자원을 받지 못한 시간을 나타내는 카운터입니다.


*  nr_bursts (Number of periods burst occurs):
설명: 이 값은 Burst가 몇 번 발생했는지를 나타냅니다. Burst는 일정 기간 동안 CPU 자원을 누적적으로 사용하는 것을 의미하며, 이 카운터는 Burst가 발생한 횟수를 나타냅니다.


*  burst_time (Cumulative wall-time in nanoseconds that any CPUs has used above quota in respective periods):
설명: 이 값은 Burst가 발생한 각 기간 동안 CPU가 할당량을 초과하여 사용한 누적 벽 시간을 나타냅니다. Burst가 발생하면 CPU가 일시적으로 제한을 초과하여 사용한 시간을 누적하는 카운터입니다

 

Hierarchical considerations

인터페이스는 개별 entity's bandwidth의 대역폭이 항상 달성 가능하도록 강제합니다(즉, max(c_i) <= C). 그러나 집계 사례의 초과 구독은 계층 구조 내에서 작업을 절약하는 의미 체계를 활성화하기 위해 명시적으로 허용됩니다.

 

인터페이스는 개별 엔티티의 대역폭이 항상 도달 가능한 것, 즉 max(c_i) <= C를 적용합니다. 그러나 집계 사례에서 초과 구독은 계층 내에서 작업 보존 시맨틱스를 활성화하기 위해 명시적으로 허용됩니다

e.g. Sum (c_i) may exceed C

[ Where C is the parent's bandwidth, and c_i its children ]

There are two ways in which a group may become throttled:

1. it fully consumes its own quota within a period

2. a parent's quota is fully consumed within its period

In case b) above, 자식의 런타임이 남아 있어도 부모의 런타임이 새로 고쳐질 때까지 허용되지 않습니다.

 

CFS Bandwidth Quota Caveats

slice 가 cpu에 할당되면 만료되지 않습니다. 그러나 cpu의 모든 스레드를 실행할 수 없게 될 경우 1ms를 제외한 모든 slice 가 global pool로 반환될 수 있습니다. 이것은 min_cfs_rq_runtime 변수에 의해 컴파일 시 구성됩니다. 이것은 global lock에 추가된 경쟁을 방지하는 데 도움이 되는 성능 변경입니다

 

cpu-local slices 이(가) 만료되지 않기 때문에 이해해야 할 몇 가지 흥미로운 코너 사례가 발생합니다.

 

cpu가 제한된 cgroup cpu 제한 응용 프로그램의 경우 각 주기의 각 cpu-local 슬라이스뿐만 아니라 할당량 전체를 자연스럽게 소비하기 때문에 상대적으로 무트 포인트가 됩니다. 따라서 nr_periods는 nr_throttled와 거의 같고 cpuacct.usage는 각 주기에서 cfs_quota_us와 거의 동일하게 증가할 것으로 예상됩니다.

 

스레드 수가 많은 비 CPU 바운드 애플리케이션의 경우 이 비 만료 뉘앙스를 사용하여 애플리케이션은 태스크 그룹이 실행 중인 각 CPU에서 사용되지 않은 슬라이스 양만큼 할당량 제한을 초과하여 잠시 버스트할 수 있습니다(일반적으로 CPU당 최대 1ms 또는 min_cfs_rq_runtime으로 정의됨). 이 약간의 버스트는 할당량이 CPU에 할당된 후 이전 기간에 완전히 사용되거나 반환되지 않은 경우에만 적용됩니다. 이 버스트 양은 코어 간에 전송되지 않습니다. 결과적으로 이 메커니즘은 단일 기간보다 긴 시간 창을 통해 태스크 그룹을 할당량 평균 사용량으로 여전히 엄격하게 제한합니다. 이는 또한 버스트 기능을 CPU당 1ms 이하로 제한합니다. 이는 높은 코어 수 머신에서 적은 할당량 제한으로 스레드 수가 많은 애플리케이션에 대해 더 나은 예측 가능한 사용자 환경을 제공합니다. 또한 할당량보다 적은 양의 CPU를 동시에 사용하면서 이러한 애플리케이션을 제어하는 경향을 제거합니다. 다른 방법은 슬라이스의 사용되지 않은 부분을 기간 동안 유효하게 유지하도록 허용함으로써 전체 슬라이스의 CPU 시간이 필요 없는 CPU 로컬 사일로에서 할당량이 낭비적으로 만료될 가능성을 줄였습니다.

 

특히 단일 코어 사용량이 100%에 도달하는 경우에는 cpu-bound 응용 프로그램과 non-cpu-bound 대화형 응용 프로그램 간의 상호 작용도 고려해야 합니다. 이러한 응용 프로그램에 각각 cpu-core의 절반을 할당하고 둘 다 동일한 CPU에서 예약된 경우 이론적으로 비 cpu-bound 응용 프로그램이 일부 기간에 최대 1ms의 추가 할당량을 사용하여 CPU-bound 응용 프로그램이 할당량을 동일한 양만큼 완전히 사용하지 못하게 할 수 있습니다. 이러한 경우 실행하도록 선택된 응용 프로그램은 모두 실행 가능하고 할당량이 남아 있으므로 CFS 알고리즘(CFS 스케줄러 참조)에 따라 달라집니다. 이러한 런타임 불일치는 대화형 응용 프로그램이 유휴 상태일 때 다음 기간에 보충됩니다.

 

Examples

  1. Limit a group to 1 CPU worth of runtime:
  2. * 
  3. If period is 250ms and quota is also 250ms, the group will get
1 CPU worth of runtime every 250ms.

# echo 250000 > cpu.cfs_quota_us /* quota = 250ms */
# echo 250000 > cpu.cfs_period_us /* period = 250ms */
  4. Limit a group to 2 CPUs worth of runtime on a multi-CPU machine 
    # echo 1000000 > cpu.cfs_quota_us /* quota = 1000ms */
# echo 500000 > cpu.cfs_period_us /* period = 500ms */

The larger period here allows for increased burst capacity.
  5. With 500ms period and 1000ms quota, the group can get 2 CPUs worth of runtime every 500ms:
  6. Limit a group to 20% of 1 CPU. 
    # echo 10000 > cpu.cfs_quota_us /* quota = 10ms */
# echo 50000 > cpu.cfs_period_us /* period = 50ms */
    By using a small period here we are ensuring a consistent latency response at the expense of burst capacity.
  7. With 50ms period, 10ms quota will be equivalent to 20% of 1 CPU:
  8. Limit a group to 40% of 1 CPU, and allow accumulate up to 20% of 1 CPU additionally, in case accumulation has been done. 
    # echo 20000 > cpu.cfs_quota_us /* quota = 20ms */
# echo 50000 > cpu.cfs_period_us /* period = 50ms */
# echo 10000 > cpu.cfs_burst_us /* burst = 10ms */
    Larger buffer setting (no larger than quota) allows greater burst capacity.
  9. With 50ms period, 20ms quota will be equivalent to 40% of 1 CPU. And 10ms burst will be equivalent to 20% of 1 CPU:

 

---

참고문헌

CFS Bandwidth Control — The Linux Kernel documentation