커널 번역(기사,문서)

[번역] scheduler/sched-deadline.txt

iamyooon 2018. 9. 8. 22:17

Deadline Task Scheduling

CONTENTS

0. 경고(WARNING)

1. 오버뷰(Overview)

2. 스케줄링 알고리즘(Scheduling algorithm)

2.1 핵심 알고리즘(Main algorithm)

2.2 대역폭 회수(Bandwidth reclaiming)

3. 실시간 태스크 스케줄링하기(Scheduling Real-Time Tasks)

3.1 정의(Definitions)

3.2 유니프로세서 시스템에서의 schedulability 분석하기(Schedulability Analysis for Uniprocessor Systems)

3.3 멀티프로세서 시스템에서의 schedulability 분석하기(Schedulability Analysis for Multiprocessor Systems)

3.4 SCHED_DEADLINE 파라미터의 관계(Relationship with SCHED_DEADLINE Parameters)

4. bandwidth 관리하기(Bandwidth management)

4.1 시스템 전역적인 설정(System-wide settings)

4.2 데드라인 태스크의 인터페이스(Task interface)

4.3 기본 동작(Default behavior)

4.4 sched_yield()의 동작(Behavior of sched_yield())

5. 데드라인 태스크의 어피니티(Tasks CPU affinity)

5.1 데드라인 태스크의 cpuset 설정하기(SCHED_DEADLINE and cpusets HOWTO)

6. 앞으로의 계획(Future plans)

A. 테스트 슈트(Test suite)

B. 간단한 예제(Minimal main())

0. WARNING

관련 설정을 조작하면 시스템 동작이 불안정해지거나 예측가능하지 않게 바뀔 수 있다.이 문서에서는 RT(그룹)스케줄링에 대해 루트 사용자가 자신이 무엇을 하는지를 알고 있다고 가정한다.

Fiddling with these settings can result in an unpredictable or even unstable system behavior. As for -rt (group) scheduling, it is assumed that root users know what they're doing.

1. Overview

sched_dl 스케줄링 클래스에 포함 된 SCHED_DEADLINE 정책은 기본적으로 EDF (Earliest Deadline First)스케줄링 알고리즘을 구현한 것이며, CBS(Constant Bandwidth Server)라고 불리는 태스크 각각이 다른 태스크의 동작을 격리할 수있는 메커니즘이 추가되었다.

The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is basically an implementation of the Earliest Deadline First (EDF) scheduling algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS) that makes it possible to isolate the behavior of tasks between each other.

2. Scheduling algorithm

2.1 Main algorithm

SCHED_DEADLINE은 태스크를 스케쥴링하기 위해 "runtime", "period", "deadline"이라는 세 가지 파라미터를 사용한다. SCHED_DEADLINE 태스크는 매 period때 마다 runtime만큼의 시간을 받는다, 할당받은 runtime은 period시작때부터 deadline안에 사용가능하다.

SCHED_DEADLINE uses three parameters, named "runtime", "period", and "deadline", to schedule tasks. A SCHED_DEADLINE task should receive "runtime" microseconds of execution time every "period" microseconds, and these "runtime" microseconds are available within "deadline" microseconds from the beginning of the period.

스케쥴러는 이 동작을 구현하기 위해 태스크가 깨어날 때마다 CBS [2,3] 알고리즘을 사용하여 guarantee와 일치하는 "scheduling deadline"을 계산한다. 그런 다음 태스크는 이러한 scheduling deadline에 맞게 EDF [1]를 사용하여 스케줄됩니다 (가장 빠른 데드라인을 갖고 있는 태스크가 실행되도록 선택된다.).

In order to implement this behavior, every time the task wakes up, the scheduler computes a "scheduling deadline" consistent with the guarantee (using the CBS[2,3] algorithm). Tasks are then scheduled using EDF[1] on these scheduling deadlines (the task with the earliest scheduling deadline is selected for execution).

적절한 "admission control"전략 ( "4. 대역폭 관리"절 참조)이 사용되었다면 (실제로 시스템에 과부하가 걸리면 보장할 수 없음) 태스크는 데드라인안의 runtime을 받는다.

Notice that the task actually receives "runtime" time units within "deadline" if a proper "admission control" strategy (see Section "4. Bandwidth management") is used (clearly, if the system is overloaded this guarantee cannot be respected).

요약하자면, CBS [2,3] 알고리즘은 각 태스크가 매 주기마다 실행될 수 있도록 스케줄링 데드라인을 태스크에 할당하여 EDF [1] 알고리즘이 다음에 실행할 태스크를 선택하는 동안 다른 태스크(대역폭 격리)간의 간섭을 방지한다. 가장 빠른 스케줄링 마감일은 다음에 실행될 예정이다. 이 기능 덕분에 "전통적인"실시간 태스크 모델 (3 절 참조)을 엄격하게 준수하지 않는 태스크도 새로운 정책을 효과적으로 사용할 수 있다.

Summing up, the CBS[2,3] algorithm assigns scheduling deadlines to tasks so that each task runs for at most its runtime every period, avoiding any interference between different tasks (bandwidth isolation), while the EDF[1] algorithm selects the task with the earliest scheduling deadline as the one to be executed next. Thanks to this feature, tasks that do not strictly comply with the "traditional" real-time task model (see Section 3) can effectively use the new policy.

보다 상세하게 보면, CBS 알고리즘은 스케줄링 데드라인을 다음과 같은 방식으로 태스크에 할당한다 :

In more details, the CBS algorithm assigns scheduling deadlines to tasks in the following way:

각 SCHED_DEADLINE 태스크는 런타임, 데드라인, 주기 파라미터를 사용해서 나타낸다.
Each SCHED_DEADLINE task is characterized by the "runtime", "deadline", and "period" parameters;
태스크의 상태는 스케줄링 데드라인 및 남은 런타임으로 나타낼 수 있다. 이 두 파라미터는 0으로 초기화된다.
The state of the task is described by a "scheduling deadline", and a "remaining runtime". These two parameters are initially set to 0;
SCHED_DEADLINE 태스크가 깨어 나면 (실행 준비가 됨), 스케줄러는 아래를 만족하는지 체크한다.
When a SCHED_DEADLINE task wakes up (becomes ready for execution), the scheduler checks if

remaining runtime runtime
---------------------------------- > --------
scheduling deadline - current time period

위 조건을 만족하거나, 아예 스케쥴링 데드라인이 지나버린 경우에는, 스케줄링 데드라인과 remaining runtime이 아래와 같이 다시 초기화된다.

then, if the scheduling deadline is smaller than the current time, or this condition is verified, the scheduling deadline and the remaining runtime are re-initialized as

스케쥴링 데드라인 = 현재 시간 + 최종 기한(scheduling deadline = current time + deadline )
나머지 런타임 = 런타임(remaining runtime = runtime)

그렇지 않으면 스케쥴링 데드라인과 남은 런타임은 변경되지 않는다.

otherwise, the scheduling deadline and the remaining runtime are left unchanged;

- SCHED_DEADLINE 태스크가 일정 시간 t동안 실행되면 나머지 런타임은 다음과 같이 감소한다. (기술적으로, 런타임은 매 틱마다 또는 태스크가 다른 태스크로 스위칭/선점 될 때마다 감소한다).

