1©Magee/Kramer 2nd EditionCSCI 5828: Foundations ofSoftware EngineeringLecture 7: Concurrent ExecutionSlides created by Magee and Kramer forthe Concurrency textbookConcurrency: concurrent execution 2©Magee/Kramer 2nd EditionChapter 3Concurrent ExecutionConcurrency: concurrent execution 3©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 4©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 5©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 6©Magee/Kramer 2nd Editionparallel composition - action interleavingthinktalk scratchthinkscratchtalkscratchthinktalkPossible 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 7©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 statesIT CHscratch0 1CONVERSEthink talk0 1 2CONVERSE_ITCHscratchthinkscratchtalk scratchtalk think0 1 2 3 4 5Concurrency: concurrent execution 8©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 9©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 10©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 11©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 12©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 13©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 14©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 15©Magee/Kramer 2nd Editionprocess prefix labels for shared resourcesHow does the model ensurethat the user that acquiresthe resource is the one torelease it?a:USERa.acquire a.usea.release0 1 2b:USERb.acquire b.useb.release0 1 2{a,b}::RESOURCEa.acquireb.acquirea.releaseb.release0 1RESOURCE_SHAREa.acquireb.acquire b.useb.releasea.usea.release0 1 2 3 4Concurrency: concurrent execution 16©Magee/Kramer 2nd Editionaction relabelingRelabeling to ensure that composedprocesses synchronize on particular actions.Relabeling functions are applied to processes to changethe names of action labels. The general form of therelabeling function is: /{newlabel_1/oldlabel_1,… newlabel_n/oldlabel_n}.CLIENT = (call->wait->continue->CLIENT).SERVER = (request->service->reply->SERVER).Note that both newlabel and oldlabel can be sets of labels.Concurrency: concurrent execution 17©Magee/Kramer 2nd Editionaction relabeling||CLIENT_SERVER = (CLIENT || SERVER) /{call/request, reply/wait}.CLIENTcall r eplycontinue0 1
View Full Document