Extension of the Next-Fit-Algorithm for memory management in operating systems
Original Publication Date: 2000-Apr-01
Included in the Prior Art Database: 2003-Jul-22
To provide programs with memory space, a memory manager is used to allocate and deallocate memory blocks and handle memory ownership. Frequently, such a memory manager is based upon the Next-Fit-Algorithm as proposed by Andrew S. Tanenbaum in "Modern Operating Systems - Design and Implementation".
- 100 -
Information / Kommunikation
Extension of the Next-Fit-Algorithm for memory management inoperating systems
Idee: Andreas Breu, Munich
To provide programs with memory space, a memory manager is used to allocate anddeallocate memory blocks and handle memory ownership. Frequently, such a memorymanager is based upon the Next-Fit-Algorithm as proposed by Andrew S. Tanenbaum in"Modern Operating Systems - Design and Implementation".
One shortcoming of the basic algorithm is memory fragmentation. In actual settings, thisphenomenon can lead to a total reset of certain systems due to memory allocation failure oflarge memory blocks after a few allocation/deallocation cycles.
To rectify this problem, the following extensions of the basic Next-Fit-Algorithm areproposed:
Upon deallocation of a memory block, the address and size of this memory block is insertedinto a FIFO free list instead of performing a garbage collection by merging with aneighboring free memory block. For practical purposes, it can be useful to hold twodifferent FIFO free lists for blocks smaller and bigger than a certain size. For reasons ofruntime performance, the maximum free list length should not be set too high.
When the memory manager now processes an allocation request, now first the free list issearched for a memory block of matching size. If present, this block is allocated, else theconventional allocation method is applied.
The heap is implemented as a doubly linked list. Thereby it is possible t...