Concurrency: How to Find Answers

So you understand serializers. You understand mutexes. You even understand test-and-set!. But how about when your concurrency has problems?

Remember, all problems are caused by mutations (stores into memory). So...

1. Write down all Reads and Stores for each "thread" (each thing being executed in parallel).
2. Write down all possible ways to order the Stores.
3. Now write down all possible ways to insert the Reads. Remember that Reads from one thread usually have to happen before some later Store.

Confusing? Try the problems below.

(define x 3)

(parallel-execute (lambda () (set! x (+ x x)))
                  (lambda () (set! x (* x x))) )

• What are the possible correct answers?

  (show answer)

  36 and 18. Remember that "correct" means "could happen if run serially (one after another), in any order".

  (hide answer)

• What are the other possible answers?

  (show answer)

  6, 9, and 12. Let's take these separately.

  The way to solve a problem like this is to write down all accesses to shared variables, and see what happens for every interleaving. Call the first procedure A and the second one B, and let's see what happens:

  A reads its first x (call it a1) and gets 3 A reads its second x (call it a2) and gets 3 A stores a1 + a2 = 6 into x B reads its first x (call it b1) and gets 6 B reads its second x (call it b2) and gets 6 B stores b1 * b2 = 36 into x	This is a correct answer, with the value 36.
  B reads its first x (call it b1) and gets 3 B reads its second x (call it b2) and gets 3 B stores b1 * b2 = 9into x A reads its first x (call it a1) and gets 9 A reads its second x (call it a2) and gets 9 A stores a1 + a2 = 18 into x	This is a correct answer, with the value 18.
  B reads its first x (call it b1) and gets 3 B reads its second x (call it b2) and gets 3 A reads its first x (call it a1) and gets 3 B stores b1 * b2 = 9 into x A reads its second x (call it a2) and gets 9 A stores a1 + a2 = 12 into x	This is an incorrect answer, with the value 12.
  B reads its first x (call it b1) and gets 3 B reads its second x (call it b2) and gets 3 A reads its first x (call it a1) and gets 3 A reads its second x (call it a2) and gets 3 B stores b1 * b2 = 9 into x A stores a1 + a2 = 6 into x	This is an incorrect answer, with the value 6.
  B reads its first x (call it b1) and gets 3 B reads its second x (call it b2) and gets 3 A reads its first x (call it a1) and gets 3 A reads its second x (call it a2) and gets 3 A stores a1 + a2 = 6 into x B stores b1 * b2 = 9 into x	This is an incorrect answer, with the value 9.
  A reads its first x (call it a1) and gets 3 A reads its second x (call it a2) and gets 3 B reads its first x (call it b1) and gets 3 A stores a1 + a2 = 6 into x B reads its second x (call it b2) and gets 6 B stores b1 * b2 = 18 into x	This is an incorrect calculation, but we still get the correct answer 18! Sometimes this can happen, like when you mistakenly write a negative in one place and then cancel it later.

  How do we know these are all of the possible answers? Notice that it doesn't matter the order of the reads performed by two different processes, only where they are with respect to the writes. So, beyond the two correct answers, there are four ways to screw this up: put A's write between B's two reads, or between B's reads and its write, or put B's write between A's two reads, or between A's reads and its write.

  (hide answer)

(define x 3)
(define y 0)

(parallel-execute (lambda () (set! x (+ x 2)))
                  (lambda () (set! x (* x x)))
                  (lambda () (set! y x)) )

• What are the possible correct answers?

  (show answer)

  (x, y) = (25, 3), (25, 5), (25, 25), (11, 3), (11, 9), (11, 11). Remember that "correct" means "could happen if run serially (one after another), in any order".

  The trick here is to see that only the first two procedures modify x, and that the procedure that modifies y could come in before, between, or after them. Make sure you can see how all of these answers can come about!

  (hide answer)