- When a SCHED_DEADLINE task executes for an amount of time t, its remaining runtime is decreased as (technically, the runtime is decreased at every tick, or when the task is descheduled / preempted);

나머지 런타임 = 나머지 런타임 - t(remaining runtime = remaining runtime - t)

나머지 런타임이 0보다 작거나 같으면 태스크가 쓰로틀링되었다(RT 스케쥴러 문헌에서는 depleted 라고도 함)고 하며 자신의 스케쥴링 데드라인때까지는 실행 할 수 없다.이 태스크의 런타임 재충전 시점(다음 항목 참조)은 스케쥴링 데드라인의 현재 값과 동일하게 설정된다.

When the remaining runtime becomes less or equal than 0, the task is said to be "throttled" (also known as "depleted" in real-time literature) and cannot be scheduled until its scheduling deadline. The "replenishment time" for this task (see next item) is set to be equal to the current value of the scheduling deadline;

현재 시간이 스로틀링된 태스크의 런타임 재충전 시점과 같으면 스케줄링 데드라인 및 남은 런타임은 다음과 같이 업데이트된다.(역주. 지금 재충전된다는 의미)

When the current time is equal to the replenishment time of a throttled task, the scheduling deadline and the remaining runtime are updated as

scheduling deadline = scheduling deadline + period
remaining runtime = remaining runtime + runtime

2.2 Bandwidth reclaiming

Bandwidth reclaiming for deadline tasks is based on the GRUB (Greedy Reclamation of Unused Bandwidth) algorithm [15, 16, 17] and it is enabled when flag SCHED_FLAG_RECLAIM is set.

The following diagram illustrates the state names for tasks handled by GRUB:

------------
(d) | Active |
------------->| |
| | Contending |
| ------------
| A |
---------- | |
| | | |
| Inactive | |(b) | (a)
| | | |
---------- | |
A | V
| ------------
| | Active |
--------------| Non |
(c) | Contending |
------------

A task can be in one of the following states:

ActiveContending: if it is ready for execution (or executing);

ActiveNonContending: if it just blocked and has not yet surpassed the 0-lag time;

Inactive: if it is blocked and has surpassed the 0-lag time.

State transitions:

(a) When a task blocks, it does not become immediately inactive since its bandwidth cannot be immediately reclaimed without breaking the real-time guarantees. It therefore enters a transitional state called ActiveNonContending. The scheduler arms the "inactive timer" to fire at the 0-lag time, when the task's bandwidth can be reclaimed without breaking the real-time guarantees.

The 0-lag time for a task entering the ActiveNonContending state is

computed as

(runtime * dl_period)
deadline - ---------------------
dl_runtime

where runtime is the remaining runtime, while dl_runtime and dl_period are the reservation parameters.

(b) If the task wakes up before the inactive timer fires, the task re-enters the ActiveContending state and the "inactive timer" is canceled. In addition, if the task wakes up on a different runqueue, then the task's utilization must be removed from the previous runqueue's active utilization and must be added to the new runqueue's active utilization.

In order to avoid races between a task waking up on a runqueue while the "inactive timer" is running on a different CPU, the "dl_non_contending" flag is used to indicate that a task is not on a runqueue but is active (so, the flag is set when the task blocks and is cleared when the "inactive timer" fires or when the task wakes up).

(c) When the "inactive timer" fires, the task enters the Inactive state and its utilization is removed from the runqueue's active utilization.

(d) When an inactive task wakes up, it enters the ActiveContending state and its utilization is added to the active utilization of the runqueue where it has been enqueued.

For each runqueue, the algorithm GRUB keeps track of two different bandwidths:

- Active bandwidth (running_bw): this is the sum of the bandwidths of all tasks in active state (i.e., ActiveContending or ActiveNonContending);

- Total bandwidth (this_bw): this is the sum of all tasks "belonging" to the runqueue, including the tasks in Inactive state.

The algorithm reclaims the bandwidth of the tasks in Inactive state. It does so by decrementing the runtime of the executing task Ti at a pace equal to

dq = -max{ Ui / Umax, (1 - Uinact - Uextra) } dt

where:

Ui is the bandwidth of task Ti;

Umax is the maximum reclaimable utilization (subjected to RT throttling limits);

Uinact is the (per runqueue) inactive utilization, computed as (this_bq - running_bw);

Uextra is the (per runqueue) extra reclaimable utilization (subjected to RT throttling limits).

Let's now see a trivial example of two deadline tasks with runtime equal to 4 and period equal to 8 (i.e., bandwidth equal to 0.5):

A Task T1

| |

|-------- |----

| | V

|---|---|---|---|---|---|---|---|--------->t

0 1 2 3 4 5 6 7 8

A Task T2

| |

| ------------------------|

| | V

|---|---|---|---|---|---|---|---|--------->t

0 1 2 3 4 5 6 7 8

A running_bw

1 ----------------- ------

| | |

0.5- -----------------

| |

|---|---|---|---|---|---|---|---|--------->t

0 1 2 3 4 5 6 7 8

- Time t = 0:

Both tasks are ready for execution and therefore in ActiveContending state. Suppose Task T1 is the first task to start execution. Since there are no inactive tasks, its runtime is decreased as dq = -1 dt.

- Time t = 2:

Suppose that task T1 blocks

Task T1 therefore enters the ActiveNonContending state. Since its remaining

runtime is equal to 2, its 0-lag time is equal to t = 4. Task T2 start execution, with runtime still decreased as dq = -1 dt since there are no inactive tasks.

- Time t = 4:

This is the 0-lag time for Task T1. Since it didn't woken up in the meantime, it enters the Inactive state. Its bandwidth is removed from running_bw.

Task T2 continues its execution. However, its runtime is now decreased as

dq = - 0.5 dt because Uinact = 0.5.

Task T2 therefore reclaims the bandwidth unused by Task T1.

- Time t = 8:

Task T1 wakes up. It enters the ActiveContending state again, and the running_bw is incremented.

3. RT 태스크 스케줄링하기(Scheduling Real-Time Tasks)

* BIG FAT WARNING ******************************************************

이 섹션에는 고전적인 데드라인 스케줄링 이론에 대한 (철저하지 않은) 요약과 SCHED_DEADLINE에 적용되는 방법이 포함되어 있다. 독자는 스케쥴링 정책을 어떻게 사용할 수 있는지에 관심이있는 경우 섹션 4로 건너 뛸 수 있다. 어쨌든, 여기서 다시 돌아와서 (시험에 대한 열망이 만족되면 : P) 모든 기술 세부 사항을 완전히 이해할 수 있도록 계속 읽는 것이 좋다.

This section contains a (not-thorough) summary on classical deadline scheduling theory, and how it applies to SCHED_DEADLINE. The reader can "safely" skip to Section 4 if only interested in seeing how the scheduling policy can be used. Anyway, we strongly recommend * to come back here and continue reading (once the urge for testing is satisfied :P) to be sure of fully understanding all technical details.

***********************************************************************

이 새로운 스케쥴링 규약을 활용할 수있는 태스크의 종류에는 제한이 없다. 비록 그것이 멀티미디어, 스트리밍, 제어어플리케이션와 같은 타이밍 행동에 대한 보증을 필요로하는 주기적인 또는 산발적인 RT 태스크에 특히 적합하다고 하다고 하더라도 말이다.

