Description
1 Introduction
Heap is a segment in a process’ virtual address space. Processes use the heap to keep variable sized objects during their execution. The allocator (heap management) library implements and manages the heap of a process. It allocates a portion of the physical address space (main memory) for implementing the heap. As threads of a process request and return space from the heap, the allocator library serves them through its API.
Basics of the allocator library is described in our main textbook OSTEP, Chapter 17[1]. Here, chunks of free memory are kept in a linked-list called free-list. Moreover, the list itself is implemented inside the heap. So, metadata like next pointers occupy space inside heap as well.
In this PA, you are expected to implement a simple allocator library. You are expected to keep a linked-list as well. However, your linked-list will not occupy space inside the heap. You can safely assume that it is disjoint with the heap. Moreover, your linked list will not just track free chunks but also occupied spaces inside the heap. Details will be provided in the following sections.
Operations of your allocator library will be called concurrently by different threads. Therefore, you need to be careful about data races. However, you are advised to implement a sequential heap manager first i.e., it works correctly when processes have single thread. Then, you add synchronization mechanism to prevent data races. The way to get the best score possible from this PA is to follow the grading section during the implementation such that you implement an item after completing its preconditions.
2 Heap Management Library
The library provides the following API:
- int initHeap(int size): This operation takes the size of the heap in terms of bytes as input and initializes the heap with the requested size. As you will see later, you do not really allocate memory for the heap in your implementation. You just initialize
1
the linked-list that represents your heap layout. Therefore, we can safely assume that initHeap always succeeds for any positive size input and returns 1 after initializing the heap. Lastly, it prints the initial heap layout (see sample runs at the end).
- int myMalloc(int ID, int size): This operation takes ID of the thread issuing the operation and the requested size in bytes as input and tries to allocate heap space of requested size. If there is a free chunk in the heap that can accommodate the request (that has enough space), this operation must succeed and return the beginning address of the newly allocated space. Otherwise, it fails and returns -1. In both cases, it prints whether the operation succeeds or fails and the final state of the heap (see sample runs at the end).
- int myFree(int ID, int index): This operation takes a thread ID and the starting address of the chunk to be freed as input. If this thread has really allocated this chunk, it frees the chunk and returns 1. Otherwise, it returns -1. In both cases, it prints whether the operation succeeds or fails and the final state of the heap (see sample runs at the end).
- void print(): Prints the memory layout (see sample runs at the end).
2.1 State: Linked-List
State of the library consists only of a linked list. The list keeps both free and allocated heap locations. The list is initialized with a single node that represents a free chunk of the size of the heap when the initHeap operation is called. The list should be updated with myMalloc and myFree operations.
The only object library keeps is the list. This means that you will not really allocate memory for the heap itself. This PA simulates the heap. Threads using this library just allocates and frees spaces from the heap. You can assume that they will not really access these locations and perform writes and reads. Therefore, allocating space for the actual heap is not needed.
Nodes of the list has three fields as seen in Figure 1: ID, SIZE and INDEX. The first field is the thread ID that allocated the chunk. Each thread has a unique non-negative ID given to them as input during its generation. If the chunk is free, this field is -1. SIZE and INDEX fields represent the size and the starting address of the chunk, respectively.
| ID | SIZE | INDEX |
Figure 1: A linked list node
Given the state representation above, the API operations should be implemented as follows:
- int initHeap(int size): Initializes the list with a single free node with given input size and start index 0. This operation always succeeds and returns 1. You can assume that the input size will be always positive. Before returning, it prints the linked list (see sample runs at the end).
- int myMalloc(int ID, int size): Your allocator library will implement the first fit approach: It will allocate space from the first free node that has enough space. Here, the first node means the one closest to the head of the list. Once the candidate free node is found, it will be divided into two nodes if it has more space than the requested size. The first node will represent the newly allocated space. The second one will represent the remaining free space. If there is no such candidate node, it will return -1. Otherwise, it will return the start index of the newly allocated node. Before returning, it prints the success info of the operation and the linked list (see sample runs at the end).
- int myFree(int ID, int index): This operation traverses the list for finding a node with the given ID and index. There can be at most one such a node in the list. If it exists, this node is turned into a free node, it merges with the neighbors if they are free as well (see Figure 2 for details of coalescing) and returns 1. Otherwise, the list does not change and returns -1. Before returning, it prints the success info of the operation and the linked list (see sample runs at the end).
- void print(): This operation just prints the list in the format seen in sample runs.
Figure 2: Coalescing. The left column shows the allocated chunk X and its immediate neighbors and the right column shows the same after freeing X and coalescing. A and B denote allocated chunks and shaded regions denote free chunks. In (a) both neighbors are allocated, so freeing X does not need coalescing. In (b) (resp., (c)), the right (left) neighbor or next (previous) node is free as well. So, after freeing X, both nodes become free and they need to be merged into a bigger single node. In (d), both neighbors of X, previous and next nodes in the list, are free. Therefore, after freeing X, a single free node replaces the previous three nodes.
2.2 Taming Concurrency
So far, we have described operations of the allocator library as if they execute atomically in isolation. However, multiple threads might call myMalloc and myFree operations concurrently.
We want your implementation to be correct under concurrency as well.
In order to ensure atomicity of your operations under concurrency, you must use synchronization mechanisms like locks or semaphores. You have to make sure that there are no race conditions. However, you have to be careful about deadlocks. Using synchronization mechanisms should never introduce deadlocks to your implementation.
