AmigaOS4.0 Memory Allocation  
Page 1 of 3

Back in the old days of the original AmigaOS, the system used to allocate areas of unused memory to new tasks was pretty simple. The size and position of blocks of free memory were kept in a list, and when memory was needed the system would traverse this list until it found a block that was sufficiently large. This block was then split, one part returned by the allocator for use, while the other part (whatever part of the block wasn't needed) was left in the free list. This method served its purpose well enough at the time, but with the increased demands of modern computing - and of course our desire to bring this new version of the Operating System to the cutting edge - AmigaOS4.0 has introduced a better way of doing things.

Memory fragmentation in the old system: In example 1, the new data is succesfully allocated in the first two-byte space available in the list. In example 2, although there is just as much free data space it is too fragmented to allow a contiguous 2-byte block of data to be allocated anywhere in the list
Let us first consider the limitations of the old method. Imagine we have an area of free memory of one megabyte in size, and we allocate all of it in single-byte blocks. Then we free up every second block. In theory the list now offers half a megabyte of free store, but you cannot even satisfy a single request for two bytes, because nowhere in the list is there a block of free memory that is that long. This is of course a very extreme example, but in practice similar situations can arise. This effect is called "(external) fragmentation" - the memory list becomes fragmented in such a way that allocation requests cannot be satisfied.

The second drawback is that the list describing the size and location of areas of free memory can get very long. With long system uptimes the memory list fragments more and more, easily resulting in a very long list of thousands of nodes. For each operation on this list (allocation and freeing a block of memory), it must be traversed. Since there's no telling how long the list might become, there's also no upper limit on how long this operation would take. This makes it unsuitable for systems that require real-time or at least near real-time behaviour.

Copyright © 2005 Hyperion Entertainment VOF. All rights reserved.
AMIGA and its logos are registered trademarks of Amiga, Inc.