## Storage Management [Data Structure]

**In case of large voluminous data, every byte of space is important and plays a major factor in determining the cost of the resources.**

**Programs that are run on computer systems will use variables that are stored in main memory for manipulation of data.**

**When a variable is defined, a calculated amount of contiguous space is allocated to the variable, depending on its type.**

* Compaction*:- is the process of eliminating waste spaces so that there is no block of memory unusable.

**
**

**Disadvantages:**

The programs performing operations on memory are suspended while compaction is performed

**Reallocation Method**

——————————-

** First fit method**: In the first-fit method, each block from the beginning is searched for a free block. The requested block of memory is allocated in the first possible free block.

freeblock *alloc,*y;

x = fbhead;

y = NULL;

alloc = NULL;

while( (x != NULL) && (x->size < n) )

{

y = x;

x = x->next;

}

if( x != NULL )

{ s = x->size;

alloc = x + s – n;

if( s == n )

if( y == NULL )

fbhead = x->next;

else

y->next = x->next;

else

x->size = s – n;

}

** Best fit method**: In the best-fit method, the entire list of free blocks is traversed and the smallest free block where allocation can be done is found out.

freeblock *alloc,*y;

x = fbhead;

y = NULL;

z = NULL;

alloc = NULL;

bz = NULL;

zsize = MAXMEM + 1;

if( z != NULL )

{

alloc = z + zsize – n;

if( zsize == n )

if( bz == NULL )

fbhead = z->next;

else

bz->next = z->next;

else

z->size = zsize – n;

}

**Garbage collection**

—————————-

Two phases of garbage collection are:

*-Marking phase*

*-Collection phase*

** Marking phase**: A node is marked if it can be accessed from a given pointer. The nodes in the memory are sequentially checked.

If there are any nodes that can be accessed

from the current node, then the nodes are all marked.

In case the second node’s address is less than the

previous node, the process continues from the second

node. The process continues until all nodes are marked.

Node structure created for the example of Marking

Phase

struct listnode

{

int info;

int mark;

int next;

}list [50];

int arptr[10];

for( i=0; i<10 ; i++)

list[ arptr[i] ].mark = TRUE;

i = 1;

while( i < 50 )

{

k = i + 1;

if( list[i].mark )

{

if( list[ list[i].next].mark != TRUE )

{

list[ list[i].next].mark = TRUE;

if( list[i].next < k )

k = list[i].next;

}

}

i = k;

}

** Collection phase**: After the required nodes are marked, the collection phase begins. In the collection phase all the nodes that are not marked are added to a separate list. Then the space allocated for these nodes are reclaimed and assigned to newer nodes.

for( i = 0; i< 50; i++ )

{

if( list[i].mark != TRUE )

{

list[i].next = glist;

glist = i;

}

list[i].mark = FALSE;

}

** The Big O Notation**: is a popular mathematical tool used to calculate time complexities for different algorithms.

The Big O notation is represented as:

f(n) = O( g((n) )

f(n) – the computing time of the algorithm when

it is run for an input size of n.

g(n) – standard function, whose value is

determined prior to the execution of the algorithm.

**Standard functions**

——————————-

n: An algorithm having a time complexity of order n, is said to be linear. The time taken is said to be linearly proportional to n.

n2: The algorithm is said to be quadratic if the time complexity is of order n2.

n3: If the time complexity of an algorithm is of order n3, then the algorithm is said to be cubic.

Log n: If the time complexity of an algorithm matches the function log n, then the algorithm is said to be logarithmic.

nlogn: If the time complexity of an algorithm is n log n, then it can be said that the algorithm solves a problem by breaking it into smaller sub-problems and solving them independently.

*Conclusion:*

When a variable is defined, a calculated amount of contiguous space is allocated to the variable

Collecting unused space towards on one end in memory is called compaction

A pointer is used to store the first location of the free block initially

The disadvantage of compaction is the programs performing operations on memory are suspended, while compaction is performed

*Conclusion:*

Thanks for sharing your thoughts. I truly appreciate your efforts and I am waiting for your next write ups thank you once again.

Thank you 🙂