TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.5, May 2014, pp
. 3266 ~ 32
7
1
DOI: http://dx.doi.org/10.11591/telkomni
ka.v12i5.4945
3266
Re
cei
v
ed O
c
t
ober 1
5
, 201
3; Revi
se
d Novem
b
e
r
25, 2013; Accept
ed De
cem
b
e
r
12, 2013
Test Method for Process Deadlock Based on Graph
Grammars
Yi Wang*
1,2
, Han Din
g
1
, Fan Yang
1
1
School of Mat
hematic
al an
d
Comp
uter Scie
nces
, Hub
e
i U
n
iversit
y
of Arts and Scie
nce,
Xi
an
g Yan
g
, 4410
53, Ch
ina,
No.29
6
of Lon
gzho
ng R
oad
2
Institute of Intelli
ge
nce Sci
e
n
c
e and T
e
chno
log
y
, Ho
hai U
n
i
v
ersit
y
,
Nanj
in
g, 210
09
8, P.R. China
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: dhnats@
16
3.com
A
b
st
r
a
ct
T
h
is pap
er pr
opos
es a test
meth
od for p
r
ocess de
ad
lo
ck base
d
on
grap
h gra
mma
rs throug
h
co
n
s
tru
c
ti
ng
p
r
o
c
e
ss re
so
u
r
ce
d
i
a
g
r
am
. Th
ro
u
g
h
u
s
i
n
g
th
e co
n
s
tru
c
ti
on
ru
l
e
s, i
t
can
con
s
tru
c
t a
n
d
j
udge
the val
i
dity of
the proc
ess re
source
dia
g
ra
m. T
h
rou
gh
u
s
ing th
e test rules, it
ca
n te
st if there is th
e
dea
dlock
in th
e process. T
h
e metho
d
is a
graph
ica
l
ap
p
r
oach; it is si
mp
le a
nd i
n
tui
t
ive w
i
th strong
oper
abi
lity.
Ke
y
w
ords
: pro
c
ess, dead
lock
, test, graph gr
ammars
Copy
right
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
The
b
a
si
c ch
ara
c
teri
stics of
ope
rating system
are
concurrent a
n
d
sh
arin
g. A system
allows multip
le pro
c
e
s
se
s to execute
con
c
u
r
rently, and
sha
r
e
s
t
he software and
hardware
resou
r
ces. In
ord
e
r to m
a
ximize the
use of t
he
com
puter
system
re
sou
r
ces, o
peratin
g sy
st
em
sho
u
ld ad
opt
the strategy
of dynamic al
locatio
n
f
o
r t
he sy
st
e
m
re
sou
r
c
e
s.
Usi
ng t
h
is
st
rat
e
gy
,
however, wh
en the a
ppli
c
ation num
be
r is big
g
e
r
th
a
n
the ent
ry n
u
mbe
r
for
a
certai
n type
s
o
f
r
e
so
ur
ce
, if th
e
a
lloc
a
tion is
imp
r
op
er
, it ma
y oc
cur
th
a
t
w
a
itin
g fo
r
re
so
ur
ces
be
tw
ee
n
the
pro
c
e
s
ses
a
nd could n
o
t move forwa
r
d, ma
ke the
pro
c
e
s
ses
b
l
ock ea
ch ot
her. In fact,
the
appli
c
ation fo
r the
sou
r
ces betwe
en the
different
p
r
o
c
e
s
ses
may
get so
me me
et acco
rding
with
a certain
ord
e
r; this is likely to ca
use
two o
r
mo
re
pro
c
e
s
ses m
u
tual blo
c
kad
e
. Each
process
“cat
che
s
” so
me re
so
urce
s, whi
c
h th
e
other
pro
c
e
s
ses
are
wa
iting for. Th
e re
sult is that
whi
c
heve
r
p
r
oce
s
s al
so
can not
get the all
re
sou
r
ce
s, and
all
of these
pro
c
e
s
ses
ca
n
not
contin
ue to ru
n.
Traditio
nal m
e
thod of testi
ng the p
r
o
c
ess dea
dl
o
ck
d
e
script
s by te
xt, but the text is long
and the
way
of thinkin
g
is
not cle
a
r. Thi
s
pa
per
,
base
d
on the
prin
ciple of graph
gramm
a
rs, u
s
es
the con
s
tru
c
tion rule
s
con
s
truct a
nd j
udg
e the validity
of the p
r
o
c
e
s
s resou
r
ce di
agra
m
. Th
rou
gh
usin
g the test
rule
s, it can test if there is
t
he deadl
ock
in the pro
c
e
s
s. The meth
o
d
is a graphi
cal
approa
ch; it is simpl
e
and i
n
tu
itive with strong op
erabil
i
ty.
2. Graph Gra
mmars
Grap
h g
r
am
mar [1-5] is u
s
ed to d
e
fine
and an
alyze
the figure. T
he figure is a
b
stra
cte
d
as a two-di
m
ensi
onal o
b
je
ct with no
de
s and edg
es.
Grap
h gram
mar involve
s
operation
s
in
clude
derivation
an
d redu
ction. I
n
the
ap
plicat
ion, they
we
re al
so
u
s
ed
i
n
a
variety fi
elds [6-9]. Ba
sic
con
c
e
p
ts an
d
operatio
ns a
r
e introdu
ce
d simply as foll
ows:
Defini
tion 1
G= (V, E, LV, LE, S, T) is a
figure, amon
g them:
V is a
set of
node
s
of a g
r
aph
G, comp
ose
d
with terminal n
ode
set VT an
d no
n-termi
nal
node set
VN;
E is a set of edge
s of a gra
ph G;
LV is a set of node
s lab
e
ls
of a graph
G;
LE is a set of edge
s lab
e
ls
of a graph
G;
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Test Metho
d
for Pro
c
e
ss
Deadlo
c
k Base
d on Graph G
r
am
m
a
rs (Yi Wan
g
)
3267
S
：，
：
E
→
VTE
→
V are
two fun
c
tion
s
that gives th
e sta
r
t nod
e
and the
end
node
of
each edg
es o
f
a graph G;
Defini
tion 2
:
A prod
uctio
n
of a graph
grammar is
a rule likes
gl
：
= g
r
. gl an
d g
r
are two
grap
hs, calle
d as the left and the right of
the produ
ctio
n sep
a
rately.
Defini
tion 3:
Ho
st grap
h, expresse
d as
gho
st, is
a graph that will be tran
sform
ed usin
g
prod
uctio
n
s.
In addition
al, a su
bgraph
of a graph t
hat is i
s
omo
r
phic
with gl i
s
exp
r
esse
d
as
glhost, which will be replaced as a graph that is
omorphic with gr when
a graph is
transformed.
Defini
tion 4:
From
gho
st, remove
all the no
de
s an
d the ed
ge
s
of a glho
st a
nd the
edge
s
whi
c
h
end
point
o
n
glh
o
st
will
get a
g
r
ap
h, call
ed
as Re
sid
ual
G
r
aph,
ma
rke
d
a
s
g
r
es
id
ua
l.
Defini
tion 5:
grho
st is a
grap
h, whi
c
h
is isomo
r
p
h
i
c
with g
r
, an
d repla
c
e
s
gl
host of a
host graph.
The p
r
od
ucti
ons i
s
th
e b
a
si
s of the t
r
ansfo
rmatio
n
for a
ho
st g
r
aph,
but in
orde
r to
compl
e
te the
transfo
rmatio
n, only p
r
od
u
c
tion i
s
not e
noug
h, the
co
rre
sp
ondi
ng
rules al
so
sh
o
u
ld
explain ho
w to embed g
r
h
o
st into gre
s
i
dual, the rule
s call
ed emb
eddin
g
rule
s.
Defini
tion 6
:
A gra
ph g
r
a
mmar
gg i
s
a
triple
(A, P, E), amon
g th
em, the A i
s
the initial
grap
h of the grap
h gramm
a
r, the P is the set
of the produ
ction
s
, the E is the embeddi
ng rul
e
s.
Defini
tion 7:
Set gg = ( A , P,
E) is a g
r
aph
gra
mma
r, L ( gg
) = {
G| A => G
∧
t
here i
s
not non-te
rmi
nal in G} is a l
angu
age
set of a graph g
r
ammar.
For
a g
r
ap
h
gramm
a
r, th
e
r
e a
r
e t
w
o
op
eration
s
: o
n
e
is d
e
rivatio
n
, the othe
r i
s
parsing.
The p
r
ior me
ans th
at from
the ho
st gra
ph to find
o
u
t a su
bg
raph
that isom
orp
h
ic
with the l
e
ft
grap
h of the prod
uctio
n
a
nd repl
aced
with a gra
ph that isomo
r
p
h
ic with the right grap
h of the
prod
uctio
n
; the latter m
e
a
n
s that from
a gra
ph to
fin
d
out a
sub
g
raph that i
s
o
m
orp
h
ic
with
the
right g
r
a
ph
of the p
r
o
d
u
c
tion a
nd
repl
a
c
ed
with
a
graph th
at iso
m
orp
h
ic with
the rig
h
t g
r
ap
h of
the p
r
odu
ctio
n. The
graph
s that
de
rived
from t
he
ho
st gra
ph
call
ed
as the
lang
u
age
of the
graph
gramm
a
r. T
h
rough
parsin
g
, if a gra
ph
ca
n arrive to
th
e initial cha
r
a
c
ter, the
grap
h is
calle
d a
s
a
langu
age of the gra
ph g
r
a
mmar.
3. Cons
truc
tion for Proce
ss Re
sourc
e
Diagram Ba
sed on Gra
p
h Grammar
Defini
tion 1
:
A pro
c
e
s
s reso
urce
diag
ram
(PRD)
can be
re
pre
s
ented a
s
P
R
D=(P, R,
Er, Ed), amo
ng them:
P is a set of processe
s;
R is a set of reso
urce
s;
Er is a set of edge
s a
c
cord
ing to a pro
c
e
ss
requ
est
s
for re
so
urce
s;
Ed is a set of edge
s a
c
cord
ing to a resou
r
ce a
s
sign
ed
to a pro
c
ess.
For exampl
e, Figure 1 is a
PRD,
Figure 1. A PRD
Among
th
em,
P= {p1, p2}, R=
{
R
1, R2},
Er= {<
p1, R1
>,
<p1, R2
>, <
p2, R1
>, <p
2,
R2
>},
Ed=
{<
R1, p1>
, <
R
2, p2>}.
< pi, Rj> p
r
e
s
ents a p
r
ocess pi appli
e
s a
resou
r
ce Rj;
< Rj, pi> p
r
e
s
ents a reso
urce Rj h
a
s b
e
e
n
allocated to
a process pi.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 3266 – 32
71
3268
Defini
tion 2:
A rea
s
on
abl
e pro
c
e
s
s re
sou
r
ce dia
g
ra
ms i
s
a PRD
in that the p
r
oce
s
se
s
have not
bee
n dea
dlo
c
ked
in a
state. A
rea
s
o
nabl
e
pro
c
e
s
s re
so
urce di
agram
sho
u
ld
sati
sfy
two co
ndition
s:
The allo
catio
n
for a re
sou
r
ce
s Rj can no
t exceed the total;
The su
m of the numb
e
r of
any process pi applies fo
r a resou
r
ce Rj and the n
u
mbe
r
of
the resou
r
ce Rj allo
cate to the pro
c
e
s
se
s is no m
o
re t
han the total of the resource Rj.
Defini
tion 3:
A complete schemati
c
di
agra
m
is a
PRD that cont
ains o
n
ly an isolate
d
node.
Based
on th
e basi
c
p
r
in
ciple of gra
p
h
gramm
a
rs, throu
gh the rules a
nd u
s
i
ng the
derivation
of
the graph
grammar
it can
co
nstruct th
e process
re
sou
r
ce di
agram. De
sig
n
rule
s
are a
s
Figu
re
2:
Figure 2. A Set of the Rule
to Const
r
u
c
t the Process
Re
sou
r
ce Dia
g
ram
Among them,
P
means a
proce
s
s;
mean
s a ki
nd of re
sou
r
ce, m is the num
be
r
of the resource;
is a non-te
rminal n
ode t
hat of a resou
r
ce.
R
u
le 1 me
ans
th
a
t
it b
e
g
i
n to
dr
aw
a
r
e
so
u
r
c
e
, tha
t
is
to
s
a
y to
dr
aw
a pr
oc
es
s re
s
o
u
r
c
e
diagram;
Rule
2
mea
n
s
startin
g
fro
m
a
non
-term
i
nal n
ode
of
a resource
a
nd b
r
ing
in
a
termin
al
node;
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Test Metho
d
for Pro
c
e
ss
Deadlo
c
k Base
d on Graph G
r
am
m
a
rs (Yi Wan
g
)
3269
Rule 3 m
ean
s that all the
non-te
rmin
al
node
s
of the reso
urce
s cha
nged into th
e terminal
node
s an
d the resou
r
ces h
ad bee
n bro
u
ght end;
Rule 4 b
r
ing i
n
a pro
c
e
ss a
nd the pro
c
e
s
s puts fo
rward an appli
c
ati
on to a re
sou
r
ce;
Rule 5 me
an
s that an existing pro
c
e
ss
put
s forwa
r
d
an appli
c
atio
n to a resource;
Rule 6 di
strib
u
tes a reso
urce to a proce
ss;
Rule
7 me
a
n
s that
an a
pplication tha
t
a
pro
c
e
s
s
puts fo
rward
to a resource b
e
e
n
cha
nge
d to the allocation that a re
sou
r
ce to a pro
c
ess.
Figure 3 is th
e con
s
tru
c
tio
n
pro
c
e
ss of t
he Figu
re 1,
Figure 3. The
Con
s
tru
c
tion
Proce
s
s of the Figure 1
4. Test fo
r Process
Dea
d
lock Ba
sed o
n
Graph Gr
a
mmar
Theorem
:
Th
e system is a
deadlo
ck
sta
t
e, if and
only if its process re
sou
r
ce di
agra
m
can n
o
t cha
n
ge to a compl
e
te schemati
c
diag
ram.
Based o
n
the
theorem, we can ju
dge if it have a deadl
ock in a syste
m
.
Step 1: In th
e pro
c
e
ss
re
sou
r
ce diag
ram to l
ook fo
r if it have a
pro
c
e
ss n
ode
that the
sum of th
e a
pplication ed
ges
and th
e
allocation ed
ges
l
e
ss tha
n
the total of the re
so
urce.
If it is
yes then it turn to step2, el
se it turn to st
ep3;
Step 2: For the pro
c
e
s
s n
ode that sati
sfy t
he condition, we can
modify the application
edge
s to the allocation ed
ges, and thi
s
make
s the process no
de be an isol
ate
d
node; Turn
to
step 1;
Step 3: If it is
a compl
e
te schem
atic dia
g
ra
m, the sy
stem does n
o
t exist the dea
dlock.
Based
on th
e basi
c
p
r
in
ciple of gra
p
h
gramm
a
rs, throu
gh the rules a
nd u
s
i
ng the
parsing
of th
e g
r
ap
h g
r
a
mmar it can
con
s
tru
c
t
th
e
process
of t
he te
st for p
r
oce
s
s d
eadl
o
ck.
De
sign rule
s are a
s
Figu
re
4. Among them:
Rule 1 p
u
ts a
n
appli
c
ation
edge
cha
nge
to an allocation edg
e for a
process no
d
e
;
Rule 2 d
e
lete
s all the allo
cation edg
es o
f
a reso
urce a
llocate to a proce
s
s;
Rule 3 p
u
t two isolate
d
no
des p
a
rse to a isolate
d
no
de;
Rule 4 p
u
t a termin
al node
resou
r
ce parse to a non-te
rminal nod
e re
sou
r
ce;
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 3266 – 32
71
3270
Rule 5 put a terminal no
de
reso
urce an
d a non-te
rmi
nal node resource pa
rse to a non-
terminal n
ode
reso
urce;
Rule 6 p
u
t an
isolated reso
urce and a
n
isolat
e
d
pro
c
e
ss p
a
rse to th
e initial cha
r
a
c
ter.
From the p
r
o
c
e
ss of the te
st for pro
c
e
ss deadl
o
c
k of the Figu
re 1,
we can see that the
Figure 1 ca
n be parse
d to the initial gra
p
h
:
λ
, so the Fi
gure 1 d
o
e
s
n
o
t exist the deadlo
c
k.
Figure 4. A set of the Rule
to Cons
t
r
u
c
t the Test for P
r
ocess Deadl
ock
Figure 5. The
Test for Pro
c
ess De
adlo
ck of the Figure
1
5. Summarize and Look
For
w
a
r
d
This pa
per p
r
opo
se
s a te
st meth
od fo
r p
r
o
c
e
s
s d
e
adlo
c
k ba
se
d
on
graph
g
r
ammars
throug
h
con
s
tructing
process resource
diag
ram.
Th
roug
h u
s
in
g the con
s
tru
c
ti
on rule
s, it can
con
s
tru
c
t an
d
judge the val
i
dity of the proce
s
s re
so
urce dia
g
ram. Throu
gh u
s
ing
the test rule
s,
it
can te
st if the
r
e is the d
e
a
d
lock in th
e p
r
ocess.
Th
e
method i
s
a
g
r
aphi
cal
app
roach; it is si
m
p
le
and intuitive with strong o
pera
b
ility.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Test Metho
d
for Pro
c
e
ss
Deadlo
c
k Base
d on Graph G
r
am
m
a
rs (Yi Wan
g
)
3271
Ackn
o
w
l
e
dg
ements
This pap
er is
sup
porte
d by
Hub
e
i Provin
cial
De
partm
ent of Ed
ucation
Re
sea
r
ch
Proje
c
t
(B201
310
1)
Referen
ces
[1]
Roze
nber
g G. Han
d
b
ook
of
Graph Gramm
a
rs an
d C
o
mp
uting
b
y
Gra
p
h
ransf
o
rmatio
n
. Sin
gap
ore:
w
o
rld sci
entific
Publ
ishi
ng. 19
97; 1 1.
[2]
Ehrig H, Engels G, Kreow
ski H2 J, et al.
Hand
bo
ok of Graph Gra
m
mars
and Co
mputi
n
g by Graph
T
r
ansformatio
n
:
Applicati
ons, l
ang
ua
ges an
d
T
ools
. Sing
ap
o
r
e :W
orld scien
tific Publis
h2i
n
g
,1999; 2.
[3]
Ehrig
H, Kreo
w
s
k
i
H
2
J, Mo
ntanar
i U, et
al
.
Hand
bo
ok of
Graph Gra
mmars an
d C
o
mp
uting
by Gra
p
h
T
r
ansformatio
n
s
: Concurre
nc
y, parall
e
lis
m, and D
i
st ributi
o
n
. Sing
ap
ore:
W
o
rld scientifi
c
Publis
hin
g
.
199
9; 3.
[4]
Dre
w
es F
,
Hoffmann B, J ans
sens D, et al
. Adaptiv
e Star Grammar. ICGT
.
200
6: 77-9
1
.
[5]
Lara
J, Bar
d
o
h
l
R, Ehri
g
H, et a
l
. Attribut
ed
Gra
p
h
T
r
ansformatio
n
w
i
th No
de
T
y
pe
Inher
itanc
e.
T
heoretic
al Co
mp
uter Scie
nc
e.
2007; 3
76(3)
: 13921
63.
[6]
Pfaltz J. W
eb
Grammars an
d
Picture
Descri
p
tion.
Co
mp
uter Grap
hics
an
d Imag
e Proc
e
ssing
. 197
2;
1(1): 193-
22
0.
[7]
Bunke
H. Attri
buted
Pro
g
ra
mmed Gra
ph
Grammars a
n
d
T
heir Ap
plic
ation
to Sc
he
matic Di
agr
am
Interpretation.
IEEE Pattern Analysis
and Ma
chin
e Intelli
ge
n
c
e
. 1982; 4(
6): 574-
582.
[8]
Fahmy
H, Blostein D.
A Graph
2Gra
mmar
Progra
m
mi
ng
Style for Rec
ogn
ition
of Mu
sic Notatio
n
.
Machi
ne Visi
o
n
and Ap
plic
ations, to ap
pear 1
9
9
2
Preli
m
i
nary res
u
lt
. Proc. First
International
Confer
ence
on
Docume
nt Anal
ysis & Rec
o
g
n
itio
n. St. Malo, F
r
ance. 1991:
70-78.
[9]
Dola
do J, T
o
rreal
dea F
.
F
o
rmal Mani
pu
lati
on of F
o
rreste
r
Diagrams b
y
Graph Grammars.
IEEE
System, Man a
nd Cyb
e
rnetics
.
1988; 18(
6): 981-9
96.
Evaluation Warning : The document was created with Spire.PDF for Python.