There are no limitations on what kind of task can exploit this new scheduling discipline, even if it must be said that it is particularly suited for periodic or sporadic real-time tasks that need guarantees on their timing behavior, e.g., multimedia, streaming, control applications, etc.

3.1 정의(Definitions)

일반적인 RT 태스크는 주기적 또는 산발적인 방식으로 computation phase(작업 인스턴스 또는 작업)의 반복으로 구성된다.

A typical real-time task is composed of a repetition of computation phases (task instances, or jobs) which are activated on a periodic or sporadic fashion.

각 작업 J_j (여기서 J_j는 태스크의 j 번째 작업임)는 도착 시간 r_j (작업이 시작되는 시간), 작업을 완료하는 데 필요한 계산 시간 c_j 및 작업의 abosolute 데드라인 d_j , 이는 작업이 완료되어야 하는 시간이다.

Each job J_j (where J_j is the j^th job of the task) is characterized by an arrival time r_j (the time when the job starts), an amount of computation time c_j needed to finish the job, and a job absolute deadline d_j, which is the time within which the job should be finished.

최대 실행 시간 max {c_j}는 작업에 대한 WCET (Worst Case Execution Time)라고 한다.

The maximum execution time max{c_j} is called "Worst Case Execution Time" (WCET) for the task.

RT 태스크는 r_ {j + 1} = r_j + P인 경우에 주기 P로 동작하거나 최소 상호 도착 시간 P로 산발적 일 수 있다. 마지막으로 d_j = r_j + D, 여기서 D는 태스크의 상대적인 데드라인이다. 요약하면 RT 태스크는 다음과 같이 설명 할 수 있다.

A real-time task can be periodic with period P if r_{j+1} = r_j + P, or sporadic with minimum inter-arrival time P is r_{j+1} >= r_j + P. Finally, d_j = r_j + D, where D is the task's relative deadline. Summing up, a real-time task can be described as

Task = (WCET, D, P)

RT 태스크의 CPU 사용량은 WCET와 그 주기(또는 최소 도착 시간) 간의 비율로 정의되며 태스크를 실행하는 데 필요한 CPU 시간의 비율을 나타낸다.

The utilization of a real-time task is defined as the ratio between its WCET and its period (or minimum inter-arrival time), and represents the fraction of CPU time needed to execute the task.

총 CPU 사용량 U = sum (WCET_i / P_i)이 M(CPU 수와 동일함)보다 큰 경우, 스케줄러는 모든 데드라인을 준수 할 수 없다.

If the total utilization U=sum(WCET_i/P_i) is larger than M (with M equal to the number of CPUs), then the scheduler is unable to respect all the deadlines.

전체 CPU 사용량은 시스템의 모든 RT 태스크에 대한 CPU 사용량 WCET_i / P_i의 합으로 정의된다. 다중 RT 태스크를 고려할 때 i 번째 태스크의 매개 변수는 "_i"접미사로 표시된다.

Note that total utilization is defined as the sum of the utilizations WCET_i/P_i over all the real-time tasks in the system. When considering multiple real-time tasks, the parameters of the i-th task are indicated with the "_i" suffix.

또한 총 CPU 사용량이 M보다 크면 RT 태스크 때문에 non-RT 태스크가 실행되지 못할 리스크가 있다. 대신 총 CPU 사용량이 M보다 작으면 non-RT 태스크가 실행할 수 있고 시스템이 모든 데드라인을 준수 할 수 있다.

Moreover, if the total utilization is larger than M, then we risk starving non- real-time tasks by real-time tasks. If, instead, the total utilization is smaller than M, then non real-time tasks will not be starved and the system might be able to respect all the deadlines.

사실 이 경우 tardiness에 대한 상한을 제공 할 수 있다 (0과 작업의 완료 시간과 absoulte 데드라인과 한의 차이 사이의 최대 값으로 정의 됨).

As a matter of fact, in this case it is possible to provide an upper bound for tardiness (defined as the maximum between 0 and the difference between the finishing time of a job and its absolute deadline).

보다 정확하게, 글로벌 EDF 스케줄러를 사용하여 각 작업의 최대 tardless가 ((M-1) · WCET_max-WCET_min) / (M-2) · U_max) + WCET_max보다 작거나 같음을 증명할 수 있다. 여기서 WCET_max = 최대 {WCET_i}는 최대 WCET, WCET_min = 최소 {WCET_i}는 최소 WCET, U_max = 최대 {WCET_i / P_i}는 최대 활용도 [12]이다.

More precisely, it can be proven that using a global EDF scheduler the maximum tardiness of each task is smaller or equal than ((M − 1) · WCET_max − WCET_min)/(M − (M − 2) · U_max) + WCET_max where WCET_max = max{WCET_i} is the maximum WCET, WCET_min=min{WCET_i} is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum utilization[12].

3.2 유니프로세서 시스템에서의 schedulability 분석하기(Schedulability Analysis for Uniprocessor Systems)

M = 1 (단일 프로세서 시스템) 또는 분할 스케줄링의 경우 (각 RT 태스크가 하나의 CPU에만 정적으로 할당 됨) 모든 데드라인을 준수하는지 formally 확인할 수 있다.

If M=1 (uniprocessor system), or in case of partitioned scheduling (each real-time task is statically assigned to one and only one CPU), it is possible to formally check if all the deadlines are respected.

모든 태스크가 D_i = P_i 인 경우에 EDF는 해당 CPU에서 실행되는 태스크의 총 사용률이 1보다 작거나 같은다면 CPU에서 실행되는 모든 태스크의 데드라인을 모두 준수 할 수 있다.

If D_i = P_i for all tasks, then EDF is able to respect all the deadlines of all the tasks executing on a CPU if and only if the total utilization of the tasks running on such a CPU is smaller or equal than 1.

만약 어떤 태스크가 D_i != P_i라면, 태스크의 density는 WCET_i/min{D_i, P_o}로 정의할 수 있고, CPU에서 동작중인 태스크들의 density의 합이 1보다 작거나 같다면 EDF는 CPU에서 동작중인 모든 태스크의 데드라인을 respect할 수 있다.

If D_i != P_i for some task, then it is possible to define the density of a task as WCET_i/min{D_i,P_i}, and EDF is able to respect all the deadlines of all the tasks running on a CPU if the sum of the densities of the tasks running on such a CPU is smaller or equal than 1:

sum(WCET_i / min{D_i, P_i}) <= 1

이 조건은 충분조건이지 필요조건은 아님을 알아 두는 것이 중요하다. 조건은 만족하지 않지만 스케줄링 가능한 태스크셋이 있다. 예를 들어 Task_1 = (50ms, 50ms, 100ms) , Task_2 = (10ms, 100ms, 100ms)로 구성된 {Task_1, Task_2} 태스크 세트를 생각해보자.

It is important to notice that this condition is only sufficient, and not necessary: there are task sets that are schedulable, but do not respect the condition. For example, consider the task set {Task_1,Task_2} composed by Task_1=(50ms,50ms,100ms) and Task_2=(10ms,100ms,100ms).

EDF는 데드 라인을 놓치지 않고 두 개의 태스크를 명확하게 스케줄 할 수 있다(Task_1은 release되는 즉시 스케줄되고 태스크의 데드라인을 고려한 시간에 끝나고 Task_2는 Task_1 직후에 스케줄되므로 응답 시간은 50/min{50,100}+10/min{100,100} = 50 / 50 + 10 / 100 = 1.1 이더라도 50ms + 10ms = 60ms 보다 클 수 없음)

