EWD 108 and EWD 116 – about the banker’s algoritm

In EWD 108 and EWD 116 Dijkstra describes the banker’s algoritm to prevent a so-called deadly embrace. This algoritm manages different scarce resources in such a manner that all in need for one or more of the managed resources, are guaranteed to get their hands on the resource at some point in time.

Of course, in computer science, a computer – it’s operating system – manages a number of resources that are required by the processes running on the computer. And how many resources each process needs is not known beforehand (and often dynamically determined).
The analogy used in the paper is that of a banker lending money to clients, with the complicating constraint that clients do not know beforehand exactly how much money they will need. So they can lend more funds later on.

The situation could occur that the banker has only left an x amount to lend out, and a client John comes with a request for an additional amount larger than x. The banker can only hope that one of the other clients will soon finish their business and return their money. Only then can the banker help John. If however none of the other clients however can finish their business without coming to the banker for an additional lending, the banker is in deep trouble. His clients are waiting for eachother to finish their business, but to finish the business they all need some more money which they all hold themselves. A deadly embrace – “dodelijke omarming”.

Paper EWD 108 is a first exploration of the algorithm.
The core of the algorithm is the “trick” that the sum of the amount lended + the maximum amount needed of the last lender accepted is never larger than the amount of money the banker has available. As such the banker can always guarantee that he will get the money back because the last lender can always be satisfied. So the last lender is a sort of clinet of last resort. She can always guarantee return to a safe state is possible. An because for that state the algorithm also guarantee (inductively) that: “the sum of the amount lended + the maximum amount needed of the last lender accepted is never larger than the amount of money the banker has available”. (All my words.)

EWD 108 describes a small banker’s algorithm in pseudocode. The algorithm is somewhat clumsily written, and (because it )holds a goto (!) (goto consideren harmful). 
In EWD 116 the algorithm is refined, and no longer presented in pseudocode.The algorithm EWD 108 requires the claims for money to be sorted, the algorithm in EWD116 has removes this constraint.

Also in EDW 116 Dijkstra make a remark about different type of claims (in banker’s term, different currencies, for example). Apparently someone has made remarks that there may be different types of resources that need to be managed by the operating system – or Dijkstra himself thought it necessary to add this nuance. Dijkstra writes the algorithm is only applicable for a single type of resource (currency).

From a technical perspective the paper is interesting from an algorithmic perspective, and a story-telling perspective – it illustrates Dijkstra great use of metaphors from the mundane world to explain complex problems. 

Also from a historical computing perspective the paper is remarkable. Dijkstra totally discards the possibility of pre-emptive scheduling – that is: have the banker tell one of his clients to pause his business until other clients have returned their money. In not even very modern computing this is very common: processes can be “pre-emptively” put to rest to make sure other processes can progress. Apparently at the time of writing, which we do not know for sure (both EWD’s are not dated; somewhere before 1964?) pre-emptive scheduling was to be invented (or Dijkstra would have been aware for sure).

Dijkstra in EWD68: plain English unfit for programming

Edsger Dijkstra portrait

In 1961, Edsger Dijkstra wrote EWD 68, a short but powerful critique of the idea of using natural language for computer programming. His objections are still relevant today, especially in discussions about AI and “natural” interfaces.

What is EWD68 about?

In EDW68 Dijkstra expresses his concerns about a project reported by researcher H.J. Gawlik to create a compiler based on a combination of mathematical notation and plain English. Dijkstra’s concern lies not so much due in the fact the idea was raised, but that it still existed after the 2,5 year that passed since he first heard about it.

Gawlik was a researcher in the Royal Armament and Development Establishment, a UK Defense R&D organisation. (I tried to retrieve some personal data on Personal data on Gawlik but the Internet failed me).

Why natural language doesn’t work for programming

According to Dijkstra, plain English, or in general language used for human to human communication, is full of nonsense (humor, sloppiness, incompleteness, contradictions, etc.). What is expected from human to computer communication should be precise and unambiguous.
Therefore plain language is unfit for the purpose Gawlik aims to use it for, it “is obviously unfit to express what has to be expressed now”.

Dijkstra was right, 50 years later

I guess Dijkstra was proven right. Programming languages based on natural languages are nowhere to be found. The approach from Gawlik is a bit like adding human characteristics to AI systems nowadays: it makes the basically as sensitive to erroneous reasoning as human beings themselves.

Gawlik has written a response in which I sense he argues Dijkstra has not understood the goal of what Gawlik was trying to achieve, but unfortunately I can not find the full article and do not wish to may 19$ for it on ACM (goodness, why?).

The roots of modern computing explained in EWD51 – Multiprogramming and the X8

