Lab 5 - Memory Allocation Algorithms


Expand for the usual lab directions
  • Submit your completed lab online to CourSys (not Canvas, not GitHub).
    • Labs are marked on completion, not correctness, so complete each part to the best of your ability and learn.
    • Lab is due Sunday and may be submitted up to 3 days late. Further extensions possible only in exceptional cases.
  • It is recommended that students attend in-person lab sections for lots of support!
    • You are invited to come to any (or more than one) lab section.
    • There is no need to attend the section you are enrolled in.
    • There is no need to attend any lab sections: there is no attendance taken.
    • You can complete the lab on your own time or own computer if you like.
    • Time suggestions are given here to guide students who are working on the lab during lab times. However, the entire lab must be completed by everyone for marks.
  • While completing these labs, you are encouraged to help your classmates and receive as much help as you like. Assignments, however, are individual work and you must not work with another person on assignments.
    • I recommend coming to the lab and working with someone.
    • Failing that, I recommend getting together with someone in the class outside of lab time to work through the lab together.
    • Failing that, you are welcome to complete the lab exercise without any collaboration.
    • Each student must submit their lab to get marks.
    • Academic honesty expectations for labs are that each student types their own lab solution. It is OK to share ideas and help each others with specific coding issues and design. It is not permitted to submit another student's file for credit.
  • If using CSIL lab PC:
    • [Only CSIL PC] If in Windows, reboot to Linux; while booting, select Ubuntu from boot menu.
    • [Only CSIL PC] Don't setup GitHub tokens in the cmpt201 container because it may be shared with other users.
    • [Only CSIL PC] Delete any possible previous docker container before starting the lab:
      docker rm cmpt201
    • [Only CSIL PC] When done your lab, copy your solution out of the container, then execute the above docker command to delete your docker container to leave it clean for the next user.
  • You do not need to use record.


Prerequisite Skills for This Lab


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.
    Linked list picture
  • 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.