Description

Introduction 

This problem is based on the implementation of Doubly Linked Lists (for Assignment 1) and Binary Search Trees (for Assignment 2) and Balanced Binary Search Trees (AVL Trees for Assignment 3) in order to create a system to perform Memory Allocation. Now the first question that would intrigue us is What is Memory Allocation? Well in simple terms, it is the reservation of portions of the Computer memory for execution of processes. Thus, this system will be running on our machines and it will give out memories to the programs as requested by them (Ever heard of malloc?)

The above statement should get more clear once we delve into the details of this system. So mainly there are two types of Memory allocation:

• Static Memory Allocation: The system knows the amount of memory required in advance. From this, it can be inferred that memory allocation that would take place while defining an Array would be static as we specify it’s size earlier. 

• Dynamic Memory Allocation: The system does not exactly know the amount of memory required. And so in this case, it would get requested for memory Dynamically. Linked Lists creation is an example of Dynamic Memory Allocation. 

We will focus on Dynamic Allocation of Memory for our Assignments. Memory in our computers is divided into different addresses. And these addresses get grouped into different blocks or segments (more on that later). Say a program demands a space of 4KB (Kilobytes), then a memory block of 4KB size is given to this program. What if some other program demands a 4KB memory and the same block gets given to it? What about the previous program which was already using that block? Think of a situation where there is an airplane with it’s lavatories not having a functional vacant/occupied slider sign... disasters will happen right? The exact same will happen here too.

So this System for Memory Allocation will be having an information about the memory spaces that would be currently occupied by other programs and the memory spaces that are currently available, so that whenever a program asks for memory only the memory block that is marked free (or currently available) will be given to that program. Now whenever a free memory block is given to a program then it is marked as occupied (or allocated) so other programs can not access it.