브레인 퍽 스케줄러

브레인 퍽 스케줄러(Brain Fuck Scheduler, BFS)는 2009년 8월 리눅스 커널용으로 설계된 프로세스 스케줄러로, 가장 빠른 적격 가상 마감일 우선 스케줄링 (EEVDF)을 기반으로 하며,^[2] 컴플리틀리 페어 스케줄러 (CFS) 및 O(1) 스케줄러의 대안으로 개발되었다.^[3] BFS는 콘 콜리바스가 만들었다.^[4]

간략 정보 개발자, 최종 버전 ...

브레인 퍽 스케줄러
개발자	콘 콜리바스

최종 버전	0.512 / 2016년 10월 3일(9년 전)(2016-10-03)^[1]

프로그래밍 언어	C
운영 체제	리눅스
라이선스	GNU GPL
웹사이트	kernel.kolivas.org

닫기

BFS의 목표는 다른 스케줄러와 비교하여, 특정 유형의 컴퓨테이션 작업 부하에 대한 성능을 맞추기 위해 휴리스틱 이론 조정이나 매개변수 튜닝이 필요 없는 더 간단한 알고리즘을 가진 스케줄러를 제공하는 것이다. 콜리바스는 이러한 튜닝 매개변수가 일반 사용자가 이해하기 어렵다고 주장했으며, 특히 여러 매개변수 간의 상호작용 측면에서 더욱 그러하다고 했다. 또한 이러한 튜닝 매개변수를 사용하면 특정 대상 컴퓨테이션 유형에서 성능이 향상될 수 있지만, 일반적인 경우에는 성능이 저하될 수 있다고 주장했다.^[4] BFS는 16개 미만의 CPU 코어를 가진 리눅스 데스크톱 컴퓨터에서 응답성을 향상시키는 것으로 보고되었다.^[5]

도입 직후, 새로운 스케줄러는 리눅스 커뮤니티에서 슬래시닷에 보도되었으며, 리눅스 매거진과 리눅스 프로 매거진에 리뷰가 실리면서 큰 화제가 되었다.^[3]^[6]^[7] 성능과 응답성이 향상되었다는 다양한 평가가 있었지만, 콘 콜리바스는 BFS를 메인라인 커널에 통합할 의도가 없었다.^[4]

"브레인 퍽 스케줄러"라는 이름은 의도적으로 도발적인데, 당시 기존 리눅스 프로세스 스케줄러의 복잡성에 대한 좌절감을 표현하기 위해 창시자 콘 콜리바스가 선택했다. 콜리바스는 컴플리틀리 페어 스케줄러 (CFS)와 같은 다른 스케줄러에서 튜닝 가능한 매개변수와 휴리스틱 기반 설계가 확산되면서 비전문가가 이해하거나 최적화하기 어렵다는 점을 강조하고자 했다. 이와 대조적으로 BFS는 사용자 수준의 구성 없이 데스크톱 상호작용성과 응답성 향상을 목표로 단순성과 예측 가능성을 염두에 두고 설계되었다.^[8]^[9]

이론적 설계 및 효율성

요약

관점

2009년 BFS가 도입되었고, 원래 이중 연결 리스트 자료 구조를 사용했지만,^[10]^[11] 이 자료 구조는 선입 선출 (FIFO) 큐처럼 취급된다. 작업 삽입은 $O(1)$ 이다.^[11]^{:ln 119–120} 다음 작업을 실행하기 위한 작업 검색은 최악의 경우 $O(n)$ 이다.^[11]^{:ln 209} 모든 CPU가 사용하는 단일 전역 실행 큐를 사용한다. 스케줄링 우선순위가 높은 작업이 먼저 실행된다.^[11]^{:ln 4146–4161} 실시간 및 등시성 우선순위 클래스를 제외한 모든 정책에서 작업은 가상 마감일 공식에 따라 정렬(또는 배포)되고 선택된다.

