Example Concurrent Program
int x = 0 co
x =x +1 //
x =x +2 oc
print x
What are the possible outputs of this program?
1
Example Concurrent Program (cont.)
• One possible execution order is:
– Thread 0: R1 := x
– Thread 1: R2 := x
– Thread 1: R2 := R2 + 2
– Thread 1: x := R2
– Thread 0: R1 := R1 + 1
– Thread 0: x := R1
(R1 == 0) (R2 == 0) (R2 == 2) (x == 2) (R1 == 1) (x == 1)
• Final value of x is 1 (!!)
• Question: what if Thread 1 also uses R1?
2
Example Concurrent Program
int x = 0 co
x =x +1 //
x =x +2 oc
print x
Possible outputs are 1, 2, and 3
0 cannot be an output because of the oc
3
More Concurrent Programming: Linked Lists (head is shared)
Insert(head, elem) {
elem→next := head; head := elem;
}
Void *Remove(head) {
(Assume one thread calls Insert and one calls Remove, concurrently)
Void *t;
t:= head;
head := head→next; return t;
}
4
head
One Possible (Bad!) Execution
Insert: head := elem; head
elem
t
Remove: head := head→next; head
elem
t
Remove: return t;
1.
Insert: elem→next := head;
head
elem
4.
2.
Remove: t := head; head
5.
3.
elem
t
5
Definitions
• Several important terms
– State
• The values of all program variables, both implicit and explicit, at a given point in time
– Atomic action
• an action that indivisibly examines or changes program state
• an operation that, once started, runs to completion
– more precisely, logically runs to completion
• we assume loads and stores are physically atomic
– meaning: if thread A stores “1” into variable x and thread B stores “2” into variable x at about the same time, result is
either “1” or “2”
6
Definitions, continued
• Additional terms
– History
• Linearization (interleaving) of the atomic actions of all threads
– not unique
– Safety: program never enters a bad state
• Example: partial correctness
– Liveness: program eventually enters a good state
• Example: termination
7
Definitions, continued
• Additional terms
– Interference
• Thread 1 interferes with Thread 2 if:
– Thread 1 executes an assignment statement that modifies a shared variable that invalidates an assertion in Thread 2
8
int x = 0 co
{x == 0} x = x + 1
{x == 1} //
{x == 0} x = x + 2
{x == 2} oc
Assertion: represents state before assignment in thread 1
Assignment in thread 1
Assertion: represents state after assignment in thread 1
Assertion: represents state before assignment in thread 2
Assignment in thread 2
Assertion: represents state after assignment in thread 2
Example of Interference Assertions are in {…}
Invalidated!
9
Race Condition
• When output depends on ordering of thread execution
• More formally:
– (1) two or more threads access a shared variable
with no synchronization, and
– (2) at least one of the threads writes to the
variable
Both the addition code and the list code shown previously have race conditions
10
General Form of Atomic Operation (Removing Race Conditions)
•
Called a conditional atomic action
– Atomically do (all of) the following: • Evaluate B
• Wait until B is true
• Execute S (an arbitrary statement list)
– If the “await (B)” is omitted, S is immediately executed, but still atomically
– <...> hides intermediate states and reduces number of histories
11
Example With Await
int x = 0 co
x =x +1 //
<(await x == 1) x = x + 2> oc
print x
This program will always output 3. (It also serializes execution.)
12
Example with Atomic Operations
int x = y = 0, z co
What are the possible final values of x, y, and z? How many histories are there?
13
Example with Atomic Operations
int x = y = 0, z co
Vars x and y must be 1 and 2; z can be -1 or 3 Number of histories is 6
General formula: (n*m)! / (m!n), where n and
m are number of threads and atomic actions
14
Same Example, Removing Explicit Atomicity
int x = y = 0, z co
x = 1; z = x+y //
y = 2; z = x-y oc
What are the possible final values of x, y, and z?
15
Same Example, Removing Explicit Atomicity
int x = y = 0, z co
x = 1; z = x+y //
y = 2; z = x-y oc
As before, x and y must be 1 and 2, but while z can still be -1 or 3 (as before), it can now also be -2 or 1
Note that enumerating all histories here is impractical Via previous formula: (8!) / (4!2) == 70 histories
16
Scheduling policies for atomic actions
• Unconditional fairness
– Every unconditional atomic action eventually executes
• Round robin scheduling satisfies this
• Weak fairness: UC + conditional atomic actions execute if true and seen by the thread
• Strong fairness: UC + conditional atomic actions execute if true infinitely often
17
Scheduling policies: WF vs. SF
continue := true; try := false co
while (continue) {try := true ; try := false} //
• With weak fairness, program may never terminate; with strong fairness, it will terminate
– Practical schedulers, however, are not strongly1f8air
Finding the max of an array in parallel
Sequential version
int max = MINVAL int a[n]
for i = 0 to n-1 {
if (a[i] > max) max = a[i]
}
19
Finding the max of an array in parallel
Incorrect parallel version
int max = MINVAL int a[n]
co i = 0 to n-1 {
if (a[i] > max) max = a[i]
}
20
Finding the max of an array in parallel
Correct but slow parallel version
int max = MINVAL int a[n]
co i = 0 to n-1 {
}
21
Finding the max of an array in parallel
Another incorrect parallel version
int max = MINVAL int a[n]
co i = 0 to n-1 {
if (a[i] > max)
}
22
Finding the max of an array in parallel
Correct, efficient (but complicated) parallel version int max = MINVAL
int a[n]
co i = 0 to n-1 {
if (a[i] > max) { Why do this?
max = a[i]> }
}
23