What Is Multilevel Feedback Queue Scheduling Algorithm In Operating System
The Multilevel Feedback Queue Scheduling (MLFQS) algorithm is a complex CPU scheduling method in operating systems that improves upon multilevel queue scheduling by allowing processes to move between queues. This algorithm is designed to handle various types of processes, assigning them dynamically based on their behavior and CPU burst time, which helps optimize CPU utilization and responsiveness.
Method to Solve the Multilevel Feedback Queue Scheduling(MLFQS) in os
- Step 1: Initialize multiple queues with different priority levels, where higher-priority queues have shorter time quantums.
- Step 2:Place each new process in the highest-priority queue.
- Step 3: Apply Round Robin scheduling in each queue.
- Step 4: If a process uses its entire time quantum without completing, it is moved to a lower-priority queue.
- Step 5: If a process in a lower-priority queue does not finish within its time quantum, it moves down again.
- Step 6: When a process in any queue becomes I/O bound, it can move back up to a higher-priority queue upon resuming.
- Step 7: Continue this reallocation until each process completes or is terminated.
Advantages and Disadvantages of Multilevel Feedback Queue Scheduling
| Advantages | Disadvantages |
|---|---|
| Efficient handling of processes with varying CPU burst times. | Complex to implement and manage multiple queues. |
| Improved CPU utilization due to dynamic priority adjustment. | Starvation can occur for lower-priority processes. |
| Reduces turnaround time for I/O-bound and interactive processes. | Increased overhead for context switching between queues. |
| Allows fair sharing of CPU time based on process needs. | Difficulty in choosing appropriate time quantum for each queue. |
| Minimizes response time for short tasks or interactive processes. | Performance can degrade if too many high-priority processes exist. |
| Adaptable to system load and changes in process behavior. | Requires fine-tuning of parameters to avoid inefficiency. |
Why Multilevel Feedback Queue Scheduling Is Better Than Other Scheduling Algorithms?
Multilevel Feedback Queue Scheduling is advantageous over simpler algorithms like First-Come-First-Serve (FCFS), Round Robin (RR), and Shortest Job Next (SJN) because it adapts dynamically to the varying requirements of processes. By allowing processes to move between different priority queues, MLFQS prevents process starvation, optimizes CPU time usage, and reduces turnaround time for interactive and I/O-bound processes. This adaptability ensures a balanced performance for systems handling diverse workloads, making it an efficient choice for many modern operating systems.
Question 1 : find the average Turn Around Time and Waiting Time of
following processes using MLFQS(MULTILEVEL FEEDBACK QUEUE SCHDULING)
process scheduling algorithm? Consider the following processes with
their Arrival Time, Burst Time. Question criteria :
(1) There are four queue Q1, Q2, Q3, Q4
(2) Queue with their time stamp Q1(T.S=4), Q2(T.S=8), Q3(T.S=16),
Q4(FCFS)
(in Q1, Q2, Q3, we use Round Robin and in Q4 we use FCFS scheduling
algorithms)
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 1 | 6 |
| P2 | 4 | 8 |
| P3 | 5 | 12 |
| P4 | 8 | 14 |
| P5 | 12 | 6 |
| P6 | 10 | 10 |
| P7 | 8 | 8 |
| P8 | 16 | 6 |
Formula:
Turnaround Time (TAT) = Completion Time - Arrival Time
Waiting Time (WT) = Turnaround Time - Burst Time
Solution:
Gantt Chart
Calculations:
| Process | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|
| P1 | 35 | 34 | 28 |
| P2 | 39 | 35 | 27 |
| P3 | 47 | 42 | 30 |
| P4 | 71 | 63 | 49 |
| P5 | 67 | 55 | 49 |
| P6 | 65 | 55 | 45 |
| P7 | 59 | 51 | 43 |
| P8 | 69 | 53 | 47 |
Average Turnaround Time:
(34 + 35 + 42 + 63 + 55 + 55 + 51 + 53) / 8 = 48.5
Average Waiting Time:
(28 + 27 + 30 + 49 + 49 + 45 + 43 + 47) / 8 = 39.75
Question 2 : find the average Turn Around Time and Waiting Time of
following processes using MLFQS(MULTILEVEL FEEDBACK QUEUE SCHDULING)
process scheduling algorithm? Consider the following processes with
their Arrival Time, Burst Time. Question criteria :
(1) There are four queue Q1, Q2, Q3, Q4
(2) Queue with their time stamp Q1(T.S=2), Q2(T.S=4), Q3(T.S=8),
Q4(FCFS)
(in Q1, Q2, Q3, we use Round Robin and in Q4 we use FCFS scheduling
algorithms)
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 6 |
| P2 | 5.0 | 2 |
| P3 | 8.0 | 5 |
| P4 | 10 | 8 |
| P5 | 14 | 4 |
| P6 | 18 | 3 |
| P7 | 22 | 2 |
| P8 | 24 | 10 |
Formula:
Turnaround Time (TAT) = Completion Time - Arrival Time
Waiting Time (WT) = Turnaround Time - Burst Time
Solution:
Gantt Chart
Calculations:
| Process | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|
| P1 | 8 | 8 | 2 |
| P2 | 7 | 2 | 0 |
| P3 | 21 | 13 | 8 |
| P4 | 36 | 26 | 18 |
| P5 | 30 | 16 | 12 |
| P6 | 29 | 11 | 8 |
| P7 | 24 | 2 | 0 |
| P8 | 40 | 16 | 6 |
Average Turnaround Time:
(8 + 2 + 13 + 26 + 16 + 11 + 2 + 16) / 8 = 11.75
Average Waiting Time:
(2 + 0 + 8 + 18 + 12 + 8 + 0 + 6) / 8 = 6.75