Concurrency : Functions vs Processes

.Concurrency 2Functions vs Processes) InteractionJean-Jacques L´evyjeanjacqueslevy.net/dea1.Concurrency ) Non-deterministismSuppose x is a global variable. At beginning, x=0ConsiderP =[x:=x+1;x:=x+1jjx:=2⁄x]after P, then x may have several values (x2f2;3;4g)Hence P is not a function from memory states to memory states.In concurrent programming, execution is not deterministic since it isupto an external agent (the scheduler).Let Σ=Variables7!Values be the set of memory states.Let [P] be the meaning of P.A concurrent program is not a (partial) function from memory states tomemory states. [P]62Σ7!Σ.ΣA concurrent program is a relation on memory states. [P]2Σ7!2 .26.Concurrency ) InteractionConsiderP =[x:=1]Q=[x:=0;x:=x+1]P and Q are same functions on memory states : ¾7!¾[1=x]Howeverafter P jjP, then x2f1gafter P jjQ, then x2f1;2gA semantic (meaning) is compositional iff [P]=[Q] implies[C[P]]=[C[Q]] for any context C[].In previous example, in any compositional semantics, [P]=[Q].ConclusionP and Q are not equivalent processes.3.Concurrency , TerminationConcurrent processes are often non terminating.An operating system never terminates; same for the software of avending machine, or a traffic-light controler, or a human, etc.A process P is a set of pairs (f ;P ), atomic action and a derivativei iprocess. It starts by performing f and then becomes process P .i iAtomic steps usually terminate.(Σ7!Σ)£PRoughly speaking, let P be the set of ...