The following manuscript
EWD 501: Variations on a theme: an open letter to C.A.R. Hoare
is held in copyright by Springer-Verlag New York.
The manuscript was published as pages 132-140 of
Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective,
Springer-Verlag, 1982. ISBN 0-387-90652-5.
Reproduced with permission from Springer-Verlag New York.
Any further reproduction is strictly prohibited.
5th July 1975
Variations on a theme: an open letter to C.A.R.Hoare.
For a variety of reasons I have not yet reacted to your article on Monitors . For one thing: it failed to convince me —something I felt bad about, because I knew that this might have been due to the circumstance that I had been too lazy to go in detail through your more sophisticated examples—. Secondly: I was not too pleased either with the alternatives I could offer myself —my difficulty in finding good identifiers for the operations I was considering was just a symptom of my own mixed feelings—. Eventually I got interested in what one can do without mutual exclusion, and I dropped the subjectÊ —not without remorse, for I had left a task undone: I had failed to make up my mind!—.
Recently the topic was brought back to my attention by a nice technical report by Coen Bron , and in a Tuesday afternoon discussion with Wim Feijen, Alain Martin, Martin Rem and Liesbeth Steffens I tried, as a result, to redesign my (formerly rejected) alternative, in the hope that this time I could do a more conclusive job. This letter records the quintessence of that discussion and the following considerations.
About the microscopic delays implied by mutual exclusion.
The whole purpose of a monitor is to grant mutually exclusive access to a bunch of common variables, and this implies two things.
First: the whole monitor concept is only adequate in circumstances such that a monitor will only be "active" during a negligible fraction of time. (And, on the next higher level of abstraction, we shall indeed ignore the CPU-time spent on "monitoring"!) Second: in any multiprocessor installation, attempted monitor calls while the monitor is active imply delays, but in view of the first remark I propose to attach no significance whatsoever to the order in which such "microscopic" delays have been caused. Such microscopic delays will last until the moment when otherwise the monitor would have become inactive, and one of the microscopically delayed processes will be granted access to the monitor. Our only (logical!) requirement is the exclusion of the (in view of our first remark highly improbable) danger of individual starvation. (Round Robin, for instance, would do!) In the following the microscopic delays will not be mentioned anymore, logically it is as if "by magic" no process attempts to call a monitor while it is active. (Early in the discussion I had failed to make a clear distinction between microscopically delayed processes eager to call the monitor, and macroscopically delayed processes that, being woken up, were eager to continue an interrupted execution of a monitor procedure —in what follows the latter class will disappear—; this confusion was so disastrous that it did not last long!)
Note. At the lowest level I expect no objection to implementing the microscopic delays by means of the busy form of waiting. (End of Note.)
About the macroscopic delays introduced by a monitor
The further purpose of a monitor is to introduce macroscopic delays when necessary, and, ideally, a monitor is formulated in such a fashion that it does not reflect the number of partners between which the cooperation is regulated. It should describe "my" behaviour versus "the others". (In the THE-system the cooperation was coded in a context in which all partners were individually known and explicitly referred to; in retrospect I regard that now as one of the more significant shortcomings of that system.) In order to describe the rules of cooperation in a way which was independent of the number of partners involved, I envisaged to describe it in terms of a finite number of named queues of sleeping —i.e. macroscopically delayed— processes, where the queues themselves could be of any length, and each sleeping process would occur at exactly one queue.
Right at the start, our decision that the elements on a queue should be linearly ordered, seemed more emphatic than yours. You write: "If more than one program is waiting on a condition, we postulate that the signal operation will activate the longest waiting program. This gives a simple, neutral queueing discipline, which ensures that every waiting program will eventually get its turn." But if individual starvation is the danger you would like to exorcize, Round Robin or allowance counts would have done as well.
I propose for the linear order of the elements in each queue a role that seems to me much more fundamental: "the (sleeping) others" are known to "me" by virtue of their place in one of the queues. If they were sets instead of linearly ordered queues, the different "(sleeping) others" would have no distinct identities.