CSCI 5828 Foundations of Software Engineering Lecture 12 Concurrent Execution Slides created by Magee and Kramer for the Concurrency textbook 1 Magee Kramer 2nd Edition Chapter 4 Shared Objects Mutual Exclusion Concurrency shared objects mutual exclusion 2 Magee Kramer 2nd Edition Shared Objects Mutual Exclusion Concepts process interference mutual exclusion Models model checking for interference modeling mutual exclusion Practice thread interference in shared Java objects mutual exclusion in Java synchronized objects methods Concurrency shared objects mutual exclusion 3 Magee Kramer 2nd Edition 4 1 Interference Ornamental garden problem People enter an ornamental garden through either of two turnstiles Management wish to know how many are in the garden at any time Garden West Turnstile people East Turnstile The concurrent program consists of two concurrent threads and a shared counter object Concurrency shared objects mutual exclusion 4 Magee Kramer 2nd Edition ornamental garden Program class diagram Thread Applet Garden east west Turnstile run init go eastD westD counterD people Counter increment display display NumberCanvas setvalue The Turnstile thread simulates the periodic arrival of a visitor to the garden every second by sleeping for a second and then invoking the increment method of the counter object Concurrency shared objects mutual exclusion 5 Magee Kramer 2nd Edition ornamental garden program The Counter object and Turnstile threads are created by the go method of the Garden applet private void go counter new Counter counterD west new Turnstile westD counter east new Turnstile eastD counter west start east start Note that counterD westD and eastD are objects of NumberCanvas used in chapter 2 Concurrency shared objects mutual exclusion 6 Magee Kramer 2nd Edition Turnstile class class Turnstile extends Thread NumberCanvas display Counter people Turnstile NumberCanvas n Counter c display n people c The run method exits and the thread terminates after Garden MAX visitors have entered public void run try display setvalue 0 for int i 1 i Garden MAX i Thread sleep 500 0 5 second between arrivals display setvalue i people increment catch InterruptedException e Concurrency shared objects mutual exclusion 7 Magee Kramer 2nd Edition Counter class class Counter int value 0 NumberCanvas display Counter NumberCanvas n display n display setvalue value void increment int temp value read value Simulate HWinterrupt value temp 1 write value display setvalue value Hardware interrupts can occur at arbitrary times The counter simulates a hardware interrupt during an increment between reading and writing to the shared counter value Interrupt randomly calls Thread sleep to force a thread switch Concurrency shared objects mutual exclusion 8 Magee Kramer 2nd Edition ornamental garden program display After the East and West turnstile threads have each incremented its counter 20 times the garden people counter is not the sum of the counts displayed Counter increments have been lost Why Concurrency shared objects mutual exclusion 9 Magee Kramer 2nd Edition concurrent method activation Java method activations are not atomic thread objects east and west may be executing the code for the increment method at the same time west PC program counter shared code increment read value east PC program counter write value 1 Concurrency shared objects mutual exclusion 10 Magee Kramer 2nd Edition ornamental garden Model go end go end arrive GARDEN value east TURNSTILE go end arrive value VAR display read write value west TURNSTILE Process VAR models read and write access to the shared counter value Increment is modeled inside TURNSTILE since Java method activations are not atomic i e thread objects east and west may interleave their read and write actions Concurrency shared objects mutual exclusion 11 Magee Kramer 2nd Edition ornamental garden model const N 4 range T 0 N set VarAlpha value read T write T VAR VAR 0 VAR u T read u VAR u write v T VAR v The alphabet of shared process VAR is declared explicitly as a set constant VarAlpha TURNSTILE go RUN RUN arrive INCREMENT end TURNSTILE INCREMENT value read x T value write x 1 RUN VarAlpha GARDEN east TURNSTILE west TURNSTILE east west display value VAR go east west go end east west end Concurrency shared objects mutual exclusion The TURNSTILE alphabet is extended with VarAlpha to ensure no unintended free autonomous actions in VAR eg value write 0 All actions in the shared VAR must be controlled shared by a TURNSTILE 12 Magee Kramer 2nd Edition checking for errors animation Scenario checking use animation to produce a trace Is this trace correct Concurrency shared objects mutual exclusion 13 Magee Kramer 2nd Edition checking for errors exhaustive analysis Exhaustive checking compose the model with a TEST process which sums the arrivals and checks against the display value TEST TEST 0 TEST v T when v N east arrive west arrive TEST v 1 end CHECK v CHECK v T Like STOP ERROR is display value read u T a predefined FSP when u v right TEST v local process state when u v wrong ERROR numbered 1 in the equivalent LTS display VarAlpha Concurrency shared objects mutual exclusion 14 Magee Kramer 2nd Edition ornamental garden model checking for errors TESTGARDEN GARDEN TEST Use LTSA to perform an exhaustive search for ERROR Trace to property violation in TEST go east arrive east value read 0 west arrive west value read 0 east value write 1 LTSA produces west value write 1 the shortest end path to reach display value read 1 ERROR wrong Concurrency shared objects mutual exclusion 15 Magee Kramer 2nd Edition Interference and Mutual Exclusion Destructive update caused by the arbitrary interleaving of read and write actions is termed interference Interference bugs are extremely difficult to locate The general solution is to give methods mutually exclusive access to shared objects Mutual exclusion can be modeled as atomic actions Concurrency shared objects mutual exclusion 16 Magee Kramer 2nd Edition 4 2 Mutual exclusion in Java Concurrent activations of a method in Java can be made mutually exclusive by prefixing the method with the keyword synchronized which uses a lock on the object We correct COUNTER class by deriving a class from it and making the increment method synchronized class SynchronizedCounter extends Counter SynchronizedCounter NumberCanvas n super n synchronized void increment super increment acquire lock release lock Concurrency shared objects mutual exclusion
View Full Document
Unlocking...