Description
In this project, you will implement your own versions of the user-space memory
management functions malloc() and free(). User-space memory management
has deep similarities with operating system memory management that we are
covering in class. To distinguish your functions from malloc() and free(), you
will call them psumalloc() and psufree(). Although your functions will be
much simpler than the system’s functions, it is our hope that they will still help
you appreciate several complexities of user-space memory management. Somewhat less directly, perhaps, they will also help you better appreciate operating
system virtual memory management (VMM) that we are covering in class. After
testing your code, you will carry out simple experiments to measure specified
performance metrics. You will describe your design and the outcome of your
experimental evaluation in a short report.
2 Background
A memory allocator performs two main tasks:
• When needed by the process, it asks the operating system VMM to expand
the process heap by calling either sbrk() or mmap(). Obviously, this
occurs at the granularity of a page (make sure you understand this clearly).
Similarly, it also releases back to the OS VMM pages that are not needed
anymore.
• It carves out objects requested by the process from this memory. This
involves managing a free list of memory “regions” and finding a contiguous
chunk of memory among one of these free regions that is large enough for
the user’s request. By a region we mean a contiguous portion of memory
(virtual or physical? Think!) among the pages assigned to the process.
When the user later frees memory, it adds it back to the free list. Notice
that this free list is a data structure that itself resides in the process heap.
The memory allocator is provided as part of a standard library and is not part
of the OS. That is, the memory allocator operates entirely within the address
space of a single process and knows nothing about which physical pages have
1
been allocated to this process or the mapping from virtual addresses to physical addresses. Make sure you understand this clearly. Recall the following
definitions of malloc() and free():
• void *malloc(size t size) allocates size bytes and returns a pointer
to the allocated memory.
• void free(void *ptr) frees the memory space pointed to by ptr, which
must have been returned by a previous call to malloc() (or calloc()
or realloc()). If free(ptr) has already been called before, undefined
behaviour occurs. If ptr is NULL, no operation is performed.
You will begin by reading Chapter 17 of OS3 which describes how a generic userspace memory allocator is implemented. Reading till Section 17.3 should suffice
for your purposes. The most important concept to understand is the role of the
data structure called the free list. You will find the examples spanning Figures
17.4-17.7 particularly enlightening. Once you have understood this material
well, you will be ready to begin your design and implementation.
3 Design and Implementation
You will implement your own memory allocator for the heap of a user-level
process. Here are some simplifications you will make in your design (compared
to what a real memory allocator does):
• When requesting memory from the OS, you will use the system call mmap().
Use man pages and/or online resources to learn about mmap(). Chapter
17 presents a small example usage of mmap() that you might find useful.
In a later segment of the course on IO virtualization, if time permits, we
will learn about some aspects of how the OS implements mmap(). An altenative way for requesting additional pages from the OS would be based
on using sbrk() which we will not be using – it is arguably a bit more
complex than mmap() and this complexity is only a distraction as far as
our main interests in this project go.
• Although a real memory allocator generally requests additional memory
from the OS in a “piecemeal” manner (i.e., only when it can’t satisfy a
request from the user), your memory allocator will call mmap() only one
time (when it is first initialized).
• You are free to use any data structures you want to manage the free list.
You must think about at least 3 different data structures (as we did in
class when discussing how to implement the list of ready/runnable processes/threads for a CPU scheduler) for managing the free list, compare
these for different relevant operations in terms of their runtimes, and describe this comparison in your report. Your data structure may not be an
array (see more below). If you choose to implement a data structure that
is not the best as per your own comparison, you must justify your choice.
• Finally, you will implement the following two policies for choosing a chunk
of memory to satisfy an allocation request: (i) best-fit and (ii) worst-fit.
These policies were mentioned briefly during Lecture 11. You can find descriptions of these policies in Section 17.3 of OS3.
2
We are now ready to specify the functions you will implement. These are:
• int psumeminit(int algo, int sizeOfRegion): This function is called
one time by the process that wants to use your memory allocator. algo
represents which memory allocation policy should be used – 0 for best-fit
and 1 for worst-fit. sizeOfRegion is the number of bytes that you request from the OS using mmap. algo & sizeOfRegion are defined as
macros in the code we are providing you – see more below about ”workloads.” Note that you need to use this allocated memory for your own data
structures as well; that is, your infrastructure for tracking the mapping
from addresses to memory objects has to be placed in this region as well.
Finally, the return value should be 0 upon successful completion of all the
function’s tasks and -1 otherwise.
IMPORTANT: If you call malloc(), or any other related function, in any of your functions, you will get a 0 grade. Similarly,
you will get a 0 grade if you use arrays for implementing your
free list or other related data structures. If in doubt, ask the
teaching staff immediately.
• void *psumalloc(int size): This function is similar to malloc(). It
takes as input the size in bytes of the object to be allocated and returns
a pointer to the start of that object. The function returns NULL if there
is not enough contiguous free space within sizeOfRegion allocated by
psumeminit() to satisfy this request.
• int psufree(void *ptr): This function frees the memory object that
ptr points to. Just like with the standard free(), if ptr is NULL, then no
operation is performed. The function returns 0 on success and -1 if ptr
was not allocated by psumalloc(). If ptr is NULL, also return -1.
• void psumemdump(): This function is for your own debugging purposes.
When invoked, it prints information about free regions of memory on the
standard output or into a file (whichever you prefer).
You must provide these functions in a shared library named psulibmem.so.
You will easily find good online resources on how to create such a library if you
are not already familiar with this.
4 Experimental Evaluation
After testing your code, you will carry out a small experimental study of the
performance of your memory allocators on 2 “workloads” (i.e., test programs)
that we will provide. Below we describe these workloads.
4.1 Workloads
Each workload will be a small program that will allocate/deallocate memory
using your functions. There are only two kinds of modifications you may make
to a test program: (i) insert calls to psumemdump() for your own debugging,
and (ii) code for performance measurement purposes (described in Section 4.2).
3
Keep in mind that we will evaluate your code using the unmodified workloads
that we provide (and not workloads modified by you).
The workloads vary the size of their requests according to two different patterns:
• small: this patter consists of requesting all small objects (the sizes are
random, distributed between 8 bytes and 256 bytes).
• mixed: this pattern consists of alternating between requesting a small
object (64 bytes) and a large object (64 KB).
Each workload consists of 100 iterations. In each iteration, the workloads vary
the order of psumalloc and psufree invocations as follows. They allocate 100
objects and then free about half of the objects (each chosen with a probability
0.5 independently of others). Upon finishing all iterations, they free all remaining objects. Combining these 2 workloads with our two allocation policies
(best-fit and worst-fit), you will have a total of 4 experiments.
4.2 Measurements
You will create a mapping of sizeOfRegion bytes via your call to mmap. For
each of the workloads, you will present the following measurements in the form
of graphs or tables in your report:
• average, median, 25th percentile1
, and 75th percentile of psumalloc()
and psufree() response times separately for best-fit and worst-fit.
To measure response time, you will record the times before and after
calling the function and take the difference.
• number of occasions when a psumalloc() could not be satisfied due to
lack of enough memory.
• number of occasions when a psumalloc() could not be satisfied due to
internal fragmentation.
5 Submission and Grading
Same as PA2, PA3 will be done in groups of 2. A group may choose either members repository as their workplace. Do remember to list both members names in
all files you submit (including your report). Your project won’t be graded if you
don’t have a name on your report. You are supposed to submit your assignment
with your private GitHub repository. Therefore, accept the invitation to access
your private repository. If you still need instructions for working with git or
adding your teammate to your repository, refer to the included Git manual file.
The TAs will grade you by inspecting your code, running some test cases for
your code, and by looking at your report.
1A percentile (or a centile) is a measure used in statistics indicating the value below which
a given percentage of observations in a group of observations fall. For example, the 20th
percentile is the value (or score) below which 20% of the observations may be found.
4
5.1 Code and Report
You must push and commit to your private repository all your source files (*.c
and *.h) and report file and a Makefile that the TAs will use to compile your
code. You should also create a short README with instructions on how to
compile and run your code. Note that you will not write a main() function
for the code that you submit. You should implement one for your own testing,
of course. The TAs will use automated scripts to link the library created by
compiling your code against our test programs and then run these.
The quality and performance of your code will make up 60% of your grade.
Roughly, the TAs will be looking at these aspects when assigning your grade:
(i) the quality and clarity of your implementation (complemented by reading
your description in your report), (ii) adherence to guidelines above about not
using global arrays for free list implementation and not making use of system’s
malloc() or related functions, and (iii) correct treatment of the workloads. The
remaining 40% of your grade will be based on a short included report file which
contains your name(s). Your report should have the following two components:
• A few simple paragraphs describing the overall structure of your code
and any important structures. For example, include a brief description
of the data structures you use to map between addresses and memory
objects. Describe your thoughts comparing 3 different data structures
for implementing the free list, and why you picked one of these over the
others. Describe how you handled any ambiguities in the specification.
Finally, list any features that you did not implement or that you know are
not working correctly.
• Graphs or tables reporting your experimental findings. If you have an
explanation for some of the behavior you observe (e.g., why best-fit outperforms worst-fit for workload X), describe it.
6 Some final remarks
• IMPORTANT: We will be comparing your codes for similarity
and all parties involved in copying will receive a 0 grade on PA3
at the very least and an F grade in the course in the worst
case. Outsourcing your code to an external entity is considered
cheating. You will also be reported to the college of engineering
disciplinary committee.
• It is very important that you start early. You will very likely find this
project to be more difficult (or at least more time consuming) than PA1
and PA2. Please seek as much as help as you need from the instructor
and the TAs.
• Good luck and happy coding!
5