EDF is clearly able to schedule the two tasks without missing any deadline (Task_1 is scheduled as soon as it is released, and finishes just in time to respect its deadline; Task_2 is scheduled immediately after Task_1, hence its response time cannot be larger than 50ms + 10ms = 60ms) even if 50 / min{50,100} + 10 / min{100, 100} = 50 / 50 + 10 / 100 = 1.1

물론 D_i! = P_i (충분조건과 필요조건 모두를 체크)인 태스크들의 확실한 스케줄 가능성을 테스트하는 것은 가능하지만, 총 사용률이나 density를 상수와 비교하는것으로는 불가능하다.

Of course it is possible to test the exact schedulability of tasks with D_i != P_i (checking a condition that is both sufficient and necessary), but this cannot be done by comparing the total utilization or density with a constant.

대신 소위 "processor demand"접근 방식을 사용하여 모든 태스크들이 크기 t의 time interval에서의 데드라인을 만족하기 위해 필요로 하는 총 CPU 시간의 양 h(t)를 계산할 수 있다. 그리고 계산된 시간은 interval 크기 t와 비교할 수 있다.

Instead, the so called "processor demand" approach can be used, computing the total amount of CPU time h(t) needed by all the tasks to respect all of their deadlines in a time interval of size t, and comparing such a time with the interval size t.

만약 h(t)가 가능한 모든 값의 t보다 작은 경우(that is, the amount of time needed by the tasks in a time interval of size t is smaller than the size of the interval) EDF는 모든 태스크의 데드라인을 준수하도록 태스크를 스케줄링할 수 있다.

If h(t) is smaller than t (that is, the amount of time needed by the tasks in a time interval of size t is smaller than the size of the interval) for all the possible values of t, then EDF is able to schedule the tasks respecting all of their deadlines.

가능한 모든 t 값에 대해 이 검사를 수행하는 것은 불가능하기 때문에 0과 최대 값 L 사이의 t 값에 대한 검사를 수행하는 것으로 충분하다는 것을[4,5,6] 입증했다. 인용 된 논문에는 수학적 세부 사항 및 h (t)와 L을 계산하는 방법을 설명한다.

Since performing this check for all possible values of t is impossible, it has been proven

[4,5,6] that it is sufficient to perform the test for values of t between 0 and a maximum value L. The cited papers contain all of the mathematical details and explain how to compute h(t) and L.

어쨌든 이러한 종류의 분석은 너무 복잡하고 온라인으로 수행하는 데 너무 많은 시간이 소요된다. 따라서 4 절에서 설명한 것처럼 Linux는 작업의 CPU 사용률에 기반한 승인 테스트를 사용한다.

In any case, this kind of analysis is too complex as well as too time-consuming to be performed on-line. Hence, as explained in Section 4 Linux uses an admission test based on the tasks' utilizations.

3.3 멀티프로세서 시스템에서의 schedulability 분석하기(Schedulability Analysis for Multiprocessor Systems)

전역 EDF 스케줄링 (분할되지 않은 시스템)을 갖춘 다중 프로세서 시스템에서 스케줄링 가능성에 대한 충분한 테스트는 CPU 사용량 또는 densities를 기반으로 할 수 없다. D_i = P_i 일지라도 1보다 약간 큰 CPU 사용량을 가진 태스크 세트는 CPU 개수와 상관없이 데드라인을 놓칠 수 있다.

On multiprocessor systems with global EDF scheduling (non partitioned systems), a sufficient test for schedulability can not be based on the utilizations or densities: it can be shown that even if D_i = P_i task sets with utilizations slightly larger than 1 can miss deadlines regardless of the number of CPUs.

M개의 CPU가 있는 시스템에서 P와 같은 period, 데드라인, WCET를 가진 첫번째 태스크 Task_1=(P,P,P)를 포함한 M+1개의 태스크세트가 있는 상황을 고려해보자. 나머지 M 개의 태스크 Task_i = (e, P-1, P-1)은 ARBITRARILY 작은 WCET(여기서는 "e"로 표시)를 가지고 첫 번째 태스크보다 작은 period를 갖는다.

Consider a set {Task_1,...Task_{M+1}} of M+1 tasks on a system with M CPUs, with the first task Task_1=(P,P,P) having period, relative deadline and WCET equal to P. The remaining M tasks Task_i=(e,P-1,P-1) have an arbitrarily small worst case execution time (indicated as "e" here) and a period smaller than the one of the first task.

따라서 모든 태스크가 같은 시간 t에 활성화되면 글로벌 EDF는 이러한 M 태스크들을 먼저 스케줄링한다. (절대적인 데드라인이 t + P - 1이기 때문에 , hence they are smaller than the absolute deadline of Task_1, which is t + P ).

Hence, if all the tasks activate at the same time t, global EDF schedules these M tasks first (because their absolute deadlines are equal to t + P - 1, hence they are smaller than the absolute deadline of Task_1, which is t + P).

결과적으로, Task_1은 t + e 시간에만 스케줄 될 수 있고 t + e + P 시간에 절대 데드라인 이후에 종료된다. 태스크 세트의 총 CPU 사용량은 U = M · e / (P-1) + P / P = M · e / (P-1) + 1이며, e의 값이 작으면 1에 가깝게 될 수 있다. 이것은 "Dhall의 효과"[7]로 알려져 있다. 참고 : Dhall의 원본 논문의 예제는 여기에서 약간 단순화되었다 (예 : Dhall은 lim_ {e -> 0} U를 보다 정확하게 계산했다).

As a result, Task_1 can be scheduled only at time t + e, and will finish at time t + e + P, after its absolute deadline. The total utilization of the task set is U = M · e / (P - 1) + P / P = M · e / (P - 1) + 1, and for small values of e this can become very close to 1. This is known as "Dhall's effect"[7]. Note: the example in the original paper by Dhall has been slightly simplified here (for example, Dhall more correctly computed lim_{e->0}U).

전역 EDF에 대한보다 복잡한 스케줄 가능성 테스트는 실시간 문헌 [8,9]에서 만들어졌지만 총 CPU 사용률 (또는 밀도)과 고정 상수 간의 간단한 비교를 기반으로 하지는 않았다. 모든 작업에 D_i = P_i가 있으면 충분한 스케줄 가능성 조건을 간단한 방법으로 표현할 수 있다.

More complex schedulability tests for global EDF have been developed in real-time literature[8,9], but they are not based on a simple comparison between total utilization (or density) and a fixed constant. If all tasks have D_i = P_i, a sufficient schedulability condition can be expressed in a simple way:

sum(WCET_i / P_i) <= M - (M - 1) · U_max

위 표현식은 U_max = max {WCET_i / P_i}일 때만 유효하다. [10]. U_max = 1 일 때 M - (M - 1) * U_max는 M - M + 1 = 1이되며 이 스케줄 가능성 조건은 Dhall의 효과를 확인한다. 멀티 프로세서 실시간 스케줄링을 위한 스케줄 가능성 테스트에 관한 문헌에 대한 보다 완벽한 조사는 [11]에서 찾을 수 있다.

