🚀 go-pugleaf

In article <44krqn$9qq@vixen.cso.uiuc.edu>,
Steve Peltz <peltz@cerl.uiuc.edu> wrote:
>In article <446ofvINN97n@keats.ugrad.cs.ubc.ca>,
>
>If you, as an application programmer, want to do your own memory management,
>just allocate pointers rather than handles. The only time you have to use
>handles is when dealing with those parts of the OS that need them (and
>typically, those are parts where handles make sense - the object may change
>size, e.g. a region).

Right, we already settled this when Nevin Liber kindly pointed out that
the Mac never uses handles for memory _management_, only for dynamic allocation
that is done on a per process basis independently of other processes. The
MacOS memory management consists of chopping up the physical address space
into partitions whose size is determined before the program is loaded. It's
not a completely unreasonable strategy if you don't have a MMU, though it
fails for any applications whose memory usage is unpredictable, or very
variable (e.g. a multi-threaded server whose load drastically varies with
time).

Handle-based allocation is flexible:  if you don't want the compaction,
you can just put a malloc() wrapper around the allocator routine that
locks everything. Unfortunatley, if you want pre-emptive threading within
one process, and have your threads allocate handles from the same heap,
it's not practical to allow the compaction. If you do, you have to make sure
that each access to a handle is atomic. In other words, as long as you are
using a temporary pointer that was derived from a handle, that handle
either has to be locked, or you have to prevent pre-emption or the
execution of any routine that may bring about compaction.  For instance,
if you are chasing a linked list, you have to lock and unlock each node
in turn.

I have thought of an implementation which would store along with each
allocated node the ID of the thread that allocated it, so that whenever
it is convenient, all of the blocks belonging to a particular thread (or
several threads) can be treated as locked items.  It's a lot of trouble
to go through to eliminate a worst-case allocation scenario, in which N
allocated cells can occupy a (1 + r)N footprint (where the maximum size
of an allocated block is 2^r) [For proofs, see the paper by J.  M.
Roberts, JACM Vol.  18, 1971].  In practice, this won't happen, for it
requires a purposeful allocation strategy carefully designed to foil any
coalescing scheme.  Threading throws in a randomizing element that makes
the worst case even more unlikely than in a single-threaded process.  It
might be worth it to have a thread-safe allocation library that supports
compaction.
-- 
PGP key id is 0xD3C7995D.
Molybdenum 95! Got your ounce of fission byproduct yet?