<< Previous exercise (3.38) | Index | Next exercise (3.40) >>

I believe the above is wrong and

110: P2 changes x from 10 to 11 between the two times that P1 accesses the value of x during the evaluation of (* x x).

is indeed possible. The serializer doesn't protect P1 at all.

@leafac I think adams is right, as "(s (lambda () (* x x))))" protected the (* x x) from interleaved, P2 can not changes x between the two times that P1 accessed the x.

None of the above is correct!! Actually the right solution is 121, 100, 101 **AND** 11. *adams* has the right reasons for the first three. However you can also get 11: Lets label the 3 processes involved: S1: calculation of x^2, S2: setting x to calculated value of x^2; R1: acquisition of value of x and setting it to x+1. Now here is what can happen: S1: acquires the mutex and calculates the value of x^2 i.e. 100, now it releases the mutex. At this point R1 acquires the mutex and calculates a value of 11 BUT before it can set the value to 11, S2 occurs (nothing barring it from occuring concurrently with R1) and therefore R1 gets to set the final value of x, i.e. 11. You can convince yourselves by running the following simulation:

(define (run-many-times in-test num) (define (run-test numtimes output) (let ((m (in-test))) (cond ((= 0 numtimes) output) ((memq m output) (run-test (- numtimes 1) output)) (true (run-test (- numtimes 1) (cons m output)))))) (run-test num '())) (define (test-2) (define x 10) (define s (make-serializer)) (parallel-execute (lambda () (set! x ((s (lambda () (* x x)))))) (s (lambda () (set! x (+ x 1))))) x) (display (run-many-times test-2 10000)) ;;Output will be (11 100 101 121) in some order

I agree with karthikk. Here's the event sequence that produces 11:

- P1) access x: 10
- P1) new value: 10 * 10 = 100
- P2) access x: 10
- P2) new value: 10 + 1 = 11
**P1) set! x to 100**- P2) set! x to 11

The key idea here is that "P1) set! x to 100" can be interleaved between P2 events.

@adams is right, you can't get 11. People say you can get 11 because you access x in P2, compute 11, and then P1 sets x to 100 before P2 can. THIS IS WRONG. P2, after computing x + 1, CANNOT BE INTERRUPTED BY P1. This is the entire point of serialization, or there would be no point. So it sets x to 11, without P1 setting x, and then x is set to 100. 11 IS NOT A POSSIBLE VALUE.

@jphilliq says that P2 cannot be interrupted by P1. This is wrong. Serialization is cooperative. Just because all of P2 is serialized does not protect it from being interleaved with a non-serialized process. At first blush it appears that there are 3 things to consider as being interleavable:

- P1a Access and compute (* x x)
- P1b Set x to computed (* x x)
- P2 Access and compute and set x to (+ x 1)

However, since P1b is not serialized, it can occur at any point along P2. The serialization of P2 has no effect on P1b. P2 is made up of 2 atomic operations:

- P2a read and calulate (+ x 1)
- P2b set x to computed (+ x 1)

P1a cannot interleave between P2a and P2b, but P1b can. That yields the following possibilities:

- P1a P1b P2a P2b --> (* 10 10) 100->x (+ 100 1) 101->x : 101
- P2a P2b P1a P1b --> (+ 10 1) 11->x (* 101 101) 121->x : 121
- P1a P2a P1b P2b --> (* 10 10) (+ 10 1) 100->x 11->x : 11
- P1a P2a P2b P1b --> (* 10 10) (+ 10 1) 11->x 100->x : 100

@karthikk and @Hoonji are correct.

Assuming that what serializer does in essence is making sure that two (or more) functions having the same serializer will run sequentially, then the execution of P1 (not serialized) and P2 (serialized) can still be interleaved and possible results are the same as if P2 was not serialized at all.

Then possible values are the same as for running in parallel P1 and P2 without any serialization: 101, 121, 110, 11, 100.

@karthikk is right.

I couldn't get their simulation code to run, but drawing out the possibilities convinced me:

https://i.imgur.com/EmI4FGN.png

The basic confusion here is that serializer only prevents *other serialized code* from running.

Counter-intuitively, this means that non-serialized code can run while the serialized code is running, and vice-versa.

Here's how x resolves to 11 (cf. bottom image in 2nd column):

1. The serializer prevents the blue proc from doing anything **in the middle of the two upward red arrows** representing `(lambda () (* x x))`.

2. The blue proc grabs x **after** the serialized portion of the red proc finishes and **before** the non-serialized part of red proc starts.

3. **The non-serialized part of the red proc sets x to 100 while the blue proc is running (crucial!).**

4. Blue proc finishes running and over-writes x to 11.

adams