Data and File Structures Unit 10

Unit 10 Dynamic Storage Management

Structure:
10.1 Introduction
Objectives
10.2 Dynamic Storage Management
10.3 Memory Management
Fixed block storage
Variable block storage
10.4 First-fit Storage Allocation
10.5 Storage Release
10.6 Buddy Systems
10.7 Garbage Collection
10.8 Summary
10.9 Terminal Questions
10.10 Answers

10.1 Introduction
In the previous unit you have learnt about one of the non liner data structure
called graph. We had a detail discussion about graph terminology, various
operations on graph and different applications of graph.
In this unit we are going to discuss “Dynamic storage management”, the
language PL/I define different storage classes depending upon the life span
and access method of the variables. We are going to examine some of the
techniques and algorithms that could be used to provide various levels of
storage management and control. Fixed block and variable block allocations
are one of the basic types under dynamic storage allocation. You will learn
about first-fit allocation which has enhancement features for variable size of
memory blocks. You will also be familiarized with buddy system allocation,
storage release and importance of garbage collection.
Objectives:
After studying this unit, you should be able to:
 describe dynamic storage management
 discuss various practices used in memory management
 explain first-fit storage allocation
 describe buddy system and storage release
 discuss the role of garbage collection.
Sikkim Manipal University Page No.: 156
Data and File Structures Unit 10

10.2 Dynamic Storage Management

Memory holds basically programs and their data. All the program need to
manipulate the data in order to complete the task. These data should be
stored in the memory for manipulation, so these data can be managed in
two different ways. Like static storage management and dynamic storage
management.
Primitive and static natures of data structures like integer, real, or character
variable has the characters that, their sizes are specified either explicitly or
implicitly in their declarations and memory will be allotted during compilation
and the sizes will not be changed during run time. For example while
declaring an integer variable in of c or c++ , the complier may allocate 2
bytes for the variable. The programmer can not change the size if he wants
to make the variable to hold overflow situation also. This shows clearly,
restrictions of static allocation are imposing limitations. These static
allocations are manageable for primitive data structure for simple
application. But we require dynamic data structures such as linked list in
order to construct the advanced structures like queue and trees. The c++
language provides storage allocation by maintaining a separate memory
area called free. Programs can request a block of contiguous memory for
their dynamic use, after allocation this will be maintained in the allocated list.
After the use allocated memory the same can be returned to the free pool.
In many of the previous preceding sections we have made free use of
structures that require a form of memory management in order to handle
requests for storage and releases of storage. When we discussed about the
tree data structure we simply requested the nodes, when ever we required
with out bothering when and how these nodes were to be released or when
they were no longer needed. This makes the programmer work easy, in this
unit we will discuss various levels of storage management and control. Most
of the dynamic storage management methods that are commonly used are
variants of the technique presented here.

10.3 Memory Management

Free memory in the free storage area or the free pool area generally holds
the memory as non-contiguous block. Their linearity can be maintained by
means of pointers between one block to another. In order to generate an
accurate memory representation, one also needs to analyze the pointers’
Sikkim Manipal University Page No.: 157
Data and File Structures Unit 10

usage. Pointer analysis is a compiler technique to identify at compile-time

the potential values of the pointers in the program. It determines the set of
locations the pointer may point to (point-to information). This information is
not only used to create the memory representation but it is also used for
synthesis. In the case of loads (...=*p), stores (*p=...), and free, we want to
synthesize the logic to access, modify or deallocate the location referenced
by the pointer. The point-to information must be both safe and accurate:
safe because we have to consider all of the locations the pointer may
reference and accurate because the smaller the point-to-set is, the more
accurate the memory representation is and the less logic we have to
generate. And we can also go for linked list where links maintains the
adjacency of blocks. Regarding the size of the blocks allocation, we follow
two practices:
 Fixed block storage allocation.
 Variable block storage allocation.
10.3.1 Fixed block storage allocation
First block storage allocation is the simplest case of dynamic storage
allocation. This is the straight forward method in which, all the blocks are of
identical in size. The user can decide the size of the block. The operating
system keeps a pointer called AVAIL. This pointer points to memory as
shown in figure 10.1.

AVAIL FIXED SIZE NODE

