🚀 go-pugleaf

Andy Newman (andy@research.canon.oz.au) wrote recently about his
involvement with a project that developed a Dynamic Memory Allocator.

I liked his account of the memory allocation procedure - and his honesty
about its non-adherence to the occam usage checking rules!

I have one comment to add.  The parallel process in the middle (the
allocator process) can very easily become the performance bottleneck of
the whole of the rest of the system, since it queues up requests and
responds to them serially.

Apart from the problem of distributing permissions to access memory blocks
of varying sizes, one might consider implementing such an allocator with a
little extra buffering.  This would have the effect of eagerly outputting
(in parallel) a permission token to each process that it serves.  Only
when a process accepts its token does the allocator reschedule and send it
another one.  Returned tokens are processed along a different set of
channels which are quite separate from the first set.  Think of the
allocator and the client processes as each being separated in both
directions by small FIFOs, and notice the reduced latency that this
provides.  Obviously, more tokens will be in transit at any time, and the
scheme will use its memory pool less effectively - but the benefit could
be that the system runs rather faster.

A similar benefit could be gained when implementing the TCP/IP
communications protocol, if one has also decided to use the 'mbuf' memory
allocation scheme suggested in its specification.  In this case, and under
heavy network loads, the allocator will be very busy and the overhead
could be quite noticeable.  Of course, this shared memory model might not
be the best choice these days, anyway!


Roger M.A. Peel
Department of Electronic and     Phone : +44 483 509284   (0483 from UK)
      Electrical Engineering       Fax : +44 483 34139
University of Surrey             Telex : 859331
Guildford                        JANET : R.Peel@uk.ac.surrey.ee
Surrey  GU2 5XH                   UUCP : ...mcsun!ukc!ee.surrey.ac.uk!R.Peel
United Kingdom


-- 
Roger Peel