Notions of serializability and concurrency appear at first sight contradictory : one seems to preclude the other. This article aims to understand when truly concurrentlyrunning processes are serializable. The impetus comes from the following passage describing the order of argument evaluation in every compliant Scheme system (R5RS, Sec 4.1.3):
Note: In contrast to other dialects of Lisp, the order of evaluation is unspecified, and the operator expression and the operand expressions are always evaluated with the same evaluation rules.It appears that while the first note allows parallel evaluation of argument expressions, the second note seemingly insists that evaluation proceed sequentially.Note: Although the order of evaluation is otherwise unspecified, the effect of any concurrent evaluation of the operator and operand expressions is constrained to be consistent with some sequential order of evaluation. The order of evaluation may be chosen differently for each procedure call.
Let's take an example of two processes, P1 and P2.
The processes are to perform the computation:
P1: 
(load (r 0) (constant 1))
 P2: 
(load (r 0) (constant 2))

We use some sort of a "portable" assembler in these examples. (r n)
denotes a register n
, which is a "process' local variable," a part of process' context. (r 0)
in P1 has no relation whatsoever to (r 0)
in P2. (location sym)
denotes locations in shared memory. We assume that load, store, etc. operations are atomic. A process can be interrupted (and forced off a CPU) only after one operation completes and before another starts. On no occasion, e.g., a load operation is performed halfway, that is, loads only a part of the bits of a value. All old CPUs literally check for interrupts only when their ALUs finish. Newer CPUs are far more complex, yet they try to give the same impression.
There can be two sequential schedules of executing P1 and P2, which are listed in the following table. The table also shows one parallel schedule:
Schedule  Operations  Result 

Sequential SS1  P1 then P2 
'((A 1) (B 2))

Sequential SS2  P2 then P1 
'((A 1) (B 2))

Parallel PS1  P1::load, P2::load, P2::store, P1::store 
'((A 1) (B 2))

It is easy to see that any other parallel schedule gives the same
result. No matter what the sequence of loads and stores to
the common memory is, the outcome is always the same as that of SS1.
The processes are to execute:
P1: 
(load (r 0) (constant 1))
 P2: 
(load (r 0) (constant 2))

Schedule  Operations  Result 

Sequential SS1  P1 then P2 
'((A 2))

Sequential SS2  P2 then P1 
'((A 1))

Parallel PS1 
P1::load, P2::load, P2::store, P1::store 
'((A 1))

Parallel PS2 
P1::load, P2::load, P1::store, P2::store 
'((A 2))

P1: 
(load (r 0) (location 'A))
 P2: 
(load (r 0) (constant 2))
 
The original store: '((A 0))

Schedule  Operations  Result 

Sequential SS1  P1 then P2 
'((A 2))

Sequential SS2  P2 then P1 
'((A 3))

Parallel PS1 
P1::load, P1::add, P2::load, P1::store, P2::store 
'((A 2))

Parallel PS2 
P1::load, P1::add, P2::load, P2::store, P1::store 
'((A 1))

While PS1 gives the same result as the sequential schedule SS1, PS2 yields something that cannot be produced with any sequential schedule. R5RS, Sec 4.1.3 specifically outlaws this kind of schedule. Yet PS1 is allowed  so argument expressions in a function call can be evaluated in parallel after all.
Computations like {P1, P2} in Ex2 are called serializable: no matter how you run the processes concurrently, there is always a way to achieve the same final result by executing these processes sequentially on a single CPU. Computation as in Ex3 is nonserializable: there exists a parallel schedule whose final result cannot be achieved in any sequential computation. In databases, for example, nonserializable transactions are considered great evil, and the perpetrators are publicly flogged (or ought to be).
One can make Example Ex3 serializable by defining a critical section around P1 and P2::store
. The example will still permit a certain
degree of concurrency: P2::load
can run in parallel with P1::load
, but then P2 must wait for P1 to complete.
Chapter "11.1 Basic concepts of concurrency" of Jeffrey Ullman's
Principles of Database Systems (2nd Edition, 1982) talks about these
issues in great detail. This book is remarkable in more ways than
one. There is the third edition of this book.
The examples 1 through 3 should help to understand the passage from R5RS quoted at the beginning of this page. One has to distinguish however between
Assuming
(define (adder x) (lambda (y z) (+ x y z)))consider the following expression:
((adder 3) ( 4 5) (* 4 5))
We have to perform four evaluations to get to the final result:
Ev#1: (adder 3) ==> (lambda (y z) (+ 3 y z)) Ev#2: ( 4 5) ==> 1 Ev#3: (* 4 5) ==> 20 Ev#4: applying the result of Ev#1 to the results of Ev#2 and Ev#3: (apply (lambda (y z) (+ 3 y z)) 1 20) ==> 22
According to R5RS, Ev#1
, Ev#2
, and Ev#3
can proceed in any order: for example, Ev#1  Ev#2  Ev#3
or Ev#3  Ev#2  Ev#1
. This order can even change from one invocation of a procedure to another invocation of the same procedure. Furthermore, Ev#1
, Ev#2
and Ev#3
can proceed in parallel, on concurrently running CPUs if available  provided that they are serializable: i.e., there exists a sequential schedule that gives the same final results.
In any case, Ev#4
may commence only after Ev#1
, Ev#2
, and Ev#3
are all finished. This is required by a strict, callbyvalue semantics of Scheme: procedure's body is evaluated only after all its arguments yield the value. If evaluation of one argument takes forever, the
procedure body will never gets a chance to run  even if the
procedure will not require the value of that particular argument.
Note, Scheme actually has other evaluators, some of them with a
nonstrict semantics. See "Four evaluators of CL/Scheme and their bottom
terms" for an illustration.
The present page is a compilation of two articles posted on a comp.lang.scheme newsgroups on Jan 5 and Jan 8, 2000.
From: oleg MessageID: <856bda$quc$1@nnrp1.deja.com> Subject: Concurrent and serializable computations [Re: Order of evaluations of arguments...] Date: Sat, 08 Jan 2000 03:37:15 GMT Newsgroups: comp.lang.scheme XArticleCreationDate: Sat Jan 08 03:37:15 2000 GMT From: oleg MessageId: <84u6ua$t7q$1@nnrp1.deja.com> Subject: Order of evaluations of arguments and bodies [Re: question about Scheme standards and SRFI process Date: Wed, 05 Jan 2000 01:31:54 GMT Newsgroups: comp.lang.scheme References: <RT5hONljzGn0S30mwmVXTGmMOBES@personalnews.de.uu.net> <B48A883C9668315CC0@0.0.0.0> <946211855.7638.0.nnrp14.9e987a3c@news.demon.co.uk> <B491ADFC96683F4844@hearsay.demon.co.uk> <946643419.27673.0.nnrp01.9e987a3c@news.demon.co.uk> XArticleCreationDate: Wed Jan 05 01:31:54 2000 GMT
olegatokmij.org