실행 동작은 라운드 로빈 스케줄링의 가중 변형이며, 특히 등시성 정책 미만에서 작업이 동일한 우선순위를 가질 때 더욱 그렇다.^[11]^{:ln 1193–1195, 334–335} 사용자 튜닝 가능한 라운드 로빈 간격(타임 슬라이스)은 기본적으로 6밀리초로, 이는 사람이 감지할 수 없는 최소한의 지터로 선택되었다.^[11]^{:ln 306} 콜리바스는 6ms 미만은 무의미하고, 라운드 로빈 타임슬라이스에 대해 300ms 이상은 처리량 측면에서 무익하다고 주장했다.^[11]^{:ln 314–320} 이 중요한 튜닝 가능 값은 처리량과 지연 시간 사이의 절충안으로 라운드 로빈 스케줄러를 맞춤 설정할 수 있다.^[11]^{:ln 229–320} 모든 작업은 실시간 FIFO를 제외하고 동일한 타임 슬라이스를 받는데, 이는 무한한 타임 슬라이스를 가진다고 가정된다.^[11]^{:ln 1646, 1212–1218, 4062, 3910}

콜리바스는 RDSL 스케줄러에서 사용했던 CPU당 다중 실행 큐(라운드 로빈^[12]^{:par. 3}) 우선순위 배열^[13]^[12] 대신 이중 연결 리스트 단일 실행 큐를 선택한 이유를 설명했다. 이는 다중 CPU 시나리오에서 공정성을 완화하고, 다중 실행 큐 시나리오에서 각 실행 큐가 자체 지연 시간과 태스크 공정성을 유지해야 하는 복잡성을 제거하기 위함이었다.^[11]^{:ln 81–92} 그는 MuQSS의 나중 버전에서는 BFS가 확정적인 지연 시간을 보장한다고 주장했다.^[14]^{:ln 471–472} 그는 또한 CPU가 증가함에 따른 잠금 경합 문제(태스크 노드 데이터 변경, 제거, 생성과 관련됨)^[14]^{:ln 126–144}와 다음 태스크 실행 조회를 위한 $O(\log n)$ 오버헤드를 인식했다.^[14]^{:ln 472–478} MuQSS는 이러한 문제를 해결하려고 시도했다.

콜리바스는 나중에 2016년 BFS v0.480 릴리스에서 설계를 스킵 리스트로 변경했다.^[15] 이로 인해 스케줄러의 효율성이 변경되었다. 그는 $O(\log n)$ 태스크 삽입, $O(1)$ 태스크 조회, $k\leq 16$ 일 때 $O(k)$ 태스크 제거를 언급했다.^[15]^{:ln 4}

가상 마감일

가상 마감일 공식은 현재 시간(niffy 단위 또는 내부 커널 시간 카운터인 나노초 jiffies)에 의해 상쇄된 nice 수준에 따라 스케일링된 라운드 로빈 타임슬라이스인 미래 마감 시간이다.^[11]^{:ln 4023, 4063} 가상 마감일은 순서만 제안할 뿐, 태스크가 미래에 스케줄링된 niffy에 정확히 실행될 것이라고 보장하지는 않는다.^[11]^{:ln 161–163}

먼저 prio 비율 조회 테이블이 생성된다.^[11]^{:ln 8042–8044} 이는 재귀 수열을 기반으로 한다. 각 nice 수준마다 10%씩 증가한다.^[11]^{:ln 161} 그래프로 그리면 포물선 패턴을 따르며, niced 태스크는 도메인으로 0에서 39(가장 높은 nice 우선순위부터 가장 낮은 nice 우선순위에 해당)까지, 범위로 128에서 5089까지 이동하는 제곱 함수로 분포된다.^[11]^{:ln 177–179, 120, 184–185} 이동 부분은 콜리바스가 언급한 가상 마감일 공식의 t 변수에서 비롯된다.

g(0) = 128
g(i) = INT( g(i-1)*11/10 )

자세한 정보 Index, Numerator ...

Index	Numerator
0	128
1	140
2	154
3	169
4	185
5	203
6	223
7	245
8	269
9	295
10	324
11	356
12	391
13	430
14	473
15	520
16	572
17	629
18	691
19	760
20	836
21	919
22	1010
23	1111
24	1222
25	1344
26	1478
27	1625
28	1787
29	1965
30	2161
31	2377
32	2614
33	2875
34	3162
35	3478
36	3825
37	4207
38	4627
39	5089

닫기

태스크의 nice-투-인덱스 매핑 함수 f(n)는 nice −20...19를 인덱스 0...39로 매핑하여 prio 비율 조회 테이블의 입력으로 사용된다. 이 매핑 함수는 커널 헤더의 sched.h에 있는 TASK_USER_PRIO() 매크로이다. 내부 커널 구현은 100에서 140 사이의 정적 우선순위 범위에서 약간 다르지만, 사용자들은 이를 −20...19 nice로 보게 된다.

