Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
V
o
l.
5, N
o
. 4
,
A
ugu
st
2015
, pp
. 70
1
~
71
3
I
S
SN
: 208
8-8
7
0
8
7
01
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJECE
Pr
ocessor
Speed Contr
o
l for
Po
wer
Reduction of Real-T
ime
Systems
Medh
a
t
H
Aw
ad
al
l
a
Department o
f
Electrical and Co
mputer Engin
eer
ing, Sultan
Qabo
os
University
(S
QU),
Oman
Department o
f
C
o
mmunication,
Electronics an
d
Com
puters
Univers
i
t
y
of
Helwan
, Eg
yp
t
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Apr 13, 2015
Rev
i
sed
May 18
, 20
15
Accepte
d
J
u
n 3, 2015
Reducing en
erg
y
consumption
is a criti
ca
l issue in the design
of batter
y
-
powered r
eal time s
y
stems to
prolong
batter
y
life. With
d
y
namic voltag
e
s
caling (DVS
) p
r
oces
s
o
rs
, energ
y
cons
um
ption can be r
e
duced ef
ficiently
b
y
making appropr
iate decisions on the
processor speed/voltage
during the
scheduling of r
eal
time tasks. Sche
duling d
e
cision is usually
based
on
parameters
which are assumed
to
be
cr
isp. However, in man
y
circumstances
the values
of t
h
es
e param
e
te
rs
ar
e vague. Th
e vagueness of parameters
suggests that to develop a fuzzy
logic ap
proach to red
u
ce ener
g
y
consumption b
y
determining th
e appr
opr
iate s
upply
-
vo
ltag
e
/sp
eed of
th
e
processor provided that timin
g cons
train
t
s
are guar
a
nt
eed
.
Intens
ive
simulated exper
i
ments
and
qu
al
itat
i
ve
com
p
aris
ons with the
m
o
st rel
a
ted
liter
a
tur
e
hav
e
b
een
conduct
e
d i
n
the
contex
t of
depend
ent r
eal-
tim
e tasks
.
Experimental results have shown that
the prop
osed fuzzy
sch
e
duler saves
m
o
re energ
y
a
nd creat
es
feas
i
b
le s
c
hedul
es
for real tim
e ta
s
k
s
.
It als
o
considers tasks prioriti
es which cause
higher sy
stem utilizatio
n and lower
de
a
d
li
ne
mi
ss time
.
Keyword:
Dyn
a
m
i
c Vo
ltag
e
Scaling
Processors
Fuzzy L
o
gic Approach
Mu
lti-sp
eed
al
g
o
rith
m
Copyright ©
201
5 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
M
e
dhat
H A
w
a
dal
l
a
,
Depa
rtem
ent of Electrical a
nd Co
m
p
u
t
er
Engin
eer
ing
,
SQ
U, Om
an
Em
a
il: med
h
a
th
a@squ
.
ed
u.om
1.
INTRODUCTION
Real-ti
m
e s
y
st
e
m
s are v
ital
t
o
in
du
strialized
in
fr
astructure such as com
m
and an
d co
nt
rol
,
pr
ocess
co
n
t
ro
l, fligh
t
con
t
ro
l, sp
ace shu
ttle av
i
o
n
i
cs,
air traffic con
t
ro
l
syste
m
s an
d
also
m
i
ssio
n
critical
co
m
p
u
t
atio
n
s
[1
]. In
all cases, ti
m
e
h
a
s an essen
tial ro
le
an
d
havi
ng
t
h
e
ri
ght
a
n
s
w
er
t
o
o
l
a
t
e
i
s
as ba
d
as n
o
t
h
a
v
i
n
g
it at all.
In
th
e literatu
re, th
ese syste
m
s h
a
v
e
b
e
en
d
e
fin
e
d
as: “syst
e
m
s
in
wh
ich
th
e co
rrectn
e
ss o
f
the
syste
m
d
e
p
e
nds no
t
o
n
l
y
o
n
th
e log
i
cal resu
lts of co
m
p
u
t
atio
n
,
bu
t also th
e tim
e at wh
ich
t
h
e
resu
lts are
produce
d
” [1].
Suc
h
system
s
m
u
st react to the requ
ests
within a fi
xed am
ount
of tim
e which is
called
deadl
i
n
e
.
Sc
he
dul
i
n
g al
g
o
ri
t
h
m
s
of t
h
ese sy
st
em
s
m
a
y
be
con
s
i
d
ere
d
one
of t
h
e
key
co
m
ponent
s o
f
a
real
-
ti
m
e
syste
m
,
wh
ich
can
either en
ab
le th
e syste
m
to
th
ri
ve
or bri
ng i
t
t
o
it
s knees. St
ri
ct
t
i
m
i
ng req
u
i
r
e
m
ent
s
m
u
st o
f
ten
b
e
m
e
t with
in
h
i
gh
ly d
y
n
a
m
i
c en
v
i
ron
m
en
ts wh
ich
d
o
no
t lend
th
em
selv
es well to static
sch
e
d
u
ling
algo
rith
m
s
. Th
e l
e
v
e
l of
u
n
c
ertain
ty in
d
y
n
a
mic, real-tim
e
envi
ronm
ents is suc
h
as to requi
r
e
sig
n
i
fican
t
flexib
ility an
d
ad
ap
tiv
ity fro
m
real syste
m
s.
Fuzzy lo
g
i
c con
t
rib
u
tion
s
i
n
th
is issu
e i
n
t
h
e
form
o
f
ap
pro
x
i
m
a
te r
eason
ing
,
wh
er
e it p
r
o
v
i
d
e
s d
ecisio
n
-
s
uppo
r
t
and
exp
e
r
t
syste
m
s
w
ith
p
o
w
e
rf
u
l
r
e
aso
n
i
ng
cap
ab
ilities bou
nd
b
y
a m
i
n
i
m
u
m
n
u
m
b
e
r o
f
ru
les.
Th
eoretically, fu
zzy
lo
g
i
c is a m
e
t
h
od
fo
r rep
r
esen
ting
anal
o
g
p
r
oce
s
s
e
s, or
nat
u
ral
phe
n
o
m
e
na t
h
at
are di
ffi
c
u
l
t
t
o
m
odel
m
a
them
ati
cal
l
y
on
a di
gi
t
a
l
co
m
put
e
r
.
Th
erefo
r
e Fu
zzy syste
m
s fit
as sch
e
d
u
ling
algo
rith
m
b
u
ild
ing
in
to
t
h
e real-tim
e s
y
ste
m
flex
ib
ili
ty an
d
ad
ap
tation
to
th
e un
certai
n
ty in
h
e
ren
t
in
real-tim
e en
v
i
ro
n
m
en
ts and
o
f
fers a m
ean
s to
im
p
r
o
v
e
sev
e
ral
i
m
p
o
r
tan
t
ch
aracteristics o
f
re
al-tim
e syste
m
s.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 4
,
Au
gu
st 2
015
:
70
1
–
71
3
70
2
Since m
o
st of
real tim
e
syste
m
s
(devices
) a
r
e ba
ttery powered. As t
h
e applications
on t
h
ese devices
are bei
ng c
o
m
p
licated, the
energy
cons
um
ption is also effectively
increasing.
So, m
i
nimizing energy
con
s
um
pt
i
on i
s
a cri
t
i
cal
i
ssue
i
n
t
h
e
desi
gn
of t
h
ese sy
st
e
m
s, and t
ech
ni
que
s t
h
at
red
u
c
e
ene
r
gy
c
o
n
s
u
m
pti
on
have
bee
n
st
u
d
i
ed at
di
ffe
rent
l
e
vel
s
i
n
det
a
i
l
s
[
2
]
.
Dy
nam
i
c vol
t
a
ge scal
i
ng (
D
VS) i
s
a t
echn
i
que t
h
at
va
ri
es t
h
e sup
p
l
y
vol
t
a
ge an
d cl
o
c
k fre
q
u
enc
y
(spee
d
) bas
e
d
on t
h
e c
o
m
put
at
i
on l
o
a
d
t
o
p
r
o
v
i
d
e
desi
re
d
per
f
o
r
m
a
nce w
i
t
h
t
h
e m
i
nim
a
l
am
ount
of e
n
ergy
con
s
um
pt
i
on i
n
ubi
qui
t
o
us
e
m
bedded
sy
st
em
s.
The p
o
w
er c
o
nsum
pt
i
on
has
t
w
o essent
i
a
l
com
ponent
s:
dy
nam
i
c and st
at
i
c
power
. T
h
e dy
nam
i
c
po
we
r co
ns
um
pt
i
o
n
,
w
h
i
c
h i
s
t
h
e m
a
i
n
com
p
o
n
e
n
t
,
has a
q
u
ad
rat
i
c
de
pen
d
ency
o
n
su
p
p
l
y
vol
t
a
ge
[3]
a
nd c
a
n
be rep
r
ese
n
t
e
d as:
Pdynam
ic = Cef .
V
d
d2 .
F
(1)
Wh
ere Cef is
th
e switch
e
d
cap
acitan
ce,
Vdd
is th
e sup
p
l
y v
o
ltag
e
, and F is th
e
p
r
o
c
esso
r clo
c
k
fre
que
ncy
(s
o
m
et
im
es referr
ed as spee
d S
)
w
h
i
c
h can
b
e
exp
r
esse
d i
n
t
e
r
m
s of su
p
p
l
y
vol
t
a
ge
V
dd a
nd
th
resh
o
l
d
v
o
ltag
e
Vt as fo
llowing
:
F =
k
. (V
dd
–
V
t
)2
/
Vd
d
(
2
)
The st
at
i
c
po
w
e
r co
nsum
pt
i
o
n i
s
pri
m
ari
l
y
occu
rre
d
due
t
o
leaka
g
e current (Ilea
k) [3],
and t
h
e static
(leaka
g
e)
powe
r (Pleak) ca
n
be expres
sed as:
Pleak =
Ileak . Vdd
(3)
Wh
en
th
e processor is id
le,
a
m
a
j
o
r po
rtion
o
f
th
e pow
er
co
nsu
m
p
tio
n
com
e
s
from
the leakage
.
C
u
r
r
ent
l
y
l
eak
age
p
o
we
r i
s
r
a
pi
dl
y
becom
i
ng
t
h
e
d
o
m
i
nant
s
o
u
r
ce
o
f
p
o
we
r c
o
ns
um
pt
i
on i
n
ci
rc
ui
t
s
an
d
p
e
rsists
wh
eth
e
r a co
m
p
u
t
er is activ
e or i
d
le [2
], an
d m
u
ch work
has been done
t
o
ad
dress th
is
p
r
ob
lem
[3,4
].
So
, loweri
n
g
su
pp
ly vo
ltag
e
is on
e
of th
e mo
st
effective
ways to
reduce
bot
h
dynam
i
c and leaka
g
e
po
we
r c
ons
um
pt
i
o
n
.
As a
res
u
l
t
,
i
t
re
duces
ener
gy
c
ons
um
pt
i
o
n
w
h
e
r
e t
h
e ene
r
gy
c
o
nsu
m
pti
on i
s
t
h
e
p
o
w
e
r
di
ssi
pat
e
d
o
v
e
r
t
i
m
e
:
Energy =
∫
Pow
e
r d
t
(
4
)
Ho
we
ver
,
D
V
S
ai
m
s
at
redu
ci
ng e
n
e
r
gy
c
o
nsum
pt
i
o
n
by
red
u
ci
n
g
t
h
e s
u
p
p
l
y
-
vol
t
a
ge/
s
pee
d
of t
h
e
pr
ocess
o
r
p
r
ov
i
d
ed t
h
at
t
i
m
i
ng c
onst
r
ai
nt
s a
r
e
gua
rant
ee
d.
In
ot
her
w
o
r
d
s
,
D
V
S
m
a
kes use
of
t
h
e
fact
t
h
at
th
ere is
no
b
e
nefit o
f
fi
n
i
sh
i
n
g
a
real tim
e j
o
b
earlier th
an
it
s d
e
ad
lin
e.
DV
S
pr
ocess
o
rs
have
t
w
o t
y
pes [
4
]
:
i
d
eal
an
d
n
on-ideal
. An i
d
eal processor ca
n
operate at any
spee
d in the range bet
w
een its
m
i
nim
u
m
avai
l
a
bl
e spe
e
d an
d m
a
xi
m
u
m available speed.
A non-ideal
p
r
o
cesso
r
h
a
s o
n
l
y d
i
screte sp
eeds with
n
e
g
lig
ib
le or
n
o
n
-
n
e
g
lig
ib
le sp
eed
tran
sitio
n o
v
e
rh
ead
s
. An
o
t
her
classification defines four different
types
of
DVS system
s:
ideal, feasi
b
le
, p
r
actical,
an
d m
u
l
tip
le
[4
].
In
t
h
i
s
pa
per
,
o
u
r
m
o
t
i
v
at
i
on i
s
t
o
de
vel
o
p a
fuzzy
l
ogi
c
ap
pr
oac
h
t
o
re
d
u
ce ene
r
gy
co
ns
um
pt
i
on
by
det
e
rm
i
n
i
ng t
h
e ap
pr
op
ri
at
e
sup
p
l
y
-
vol
t
a
ge
/
s
peed
o
f
t
h
e
pr
ocess
o
r p
r
ovi
ded
t
h
at
t
i
m
i
ng co
nst
r
ai
nt
s ar
e
gua
ra
nteed.
Fuzzy logic a
p
proac
h
is
propos
ed
because
in a dynam
i
c
ha
rd real-time syste
m
, not all the
characte
r
istics of tasks
(e.g.,
prece
de
nce c
o
nst
r
ai
nt
s
,
re
so
urce
re
qui
rem
e
nts, etc.) a
r
e
known a
pri
o
ri. For
ex
am
p
l
e, th
e arriv
a
l tim
e
fo
r th
e n
e
x
t
task
is u
n
k
nown
for aperi
odic tas
k
s. T
o
be m
o
re precise, the
r
e is an
in
h
e
rit un
certain
ty in
h
a
rd
real-ti
m
e en
v
i
ro
n
m
en
t wh
ich will wo
rsen
sch
e
d
u
ling
p
r
ob
lem
s
(e.g
. arb
itrary
arriv
a
l ti
m
e
, u
n
certain
co
m
p
u
t
atio
n
ti
m
e
a
n
d
d
ead
lin
e)
.
Characteristics
of a task
th
at
m
a
y b
e
u
n
certain
in
clu
d
e
exp
ected
n
e
x
t
arriv
a
l
ti
m
e
, critica
lit
y
,
o
r
im
p
o
r
tan
c
e o
f
th
e task
, sy
ste
m
lo
ad
an
d
/
o
r
p
r
ed
icted
load
of
i
ndi
vi
dual
pr
oc
essor
s
, an
d r
u
n
t
i
m
e
, or
m
o
re speci
fi
cal
l
y
average
vs.
worst
-
case run tim
e.
There
f
ore,
our goal
i
s
t
o
devel
o
p an ap
pr
oach f
o
r ha
r
d
real
-t
i
m
e schedul
i
n
g
t
h
at
can be appl
i
e
d t
o
a dy
nam
i
c envi
r
o
n
m
ent
in
vo
lv
ing
a certain
d
e
g
r
ee of u
n
certai
n
ty.
In
th
is p
a
per, we concent
r
ate on a hard re
al time sys
t
e
m
on
a
p
r
eem
p
t
ab
le un
ipro
cessor syste
m
with
a
set o
f
d
e
p
e
nd
en
t
task
s. Th
ese task
s will b
e
characterized
b
y
worst-
case com
put
at
i
o
n
t
i
m
e
, bl
oc
ki
ng
ti
m
e
an
d task
d
ead
lin
e.
Th
e rest o
f
t
h
e
p
a
p
e
r is org
a
n
i
zed
as fo
llows:
sectio
n
2
ou
tlin
es th
e
related
work
t
o
th
e t
h
eme o
f
th
is
p
a
p
e
r. Section
3
d
e
m
o
n
s
trates th
e m
u
lti-sp
eed
algorith
m
.
Sectio
n
4
g
i
v
e
s an
o
v
e
rv
iew
ab
ou
t
fu
zzy
i
n
feren
c
e
sy
st
em
. Sect
i
on 5
sh
ow
s t
h
e
pr
o
pose
d
fuzz
y
sy
st
em
. Sect
ion
6
prese
n
t
s
e
xpe
ri
m
e
nt
s and di
sc
ussi
ons
.
Sect
i
o
n
7 c
oncl
ude
s t
h
e pa
per
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Process
o
r
S
p
e
e
d C
ont
r
o
l
f
o
r
Pow
e
r Re
d
u
ct
i
o
n
of
Real
-
T
i
m
e Syst
e
m
s
(
Med
hat
H Aw
a
dal
l
a
)
70
3
2.
RELATED WORK
Man
y
Research
ers
h
a
v
e
tried
to
im
p
l
e
m
en
t fu
zzy l
ogic t
o
sche
dule the
processes
.
There are four
main
ap
pro
a
ches repo
rted
in
t
h
e literatu
re
for th
e fu
zzy sched
u
ling
p
r
o
b
l
em
s
;
fu
zzifyin
g
d
i
rectly th
e classical
di
spat
c
h
i
n
g rul
e
s, usi
n
g f
u
zzy
ran
k
i
n
g, f
u
zzy
dom
i
n
ance rel
a
t
i
on m
e
t
hods,
and s
o
l
v
i
n
g m
a
t
h
em
ati
cal
model
s
t
o
det
e
rm
i
n
e t
h
e
o
p
t
i
m
a
l
schedul
es
by
he
ur
i
s
t
i
c
app
r
o
x
i
m
at
i
on m
e
t
hods
[5]
.
R
o
un
d
r
o
b
i
n sc
hed
u
l
i
n
g
usi
n
g
n
e
uro
fu
zzy app
r
o
a
ch
and
Soft real-ti
m
e fu
zzy task
sch
e
dulin
g
fo
r m
u
ltip
ro
cessor system
s
[6
]. Fu
zzy Better
Jo
b
First (FBJF) schedu
ling
alg
o
rith
m
lo
g
i
cally in
teg
r
at
es param
e
ters and
uses fuzzy
ranking approach to
det
e
rm
i
n
e t
h
e
next
m
o
st
wor
t
hy
jo
b t
o
be e
x
ecut
e
d has
be
en p
r
o
p
o
sed [
7
]
.
A fuzzy
sch
e
dul
i
n
g ap
p
r
oa
ch t
o
arran
g
e
real-time p
e
rio
d
i
c an
d
n
o
n
-
p
e
riodic task
s with
referen
ce to o
p
tim
a
l
u
tili
zatio
n
of d
i
stribu
ted
pr
ocess
o
rs
has
been
p
r
op
ose
d
[8]
.
I
n
t
h
ei
r
pa
per
,
a
n
at
t
e
m
p
t i
s
m
a
de t
o
ap
p
l
y
fuzzy
l
o
gi
c i
n
t
h
e
de
si
g
n
a
n
d
i
m
p
l
e
m
en
tatio
n
o
f
a m
o
d
i
f
i
ed
sch
e
du
ling
alg
o
r
ith
m
to
o
v
er
co
m
e
th
e sho
r
tco
m
in
g
o
f
w
e
ll-
known
sche
dul
i
n
g al
g
o
ri
t
h
m
s
. Fu
rt
h
e
rm
ore, m
a
ny dy
nam
i
c and
st
at
i
c
sched
u
l
i
ng al
g
o
r
i
t
h
m
s
[
9
-
10]
have
bee
n
p
r
op
o
s
ed
and
ap
p
lied
o
n
u
n
ip
ro
cesso
r syste
m
s. Also
mu
ltip
ro
cesso
r an
d
d
i
stribu
ted syste
m
s
h
a
v
e
b
een
considere
d
[11].
Regarding the
energy efficient schedu
ling,
Weiser et al.
[12] are c
o
nsid
ered the
pionee
rs
in that fiel
d
whe
r
e they expected the
DVS techniqu
e,
t
h
en Ya
o et
al
. [1
3]
have
pr
o
pose
d
a
n
o
p
t
i
m
a
l
st
ati
c
(of
f
l
i
n
e
)
sche
dul
i
n
g al
g
o
ri
t
h
m
by
cons
i
d
eri
n
g a set
o
f
ape
r
i
o
di
c j
o
b
s
on a
n
i
d
eal
p
r
oces
so
r.
Ho
w
e
ver
,
t
h
e p
r
o
b
l
e
m
of
DVS with
depende
nt tasks
because of s
h
ared res
o
urces
has been
first a
d
dresse
d in [14]. Jejuri
kar a
n
d Gupta
[1
5]
ha
ve p
r
o
pos
ed t
w
o al
g
o
ri
t
h
m
s
for
sc
hed
u
l
i
n
g fi
xed
pri
o
ri
t
y
, R
a
t
e
M
o
n
o
t
o
ni
c (
R
M
)
sche
dul
e
r
, t
a
sk
s
usi
n
g
pri
o
ri
t
y
cei
l
i
ng
pr
ot
oc
ol
(
P
C
P
)
de
sc
ri
be
d i
n
[
1
6]
as res
o
urce
ac
cess p
r
ot
oc
ol
.
They
have
c
o
m
put
ed
static slo
w
down
factors which
gu
aran
tee th
at all task
s will
m
eet
th
eir d
e
ad
lin
es tak
i
ng
in
to
accou
n
t
th
e
bloc
king tim
e
cause
d
by the t
a
sk sy
nchroniz
ation to acces
s sha
r
ed resources. In t
h
eir
first algorithm
,
critical
sectio
n
m
a
x
i
mu
m
sp
eed
(CSMS), th
ey
h
a
ve let th
e critica
l
sectio
n
s
(sect
io
n
s
d
eal with
sh
ared
resou
r
ces) t
o
b
e
ex
ecu
t
ed
at m
a
x
i
m
u
m
p
r
o
cesso
r speed and
t
h
ey
h
a
ve co
m
p
u
t
ed sl
o
w
do
wn
f
actor
s
f
o
r
ex
ecu
tin
g
non
cr
itical sect
io
ns. Th
e second alg
o
r
ith
m
,
co
n
s
tan
t
static sl
o
w
do
wn
(
C
SS)
,
co
m
p
u
t
es a u
n
i
fo
r
m
slo
w
d
o
wn
factor for all tasks a
n
d
for al
l sections
(criti
cal and
non-c
ritical) saving s
p
eed s
w
itches
occurre
d i
n
t
h
e first
algorithm
(CSMS).
The sam
e
aut
h
ors
[
17]
ha
ve
t
h
en e
x
t
e
nde
d
t
h
ei
r
pre
v
i
o
us
al
go
ri
t
h
m
s
(C
SM
S an
d C
S
S
)
t
o
ha
n
d
l
e
dy
nam
i
c pri
o
ri
t
y
, Earl
i
e
st
D
eadl
i
n
e Fi
rst
(
E
DF
) sc
he
dul
er, t
a
s
k
s
usi
n
g
dy
nam
i
c pri
o
ri
t
y
cei
l
i
ng p
r
ot
oc
ol
(DPC
P) s
h
o
w
n i
n
[
1
8]
. The
dy
nam
i
c pri
o
ri
t
y
cei
l
i
ng pr
ot
oc
ol
i
s
an e
x
t
e
nsi
on
of
or
i
g
i
n
al
p
r
i
o
ri
t
y
cei
l
i
n
g
pr
ot
oc
ol
t
o
dea
l
wi
t
h
dy
nam
i
c pri
o
ri
t
y
t
a
sks (
E
DF sc
he
dul
i
n
g)
. Jej
u
ri
kar a
n
d G
upt
a
[1
9]
h
a
ve al
so
pr
op
o
s
ed a
gene
ric algorit
h
m
that works
with
b
o
t
h
ED
F an
d R
M
sch
e
dul
e
r
s, a
n
d
t
h
ey
have i
n
t
r
o
d
u
ced t
h
e c
onc
ept
o
f
fre
que
ncy
i
n
h
e
ri
t
a
nce i
n
t
h
ei
r al
gori
t
h
m
.
Zhan
g an
d C
h
ans
o
n [2
0]
have w
o
r
k
e
d
on t
h
e sam
e
pro
b
l
e
m
(sche
d
ul
i
n
g
o
f
depe
n
d
ent
t
a
s
k
s) a
nd
p
r
o
p
o
se
d t
h
ree al
g
o
r
i
t
h
m
s
for e
n
er
g
y
effi
ci
ent
sc
h
e
dul
i
n
g
of
de
p
e
nde
nt
tasks with sha
r
ed res
o
urces over E
D
F sche
d
u
l
e
r, w
h
e
r
e t
h
e
y
have use
d
st
ack res
o
u
r
ce p
o
l
i
c
y
(SR
P
) pr
op
ose
d
by
B
a
ke
r [
2
1]
as res
o
u
r
ce ac
cess p
r
ot
oc
ol
.
The SR
P ca
n
han
d
l
e
st
at
i
c
a
n
d
dy
nam
i
c pri
o
ri
t
y
t
a
sks
(E
DF a
n
d
RM schedulers),
reduces
context s
w
itches
over
PCPs,
an
d is easy im
p
l
e
m
en
ted
.
Th
e first al
g
o
rithm
is th
e
sam
e
as C
SS fo
r ED
F sch
e
dul
e
r
p
r
o
p
o
se
d i
n
[
2
2]
beca
use t
h
ey
ha
ve
deri
v
e
d t
h
e
s
t
at
i
c
sl
owd
o
w
n
fact
or
d
i
rectly fro
m
t
h
e EDF sch
e
dulab
ility test wit
h
b
l
o
c
k
i
ng
time in
[23
]
:
∀
,
1
,
1
(5
)
wh
ere C is th
e co
m
p
u
t
atio
n
time (wo
r
st case ex
ecu
tion
ti
me W
C
ET),
D is th
e task
relativ
e d
e
ad
lin
e,
n i
s
t
h
e
n
u
m
b
er
of
t
a
sks
,
a
n
d
B
i
s
t
h
e
bl
oc
ki
ng
t
i
m
e t
h
at
can
be
defi
ne
d as
t
h
e m
a
xim
u
m
t
i
m
e
t
h
rou
g
h
whi
c
h
a high priority task can
be bl
ocked
by a low
pri
o
rity task due to excl
us
ive
access to sha
r
ed res
o
urce (i
ndex i
refers to th
e
b
l
o
c
k
e
d
h
i
gh
prio
rity task). The second
algo
rith
m
is th
e dual sp
eed
(DS)
alg
o
rith
m
.
Th
e m
a
in
co
n
c
ep
t
o
f
t
h
is alg
o
rith
m
is
u
s
ing
two
sp
eed
s
(L,
H) and
switch
i
ng
b
e
tween
t
h
em
. In
itially th
e alg
o
r
ith
m
o
p
e
rates
with
th
e low sp
eed L, an
d switches to
the h
i
gh spee
d
H as
s
o
on as
a
bloc
king
occurs. T
h
e last
alg
o
rith
m
is
th
e d
u
a
l sp
eed
dyn
amic
(online) reclaim
i
ng algorithm
whic
h dy
nam
i
ca
lly collects the residue
t
i
m
e
from
early
com
p
l
e
t
e
d jo
bs a
n
d
re
di
st
ri
but
es i
t
t
o
t
h
e
ot
he
r pe
n
d
i
n
g
jo
bs t
o
f
u
rt
her
red
u
ce t
h
e p
r
o
cesso
r
spee
d an
d achi
e
ve m
o
re ener
gy
savi
n
g
. T
h
e
n
t
h
e sam
e
autho
r
s [
2
4]
deve
l
ope
d t
h
ei
r
pre
v
i
o
us al
g
o
ri
t
h
m
s
t
o
achi
e
ve m
o
re
ener
gy
savi
ng
and al
s
o
t
o
fu
nct
i
on
wi
t
h
R
M
sched
u
l
e
r i
n
ad
di
t
i
on t
o
EDF sc
he
dul
e
r
. B
a
rua
h
[25] has take
n a closer look at ED
F-sc
he
duled syste
m
s in whic
h access
to
sha
r
ed
res
o
urces is a
r
bitra
t
ed by
the SRP. (He has referre
d
to such
sy
st
em
s as EDF+SR
P sc
h
e
dul
e
d
sy
st
em
s), w
h
ere
he ha
s pr
ove
d t
h
at
u
nde
r
cert
a
i
n
ass
u
m
p
t
i
ons E
D
F+SR
P i
s
o
p
t
i
m
a
l
,
but
he
has
not
t
a
ken e
n
e
r
gy
e
ffi
ci
ency
i
n
t
o
acc
ou
nt
. Lee et
al
.
[2
6]
h
a
v
e
d
e
v
e
l
o
p
e
d
the
d
u
a
l
sp
eed
(DS) algo
rith
m
p
r
opo
sed
by Zh
an
g and Ch
anson
[24
]
to u
s
e m
u
ltip
le sp
eeds
in
stead
of
two
sp
eed
s
to
g
e
t th
eir first
m
u
lti-sp
eed
(MS)
alg
o
rith
m
.
Also
t
h
ey h
a
v
e
pro
p
o
s
ed
an
enhan
ced
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 4
,
Au
gu
st 2
015
:
70
1
–
71
3
70
4
m
u
lt
i
-
speed (
E
M
S
) al
go
ri
t
h
m
t
h
at
furt
her r
e
duce
s
t
h
e en
ergy
di
ssi
pat
i
o
n by
co
nsi
d
e
r
i
ng
onl
y
rem
a
ini
n
g
bl
oc
ki
n
g
t
i
m
e to c
o
m
put
e a l
o
wer
spee
d.
3.
SYSTE
M
MO
DEL
3.
1.
Ta
sk Mo
del
In
t
h
is p
a
p
e
r,
fo
r
sim
p
lic
ity, real-ti
m
e p
e
rio
d
ic task
s are con
s
id
ered. Each task
τ
is c
h
ara
c
terized
by
th
e fo
llowing
param
e
ters:
The
release tim
e (r): t
h
e tim
e w
h
en
the tas
k
first release
d
.
The
peri
od
(T
)
:
t
h
e co
nst
a
nt
i
n
t
e
r
v
al
bet
w
ee
n
jo
bs
.
The relative de
adline (D):
the
maxim
u
m
acceptable
delay for task processi
ng.
Th
e co
m
p
u
t
atio
n ti
m
e
(C): the wo
rst case execu
tio
n tim
e (
W
CET) of an
y
jo
b.
The
bl
oc
ki
n
g
t
i
m
e
(B
):
t
h
e m
a
xi
m
u
m
tim
e a task ca
n
be
bl
oc
ked
by
a
n
ot
he
r
l
o
we
r
pri
o
ri
t
y
t
a
sk.
In th
is
p
a
p
e
r
we con
s
id
er
well fo
rm
ed
task
s t
h
at satisfy th
e
co
nd
itio
n
:
0
≤
C
≤
D
≤
T.
A 3-t
upl
e
τ
={C, D, T} repre
s
ents each task
, the relative deadline is assumed to
be the sam
e
as
the period in
all illu
strativ
e ex
am
p
l
es.
3.2.
Processor Model
The t
a
sks are
sche
dul
e
d
o
n
a si
ngl
e DV
S pr
ocess
o
r t
h
at
sup
p
o
rt
s va
ri
a
b
l
e
fre
que
ncy
(spee
d
) an
d
v
o
ltag
e
lev
e
ls co
n
tinuo
usly, i.e. DVS
p
r
o
c
esso
rs can
o
p
e
rate at an
y sp
eed
/vo
ltag
e
in
i
t
s rang
e (id
eal
). Of
course, practical DVS
processors s
u
pports disc
rete
sp
eed
/
v
o
ltag
e
l
e
v
e
ls
(non
ideal). So
, th
e
d
e
sired
sp
eed
/
vo
ltag
e
o
f
th
e id
eal
DVS
pro
cessor i
s
ro
und
ed
to
t
h
e
neare
s
t hi
gher speed/
v
o
l
t
a
g
e
lev
e
l th
e practical
DV
S p
r
oces
so
r
sup
p
o
rts. T
h
e
tim
e
(energy
)
r
e
qui
red to c
h
a
nge t
h
e proces
sor s
p
ee
d is ve
ry s
m
all co
m
p
ared t
o
th
at requ
ired
to
co
m
p
lete a t
a
sk
. It is assumed
th
at th
e v
o
ltag
e
ch
ang
e
o
v
e
rh
ead, si
m
i
lar to
th
e co
n
t
ex
t switch
ove
rhead, is i
n
corporated i
n
the tas
k
c
o
mputation tim
e.
In th
is
p
a
p
e
r, it is assu
m
e
d
th
at th
e
pro
c
esso
r’s
m
a
xim
u
m
speed i
s
1 a
n
d al
l
ot
her
spee
ds
are
no
rm
alized with
respect
to
th
e ma
x
i
mu
m s
p
e
e
d
.
4.
MULTI-SPE
ED AL
GORITHM
Mu
lti-sp
eed
(MS) algo
rit
h
m p
r
op
osed b
y
Lee et al
. [25
]
is a b
l
o
c
k
i
n
g
aware
sch
e
du
lin
g algo
rith
m
with
non-pree
m
p
tible critical sections
using SRP
as res
o
urc
e
access protoc
ol.
The MS algorithm can be conside
r
ed as an
extensi
on
of dual sp
ee
d (DS) algorithm
[24], where the
diffe
re
nce bet
w
een t
h
e two
algorithm
s
is
that MS al
gorithm
uses
m
a
ny speeds (low s
p
eed
SL and
m
u
ltiple
high s
p
eeds Sm
where 1
≤
m
≤
n
) i
n
st
ead
o
f
t
w
o
spee
ds
(l
o
w
s
p
eed
L a
n
d
one
hi
gh
spee
d
H)
i
n
DS al
go
ri
t
h
m
.
Lik
e
DS al
g
o
ri
th
m
,
MS alg
o
rith
m
in
itia
lly st
arts with
th
e low sp
eed
SL then
it switch
e
s t
o
o
n
e
of
h
i
gh
sp
eeds
as soon as a
bl
ocki
ng
occ
u
rs
.
The
high spee
d to
whic
h
the
MS algorithm
switches is
det
e
rm
ined according to
t
h
e bl
oc
ki
n
g
t
a
sk, i
.
e. eac
h bl
ocki
ng t
a
s
k
τ
m
has i
t
s
own hi
gh s
p
eed Sm
, and acc
or
di
n
g
t
o
t
h
e bl
oc
ki
n
g
t
a
sk,
th
e algo
rith
m
switch
e
s t
o
the con
v
e
n
i
en
t
hig
h
sp
eed
.
Th
e lo
w sp
eed
SL, wh
ich is ex
actly th
e sam
e
as low
sp
eed
L in
DS alg
o
rith
m
,
is t
h
e op
tim
a
l
lo
west sp
eed
with
wh
ich
all task
s can
b
e
sch
e
d
u
led
witho
u
t
m
i
ssin
g
any dea
d
line
,
a
n
d it is de
rive
d from
the plain ED
F
sc
hedula
bility test without
sha
r
ed res
o
urces:
(6
)
The
hi
g
h
spe
e
d Sm
for a
bl
oc
ki
n
g
t
a
s
k
τ
m
is d
e
riv
e
d
as in
DS alg
o
rith
m
fro
m
th
e EDF
sch
e
d
u
l
ab
ility t
e
st with
sh
ared reso
urces and
SRP pro
t
o
c
o
l:
∀
,1
,
(7
)
Whe
r
e the
bl
ocking tim
e Bm here is t
h
e maxim
u
m
tim
e (
l
ength of critical section
of
τ
m
)
th
r
o
ugh
wh
ich
a lo
w prio
rity task
τ
m
can bloc
k anot
her
high pri
o
ri
ty task due
to exclusi
v
e access to share
d
re
source
and
unl
i
k
e m
e
nt
i
one
d
bef
o
re
,
i
nde
x m
refer
s
t
o
t
h
e bl
oc
ki
ng t
a
s
k
(l
o
w
p
r
i
o
ri
t
y
t
a
sk)
.
T
h
e ab
o
v
e m
e
nti
one
d
spee
ds S
L
a
n
d
Sm
have t
o
sat
i
s
fy
t
h
e c
o
ndi
t
i
on:
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Process
o
r
S
p
e
e
d C
ont
r
o
l
f
o
r
Pow
e
r Re
d
u
ct
i
o
n
of
Real
-
T
i
m
e Syst
e
m
s
(
Med
hat
H Aw
a
dal
l
a
)
70
5
1
(8
)
MS algorithm
ends the
high
s
p
eed
interval whe
n
t
h
e dead
line of the
blocking ta
s
k
is reached or t
h
e
pr
ocess
o
r
bec
o
m
e
s i
d
l
e
. In s
o
m
e
real
tim
e t
a
sks [2
3]
, M
S
im
pro
v
es t
h
e ener
gy
co
ns
um
pt
i
on h
o
we
ver i
n
ot
he
rs t
a
s
k
s, t
h
e t
i
m
i
ng co
ns
traints
are not guarantee
d
.
5.
FUZ
Z
Y
INFERENCE SYSTEMS
A f
u
zzy
i
n
fer
e
nce sy
st
em
(FIS)
t
r
i
e
s t
o
de
ri
ve a
n
s
w
ers
f
r
om
a kn
o
w
l
e
dge
base
by
us
i
ng a
f
u
zzy
i
n
fere
nce
en
gi
ne.
The
i
n
fere
n
ce en
gi
ne
w
h
i
c
h i
s
co
nsi
d
e
r
e
d
t
o
be
t
h
e
b
r
ai
n
o
f
t
h
e e
xpe
rt
s
y
st
em
s pro
v
i
d
e
s
t
h
e
m
e
t
hod
ol
o
g
i
e
s
fo
r rea
s
o
n
i
n
g
aro
u
nd t
h
e i
n
fo
rm
ati
on i
n
t
h
e
kn
o
w
l
e
d
g
eba
s
e an
d f
o
rm
ul
at
ing t
h
e r
e
sul
t
s
.
Fuzzy
l
ogi
c i
s
a
n
ext
e
nsi
o
n
of B
o
o
l
ean l
o
gi
c deal
i
ng
wi
t
h
t
h
e
c
once
p
t
of
part
i
a
l
t
r
ut
h t
h
at
d
e
not
es t
h
e e
x
t
e
nt
t
o
whi
c
h a pr
op
o
s
i
t
i
on i
s
t
r
ue. Whe
r
eas cl
assi
cal
l
ogi
c hol
ds
t
h
at
every
t
hi
n
g
can be exp
r
ess
e
d i
n
bi
na
ry
t
e
rm
s (0
or 1, black or white,
yes or no),
fu
zzy logic replaces B
oole
a
n tr
uth values
with
the de
gre
e
of
t
r
ut
h. Degree of
t
r
ut
h i
s
oft
e
n em
pl
oy
ed t
o
capt
u
r
e t
h
e im
preci
se
m
odes of
reaso
n
i
n
g t
h
at
pl
ay
an essent
i
a
l
rol
e
i
n
t
h
e
hum
a
n
ab
ility to
m
a
k
e
d
ecision
s in
an
env
i
ron
m
en
t o
f
un
certain
t
y an
d im
p
r
ecisio
n
.
Th
e m
e
mb
ersh
ip fun
c
tion
o
f
a
fuzzy set c
o
rre
s
ponds t
o
the i
ndicator
function of the
classical sets. It ca
n
b
e
ex
pr
e
s
s
e
d
in
th
e fo
r
m
o
f
a c
u
rve
that defi
nes
how each point i
n
the i
n
put s
p
a
ce is
m
a
ppe
d to a m
e
m
b
ership val
u
e
or a
de
gree
of trut
h
between
0 an
d
1. T
h
e
m
o
st
co
m
m
on shape
o
f
a m
e
m
b
ershi
p
f
u
n
c
t
i
on i
s
t
r
i
a
n
g
u
l
a
r, al
t
h
o
u
g
h
t
r
apez
oi
dal
a
nd
bell
curves are als
o
use
d
. T
h
e input sp
ace is som
e
times referre
d to as the
unive
rse of
discourse [6].
Fuzzy
Infere
nce Syste
m
s are conce
p
tually very
sim
p
le. An
FIS co
nsists o
f
an
i
n
pu
t stage, a processing stage
,
and an
out
put
stage. T
h
e input stage
maps the i
n
put
s
, s
u
ch as
d
e
adlin
e, ex
ecu
tion ti
m
e
, an
d
so
on
, t
o
t
h
e ap
pr
op
r
i
ate
m
e
m
b
ershi
p
fu
nct
i
o
n
s
an
d t
r
u
t
h val
u
e
s
. T
h
e
pr
ocessi
ng st
a
g
e i
n
vo
kes eac
h ap
p
r
o
p
ri
at
e r
u
l
e
an
d ge
ne
ra
t
e
s a
resu
lt fo
r each. It th
en
co
m
b
in
es th
e resu
lts of th
e ru
les.
Finally, th
e o
u
t
p
u
t
stag
e conv
erts th
e co
m
b
in
ed
resu
lt
back i
n
t
o
a spe
c
i
f
i
c
out
p
u
t
val
u
e [
6
]
.
As
di
scusse
d earl
i
e
r, t
h
e pro
c
essing
stag
e, wh
ich
is called
th
e in
feren
ce
engi
ne, i
s
base
d
on a
col
l
ect
i
o
n
o
f
l
o
gi
c r
u
l
e
s i
n
t
h
e
f
o
rm
of
IF-T
HEN state
m
ents, where the IF pa
rt is
called
the "antece
de
nt" and the
THE
N
pa
rt is called th
e "co
n
sequ
en
t".
Typical fuzzy infe
rence
s
u
bsystem
s
have dozen
s
of rules. T
h
ese
rules are
store
d
i
n
a
knowledgeba
s
e. An exam
ple of
fu
zzy IF THEN
ru
les is: IF d
e
ad
lin
e is
early th
en
p
r
iority is h
i
g
h
,
i
n
wh
ich
d
ead
lin
e an
d
p
r
i
o
rity are ling
u
i
stics
v
a
riables and
p
r
ior
ity and
h
i
gh
are ling
u
i
stics t
e
rm
s. Th
e fi
v
e
step
s
towa
rd a fuzzy
infe
rence
are
a
s
follows:
1.
Fu
zzifying
i
n
pu
ts
2.
Ap
pl
y
i
ng
f
u
zz
y
ope
rat
o
rs
3.
Ap
pl
y
i
ng
i
m
pl
icat
i
on m
e
t
hods
4.
Ag
gr
egat
i
n
g o
u
t
p
ut
s
5.
Defu
zzifying
resu
lts
B
e
l
o
w i
s
a
qui
ck
revi
e
w
of
t
h
ese st
e
p
s.
H
o
weve
r,
a
det
a
i
l
e
d st
udy
i
s
n
o
t
i
n
t
h
e sc
o
p
e
o
f
t
h
i
s
pa
per
.
Fu
zzifying
t
h
e in
pu
ts is the
act o
f
d
e
term
i
n
ing
th
e d
e
g
r
ee to
wh
ich
th
ey b
e
lon
g
to
each
o
f
t
h
e ap
pro
p
riate
fuzzy sets
via me
m
b
ership
functions.
Once
the inputs
have been fuzzifie
d
, the
de
gree t
o
which
each
part
of
the antecede
n
t has bee
n
satisfied for each rule is known.
If the antecedent
of a give
n rul
e
has
m
o
re tha
n
one
part, the fuzzy ope
rator is applied to
obtain one value that represe
n
ts the re
sult of the ant
eceden
t for tha
t
rule.
The im
plica
tion function then
m
odifies
that out
put fuzzy set to the degre
e
specified by
the antecede
n
t. Since
d
ecision
s are
based
on
th
e testin
g
o
f
all of the ru
les in
the
F
u
zzy
I
n
f
e
re
nce
Su
bsy
s
tem
(FI
S
),
the
res
u
lts
fr
o
m
each rule m
u
st be com
b
ined
in orde
r to m
a
ke the fi
nal de
cision.
Aggreg
ation is the
process
by which t
h
e
fuzzy sets that
represent the
out
puts
of eac
h rule are
processes into a s
i
ngle fuzzy
set. Th
e inpu
t for th
e
defuzzification proces
s is the
aggre
g
ated
ou
tp
u
t
fu
zzy set an
d th
e
ou
tpu
t
i
s
th
en
a si
ng
le
crisp
v
a
lu
e [6
]. Th
is
proce
d
ure can
be summ
arized as fo
llo
ws:
map
p
i
n
g
inpu
t ch
aracteristics to
in
pu
t m
e
m
b
e
r
sh
i
p
fu
n
c
tion
s
, in
pu
t
me
m
b
ersh
ip
fu
n
c
tion
t
o
ru
l
e
s, ru
les t
o
a set of
o
u
t
put
cha
r
acteristics, output c
h
aracteristics to
out
put
me
m
b
ersh
ip fun
c
tio
ns, and
t
h
e ou
tpu
t
m
e
mb
ersh
ip fun
c
tion
to a
sing
le crisp
v
a
lu
e
d
outp
u
t
. T
h
er
e
ar
e tw
o
com
m
on i
n
fer
e
nce m
e
t
h
o
d
s [6]
.
T
h
e fi
rst
one i
s
cal
l
e
d M
a
m
d
ani
'
s fuzzy
i
n
ference
m
e
t
hod p
r
op
o
s
ed b
y
Ebra
hi
m
M
a
mdani
[
8
]
an
d t
h
e seco
n
d
o
n
e
i
s
Takagi
-
S
u
g
en
o
-
Ka
n
g
, o
r
sim
p
l
y
Sugen
o
, m
e
t
hod
of
fuzz
y
in
feren
c
e in
trod
u
c
ed in
[9
].
Th
ese two
m
e
th
od
s are t
h
e
sam
e
in
m
a
n
y
resp
ects,
su
ch as th
e
p
r
o
cedu
r
e of
fuzzify
in
g t
h
e
inp
u
ts an
d
fuz
z
y
ope
rato
rs.
The m
a
in
difference betwee
n
Mam
d
ani
and
Su
geno
is that th
e
Su
gen
o
’
s
out
p
u
t
m
e
m
b
ershi
p
fu
nct
i
o
ns a
r
e
ei
t
h
er l
i
n
ea
r
or c
o
nst
a
nt
b
u
t
M
a
m
d
ani
’
s i
n
fe
rence
ex
pe
ct
s t
h
e
out
put
m
e
m
b
ershi
p
f
unct
i
o
ns
t
o
be
f
u
zzy
set
s
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 4
,
Au
gu
st 2
015
:
70
1
–
71
3
70
6
6.
THE PROPOSED
MODEL
I
n
t
h
e pr
opo
sed
m
o
d
e
l, th
e i
n
pu
t stag
e consists o
f
fou
r
i
n
pu
t v
a
riab
les i.e. wo
rst ex
ecu
tio
n
tim
e,
deadl
i
n
e
,
bl
oc
k
i
ng t
i
m
e and ar
ri
vi
n
g
t
i
m
e as
sho
w
n i
n
Fi
g
u
r
e
1.
Wo
rst
e
x
e
c
ut
i
o
n
t
i
m
e
i
s
the act
ual
am
ou
nt
o
f
ti
m
e
a task
requ
ires
o
n
CPU t
o
g
e
t ex
ecu
t
ed
, b
l
o
c
k
i
ng
tim
e
is h
o
w m
u
ch
time a task
can
wait b
e
fore g
e
t
tin
g
a
chance
to get execute
d, Dea
d
line
re
pr
esen
t
s
th
e fi
n
a
l ti
me li
m
i
t b
e
fore
wh
at a task
has to
g
e
t termin
ated
wh
ereas th
e arriv
i
n
g
tim
e i
s
th
e ti
m
e
at
wh
ich
th
e
j
ob is r
ead
y to
b
e
assign
ed
to
th
e pro
cesso
r. Th
e
com
b
i
n
at
i
on o
f
fo
ur i
n
p
u
t
par
a
m
e
t
e
rs deci
de
s t
h
e jo
b p
r
iori
ty and the appropriate
process
o
r s
p
eed t
o
execute
it.
Fi
gu
re
1.
I
n
fe
r
e
nce sy
st
em
bl
ock
di
a
g
ram
M
e
m
b
ershi
p
f
unct
i
o
ns
descri
be t
h
e de
gree t
o
w
h
i
c
h eac
h i
n
p
u
t
pa
ram
e
t
e
r
repre
s
ent
s
i
t
s
associ
at
i
o
n
.
Li
ng
ui
st
i
c
va
ri
abl
e
s are
assi
g
n
ed
t
o
eac
h i
n
put
par
a
m
e
t
e
r, to
rep
r
esen
t t
h
is asso
ciation
.
Worst ex
ecu
tion
tim
e
i
s
cat
ego
r
i
zes
as Lo
w, M
e
di
um
and Hi
gh
.
Sim
i
l
a
rl
y
bl
ocki
n
g
t
i
m
e
i
s
defi
ne
d i
n
t
h
e s
a
m
e
way
.
H
o
weve
r,
Deadl
i
n
e a
n
d
Ar
ri
vi
n
g
t
i
m
e
are de
fi
ne
d as
earl
y
, m
e
di
u
m
and l
a
t
e
. T
h
e
out
put
param
e
ters,
jo
b
pri
o
ri
t
y
and
pr
ocess
o
r s
p
ee
d are de
fi
ne
d as l
o
w, m
e
di
u
m
and hi
gh as de
pi
ct
ed i
n
Fi
g
u
r
e
2. Tabl
e 1 de
pi
ct
s t
h
e val
u
e
s
use
d
for co
nstru
c
ting
th
ese
v
a
riou
s fu
zzy m
e
m
b
ersh
ip fu
n
c
tion
s
.
Fi
gu
re
2.
M
e
m
b
ers
h
i
p
f
u
nct
i
o
ns
of
t
h
e
sy
st
em
param
e
t
e
rs
Fu
zzy ru
les try to
co
m
b
in
e these
param
e
te
rs as t
h
ey are
connect
ed in
real worlds
. Some of thes
e
rul
e
s a
r
e m
e
nt
i
one
d i
n
Ta
bl
e
1:
For i
n
st
ance,
r
u
l
e
no
-
6
an
d r
u
l
e
no
-
21
(Ta
b
l
e
2)
a
r
e activated for t
h
e cont
ro
l of job
p
r
i
o
rity an
d
pr
ocess
o
r
spee
d. T
h
e
res
u
l
t
a
n
t
pri
o
ri
t
y
an
d
pr
ocess
o
r
spee
d are
al
so
gi
ve
n i
n
Fi
g
u
re
3,
fr
om
whi
c
h t
h
e cri
s
p
out
put
val
u
e
s
can
be
det
e
rm
ined
. I
n
f
u
zzy
i
n
fe
rence
sy
st
em
s, t
h
e num
ber o
f
rul
e
s
has
a di
rect
e
ffect
on
i
t
s
ti
m
e
co
m
p
lex
ity. Th
erefo
r
e,
hav
i
ng
fewer
ru
l
e
s m
a
y resu
lt in
a
b
e
tter system
p
e
rform
an
ce.
In
o
u
r
p
r
o
p
o
s
ed
app
r
o
a
ch
, a
n
e
w
l
y arriv
e
d
task
w
ill b
e
add
e
d
t
o
th
e input o
f
job
qu
eu
e. Th
is qu
eu
e
h
a
s th
e
rem
a
i
n
ing
task
s
from last cyc
l
e t
h
at h
a
s
n
o
t
yet b
een
assi
g
n
e
d
.
Th
e fo
llowin
g
al
g
o
rith
m
will b
e
execute
d:
L
ow
Medi
um
H
ig
h
ti
m
e
Bl
ock
i
ng
L
ow
M
edium
H
ig
h
ti
m
e
ex
ecu
t
i
on
cas
e
wo
r
s
t
Medi
um
Medi
um
Slo
w
Fast
P
r
io
rity
sp
eed
P
r
o
c
e
sso
r
L
ow
H
ig
h
E
ar
l
y
Medi
um
L
at
e
ti
m
e
A
rri
vi
ng
E
ar
l
y
Medi
um
L
at
e
Deadlin
e
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Process
o
r
S
p
e
e
d C
ont
r
o
l
f
o
r
Pow
e
r Re
d
u
ct
i
o
n
of
Real
-
T
i
m
e Syst
e
m
s
(
Med
hat
H Aw
a
dal
l
a
)
70
7
Tabl
e
1.
Val
u
e
s
use
d
fo
r c
o
ns
t
r
uct
i
n
g
vari
ou
s f
u
zzy
m
e
m
b
ershi
p
F
u
nct
i
o
n
s
Variab
les
Earl
y
Med
i
u
m
Late
Deadline
1 2.
5 5
2 3 8
3 6
10
(Para
m
ete
r
s f
o
r de
adline)
Variables
Low
Mediu
m
High
Wo
rs
t c
a
s
e
execution
ti
m
e
1 2.
5 5
2 3 8
3 6
10
(Para
m
ete
r
s f
o
r wo
rst case
execution ti
m
e
)
Variab
les
Earl
y
Med
i
u
m
Late
Ar
r
i
ving
tim
e
0.
0 0.
6 2.
0
0.
6 2.
0 3.
4
2.
0 3.
4 4.
0
(
P
a
r
a
m
e
t
er
s for
a
rriving tim
e
)
Variables
Low
Mediu
m
High
Blocking
tim
e
0.
0 0.
8 2.
0
0.
8 2.
0 3.
2
2.
0 3.
2 4.
0
(
P
ar
a
m
eter
s for
blocking tim
e
)
Variables
Low
Mediu
m
High
Pr
ior
ity 1
3.
5
6.
5
2.
5 5.
5
8.
5
4 7
10
(Para
m
ete
r
s f
o
r p
r
i
o
rity)
Var
i
ables
Slow
M
e
diu
m
Fast
Processor
speed
0.
1 0.
35
0.
65
0.
25
0.
55
0.
8
0.
4 0.
7
1
(Para
m
ete
r
s f
o
r pr
ocessor speed)
Tabl
e 2. Som
e
of
del
e
ope
d fu
zzy
rul
e
s
Fu
zz
y
Rule
No.
Deadline
Worst
case
execution
ti
me
Arriving
ti
me
Block
i
ng
ti
me
priority Processor
speed
1
E
a
r
l
y L
o
w
E
a
r
l
y L
o
w
High
Slow
2
E
a
r
l
y L
o
w
E
a
r
l
y M
e
diu
m
High
M
e
diu
m
3 E
a
r
l
y
M
e
diu
m
M
e
diu
m
L
o
w
High
M
e
diu
m
4
M
e
diu
m
M
e
diu
m
M
e
diu
m
L
o
w
M
e
diu
m
M
e
diu
m
5
M
e
diu
m
M
e
diu
m
M
e
diu
m
High
M
e
diu
m
Fast
6
M
e
diu
m
High
M
e
diu
m
High
M
e
diu
m
Fast
7
L
a
te High
L
a
te High
L
o
w
Fast
8
L
a
te High
L
a
te M
e
diu
m
L
o
w
M
e
diu
m
9
Late
Lo
w
Late
Med
i
u
m
Lo
w
Med
i
u
m
10
E
a
r
l
y
L
o
w
L
a
te
M
e
diu
m
High
M
e
diu
m
11
E
a
r
l
y
High
M
e
diu
m
L
o
w
High
M
e
diu
m
12
E
a
r
l
y
High
M
e
diu
m
High
High
Fast
13
M
e
diu
m
L
o
w
L
a
te
High
M
e
diu
m
Fast
1
4
Late
Lo
w
Late
Hig
h
Lo
w
Fast
15
M
e
diu
m
L
o
w
E
a
r
l
y
M
e
diu
m
M
e
diu
m
M
e
diu
m
16
M
e
diu
m
M
e
diu
m
M
e
diu
m
M
e
diu
m
M
e
diu
m
M
e
diu
m
17
E
a
r
l
y
High
L
a
te
L
o
w
High
L
o
w
18
M
e
diu
m
High
High
L
o
w
M
e
diu
m
L
o
w
19
L
a
te
High
E
a
r
l
y
High
L
o
w
Fast
2
0
Late
Lo
w
Late
Lo
w
Lo
w
Lo
w
21
L
a
te M
e
diu
m
L
a
te M
e
diu
m
L
o
w
M
e
diu
m
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 4
,
Au
gu
st 2
015
:
70
1
–
71
3
70
8
Fi
gu
re 3.
Act
i
v
at
i
on of
r
u
l
e
6 and
2
1
L
oop
1
.
For each
read
y task
, feed
th
e d
e
ad
lin
e, ex
ecu
tion
tim
e, b
l
o
c
k
i
ng
tim
e
an
d arriv
i
ng
ti
me in
to
th
e
i
n
fere
nce
en
gi
ne. C
o
nsi
d
e
r
t
h
e o
u
t
p
ut
o
f
i
n
fe
rence
m
odul
e a
s
p
r
i
o
ri
t
y
of t
h
e t
a
sk a
n
d t
h
e
pr
ocess
o
r
s
p
ee
d.
2
.
Ex
ecu
te th
e
task
with
h
i
g
h
e
st p
r
iority with
th
e d
ecid
e
d
speed
un
less it is
b
l
o
c
k
e
d
b
y
lo
wer priority
j
o
b
un
til a sch
e
d
u
ling
ev
en
t
occu
rs (a ru
nn
ing
task
fi
n
i
sh
es, a n
e
w task
arri
v
e
s).
3.
Update t
h
e s
y
ste
m
states.
End Loop
We chose to
treat deadline
tim
e
as
th
e m
o
st
i
m
p
o
r
tant p
r
in
cip
l
es
beh
i
nd
choo
sing
a task
for
sche
dul
i
n
g
bec
a
use t
h
e m
a
jor
pu
rp
ose
of
ha
rd
real
-t
i
m
e sched
u
l
i
n
g i
s
t
o
m
eet
t
h
e deadl
i
ne. A
f
t
e
r t
h
i
s
,
wo
rst
ex
ecu
tion
tim
e
and
th
en
earli
est arriv
i
n
g
time. Howev
e
r i
f
th
e l
o
west
p
r
i
o
rity jo
b is on
l
y
av
ailab
l
e job, it will
b
e
assign
ed
to th
e p
r
o
cessor till an
o
t
h
e
r
h
i
g
h
e
r
p
r
iority
jo
b
arri
v
e
s. Si
nce th
e p
a
p
e
r
has ano
t
h
e
r
ob
jectiv
e
wh
ich
is to
red
u
c
e th
e
p
o
wer con
s
u
m
p
tio
n
,
after
d
ecid
i
ng wh
ich
j
o
b
will b
e
assign
ed
to
th
e
p
r
o
cessor, the
sy
st
em
wi
ll
deci
de at
whi
c
h spee
d t
h
e pr
oc
essor s
h
oul
d
perform
.
The process
o
r s
p
eed
is
m
a
inly affected by
spee
d
of t
h
e
bl
ocki
ng
t
i
m
e
of
t
h
e l
o
wer
p
r
i
o
r
i
t
y
t
a
sks.
7.
Experiments a
nd Discuss
i
on
To
illu
strate th
e fu
zzy app
r
o
a
ch
and
th
e contrib
u
tion
of th
is p
a
p
e
r. Ex
am
p
l
es i
m
p
l
e
m
en
ted
in
[23
]
are rep
eated
fo
r the sak
e
o
f
q
u
a
litativ
e com
p
ariso
n
an
d
o
t
h
e
r task
s
h
a
v
e
b
e
en
p
e
rform
e
d
to
ad
dress th
e
g
e
n
e
ralizatio
n
o
f
app
l
yin
g
fuzzy lo
g
i
c as a sch
e
d
u
l
er appro
a
ch
an
d
its
cap
ab
ility to
min
i
mize th
e en
erg
y
con
s
um
pt
i
on
o
f
p
o
w
e
re
d real
t
i
m
e
sy
st
em
s.
The fi
rst
ha
rd
real ti
m
e
syste
m
with
th
ree t
a
sks is c
onsi
d
e
r
ed as
fo
llowing
:
τ
1
={1
,4
,
4
},
τ
2
={1.
5 ,
1
2 ,
1
2
},
τ
3
={3 ,2
4 ,24
}
The a
rrival times and critical sections
of t
h
e
thr
ee task
s wit
h
in
t
h
e least commo
n
m
u
lt
ip
le (LCM)
o
f
p
e
r
i
o
d
s
ar
e show
n in
f
i
gu
r
e
4(a)
.
Acco
r
d
i
n
g t
o
t
h
e de
vel
o
pe
d i
n
fe
rence sy
st
e
m
,
τ
1 has t
h
e hi
g
h
est
p
r
i
o
ri
t
y
, fol
l
o
wed
by
τ
2
and
lastly
τ
3. T
h
e
res
u
l
t
a
nt
l
o
w s
p
eed
SL i
s
e
q
u
a
l
0.
5,
w
h
i
c
h i
s
t
h
e sam
e
as cal
cul
a
t
e
d ba
se
d
on
eq
uat
i
o
n
6 t
h
at
represen
ts
th
e p
r
o
cesso
r u
tilizatio
n
fact
o
r
U=
∑
C
/
T [2
6]
. T
h
ere a
r
e t
w
o bl
ocki
ng t
a
s
k
s i
n
t
h
i
s
exam
pl
e:
τ
2 t
h
at
can bl
ock
hi
g
h
e
r pri
o
ri
t
y
t
a
sk
τ
1 fo
r m
a
xim
u
m
t
i
m
e
B
2
=1.5
and
τ
3 t
h
at
can bl
oc
k
hi
g
h
er
pri
o
ri
t
y
t
a
sks
τ
1
and
τ
2
for m
a
x
i
m
u
m
ti
me B3
=3
.
So
, th
ere will be two h
i
g
h
sp
ee
d
s
(S2
,
S3) acco
rd
ing
t
o
th
ese two b
l
o
c
k
i
n
g
tasks,
an
d
th
ese two
sp
eed
s
are S2
= 0
.
6, and
S3
= 0
.
92
. Th
e two
sp
eeds (S2, S3
) also
satisfy th
e co
nd
ition
(7),
whe
r
e 0.
5
≤
S2
≤
1
a
n
d 0.
5
≤
S3
≤
1.
activated
is
1a
-
Table
from
6
-
Rule
activated
is
1b
-
Table
from
21
-
Rule
time
Blocking
Deadline
time
execution
case
Worst
21
-
Rule
an
d
6
-
Rule
from
priority
Resultant
21
-
Rule
an
d
6
-
Rule
fro
m
speed
processor
Resultant
time
Arriving
Deadline
time
execution
case
Worst
time
Blocking
time
Arriving
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Process
o
r
S
p
e
e
d C
ont
r
o
l
f
o
r
Pow
e
r Re
d
u
ct
i
o
n
of
Real
-
T
i
m
e Syst
e
m
s
(
Med
hat
H Aw
a
dal
l
a
)
70
9
Fi
gu
re
4.
(a
) T
a
sk set
desc
ri
pt
i
on:
a
rri
val
t
i
m
e
s, c
o
m
put
at
i
on t
i
m
es, and c
r
i
t
i
cal
sect
i
ons.
(b
) M
S
al
g
o
ri
t
h
m
.
(c) Fuzzy
l
ogic
.
The rect
a
n
gl
es rep
r
ese
n
t
t
h
e
pr
ocessi
ng
of
t
a
sks (
j
obs
)
by
C
P
U
wh
er
e t
h
e ve
rt
i
cal
di
m
e
nsi
o
n
rep
r
ese
n
t
s
t
h
e
pr
ocess
o
r
spe
e
d, a
nd t
h
e
h
o
ri
z
ont
al
dim
e
nsion re
presents the exec
ution tim
e elapsed for
processi
ng tas
k
s accordi
ng t
o
their
W
C
ET
s and the proc
esso
r s
p
ee
d. It
is clearly noted that the area of the
rectangles of t
h
e jobs of t
h
e
sa
m
e
task is
the sam
e
d
u
e
to
th
at a task
always tak
e
s th
e sam
e
n
u
m
b
er o
f
ex
ecu
tion
cycles wh
ich equ
a
l
s
to
p
r
o
cessor sp
eed m
u
ltip
lie
d
b
y
elap
sed
ti
me.
Back
to
figu
re
4
(
a), it is assu
med
th
at
τ
3 is
released be
fore
τ
1
with
eno
ugh
ti
m
e
(
ε
) to
lo
ck
th
e shred
reso
u
r
ce. Whe
n
task
τ
1
is rel
eased
, it will be b
l
o
c
k
e
d
b
y
th
e lower
p
r
i
o
ri
ty task
τ
3 due
to exclusive ac
cess to
share
d
res
o
urc
e
(accordi
ng to SRP, a task may be bloc
ked
whe
n
it is released, a
nd as s
o
on as it starts,
it can
n
o
t
b
e
b
l
o
c
k
e
d). So
, t
h
e pro
c
esso
r will start ex
ecu
tin
g
τ
3
w
ith
h
i
gh
sp
eed
S3
.
A
t
ti
m
e
t=4
,
w
h
en
th
e second
jo
b o
f
t
a
sk
τ
1
is released
, it is
also
b
l
o
c
k
e
d
b
y
th
e lo
wer
prio
rity task
τ
2 rel
eased be
f
o
re
i
t
wi
t
h
enoug
h t
i
m
e
(
ε
) t
o
loc
k
t
h
e
shre
d
res
o
u
r
ce.
MS algorithm
whic
h
operat
es
wi
t
h
hi
g
h
spe
e
d S3 swi
t
c
hes
t
o
t
h
e
m
a
xim
u
m
of t
h
e t
w
o h
i
gh spee
ds
(S3,S2
) wh
ich
is S3
, an
d MS
alg
o
rith
m
en
d
s
th
is
h
i
gh
sp
eed
in
terv
al and
switch
e
s t
o
th
e lo
w sp
eed SL at
ti
m
e
t=6
.
5 wh
en
th
e pr
o
cessor
b
e
co
m
e
s id
le as sho
w
n
i
n
f
i
gu
r
e
4(
b)
.
At ti
m
e
t=1
6
,
wh
en
th
e fift
h
j
o
b
of task
τ
1
is released
, it
will b
e
b
l
o
c
k
e
d
b
y
th
e second
jo
b
o
f
task
τ
2, an
d M
S
al
go
ri
t
h
m
swi
t
c
hes t
o
t
h
e hi
g
h
spee
d S2 a
nd
end
s
t
h
i
s
hi
g
h
spee
d i
n
t
e
rv
al
whe
n
t
h
e p
r
oc
esso
r
b
eco
m
e
s id
le.
The sam
e
scenario is ha
ppe
ne
d in the case of the
p
r
o
p
o
sed
fuzzy
l
o
gi
c ap
pr
oac
h
, as sh
o
w
n i
n
fi
g
u
r
e
4
(
c), it starts with
h
i
gh
sp
eed
S3,
howev
er it switch
e
s to S2
as lon
g
as
τ
2 showed
up.
Fuzzy logic ends this
h
i
gh
sp
eed
in
t
e
rv
al
S2 and
switch
e
s t
o
th
e
lo
w
sp
eed
SL
at ti
m
e
t=9
when
τ
1 is
releas
ed.
The
proces
sor idle
ti
m
e
is red
u
c
ed
fro
m
3
3
%
in MS to
23
% in fu
zzy l
o
g
i
c app
r
o
a
ch
wh
ich
reflects th
e im
p
r
ov
em
en
ts ach
ieved
i
n
t
h
e sy
st
em
per
f
o
r
m
a
nce i
n
ad
di
t
i
on t
o
t
h
ere i
s
no
dea
d
l
i
ne m
i
ss, furt
h
e
rm
ore t
h
e i
n
t
e
rval
of
S
3
i
s
r
e
duce
d
whi
c
h i
n
t
u
rn
r
e
duce
t
h
e
p
o
w
e
r c
ons
um
pt
i
on.
An
ot
he
r har
d
r
eal
t
i
m
e
sy
st
em
with
th
ree task
s is add
r
essed
:
τ
1
= {2
, 5,
5
}
,
τ
2
= {2
.5
, 10
, 10},
τ
3
=
{
4
, 40, 40}
In t
h
is exam
ple,
τ
1 has
t
h
e hi
ghe
st
p
r
i
o
ri
t
y
,
τ
2 i
s
m
i
ddl
e an
d t
h
e
n
τ
3
is th
e lo
west
on
e. Th
e resu
ltant
lo
w
sp
eed
SL
is equ
a
l 0.7,
wh
ich
is less th
an
th
e lo
w s
p
ee
d cal
cul
a
t
e
d
ba
sed
o
n
e
quat
i
o
n
6.
T
h
ere
are
t
w
o
b
l
o
c
k
i
ng
task
s
in
th
is ex
am
p
l
e:
τ
2 t
h
at
can b
l
ock
hi
g
h
er
pri
o
ri
t
y
t
a
sk
τ
1 f
o
r m
a
xim
u
m
t
i
m
e
B
2
=2, an
d
τ
3 t
h
at
can
bl
oc
k hi
gh
er p
r
i
o
ri
t
y
t
a
sks
τ
1 a
n
d
τ
2
fo
r
max
i
m
u
m
ti
me
B3
=3. So
, t
h
ere will b
e
two
hig
h
sp
eed
s
(S2, S3).
S2= 0.8, and
S3=
1
. T
h
e two spee
ds (S2, S3
) als
o
satisfy the condit
i
on (7), where 0.7
≤
S2
≤
1 an
d
0.
7
≤
S3
≤
1.
Fi
gu
re 5
(
b) s
h
ows M
S
al
g
o
ri
t
h
m
whi
c
h en
d
s
t
h
e hi
gh
sp
eed
in
terv
al when
processor becom
e
s
idle
(at tim
e
s
t=10.75, t=19.75,
t
=
29.75, a
nd t=
39.75) or the
deadline
of
bl
ocki
ng task is reache
d
, while
figure
5(c
)
s
h
ows t
h
e
fuzzy l
ogic a
p
proach
which ends the
hi
gh sp
eed
in
terv
al
when
t
h
e
b
l
ock
e
d task
d
e
adlin
e is
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE Vo
l. 5
,
N
o
. 4
,
Au
gu
st 2
015
:
70
1
–
71
3
71
0
reache
d
(at time t=6), the proces
sor be
c
o
mes idle, or a
lowe
r or e
qual
prio
rity is selected to run (a
t times
t=1
0
,
t=19
.1
25, t=29
.1
25
, and t=3
9
.125
).
Fi
gu
re
5.
(a
) T
a
sk set
desc
ri
pt
i
on:
a
rri
val
t
i
m
e
s, c
o
m
put
at
i
on t
i
m
es,
and critical sec
tions. (b) MS
a
l
go
rithm
.
(c) F
u
zzy
lo
gic
Agai
n a
not
her
m
o
re exam
ple, ha
rd real tim
e
syste
m
with
the fo
llo
wi
n
g
th
ree task
s is im
p
l
e
m
en
ted
:
τ
1
={1,
4,
4
},
τ
2
={2,
8,
8
},
τ
3
={3
,
10
, 10
}
Ag
ai
n
th
e arriv
a
l ti
m
e
s an
d
critical sectio
n
s
o
f
th
e three
task
s with
i
n
the least co
mm
o
n
m
u
ltip
le
(
L
CM)
o
f
p
e
r
i
o
d
s
ar
e show
n
in
Figu
r
e
6(
a).
Ag
ain
τ
1
h
a
s
t
h
e h
i
gh
est
priority,
τ
2
is m
i
d
d
le an
d th
en
τ
3 i
s
t
h
e
lo
w
e
st
on
e. The r
e
su
ltan
t
low
sp
eed
SL is equ
a
l 0.8, an
d s2= 0
.
82
5 and
s3=0
.8
75
There i
s
a
g
ai
n
an i
m
provem
e
nt
i
n
t
h
e sy
st
e
m
perf
orm
a
nce base
d o
n
f
u
zz
y
l
ogic com
p
ared with M
S
al
go
ri
t
h
m
wher
e t
h
e
pr
ocess
o
r
i
d
l
e
t
i
m
e i
s
reduce
d
fr
om
4.2
8
% t
o
2.
6%.
Fi
gu
re
6.
(a
) T
a
sk set
desc
ri
pt
i
on:
a
rri
val
t
i
m
e
s, c
o
m
put
at
i
on t
i
m
es,
and critical sec
tions. (b) MS
a
l
go
rithm
.
(c) F
u
zzy
lo
gic
T
1
T
2
T
a
sk
block
e
d
T
1
T2
N
o
n
cri
t
i
c
a
l
se
ct
i
o
n
C
r
itic
a
l
se
ct
i
o
n
T1
T2
T
1
{
1
,4
,4
}
,
B
1
=1
.
5
T
2
{
2
,8
,8
}
,
B
2
=2
.
5
T
3
{
3
,1
0
,
10
}
,
B
3
=0
(
a
)
(
b
)
(c
)
10
5
15
20
25
30
35
40
T
3
T3
T3
S3
inter
v
a
l
T
a
sk
r
e
leas
e
T
a
sk
deadlin
e
S3
inter
v
a
l
S3
inter
v
a
l
T
a
sk
block
e
d
T
a
sk
block
e
d
Pr
oc
es
s
o
r
id
le
T
a
sk
block
e
d
S3
inter
v
a
l
S
3
i
n
te
r
v
a
l
S
3
in
te
r
v
a
l
T
a
sk
block
e
d
T
a
sk
block
e
d
Pr
oc
es
s
o
r
id
le
s1
inter
v
a
l
S
1
in
te
r
va
l
S1
inter
v
a
l
S1
inter
v
a
l
16
11
16
21
26
31
36
41
T1
T2
Pr
o
c
e
s
s
o
r
id
le
T
a
s
k
b
l
o
cke
d
Hi
gh s
peed
(
S
3)
in
te
r
v
a
l
N
o
n
c
r
it
ic
a
l
s
e
c
t
io
n
C
r
itic
a
l
s
e
c
t
io
n
T1
T2
T1{
2
,5
,5
}
T2{
2
.5
,
1
0
,
10}
T3{
4
,
40,
40}
(a
)
(
b)
T1
T2
T
a
s
k
b
l
o
cke
d
S
3 i
n
t
e
rval
(c
)
T
a
s
k
b
l
o
cke
d
T3
T3
T
a
s
k
b
l
o
cke
d
S
2 i
n
te
rva
l
S
2 i
n
te
rva
l
S
2 i
n
te
rva
l
S
2 i
n
te
rva
l
Pr
o
c
e
s
s
o
r
id
le
S
2
in
t
e
r
v
a
l
S
2
in
t
e
r
v
a
l
S
2
in
t
e
r
v
a
l
T3
Task
rel
eas
ed
Task
deadl
i
n
e
T
a
s
k
b
l
o
cke
d
T
a
s
k
b
l
o
cke
d
T
a
s
k
b
l
o
cke
d
T
a
s
k
b
l
o
cke
d
T
a
s
k
b
l
o
cke
d
T
a
s
k
b
l
o
cke
d
Evaluation Warning : The document was created with Spire.PDF for Python.