where U_max = max{WCET_i / P_i}[10]. Notice that for U_max = 1, M - (M - 1) · U_max becomes M - M + 1 = 1 and this schedulability condition just confirms the Dhall's effect. A more complete survey of the literature about schedulability tests for multi-processor real-time scheduling can be found in [11].

알 수 있듯이 총 사용량이 M보다 작다고 해서 글로벌 EDF가 데드라인을 놓치지 않고 작업을 스케줄링한다는 보장은 없다. (즉, 글로벌 EDF는 최적의 스케줄링 알고리즘이 아니다).

As seen, enforcing that the total utilization is smaller than M does not guarantee that global EDF schedules the tasks without missing any deadline (in other words, global EDF is not an optimal scheduling algorithm).

그러나 M보다 작은 전체 활용도는 non-RT 태스크가 굶지 않고 RT 태스크의 지각이 상한선임을 보장하기에 충분하다. RT 태스크에 의해 발생하는 maximum tardiness에 대한 different bounds가 다양한 논문에서 개발되었지만 [13,14], SCHED_DEADLINE에서 중요한 이론적인 결과는 총 사용률이 M보다 작거나 같으면 태스크의 응답시간이 제한된다는 것이다.

However, a total utilization smaller than M is enough to guarantee that non real-time tasks are not starved and that the tardiness of real-time tasks has an Upper bound [12] (as previously noted). Different bounds on the maximum tardiness experienced by real-time tasks have been developed in various papers[13,14], but the theoretical result that is important for SCHED_DEADLINE is that if the total utilization is smaller or equal than M then the response times of the tasks are limited.

3.4 SCHED_DEADLINE 파라미터와의 관계(Relationship with SCHED_DEADLINE Parameters)

마지막으로 섹션 2 에 설명 된 SCHED_DEADLINE의 스케줄링 파라미터(런타임, 데드라인 및 period)와 이 절에 설명된 RT 태스크의 파라미터(WCET, D, P) 간의 관계를 이해하는 것이 중요하다. 태스크의 시간 제한은 위에서 설명한 절대 데드라인 d_j = r_j + D로 표현되는 반면 SCHED_DEADLINE은 스케줄링 데드라인 (2 절 참조)에 따라 태스크를 스케줄한다.

Finally, it is important to understand the relationship between the SCHED_DEADLINE scheduling parameters described in Section 2 (runtime, deadline and period) and the real-time task parameters (WCET, D, P) described in this section. Note that the tasks' temporal constraints are represented by its absolute deadlines d_j = r_j + D described above, while SCHED_DEADLINE schedules the tasks according to scheduling deadlines (see Section 2).

SCHED_DEADLINE을 사용하여 RT 태스크를 스케줄링하면 모든 태스크의 스케줄링 데드라인을 준수하도록 할 수 있다. 이를 수행하려면 다음을 설정하여 태스크를 스케줄링해야 한다.

If an admission test is used to guarantee that the scheduling deadlines are respected, then SCHED_DEADLINE can be used to schedule real-time tasks guaranteeing that all the jobs' deadlines of a task are respected. In order to do this, a task must be scheduled by setting:

runtime >= WCET
deadline = D
period <= P

다시 말해, 런타임 >= WCET 이고 period <= P이면 스케줄링 데드라인과 절대 데드라인(d_j)이 일치하므로 적절한 승인 제어가 이 작업에 대한 작업의 절대 period을 준수 할 수 있다. (이것은 "hard schedulability property" 라고 부르며 [2]의 보조 정리 1의 확장이다). runtime> deadline 인 경우 승인 제어는 임시 작업을 repect할 수 없으므로이 작업을 거부한다.

IOW, if runtime >= WCET and if period is <= P, then the scheduling deadlines and the absolute deadlines (d_j) coincide, so a proper admission control allows to respect the jobs' absolute deadlines for this task (this is what is called "hard schedulability property" and is an extension of Lemma 1 of [2]). Notice that if runtime > deadline the admission control will surely reject this task, as it is not possible to respect its temporal constraints.

References:

1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram-ming in a hard-real-time environment. Journal of the Association for Computing Machinery, 20(1), 1973.
2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf
3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab Technical Report. http://disi.unitn.it/~abeni/tr-98-01.pdf
4 - J. Y. Leung and M.L. Merril. A Note on Preemptive Scheduling of Periodic, Real-Time Tasks. Information Processing Letters, vol. 11, no. 3, pp. 115-118, 1980.
5 - S. K. Baruah, A. K. Mok and L. E. Rosier. Preemptively Scheduling Hard-Real-Time Sporadic Tasks on One Processor. Proceedings of the 11th IEEE Real-time Systems Symposium, 1990.
6 - S. K. Baruah, L. E. Rosier and R. R. Howell. Algorithms and Complexity Concerning the Preemptive Scheduling of Periodic Real-Time tasks on One Processor. Real-Time Systems Journal, vol. 4, no. 2, pp 301-324, 1990.
7 - S. J. Dhall and C. L. Liu. On a real-time scheduling problem. Operations research, vol. 26, no. 1, pp 127-140, 1978.
8 - T. Baker. Multiprocessor EDF and Deadline Monotonic Schedulability Analysis. Proceedings of the 24th IEEE Real-Time Systems Symposium, 2003.
9 - T. Baker. An Analysis of EDF Schedulability on a Multiprocessor. IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 8, pp 760-768, 2005.
10 - J. Goossens, S. Funk and S. Baruah, Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors. Real-Time Systems Journal, vol. 25, no. 2–3, pp. 187–205, 2003.
11 - R. Davis and A. Burns. A Survey of Hard Real-Time Scheduling for Multiprocessor Systems. ACM Computing Surveys, vol. 43, no. 4, 2011. http://www-users.cs.york.ac.uk/~robdavis/papers/MPSurveyv5.0.pdf
12 - U. C. Devi and J. H. Anderson. Tardiness Bounds under Global EDF Scheduling on a Multiprocessor. Real-Time Systems Journal, vol. 32, no. 2, pp 133-189, 2008.
13 - P. Valente and G. Lipari. An Upper Bound to the Lateness of Soft Real-Time Tasks Scheduled by EDF on Multiprocessors. Proceedings of the 26th IEEE Real-Time Systems Symposium, 2005.
14 - J. Erickson, U. Devi and S. Baruah. Improved tardiness bounds for Global EDF. Proceedings of the 22nd Euromicro Conference on Real-Time Systems, 2010.
15 - G. Lipari, S. Baruah, Greedy reclamation of unused bandwidth in constant-bandwidth servers, 12th IEEE Euromicro Conference on Real-Time Systems, 2000.
16 - L. Abeni, J. Lelli, C. Scordino, L. Palopoli, Greedy CPU reclaiming for SCHED DEADLINE. In Proceedings of the Real-Time Linux Workshop (RTLWS), Dusseldorf, Germany, 2014.
17 - L. Abeni, G. Lipari, A. Parri, Y. Sun, Multicore CPU reclaiming: parallel or sequential?. In Proceedings of the 31st Annual ACM Symposium on Applied Computing, 2016.

4. 대역폭 관리하기(Bandwidth management)

