Friday, April 1, 10pm
See Assignment 9 on Canvas for the Github Classroom link.
This is a pair assignment, but you can work alone, if you so choose.
Submit the contents of your repository via Gradescope. See Deliverables below for what to submit. If you are working with a partner, do not forget to include their name with the submission.
There will be no autograder for this assignment ahead of the deadline. Read the requirements and run tests locally.
For this assignment, we will write a safer and more efficient version
of the memory allocator from Assignment 7.
Our goal is to get performance closer to that of the actual
malloc, while making it safe for use by multiple
threads.
mmap to Allocate Page-sized
BlocksmmapFor the basic allocator implemented in Assignment 7, you were asked to use the sbrk function/system call to change the size of the heap. This call is not the only way to request memory for our process.
Linux (as well as other modern Unix variants) provides another way to
request memory for a process using the mmap system call. In
general, mmap allows us to map a file or a device into
memory, meaning that any reads/writes within the memory region returned
from a successful mmap call are reflected in the file (more
on this in the file system project). In other words, mmap
allows us to allocate memory from the operating system, backed by a
particular file. On Linux and some other operating systems, we can even
request “anonymous” mappings, meaning that the returned region is not
backed by any file. In this mode, mmap can behave like
malloc.
An “mmapped” region’s size is always aligned along the boundary of a
page.
This means that one constraint of mmap is that allocations with
mmap should be made in multiples the size of a page. Even
if you specify a size that is not a multiple of the system’s page size,
mmap will round up to the nearest page. For example, if our
page size is 4KB (4096 bytes), and we only use 12 bytes in total during
our program’s execution, we have quite a bit of waste! In practice, for
large desktop applications this is not a major issue.
A brief set of slides with some notes on mmap is
provided with the starter code.
Because of concerns about fragmentation, mmap may not
be optimal, especially if a program makes lots of little allocations.
However, mmap has its advantages. It can be very fast
because it maps directly to RAM. Remember, whether we are requesting
memory with mmap or sbrk, at the end of the
day, what we get is just a pointer to a block of memory.
Our first task will be to try to get the best of both worlds. Extend
the allocator from Assignment 7
to use mmap with the following simple heuristic:
mmap.sbrk.Remember that the size of the memory region we get from
mmap will be always a multiple of a page. If you are not
using a full page, you will need to split your blocks
to use the memory efficiently. That is, if there is left-over memory
from a previous mmap when malloc is called,
the allocator should use that block.
Data races can affect memory allocators too. In a multi-threaded
environment, we cannot simply make requests to our malloc
and free functions based on our previous implementation. We
could have a scenario where two or more threads request
memory at the same time, and potentially all allocate the same block of
memory in the heap. This would certainly be unlucky!
Luckily, we have mutexes to enforce mutual exclusion and help protect against data races. Remember, when we use pthread_mutex_lock and pthread_mutex_unlock, this creates a critical section where only one thread that has acquired the lock can execute a section of code, thus enforcing sequential execution over shared data.
Implement locking mechanisms such that, whenever there is an
allocation (malloc or calloc) or deallocation
(free), a lock protects that section of code from being run
by another thread.
sbrk for small
allocations and then mmap for large allocations.mymalloc.c and include
any additional .c and .h files your
implementation relies on. For example, you might want to compile your
helper data structure separately.
Commit the code to your repository. Do not include any executables,
.o files, or other binary, temporary, or hidden files.
Once you are done, remember to submit your solution to Gradescope and do not forget to include your partner.
man pages of mmap,
munmap, sbrk, malloc,
calloc, free, realloc, …assert to check that your
assumptions about state are valid.asserts to check expected results. Use our tests for
queue/vector from Assignment 4 as an example.if-else if-else or a multi-case
switch should
be the only reason to go beyond 40-50 lines per function. Even so, the
body of each branch/case should be at most 3-5 lines long.pthread_mutex_lock and
pthread_mutex_unlock to ensure consistency.sbrk calls, especially
if you are getting errors.free function and
calloc as well.memset (if you are using
memset in calloc) that you are not
memset’ing over your block.mallocs and frees, mallocs of a
wide range of sizes to exercise the sbrk and
mmap implementations, and other edge cases.sysconf(_SC_PAGE_SIZE)
to get the OS’s page size. Check the manpage for sysconf to
see which header you need to include.Q: Do I need to munmap the
memory?
A: No–for our allocators we will not worry about
unmapping the memory. In practice our operating system will do this for
us.
Q: Can I just allocate for 10000 cpus? There is no
possible way the instructors can test for that.
A: In the past students have done this, so we manually
check if you statically allocate your lists with some fixed value. Nice
try!
Q: Do I need to merge blocks?
A: It would be good to merge adjacent free blocks
(right after you do a free), but is not required.
Q: If you need to split a block but the amount of
remaining memory in the block is less than the amount of memory of a new
block (which we need to split the remaining memory into a new block),
what should we do?
A: In this case you do not need to do anything, that is
an acceptable amount of fragmentation to live with.