1
CSC351-Operating System
Week-6 Lecture-11
Semester 5
2
Round Robin
Preamble Scheduling
(Past lesson
brief)
Lahore Garrison University
3
Multilevel Queue
Ready queue is partitioned into separate queues, eg:
foreground (interactive)
background (batch)
Process permanently in each queue
Each queue has its own scheduling algorithm:
foreground – RR
background – FCFS
Scheduling must be done between the queues:
Fixed priority scheduling; (i.e., serve all from foreground then from
background). Possibility of starvation.
Time slice – each queue gets a certain amount of CPU time which it can
schedule amongst its processes; i.e., 80% to foreground in RR
20% to background in FCFS
Lahore Garrison University
4
Multilevel Queue Scheduling
Lahore Garrison University
5
Example Question
Consider the below table of four processes under Multilevel
queue scheduling. Queue number denotes the queue of the
process.
Priority of queue 1 is greater than queue 2. queue 1 uses Round
Robin (Time Quantum = 2) and queue 2 uses FCFS.
Lahore Garrison University
6
Solution
Lahore Garrison University
7
Practice Task 1:
Lahore Garrison University
8
Solution
Lahore Garrison University
Disadvantages of Multilevel 9
Queue Scheduling
The main disadvantage of Multilevel Queue
Scheduling is the problem of Starvation for lower-level
processes.
what is Starvation?
Well, due to starvation, lower-level processes either never
execute or have to wait for a long amount of time
because of lower priority or higher priority process taking
a large amount of time.
Lahore Garrison University
10
Multilevel Feedback Queue
A multilevel feedback queue (MLFQ) is a CPU scheduling algorithm that
uses multiple queues with varying priorities to manage process
execution. It dynamically adjusts priorities based on process behavior,
promoting or demoting processes between queues.
Lahore Garrison University
11
Features of MLFQ
Multiple queues: MLFQ maintains multiple queues with different priorities.
Feedback mechanism: The feedback mechanism in MLFQ scheduling
allows the adjustment of process priority based on its past behavior. If a
process exhausts its time slice in a lower-priority queue, it can be
promoted to a higher-priority queue to receive more CPU time.
Time slicing: Each process is assigned a specific time quantum to
execute in its current queue.
Dynamic priority adjustment: The feedback mechanism allows the
adjustment of process priority based on its behavior over time.
Preemption: It enables a high-priority process to interrupt and take
precedence over a low-priority process to ensure it receives the
necessary CPU time.
Lahore Garrison University
12
Example of Multilevel Feedback
Queue
Three queues:
Q0 – RR with time quantum 8 milliseconds
Q1 – RR time quantum 16 milliseconds
Q2 – FCFS
Scheduling
A new job enters queue Q0 which is served
RR
When it gains CPU, job receives 8
milliseconds
If it does not finish in 8 milliseconds, job
is moved to queue Q1
At Q1 job is again served RR and receives
16 additional milliseconds
If it still does not complete, it is
preempted and moved to queue Q2
Lahore Garrison University
13
Functionality of MLFQ
MLFQ scheduling requires configuring parameters such as the number of
queues, time quantum, and priority adjustment. These parameters
enable efficient resource utilization and ensure fairness in executing
processes.
Lahore Garrison University
14
Conclusion
The multilevel feedback queue (MLFQ) scheduling algorithm is a
versatile approach to CPU scheduling. It optimizes resource utilization by
dynamically adjusting priorities and utilizing multiple queues. MLFQ
enhances system responsiveness and overall performance with features
like preemption and task prioritization.
Lahore Garrison University
15
Pros & Cons
Lahore Garrison University
16
Reference
To cover this topics , different reference material has
been used for consultation.
Operating systems concept by Abraham siberchatz
edition 9
Tutorialspoint.com
Google.com
Lahore Garrison University
