本次为SFU CS300操作系统代写C语言实现内存管理
Project 5: Memory Management
This project deals with memory management where you will design a contiguous memory allocator library.
Marking
This project will be graded based on correctness (90%) and correct memory management (10%). For correctness, you can assume that there will be more than 45 test cases for this project, and every test failure will cause one point deduction. For correct memory management, you will lose 5% for memory leak and 5% for memory error (such as incorrect memory access). The correct management will be checked by valgrind.
Overview
In this project, you will implement a simple contiguous allocator that supports different allocation techniques that were discussed in class. The allocator will be used as a library that exposes interface to allocate, deallocate and manage memory.
Design
- Initializing contiguous memory allocation:
The allocator needs to know the total size of memory assumed in this project and the memory allocation algorithm to be used. This information will be supplied by the following API:void initialize_allocator(int _size, enum allocation_algorithm _aalgorithm);
In the above function,
_size
indicates the contiguous memory chunk size that is assumed for the rest of the program. Any requests for allocation and deallocation requests (see point 2) will be served from this contiguous chunk. You must allocate the memory chunk usingmalloc()
. In the above API,allocation_algorithm
is anenum
(as shown below) which will determine the algorithm used for allocation in the rest of the program:enum allocation_algorithm {FIRST_FIT, BEST_FIT, WORST_FIT};
FIRST_FIT
satisfies the allocation request from the first available memory block (from left) that is at least as large as the requested size.BEST_FIT
satisfies the allocation request from the available memory block that at least as large as the requested size and that results in the smallest remainder fragment.WORST_FIT
satisfies the allocation request from the available memory block that at least as large as the requested size and that results in the largest remainder fragment. - The allocation and deallocation requests will be similar to
malloc
andfree
calls in C, except that they are calledkalloc
andkfree
as shown below:void* kalloc(int _size); void kfree(void* _ptr);
As expected,
kalloc
returns a pointer to the allocated block of size_size
andkfree
takes away the ownership of the block pointed by_ptr
. If allocation cannot be satisfied,kalloc
returnsNULL
. Hence, the calling program can now look like:int* p = (int*) kalloc(sizeof(int)); if(p != NULL) { // do_some_work(p); kfree(p); }
Your allocator must maintain meta-data (pointer to the block and size of block) about the allocated and free blocks so that they can be used for faster allocation and compaction (as discussed in point 3). This meta-data must be held in form of
linked lists
(separate lists for allocated blocks and free blocks). When a block gets allocated (usingkalloc
), its meta-data must be inserted to the list of allocated blocks. Similarly when a block gets freed (usingkfree
), its meta-data must be inserted to the list of free blocks. The free list must never maintain contiguous free blocks (as shown in Figure 1), i.e., if two blocks, one of sizem
and other of sizen
, are consecutive in the memory chunk, they must become a combined block of sizem + n
(as shown in Figure 2). This combination must happen whenkfree
is called.Figure 1: Each block is labeled with its size. White indicates free block while allocated blocks are colored.
Figure 2: Example with contiguous free blocks. This should never occur as contiguous free blocks should be merged immediately (as shown in Figure 1).
- Since contiguous allocation results in fragmentation, the allocator must support a compaction API as shown below:
int compact_allocation(void** _before, void** _after);
Compaction will be performed by grouping the allocated memory blocks in the beginning of the memory chunk and combining the free memory at the end of the memory chunk (as shown in Figure 3). This process will require you to manipulate the allocated and free meta-data lists. The process of compaction must be in-place, which means that you must not declare extra memory chunk to perform compaction. This can be done by going through the allocated list in a sorted manner and copying the contents of allocated blocks on free blocks from left to right.
Figure 3: Result of compaction on memory chunk shown in Figure 1
As compaction relocates data, all the pointer addresses in the driver program must also be updated. Hence, the API accepts
_before
and_after
arrays ofvoid*
pointers (hence they arevoid**
). The relocation logic will insert the previous address and new address of each relocated block in_before
and_after
. You can assume that_before
and_after
arrays supplied by the driver program are large enough(i.e., you don’t need to worry about allocation of these two arrays). The return value is an integer which is the total number of pointers inserted in the_before
/_after
array. This way, the calling program can perform pointer adjustment like this:void* before[100]; void* after[100]; // in this example, total pointers is less than 100 int count = compact_allocation(before, after); for(int i=0; i<count; ++i) { // Update pointers }
- Information about the current state of memory can be found by the following API:
void print_statistics(); int available_memory();
print_statistics()
prints the detailed statistics as shown below (<X>
is a number):Allocated size = <X> Allocated chunks = <X> Free size = <X> Free chunks = <X> Largest free chunk size = <X> Smallest free chunk size = <X>
available_memory()
returns the available memory size (same asFree size
inprint_statistics()
) - In order to avoid memory leaks after using your contiguous allocator, you need to implement a function that will release any dynamically allocated memory in your contiguous allocator.
void destroy_allocator();
You can assume that the
destroy_allocator()
will always be the last function call of main function in the test cases. And similar to previous projects, valgrind will be used to detect memory leaks and memory errors.
Notes
You can use your own linked list solution or the provided solution set from project 1.
Submission
Submit an archive kallocation.tar.gz
of your code (including main.c
) and make file (Sample Codes) on CourSys. We will build your code using your Makefile, and then run it using the command: ./kallocation
. You may use more than one .c/.h file in your solution, and your Makefile must correctly build your project. Please remember that all submissions will automatically be compared for unexplainable similarities.