자세한 정보 Nice, Index ...

Nice	Index
−20	0
−19	1
−18	2
−17	3
−16	4
−15	5
−14	6
−13	7
−12	8
−11	9
−10	10
−9	11
−8	12
−7	13
−6	14
−5	15
−4	16
−3	17
−2	18
−1	19
0	20
1	21
2	22
3	23
4	24
5	25
6	26
7	27
8	28
9	29
10	30
11	31
12	32
13	33
14	34
15	35
16	36
17	37
18	38
19	39

닫기

가상 마감일은 이 정확한 공식에 기반한다:^[11]^{:ln 4063, 4036, 4033, 1180}

T = 6
N = 1<<20
d(n,t) = t + g(f(n)) * T * (N/128)

또는 다음과 같이 표현될 수 있다.

{\mathtt {d(n,t)={\frac {g(f(n))}{128}}*T*N+t}}

^[16]

여기서 d(n,t)는 nice n과 현재 시간 t(niffy 단위)의 함수로 u64 정수 나노초 단위의 가상 마감일이며, g(i)는 인덱스의 함수로 prio 비율 테이블 조회, f(n)은 태스크의 nice-투-인덱스 매핑 함수, T는 밀리초 단위의 라운드 로빈 타임슬라이스, N은 $\mathrm {\frac {10^{9}ns}{10^{3}ms}}$ 의 변환 계수를 나노초 단위의 1밀리초로 근사화한 지연 감소 상수로, 콜리바스는 그 규모와 비슷한 2의 거듭제곱 상수 N을 사용한다.^[11]^{:ln 1173–1174} d 값이 작을수록 가상 마감일이 빨라지며, 이는 음의 nice 값에 해당한다. d 값이 클수록 가상 마감일이 뒤로 밀리며, 이는 양의 nice 값에 해당한다. 타임슬라이스가 만료될 때마다 이 공식을 사용한다.^[11]^{:ln 5087}

2진수 128은 10진수 100에 해당하며, 이는 "의사 100"일 가능성이 있다.^[11]^{:ln 3415} 2진수 115는 10진수 90에 해당한다. 콜리바스는 "빠른 시프트"를 위해 128을 사용하는데,^[11]^{:ln 3846, 1648, 3525} 이는 나눗셈이 2진수 오른쪽 시프트인 경우이다.

자세한 정보 Nice, Virtual deadline in timeslices relative to t ...

Nice	Virtual deadline in timeslices relative to t	Virtual deadline in exact seconds relative to t
−20	1.0	0.006
−19	1.09	0.006562
−18	1.2	0.007219
−17	1.3	0.007922
−16	1.4	0.008672
−15	1.5	0.009516
−14	1.7	0.010453
−13	1.9	0.011484
−12	2.1	0.012609
−11	2.3	0.013828
−10	2.5	0.015187
−9	2.7	0.016688
−8	3.0	0.018328
−7	3.3	0.020156
−6	3.6	0.022172
−5	4.0	0.024375
−4	4.4	0.026812
−3	4.9	0.029484
−2	5.3	0.032391
−1	5.9	0.035625
0	6.5	0.039188
1	7.1	0.043078
2	7.8	0.047344
3	8.6	0.052078
4	9.5	0.057281
5	10.5	0.063000
6	11.5	0.069281
7	12.6	0.076172
8	13.9	0.083766
9	15.3	0.092109
10	16.8	0.101297
11	18.5	0.111422
12	20.4	0.122531
13	22.4	0.134766
14	24.7	0.148219
15	27.1	0.163031
16	29.8	0.179297
17	32.8	0.197203
18	36.1	0.216891
19	39.7	0.238547

닫기

스케줄링 정책

BFS는 CPU 작업에 허용되는 태스크의 양을 결정하기 위해 스케줄링 정책을 사용한다. BFS는 최상위부터 최하위까지 4가지 스케줄링 계층(스케줄링 정책 또는 스케줄링 클래스라고 함)을 사용하여 태스크를 선택하는 방식을 결정하며,^[11]^{:ln 4146–4161} 최상위 계층의 태스크가 먼저 실행된다.

