Concurrency concurrent execution 1 Magee Kramer 2nd Edition Concurrency concurrent execution 2 Magee Kramer 2nd Edition Chapter 3 Concurrent Execution Concurrency concurrent execution 3 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 programs Concurrency concurrent execution 4 Magee Kramer 2nd Edition Definitions Concurrency Logically simultaneous processing A Does not imply multiple processing B elements PEs Requires interleaved execution on a single PE C Parallelism Physically simultaneous processing Involves multiple PEs and or independent device operations Time 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 Concurrency concurrent execution 5 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 6 Magee Kramer 2nd Edition parallel composition 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 think talk scratch think scratch talk scratch think talk Concurrency concurrent execution Disjoint alphabets Possible traces as a result of action interleaving 7 Magee Kramer 2nd Edition parallel composition action interleaving scratch think ITCH talk CONVERSE 0 1 0 2 states The combined process is the Cartesian product of ITCH and CONVERSE 1 scratch 2 3 states scratch think talk scratch CONVERSE ITCH from ITCH 0 1 2 0 0 0 1 0 2 Concurrency concurrent execution 3 1 2 from CONVERSE 4 talk 1 1 5 think 1 0 2 x 3 states 8 Magee Kramer 2nd Edition parallel composition algebraic laws Commutative Associative P Q Q P P Q R P Q R P Q R Clock radio example CLOCK tick CLOCK RADIO on off RADIO CLOCK RADIO CLOCK RADIO LTS Concurrency concurrent execution Traces Number of states 9 Magee Kramer 2nd Edition modeling interaction shared actions 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 MAKER make ready MAKER USER ready use USER MAKER USER MAKER USER LTS Traces Concurrency concurrent execution Number of states MAKER synchronizes with USER when ready Non disjoint 10 alphabets Magee Kramer 2 Edition nd 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 time Concurrency concurrent execution 11 Magee Kramer 2nd Edition modeling interaction handshake A handshake is an action acknowledged by another MAKERv2 make ready used MAKERv2 USERv2 ready use used USERv2 3 states MAKER USERv2 MAKERv2 USERv2 3 x 3 states make 0 ready 1 2 used Concurrency concurrent execution use 3 3 states 4 states Interaction constrains the overall behaviour 12 Magee Kramer 2nd Edition modeling interaction multiple processes Multi party synchronization 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 makeA makeB 0 makeA 1 ready 2 Concurrency concurrent execution assemble 3 4 makeB used 5 13 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 14 Magee Kramer 2nd Edition process instances and labeling a P prefixes each action label in the alphabet of P with a Two instances of a switch process SWITCH on off SWITCH TWO SWITCH a SWITCH b SWITCH a on b on a SWITCH b SWITCH 0 1 0 a off 1 b off An array of instances of the switch process SWITCHES N 3 forall i 1 N s i SWITCH Concurrency concurrent execution 15 SWITCHES N 3 s i 1 N SWITCH 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 acquire release RESOURCE USER acquire use release USER RESOURCE SHARE a USER b USER a b RESOURCE Concurrency concurrent execution 16 Magee Kramer 2nd Edition process prefix labels for shared resources a acquire a use b acquire a USER b use b USER 0 1 2 0 1 a release 2 b release How does the model ensure that the user that acquires the resource is the one to release it b acquire b acquire a acquire a b RESOURCE 0 1 a acquire b use a release b release a use RESOURCE SHARE 0 1 2 3 4 b release Concurrency concurrent execution 17 a release Magee Kramer 2nd Edition action relabeling Relabeling functions are applied to processes to change the names of action labels The general form of the relabeling function is newlabel 1 oldlabel 1 newlabel n oldlabel n Relabeling to ensure that composed processes synchronize on particular actions CLIENT call wait continue CLIENT
View Full Document
Unlocking...