Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
V
o
l.
6, N
o
. 4
,
A
ugu
st
2016
, pp
. 14
89
~
1
498
I
S
SN
: 208
8-8
7
0
8
,
D
O
I
:
10.115
91
/ij
ece.v6
i
4.9
781
1
489
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
Perform
a
nce An
alysi
s
of Pree
mptive Based Uniprocessor
Scheduling
M S
h
a
n
mu
ga
s
und
aram
1
, R. Kum
a
r
2
,
Ha
rish M Kitt
ur
1
1
School of
Electronics Eng
i
neering, VIT Univers
i
ty
, India
2
Wipro Technologies, Ch
ennai, I
ndia
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Dec 25, 2015
Rev
i
sed
Mar
11
, 20
16
Accepted
Mar 28, 2016
All th
e r
eal-
time s
y
stems ar
e bo
und
with
r
e
sponse time
constraints, or
else,
there is
a ris
k
of
s
e
ver
e
cons
equ
e
nces
, which in
cludes
fai
l
ure
.
T
h
e S
y
s
t
em
will fai
l
when
not able
to
m
eet the r
e
qui
rem
e
nts accord
ing
to th
e
s
p
ecifi
cat
ions
.
The probl
em
of real-
tim
e scheduling is ver
y
vast, rang
ing
from
uni-proces
sor to com
p
li
ca
ted-m
u
ltipro
cessor. In
this p
a
pe
r, we
hav
e
compared
th
e performance of
real-tim
e
tasks that should b
e
schedu
led
properly
,
to
get optimum perf
orma
nce. Analysis methodology
and
th
e
concep
t of optimization leads to the de
sign of
appropriate scheduling. W
e
have don
e
the analy
s
is
among R
M
and EDF
algo
rithm that
are
important for
scheduling
in un
i-processor.
Keyword:
EDF
Real Tim
e
Syste
m
RM
Task
U
n
ip
ro
cesso
r Sch
e
du
ling
Copyright ©
201
6 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 S
h
an
mu
g
a
su
nd
ar
a
m
,
Sch
ool
o
f
El
ec
t
r
o
n
i
c
s E
ngi
ne
eri
n
g,
VIT Un
iv
ersity,
O
l
d
Mad
r
as R
o
ad,
V
e
llo
r
e
,
63
201
4, Tam
iln
ad
u,
I
n
d
i
a.
Em
ail: phds
undaram
@gm
a
il.
com
1.
INTRODUCTION
The m
o
t
i
v
at
i
on be
hi
n
d
a con
t
i
nuo
us f
r
am
ewo
r
k i
s
t
o
ha
ve a physical im
pact
in
a p
i
c
k
ed
tim
e-li
mi
t.
A co
n
tinuo
u
s
fram
ewo
r
k is mad
e
u
p
of a contro
lled
an
d
co
ntro
llin
g fram
e
w
ork. Th
e co
mp
u
t
er sp
eaks
with
its
surroundi
ngs on the prem
ise
of
data
accessible about the s
u
rroundi
ngs. A c
ontinuous
syste
m
that controls
a
gadget / m
e
thodology/ sens
ors
,
gi
ves the
readi
ngs at
int
e
rm
ittent interim
and
the c
o
m
puter reacts to the
actuators with the
help of
signals. The
r
e m
a
y be unknowing occasi
ons a
n
d they shoul
d likewise get a reaction
[1]
.
In all cases, there is a peri
odi
c bound in
which th
e react
i
o
n o
u
ght
t
o
be
con
v
ey
ed
. T
h
e
pot
e
n
t
i
a
l
of
th
e syste
m
is
to
m
eet
th
o
s
e b
o
u
n
d
req
u
ests relies o
n
u
p
o
n
its capab
ility
to
p
e
rfo
r
m
th
e fu
nda
m
e
n
t
al
calculations inside the lim
i
te
d tim
e
. In
the event that va
rious occasi
o
ns a
ll the while happeni
ng ine
v
ita
bly, the
com
puter
will need to ti
m
e
ta
ble the
pr
ocessing
so that e
v
e
r
y reaction is reco
rde
d
in the
oblige
d
ti
m
e
li
mits. It
may h
a
pp
en th
at, t
h
e
fram
e
work is
no
t ab
le to satisfy
all th
e con
cei
vab
l
e su
dd
en
req
u
e
sts.
In th
e
critical
circum
stances, the fram
ework needs suffic
i
ent assets
and fit for ha
ndling at unbounde
d
pace ca
n ful
f
ill
an
y
su
ch
tim
e
li
mitatio
n
.
In
ab
ility to
meet
th
ese req
u
i
rem
e
n
t
s for a reactio
n
can
co
m
e
ab
ou
t in
to
d
i
verse
resu
lts. Th
ere may b
e
n
o
im
p
act b
y
an
y stretch
o
f
t
h
e im
ag
in
atio
n
o
r
th
e i
m
p
act
may b
e
litt
le o
r
correct
ab
le.
On t
h
e ot
her
h
a
nd
, t
h
e
out
c
o
m
e
s
m
a
y
be di
sast
ro
us.
Eve
r
y
assi
gnm
ent
h
a
ppe
ni
n
g
i
n
a
cont
i
n
u
o
u
s
f
r
a
m
ewor
k
has som
e
t
i
m
i
ng
pr
op
ert
i
e
s.
These p
r
o
p
e
r
t
i
e
s ou
ght
t
o
be con
s
i
d
ere
d
w
h
en f
aci
n
g
assi
g
n
m
e
nt
s on a
cont
i
n
u
o
u
s
f
r
a
m
ewor
k
[2]
,
[3]
.
Relea
s
e time:
Ti
m
e
n
eed
ed
fo
r h
a
nd
lin
g erran
d
.
Dead
lin
e:
m
a
x
i
m
u
m
allo
wab
l
e ti
m
e
to
co
m
p
lete th
e g
i
v
e
n assig
n
m
en
t.
Mi
ni
m
u
m
def
e
r
r
al
:
Mi
n
i
m
u
m
o
b
lig
ed
i
n
terv
al b
e
fo
re starting
th
e ex
ecu
tion of th
e assign
men
t
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 4
,
Au
gu
st 2
016
:
14
89
–
1
498
1
490
Maximum deferral:
M
a
xi
m
u
m
m
easure
of
perm
eabl
e
t
i
m
e
be
fo
re
startin
g th
e
ex
ecu
tio
n of t
h
e errand
i
s
beg
u
n
, a
f
t
e
r
di
schar
g
i
n
g t
h
e a
ssi
gnm
ent
.
Worst-c
ase ex
ecution time
:
Max
i
m
u
m
ti
me tak
e
n
to
com
p
le
te th
e errand
, after the assig
n
m
en
t is
di
scha
rge
d
.
Run
time:
Time tak
e
n to
fin
i
sh
th
e und
ertak
i
n
g
withou
t a
b
r
eak
, after t
h
e assig
n
m
en
t is d
i
sch
a
rg
ed
.
Wei
ght
(
o
r
nee
d
)
:
Relativ
e critics o
f
t
h
e task
.
The t
a
r
g
et
o
f
a
com
put
er
bas
e
d c
ont
r
o
l
l
e
r
m
a
y
be t
o
sum
m
on t
h
e r
o
b
o
t
s
by
m
ovi
n
g
t
h
e
part
s
fr
om
mach
in
es to
tran
sp
ort in
some o
b
lig
ed
d
e
sig
n
with
ou
t
im
p
act
in
g
d
i
fferen
t
articles. In
th
e ev
en
t that the
p
r
o
cesso
r con
t
ro
lling
a
robo
t do
es
no
t su
m
m
o
n
it to
do
t
h
e
d
e
sired
work
in ti
m
e
, th
e
robo
t m
a
y
i
m
p
act an
altern
ate qu
esti
o
n
on
t
h
e industrial facility fl
o
o
r.
A
con
s
tant fram
e
w
o
rk
will n
o
r
m
a
lly n
eed
to m
eet
n
u
m
ero
u
s
requ
ests in
sid
e
a b
o
und
ti
m
e
.
Th
e essen
tials o
f
th
e req
u
e
st
s
m
a
y
d
i
ffer i
n
n
a
ture (ex
a
m
p
le a secu
rity b
a
sed
in
terest m
i
g
h
t
b
e
m
o
re critical th
an
b
a
sic in
fo
rm
atio
n
processin
g
requ
est). So
th
e
po
rti
o
n
of th
e
framework
asset
s
re
qui
re
m
e
nt
s t
o
be a
r
r
a
nge
d
wi
t
h
t
h
e
goal
t
h
at
al
l
re
que
st
s are
m
e
t
wi
t
h
i
n
t
h
e
du
e
dat
e
s.
The pl
a
nni
ng i
s
carri
ed
out
t
o
use a sc
hed
u
l
er
whic
h exec
utes a book
ing arrangem
ent that
characte
r
izes how the asset
s
of the fram
e
work are
allo
tted
to
th
e proj
ect. Pl
anning arra
ngem
ents are
u
n
c
ov
ered
numerically
so
th
is ex
actness
of the formal particular
and sy
st
em
adva
ncem
ent
can b
e
su
pp
lem
e
n
t
ed
b
y
a scien
tific ti
m
i
n
g
in
v
e
stigatio
n
o
f
th
e syste
m
p
r
op
erly.
2.
DIS
C
U
SSI
ON
OF
DIFFE
R
E
NT METH
O
D
OLO
G
IES
In real-tim
e, correctness
of t
h
e system
als
o
de
p
e
nd
s
on
th
e tim
e o
f
d
e
liv
ery ap
art
fro
m
lo
g
i
cal
so
lu
tion
.
If t
h
e syste
m
is
n
o
t
h
a
nd
led
i
n
th
e b
e
st way with ti
m
e
li
mit, th
en
system
failu
re is su
rely go
in
g
t
o
h
a
pp
en
. Th
erefo
r
e, it is v
e
ry essen
tial to
assure th
e tim
e co
n
s
train
t
s of th
e
syste
m
. Pred
ictab
ility is d
e
fined
as
th
e po
ssi
b
ility
o
f
d
e
term
in
in
g th
e co
m
p
letio
n
tim
e o
f
activ
ated
job
.
Wh
il
e m
e
e
tin
g
th
e
ti
m
e
co
n
s
train
t
s the
system
will
m
eet the m
a
xim
u
m
utilizati
on
[4].
It is es
sential that the
controlling-system
should be
reliable
with
th
e real-t
i
m
e co
n
s
train
t
s. Ot
h
e
rwise,
th
is system
’s
respon
se m
a
y
b
e
terrib
le.
Hen
ce, m
o
n
itoring
t
h
e
st
at
us i
n
t
h
e
r
e
gul
a
r
ba
si
s a
n
d
p
r
oce
ssi
n
g
t
h
e i
n
f
o
rm
ati
on i
n
a
n
d t
i
m
ely
m
a
nner a
r
e
necessa
ry
[
5
]
.
In
real
-
ti
m
e
, th
e ap
p
licatio
n
is a com
b
in
atio
n
o
f
a v
a
riety o
f
jo
b
s
with
cru
c
ial at d
i
fferen
t
lev
e
ls.
W
e
can
categ
orize
th
em
as sh
o
w
n
in
Fi
g
u
re 1. So
ft
real-tim
e
task
s ar
e t
h
at in
wh
ich
th
e
syste
m
will w
o
rk
ev
en
t
h
oug
h
t
h
e
m
i
ssi
ng of
som
e
deadl
i
n
e
s
. B
u
t
,
som
e
t
i
m
e
s
it
m
a
y
l
ead t
o
p
a
y
conse
q
uenc
es [6]
.
In
har
d
real
-t
i
m
e,
m
i
ssi
ng
of
task
's d
ead
lin
e lead
s to
catastroph
ic e
ffe
ct.
There
is one m
o
re
set of tasks
,
called fi
rm
real-tim
e tasks, whic
h
are tho
s
e
will fin
i
sh
t
h
eir ex
ecu
tio
ns
b
e
fo
re th
e
d
ead
lines [7].
Fi
gu
re
1.
Ty
pe
s o
f
Tas
k
s
2.
1.
Unipr
o
cess
o
r Real
-time Scheduling
It decides the
tim
e
and the e
nvi
ron
m
en
t to
ex
ecu
te task
s
su
ch
th
at tim
e
requ
irem
en
ts are m
e
t and
per
f
o
r
m
a
nce i
s
opt
i
m
i
zed. Sched
u
l
i
n
g-a
n
al
y
s
i
s
defi
nes t
h
e
st
udy
of t
h
e p
r
ope
rt
i
e
s o
f
sc
h
e
dul
i
n
g
pol
i
c
i
e
s [8]
.
Feasible Sc
he
dule de
fines
that
each a
n
d e
v
ery task m
u
st
be
execute
d
within the
de
a
d
line without
violating the
co
nstrain
t
s, whereas
o
p
tim
al s
c
h
e
du
le tells ab
ou
t
o
p
tim
al criteria related
to th
e
feasib
le sch
e
du
les.
R
eal
-t
im
e sy
stem
s gi
ve t
h
e
pre
f
ere
n
ce
fo
r
preem
pt
i
v
e b
a
sed
pri
o
ri
t
y
sched
u
l
i
n
g,
w
h
i
c
h can
be
fu
rt
he
r cat
eg
o
r
i
zed as s
h
ow
n i
n
Fi
gu
re
2.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Perf
or
ma
nce A
nal
ysi
s
of
Pree
mpt
i
ve B
a
se
d
Uni
p
ro
cess
o
r
Sche
d
u
l
i
n
g
(
M
.
S
h
a
n
m
u
g
a
su
n
dar
a
m
)
1
491
Fi
gu
re
2.
Ty
pe
s o
f
Sc
he
dul
e
r
s
Two
m
o
st i
m
p
o
r
tan
t
priorities driv
en
p
r
eem
p
tio
n sch
e
du
ling
techn
i
qu
es are:
Rate Mo
no
ton
i
c Sch
e
du
lin
g (RMS - Static)
Earliest Dead
lin
e Fi
rst (EDF - Dyn
a
m
i
c)
Schedulin
g Test:
-
A sche
d
u
l
i
ng t
e
st
i
s
a m
e
t
hod t
o
t
e
st
t
h
e part
i
c
ul
ar
appl
i
cat
i
o
n
,
whet
her i
t
i
s
co
m
p
leted
with
in
th
e
g
i
v
e
n d
ead
lin
e
wh
en
th
e
j
o
b
s
or tasks are sc
hedule
d
as
per specific algorithm
.
Sch
e
d
u
l
ab
ility u
tilizatio
n
is t
h
e m
a
x
i
m
u
m
allo
wab
l
e
u
s
ag
e of resou
r
ces
by th
e set
o
f
task
s t
o
g
u
a
ran
t
ee th
e
o
p
tim
ali
t
y.
Optim
a
l Sche
duler:
- A sch
e
du
ler is referred
as op
ti
m
a
l, if su
pp
ose it can
ab
le to
in
crease the
avera
g
e
res
p
onse tim
e
or t
o
re
duce
the a
v
e
r
a
g
e
waiting time [9].
Param
e
ters related
to
t
h
e task are
g
i
v
e
n
as follo
ws:
r
→
read
y tim
e
c
→
m
a
xim
u
m
com
put
at
i
onal
t
i
m
e
d
→
relativ
e dead
lin
e
D
→
ab
so
lu
te dead
lin
e
If t
h
e task
Ʈ
has m
o
re t
h
a
n
o
n
e i
n
st
a
n
ce,
we
ha
ve '
T
'
peri
od
(
f
o
r
pe
ri
o
d
i
c
t
a
sks
)
.
Ad
di
t
i
ona
l
con
s
t
r
ai
nt
s a
r
e
peri
odi
c
re
qu
est
of
ser
v
i
ce
of t
h
e t
a
s
k
,
de
pende
n
cy bet
w
een the
tasks
,
resource s
h
ari
n
g and
p
r
eem
p
tio
n
d
e
tails. A task
can
b
e
represented
wit
h
th
e param
e
ters
C
and
P
. W
h
er
e
C
is the
worst
case
ex
ecu
tion
tim
e
/
co
m
p
ile ti
m
e
su
ch
th
at
.Also
T is th
e p
e
riod
of th
e task.
A task
set can
b
e
rep
r
esen
t
e
d
as
.
2.
1.
1.
A Simple
Model
C
onsi
d
er a si
m
p
l
e
real
-t
im
e appl
i
cat
i
on c
onsi
s
t
s
o
f
a pr
i
o
ri
t
y
based p
e
ri
o
d
i
c
har
d
re
al
-t
im
e
t
a
sks
whic
h do
not need
a
n
y
ext
r
a resources
.
We de
fine a si
m
p
le code in real-tim
e as,
H
receives the si
gnal from
S
(sen
so
r) p
e
riod
ically in
th
e
in
ter-arrival time
T
.
The processing of
an event
is de
fi
ne
d as a t
a
s
k
. L
e
t
us co
nsi
d
er
C
as the
worst-case
co
m
p
u
t
atio
n
ti
me. Th
e task sh
ou
ld
b
e
co
m
p
leted
b
y
D
un
it ti
m
e
. Assu
m
e
th
e effectiv
e dead
lin
e
bo
und
ed
b
y
T
suc
h
that
[7]. Conside
r
the
application
which recei
ves t
h
e signals from two se
nsors.
Sens
orA
send the
signal
at eve
r
y
P
1
time u
n
it an
d each
o
f
th
em
n
e
ed
C
1
u
n
i
t
s
o
f
c
o
m
put
at
i
on t
i
m
e
and
Se
ns
or
B
sen
d
at
every
T
S1
tim
e
u
n
its an
d n
e
ed
u
n
its. Let
us assu
m
e
ab
so
l
u
te d
e
ad
lin
e
(
D
) =
pe
rio
d
(
T
) su
ch
t
h
at it is
T
S1
uni
t
s
o
f
t
i
m
e
for Se
ns
or
A an
d
Ts
2
un
its of ti
m
e
fo
r SensorB. Now th
e
q
u
estio
n
is: wh
en th
e co
d
e
p
e
ri
od
ically
col
l
ect
t
h
e
dat
a
fr
om
sens
ors
,
ho
w ca
n
i
t
det
e
rm
i
n
es t
h
e dea
d
l
i
n
e
of
eac
h
d
e
vi
ce
?
B
e
f
o
re
doi
ng
t
h
e
anal
y
s
i
s
of
th
e abov
e
p
r
ob
lem
,
first we m
u
st k
n
o
w t
h
e assu
m
p
tio
ns. Let
u
s
assume th
at co
d
e
is th
e co
m
b
inatio
n
o
f
peri
odic inde
pende
nt tasks.
Ass
u
m
e
the syste
m
has
one process
o
r whi
c
h periodically
receives unbuffe
red
events
from
the external e
nvi
ronm
ent [10].
2.
1.
2.
Schedulin
g S
t
rate
gy
Let u
s
con
s
id
er th
e set o
f
task
s to
b
e
one
way
of t
h
e sc
h
e
dul
i
n
g i
s
, by
anal
y
z
i
n
g
th
e set of task
statically an
d
determ
in
es th
eir ti
m
e
li
mitatio
n
s
. Th
is
can
b
e
used
fo
r creating
a
fix
e
d
sch
e
d
u
ling
table b
y
wh
ich
the task
s will b
e
d
i
sp
atch
ed
for ex
ecu
tio
n
during
run
-
tim
e.
Hen
c
e, th
e o
r
der o
f
ex
ecu
tion
will b
e
fix
e
d
.
In th
e
sch
e
du
lin
g
an
alysis, a po
sitiv
e
n
u
m
b
e
r is
assi
g
n
e
d
as priority.
By co
nv
en
tio
n, th
e lowest
num
eri
c
val
u
e
has t
h
e
hi
ghest
im
port
a
nc
e. C
onsi
d
er
t
h
e
fol
l
owi
n
g
t
w
o si
m
p
l
e
p
r
i
o
ri
t
y
sch
e
dul
i
n
g
di
sci
p
l
i
nes
as show
n Figu
re 3
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 4
,
Au
gu
st 2
016
:
14
89
–
1
498
1
492
Fi
gu
re 3.
C
l
assi
fi
cat
i
on of
p
r
i
o
ri
t
y
base
d sch
e
dul
i
n
g
2.
2.
Rate Mon
o
ton
i
c
Schedulin
g
It is the
m
e
thod; the pri
o
rities ar
e assigned to the set of
set of tasks in a task-set as a
m
onot
oni
c
fun
c
tion
of th
e p
e
riod
ic task
rate. Rate
m
o
n
o
to
n
i
c sc
h
e
du
ling
g
i
v
e
s th
e in
eq
u
a
lity b
e
tween
to
tal u
tilizati
o
n
of
p
r
o
cesso
r and
a th
eoretically calcu
lated
b
oun
d wh
ich is th
e sufficien
t cond
itio
n
t
h
at en
su
res co
m
p
letio
n
o
f
set
o
f
task
s in
a task
set
with
in
t
h
e end
o
f
th
eir
period
s
[11
]
,[12].
(1)
Whe
r
e
j
is t
h
e ex
ecu
tio
n time,
j
is t
h
e in
terarriv
al tim
e o
f
task
.
Let
us a
ssum
e
t
h
e m
odel
o
f
t
a
sk as
gi
ven
bel
o
w
1.
Period
ic taskset: (
j
,
j
)
2.
j
=
j
3.
Release tim
e
=
Start
of
Peri
od.
4.
Task i
s
i
n
depe
nde
nt
.
Rate
Sta
t
ic prio
rity
scheduling
RM static p
r
iority are th
o
s
e wh
ich
are
h
i
gh
er
prio
rities
g
i
v
e
n
to task
s with
sm
a
ll p
e
riod
s.
R
u
n
-
t
i
m
e
Sche
dul
i
n
g a
r
e t
hos
e p
r
eem
p
tiv
e
with
h
i
gh
est p
r
io
rity
first
RMS is o
p
timal, if th
e set o
f
task
s is sch
e
du
lab
l
e w
ith
any static sch
e
d
u
lin
g
algo
rith
m
,
it is sch
e
d
u
l
ab
le
with
RMS.
RMS: Schedula
b
ility
Test:
U < 1
does
n
o
t
m
ean sched
u
l
a
bl
e wi
t
h
R
M
S
.
Utilizatio
n
bou
nd
:
for a
g
i
ven
task
-set
Ʈ
S
, f
i
nd
UB
(
Ʈ
S
)
suc
h
t
h
at
U
≤
UB
(
Ʈ
S
)
if an
d o
n
l
y
if
Ʈ
S
is
sche
dul
a
b
l
e
by
R
M
S (
n
ecessa
ry
and s
u
fficient test).T
h
e
bound
UB
(
Ʈ
S
)
in EDF is
1
.
Assu
m
e
a set of
n
ind
e
p
e
nd
ent task
s:
Ʈ
S
=
{(
1
,
1
),
(
2,
2
)….
(
,
)}
A
n
d
U
=
1
If
, the
n
Ʈ
S
i
s
sc
hed
u
l
a
bl
e
by
R
M
S.
Here th
e
bo
und
d
e
p
e
nd
s co
mp
letely o
n
t
h
e size o
f
th
e task
set
RMS Alg
o
r
ithm
Pro
c
ed
ure fea
s
ib
le RTI (ta
s
k-set
)
in
t x ;
y= size(task-se
t,1)
;
n_
Feasi
b
l
e
=
1
;
in
t T
=
0
,
T
old
= 0;
fo
r
a
ll i=1:n do
T = T+ task
-se
t
( i, 1)
;
wh
ile (T >
T
old
)
T
old
= T
;
T = task
-set(i,1)
;
fo
r a
ll
j=1:i-1
d
o
T = T
+ ceil( R
old
/ ta
sk-
s
er(j,
2
)) ×
ta
sk-
s
et(j,1
)
;
end_for
if (T>
ta
sk-set(i,
2
))
th
en
n_
Feasi
b
l
e
=
0
;
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Perf
or
ma
nce A
nal
ysi
s
of
Pree
mpt
i
ve B
a
se
d
Uni
p
ro
cess
o
r
Sche
d
u
l
i
n
g
(
M
.
S
h
a
n
m
u
g
a
su
n
dar
a
m
)
1
493
b
r
e
a
k
;
en
d_
if
end_for
i
f
(
n_Fea
si
bl
e == 0)
t
h
en
b
r
e
a
k
;
en
d_
if
en_w
hi
l
e
en
d_
fun
c
tion
C
onsi
d
er
t
h
e s
e
t
of
t
a
sks
as s
h
o
w
n i
n
Ta
bl
e
1.
Tabl
e
1. E
x
am
pl
e Tas
k
set
Task
Ci
Di
Ti
Ʈ
1 2
2
3
Ʈ
2 2
3
5
Ʈ
3 2
4
9
Fig
u
re
4
sho
w
s th
e RM sch
e
du
lab
ility th
e g
i
v
e
n task
s.
Fi
gu
re 4.
R
M
Sche
dul
i
n
g
2.
3.
Ea
rliest Deadline
First Algorithm
EDF
al
g
o
ri
t
h
m
i
s
a m
e
t
hod t
h
at
can
be
u
s
e
d
t
o
ad
d t
h
e t
i
m
e red
u
n
d
a
n
c
y
t
o
t
o
l
e
rat
e
t
h
e t
r
a
n
si
ent
fau
lts [1
3
]
.
Fo
r real-ti
m
e p
r
o
c
esses ti
m
e
red
u
n
d
a
n
c
y shou
ld
b
e
m
a
in
tain
ed
to
m
e
e
t
th
e fault to
leran
ce. M
o
stly
Transien
t fau
lts will b
e
h
a
nd
led
b
y
EDF
[1
4
]
.
If th
e tr
an
sien
t
fau
lt
o
c
cu
rs, th
en
t
h
e task
is
rep
eat
ed
in
in
terv
als
wh
en th
e fau
lt
o
ccurs
u
n
til th
e syste
m
wo
rk
s co
rrectly [15
]
. In
g
e
n
e
ral, t
h
e
o
c
cu
rren
ce
of tran
sient
faul
t
s
i
s
m
o
re
f
r
eq
ue
nt
w
h
e
n
c
o
m
p
ared t
o
ot
h
e
r fa
ul
t
s
[
1
6]
.
In
EDF
th
e h
i
gh
est
p
r
iority is assign
ed to
t
h
e task
wh
ich m
e
e
t
s d
ead
line first i
n
th
e
p
r
esen
ce
of
fau
lts.
Hence, t
h
is is called
as Earliest Dead
lin
e First
sc
hed
u
l
i
n
g
.
I
f
t
h
e t
a
sk,
w
h
i
c
h i
s
r
u
nni
ng
d
o
es
not
hav
e
the
m
i
nim
u
m
deadline t
h
en t
h
at task
is stopped a
nd the
hi
ghe
r priority ta
sk is placed and exec
uted.
E
D
F
does
not
m
a
nage t
h
e t
i
m
e
red
u
n
d
a
ncy
.
It
does
not
g
u
ara
n
t
ee that
in presence
of fau
lts al
l th
e task
s
wi
ll b
e
co
m
p
leted
wit
h
in
th
e sp
eci
fied
ti
m
e
. It
is u
s
ed
to
ju
st add th
e ti
me red
u
n
d
a
n
c
y in
o
r
d
e
r to
m
a
k
e
th
e syste
m
fau
lt to
leran
t
[1
7
]
.
2.
4.
Ta
sk Mo
del
Ass
u
m
e
t
h
e t
a
sks t
o
be
pe
ri
o
d
i
c
, i
nde
pe
nde
nt
a
n
d
p
r
eem
pt
i
v
e. C
o
n
s
i
d
er
a
set
o
f
n
t
a
sks
{
Ʈ
1
,
Ʈ
2
,
Ʈ
3
...
Ʈ
n
} such that
Ʈ
j
= (
C
j
R
j
, D
j
, T
j
)
where
j=
1
,
2
,
….
.n
and C
j
R
j
, D
j
, T
j
co
rr
esp
ond
s to
t
i
m
e
to co
m
pute, time
to release,
dea
d
line a
n
d task
peri
od.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 4
,
Au
gu
st 2
016
:
14
89
–
1
498
1
494
Task
u
tilizatio
n
is
To
tal u
tilizatio
n
o
f
th
e system is
As th
e
fau
lts are tran
sien
t it affects
o
n
l
y
o
n
e
task
at a tim
e
whic
h ca
n be
c
o
rrected
by re
-execution.
The detection of
these fa
ults
can be done
i
n
diffe
re
nt ways. One
of suc
h
m
e
thod is acce
pt
ance test.
2.
5.
Schedul
a
b
ility test
(
2
)
C
onsi
d
er t
h
e t
a
skset
as gi
ve
n i
n
Ta
bl
e 4.
Whi
l
e
d
o
i
n
g t
h
e sche
d
u
l
i
ng
anal
y
s
i
s
fo
r t
h
e set
of gi
ven
task
s
u
n
d
e
r
EDF Sch
e
du
ling
,
w
e
h
a
v
e
go
t the sch
e
du
lin
g str
a
ter
g
y as sh
ow
n in
Figu
r
e
5.
Fi
gu
re 5.
ED
F Sche
dul
i
n
g
2.
6.
Com
p
ar
a
t
i
v
e An
al
ysi
s
of
R
M
and
E
D
F
For t
h
e anal
y
s
i
s
, we ha
ve ass
u
m
e
d preem
ptabl
e
peri
odi
c t
a
sks wi
t
h
m
a
xi
m
u
m
co
m
put
at
i
on t
i
m
e
C
j
,
peri
od
T
j
and
relativ
e d
ead
line
D
j
(D
j
≤
T
j
)
.
Gen
e
rated
t
h
e task
set with
d
i
fferen
t
co
m
b
in
atio
n
of task
s
u
nder
uni
fo
rm
di
st
ri
but
i
o
n
[
1
8]
.
We
ha
ve c
o
n
d
u
ct
ed
t
w
o set
s
o
f
e
xpe
ri
m
e
nts. I
n
t
h
e
first
set, we
ha
ve
a
n
alyzed t
h
e
oc
currence
of
num
ber
of
pree
m
p
ti
ons,
w
h
i
l
e
sched
u
l
i
n
g t
h
e
set
of t
a
sk
s by
R
M
and E
D
F
Sche
dul
i
n
g al
g
o
ri
t
h
m
s
. To m
a
ke i
t
fai
r
, we ha
ve
c
onsi
d
ere
d
o
n
l
y
p
r
eem
pt
abl
e
feasib
le task
wi
th
zero
p
r
eem
ptio
n
co
st.
Fi
gu
re
6 s
h
ow
s t
h
e
per
f
o
r
m
a
nce
of R
M
a
n
d
EDF
sche
d
u
l
i
n
g
i
n
t
e
rm
s of
preem
pt
i
on as
t
h
e f
u
n
c
t
i
o
n
o
f
nu
m
b
er of t
a
sk
s
b
y
k
eep
i
n
g
to
tal
u
tilizati
o
n as con
s
tan
t
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Perf
or
ma
nce A
nal
ysi
s
of
Pree
mpt
i
ve B
a
se
d
Uni
p
ro
cess
o
r
Sche
d
u
l
i
n
g
(
M
.
S
h
a
n
m
u
g
a
su
n
dar
a
m
)
1
495
(a)
(b)
(
c
)
(
d
)
(
e
)
(
f
)
Fi
gu
re 6.
Pree
m
p
ti
on vs.
N
o
.
o
r
t
a
sk
s
w
h
e
n
U
=
C
o
nst
a
nt
(
5
5
,
65
, 75
, 85
, 90
an
d 9
5
)
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 4
,
Au
gu
st 2
016
:
14
89
–
1
498
1
496
Fig
u
re 7
sho
w
s th
e No. of preem
p
tio
n
s
as th
e fu
n
c
tion
of to
tal u
tilizat
io
n
fo
r co
n
s
tan
t
n
u
m
b
e
r
of
t
a
sks.
Fr
om
t
h
e g
r
ap
h,
we
h
a
ve
fo
u
n
d
t
h
at
t
h
e
no
.
of
pre
e
m
p
tions
dec
r
eases whe
n
there is a
n
i
n
cre
a
se in
n
u
m
b
e
r
o
f
tasks and
t
o
tal u
tilizatio
n
in bo
t
h
t
h
e algorith
m
s
.
(
a
)
(
b
)
(
c
)
(
d
)
Fig
u
re
7
.
No
. of Preem
p
tio
n
vs. To
tal Utilizatio
n
for
Ʈ
= C
o
nst
a
nt
(1
0,
2
0
,
30
an
d
4
0
)
We
h
a
ve carried
o
u
t
t
h
e second
ex
p
e
rim
e
n
t
t
o
find
th
e effect o
f
to
tal u
tilizatio
n
o
n
th
e sch
e
du
lab
ility
of t
h
e
gi
ve
n al
go
ri
t
h
m
s
by
k
eepi
n
g t
h
e
co
n
s
t
a
nt
n
u
m
b
er o
f
t
a
sks
as s
h
o
w
n
i
n
Fi
gu
re
8
.
Fi
g
u
re
9
sh
o
w
s t
h
e
p
e
rform
a
n
ce o
f
sch
e
d
u
ling
in ter
m
s o
f
feasib
ility ratio
v
s
. n
o
. o
f
tasks for th
e co
nstan
t
u
tilizatio
n
.
Here, we
h
a
v
e
fou
n
d
t
h
e d
e
crease in feasib
ility ratio
alo
n
g
with
in
crease in
nu
m
b
er o
f
task
s and
t
o
tal u
tilizatio
n
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Perf
or
ma
nce A
nal
ysi
s
of
Pree
mpt
i
ve B
a
se
d
Uni
p
ro
cess
o
r
Sche
d
u
l
i
n
g
(
M
.
S
h
a
n
m
u
g
a
su
n
dar
a
m
)
1
497
(
a
)
(
b
)
(
c
)
(
d
)
Fig
u
re 8
.
Task
Feasib
ility
Rati
o
v
s
. To
tal Utilizatio
n
fo
r
Ʈ
=
Co
n
s
tan
t
(5
, 15, 35
, 40)
(
a
)
(
b
)
Fig
u
re 9
.
Task
Feasib
ility
Rati
o
v
s
. No
. of
Task
s for
U
=
C
o
nst
a
nt
(0
.5
-
0
.
8,
0.
9
5
)
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 4
,
Au
gu
st 2
016
:
14
89
–
1
498
1
498
3.
CO
NCL
USI
O
N
Th
is p
a
p
e
r presen
ted
th
e an
alysis o
f
th
e
mo
st wan
t
ed
in
du
strial n
eed
ed
sch
e
d
u
ling
algo
rith
m
s
fo
r
increasing the
perform
a
nce of
real-tim
e
syste
m
s. From
the
result of sim
u
lation, we
ha
ve
found each
of the
m
dom
inates each
othe
r’s
at di
ffere
n
t sce
n
ari
o
s. T
h
e
real
be
nefit of RM
ove
r E
D
F is
easie
r im
ple
m
entation in
th
e co
mm
ercia
l
k
e
rn
el. Ho
wev
e
r EDF allows th
e fu
ll CPU
u
tilizatio
n
wh
ich
m
ean
s
m
o
re efficien
t u
tilizatio
n
of res
o
urces
. T
h
ese
properties
are
very e
ssential for
a
real
-time syste
m
dealing
with
resource c
onst
r
aints.
REFERE
NC
ES
[1]
Schneider
S., “Concurrent and
R
eal-
time S
y
s
t
ems: th
e CSP Approach,” John Wiley
and
Sons Ltd
,
US, 2000.
[2]
X. Pan,
et a
l
.
, “
R
es
earch on R
e
a
l
-Tim
e S
c
hedu
li
ng S
t
rateg
y
for
Trans
i
en
t F
a
ult
Toler
a
nce
in NC S
y
s
t
em
,”
Pro
c
of
the S
i
xth
Int Con
f
on In
tellig
ent S
y
stems Design a
nd Applications
, 2006.
[3]
Liber
a
to F
.
,
et a
l
., “
T
ol
eran
t to
Mutliple
Transi
e
n
t Faults for Aperiodi
c Tasks in
Hard Real
Tim
e
S
y
stem
s,”
IE
EE
Transactions on
Computers
, vol.
49, pp
. 906-914
, 2000.
[4]
Shy
e
A
.
,
et al.
,
“Using Process - Lev
e
l r
e
dundan
c
y
to
Explo
it M
u
ltipl
e
Cor
e
s for
Transi
ent Fau
lt
Toler
a
nce,”
Pro
c
pf 37th
Annual I
EEE /
IFIP Int C
onf on
Dep
e
nda
ble S
y
stems and
Networks, (
E
din
burgh)
, pp. 297-
306, 2006
.
[5]
M. Pand
y
a
and
M. Malek, “
M
inim
um Achieva
b
le Utili
zat
ion for Fault-Toler
a
n
t
Processing of
Periodic Tasks,
”
IEEE Transactio
ns on Computers
, vol. 47
, pp
. 110
2-1112, 1998
.
[6]
M. Shanmugasundaram,
et al.
,
“
A
pproaches for Transien
t Fault
Toler
a
nc
e in
Multiproc
e
ssor - A State of Art
,
”
Indian Journal o
f
Science and
Technology
, vo
l. 8, pp. 1-9, 2015.
[7]
Be
i
t
o
ll
a
h
i H.,
et al
.
,
“
F
ault-
toler
a
nt
Earl
iest-De
a
d
line-First Sch
e
duling Algori
t
h
m
s,”
IEEE Sym
posium on Parallel
and Distributed
Processing (
L
ong Bea
c
h, CA)
,
p
p
. 1-6
,
2007
.
[8]
H. A
y
din
,
“
E
xa
c
t
Fault-Sensit
ive
Feas
ibili
t
y
Anal
ysis of Re
al-T
im
e Tasks,
”
IEEE
Transactions on Computers,
vol.
56, pp
. 1372
– 1
386, 2007
.
[9]
A
s
adi M
.,
et a
l
.
,
“A Modified BCE Algorithm for
Fault-Toleran
ce
Scheduling of
Periodic Ta
sks in
Ha
rd Re
al-Tim
e
S
y
ste
m
s,
”
Third
Asia Int Conf on
Modeling
&
Si
mulation
, pp. 28
7-291, 2009
.
[10]
Mosse
D.
,
et
al
., “A Nonpreemtive Real
-Time Scheduler
with R
e
cover
y
from Tr
an
sient Faults and
its app
lications
,”
IEEE Transactio
ns on
Software Engineering
, vol.
8, pp
. 752-767
,
2003.
[11]
C. L.
Liu and J.
W
.
La
yland
,
“
S
cheduling Algori
t
h
m
s
for Multiprogram
m
i
ng in a Hard- Real-
T
im
e Environm
ent
,
”
Journal of the Association
for C
o
mputing Mach
inery
, vo
l. 20, pp. 46-61, 1973.
[12]
H. Beito
llah
i
a
nd G. Deconin
c
k, “
F
ault-
Tole
rant
Rate-Mono
tonic Sch
e
dulin
g Algorithm in Uniprocessor
Embedded S
y
stems,”
12th Pa
cific Rim Inter
national Sympo
s
ium on Dependable Computing (
R
iverside,
California)
, pp.
395-396, 2006
.
[13]
R. M. Pathan, “
F
ault-Tol
e
ran
t
Real-
T
im
e Sched
u
ling
Algorithm
for Tolerat
i
ng Multiple Tr
ansie
n
t Faults,”
4th I
n
t
Conf on
Electrical and Com
puter Engin
eering
(
D
haka)
, pp. 5
57-5
80, 2006
.
[14]
Buttazzo G. C.,
“Rate Monotoni
c vs. EDF: Judg
ment Day
,
”
AC
M Journal of Real Time Systems,
vol/issue: 29(1
)
,
pp. 5-26
, 2005
.
[15]
B.
Al
a
m
a
n
d A. Kuma
r,
“A Re
al
T
i
me
Sc
he
duling Al
gori
t
h
m for T
o
le
ra
ti
ng Si
ngl
e
Tra
n
si
e
n
t
Faul
t
,
”
Int Conf on
Information Systems and Com
puter Networks (
M
a
t
hura)
,
pp. 11-1
4
, 2014
.
[16]
E. B
i
ni
and G.
C. But
t
az
zo,
“
M
easuring
the
per
f
orm
a
nce of
sch
e
dulab
ilit
y
t
e
sts,
”
Real-Time Sys
t
em
, vo
l. 30, pp.
129–154, 2005
.
[17]
L. Yang
and Q.
Zhu, “A Kind
of New Real-time
Scheduling Al
go
rithm for Embedded Linux
,”
Ind
onesian Journa
l
of Electrical En
gineer
ing
and C
o
mputer Science
, vol/issue: 12(6)
, pp
. 4444-4450
, 2014.
[18]
M
.
Awadall
a, “
P
roces
s
o
r S
p
eed Control for P
o
wer Reduct
i
on o
f
Real-
T
im
e S
y
s
t
em
s
Heuris
tica
l
l
y
,”
In
ternationa
l
Journal of Electrical and
Computer
Eng
i
neer
ing
,
vol/issue:
5(4), p
p
. 701-713
, 201
5.
Evaluation Warning : The document was created with Spire.PDF for Python.