CS 22
Clab 25: 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.
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.
<![CDATA[
(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
<![CDATA[
(after2)
]]>
Approximately 2 seconds pass and we get our output. Now try:
<![CDATA[
(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 clicking on in mzscheme: threads in
"Threads" Don't worry about custodians and error handlers. For now
think of a thunk as a parameterless procedure.
Before you try the following, predict what will happen.
<![CDATA[
(begin
(thread after7)
(thread after2)
'done)
]]>
Now read about threads again and figure out why you got what you
got. 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
<![CDATA[(parallel-execute <p1> <p2> ... <pk>) ]]>by the following
construction in
drscheme:
<![CDATA[
(begin
(thread <p1>)
(thread <p2>)
:
(thread <pk>)
)
]]>
Now try the following in the interaction window.
<![CDATA[
> (define x 10)
> (begin
(thread (lambda() (set! x (* x x))))
(thread (lambda() (set! x (+ x 1))))
)
#<thread>
> x
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
<![CDATA[
(define chgx
(let
((x 10))
(begin
(thread (lambda() (begin
(sleep 0.001)
(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:
<![CDATA[
> 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:
<![CDATA[
> 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
<![CDATA[
(thread (lambda() (set! x (* x x))))
(thread (lambda() (set! x (+ x 1))))
]]>
Define the following.
<![CDATA[
(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:
<![CDATA[
> (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.
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.
Read about semaphores (especially make-semaphore, semaphore-wait,
and semaphore-post) in drscheme help. Read about serializers on
page 305 of sicp. We can use semaphores to make serializers. Here is
how:
<![CDATA[
(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:
<![CDATA[
(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:
<![CDATA[
(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.
Ask any questions you may have.
<![CDATA[
]]>