# Best Speed Fit EDF Scheduling for Performance Asymmetric Multiprocessors

Authors: Peng Wu; Minsoo Ryu
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

In order to improve the performance of a real-time system, asymmetric multiprocessors have been proposed. The benefits of improved system performance and reduced power consumption from such architectures cannot be fully exploited unless suitable task scheduling and task allocation approaches are implemented at the operating system level. Unfortunately, most of the previous research on scheduling algorithms for performance asymmetric multiprocessors is focused on task priority assignment. They simply assign the highest priority task to the fastest processor. In this paper, we propose BSF-EDF (best speed fit for earliest deadline first) for performance asymmetric multiprocessor scheduling. This approach chooses a suitable processor rather than the fastest one, when allocating tasks. With this proposed BSF-EDF scheduling, we also derive an effective schedulability test.


---

## Body

## 1. Introduction

Modern semiconductor technology adopts the use of multiple processors in their motherboard design because of the growing demand of performance and saving energy which cannot be handled by single processor systems. In this regard, performance asymmetric multiprocessors, where individual cores possess different performance, are believed to provide improved performance and low power consumption when compared to performance symmetric multiprocessors, where the cores are identical [1]. This is because such heterogeneous architecture allows the allocation of computing resources according to the needs of an application and better handling of dynamic workload requirements by exploiting speed of the fast cores and power efficiency of the slow cores available. One example of heterogeneous multiprocessor architectures is the ARM big.LITTLE architectures that combine slow and fast processing cores that possess identical instruction set but different execution speeds. The ARM big.LITTLE architectures are already used by Samsung in their Galaxy Note5 and S6 Edge.For embedded real-time systems, in addition to resource and power optimization, guaranteeing the deadlines of a real-time system is a critical requirement. Scheduling on such a performance asymmetric multicore platform is much more challenging than scheduling on identical multicore platform since the processing speed depends not only on the processor type, but also on the task executed. Thus, on heterogeneous multicore platforms, a decision that which type of processor will execute a given task over a period of time is also important.Liu and Layland proposed earliest deadline first (EDF) scheduling algorithm on real-time single processor first in 1973 [2]. It is proved to be an optimal algorithm on single processor. Baker demonstrated an efficiently computable schedulability test for EDF scheduling on an asymmetric multiprocessors platform [3]. However, most of the previous research on EDF scheduling algorithm and relative scheduling algorithms for performance asymmetric multiprocessors is focused on the task priority approach [4–8]. They simply assign the highest priority task to the fastest processor. Since processors have different processing speeds in performance asymmetric multiprocessors, we believe that task allocation to an appropriate processor is also an important issue to be considered.In the current research we focus on providing an improved scheduling algorithm based on EDF for handling real-time tasks for performance asymmetric multiprocessor systems. More specifically, we propose a new EDF scheduling algorithm, best speed fit EDF (BSF-EDF). For BSF-EDF, the priorities of the tasks are chosen according to the original EDF scheduling algorithm, whereas it differs in terms of task allocation to processors, such that in the former approach the highest priority task is assigned to a faster processor and in the latter approach the highest priority task is allocated to the appropriate idle processor. We also obtain a new schedulability test for the BSF-EDF on performance asymmetric multiprocessors.The rest of the paper is organized as follows. In Section2, we describe system model and background. Section 3 presents the BSF-EDF scheduling with an example. In Section 4, we describe the proposed schedulability test for the BSF-EDF scheduling algorithm.


## 2. System Model and Background

We consider anm-core performance asymmetric multiprocessor system and we use π to denote the set of m performance asymmetric processors. We use s
i to represent the processing speed of any processor P
i. For convenience we use 1 to represent the speed of the slowest processor, such that the speed of faster processors can be represented by a multiple of 1; for example, s
i
=
3. We also assume that the speeds of processors are specified in nondecreasing order: s
i
≤
s
i
+
1 for all i. Let S
i be the cumulative sum of processor speeds of the first i processors in a performance asymmetric multiprocessors platform π:(1)
S
i
=
∑
j
=
1
i
s
j
.Immediately, S
m denotes the cumulative sum of π.In this paper, we consider a sporadic task model. LetГ
=
{
τ
1
,
τ
2
,
τ
3
,
…
,
τ
n
} be a set of n sporadic tasks. A sporadic task τ
i is defined by a 3-tuple e
i
,
d
i
,
T
i, where e
i is the worst case execution time when it is executed in the lowest speed processor, d
i is the relative constrained deadline such that e
i
≤
d
i
≤
T
i, and T
i is the minimum interarrival time, which is also referred as period of the task. The minimum interarrival time T
i means that any two consecutive requests of τ
i are separated by at least T
i. We use τ
i
,
j to represent thejth job of task τ
i and A
i
,
j to denote the arrival time of τ
i
,
j. Note that a task can have different execution time based on different speeds of processors. Therefore, a job executing on thejth processor for a duration of t time can receive t
×
s
j units of execution.Now we introduce several further notions that we will use for schedulability analysis. Since processors have varying speeds, we use the slowest processor to measure the worst case execution timee
i of a task τ
i. The utilization u
i of a task τ
i is the ratio of the worst case execution time to its period, that is, e
i
/
T
i. The total utilization U
s
u
m
(
Γ
) and the largest task utilization u
m
a
x
(
Γ
) of a task set are defined as follows:(2)
U
s
u
m
Γ
=
∑
τ
i
∈
Γ
u
i
,
u
m
a
x
Γ
=
max
τ
i
∈
Γ
⁡
u
i
.The density δ
i of a task τ
i is defined to be the ratio of e
i
/
d
i, that is, ratio of the worst case execution time to the relative deadline. The maximum density δ
m
a
x
(
Γ
) of a task set Γ is defined as follows: (3)
δ
m
a
x
Γ
=
max
τ
i
∈
Γ
⁡
δ
i
.The concepts of processor demand bound function D
B
F
(
τ
i
,
Δ
t
) and processor load are used in the analysis of multiprocessor scheduling and are well-studied in detail in [9]. D
B
F
(
τ
i
,
Δ
t
) is used to represent an upper bound on the maximum cumulative processing time demand by jobs of τ
i that arrive in and also have deadline within any interval of length Δ
t. It has been shown that(4)
D
B
F
τ
i
,
Δ
t
≝
max
⁡
0
,
Δ
t
-
d
i
T
i
+
1
e
i
if
Δ
t
≥
d
i
e
i
if
Δ
t
<
d
i
. The processor load parameter is based on the DBF function which is the maximum value of the ratio of processor demand bound and length of the time interval Δ
t [10].(5)
L
O
A
D
Г
≝
max
Δ
t
>
0
⁡
∑
τ
i
∈
Г
D
B
F
τ
i
,
Δ
t
Δ
t
.


