CSCI 315 Operating Systems Design

Bucknell University

Lab 7

Goals

  • Learn to design and to implement a custom memory allocator: The operating system provides mechanisms for dynamic allocation in contiguous memory spaces. There are multiple criteria to assess how well these mechanisms work, including speed of execution and the minimization of external fragmentation (to that end, you learned of different policies for allocation decisions, such as first- fit, best-fit, and worst-fit). In this lab, you will design and implement a memory allocation system to work in user space and apply the concepts you have studied so far.
  • Learn to work with a source tree similar to what you would find in open software. This lab gives you, as a starting point, a source code tree that includes a number of files and a Makefile to build separately compiled objects. This code includes a test suite that serves to shake the implementation around to expose bugs and test its functionality. You will add your new files to this source code tree, modify the Makefile given to you, and implement a test suite of your own to exercise your custom memory allocator.

Credits

This lab was developed by Prof. L. Felipe Perrone. Permission to reuse this material in parts or in its entirety is granted provided that this credits note is not removed. Additional students files associated with this lab, as well as any existing solutions can be provided upon request by e-mail to perrone[at]bucknell[dot]edu

Set Up

Read your SGG textbook from the start of Chapter 9 through 9.2 (8 up through 8.3 9th edition), inclusively.

For labs 7 and 8, it will be helpful to read:

Continue to work on the files you started in the prelab.

Problem 3 (70 points)

The implementation of a doubly-linked list abstract data type (ADT) in C is given to you among the files you copied for Lab7. You may use this code with the usual guarantees of open source software: The solution that is being given to you has undergone a good amount of testing, but there are no guarantees that it is absolutely perfect. You may want to read the code to understand the implementation, you may want to test it further, or do anything else you find appropriate to develop the confidence you have in it.

Be sure to put the files you create for this lab in the appropriate directories in this source code tree! That is, new header files should go in include/, new source files should go in src/, etc. Note that you may want to modify the code of this doubly-linked list so as to have a little more information in the node structure than what is given to you in the original module. (See more about this point in the description of the deallocate function below.) If you modify the doubly-linked list code, you should want to modify the test suite in src/dlisttest.c and run these tests to ensure that the module runs correctly after your changes.

For this problem, you will create a custom memory allocator. Since your code will not be part of the operating system, it will execute in user mode. The general idea is that one who uses your allocator will include a header file which declares your functions and also link with the code that defines/implements them. A program using your allocator will have to get it initialized before any calls are made to use dynamically allocated memory; our standard prototype for the initialization is:

int allocator_init(size_t size);

This function will create and initialize two doubly-linked lists used for memory management: one which keeps track of the memory that is available (call it free_list) and another which keeps track of memory which is already in use (call it allocated_list). All the memory manipulated by your allocator will reside in the heap of the process that uses it. When allocator_init starts, it will call the standard malloc to request a contiguous space of size bytes from the underlying operating system. The pointer received from malloc will be used to initialize a single node in your free_list; your allocated_list must start out empty. If the malloc call does not succeed, this function must return -1, otherwise, it must return 0. The correct implementation of this function earns you 12 points.

Ultimately, a custom memory allocator will need an API similar to what you have for malloc and free, functions that provide dynamic memory allocation in C. With that in mind, we define the API for a function to allocate memory and another to deallocate. (We will not worry about implementing anything like calloc and realloc, although they would be simple extensions once your basic functionality is implemented.)

void *allocate (size_t size);

Equivalent to malloc. This function will traverse the free_list and find a contiguous chunk of memory that can be used to satisfy the request of an area of size bytes. If the caller makes a request for memory that is larger than what your allocator can honor, this function must return NULL. Your allocate function must be flexible enough to allow for different allocation policies, namely first-fit, best-fit, and worst-fit. You should probably create three functions, one for each of these policies, which are used internally by allocate and are not visible to the user of your custom memory allocator. Having those functions allows you to make easy modifications to the policy used by allocate. You will want to design your code so that it is easy run experiments with different allocation policies, so think carefully about how you will define your functions prototypes. The design of these functions’ API and their implementation (obviously) is up to you. You should describe all additional functions used in your code in a file called designAPI.txt that is turned in with the other deliverables for this lab (a clear and well-written design description earns you 12 points; be sure to place this file in the doc/ directory of your source code tree). The correct implementation of this function earns you 12 points.

int deallocate(void *ptr);

Equivalent to free. This function will use ptr to find the corresponding node in the allocated_list and free up that chunk of memory. If the caller attempts to deallocate a pointer that cannot be found in the allocated_list, this function must return -1, otherwise it should return 1 (in order to be consistent with the memory_test examples). To make your development process easier, at first, you can simply move the deallocated memory from the allocated_list to the free_list. Note that just as the C library’s  free, deallocate does not ask you for the size of the memory you are returning to the system. Think about how you can make your custom allocator keep track of the size of each allocated chunk of memory — the cleanest solution might require you to change the code of the doubly-linked list given to you. This modification will earn you 7 points. The correct implementation of this function earns you 12 points.

The entire code of your custom memory allocator will be encapsulated in two files:

  • allocator.h
  • allocator.c

Two test programs are given among the files you copied, memory_test.c and memory_test_1.c. Please read these two programs and make sure you understand how the test programs work. Obviously what you developed must pass these tests. Once your implementation passes these tests, develop a new test program of your own, and try to come up some tests of your own. Reviewing the past uses of the malloc functions may help you come up with some ideas. Name this program memory_test_2.c. The the passing of the two given test files and your own test program corresponds to 15 points.

Finally, you have to put together a Makefile for one to build your allocator (as a separately compiled module) and all the corresponding tests. Not submitting a Makefile that builds all your code correctly will lose you 10 points.

When you are done with this, you need to:

  • git pull
  • git add Makefile
  • git add src/allocator.c
  • git add include/allocator.h
  • git add doc/designAPI.txt
  • git add src/memory_test*.c
  • git add [any of dnode/dlist.[c,h] that you modified]
  • git commit -m “Lab7 completed”
  • git push

Grading Rubric

Problem 3 (a total of 70 points)

  1. [12 points] The correct implementation of allocator_init.
  2. [12 points] A clear explanation, in the file designAPI.txt, of the design of your supporting functions for dealing with various policies for contiguous memory allocation (best-fit, first-fit, and worst-fit). Your document should describe the API of your functions and how they are used in your custom memory allocator.
  3. [12 points] The correct implementation of allocate.
  4. [7 points] Your correct modification to the doubly-linked list module given to you, which should support your deallocate implementation.
  5. [12 points] The correct implementation of deallocate.
  6. [15 points] Pass the tests in memory_test.c and memory_test_1.c. The implementation of a test suite of your own in memory_test_2.c.
  7. [-10 points] The student hasn’t submitted a Makefile that builds all the files used in the implementation and in the testing of the custom memory allocator.

Additional Challenge (30% additional points on this lab total)

Once the functionality described above works to specification, you may want to tackle an extra credit problem: you can check if the deallocated memory is adjacent to any other chunk of free memory and consolidate the corresponding free_list nodes into a single node representing the sum of the sizes of the two original nodes.

If you decide to go for this challenge, PLEASE place your implementation in directory Lab7/extra-credit in which you will replicate the entire source code tree. Submit this  via git as usual. (You will need to have the standard, un-optimized allocator for the next lab.)

Print Friendly, PDF & Email