Dijkstra’s EWD 51 is a structured educational coverage of the workings of semaphores in communicating processes and with IO devices. It is the first part in a series of three articles called MULTIPROGAMMERING EN DE X8″ (Multiprogramming and the X8), EWD54 and 57 describe part 2 and 3.

if then else

The X8 is the Dutch research computer for which Dijkstra and hos team developed the operating system, and he was able to test his now famous concepts for multiprogramming. 
In a way it is the formal part of the talk that Dijkstra held and was transcribed in EWD 35.

EWD 51 extensively discusses the mechanisms of semaphores, the conditions, and (hardware) implications. That is the summary. To give more would be pointless, and you’d rather read the entire article. (The article is in Dutch – I could provide a quick translation if you are interested. Please let me know through a comment on this post, or send me an email)

The Dutch language used in this article is highly interesting. Dijkstra invents concepts for which no words existed before (seinpaal/semaphore as computing concept to start with) the abbreviations P (prolaag/pass – probeer te verlagen) and V (verhoog/increase), critieke secties / critical sections, ingreep-flip-flop / interrupt-flip-flops, luisterbit / listener bit, doof-horend bit.

The article could still  function as a modern introduction into the topic and still be applicable to today’s computers.

So far ahead, so clear, so up to date still.

EDW 37 – a review of the new IBM 1620

In EWD 37 Dijkstra records a product review of the the new IBM 1620 computer, which came to the market in 1959.
As often, the article starts with a wonderful Dijkstra-esk introduction.

It is a good custom that scientific articles are reviewed and that no publisher ever thinks about starting a lawsuit or any other measures of vengeance against the author of a very unfavourable review of one of his publications.

He continues,

With this in mind it is somewhat curious that it is not customary to review digital computers. Reviews of these scientific instruments are in some respects much more important: it is a pity if you have bought the wrong book, but it is much, much worse if you have bought the wrong computer.

Photo of the IBM 1620 computer

Foto from https://www.columbia.edu/cu/computinghistory/1620.html.

I am not sure if it is the first review of a new computer ever, but it is an interesting one, and it goes quite deep into the technical aspects.
(BTW for the historians amongst us, the 1620 was considered the first “mini-computer”.)

It is my considered opinion, however, that this machine embodies some very fundamental mistakes and certainly after the publication of the two letters mentioned above I regard it as my duty not to remain silent any longer. Manufacturers should be warned for these mistakes in order not to be tempted to incorporate them in their future designs, also machine users should be warned for these mistakes in order to help them in not chosing the wrong machine and in order to create a climate where machines will be judged more by their fundamental properties.

Dijkstra surfaces two major flaws in the design of this computer.
An instruction for constructing subroutines (Branch And Transmit) that is basically unusable because it is impossible to use in nested subroutines.

Another problem Dijkstra identifies is with the design of the paper tape processing. And it wouldn’t be Dijkstra if he would not illustrate this shortcoming with a great metaphor.

But now a curious problem arises: the terminal Record XXX Mark which has been stored is indistinguishable from previous Record Marks which might have been read from the tape, and therefore the machine is faced with a problem that shows a striking resemblance to the prototype of an improper algorithm: a man asking the way and getting the answer “You go straight on and turn to the right just before the last steel bridge.”

Dijkstra goes on to criticize the implementation of the variable field addressing method. He proves the implementation in not only very uneconomic (wasting memory – “cores”), but also severely limiting memory management. So severe that he questions the intelligence of the designers of the computer.

I always wonder whether the designers of such machines have been aware of the restrictive consequences of the technique in question; if so, it is hard to respect their conscious decision to stick to it, if not, are they the people that should have been designing machines? I always wonder……

Looking at these shortcomings they seem quite hilarious, but these were the early days of computing.

Dijkstra concludes his review with a final scathing verdict. Not only the buyers must have been totally ignorant to have bought such a machine, also the manufacturer is to blame.

As the reader will understand, my recent study of the IBM 1620 has been a shocking experience: I knew that it was a rather small machine but I had never suspected that it would embody so many basic blunders. Personally, I cannot undergo such an experience without asking myself what its morals are.
One of the facts we have to face is that this machine, despite of its poor qualities, has been bought or rented. Either the customer is incompetent to judge what he is buying, or the contracts are signed by the wrong persons; in both cases the conclusion is that the fact, that other people have chosen a particular machine, is no guarantee whatsoever as far as its quality is concerned.
…
The next fact that we have to face is that this machine, despite of its poor qualities, has been produced, in this case even by a big firm with a long and considerable experience. The straightforward conclusion is, that nor the size nor the experience is a guarantee as far as the quality of the product is concerned. Well, we can think of various explanations for this apparent inconsistency, but the most obvious explanation predicts still more blunders in the more ambitious and more complicated products of the manufacturer in question.

Thank you very much. There you go, IBM.