Figure 10.1: Free storage with fixed block memory

A user program communicates with the memory manager by means of two

functions GETNODE(NODE) and RETURNNODE (ptr). GETNODE()
procedure is used to avail an free node from the AVAIL list whereas the
RETURNNODE() is used to return the block of memory, whenever a
memory block is no longer required.

Sikkim Manipal University Page No.: 158

Data and File Structures Unit 10

Procedure GETNODE(NODE)
If (AVAIL=NULL) then
Print “The memory is insufficient”
Else
Ptr=AVAIL
AVAIL=[Link]
Return(ptr)
Exit

Whenever the GETNODE() is executed it checks for the availability of free

node in the AVAIL list and get a memory block from the AVAIL list as shown
in the figure 10.2.

Figure 10.2: Getting a block from AVAIL list

Procedure RETURNNODE(ptr)
Ptr1=AVAIL
While([Link] is not NULL)
Ptr1=[Link]
[Link]=ptr
[Link]=NULL
Exit

Procedure RETURNNODE() used to return back the used memory to the

AVAIL list, it will be added at the end of the list as shown in the figure 10.3.

Figure 10.3: Returning a block to AVAIL list

Sikkim Manipal University Page No.: 159

Data and File Structures Unit 10

So far as the implementation of fixed block allocation is concerned, this is

the simplest strategy. But main drawback of this strategy is the wastage of
space. For example, suppose each memory block is of size 1k (1024 bytes);
now for a request of a memory block, say, of size 1.1k we have to avail 2
blocks (that is 2k memory space), thus wasting 0.9k memory space. Making
the size of the block too small reduces the wastage of space; however, it
also reduces the overall performance of the scheme.
10.3.2 Variable block storage allocation
To overcome the disadvantages of fixed block storage, blocks of variable
sizes are used, which is represented in the figure 10.4. Here also linked lists
play a vital for the management of memory blocks. The procedures used for
allocation and deallocation of memory blocks from the variable block
storage are as follows.

Figure 10.4: Availing a node from a pool with variable sized blocks.
Procedure GETNODE(NODE)
If (AVAIL=NULL) then
Print “Memory is insufficient”
Exit.
Endif
Ptr=AVAIL
While ([Link] is not NULL) and
([Link]<SIZEOF(NODE)) do
ptr1=ptr
ptr=[Link]
Endwhile
if ([Link] is NULL) and
([Link]<SIZEOF(NODE)) then
Print” Memory request is too large: unable to serve”
Else
[Link]=[Link]
Return (ptr)
Endif
Exit
Sikkim Manipal University Page No.: 160
Data and File Structures Unit 10

This procedure assumes the blocks of memory are stored in ascending

order of their sizes. The node structure maintains a field to store the size of
the block, namely SIZE. SIZEOF() is a method that will return the size of the
node. The above procedure initially check for the NULL status of AVAIL list
and proceeds with the search for the exact size of block which is requested
and return the same, if the pool does not have the requested size it will
return the bigger size of block.

Procedure RETURNNODE(ptr)
Ptr1=AVAIL
While ([Link] < ptr. SIZE) and ([Link] ≠ NULL) do
Ptr2=ptr1
Ptr1=[Link]
Endwhile
If ([Link] <[Link]) then
[Link] =ptr
[Link]=ptr1
Else
[Link]=ptr
[Link]=NULL
Endif
Exit

Procedure RETURNNODE() will return the used block of memory to the

memory pool. While returning unless like fixed block, it searches for the size
the existing pool where it can be inserted. Because we assume that the free
pool memory blocks are arranged in ascending order. So while returning,
procedure will find the place according the size of the returning block and
the same will be inserted into the memory pool.

Self Assessment Questions

1. Pick the correct option:
Free memory in the free storage area generally holds the memory as
____________________ block
a) contiguous
b) continuous
c) non-contiguous
d) non-continuous
Sikkim Manipal University Page No.: 161
Data and File Structures Unit 10

2. Read the following statements and pick the correct option:

The two types of storage allocation are:
1) fixed block storage allocation
2) variable block storage allocation
3) fixed non-contiguous storage allocation
4) variable contiguous storage allocation.
a) 1,3
b) 2,4
c) 1,2
d) 1,4
3. Procedure _________________ will return the used block of memory
to the memory pool.

