CS 563 Concurrent Programming
Lecture 10: Synchronization, Atomic Actions, and Await Statements
Research Project Timeline
Copyright By PowCoder代写 加微信 powcoder
3/1: Reading list 1 due
3/22: Reading list 2 due
3/23: Midterm
3/30-4/20: Research paper presentations (2 students/lecture time) 4/5: Research project proposal due
4/22-4/29: Research project presentations (4 students/lecture time) 5/8: Research project due (paper and source code)
P1: x=y+z; P2: y=1; z = 2;
What are the final values of x, y, and z?
Answer depends on execution order and what is atomic
State: values of variables at a point in time Atomic action: indivisible state change
hardware: load, store, add, …
software: critical sections (later…)
History: a trace of ONE execution; an interleaving of atomic actions
Property: an attribute of ALL histories of a program, e.g., correctness
How many histories are there in a program with n processes and m atomic actions per process?
(n m)! / (m!)n
If n = 2 and m=4…
Synchronization
Synchronization
restricts the number of histories
Example: given array a[1:n] of positive integers
find the maximum value m by examining all elements in parallel
Finding Max of Array
Goal — expressed as a predicate
(∀ j:1<=j<=n:m>=a[j])∧ (∃ j:1<=j<=n:m=a[j])
Sequential program
for [i = 0 to n-1] {
if a[i] > m
Concurrent Program
Program outline
co [i = 0 to n-1] {
No synchronization (hence no constraints)
if a[i] > m {
What is true before and after this statement? What is wrong with this program?
interference
What’s the most that we can say?
m is SOME a[i]
Make it a single atomic action
〈 if(a[i]>m){ m = a[i]
The program is now correct, but…
Use smaller atomic actions
if (a[i] > m) {
〈 m=a[i] 〉 }
Combine 2 and 3: Double checking
if (a[i] > m) {
〈 if(a[i]>m){
m = a[i] }〉
Points to Remember
Synchronization is needed when we don’t have independence Angle brackets specify atomic actions
Double-checking technique — especially when it is possible that the first check is false
Synchronization
Prevents undesirable interleavings by:
Combining fine-grained atomic actions into coarse-grained atomic actions
Mutual exclusion
Delaying process execution until some predicate is satisfied
Condition synchronization
Atomic Actions
Fine grained — reads and writes of simple variables (loads/stores)
Coarse grained — programmed using <...> or real code (critical section)
Example: Fine-grained Atomicity
int y = 0, z = 0; co x = y + z;
// y = 1; z = 2; co;
What is the final value of x
How to achieve expression atomicity?
co statement: a simple way to represent concurrency
Definitions
A critical reference in an expression is a reference to a variable that is changed by other processes
An assignment x=e satisfies the At-Most-Once Property if one of the following is true:
e contains at most one critical reference and x is not referenced by another process
e contains no critical references, in which case x may be read by other processes
Appearance of Atomicity
If an assignment meets the requirements of the At-Most-Once property
execution of the assignment statement will appear to be atomic
int x = 0, y = 0;
co x = x + 1; // y = y + 1; oc;
int x = 0, y = 0;
co x = y + 1; // y = y + 1; oc;
int x = 0, y = 0;
co x = y + 1; // y = x + 1; oc;
int y = 0, z = 0; co x = y + z;
// y = 1; z = 2; co;
Coarse-grained may be required when At-Most-Once Property is not held
Need mechanism for constructing coarse-grained atomic actions
Sequence of fine-grained atomic actions Appearance
Specifying Atomic Actions
execute statement list S indivisibly (mutual exclusion)
< await(B); >
wait for B to be true (conditional synchronization)
< await(B) S; >
wait for B to be true, then execute S ALL AS A SINGLE ATOMIC ACTION
Example of use of await
〈 s=s+1; 〉
〈 await (s>0) s = s-1; 〉
At-Most-Once Property
if either:
S is a single assignment and meets At-Most-Once Property requirement, OR
S is implemented by a single indivisible machine instruction
if B meets At-Most-Once Property requirement (i.e., contains only one critical reference)
Producer/Consumer Synchronization
copy a[n] in Producer to b[n] in Consumer using a single shared buffer
How? Use synchronization to alternate access to the buffer
int buf, p = 0, c = 0;
process Producer {
while (p < n) {
〈 await (p == c); 〉
buf = a[p];
process Consumer {
while (c < n) {
〈 await(p>c); 〉
b[c] = buf;
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com