## 3. BSF-EDF Scheduling Algorithm for Performance Asymmetric Multiprocessor Platform

Our scheduling algorithm proposed in this paper is a priority driven scheduling algorithm, which means that the highest priority task always runs first. Moreover, we choose global multiprocessor scheduling policy. Global scheduling maintains a single system-wide queue of ready tasks, from which tasks are extracted at run-time, to be scheduled on the available computing resources. Global scheduling is more appropriate for open systems, as there is no need to run load balancing algorithms when the set of tasks changes. We also allow preemption of tasks in our proposed BSF-EDF scheduling algorithm and migration of tasks between different speed processors is also permitted.Now there are two crucial issues to be addressed, task priority assignment and task allocation to processors. For BSF-EDF scheduling we assign the priorities to tasks according to their absolute deadline, such that the task with earlier deadline has higher priority. In previous research work, individuals simply assign the highest priority task to the fastest idle processor. Contrary to this, we assign the highest priority task to the appropriate idle processor rather than the fastest idle one. The appropriate processor is the slowest speed processor which ensures that a task can be executed without missing its deadline. In other words, we choose the slowest speed idle processor whose speed is no less than the utilization of the task. If there does not exist such appropriate processor, we allocate the task to the slowest idle processor. We should reschedule all the tasks whenever a schedule event occurs. Schedule events include two cases, when (a) a running job is finished and (b) a new job has arrived. Specifically, we say that(
1
) no processor is idle while there is an active task, (
2
) a scheduled task always executes on the best speed fit processor, if there exists such a processor, and (
3
) higher priority task always runs first.Example 1.
Figure1 manifests a simple BSF-EDF scheduling example on a performance asymmetric multiprocessor platform. Consider a performance asymmetric multiprocessor platform π
=
{
1,2
} which has two processors and a task set Г
=
τ
1
(
4,4
,
4
)
,
τ
2
(
4,4
,
4
)
,
τ
3
(
6,6
,
6
). Initially, τ
1,1 has the highest priority, and P
1 is the appropriate idle processor, so we allocate it to P
1. The second priority job τ
2,1 is allocated to processor P
2. Job τ
2,1 finishes at time t
=
2; therefore, time t
=
2 is a schedule event time. All tasks should be rescheduled. τ
1,1 still has the highest priority; we allocate it to P
1, and we allocate second priority job τ
3,1 to P
2. τ
1,1 finishes its execution at time t
=
4, so a schedule event appears. Now τ
3,1 has the highest priority, so we allocate it to P
1, and we allocate job τ
1,2 to P
2. It is easy to see that all tasks will satisfy their deadline under BSF-EDF. The processors are used to their 100% utilization. As shown in the figure, t
=
{
2,4
,
6,8
,
10,12
} are schedule event points.Figure 1
Task schedule under BSF-EDF.


## 4. BSF-EDF Schedulability Analysis for Performance Asymmetric Multiprocessor Platform

With respect to a given platform, a given sporadic task set is said to be BSF-EDF schedulable if the schedule is able to meet all deadlines for every collection of jobs that may be generated by the task set. In this section, we derive a schedulability test for the BSF-EDF scheduling on performance asymmetric multiprocessors.We first obtain a necessary condition when a task misses its deadline for the BSF-EDF scheduling. By taking the contrapositive of the condition, we obtain a sufficient schedulability condition.Suppose that a jobτ
i
,
j of task τ
i is the one to first miss its deadline at time-instant A
i
,
j
+
d
i (see Figure 2). A
i
,
j denotes the arrival time of job τ
i
,
j. Due to the properties of BSF-EDF scheduling, we discard the legal sequence of jobs with deadlines later than A
i
,
j
+
d
i. We only consider the BSF-EDF schedule of the remaining legal sequence of job requests, since the later deadline jobs have no effect on the scheduling of earlier deadline ones under BSF-EDF. It follows that a deadline miss of τ
i occurs at time-instant A
i
,
j
+
d
i (and this is the earliest deadline miss).Figure 2
A jobτ
i
,
j of task τ
i arrives at A
i
,
j and misses its deadline at time-instant A
i
,
j
+
d
i.For a given task setГ
=
{
τ
1
,
τ
2
,
τ
3
,
…
,
τ
n
}, let W
(
t
p
,
t
q
) be the total amount of work done during [
t
p
,
t
q
), and let R
(
t
p
,
t
q
) be the total amount of processor time demand in [
t
p
,
t
q
) required by all the jobs in this legal sequence of task set Г.We derive a necessary condition for a taskτ
i to miss its deadline, by following three steps: (
1
) deriving a lower bound on the total amount of processor time demand during the time interval [
t
0
,
A
i
,
j
+
d
i
) in Section 4.1, (
2
) deriving an upper bound on the total amount of processor time demand during the time interval [
t
0
,
A
i
,
j
+
d
i
) in Section 4.2, and (
3
) combining the lower bound and upper bound into a necessary condition for task τ
i missing its deadline. Note that t
0 is a special time point that will be explained in the coming section.