10.4 First Fit Storage Allocation

In the first fit algorithm, the allocator keeps a list of free blocks (known as
the free list) and, on receiving a request for memory, scans along the list for
the first block that is large enough to satisfy the request. If the chosen block
is significantly larger than that requested, then it is usually split, and the
remainder added to the list as another free block. The first fit algorithm
performs reasonably well, as it ensures that allocations are quick. When
recycling free blocks, there is a choice as to where to add the blocks to the
free list – effectively in what order the free list is kept.
With the variable size blocks, we encounter the problem of fragmentation,
which did not appear in the case of fixed size requests. There are two types
of memory fragmentation which can arise; they are internal and external
fragmentation.
Fragmentation: In computer storage, fragmentation is a phenomenon in
which storage space is used inefficiently, reducing storage capacity and in
most cases performance. The term is also used to denote the wasted space
itself.
Internal fragmentation: Internal fragmentation occurs when more storage
is allocated than is actually requested. This left over space, known as slack
space, causes a degradation of system performance. For example, space
can be left over between the last byte of the file and the first byte of the next
sector. This slack space can add up and eventually cause system
performance to degrade.
Sikkim Manipal University Page No.: 162
Data and File Structures Unit 10

External fragmentation: External fragmentation occurs when free memory

becomes divided into several small blocks over time. For example, this can
cause problems when an application requests a block of memory of
1000bytes, but the largest contiguous block of memory is only 300bytes.
Even if ten blocks of 300 bytes are found, the allocation request will fail
because they are not contiguous. This can be caused by an excessive
amount of clutter on a system. Total memory space exists to satisfy a
request, but it is not contiguous.
If we assume the free list has a AVAIL being the address of the list head,
LINK(AVAIL) being a pointer to the first block on the free list , and
SIZE(AVAIL) being set to 0. Then general algorithm for servicing a request
first a block of size N can be formulated as
Function ALLOCATE_FIRST (AVAIL, N, MIN) Given AVAIL, the address of
the list head, and N the size of block requested, this function returns p, the
address of the block of length ≥ N, SIZE(p) set to the actual length of the
block. Variable MIN keep tracks of waste memory to avoid fragmentation
means, no block of size MIN or smaller will be formed by splitting a
particular block. K is variable contains the difference between the requested
and the available block size. Q is a variable pointing to the block previous p
in the linked list of available block.
ALLOCATE_FIRST (AVAIL, N, MIN)
1. [Initialize]
QAVAIL
PLINK(Q)
2. [find block large enough for request]
Repeat while p≠ NULL
If SIZE(p) ≥ N
then k SIZE(p)-N
if k≤ MIN
then LINK(Q)LINK(p)
else SIZE(p)k
pp+k
SIZE(p)  N
Return(p)
Else Q  p
P LINK(Q)
3. [No suitable block]
Return (NULL)

Sikkim Manipal University Page No.: 163

Data and File Structures Unit 10

The above algorithm starts searching block which is large enough for the
request. If the size of the current block is greater than or equal to the
requested size then it will split the block. But if the fragment is less than the
minimum size then release the entire block of storage otherwise release the
block of requested size and return the address to the block. If the current
block is lesser than the request then move on to search of block in the free
list. If the process not able to identify till the end of the free list it will return
the status as no suitable block found.
Modification can be done on first-fit algorithm in order to reduce its search
time. Modification is search for a suitable block at the point where the
previous search terminated, rather than always with the first block. If so the
smaller blocks will be eventually scattered rather accumulating in the
beginning of the list. ALLOCATE_FIRST_ROVER is the modified first-fit
algorithm.

ALLOCATE_FIRST_ROVER(AVAIL, N,MIN, ROVER)

1. [Initialize]
QROVER
PLINK(Q)
TIME0
2. [Find large enough block].
Repeat while TIME=0 or Q ≠ ROVER
If p = NULL
then QAVAIL
pLINK(Q)
TIME1
else if SIZE(p) ≥ N
then k SIZE(p)-N
if k ≤ MIN
then LINK(Q)LINK(p)
ROVERQ
else SIZE(p)k
ROVERp
Pp+k
SIZE(p)N
Return(p)
else Q p
pLINK(Q)
3. [No suitable block]
Return (NULL)