• What are the other possible answers? (Already you know this is going to be a little painful; try to do it methodically!)

  (show answer)

  6, 9, and 12. Let's take these separately.

  What's important to notice is that setting y doesn't affect the value of x at all! Call the first procedure A, the second one B, and the third one C, and...

  (There are fifteen possibilities here, all distinct! If you haven't come up with all of them, go back and try again. Then try to match yours up with these.)

  A reads its x (call it a) and gets 3 A stores a + 2 = 5 into x B reads its first x (call it b1) and gets 5 B reads its second x (call it b2) and gets 5 B stores b1 * b2 = 25 into x C reads its x and stores it into y	This is a correct answer, with the value (25, 25).
  A reads its x (call it a) and gets 3 A stores a + 2 = 5 into x C reads its x and stores it into y B reads its first x (call it b1) and gets 5 B reads its second x (call it b2) and gets 5 B stores b1 * b2 = 25 into x	This is a correct answer, with the value (25, 5).
  C reads its x and stores it into y A reads its x (call it a) and gets 3 A stores a + 2 = 5 into x B reads its first x (call it b1) and gets 5 B reads its second x (call it b2) and gets 5 B stores b1 * b2 = 25 into x	This is a correct answer, with the value (25, 3).
  B reads its first x (call it b1) and gets 3 B reads its second x (call it b2) and gets 3 B stores b1 * b2 = 9 into x A reads its x (call it a) and gets 9 A stores a + 2 = 11 into x C reads its x and stores it into y	This is a correct answer, with the value (11, 11).
  B reads its first x (call it b1) and gets 3 B reads its second x (call it b2) and gets 3 B stores b1 * b2 = 9 into x C reads its x and stores it into y A reads its x (call it a) and gets 9 A stores a + 2 = 11 into x	This is a correct answer, with the value (11, 9).
  C reads its x and stores it into y B reads its first x (call it b1) and gets 3 B reads its second x (call it b2) and gets 3 B stores b1 * b2 = 9 into x A reads its x (call it a) and gets 9 A stores a + 2 = 11 into x	This is a correct answer, with the value (11, 3).
  C reads its x and stores it into y B reads its first x (call it b1) and gets 3 B reads its second x (call it b2) and gets 3 A reads its x (call it a) and gets 3 B stores b1 * b2 = 9 into x A stores a + 2 = 5 into x	This is an incorrect answer, with the value (5, 3).
  B reads its first x (call it b1)and gets 3 B reads its second x (call it b2) and gets 3 A reads its x (call it a) and gets 3 B stores b1 * b2 = 9 into x C reads its x and stores it into y A stores a + 2 = 5 into x	This is an incorrect answer, with the value (5, 9).
  B reads its first x (call it b1) and gets 3 B reads its second x (call it b2) and gets 3 A reads its x (call it a) and gets 3 B stores b1 * b2 = 9 into x A stores a + 2 = 5 into x C reads its x and stores it into y	This is an incorrect answer, with the value (5, 5).
  C reads its x and stores it into y B reads its first x (call it b1) and gets 3 B reads its second x (call it b2)and gets 3 A reads its x (call it a) and gets 3 A stores a + 2 = 5 into x B stores b1 * b2 = 9 into x	This is an incorrect answer, with the value (9, 3).
  B reads its first x (call it b1) and gets 3 B reads its second x (call it b2) and gets 3 A reads its x (call it a) and gets 3 A stores a + 2 = 5 into x C reads its x and stores it into y B stores b1 * b2 = 9 into x	This is an incorrect answer, with the value (9, 5).
  B reads its first x (call it b1) and gets 3 B reads its second x (call it b2) and gets 3 A reads its x (call it a) and gets 3 A stores a + 2 = 5 into x B stores b1 * b2 = 9 into x C reads its x and stores it into y	This is an incorrect answer, with the value (9, 9).
  C reads its x and stores it into y A reads its x (call it a) and gets 3 B reads its first x (call it b1) and gets 3 A stores a + 2 = 5 into x B reads its second x (call it b2) and gets 5 B stores b1 * b2 = 15 into x	This is an incorrect answer, with the value (15, 3).
  A reads its x (call it a) and gets 3 B reads its first x (call it b1) and gets 3 A stores a + 2 = 5 into x C reads its x and stores it into y B reads its second x (call it b2) and gets 5 B stores b1 * b2 = 9 into x	This is an incorrect answer, with the value (15, 5).
  A reads its x (call it a) and gets 3 B reads its first x (call it b1) and gets 3 A stores a + 2 = 5 into x B reads its second x (call it b2) and gets 5 B stores b1 * b2 = 15 into x C reads its x and stores it into y	This is an incorrect answer, with the value (15, 15).

  We followed the same procedure as before: find out where the writes can go to mess up the reads. B's write can go between A's read and A's write, or A's write can go between B's two reads, or A's write can go between B's reads and B's write. For each of these 3 possibilities, C's read can come before both writes, between the two writes, or after both writes.

  I don't want to promise I haven't made a mistake, however; concurrency is hard! Bonus candy to anyone who finds an incorrect but possible value that I missed. (But I'm pretty sure this is correct.)

  (hide answer)

Back to Jordy's home page | Course home page