Minix 3/Memory Management

Minix2 is supposed to have a 'simple' memory manager, because a) it is intended for a single user, and b) it is supposed to run on an 8088, which does not support virtual memory. The memory manager has a posix memory interface - i.e. it is used when the functions fork() or exec() is called.

Here is some discussion about some terms bandied about memory managers.

1. First fit algorithm a memory manager allocates memory so the most basic parameter would be the requested size. The mm can search a list of non-allocated memory blocks , until it finds a contiguous block of unallocated memory that is larger than the requested size, split it into a block for use of the requested size, and a smaller unused block which is the rest of the block. Then the requested size block is returned for usage.

The algorithm "best fit", searches a list of unused blocks , until the nearest larger or equal sized block is found, and returned , but the problem with this algorithm is that the unused part of the block that is returned to the free list tends to be small and useless.

One important aspect of any free memory allocation algorithm, is that once the used block is returned, it must be compared with adjacent blocks to see if they are also unused, and merged with the block before and /or after to keep the free block sizes as large as possible. If this is not done, free block sizes quickly become too small to use for some requests.

This requirement makes the "quick fit" algorithm , more complicated to implement than simple "first fit" : quick fit is where lists of free blocks are kept according to size range , but when blocks are returned, these lists aren't useful for finding the adjacent free blocks, which may be listed in a different size range.

There is also "worst fit", where the largest free block is chosen always.

First three algorithms are described in The Art of Computer Programming, vol. 1 by D.E. Knuth.