Skip to the content of the web site.

Project 2

In this project, you will implement a real-time memory allocation strategy called half-fit. The requirements of the project are as follows:

There is one allocation function, void *half_alloc( size_t n ), that takes an integer as an argument and returns a block of memory of the appropriate size. Memory will be allocated in multiples of 32 bytes (including a four-byte header). Any request for any other amount will result in a block of memory of the next largest size being allocated; although the user will not be aware of this. Available memory will be divided into buckets of size 32, 64, 128, 256, 512, 1024 and all the way up to 32768 in powers of two. Each bucket will contain all available blocks of memory of the size up and including to the next size minus 1 (although, as sizes are multiples of 32, it will really be only up to the next size minus 32). Therefore, an available block of 900 bytes will be in the bucket corresponding to 512 to 1023 (although it will only contain blocks from size 512 to 992). A request for n bytes will access a block from the bucket corresponding to the least power of two greater than or equal to the requested amount. As all the blocks in this bucket must be greater than or equal to this power, it is guaranteed that any block of memory from this pool will be acceptable.

The system will be initialized with a single block of size 32768. You will require function void half_init(). This function will always initialize the system as if no memory has been allocated.

Given a block from the appropriate pool, suppose that is of size m bytes and the request is for n bytes. If m − n < 32, then allocate the entire block and return the address of the first byte. Otherwise, split the block into two allocating the n bytes and placing the other block into the appropriate bucket for a block of size m − n.

Note that if a request is made, say, for a block of size 94 bytes, if the bucket containing blocks of size 128 to 255 is empty, you will keep searching progressively larger and larger buckets until one is found that is not empty. If all buckets are empty, the null pointer is returned.

You do not have to clear the entries of the block (that is, set them to zero).

There is one de-allocation function, void half_free( void * ), that takes a block of memory and re-integrates it back into the memory pool. If the freed memory block is adjacent to other currently freed memory blocks, it is merged with them and the combined block is then re-integrated into the memory pool.

Block design

When a block is allocated, it will be cast as a structure with

  1. 10 bits storing a representation of the address of the previous block in memory,
  2. 10 bits storing a representation of the address of the next block in memory,
  3. 10 bits storing a representation of the size of this block,
  4. 1 bit indicating whether the current block is allocated or deallocated.

The representation is based on the fact that blocks are multiples of 32 bytes. Therefore, the ten bits 0110111011 would represent the address 011011101100000 and the size 0000001101 would represent the size 110100000, or 13 × 32 = 416 bytes.

When a block is unallocated, another 10 bits will be used to store a representation of the address of the next block in the linked list.

The memory map is shown in Figure 1.


Figure 1. Memory map for unallocated and allocated blocks.

The user will be passed the actual address of the first block memory.

Please note, as long as the first four fields fit in 32 bits, and the next two fit in the next 32 bits, how you arrange them is up to you. You may, for example, want to use the least-significant bits, in which case, slightly less work is required when extracting the values.

You are welcome to use the one remaining bit in the first four bytes and the 12 remaining bits in the next four bytes.

Grading

This project will be tested by having it execute a task that repeatedly allocates and de-allocates memory. There will be only one task for this project; however, later, we will deal with synchronization issues so as to allow multiple tasks to make simultaneous requests. This task will make numerous allocations of randomly selected sizes as well as numerous corresponding de-allocations. This will be timed and a value will be printed to the LED screen.

If your project is successful, you will receive a minimum grade of 80 % on the project. The remaining 20 % is based on how fast your implementation is relative to other students in the class.

If there is an error in your implementation, you will be assigned a grade relative to the number of errors made, with a grade no higher than 80 %.

More information

You will have to use a significant amount of bit-shifting in this project. For example,

  • x >> 10 will shift the bits of the argument x over by 10 bits to the right, so 00010001110111001001100010100010 would become 00000000000001000111011100100110.
  • x << 10 will shift the bits of the argument x over by 10 bits to the left, so 00010001110111001001100010100010 would become 01110010011000101000100000000000.
  • x & 1023 will set all bits other than the last 10 to zero (as 210 = 1024 and 102310 = 11111111112), so 00010001110111001001100010100010 would become 00000000000000000000000010100010.
  • 1 << 10 will have the value 210 = 100000000002.

All the addresses will, of course, be relative to the base address of the memory pool.

Note: if the user asks for a block of size 128, this will require a block of size 132, as four bytes are required for the header. Even the the initial block size is 32768, the actual memory available will only be 32764 as the four leading bytes will be the header of this one block.

Note: the last five bits of the address returned to the user will always be the same.

Things to consider