Sikkim Manipal University Page No.: 164

Data and File Structures Unit 10

ROVER is a new variable going to points to the last examined free node
return by the previous function p. TIME is a flag associated with the
traversal of the list. This flag is set to 1 when the end of the list is
encountered. k is a local variable which contains the difference between the
size of a block and the requested block size. Q is also a local variable and
points to the block previous to p in the linked list of available blocks.
Self Assessment Questions
4. Co-relate:
Internal fragmentation: more storage is allocated than is actually
requested :: External fragmentation: free memory is divided into several
_______________
5. Say true or false:
In the first fit algorithm, the allocator keeps a list of free blocks and, on
receiving a request for memory, and starts allocating from first block to
satisfy the request.

10.5 Storage Release

Now we are going to discuss what “Storage release” is., It is the process of
releasing an allotted memory and returning it to the free list. We can simply
add this to the free list as unordered free list. After subsequent process, the
list will contain the large number of small blocks, which leads to increasing
time of allocation routine and some time we may unable to meet certain
requests because of all blocks are simply too small. To overcome this
problem, we are going to form one block out of two contiguous free blocks.
New released block is check for contiguity with its predecessor and
successor blocks on the free list, and merged with them whenever contiguity
occurs, then the free list always contain the smallest number of blocks. The
following algorithm can be used to insert a block on the free list, merging it
as necessary with contiguous neighbors.

Sikkim Manipal University Page No.: 165

Data and File Structures Unit 10

Procedure FREE_BLOCK (AVAIL, RB, ROVER)

1. [initialize optimally]
If RB>ROVER
then Q ROVER
else Q AVAIL
p  LINK(Q)
2. [find predecessor and successor in sorted list]
Repeat while p ≠ NULL and RB > p
Qp
P LINK (Q)
3. [collapse with successor, p?]
If p = NULL or RB + SIZE (RB) ≠ p
then LINK(RB)p
else LINK(RB)LINK(p)
SIZE(RB) SIZE(RB)+ SIZE(p)
If ROVER=p
then ROVERRB
4. [Collapse with predecessor, Q?]
If Q =AVAIL or Q+SIZE(Q) ≠ RB
then LINK(Q)RB
else LINK(Q)=LINK(RB)
SIZE(Q)=SIZE(Q)+SIZE(RB)
5. [Finished]
Return

Initially the address of RB(Returned Block) is compared with the

[Link] is the variable indicates the starting point for searching in
the allocation routine and the RB is the address of the block to returned.. If
RB is greater than the ROVER then search starts at the variable starting
point, otherwise search starts at the list head (QAVAIL). It starts searching
for predecessor and successor of the returned block in the free storage list.
If an allocated block exists between the freed block and its successor or at
the end of the free storage list then insert the block in the free list, otherwise
collapse the block with its successor in the free list. If an allocated block
exists between the freed block and its predecessor are at the front of the

Sikkim Manipal University Page No.: 166

Data and File Structures Unit 10

free storage list then insert the block in the free list, otherwise collapse the
block with its predecessor in the free list.

10.6 Buddy Systems

The buddy memory allocation technique is a memory allocation algorithm
that divides memory into partitions to try to satisfy a memory request as
suitably as possible. This system makes use of splitting memory into halves
to try to give a best-fit. According to Donald Knuth, the buddy system was
invented in 1963 by Harry Markowitz. In comparison to other simpler
techniques such as dynamic allocation, the buddy memory system has little
external fragmentation, and has little overhead trying to do compaction of
memory. Because of the way the buddy memory allocation technique works
there may be a moderate amount of internal fragmentation - memory wasted
because the memory requested is a little larger than a small block, but a lot
smaller than a large block. (For instance, a program that requests 66K of
memory would be allocated 128K, which results in a waste of 62K of
memory).Buddy system falls between dynamic and fixed partitioning.
The partitioning in buddy system: The buddy system of partitioning relies
on the fact that space allocations can be conveniently handled in sizes of
power of 2. There are two ways in which the buddy system allocates space.
Suppose we have a hole which is the closest power of two. In that case, that
hole is used for allocation. In case we do not have that situation then we
look for the next power of 2 hole size, split it in two equal halves and
allocate one of these. Because we always split the holes in two equal sizes,
the two are buddies". Hence, the name buddy system. We shall illustrate
allocation using a buddy system. We assume that initially we have a space
of 1024 K. We also assume that processes arrive and are allocated
following a time sequence as shown in figure 10.5, With 1024 K or (1 M)
storage space we split it into buddies of 512 K, splitting one of them to two
256 K buddies and so on till we get the right size. Also, we assume scan of
memory from the beginning. We always use the first hole which
accommodates the process. Otherwise, we split the next sized hole into
buddies. Note that the buddy system begins search for a hole as if we had a
fixed number of holes of variable sizes but turns into a dynamic partitioning
scheme when we do not find the best-fit hole. The buddy system has the
advantage that it minimizes the internal fragmentation. However, it is not

