1©Magee/Kramer 2nd EditionCSCI 5828: Foundations ofSoftware EngineeringLecture 7: Concurrent ExecutionSlides created by Magee and Kramer forthe Concurrency textbook2/05/2008Concurrency: concurrent execution 2©Magee/Kramer 2nd EditionWhat’s the Difference? EXAMPLE = ({foo, bar} → baz → EXAMPLE). and EXAMPLE1 = ({foo, bar} → BAZ), BAZ = (baz → EXAMPLE1).Concurrency: concurrent execution 3©Magee/Kramer 2nd EditionChapter 3Concurrent ExecutionConcurrency: concurrent execution 4©Magee/Kramer 2nd EditionConcurrent executionConcepts: processes - concurrent execution and interleaving. process interaction.Models: parallel composition of asynchronous processes - interleavinginteraction - shared actionsprocess labeling, and action relabeling and hidingstructure diagramsPractice: Multithreaded Java programsConcurrency: concurrent execution 5©Magee/Kramer 2nd EditionDefinitionsConcurrencyLogically simultaneous processing.Does not imply multiple processingelements (PEs). Requiresinterleaved execution on a single PE.ParallelismPhysically simultaneous processing.Involves multiple PEs and/orindependent device operations.Both concurrency and parallelism require controlled access toshared resources . We use the terms parallel and concurrentinterchangeably and generally do not distinguish between real andpseudo-concurrent execution.ATimeBCConcurrency: concurrent execution 6©Magee/Kramer 2nd Edition3.1 Modeling Concurrency How should we model process execution speed? arbitrary speed(we abstract away time) How do we model concurrency? arbitrary relative order of actions from different processes(interleaving but preservation of each process order ) What is the result? provides a general model independent of scheduling(asynchronous model of execution)Concurrency: concurrent execution 7©Magee/Kramer 2nd Editionparallel composition - action interleavingthinktalkscratchthinkscratchtalkscratchthinktalkPossible traces asa result of actioninterleaving.If P and Q are processes then (P||Q) represents theconcurrent execution of P and Q. The operator || isthe parallel composition operator.ITCH = (scratch->STOP).CONVERSE = (think->talk->STOP).||CONVERSE_ITCH = (ITCH || CONVERSE).DisjointalphabetsConcurrency: concurrent execution 8©Magee/Kramer 2nd Editionparallel composition - action interleaving(0,0) (0,1) (0,2) (1,2)(1,1) (1,0)from CONVERSEfrom ITCH2 states3 states2 x 3 statesITCHscratch0 1CONVERSEthink talk0 1 2CONVERSE_ITCHscratchthinkscratchtalk scratchtalk think0 1 2 3 4 5The combinedprocess is theCartesian productof ITCH andCONVERSEConcurrency: concurrent execution 9©Magee/Kramer 2nd Editionparallel composition - algebraic lawsCommutative: (P||Q) = (Q||P)Associative: (P||(Q||R)) = ((P||Q)||R) = (P||Q||R).Clock radio example:CLOCK = (tick->CLOCK).RADIO = (on->off->RADIO).||CLOCK_RADIO = (CLOCK || RADIO).LTS? Traces? Number of states?Concurrency: concurrent execution 10©Magee/Kramer 2nd Editionmodeling interaction - shared actionsMAKER = (make->ready->MAKER).USER = (ready->use->USER).||MAKER_USER = (MAKER || USER).MAKERsynchronizeswith USERwhen ready.If processes in a composition have actions in common,these actions are said to be shared. Shared actions arethe way that process interaction is modeled. Whileunshared actions may be arbitrarily interleaved, ashared action must be executed at the same time by allprocesses that participate in the shared action.LTS? Traces? Number of states?Non-disjointalphabetsConcurrency: concurrent execution 11©Magee/Kramer 2nd Editionshared alphabets affect the Cartesian product BILL = (play → meet → STOP). BEN = (work → meet → STOP). Each process has three states (initial, after first action, after second action) Cartesian product should produce 9 states (3 x 3) But LTS contains only 5 states! Why? Due to rules governing shared actions Full Cartesian Product: (initial, initial), (initial, work), (initial, meet), (play,initial), (play, work), (play, meet), (meet, initial), (meet, work), (meet, meet) But due to rules governing shared actions, the red tuples are not permitted;Both processes must be ready to transition to the state after the “meet” actionat the same timeConcurrency: concurrent execution 12©Magee/Kramer 2nd EditionMAKERv2 = (make->ready->used->MAKERv2).USERv2 = (ready->use->used ->USERv2).||MAKER_USERv2 = (MAKERv2 || USERv2).modeling interaction - handshakeA handshake is an action acknowledged by another:Interactionconstrainsthe overallbehaviour.3 states3 states3 x 3states?4 statesmake ready useused0 1 2 3Concurrency: concurrent execution 13©Magee/Kramer 2nd Editionmodeling interaction - multiple processesMAKE_A = (makeA->ready->used->MAKE_A).MAKE_B = (makeB->ready->used->MAKE_B).ASSEMBLE = (ready->assemble->used->ASSEMBLE).||FACTORY = (MAKE_A || MAKE_B || ASSEMBLE).Multi-party synchronization:makeAmakeB makeA ready assembleusedmakeB0 1 2 3 4 5Concurrency: concurrent execution 14©Magee/Kramer 2nd Editioncomposite processesA composite process is a parallel composition of primitiveprocesses. These composite processes can be used in thedefinition of further compositions.||MAKERS = (MAKE_A || MAKE_B).||FACTORY = (MAKERS || ASSEMBLE).Substituting the definition for MAKERS in FACTORY and applying thecommutative and associative laws for parallel composition results inthe original definition for FACTORY in terms of primitive processes.||FACTORY = (MAKE_A || MAKE_B || ASSEMBLE).Concurrency: concurrent execution 15©Magee/Kramer 2nd Editionprocess instances and labelinga:P prefixes each action label in the alphabet of P with a.SWITCH = (on->off->SWITCH).||TWO_SWITCH = (a:SWITCH || b:SWITCH).Two instances of a switch process:||SWITCHES(N=3) = (forall[i:1..N] s[i]:SWITCH).||SWITCHES(N=3) = (s[i:1..N]:SWITCH).An array of instances of the switch process:a:SWITCHa.ona.off0 1b:SWITCHb.onb.off0 1Concurrency: concurrent execution 16©Magee/Kramer 2nd Editionprocess labeling by a set of prefix labels{a1,..,ax}::P replaces every action label n in thealphabet of P with the labels a1.n,…,ax.n. Further,every transition (n->X) in the definition of P isreplaced with the transitions ({a1.n,…,ax.n} ->X).Process prefixing is useful for modeling shared resources:||RESOURCE_SHARE = (a:USER || b:USER || {a,b}::RESOURCE).RESOURCE = (acquire->release->RESOURCE).USER = (acquire->use->release->USER).Concurrency: concurrent execution
View Full Document
Unlocking...