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.

Turn-in requirements: make your changes to hw8.c only. Your solution will be graded based on performance in a variety of scenarios, some or all of which are already present in main.c.

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.

Like in malloc, make sure you use the free memory to represent the linked list.

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. To implement this, use the boundary tag method used by the standard malloc.

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. For this, use an array of free lists for various sizes.

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