Sikkim Manipal University Page No.: 167

Data and File Structures Unit 10

popular because it is very slow. In Figure 10.5 we assume the requirements

as (P1:80 K); (P2:312 K); (P3:164 K); (P4:38 K). These processes arrive in
the order of their index and P1 and P3 finish at the same time.

Figure 10.5: Buddy system allocations

Binary buddy system algorithm

acquire(x): x <= 2k, the corresponding free list is searched
 If there is a block in this list, it is allocated;
 Otherwise a block of size 2k+1, 2k+2, and so on is searched and taken off
the free list. The block is divided into two buddies. One buddy is put on
the free list for the next lower size and the other is either allocated or
further splinted if needed.
release(x): The block is placed back in the free list of its size, and
 if its buddy is also free they are combined to form a free block of size
2k+1. This block is then moved to the corresponding free list.
 If its buddy is free they are combined to form a free block of size 2k+2,
which is then moved to the appropriate free list and so on.
Advantage:
Both acquire( ) and release( ) operations are fast.
Disadvantages:
Only memory of size that is a power of 2 can be allocated, internal
fragmentation can happen if memory request is not a power of 2.

Sikkim Manipal University Page No.: 168

Data and File Structures Unit 10

When a block is released, its buddy may not be free, resulting in external
fragmentation.

10.7 Garbage Collection

Garbage collection is the systematic recovery of pooled computer storage
that is being used by a program when that program no longer needs the
storage. This frees the storage for use by other programs (or processes
within a program). It also ensures that a program using increasing amounts
of pooled storage does not reach its quota (in which case it may no longer
be able to function). Garbage collection is an automatic memory
management feature in many modern programming languages, such as
Java and languages in the .NET framework. Languages that use garbage
collection are often interpreted or run within a virtual machine like the JVM.
In each case, the environment that runs the code is also responsible for
garbage collection. In older programming languages, such as C and C++,
allocating and freeing memory is done manually by the programmer.
Memory for any data that can't be stored within a primitive data type,
including objects, buffers and strings, is usually reserved on the heap. When
the program no longer needs the data, the programmer frees that chunk of
data with an API call. Because this process is manually controlled, human
error can introduce bugs in the code. Memory leaks occurs when the
programmer forgets to free up memory after the program no longer needs it.
Other times, a programmer may try to access a chunk of memory that has
already been freed, leading to dangling pointers that can cause serious
bugs or even crashes. Programs with an automatic garbage collector (GC)
try to eliminate these bugs by automatically detecting when a piece of data
is no longer needed. Basic principles of garbage collection are:
1) Find data objects in a program that cannot be accessed in the future.
2) Reclaim the resources used by those objects.
Garbage collection frees the programmer from manually dealing with
memory deallocation. As a result, certain categories of bugs are eliminated
or substantially reduced:
 Dangling pointer bugs, which occur when a piece of memory is freed
while there are still pointers to it, and one of those pointers is then used.
By then the memory may have been re-assigned to another use, with
unpredictable results.

Sikkim Manipal University Page No.: 169

Data and File Structures Unit 10

 Double free bugs, which occur when the program tries to free a region
of memory that has already been freed, and perhaps already been
allocated again.
 Certain kinds of memory leaks, in which a program fails to free memory
