Storage Management

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

A linear list is used to keep track of list of free blocks
The process of detecting unused nodes and collecting them together is known as Garbage Collection
Garbage collection is done in two phases – marking phase and collection phase
The garbage collection routine is called when there are only few spaces left in memory