CS 37

Clab 23: Concurrency

Today we want to talk about concurrency. Deep down, most modern computers utilize some real concurrency. For example starting a disk read and then performing some other operations while the read is taking place. Pipelining is also a form of true concurrency. Our server allspice has two processors so it also exercises real concurrency. Some of the lab machines have two dual-cores which mean they are capable of well over 4 operations taking place simultaneously. In addition, time-sharing operating systems simulate concurrency even on single processor systems. In drscheme we will be studying concurrency by means of simulated concurrency achieved through threads. First let's look at a couple of simple definitions. If it is not already there, make your language level: Pretty Big.

(define after7 (lambda () (sleep 7) (display "7 secs gone.") (newline))) (define after2 (lambda () (sleep 2) (display "2 secs gone.") (newline))) after7 waits 7 seconds and then prints 7 seconds gone. after2 does the same for 2 seconds. Put these in your definitions window, save and execute. Now run (after2) As you run these, count one, one-thousand, two, one-thousand. etc. Approximately 2 seconds pass and we get our output. Now try: (begin (after7) (after2) 'done) begin sets up a sequence of operations. after7 is executed and when it returns after2 is executed and when after2 is done, the begin returns done.

Now read about threads in help by choosing the PLT mzscheme Language Manual. Scroll down to chapter 7: Threads and click on that Chapter 7 heading. Read up to 7.1 in "Threads". Don't worry about custodians and error handlers. For now think of a thunk as a parameterless procedure. Leave that help window open somewhere so we can go back to it. Before you try the following, predict what will happen.

(begin (thread after7) (thread after2) 'done) Now read about threads again and figure out why you got what you got.

Now do:

(begin (display (thread after7)) (display (thread after2)) 'done) Note that the begin behaves: (thread after7) is invoked, then (thread after2) is invoked then 'done is returned. The begin process is finished. However it invoked two threads that are running (simultaneously - in drscheme's simulation). Even though (thread after7) started before (thread after2), (thread after2) finishes first after about 2 seconds. (thread after7) finishes after an additional 5 seconds. I'll say a few words about this. SICP discusses a parallel-execute procedure on page 304. drscheme does not have a parallel-execute procedure. For our purposes, we can obtain the same result as sicp's (parallel-execute <p1> <p2> ... <pk>) by the following construction in drscheme: (begin (thread <p1>) (thread <p2>) : (thread <pk>) ) Now try the following in the interaction window. > (define x 10) > (begin (thread (lambda() (set! x (* x x)))) (thread (lambda() (set! x (+ x 1)))) ) #<thread> > x 121 If drscheme really ran these two threads on parallel processors, we might get different answers if we ran the same sequence several times. There is a chance that one of you may get a different answer than 121.

We would like to try this several times with different timings for accessing and setting x. Doing all the work in the interaction window with the global variable x would involve resetting x each time and typing too much. So ... Review pp. 297-304. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-23.html#%_sec_3.4.1
Read especially carefully the section headed Serializers in Scheme on the bottom of page 304 and top of p. 305, then try defining

(define chgx (let ((x 10)) (begin (thread (lambda() (begin (sleep 0.05) (set! x (* x x))))) (thread (lambda() (begin (sleep 0.001) (set! x (+ x 1))))) (sleep 1.5) x))) When I tried a few executions, I got: > chgx 121 > chgx 121 > chgx 121 > chgx 121 > chgx 121 You might get 101. It is theoretically possible that you will get 121 sometimes and 101 other times. When I change the first sleep amount, I can get: > chgx 101 > chgx 101 > chgx 101 > chgx 101 Fool around with the sleep amount to get both 101 and 121. It is hard to get drscheme to behave truly non-deterministically. So let's define a function that will simulate different timings for the two parallel functions (thread (lambda() (set! x (* x x)))) (thread (lambda() (set! x (+ x 1)))) Define 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)))) 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. Here is 101: > (chgx 0 0 0 1 0) 101 Now you select parameters to get each of the 5 values:101, 121, 110, 11, 100. On a piece of paper, write down parameter values that will get you each of the values. Make sure you understand why. Bring your numbers with you to our next clab.

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.

Ask any questions you may have.