occupied by objects that will not be used again, leading, over time, to
memory exhaustion.
Reachability of an object can be defined as an object for which, there exists
some variable in the program environment leads to it, either directly or
through references from other reachable objects. Objects can be reachable
in two ways. Roots are objects generally can reach includes all the objects
referred locally or globally. Secondly any reference from the reachable
object is also reachable of transitive closure nature. In a program the objects
which can not be reached is called Syntactic garbage, and those objects
that are never used by the program are called semantic garbage.
The garbage collector can reclaim only objects that have no references. An
object that is reachable cannot be garbage collected by the garbage
collector. Such a reference is known as a strong reference. An object is
eligible for garbage collection if it does not contain any strong references,
irrespective of the number of weak references it contains. A short weak
reference does not track resurrection while a long weak reference tracks
resurrection. The primary advantage of maintaining weak references to an
object is that it allows the garbage collector to collect or reclaim memory of
the object if it runs out of memory in the managed heap.
Self Assessment Questions
6. Buddy system falls between dynamic and fixed __________________.
7. Read the following statements and pick the correct option:
Basic principles of garbage collection are:
1) Scan for unallocated memory space.
2) Find data objects in a program that cannot be accessed in the future.
3) Delete the allocated data.
4) Reclaim the resources used by those objects.
a) 1, 2
b) 2, 4
c) 3, 4
d) 2, 3

Sikkim Manipal University Page No.: 170

Data and File Structures Unit 10

8. Co-relate:
Objects which cannot be reached:_______________: : Objects that
are never used : Semantic garbage.

10.8 Summary
Dynamic data structures are data structures that grow and shrink as you
need them to by allocating and deallocating memory from a place called the
heap. They are extremely important for programming languages, because
they allow the programmer to exactly control memory consumption. In this
unit we discussed, what is dynamic memory management how fixed and
variable block of memories are allocated and de-allocated and how the first-
fit and best-fit algorithms are useful for allocating memory. Buddy system is
one of the memory allocation technique through which we can easily identify
the suitable free area in the quickest way. There are many techniques
dealing with allocation of memory but once the memory is allotted it needs
to be de-allocated to free the memory. Hence we also discussed the
concept of storage release. ,. Finally we highlighted the concept of garbage
collection, which is the process of recovering unused objects or variable
memory so that those can be used by the other programs. Garbage
collection process can be triggered either manually or the appropriate
functions can be called.

10.9 Terminal Questions

1. Explain the meaning of dynamic storage management.
2. Differentiate fixed and variable storage allocations.
3. Describe first-fit storage allocation.
4. Explain the concept of storage release.
5. What is the significance of buddy system?
6. What do you mean by garbage collection?

10.10 Answers
Self Assessment Questions
1. c) non-contiguous
2. c) Fixed block storage allocation, Variable block storage allocation
3. RETURNNODE()
4. small blocks

Sikkim Manipal University Page No.: 171

Data and File Structures Unit 10

5. False
Correct answer: In the first fit algorithm, the allocator keeps a list of free
blocks and, on receiving a request for memory, scans along the list for
the first block that is large enough to satisfy the request.
6. partitioning
7. b) 2, 4
8. Syntactic garbage

Terminal Questions
1. All the program need to manipulate the data in order to complete the
task. These data should be stored in the memory for manipulation, so
these data can be managed in two different ways. Like static storage
management and dynamic storage management. (Refer section 10.2 for
detail)
2. This is the straight forward method in which, all the blocks are of
identical in size. In variable block storage allocation blocks of variable
sizes are used. (Refer section 10.3 for detail)
3. In the first fit algorithm, the allocator keeps a list of free blocks (known as
the free list) and, on receiving a request for memory, scans along the list
for the first block that is large enough to satisfy the request. (Refer
section 10.4)
4. Storage release is the process of releasing an allotted memory and
returning it to the free list. (Refer section 10.5 for detail)
5. The buddy memory allocation technique is a memory allocation
algorithm that divides memory into partitions to try to satisfy a memory
request as suitably as possible. (Refer section 10.6)
6. Garbage collection is the systematic recovery of pooled computer
storage that is being used by a program when that program no longer
needs the storage. (Refer section 10.7)

Sikkim Manipal University Page No.: 172