This document has not been added to the Gist index due to insufficient English content. You can find this document, and others like it, by searching the Prior Art Database Express index.

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

IP.com Prior Art Database Disclosure
IP.com Disclosure Number: IPCOM000017257D
Publication Date: 01-Apr-2000
Find Similar Download

Publishing Venue

Siemens Disclosure Journal

Related People

Andreas Breu - Author
Munich

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". One shortcoming of the basic algorithm is memory fragmentation. In actual settings, this phenomenon can lead to a total reset of certain systems due to memory allocation failure of large memory blocks after a few allocation/deallocation cycles.

Copyright

Siemens Technik Report Jahrgang 3 Nr.7 April 2000

Language

German

Country

Germany

Document File

1 pages / 13.4 KB

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

First page image
The Find Similar feature is not available for this document.
We are pleased to offer a download of this document free of charge.
Files available for download:
  • a representative PDF of the primary file (contains all the relevant information for most users)
  • the full document ZIP file containing the primary file, packaged metadata, and attachments (as appropriate)
To obtain the file, please enter the "captcha" below and click the Download button.
Avoid entering CAPTCHAs! Sign In or Create a Free Account.

Challenge image
  • Please enter letters and numbers only; no spaces.
  • Cannot read this one? Click the image.
  • Difficulty with captchas? Contact us with the URL of this page and we will email it to you.