DHA SUFFA UNIVERSITY
Department of Computer Science
CS-2004L
Operating Systems
Fall 2020
Need = Max – Allocation
The system is in a safe state since the sequence < P2, P4, P5, P1, P3> satisfies safety criteria.
Advantage of Banker’s algorithm
Avoids deadlock and it is less restrictive than deadlock prevention.
DHA SUFFA UNIVERSITY
Department of Computer Science
CS-2004L
Operating Systems
Fall 2020
Disadvantage of Banker’s algorithm
Only works with a fixed number of resources and processes.
ASSIGNMENT # 11
1. Write a shell script or a C++/ Java program to implement Banker’s Algorithm for Deadlock
avoidance.
SUBMISSION GUIDELINES
● Take a screenshot of each task (code and output).
● Place all the screenshots in a single word file labeled with Roll No and Lab No. e.g.
‘cs172xxx_Lab01’.
● Convert the file into PDF.
● Make a folder labeled with Roll No, place the pdf and .cpp/.java/.sh files in this folder
● Submit the folder at LMS
DHA SUFFA UNIVERSITY
Department of Computer Science
CS-2004L
Operating Systems
Fall 2022
Lab 12 – Memory Management Algorithms (Best, First and Worst)
Objective(s):
● Understanding of Memory Management.
● Understanding of First Fir, Best Fit and Worst Fit algorithm.
● To implement First Fit, Best Fit and Worst Fit algorithm.
Memory Management
Memory management is the process of controlling and coordinating computer memory,
assigning portions called blocks to various running programs to optimize overall system
performance. Memory management resides in hardware, in the OS (operating system), and in
programs and applications.
Basic Requirements that Drive Memory Design
● The primary memory access time must be as small as possible. This need influences both
software and hardware design.
● The primary memory must be as large as possible. Using virtual memory, software and
hardware can make the memory appear to be larger than it actually is.
● The primary memory must be cost-effective. The cost cannot be more than a small
percentage of the total cost of the computer.
Memory Manager
The purpose of the memory manager is
● To allocate primary memory space to processes
● To manage the process address space into the allocated portion of the primary
memory.
● To minimize access times using a cost-effective amount of primary memory
DHA SUFFA UNIVERSITY
Department of Computer Science
CS-2004L
Operating Systems
Fall 2020
Memory Management Algorithm
In an environment that supports dynamic memory allocation, the memory manager must keep a
record of the usage of each allocatable block of memory. This record could be kept by using
almost any data structure that implements linked lists. An obvious implementation is to define a
free list of block descriptors, with each descriptor containing a pointer to the next descriptor, a
pointer to the block, and the length of the block. The memory manager keeps a free list pointer
and inserts entries into the list in some order conducive to its allocation strategy. A number of
strategies are used to allocate space to the processes that are competing for memory.
1. Best Fit Algorithm
2. First Fit Algorithm
3. Worst Fit Algorithm
First Fit Algorithm
The first fit approach is to allocate the first free partition or hole large enough which can
accommodate the process. It finishes after finding the first suitable free partition.
Advantages
Fastest algorithm, because it searches as little as possible
Disadvantages
The remaining unused memory areas left after allocation become waste if it is too small. Thus
requests for larger memory requirements cannot be accomplished.
DHA SUFFA UNIVERSITY
Department of Computer Science
CS-2004L
Operating Systems
Fall 2020
ALGORITHM:
1. Start the program.
2. Get the number of memory partitions and their sizes.
3. Get the number of processes and values of block size for each process.
4. Initialize all memory blocks as free.
5. Start by picking each process and check if it can be assigned to the current block.
6. If size-of-process <= size-of-block if yes then assign and check for the next
process.
7. If not then keep checking the further blocks.
8. Stop the program.
Example:
Input:
BlockSize[] = {100, 500, 200, 300, 600}
ProcessSize[] = { 212, 417, 112, 426}
DHA SUFFA UNIVERSITY
Department of Computer Science
CS-2004L
Operating Systems
Fall 2020
Output:
Best Fit Algorithm
The best fit deals with allocating the smallest free partition which meets the requirement of the
requesting process. This algorithm first searches the entire list of free partitions and considers
the smallest hole that is adequate. It then tries to find a hole which is close to the actual process
size needed.
ALGORITHM:
1. Start the program.
2. Get the number of memory partitions and their sizes.
3. Get the number of processes and values of block size for each process.
4. Initialize all memory blocks as free.
5. Start by picking each process and find the minimum block size that can be assigned to
current process i.e., find min(bockSize[1], blockSize[2],……blockSize[n]) >
processSize[current], if found then assign it to the current process.
6. If not then leave that process and keep checking the further processes.
7. Stop the program.
DHA SUFFA UNIVERSITY
Department of Computer Science
CS-2004L
Operating Systems
Fall 2020
Advantages
Memory utilization is much better than first fit as it searches the smallest free partition first
available.
Disadvantages
It is slower and may even tend to fill up memory with tiny useless holes.
Example:
Input:
BlockSize[] = {100, 500, 200, 300, 600}
ProcessSize[] = { 212, 417, 112, 426}
Output:
Worst Fit Algorithm