Summary of Thursday, January 16

1. Characterize interactions which may jeopardize consistency of concurrent systems
2. Describe two basic forms of synchronization required to control these interactions
3. Identify classical concurrent programming problems (illustrate why there are 2 forms)
4. Illustrate synchronization via Java

Characterize Interactions Which May Jeopardize Consistency: Interference

Interference

• Interference refers to the loss of consistency in an object shared among concurrent threads
• This defines interference, but how can we detect or predict it?

Bernstein's condition allows us to identify which threads and objects will interfere

• Consider 2 threads, T1 and T2 with read and write sets, R1, R2, W1, and W2 respectively.
• Then, T1 and T2 will interfere if

(R1 and W2) or (W1 and R2) or (W1 and W2)
Read/Write or Write/Read or Write/Write

Notice that the only condition missing from Berstein's condition is Read/Read. Thus, according to Berstein, this is the only condition in which there is no interference.

Read/Read No Interference Read/Write Interference Write/Write Interference

Note that Berstein's condition does not tell us how to fix the interference.

Two Basic Forms of Synchronization

Mutual Exclusion

• Preventing concurrent access to shared objects in order to preserve consistently
• Useful for a class of synchronization problems, but is not powerful enough for all

Condition Synchronization

• Blocking attempted operations on a shared objects until that object is in a state where the operation will preserve consistency of object
• Note that an ill-conceived sync algo may appear/test fine

Classical Concurrent Programming Problems

Exclusive Use

• Can be handled with simple ME

Producer-Consumer and the ``Bounded Buffer''

• ME not enough. Need state of shared object

Reader-Writer

• Need more than state of shared objects. Need to know state of threads using shared object(s)

Dining Philosophers

• Complex form of multi-ME

Illustrate Synchronization via Java

Java Support for Synchronization -- Threads

• Write code in classes, implement with runnable interface
• Create thread, specifying instance of class
• Basic sync supported via method qualifier -- synchronized

Problem Set 1

• Run CounterTest 10 times
• Explain variation in times
• Create CounterTest with 3 incrementors and 3 decrementors
• Revise BoundedCounterVST, address issues of liveness