Assignment 1 Memory Pool Management using LinkedList and Arrays

Objective:

To create a Memory pool using Arrays and Linked List and manage allocation of memory for incoming requests. The blocks are assumed to of power of 2 and each index in the array correspond to the actual size of memory block upon which the linked list is made of.

Approach:

Steps Performed to create and allocate memory blocks:

1. Created a node class through which the memory pool is created.
2. Created an array of linked list to create a memory pool.
3. Created a method to get the memory block from the pool.
4. Methods to split or merge memory blocks if the requested block is not present at the particular index.
5. Created the final linked list of requested blocks.
6. Calculated the number of failed requests for the run of 1000 block requests.
7. And performed empirical analysis.

Code Description:

1. LinkedList class a. Contains an inner class as node, which contains the data and next pointer. b. Contains a method to insert new node in ascending order (Insertion Sort). c. Contains a method to delete a node.
2. MemoryPool class a. Contains Pool as an array of linkedlist, which works as a memory pool. b. createMemoryPool() method to create a memory pool. c. printMemoryPool() method to print the memory pool. d. getBlock() method to fetch the block from the memory pool and if require then split. e. getBlocksMovingUpwards() method to merge the memory block. f. newStartBlock contains the requested blocks.

Empirical Analysis:

Input	Duration (in Milliseconds)
200	11
400	17
600	19
800	20
1000	21

Considered the initial Memory Pool:

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

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=200, b= 0.63
When N=400, b=0.45
When N=600, b=0.27
We consider b=0.45 and the value of c happens to be c=0.02.
When used the formula stated above,
The T(N) = 10.95 milliseconds, whereas the actual result is 11 milliseconds.

Output screenshots: