CS 22

Clab 26: More Concurrency

Today we will continue our discussion about concurrency. If there is time we'll look at a deque implementation.

Last clab, we defined the following.

(define chgx (lambda (bef-mul1 bef-mul2 bef-mul3 bef-plus1 bef-plus2) (let ((x 10)) (begin (thread (lambda() (begin (sleep bef-mul1) (let ((y1 x)) (sleep bef-mul2) (let ((y2 x)) (sleep bef-mul3) (set! x (* y1 y2))))))) (thread (lambda() (begin (sleep bef-plus1) (let ((z x)) (sleep bef-plus2) (set! x (+ z 1)))))) (sleep (+ 1 bef-mul1 bef-mul2 bef-mul3 bef-plus1 bef-plus2)) x)))) Following SICP, think of P1 as the process: (lambda () (set! x (* x x))) and P2 as the process: (lambda () (set! x (+ x 1))) chgx runs the processes P1 and P2 discussed on bottom of page 304 concurrently. However chgx inserts parameterized delays affecting when these processes access the value of x and when they change the value of x. Using only parameters of 0, 0.5, and 1, you can make chgx return each of the values 101, 121, 110, 11, 100 illustrated on the top of page 305.

You selected parameters to get each of the 5 values:101, 121, 110, 11, 100. and wrote down parameter values that will get you each of the values.

The fact that all these values could occur depending on the order in which parts of P1 and P2 are interleaved illustrates how important it is to be able to control access to critical values when concurrency is possible. An assignment like x = x + y; in C is not an indivisible operation. On many machines this would involve a fetch of the value of x from the RAM memory to a CPU register, a fetch of the value y from memory to a CPU register, adding those registers and storing the result in a CPU register, sending the value obtained from the CPU register holding it to memory location x. The execution of your program could be interrupted after any of these. If your program is not part of a concurrent system, no other procedures should be able to access your variables. A time-sharing operating system can save the state of your computation and give it back when your code is allowed to execute again. If your code is part of a concurrent system, all the problems we are illustrating could happen if you are not careful.

To be careful, one must control access to certain variables during critical sections of their code. Consider several airline agents in different cities reserving the same seat on a flight. A number of mechanisms have been developed in different programming languages to achieve this goal.

In drscheme help, read about semaphores in mzscheme semaphores in "Semaphores". Pay special attention to make-semaphore, semaphore-wait, and semaphore-post. The sentence: "MzScheme's semaphores have the usual single-threaded access for reliable synchronization." means that effectively these operations are uninterruptable and indivisible.

Now read about serializers on page 305 of sicp. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-23.html#%_sec_3.4.1
We can use semaphores to make serializers. Here is how:

(define (make-serializer) (let ((mutex (make-semaphore 1))) (lambda (p) (define (serialized-p . args) (semaphore-wait mutex) (let ((val (apply p args))) (semaphore-post mutex) val)) serialized-p))) Put the definition of make-serializer in your definition window and execute it. Then use a serializer in the interaction window as below: (define x 10) (define s (make-serializer)) (begin (thread (s (lambda () (set! x (* x x))))) (thread (s (lambda () (set! x (+ 1 x))))) 'done) I'll say a few words about what s is and how it protects P1 and P2. To check this out further, define and execute: (define chgx-seri (lambda (bef-mul1 bef-mul2 bef-mul3 bef-plus1 bef-plus2) (let ((x 10) (s (make-serializer))) (begin (thread (lambda() (begin (sleep bef-mul1) ((s (lambda () (let ((y1 x)) (sleep bef-mul2) (let ((y2 x)) (sleep bef-mul3) (set! x (* y1 y2)))))))))) (thread (lambda() (begin (sleep bef-plus1) ((s (lambda () (let ((z x)) (sleep bef-plus2) (set! x (+ z 1))))))))) (sleep (+ 1 bef-mul1 bef-mul2 bef-mul3 bef-plus1 bef-plus2)) x)))) chgx-seri is a protected version of the parallel execution of P1 and P2. Whichever one gets the semaphore first prevents the other one from executing until it (the one with the semaphore) is finished. Don't trust me on this. Compare the execution of chgx-seri and chgx on the 5 parameter combinations you wrote down earlier. chgx should give you 5 different values. chgx-seri should give you only two different values. You should be able to explain why.

Serializers solve many problems but introduce a whole new set of problems. Deadlock and starvation are among them. We do not have time in this course to investigate starvation. Here is some of what SICP says about deadlock:

Deadlock Now that we have seen how to implement serializers, we can see that account exchanging still has a problem, even with the serialized-exchange procedure above. Imagine that Peter attempts to exchange a1 with a2 while Paul concurrently attempts to exchange a2 with a1. Suppose that Peter's process reaches the point where it has entered a serialized procedure protecting a1 and, just after that, Paul's process enters a serialized procedure protecting a2. Now Peter cannot proceed (to enter a serialized procedure protecting a2) until Paul exits the serialized procedure protecting a2. Similarly, Paul cannot proceed until Peter exits the serialized procedure protecting a1. Each process is stalled forever, waiting for the other. This situation is called a deadlock. Deadlock is always a danger in systems that provide concurrent access to multiple shared resources.
Ask any questions you may have.