Operating System代写:CS164 Malloc



  1. Check out the malloc tutorial from Dan Luu on how these functions can be implemented at: http://danluu.com/malloc-tutorial/
    For your convenience, it is also appended in this file. The tutorial implements working versions of malloc, free, calloc and realloc and you can use that code as-is.

  2. Write a driver function (i.e., main function) to demonstrate the usage and efficiency of these functions. The main() should have at least 10 calls each to malloc, calloc and realloc and at least 5 calls to free. Set up the function to print out the heap start/end addresses and also print out the memory leaks in your code.

  3. Your main task is to implement the exercises mentioned in the tutorial. These are also shown below:

    • (a) Convert the single linked list implementation of the tutorial into a doubly linked list version; make changes to all the functions accordingly to work with the doubly linked list.
    • (b) malloc is supposed to return a pointer “which is suitably aligned for any built-in type”.
      Does our malloc do that? If so, why? If not, fix the alignment. Note that “any built-in type” is basically up to 8 bytes for C.
    • (c) The implemented malloc is really wasteful if we try to re-use an existing block and we don’t need all of the space. Implement a function that will split up blocks so that they use the minimum amount of space necessary
    • (d) After doing (c), if we call malloc and free lots of times with random sizes, we’ll end up with a bunch of small blocks that can only be re-used when we ask for small amounts of space. Implement a mechanism to merge adjacent free blocks together so that any consecutive free blocks will get merged into a single block.
    • (e) The current implementation implements a first fit algorithm for finding free blocks. Implement a best fit algorithm instead.
  4. Repeat Step (2) with this implementation to demonstrate usage of the functions and memory leakage.

  5. Your code must use the set-up mentioned in this tutorial. Other online resources can be consulted but NOT copied. The tutorial mentions some other implementations for splitting/merging blocks that can only be consulted but not copied