In e na ional Jou nal o Embedded Sys ems and Applica ions (IJESA) Vol.3, No.3, Sep embe 2013
DOI : 10.5121/ijesa.2013.3301 1
TEMPORAL WORKLOAD ANALYSIS AND ITS
APPLICATION TO POWER-AWARE SCHEDULING
Ye-In Seol1, Jeong-Uk Kim1 and Young-Kuk Kim2,
1G een Ene gy Ins i u e, Sangmyung Uni e si y, Seoul, Sou h Ko ea
2Dep . o Compu e Sci. & Eng., Chungnam Na ‟l Uni e si y, Daejeon, Sou h Ko ea
ABSTRACT
Powe -awa e scheduling educes CPU ene gy consump ion in ha d eal- ime sys ems h ough dynamic
ol age scaling(DVS). The basic idea o powe -awa e scheduling is o ind slacks a ailable o asks and
educe CPU‟s equency o lowe i s ol age using he ound slacks. In his pape , we in oduce empo al
wo kload o a sys em which speci ies how much busy i s CPU is o comple e he asks a cu en ime.
Analyzing empo al wo kload p o ides a su icien condi ion o schedulabili y o p eemp i e ea ly-deadline
i s scheduling and an e ec i e me hod o iden i y and dis ibu e slacks gene a ed by ea ly comple ed
asks. The simula ion esul s show ha p oposed algo i hm educes he ene gy consump ion by 10-70%
o e he exis ing algo i hm and i s algo i hm complexi y is O(n). So, p ac ical on-line schedule could be
de ised using he p oposed algo i hm.
KEYWORDS
Powe -awa e Scheduling, Real- ime Scheduling, Embedded Sys ems
1. INTRODUCTION
Ene gy consump ion issues a e becoming mo e impo an o mobile o ba e y-ope a ed
embedded sys ems. Since he ene gy consump ion o CMOS ci cui s, used in a ious
mic op ocesso s, has a quad a ic dependency on he ope a ing ol age( )[2], i is a e y
use ul me hod o educing ene gy consump ion o lowe he ope a ing ol age o ci cui s. Bu ,
lowe ing he ope a ing ol age also dec eases i s clock speed o equency, so he execu ion imes
o asks a e p olonged. This makes p oblem mo e complex o ha d eal- ime embedded sys ems
whe e iming cons ain s o asks should be me .
The e has been signi ican esea ch e o on Dynamic Vol age Scaling(DVS) o eal- ime
sys ems o educe ene gy consump ion while sa is ying he iming cons ain s[1,4-6,8-11,13]. The
chance o lowe i s ol age occu s when he e a e slacks o he cu en execu ing eal- ime ask.
Gene ally he e a e wo sou ces o slack, i.e., when he sum o wo s case execu ion imes o asks
is below he CPU‟s p ocessing capaci y and when a ask comple es ea ly wi hou consuming i s
wo s case execu ion ime. Main conce n o DVS algo i hms is how o iden i y hose slacks and
how o dis ibu e hem.
DVS algo i hms also depend on he scheduling policy, ask model, and p ocesso a chi ec u e. In
his pape , we adop Ea ly-Deadline Fi s (EDF) scheduling policy, pe iodic o spo adic ask
model and unip ocesso sys em. EDF assigns dynamic p io i y o eady asks and i is known as
op imal o unip ocesso sys em[7]. Pe iodic ask model assumes asks a e eleased pe iodically
and hei ela i e deadlines a e he same as hei espec i e pe iods. Spo adic ask model allows
In e na ional Jou nal o Embedded Sys ems and Applica ions (IJESA) Vol.3, No.3, Sep embe 2013
2
asks a e eleased andomly, bu he e is a es ic ion on he minimum in e -a i al ime o he
same ask. In hose ask models, we equi e a p io i knowledge o asks, i.e., pe iod, wo s -case
execu ion ime, o minimum in e -a i al ime, e c. Some wo ks don‟ assume hese kinds o
in o ma ion[5], o adop ape iodic ask model[11,12]. Bu , many ha d eal- ime applica ions a e
classi ied as pe iodic o spo adic, so conside ing pe iodic and/o spo adic ask model is p ac ical.
In his pape , we in oduce a no ion o empo al wo kload which e lec s how much busy he
sys em is. I will be showed ha analyzing empo al wo kload p o ides a use ul me hod o eal-
ime scheduling, especially EDF. We analyze he beha io s o EDF scheduling using empo al
wo kload, and p esen some in e es ing esul s by which we unde s and mo e deeply he ea u es
o EDF scheduling.
Also we apply he analysis esul s in o powe -awa e scheduling, and p esen an algo i hm which
adop s he esul s o CC-EDF[9] and empo al wo kload analysis. The simula ion esul s show
ha he p oposed algo i hm wi h a o dable algo i hmic complexi y educes mo e ene gy
consump ion han p e ious wo k.
The es o he pape is o ganized as ollows. In sec ion 2, we p esen he sys em model and
no a ions adop ed in his pape and in oduce some p e ious wo ks which mo i a e he wo k done
in his pape . In sec ion 3, we de ine he empo al wo kload and analyze EDF scheduling using i .
In sec ion 4, we p esen a powe -awa e scheduling algo i hm de i ed om he empo al wo kload
analysis. In sec ion 5, simula ion esul s will be p o ided and sec ion 6 will conclude and discuss
he u u e di ec ions o his pape .
2. MOTIVATION
In his sec ion we p esen he sys em model and in oduce he esul o he ela ed wo k.
2.1. Sys em Model
We conside p eemp i e ha d eal- ime sys em in which all asks a e pe iodic o spo adic and
mu ually independen . The a ge p ocesso is DVS enabled unip ocesso and i s supply ol age
and equency a e a ied con inuously be ween [ min, max] and [ min, max], espec i ely. Le
* + be a se o pe iodic o spo adic asks. Each ask is ep esen ed as
( ) whe e
is pe iod o pe iodic ask o minimum in e -a i al ime o spo adic ask;
is wo k-case compu a ion ime o ask Ti a he maximum equency;
Di is ela i e deadline o a ask Ti.
I a ins ance o job o ask eleased a , hen i s absolu e deadline( ) is . We
will conside asks only wi h , so ask could be ep esen ed as ( ). Also he
ollowing no a ions will be used.
o : he wo s -case u iliza ion o ask a he maximum equency, i.e.,
⁄.
o : he wo s -case o al u iliza ion o all asks in he sys em, i.e., ∑
.
: ask‟s ac ual compu a ion ime which should be less han . Fo uncomple ed
asks, .
: ac ual u iliza ion o ask, i.e., .
: ac ual o al u iliza ion o sys em, i.e., ∑
: ask‟s emaining compu a ion ime.
: j h ins ance o job o ask .
In e na ional Jou nal o Embedded Sys ems and Applica ions (IJESA) Vol.3, No.3, Sep embe 2013
3
: cu en equency a io, i.e., cu / max
: ask‟s execu ion ime, i.e., .
: ask‟s emaining execu ion ime, i.e.,
elease ime o ask
2.2. Rela ed Wo k
EDF scheduling has been ex ensi ely in es iga ed in he a ea o eal- ime and powe -awa e
scheduling[1,3-5,7-12]. Bu , some dynamic na u es o EDF we e no ully exploi ed, o example
dynamic densi y unc ion in oduced in [6]. Dynamic densi y o a job is de ined as i s emaining
execu ion ime di ided by he ime o deadline. They deal wi h he case o uni execu ion ime and
mul i-p ocesso sys em using dynamic densi y unc ion. Tempo al wo kload in oduced in his
pape is simila o iden ical o dynamic densi y unc ion, so we can say ha we ex ended hei
esul s in o mo e gene al ask model, bu unip ocesso sys em.
While de ising a new powe -awa e scheduling algo i hm based on he empo al wo kload
analysis, we especially conside ed he esul s p esen ed by Pillai and Shin[9]. They in oduced a
cycle-conse ing me hod o eal- ime DVS. This me hod educes he ope a ing equency on each
ask comple ion and inc eases on each ask elease. When a ask comple es i s cu en in oca ion
a e using compu a ion ime, hey ea he ask as i i s wo s -case execu ion ime we e .
So p ocesso speed could be se as he ac ual o al u iliza ion which is always less han o
equals o wo s -case o al u iliza ion .
Mei e al.[8] in eg a ed he abo e cycle-conse ing me hod and he esul o Qadi e al.[10] o
spo adic ask se . Bu , hese me hod doesn‟ ully u ilize he slack gene a ed. Le ‟s see he
ollowing igu e. I a ask comple ed a , hen du ing he ime in e al , - he sys em
ope a ed a highe equency han equi ed. This obse a ion p o ides a clue o mo e slow down
he p ocesso when a ask comple es. We will show la e ha he amoun o slack which could be
used o lowe ing p ocesso equency is ela ed wi h empo al wo kload o he comple ed ask.
Figu e 1. CC-EDF[9] o CC-DVSST[8] Schedule
3. TEMPORAL WORKLOAD ANALYSIS
In his sec ion, we in oduce some de ini ions and analyze beha io s o EDF scheduling. This
sec ion will p o ide a conc e e heo e ical basis o he powe -awa e scheduling algo i hm
p esen ed in he nex sec ion.
3.1. Tempo al Wo kload
De ini ion 1: Tempo al wo kload o a ask a ime , ( ) o i no con using, is de ined
as ( ) o 0 i i is comple ed be o e o a . Tempo al wo kload o a sys em a ime ,
( ) o , is he sum o empo al wo kloads o all asks in he sys em a ime .
Tempo al wo kload o a ask is simila o iden ical o dynamic densi y o a job[6], bu we
in oduce new no ion o empo al wo kload o dis inguish emaining execu ion ime and
( )
In e na ional Jou nal o Embedded Sys ems and Applica ions (IJESA) Vol.3, No.3, Sep embe 2013
4
emaining compu a ion ime, so mo e applicable o powe -awa e scheduling. Following no a ions
a e also used h oughou his pape .
o ( ) : empo al wo kload o ask se
o ( ) : empo al wo kload o a ask in ask se
( ( ) ( )) : ( ) when execu es du ing , ), and execu es
du ing , ).
Fo he ime being, R because we schedule asks wi h ull speed o CPU, i.e., .
Lemma 1: is mono onically dec easing du ing a ime in e al , ) i no ask was eleased
du ing ha in e al, ( ) , and we schedule wi h EDF.
P oo : Le ask was execu ed du ing , ), hen by de ini ion o empo al wo kload,
( )
, ( )
.
( ) ( ) .
/ 0
1 .
/
( )( ) ( )
( )( )
( )( )
=
∑
( )( )
( ∑(
) ) (1)
By assump ion, ( ) ∑
, and o we schedule wi h EDF,
is always less han
o equals o 1, so Equa ion (1) is always la ge han o equals o 0 which implies is
mono onically dec easing.
Now we conside which ask we schedule a ime e ec s on empo al wo kload o a sys em.
Lemma 2: ( ( )) ( ( )) .
P oo : ( ( )) and ( ( )) a e he empo al wo kloads o a sys em a ime
when we schedule and espec i ely a ime . So,
( ( ))
. ( )/
( ( )) . ( )/
(
) (2)
By assump ion, Eq. 2 is less han 0 which implies Lemma 2 is ue.
Lemma 2 p o ides ano he clue ha EDF scheduling policy is op imal in p eemp i e unip ocesso
scheduling.
Co olla y 1: ( ( )) ( ( )) .
Co olla y 1 s a es ha empo al wo kload o a sys em doesn‟ depend on which ask execu e a
ime when asks‟ deadlines a e he same.
Lemma 3: ( ( ) ( )) ( ( ) ( )) .
In e na ional Jou nal o Embedded Sys ems and Applica ions (IJESA) Vol.3, No.3, Sep embe 2013
5
P oo : ( ( ) ( )) is he empo al wo kload o a sys em when we schedule a
, ) and a , ) and ( ( ) ( )) is he empo al wo kload
o a sys em when we schedule a , ) and a , ) , bu a ime
( ), has he same because is he same o he wo cases, and also. So,
Lemma 3 holds.
Lemma 3 implies ha he o de o execu ion has no e ec on he las empo al wo kload o a
sys em i he e is no deadline miss. Which ask execu ed and how much i execu ed du ing a ime
in e al conce n only he calcula ion o he las empo al wo kload o a sys em.
A Lemma 1, we p o ed he mono onic dec easing p ope y o empo al wo kload unde EDF
scheduling. Mo e in es iga ion shows ha when a ask‟s deadline expi es, hen he empo al
wo kload o a sys em dec eases as leas as he empo al wo kload o he ask i he e is no ask
elease du ing he ime in e al. Following Lemma p o es he abo e discussion.
Lemma 4: ( ) ( ) ( ) i he e is no ask elease du ing ( ), ( )
and we schedule using EDF.
P oo : Le ‟s conside a ideal CPU ha execu es e e y asks concu en ly p opo ional o hei
ini ial empo al wo kload. This could be accomplished by minimizing δ as small as possible in
Fig. 2.
Figu e 2. Ideal CPU execu ion
Figu e 3. Real CPU execu ion
The execu ion o ideal CPU could be eloca ed as he igh side o Fig. 2. Because only he
amoun o execu ion ime con ibu es o las empo al wo kload by Lemma 3, empo al wo kload
o bo h side o Fig. 2 is he same. Also, he execu ion o eal CPU could be eloca ed as he igh
side o Fig. 3. A he igh side o Fig. 3, he a eas o „a‟ and „b‟ equal o o al compu a ion ime
could no be changed. By Lemma 2, empo al wo kload o he eal CPU is less han o equals o
ha o he ideal CPU. The empo al wo kloads o asks in ideal CPU don‟ change du ing he ime
in e al , ) and he empo al wo kload o he ask whose deadline is se s o ze o a
. So,
( ) o he eal CPU ( ) o he ideal CPU
( ) ( ) (3)
a
b
In e na ional Jou nal o Embedded Sys ems and Applica ions (IJESA) Vol.3, No.3, Sep embe 2013
6
In he p ocess o p o ing Lemma 4, we p esen ed a use ul high limi o empo al wo kload unde
EDF scheduling. I is ha empo al wo kload o ideal CPU sys em p o ides an in ui i e high limi
as Eq. (3) s a es.
3.2. Tempo al Wo kload Isomo phic
Now we in oduce new no ion o compa e empo al wo kloads o di e en sys ems.
De ini ion 2: Task sys ems, and , a e empo al-wo kload-isomo phic i such ha
( ) ( ) o all ime .
I empo al wo kload alue o sys em is always he same o cons an mul iples o ha o sys em
, hen we can easily assume ha schedulabili y condi ions o wo sys ems a e e y close o he
same and schedule beha io s a e e y simila o each o he .
Lemma 5: Following wo pe iodic ask sys ems, and a e empo al-wo kload-isomo phic unde
wo s -case execu ion scena ios.
* ( ), whe e * + could be mul ise . EDF scheduling}
* ( ∑ ) . * + is dis inc se o * +, i.e., i . is o all o A
such ha . EDF scheduling} .
P oo : Le ’s conside in and i s cousin asks * + in , i.e., o . Then elease imes
and deadlines o all abo e asks a e he same. Unde EDF scheduling, deadline o ask is he only
c i e ion o scheduling, hen we can make he ollowing condi ion hold ha i we schedule a job
o , hen a job o some co esponding ‟s is scheduled. I no , hen he e could be one o mo e
jobs whose deadline is coincided wi h . Bu , despi e he exis ence o ano he job o he same
deadline and a di e en schedule could be done a ha momen , by Lemma 3 and
Co olla y 1. Also, he las ime a which all jobs o he same deadline a e comple ed is he same
o and . So, Lemma 5 holds.
Now, we conside he schedulabili y condi ion o ask sys em using empo al wo kload.
Following Lemma is di ec ly implied om he de ini ion o empo al wo kload because empo al
wo kload iden i ies he amoun o wo k o be done un il deadline o each ask.
Lemma 6: I wo ini e ask sys em and a e empo al-wo kload-isomo phic, hen
schedulabili y condi ions o wo sys ems a e iden ical.
P oo : We p o e his Lemma by con adic ion. I ask sys em has iola ed i s iming cons ain s
and no , hen he e exis s a ask o such ha
.
Bu empo al wo kload o sys em could no each in ini e because i has ini e asks and each
ask o sys em has ini e alue o empo al wo kload. This con adic s wi h assump ion o his
Lemma.
3.3. Uppe Bound o Tempo al Wo kload
De ini ion 3: Task sys em is empo al-wo kload-uppe -bounded i ( ) o all ime .
will deno e he uppe bound .
In e na ional Jou nal o Embedded Sys ems and Applica ions (IJESA) Vol.3, No.3, Sep embe 2013
7
Because empo al wo kload o a sys em deno es he a io o o e head o CPU capaci y, we may
schedule all he asks o he sys em wi hou iola ing i s iming cons ain s i is below o
he same as 1. Following heo em shows abo e discussion is ue.
Theo em 1: I ( ) o all ime , i.e., , hen ask se is schedulable using
EDF.
P oo : We will p o e i by induc ion on ime . Le ‟s assume ha his heo em holds un il ime ,
i.e., we success ully scheduled he asks un il ime . A ime , we can s ill schedule he highes
p io i y ask, i.e., he sho es deadline ask, wi hou iola ing i s deadline i he e is no ask
elease du ing ( ) o ( ) ( ). I he e is a ask elease a ime whe e
, hen we can insis ha his heo em s ill hold un il ime because he e is no
deadline du ing ( ). F om he assump ion, a , he empo al wo kload o ask se
should be less o equals o 1. So, we p o ed ha his heo em s ill holds un il o
which a e la ge han i i holds a .
Theo em 1 s a es ha i we p ese e he uppe bound o empo al wo kload below o equal o 1,
hen i is always schedulable. Also heo em 1 p o ides a su icien condi ion o he
schedulabili y o a sys em. Now we in es iga e he empo al wo kload uppe bounds o pe iodic
ask sys ems.
Theo em 2: Fo a pe iodic o spo adic ask sys em * ( ). EDF+, s ∑ .
P oo : We al eady said ha ideal CPU wi h EDF scheduling policy p o ides an uppe bound o
empo al wo kload. Fo a pe iodic o spo adic ask sys em o ideal CPU, clea ly i s empo al
wo kload is always less han o equals o i s o al u iliza ion. So heo em 2 holds.
3.3. Tempo al Wo kload a Lowe P ocessing Speed
Now, we conside he case o , i.e., CPU‟s p ocessing speed is no always 1.
Lemma 7: Following wo pe iodic ask sys ems, and a e empo al-wo kload-isomo phic unde
wo s -case execu ion scena ios.
* ( ) ∑ , CPU‟s p ocessing speed is ( ), EDF},
* ( ) , CPU‟s p ocessing speed is 1, EDF}.
P oo : Clea ly a ime = 0, ( ) ( ) by de ini ion 1. And when we execu e a ask
o sys em , a ime , ollowing holds.
( ) ( ) .
( ) ( ) ( )
( )
( )
(4)
Eq. (4) s a es ha i we execu e asks o he same deadline a he same ime o sys em and ,
hen he a io o empo al wo kloads o wo sys ems a e no changed. Because and use EDF
scheduling policy and execu ion imes(no compu a ion imes) and deadlines o and i s
co esponding a e iden ical unde wo s -case execu ion scena ios, Lemma 7 holds. The e could
be he cases when we execu e o and o , i.e., deadlines o wo asks a e coinciden ly
exac , bu by Lemma 3 and Co olla y 1, Lemma 7 s ill holds as we insis ed a Lemma 5.
Co olla y 2: Fo a pe iodic ask sys em * ( ) ∑ +, hen we can schedule
wi h cons an CPU speed .
In e na ional Jou nal o Embedded Sys ems and Applica ions (IJESA) Vol.3, No.3, Sep embe 2013
8
P oo : By Lemma 7, we can cons uc a empo al-wo kload-isomo phic sys em o whose
is 1 and i s CPU p ocessing speed is 1. Then by heo em 1, he newly cons uc ed ask se
could be success ully scheduled wi h EDF. By Lemma 6, his shows ha o iginal ask se could
be success ully scheduled.
Using Lemma 7 and Co olla y 2, we can sa ely lowe p ocessing speed o pe iodic eal- ime ask
sys em when i s o al u iliza ion is below 1 as many p e ious wo ks o powe -awa e scheduling
said.
Following heo em is he epe i ion o Theo em 4 o DVSST pape [10]. DVSST algo i hm scales
up CPU whene e new ask eleases and scales down whene e i s deadline expi es exac ly as
much as u iliza ion o ha ask.
Theo em 3: Spo adic ask sys em wi h ∑ and DVSST algo i hm, i is schedulable using
EDF i and only i ∑
.
P oo : “Only I ” pa : As he asse ion s a ed in [10], i , hen EDF will no ind a easible
schedule, he e o e DVSST combined wi h EDF will no ind a easible schedule.
“I ” pa : As we s a ed a Lemma 4, ideal CPU can p o ide an uppe bound o empo al
wo kload. So, whene e a new ask eleased, empo al wo kload o ideal CPU sys em inc eased
as much as u iliza ion o ha ask du ing , - and whene e a deadline o a ask expi es i
dec eased also as much as ha amoun . Now suppose ha he e is nei he new ask elease no
deadline expi a ion du ing , - and is he empo al wo kload o ideal CPU du ing he ime
in e al, hen we can cons uc a new ask sys em whose o al u iliza ion is 1 and each ask has
he same deadline o o iginal co esponding ask and i s compu a ion ime is .
Then by Theo em 1, we can schedule new ask sys em using EDF and by Lemma 6, we can say
ha we can schedule o iginal ask sys em wi h EDF o wo ask sys ems a e empo al wo kload
isomo phic du ing he in e al. And o wo ask sys ems ha e iden ical deadline dis ibu ions, we
always make su e ha ( ) pai o asks execu e a he same ime in each sys em wi hou
iola ing EDF policy. So by Lemma 7, abo e p ocess could be epea ed a e e y ime in e al
du ing which nei he new ask eleases no deadline expi es. This p o es „i ‟ pa .
Following heo em 4 s a es ha empo al wo kload analysis p o ides ano he use ul
schedulabili y es .
Theo em 4: Le = {pe iodic o spo adic ask sys ems whose o al u iliza ions a e less han o
equal o 1}, = { ask sys ems whose a e less han o equal o 1}, and = { ask
sys ems whose loading ac o s[5]( ((∑ ) ( ))) a e less han o equal o
1}, hen
.
P oo : By Theo em 2,3 and Co olla y 2, clea ly . Bu doesn’ assume
nei he minimum in e al no pe iodici y o asks, so .
is he maximum se o asks which could be scheduled by EDF because loading ac o es
p o ides necessa y and su icien condi ion[5]. So, . Bu , o he ollowing ask
se * ( ) +, , bu . So,
Theo em 4 holds.
In e na ional Jou nal o Embedded Sys ems and Applica ions (IJESA) Vol.3, No.3, Sep embe 2013
9
The empo al wo kload o he ask se in Theo em 4 is in ini e when N is in ini e, so he e is no
uppe limi ed alue o which p o ides necessa y condi ion o schedulabili y es .
4. POWER-AWARE SCHEDULING ALGORITHM
4.1. An On-Line Algo i hm
In sec ion 3, we analyzed scheduling beha iou s o EDF using empo al wo kload. Now we apply
he esul s in o powe -awa e scheduling. As we s a ed a sec ion 2, p e ious algo i hms such as
CC-EDF, DVSST and CC-DVSST don‟ ully u ilize he slacks gene a ed by ea ly comple ed
asks. Bu , based on he empo al wo kload analysis, we can ind mo e slacks o slow down he
CPU speed. Be o e p esen ing mo e discussion, le ‟s in oduce new de ini ion.
De ini ion 4: Tempo al idleness ( ) o a ask a ime is de ined as ollowing.
0 un il i s comple ion and a e i s deadline.
( ) i i was comple ed a ime and .
( ) i .
The eal alue o depends on he s a us o sys em and how o calcula e will be p esen ed la e .
Likewise he de ini ion o empo al wo kload o a sys em, empo al idleness o a sys em, ( ) o
, is de ined as he sum o ( ). No e ha ( ) is he same as ( ) o uncomple ed case.
Now, conside he amoun o compu a ion ime un il i s comple ion. A CC-EDF and CC-DVSST,
hey lowe he p ocessing speed o ask when i is comple ed. This means ha i s pace o
compu a ion is as e han ac ual execu ion needed as s a ed a sec ion 2. Following igu e shows
he si ua ion.
Figu e 4. Compu a ion ime compa ison
A ime , ask was comple ed, so du ing , -, i s compu a ion ime(= ) is
la ge han needed ( ) as amoun o ( ). I we assume ha ask execu ed wi h i s
empo al wo kload du ing , -, hen ( ) ( ) equals o ( ) and
( ) ( ) equals o ( ) . Bu , ( ) , (
) ( ). So, , i.e., . I is ha he
amoun o slack could be used un il i s deadline is ( ) ( ) , i.e.,
( ). Following lemma shows i o mally.
Lemma 8: A CC-EDF o CC-DVSST scheduling, he amoun o compu a ion ime exceeding i s
ac ual pace un il i s comple ion ime( ) is he same as , ( ) ( )- ( ).
P oo : , ( ) ( )- ( )
0
1 ( )
( )
( )
b
a
c
d
e
g
h
In e na ional Jou nal o Embedded Sys ems and Applica ions (IJESA) Vol.3, No.3, Sep embe 2013
16
6. CONCLUSION
In his pape , we analyzed he beha io s o EDF scheduling and p esen ed a powe -awa e
scheduling algo i hm o pe iodic and spo adic asks. Tempo al wo kload analysis p o ides
ano he su icien condi ion o schedulabili y o p eemp i e eal- ime ask scheduling and
ano he o mal me hod o p o e he co ec ness o powe -awa e scheduling algo i hms. The
p oposed algo i hm also adop s he esul s o cycle conse ing me hod(CC-EDF) and spo adic
ask scheduling(DVSST). The simula ion esul s show ha he p oposed algo i hm ou pe o ms
exis ing algo i hms up o 10-70 % wi h espec o CPU ene gy sa ing.
In he u u e we would like o imp o e he p oposed algo i hm. This could be done i we assign
all slacks gene a ed by ea ly comple ed highe p io i y asks in o he ask o highes p io i y
among uncomple ed eady asks ins ead o e enly dis ibu ing hem un il he ends o deadlines.
This me hod may lowe p ocesso equency much mo e han he p oposed algo i hm. Also we
would like o apply he empo al wo kload analysis in o ano he a ea o eal- ime ask scheduling,
o example, ape iodic ask accep ance p oblem. I we could main ain he empo al wo kload o a
sys em below o equal o 1, hen eal- ime cons ain s o all asks in he sys em a e me . So his
may p o ide an e ec i e me hod o ape iodic ask scheduling.
ACKNOWLEDGEMENTS
This wo k was suppo ed by he Indus ial S a egic Technology De elopmen P o-
g am(10041740, De elopmen o a so wa e ha p o ides cus omized eal- ime op imal con ol
moni o ing se ices by in eg a ing equipmen s in buildings wi h web se ice) unded by he
Minis y o T ade, Indus y and Ene gy(MOTIE, Ko ea).
REFERENCES
[1] H. Aydin, R. Melhem, D. Mosse and P. Mejia-Al a ez, “Powe -awa e scheduling o pe iodic eal-
ime asks,” IEEE T ans. on Compu e s, Vol. 53, pp 584-600, 2004.
[2] T. D. Bu d and R. W. B ode sen, “Ene gy e icien CMOS mic op ocesso design,” In P oc. o
Twen y-Eigh h Hawaii In ‟l Con . on Sys em Sciences, Vol. 1, 1995.
[3] H. Che o and M. Che o. “Some Resul s o he Ea lies Deadline Scheduling Algo i hm,” IEEE
T ansac ions on So wa e Enginee ing, Vol.15(10),pp.1261–1269, 1989.
[4] W. Kim, J. Kim, and S. L. Min, “A Dynamic Vol age Scaling Algo i hm o Dynamic-P io i y Ha d
Real-Time Sys ems Using Slack Time Analysis,” In P oc. o Design, Au oma ion and Tes in Eu ope,
pp. 788–794, 2002.
[5] C. H. Lee and K. G. Shin, “On-line dynamic ol age scaling o ha d eal- ime sys ems using he EDF
algo i hm,” In P oc. o IEEE In ‟l Real-Time Sys ems Symposium, pp. 319-327, 2004.
[6] J. Lee, A. Easwa an, I. Shin, and I. Lee, “Mul ip ocesso eal- ime scheduling conside ing
concu ency and u gency,” ACM SIGBED Re iew, Vol. 7(1), 2010.
[7] C. L. Liu and J.W. Layland, “Scheduling algo i hms o mul ip og amming in a ha d eal- ime
en i onmen ,” J. ACM Vol.20(1), pp 46-61, 1973.
[8] J. Mei, K. Li, J. Hu, S. Yin, and E. H-M Sha, “Ene gy-awa e p eemp i e scheduling algo i hm o
spo adic asks on DVS pla o m,” Mic op ocesso s & Mic osys ems, Vol.37, pp. 99-112, 2013.
[9] P. Pillai and K. G. Shin, “Real- ime dynamic ol age scaling o low-powe embedded ope a ing
sys ems,” ACM SIGOPS Ope a ing Sys em Re iew,Vol.35(5), pp. 89-102, 2001.
[10] A. Qadi, S. Godda d, and S. Fa i o , “A dynamic ol age scaling algo i hm o spo adic asks,” In
P oc. o IEEE In 'l Real-Time Sys ems Symposium, pp 52-62, 2003.
[11] D. Shin and J. Kim, “Dynamic ol age scaling o pe iodic and ape iodic asks in p io i y-d i en
sys ems,” In P oc. o he Asia and Sou h Paci ic Design Au oma ion Con e ence, pp 653-658, 2004.
[12] M. Spu i and G. Bu azzo, “Scheduling ape iodic asks in dynamic p io i y sys ems,” Real-Time
Sys ems, Vol.10(2),pp.179–210, 1996.
In e na ional Jou nal o Embedded Sys ems and Applica ions (IJESA) Vol.3, No.3, Sep embe 2013
17
[13] F. Yao, A. Deme s, and S. Shenke , “A scheduling model o educed CPU ene gy,” In P oc. o he
IEEE Founda ions o Compu e Science, pp.374–382, 1995.
[14] RTSIM:Real- ime sys em simula o , h p:// sim.sssup.i .
AUTHORS
Ye-In Seol ecei ed his B.S. deg ee in Nuclea Enginee ing om Seoul Na ional
Uni e si y, Ko ea in 1992, M.S. deg ee in Compu e Science and S a is ics om Seoul
Na ional Uni e si y in 1994. He is a chie esea che in G een Ene gy Ins i u e o
SangMyung Uni e si y in Seoul. His esea ch in e es s include embedded sys em,
eal- ime sys em and building au oma ion sys em.
Jeong-Uk Kim ecei ed his B.S. deg ee in Con ol and Ins umen a ion Enginee ing
om Seoul Na ional Uni e si y, Ko ea in 1987, M.S. and Ph.D. deg ees in Elec ical
Enginee ing om Ko ea Ad anced Ins i u e o Science and Technology in 1989, and
1993, espec i ely. He is a p o esso in SangMyung Uni e si y in Seoul. His esea ch
in e es s include sma g id demand esponse, building au oma ion sys em, and
enewable ene gy.
Young-Kuk Kim ecei ed he B.S. and M.S. deg ees in Compu e Science and
S a is ics om Seoul Na ional Uni e si y, Ko ea in 1985 and 1987 espec i ely and he
Ph.D. deg ee in Compu e Science om Uni e si y o Vi ginia, Cha lo es ille,
Vi ginia in 1995. A e his Ph.D., he isi ed VTT In o ma ion Technology, Finland
and SINTEF Telecom & In o ma ics, No way as an ERCIM esea ch ellow du ing
1995-1996. He joined he Chungnam Na ional Uni e si y as a acul y membe o he
Compu e Science Depa men in Ma ch 1996. F om Augus 2002 o July 2003, he
isi ed Compu e Science Depa men a Uni e si y o Cali o nia, Da is as an
exchange schola . His esea ch in e es s include eal- ime sys ems, da abase sys ems,
mul imedia and mobile in o ma ion sys ems
