Homework 8: DIY Memory Allocator

User programs typically allocate memory using the standard library functions malloc() and free(). These are userspace functions, which both use the sbrk() system call to request and release memory allocated to the process.

In this homework, we create an alternative memory allocator, which provides the functions myalloc(), and myfree(). The performance of your allocator will be measured in terms of program runtime and fragmentation.

Basic mymalloc() and myfree()

Based on the homework template, support the re-use of free()'d allocations in subsequent calls to mymalloc(). You may want to use a linked list to represent free allocations here, as we don't worry too much about performance.

Coalescing myfree()

Improve your myfree() implementation to support the coalescing of two or more small free()'d allocations, so that a subsequent larger mymalloc() can re-use the freed memory.

For example, say I free 4 consecutive allocations of 4 bytes each. A later mymalloc(16) should be able to reuse the free'd memory.

Faster mymalloc()

When the number of free allocations is large, every call to malloc potentially takes a long time. Change the way you represent free allocations to speed up the process. You may want to use either use a balanced tree, or a number of linked lists for various sizes.

Edit | Attach | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2011-03-11 - 23:10:09 - Main.jakob
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF