Share
Explore BrainMass

Memory Allocator Based on "Buddy System" Scheme

Implement a simple memory allocator based on the so-called "Buddy System" scheme, that allocates memory in blocks with sizes that are powers of two, starting at a block size that is given as an argument when the allocator is initialized.

* The memory allocator shall be implemented as a C module my_allocator, which consists of a header file my_allocator.h and my_allocator.c. It should provide the functions my_malloc() and my_free(), very similar to the UNIX calls malloc() and free().

* Evaluate the correctness (up to some point) and the performance of your allocator. For this use the given strange implementation of a highly-recursive Ackermann function. In this implementation of the Ackermann function, random blocks of memory are allocated and de-allocated sometime later, generating a large combination of different allocation patterns.

* Write a program called memtest, which reads the basic block size and the memory size (in bytes) from the command line, initializes the memory, and then calls the Ackermann function. It measures the time it takes to perform the number of memory operations. Make sure that the program exits cleanly if aborted (using atexit() to install the exit handler).

* Use the getopt() C library function to parse the command line for arguments. The synopsis of the memtest program is of the form

memtest [-b <blocksize>] [-s <memsize>]

-b <blocksize> defines the block size, in bytes. Default is 128 bytes.
-s <memsize> defines the size of the memory to be allocated, in bytes.
Default is 512kB.

* Repeatedly invoke the Ackermann function with increasingly larger values for n and m (be careful to keep n <= 3; the processing time increases very steeply for larger values of n).

* Make sure that the allocator gets de-allocated (and its memory freed) when the program either exits or aborts (for example, when the user presses Ctrl-C).

Please see the attachments for more details.

I have been tasked with the attached problem, and do not seem to make any progress.

Attachments

Solution Preview

Please unzip the attachment 524930.zip and type 'make' at command prompt once inside the unzipped directory.

This solution does not use C pointers but instead uses index into the managed memory pool (char array) to serve as the pointer. Here are some of the suggested improvements you can explore.

1. See if using C pointers helps you reduce some linked list management code.
2. If you are using C pointers, you can explore using circular linked list with respective free lists array cell also forming part of this circular list (so that there will always be at least one node in circular linked list) which is bound to significantly reduce the linked list management code.

3. This solution uses standard buddy memory allocation scheme where some management information is also stored in a header prepended to allocated memory ...

Solution Summary

This solution does not use C pointers but instead uses index into the managed memory pool (char array) to serve as the pointer. It uses standard buddy memory allocation scheme where some management information is also stored in a header prepended to allocated memory space. However it is different in respect that it just uses two bytes for storing the buddy status of the block (free/inuse) and the size (stored as power of 2) of the block used to satisfy the allocation request.

Code is fairly commented to help you understand what is being done there. Solution also suggests some improvements you can explore.

$2.19