The Mutual Exclusion Problem
Goals for this lecture :
- To introduce the early concepts of parallel execution
and synchronisation.
- To introduce the Mutual Exclusion Problem.
- To introduce safety and liveness
properties.
Click here ,
here , and here for these
notes in postscript
We now move on to present concurrent programming in a more historically
correct order.
This means considering the early concepts of
parallel execution and synchronisation which
emerged in the 1960s.
In those days the term interleaving was understood
in the context of multi-programming,
that is, "... the concurrent execution of several independent
programs on one processor" ( p. 4,
[ B-A90 ] ).
In CCS-speak we would say that the early notion of
interleaving was just the rules Com1 and
Com2, communication still being some way off.
These ideas of the time were elegantly captured in
Dijktra's Co-operating Sequential Processes
[ Di68 ].
He saw parallel execution as the interleaving of statements,
analogous to sequential execution which was the execution of statements one
after the other.
Not surprisingly then Dijkstra suggested the parbegin-parend
notation to contrast with Algol's begin-end
( Slide 1 ).
Instead of using just one program counter the parallel compound
has a counter for each of its statements.
As we said, interleaving in Dijkstra's model is interleaving
(in CCS-speak)
using just rules
Com1 and Com2, but this raises the
question of what is an atomic statement in Dijkstra's model?
There was no satisfactory answer available at the time.
The notion of `synchronisation' for parallel compounds
can be easily expressed using CCS-speak
( Slide 2 ).
It is just the outlawing of some possible derivation sequences,
but the problem is how to express it!
At the time there were no primitive commands for saying
that such and sequences are to be allowed but others are not.
And so, if the implementer could not control synchronisation it
was left to the programmer to simulate it.
In Lectures 10 and 11 we are studying the
ways that programmers once used to control synchronisation
before the advent of primitives.
We study this not for reasons of nostalgia, but because their
methods would later be taken up by implementers to build
synchronisation primitives
( Slide 3 ).
And so, when later we come to such primitives as the
semaphore we will have some idea as to how they
might be implemented.
The best way to study the intricacies of synchronisation is
to use an archetypal problem.
The most well known of these is the
Mutual Exclusion Problem ( MEP )
( Slide 4 ).
The MEP is how to write the protocols surrounding the
critical sections which may not overlap.
Now try Exercise 1.
Before that can be done we need some correctness
properties for interleaving and synchronisation which
can be used to assess the performance of suggested protocols.
Correctness properties are for reasons of safety
(i.e. nothing bad can happen)
( Slide 5 )
or for liveness
( Slide 6 )
(i.e. something good will eventually happen).
Now try Exercise 2 to
test your understanding of fairness.
In order to maintain mutual exclusion we must have some way of
making one process `wait' before entering its critcial until the
other has cleared its own critical section.
This can be achieved using busy waiting
( Slide 7 ).
Note that steps will have to be taken to ensure that no
interference can take place during the execution of each
busy_wait_loop_i.
At this point we need to consider which language should be used for concurrent programming,
There are two approaches.
We could either design a new high level language with lots of built-in primitives for
concurrency, synchronisation, and message passing; this was the approach in
CS224 where we have used
Pascal-FC and SR.
Alternatively we could start with Java and threads, then build up a suite of classess and objects.
First let us see how we used to do it.
Before programming busy waiting we need to start introducing
SR.
We start with the picture from the front of the book
to introduce its concept of parallel execution as multi
threaded computation
( Slide 8 ).
Next we introduce (in the abstract) its three components
of resource, global, and operation
( Slide 9 ).
The resource is SR's outermost unit of
encapsulation, compilation and spatial existence, in other words,
a module.
The global is an object shared between resources.
The operation (existing inside either a resource or
a global) is a generalisation of procedure,
with its three aspects of declaration, implementation,
and invocation.
Invocation may be invoked synchronously or asynchronously.
Of particular interest here is a process operation which
is automatically invoked asynchronously when declared and implemented.
Next we give some single resource example SR programs
to give substance to the philosophy just introduced.
First we give a program to compute a single factorial
( Slide 10 ,
fac.sr ).
See Note 1.
Next we try a sequential algorithm for multiplying
two n by n matrices
( Slide 11 ,
Slide 12 ,
matrix1.sr ,
Exercise 3 ).
Being concurrent programmers we soon note that all of the
n² inner products could be done in parallel,
but first an important point on parallelism in SR.
SR is much more flexible in its invocation methods than
could have ever been realised back in Dijkstra's day.
Thus it is not surprising to learn that SR has no
need for parallel compounds.
As processes in SR are automatically
invoked asynchronously we can model any parallel compound
as a resource of processes
( Slide 13 ).
And so we say thank you for the parallel compound, but
it's now time for it to be retired.
In our array multiplication problem we make each of the
n² inner products a process
( Slide 14 ,
matrix2.sr ).
Note how the final-end brackets are used to ensure
that the matrix product is computed before we try and print it.
Now that we have introduced both the MEP and SR we can
spend the next lecture programming solutions.
At this point of the course you should have purchased your
SR course textbook
[ AO93 ]
and be studying hard to familiarise yourself with the language.
The drawback of using a purpose built concurrent programming language such as SR is that
it is not (at least not yet!) part of the mainstream Java OOP world, and that is where
we really want to be.
Java offers us the foundations for concurrent programming,
namely multiple threads and a synchronisation primitive
( Slide 15 ,
[ Bi98 ] ).
The choice for concurrent programming is thus to be in a rigid framework where concurrency
primitives are prescribed, or to work in an 'open ended' environment where concurrency primitives
are to be invented or downloaded.
Further Study
Further Study
is always welcome.