각 태스크에는 prio라는 특별한 값이 있다. v0.462 버전(ck 4.0 커널 패치셋에서 사용됨)에서는 총 103개의 "우선순위 큐"(또는 prio) 또는 허용되는 값이 존재한다. 실제 특별한 자료 구조는 우선순위 큐로 사용되지 않았고, 이중 연결 리스트 실행 큐 자체만 사용되었다. prio 값이 낮을수록 중요도가 높고 먼저 실행된다.

실시간 정책

실시간 정책은 실시간 태스크를 위해 설계되었다. 이 정책은 실행 중인 태스크가 하위 prio 태스크 또는 하위 우선순위 정책 계층에 의해 중단(즉, 선점)될 수 없음을 의미한다. 스케줄러가 실시간 정책 하에서 고려하는 우선순위 클래스는 SCHED_RR 및 SCHED_FIFO로 표시된 태스크이다.^[11]^{:ln 351, 1150} 스케줄러는 실시간 라운드 로빈(SCHED_RR)과 실시간 FIFO(SCHED_FIFO)를 다르게 처리한다.^[11]^{:ln 3881–3934}

설계는 처음 100개의 정적 우선순위 큐를 설정했다.^[11]^{:ln 189}

실행을 위해 선택될 태스크는 100개 큐 중 가장 낮은 prio 값의 태스크 가용성과 FIFO 스케줄링을 기반으로 한다.^[11]^{:ln 4146–4161}

포크 시, 프로세스 우선순위는 일반 정책으로 강등된다.^[11]^{:ln 2708}

실시간 정책 클래스에 대한 요청과 함께 sched_setscheduler가 비특권 사용자(즉, 비루트 사용자)에 의해 호출될 경우, 스케줄러는 태스크를 등시성 정책으로 강등한다.^[11]^{:ln 350–359, 5023–5025}

등시성 정책

등시성 정책은 루트가 아닌 사용자를 위한 거의 실시간 성능을 위해 설계되었다.^[11]^{:ln 325}

이 설계는 기본적으로 의사 실시간 태스크로 실행되지만, 실시간 수준으로 튜닝될 수 있는 하나의 우선순위 큐를 설정했다.^[11]^{:ln 1201, 346–348}

이 정책의 동작은 태스크가 온라인 CPU 수와 타이머 해상도에 5초를 스케일링한 값에 1틱을 더한 튜닝 가능한 리소스 처리 비율(기본값 70%^[11]^{:ln 343, 432})을 초과할 경우 일반 정책으로 강등될 수 있다.^[11]^{:ln 343, 3844–3859, 1167, 338}^[14]^{:ln 1678, 4770–4783, 734} 다중 실행 큐 설계로 인해 MuQSS에서 공식이 변경되었다. 정확한 공식은 다음과 같다.

{\mathtt {T_{BFS}=((5*F*n)+1)*R}}

{\mathtt {T_{MuQSS}=(5*F)*R}}

여기서 T는 등시성 틱의 총 수, F는 타이머 주파수, n은 온라인 CPU의 수, R은 소수점 대신 정수로 된 튜닝 가능한 리소스 처리 비율이다. 타이머 주파수는 기본적으로 250으로 설정되어 커널에서 편집 가능하지만, 일반적으로 서버의 경우 100Hz, 대화형 데스크톱의 경우 1000Hz로 튜닝된다. 250이 균형 잡힌 값이다. R을 100으로 설정하면 태스크가 실시간처럼 작동하고 0으로 설정하면 의사 실시간이 아니게 되며, 중간 값은 의사 실시간이다.^[11]^{:ln 346–348}

가장 빠른 가상 마감일을 가진 태스크가 실행을 위해 선택되지만, 여러 등시성 태스크가 존재할 경우, nice 수준을 고려하지 않고 라운드 로빈 방식으로 태스크를 스케줄링하여 튜닝 가능한 라운드 로빈 값(기본값 6ms)으로 태스크가 공정하게 차례로 실행될 수 있도록 한다.^[11]^{:ln 334}

등시성 정책의 이러한 동작은 BFS 및 MuQSS에만 고유하며 다른 CPU 스케줄러에는 구현되지 않을 수 있다.^[11]^{:ln 324, 8484–8485}^[14]^{:ln 1287–1288}

일반 정책

일반 정책은 일반적인 사용을 위해 설계되었으며 기본 정책이다. 새로 생성된 태스크는 일반적으로 일반으로 표시된다.^[11]^{:ln 502}

