what is Multilevel Queue Scheduling Algorithm In Operating System ?
In the Multilevel Queue Scheduling algorithm, the processes are divided into multiple queues based on specific characteristics, such as process priority or memory requirements. Each queue has its own scheduling algorithm, which could be First-Come-First-Serve (FCFS), Shortest Job First (SJF), or Round Robin (RR), depending on the type of processes it holds. This algorithm is typically used in scenarios where different types of processes need to be managed independently and efficiently.
Method for solving Multilevel Queue Scheduling (MLQS) in os
- Step 1: Divide the processes into multiple queues based on priority or process type.
- Step 2: Assign a scheduling algorithm to each queue according to the specific requirements of the processes in that queue.
- Step 3: Define the priority levels among queues, determining which queue should be given preference when multiple queues have processes ready to run.
- Step 4: If a process completes its execution in its assigned queue, it is removed; otherwise, it may be moved to another queue as per the system’s defined rules.
- Step 5: Repeat the above steps until all processes in all queues are completed.
Advantages and Disadvantages of Multilevel Queue Scheduling
| Advantages | Disadvantages |
|---|---|
| Enables specific scheduling policies for different types of processes, improving efficiency. | Static division of queues may lead to underutilization of resources if queues are imbalanced. |
| Allows easy prioritization of system processes over user processes, enhancing system performance. | Higher-priority queues can lead to starvation of processes in lower-priority queues. |
| Each queue can be customized to meet specific needs, offering flexibility. | Complex to implement and maintain, especially with a large number of queues and processes. |
| Reduces the turnaround time for certain high-priority processes. | Lack of interaction among queues can cause inefficiencies in overall CPU utilization. |
| Supports separation of long-term and short-term tasks. | Static assignment of processes means changes to process priorities are challenging. |
| Helps manage processes that require different resources effectively. | Once a process is assigned to a queue, it generally cannot be moved, reducing adaptability. |
Why Multilevel Queue Scheduling Is Better than Other Scheduling Algorithms?
Multilevel Queue Scheduling is particularly beneficial in environments where different categories of tasks require distinct scheduling policies. By allowing separate scheduling algorithms per queue and facilitating priority-based processing, it can deliver more efficient performance compared to a single algorithm for all processes. This makes it highly suitable for systems requiring quick responses for specific types of processes, as well as in multiuser environments, where prioritizing system tasks can help maintain system stability and responsiveness.
Question 1 : find the average Turn Around Time and Waiting Time of
following processes using MLQS(MULTILEVEL QUEUE SCHEDULING) process
scheduling algorithm? Consider the following processes with their
Arrival Time, Burst Time. Question criteria :
(1) There are three queue Q1, Q2, Q3
(2) In Q1 (sjf, non-preemptive), Q2(Round robin,
timestamp=2),Q3(FCFS)
| Process | Arrival Time | Burst Time | Queue name |
|---|---|---|---|
| P1 | 0 | 8 | Q2 |
| P2 | 1 | 6 | Q1 |
| P3 | 1 | 4 | Q3 |
| P4 | 2 | 3 | Q2 |
| P5 | 2 | 1 | Q1 |
| P6 | 3 | 4 | Q2 |
| P7 | 3 | 1 | Q1 |
| P8 | 4 | 2 | Q2 |
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 | 25 | 25 | 17 |
| P2 | 7 | 6 | 0 |
| P3 | 29 | 28 | 24 |
| P4 | 20 | 18 | 15 |
| P5 | 8 | 6 | 5 |
| P6 | 22 | 19 | 15 |
| P7 | 9 | 6 | 5 |
| P8 | 17 | 13 | 11 |
Average Turnaround Time:
(25 + 6 + 28 + 18 + 6 + 19 + 6 + 13) / 8 = 15.125
Average Waiting Time:
(17 + 0 + 24 + 15 + 5 + 15 + 5 + 11) / 8 = 11.5
Question 2 : find the average Turn Around Time and Waiting Time of
following processes using MLQS(MULTILEVEL QUEUE SCHDULING) process
scheduling algorithm? Consider the following processes with their
Arrival Time, Burst Time. Question criteria :
(1) There are three queue Q1, Q2, Q3
(2) In Q1 (Priority scheduling, premptive), Q2(sjf, preemptive) ,
Q3(Round robin, timestamp=1)
(for priority scheduling, take 1 is the highest priority)
| Process | Arrival Time | Burst Time | Queue Name | Priority |
|---|---|---|---|---|
| P1 | 0 | 8 | Q2 | |
| P2 | 1 | 6 | Q1 | 4 |
| P3 | 1 | 4 | Q3 | |
| P4 | 2 | 3 | Q2 | |
| P5 | 2 | 1 | Q1 | 1 |
| P6 | 3 | 4 | Q2 | |
| P7 | 3 | 1 | Q1 | 5 |
| P8 | 4 | 2 | Q2 |
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 | 25 | 25 | 17 |
| P2 | 8 | 7 | 1 |
| P3 | 29 | 28 | 24 |
| P4 | 14 | 12 | 9 |
| P5 | 3 | 1 | 0 |
| P6 | 18 | 15 | 11 |
| P7 | 9 | 6 | 5 |
| P8 | 11 | 7 | 5 |
Average Turnaround Time:
(25 + 7 + 28 + 12 + 1 + 15 + 6 + 7) / 8 = 12.625
Average Waiting Time:
(17 + 1 + 24 + 9 + 0 + 11 + 5 + 5) / 8 = 9
Question 3 : find the average Turn Around Time and Waiting Time of
following processes using MLQS(MULTILEVEL 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) In Q1(Round robin, timestamp=1), Q2(preemptive Priority scheduling), Q3(preemptive sjf ), Q4(FCFS)
(for priority scheduling, take 1 is the highest priority)
| Process | Arrival Time | Burst Time | Queue name | Priority |
|---|---|---|---|---|
| P1 | 0 | 6 | Q2 | 2 |
| P2 | 2 | 1 | Q1 | 1 |
| P3 | 6 | 4 | Q2 | 3 |
| P4 | 10 | 6 | Q3 | 7 |
| P5 | 18 | 12 | Q4 | 8 |
| P6 | 24 | 4 | Q1 | 10 |
| P7 | 26 | 3 | Q1 | 12 |
| P8 | 32 | 8 | Q2 | 5 |
| P9 | 36 | 6 | Q2 | 4 |
| P10 | 40 | 10 | Q3 | 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 | 7 | 7 | 1 |
| P2 | 3 | 1 | 0 |
| P3 | 11 | 5 | 1 |
| P4 | 17 | 7 | 1 |
| P5 | 61 | 43 | 31 |
| P6 | 31 | 7 | 3 |
| P7 | 29 | 3 | 0 |
| P8 | 46 | 14 | 6 |
| P9 | 42 | 6 | 0 |
| P10 | 56 | 16 | 6 |
Average Turnaround Time:
(7 + 1 + 5 + 7 + 43 + 7 + 3 + 14 + 6 + 16) / 10 = 10.9
Average Waiting Time:
(1 + 0 + 1 + 1 + 31 + 3 + 0 + 6 + 0 + 6) / 10 = 4.9