MPhil course in Multicore Programming - Exercise Sheet 2

      Version of Mon Jan 12 17:36:00 GMT 2011

Due: 3rd February (revised date - two weeks after the start of term).
Please hand to student admin, with a coversheet.

1. Which of the following programs are data race free? Justify your
answer by either showing a 'racy' execution or by giving a reason why
there cannot be a data race.

 a. Thread 1: lock m; *x = 1; unlock m; *y = 1 
    Thread 2: lock m; r = *x; unlock m; if (r = 1) then print *y

 b. Thread 1: *y = 1; lock m; *x = 1; unlock m;
    Thread 2: lock m; r = *x; unlock m; if (r = 1) then print *y

 c. Thread 1: *y = 1; lock m; *x = 1; unlock m;
    Thread 2: lock m; r = *x; unlock m; if (*x = 1) then print *y

where m is a monitor, x and y shared-memory locations and r is a local
variable. Assume that all memory locations are zero-initialised.

2. Let us assume that our language has the DRF principle as its memory
model. Which of the following programs can output 42? Why?

 a. Thread 1: lock m; *x = 1; unlock m
    Thread 2: lock m; *x = 2; unlock m
    Thread 3: lock m; if (*x = *x) then print 42; unlock m

 b. Thread 1: lock m1; *x = 1; unlock m1
    Thread 2: lock m2; *x = 2; unlock m2
    Thread 3: lock m1; lock m2; 
              if (*x = *x) then print 42; 
              unlock m2; unlock m1

 c. Thread 1: lock m1; *x = 1; unlock m1
    Thread 2: lock m2; r = *x; unlock m2;
              if r = 1 then print 1

where m, m1, m2 are monitors, x is a shared-memory location and r is a
local variable. Assume that all memory locations are zero-initialised.

3. Which of the following program transformations are correct under
sequential consistency in any context? For the incorrect ones, give a
context and an execution where the transformation introduces a new
behaviour. For the correct ones argue how the original program could
simulate the transformed one (without going into the details of the
simulation relation).

 a. r1 = *x; r2 = *y    =>   r2 = *y; r1 = *x 

 b. *x = r1; r2 = *y    =>   r2 = *y; *x = r1 

 c. r1 = *x; *x = r1    =>   r1 = *x


 (r1 and r2 are local variables, x and y are shared-memory locations)

4. List all well-behaved executions (in the sense of the JMM) of the
following programs.

 a. Thread 1: lock m1; x = 1; unlock m1
    Thread 2: int r1, r2; r1 = x; lock m1; r2 = x; unlock m1

 b. Thread 1: x = 1; v = 1;
    Thread 2: int r = 0; if (v == 1) then r = x

Here, m1 is a monitor, x is a non-volatile location, v is a volatile
location, r1, r2 and r are local variables. As opposed to exercises
1-3, we use a more Java-like semantics here: assignments to/from
shared-variables are writes/reads, so there is no need for the *
operator. Also note that in Java, volatile variable accesses are
synchronisation - a volatile write is a release, a volatile read is an
acquire. Assume that all memory locations are zero-initialised and
that the initialisation happens-before all other actions.

Optional: A. Which of the program transformations from exercise (3)
above are correct under the TSO memory model? Why?