앞에서 언급했듯이, deadline 스케줄링이 효과적이고 유용하기 위해서는 (즉, "deadline"안에서 "runtime"을 제공하는게 가능하게 하기 위해) , 통제하에 여러 태스크에게 사용 가능한 CPU 시간의 할당을 가능하게 할 방법을 갖는 것이 중요하다. 이 방법은 보통 "admission control" 이라고 하며, admission control이 수행되지 않으면, 데드라인 태스크의 실행을 보장할 수 없다.

As previously mentioned, in order for -deadline scheduling to be effective and useful (that is, to be able to provide "runtime" time units within "deadline"), it is important to have some method to keep the allocation of the available fractions of CPU time to the various tasks under control. This is usually called "admission control" and if it is not performed, then no guarantee can be given on the actual scheduling of the -deadline tasks.

3 절에서 이미 언급했듯이, 실시간 태스크 세트를 올바르게 스케줄링하는 데 필요한 조건은 총 CPU사용률이 M(cpu 갯수)보다 작아야한다는 것이다. 데드라인 태스크에 대해 이야기 할 때, 모든 데드라인 태스크의 runtime/period의 비율이 M보다 작을 것을 요구한다. runtime/period 비율은 "기존" RT 태스크의 사용률과 동일하며 "대역폭"이라고도 한다. (예를 들어 cpu가 2개일 경우 period가 1s일 때 runtime은 2s보다 작아야 한다는것이다. 2/1 = 2 <= 2(M))

As already stated in Section 3, a necessary condition to be respected to correctly schedule a set of real-time tasks is that the total utilization is smaller than M. When talking about -deadline tasks, this requires that the sum of the ratio between runtime and period for all tasks is smaller than M. Notice that the ratio runtime/period is equivalent to the utilization of a "traditional" real-time task, and is also often referred to as "bandwidth".

데드라인 태스크에 할당할 수 있는 CPU 대역폭을 제어하는 데 사용되는 인터페이스는 RT 태스크 그룹 스케쥴링에서 이미 사용되는 것과 비슷하다(일명 RT 스로틀링이라고 부른다. Documentation/scheduler/sched-rt-group.txt 참조) 인터페이스는 procfs에 있는 read/write 가능한 제어 파일(시스템 전체 설정의 경우에만)을 기반으로 한다. 태스크 그룹 레벨에서 SCHED_DEADLINE 대역폭을 관리하는 방법을 파악하려면 더 많은 논의가 필요하기 때문에 cgroupfs를 통해 제어되는 그룹 별 설정은 여전히 데드라인 태스크에게는 정의되어 있지 않다.

The interface used to control the CPU bandwidth that can be allocated to -deadline tasks is similar to the one already used for -rt tasks with real-time group scheduling (a.k.a. RT-throttling - see Documentation/scheduler/sched-rt-group.txt), and is based on readable/writable control files located in procfs (for system wide settings). Notice that per-group settings (controlled through cgroupfs) are still not defined for -deadline tasks, because more discussion is needed in order to figure out how we want to manage SCHED_DEADLINE bandwidth at the task group level.

데드라인의 대역폭 관리와 RT 스로틀링의 가장 큰 차이점은 - 데드 라인 태스크에는 자신만의 대역폭을 가지고 있다는 것(RT는 없음) 이다. 따라서 원하는 대역폭을 강제로 적용하기 위한 고차원의 쓰로틀링 메카니즘이 필요없다는 것이다. 다른 말로, 이 말은 인터페이스 매개 변수는 admission control 때(예를 들어 사용자가 sched_setattr ()을 호출 할 때)만 사용된다. 스케쥴링은 실제 태스크에 설정된 파라미터를 고려해서 수행된다. 따라서 CPU 대역폭은 태스크들의 필요를 반영해서 SCHED_DEADLINE 태스크에게 할당된다. 따라서 이 간단한 인터페이스를 사용하여 데드라인 태스크의 총 사용량을 제한 할 수 있다.(즉, 모든 데드라인 태스크의 runtime/period비율의 합 < global_dl_utilization_cap)

