Memory Allocation : It is the technique of allocating memory storage to program in order that the program can be run.
First fit algorithm: The question asked for examples not algorithms the first fit algorithm may be explained.
Suppose the memory allocation is as follows: suppose indicates allocated block & denotes a free block. The size of the free blocks are indicated. Suppose the current requirement is 8K. Then the first fit algorithm will allocate it from the block of 20K.
The advantage ; it is part disadvantage : fragmentation.
P=freeblock
aloc= null
q=null;
while (p!=null && size (p) < n )
{
Q=p;
p=next(P)
}/* end while
*/ if (p!=null)
{/* there is block large enough*/
s=size(p); alloc=p+s-n; /* alloc contain the address of the designed
block*/
if(s==n)
/* remove the block from the free list*/ if
(q==null)
free block=next(p);
else
next(q)=next(p);
else
/* adjust the size of tile remaining free block*/
size(p)=s-n;
}/* end if*/
The Best fit algorithm : The best fit method obtains the smallest free block whose size is greater than or equal to n. An algorithm to obtain such a block by traversing the entire free list follows. We assume that the memsize is the total no. of words in memory.
The Best fit algorithm allocates the memory from the block that fits the requirement best i.e. the block that has size greater than the requirement, but no other block of lesser size can meet the requirement. Thus for the above problem the allocation will be made from block of size 10 K. Advantage : fragmentation is reduced Disadvantage : more time.
p=freeblock; /*p is used to traverse the free list */
q==null; /* q is one block behind p*/ r=null; /*
r points to the desired block*/ rq=null; /*
rq is one block behind r */
rsize=memsize+l; /* rsize is the size of the block at r */
alloc = null; /* alloc will point to block selected */
while(!=null)
{
if(size(p)>= n && size(p)<rsize)
{
/* we have found a free block closer in size */
r=p;
rq=q;
rsize=size(p);
}
/* END IF */
/* continue traversing the free list */
q=P;
p=next (p);
}
/* end while */
if{r!=null)
{
/* there is block of sufficient size */
alloc = r + r size – n ;
if (r size = =n){
/* remove the block from the free
list */ if(rq= = null )
free block = next (r );
else
next(rq)= next( r );
else size(r) = rsize- n ;
} /* end if */