TWiki
>
CS385spring12 Web
>
Homework7
(2012-03-08, Main.jakob)
(raw view)
E
dit
A
ttach
---+ Homework 7: 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. *NOTE:* The template makefile tells gcc to compile in 32-bit mode, even if you're on a 64-bit system. If you get a complaint about missing stubs-32.h, just run =sudo apt-get install libc6-dev-i386=. *Turn-in requirements:* make your changes to hw7.c only.Your solution should use only =sbrk()= to request and release memory. This means you cannot use other built-in memory allocation functions like =malloc()=, =calloc()= or =mmap()=. 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. ---++ Some hints * *WARNING:* this will not work on OS X. the brk() system call does not exist on OS X, and is emulated in userspace. This creates a 4 Mb limit on the break size. * Sometimes, the "best fit" from the free list is still not a very good fit (could be several megabytes off if you're unlucky, especially with a coalescing solution). In that case, simply split your best fit chunk into a great fit, and a newly initialized leftover chunk, that you then add back to the free list. * When you have a free chunk adjacent to the break, call sbrk with a negative argument to lower the break. Be careful to remove the "adjacent" chunk from your free list! * Use gdb to debug your segmentation faults! * If you get a segfault that only happens on the console, and not in gdb, turn on "core dumps" with the command "ulimit -c unlimited". You can then do a retrospective debugging session with gdb thus: "gdb hw7 core", which shows you the status of the program as it crashed. ---++ Example of "good performance", full hw7 implementation output <verbatim> ./hw7 987987 Simple alloc/free, alloc/free cycle: 0, timediff:237 Coalescing free and splitting mymalloc: 0, timediff:29 After freeing coalesced blocks: -10320000, timediff:7 Random malloc and free sequence: 0, timediff: 698 </verbatim> with 1000 16-byte spaced lists: <verbatim> Simple alloc/free, alloc/free cycle: 0, timediff:291 Coalescing free and splitting mymalloc: 0, timediff:67 After freeing coalesced blocks: -10320000, timediff:7 Random malloc and free sequence: 0, timediff: 822 </verbatim> with a single list: <verbatim> Simple alloc/free, alloc/free cycle: 0, timediff:239 Coalescing free and splitting mymalloc: 0, timediff:29 After freeing coalesced blocks: -10320000, timediff:7 Random malloc and free sequence: 0, timediff: 2491 </verbatim> without coalescing or lowering the break: <verbatim> Simple alloc/free, alloc/free cycle: 100080000, timediff:332 Coalescing free and splitting mymalloc: 9216072, timediff:33 After freeing coalesced blocks: 8192064, timediff:0 Random malloc and free sequence: 497408, timediff: 2535 </verbatim> with coalescing, but without splitting: <verbatim> Simple alloc/free, alloc/free cycle: 0, timediff:230 Coalescing free and splitting mymalloc: 8192064, timediff:29 After freeing coalesced blocks: -10320000, timediff:7 Random malloc and free sequence: 0, timediff: 666 </verbatim>
E
dit
|
A
ttach
|
P
rint version
|
H
istory
: r5
<
r4
<
r3
<
r2
<
r1
|
B
acklinks
|
V
iew topic
|
Ra
w
edit
|
M
ore topic actions
Topic revision: r5 - 2012-03-08 - 20:34:15 - Main.jakob
CS385spring12
Syllabus
Lecture Notes
Homeworks
Discussion Board
Subversion help
Additional Material
ABOUT US
Our Department
Recent News
Contact Us
ACADEMICS
Prospective Students
Undergraduate
CS Minor
Graduate
Courses
RESEARCH
Overview
By Faculty
Labs
PEOPLE
Faculty
Adjuncts
Staff
Students
Alumni
Copyright 2016 The Board of Trustees
of the University of Illinois.
webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF