Browse Prior Art Database

Extension of the Next-Fit-Algorithm for memory management in operating systems

IP.com Disclosure Number: IPCOM000017257D
Original Publication Date: 2000-Apr-01
Included in the Prior Art Database: 2003-Jul-22
Document File: 1 page(s) / 13K

Publishing Venue

Siemens

Related People

Andreas Breu: AUTHOR

Abstract

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".

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 61% of the total text.

-   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...