A main difference between deadline bandwidth management and RT-throttling is that -deadline tasks have bandwidth on their own (while -rt ones don't!), and thus we don't need a higher level throttling mechanism to enforce the desired bandwidth. In other words, this means that interface parameters are only used at admission control time (i.e., when the user calls sched_setattr()). Scheduling is then performed considering actual tasks' parameters, so that CPU bandwidth is allocated to SCHED_DEADLINE tasks

respecting their needs in terms of granularity. Therefore, using this simple interface we can put a cap on total utilization of -deadline tasks (i.e., \Sum (runtime_i / period_i) < global_dl_utilization_cap).

4.1 시스템 전역적인 설정(System wide settings)

시스템 전역적인 설정은 proc 파일시스템 기반으로 구성되어 있다.

The system wide settings are configured under the /proc virtual file system.

지금은 rt태스크가 사용하던 kernel knob 이 deadline 태스크의 admission contrl에 사용되고 있고 deadline 태스크가 사용하는 runtime은 rt 태스크의 runtime에 account된다. 우리는 이것이 전적으로 바람직하지 않다는 것을 알고 있다. 그러나 지금은 작은 인터페이스를 가지고 나중에 쉽게 변경할 수 있는게 좋다. 이상적인 상황(5 참조)은 -deadline 서버에서 -rt 태스크를 실행하는 것이다. 이 경우 rt태스크의 대역폭은 dl_bw의 바로 아래의 하위 집합이다.

For now the -rt knobs are used for -deadline admission control and the -deadline runtime is accounted against the -rt runtime. We realize that this isn't entirely desirable; however, it is better to have a small interface for now, and be able to change it easily later. The ideal situation (see 5.) is to run -rt tasks from a -deadline server; in which case the -rt bandwidth is a direct subset of dl_bw.

즉, M개의 CPU로 구성된 root_domain의 경우 태스크의 대역폭 합이 아래와 같을때 데드 라인 태스크는 생성가능하다.

This means that, for a root_domain comprising M CPUs, -deadline tasks can be created while the sum of their bandwidths stays below:

M * (sched_rt_runtime_us / sched_rt_period_us)

또한 대역폭 관리 로직을 비활성화하는 것도 가능하다, 그리고 임의의 수준을 넘을정도까지의 대역폭 초과도 가능하다. 이것은 /proc/sys/kernel/sched_rt_runtime_us에 -1을 쓰면 된다.

It is also possible to disable this bandwidth management logic, and be thus free of oversubscribing the system up to any arbitrary level. This is done by writing -1 in /proc/sys/kernel/sched_rt_runtime_us.

4.2 Task interface

각 인스턴스에서 주어진 크기의 런타임을 실행하는 주기적/비주기적 태스크를 설정하고 timing constraints needs의 긴급함에 따라서 스케쥴링은 일반적으로 아래의 방법으로 한다.

Specifying a periodic/sporadic task that executes for a given amount of runtime at each instance, and that is scheduled according to the urgency of its own timing constraints needs, in general, a way of declaring:

a (최대 / 표준) 인스턴스 실행 시간.(a (maximum/typical) instance execution time,)
연속되는 인스턴스 간의 최소 간격(a minimum interval between consecutive instances,)
각 인스턴스를 완료해야하는 시간 제약 조건.(a time constraint by which each instance must be completed.)

따라서:

Therefore:

* 모든 필수 필드를 포함하는 새로운 구조체 sched_attr이 제공된다.

a new struct sched_attr, containing all the necessary fields is provided;

* sched_setattr(), sched_getattr()과 같은 새로운 스케줄 관련 시스템콜이 구현된다.

the new scheduling related syscalls that manipulate it, i.e., sched_setattr() and sched_getattr() are implemented.

디버깅을 위해, SCHE_DEADLINE 태스크의 absolute deadline과 leftover runtime은 /proc/<pid>/sched(entries dl.runtime and dl.deadline, both values in ns).에서 확인할 수 있다. 이 값을 얻기 위한 프로그래밍적 방법은 아래에서 다루고 있다.

For debugging purposes, the leftover runtime and absolute deadline of a SCHED_DEADLINE task can be retrieved through /proc/<pid>/sched (entries dl.runtime and dl.deadline, both values in ns). A programmatic way to retrieve these values from production code is under discussion.

4.3 기본 동작(Default behavior)

SCHED_DEADLINE 대역폭의 기본값은 950000으로 rt_runtime과 같다. 기본적으로 rt_period가 1000000이면 deadline 태스크가 최대 95%까지의 cpu시간을 쓸 수 있다는 것을 의미한다. 사용가능한 cpu시간은 각 root_domain을 구성하고 있는 cpu개수로 곱한 값이 된다.

The default value for SCHED_DEADLINE bandwidth is to have rt_runtime equal to 950000. With rt_period equal to 1000000, by default, it means that -deadline tasks can use at most 95%, multiplied by the number of CPUs that compose the root_domain, for each root_domain.

이것은 또한 non deadline 태스크는 최소한 5%의 CPU시간을 사용가능한 것을 의미한다. 그리고 dealine 태스크는 deadline 파라미터를 고려하고 worst-case delay를 보장하는 자신의 런타임을 받을것이다. 만약 "deadline"과 "period"가 같고 partitioned 스케쥴링을 구현하기 위해 cpuset 메카니즘이 사용된다(5 절 참조), 이런 간단한 설정은 deterministically하게 deadline 태스크가 자신의 런타임을 period안에 받는것을 보장할 수 있다.

This means that non -deadline tasks will receive at least 5% of the CPU time, and that -deadline tasks will receive their runtime with a guaranteed worst-case delay respect to the "deadline" parameter. If "deadline" = "period" and the cpuset mechanism is used to implement partitioned scheduling (see Section 5), then this simple setting of the bandwidth management is able to deterministically guarantee that -deadline tasks will receive their runtime in a period.

마지막으로, admission control을 위험에 빠뜨리지 않기 위해 deadline 태스크는 fork할 수 없다.

Finally, notice that in order not to jeopardize the admission control a -deadline task cannot fork.

4.4 sched_yield()의 동작(Behavior of sched_yield())

SCHED_DEADLINE 태스크가 sched_yield ()를 호출하면 runtime이 보충 될 다음 기간까지 나머지 runtime을 포기하고 즉시 throttling 된다.(dl_yielded 플래그가 설정되면 이 플래그는 태스크를 throttling 하고 sched_yield() 호출 후에 runtime을 충전하는 데 사용됨)

When a SCHED_DEADLINE task calls sched_yield(), it gives up its remaining runtime and is immediately throttled, until the next period, when its runtime will be replenished (a special flag dl_yielded is set and used to handle correctly throttling and runtime replenishment after a call to sched_yield()).

이런 sched_yield()의 동작은 태스크를 다음 period의 시작 부분에서 정확히 깨울 수 있도록 해준다. 또한 sched_yield()는 추후에 남은 runtime을 다른 데드라인 태스크에 의해 reclamation할 수 있게 해서 대역폭 회수 메카니즘에 유용하게 쓰일 수 있다.

This behavior of sched_yield() allows the task to wake-up exactly at the beginning of the next period. Also, this may be useful in the future with bandwidth reclaiming mechanisms, where sched_yield() will make the leftoever runtime available for reclamation by other SCHED_DEADLINE tasks.

5. 태스크의 cpu affinity(Tasks CPU affinity)

- 데드 라인 태스크은 생성 된 전체 root_domain보다 작은 affinity mask를 가질 수 없다. 그러나 cpuset을 사용한다면 affinity를 지정할 수는 있다.(Documentation/cgroup-v1/ cpusets.txt).

-deadline tasks cannot have an affinity mask smaller that the entire root_domain they are created on. However, affinities can be specified through the cpuset facility (Documentation/cgroup-v1/cpusets.txt).

5.1 SCHED_DEADLINE and cpusets HOWTO

간단하게 구성된 예제 (데드라인 태스크를 cpu0에서만 동작하도록 고정)는 다음과 같다 (rt-app는 -deadline 태스크을 만드는 데 사용된다).

An example of a simple configuration (pin a -deadline task to CPU0) follows (rt-app is used to create a -deadline task).

# mkdir /dev/cpuset
# mount -t cgroup -o cpuset cpuset /dev/cpuset
# cd /dev/cpuset
# mkdir cpu0
# echo 0 > cpu0/cpuset.cpus
# echo 0 > cpu0/cpuset.mems
# echo 1 > cpuset.cpu_exclusive
# echo 0 > cpuset.sched_load_balance
# echo 1 > cpu0/cpuset.cpu_exclusive
# echo 1 > cpu0/cpuset.mem_exclusive
# echo $$ > cpu0/tasks
# rt-app -t 100000:10000:d:0 -D5

이제부터는 태스크의 affinity를 지정하지 않아도 자동으로 설정된다.

(it is now actually superfluous to specify task affinity)

6. Future plans

여전히 보완이 필요한 부분은 아래와 같다.

Still missing:

현재 런타임과 absoulte deadline 값을 얻기 위한 프로그래밍 적인 방법

programmatic way to retrieve current runtime and absolute deadline

특히 상호 작용이 없는 태스크들 사이에서 bandwidth isolation을 유지할 기회에 관한 deadline 상속을 개선할 예정이다. 이것은 이론적 관점과 실용적인 관점 모두에서 연구되고 있으며, 우리는 시범적인 코드를 조만간 만들어낼 수 있을 것이다.

refinements to deadline inheritance, especially regarding the possibility of retaining bandwidth isolation among non-interacting tasks. This is being studied from both theoretical and practical points of view, and hopefully we should be able to produce some demonstrative code soon;

(c)group 기반의 대역폭 관리기능 또한 아마 계획중이다.

(c)group based bandwidth management, and maybe scheduling;

메커니즘의 unprivileged use을 허용하는 가장 좋은 방법, 루트가 아닌 사용자가 시스템을 "속이려는"것을 방지하는 방법은 무엇일까?

access control for non-root users (and related security concerns to address), which is the best way to allow unprivileged use of the mechanisms and how to prevent non-root users "cheat" the system?

이미 설명한 것처럼 이 태스크를 EDF 조절 패치 [https://lkml.org/lkml/2010/2/23/239]와 병합 할 계획도 있지만 병합의 예비 단계에 있다. 우리가 나아가야 할 방향을 결정하는 데 도움이 될 의견을 찾고 있다.

As already discussed, we are planning also to merge this work with the EDF throttling patches [https://lkml.org/lkml/2010/2/23/239] but we still are in the preliminary phases of the merge and we really seek feedback that would help us decide on the direction it should take.

Appendix A. 테스트 슈트(Test suite)

SCHED_DEADLINE 정책은 광범위한 Linux Scheduler validation suit의 일부인 두 어플리케이션을 사용하여 쉽게 테스트 할 수 있다. 이 suit는 아래 GitHub 저장소에서 사용할 수 있다.

The SCHED_DEADLINE policy can be easily tested using two applications that are part of a wider Linux Scheduler validation suite. The suite is available as a GitHub repository:

https://github.com/scheduler-tools

첫 번째 테스트 어플리케이션은 rt-app 이라고 하며 매개 변수를 명시해서 멀티 스레드를 시작하는 데 사용할 수 있다. rt-app는 SCHED_{OTHER, FIFO, RR, DEADLINE} 스케줄링 정책과 관련 매개 변수 (예 : niceness, 우선 순위, 런타임/ 데드라인/period)를 지원한다. rt-app는 특정 워크로드를 종합적으로 재현하고 (실제 사용 사례를 모방 한 것일 수도 있음) 스케줄러가 그러한 태스크 부하에서 어떻게 작동하는지 평가할 수 있는 유용한 도구이다. 이 방법으로 결과를 쉽게 재현 할 수 있다. rt-app는 아래에서 다운로드 할 수 있다.

The first testing application is called rt-app and can be used to start multiple threads with specific parameters. rt-app supports SCHED_{OTHER,FIFO,RR,DEADLINE} scheduling policies and their related parameters (e.g., niceness, priority, runtime/deadline/period). rt-app is a valuable tool, as it can be used to synthetically recreate certain workloads (maybe mimicking real use-cases) and evaluate how the scheduler behaves under such workloads. In this way, results are easily reproducible. rt-app is available at:

https://github.com/scheduler-tools/rt-app

스레드 매개 변수는 다음과 같이 명령 줄에서 지정할 수 있다.

Thread parameters can be specified from the command line, with something like this:

# rt-app -t 100000:10000:d -t 150000:20000:f:10 -D5

위의 명령문은 스레드 2개를 만든다. SCHED_DEADLINE에 의해 스케줄 된 첫 번째는 100ms마다 10ms 동안 실행된다. SCHED_FIFO 정책과 우선 순위 10으로 스케줄링되는 두 번째 스레드는 150ms마다 20ms 동안 실행된다. 테스트는 총 5 초 동안 실행된다.

The above creates 2 threads. The first one, scheduled by SCHED_DEADLINE, executes for 10ms every 100ms. The second one, scheduled at SCHED_FIFO priority 10, executes for 20ms every 150ms. The test will run for a total of 5 seconds.

좀 더 흥미롭게도, rt-app에 입력으로 json 파일을 아래와 같이 전달할 수 있다.

More interestingly, configurations can be described with a json file that can be passed as input to rt-app with something like this:

# rt-app my_config.json

두 번째 방법으로 지정할 수있는 파라미터는 커맨드라인 옵션의 수퍼셋이다. 자세한 내용은 rt-app 설명서를 참조하자. (<rt-app-sources> / doc / *. json).

The parameters that can be specified with the second method are a superset of the command line options. Please refer to rt-app documentation for more details (<rt-app-sources>/doc/*.json).

두 번째 테스트 어플리케이션은 schedtool-dl이라는 schedtool을 수정 한 것으로, 특정 PID/어플리케이션에 대한 SCHED_DEADLINE 파라미터를 설정하는 데 사용할 수 있다. schedtool-dl은 아래 경로를 통해 다운로드 할 수 있다.

The second testing application is a modification of schedtool, called schedtool-dl, which can be used to setup SCHED_DEADLINE parameters for a certain pid/application. schedtool-dl is available at:

https://github.com/scheduler-tools/schedtool-dl.git

사용법은 직관적이다:

The usage is straightforward:

# schedtool -E -t 10000000:100000000 -e ./my_cpuhog_app

이 명령문을 통해 my_cpuhog_app는 100ms마다 10ms의 SCHED_DEADLINE 예약 내에 실행된다 (파라미터는 마이크로 초로 표시됨). 또한 schedtool을 사용하여 이미 실행중인 어플리케이션에 대한 예약을 만들 수 있다 (pid를 알고있는 경우).

With this, my_cpuhog_app is put to run inside a SCHED_DEADLINE reservation of 10ms every 100ms (note that parameters are expressed in microseconds). You can also use schedtool to create a reservation for an already running application, given that you know its pid:

# schedtool -E -t 10000000:100000000 my_app_pid

Appendix B. Minimal main()

아래는 실시간 애플리케이션 개발자가 SCHED_DEADLINE 예약을 생성하는 방법을 보여주는 간단한 코드다.

We provide in what follows a simple (ugly) self-contained code snippet showing how SCHED_DEADLINE reservations can be created by a real-time application developer.

#define _GNU_SOURCE
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <linux/unistd.h>
#include <linux/kernel.h>
#include <linux/types.h>
#include <sys/syscall.h>
#include <pthread.h>

#define gettid() syscall(__NR_gettid)

#define SCHED_DEADLINE 6

/* XXX use the proper syscall numbers */
#ifdef __x86_64__
#define __NR_sched_setattr 314
#define __NR_sched_getattr 315
#endif

#ifdef __i386__

#define __NR_sched_setattr 351
#define __NR_sched_getattr 352
#endif

#ifdef __arm__
#define __NR_sched_setattr 380
#define __NR_sched_getattr 381
#endif

static volatile int done;

struct sched_attr {
__u32 size;

__u32 sched_policy;
__u64 sched_flags;

/* SCHED_NORMAL, SCHED_BATCH */
__s32 sched_nice;

/* SCHED_FIFO, SCHED_RR */
__u32 sched_priority;

/* SCHED_DEADLINE (nsec) */
__u64 sched_runtime;
__u64 sched_deadline;
__u64 sched_period;
};

int sched_setattr(pid_t pid, const struct sched_attr *attr, unsigned int flags)
{
return syscall(__NR_sched_setattr, pid, attr, flags);
}

int sched_getattr(pid_t pid, struct sched_attr *attr, unsigned int size, unsigned int flags)
{
return syscall(__NR_sched_getattr, pid, attr, size, flags);
}

void *run_deadline(void *data)
{
struct sched_attr attr;
int x = 0;
int ret;
unsigned int flags = 0;

printf("deadline thread started [%ld]\n", gettid());

attr.size = sizeof(attr);
attr.sched_flags = 0;
attr.sched_nice = 0;
attr.sched_priority = 0;

/* This creates a 10ms/30ms reservation */
attr.sched_policy = SCHED_DEADLINE;
attr.sched_runtime = 10 * 1000 * 1000;
attr.sched_period = attr.sched_deadline = 30 * 1000 * 1000;

ret = sched_setattr(0, &attr, flags);
if (ret < 0) {
done = 0;
perror("sched_setattr");
exit(-1);
}

while (!done) {
x++;
}

printf("deadline thread dies [%ld]\n", gettid());
return NULL;
}

int main (int argc, char **argv)
{
pthread_t thread;

printf("main thread [%ld]\n", gettid());
pthread_create(&thread, NULL, run_deadline, NULL);

sleep(10);
done = 1;

pthread_join(thread, NULL);
printf("main dies [%ld]\n", gettid());
return 0;
}

저작자표시 비영리 변경금지 (새창열림)