Phase 1 Due: Wednesday, Oct 1 @ 11:59 p.m.
Phase 2 Due: Wednesday, Oct 8 @ 11:59 p.m.
Your mission is to use the system call sbrk to implement your own versions of malloc and free. The exercise should make you think about memory allocation and deallocation, including defragmentation. (Relocation of virtual addresses in memory is another important memory management concept, but we will tackle that idea in class, later.)
Before you start work, you should complete a set of readings about memory:
Without looking too hard, you can also find various implementations of malloc and free online. I don't recommend doing so; you'll miss the opportunity to think through the problem, which is the point of the assignment. Also, since I know that solutions are online, you have to figure I will use software to check for similarity with various sources.
Do not run your code for this exercise on cs.utm.utoronto.ca or any other shared server. If you allocate a huge amount of memory, you could decrease performance for other users. Instead, run your program on DHrrrrPCxx, where rrrr is the room number of a lab in Deerfield Hall and XX is the PC's number (from 01 to ~30). Before running your code, you may wish to use the w command to determine who is on the system and what the load on the system is. To be polite, don't slam a system that someone is using.
The starter code consists of a file that will eventually contain two memory management functions called mymalloc and myfree and a test program that demonstrates how your mymalloc and myfree functions will be invoked. Note that the test program uses pthreads, so you will need to include the pthread compilation flag. You may modify this test program for testing purposes, but we will use our own test harness, so make sure your mymemory.c works with our version of the test harness!
The test program loads "traces" which are text files containing a series of malloc and free operations to perform. Here are two example traces: a short one and a larger random trace. You will want to create additional traces for testing. In particular, consider various access patterns (mallocing large items, freeing every other malloc, and then mallocing smaller items, for example) that might cause interesting memory usage if your allocator does not allocate space nicely or coalesce it. To help you generate traces, here is a python script that generates random traces.
This assignment consists of two phases: a deadline for a functional implementation and a deadline for a more efficient (but still functional) implementation. In addition to the submission of code, each phase also contains a related written component. This rubric describes the weight of each component and outlines how each component will be evaluated.
For the first deadline, your goal is to implement a basic version of mymalloc and myfree implementations that operates in a multi-threaded environment. Your implementation should be able to allocate as much memory as sbrk will give you, to free pointers returned by the user, and to reallocate freed space. However, your implementation does not need to coalesce free space, nor do you need to spend time making your implementation more space or time efficient. In short, your submission will be evaluated on its ability to allocate significant amounts of memory, reclaim parts of it, and reallocate the freed memory.
You may find, if you decide to allocate all of memory, that your program allocates an incongruous amount of memory. Most OS implementations will happily allocate memory to you but won't necessarily actually allocate physical memory unless you write to the allocated memory. This means that you should write to every byte of memory you receive in order to guarantee that it's actually being materialized. Be very careful if you do this. Your system will begin swapping heavily, and you could crash applications that try to allocate memory. Run this kind of test on your own system only.
Once you are confident in this phase, turn it in (commit it to your repository) before moving to the next phase. In addition to your code, submit a README file (in txt or pdf format only, please) that includes two paragraphs (no more than 250 words) that describes (1) the data structures you use to track each memory allocation and (2) the algorithm you use to select which memory to allocate/reallocate.
Once you have a basic working implementation, it's time to consider optimizations. The first step is to implement coalescing of free space. (If a user frees adjacent blocks of size N and M, it should be possible to use that space to allocate a block of size up to N + M.) The second step is to consider how to reduce the space overhead required to maintain the allocation metadata. The third and final step is to reduce the time required to find the best space to allocate while simultaneously minimizing unusable space. (You should probably allocate space from the smallest available block whenever possible.)
In addition to submitting your code, update your README to include one or two paragraphs (no more than 250 words) that describes the changes you made to improve the efficiency of your malloc and free implementations. Your description should include some justification (specific use cases or traces, for example) that of the design decisions you made.
Your submission this week will be evaluated by comparing it to system malloc and the submissions of your colleagues. We will spend some time in tutorial comparing implementations, so be prepared to discuss the optimizations you've implemented -- and be aware that your implementation will be run "live" to compare its performance to other submissions. The best performing submissions (compared to others in the class) can claim a trip to Starbucks; I'll pay for the maximally-sized beverage for each winner.
Each phase of the assignment should be submitted to your svn repository by the deadline. Don't forget to commit your README (in text or pdf format). We will pull the last commit before the deadline when marking each phase.