Modernization Hub

Modernization and Improvement
Mod-01 Lec-39 PetriNets-I

Mod-01 Lec-39 PetriNets-I

This topic is on PetriNets, we have look at
different techniques for mathematical modeling of systems right, we have seen in the basic
queuing networks ora queuing system, the mm 1 queues is an marks out chains, you have
looked at close queuing net works MBA and the related techniques. So, petri nets is
a other form of mathematical modeling to formally specified a particular system right, normally
specification we can also derived some performance results also from this petri nets modeling.
So, it is very similar to mark out chains in terms of applications right; we can essentially
model the behavior of a system, and then try to derive some properties from that particular
model. So, the name petri nets arises, because this
was invented by I guess Carl Adam Petri, I guess we can see invented, because he came
up with this and if you look at Wikipedia forthis page on petri, he written that one
page on himself in says actually discover, he came of this in19, when he was about 13
years old the 1930s, but then he formally here it as a presentation in 1962 as part
of as Ph.D theses. So, we did not know about how true it is,
whether he came up with this 13th year are not, we will simply use right and 1962 as
the age 1, as the time and this was actually formally announce to the world right, this
is the part of this Ph.D theses. The Ph.D theses itself was publish in 1966, but the
ideas were originally conceived in1962. So, this as be said right use to model the behavior
ofa system right; model the functionalityslash behavior of a system. And what the system
is we will see examples of the systems as we go will on. And if you in terms of applications
right, there are lot of domains where this can be applied oneof course we know, we know
computer systems where we can actually model this computer communication, networks we can
model right. So, we can look at computer systems, the word
thus the type that we saw before, that we model with MBA and so on, are computer communication
network right, so computer networks protocols and related fields, but in addition it is
got lot of other applications in like, manufacturing for it is all right, if you look at some other
examplesyou will very clearly see that you know, just like any computer processing system
can also be map to manufacturing system, where there are parts, there are components and
you are do some processing on those components and then write combine those parts in two
different system. So, manufacturing systems, production systems
were they actually manufacture part in terms in to product system in and also sophisticated
scheduling systemsright, this is scheduling not from merely our computer systems, networks
from a scheduling, but also scheduling in terms of jobs in shops right; the machines
available and jobs to the processed on the machines and we need some sort of scheduling
systems, there also controllers right, so we can look at controllers as inyour PLC controllers,
that we see rightembeddedcontrollers, let we see on various devices, other program logic
control is right. So, this can also be model behavior of those can be model with the help
of petri nets, that is them basic, some of the applications that you can see withthatthat,
can be del with using petri nets, so that is the first part of who came up with it and
what it can be potentially used for. So, now, let us look at what is formal definition
right, so petri net we want to use PN to represent the Petri Net right, so petri net is a formal
languageit is formal languageto represents the system; it is also a graphical language.
So, by looking at the system graph, just like state machine like right, state machine is
also a graphical means of representing system behavior, this is also a graphical language;
and this is especially for modeling systems with concurrency this is what does key right,
howdo you deal with concurrent systems model. And if you go back to the 1960s computer science
in concurrency at the time probably just, people just talking about right, you do not
use concurrency as we use today multi thread system are we common or parallel system is
become quite common, and so this is systems were there are concurrent operations going
on; concurrent processing there are going on that communicate with each other and you
want understand if, because of these concurrent processing right for example, we will see
example in terms of right, the basic threading and things like that, so but it is, that is
the basic idea right, where are the concurrency you can try to use this petri net system to
model system behavior and from that derives some sort of performance metrics.
So, formallysoso petri net, if you were to talk about in the graphical, or in a graph
theory term this is bi-partite graph, so it is a bi-partite graphcontaining two types
of nodes and then you have graphs connecting those two types of nodes. So, two types of
nodes aresothe nodes types are vertex types call PLACES.So, place is one type, places
whatever is place where you store something, store token for example, think of it is a
box or buffer something that wholes, so that is called a place; and is this can also be
used tothink and terms of system state right, so this represents some sort of condition
that has to be satisfied right in the communication, in the process that we are trying to model.
So, place is term that going to used and the next term is transition, so transition is
the other node type, in this bi-partite graph and transition essentially represent some
event that occurs are some processing activity that takes place. So, there are items held
in places and all those items when some conditions are satisfied at transition will trigger,
it transition will occur and that transition is name implies will changes state from, change
a system from one state to some other state, so that is transition. As the transition like
is it, corresponds to some sort of activity, so for example, if you look at say use use
the program is waiting for data right, waiting for some input from the keyboard.
So, as in is the keyboard input arrives it gets stored in a keyboard buffer right or
in the system cornel buffer corresponding to the keyboard, and then you have some logic
that works on that character that are character rate from the keyboard. So, that processing
is the activity that is the transition that takes your input keyboard values and then
converts that to some other value right. So, for example, user types in excess input,
the processing is a output esquire, so the logic is represented by the transition and
then intern produces output is esquire, so that goes to some other place, so that is
these are the main components, place and transition. And we usecircle to denote PLACES and the
transition there are different ways, we normally simply draw straight line to represent transition
are sometimes it will rectangle right, thin rectangle like that represent transition and
there are differences wereare sometimes just people use evenboxes to represent transition.We
are going to use this straight line to represent transition, the places are simply circlesand
inside this place inside this box as you can find tokens right, that is the other component
of the system. So, that are places and transitions and there
are tokens that circulate between this places in the system by are this transitions, what
transitions like gates and it goes from place to place through this different gates and
the gate can be open only when certain conditions are met, that is the basic idea otherwise
the gate is kept closed right, so in the gate opens the horse jump from one part of the
field the other part of the field right, so that is the basic idea. So, now these are
the three node types in our bi-partite graph, so what will be need in the bi-partite graph
the edges right, the arcs the connect these to node types. So, we have now, so the places and transitions
are connected by directed edges are we also called them arcs right, so directed
bi-partite graph. So, now let us, so they arccan exist only between a place in a transition
viceversa, but you cannot have an arc between two place that is why it is a bi-partite graph
right otherwise it is so. So, the Arc exists only between a place and transition (No audio
from 10:07 to 10:17) or vice-versa. So, that these are the,that is it this basically defines
also is notion of and then we have of course tokens right,so tokens circulate in the system
between places (No audio from 10:39 to 10:51), so these are the basic entities that are available
in the system. So, nextlet us look at the simple example right, thatfigure as to show
what is going on. So, here is a place, here is in other place
there is, this place is one token, this place has two tokens, here is a transitions and
we have state in there,there is in arc connecting this place to this transition and this place
to this transition; and then from this transition you can have output transition that go to
other places, so this is your basic model of the system components. So, these are on
the left are input places with respect to this particular transition,right this input
place could be output place for some other transition, for this given transition this
is the input place, and thenthese are your output placesand this is the token in the
system. So, tokens get created in these places and
they get moved on the system, next we go will on, now when does thetransition takes take
place right, so this simplest rule for the transition to take places that as long as
there is, if there is a multiple input places for a given transition, if there is one token
at present in, at least one token present in all the input places that are connecting
to a transition, then the transition will fired. And as the result of the transition
what will happen is, one token will be moved from will be removed from here, one token
will be removed from here, and then you will be placing one token here and one token there.
And the number of inputs, number of outputs need not be equal, I can have less number
of input places and more number of output places viceversa, all we are saying is when
a transition occurs I delete tokens from all the input places and add one, one token to
all the output places that is the very basic definition of what happens, we can make this
more complex later on by doing multiple tokens in things like that, but simply speaking that
iswhy transition occurs, whenever there is an input in this basically all this conditions
have to be true that is what did say right, when all this conditions are true the transitions
fired as, as the result of the transitions some values get deposited in need these corresponding
output places. So, implicitly there is copying and things that going on, but as well as system
goestoken is going to be created is each of those output places is that clear, questions
no, so will write it down now. So, transition triggers in the basic definition,
we said triggered or fired right, whenever there is
at least one tokenin all the input places, in all its input places that is point, and
once fired one token is removed from all the input places and one token is added in or added to all
output places, I would say all its input places is added toall of its output places that is
the fundamental think of atransition. Now, the lots of hidden details rightwhen is transition,
how long it is transition take to fired is it instantaneous right, when a transition
fired immediately does a packet get delivered, all is there delay right processing delay,
if you look at a transition is event or in activity naturally it cannot be instantaneous
right sometimes it can be, sometimes it need not be.
So, all those other extension will come later on, but that is the basic notion of ordered
transition is for this system is cancel. So, will set of go through some example, so in
other word all the input, in other says in input arcs represent conditions right that
are to be satisfied for this event are transition to be activated,that what is this basic definition. So, if you can interrupt the input places
as pre-conditions, if you remember when you write this in c program, in programs in general
right, we talk about pre-conditions. So, pre-conditions when they are satisfied right only then this
function can be executed right, so they represent the preconditions and the output places represent
the post-conditions this is in terms of our programming terminology right. So, post-conditions
could be right number of items in the buffer is x plus 1, before it was x, after that it
was x plus 1 those of the pre post-conditions, so for example, if I what to say right this
issimple system right, so this is the input place,that is the output place. So, this is
before firing, let see this is t 1right, this is p 1 and this is p 2, so before firing of
t 1 this is about the system state was, then after firing system state will find this empty
and this will have 1 buffer1, so p 2 will have token, p 1 will have a no token; incase
p 1 have more tokens two tokens in that case p 1 will still have one more token left, but
p 2 will have this one extra token add it right, so that is the basic right.
So, by default one token is removed and one token is added to the corresponding from to
thus in input and output places, so that is the, so formally if I want to represent this
right, so this is a graph, so they any questions on this basic representation so for right,
so in activation happen one token is remove from all the input, one token is added to
all the output places. So,begin to state this formally right, a petri
net called PN is defined by four triple, there is P, there is T, there is I, there is O,
these are the components of the petri net. So, what is P, P is the set of places and
that is represented by P 1, P 2 up to P Mright, so M is thecardinality of places, so that
M places in the system, T is the set of transitions and there are N transition in the system,
so we will call them T 1 to T N. So, what is this INO, any ideawhat I could
be All the All the input places right, so what would
be the, what would I B I am sorry, it will be the set of input places
know for every transition right, I could have one or more of the input places connected
right and I have in such transitions, so there are M places and N transition. So, what could
be this I B matrix right, matrix ofwhatever M by N or N by M, so this I is a matrix that
basically tells you, which are the different places, input places that are associated with
the corresponding transition; and entries will be 1 or 0 in the basic case, we can have
more sophisticatedcases later on, based on multiplicity of the arcs and things like that,
but basically this is just you have connectivity matrix right, this is a set of gages in the
system, because is by it is a directed graph I need to provide one this way and one for
the other way, so these are all in the inputs right.
So, for example, I am it say that P 1 and P 2 are inputs to transition 1 and may be
P 2 and P 4 and may be P M are inputs transition 2 and so on right. So, some sort ofstructure
is the, this is the input, this you definition you have to come up this you given a problem,
given a system you model the system and then part of the end of the modeling will come
up this particular matrix. And likewise, you have the O matrix also which
will specify for each transition, what are the corresponding, so same thing the rows
of the same and the columns of the same, so it is possible that of the end of transition
right, you will have and if you look at it there is technically no loop at right, this
are loop less, you do not want to go from input place, the input and output places are
it can have loops they will allowed, but now for let us assumed that there are this is
a loop less system right, where they output places are different from the input places,
so like this could be anything right,this could be just 1 0 0 0 and things like that,
so these are a specification for the network itself.
So, this is now a static definition of the system, of this network with only this definition
what can I do, you can do anything, we need to have something this is, we need something
dynamic in the system right, what is the dynamic part where is the dynamic it is come in, when
you bring its tokens. So, now this system state is captured by the number of tokens
that are present in all those different M places right.
So, there are right M places, like if you look at this CPU disk problem there is 1CPU
queue and there are 4 disksdisks queues right. So, the systems state is captured by the number
of jobs in each of those 4 queues, each of each of those queues right, each of 5 queues
in total that is the system state right. So, therefore, this static definition of a system
is this, but you lot also bring in the dynamic definition, so will have to have one more
tupelo to this, so that is what is called us the marking. So, will define a marking, marking of a petri
net at time t, we will associate know, because this is technically moving through time right,
so at timetthe marking of a system is simply given by the number of tokens present in each
of those various places. So, where m i f, m i f t is the number of tokens
in place i at time t, this is the definition of marking of the system, so this it present
the current active state of the system rightdynamic state of the dynamic state of the system itself
right and then we used this show, when we start just like in the case of state transitionmark
out chain rightor state transition diagram you always what is an initial state this right.
Let us start somewhere, there is big chain, big graph there different states of connected
to different ways you always say this is the initial state right, so in addition to set
ofthe state transition matrix you also specify the starting state, so likewise you all to
have to, also have to provide the initial marking of the system right.
So, sometimes t 0 which is the initial time right m of t 0 represents the
initial marking, there is the little bit of confusion here, because is m is appearing
both as the number of places as well as the marking of the system right. So, just bar
with that we know one marking with that m, when I use the term m in terms for the number
of places we need talking about the other m, so this is basically, so now we are the
petri net definition will now actually include you are set of places, set of transitions,
inputs matrix, output matrix as well as m of t 0. So, now, if I give this to you saying
this is where this is my starting state of the system, so now we will start with may
be one token in one of those places are nine tokens in the case of CPU disk example right,
add put nine tokens somewhere, if you remember MBA, we did the same think right, how do you
find out the number ofjobs in each of those queues, we start wise simply saying that all
jobs end are equally divided amount all those m queues, so it is n by m is starting state
they need tried triedtried and find out the steady state in terms of number of distributed,
like ways will start with putting all the nine jobs in the CPU queue and then see how
the system progresses with time and finally will come to a steady state system, say that
could be m of t 0right, so that is your initial marking of the system.
So, from this initial marking then what will happen is, we can fired transition that are
various transition that there are possible, because these are all transition in parallel
right, the different combination of transition it can take place and then the state of the
system the marking of the petri net keeps changing with time and that is something that
we will now try to study and go all that is main think right. So, given the petri net
given the initial marking, what is the sequenceof markings that the system will go threw, will
the system lead to dead luck right are if does not lead to dead luck what is the probability
ofthe system being in the given mark states, at given point in time, all those thinks will
what you want you want to find out, and those will translate to our performance petri net.
So, let us look at few more examples, and some sort of you knowclassifications of the
petri net components, so questions no. So, let us look at one petri net right, which
is basically a system which is you know assume that is the machine right that can be loaded
and that will do some processing and then after that it will do some one loading, we
can think of this is a machine are as a computer computer science terms, this is just as CPU
that is processing something. So, the here is data is available it gets process gets
in some post processed bufferwere it can be take in for printing are something like that,
so and thenremove this is also loop in this particular system. So, we havethree states
sorry three places P 1, P 2, P 3 and then there are two transitions sorry, I missing
the transitions. Let us, vacant we need three transitions right,
because from I cannot go from transition to transition right; we will go back draw this
again, there is P 1, T 1 that is one, we go to P 2that is a next storage place and then
that goes to the next transition just T 2, then it goes to P 3, then it goes to transition
T 3 which then finally loops back to, so this is the static definition of the system, these
are all that notes and corresponding arcs that is defined. So, now an a bring let us
an initialstate is 1, 0, 0, so the initial state M of t 0 is equal to 1, 0, 0, so what
that is the initial state. Now, the input matrix willsorry, I matrix
will be what,what will be I matrix look like, remember the I matrix rows are all transitions
right, so T 1 what are the input places only P 1right, so only P 1 others are 0, 0, T 2,
0 1 0, 0 0 1right, this is are standard graph representation right, because when I have
impost input was the system I should specified that right. So, think about did in the programming
right, if I have to give you this model this will way of inputs to you this is representation
of the petri net system right, I will tell you the set of places and transition and likewise
O is what,what is the output 0 1 0, 0 0 1, 1 0 0that is all, right this now completely
specifies may input of the petri net as such. So, P is the set of, so if you on to be more
complete P is the set of states P 1,P 2,P 3 that is input, then T is T 1, T 2, T 3 this
is also given to us. So, now, the representation as well as the initial value, we have to look
for some properties of that petri net, because we ultimately our goal is to get some set
of performance results from this system right, I think a did something and suppose to alright,is
that clear, questions. Now, there are different you know types of
I guess sub components of the system right, so we just talk about some of those things
in sequence. So, for example, you could have a sequential
action, this is an very straight forward where there is you know place that feeds a transition
which inferred feeds like, this has a sequential action right data comes in which processed
here, get processed here and finally, gets in store there and its possible let you can
have a system with a transition with no input, that is somethingwe are not yet talked about,
but I can have a system like this, I can even have a system like that where the first transition
has no input at all, which means it willit will keep on triggering right.
So, it is just like a while loop at just keeps triggering only think is a add some delay
to this, if each transitions take some time say 5 millisecondsare exponential time with
some meant 10 milliseconds, then this will that is the processing time for the particular
system right and then it gets inputs. So, whenever it generates something it puts the
token here, and then whenever there is thetoken it will be simply picked up by this transition
as long as that is one token this transition will fired, and after it process is it there
is nothing for it output in the system, this is also very simple sequential action.
And you know what this kind ofpercent, if I tell you that the times spent each of those
transitions right is exponential with parameter lambda and parameter mew what could this be,
what could this be, what could this system be, any ideas. M M 1 queue right, because this is exponential
time, this is your packet arrival process right. So, everyone exponential right, every
one over lambda with me, one over lambdayou generate the packet, when a packet comes it
goes here when whenever this queue is not empty this is a server, this a arrival process,
this is a server process right and whenever picks packet for processing, customer for
processing it spends one over mew to are mean one over mew time on that process and then
that is it, there is no output you do not really care about it right this is your basic
M M 1 queue, if you look at itwhere there is no input and where there is no output,
so this is actually representing an M M 1 queue system.
Now, the question is what do we do with this, how can with, how do you use this for performance
evaluation I will come to that later; we will look at, so initial marking of the system
could still simply 0right, initial marking 0 no customers in this system, so we have
to defined what will state ofthe system is in, how see go through different marking of
the system. So, what areall the possible marking for this
system, though marking for the system is the number of tokens right in this only, in this
place it could be 0, 1, 2, 3 up to infinity right; that marking represents the state of
the system right. So, those are all the number of items stored in this place is simply in
the number of customers in the queue rightor number of customers waiting in queue, because
this transition implies that is there is it is always processing someone right, this transition
will be fired whenever it finishes a particular, so this will be not fired this queue is empty
as long as queue isnon empty it will simply pick up their next process.
And now, that is it clear why this is an M M 1 queue and implicitly of not really defined
one more think, if there are say three tokens in this queue right, which of the token get
to selected for processing, that is again schedule in discipline, so implicitly we are
assuming it is FCFS, but we can also bring in other scheduling discipline. So, we are
saying that by this definition as long as there is 1 packet in this queue, I will start
processing itand then if there ismore than 1 packet then this this representation does
not tell as anything at all this simply says one of them will be selected, but the idea
is that it is a FCFS are could be some other queue 2, that is something will have to bring
when we do the analysis part of the system. So, that is so called assequential action
where you know one action face finishes it goes to the pipe line right simply keeps processing
these are all the processing steps in the pipe. So, you can see, you can know use this
representation for modeling a pipe line for finding a threw put of a pipe line, finding
are where the bottle neck in this pipe line is all those things you can actually tried
the find out. So, then we have dependency, so dependent
transition is what we are seeing before, when there are more than one input places, so this
iswhen all these places have tokenat least one token then you will generate, then this
transition will trigger and then you will go and process that. So, this let say that
this means at some data, let say now done a parallelhave done some parallel processing,
that is some processing here which I am not showing and let say that I am searching for
something right. So, I given the search item to some different databases and they allowed
to come all have to come back to me with the respective results in the corresponding databases,
then this will represents the join operation right.
If you will look at process for cannot join, this is like a join operation were as long
as all these places have the corresponding data values I can take them and start processing,right
that was this represents. So, if you look if you look at the multi threaded operation
that is what this, these are all different threats they have completed and place some
data item here, for further processing and this will not proceed until all these are
having at least one token then it will proceed for that right.
Now, there is there isimplicitly semanticsright, some of the semantics are not clearly stated
from the diagram itself these are all the implicit semantics is only differences compared
to see UML or may be it is not a fair compares and at least in this case this semantics are
well defined, once the semantic is well define then you can implement system it will understand
inbred in processgiven petri net and then give your results right.
Only one the semantics are not clearly defined your problem right, when we for example, right
draw around diagrams, we will have different implement are a inter production for a same
diagram, but here the inter prediction are fixed this is the semantic for this particular
syntax it were trying here, so queues the dependency class or dependency form of transition,
questions. Now, sometimes we end of with conflict situations,
which is also not uncommon in programming system it be well, so what could be a conflict,
so here is a transition that is expecting input from two different placesand if that
right this is one transition; now if I havean other transition which is also doing this
same thing, except at there is the extra line two transition, but one common place between
those two transition. Now, if there is only data here and here let us called is P 1, P
2 and P 3 right, so if P 1 and P 2 this is T 1 and T 2right, so if P 1 and P 2 have tokens,
but not P 3, if P 3 does not have a token then what will happen, T 1 is fired right,
because T 1 conditions are mightlikewise if P 2 and P 3 have tokens, but not P 1 then
what happens T 2 is fired. So, that isclear, this system no how do resolves
this what happens of all three have tokens, at given incidence of time all three have
tokens, then what should happen that is the conflict right, so now both thisevens aretransitions
can be fired, so now there is to be an additional policy, some other specification that either
says T 1 has higher priority than T 2 are some probability has to be defined saying
T 1 probability is 0.05 or 0.09 T 2 probability is 0.01, so there is a probabilistic way of
transition aretriggering a transition then there are multiple simultaneous transition
in conflict right, you cannot multiple transitions at different places of the network then there
is no conflict, when they are conflicting then you have to have a conflict resolution
alsoright. So, that is that is again these this you will find right, you will find in
this cases when such as in occursthen there is to be some other mechanism that specifies
out to resolves this particular conflict, is it clear, any questions on conflict? Thennow, we come to set ofright concurrency,
because we say that concurrency is one of the key things is how do you model concurrency
in a particular system, so let us say that have to do this parallel processing and given
a value x, I have to comparewhether n or two numbers in n and x is the input to the systemand
I have to compare and say whether N to the power x is greater or x to the power n is
greater; I can do this sequential, I can do that in parallel right, so that was this will
right to this represents. So, here now, the data is the token will contained two values
tupeloright, so as long as there is one token available for processingthis transition will
trigger. And like we said before if I have something
like this token will be placed in both these places right, ifthis transition triggers a
copy of the data will technically go to both the places that is the semantics at a greater
point. So, when any all other places will get one, one token each and what the content
of the token is simply, the token it is presents some token how were that is defined right,
so something that will how to defined. And so here it is, this is getting process to
this is also processing right this high compute the enough x this computing x of N and then
they place the results here in this corresponding places, now here is again what we saw before
right, so this is like a set this is like a join operation when both these values are
ready this transition will trigger and then you finally, put that in a output their; so
this is how what we call as concurrency right this model concurrency in the system this
is this is very much all your concurrencyright operations can be model as follows, questions
on that. Now, when we talk about concurrencywhat is also important some other activity show
also come in to play right what is that and two systems, two processes are sharing something
we have to model sharing of variables right. How do you share, how do you model resource
shine, our classic producer consumer problem right, so producer is producing data, so normally
what will you say producer produces data gets into a buffer right. And then it gets arrow, now right some processing
is done to that area could be something else toward the process that want to update this
same variable something of that nature right. So, how do you do that, so I have two such
processes that are doing some kind of processingall the transition right here, now there is a
share token, share variable only thing is a need to enforce mutual exclusion, I cannot
have the same variable used by these two at the same plan, so to do that we can represented
this way, this is graph make any sense, so this is where the right, so what happen is
right for this transition to trigger right, what are the conditions it needs in input
from this place and in input from this place. And then the result of the computation is
toyed here, and after it gets toyed, then it gets I then then once there is in item
here right, then it will trigger this long as one item herewill trigger this transition,
now what will happen is the copy will go to further processing for this particular process,
but the original data is essentially return back to the sharedbuffer right, this represents
the shared spaceas long as this is item here only canI this one be triggerthere is only
one item here, so this is the case when this condition is satisfied, now what is happening
is actually conflict here right. We have a conflict here, because if this is the case
which of these to going to get trigger, anyone of them in unitsare whatever systems, wehandled
at the help of new text, they both ask for the lock at the same time, one of them gets
it one of them does not right. So, assume that when this was the case that
this is own that get selected, this is selected and the data gets powered it here and then
it gets process here and then the copy return backs returns back to the buffer let we started,
then what will happen again now then this transition can then trigger after that right.
So, this is step one gets process tier and then you know comes back here, now that the
data it item is available, that is also data item available herethen this can get processed
and then gets toyed in the next transition triggers and then after that we simply return
that back, data back here right. That is one way ofcapturing social, now the
semantic is important right implementing this when a tool will that we have make sure that
these are all clearly stated and how is the going to be the done also very important;
could be simply random anyone of the them which is what will happen in a mutes case
right, is the one in get unless there is specific priorities associated with those. So, that
is have you wouldhandled, you can model resource sharing, so like this there is lot of other
you know variations also. So, how do you handled buffers, how do we
capture a limited size buffer M M 1 B, how will be model that if you remember, count
the put some restriction on the number of tokens, so has to be some other semantic its
comes in, so let us try this particular things. So, here token is produced and the token normally
gets toyed in this buffer, but let say this buffer there some capacity, this a maximum
number of tokens available, so here is some input buffer where we can start of store endlessly.
So, this is P 1, this is T 1, this is P 2, but I want to make sure that in this P 2 part
of the system I should have exactly are at most B buffer I cannot handled more than thatthis
is what happened this is like processing right arrival comes in, this is processing are the
server is selecting the packetand then once the processing happens it goes on to some
other part of the system right something that on here about.
So, what we do this, when P 2 finishes we introduces in other place called P 3 that
will feedback to this T 1 similar, the resource sharing example we saw before, now the condition
is that P 2 plus P 3 right should have less than or equal to B, this is way I can limited
the buffer in the system. So, this again something this is part of the specification right, so
have to normally draw this diagram also put in some other data that explains the, this
is the meaning right, so have to some other notations to capture that. So, if I do that
then what happens initially whatwhere willlets a B equalsyou knowis 3 let B equals 3, initially
what will be the system state initial marking where will those three tokens B P 1 inputs
in coming here. So, that is some input process it is generating this P 2 is time variable,
this is where this is actual storage before it goes to server right. So, this could be
infinite I am not thinking about that this is where I want to control and you want to
see at most 3 packets in P 2,P 3 combined. So, were we will puts the three tokens P 3,
so I put the three tokens here, I put the three tokens there right. So, this is empty
now what will happen can this T 1 fired, T 1 cannot fired unless there is the inputs
that in generated right, so I will try red, so input arrivesthis is input, what happens
now, I will there is at least one token here, at least one token here and therefore, this
transition will no fired. So, when that transition fires, this token
is removed one token is removed and where is the token now added token gets added there
right, so P 2 has no one token. So, what will happen is going to get processed by this transition
T 2, so after processing right when this transition T 2finally triggers and completes what will
happen this packet is now processed in this going on to next destination, at the same
time you are now returning right the token here,that is word try it to do. So, therefore,
in the instant of time that only process this 1 packet there, they were two tokens setting
here, there is 1 here, so collectively we had 3 right, but we could also have this over
the opposite is also true right, so it is possible that I will have say no packets here
and let say that currently. I have 3 packets setting there, that looks
like a smiley, so there are 3 packets sitting in P 2 which means there is no packet sitting
in P 3. So, what happens if a new packets comes in can it trigger, new packet cannot
get trigger why because, there is nothing in P 3, so when will P 3 get one token only
when one process that is or one token that is getting process T 2 finishes and comes
back to P 3 that is you have a model a system with buffer is it understood right. So, that
is need pay of trend to, but only these have to mechanism is specifying there this P 3,
P 2,P 3 or tie together and there is extra condition right, so this is now additional
distains on the system that, we have to tell the underlines in implement under than underline
tool to have able to process that correctly; so questions on this part, no?
Now, can I simplify this to represent by M M 1 B with what remember me saw M M 1right
had just a two transition then one place in between, now can I do same think how do I
convert this two way M M 1 B there anyway we can do that, I do not need an input place,
I do not need anything to whole the input place right (No Audio From 50.24 to 50.32).
So, this is the transition T 1 with parameter lambda exponential rightthis is theimplicitly
exponential, the actually special class of network this not a general, stochastic petri
network that is when this will apply, but we will defined those things later on. So,
then I have that, this is where the all packets of getting stored, this is where all the packets
are getting processed, this ismy secondary buffer that isall right this represents M
M 1 B as long as will still called P 2 and P 3 right where the condition that P 2 plus
P 3 should be less than equal to B, that is all any right, because this tried trigger
willeven there is no keep on triggering right every one more lambda units of our main units
of time it will keep generating a packet, and the server will keep processing after
processing we do not care what happens, you only care about the number of packets in the
system for given lambda and given mu that is for we want to look at.
So, that is your, how we can capture buffer in the system M M 1 B right, what we saw before
was only P 2, but not the extra P 3 is brought in to capture the limits on the particular
system. And likewise, we can also you know when you
talking about communication protocols, network protocolswe can also emulate or model the
passage of messages between two different programs. So, let see there is program 1 or
process 1 let is doing some set of processing right, so that is the conditional class there
is right there is the dependency there and then some set of processing is taking place
and this is one process programthen there is program 1, which is doing some processing
it generates something and output of this transition goes there and notice this around
the put always there right side right, we can enough do wherever want to as long as
the arrows clear we know what is this representative, one more transition, one more placeand then
finally, this is done. So, this is one message that is going from program 2 to program 1
and we care also have and other message fromfrom here to here sorry, this is a way of trying
to show two programs sending messages to each other. So, what will be the interpretation
of this, can you think of let say this is the senderand this this technically need not
be there this particularly loop actually lets need not be there. So, what happens is this,
so when the sender whenever there is the message to be sent this transition triggers, so message
is available transition triggers. What is it do, itsends that message to other
program, so basically there is a token being placed here, and let say the token is always
there right it is not relevant. So, as you as get a message this is sender, this is receiver
right; sender this is the processing of the sending packet all the transmission of everything
is happening here, messages now low read there and I can introduce delays on this arc itself,
which here not at you know dealing with for now. So, now, there is a message available
this is some other internal condition which is true, so message gets processed by the
receiver and thenthe message gets received and then right some initial processing is
done here, then some computation is also done here, after the end of the computation what
happens is right, let say that there is a tokens it finally gets placed it could represent
the arc packet. So, this represents the message being sent
right this is where the packet generationis taking place, after sending the packet what
to I do with it I buffer it right we all buffer it right then I sit here waiting, so this
transition will not trigger, will trigger only there is a buffer packet and an acknowledgement
come from the receiver I then go forward and I can remove this token from here, place the
token here right the buffer can get empty, that lapper only when get the return message
interms of an acknowledgement, this is like a simple stock, when protocol I send the message
wait for the sender to the acknowledgement, I get the acknowledgement and I go forward
remove the token from here, put the token here this could be simply, post packet processing
right, whatever that is involved here this could be deleting this packet recording delay
and thinks like that. So, this is the way and actually model the communication between
to entity in a given system right. So, these are all the various thingsthat you can do
for a system is its communication modelexplanations are fine, so packet gets generated gets and
gets processed some additional processing acknowledgement get generated comes back right.
I could may be removes this place it is really not relevant right, just to show that someactivities
is going on basically I get it process technology its sent it back I canrelease the packet from
I buffer from the sender buffer and then proceed for that beyond that point. So, like this
there are lots of such combinations, so now what do we do with always, so what is the
point of all the diagram drawing right. So, we are interested in some mathematical properties
of this system and then also finding out if we can derive some performance matrix from
this system. So, what are the properties of the petri net,
that one would be interested inthere are several we will just list about four of them, the
first is called the boundedness property, we would like to knowfor a given system, for
a given marking depending on the way all these transitions flow right would the number of
tokens in a place be bounded, that is a questions
that we want to ask, that is the fundamental property why because, if the number of tokens
keeps growing unbounded we know the system unstable and therefore, right being in the
having lots of delays in things like that we see with the M M 1right,MM 1 if lambda
is greater than mew it is going to be unstable and therefore the queue size will grow very
large and therefore, we will have right unstable behavior. So, there is something that is a
property that we will like to investigate and the second is saw, so called safeness
which is the special case of this boundedness propertywhich says the system is supposed
be safe, ifwill the number of tokens in any place exceed one, that is also an important
question, will any place or a number of tokens by mistake exit one where you do not want
that happen is that say this is the manufacturing plan right some assembly is going on and you
do not want to have say two parts right ofits tried build a car are may be some other small
at component, you do not want have two parts are two numbers of same part trying up in
the given assembly like on a given particular unit right, one machine can only handled say
one particular item you do not want to have two items showing upon the disk at is similar
can happen right. Because some have the way the delays areknow done in the system is it
will it be the case that there will be a one particular place with more than one token
between, more than one component we will build which it cannot handled which means system
right end that machine may and crashing andso on.
So, that is the so called safeness property of the system, which we may not relate yet
in terms of computing there are probably other applications and the second thing is whether
is dead lock free, in other words enter a marking where from which is in get out of
we will about a dead lock right where. So, I entered in a state are a marking where I
cannot leave that marking and move to any other state of the system, so dead lock is
also an important property of such a system and the fourth is so called reach ability
property. So, given the initial marking M not M of t 0 thus initial marking I want to
know, can I reach this some other specified marking, is it possible toreach some other
marking say you know M A. So, what is that mean it means this right,
let say there are four places in the system and the initial state 0, 1, 0, 0 this is M
of T not for some particular system that we are modeling, I want to know whether is it
possible to through a series of transition at just 1 transition, it was series of transition
can I end of in the state M A which will be say 2, 3, 4, 4 are something like, thatthis
is some for some reason I need to find out the disk and happen are not, this may be should
happen or should not happen right for whatever reason I want to know whether it is possible
go from this state to this particular state, so how do we do that, is it possible right.
That is something that system should be able to answer with help of its tool that be talking
about right. So, these are some of the properties of this petri net that one word like to investigated,
so how do we do that, I will just stop after there, so the analysis methods, so given a
petri net and given this petri net on this different properties and how do we go about
stating the properties that we are true or untrue whatever it is we have to shows improves.
So, the simplest way to that is enumeration right I have bunch of states I have bunch
of transitions are try all possible combinations right start first one then T 1 then T 1, T
2 T 1, T 2, T 3 and so on. So, we can do just enumerate and there are tools that at will
do that for you up towards next and right you can actually try enumerating to the extend
possible become exponential then of course, you run out of time, but you like to see weather
this is endurable and reasonable amount of time to be able answer this particular question,
so that is one particular right there. And the second is M M sir linear algebra techniqueswhere
we use repeated you know matrix multiplications, also can be used I am not going to the detail
of those due to lack of time, but these are ways you can actually used in algebra to find
out right the probability going from are not probability is, that we will going to be the
next state, we saw this when we did our Marko state chainMarko chains right. Where given
the initial state of the system thatand then gave in the state transition matrix right,
if applied once that is once to transitions I apply the multiply by the same esteem again
I get the next possible set of states and which this keeps on going and till you find
out the steady state probability right, that is how we did that at the similarly, we can
keep on try to this the algebra techniques of this just multiplying by matrix over and
over again find out some set of properties of the system itself.
So, that is something it we willagain not cover about and the third is actually simulation,
so, this is gain of interesting right we said going to use petri nets to complement our
simulation, now I am saying actually I will simulate the petri net to find out thesebehavior
of the system, so in some cases what what the idea is that you can either this the same
code right, can be codedas the petri net with this more formal representation.
If you look at this your simulation code is there of formal representation of states and
transition between the states we do not really have that right, it is bunch of function is
called in like that, but assume you can representthat in a formal manner with this transition in
things like that, then you can actually bring any simulated right, we did this all those
one of the first assignment, the tutorial the assignment one was actually simulating
the change ofstates right, we started of some states with some probability p y we move to
different state then to different states and so on, that is simply simulation right.
So, likewise I can do that, I can start of with the initial transition with initial marking
and then when there are choices right I can keep one randomly choosing one of those choices
and then tried similar system behavior and then see whether it is possible to go to this
particular state are are some other state in the system. So, that is also these are
all different techniques that can one use foranalyzing the system right and then that
last techniques is also converting this petri net are the will at stochastic petri net,
so we can convert as stochastic petri net to a mark out chain a continues time mark
out chain then you can see a continues time mark out chain properties to actually solve
problems are answer problems in the original stochastic petri net. So, that is the first
level introduction of what petri nets are, so it basically collection of places transitions
and arcs at the system defined behavior that is what we are seeing now so for, we will
come back and the next lecture, we will cover as to we look at an example, that will show
actually how we can model a system, and how we can actually derived a performance matrix
from those system, we from those system with the help ofthe petri net model.

19 comments on “Mod-01 Lec-39 PetriNets-I

  1. I do not understand the negative comments on this presentation.  Yes, he has an accent, but he is easy to understand.  I thought this was presented in a clear step by step manner.  Thanks for sharing your lecture.

  2. Although im quite good in english (not mothertounge) it`s really hard to understand the accent 🙁

Leave a Reply

Your email address will not be published. Required fields are marked *