### 4.1. Lower Bound

In this section, we obtain a lower bound ofR
t
0
,
A
i
,
j
+
d
i.Consider jobτ
i
,
j arriving at time A
i
,
j misses its deadline at time-instant A
i
,
j
+
d
i. Let B
v be the total duration over [
A
i
,
j
,
A
i
,
j
+
d
i
) for which exactly v processors are busy in this BFS-EDF schedule, 0
≤
v
≤
m. Note that B
0 is necessarily zero, since τ
i
,
j does not finish before its deadline. Figure 3 manifests an example to understand this definition. S
v
′ denotes the cumulative speed of the currently running v processors. We can then write(6)
W
A
i
,
j
,
A
i
,
j
+
d
i
=
∑
v
=
1
m
S
v
′
B
v
.Since ∑
v
=
1
m
S
v
′
B
v
=
S
m
B
m
+
∑
v
=
1
m
-
1
S
v
′
B
v and S
m
B
m
=
S
m
(
d
i
-
∑
v
=
1
m
-
1
B
v
), we can write(7)
W
A
i
,
j
,
A
i
,
j
+
d
i
=
S
m
d
i
-
∑
v
=
1
m
-
1
S
m
B
v
-
S
v
′
B
v
.As we mentioned in Section 2, S
v means the cumulative speed of the first v lowest speed processors. The tasks may be allocated to the faster speed processors under BSF-EDF; therefore we can get (8)
S
v
′
≥
S
v
.From (7) and (8) above, we conclude that(9)
W
A
i
,
j
,
A
i
,
j
+
d
i
≥
S
m
d
i
-
∑
v
=
1
m
-
1
S
m
B
v
-
S
v
B
v
=
S
m
d
i
-
∑
v
=
1
m
-
1
S
m
-
S
v
s
1
s
1
B
v
.Let λ
π
=
max
1
≤
i
≤
m
⁡
(
∑
j
=
i
+
1
m
s
j
/
s
1
). It immediately follows that(10)
λ
π
≥
S
m
-
S
v
s
1
for
1
≤
v
≤
m
-
1
.Combining (9) and (10), we have(11)
W
A
i
,
j
,
A
i
,
j
+
d
i
≥
S
m
d
i
-
λ
π
∑
v
=
1
m
-
1
s
1
B
v
.Due to the work conserving property of BSF-EDF, τ
i
,
j must always be running in one of processors in time interval [
A
i
,
j
,
A
i
,
j
+
d
i
), except when all the processors are busy. The processor time that τ
i
,
j receives during [
A
i
,
j
,
A
i
,
j
+
d
i
) cannot be less than ∑
v
=
1
m
-
1
s
1
B
v, which is the worst case processor time when τ
i
,
j is running on the slowest processor s
1. The processor time that τ
i
,
j receives must not exceed e
i, since job τ
i
,
j misses its deadline. Thus, we have(12)
e
i
>
∑
v
=
1
m
-
1
s
1
B
v
.By applying this to (11), we have (13)
W
A
i
,
j
,
A
i
,
j
+
d
i
>
S
m
d
i
-
λ
π
e
i
,
W
A
i
,
j
,
A
i
,
j
+
d
i
d
i
>
S
m
-
λ
π
δ
i
.Since δ
m
a
x
(
Γ
)
≥
δ
i, we can write(14)
W
A
i
,
j
,
A
i
,
j
+
d
i
d
i
>
S
m
-
λ
π
δ
m
a
x
Γ
.Let (15)
μ
=
S
m
-
λ
π
δ
m
a
x
Γ
.Then we have(16)
W
A
i
,
j
,
A
i
,
j
+
d
i
>
μ
d
i
.Based on this, we now obtain a lower bound of R
t
0
,
A
i
,
j
+
d
i, where t
0 is the earliest time point t such that t
≤
A
i
,
j and W
t
,
A
i
,
j
+
d
i
>
μ
(
A
i
,
j
+
d
i
-
t
). Note that we can always find such a time instant since at least A
i
,
j satisfied A
i
,
j
≤
A
i
,
j and W
A
i
,
j
,
A
i
,
j
+
d
i
>
μ
(
A
i
,
j
+
d
i
-
A
i
,
j
). Let Δ
=
A
i
,
j
+
d
i
-
t
0; then we finally have (17)
W
t
0
,
A
i
,
j
+
d
i
>
μ
Δ
.Note that the job τ
i
,
j cannot be completed before time A
i
,
j
+
d
i, so the total amount of work processed can never exceed the amount of processor time demand. Thus, we have(18)
R
t
0
,
A
i
,
j
+
d
i
≥
W
t
0
,
A
i
,
j
+
d
i
.It immediately follows that (19)
R
t
0
,
A
i
,
j
+
d
i
>
μ
Δ
.As a result, μ
Δ is a lower bound of the total amount of processor time demand during the time interval [
t
0
,
A
i
,
j
+
d
i
).Figure 3
An example: there are three processors, and the total length of blue color units isB
3. The total length of orange color units is B
2. The total length of purple color units is B
1.


