FOR FREE CONTENT
- Introduction: OS
- Booting Process
- Command Interpreter
- Dual mode of operation
- System Calls
- Difference between system call and library call
- Interrupt and Trap
- Introduction
- Scheduling Criteria, Terms and Concepts
- Different Type Scheduling Algorithms
- Longest Job First
- Longest Remaining Time First
- Highest Response Ratio Next (HRRN)
- Priority Scheduling
- Least Completed Next (LCN) Scheduling
- Multi-Level Queue Scheduling
- Multilevel Feedback Queue Scheduling
- Guaranteed Scheduling
- Fair Share Scheduling
- Lottery Scheduling
- Multi-Processor Scheduling
- Deadline Scheduling
- Rate-Monotonic Scheduling
- POSIX Real-Time Scheduling
- Priority Inversion
- Proportional Share Scheduling
- Comparison table of Scheduling Algorithm
- Algorithm Evaluation for Scheduling
- Important concept of MM
- Memory Representation as Address
- Memory layout for a Process
- Logical and Physical Address Space
- Necessity of Memory Management
- Introduction
- Concept of Non-contiguous memory allocation
- Basic concept of Paging
- Address Translation
- Process of Paging Method
- Calculation of Offset for paging
- Calculation of Logical Address Bit and number of Pages
- Calculation of Physical Address Bit and number of Frames
- Calculation of Page Table Size
- Organization of MMU
- Why Page size power of 2
- Paging Address Calculation: example1
- Paging Numeric Problem: Example2
- Paging Address Calculation: Example3
- Paging Address Calculation: Question1
- Some Important Question 2
- Paging Address Translation: Question3
- UGC NET Paging Question
- GATE Paging Question
- Number of information at Page Entry
- Exams Question on Page Entry Information
- Exam Question: Page Entry Information
- Calculates Page Table Entry Size
- Calculates Page Size
- Calculation of Optimal Page Size
- Question on Optimal Page Size
- Hashed Page Table with Example
- Inverted Page Table with Gate Question
- Question on Inverted Page Table
- Multi-Level Paging
- Multi-level paging: Example1
- Multi-level paging: Example2
- Allocation of Frames
- Subject Mock
Best Fit and Worst Fit
3) Best Fit
Allocate the smallest hole that is big enough. We must search the entire holes unless the list is ordered by size. It chooses the smallest hole possible and it allocates the process.
The best-fit allocation method keeps the free/busy lists in order by size, smallest to largest.
Example for the Best Fit
Now a process P4 of size 15 MB tries to allocate at the memory. So, as per the best-fit algorithm, it chooses the smallest one possible, so, it chooses a hole with a size 20 MB for process P4, whereas if we think about the first fit, it will choose Hole-40 MB for process P4.
.png)
Advantage of Best Fit
It tries to reduce the wastage of space because it allocated the smallest appropriate holes for requesting process.
Disadvantage of Best Fit
i) It requires O(n) time to search the entire list and find the smallest one.
ii) As if it chooses the smallest possible space, so, the very small size of hole is free and not fit farther for any process, it will wastage at the above the best-fit example, at best for P4 process allocated space is hole-18 MB, so, after allocated P2, the new hole is 2 MB and it too small to allocate any process at future, so, it is wastage.
.png)
So, sometimes best fit is not an efficient one. But in the case of the first fit, P2 allocated it H-40 MB, so, after allocated P2, the free hole will be 22 MB, it will good hole for a size
4) Worst fit
Allocate the largest hole. Again, we must search the entire list, unless it is sorted by size. In case of worst fit, unlike the best fit, it searches the entire hole and chooses the largest hole possible, and allocates the process.
The best-fit allocation method keeps the free/busy lists in order by size, largest to smallest.
Here it requires O(n) time like the best fit to search the entire list and find the largest one. But one advantage is there compare to best first, after allocating process as per worst fit free holes size is large and it is useful to allocate other processes.
Hereafter allocating free hole size is large i.e. better but still, it requires O(n) to search the entire hole.
.png)
