AmigaOS 4.0 New Memory System Revisited

AmigaOS 4.0 New Memory System Revisited

[Virtual Address Space Allocation]
For one, all free resource blocks are held in space-segregated lists, i.e. there is a list for each power-of-two resource group. This makes allocations a lot faster by providing an upper and lower bound for a search. For example, if you want to allocate a block of 2^10 bytes, you can basically skip searching any block below 2^10 bytes in size simply because it won't fit. Similarly, you don't need to search for blocks that are larger than, say, twice the size of the block, since there might still be blocks of a size near to what we need. Size-segregated free lists help narrow down the search, making the search itself faster and the result better in terms of fragmentation.

In addition, the resource maps use the normal object caches for accelerating "small" allocations. Most allocations are below a certain size. For example, the virtual addresses are always allocated in chunks of at least one "page" in memory (4KB). So it's common to allocate blocks of one, two, four, or eight pages. The object caches provide an easy method for keeping these common sizes, making every allocation of these sizes an exact fit, further reducing fragmentation.

/*
This is a great way to handle memory allocation, IMO. It's not quite O(1), but it's certainly faster than your average O(n) algorithms. I'd say it would be O(m/n) where 0 < m < 1 and n > 1. This should also greatly reduce external fragmentation of the VM system.
*/

[Physical Page Allocation]
The de-facto standard in allocation of physical pages is a method invented by Knuth, called the "buddy system". Basically every modern operating system uses it, and AmigaOS4.0 is no exception to that.

Buddy systems are in essence size-segregated free lists (see above). To allocate, the system searches for a free block of at least the size of the allocation. Then, if the block is too large, it's split into two even-sized blocks. These blocks are called "buddies". One block is returned to it's appropriate free list, and the other is considered further, maybe splitting it further until it's size matches that of the allocation.

/*
It appears that AmigaOS favors "best-fit" over "first fit" allocation. Generally speaking, this is the favored approach as you alleviate memory fragmentation at the expense of a few extra CPU cycles. There's nothing worse than having 30% of your physical memory free, but fragmented to the point that no block is able to serve a request.
*/