International Journal of Trend in Scientific Research and Development (IJTSRD)

Volume 3 Issue 5, August 2019 Available Online: www.ijtsrd.com e-ISSN: 2456 – 6470

Analysis of Allocation Algorithms in Memory Management

Lae Wah Htun1, Moh Moh Myint Kay1, Aye Aye Cho2
1AssistantLecturer, 2Associate Professor
1,2University of Computer Studies, Hinthada, Myanmar

How to cite this paper: Lae Wah Htun | ABSTRACT

Moh Moh Myint Kay | Aye Aye Cho Memory management is the process of controlling and coordinating computer
"Analysis of Allocation Algorithms in memory, assigning portions called blocks to various running programs to
Memory Management" Published in optimize overall system performance and also known as memory allocation.
International Placement algorithms are implemented to determine the slot that can be
Journal of Trend in allocated process amongst the available ones in the partitioned memory.
Scientific Research Memory slots allocated to processes might be too big when using the existing
and Development placement algorithms hence losing a lot of space due to internal fragmentation.
(ijtsrd), ISSN: 2456- In dynamic partitioning, external fragmentation occurs when there is a
6470, Volume-3 | sufficient amount of space in the memory to satisfy the memory request of a
Issue-5, August process but the process’s memory request cannot be satisfied as the memory
2019, pp.1985- IJTSRD26731 available is in a non-contiguous manner. This paper describes how to resolve
1987, external fragmentation using three allocation algorithms. These algorithms are
https://doi.org/10.31142/ijtsrd26731 First-fit, Best-fit and Worst-fit. We will present the implementation of three
algorithms and compare their performance on generated virtual trace.
Copyright © 2019 by author(s) and
International Journal of Trend in Scientific KEYWORDS: Best-fit, First-fit, Worst-fit, Performance, Memory Management
Research and Development Journal. This 1. Introduction
is an Open Access article distributed Memory Management is the function responsible for allocating and managing
under the terms of computer’s main Memory. Different memory allocation algorithms have been
the Creative devised to organize memory efficiently. Allocation algorithms are implemented
Commons Attribution to determine the slot that can be allocated a process amongst the available ones
License (CC BY 4.0) in the partitioned memory block. Allocating a single contiguous section of
(http://creativecommons.org/licenses/by memory to each process is the most primitive method of memory management,
/4.0) usually called partitioning.

In partitioning, the simplest partitioning method is dividing size partition compared to equal size partition, memory
memory into several fixed-sized partitions in advance, called wastage is minimized, and may not give best throughput as
fixed partitioning. Fixed partitioning is the oldest and some partitions may be unused. The unequal size partitions
simplest technique used to put more than one processes in use two types of queues where processes are assigned to
the main memory. In fixed partitioning, there are two memory blocks. They are multiple queue and single queue.
methods: equal-sized partitioning and unequal-sized In multiple queues, each process is assigned to the smallest
partitioning. In equal-sized partitioning, any process whose partition in which it fits and minimizes the internal
size is less than or equal to the partition size can be loaded fragmentation problem. In single queue, the process is
into any available partition. Fixed size partitions suffer from assigned to the smallest available partition and the level of
two types of problems; they are overlays and internal multiprogramming is increased. If process loaded is much
fragmentation. smaller than any partition either equal or unequal, then it
suffers from internal fragmentation in which memory is not
If a process is larger than the size of the partition then it used efficiently. To overcome this problem, an approach
suffers from overlaying problem in which only required known as dynamic partitioning was developed. Partitioning
information will be kept in memory. Overlays are extremely may be done dynamically, called dynamic partitioning. In
complex and time consuming task. When the memory dynamic partitioning, external fragmentation occurs when
assigned to the process is slightly larger than the memory there is a sufficient amount of space in the memory to satisfy
requested by the process this creates free space in the the memory request of a process but the process’s memory
allocated causing internal fragmentation. It occurs when request cannot be satisfied as the memory available is in a
fixed sized memory blocks are allocated to the processes. non-contiguous manner. A method for overcoming external
fragmentation is compaction. The difficulty with compaction
In multiple queues, each process is assigned to the smallest is that it is a time-consuming and requires relocation
partition in which it fits and minimizes the internal capability. Therefore, different strategies may be taken as to
fragmentation problem. In single queue, the process is how space is allocated to processes: the common placement
assigned to the smallest available partition and the level of algorithms are Firs-fit, Best-fit and Worst-fit.
multiprogramming is increased the size of each block in
fixed partition is varied where processes are assigned to the 2. Background of Theory
blocks where it fits exactly: in other words, processes may be Modern operating systems provide efficient memory
queued to use the best available partition. In the unequal management and still research is being conduct to improve

@ IJTSRD | Unique Paper ID – IJTSRD26731 | Volume – 3 | Issue – 5 | July - August 2019 Page 1985
 International Journal of Trend in Scientific Research and Development (IJTSRD) @ www.ijtsrd.com eISSN: 2456-6470
