malloc in nos

[mitel!Software!perryd@uunet.UU.NET (Dave Perry)]

Our packet switch was showing signs of low memory (refusing connections),
despite the fact that there was lots of memory available.  The current
theory is that this was because memory was so badly fragmented that an
allocation of sufficient size could not be made.

The storage allocator is based on one that appeared in the text by K&R.
The free list is actually a ring, and when a new request for memory is
made, the search starts at the last allocated block.  K&R says that this
strategy is used to keep the free list more "homogeneous".

My question is whether this is always desireable. I tried modifying malloc
so that it always starts at the base of the free list. This produced the
expected effect, ie., small allocations seem to group at the beginning
of the free list, and larger ones group toward the end. In practice I
have observed that almost all of available memory is usually in a single
block at the end of the list.

It seems to me that this behaviour would help avoid the fragmentation
problem, perhaps with a performance penalty since the list must be searched
starting at the base each time.

Can anyone share some insite on this topic?

Dave
VE3IFB