Pre-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.

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 8 up to 8.3, inclusively.

For this lab and the next, it will be helpful to read:

Create a new directory for this week’s work:

~/csci315/Labs/Lab7

In this directory, create a file called answers.txt where you will write BRIEF and CLEAR answers to the questions below.

Problem (30 points)

The operating system must keep track of which portions of memory have been “doled out” to processes (e.g. in use)  and which portions are unallocated (e.g. free). In this lab, you will implement a custom memory allocator, which will keep track of allocated and free memory chunks using two doubly-linked lists. One list will be called the free-list (sections of memory that are not allocated) and the allocated-list (sections of memory that are in use).

Consider that memory will be allocated:

  • At the time each process is created (so that its executable can be loaded into memory).
  • At the time each process calls malloc.

Consider that memory is de-allocated:

  • At the time each process calls free.
  • At the time each process is terminated.
  1. Reflect on how processes will cause insertions and removals in the doubly-linked lists that keep track of the memory that is allocated or free. Discuss whether doubly-linked lists are suitable for use in a custom memory allocator. (4 points)
  2. Propose one or more data structures that might work as well or possibly better than doubly-linked lists for keeping track of allocated and free memory. (4 points)
  3. Define the term external fragmentation and describe a scenario where it occurs. (3 points)
  4. Define the term internal fragmentation and describe a scenario where it occurs. (3 points)
  5. Describe the first-fit allocation policy. Give one advantage and one disadvantage of its use. (4 points)
  6. Describe the best-fit allocation policy. Give one advantage and one disadvantage of its use. (4 points)
  7. Describe the worst-fit allocation policy. Give one advantage and one disadvantage of its use. (4 points)

When you are done with this, you need to:

  • git add answers.txt
  • git commit “pre-lab 7 completed”
  • git push

 

Print Friendly