### 4.2. Upper Bound

We now obtain an upper bound ofR
t
0
,
A
i
,
j
+
d
i of the total amount of processor time demand. For this, we need to consider two types of jobs, regular jobs that arrived at or after t
0 and the jobs that arrive before t
0 but have not completed execution in the BSF-EDF schedule by the time-instant t
0. We will refer to jobs arriving prior to t
0 that need execution over [
t
0
,
A
i
,
j
+
d
i
) as carry-in jobs. We use R
c to denote the total amount of processor time demand caused by carry-in jobs and use R
r to denote the total amount of processor time demand caused by the regular jobs.We first compute the upper bound ofR
c by (
1
) determining an upper bound on the remaining processor time demand for each carry-in job, (
2
) determining a maximum value of the number of carry-in jobs, and (
3
) combining the per-job bounds to obtain an upper bound on the total remaining processor time demand of all carry-in jobs.Lemma 2.
Each carry-in job has less thanδ
m
a
x
(
Γ
)
Δ remaining execution requirement at time-instant t
0.Proof.
Let us consider a carry-in jobτ
p
,
q of a task τ
p that arrives at time-instant A
p
,
q
<
t
0 and has not completed its execution by time t
0 (see Figure 2). Let ϕ
p
,
q
=
t
0
-
A
p
,
q. Let e
p
,
q
′ be the processing time that τ
p
,
q receives during time interval [
A
p
,
q
,
t
0
). By using the same approach as in Section 4.1, let I
v be the total duration over A
p
,
q
,
t
0 for which exactly v processors are busy in this BSF-EDF schedule. J
v denotes the cumulative speed of the currently running v processors over A
p
,
q
,
t
0. Thus, the total amount of work processed in [
A
p
,
q
,
t
0
) can be calculated by S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
(
S
m
I
v
-
J
v
I
v
). Since J
v
≥
S
v, it immediately follows that (20)
e
p
,
q
′
≥
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
I
v
-
S
v
I
v
.Since we can also express the total amount of work done during the time interval [
A
p
,
q
,
t
0
) by W
A
p
,
q
,
A
i
,
j
+
d
i
-
W
t
0
,
A
i
,
j
+
d
i, we can write(21)
W
A
p
,
q
,
A
i
,
j
+
d
i
-
W
t
0
,
A
i
,
j
+
d
i
=
e
p
,
q
′
.By applying (20) to (21), we have (22)
W
A
p
,
q
,
A
i
,
j
+
d
i
-
W
t
0
,
A
i
,
j
+
d
i
≥
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
I
v
-
S
v
I
v
.By the definition of t
0 (see (17)), it must satisfy(23)
W
t
0
,
A
i
,
j
+
d
i
>
μ
Δ
.Note that t
0 is the earliest time point t such that t
≤
A
i
,
j and W
t
,
A
i
,
j
+
d
i
>
μ
(
A
i
,
j
+
d
i
-
t), and we can also get(24)
W
A
p
,
q
,
A
i
,
j
+
d
i
≤
μ
Δ
+
ϕ
p
,
q
.It immediately follows that (25)
μ
Δ
+
ϕ
p
,
q
-
μ
Δ
>
W
A
p
,
q
,
A
i
,
j
+
d
i
-
W
t
0
,
A
i
,
j
+
d
i
.By combining it to (22), we have(26)
μ
Δ
+
ϕ
p
,
q
-
μ
Δ
>
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
I
v
-
S
v
I
v
⟹
μ
ϕ
p
,
q
>
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
I
v
-
S
v
I
v
⟹
μ
ϕ
p
,
q
>
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
-
S
v
s
1
s
1
I
v
.Since (27)
λ
π
=
max
1
≤
i
≤
m
⁡
∑
j
=
i
+
1
m
s
j
s
1
,
λ
π
≥
S
m
-
S
v
s
1
for
1
≤
v
≤
m
-
1
,we can write(28)
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
-
S
v
s
1
s
1
I
v
≥
S
m
ϕ
p
,
q
-
λ
π
∑
v
=
1
m
-
1
s
1
I
v
.Equation (26) then becomes (29)
μ
ϕ
p
,
q
>
S
m
ϕ
p
,
q
-
λ
π
∑
v
=
1
m
-
1
s
1
I
v
.Observe that the amount of execution that carry-in job τ
p
,
q receives over A
p
,
q
,
t
0 is no less than ∑
v
=
1
m
-
1
I
v
s
1 since τ
p
,
q must be executing on one of the processors during any instant, when any processor is idle. Thus, we have(30)
e
p
,
q
′
≥
∑
v
=
1
m
-
1
s
1
I
v
.It immediately follows that (31)
S
m
ϕ
p
,
q
-
λ
π
∑
v
=
1
m
-
1
s
1
I
v
≥
S
m
ϕ
p
,
q
-
λ
π
e
p
,
q
′
.By (29) and (31), we can write(32)
μ
ϕ
p
,
q
>
S
m
ϕ
p
,
q
-
λ
π
e
p
,
q
′
.Using μ
=
S
m
-
λ
π
δ
m
a
x
(
Γ
) (defined in Section 4.1) in (32), it follows that (33)
S
m
-
λ
π
δ
m
a
x
Γ
ϕ
p
,
q
>
S
m
ϕ
p
,
q
-
λ
π
e
p
,
q
′
,resulting in (34)
e
p
,
q
′
>
δ
m
a
x
Γ
ϕ
p
,
q
.Note that e
p
,
q
=
d
p
δ
p and that the remaining processing time demand of the carry-in job τ
p
,
q of task is e
p
,
q
-
e
p
,
q
′. Thus, we have(35)
e
p
,
q
-
e
p
,
q
′
<
d
p
δ
p
-
δ
m
a
x
Γ
ϕ
p
,
q
.The absolute deadline of carry-in job τ
p
,
q is no later than time A
i
,
j
+
d
i; that is, d
p
-
ϕ
p
,
q
≤
Δ. Also, δ
p
≤
δ
m
a
x
(
Γ
); therefore(36)
e
p
,
q
-
e
p
,
q
′
<
d
p
δ
p
-
δ
m
a
x
Γ
ϕ
p
,
q
,
e
p
,
q
-
e
p
,
q
′
<
d
p
δ
m
a
x
Γ
-
δ
m
a
x
Γ
ϕ
p
,
q
,
e
p
,
q
-
e
p
,
q
′
<
δ
m
a
x
Γ
d
p
-
ϕ
p
,
q
,
e
p
,
q
-
e
p
,
q
′
<
δ
m
a
x
Γ
Δ
.As a result, an upper bound of the remaining processor time demand for each carry-in job can be expressed asδ
m
a
x
(
Γ
)
Δ.We obtained the upper bound on the remaining processor time demand for each carry-in job. We will now determine the maximum value of the number of carry-in jobs.Lemma 3.
The number of carry-in jobs is bounded by(37)
Ω
=
max
⁡
ω
:
S
ω
<
μ
.Proof.
Letε be an arbitrarily small positive number. From the definition of t
0, it follows that (38)
W
t
0
,
A
i
,
j
+
d
i
>
μ
Δ
,
W
t
0
-
ε
,
A
i
,
j
+
d
i
≤
μ
ε
+
Δ
.Therefore, the work processed during [
t
0
-
ε
,
t
0
) is less than μ
ε since W
t
0
-
ε
,
A
i
,
j
+
d
i
-
W
t
0
,
A
i
,
j
+
d
i
<
μ
ε. Based on the definition of μ
≤
S
m, it follows that the work processed during [
t
0
-
ε
,
t
0
) is less than ε
S
m. Therefore some processor is idle during [
t
0
-
ε
,
t
0
). This implies that all carry-in jobs are running in this interval and the number of carry-in jobs is the same as the number of busy processors. Let ω be the number of busy processors over [
t
0
-
ε
,
t
0
) and let Ω be an upper bound of ω. Thus, we have(39)
Ω
=
max
⁡
ω
:
S
ω
<
μ
.Therefore the upper bound ofR
c is Ω
Δ
δ
m
a
x
(
Γ
).Now let us consider the upper bound of the total amount of processor time demand caused by regular jobs. Fortunately, it is a well-studied subject, and algorithms are known for computing DBF and LOAD [9, 10]. Baruah et al. showed that the upper bound of R
r can be calculated by Δ
×
L
O
A
D
(
Γ
), where(40)
L
O
A
D
Г
≝
max
Δ
t
>
0
⁡
∑
τ
i
ϵ
Г
D
B
F
τ
i
,
Δ
t
Δ
t
,
D
B
F
τ
i
,
Δ
t
≝
max
⁡
0
,
Δ
t
-
d
i
T
i
+
1
e
i
if
Δ
t
≥
d
i
e
i
if
Δ
t
<
d
i
.As a result, an upper bound of the total amount of processor time demand can be expressed as(41)
R
t
0
,
A
i
,
j
+
d
i
≤
L
O
A
D
Γ
Δ
+
Ω
Δ
δ
m
a
x
Γ
.