이 설계는 하나의 우선순위 큐를 설정했으며, 가장 빠른 가상 마감일에 따라 태스크가 먼저 실행되도록 선택된다.

유휴 우선순위 정책

유휴 우선순위는 분산 프로그램 및 트랜스코더와 같은 백그라운드 프로세스를 위해 설계되었으므로 포그라운드 프로세스 또는 이 스케줄링 정책 위에 있는 프로세스는 중단 없이 실행될 수 있다.^[11]^{:ln 363–368}

이 설계는 1개의 우선순위 큐를 설정했으며, 태스크는 무한한 리소스 점유를 방지하기 위해 자동으로 일반 정책으로 승격될 수 있다.^[11]^{:ln 368}

동일한 우선순위 정책에 있는 다른 유휴 우선순위 태스크 중 다음에 실행될 태스크는 가장 빠른 가상 마감일에 따라 선택된다.^[11]^{:ln 4160–4161}

선점

선점은 더 높은 우선순위 정책(즉, 더 높은 prio)을 가진 새로 준비된 태스크가 현재 실행 중인 태스크보다 더 빠른 가상 마감일을 가질 때 발생할 수 있으며, 이 경우 현재 실행 중인 태스크는 스케줄링 해제되어 큐의 맨 뒤로 이동된다.^[11]^{:ln 169–175} 스케줄링 해제는 가상 마감일이 업데이트되었음을 의미한다.^[11]^{:ln 165–166} 태스크가 모든 시간을 사용했을 때, 태스크의 시간은 최대 라운드 로빈 퀀텀으로 다시 채워진다.^[11]^{:ln 4057–4062, 5856} 스케줄러가 가장 빠른 가상 마감일을 가진 더 높은 prio의 태스크를 발견하면, 모든 논리적 CPU(하이퍼스레드 코어/SMT 스레드 포함)가 바쁜 경우에만 중요도가 낮은 현재 실행 중인 태스크 대신 실행된다. 스케줄러는 사용되지 않는 논리적 CPU가 있다면 가능한 한 오래 선점을 지연한다.

태스크가 유휴 우선순위 정책으로 표시된 경우, 다른 유휴 정책으로 표시된 태스크라도 전혀 선점할 수 없으며 협력적 멀티태스킹을 사용한다.^[11]^{:ln 2341–2344}

태스크 배치, 다중 코어

스케줄러가 비유니코어 시스템에서 깨어나는 태스크를 발견하면, 해당 태스크를 실행할 논리적 CPU를 결정해야 한다. 스케줄러는 태스크가 실행된 동일한 CPU에서 유휴 하이퍼스레드 코어(또는 유휴 SMT 스레드)를 가장 선호하고,^[11]^{:ln 261} 그 다음은 멀티코어 CPU의 다른 유휴 코어,^[11]^{:ln 262} 그 다음은 동일한 NUMA 노드의 다른 CPU,^[11]^{:ln 267, 263–266, 255–258} 그 다음은 동일한 NUMA 노드에서 선점될 모든 바쁜 하이퍼스레드 코어/SMT 스레드/논리적 CPU,^[11]^{:ln 265–267} 그 다음은 다른 (원격) NUMA 노드를 선호하며,^[11]^{:ln 268–270} 이는 선호 목록에 따라 순위가 매겨진다.^[11]^{:ln 255–274} 이 특별한 스캔은 태스크 마이그레이션으로 인한 지연 시간 오버헤드를 최소화하기 위해 존재한다.^[11]^{:ln 245, 268–272}

선점 순서는 위 문단과 유사하다. 선점 순서는 동일한 멀티코어 내 하이퍼스레드 코어/SMT 단위가 먼저이고, 그 다음은 멀티코어 내 다른 코어, 그 다음은 동일한 NUMA 노드 내 다른 CPU이다.^[11]^{:ln 265–267} 다른 원격 NUMA 노드에서 선점할 태스크를 스캔할 때, 선점은 해당 머신의 모든 논리적 CPU(하이퍼스레드 코어/SMT 스레드 포함)가 모두 바쁘다고 가정할 때, 낮은 prio 또는 동일한 prio 또는 나중 가상 마감일을 가진 바쁜 스레드에 대해 이루어진다.^[11]^{:ln 270} 스케줄러는 선점할 낮은 우선순위 또는 동일한 우선순위 정책 태스크(필요한 경우 나중 가상 마감일을 가진)를 스캔하고, 선점할 수 없는 더 높은 우선순위 정책 태스크가 있는 논리적 CPU를 피해야 한다. 로컬 선점은 원격 유휴 NUMA 단위를 스캔하는 것보다 더 높은 순위를 갖는다.^[11]^{:ln 265–269}

