Designing Concurrent Programs
• It’s hard
– where to start?
– translation from pseudocode not always clear – tricky race conditions
– seems to be ad hoc
• What’s needed
– systematic ways to write concurrent programs
Systematic Concurrent Program Design (Review)
• Concepts:
– atomic actions
• denoted by < S >
• means execute S atomically
– await statements
• allowed inside atomic actions
• denoted by < await (B) S >
• means atomically: wait for B to be true, then execute S
• if no await (i.e., just < S >, we assume that B is “true”, i.e. < await (TRUE) S >
Example — Readers/Writers (Review)
• ReadEnter()
• ReadExit()
• WriteEnter()
• WriteExit()
Advantages (Review)
• Whenever “worried” about race conditions – just put code inside an atomic action
• Don’t need to worry about ensuring threads are eligible to proceed past an await
– this is done automatically
How to implement atomic actions and await statements?
• Use one single entry semaphore, e, for the whole program — initialized to 1
• Consider each atomic action of form: < await (B) S >
• Associate with each a counter db, a blocking semaphore b; both initialized to 0
– semaphore b will block threads when B is false
– counter db will keep track of number of threads delayed on semaphore b
Translating
P(e)
if (!B1) {
db1++; V(e); P(b1)
S1 SIGNAL
// gain mutual exclusion
// if B1 false, better block // increase counter
// release mutual exclusion // block
// now we execute S1
// maybe others can wake up
}
P(e)
S1 SIGNAL
Translating
// gain mutual exclusion
// now we execute S1
// maybe others can wake up
What’s SIGNAL?
• Suppose there are n different guards in atomic actions in the program
• Then, SIGNAL is:
if B1 and db1 > 0 db1–; V(b1)
else if B2 and db2 > 0 db2–; V(b2)
else if …..
elseifBnanddbn >0 dbn–; V(bn)
else V(e)
Example with Readers/Writers
Example with Readers/Writers
SIGNAL can be often be optimized
• May be the case that some guards can not possibly be true
– can then just eliminate them
– e.g., : Readers/Writers
• when reader leaves database, we know there cannot possibly be any delayed writers
Atomic Actions become “Passing the Baton” solution
• Advantages:
– methodical
– compiler could make transformation
– passing the baton solutions are easy to modify to achieve different goals (e.g., who has preference, fairness, etc.)
• Disadvantages
– solution overly general
– can optimize by hand, but difficult for compiler