### 4.3. BSF-EDF Schedulability Test

We now describe a sufficient schedulability test for the BSF-EDF scheduling algorithm.Theorem 4.
A task setГ
=
{
τ
1
,
τ
2
,
τ
3
,
…
,
τ
n
} is schedulable by BSF-EDF on anm-core performance asymmetric multiprocessor platform π
=
{
P
1
,
P
2
,
…
,
P
m
}, with processing speeds s
1
=
s
2
=
⋯
=
s
q
=
1, and s
i
>
1 for q
<
i
≤
m, if it satisfies the following condition:(42)
L
O
A
D
Г
≤
μ
-
Ω
δ
m
a
x
Γ
,where μ and Ω are defined in (15) and (37), respectively.Proof.
We prove it through the principle of contradiction. We obtain necessary condition for the jobτ
i
,
j missing its deadline. Negating this condition yields a sufficient condition for the BSF-EDF schedulability.
From the foregoing discussion, we already got the upper bound and lower bound of the total amount of processor time demand during the time interval[
t
0
,
A
i
,
j
+
d
i
). As a result, we obtain the following bound on R
t
0
,
A
i
,
j
+
d
i:(43)
R
t
0
,
A
i
,
j
+
d
i
≤
L
O
A
D
Γ
Δ
+
Ω
Δ
δ
m
a
x
Γ
,
R
t
0
,
A
i
,
j
+
d
i
>
μ
Δ
.Based on (43), we can get the necessary condition for a task τ
i to miss its deadline:(44)
L
O
A
D
Γ
Δ
+
Ω
Δ
δ
m
a
x
Γ
>
μ
Δ
≡
L
O
A
D
Γ
+
Ω
δ
m
a
x
Γ
>
μ
≡
L
O
A
D
Γ
>
μ
-
Ω
δ
m
a
x
Γ
.Equivalently, the negation of this condition is sufficient to ensure BSF-EDF schedulability: (45)
L
O
A
D
Г
≤
μ
-
Ω
δ
m
a
x
Γ
,which is as claimed in Theorem 4.


## 4.1. Lower Bound

