Assignment 3 Memory Pool Management using Binary Trees

• Objective: To create a memory pool using Binary trees with the root node representing the maximum sized memory block. One has to traverse the tree to fetch the required memory block and mark it as allocated. As and when the requested memory block goes out of stock, we need to mark the sub tree as occupied.

• Steps Performed to create and allocate memory blocks:

1. Created a node class through which the memory pool is created.
2. Created a binary tree of nodes to serve as a memory pool.
3. Created a method to get the memory block from the pool.
4. Allocated the final block and its children for requested input block size.
5. And performed empirical analysis.

• Code Description:
  1. Binary Tree class
  a. Contains an inner class as node, which contains the data and pointer to left and right sub tree.
  b. Contains a method to verify the height of tree
  c. Contains a method Breadth First Traversal to index the nodes with a Unique id
  d. Contains a method level order traversal to print the node values
  e. Contains a method to find the block of required input size
  f. Contains a method to check if child nodes are occupied.
  g. Contains two methods to look for next node
  h. Contains a method to look up hash map verifying previous requests
  i. Contains a method to traverse the tree and fetch a node of given unique id
  j. Contains a method to traverse and set the nodes of child as occupied
  k. Contains a Hash map to look up for nodes that are assigned to memory requests
  l. Contains a method to delete a node.
  2. Memory Pool class
  a. Contains a function that generates random values for memory requests
  b. Contains code to print the result of the generated requests, running time

• Empirical Analysis:

Input	Duration (in Milliseconds)
50	13
100	22
150	51
200	68
320	175

• Considered the initial Memory Pool:

S.no	Memory in KBs	Number of Blocks
1	1	1024
2	2	512
3	4	256
4	8	128
5	16	64
6	32	32
7	64	16
8	128	8
9	256	4
10	512	2
11	1024	1

• Graphical representation of time-complexity:
  

• Data Analysis: Using Logarithmic scale:
  Log(T(N)) = b log(N)+c
  Where T(N) = time required to process the input
  N = number of inputs
  We tested the results against standard formula and here are the values.
  When N=50, b= 0.68
  When N=150, b=0.45
  When N=300, b=0.27
  We consider b=0.68 and the value of c happens to be c=0.06.
  When used the formula stated above,
  The T(N) = 12.72 milliseconds, whereas the actual result is 13 milliseconds.

• Output screenshots: