DOC PREVIEW
Berkeley ELENG C249A - Lecture Notes

This preview shows page 1-2-3-4-5-6-7-50-51-52-53-54-55-56-100-101-102-103-104-105-106 out of 106 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 106 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1EE249Fall04Outline• Petri nets– Introduction– Examples– Properties– Analysis techniques2EE249Fall04Petri Nets (PNs)• Model introduced by C.A. Petri in 1962– Ph.D. Thesis: “Communication with Automata”• Applications: distributed computing, manufacturing, control, communication networks, transportation…• PNs describe explicitly and graphically:– sequencing/causality– conflict/non-deterministic choice– concurrency• Basic PN model– Asynchronous model (partial ordering)– Main drawback: no hierarchy3EE249Fall04Example: Synchronization at single track rail segment• „Preconditions“4EE249Fall04Playing the „token game“5EE249Fall04Conflict for resource „track“6EE249Fall04Petri Net Graph• Bipartite weighted directed graph:– Places: circles– Transitions: bars or boxes– Arcs: arrows labeled with weights• Tokens: black dotst1p1p2t2p4t3p3237EE249Fall04Petri Net• A PN (N,M0) is a Petri Net Graph N– places: represent distributed state by holding tokens– marking (state) M is an n-vector (m1,m2,m3…), where mi is the non-negative number of tokens in place pi.– initial marking (M0) is initial state– transitions: represent actions/events– enabled transition: enough tokens in predecessors– firing transition: modifies marking• …and an initial marking M0.t1p1p2t2p4t3p323Places/Transitions: conditions/events8EE249Fall04Transition firing rule• A marking is changed according to the following rules:– A transition is enabled if there are enough tokens in each input place– An enabled transition may or may not fire– The firing of a transition modifies marking by consuming tokens from the input places and producing tokens in the output places2232239EE249Fall04Concurrency, causality, choicet1t2t3 t4t5t610EE249Fall04Concurrency, causality, choiceConcurrencyt1t2t3 t4t5t611EE249Fall04Concurrency, causality, choiceCausality, sequencingt1t2t3 t4t5t612EE249Fall04Concurrency, causality, choiceChoice,conflictt1t2t3 t4t5t613EE249Fall04Concurrency, causality, choiceChoice,conflictt1t2t3 t4t5t614EE249Fall04Communication ProtocolP1Send msgReceive AckSend AckReceive msgP215EE249Fall04Communication ProtocolP1Send msgReceive AckSend AckReceive msgP216EE249Fall04Communication ProtocolP1Send msgReceive AckSend AckReceive msgP217EE249Fall04Communication ProtocolP1Send msgReceive AckSend AckReceive msgP218EE249Fall04Communication ProtocolP1Send msgReceive AckSend AckReceive msgP219EE249Fall04Communication ProtocolP1Send msgReceive AckSend AckReceive msgP220EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer21EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer22EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer23EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer24EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer25EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer26EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer27EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer28EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer29EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer30EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer31EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer32EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer33EE249Fall04Producer-Consumer ProblemProduceConsumeBuffer34EE249Fall04Producer-Consumer with priorityConsumer B can consume only if buffer A is emptyInhibitor arcsAB35EE249Fall04PN properties• Behavioral: depend on the initial marking (most interesting)– Reachability– Boundedness– Schedulability– Liveness– Conservation• Structural: do not depend on the initial marking (often too restrictive)– Consistency– Structural boundedness36EE249Fall04Reachability• Marking M is reachable from marking M0 if there exists a sequence of firings σσσσ = = = = M0 t1 M1 t2 M2… M that transforms M0 to M.• The reachability problem is decidable.t1p1p2t2p4t3p3Μ0 = (1,0,1,0)M = (1,1,0,0)Μ0 = (1,0,1,0)t3M1 = (1,0,0,1)t2M = (1,1,0,0)37EE249Fall04• Liveness: from any marking any transition can become fireable– Liveness implies deadlock freedom, not viceversaLivenessNot live38EE249Fall04• Liveness: from any marking any transition can become fireable– Liveness implies deadlock freedom, not viceversaLivenessNot live39EE249Fall04• Liveness: from any marking any transition can become fireable– Liveness implies deadlock freedom, not viceversaLivenessDeadlock-free40EE249Fall04• Liveness: from any marking any transition can become fireable– Liveness implies deadlock freedom, not viceversaLivenessDeadlock-free41EE249Fall04• Boundedness: the number of tokens in any place cannot grow indefinitely– (1-bounded also called safe)– Application: places represent buffers and registers (check there is no overflow)BoundednessUnbounded42EE249Fall04• Boundedness: the number of tokens in any place cannot grow indefinitely– (1-bounded also called safe)– Application: places represent buffers and registers (check there is no overflow)BoundednessUnbounded43EE249Fall04• Boundedness: the number of tokens in any place cannot grow indefinitely– (1-bounded also called safe)– Application: places represent buffers and registers (check there is no overflow)BoundednessUnbounded44EE249Fall04• Boundedness: the number of tokens in any place cannot grow indefinitely– (1-bounded also called safe)– Application: places represent buffers and registers (check there is no overflow)BoundednessUnbounded45EE249Fall04• Boundedness: the number of tokens in any place cannot grow indefinitely– (1-bounded also called safe)– Application: places represent buffers and registers (check there is no overflow)BoundednessUnbounded46EE249Fall04Conservation•Conservation: the total number of tokens in the net is constantNot conservative47EE249Fall04Conservation•Conservation: the total number of tokens in the net is constantNot conservative48EE249Fall04Conservation•Conservation: the total number of tokens in the net is constantConservative2249EE249Fall04Analysis techniques• Structural analysis techniques– Incidence matrix– T- and S- Invariants• State Space Analysis techniques– Coverability Tree– Reachability Graph50EE249Fall04Incidence Matrix• Necessary condition for marking M to be reachable from initial marking M0:there exists firing vector v s.t.:M = M0+ A vp1 p2 p3t1t2t3A=A=--1100001111--1100--1111t1 t2 t3p1p2p351EE249Fall04State equationsp1 p2


View Full Document

Berkeley ELENG C249A - Lecture Notes

Documents in this Course
Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?