Memory Management

Algorithm

1. Memory consist of two blocks:
   1. Main useable memory – pointers from this memory is returned to user
   2. Descriptor memory – used to store block descriptors which keep tracks of the memory usage.
2. Block Descriptor – A block descriptor is a structure which stores the information regarding memory allocation and deallocation. Linked list is used to implement block descriptor. It has the following components:
   1. Pointer to memory address returned to user for usage
   2. Pointer to next block descriptor
   3. Size of the memory block returned for usage
   4. Boolean flag to denote if memory block is free or not
3.  A set chunk of memory at the bottom is designated for block descriptors. We define this memory are before any allocations and only remaining part is available for the users.
4. Fail State:
   1. If we are out of memory to return to user.
   2. It we are out of block descriptors (i.e. descriptor memory runs out). Usually an optimal part of memory is decided to be used as block descriptor memory.
5. Initial State:
   1. Two pointers; one pointing to the memory location available for the user to use and other to the memory location storing block descriptors. We will call these as main memory pointer and descriptor memory pointer respectively. One more pointer free memory pointer will point to the main memory pointer initially.
   2. A variable storing the size of available free memory for usage.
   3. Block descriptor list will have one element at the beginning pointing to the main memory location and storing size as the total available size. Its Boolean flag will denote that this block is available for allocation.
   4. A variable storing the size of available descriptor memory.
6. First Allocation:
   1. Return the main memory pointer to the user.
   2. Decrease the total available size of the main memory by the size required by the user. We will return few more bytes of memory to the user in order to achieve memory alignment.
   3. Move the free memory pointer to point to the free memory, i.e. main memory plus the size returned to user.
   4. In block descriptor list:
      1. Set the boolean flag to not available.
      2. Set the size to the size returned to the user.
      3. Create a new block descriptor and point the next pointer to the newly created block descriptor.
      4. Create one new block descriptor with:
         1. Size as remaining free memory size
         2. Boolean flag denoting available for allocation
         3. Next pointer as null
         4. Memory pointer pointing to free memory pointer.

This will create a linked list of all the block descriptors with each block descriptor pointing to the next block descriptor.

1. From next allocation onwards:
   1. Traverse through the block descriptor searching if any already created block descriptor is available for allocation. Block descriptor will be available for allocation if its boolean flag denotes it as free and size is enough to fulfil user demand.
   2.  If any block is available for allocation return that block to the user. This will result in fragmentation of memory if size of block and size asked by user are not equal.
   3. To minimize/optimize fragmentation, return the memory block address from available block descriptor to the user, decrease its size to the new size required by user and flip the available flag back to false.
   4. Now create a new block descriptor with:
      1. Size as remaining size from the size of previous block descriptor.
      2. Memory address for user will be moved forward according to size asked by used.
      3. Available Boolean flag as true.
   5. Since we are doing garbage collection with each deallocation, it is important here to keep the block descriptor list serialized i.e. memory pointed by next pointer of each block descriptor should be in an order. For this purpose, the new block free descriptor created to avoid fragmentation should be attached in between the block descriptor returned to user and its next block descriptor.
   6. Increase the free memory pointer to point to next available free memory if no free block descriptor. If we find an already available block descriptor, no change is required in free memory pointer.
   7. Create a new block descriptor and add it to the next pointer of current block descriptor with:
      1. Size as total available size after allocation.
      2. Memory address for user as free memory pointer.
      3. Next pointer as null.
      4. Available boolean flag as true.
   8. Decrease the total free memory size accordingly after each allocation.
2.  Deallocation
   1. Traverse through the block descriptor list to look for the memory required to be deallocated.
   2. If memory is not found, exit deallocation without doing anything.
   3. If memory is found:
      1. Flip the boolean available flag to true.
      2. Increase the total free memory size accordingly.
3. Garbage Collection
   1. With this approach we will not require to implicitly call for garbage collection.  Garbage collection will be called after each deallocation.
   2. When any memory block is deallocated, check if its previous memory is block is available for allocation (i.e. if it is free). If yes, we will combine the two blocks into one. For combining:
      1. Add the size of current free block to previous free block.
      2. Change the next pointer of previous free block to current’s next pointer. This will combine the two separate free blocks into one.
      3. Check if new next block is free as well, do the same steps as above to combine the two into one.
   3. If previous memory block is not free, check if the next memory block if free or not.
   4. It next memory block is not free as well, no garbage collection is required.
   5. If next memory block is free, combine the two block into one.

Click Here for GitHub link