Comparative Analysis of Memory Management Algorithms in OS

This assignment delves into the critical aspects of memory management within operating systems. It begins with an abstract highlighting the importance of efficient memory utilization, especially in real-time systems. The introduction defines the role of the operating system as an interface between hardware and users, emphasizing its responsibility for managing memory through various techniques. A literature review examines dynamic memory management, the buddy system, and different fit algorithms, including two-level and TLSF algorithms, discussing their strengths and weaknesses in real-time contexts. The methodology focuses on understanding and applying various memory management methods. The assignment covers best-fit and first-fit allocation algorithms, fragmentation (internal and external), and page number calculations. It also explores scheduling algorithms like FIFO, SJN, SRT, and Round Robin, analyzing their impact on job execution and page fault reduction. The conclusion emphasizes the trade-offs of different memory management algorithms and highlights the suitability of TLSF for real-time systems due to its low internal fragmentation and fast response time.

Answer – 1
Abstract: In a present era of computing, applications as well as operating systems, efficient
memory not able to survive without management, especially if an application for an undefined
long time should be subject to serious load. To increase the performance resources should be
used efficiently. Real time systems have to use memory to perform efficiently from time to time,
otherwise, the purpose of real time system will be lost. It is completely a responsibility of OS to
give assistance for the memory management processes through various methods as it acts as the
key resource such as the interface that runs on hardware plus applications. Diverse memory
allocation algorithms have been designed to organize memory according to the needs and
scenarios of use in different timestamps, but there are issues and challenges to provide full
support for the reality of these allocations. In any operating system, our management is
controlled by various aspects like memory management, hardware level, application level and
operating system level memory management in particular.
Introduction: Operating system acts as the interface between the hardware and the end user. It
controls the operation and processing of the computer system. And it is also defined as “a
program that manages the computer hardware”. The mainframe operating system is designed
mainly to optimize the use of hardware. The personal computer OS’s support multifaceted
games, diverse business applications as well as for all in between, the operating system for
mobile or versatile computers give an atmosphere in which the user can effortlessly interface to
execute the program with a computer. In this way, some OS are planned to be well-situated, for
others to become efficient, and by a few combination of the other two.
Literature Review:
Dynamic memory management plays an important role in memory management because the
overhead associated with static memory management is allocated for the program that runs on
time compilation and does not use any block of memory Which cannot be used by other
applications, efficient use of assets and more vibrant memory allocations always heap memory
record structure is used, the stack using static memory allocation use DMA makes more efficient
than static memory allocation(Vishwasrao Nilesh, 2016).
A new diversity of the famous buddy system has been named as a tertiary buddy, which is a
better division and reaction time than the differences in other friend systems, with the extension
of binary buddy system over time. Tertiary buddy's observation will be presented in the
forthcoming sections (Yadav Divakar).
Many research has been done to improve the dynamic memory recurrences and the basics of
different and sequential fit are always in the improvement area, which has to be improved. Two-
level different fit algorithms are one of the improvements of the different fit algorithm.
Considering the requirements of real-time systems, different algorithms have been proposed

separately from two levels(I.Ripoll). Even some improvements have been done on different
algorithms at two levels so that it can be made more suitable for the real-time system.
Searching Strategy: Initially, I discovered memory management techniques and methods in the
OS are simply increases my understanding about memory management and not to miss the
necessary concepts and ideas. In order to obtain relevant research papers with a detailed analysis
of emerging memory management techniques, every possible search was conducted in IEEE,
digital library, Google Scholar and research paper such as research paper such as research gate
were made available in the third part. To get relevant research knowledge I used several
keywords like memory management, operating system memory allocation, real time OS memory
allocation, issues in memory allocation and techniques for dynamic memory allocation. By
researching on various research publishing platforms, I found detailed information about
operating system techniques for memory management, allocation, algorithms, and issues
associated to these techniques.
Selection: After basic studies of operating system memory management, problems related to
operating system management as well as traditional techniques of memory management and
these appropriate techniques are never utilized for the real-time memory practice, which is less
for applications and operating systems (Heikkilä).
Study Methodology: Rather than a pure proportional analysis of the OS memory management
strategies, the main center of attention was on indulgence of OS, memory management methods
or techniques and understanding those situations, where these method or techniques are applied.
Therefore to focus more on the outcome, an overview as well as essential details of a few new
plus pre-existing techniques or methods has been presented appropriately in this study and the
important issues associated to these entire algorithms end to the complications associated with
these methods or techniques as well as requirements. To answer real-time unique applications
research questions.
Conclusion: Every technology related to vibrant memory management also has professionals
and cons as well as can be superlatively used in a special situation. Mainly algorithms are better
versions of formerly discussed schemes like the sequential and separate fit as well as TLSF. The
analysis demonstrates that the mention of TLSF is suitable for the real time system in the
technique because the internal fragmentation is very low due to TLSF, its reaction time is
extremely good, and it is a basic demand of all real time frameworks, where time. The most
significant factor is. Apart from this, TLSF allocation in addition to allocation time is a small
steady time which makes it faster than all other conventional techniques.

Answer – 2
a) Best fit Memory Allocation Algorithm
With best fit allocation algorithm the size of the memory block needed by the job is calculated
by the below formula
¿ block ¿=n+ ¿ header ¿
After getting the size of block the memory block list is scanned for the smallest block which has
with
nWords≥¿ block ¿ .
Thus for our problem the allocation of jobs to the memory blocks will be as shown bellow
Job Number Requested Memory Allocated Memory Block Memory Block Size
Job A 57K Block 4 300K (high-order memory)
Job C 50K Block 3 200K
Job D 701K Block 1 900K (low-order memory)
Job B which requires 920K will not be allocated to the remaining Block 2 which is of size 910K
since the memory block size is not enough to satisfy its requirement, it requires at least 920
memory block size.
b) First Fit Memory Allocation Algorithm
In this approach jobs are allocated to the free memory blocks, by searching through the free
memory blocks and once an enough memory block is found it is allocated, without considering
the memory blocks which haven’t been reached. It finishes after finding the first suitable free
partition.
Job Number Requested Memory Allocated Memory Block Memory Block Size
Job A 57K Block 1 900K (low-order memory)
Job C 50K Block 2 910K
The bellow jobs were not allocated to any free memory block since, after allocating Job A to
Block 1; the remaining blocks were not enough for B and after allocating Job 2 to Block 3, and
none of the remaining blocks was enough for job D. Thus the below jobs were not allocated.

Job D 701K
Job B 920K
Answer – 3
Fragmentation occurs within a very vibrant memory allocation framework when several free
blocks are seriously very small to convince any request.
External Fragmentation: It occurs when the dynamic algorithm of memory allocation allocates a
few memory as well as a very small piece remains that cannot be successfully utilized. If a large
amount of external fragmentation happens than the usable memory reduced drastically. Overall
memory space presents just to convince a request, however it is never be contiguous. When a
process loads and is removed from memory, the blank space creates a hole in the memory space,
and there are several holes in a memory space and this is named as external fragmentation. Even
though the very first fit as well as the perfect fit can change the actual external fragmentation
amount, it cannot be completely eliminated. Compaction can be the perfect solution for outer
fragmentation.
Internal Fragmentation: This is a space which is wasted within allocated memory systems or
blocks due to constraints on the permissible sizes of all allocated blocks. All owed or allocated
memory might be to some extent larger than the requested memory therefore this difference in
sizes cause partition of memory, however not being utilized. Internal Fragmentation simply a
area or a region as well as a page which never utilized by the work occupying that particular
region or for a page. Also this space is completely unavailable for employ by the framework
until that specific job is not finished completely and the region or page is released. When the
process is slightly more than the requested memory from the memory process, it creates an
empty space in an allotted block, which creates internal fragmentation.
The fundamental reason behind incidents of internal as well as external or outer fragmentation is
that inner or internal fragmentation happens when the memory is split into blocks of fixed size
while the external fragmentation happens when the memory variable is divided into the size
blocks.
When the allocated memory block in the process becomes to some extent larger than the
requested memory, after that space left in an allocated memory model or block is due to internal
fragmentation. On the other hand, when the procedure is detached from memory, then it creates
complimentary space, which causes a hole within a memory and it is named as external
fragmentation.
Answer – 4
a) Number of pages needed to store the entire job
471
100 +1=5( page no 0−4 )

To store page number: 3 bits
To store offset:7 bits
b) 100∗0+0=0
Page 0=Dispacement 0 , Address 0
100∗1+0=100
Page 1=Dispacement 0 , Address100
132∗1+0=132
Page 1=Dispacement 32 , Address 132(Page 1is where instruction islocated )
100∗2+0=200
Page 2=Dispacement 0 , Address200
100∗3+0=300
Page 3=Dispacement 0 , Address 300
100∗4+ 71=471
Page 4=Dispacement 71 , Address 400
Answer – 5
a) By using FIFO algorithm,
Total number of page fault occurs=10
Page fault ratio ( failure ratio )= 9
12∗100=75 %

