The banker’s algorithm and refinements thereof

0. Introduction

In this report, the interference between simultaneous programs is discussed, as it arises from the shared use of peripheral equipment. No attention is paid (for now?) to the restrictions that follow from the fact that these different programs must be housed in the same (finite) memory. Our primary concern regarding this interference is its control, i.e., the avoidance of a deadly embrace. Our first consideration applies when there is only a single type of communication device.

1. The banker with homogeneous customers and one currency

A banker (read "installation") disposes of a finite capital in guilders (read "tape readers"). He is willing to lend money to customers (read "programs") under the following conditions:

1. the customer makes the loans for a time-limited finite transaction;
2. the customer must specify in advance the maximum amount of the loan required for the transaction;
3. the customer does not need to immediately draw down this total amount and stick to it until the end; on the contrary, he is encouraged to come ask for more money only when he needs it and to come repay as soon as possible;
4. the customer may not complain when he comes requesting an extension of his loan for more money and hears: "Admittedly your request does not exceed your specified maximum, but at this moment I cannot grant you the requested loan. I will send you a message when I can indeed grant you the loan you requested";
5. the guarantee that this moment will arrive in due time the customer derives from the wisdom of the banker and the fact that his fellow customers are bound by the same requirement, namely, that they, as soon as they have obtained control over the requested amount, continue their business with due speed, i.e., within a finite time come to ask for more, or repay, or terminate their transaction;
6. termination of a transaction, of the banker-customer contract implies that the borrowed amount has been fully repaid. Interest is not calculated.

The primary questions are

1. under what conditions can the banker enter into a contract with a customer who presents himself?
2. under what conditions can the banker, upon a request for (more) money, proceed to payment without running the risk that he, due to deadly embrace, cannot meet his obligations?

To explain the phenomenon of deadly embrace, the following example: A banker with a capital of 8 guilders has two customers A and B, who have both stated 6 guilders as their maximum need. If A and B have both withdrawn two guilders, there is still no problem. If now, for example, A first extends his loan to 3 guilders, that is permissible. However, if B then asks for his third guilder, payment must be withheld, even though there are still 3 guilders in the cash reserve. For if B's third guilder were paid out, there would remain only 2 guilders in the cash reserve. If now A asks for another 3 guilders for his continuation (which he can claim "in due time"), this cannot be given and A must wait; but if B also has reached a stage with his affairs where

if he needs the remaining 3 guilders before he can think about repayment, then the whole group is stuck fast. This phenomenon is called "the deadly embrace" and it is this calamity that the banker must prudently prevent. This paragraph for explanation.

Question a. is easily answered: the banker can sign the contract with every customer who applies if the need stated by the customer does not exceed the banker's total capital.

To answer question b. we introduce some terms:

The banker has a fixed "capital". Each customer specifies his maximum "need".
For each customer it holds that

The current state of a customer is given by his "loan"; initially "loan ≡ 0", for each customer it will always hold

Depending on these two quantities we introduce, for each customer, the "claim", given by

The claim is therefore the amount that the customer may still need to claim for the completion of his transactions.
Finally we introduce the so-called "cash reserve" given by

Of course, "0 ≤ cash reserve" holds.

To see whether the banker can proceed to payment upon a request for more, he investigates the state that would arise if he were to proceed to payment. If this state is "safe", then he proceeds to payment; if this state is "unsafe", then the payment is withheld and the customer is put on the waiting list. It remains for us to describe how he investigates the safety of a situation.

It is clear that the banker, by always keeping the situation safe, can always avoid the deadly embrace. One can also show that as soon as the banker allows himself to be lured into an unsafe situation, the need pattern can develop in such a way that the deadly embrace can no longer be averted.

2. Extension to several inconvertible currencies

The above applies when the mutual interference between programs is limited to "fighting over a type of device", say "tape readers", where one tape reader is just as good as another for us each time. In practice, we were confronted with the fact that programs want to use tape readers, tape punches, card readers, and whatever else. These are inconvertible in the sense that it helps very little if you try to comfort a program that actually needs a tape reader with the message "Bad luck, but I still have a punch for you".

In terms of the banker this amounts to the fact that capital, loan, need, claim, and cash reserve are now expressed not only in guilders, but in more dimensions (francs, pounds, and crowns). The passage in the algorithm 'a customer whose momentary claim does not exceed the momentary value of the amount to be released' should be replaced by 'a customer, of whom no claim exceeds the momentary value of the corresponding cash reserve'. Furthermore, the entire algorithm, including the concept of cash, remains usable without change.