|
|
От: | Mirrorer | |
| Дата: | 03.10.06 11:40 | ||
| Оценка: | 34 (4) | ||
Foreword
For a variety of reasons, this is a book eagerly awaited by all who knew it
was in the making; to say that their patience has been rewarded would be an
understatement.
A simple reason was that it is Tony Hoare’s first book. Many know him
from the lectures he has untiringly given all over the world; many more know
him as the articulate and careful author of a number of articles (of great variety!)
that became classics almost before the printer’s ink had dried. But a
book is a different medium: here the author can express himself without the
usually stringent limitations of time and space; it gives him the opportunity
of revealing himself more intimately and of covering a topic of wider span,
opportunities of which Tony Hoare has made the best use we could hope for.
A more solid reason was derived from the direct contents of the book.
When concurrency confronted the computing community about a quarter of
a century ago, it caused an endless confusion, partly by the technically very
different circumstances in which it emerged, partly by the accident of history
that it introduced non-determinism at the same time. The disentanglement of
that confusion required the hard work of a mature and devoted scientist who,
with luck, would clarify the situation. Tony Hoare has devoted a major part
of his scientific endeavours to that challenge, and we have every reason to be
grateful for that.
The most profound reason, however, was keenly felt by those who had
seen earlier drafts of his manuscript, which shed with surprising clarity new
light on what computing science could—or even should—be. To say or feel
that the computing scientist’s main challenge is not to get confused by the
complexities of his own making is one thing; it is quite a different matter to
discover and show how a strict adherence to the tangible and quite explicit
elegance of a few mathematical laws can achieve this lofty goal. It is here
that we, the grateful readers, reap to my taste the greatest benefits from the
scientific wisdom, the notational intrepidity, and the manipulative agility of
Charles Antony Richard Hoare.
Edsger W. Dijkstra
The ultimate objective of the book is to convey an insight which will enable
the reader to see both current and future problems in a fresh light, in which
they can be more efficiently and more reliably solved; and even better, they can
sometimes be avoided.
The most obvious application of the new ideas is to the specification,
design, and implementation of computer systems which continuously act and
interact with their environment. The basic idea is that these systems can be
readily decomposed into subsystems which operate concurrently and interact
with each other as well as with their common environment. The parallel composition
of subsystems is as simple as the sequential composition of lines or
statements in a conventional programming language.
This insight brings practical benefits. Firstly, it avoids many of the traditional
problems of parallelism in programming—interference, mutual exclusion,
interrupts, multithreading, semaphores, etc. Secondly, it includes
as special cases many of the advanced structuring ideas which have been
explored in recent research into programming languages and programming
methodology—the monitor, class, module, package, critical region, envelope,
form, and even the humble subroutine. Finally, it provides a secure mathematical
foundation for avoidance of errors such as divergence, deadlock and
non-termination, and for achievement of provable correctness in the design
and implementation of computer systems.
Chapter 1 introduces the basic concept of a process as a mathematical abstraction
of the interactions between a system and its environment. It shows how
the familiar technique of recursion may be used to describe processes that last
a long time, or forever. The concepts are explained first by example and then
by pictures; a more complete explanation is given by algebraic laws, and by an
implementation on a computer in a functional programming language.
The second part of the chapter explains how the behaviour of a process
can be recorded as a trace of the sequence of actions in which it engages. Many
useful operations on traces are defined. A process can be specified in advance
of implementation by describing the properties of its traces. Rules are given
to help in implementation of processes which can be proved to meet their
specifications.
The second chapter describes how processes can be assembled together
into systems, in which the components interact with each other and with their
external environment. The introduction of concurrency does not by itself introduce
any element of nondeterminism. The main example of this chapter is
a treatment of the traditional tale of the five dining philosophers.
The second part of Chapter 2 shows how processes can be conveniently
adapted to new purposes by changing the names of the events in which they
engage. The chapter concludes with an explanation of the mathematical theory
of deterministic processes, including a simple account of the domain theory
of recursion.
The third chapter gives one of the simplest known solutions to the vexed
problem of nondeterminism. Nondeterminism is shown to be a valuable technique
for achieving abstraction, since it arises naturally from the decision to
ignore or conceal those aspects of the behaviour of a systems in which we are
no longer interested. It also preserves certain symmetries in the definition of
the operators of the mathematical theory.
Proof methods for nondeterministic processes are slightly more complicated
than those for deterministic processes, since it is necessary to demonstrate
that every possible nondeterministic choice will result in a behaviour
which meets the given specification. Fortunately, there are techniques for
avoiding nondeterminism, and these are used extensively in Chapters 4 and 5.
Consequently the study or mastery of Chapter 3 can be postponed until just
before Chapter 6, in which the introduction of nondeterminism can no longer
be avoided.
In the later sections of Chapter 3, there is given a complete mathematical
definition of the concept of a nondeterministic process. This definition will
be of interest to the pure mathematician, who wishes to explore the foundations
of the subject, or to verify by proof the validity of the algebraic laws and
other properties of processes. Applied mathematicians (including programmers)
may choose to regard the laws as self-evident or justified by their utility;
and they may safely omit the more theoretical sections.
Chapter 4 at last introduces communication: it is a special case of interaction
between two processes, one of which outputs a message at the same time
as the other one inputs it. Thus communication is synchronised; if buffering is
required on a channel, this is achieved by interposing a buffer process between
the two processes.
An important objective in the design of concurrent systems is to achieve
greater speed of computation in the solution of practical problems. This is illustrated
by the design of some simple systolic (or iterative) array algorithms.
A simple case is a pipe, defined as a sequence of processes in which each process
inputs only from its predecessor and outputs only to its successor. Pipes
are useful for the implementation of a single direction of a communications
protocol, structured as a hierarchy of layers. Finally, the important concept
of an abstract data type is modelled a a subordinate process, each instance of
which communicates only with the block in which it is declared.
Chapter 5 shows how the conventional operators of sequential programming
can be integrated within the framework of communicating sequential
processes. It may be surprising to experienced programmers that these operators
enjoy the same kind of elegant algebraic properties as the operators of
familiar mathematical theories; and that sequential programs can be proved
to meet their specifications in much the same way as concurrent programs.
Even the externally triggered interrupt is defined and shown to be useful, and
subject to elegant laws.
Chapter 6 describes how to structure and implement a system in which
a limited number of physical resources such as discs and line printers can be
shared among a greater number of processes, whose resource requirements
vary with time. Each resource is represented as a single process. On each
occasion that a resource is required by a user process, a new virtual resource
is created.
A virtual resource is a process which behaves as if it were subordinate to
the user process; but it also communicates with the real resource whenever required.
Such communications are interleaved with those of other concurrently
active virtual processes. So the real and virtual processes play the same roles
as the monitors and envelopes of PASCAL PLUS. The chapter is illustrated by
the modular development of a series of complete but very simple operating
systems, which are the largest examples given in this book.
