Lab 5 - Memory Allocation Algorithms

Prerequisite Skills for This Lab

---

• Understand memory allocation from notes, see slides.
• C Skills
  • Able to work with a C linked-list.
    • See YouTube Video on Linked List in C
  • Able to create and use structs.
  • Able to use pointers: type cast, dereference, pointer arithmetic.
  • Able to compile, run, and debug C programs.

Part 1

---

In a file name lab5.c, In the following code, implement:

1. First-fit block selection.
2. Best-fit block selection.
3. Worst-fit block selection.
4. Printing out block IDs.

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

struct header {
  uint64_t size;
  struct header *next;
  int id;
};

void initialize_block(struct header *block, uint64_t size, struct header *next,
                      int id) {
  block->size = size;
  block->next = next;
  block->id = id;
}

int find_first_fit(struct header *free_list_ptr, uint64_t size) {
  // TODO: Implement first fit
  return -1;
}

int find_best_fit(struct header *free_list_ptr, uint64_t size) {
  int best_fit_id = -1;
  // TODO: Implement best fit
  return best_fit_id;
}

int find_worst_fit(struct header *free_list_ptr, uint64_t size) {
  int worst_fit_id = -1;
  // TODO: Implement worst fit
  return worst_fit_id;
}

int main(void) {

  struct header *free_block1 = (struct header*) malloc(sizeof(struct header));
  struct header *free_block2 = (struct header*) malloc(sizeof(struct header));
  struct header *free_block3 = (struct header*) malloc(sizeof(struct header));
  struct header *free_block4 = (struct header*) malloc(sizeof(struct header));
  struct header *free_block5 = (struct header*) malloc(sizeof(struct header));

  initialize_block(free_block1, 6, free_block2, 1);
  initialize_block(free_block2, 12, free_block3, 2);
  initialize_block(free_block3, 24, free_block4, 3);
  initialize_block(free_block4, 8, free_block5, 4);
  initialize_block(free_block5, 4, NULL, 5);

  struct header *free_list_ptr = free_block1;

  int first_fit_id = find_first_fit(free_list_ptr, 7);
  int best_fit_id = find_best_fit(free_list_ptr, 7);
  int worst_fit_id = find_worst_fit(free_list_ptr, 7);

  // TODO: Print out the IDs

  return 0;
}

Part 2: Coalescing Contiguous Free Blocks

---

Write a pseudo-code algorithm for the coalescing contiguous free blocks.

• Write your algorithm is comments in your .c file.
• As an example, test your algorithm on a memory layout like this, after the red block (z) is freed.
  
• Hint - Newly Freed Block

  Your algorithm should handle a single newly freed block. If you assume the current link-list of free blocks has been coalesced, then you only need to consider merging the single newly freed block to existing blocks in the linked-list.

3. Reviewing (10 mins)

---

• During the last 10 minutes of the in-person lab, TAs will show a sample solution.
• TAs will talk through how the solution works and discuss its implementation.
• Discussion Points
  • How does the code work?
    • What is the memory layout?
    • What is being done each iteration of the loops?
  • How does the coalescing algorithm work?
• Now that you have seen the solution:
  • Finish implementing your solution: don't just copy the solution, but it is OK if you use the ideas you saw to help you finish.
  • Revise your solution to improve it based on what you learned.

4. [Optional] Challenges

---

1. Optional: Implement your coalescing algorithm!
2. Optional: Test your implementation with a larger data set. Randomly create new blocks, allocate them, and free them. Can you make it crash?

Submission

---

Submit your C code to CourSys by Sunday midnight. The file name must be an exact match to what CourSys is expecting, otherwise it won't accept it. Remember you can submit up to 3 days late with no penalty if needed (but please plan to get it done on time to stay up to date on the course!)

Submissions will be marked for completion. It must be valid C code that runs (however we are unlikely to actually compile and run the code). You do not need to complete any optional steps.