CPU 주파수 조절(CPU 주파수 거버너라고도 함)에 의해 CPU 속도가 느려져 태스크가 비자발적으로 선점될 때, 실시간 정책으로 표시된 태스크를 제외하고는 태스크에 특별히 "고정"(sticky) 표시가 된다.^[11]^{:ln 2085} 고정 표시는 태스크가 아직 사용되지 않은 시간을 가지고 있으며, 태스크가 동일한 CPU에서만 실행되도록 제한됨을 나타낸다.^[11]^{:ln 233–243} CPU 스케일링 거버너가 CPU를 더 느린 속도로 스케일링할 때마다 태스크는 고정으로 표시된다.^[11]^{:ln 2082–2107, 8840–8848} 유휴 상태로 고정된 태스크는 우연히 전체 Ghz 속도로 다시 실행되거나, 태스크가 실행된 동일한 CPU가 아닌 최적의 유휴 CPU에서 다시 스케줄링되어 실행된다.^[11]^{:ln 2082–2086, 239–242, 2068–2079} 태스크를 다른 CPU나 NUMA 노드로 마이그레이션하는 오버헤드로 인해 지연 시간이 증가하기 때문에 태스크를 다른 곳으로 마이그레이션하는 것보다 유휴 상태로 두는 것이 바람직하지 않다.^[11]^{:ln 228, 245} 이 고정 기능은 BFS의 마지막 버전(v0.512)에서 제거되었으며(콜리바스의 패치셋 4.8-ck1에 해당), MuQSS에는 존재하지 않았다.

schedtool

특권 사용자는 schedtool 프로그램을 사용하여 프로세스의 우선순위 정책을 변경하거나,^[11]^{:ln 326, 373} 프로그램 자체에서 변경할 수 있다.^[11]^{:ln 336} 우선순위 클래스는 코드 수준에서 시스템 호출인 sched_setscheduler를 통해 조작될 수 있으며, 이는 루트에게만 허용된다.^[17] schedtool은 이 기능을 사용한다.^[18]

벤치마크

현대 연구에서^[5] 저자는 리눅스 커널 v3.6.2를 사용하여 BFS와 CFS를 여러 성능 기반 종점으로 비교했다. 이 연구의 목적은 바닐라 리눅스 커널의 컴플리틀리 페어 스케줄러(CFS)와 해당 커널에 ck1 패치셋이 적용된 BFS를 평가하는 것이었다. 7개의 다른 머신을 사용하여 성능 기반 지표를 사용하여 차이점이 존재하는지, 그리고 어느 정도까지 확장되는지 확인했다. 논리 CPU 수는 1개에서 16개까지 다양했다. 이러한 종점은 BFS의 주요 설계 목표에 포함되지 않았다. 결과는 고무적이었다.

BFS를 포함한 ck1 패치셋이 적용된 커널은 테스트된 거의 모든 성능 기반 벤치마크에서 CFS를 사용하는 바닐라 커널보다 1%에서 8% 더 우수한 성능을 보였다.^[5] 더 큰 테스트셋으로 추가 연구를 수행할 수 있지만, 평가된 7개 PC의 소규모 테스트셋을 기반으로 볼 때, 이러한 프로세스 큐잉, 효율성/속도 증가는 전반적으로 CPU 유형(모노, 듀얼, 쿼드, 하이퍼스레드 등), CPU 아키텍처(32비트 및 64비트) 및 CPU 다중성(모노 또는 듀얼 소켓)과는 무관하다.

또한 코어 2 듀오 및 코어 i7과 같이 일반적인 워크스테이션 및 노트북을 대표하는 여러 "현대" CPU에서 BFS는 모든 벤치마크에서 바닐라 커널의 CFS보다 일관되게 우수한 성능을 보였다. 효율성과 속도 향상은 작지만 상당했다.

채택

BFS는 다음 데스크톱 리눅스 배포판의 기본 스케줄러이다.

