forked from twcamper/sicp-kindle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-23.html
1267 lines (1010 loc) · 65 KB
/
book-Z-H-23.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http:https://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o,
(c) Dorai Sitaram, http:https://www.cs.rice.edu/~dorai/tex2page -->
<head>
<meta name="generator" content="HTML Tidy for Linux (vers 7 December 2008), see www.w3.org" />
<title>Structure and Interpretation of Computer Programs</title>
<link href="book-Z-C.css" title="default" rel="stylesheet" type="text/css" />
<meta name="robots" content="noindex,follow" />
</head>
<body>
<mbp:pagebreak />
<p><a name="%_sec_3.4"></a></p>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_3.4">3.4 Concurrency:
Time Is of the Essence</a></h2>
<p><a name="%_idx_3578"></a> We've seen the power of
computational objects with local state as tools for modeling.
Yet, as section <a href="book-Z-H-20.html#%_sec_3.1.3">3.1.3</a> warned, this power
extracts a price: the loss of referential transparency, giving
rise to a thicket of questions about sameness and change, and the
need to abandon the substitution model of evaluation in favor of
the more intricate environment model.</p>
<p><a name="%_idx_3580"></a>The central issue lurking beneath the
complexity of state, sameness, and change is that by introducing
assignment we are forced to admit <em>time</em> into our
computational models. Before we introduced assignment, all our
programs were timeless, in the sense that any expression that has
a value always has the same value. In contrast, recall the
example of modeling withdrawals from a bank account and returning
the resulting balance, introduced at the beginning of
section <a href="book-Z-H-20.html#%_sec_3.1.1">3.1.1</a>:</p>
<p><tt>(withdraw 25)<br />
<i>75</i><br />
(withdraw 25)<br />
<i>50</i><br /></tt></p>
<p>Here successive evaluations of the same expression yield
different values. This behavior arises from the fact that the
execution of assignment statements (in this case, assignments to
the variable <tt>balance</tt>) delineates <em>moments in
time</em> when values change. The result of evaluating an
expression depends not only on the expression itself, but also on
whether the evaluation occurs before or after these moments.
Building models in terms of computational objects with local
state forces us to confront time as an essential concept in
programming.</p>
<p>We can go further in structuring computational models to match
our perception of the physical world. Objects in the world do not
change one at a time in sequence. Rather we perceive them as
acting <em>concurrently</em> -- all at once. So it is often
natural to model systems as collections of computational
processes that execute concurrently. Just as we can make our
programs modular by organizing models in terms of objects with
separate local state, it is often appropriate to divide
computational models into parts that evolve separately and
concurrently. Even if the programs are to be executed on a
sequential computer, the practice of writing programs as if they
were to be executed concurrently forces the programmer to avoid
inessential timing constraints and thus makes programs more
modular.</p>
<p>In addition to making programs more modular, concurrent
computation can provide a speed advantage over sequential
computation. Sequential computers execute only one operation at a
time, so the amount of time it takes to perform a task is
proportional to the total number of operations performed.<a href="#footnote_Temp_405" name="call_footnote_Temp_405" id="call_footnote_Temp_405"><sup><small>34</small></sup></a>
However, if it is possible to decompose a problem into pieces
that are relatively independent and need to communicate only
rarely, it may be possible to allocate pieces to separate
computing processors, producing a speed advantage proportional to
the number of processors available.</p>
<p>Unfortunately, the complexities introduced by assignment
become even more problematic in the presence of concurrency. The
fact of concurrent execution, either because the world operates
in parallel or because our computers do, entails additional
complexity in our understanding of time.</p>
<p><a name="%_sec_3.4.1"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.4.1">3.4.1 The Nature
of Time in Concurrent Systems</a></h3>
<p><a name="%_idx_3584"></a> On the surface, time seems
straightforward. It is an ordering imposed on events.<a href="#footnote_Temp_406" name="call_footnote_Temp_406" id="call_footnote_Temp_406"><sup><small>35</small></sup></a> For any
events <em>A</em> and <em>B</em>, either <em>A</em> occurs before
<em>B</em>, <em>A</em> and <em>B</em> are simultaneous,
or <em>A</em> occurs after <em>B</em>. For instance, returning to
the bank account example, suppose that Peter withdraws $10 and
Paul withdraws $25 from a <a name="%_idx_3588"></a>joint account
that initially contains $100, leaving $65 in the account.
Depending on the order of the two withdrawals, the sequence of
balances in the account is either $100 <img src="book-Z-G-D-15.gif" border="0" /> $90 <img src="book-Z-G-D-15.gif" border="0" /> $65 or $100 <img src="book-Z-G-D-15.gif" border="0" />
$75 <img src="book-Z-G-D-15.gif" border="0" /> $65. In a computer
implementation of the banking system, this changing sequence of
balances could be modeled by successive assignments to a variable
<tt>balance</tt>.</p>
<p>In complex situations, however, such a view can be
problematic. Suppose that Peter and Paul, and other people
besides, are accessing the same bank account through a network of
banking machines distributed all over the world. The actual
sequence of balances in the account will depend critically on the
detailed timing of the accesses and the details of the
communication among the machines.</p>
<p><a name="%_idx_3590"></a>This indeterminacy in the order of
events can pose serious problems in the design of concurrent
systems. For instance, suppose that the withdrawals made by Peter
and Paul are implemented as two separate processes sharing a
common variable <tt>balance</tt>, each process specified by the
procedure given in section <a href="book-Z-H-20.html#%_sec_3.1.1">3.1.1</a>:</p>
<p><tt><a name="%_idx_3592"></a>(define (withdraw amount)<br />
(if (>= balance amount)<br />
(begin (set! balance (- balance amount))<br />
balance)<br />
"Insufficient funds"))<br />
</tt></p>
<p>If the two processes operate independently, then Peter might
test the balance and attempt to withdraw a legitimate amount.
However, Paul might withdraw some funds in between the time that
Peter checks the balance and the time Peter completes the
withdrawal, thus invalidating Peter's test.</p>
<p>Things can be worse still. Consider the expression</p>
<p>
<tt>(set! balance (- balance amount))<br /></tt></p>
<p>executed as part of each withdrawal process. This consists of
three steps: (1) accessing the value of the <tt>balance</tt>
variable; (2) computing the new balance; (3) setting
<tt>balance</tt> to this new value. If Peter and Paul's
withdrawals execute this statement concurrently, then the two
withdrawals might interleave the order in which they access
<tt>balance</tt> and set it to the new value.</p>
<p>The timing diagram in figure <a href="#%_fig_3.29">3.29</a> depicts an order of events where
<tt>balance</tt> starts at 100, Peter withdraws 10, Paul
withdraws 25, and yet the final value of <tt>balance</tt> is 75.
As shown in the diagram, the reason for this anomaly is that
Paul's assignment of 75 to <tt>balance</tt> is made under the
assumption that the value of <tt>balance</tt> to be decremented
is 100. That assumption, however, became invalid when Peter
changed <tt>balance</tt> to 90. This is a catastrophic failure
for the banking system, because the total amount of money in the
system is not conserved. Before the transactions, the total
amount of money was $100. Afterwards, Peter has $10, Paul has
$25, and the bank has $75.<a href="#footnote_Temp_407" name="call_footnote_Temp_407" id="call_footnote_Temp_407"><sup><small>36</small></sup></a></p>
<p><a name="%_idx_3596"></a><a name="%_idx_3598"></a>The general
phenomenon illustrated here is that several processes may share a
common state variable. What makes this complicated is that more
than one process may be trying to manipulate the shared state at
the same time. For the bank account example, during each
transaction, each customer should be able to act as if the other
customers did not exist. When a customer changes the balance in a
way that depends on the balance, he must be able to assume that,
just before the moment of change, the balance is still what he
thought it was.</p>
<p><a name="%_sec_Temp_408"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_408">Correct
behavior of concurrent programs</a></h4>
<p><a name="%_idx_3600"></a> The above example typifies the
subtle bugs that can creep into concurrent programs. The root of
this complexity lies in the assignments to variables that are
shared among the different processes. We already know that we
must be careful in writing programs that use <tt>set!</tt>,
because the results of a computation depend on the order in which
the assignments occur.<a href="#footnote_Temp_409" name="call_footnote_Temp_409" id="call_footnote_Temp_409"><sup><small>37</small></sup></a> With
concurrent processes we must be especially careful about
assignments, because we may not be able to control the order of
the assignments made by the different processes. If several such
changes might be made concurrently (as with two depositors
accessing a joint account) we need some way to ensure that our
system behaves correctly. For example, in the case of withdrawals
from a joint bank account, we must ensure that money is
conserved. To make concurrent programs behave correctly, we may
have to place some restrictions on concurrent execution.</p>
<p><a name="%_fig_3.29"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.29:</b> Timing diagram showing how
interleaving the order of events in two banking withdrawals
can lead to an incorrect final balance.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-31.gif" border="0" /></td>
</tr>
<tr>
<td><a name="%_idx_3602"></a></td>
</tr>
</table>
</div>
<p>One possible restriction on concurrency would stipulate that
no two operations that change any shared state variables can
occur at the same time. This is an extremely stringent
requirement. For distributed banking, it would require the system
designer to ensure that only one transaction could proceed at a
time. This would be both inefficient and overly conservative.
Figure <a href="#%_fig_3.30">3.30</a> shows Peter and Paul
sharing a bank account, where Paul has a private account as well.
The diagram illustrates two withdrawals from the shared account
(one by Peter and one by Paul) and a deposit to Paul's private
account.<a href="#footnote_Temp_410" name="call_footnote_Temp_410" id="call_footnote_Temp_410"><sup><small>38</small></sup></a> The two
withdrawals from the shared account must not be concurrent (since
both access and update the same account), and Paul's deposit and
withdrawal must not be concurrent (since both access and update
the amount in Paul's wallet). But there should be no problem
permitting Paul's deposit to his private account to proceed
concurrently with Peter's withdrawal from the shared account.</p>
<p><a name="%_fig_3.30"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.30:</b> Concurrent deposits and
withdrawals from a joint account in Bank1 and a private
account in Bank2.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-32.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>A less stringent restriction on concurrency would ensure that
a concurrent system produces the same result as if the processes
had run sequentially in some order. There are two important
aspects to this requirement. First, it does not require the
processes to actually run sequentially, but only to produce
results that are the same <em>as if</em> they had run
sequentially. For the example in figure <a href="#%_fig_3.30">3.30</a>, the designer of the bank account system
can safely allow Paul's deposit and Peter's withdrawal to happen
concurrently, because the net result will be the same as if the
two operations had happened sequentially. Second, there may be
more than one possible ``correct'' result produced by a
concurrent program, because we require only that the result be
the same as for <em>some</em> sequential order. For example,
suppose that Peter and Paul's joint account starts out with $100,
and Peter deposits $40 while Paul concurrently withdraws half the
money in the account. Then sequential execution could result in
the account balance being either $70 or $90 (see
exercise <a href="#%_thm_3.38">3.38</a>).<a href="#footnote_Temp_411" name="call_footnote_Temp_411" id="call_footnote_Temp_411"><sup><small>39</small></sup></a></p>
<p>There are still weaker requirements for correct execution of
concurrent programs. A program for simulating <a name="%_idx_3606"></a>diffusion (say, the flow of heat in an object)
might consist of a large number of processes, each one
representing a small volume of space, that update their values
concurrently. Each process repeatedly changes its value to the
average of its own value and its neighbors' values. This
algorithm converges to the right answer independent of the order
in which the operations are done; there is no need for any
restrictions on concurrent use of the shared values.</p>
<p><a name="%_thm_3.38"></a> <b>Exercise
3.38.</b> Suppose that Peter, Paul, and Mary share a
joint bank account that initially contains $100. Concurrently,
Peter deposits $10, Paul withdraws $20, and Mary withdraws half
the money in the account, by executing the following
commands:</p>
<table border="0">
<tr>
<td valign="top">Peter:</td>
<td valign="top"><tt>(set! balance (+ balance 10))</tt></td>
</tr>
<tr>
<td valign="top">Paul:</td>
<td valign="top"><tt>(set! balance (- balance 20))</tt></td>
</tr>
<tr>
<td valign="top">Mary:</td>
<td valign="top"><tt>(set! balance (- balance (/ balance
2)))</tt></td>
</tr>
</table>
<p>a. List all the different possible values for <tt>balance</tt>
after these three transactions have been completed, assuming that
the banking system forces the three processes to run sequentially
in some order.</p>
<p>b. What are some other values that could be produced if the
system allows the processes to be interleaved? Draw timing
diagrams like the one in figure <a href="#%_fig_3.29">3.29</a> to explain how these values can occur.</p>
<p><a name="%_sec_3.4.2"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.4.2">3.4.2 Mechanisms
for Controlling Concurrency</a></h3>
<p><a name="%_idx_3608"></a> We've seen that the difficulty in
dealing with concurrent processes is rooted in the need to
consider the interleaving of the order of events in the different
processes. For example, suppose we have two processes, one with
three ordered events (<em>a</em>,<em>b</em>,<em>c</em>) and one
with three ordered events (<em>x</em>,<em>y</em>,<em>z</em>). If
the two processes run concurrently, with no constraints on how
their execution is interleaved, then there are 20 different
possible orderings for the events that are consistent with the
individual orderings for the two processes:</p>
<div align="left"><img src="ch3-Z-G-33.gif" border="0" /></div>
<p>As programmers designing this system, we would have to
consider the effects of each of these 20 orderings and check that
each behavior is acceptable. Such an approach rapidly becomes
unwieldy as the numbers of processes and events increase.</p>
<p>A more practical approach to the design of concurrent systems
is to devise general mechanisms that allow us to constrain the
interleaving of concurrent processes so that we can be sure that
the program behavior is correct. Many mechanisms have been
developed for this purpose. In this section, we describe one of
them, the <em>serializer</em>.</p>
<p><a name="%_sec_Temp_413"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_413">Serializing
access to shared state</a></h4>
<p><a name="%_idx_3610"></a> Serialization implements the
following idea: Processes will execute concurrently, but there
will be certain collections of procedures that cannot be executed
concurrently. More precisely, serialization creates distinguished
sets of procedures such that only one execution of a procedure in
each serialized set is permitted to happen at a time. If some
procedure in the set is being executed, then a process that
attempts to execute any procedure in the set will be forced to
wait until the first execution has finished.</p>
<p>We can use serialization to control access to shared
variables. For example, if we want to update a shared variable
based on the previous value of that variable, we put the access
to the previous value of the variable and the assignment of the
new value to the variable in the same procedure. We then ensure
that no other procedure that assigns to the variable can run
concurrently with this procedure by serializing all of these
procedures with the same serializer. This guarantees that the
value of the variable cannot be changed between an access and the
corresponding assignment.</p>
<p><a name="%_sec_Temp_414"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_414">Serializers in
Scheme</a></h4>
<p>To make the above mechanism more concrete, suppose that we
have extended Scheme to include a procedure called <a name="%_idx_3612"></a><tt>parallel-execute</tt>:</p>
<p>
<tt>(parallel-execute <<em>p<sub>1</sub></em>> <<em>p<sub>2</sub></em>> </tt>...
<<em>p<sub><em>k</em></sub></em>>)<br /></p>
<p>Each <<em>p</em>> must be a procedure of no arguments.
<tt>Parallel-execute</tt> creates a separate process for each
<<em>p</em>>, which applies <<em>p</em>> (to no
arguments). These processes all run concurrently.<a href="#footnote_Temp_415" name="call_footnote_Temp_415" id="call_footnote_Temp_415"><sup><small>40</small></sup></a></p>
<p>As an example of how this is used, consider</p>
<p><tt>(define x 10)<br />
<br />
(parallel-execute (lambda () (set! x (* x x)))<br />
(lambda () (set! x (+ x 1))))<br />
</tt></p>
<p>This creates two concurrent processes --
<em>P</em><sub>1</sub>, which sets <tt>x</tt> to <tt>x</tt> times
<tt>x</tt>, and <em>P</em><sub>2</sub>, which increments
<tt>x</tt>. After execution is complete, <tt>x</tt> will be left
with one of five possible values, depending on the interleaving
of the events of <em>P</em><sub>1</sub> and
<em>P</em><sub>2</sub>:</p>
<table border="0">
<tr>
<td valign="top">101:</td>
<td valign="top"><em>P</em><sub>1</sub> sets <tt>x</tt> to
100 and then <em>P</em><sub>2</sub> increments <tt>x</tt> to
101.</td>
</tr>
<tr>
<td valign="top">121:</td>
<td valign="top"><em>P</em><sub>2</sub> increments <tt>x</tt>
to 11 and then <em>P</em><sub>1</sub> sets <tt>x</tt> to
<tt>x</tt> times <tt>x</tt>.</td>
</tr>
<tr>
<td valign="top">110:</td>
<td valign="top"><em>P</em><sub>2</sub> changes <tt>x</tt>
from 10 to 11 between the two times that
<em>P</em><sub>1</sub> accesses the value of <tt>x</tt>
during the evaluation of <tt>(* x x)</tt>.</td>
</tr>
<tr>
<td valign="top">11:</td>
<td valign="top"><em>P</em><sub>2</sub> accesses <tt>x</tt>,
then <em>P</em><sub>1</sub> sets <tt>x</tt> to 100, then
<em>P</em><sub>2</sub> sets <tt>x</tt>.</td>
</tr>
<tr>
<td valign="top">100:</td>
<td valign="top"><em>P</em><sub>1</sub> accesses <tt>x</tt>
(twice), then <em>P</em><sub>2</sub> sets <tt>x</tt> to 11,
then <em>P</em><sub>1</sub> sets <tt>x</tt>.</td>
</tr>
<tr>
<td valign="top"></td>
</tr>
</table>
<p>We can constrain the concurrency by using serialized
procedures, which are created by <em>serializers</em>.
Serializers are constructed by <tt>make-serializer</tt>, whose
implementation is given below. A serializer takes a procedure as
argument and returns a serialized procedure that behaves like the
original procedure. All calls to a given serializer return
serialized procedures in the same set.</p>
<p>Thus, in contrast to the example above, executing</p>
<p><tt>(define x 10)<br />
<br />
(define s (make-serializer))<br />
<br />
(parallel-execute (s (lambda () (set! x (* x x))))<br />
(s (lambda () (set! x (+ x 1)))))<br />
</tt></p>
<p>can produce only two possible values for <tt>x</tt>, 101 or
121. The other possibilities are eliminated, because the
execution of <em>P</em><sub>1</sub> and <em>P</em><sub>2</sub>
cannot be interleaved.</p>
<p>Here is a version of the <tt>make-account</tt> procedure from
section <a href="book-Z-H-20.html#%_sec_3.1.1">3.1.1</a>,
where the deposits and withdrawals have been serialized:</p>
<p><tt><a name="%_idx_3614"></a><a name="%_idx_3616"></a>(define (make-account balance)<br />
(define (withdraw amount)<br />
(if (>= balance amount)<br />
(begin (set! balance (- balance amount))<br />
balance)<br />
"Insufficient funds"))<br />
(define (deposit amount)<br />
(set! balance (+ balance amount))<br />
balance)<br />
(let ((protected (make-serializer)))<br />
(define (dispatch m)<br />
(cond ((eq? m 'withdraw) (protected withdraw))<br />
((eq? m 'deposit) (protected deposit))<br />
((eq? m 'balance) balance)<br />
(else (error "Unknown request -- MAKE-ACCOUNT"<br />
m))))<br />
dispatch))<br /></tt></p>
<p>With this implementation, two processes cannot be withdrawing
from or depositing into a single account concurrently. This
eliminates the source of the error illustrated in
figure <a href="#%_fig_3.29">3.29</a>, where Peter changes
the account balance between the times when Paul accesses the
balance to compute the new value and when Paul actually performs
the assignment. On the other hand, each account has its own
serializer, so that deposits and withdrawals for different
accounts can proceed concurrently.</p>
<p><a name="%_thm_3.39"></a> <b>Exercise
3.39.</b> Which of the five possibilities in the
parallel execution shown above remain if we instead serialize
execution as follows:</p>
<p><tt>(define x 10)<br />
<br />
(define s (make-serializer))<br />
<br />
(parallel-execute (lambda () (set! x ((s (lambda () (* x x))))))<br />
(s (lambda () (set! x (+ x 1)))))<br />
</tt></p>
<p><a name="%_thm_3.40"></a> <b>Exercise
3.40.</b> Give all possible values of <tt>x</tt> that
can result from executing</p>
<p><tt>(define x 10)<br />
<br />
(parallel-execute (lambda () (set! x (* x x)))<br />
(lambda () (set! x (* x x x))))<br />
</tt></p>
<p>Which of these possibilities remain if we instead use
serialized procedures:</p>
<p><tt>(define x 10)<br />
<br />
(define s (make-serializer))<br />
<br />
(parallel-execute (s (lambda () (set! x (* x x))))<br />
(s (lambda () (set! x (* x x x)))))<br />
</tt></p>
<p><a name="%_thm_3.41"></a> <b>Exercise 3.41.</b> Ben
Bitdiddle worries that it would be better to implement the bank
account as follows (where the commented line has been
changed):</p>
<p><tt><a name="%_idx_3618"></a>(define (make-account balance)<br />
(define (withdraw amount)<br />
(if (>= balance amount)<br />
(begin (set! balance (- balance amount))<br />
balance)<br />
"Insufficient funds"))<br />
(define (deposit amount)<br />
(set! balance (+ balance amount))<br />
balance)<br />
<em>;; continued on next page</em><br />
<br />
(let ((protected (make-serializer)))<br />
(define (dispatch m)<br />
(cond ((eq? m 'withdraw) (protected withdraw))<br />
((eq? m 'deposit) (protected deposit))<br />
((eq? m 'balance)<br />
((protected (lambda () balance)))) <em>; serialized</em><br />
(else (error "Unknown request -- MAKE-ACCOUNT"<br />
m))))<br />
dispatch))<br /></tt></p>
<p>because allowing unserialized access to the bank balance can
result in anomalous behavior. Do you agree? Is there any scenario
that demonstrates Ben's concern?</p>
<p><a name="%_thm_3.42"></a> <b>Exercise 3.42.</b> Ben
Bitdiddle suggests that it's a waste of time to create a new
serialized procedure in response to every <tt>withdraw</tt> and
<tt>deposit</tt> message. He says that <tt>make-account</tt>
could be changed so that the calls to <tt>protected</tt> are done
outside the <tt>dispatch</tt> procedure. That is, an account
would return the same serialized procedure (which was created at
the same time as the account) each time it is asked for a
withdrawal procedure.</p>
<p><tt><a name="%_idx_3620"></a>(define (make-account balance)<br />
(define (withdraw amount)<br />
(if (>= balance amount)<br />
(begin (set! balance (- balance amount))<br />
balance)<br />
"Insufficient funds"))<br />
(define (deposit amount)<br />
(set! balance (+ balance amount))<br />
balance)<br />
(let ((protected (make-serializer)))<br />
(let ((protected-withdraw (protected withdraw))<br />
(protected-deposit (protected deposit)))<br />
(define (dispatch m)<br />
(cond ((eq? m 'withdraw) protected-withdraw)<br />
((eq? m 'deposit) protected-deposit)<br />
((eq? m 'balance) balance)<br />
(else (error "Unknown request -- MAKE-ACCOUNT"<br />
m))))<br />
dispatch)))<br /></tt></p>
<p>Is this a safe change to make? In particular, is there any
difference in what concurrency is allowed by these two versions
of <tt>make-account</tt> ?</p>
<p><a name="%_sec_Temp_420"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_420">Complexity of
using multiple shared resources</a></h4>
<p><a name="%_idx_3622"></a><a name="%_idx_3624"></a> Serializers
provide a powerful abstraction that helps isolate the
complexities of concurrent programs so that they can be dealt
with carefully and (hopefully) correctly. However, while using
serializers is relatively straightforward when there is only a
single shared resource (such as a single bank account),
concurrent programming can be treacherously difficult when there
are multiple shared resources.</p>
<p>To illustrate one of the difficulties that can arise, suppose
we wish to swap the balances in two bank accounts. We access each
account to find the balance, compute the difference between the
balances, withdraw this difference from one account, and deposit
it in the other account. We could implement this as
follows:<a href="#footnote_Temp_421" name="call_footnote_Temp_421" id="call_footnote_Temp_421"><sup><small>41</small></sup></a></p>
<p><tt><a name="%_idx_3626"></a><a name="%_idx_3628"></a>(define (exchange account1 account2)<br />
(let ((difference (- (account1 'balance)<br />
(account2 'balance))))<br />
((account1 'withdraw) difference)<br />
((account2 'deposit) difference)))<br />
</tt></p>
<p>This procedure works well when only a single process is trying
to do the exchange. Suppose, however, that Peter and Paul both
have access to accounts <em>a</em>1, <em>a</em>2, and
<em>a</em>3, and that Peter exchanges <em>a</em>1 and <em>a</em>2
while Paul concurrently exchanges <em>a</em>1 and <em>a</em>3.
Even with account deposits and withdrawals serialized for
individual accounts (as in the <tt>make-account</tt> procedure
shown above in this section), <tt>exchange</tt> can still produce
incorrect results. For example, Peter might compute the
difference in the balances for <em>a</em>1 and <em>a</em>2, but
then Paul might change the balance in <em>a</em>1 before Peter is
able to complete the exchange.<a href="#footnote_Temp_422" name="call_footnote_Temp_422" id="call_footnote_Temp_422"><sup><small>42</small></sup></a> For
correct behavior, we must arrange for the <tt>exchange</tt>
procedure to lock out any other concurrent accesses to the
accounts during the entire time of the exchange.</p>
<p>One way we can accomplish this is by using both accounts'
serializers to serialize the entire <tt>exchange</tt> procedure.
To do this, we will arrange for access to an account's
serializer. Note that we are deliberately breaking the modularity
of the bank-account object by exposing the serializer. The
following version of <tt>make-account</tt> is identical to the
original version given in section <a href="book-Z-H-20.html#%_sec_3.1.1">3.1.1</a>, except that a
serializer is provided to protect the balance variable, and the
serializer is exported via message passing:</p>
<p><tt><a name="%_idx_3630"></a>(define (make-account-and-serializer balance)<br />
(define (withdraw amount)<br />
(if (>= balance amount)<br />
(begin (set! balance (- balance amount))<br />
balance)<br />
"Insufficient funds"))<br />
(define (deposit amount)<br />
(set! balance (+ balance amount))<br />
balance)<br />
(let ((balance-serializer (make-serializer)))<br />
(define (dispatch m)<br />
(cond ((eq? m 'withdraw) withdraw)<br />
((eq? m 'deposit) deposit)<br />
((eq? m 'balance) balance)<br />
((eq? m 'serializer) balance-serializer)<br />
(else (error "Unknown request -- MAKE-ACCOUNT"<br />
m))))<br />
dispatch))<br /></tt></p>
<p>We can use this to do serialized deposits and withdrawals.
However, unlike our earlier serialized account, it is now the
responsibility of each user of bank-account objects to explicitly
manage the serialization, for example as follows:<a href="#footnote_Temp_423" name="call_footnote_Temp_423" id="call_footnote_Temp_423"><sup><small>43</small></sup></a></p>
<p><tt><a name="%_idx_3632"></a>(define (deposit account amount)<br />
(let ((s (account 'serializer))<br />
(d (account 'deposit)))<br />
((s d) amount)))<br /></tt></p>
<p>Exporting the serializer in this way gives us enough
flexibility to implement a serialized exchange program. We simply
serialize the original <tt>exchange</tt> procedure with the
serializers for both accounts:</p>
<p><tt><a name="%_idx_3634"></a>(define (serialized-exchange account1 account2)<br />
(let ((serializer1 (account1 'serializer))<br />
(serializer2 (account2 'serializer)))<br />
((serializer1 (serializer2 exchange))<br />
account1<br />
account2)))<br /></tt></p>
<p><a name="%_thm_3.43"></a> <b>Exercise
3.43.</b> Suppose that the balances in three accounts
start out as $10, $20, and $30, and that multiple processes run,
exchanging the balances in the accounts. Argue that if the
processes are run sequentially, after any number of concurrent
exchanges, the account balances should be $10, $20, and $30 in
some order. Draw a timing diagram like the one in
figure <a href="#%_fig_3.29">3.29</a> to show how this
condition can be violated if the exchanges are implemented using
the first version of the account-exchange program in this
section. On the other hand, argue that even with this
<tt>exchange</tt> program, the sum of the balances in the
accounts will be preserved. Draw a timing diagram to show how
even this condition would be violated if we did not serialize the
transactions on individual accounts.</p>
<p><a name="%_thm_3.44"></a> <b>Exercise
3.44.</b> <a name="%_idx_3636"></a>Consider the
problem of transferring an amount from one account to another.
Ben Bitdiddle claims that this can be accomplished with the
following procedure, even if there are multiple people
concurrently transferring money among multiple accounts, using
any account mechanism that serializes deposit and withdrawal
transactions, for example, the version of <tt>make-account</tt>
in the text above.</p>
<p>
<tt>(define (transfer from-account to-account amount)<br />
((from-account 'withdraw) amount)<br />
((to-account 'deposit) amount))<br /></tt></p>
<p>Louis Reasoner claims that there is a problem here, and that
we need to use a more sophisticated method, such as the one
required for dealing with the exchange problem. Is Louis right?
If not, what is the essential difference between the transfer
problem and the exchange problem? (You should assume that the
balance in <tt>from-account</tt> is at least
<tt>amount</tt>.)</p>
<p><a name="%_thm_3.45"></a> <b>Exercise
3.45.</b> Louis Reasoner thinks our bank-account
system is unnecessarily complex and error-prone now that deposits
and withdrawals aren't automatically serialized. He suggests that
<tt>make-account-and-serializer</tt> should have exported the
serializer (for use by such procedures as
<tt>serialized-exchange</tt>) in addition to (rather than instead
of) using it to serialize accounts and deposits as
<tt>make-account</tt> did. He proposes to redefine accounts as
follows:</p>
<p>
<tt>(define (make-account-and-serializer balance)<br />
(define (withdraw amount)<br />
(if (>= balance amount)<br />
(begin (set! balance (- balance amount))<br />
balance)<br />
"Insufficient funds"))<br />
(define (deposit amount)<br />
(set! balance (+ balance amount))<br />
balance)<br />
(let ((balance-serializer (make-serializer)))<br />
(define (dispatch m)<br />
(cond ((eq? m 'withdraw) (balance-serializer withdraw))<br />
((eq? m 'deposit) (balance-serializer deposit))<br />
((eq? m 'balance) balance)<br />
((eq? m 'serializer) balance-serializer)<br />
(else (error "Unknown request -- MAKE-ACCOUNT"<br />
m))))<br />
dispatch))<br /></tt></p>
<p>Then deposits are handled as with the original
<tt>make-account</tt>:</p>
<p><tt>(define (deposit account amount)<br />
((account 'deposit) amount))<br /></tt></p>
<p>Explain what is wrong with Louis's reasoning. In particular,
consider what happens when <tt>serialized-exchange</tt> is
called.</p>
<p><a name="%_sec_Temp_427"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_427">Implementing
serializers</a></h4>
<p><a name="%_idx_3638"></a> We implement serializers in terms of
a more primitive synchronization mechanism called a <a name="%_idx_3640"></a><em>mutex</em>. A mutex is an object that
supports two operations -- the mutex can be <a name="%_idx_3642"></a><em>acquired</em>, and the mutex can be <a name="%_idx_3644"></a><em>released</em>. Once a mutex has been
acquired, no other acquire operations on that mutex may proceed
until the mutex is released.<a href="#footnote_Temp_428" name="call_footnote_Temp_428" id="call_footnote_Temp_428"><sup><small>44</small></sup></a> In our
implementation, each serializer has an associated mutex. Given a
procedure <tt>p</tt>, the serializer returns a procedure that
acquires the mutex, runs <tt>p</tt>, and then releases the mutex.
This ensures that only one of the procedures produced by the
serializer can be running at once, which is precisely the
serialization property that we need to guarantee.</p>
<p><tt><a name="%_idx_3660"></a>(define (make-serializer)<br />
(let ((mutex (make-mutex)))<br />
(lambda (p)<br />
(define (serialized-p . args)<br />
(mutex 'acquire)<br />
(let ((val (apply p args)))<br />
(mutex 'release)<br />
val))<br />
serialized-p)))<br /></tt></p>
<p>The mutex is a mutable object (here we'll use a one-element
list, which we'll refer to as a <a name="%_idx_3662"></a><em>cell</em>) that can hold the value true or
false. When the value is false, the mutex is available to be
acquired. When the value is true, the mutex is unavailable, and
any process that attempts to acquire the mutex must wait.</p>
<p>Our mutex constructor <tt>make-mutex</tt> begins by
initializing the cell contents to false. To acquire the mutex, we
test the cell. If the mutex is available, we set the cell
contents to true and proceed. Otherwise, we wait in a loop,
attempting to acquire over and over again, until we find that the
mutex is available.<a href="#footnote_Temp_429" name="call_footnote_Temp_429" id="call_footnote_Temp_429"><sup><small>45</small></sup></a> To
release the mutex, we set the cell contents to false.</p>
<p><tt><a name="%_idx_3668"></a>(define (make-mutex)<br />
(let ((cell (list false))) <br />
(define (the-mutex m)<br />
(cond ((eq? m 'acquire)<br />
(if (test-and-set! cell)<br />
(the-mutex 'acquire))) <em>; retry</em><br />
((eq? m 'release) (clear! cell))))<br />
the-mutex))<br />
(define (clear! cell)<br />
(set-car! cell false))<br /></tt></p>
<p><tt>Test-and-set!</tt> tests the cell and returns the result
of the test. In addition, if the test was false,
<tt>test-and-set!</tt> sets the cell contents to true before
returning false. We can express this behavior as the following
procedure:</p>
<p><tt><a name="%_idx_3670"></a>(define (test-and-set! cell)<br />
(if (car cell)<br />
true<br />
(begin (set-car! cell true)<br />
false)))<br />
</tt></p>
<p>However, this implementation of <tt>test-and-set!</tt> does
not suffice as it stands. There is a crucial subtlety here, which
is the essential place where concurrency control enters the
system: The <tt>test-and-set!</tt> operation must be performed
<a name="%_idx_3672"></a><em>atomically</em>. That is, we must
guarantee that, once a process has tested the cell and found it
to be false, the cell contents will actually be set to true
before any other process can test the cell. If we do not make
this guarantee, then the mutex can fail in a way similar to the
bank-account failure in figure <a href="#%_fig_3.29">3.29</a>. (See exercise <a href="#%_thm_3.46">3.46</a>.)</p>
<p>The actual implementation of <tt>test-and-set!</tt> depends on
the details of how our system runs concurrent processes. For
example, we might be executing concurrent processes on a
sequential processor using a <a name="%_idx_3674"></a>time-slicing mechanism that cycles through the
processes, permitting each process to run for a short time before
interrupting it and moving on to the next process. In that case,
<tt>test-and-set!</tt> can work by disabling time slicing during
the testing and setting.<a href="#footnote_Temp_430" name="call_footnote_Temp_430" id="call_footnote_Temp_430"><sup><small>46</small></sup></a>
Alternatively, multiprocessing computers provide instructions
that support atomic operations directly in hardware.<a href="#footnote_Temp_431" name="call_footnote_Temp_431" id="call_footnote_Temp_431"><sup><small>47</small></sup></a></p>
<p><a name="%_thm_3.46"></a> <b>Exercise
3.46.</b> Suppose that we implement
<tt>test-and-set!</tt> using an ordinary procedure as shown in
the text, without attempting to make the operation atomic. Draw a
timing diagram like the one in figure <a href="#%_fig_3.29">3.29</a> to demonstrate how the mutex
implementation can fail by allowing two processes to acquire the
mutex at the same time.</p>
<p><a name="%_thm_3.47"></a> <b>Exercise
3.47.</b> <a name="%_idx_3692"></a>A semaphore (of
size <em>n</em>) is a generalization of a mutex. Like a mutex, a
semaphore supports acquire and release operations, but it is more
general in that up to <em>n</em> processes can acquire it
concurrently. Additional processes that attempt to acquire the
semaphore must wait for release operations. Give implementations
of semaphores</p>
<p>a. in terms of mutexes</p>
<p>b. in terms of atomic <tt>test-and-set!</tt> operations.</p>
<p><a name="%_sec_Temp_434"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_434">Deadlock</a></h4>
<p><a name="%_idx_3694"></a><a name="%_idx_3696"></a> Now that we
have seen how to implement serializers, we can see that account
exchanging still has a problem, even with the
<tt>serialized-exchange</tt> procedure above. Imagine that Peter
attempts to exchange <em>a</em>1 with <em>a</em>2 while Paul
concurrently attempts to exchange <em>a</em>2 with <em>a</em>1.
Suppose that Peter's process reaches the point where it has
entered a serialized procedure protecting <em>a</em>1 and, just
after that, Paul's process enters a serialized procedure
protecting <em>a</em>2. Now Peter cannot proceed (to enter a
serialized procedure protecting <em>a</em>2) until Paul exits the
serialized procedure protecting <em>a</em>2. Similarly, Paul
cannot proceed until Peter exits the serialized procedure
protecting <em>a</em>1. Each process is stalled forever, waiting
for the other. This situation is called a <em>deadlock</em>.
Deadlock is always a danger in systems that provide concurrent