DOCUMENT ID:  1536-02

SYNOPSIS:     Memory Allocation Strategies           

OS RELEASE:   2.x      

PRODUCT:      Solaris x86

KEYWORDS:     memory buddy allocator           


DESCRIPTION: 

A brief understanding of how Solaris handles memory.         


SOLUTION:

Memory Allocation Strategies

To satisfy a memory request, the memory allocator can choose one of
three strategies for deciding which free block to allocate:

*  first fit - in this case, the memory allocator  searches the freelist
   for the first block that is big enough to satisfy the  request.  This
   has the advantage of being very efficient, and is used in UNIX System
   V Release 3 implementations.

*  best fit - with this  method,  the  memory  allocator  allocates  the
   memory  segment with the size closest to the  required.  This has the
   advantage  that the chunk of memory  left over  will be the  smallest
   possible, so memory wastage is minimized.

*  Worst fit - in this case, the memory allocator  allocates the largest
   chunk of memory  available  to it in order to  satisfy  the  request.
   This  seemingly  strange  choice  has the  benefit  that the chunk of
   memory  left over will be quite  large -  possibly  large  enough  to
   satisfy another memory request.

An alternative scheme is the buddy system.  In this system, allocated
block sizes must be to the power of 2 (i.e.  4, 8, 16, 32 bytes and so
on).  There is also a minimum allocation size, say 8 bytes.  Blocks are
manipulated in pairs; each block has a partner or buddy (an American
colloquial term meaning "friend" or in some circumstances, "foe"!).  A
memory pool starts out as a fixed size - for example 4096 bytes. 
Associated with a pool is a bitmap which represents the allocation
status (or the availability) of each minimum sized block in the pool. 

In order to allocate a block, larger blocks are repeatedly split in half
until a block of the correct size is yielded.  For example, suppose a
request is made for a 32 byte block, the allocator takes the 4096 byte
block and splits it into two blocks each measuring 2048 bytes.  The
first block remains free, and the second is divided into two 1024 byte
blocks, and so on, until a 32 byte block is yielded, which is allocated
to the caller - its partners (or buddy's) block of 32 bytes remains
free.  the bits representing the allocated block are then configured in
the bitmap.  A subsequent request for 32 bytes would take the free 32
byte block, which is the buddy of the original.  If a subsequent request
was made for 64 byte block would be used instead. 

When the initial 32 byte block is freed, the memory allocator checks if
its buddy is free.  If it is, the 2 blocks are coalesced into a single
64 byte block and the process continues, possibly resulting with the
original 4096 byte block.  Text starts here. 


DATE APPROVED: 10/18/95