Information streams sharing a finite buffer

Copyright Notice

The manuscript

EWD329: Information Streams Sharing a Finite Buffer was published as

Information Processing Letters 1: 179-180, copyright © 1972. It is reproduced here by permission of the publisher, Elsevier Science. Single copies of the manuscript may be downloaded and printed for the reader's personal research and study.

Inforation: Strens Sring a Finite Buffer.

Edsger W.Dijkstra

Department of Mathematics, Technological University Eindhoven, the Netherlands

(synchronization, buffer sharing, individual starvation)

The purpose of this letter is twofold: firstly to illustrate the usefulness of the notational technique of the "conditional critical section" as developed by C.A.R. Hoare and P. Brinch Hansen, secondly to publish an algorithm that, although trivial, is extremely useful when you need it.

We consider a number of producer/consumer pairs, where pair $i$ is coupled via an information stream containing $n_i$ portions. We assume all portions to be of equal length and the finite buffer that should contain all portions of all streams to have a capacity of "tot" portions.

In the technique of the conditional critical section we declare a composite variable "v" consisting of all the $n_i$ (initially = 0) and the variable $f$ (initially = tot).

To synchronize producers and consumers such that

a) $0 ≤ n_{i}$ for all $i$

$\sum_{i}n_{i}≤ \mathrm{tot}$

we can consider the solution

$\text{conclusion}_i: \text{with} v \text{when} n_i > 0 do$

begin $f:= f + 1$ ; $n_i := n_i - 1$ ; etc end

production: with v when f > 0 do

begin $\mathfrak{n}{\dot{\mathfrak{i}}} = \mathfrak{n}{\dot{\mathfrak{i}}} + 1$ . $f:= f - 1$ ; etc end

where the rules of the conditional critical section imply that

'； thanks to the clause "with v" at any moment in time only one of the processes will execute the section following it 2) if the condition following "when" is found satisfied, the statement following its "do" will be executed in the same critical section 3) if the condition following "when" is found not satisfied, the process in question will be put to sleep, i.e. attached to a queue associated with $v$ . 4) after completion of a critical statement the corresponding queue will be

Ianned and if one of the conditions is found fulfilled the corresponding process will be woken up and will be allowed to perform its critical statement. (In the above text "etc" stands for the actual removal or addition of a portion.)

The above solution, although guaranteeing the inequalities a) and b) has two undesirable properties:

1) when the effort of waking up takes place on the "honest" basis:"first come, first served", in the case of total output limitation a slow consumer will eventually slow down all other consumers to its slow speed 2) in the case of a stopped consumer, its information stream may occupy the total buffer and thereby block all other streams.

Let $r_i (≥ 1)$ be the minimum number of portions that the buffer needs to accommodate for a smooth processing of stream. With the same composite variable "v", consisting of all the $n_i$ (initially = 0) and $f$ (initially = tot - $\sum_{i} r_i$ ) ≥ 0, the solution

\text {c o n s u m p t i o n} _ {i}: \text {w i t h v w h e n} n _ {i} > 0 do

\begin{array}{l} \text {b e g i n} \text {i f} n _ {i} > r _ {i} then f := f - 1; \ n _ {i} := n _ {i} - 1; \text {e t c} \ \end{array}

end

\text {i n d u c t i o n} _ {i}: \text {w i t h v w h e n} n _ {i} < r _ {i} or f > 0 do

\text {b e g i n} n _ {i} := n _ {i} + 1;

\underline {{i f}} n _ {i} > r _ {i} \underline {{then}} f := f - 1;

etc

end

haranteess $0≤ f = \mathrm{tot} - \sum_{i}\max (r_{i},r_{i})$ and the two objections don't hold anymore. As a matter of fact, the absence of the danger of individual starvation for any of the streams is now independent of the particular waking up strategy. The extension to portions of different size is straightforward.