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