Concurrency: concurrent execution 1 ©Magee/Kramer 2nd EditionConcurrency: concurrent execution 2 ©Magee/Kramer 2nd EditionConcurrency: concurrent execution 3 ©Magee/Kramer 2nd Edition Chapter 3 Concurrent ExecutionConcurrency: concurrent execution 4 ©Magee/Kramer 2nd Edition Concurrent execution Concepts: processes - concurrent execution and interleaving. process interaction. Models: parallel composition of asynchronous processes - interleaving interaction - shared actions process labeling, and action relabeling and hiding structure diagrams Practice: Multithreaded Java programsConcurrency: concurrent execution 5 ©Magee/Kramer 2nd Edition Definitions Concurrency Logically simultaneous processing. Does not imply multiple processing elements (PEs). Requires interleaved execution on a single PE. Parallelism Physically simultaneous processing. Involves multiple PEs and/or independent device operations. Both concurrency and parallelism require controlled access to shared resources . We use the terms parallel and concurrent interchangeably and generally do not distinguish between real and pseudo-concurrent execution. A Time B CConcurrency: concurrent execution 6 ©Magee/Kramer 2nd Edition 3.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 Edition parallel composition - action interleaving thinktalkscratch thinkscratchtalk scratchthinktalk Possible traces as a result of action interleaving. If P and Q are processes then (P||Q) represents the concurrent execution of P and Q. The operator || is the parallel composition operator. ITCH = (scratch->STOP). CONVERSE = (think->talk->STOP). ||CONVERSE_ITCH = (ITCH || CONVERSE). Disjoint alphabetsConcurrency: concurrent execution 8 ©Magee/Kramer 2nd Edition parallel composition - action interleaving (0,0) (0,1) (0,2) (1,2) (1,1) (1,0) from CONVERSE from ITCH 2 states 3 states 2 x 3 states ITCHscratch0 1CONVERSEthink talk0 1 2CONVERSE_ITCHscratchthinkscratchtalk scratchtalk think0 1 2 3 4 5The combined process is the Cartesian product of ITCH and CONVERSEConcurrency: concurrent execution 9 ©Magee/Kramer 2nd Edition parallel composition - algebraic laws Commutative: (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 Edition modeling interaction - shared actions MAKER = (make->ready->MAKER). USER = (ready->use->USER). ||MAKER_USER = (MAKER || USER). MAKER synchronizes with USER when ready. If processes in a composition have actions in common, these actions are said to be shared. Shared actions are the way that process interaction is modeled. While unshared actions may be arbitrarily interleaved, a shared action must be executed at the same time by all processes that participate in the shared action. LTS? Traces? Number of states? Non-disjoint alphabetsConcurrency: concurrent execution 11 ©Magee/Kramer 2nd Edition shared 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” action at the same timeConcurrency: concurrent execution 12 ©Magee/Kramer 2nd Edition MAKERv2 = (make->ready->used->MAKERv2). USERv2 = (ready->use->used ->USERv2). ||MAKER_USERv2 = (MAKERv2 || USERv2). modeling interaction - handshake A handshake is an action acknowledged by another: Interaction constrains the overall behaviour. 3 states 3 states 3 x 3 states? 4 states make ready useused0 1 2 3Concurrency: concurrent execution 13 ©Magee/Kramer 2nd Edition modeling interaction - multiple processes MAKE_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 Edition composite processes A composite process is a parallel composition of primitive processes. These composite processes can be used in the definition of further compositions. ||MAKERS = (MAKE_A || MAKE_B). ||FACTORY = (MAKERS || ASSEMBLE). Substituting the definition for MAKERS in FACTORY and applying the commutative and associative laws for parallel composition results in the original definition for FACTORY in terms of primitive processes. ||FACTORY = (MAKE_A || MAKE_B || ASSEMBLE).Concurrency: concurrent execution 15 ©Magee/Kramer 2nd Edition process instances and labeling a: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 Edition process labeling by a set of prefix labels {a1,..,ax}::P replaces every action label n in the alphabet of P with the labels a1.n,…,ax.n. Further, every transition (n->X) in the definition of P is replaced 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
View Full Document
Unlocking...