Inter
national
J
our
nal
of
Electrical
and
Computer
Engineering
(IJECE)
V
ol.
8,
No.
1,
February
2018,
pp.
429
–
440
ISSN:
2088-8708
429
I
ns
t
it
u
t
e
o
f
A
d
v
a
nce
d
Eng
ine
e
r
i
ng
a
nd
S
cie
nce
w
w
w
.
i
a
e
s
j
o
u
r
n
a
l
.
c
o
m
Schedulability
of
Rate
Monotonic
Algorithm
using
Impr
o
v
ed
T
ime
Demand
Analysis
f
or
Multipr
ocessor
En
vir
onment
Leena
Das
1
,
Soura
v
Mohapatra
2
,
and
Dur
ga
Prasad
Mohapatra
3
1
Departement
of
Computer
Science
and
Engineering,
KIIT
Uni
v
ersity
,
Bhubanesw
ar
,
Odisha,
India
2,3
Departement
of
Computer
Science
and
Engineering,
National
Institute
of
T
echnology
Rourk
ela,
Odisha,
India
Article
Inf
o
Article
history:
Recei
v
ed:
Sep
2,
2017
Re
vised:
Dec
26,
2017
Accepted:
Jan
10,
2018
K
eyw
ord:
RMA
Real
T
ime
System
T
ime
Demand
Analysis
Scheduling
Multiprocessor
ABSTRA
CT
Real-T
ime
Monotonic
algorithm
(RMA)
is
a
widely
used
static
priority
scheduling
algo-
rithm.
F
or
application
of
RMA
at
v
arious
systems,
it
is
essential
to
determine
the
sys-
tem’
s
feasibility
first.
The
v
arious
e
xisting
algorithms
perform
the
analysis
by
reducing
the
scheduling
points
in
a
gi
v
en
task
s
et.
In
this
paper
we
propose
a
schedubility
test
algo-
rithm,
which
reduces
the
number
of
tasks
to
be
analyzed
instead
of
reducing
the
scheduling
points
of
a
gi
v
en
task.
This
significantly
reduces
the
number
of
iterations
tak
en
to
compute
feasibility
.
This
algorithm
can
be
used
along
with
the
e
xisting
algorithms
to
ef
fecti
v
ely
re-
duce
the
high
comple
xities
encounte
red
in
processing
lar
ge
task
sets.
W
e
also
e
xtend
our
algorithm
to
multiprocessor
en
vironment
and
compare
number
of
iterations
with
dif
ferent
number
of
proce
ssors.
This
paper
then
compares
the
proposed
algorithm
with
e
xisting
al-
gorithm.
The
e
xpected
results
sho
w
that
the
proposed
algorithm
performs
better
than
the
e
xisting
algorithms.
Copyright
c
2018
Institute
of
Advanced
Engineering
and
Science
.
All
rights
r
eserved.
Corresponding
A
uthor:
Leena
Das
Departement
of
Computer
Science
and
Engineering
KIIT
Uni
v
ersity
,
Bhubanesw
ar
,
Odisha
ldasfcs@kiit.ac.in
1.
INTR
ODUCTION
Real-time
systems
are
dif
ferent
from
other
types
of
systems
in
the
sense
that
the
y
must
pro
vide
accurate
results
in
both
temporal
and
logical
aspects.
Apart
from
being
able
to
carry
out
the
required
task,
the
system
must
do
it
within
a
certain
period
of
time.
F
or
e
xample,
when
a
temperature
sensor
in
a
thermal
plant
gi
v
es
a
w
arning,
then
the
system
must
turn
on
cooling
mechanisms
withing
a
certain
interv
al
of
time
barring
which
the
plant’
s
operation
may
f
ail.
Here
the
response
of
the
system
must
be
correct
as
well
as
be
completed
in
a
gi
v
en
interv
al
of
time.
A
real-
time
system
can
be
di
vided
broadly
into
thre
e
spheres;
the
en
vironment,
the
controller
and
the
controlled
object.
The
controller
gets
input
from
the
en
vironment
and
then
pro
vides
information
to
the
controlled
object.
The
time
it
tak
es
to
pro
vide
the
instruction
is
kno
wn
as
the
e
xecution
time
.
The
time
after
which
a
e
v
ent
repeats
itself
in
the
en
vironment
is
kno
wn
as
the
period
of
that
e
v
ent.
Ev
ery
e
v
ent
needs
a
certain
time
interv
al
before
which
it
has
to
be
e
x
ecuted.
This
is
kno
wn
as
the
deadline
.
Thus
a
real
time-system’
s
primary
goal
is
to
pro
vide
a
scheduling
algorithms
where
all
the
deadlines
are
met,
taking
into
account
the
period
and
e
x
ecution
time.
T
o
accomplish
this
there
are
a
number
of
algorithms
primarily
cate
gorized
into
tw
o
cate
gories:
static
priority
and
dynamic
priority
algorithms.
Static
priority
algorithms
are
those
which
the
priority
assigned
are
static
in
nature.
While
in
dynamic,
the
priorities
changes
dynamically
.
This
paper
concentrates
on
static
priority
scheduling,
most
specifically
RMA.
Rate
Monotonic
Algorithm
(RMA)
is
one
of
the
most
widely
used
and
ef
fecti
v
e
scheduling
algorithm.
RMA
uses
mathematical
model
of
static
priorit
y
based
scheduling
where
the
priority
is
the
period
of
the
tasks.
It
supports
the
intuition
that
the
tasks
that
occur
more
frequently
should
be
gi
v
en
higher
priority
.
RMA
w
as
first
proposed
in
[1].
W
orking
of
RMA
depends
on
the
periods
of
the
tasks.
F
or
a
gi
v
en
task
set
to
be
termed
as
feasible,
it
must
be
possible
to
be
scheduled
with
a
gi
v
en
algorithm,
in
this
case,
RMA.
This
feasibility
tests
are
generally
kno
wn
as
schedulability
bounds.
F
or
an
algorithm
to
w
ork,
it
must
be
within
certain
limits.
Schedulability
bound
pro
vides
this
limit.
The
J
ournal
Homepage:
http://iaescor
e
.com/journals/inde
x.php/IJECE
I
ns
t
it
u
t
e
o
f
A
d
v
a
nce
d
Eng
ine
e
r
i
ng
a
nd
S
cie
nce
w
w
w
.
i
a
e
s
j
o
u
r
n
a
l
.
c
o
m
,
DOI:
10.11591/ijece.v8i1.pp429-440
Evaluation Warning : The document was created with Spire.PDF for Python.
430
ISSN:
2088-8708
w
ork
in
[1]
g
a
v
e
an
initial
feasibility
bound.
It
w
as
impro
v
ed
by
Seto
and
Lehoczy
in
[3,
2]
by
the
use
of
a
time
demand
analysis
function
to
mak
e
it
an
e
xact
feasi
bility
test.
Our
w
ork
focuses
on
this
aspect
of
RMA
scheduling.
V
arious
types
of
other
bounds
were
also
proposed.
The
concept
of
harmonic
period
w
as
e
xplored
by
K
uo
et.
al
in
[4]
that
sho
wed
the
scheduablility
of
tasks
satisfying
the
harmonic
conditions.
Our
paper
no
w
analyses
the
initial
method
proposed
in
[3,
2],
often
termed
as
time
demand
anal
ysis
and
implements
it.
W
e
then
propose
an
algorithm
to
impro
v
e
this
implementation.
The
rest
of
the
paper
is
or
g
anized
as
follo
ws:
Section
2
describes
the
background
and
general
theory
refer
-
enced
in
this
paper
.
It
also
describes
the
e
xisting
feasibility
bounds.
Section
3
describes
the
t
ime
demand
analysis
for
the
uniprocessor
systems
with
RMA
scheduling
and
pro
vides
moti
v
ation
of
ho
w
it
can
be
impro
v
ed.
Section
4
describes
t
he
proposed
algorithm
for
schedulability
analysis
and
also
e
xtends
it
to
multiprocessors
real-time
systems.
W
e
discuss
the
implementation
of
the
proposed
algorithm
and
pro
vide
results.
In
Section
5,
we
analyze
the
dif
ferent
results
and
comparison
with
related
w
ork
are
done.
Conclusion
and
future
w
ork
are
then
sho
wn
in
Section
6.
2.
B
ASIC
CONCEPT
Real-time
systems
can
be
di
vided
into
three
broad
cate
gories:
(1)
Har
d
r
eal-t
ime
Systems
,
(2)
F
irm
r
eal-time
Systems
and
(3)
Soft
r
eal-time
Systems
.
If
the
completion
of
task
is
not
achie
v
ed
within
the
deadline
in
a
Har
d
r
eal-time
system
then
a
system
f
ailure
occurs.
While
if
the
system
still
can
function
with
some
de
gradation
in
performance
if
the
deadlines
are
missed
then
the
system
is
termed
as
Soft
r
eal-time
System.
Firm
r
eal-time
systems
are
in
between
Hard
and
soft
real-time
systems
.
In
this
paper
we
ha
v
e
considered
har
d
r
eal-time
systems
i.e.
all
the
deadlines
must
be
met.
The
e
v
ent
that
determines
a
course
of
action
is
kno
wn
as
a
task.
On
the
occurrence
of
a
task,
the
system
does
processing
and
responds
accordingly
.
There
are
three
types
of
tasks:
1.
Periodic
T
asks:
These
are
the
tasks
that
occur
after
after
a
specified
interv
al
of
time.
F
or
e
xample
a
sensor
sending
temperature
data
e
v
ery
10
seconds.
W
e
say
that
this
task
is
periodic
with
period
of
10
secs.
2.
Aperiodic
T
asks:
These
are
the
tasks
which
can
occur
after
an
y
amount
of
time
after
the
occurrence
of
the
last
instance,
e
xcept
immediately
.
3.
Sporadic
T
asks:
These
are
aperiodic
tasks
where
the
repetition
period
can
be
zero.
In
our
paper
we
deal
with
periodic
tasks
only
.
No
w
we
describe
the
v
arious
notations
used
in
our
paper
.
C
i
:
Ex
ecution
time
of
i
th
task
T
i
:
Period
of
i
th
task
U
i
:
Utilization
of
i
th
task
w
i
:
T
ime
demand
function
v
alue
t
:
Current
time
point
An
y
other
notations
ha
v
e
been
described
as
and
when
used.
2.1.
Related
W
orks
In
this
section
we
describe
the
schedubility
analysis
of
RMA
and
the
related
w
ork
done.
W
e
describe
the
v
arious
schedulabi
lity
bounds
present.
W
e
introduce
the
T
ime
Demand
Analysis
[2,
5],
which
w
as
further
impro
v
ed
in
[6,
7].
W
e
also
surv
e
y
some
w
orks
that
g
a
v
e
us
direction
to
proceed
in
the
w
ork.
In
this
paper
[6]
the
authors
proposed
a
no
v
el
schedulability
analysis
for
v
erifying
the
feasibility
of
lar
ge
periodic
task
sets
under
the
rate
monotonic
algorithm,
when
the
e
xact
test
cannot
be
applied
on
line
due
to
prohibiti
v
ely
long
e
x
ecution
times.
The
proposed
test
has
the
same
comple
xity
as
the
original
Liu
and
Layland
bound
b
ut
it
is
less
pessimistic,
so
allo
wing
to
accept
task
sets
that
w
ould
be
rejected
using
the
original
approach.
The
performance
of
the
proposed
approach
is
e
v
aluated
with
respect
to
the
classical
Liu
and
Layland
method,
and
theoretical
bounds
are
deri
v
ed
as
a
function
O(n)
(the
number
of
tasks)
and
for
the
limit
case
of
n
tending
to
infinity
.
The
analysis
is
also
e
xtended
to
include
aperiodic
serv
ers
and
blocking
times
due
to
concurrenc
y
control
protocols.
Extensi
v
e
simulations
on
synthetic
tasks
sets
are
presented
to
compare
the
ef
fecti
v
eness
of
the
proposed
test
with
respect
to
the
Liu
and
Layland
method
and
the
e
xact
response
time
analysis.
IJECE
V
ol.
8,
No.
1,
February
2018:
429
–
440
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
431
This
paper
g
a
v
e
a
bound
that
impro
v
ed
on
the
e
xisting
bound
[1].
It
w
as
named
as
h
yperbolic
bound.
This
bound
w
as
found
to
ha
v
e
a
linear
comple
xity
.
This
can
be
used
as
an
e
xtension
prior
to
the
calculation
of
time
demand
analysis.
In
the
paper
[10]
feasibility
analysis
of
fix
ed
priority
sys
tems
has
been
widely
studied
in
the
real-time
litera-
ture
and
se
v
eral
acceptance
tests
ha
v
e
been
proposed
to
guarantee
a
set
of
periodic
tasks.
The
y
can
be
di
vided
into
tw
o
main
classes:
polynomial
time
tests
and
e
xact
tests.
Polynomial
time
tests
can
ef
ficiently
be
used
for
an
on-line
guar
-
antee
of
real-time
applications,
where
tasks
are
acti
v
ated
at
runtime.
These
tests
introduce
a
ne
gligible
o
v
erhead,
when
e
x
ecuted
upon
a
ne
w
task
arri
v
al,
ho
we
v
er
,
pro
vide
only
a
suf
ficient
schedulability
condition,
which
may
cause
a
poor
processor
utilization.
On
the
other
hand,
e
xact
tests,
which
are
based
on
response
time
analysis,
pro
vide
a
necessary
and
suf
ficient
schedulability
condition
b
ut
are
too
comple
x
to
be
e
x
ecuted
online
for
lar
ge
task
sets.
As
a
consequence,
for
lar
ge
task
sets,
the
y
are
often
e
x
ecuted
of
fline.
In
this
paper
,
the
authors
propose
a
no
v
el
approach
for
analyzing
the
schedulability
of
periodic
task
sets
on
a
single
processor
under
an
arbitrary
fix
ed
priority
assignment.
Using
this
approach,
the
y
deri
v
e
a
ne
w
schedulability
test
which
can
be
tuned
through
a
parameter
to
balance
comple
xity
v
ersus
acceptance
ratio,
so
that
it
can
be
used
online
to
better
e
xploit
the
processor
,
based
on
the
a
v
ailable
computational
po
wer
.
The
test
is
sho
wn
to
be
significantly
f
aster
than
the
current
response
time
analysis
methods.
Moreo
v
er
,
the
proposed
approach
of
fers
an
e
xplanation
of
some
kno
wn
phenomena
of
fix
ed
priority
scheduling
and
could
be
helpful
for
further
w
ork
on
schedulability
analysis.
The
paper
[9]
is
an
e
xtension
of
the
pre
vious
paper
[10].
It
e
xplores
in
detail
and
e
xtends
the
w
ork
done
by
generalizing
it
to
fix
ed
priority
systems
rather
than
just
rate
monotonic
algorithm.
The
name
of
the
approach
is
HET
.
There
were
other
properties
e
xplored
b
ut
not
related
to
RMA
schedulability
.
Rest
of
the
details
and
proofs
are
e
xtensions.
In
the
paper
[12],
the
authors
discuss
ho
w
the
high
computational
comple
xity
required
for
performing
an
e
xact
schedulability
analysis
of
fix
ed
priority
systems
has
led
the
research
community
to
in
v
estig
ate
ne
w
feasibility
tests
whic
h
are
less
comple
x
than
e
xact
tests,
b
ut
still
pro
vide
a
reasonable
performance
in
terms
of
acceptance
ratio.
The
performance
of
a
test
is
typical
ly
e
v
aluated
by
generating
a
huge
number
of
synthetic
task
sets
and
then
computing
the
fraction
of
those
that
pass
the
t
est
with
respect
to
the
total
number
of
feasible
ones.
The
resulting
ratio,
ho
we
v
er
,
depends
on
the
metrics
used
for
e
v
aluating
the
performance
and
of
the
method
for
generating
random
task
parameters.
In
particular
,
an
important
f
actor
that
af
fects
the
o
v
erall
result
of
the
simulation
is
the
probability
density
function
of
the
random
v
ariables
used
to
generate
the
task
set
parameters.
In
this
paper
,
the
authors
discuss
and
compare
three
dif
ferent
metri
cs
that
can
be
used
for
e
v
aluating
the
performance
of
schedulability
tests.
Then,
the
y
in
v
estig
ate
ho
w
the
random
generation
procedure
can
bias
the
simulation
results
of
some
specific
scheduling
algorithm.
An
ef
ficient
method
for
generating
task
sets
with
uniform
distrib
ution
in
a
gi
v
en
space
w
as
gi
v
en
and
sho
wn
ho
w
some
intuiti
v
e
solutions
typically
used
for
task
set
generation
can
bias
the
simulation
results.
This
is
the
primary
paper
from
which
the
generation
of
task
set
has
been
done.
The
task
set
must
be
generated
as
the
capture
of
real-time
dataset
s
is
v
ery
dif
ficult.
Generation
of
a
uniform
dataset
is
the
primary
objecti
v
e
of
this
paper
.
RMA
w
as
first
proposed
by
[1]
in
1973
as
an
optimal
scheduling
algorithm
for
static
priority
task
set.
The
priority
w
as
assigned
to
the
periods
of
the
tasks.
F
or
a
task
set
T
(
T
1
;
T
2
;
:::;
T
n
)
period(
T
i
)
<
period(
T
j
)
=
)
priority(
T
i
)
>
priority(
T
j
)
F
or
v
alidating
the
feasibility
of
a
task
set
by
determining
whether
it
is
schedulable
or
not,
a
v
ariety
of
tests
ha
v
e
been
de
v
eloped.
The
first
uni
v
ersal
feasibility
bound
for
all
types
of
scheduling
systems
is
gi
v
en
by
n
X
1
U
1
(1)
The
sum
of
utilizati
on
of
all
the
tasks
in
the
task-set
should
be
less
than
equal
to
1.
This
gi
v
es
the
necessary
upper
bound
for
an
y
scheduling
algorithm
including
RMA.
But
this
is
not
suf
ficient.
W
e
refer
to
this
bound
as
sc
hedulability
bound
1
.
A
tighter
feasibility
test
w
as
proposed
in
[1]
which
stated
that
a
periodic
static
priority
system
is
feasible
if
n
X
1
U
n
(2
1
=n
1)
(2)
Where
n
is
the
total
number
of
tasks
in
the
task-set.
The
v
alue
tends
to
l
n
(2)
as
n
tends
to
1
.
This
sho
ws
that
in
an
y
suf
ficiently
lar
ge
task-set,
if
the
total
utilization
is
les
s
than
0.693,
then
it
can
be
scheduled.
This,
ho
we
v
er
,
is
a
suf
ficient
condition
only
.
Ev
en
if
the
total
utilization
remains
greater
than
this
bound,
it
can
still
be
static
feasible.
T
o
tak
e
into
account
this
f
actor
,
v
arious
necessary
and
suf
ficient
tests
were
proposed
[2,
5,
6,
7,
8,
16,
17].
The
initial
test
proposed
in
[2,
5]
w
as
further
impro
v
ed
in
[6,
8].
These
al
l
tests
remained
pseudo
polynomial.
The
proposed
tests
Sc
hedulability
of
Rate
Monotonic
Algorithm
using
Impr
o
ved
T
ime
Demand
...
(Leena
Das)
Evaluation Warning : The document was created with Spire.PDF for Python.
432
ISSN:
2088-8708
can
be
di
vided
into
tw
o
types;
iterati
v
e
[5,
16]
and
as-per
-task
basis
[2,
9,
10,
8].
The
later
analyses
feasibility
on
task
arri
v
al
times
kno
wn
as
scheduling
points.
The
former
uses
an
iterati
v
e
technique.
Recently
the
w
ork
by
Allah
et.
al.
in
[7]
impro
v
ed
the
w
ork
by
Bini
and
Buttazzo
in
[6]
by
restricting
the
actual
number
of
scheduling
points.
W
e
no
w
discuss
the
e
xact
feasibility
test
upon
which
we
propose
our
impro
v
ement.
2.2.
Exact
Schecduability
T
est
Phase
I
of
a
task
i
s
defined
as
the
time
when
the
first
instance
of
the
task
is
released
into
the
system.
T
w
o
tasks
T
i
and
T
j
are
said
to
be
of
same
phasing
if
f
I
i
=
I
j
.
In
the
w
ork
[1]
it
w
as
sho
wn
that
in
the
scenario
where
the
phasing
of
all
the
tasks
are
equal,
it
results
in
the
longest
response
time.
This
is
generally
kno
wn
as
the
critical
instant
.
This
scenario
creates
the
w
orst
case
task
set
phasing
and
thus
can
be
used
as
a
criterion
for
the
schedulability
of
the
gi
v
en
task
set.
The
idea
can
be
re-framed
as
”
A
periodic
task
set
can
be
sc
heduled
by
a
fixed
priority
sc
heduling
algorithm
if
the
d
e
ad
l
ine
of
the
fir
st
job
of
eac
h
task
is
met
while
using
that
algorithm
fr
om
a
critical
instant
”.
Since
RMA
is
a
fix
ed
priority
scheduling
algorithm,
the
condition
satisfies
for
it.
Let
T
be
a
task
set
T
(
T
1
;
T
2
;
:::;
T
n
)
with
tasks
ha
ving
increasing
periods
(thus
decreasing
priority).
As
per
RMA
’
s
priority
property
a
task
ha
ving
lo
wer
period
has
to
be
scheduled
before
task
of
higher
period.
Thus
a
task
T
i
can
only
be
af
fected
by
the
tasks
T
j
where
period(
T
j
)
>
period(
T
i
).
This
gi
v
es
the
intuition
that
that
while
checking
for
the
schedulabili
ty
of
the
task
only
those
task
should
be
considered
whose
periods
more
than
the
current
(or
pri
ority
less).
This
ordering
can
be
achie
v
ed
by
sorting
the
task
set
in
ascending
order
of
their
period.
When
the
task
set
is
no
w
processed,
the
tasks
a
re
encountered
with
decreasing
priority
.
As
the
At
the
time
of
critical
instance,
a
v
alue
is
calculated.
This
v
alue
gi
v
es
the
estimate
as
to
ho
w
much
the
system
is
feasible.
These
ideas
were
stated
mathematically
in
[2]
as
follo
ws
w
i
(
t
)
=
C
i
+
i
1
X
1
d
t=T
k
e
C
k
(3)
w
i
(
t
)
is
the
time
demand
function
of
i
th
task
when
it
is
released
at
the
critical
instant.
As
can
be
seen,
the
tasks
from
starting
to
i
1
only
contrib
ute
to
this
v
alue
function.
The
tasks
after
the
i
th
task
cannot
af
fect
as
the
y
ha
v
e
lo
wer
priority
(as
task
set
is
sorted).
After
this
calculation,
the
schedulabilty
bound
w
as
gi
v
en
as
w
i
(
t
)
<
t
(4)
Where
w
i
(
t
)
can
be
interpreted
as
demand
and
the
time
t
can
be
seen
as
the
supply
.
So,
the
demand
must
be
less
than
the
supply
for
the
task
set
to
be
feasible.
Equation
(4)
in
v
olv
es
checking
for
time
instances
the
demand
of
a
gi
v
en
task.
The
time
instances
that
must
be
check
ed
relates
to
the
the
tasks
ha
ving
higher
priority
than
the
current.
As
mentioned
earlier
,
property
of
RMA
asserts
that
only
higher
priority
tasks
can
af
fect
the
current
task.
Thus
only
those
time
instances
need
to
be
check
ed
that
are
multiples
of
period
of
all
the
high
priority
tasks.
t
=
j
T
k
;
(5a)
k
=
1
;
2
;
:::;
i
;
(5b)
j
=
1
;
2
;
:::;
d
T
i
=T
k
e
(5c)
Combining
Equation
(3)
and
(5a,
5b,
5c)
an
algorithm
can
be
implement
ed
using
Equation
(4)
as
the
checking
condition.
W
e
shall
refer
this
algorithm
to
as
T
ime
Demand
Analysis
(TD
A)
In
this
paper
we
e
xplore
a
ne
w
method
to
approach
the
t
ask
set
to
determine
schedulabili
ty
.
The
main
idea
in
this
paper
can
be
applied
to
an
y
static
priority
algorithm
b
ut
for
being
in
synchronization
with
the
pre
vious
results
we
use
RMA.
Simulation
sho
ws
our
results
are
better
that
the
other
w
orks
one
in
the
same
field.
In
the
ne
xt
section
we
e
xplore
the
e
xisting
e
xact
schedulability
algorithm
and
propose
our
impro
v
ement.
3.
TIME
DEMAND
AN
AL
YSIS
(TD
A)
Before
presenting
the
impro
v
ed
algorithm
we
first
describe
the
TD
A
in
detail.
W
e
then
implement
the
TD
A
so
as
to
pro
vide
a
common
ground
upon
which
the
impro
v
ed
algorithm
can
be
compared.
As
presented
abo
v
e,
TD
A
can
be
described
by
three
Equations
(3-5).
W
e
no
w
present
ho
w
to
carry
out
TD
A
on
a
sample
task
set.
3.1.
Implementation
of
TD
A
The
first
requirement
is
the
sorting
of
the
t
ask
sets.
The
task
sets
are
sorted
according
to
their
periods.
After
the
sorting
is
done,
s
tarting
from
the
first
task,
the
computations
are
carried
out
to
determine
the
time
demand
function
IJECE
V
ol.
8,
No.
1,
February
2018:
429
–
440
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
433
v
alue
for
each
task
using
Equations
(3)
and
(5a,
5b,
5c).
If
the
v
alue
of
t
he
time
demand
function
for
a
task
does
not
satisfy
Equation
(4)
then
it
is
deemed
as
unschedulable.
W
e
can
di
vide
the
algorithm
into
three
phases
for
better
Algorithm
1:
TD
A
Input:
task
set
Output:
schedulable
or
not
1
Sort
the
task-set;
2
r
epeat
3
Calculate
time
points
from
Equation
(5);
4
Calculate
w
(
t
)
from
Equation
(3);
5
if
w
(
t
)
t
then
6
return
N
otschedul
abl
e
;
7
e
xit
algorithm;
8
until
all
tasks
in
the
sorted
set
have
been
pr
ocessed
;
9
return
schedul
ab
l
e
;
understanding:
1.
Determining
the
Or
der
of
e
xecution
-
The
task-set
i
s
sorted
as
per
increasing
period.
The
sorted
task
sets
are
sequentially
processed
one
by
one.
Ev
ery
task
is
then
subjected
to
TD
A.
The
task,
if
an
y
,
at
which
the
TD
A
gi
v
es
result
as
unschedulable,
is
the
threshold
task.
Since
the
task
set
is
sorted,
an
y
task
after
that
also
will
be
unsceduable.
2.
Determining
the
Discr
ete
time
points
-
Schedulability
test,
as
mentioned
earlier
need
only
be
performed
at
certain
time
interv
als.
Using
Equation
(5)
those
time
points
are
calcul
ated
for
e
v
ery
task.
These
are
the
points
where
a
instant
of
one
of
the
task
occurs
and
thus
needs
to
be
check
ed
for
schedulability
.
3.
Computing
the
time
demand
function
value
-
The
v
alue
calc
ulated
from
Equation
(3)
can
be
computed
after
all
the
time
points
are
calculated.
At
e
v
ery
t
ime
point
this
v
alue
is
computed
and
continually
summed
o
v
er
.
The
final
sum
is
the
required
v
alue
that
is
compared
in
Equation
(4).
This
v
alue
is
t
hen
check
ed
as
per
the
Equation
(4)
which
gi
v
es
the
decision
whether
schedulable
or
not.
The
steps
are
described
in
an
algorithm
in
Algorithm
1:
TD
A
Algorithm
2:
Sort
Input:
task
set
Output:
sorted
task
set
1
f
or
e
very
task
T
i
do
2
v
al
=
period(
T
i
);
3
s
1
=
Inde
x
of
T
i
;
4
s
2
=
0;
5
f
or
e
very
task
T
k
in
T
i
+1
to
T
n
do
6
if
v
al
per
iod
(
T
k
)
then
7
store
inde
x
k
in
s
2
;
8
v
al
=
period(
T
k
);
9
Sw
ap
v
alues
at
inde
x
s
1
and
s
2
;
10
r
etur
n
sorted
task
set
;
The
sorting
of
the
task
set
can
be
done
in
an
y
w
ay
.
W
e
used
associati
v
e
selection
sort
[11]
where
the
task
set
w
as
sorted
according
to
increasing
periods.
The
sorting
algorithm
is
gi
v
en
in
Algorithm
2:
Sort.
W
e
implemented
TD
A
using
C++
with
STL
on
a
Intel
Core
i7
3632Q
2.20
GHz
processor
.
W
e
ha
v
e
measured
the
performance
in
terms
of
iterations
so
as
to
pro
vide
an
uniform
performance
criteria
across
multiple
types
of
processors.
The
w
orst
case
of
the
algorithm
occurs
when
a
gi
v
en
task
is
sc
hedulable
as
that
w
ould
require
the
full
task
set
to
be
tested.
F
or
measuring
the
performance
of
the
algorithm
the
task
set
is
being
generated
randomly
.
The
generation
is
such
that
the
total
utilization
of
the
tasks
does
not
e
xceed
1.0
b
ut
is
v
ery
near
to
it.
In
other
w
ords,
all
the
Sc
hedulability
of
Rate
Monotonic
Algorithm
using
Impr
o
ved
T
ime
Demand
...
(Leena
Das)
Evaluation Warning : The document was created with Spire.PDF for Python.
434
ISSN:
2088-8708
tasks
satisfy
the
necessary
sc
hedulability
bound
1
b
ut
do
not
sat
isfy
the
suf
ficient
sc
hedulability
bound
2
.
This
enables
the
task
set
to
be
processed
by
TD
A.
This
generation
creates
equally
weighted
task
sets
to
w
ards
the
total
utilization.
This
idea
is
broadly
tak
en
from
[12]
who
g
a
v
e
a
detailed
method
to
generate
properly
distrib
uted
random
task
sets.
The
task
set
we
ha
v
e
used
is
not
specifically
e
v
enly
distrib
uted
b
ut
serv
es
the
purpose
of
implementing
the
algorithm.
An
e
xample
task
set
is
gi
v
en
in
T
able
1.
The
total
utilization
in
this
case
is
0.8902
which
is
clearly
greater
than
the
sc
hedulability
bound
2
which
is
0.717.
T
able
1.
Sample
task
set.
T
otal
utilization
is
such
that
the
task
set
has
to
be
processes
by
TD
A
Period
Ex
ecution
T
ime
Utilization
(
C
=P
)
62
628
0.098726
55
558
0.098566
94
946
0.099365
60
610
0.098360
51
513
0.099415
75
756
0.099206
90
910
0.098901
62
627
0.098883
81
820
0.098780
This
implementation
sho
ws
that
the
number
of
iterations
increases
at
a
pseudo-polynomial
rate
with
the
number
of
tasks
in
the
task
set.
The
result
is
sho
wn
in
T
able
1.
W
e
no
w
discuss
ho
w
can
this
result
be
impro
v
ed.
T
able
2.
The
Performance
of
TD
A
measured
in
terms
of
iterations
with
respect
to
the
number
of
tasks
in
the
task
set.
No
of
T
asks
Iterations
10
20
20
65
30
97
40
185
50
292
100
1239
200
5904
300
14695
400
31189
500
58209
3.2.
Scope
f
or
impr
o
v
ement
From
T
able
1
it
can
be
seen
that
the
rate
of
increase
in
the
number
of
iterations
is
pseudo
polynomial.
The
primary
dra
wback
of
TD
A
is
that
the
task-set
is
processed
linearly
.
From
one
task
to
the
other
,
e
v
ery
task
is
visited
one
by
one.
In
the
w
orst
case,
when
the
task
set
is
schedulable,
TD
A
needs
to
visit
all
the
tasks.
This
w
ould
result
in
a
time
comple
xity
of
(
n
)
for
the
outer
loop.
The
selection
of
tasks
results
in
a
linear
comple
xity
.
W
e
propose
an
impro
v
ement
to
this
approach
by
not
using
the
linear
approach.
TD
A
can
also
be
impro
v
ed
in
other
w
ays
such
as
reducing
the
number
of
time
points
in
Equations
(5a,
5b,
5c)
as
proposed
in
[6]
and
further
impro
v
ed
in
[7].
Our
approach
is
dif
ferent
from
theirs
in
the
w
ay
that
we
reduce
the
number
of
tasks
to
be
check
ed
rather
than
reducing
the
number
of
scheduling
points
for
each
task.
The
rest
of
the
paper
discusses
our
proposed
algorithm.
4.
IMPR
O
VED
TIME
DEMAND
AN
AL
YSIS
Before
looking
at
the
proposed
algorithm,
one
important
property
of
RMA
must
be
established
as
gi
v
en
belo
w:
A
task’
s
sc
hedulability
is
only
af
fected
by
those
tasks
whic
h
ar
e
having
higher
priority
than
it
.
This
can
be
seen
as
a
deri
v
ation
from
the
nature
of
RMA
itself.
Since
high
priority
is
assigned
to
lo
wer
period,
a
task
ha
ving
higher
period
cannot
af
fect
the
one
ha
ving
lo
wer
period.
In
TD
A,
the
first
step
is
to
sort
the
task
set.
IJECE
V
ol.
8,
No.
1,
February
2018:
429
–
440
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
435
An
y
task
T
i
in
the
sorted
task
set
T
(
T
1
;
:::;
T
n
)
will
ha
v
e
tasks
with
lo
wer
period
before
it
and
higher
period
after
it.
If
a
task
is
deemed
to
be
schedulable
then
it
is
tri
vial
that
the
task
before
it
m
ust
also
ha
v
e
been
schedulable.
This
property
enables
us
to
de
viate
from
the
linear
nature
of
tra
v
ersal.
Instead
of
pr
oceeding
in
a
linear
fashion
we
can
use
a
dif
fer
ent
appr
oac
h
of
tr
aver
sing
the
task
set
t
o
determine
unSc
hedulability
.
This
is
the
central
idea
of
the
impro
v
ed
algorithm.
Belo
w
we
describe
in
detail
the
proposed
algorithm
which
we
ha
v
e
decided
to
name
as
Impro
v
ed
T
ime
Demand
Analysis
(ITD
A).
4.1.
Selection
Function
W
e
no
w
describe
a
ne
w
w
ay
to
select
a
task
instead
of
linear
selection
as
it
is
done
in
TD
A.
Let
T
1
be
the
first
task
in
the
sorted
set.
As
per
TD
A,
this
task
is
determined
to
be
schedulable
or
not
by
calculating
the
time
points
and
checking
the
condition.
Suppose
this
task
comes
out
to
be
schedulable.
F
or
the
ne
xt
iteration,
instead
of
checking
the
ne
xt
task,
a
dif
ferent
tasks
T
k
is
chosen.
No
w
tw
o
possibilities
can
occur
as
gi
v
en
belo
w
,
1.
T
k
is
not
sc
hedulable
:
If
T
k
is
not
schedulable
then
the
tasks
after
that
can
not
be
schedulable
also.
In
this
case
the
algorithm
returns
f
alse
and
e
xits.
2.
T
k
is
sc
hedulable
:
If
T
k
is
schedulabl
e
then,
as
stated
abo
v
e,
the
tasks
from
T
1
to
T
k
1
are
also
schedulable.
The
algorithm
need
not
check
those
tasks.
W
e
can
proceed
on
to
the
ne
xt
task.
No
w
we
describe
in
detail
ho
w
to
select
the
ne
xt
task.
Let
n
be
the
total
number
of
tasks
present.
Let
k
be
the
task
position
of
the
current
task.
Let
the
computed
v
alue
of
time
demand
functi
on
for
the
current
task
be
w
(
t
)
and
the
corresponding
maximum
time
among
the
time-points
for
the
task
be
t
.
Then
we
define
a
ratio
r
to
be
r
=
t=w
(
t
)
(6)
This
ratio
is
the
ratio
of
t=w
(
t
)
from
Equation
(4).
It
can
be
seen
that
that
for
a
schedulable
task,
this
ratio
will
be
greater
than
1.
As
the
task
becomes
unschedulable,
the
ratio
will
go
belo
w
1.
Thus
the
criteria
that
a
gi
v
en
task
is
schedulable
can
be
re
written
as,
r
1
(7)
T
o
pro
vide
an
idea
of
the
v
alue
of
r
,
a
graph
is
plotted
for
a
gi
v
en
task
set
for
the
r
atio
vs
the
number
of
sorted
tasks
and
is
gi
v
en
in
Figure
1.
As
we
can
see,
the
ratio
con
v
er
ges
to
1
as
the
iteration
nears
the
unschedulable
task
in
the
task
Figure
1.
Nature
of
change
of
ratio
with
the
tasks
in
the
sorted
set.
The
ratio
con
v
er
ges
to
1
as
the
tasks
reach
uncscheduabe
utilization.
set.
W
e
no
w
de
v
elop
a
selection
function
that
gi
v
es
an
estimate
as
to
ho
w
close
the
ratio
is
to
1.
If
it
is
v
ery
close
then
the
ne
xt
task
that
is
to
be
selected
is
near
to
the
current
one
and
vice-v
erse.
This
approximation
function
is
a
mapping
of
range
of
ratio
r
to
the
range
of
task-set.
Thus
it
gi
v
es
a
ne
w
position
with
respect
to
the
position
of
the
current
task.
As
a
function
it
can
be
represented
as
m
=
k
+
d
r
(
n=
M
AX
)
e
(8)
Sc
hedulability
of
Rate
Monotonic
Algorithm
using
Impr
o
ved
T
ime
Demand
...
(Leena
Das)
Evaluation Warning : The document was created with Spire.PDF for Python.
436
ISSN:
2088-8708
Where
M
AX
is
the
maximum
v
alue
of
the
ratio,
which
is
the
ratio
of
the
first
task’
s
time
demand
function
to
time
point
for
that
task
and
m
is
the
ne
xt
task
that
is
to
be
e
x
ecuted.
So
after
the
computation
of
T
k
the
ne
xt
task
to
be
processed
is
T
m
instead
of
T
k
+1
.
T
aking
into
consideration
the
selection
function
we
propose
our
algorithm,
ITD
A.
Algorithm
3:
ITD
A
Input:
task
set
Output:
schedulable
or
Unschedulable
1
Sort
the
task-set;
2
k
=
1
;
3
r
epeat
4
T
ask
considered
k
;
5
Calculate
time
points
from
Equation
(5);
6
Calculate
w
(
t
)
from
Equation
(3);
7
if
w
(
t
)
t
then
8
return
N
otschedul
abl
e
;
9
e
xit
algorithm;
10
Calculate
ratio
r
using
Equation
(6);
11
Calculate
v
alue
m
using
Equation
(8);
12
k
=
m
;
13
until
last
task
is
not
c
hec
k
ed
OR
r
atio
1
;
14
return
schedul
ab
l
e
;
4.2.
Implementation
and
Results
The
algorithm
w
as
implemented
in
the
same
w
ay
as
the
TD
A.
Instead
of
a
central
linear
loop,
a
loop
based
on
m
and
r
atior
is
i
terated.
At
each
iteration
the
ne
w
v
alue
k
is
calculated
which
becomes
the
ne
xt
task
to
be
scheduled.
This
decreases
the
(
n
)
comple
xity
by
e
xponential
times.
The
comple
xit
y
becomes
(
l
og
n
)
.
The
loop
iterates
until
the
last
task
has
been
check
ed
or
the
v
alue
of
ratio
goes
belo
w
1.
On
running
the
algorithm
on
the
same
sample
task
sets
as
TD
A,
we
obtain
the
result
sho
wn
in
T
able
3.
Before
discussing
the
observ
ations
in
T
able
3,
in
t
he
ne
xt
T
able
3.
The
Performance
of
ITD
A
comparing
the
number
of
iterations
with
TD
A
on
common
task
set
No
of
T
asks
Iterations
in
TD
A
Iterations
in
ITD
A
10
20
8
20
65
11
30
97
29
40
185
45
50
292
57
100
1239
361
200
5904
1365
300
14695
5964
400
31189
11086
500
58209
33609
subsection,
we
propose
an
e
xtension
to
ITD
A
that
enables
it
to
w
ork
for
multiprocessor
en
vironment.
4.3.
ITD
A
f
or
Multipr
ocessor
T
o
the
best
our
kno
wledge,
there
e
xist
no
algorithm
for
schedulability
analysis
of
multiprocessor
real-time
systems
using
RMA.
In
this
section,
we
ha
v
e
e
xtended
ITD
A
to
multiprocessor
systems.
W
e
named
this
proposed
algorithm
as
Impro
v
ed
T
ime
Demand
Analysis
for
Multiprocessor
en
vironment
(MITD
A).
The
aim
of
MITD
A
is
to
determine
whether
a
task-set
is
schedulable
in
a
system
ha
ving
more
than
one
processor
a
v
ailable
for
the
processing
of
the
task.
W
e
no
w
describe
MIT
A
in
detail.
IJECE
V
ol.
8,
No.
1,
February
2018:
429
–
440
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
437
MITD
A
tak
es
input
the
number
of
processors
a
v
ailable
in
the
multiprocessor
en
vironment.
In
the
ne
xt
step,
MITD
A
di
vides
the
task
set
among
the
specified
number
of
processors.
After
the
di
vision
is
done,
t
he
algorithm
checks
the
feasibility
of
tasks
in
each
allocated
processor
.
The
steps
of
the
algorithm
is
described
belo
w
,
T
able
4.
The
Performance
of
MITD
A
on
a
4
processor
system
sho
wing
the
number
of
tasks
allocated
to
each
of
the
processor
and
the
total
number
of
iterations
tak
en
to
carry
out
the
test.
Number
of
tasks
in
Number
of
tasks
in
Number
of
tasks
in
Number
of
tasks
in
No
of
T
asks
Processor
0
Processor
1
Processor
2
Processor
3
T
otal
Iterations
100
16
13
16
14
70
120
18
19
18
16
101
140
21
22
22
21
90
160
24
23
24
23
98
180
28
31
28
27
163
200
33
33
31
33
362
220
36
36
35
32
447
240
38
37
36
39
448
260
39
41
40
43
540
280
46
45
45
44
607
300
50
49
51
47
793
1.
Allocate
the
tasks
to
pr
ocessor
s
:
The
tasks
are
di
vided
among
the
processors.
This
di
vision
is
done
by
balancing
the
utilization
using
Utilization
Balancing
Algorithm
[13].
2.
Determine
sc
hedulability
of
eac
h
pr
ocessor
:
Each
processor
has
a
number
of
tasks
allocated
to
it
whi
ch
are
balanced
in
terms
of
total
utilization.
On
each
of
these
task-sets,
ITD
A
is
performed.
The
result
obtained
gi
v
es
the
schedulability
of
each
processor
.
Combining
the
results
of
the
indi
vidual
processors,
the
total
schedulability
can
be
estimated.
The
full
algorithm
is
summarised
in
Algorithm
4,
T
aking
the
same
task-set
of
v
ariable
number
of
tasks
and
running
it
for
a
system
of
4
processors
we
get
the
v
alues
at
T
able
4.
In
the
ne
xt
section
we
discuss
the
results
of
MITD
A.
5.
RESUL
T
AND
DISCUSSION
W
e
no
w
discuss
the
results
pro
vided
via
Figure
2,
T
able
2
and
T
able
3.
TD
A
g
a
v
e
the
base
number
of
iterations
depicted
in
T
able
2.
Our
paper
then
used
this
to
compare
the
performance
of
ITD
A
and
MITD
A.
The
results
pro
vided
in
T
able
3
and
4
sho
w
the
number
of
iterations
using
ITD
A
and
for
multiprocessor
en
vironment
using
M
ITD
A.
T
able
4
sho
ws
the
number
of
tasks
allocated
to
each
processor
and
the
total
number
of
iterations
tak
en
for
each
task
set.
It
can
be
seen
that
the
number
of
tasks
allocated
is
such
that
the
total
utilization
of
all
the
processors
are
balanced.
This
also
mak
es
the
number
of
tasks
allocated
to
each
processor
to
be
roughly
equal
in
number
,
and
thus
achie
ving
proper
load
balancing.
Also
by
comparing
this
wi
th
T
able
3
we
can
see
that
the
number
of
iterations
are
less
than
that
of
uniprocessor
.
The
graph
pro
vided
in
Figure
2
sho
ws
this
comparison
in
detail.
The
number
of
iterations
decrease
from
uniprocessor
to
2
processor
en
vironment
and
then
to
4
processor
en
vironment.
The
Figure
2
sho
wed
the
v
ariation
of
the
iterations
from
which
we
can
infer
that
the
algorithm
t
ak
es
less
number
of
iterations
with
increasing
number
of
processors.
Thus,
ITD
A
impro
v
es
the
performance
by
reducing
the
comple
xity
from
linear
to
log
arithmic
terms
and
MITD
A
pro
vides
a
suiT
able
algorithm
to
determine
schedulability
in
a
multiprocessor
en
vironment.
5.1.
Comparision
with
r
elated
w
orks
There
ha
v
e
been
v
ari
ou
s
w
ork
done
on
schedulability
analysis
of
v
arious
priority
based
algorithms.
The
idea
of
discrete
scheduling
points
w
as
tak
en
into
account
in
[15],
although
the
y
propo
s
ed
it
for
EDF
.
Their
w
ork
w
as
impro
v
ed
and
e
xtended
in
[14].
Recently
[7]
proposed
an
Enhanced
T
ime
Demand
analysis
(ETD
A)
which
impro
v
ed
upon
Hyper
-planes
Exact
T
est
proposed
by
Bini
and
Buttazzo
in
[6].
Their
implementation
decreased
the
actual
number
of
scheduling
points.
The
y
measured
the
performance
in
terms
of
total
CPU
time
tak
en
for
a
gi
v
en
task
set
to
be
analyzed.
Our
alogorithm,
ITD
A,
reduced
the
number
of
total
tasks
considered.
T
able
5
sho
ws
the
comparision
between
ETD
A
and
ITD
A.
Since
the
task-set
w
as
is
randomly
generated,
we
took
a
v
erage
of
multiple
readings
to
remo
v
e
an
y
ambiguity
.
Sc
hedulability
of
Rate
Monotonic
Algorithm
using
Impr
o
ved
T
ime
Demand
...
(Leena
Das)
Evaluation Warning : The document was created with Spire.PDF for Python.
438
ISSN:
2088-8708
Algorithm
4:
MITD
A
Input:
task
set
,
pr
ocessor
s
Output:
schedulable
or
Unschedulable
1
Sort
the
task-set;
2
k
=
1
;
3
Initialize
util
iz
ation
=
0
for
each
processor;
4
r
epeat
5
Find
processor
P
k
with
min
util
iz
ation
;
6
Assign
ne
xt
task
T
i
to
P
k
;
7
Update
util
iz
ation
of
P
k
+
=
util
iz
ation
of
T
k
;
8
until
all
tasks
have
been
allocated
;
9
f
or
eac
h
pr
ocessor
P
k
do
10
Considered
allocated
task-set
for
P
k
;
11
k
=
1
;
12
r
epeat
13
T
ask
considered
k
;
14
Calculate
time
points
from
Equation
(5);
15
Calculate
w
(
t
)
from
Equation
(3);
16
if
w
(
t
)
t
then
17
return
N
otschedul
abl
e
;
18
e
xit
algorithm;
19
Calculate
ratio
r
using
Equation
(6);
20
Calculate
v
alue
m
using
Equation
(8);
21
k
=
m
;
22
until
last
task
is
not
c
hec
k
ed
OR
r
atio
1
;
23
return
schedul
ab
l
e
;
T
able
5.
Comparision
of
ETD
A
[7]
with
ITD
A
No
of
T
asks
CPU
time
for
ETD
A
(ms)
CPU
time
for
ITD
A
(ms)
100
45
32
200
56
41
300
70
54
400
121
76
500
158
97
F
or
the
best
of
our
kno
wledge
there
has
been
no
multiprocessor
implementation
of
ETD
A.
Thus
MITD
A
is
presented
as
a
ne
w
algorithm.
Performance
of
MITD
A
depends
of
the
ef
ficienc
y
of
ITD
A.
As
ITD
A
is
sho
wn
to
perform
better
than
ETD
A,
we
can
say
that
MITD
A
is
also
ef
ficient.
The
ETD
A
and
the
ITD
A
can
be
fused
together
to
pro
vide
e
v
en
better
results.
W
e
carried
out
our
tests
independently
as
that
enables
us
to
compare
performance
with
TD
A
directly
.
6.
CONCLUSION
W
e
ha
v
e
de
v
eloped
an
algorithm
that
impro
v
ed
the
e
xisting
TD
A
as
an
e
xact
feasibility
test
for
static
priority
scheduling.
W
e
tested
the
algorithm
for
RMA.
The
proposed
algorithm
is
named
as
ITD
A.
Further
we
e
xt
ended
this
algorithm
multiprocessor
en
vironment.
W
e
named
this
algorithm
as
MITD
A.
Our
algorithm
is
taking
less
number
of
iterations
than
the
e
xisting
TD
A
algorithm.
ITD
A
can
be
used
along
with
other
e
xact
sceduability
tests
to
gi
v
e
e
v
en
better
performance.
Further
using
MITD
A
we
s
ho
w
that
on
increasing
the
number
of
processors
the
total
number
of
iterations
decrease.
Our
future
w
ork
will
be
to
introduce
task
dependenc
y
for
MITD
A.
In
our
current
task-sets
the
tasks
are
assumed
to
be
independent
of
each
other
.
Another
future
w
ork
is
to
e
x
ecute
MITD
A
in
parallel
so
as
to
further
reduce
the
time
required
to
compute
feasibility
.
This
can
be
achie
v
ed
usi
ng
nati
v
e
pthreads
or
OpenMP
using
shared
memory
architecture.
IJECE
V
ol.
8,
No.
1,
February
2018:
429
–
440
Evaluation Warning : The document was created with Spire.PDF for Python.