In this section, we obtain a lower bound ofR
t
0
,
A
i
,
j
+
d
i.Consider jobτ
i
,
j arriving at time A
i
,
j misses its deadline at time-instant A
i
,
j
+
d
i. Let B
v be the total duration over [
A
i
,
j
,
A
i
,
j
+
d
i
) for which exactly v processors are busy in this BFS-EDF schedule, 0
≤
v
≤
m. Note that B
0 is necessarily zero, since τ
i
,
j does not finish before its deadline. Figure 3 manifests an example to understand this definition. S
v
′ denotes the cumulative speed of the currently running v processors. We can then write(6)
W
A
i
,
j
,
A
i
,
j
+
d
i
=
∑
v
=
1
m
S
v
′
B
v
.Since ∑
v
=
1
m
S
v
′
B
v
=
S
m
B
m
+
∑
v
=
1
m
-
1
S
v
′
B
v and S
m
B
m
=
S
m
(
d
i
-
∑
v
=
1
m
-
1
B
v
), we can write(7)
W
A
i
,
j
,
A
i
,
j
+
d
i
=
S
m
d
i
-
∑
v
=
1
m
-
1
S
m
B
v
-
S
v
′
B
v
.As we mentioned in Section 2, S
v means the cumulative speed of the first v lowest speed processors. The tasks may be allocated to the faster speed processors under BSF-EDF; therefore we can get (8)
S
v
′
≥
S
v
.From (7) and (8) above, we conclude that(9)
W
A
i
,
j
,
A
i
,
j
+
d
i
≥
S
m
d
i
-
∑
v
=
1
m
-
1
S
m
B
v
-
S
v
B
v
=
S
m
d
i
-
∑
v
=
1
m
-
1
S
m
-
S
v
s
1
s
1
B
v
.Let λ
π
=
max
1
≤
i
≤
m
⁡
(
∑
j
=
i
+
1
m
s
j
/
s
1
). It immediately follows that(10)
λ
π
≥
S
m
-
S
v
s
1
for
1
≤
v
≤
m
-
1
.Combining (9) and (10), we have(11)
W
A
i
,
j
,
A
i
,
j
+
d
i
≥
S
m
d
i
-
λ
π
∑
v
=
1
m
-
1
s
1
B
v
.Due to the work conserving property of BSF-EDF, τ
i
,
j must always be running in one of processors in time interval [
A
i
,
j
,
A
i
,
j
+
d
i
), except when all the processors are busy. The processor time that τ
i
,
j receives during [
A
i
,
j
,
A
i
,
j
+
d
i
) cannot be less than ∑
v
=
1
m
-
1
s
1
B
v, which is the worst case processor time when τ
i
,
j is running on the slowest processor s
1. The processor time that τ
i
,
j receives must not exceed e
i, since job τ
i
,
j misses its deadline. Thus, we have(12)
e
i
>
∑
v
=
1
m
-
1
s
1
B
v
.By applying this to (11), we have (13)
W
A
i
,
j
,
A
i
,
j
+
d
i
>
S
m
d
i
-
λ
π
e
i
,
W
A
i
,
j
,
A
i
,
j
+
d
i
d
i
>
S
m
-
λ
π
δ
i
.Since δ
m
a
x
(
Γ
)
≥
δ
i, we can write(14)
W
A
i
,
j
,
A
i
,
j
+
d
i
d
i
>
S
m
-
λ
π
δ
m
a
x
Γ
.Let (15)
μ
=
S
m
-
λ
π
δ
m
a
x
Γ
.Then we have(16)
W
A
i
,
j
,
A
i
,
j
+
d
i
>
μ
d
i
.Based on this, we now obtain a lower bound of R
t
0
,
A
i
,
j
+
d
i, where t
0 is the earliest time point t such that t
≤
A
i
,
j and W
t
,
A
i
,
j
+
d
i
>
μ
(
A
i
,
j
+
d
i
-
t
). Note that we can always find such a time instant since at least A
i
,
j satisfied A
i
,
j
≤
A
i
,
j and W
A
i
,
j
,
A
i
,
j
+
d
i
>
μ
(
A
i
,
j
+
d
i
-
A
i
,
j
). Let Δ
=
A
i
,
j
+
d
i
-
t
0; then we finally have (17)
W
t
0
,
A
i
,
j
+
d
i
>
μ
Δ
.Note that the job τ
i
,
j cannot be completed before time A
i
,
j
+
d
i, so the total amount of work processed can never exceed the amount of processor time demand. Thus, we have(18)
R
t
0
,
A
i
,
j
+
d
i
≥
W
t
0
,
A
i
,
j
+
d
i
.It immediately follows that (19)
R
t
0
,
A
i
,
j
+
d
i
>
μ
Δ
.As a result, μ
Δ is a lower bound of the total amount of processor time demand during the time interval [
t
0
,
A
i
,
j
+
d
i
).Figure 3
An example: there are three processors, and the total length of blue color units isB
3. The total length of orange color units is B
2. The total length of purple color units is B
1.


## 4.2. Upper Bound