또한 BFS는 구글의 안드로이드 개발 저장소의 실험 브랜치에 추가되었다.^[23] 그러나 블라인드 테스트에서 개선된 사용자 경험을 보이지 않아 프로요 릴리스에는 포함되지 않았다.^[24]

MuQSS

요약

관점

BFS는 정식 명칭이 다중 큐 스킵 리스트 스케줄러(Multiple Queue Skiplist Scheduler)인 MuQSS로 대체되어 중단되었다.^[25]^[26] 주요 저자는 2021년 8월 말까지 MuQSS 작업을 중단했다.^[27]

이론적 설계 및 효율성

MuQSS는 양방향 정적 배열 8레벨 스킵 리스트를 사용하며, 태스크는 정적 우선순위[큐](스케줄링 정책을 의미)와 가상 마감일에 따라 정렬된다.^[14]^{:ln 519, 525, 537, 588, 608} 8은 캐시라인에 배열을 맞추기 위해 선택되었다.^[14]^{:ln 523} 이중 연결 자료 구조는 태스크 제거 속도를 높이기 위해 선택되었다. 이중 스킵 리스트를 사용하면 태스크 제거가 O(1)에 불과한 반면, 윌리엄 푸의 원래 설계는 최악의 경우 $O(n)$ 이 소요된다.^[14]^{:ln 458}

작업 삽입은 $O(\log n)$ 이다.^[14]^{:ln 458} 다음 작업 실행을 위한 검색은 $O(k)$ 인데, 여기서 $k$ 는 CPU 수이다.^[14]^{:ln 589–590, 603, 5125} 다음 작업 실행은 실행 큐당 $O(1)$ 이지만,^[14]^{:ln 5124} 스케줄러는 CPU 간 작업 공정성을 유지하고, 지연 시간 또는 균형(NUMA 노드 간 액세스보다 동일 NUMA 노드에서 CPU 사용률 및 캐시 일관성을 최대화하기 위해)을 위해 다른 모든 실행 큐를 검사하므로 궁극적으로 $O(k)$ 이다.^[14]^{:ln 591–593, 497–501, 633–656} 처리할 수 있는 최대 작업 수는 CPU당 실행 큐당 64k개이다.^[14]^{:ln 521} 일부 구성에서는 CPU당 하나의 실행 큐를 사용하는 다중 작업 실행 큐를 사용하지만, 이전 버전인 BFS는 모든 CPU에 대해 하나의 작업 실행 큐만 사용했다.

태스크는 스킵 리스트에 실시간 정책 우선순위가 먼저 오고 유휴 정책 우선순위가 마지막으로 오는 방식으로 그래디언트(단계별 변화)로 정렬된다.^[14]^{:ln 2356–2358} 일반 및 유휴 우선순위 정책은 nice 값을 사용하는 가상 마감일에 따라 정렬된다.^[14]^{:ln 2353} 실시간 및 등시성 정책 태스크는 nice 값을 무시하고 선입 선출 (FIFO) 순서로 실행된다.^[14]^{:ln 2350–2351} 동일한 키를 가진 새로운 태스크는 FIFO 순서로 배치되는데, 이는 새로운 태스크가 목록의 끝(즉, 수직으로 가장 위쪽 노드)에 배치되고, 0번째 레벨 또는 맨 아래쪽에 있는 태스크가 수직으로 가장 가까운 위쪽 및 헤드 노드에서 가장 먼 태스크보다 먼저 실행된다는 의미이다.^[14]^{:ln 2351–2352, 590} 삽입 정렬에 사용되는 키는 정적 우선순위^[14]^{:ln 2345, 2365,} 또는 가상 마감일이다.^[14]^{:ln 2363}

사용자는 멀티코어 간에 실행 큐를 공유하거나 논리적 CPU당 하나의 실행 큐를 가질 수 있다.^[14]^{:ln 947–1006} 실행 큐 공유 설계는 처리량과 맞바꾸어 지연 시간을 줄이려는 의도였다.^[14]^{:ln 947–1006}

MuQSS가 도입한 새로운 동작은 타임슬라이스가 소진되어 태스크를 다시 스케줄링할 때 밀리초 미만의 정확도를 위한 고해상도 타이머 사용이었다.^[14]^{:ln 618–630, 3829–3851, 3854–3865, 5316}

같이 보기

공정 공유 스케줄링

각주

Loading content...

외부 링크

Loading content...

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.