Memory management:
Memory management is the
functionality of an operating system which handles or manages primary memory
and moves processes back and forth between main memory and disk during
execution.
Memory management can be
categorized as:
o
Static memory management.
o
Dynamic memory management.
§ In
Static memory management, memory is allocated at compile time.
§ In
static memory management, required memory for given process is already known
and once the memory has been allocated, no changes can be done at run time.
§ In
Dynamic memory management, memory is allocated at run time.
§ While
in dynamic memory management, memory management unit explicitly keeping track
of allocated and free memory.
The advantage of
dynamic memory management is that it required less memory while in static
management more memory required.
Dynamic Memory management
can be further divided in two categories:
1) Manual memory
management
2) Automatic memory
management.
Manual memory management,
programmer can allocate or deallocate memory manually.
Automatic memory
management, memory management unit deallocate the
memory if object is out of scope.
The main methodology of
Dynamic Memory Allocator algorithm is keeping link list of unallocated memory
blocks and allocated memory blocks.
CONVENTIONAL ALGORITHMS:
There are four types of
conventional dynamic memory allocation/deallocation algorithms.
1) Sequential fit
2) Buddy allocator system
3) Indexed fit
4) Bitmapped fit
Ø Sequential
fit Algorithm:
Simplest algorithm for
dynamic memory allocator algorithm in which it maintains single link list of
unallocated memory blocks and unallocated blocks are allocated from this link
list via different mechanism
In first fit, the link list
is searched from starting and it will return the first block which is large
enough to satisfy the need. While in Next fit, unlike First fit it will search
from where the search was left off. In the Best Fit, the entire link list will
be searched and return the smallest block which will large enough to hold the
request. While in Worst Fit, unlike best fit it will return the largest block
Ø Buddy
Allocator Algorithm:
This algorithm uses an
array of link lists of unallocated blocks. Each list for allowable block size.
For example, list of 2N block size like 200 kb, 400 kb, 800 kb so on. The buddy
allocator finds a smallest block which is large enough to hold the request from
list of unallocated blocks.
Ø Indexed
Fit Algorithm:
This algorithm uses
structured index to implement desired fit. According to allocation policy, it
uses data structure likes tree or hash table for searching unallocated blocks.
Ø Bitmapped
Fit Algorithm:
This algorithm uses a
bitmap which represent weather heap is used or not. This map is a simple vector
of one bit flag with one bit corresponding to each word of heap area.
UNCONVENTIONAL
ALGORITHMS:
“Unconventional” itself
suggest that it is not usual or traditional. Here unconventional means to
overcome the issues of conventional algorithms, certain researchers have been
found new algorithms which are more accurate and perfect in terms of
performance for allocating memory to the processes.
Three algorithms are
explained:
1) Two level segregated
fit algorithm (TLSF)
2) Improved two level
segregated fit algorithm
3) Smart memory allocator
algorithm.
Ø Two
level segregated fit algorithm:
This algorithm resolves
the problem of worst case bound by preserving the efficiency of allocation or
deallocation.
In order to meet embedded
system constraint the TLSF algorithm has been made with strict constrain like
immediate merging, splitting threshold, good-fit strategy, no
reallocation, same strategy for all block sizes, memory is not cleaned up.
Immediate merging means
as soon as the memory block is freed, it would merge with its neighbor free
block to make a larger block.
Ø Improved
TLSF:
Improved TLSF is nothing
but improvement in two level segregated fit algorithm.
This algorithm is
proposed to improve the performance and efficiency in allocating small blocks
and reduce fragmentation, it uses different strategies to allocate blocks for
different sizes.
Ø Smart
Memory Allocator Algorithm:
This is a custom type of
dynamic memory algorithm having best response time and less memory
fragmentation.
This algorithm divides
memory blocks into two categories.
1.
Short-lived
2.
Long lived
The short-lived memory
blocks are allocated in the direction of lowest level to highest level from
heap while long-lived memory blocks are allocated from highest level to lowest
level.
As this algorithm
predicting memory object life scope, it can easily allocate memory block from
either short-lived or long-lived memory pool.
0 Comments