No page fault ratio= 2
12∗100=16.67 %
b) By using FIFO
Total number of page fault occurs=9
Page fault ratio= 9
12∗100=75 %
No page fault ratio= 3
12∗100=25 %
c) Yes, by increasing the size of memory, the number of page fault would decrease.
Answer – 6
a) In FCFS jobs are executed in the order of their arrival, therefore order of processing is,
A−B−C−D−E
Since, arrival time is 0,
The whole time needed to practice five jobs is,
(CPU time of A) + (CPU time of B)+ (CPU time of C) + (CPU time of D ) + (CPU time
of E)
¿ 12+2+15+7+3
Total time ¿ process all five jobs=39 ms
Turnaround time=finishtime−arrival time
Turnaround tiime of A=12−0=12
Turnaround tiime of B=14−0=14
Turnaround tiime of C=29−0=29

Turnaround tiime of D=36−0=36
Turnaround tiime of E=39−0=39
Average turnaround time= 12+14 +29+36+39
5 =26 ms
b) In SJN or SJF, a job with shortest execution time is selected for execution.
In above problem the jobs are processed in order,
B−E−D− A−C
The whole time needed to practice five jobs is,
(CPU time of B) + (CPU time of E)+ (CPU time of D) + (CPU time of A ) + (CPU time
of C)
¿ 2+3+7+12+15=39
Total time ¿ process all five jobs=39 ms
Turnaround time=finishtime−arrival time
Turnaround tiime of B=2−0=2
Turnaround tiime of E=5−0=5
Turnaround tiime of D=12−0=12
Turnaround tiime of A=24−0=24
Turnaround tiime of C=39−0=39
Average turnaround time= 2+ 5+12+ 24+39
5 =16.4 ms
Answer – 7
a) FCFS
B,C,D,E will be in queue by the time the first job A is finished their arrival time is less
than the CPU cycle of A. It is executed based on the First Come First Serve basis on
arrival time.
b) SJN
Shortest CPU cycle is for job E having 1 CPU cycle, so it will execute first.
Based on the ascending order of CPU cycle B,D, C, A will be in queue.
c) SRT
Shortest Remaining Time will select the job for execution which has the least amount of
remaining time until its completion.
Job E has the shortest remaining time and so it will be executed first. When it is finished,
then jobs in queue will be in order as B, D, C, A, C, D, A, A
d) Round Robin
In Round Robin the time slices gets assigned to each of the jobs in equal portions and in a

circular order which handles all processes irrespective of their priority.
Since we are using a quantum time of 5 but ignoring the context switching and natural
wait time required, so
job A is executed first. After it gets finished then next jobs will be in order as B, C, D, E,
A, C, D, A.

References:
[1].NileshVishwasrao and PrabhudevIrabashetti (2016), “Dynamic Memory Allocation: Role
in Memory Management”, International Journal of Current Engineering and Technology,
Vol. 4, No. 2, April 2014.
[2].Divakar Yadav and Ashok Sharma (2016) “Tertiary Buddy System for Efficient Dynamic
Memory Allocation”, Conference: Proceeding SEPADS'10 Proceedings of the 9th
WSEAS international conference on Software engineering, parallel and distributed
systems, At Cambridge.
[3].Masmano, I.Ripoll, A. Crespo, and J. Real (2004)” TLSF: a new dynamic memory
allocator for real-time systems”, Real-Time Systems, 2004. ECRTS 2004. Proceedings.
16th Euromicro Conference.
[4].Mohamed A. Shalan (2003) “Dynamic Memory Management for Embedded Real-Time
Multiprocessor System On a Chip”, A Thesis in Partial Fulfillment of the Requirements
for the Degree of Doctor of Philosophy from School of Electrical and Computer
Engineering ,Georgia Institute of Technology, November 2003.
[5].Seyeon Kim (2014).“Node-oriented dynamic memory management for real-time systems
on ccNUMA architecture systems”, University of York Department of Computer Science,
conference paper April 2014.
[6].ValtteriHeikkilä (2017)“A Study on Dynamic Memory Allocation Mechanisms for Small
Block Sizes in Real-Time Embedded Systems”, University of Oulu Department of
Information Processing Science.