D:\User\sbornik_38_pdf\36.DVI


Mathematical Problems of Computer Science 38, 84{86, 2012.

M odeling FI FO Queues by Dynamic P etr i N ets

Go h a r R . P e t r o s ya n

Armenian State Pedagogical University after Kh. Abovyan
E-mail: blueayez777@mail.ru

P e t r i N e t s ( P N ) a r e a g r a p h ic a l t o o l fo r fo r m a l d e s c r ip t io n o f t h e ° o w o f a c t ivit ie s in
c o m p le x s ys t e m s . Co m p a r e d t o o t h e r m o r e p o p u la r t e c h n iqu e s o f g r a p h ic a l s ys t e m r e p r e -
s e n t a t io n ( fo r in s t a n c e , b lo c k d ia g r a m s o r lo g ic a l t r e e s ) , P N a r e p a r t ic u la r ly m a t c h e d fo r
r e p r e s e n t a t io n o f lo g ic a l in t e r a c t io n s a m o n g p a r t s o r a c t ivit ie s in a s ys t e m in a n a t u r a l wa y.
Typ ic a l s it u a t io n s t h a t c a n b e m o d e le d b y P N a r e : s yn c h r o n iz a t io n , s e qu e n t ia lit y, c o n c u r -
r e n c y a n d c o n ° ic t [1 ], [2 ], [3 ], [5 ].

In c o m p u t e r s c ie n c e , a qu e u e is a p a r t ic u la r kin d o f a b s t r a c t d a t a t yp e o r c o lle c t io n in
wh ic h t h e e n t it ie s in t h e c o lle c t io n a r e ke p t in a n o r d e r a n d t h e p r in c ip a l o p e r a t io n s ( o r t h e
o n ly o n e ) in t h e c o lle c t io n a r e ( is ) t h e a d d it io n o f e n t it ie s t o t h e r e a r t e r m in a l p o s it io n a n d
r e m o va l o f e n t it ie s fr o m t h e fr o n t t e r m in a l p o s it io n . Th is m a ke s t h e qu e u e a Fir s t -In -Fir s t -
Ou t ( FIFO) d a t a s t r u c t u r e . In a FIFO d a t a s t r u c t u r e , t h e ¯ r s t e le m e n t a d d e d t o t h e qu e u e
will b e t h e ¯ r s t o n e t o b e r e m o ve d . Th is is e qu iva le n t t o t h e r e qu ir e m e n t t h a t o n c e a n
e le m e n t is a d d e d , a ll e le m e n t s t h a t we r e a d d e d b e fo r e h a ve t o b e r e m o ve d b e fo r e a d d it io n o f
t h e n e w e le m e n t . A qu e u e is a n e xa m p le o f a lin e a r d a t a s t r u c t u r e [5 ].

De¯nition. A P e t r i N e t is M = ( C; ¹) , wh e r e C = ( P; T; I; O ) is t h e n e t wo r k s t r u c t u r e ,
a n d ¹ is t h e n e t wo r k c o n d it io n . Th e P -p o s it io n s , T -t r a n s it io n s a r e ¯ n it e s e t s ; I : T ! P 1;
O : T ! P 1 a r e t h e in p u t a n d o u t p u t fu n c t io n s , r e s p e c t ive ly, wh e r e P 1 a r e a ll p o s s ib le
c o lle c t io n s ( r e p e t it ive e le m e n t s ) o f P ; ¹ : P ! N0 is t h e fu n c t io n o f c o n d it io n s , wh e r e
N0 = f0 ; 1 ; : : :g is t h e s e t o f in t e g e r s . W e d e t e r m in e ( in a kn o wn m a n n e r ) t h e a llo we d
t r a n s it io n s o f P e t r i N e t s a n d t h e t r a n s it io n s fr o m o n e s t a t e t o a n o t h e r , a s we ll t h e s e t o f
r e a c h a b le s t a t e s .

Th e s t a t e o f t h e n e t wo r k is r e p r e s e n t e d b y t h e fo llo win g ve c t o r :

( ¹( P1 ) ; ¹( P2 ) ; :::; ¹( Pm ) ) ; if P = fP1; P2; :::; Pmg;
¹ is a fu n c t io n , wh ic h c a r r ie s o u t t h e fo llo win g m a p p in g , ¹ : P ! N0, wh e r e N0 is u s e d t o
e n c o d e t h e n u m b e r o f t o ke n s in t h e p o s it io n s . B e fo r e s t a r t in g it s wo r k t h e n e t m u s t h a ve
a n in it ia l s t a t e , ( ¹0 ( P1 ) ; ¹0 ( P2 ) ; :::; ¹0 ( Pm ) ) , wh e r e t h e n u m b e r o f t o ke n s in t h e ir r e s p e c t ive
p o s it io n s a r e s h o wn [1 , 4 ].

Th e c o m p le xit y o f t h e s t a n d a r d P e t r i N e t m o d e lin g o f t h e t h e FIFO qu e u e is 4 m + 6 ( m¡
1 ) + 2 + 2 = 1 0 m ¡ 2 ( t h e n u m b e r o f p la c e s , t r a n s it io n s , a r c s , fo r a n e t wo r k wit h m e le m e n t s
a r e c a lc u la t e d ) .

Th e d i®e r e n c e b e t we e n d yn a m ic P e t r i N e t s fr o m t h e s t a n d a r d P e t r i N e t s is t h a t t h e
s t r u c t u r e o f t h e ¯ r s t c h a n g e s d u r in g it s wo r k, t h a t is , p o s it io n s o r t r a n s it io n s c a n b e a d d e d
o r r e m o ve d fr o m t h e n e t , b e s id e s , a n d , c o n s e qu e n t ly, t h e in p u t a n d o u t p u t fu n c t io n s a r e
c h a n g e d [4 ].

8 4



G. Petrosyan 8 5

B e lo w is t h e m a t h e m a t ic a l d e ¯ n it io n o f d yn a m ic P e t r i N e t s , wh e r e we h a ve in t r o d u c e d
t h e id e a o f d yn a m ic m e m o r y. Th is id e a h e lp s u s t o u s e t h e fr e e d m e m o r y s p a c e .

Fir s t , we d e n o t e t h e s e qu e n c e o f a ll p la c e s a s fo llo ws : ­ = ( P0; P1; P2; :::; Pk; :::; P2k ) , a n d
t h e s e qu e n c e o f a ll t r a n s it io n s b y t h e fo llo win g
à = ft0; t1; :::; tk; :::; t2k g.

L e t 's d e ¯ n e t h e fo llo win g , C = ( P; T; I; O ) , a s t h e c u r r e n t s t r u c t u r e o f t h e n e t wo r k,
wh e r e P µ ­ is t h e ¯ n it e s e t o f p o s it io n s a t t h e g ive n m o m e n t , a n d T µ Ã is t h e ¯ n it e s e t o f
t r a n s it io n s a t t h e g ive n m o m e n t , a n d I : T ! P 1 a n d O : T ! P 1, a r e t h e c u r r e n t in p u t
a n d o u t p u t fu n c t io n s , r e s p e c t ive ly. P 1 h a s t h e s a m e m e a n in g a s in t h e p r e vio u s c a s e s .

D e n o t e ¹ : ­ ! N¡10 , a s t h e fu n c t io n o f c o n d it io n , wh e r e N¡10 is t h e s e t o f in t e g e r s ( t h e
n u m b e r s o f t o ke n s in t h e p o s it io n s ) , in c lu d in g ( -1 ) , t h a t e n c o d e s t h e u n u s e d p o s it io n s .

L e t P = fPi1; Pi2; :::; Pirg is g ive n , ( ¹( Pi1 ) ; ¹( Pi2 ) ; :::; ¹( Pir ) ) b e t h e ve c t o r o f t h e c u r r e n t
s t a t e a t t h e g ive n m o m e n t .

Mo r e o ve r , if P = fPi1; Pi2; :::; Pirg is t h e n u m b e r o f p o s it io n s in t h e n e t wo r k, t h e n t h e
fu n c t io n ¹ p e r fo r m s t h e fo llo win g m a p p in g :

¹ : P ! No; ¹ : ( ­=P ) ! f¡ 1 g:

To o b s e r ve t h e p r o c e s s e s in t h e n e t wo r k, yo u ¯ r s t n e e d t o kn o w t h e la ws o f t h e s t r u c t u r a l
c h a n g e s .

S u p p o s e we h a ve a n M = ( C; ¹ ) d yn a m ic P e t r i N e t , wh ic h c u r r e n t ly h a s C = ( P; T; I; O )
a n d is in t h e ¹ c u r r e n t c o n d it io n .

L e t 's s a y t h a t t 2 T t r a n s it io n is a llo we d , if 8P 2 I ( t ) , ¹ ( P ) ¸ ]( P; I ( t ) ) , wh e r e ]( x; A )
h a s t h e s a m e m e a n in g a s in t h e s t a n d a r d P e t r i n e t wo r ks [1 , 4 ].

L e t M = ( C; ¹ ) b e a d yn a m ic n e t wo r k a n d t h e t r a n s it io n t 2 T is a llo we d t o r u n .
In t h is c a s e , a s we h a ve n o t e d , n o t o n ly t h e s t a t e o f t h e n e t wo r k will c h a n g e , b u t a ls o

t h e s t r u c t u r e . In c o n t r a s t t o t h e p r e vio u s d e ¯ n it io n , we d e ¯ n e t h e fu n c t io n ± [1 , 4 ], wh ic h
d e p e n d s o n t h e t h r e e a r g u m e n t s ( C; ¹; t ) , a n d r e t u r n s b a c k t h e n e w s t r u c t u r e a n d s t a t e o f
t h e n e t wo r k a ft e r t h e t r a n s it io n t a s a n e w va lu e . In fa c t we c o n c lu d e t h a t , in o p t im iz a t io n
s e n s e , t h e P e t r i D yn a m ic N e t s a r e m o r e c o n ve n ie n t fo r m o d e lin g o f s ys t e m s o f s o m e t yp e
t h a n t h e s t a n d a r d P e t r i N e t s .

In fa c t , ± ( C; ¹; t ) = ( C0; ¹0 ) , wh e r e C = ( P 0; T 0; I0; O0 ) is a n e w s t r u c t u r e .
P 0 is t h e s e qu e n c e o f t h e n e w p o s it io n s ,
T 0 is t h e s e qu e n c e o f t h e n e w t r a n s it io n s ,
I0 : T 0 ! ( P 0 ) 1 is t h e n e w in p u t fu n c t io n ,
O0 : T 0 ! ( P 0 ) 1 is t h e n e w o u t p u t fu n c t io n .
¹0 = ( ¹0 ( P0 ) ; ¹

0 ( P1 ) ; :::; ¹
0 ( Pk ) ; :::; ¹

0 ( P2k ) ) a n d ¹
0 : ( ­=P 0 ) ! f¡ 1 g.

Th e in it ia l s t r u c t u r e o f t h e n e t wo r k is d e n o t e d a s C0, a n d t h e in it ia l c o n d it io n is ¹0. Th e
n e t wo r k g e n e r a t e s ( C; ¹) p a ir s o f s e t s , a n d t h is s e t is d e n o t e d b y R ( C0; ¹0 ) , wh e r e
1 . ( C0; ¹0 ) 2 R ( C0; ¹0 ) is in it ia l s t a t e ,
2 . if ( C0; ¹0 ) 2 R ( C0; ¹0 ) a n d 9 t 2 T 0, s u c h t h a t ± ( C0; ¹0; t ) = ( C0; ¹0 ) 2 R ( C0; ¹0 ) ,
3 . Th e o t h e r ( C; ¹ ) p a ir s in R ( C0; ¹0 ) d o n o t b e lo n g t o R( C0; ¹0 ) a n d t h e la t t e r c a n b e
in ¯ n it e .



8 6 Modeling FIFO Queues by Dynamic Petri Nets

R e fe r e n c e s

[1 ] J. L . P e t e r s o n ., P etri net theory and the modeling of systems. P r e n t ic e H a ll, E n g le wo o d
Cli®s , 1 9 8 1 .

[2 ] T. Mu r a t a , " P e t r i N e t s : P r o p e r t ie s , A n a lys is a n d A p p lic a t io n s " , P roceedings of the IE E E ,
vo l. 7 7 , n o . 4 , 1 9 8 9 .

[3 ] W . R e is in g , G. R o z e n b e r g ( e d s ) . L e c t u r e N o t e s o n P e t r i N e t s . P a r t s I a n d II / / L e c t u r e
N o t e s in Co m p u t e r S c ie n c e s . V . 1 4 9 1 - 1 4 9 2 . S p r in g e r - V e r la g , 1 9 9 8 .

[4 ] Â. Å. Êîòîâ, Ñåòè Ïåòðè. Ì.: Íàóêà, 1984.

[5 ] Ä. Êíóò, Èñêóññòâî ïðîãðàììèðîâàíèÿ, Ò1-Ò3, 2008.