Brain Fuck 스케줄러

Brain Fuck 스케줄러
개발자	콘 콜리바스
최종 릴리즈	0.512 / 2016년 10월 3일, 5년전(
기입처	C
운영 체제	리눅스
면허증.	GNU GPL
웹 사이트	kernel.kolivas.org

리눅스 커널의 단순화된 구조에서 프로세스 스케줄러의 위치

Brain Fuck Scheduler(BFS)는 Complete Fair Scheduler(CFS) 및 O(1) ^[2]Scheduler의 대안으로 2009년8월에 Linux 커널용으로 설계된 프로세스스케줄러입니다BFS는 경험이 풍부한 커널 프로그래머 Con Kolivas에 ^[3]의해 작성되었습니다.

BFS의 목적은 다른 스케줄러에 비해 단순한 알고리즘을 스케줄러에 제공하는 것입니다.이 알고리즘은 특정 유형의 계산 워크로드에 따라 성능을 맞춤화하기 위해 휴리스틱스나 파라미터를 조정할 필요가 없습니다.Kolivas는 이러한 조정 가능한 매개변수를 일반 사용자가 이해하기 어려웠으며, 특히 서로에 대한 여러 매개변수의 상호작용 측면에서, 그러한 조정 매개변수의 사용은 종종 t의 더 나쁜 성능의 희생을 감수하면서 특정 목표 유형의 계산에서 향상된 성능을 초래할 수 있다고 주장했다.일반적인 ^[3]경우입니다.BFS는 코어 ^[4]수가 16개 미만인 Linux 데스크톱 컴퓨터에서 응답성이 향상되는 것으로 보고되었습니다.

소개 직후, 새로운 스케줄러는 Linux 커뮤니티 내에서 Slashdot에 등장하여 Linux Magazine 및 Linux Pro ^[2]^[5]^[6]Magazine 리뷰와 함께 헤드라인을 장식했다.성능 및 응답성 향상에 대한 다양한 리뷰가 있었지만 Con Kolivas는 BFS를 메인라인 ^[3]커널에 통합하려는 의도는 없었습니다.

이론적인 설계와 효율

2009년에 BFS가 도입되어 원래 이중 링크 리스트 데이터 ^[7]^[8]구조를 사용했지만 데이터 구조는 큐처럼 취급됩니다.작업 $O(1)$ 은 $O(1)$ O ( $O(1)$ ) $O(1)$ { $displaystyle O$ (1 $O(1)$ ^[8]^{: ln 119-120}입니다. 실행할 다음 작업에 대한 작업 검색은 O $)$ { $displaystyle$ O $(n)}$ 최악의 $O(n)$ ^[8]^{: ln 209} $O(n)$ 입니다.모든 CPU가 사용하는 단일 글로벌 실행 큐를 사용합니다.스케줄링 우선순위가 높은 작업이 ^[8]^{: ln 4146–4161}먼저 실행됩니다.작업은 실시간 및 Isocronous priority 클래스를 제외한 모든 정책에서 가상 기한 공식에 따라 정렬(또는 분산)되고 선택됩니다.

실행 동작은 특히 태스크가 Isocronous ^[8]^{: ln 1193-1195, 334–335}정책보다 우선순위가 동일한 경우 라운드 로빈 스케줄러의 가중치 변동입니다.사용자가 조정할 수 있는 라운드로빈 간격(타임슬라이스)은 디폴트로 6밀리초입니다.이것은,^[8]^{: ln 306} 인간이 검출할 수 있는 최소 지터로 선택되고 있습니다.Kolivas는 라운드 로빈 타임슬라이스가 6밀리초 미만인 것은 의미가 없으며 300밀리초를 초과하는 것은 throughput ^[8]^{: ln 314-320}측면에서 성과가 없다고 주장했습니다.이 중요한 조정 가능은 스루풋과 ^[8]^{: ln 229–320}레이텐시의 트레이드오프로서 라운드 로빈 스케줄러를 커스터마이즈 할 수 있습니다.무제한 타임 ^[8]^{: ln 1646, 1212–1218, 4062, 3910}슬라이스를 갖는 것으로 가정되는 실시간 FIFO를 제외하고 모든 태스크가 동일한 타임 슬라이스를 얻습니다.

Kolivas 왜 그는 두배로 연결 리스트 mono-runqueue과 CPU는 그의 RDSL 스케줄러에 있었고 복잡성은multi-runqueue 시나리오의 각 runqueue mainta 제거 다중 CPU시나리오 중 공정성을 완화하기 위해 넣는 데 사용된multi-runqueue(라운드 robin[9]:이븐파 3)우선 순위 array[10][9] 가려고 선택한 이유를 설명했다.자체latencie에및 [태스크] 공정성.^[8]^{: ln 81-92}그는 나중에 MuQSS를 ^[11]^{: ln 471–472}반복할 때 BFS를 통해 결정론적 지연이 보장되었다고 주장했다.또한 CPU의 증가와 실행을 ^[11]^{: ln 472–478}위한 O $O(\log n)$ n $)\style$ O(\ $log$ n)\style O $(\$ log n $)$ 의 $O(\log n)$ 오버헤드로 인한 잠금 경합 문제(태스크 노드 데이터의 ^[11]^{: ln 126–144}변경, 삭제, 작성과 관련된 문제)도 인식하고 있습니다.MuQSS는 이러한 문제를 해결하려고 했습니다.

Kolivas는 이후 2016년 ^[12]BFS의 v0.480 릴리즈에서 디자인을 건너뛰기 목록으로 변경하였다.이번에는 스케줄러의 효율이 변경되었습니다.O $O(\log n)$ ( $O(\log n)$ n $O(\log n)$ ) { $displaystyle$ O ( \ $log$ n ) }태스크 $O(\log n)$ $O(1)$ 삽입 $O(1)$ $O(1)$ ( ) $O(1)$ { $displaystyle$ O ( $1$ $)태스크$ 룩업, $O(k)$ ( $O(k)$ ) { $displaystyle$ O ( k ) $k\leq 16$ $k\leq 16$ { $displaystyle 16$ 태스크 삭제에 ^[12]^{: ln 4} $O(\log n)$ 했습니다.

가상 기한

가상 기한 공식은 현재 시각에 의한 적절한 레벨오프셋(내부 커널 시간 ^[8]^{: ln 4023, 4063}카운터인 niffy 단위 또는 nano second jiffies)에 근거한 스케일링된 라운드 로빈 타임슬라이스인 미래 마감 시간입니다.가상 마감은 주문만 제시했을 뿐 작업이 정확히 예정된 날짜에 ^[8]^{: ln 161-163}실행된다는 보장은 없습니다.

우선 prio ratio 룩업테이블을 만듭니다.^[8]^{: ln 8042-8044}이것은 재귀적 시퀀스를 기반으로 합니다.좋은 ^[8]^{: ln 161}레벨마다 10%씩 증가합니다.그래프로 나타내면 포물선 패턴을 따르며, 네이스된 태스크는 도메인으로 0 ~39(가장 높은 우선순위에서 가장 낮은 우선순위로 대응)의 이동 제곱 함수로 배포되며,^[8]^{: ln 177-179, 120, 184–185} 범위로 128 ~5089가 배포됩니다.움직이는 부분은T 변수는 Kolivas가 암시한 가상 마감 공식에 있습니다.

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

색인	분자
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

태스크의 나이스-인덱스 매핑 함수 f(n)는 나이스 -20에서 매핑됩니다.19에서 지수 0으로...prio ratio lookup 테이블에 대한 입력으로 사용되는 39.이 매핑 함수는TASK_USER_PRIO()커널 헤더 내의 sched.h에 매크로를 입력합니다.내부 커널 구현은 100 ~140의 정적 우선 순위 범위에 따라 약간 다르지만 사용자는 -20으로 인식합니다.19개 괜찮네요.

좋아.	색인
−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

가상 기한은 다음 ^[8]^{: ln 4063, 4036, 4033, 1180}공식을 기반으로 합니다.

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

또,

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

^[13]

여기서 d(n,t)는 nice n 및 t의 함수로서 u64 정수 나노초 단위의 가상 마감 시간, g(i)는 인덱스의 함수로서 prio 비율 테이블 룩업, f(n)는 태스크의 nice-to-index 매핑 함수, T는 밀리초 단위의 라운드 로빈 타임슬라이스, N은 1밀리초의 상수입니다. $\mathrm {\frac {10^{9}ns}{10^{3}ms}}$ $\mathrm {\frac {10^{9}ns}{10^{3}ms}}$ 의 $\mathrm {\frac {10^{9}ns}{10^{3}ms}}$ 계수의 지연 시간 감소 $근사치$ (\ $displaystyle \mathrm$ \ $frac {$ 10 $^{9}ns}{10^{$ 3}ms $}})$ 그러나 $\mathrm {\frac {10^{9}ns}{10^{3}ms}}$ Kolivas는 대략적인 척도를 ^[8]^{: ln 1173–1174}가진 베이스 2 상수 N을 사용한다.d 값이 작을수록 가상 기한이 음의 nice 값에 더 빨리 대응한다는 것을 의미합니다.d 값이 클수록 가상 기한이 양의 nice 값에 따라 나중에 뒤로 밀려난다는 것을 나타냅니다.타임슬라이스가 ^[8]^{: ln 5087}만료될 때마다 이 공식을 사용합니다.

베이스 2의 128은 베이스 10의 100과 경우에 따라서는 「100」^[8]^{: ln 3415}에 대응합니다.베이스 2의 115는 베이스 10의 90에 대응합니다.Kolivas는 "고속 이동"^[8]^{: ln 3846, 1648, 3525}에 128을 사용합니다. 나눗셈은 오른쪽 이동 기준 2입니다.

좋아.	t에 상대적인 가상 기한(타임 라이선스)	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개의 스케줄링 계층(스케줄링 정책 또는 스케줄링 클래스라고 함)을 best에서 best로 정렬하여 사용합니다.이것에 의해, 톱에 있는 계층이 최초로 실행되는 태스크가 어떻게 선택되는지가^[8]^{: ln 4146-4161} 결정됩니다.

각 작업에는 prio라고 하는 특별한 값이 있습니다.v0.462 에디션(-ck 4.0 커널 패치셋에서 사용)에서는 총 103개의 "priority 큐"(prio라고도 함) 또는 허용되는 값이 있습니다.priority 큐로서 실제로 특별한 데이터 구조는 사용되지 않고 이중 링크 리스트 런큐 자체만 사용되었습니다.prio 값이 작을수록 prio 값이 더 중요해지고 먼저 실행됩니다.

실시간 정책

실시간 정책은 실시간 작업을 위해 설계되었습니다.이 정책은 실행 중인 태스크가 낮은 prio-ed 태스크 또는 낮은 priority 정책 계층에 의해 중단될 수 없음을 의미합니다.스케줄러에 의해 실시간정책 하에서 고려되는 priority 클래스는 SCHED_R 및 SCHED_FIFO ^[8]^{: ln 351, 1150}마크가 붙은 클래스입니다.스케줄러는 Realtime Round Robin(SCHED_R)과 Realtime FIFO(SCHED_FIFO)를 ^[8]^{: ln 3881-3934}다르게 취급합니다.

이 설계에서는 최초 100개의 스태틱priority ^[8]^{: ln 189}큐가 배치되어 있습니다.

실행 대상으로 선택되는 작업은 100개의 큐 중 가장 낮은 prio 값의 작업 가용성과 FIFO ^[8]^{: ln 4146–4161}스케줄링을 기반으로 합니다.

포크에서는 프로세스 우선순위가 일반 ^[8]^{: ln 2708}정책으로 강등됩니다.

실시간 정책 클래스 요청과 함께 sched_setscheduler를 권한 없이(즉, 루트 사용자가 아닌) 사용하면 스케줄러는 작업을 Isocronous ^[8]^{: ln 350–359, 5023–5025}정책으로 강등합니다.

등시성 정책

Isocronous 정책은 루트 사용자가 ^[8]^{: ln 325}아닌 사용자의 거의 실시간 성능을 제공하도록 설계되었습니다.

이 설계에서는 기본적으로 의사 실시간 태스크로 실행되지만 ^[8]^{: ln 1201, 346–348}실시간 수준으로 튜닝할 수 있는 priority 큐가 1개 배치되어 있습니다.

정책의 동작에 의해 온라인 CPU의 수 및 타이머 ^[8]^{: ln 343, 3844–3859, 1167, 338}^[11]^{: ln 1678, 4770–4783, 734}분해능에 1틱을 더한 5초의 조정 가능한 자원 처리율(디폴트로는^[8]^{: ln 343, 432} 70%)을 넘으면 작업이 일반^[8]^{: ln 336} 정책으로 강등될 수 있습니다.MuQSS에서는 멀티 런큐 설계에 의해 공식이 변경되었습니다.정확한 공식은 다음과 같습니다.

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

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

여기서 T는 등시성 틱의 합계수, F는 타이머 주파수, n은 온라인 CPU의 수, R은 조정 가능한 자원 처리율(10 진수가 아닌 정수)입니다.타이머 주파수는 기본 250으로 설정되어 커널에서 편집 가능하지만 보통 서버의 경우 100Hz, 대화형 데스크톱의 경우 1000Hz로 조정됩니다.250은 균형값입니다.R을 100으로 설정하면 작업이 실시간으로 동작하고 0으로 설정하면 의사 실시간이 아니며 중간에 있는 것은 의사 ^[8]^{: ln 346–348}실시간이 아닙니다.

가장 빠른 가상 기한을 가진 작업이 실행되도록 선택되었지만 여러 Isocronous 작업이 존재하는 경우 라운드 로빈으로 스케줄링되므로 조정 가능한 라운드 로빈 값(기본값은 6 ms)을 적절한 ^[8]^{: ln 334}확률로 차례로 실행할 수 있습니다.

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

일반 정책

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

설계는 1개의 우선 큐를 배치하고 작업은 가장 빠른 가상 마감에 따라 먼저 실행되도록 선택됩니다.

아이돌 priority 정책

아이돌 priority는 분산 프로그램이나 트랜스코더 등의 백그라운드프로세스용으로 설계되어 포그라운드프로세스 또는 이 스케줄링 정책 이상의 프로세스를 중단 ^[8]^{: ln 363–368}없이 실행할 수 있습니다.

설계에 의해 1개의 priority 큐와 태스크가 자동으로 일반 정책으로 승격되어 무기한 자원 ^[8]^{: ln 368}보유를 방지할 수 있습니다.

동일한 우선 순위 정책에 상주하는 다른 작업과의 유휴 우선 순위에서 실행된 다음 작업이 가장 빠른 가상 ^[8]^{: ln 4160–4161}마감일까지 선택됩니다.

프리엠프션

프리엠프션은 priority 정책이 높은 새로 준비된 작업(즉 prio가 높은 작업)이 현재 실행 중인 작업보다 빠른 가상 기한을 가질 때 발생할 수 있습니다.이 작업은 스케줄 해제되어 ^[8]^{: ln 169–175}큐의 맨 뒤에 배치됩니다.스케줄 해제란 가상 기한이 ^[8]^{: ln 165–166}갱신되는 것을 의미합니다.작업 시간이 ^[8]^{: ln 4057–4062, 5856}모두 소모되면 최대 라운드 로빈 퀀텀으로 다시 채워집니다.스케줄러가 가상 기한이 가장 빠른 상위 prio에서 작업을 발견한 경우 현재 실행 중인 작업 대신 모든 논리 CPU(하이퍼스레드 코어/SMT 스레드 포함)가 사용 중인 경우에만 작업이 실행됩니다.사용하지 않는 논리 CPU가 있는 경우 스케줄러는 프리엠프션을 가능한 한 지연시킵니다.

태스크에 아이돌priority 정책이 표시되어 있는 경우 다른 아이돌정책 마킹된 태스크도 프리엠프트할 수 없고 공동 멀티태스킹을 ^[8]^{: ln 2341–2344}사용할 수 없습니다.

작업 배치, 다중 코어

스케줄러는 비유니코어 시스템에서 웨이크업 작업을 검출하면 작업을 실행할 논리 CPU를 결정해야 합니다.그 수첩 가장 한가한hyperthreaded 코어 처음으로 같은 CPU에는 작업 on,[8]:ln 261 후 다심 CPU,[8]의 다른 아이들 핵심:ln 실행(또는 유휴 SMT사용 threads)는 262개 그 다음 다른 CPU 같은 불균일 기억 장치 접근 node,[8]에:ln 267명, 263–266, 255–258 다음 모두 바쁘hyperthreaded 코어/SMT사용 스레드/논리적인 CPU에 선점할 집착하고 있다. 그 같은 불균일 기억 장치 접근 node,[8]:ln 265–267 다음 다른(원격)불균일 기억 장치 접근 끄덕였다e^[8]^{: ln 268–270} 및 preference ^[8]^{: ln 255–274}리스트에 랭크되어 있습니다.이 특수 검사는 ^[8]^{: ln 245, 268–272}작업 마이그레이션으로 인한 지연 시간 오버헤드를 최소화하기 위해 존재합니다.

선매조건부 순서는 위 항과 유사하다.프리엠프션 순서는 먼저 동일한 멀티코어의 하이퍼스레드 코어/SMT 장치, 다음으로 멀티코어의 다른 코어와 동일한 NUMA ^[8]^{: ln 265-267}노드의 다른 CPU입니다.다른 원격 NUMA 노드에서 프리엠프션할 작업을 검색할 때 프리엠프션은 시스템의 모든 논리적 CPU(하이퍼스레드 코어/SMT 스레드 포함)가 ^[8]^{: ln 270}비지 상태라고 가정할 때 prio 또는 가상 마감일이 더 낮거나 더 늦은 모든 비지 스레드입니다.스케줄러는 priority가 낮거나 같은 정책 태스크(필요한 경우 가상 마감일보다 늦은 경우)를 사용하여 적절한 태스크를 검색하여 priority가 높은 정책을 사용할 수 없는 태스크를 사용하여 논리 CPU를 프리엠프션 및 회피해야 합니다.로컬 프리엠프션은 원격 유휴 NUMA ^[8]^{: ln 265–269}장치를 검색하는 것보다 높은 순위를 가집니다.

커널 매개 CPU 주파수 스케일링(CPU 주파수 거버너라고도 함)의 결과로 CPU가 느려질 때 태스크가 비자발적으로 프리엠프트되면 실시간정책으로 ^[8]^{: ln 2085}마크된 태스크 이외의 태스크는 특별히 "스틱"으로 마크됩니다.sticky로 표시된 것은 작업에 아직 사용되지 않은 시간이 있고 동일한 ^[8]^{: ln 233–243}CPU로 실행되는 작업이 제한되었음을 나타냅니다.CPU 스케일링 거버너가 CPU 스케일링을 저속으로 ^[8]^{: ln 2082–2107, 8840–8848}하면 작업은 스틱으로 표시됩니다.아이돌 상태였던 스틱 작업은 우연히 최대 Ghz 속도로 실행되거나 태스크가 실행된 ^[8]^{: ln 2082–2086, 239–242, 2068–2079}CPU와 동일한 CPU가 아닌 최적의 유휴 CPU에서 실행되도록 다시 예약됩니다.작업을 다른 곳으로 마이그레이션하는 것은 바람직하지 않지만 작업을 다른 CPU 또는 NUMA ^[8]^{: ln 228, 245}노드로 마이그레이션하는 데 따른 오버헤드가 증가하므로 작업을 유휴 상태로 두는 것이 좋습니다.이 스틱 기능은 Kolivas의 패치셋 4.8-ck1에 대응하는 BFS(v0.512)의 마지막 반복에서는 삭제되어 MuQSS에는 존재하지 않습니다.

시스템 도구

권한 있는 사용자는 schedtool 프로그램을^[8]^{: ln 326, 373} 사용하여 프로세스의 우선순위 정책을 변경할 수도 있고 프로그램 ^[8]^{: ln 336}자체에서 변경할 수도 있습니다.priority 클래스는 sched_setscheduler와 같은 syscall을 사용하여 코드레벨로 조작할 수 있습니다.^[14]schedtool은 ^[15]scheduler를 사용합니다.

벤치마크

동시대 ^[4]연구에서 저자는 Linux 커널 v3.6.2 및 여러 성능 기반 엔드포인트를 사용하여 BFS와 CFS를 비교했습니다.이 연구의 목적은 vanilla Linux 커널의 Complete Fair Scheduler(CFS)와 ck1 패치셋으로 패치된 대응하는 커널의 BFS를 평가하는 것이었습니다.7대의 다른 머신을 사용하여 차이가 존재하는지 여부와 성능 기반 메트릭을 사용하여 어느 정도 확장되는지 확인했습니다.논리 CPU의 범위는 1에서 16까지입니다.이러한 엔드 포인트는 BFS의 주요 설계 목표의 요소가 되지 않았습니다.결과는 고무적이었다.

BFS를 포함한 ck1 패치세트로 패치가 적용된 커널은 테스트된 ^[4]거의 모든 퍼포먼스 기반 벤치마크에서 CFS를 사용한 바닐라 커널보다 성능이 뛰어났습니다.더 큰 테스트 세트를 사용하여 더 많은 테스트를 수행할 수 있지만 평가된 7대의 소규모 테스트 세트에 따라 프로세스 큐잉의 증가, 효율성/속도 전체적으로 CPU 유형(모노, 듀얼, 쿼드, 하이퍼스레드 등), CPU 아키텍처(32비트 및 64비트), CPU 멀티시티(모노 또는 듀얼 소켓)와는 무관합니다.

게다가 인텔 Core 2 Duo 나 Core i7 등, 일반적인 워크스테이션이나 노트북 PC를 대표하는 「현대」의 CPU에서는, BFS 는, 모든 벤치마크에서 CFS 를 일관되게 웃돌았습니다.효율과 속도의 향상은 미미한 수준이었다.

도입

BFS는 다음 데스크톱 Linux 배포의 기본 스케줄러입니다.

또한 BFS는 Google의 Android 개발 ^[20]저장소의 실험 지점에 추가되었습니다.블라인드 테스트 결과 사용자 환경이 ^[21]개선되지 않아 Froyo 릴리즈에는 포함되지 않았습니다.

MuQSS

BFS는 MuQSS(공식적으로는 Multiple Queue Skiplist Scheduler)를 위해 폐지되었습니다.MuQSS는 같은 ^[22]^[23]개념의 구현으로 다시 작성되었습니다.

이론적인 설계와 효율

MuQSS는 양방향 스태틱어레이 8레벨 스킵리스트를 사용합니다.작업은 스태틱priority [queues](스케줄 정책 참조) 및 가상 ^[11]^{: ln 519, 525, 537, 588, 608}마감에 따라 정렬됩니다.캐시라인에 ^[11]^{: ln 523}어레이를 적합하도록 8이 선택되었습니다.작업 제거를 가속화하기 위해 이중으로 연결된 데이터 구조 설계를 선택했습니다.작업 삭제에는 William Pugh의 원래 설계와 비교하여 더블 스킵리스트의 O(1)만 필요합니다.O $O(n)$ ( $O(n)$ $)\$ $displaystyle$ O ( $n$ )최악의 $O(n)$ ^[11]^{: ln 458} $O(n)$ 입니다.

태스크 $O(\log n)$ 은 O $O(\log n)$ ( $){$ $displaystyle$ O ( \ $log$ n ) $O(\log n)$ ^[11]^{: ln 458}。실행 룩업의 다음 작업은 O $O(k)$ ( $O(k)$ $)\displaystyle$ O $(k$ 입니다. $여기$ 서 k는 CPU의 ^[11]^{: ln 589–590, 603, 5125}수입니다.실행에 대한 다음 업무는 O(1){O(1)\displaystyle}runqueue,[11], 여성당 ln 5124지만 스케줄러, 잠복기 또는 균형(는 불균일 기억 장치 접근 노드를 가로질러에 액세스 하려는 것에 동일한 불균일 기억 장치 접근 노드에서 CPU사용과 캐시 일관성을 극대화하기 위해)에, 다른 모든 runqueues들은 CPU간의 업무 공정성을 유지하는 것이 궁극적으로 O(k){\disp를 검토한다.laystyle O(k $O(k)$ ^[11]^{: ln 591–593, 497–501, 633–656} 처리할 수 있는 최대 작업 ^[11]^{: ln 521}수는 CPU당 런큐당 64k 작업입니다.일부 구성에서는 CPU당 하나의 runqueue를 사용하는 반면 이전 BFS에서는 모든 CPU에 대해 하나의 runqueue만 사용했습니다.

실시간 정책 priority가 우선이고 아이돌정책 priority가 마지막에 ^[11]^{: ln 2356-2358}오도록 작업은 건너뛰기 목록의 그라데이션으로 정렬됩니다.일반 priority 정책 및 유휴 priority 정책은 여전히 적절한 ^[11]^{: ln 2353}값을 사용하는 가상 기한에 따라 정렬됩니다.실시간 및 Isocronous 정책 태스크는 ^[11]^{: ln 2350–2351}적절한 값을 무시하고 FIFO 순서로 실행됩니다.동일한 키를 가진 새로운 태스크는 FIFO 순서로 배치됩니다.즉, 새로운 태스크는 목록의 끝에 배치되고(즉, 가장 위에 있는 노드), 0번째 레벨 또는 전면 아래쪽에 있는 태스크는 수직으로 가장 가까운 태스크와 헤드 ^[11]^{: ln 2351–2352, 590}노드에서 가장 먼 태스크보다 먼저 실행됩니다.삽입된 정렬에 사용되는 키는 정적^[11]^{: ln 2345, 2365,} 우선 순위 또는 가상 ^[11]^{: ln 2363}마감입니다.

사용자는 다중 코어 간에 런큐를 공유하거나 논리 ^[11]^{: ln 947–1006}CPU별로 런큐를 사용할 수 있습니다.런큐 설계를 공유하는 것은 ^[11]^{: ln 947–1006}스루풋의 트레이드오프로 지연을 줄이기 위한 것이었습니다.

MuQSS에 의해 도입된 새로운 동작은 타임라이스가 소진되어 작업이 ^[11]^{: ln 618-630, 3829–3851, 3854–3865, 5316}재스케줄 되었을 때 밀리초 미만의 정확도로 고해상도 타이머를 사용하는 것입니다.

「」를 참조해 주세요.

공평한 공유 스케줄링

레퍼런스

^ "-ck hacking: BFS version 0.512, linux-4.8-ck1, MuQSS for linux-4.8". ck-hack.blogspot.com. 2016-10-03. Retrieved 2016-11-10.
^ ^a ^b "Con Kolivas Introduces New BFS Scheduler » Linux Magazine". Linuxpromagazine.com. 2009-09-02. Retrieved 2013-10-30.
^ ^a ^b ^c "FAQs about BFS v0.330". Ck.kolivas.org. Retrieved 2013-10-30.
^ ^a ^b ^c "CPU Schedulers Compared" (PDF). Repo-ck.com. Retrieved 2013-10-30.
^ "Con Kolivas Returns, With a Desktop-Oriented Linux Scheduler". Slashdot. Retrieved 2013-10-30.
^ "Ingo Molnar Tests New BF Scheduler". Linux Magazine. 2009-09-08. Retrieved 2013-10-30.
^ "sched-bfs-001.patch". Con Kolivas. 2009-08-13. Retrieved 2020-10-09.
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q ^r ^s ^t ^u ^v ^w ^x ^y ^z ^aa ^ab ^ac ^ad ^ae ^af ^ag ^ah ^ai ^aj ^ak ^al ^am ^an ^ao ^ap ^aq ^ar ^as ^at ^au ^av ^aw ^ax ^ay ^az ^ba ^bb ^bc ^bd ^be ^bf ^bg ^bh "4.0-sched-bfs-462.patch". Con Kolivas. 2015-04-16. Retrieved 2019-01-29.
^ ^a ^b "The Rotating Staircase Deadline Scheduler". corbet. 2007-03-06. Retrieved 2019-01-30.
^ "sched-rsdl-0.26.patch". Con Kolivas. Archived from the original on 2011-07-26. Retrieved 2019-01-30.
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q ^r ^s ^t ^u ^v "0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch". Con Kolivas. 2018-08-27. Retrieved 2019-01-29.
^ ^a ^b "4.7-sched-bfs-480.patch". Con Kolivas. 2016-09-02. Retrieved 2020-10-09.
^ 이해하기 쉽도록 대체 공식이 제시되어 있습니다.모든 수학은 정수 수학으로 이루어지기 때문에 정밀도 손실은 클 것입니다.이것이 아마도 Kolivas가 128의 배수로서 128을 가장 큰 수치 중 하나로 나눗셈을 연기하여 나머지가 없는 이유일 것이다.
^ "The Linux Scheduler". Moshe Bar. 2000-04-01. Retrieved 2019-01-29.
^ "schedtool.c". freek. 2017-07-17. Retrieved 2019-01-30.
^ "Sabayon 7 Brings Linux Heaven". Ostatic.com. Retrieved 2013-10-30.
^ "2010 Edition is now available for download". PCLinuxOS. 2013-10-22. Retrieved 2013-10-30.
^ "Zenwalk 6.4 is ready ! - Releases - News". Zenwalk.org. Archived from the original on 2013-10-23. Retrieved 2013-10-30.
^ "About GalliumOS - GalliumOS Wiki". wiki.galliumos.org. Retrieved 2018-06-08.
^ [1 ] 2009년 9월 22일 Wayback Machine에서 아카이브 완료
^ "CyanogenMod 5 for the G1/ADP1". Lwn.net. Retrieved 2013-10-30.
^ "ck-hacking: linux-4.8-ck2, MuQSS version 0.114". ck-hack.blogspot.com. 2016-10-21. Retrieved 2016-11-10.
^ "Con Kolivas Announces First Major Release of MuQSS, Successor to BFS - Phoronix".

외부 링크

Brain Fuck 스케줄러 FAQ

[1] "-ck hacking: BFS version 0.512, linux-4.8-ck1, MuQSS for linux-4.8". ck-hack.blogspot.com. 2016-10-03. Retrieved 2016-11-10.

[Linux_Pro_Magazine_on_BFS-2] "Con Kolivas Introduces New BFS Scheduler » Linux Magazine". Linuxpromagazine.com. 2009-09-02. Retrieved 2013-10-30.

[bfsfaq-3] "FAQs about BFS v0.330". Ck.kolivas.org. Retrieved 2013-10-30.

[shedulers_compared-4] "CPU Schedulers Compared" (PDF). Repo-ck.com. Retrieved 2013-10-30.

[5] "Con Kolivas Returns, With a Desktop-Oriented Linux Scheduler". Slashdot. Retrieved 2013-10-30.

[6] "Ingo Molnar Tests New BF Scheduler". Linux Magazine. 2009-09-08. Retrieved 2013-10-30.

[sched-bfs-001.patch-7] "sched-bfs-001.patch". Con Kolivas. 2009-08-13. Retrieved 2020-10-09.

[4.0-sched-bfs-462.patch-8] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q ^r ^s ^t ^u ^v ^w ^x ^y ^z ^aa ^ab ^ac ^ad ^ae ^af ^ag ^ah ^ai ^aj ^ak ^al ^am ^an ^ao ^ap ^aq ^ar ^as ^at ^au ^av ^aw ^ax ^ay ^az ^ba ^bb ^bc ^bd ^be ^bf ^bg ^bh "4.0-sched-bfs-462.patch". Con Kolivas. 2015-04-16. Retrieved 2019-01-29.

[lwn-224865-9] "The Rotating Staircase Deadline Scheduler". corbet. 2007-03-06. Retrieved 2019-01-30.

[10] "sched-rsdl-0.26.patch". Con Kolivas. Archived from the original on 2011-07-26. Retrieved 2019-01-30.

[0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch-11] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q ^r ^s ^t ^u ^v "0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch". Con Kolivas. 2018-08-27. Retrieved 2019-01-29.

[4.7-sched-bfs-480.patch-12] "4.7-sched-bfs-480.patch". Con Kolivas. 2016-09-02. Retrieved 2020-10-09.

[13] 이해하기 쉽도록 대체 공식이 제시되어 있습니다.모든 수학은 정수 수학으로 이루어지기 때문에 정밀도 손실은 클 것입니다.이것이 아마도 Kolivas가 128의 배수로서 128을 가장 큰 수치 중 하나로 나눗셈을 연기하여 나머지가 없는 이유일 것이다.

[14] "The Linux Scheduler". Moshe Bar. 2000-04-01. Retrieved 2019-01-29.

[15] "schedtool.c". freek. 2017-07-17. Retrieved 2019-01-30.

[16] "Sabayon 7 Brings Linux Heaven". Ostatic.com. Retrieved 2013-10-30.

[17] "2010 Edition is now available for download". PCLinuxOS. 2013-10-22. Retrieved 2013-10-30.

[18] "Zenwalk 6.4 is ready ! - Releases - News". Zenwalk.org. Archived from the original on 2013-10-23. Retrieved 2013-10-30.

[19] "About GalliumOS - GalliumOS Wiki". wiki.galliumos.org. Retrieved 2018-06-08.

[20] [1 ] 2009년 9월 22일 Wayback Machine에서 아카이브 완료

[21] "CyanogenMod 5 for the G1/ADP1". Lwn.net. Retrieved 2013-10-30.

[bfsretired-22] "ck-hacking: linux-4.8-ck2, MuQSS version 0.114". ck-hack.blogspot.com. 2016-10-21. Retrieved 2016-11-10.

[phoronix-MuQSS-23] "Con Kolivas Announces First Major Release of MuQSS, Successor to BFS - Phoronix".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

Search

Brain Fuck 스케줄러

네임스페이스

더

목차