From: johnl@SDFSERV.hac.com (John Lee)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Flushing Devices; C= doco (mutter!)
Date: 8 Jan 93 02:46:33 GMT
Organization: Hughes Aircraft Company, El Segundo, CA

In article <crystal.726440462@glia> crystal@glia.biostr.washington.edu (Crystal) writes:
[...]
>Memory is not all THAT cheap...and with only 2Meg of Fast ram...*I*'ve
>panicked!  This is a VERY important consideration - flushing memory and
>getting things back to an unfragmented state so PageStream doesn't crash.
>*grumble*
>
>A POX on programmers who can't clean up after themselves...(or their programs!)

First off:  yes, a pox on the developers of PageStream who didn't
handle memory allocation errors correctly.

True, the cost of adding more memory is non-trivial for many of us, but
it's not like unflushed libraries and devices greedily hoard memory
from the poor PageStreams that need it.  As said before, the flushing
of those libraries and devices are simple delayed until it's really
needed, when a memory request cannot be fulfilled.  Think of it as a
cheap and simple caching mechanism (which it is.)

As for unfragmenting memory, I don't think flushing to half-dozen or so
unused libraries and devices will do much.  It's really not that big a
deal, but forgive a little discourse as to why this is so.

Keeping memory unfragmented is one of those great complex Black Magic
chores.  It's a tremendously tricky problem when you can't move things
around to compact memory.  For instance, the unflushed libraries and
devices may hold onto large contiguous blocks.  This forces smaller
memory requests to be satisfied with smaller and better fitting blocks
of memory instead of breaking up larger blocks.  Notice that is
can actually _help_ to reduce fragmentation.

"But wait!" you cry.  "What if the memory allocator already implements
a Best-Fit algorithm?"  Always flushing unused libraries and devices
can _still_ increase fragmentation.  A short example will clarify this.

Assume we have one 24 byte free memory block, and 20 byte and 64 byte
blocks tied up in an unflushed library.  None of the blocks are adjacent
and so cannot be coalesced.  We'll allocate memory using the Best-Fit
algorithm.

If flushes are delayed:
    Action                Free Memory,(Unflushed Memory)
    ------                ------------------------------
    Initial Condition     24,(20,64)
    1.  malloc(16)         8,(20,64)
    2.  malloc(8)            (20,64)
    3.  malloc(20)        (flush occurs) 64

we're left with one contiguous 64 byte block.

If flushes are immediate:
    Action                Free Memory
    ------                -----------
    Initial Condition     20,24,64
    1.  malloc(16)         4,24,64
    2.  malloc(8)          4,16,64
    3.  malloc(20)         4,16,44

and we're left with three fragmented blocks.

Of course this is a contrived example, but the point is that keeping
memory unfragmented is a very tough problem.  Since flushing immediately
won't help memory allocation, why not delay it to cache things and
perhaps save a little disk access?

-------------------------------------------------------------------------------
The crew faces deadly GURUs!  Next time on AmigaDOS: The Next Generation.
	+--------+			John Lee
	| HUGHES |
	+--------+			Internet: jhlee@hac2arpa.hac.com	
The above opinions are those of the user and not of those of this machine.