We now obtain an upper bound ofR
t
0
,
A
i
,
j
+
d
i of the total amount of processor time demand. For this, we need to consider two types of jobs, regular jobs that arrived at or after t
0 and the jobs that arrive before t
0 but have not completed execution in the BSF-EDF schedule by the time-instant t
0. We will refer to jobs arriving prior to t
0 that need execution over [
t
0
,
A
i
,
j
+
d
i
) as carry-in jobs. We use R
c to denote the total amount of processor time demand caused by carry-in jobs and use R
r to denote the total amount of processor time demand caused by the regular jobs.We first compute the upper bound ofR
c by (
1
) determining an upper bound on the remaining processor time demand for each carry-in job, (
2
) determining a maximum value of the number of carry-in jobs, and (
3
) combining the per-job bounds to obtain an upper bound on the total remaining processor time demand of all carry-in jobs.Lemma 2.
Each carry-in job has less thanδ
m
a
x
(
Γ
)
Δ remaining execution requirement at time-instant t
0.Proof.
Let us consider a carry-in jobτ
p
,
q of a task τ
p that arrives at time-instant A
p
,
q
<
t
0 and has not completed its execution by time t
0 (see Figure 2). Let ϕ
p
,
q
=
t
0
-
A
p
,
q. Let e
p
,
q
′ be the processing time that τ
p
,
q receives during time interval [
A
p
,
q
,
t
0
). By using the same approach as in Section 4.1, let I
v be the total duration over A
p
,
q
,
t
0 for which exactly v processors are busy in this BSF-EDF schedule. J
v denotes the cumulative speed of the currently running v processors over A
p
,
q
,
t
0. Thus, the total amount of work processed in [
A
p
,
q
,
t
0
) can be calculated by S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
(
S
m
I
v
-
J
v
I
v
). Since J
v
≥
S
v, it immediately follows that (20)
e
p
,
q
′
≥
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
I
v
-
S
v
I
v
.Since we can also express the total amount of work done during the time interval [
A
p
,
q
,
t
0
) by W
A
p
,
q
,
A
i
,
j
+
d
i
-
W
t
0
,
A
i
,
j
+
d
i, we can write(21)
W
A
p
,
q
,
A
i
,
j
+
d
i
-
W
t
0
,
A
i
,
j
+
d
i
=
e
p
,
q
′
.By applying (20) to (21), we have (22)
W
A
p
,
q
,
A
i
,
j
+
d
i
-
W
t
0
,
A
i
,
j
+
d
i
≥
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
I
v
-
S
v
I
v
.By the definition of t
0 (see (17)), it must satisfy(23)
W
t
0
,
A
i
,
j
+
d
i
>
μ
Δ
.Note that t
0 is the earliest time point t such that t
≤
A
i
,
j and W
t
,
A
i
,
j
+
d
i
>
μ
(
A
i
,
j
+
d
i
-
t), and we can also get(24)
W
A
p
,
q
,
A
i
,
j
+
d
i
≤
μ
Δ
+
ϕ
p
,
q
.It immediately follows that (25)
μ
Δ
+
ϕ
p
,
q
-
μ
Δ
>
W
A
p
,
q
,
A
i
,
j
+
d
i
-
W
t
0
,
A
i
,
j
+
d
i
.By combining it to (22), we have(26)
μ
Δ
+
ϕ
p
,
q
-
μ
Δ
>
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
I
v
-
S
v
I
v
⟹
μ
ϕ
p
,
q
>
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
I
v
-
S
v
I
v
⟹
μ
ϕ
p
,
q
>
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
-
S
v
s
1
s
1
I
v
.Since (27)
λ
π
=
max
1
≤
i
≤
m
⁡
∑
j
=
i
+
1
m
s
j
s
1
,
λ
π
≥
S
m
-
S
v
s
1
for
1
≤
v
≤
m
-
1
,we can write(28)
S
m
ϕ
p
,
q
-
∑
v
=
1
m
-
1
S
m
-
S
v
s
1
s
1
I
v
≥
S
m
ϕ
p
,
q
-
λ
π
∑
v
=
1
m
-
1
s
1
I
v
.Equation (26) then becomes (29)
μ
ϕ
p
,
q
>
S
m
ϕ
p
,
q
-
λ
π
∑
v
=
1
m
-
1
s
1
I
v
.Observe that the amount of execution that carry-in job τ
p
,
q receives over A
p
,
q
,
t
0 is no less than ∑
v
=
1
m
-
1
I
v
s
1 since τ
p
,
q must be executing on one of the processors during any instant, when any processor is idle. Thus, we have(30)
e
p
,
q
′
≥
∑
v
=
1
m
-
1
s
1
I
v
.It immediately follows that (31)
S
m
ϕ
p
,
q
-
λ
π
∑
v
=
1
m
-
1
s
1
I
v
≥
S
m
ϕ
p
,
q
-
λ
π
e
p
,
q
′
.By (29) and (31), we can write(32)
μ
ϕ
p
,
q
>
S
m
ϕ
p
,
q
-
λ
π
e
p
,
q
′
.Using μ
=
S
m
-
λ
π
δ
m
a
x
(
Γ
) (defined in Section 4.1) in (32), it follows that (33)
S
m
-
λ
π
δ
m
a
x
Γ
ϕ
p
,
q
>
S
m
ϕ
p
,
q
-
λ
π
e
p
,
q
′
,resulting in (34)
e
p
,
q
′
>
δ
m
a
x
Γ
ϕ
p
,
q
.Note that e
p
,
q
=
d
p
δ
p and that the remaining processing time demand of the carry-in job τ
p
,
q of task is e
p
,
q
-
e
p
,
q
′. Thus, we have(35)
e
p
,
q
-
e
p
,
q
′
<
d
p
δ
p
-
δ
m
a
x
Γ
ϕ
p
,
q
.The absolute deadline of carry-in job τ
p
,
q is no later than time A
i
,
j
+
d
i; that is, d
p
-
ϕ
p
,
q
≤
Δ. Also, δ
p
≤
δ
m
a
x
(
Γ
); therefore(36)
e
p
,
q
-
e
p
,
q
′
<
d
p
δ
p
-
δ
m
a
x
Γ
ϕ
p
,
q
,
e
p
,
q
-
e
p
,
q
′
<
d
p
δ
m
a
x
Γ
-
δ
m
a
x
Γ
ϕ
p
,
q
,
e
p
,
q
-
e
p
,
q
′
<
δ
m
a
x
Γ
d
p
-
ϕ
p
,
q
,
e
p
,
q
-
e
p
,
q
′
<
δ
m
a
x
Γ
Δ
.As a result, an upper bound of the remaining processor time demand for each carry-in job can be expressed asδ
m
a
x
(
Γ
)
Δ.We obtained the upper bound on the remaining processor time demand for each carry-in job. We will now determine the maximum value of the number of carry-in jobs.Lemma 3.
The number of carry-in jobs is bounded by(37)
Ω
=
max
⁡
ω
:
S
ω
<
μ
.Proof.
Letε be an arbitrarily small positive number. From the definition of t
0, it follows that (38)
W
t
0
,
A
i
,
j
+
d
i
>
μ
Δ
,
W
t
0
-
ε
,
A
i
,
j
+
d
i
≤
μ
ε
+
Δ
.Therefore, the work processed during [
t
0
-
ε
,
t
0
) is less than μ
ε since W
t
0
-
ε
,
A
i
,
j
+
d
i
-
W
t
0
,
A
i
,
j
+
d
i
<
μ
ε. Based on the definition of μ
≤
S
m, it follows that the work processed during [
t
0
-
ε
,
t
0
) is less than ε
S
m. Therefore some processor is idle during [
t
0
-
ε
,
t
0
). This implies that all carry-in jobs are running in this interval and the number of carry-in jobs is the same as the number of busy processors. Let ω be the number of busy processors over [
t
0
-
ε
,
t
0
) and let Ω be an upper bound of ω. Thus, we have(39)
Ω
=
max
⁡
ω
:
S
ω
<
μ
.Therefore the upper bound ofR
c is Ω
Δ
δ
m
a
x
(
Γ
).Now let us consider the upper bound of the total amount of processor time demand caused by regular jobs. Fortunately, it is a well-studied subject, and algorithms are known for computing DBF and LOAD [9, 10]. Baruah et al. showed that the upper bound of R
r can be calculated by Δ
×
L
O
A
D
(
Γ
), where(40)
L
O
A
D
Г
≝
max
Δ
t
>
0
⁡
∑
τ
i
ϵ
Г
D
B
F
τ
i
,
Δ
t
Δ
t
,
D
B
F
τ
i
,
Δ
t
≝
max
⁡
0
,
Δ
t
-
d
i
T
i
+
1
e
i
if
Δ
t
≥
d
i
e
i
if
Δ
t
<
d
i
.As a result, an upper bound of the total amount of processor time demand can be expressed as(41)
R
t
0
,
A
i
,
j
+
d
i
≤
L
O
A
D
Γ
Δ
+
Ω
Δ
δ
m
a
x
Γ
.