Normally, in a linked list, it is reasonable to assign NULL (memory location 0) to either the previous or next pointer to indicate that we are either at the front or the back of the linked list, respectively. This is because it is impossible that memory location 0 to be assigned through dynamic memory allocation (this is always occupied by the first instruction to be executed when the processor begins cycling). In this case, however, we only allow 10 bits for a pointer and each possible 10-bit value represents a valid 32-byte chunk of memory. How could you indicate when you are at the beginning or end of a linked list?

Example

Consider the following where the blocks follow the same scheme as above. Memory is divided into 1024 possible blocks of size 32, so we must somehow store sizes between 1 and 1024 in 10 bits—this is left to you. Initially there is only one block of unallocated memory, as shown in Figure 2.


Figure 2. A single unallocated block.

If a request comes in for 6112 bytes; this plus the 4-byte header requires 192 32-byte chunks. Normally, we would try to find a block between 256 and 511 32-bytes, but that bucket is empty, so we search ahead finding the only block and thus we split it, as shown in Figure 3.


Figure 3. After one request of size 192 blocks is allocated (192 is for requests between 6109 and 6140 bytes).

Next, a request comes in for 3300 bytes; this plus the 4-byte header requires 104 32-byte chunks. Again, we should start searching the bucket storing blocks between 128 and 255 blocks, but that is empty as is the next bucket storing blocks of size 256 to 511, so we take the block out of the next bucket and split it, as is shown in Figure 4.


Figure 4. After a second request for 104 blocks is allocated (104 is for requests between 3293 and 3324 bytes).

Next, a request comes for 5360 bytes, which requires 268 32-byte chunks. The bucket for blocks of size 512 to 1023 is non-empty, so we take that block out of the bucket, sub-divide it, and the remaining half is placed back into the bucket for blocks of size 256 to 511 blocks, as shown in Figure 5.


Figure 5. After a third request for 268 blocks is allocated (268 is for requests between 8541 and 8572 bytes).

Now, suppose that the first block allocated is now freed. It is flagged as such and it is inserted into the bucket storing available memory blocks with size between 128 and 255, as shown in Figure 6.


Figure 6. After freeing the first allocated block block.

Freeing the third block allocated requires it to be merged with the following unallocated block, as is shown in Figure 7. The unallocated block must be removed from the bucket containing blocks of size 256 to 511 and the merged block must be put into the bucket containing blocks of size 512 to 1023.


Figure 7. After freeing the third block allocated, requiring the third and fourth unallocated blocks to be merged.

A request comes for 2540 bytes, which requires 80 32-byte chunks. We search the bucket for blocks of size 128 to 255 and it is not empty, so we pop a memory block from that bucket and sub-divide it. The remaining memory block is returned to the bucket containing blocks of size 64 to 127, as is shown in Figure 8.


Figure 8. After a fourth request for 80 blocks is allocated (80 is for requests between 2525 and 2556 bytes).

Finally, suppose the second block allocated is now freed. In this case, both of its neighbors are also not allocated, so all three must be merged. The first and third are removed from their buckets and this creates a block of size 944, which is pushed into the bucket containing blocks of size 512 to 1023. This is shown in Figure 9.


Figure 9. After freeing the second block allocated, requiring the last three unallocated blocks to be merged.

To demonstrate the doubly linked list structure of the buckets, let us consider the state in Figure 8. There are two unallocated blocks, the first of 112 32-byte chuncks, and the other of 728 32-byte chunks. The first falls into the bucket associated with blocks on the range from 64 to 127 (64 = 26), while the second falls into the bucket associated with blocks on the range from 512 to 1023 (512 = 29). In this case, the buckets are linked as in Figure 10.


Figure 10. The state of the buckets at the same time as Figure 8.

Now, let's take it from this point, as having two buckets with one block each is not instructive.

Suppose, however, that there is a request for a block of 15990 bytes (thus requiring 16000 bytes which is 500 32-byte chunks). This request can be satisfied because the bucket containing blocks of size 512 to 1023 32-byte chunks is non-empty. We pop it out of its bucket, split it into two, allocate the one half and place the other in an appropriate bucket, as shown in Figure 11.


Figure 11. Allocating another block of memory.

Note that a request for 17000 bytes could not be satisfied: 17000 bytes requires 532 blocks, and thus, the half-fit algorithm would only investigate the bucket containing blocks of size 1024 to 2047, a bucket that is currently empty (with no other larger buckets available). This seems counter-intuitive, as there is a block that could be used to satisfy this request. What modification would you make to the half-fit algorithm under this circumstance? How would this affect the run time?


Figure 12. Deallocating the first block.