OS Lab - Memory Allocator Evaluation

In this lab, you should evaluate the three your memory allocators (first fit, next fit, best fit) by constructing a program that allocates and frees memory for an extended period of time. This program terminates and prints statistics on memory utilization and execution cost at the first time a memory allocation request fails.

Your allocator should be dividing an arena whose initial size is 2MB, and does not grow.

The program proceeds in rounds. In each round i, a random integer between 1 and 10 is drawn, which indicates the number of regions to be allocated in round i. Each region's size should be randomly selected in the range of 8..1008 as (x mod 1000) + 8 where x is a randomly generated integer read from an input file. Recall that % is the mod operator in "c".

At the end of each round, the first region allocated for that round is freed.

I have provided a text file lab3-rands.txt that contains a pseudo-random sequence of integers. When your program needs a random number in the range [min..max], do so using a function udri(min, max) that

  1. reads the next integer from the file lab3-rands.txt to variable v
  2. returns (v mod (max-min)) + min

What you should report the first time a malloc fails.

Review of overhead and fragmentation

15 point Extra credit challenge, due with lab 3b, and not accpted late
The "memalign" function in my malloc.c is pathologically broken and should be replaced. Memalign should return a region of (at least) the requested size & aligned to an address that is a multiple of requested "alignment". I will award 15 points to students who figure out how to do this correctly. Note that your solution may need to carve the block containing the aligned region from a much larger free block.