[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Deadlock free routing

Øyvind Teig wrote:
Deadlock free routing

We have a discussion about deadlock-free routing.

Sirs                                           26 June 1997

In order to guarantee deadlock-free routing:

Q1. What is the relationship between how many buffers we need
    and the blocking characteristics of application-code?

My first reaction would be to refer back to Peter's High Level Paradigms paper of WoTUG 19 (?) and to the various forms in which Jeremy Martin's work has been published.

Briefly: Client-Server networks cannot deadlock if they are free of cycles; IO-Par and IO-Seq networks are also deadlock free. (Other networks may or may not be deadlock free.)

One of the exciting corollories of these theoretical results is the rather counter-intuitive discovery that less buffering is needed. This is interesting because most informal approaches (such as Schlaer-Mellor - admitedly an analysis technique but one involving communicating objects) rely on large buffers to operate correctly. Often what happens when buffers run out is ill-defined.

It is difficult to have really large buffers in occam because there is no support for virtual memory. It's just as well that deadlock freedom can be had with no buffering or just a little buffering of fixed-size - this takes less memory and probably executes more efficiently too. :-)

Right. Time to stop thinking aloud and leave the subject to someone who really knows what they're talking about!

Richard Beton BSc CPhys MInstP
Roke Manor Research Limited
--------- Standard Disclaimer about my own views etc etc --------
Welsh Highland Railway: http://www.whr.co.uk/WHR/WHR.html