## 4.3. BSF-EDF Schedulability Test

We now describe a sufficient schedulability test for the BSF-EDF scheduling algorithm.Theorem 4.
A task setГ
=
{
τ
1
,
τ
2
,
τ
3
,
…
,
τ
n
} is schedulable by BSF-EDF on anm-core performance asymmetric multiprocessor platform π
=
{
P
1
,
P
2
,
…
,
P
m
}, with processing speeds s
1
=
s
2
=
⋯
=
s
q
=
1, and s
i
>
1 for q
<
i
≤
m, if it satisfies the following condition:(42)
L
O
A
D
Г
≤
μ
-
Ω
δ
m
a
x
Γ
,where μ and Ω are defined in (15) and (37), respectively.Proof.
We prove it through the principle of contradiction. We obtain necessary condition for the jobτ
i
,
j missing its deadline. Negating this condition yields a sufficient condition for the BSF-EDF schedulability.
From the foregoing discussion, we already got the upper bound and lower bound of the total amount of processor time demand during the time interval[
t
0
,
A
i
,
j
+
d
i
). As a result, we obtain the following bound on R
t
0
,
A
i
,
j
+
d
i:(43)
R
t
0
,
A
i
,
j
+
d
i
≤
L
O
A
D
Γ
Δ
+
Ω
Δ
δ
m
a
x
Γ
,
R
t
0
,
A
i
,
j
+
d
i
>
μ
Δ
.Based on (43), we can get the necessary condition for a task τ
i to miss its deadline:(44)
L
O
A
D
Γ
Δ
+
Ω
Δ
δ
m
a
x
Γ
>
μ
Δ
≡
L
O
A
D
Γ
+
Ω
δ
m
a
x
Γ
>
μ
≡
L
O
A
D
Γ
>
μ
-
Ω
δ
m
a
x
Γ
.Equivalently, the negation of this condition is sufficient to ensure BSF-EDF schedulability: (45)
L
O
A
D
Г
≤
μ
-
Ω
δ
m
a
x
Γ
,which is as claimed in Theorem 4.


## 5. Conclusions

In this paper, we presented a unique approach to task allocation in a performance asymmetric multiprocessor system based on EDF, called BSF-EDF. In BSF-EDF we chose the appropriate slowest speed processor to execute the highest priority task. To our knowledge, this is the first piece of work that considers the task allocation problem on performance asymmetric multiprocessors. We hold the view that choosing an appropriate processor instead of a fastest one gives opportunities of improved scheduling, by reserving fast processors for future tasks that will arrive later. We have also presented an effective schedulability test for performance asymmetric multiprocessors based on the properties of the proposed BSF-EDF.



---

*Source: 1237438-2017-02-20.xml*