the way the memory is allocated for applications because the Implementation in Best-fit:
main problem faces by memory allocation algorithms is to 1. Input memory blocks with size and processes with size.
efficiently allocating the demanded memory blocks to the 2. Initialize all memory blocks as free.
demanding applications with the minimum response time 3. Start by picking each process and find the minimum
along with minimum memory loss in the shape of traditional block size that can be assigned to current process i.e.,
memory loss problem called the fragmentation of memory. find min(blockSize[1]),blockSize[2],………,blockSize[n] >
We will use the placement algorithm to efficiently allocate processSize[current] it found then assign it to the
the processes in the main memory. current process.
4. If not then leave that process and keep checking the
A. First-fit further processes.
In First-fit, scan the memory from the beginning and allocate
the first available block that is large enough. It is one of the Calculation with Best-fit, above the problem describes in
fastest algorithms as it would search only as little as First-fit
possible. But, the remaining unused memory areas left after In Best-fit:
allocations become waste if it is too smaller. Thus request for 212KB is put in 300KB partition
large memory requirement cannot be accomplished. We will 150KB is put in 200KB partition
prove that the following problem, which algorithm makes 375KB is put in 400KB partition
the most efficient use of memory. 950KB is put in 1000KB partition
Implementation in First-fit: 350KB is put in 500KB partition
1. Input memory blocks with size and processes with size. 632KB is put in 700KB partition
2. Initialize all memory blocks as free. 400KB is put in 600KB partition
3. Start by picking each process and check if it can be 717KB is put in 800KB partition
assigned to current block. 811KB is put in 900KB partition
4. If size-of-process <= size-of-block if yes then assign and
check for next process
5. If not then keep checking the further blocks.

For example: Given ten memory partitions of 500KB, 200KB,

800KB, 400KB, 100KB, 700KB, 300KB, 600KB, 1000KB,
900KB (in order), How would the First-fit, Best-fit, Worst- fit
algorithms place processes of 212KB, 150KB, 375KB, 950KB,
350KB, 632KB, 400KB, 717KB, 811KB (in order)? Which
algorithm makes the most efficient use of memory?

In First-fit:
212KB is put in 500KB partition Figure2. Best-fit Output results
150KB is put in 288KB (new partition 288KB=500KB-
212KB) C. Worst-fit
375KB is put in 800KB partition In Worst-fit, the entire list of blocks must be searched the
950KB is put in 1000KB partition largest block and allocate this block. Reduce the rate of
350KB is put in 425KB (new partition 425KB=800KB-375KB production of small gaps. In contrast, this strategy produces
632KB is put in 700KB partition the largest leftover block, which may be big enough to hold
400KB is put in 400KB partition another process. But, if a process requiring larger memory
717KB is put in 900KB partition arrives at a later stage then it cannot be accommodated as
811 must wait the largest hole is already split and occupied.

Implementation in Worst-fit:
1. Input memory blocks with size and processes with size.
2. Initialize all memory blocks as free.
3. Start by picking each process and find the maximum
block size that can be assigned to current process i.e.,
find max (blockSize[1]), blockSize[2],……., blockSize[n] >
processSize[current] it found then assign it to the
current process.
4. If not then leave that process and keep checking the
further processes.

Calculation with Worst-fit, above the problem describes in

Figure1. First-fit Output results
First-fit
In Worst-fit:
B. Best-fit
212KB is put in 1000KB partition
In Best-fit, the entire list of blocks must be searched the
150KB is put in 900KB partition
closest in size to the request and allocate this block. Memory
375KB is put in 800KB partition
utilization is much better than First-fit as it searches the
950KB must wait
smallest free partition first available. But, it is slower and
350KB is put in 788KB (new partition 788KB=1000KB-
may even tend to fill up memory with tiny useless holes.
212KB)

@ IJTSRD | Unique Paper ID – IJTSRD26731 | Volume – 3 | Issue – 5 | July - August 2019 Page 1986
 International Journal of Trend in Scientific Research and Development (IJTSRD) @ www.ijtsrd.com eISSN: 2456-6470
632KB is put in 750KB (new partition 750KB=900KB- 4. Conclusion
150KB) Main memory management is very important in operating
400KB is put in 700KB partition system. Simulations have shown that both First-fit and Best-
717KB must wait fit are better than Worst-fit in terms of decreasing both time
811KB must wait and storage utilization. Neither First-fit nor Best-fit is clearly
better in terms of storage utilization but First-fit is generally
faster. Among three algorithms, Best-fit algorithm makes the
most efficient use of memory. In this paper, we also proved
that Best-fit algorithm is the best in memory utilization.

References
[1] Rachael Chikorrie, Okuthe P. Kogeda, Manoj Lall: “An
Optimized Main Memory Management Partitioning
Placement Algorithm”, Pan African conference on
Science, computing and Telecommunications (PACT)
Figure3. Worst-fit Output results Publisher, July 27-29, Kampala Uganda 2015.

3. Experimental Results [2] Abraham Silerschatz, Peter Beer Galvin, and Greg
In this paper, we have been seen that Best-fit algorithm is Gange, “Operating System Concepts”, John Wiley &
the best among three placement algorithms. We are Sons, INC., January 1, 2002.
explained with a problem, how to calculate this algorithm. [3] William Stallings, “Operating System Internals and
These algorithms cannot eliminate external fragmentation. Design Principles”, March 20, 2017.
To overcome this problem, we must use compaction.
[4] Ledisi G. Kabari, TamunoomieS. Gogo, ”Efficiency of
Memory Allocation Algorithms Using Mathematical
Model”, International Journal of Emerging Engineering
Research and Technology Volume 3, Issue 9,
September, 2015, PP 55-67
[5] Muhammand Abfullh Awais, “Challenges and
Techniques for Algorithms in Relation with Today’s
Real Time Needs”, International journal of Multi-
Disciplinary Sciences and Engineering, vol.7, No.3,
March 2016.

Figure4. Comparison of Three Allocation Algorithms for

Performance

@ IJTSRD | Unique Paper ID – IJTSRD26731 | Volume – 3 | Issue – 5 | July - August 2019 Page 1987