Multilevel queue scheduling in Operating Systems - Step-by-Step Execution

Concept Flow - Multilevel queue scheduling

New process arrives

↓

Assign to a queue based on priority/type

↓

Select queue to schedule

↓

Schedule process from selected queue

↓

Process runs

↓

Process finishes or yields

↓

Repeat scheduling from queues

Processes are divided into separate queues by type or priority. The scheduler picks a queue and runs processes from it, repeating this cycle.

Execution Sample

Operating Systems

Queues:
  Q1: System processes (highest priority)
  Q2: Interactive processes
  Q3: Batch processes (lowest priority)
Schedule order: Q1 -> Q2 -> Q3
Run one process from each queue in turn.

This example shows three queues with different priorities. The scheduler runs one process from the highest priority queue first, then moves to the next queue.

Analysis Table

Step	Queue Selected	Process Chosen	Action	Result
1	Q1	P1 (System)	Run process	P1 runs
2	Q2	P2 (Interactive)	Run process	P2 runs
3	Q3	P3 (Batch)	Run process	P3 runs
4	Q1	P4 (System)	Run process	P4 runs
5	Q2	P5 (Interactive)	Run process	P5 runs
6	Q3	P6 (Batch)	Run process	P6 runs
7	Q1	No process	Skip queue	Move to Q2
8	Q2	No process	Skip queue	Move to Q3
9	Q3	No process	Skip queue	No processes left, scheduling ends

💡 All queues are empty, no processes left to schedule.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
Q1 Processes	[P1, P4]	[P4]	[P4]	[P4]	[]	[]	[]	[]	[]	[]
Q2 Processes	[P2, P5]	[P2, P5]	[P5]	[P5]	[P5]	[]	[]	[]	[]	[]
Q3 Processes	[P3, P6]	[P3, P6]	[P3, P6]	[P6]	[P6]	[P6]	[]	[]	[]	[]

Key Insights - 3 Insights

Why does the scheduler skip a queue when it has no processes?

Because the execution_table rows 7 and 8 show 'No process' and 'Skip queue', the scheduler moves on to the next queue to avoid waiting on empty queues.

How does the scheduler decide which queue to pick next?

The scheduler follows a fixed order of queues by priority, as shown in the concept_flow and execution_table, cycling through queues from highest to lowest priority.

What happens if a process in a lower priority queue is ready but higher priority queues are not empty?

The scheduler cycles through the queues in fixed order, so the lower priority process gets its turn even if higher priority queues have processes ready, as seen in step 3 of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which process runs and from which queue?

A P3 from Q3

B P2 from Q2

C P1 from Q1

D P4 from Q1

💡 Hint

Check the 'Queue Selected' and 'Process Chosen' columns at step 3 in the execution_table.

At which step does the scheduler find Q1 empty and skip it?

A Step 9

B Step 5

C Step 7

D Step 3

💡 Hint

Look for 'No process' and 'Skip queue' in the execution_table for Q1.

If a new system process arrives after step 9, what will change in the variable_tracker?

A Q3 Processes will have a new process added

B Q1 Processes will have a new process added

C Q2 Processes will have a new process added

D No changes because scheduling ended

💡 Hint

System processes belong to Q1 as shown in the variable_tracker start state.

Concept Snapshot

Multilevel queue scheduling divides processes into separate queues by priority or type.
Scheduler picks queues in fixed order, running processes from each queue in turn.
Higher priority queues run before lower priority ones.
Queues are independent; processes do not move between queues.
If a queue is empty, scheduler skips it and moves on.
Scheduling ends when all queues are empty.

Full Transcript

Multilevel queue scheduling organizes processes into different queues based on their priority or type. When a new process arrives, it is assigned to a specific queue. The scheduler then selects queues in a fixed priority order, running one process from each queue in turn. If a queue has no processes, the scheduler skips it and moves to the next queue. This cycle repeats until all queues are empty and no processes remain to be scheduled. This method ensures that higher priority processes get CPU time before lower priority ones, but processes do not move between queues once assigned.

Practice

1. What is the main characteristic of multilevel queue scheduling in operating systems?

easy

A. Processes move freely between queues during execution.

B. All processes are scheduled using the same method regardless of type.

C. Processes are divided into separate queues based on priority or type.

D. It uses a single queue with round-robin scheduling.

Solution

1. Step 1: Understand the queue division concept

   Multilevel queue scheduling divides processes into different queues based on their priority or type, such as system processes, interactive processes, etc.

2. Step 2: Recognize process movement rules

   Processes do not move between queues once assigned; each queue has its own scheduling method.

3. Final Answer:

   Processes are divided into separate queues based on priority or type. -> Option C

4. Quick Check:

   Multilevel queue = Separate queues by priority/type [OK]

Hint: Remember: fixed queues by type, no moving between them [OK]

Common Mistakes:

• Thinking processes can move between queues
• Assuming all queues use the same scheduling method
• Confusing with multilevel feedback queue

2. Which of the following is a correct statement about the scheduling method in multilevel queue scheduling?

easy

A. Processes are scheduled only after all queues are empty.

B. Each queue can have its own scheduling algorithm.

C. Scheduling is done randomly across all queues.

D. All queues must use the round-robin algorithm.

Solution

1. Step 1: Identify scheduling flexibility per queue

   In multilevel queue scheduling, each queue can use a different scheduling algorithm suitable for its process type.

2. Step 2: Eliminate incorrect options

   Options stating all queues use the same method or random scheduling are incorrect.

3. Final Answer:

   Each queue can have its own scheduling algorithm. -> Option B

4. Quick Check:

   Different queues = different scheduling methods [OK]

Hint: Each queue can pick its own scheduling style [OK]

Common Mistakes:

• Assuming all queues use round-robin
• Believing scheduling is random
• Thinking scheduling waits for all queues to empty

3. Consider a multilevel queue scheduling system with two queues: Queue 1 (high priority) uses FCFS, Queue 2 (low priority) uses Round Robin. If Queue 1 has 3 processes arriving first and Queue 2 has 2 processes arriving later, which queue's processes will be scheduled first?

medium

A. Queue 2 processes because Round Robin is fairer.

B. Both queues are scheduled alternately regardless of priority.

C. Queue 2 processes because they arrived later.

D. Queue 1 processes because it has higher priority.

Solution

1. Step 1: Identify priority order in multilevel queue

   Multilevel queue scheduling serves queues based on priority; higher priority queues are served before lower ones.

2. Step 2: Apply priority to given queues

   Queue 1 has higher priority, so its processes are scheduled first, regardless of scheduling method or arrival time of Queue 2.

3. Final Answer:

   Queue 1 processes because it has higher priority. -> Option D

4. Quick Check:

   Higher priority queue runs first [OK]

Hint: Higher priority queue always runs before lower ones [OK]

Common Mistakes:

• Thinking Round Robin queue runs first due to fairness
• Assuming arrival time overrides priority
• Believing queues are scheduled alternately

4. Identify the error in this description of multilevel queue scheduling: "Processes can move between queues if they wait too long in their current queue."

medium

A. This is incorrect; processes do not move between queues.

B. This is correct; processes move to higher priority queues.

C. This is correct; processes move to lower priority queues.

D. This is incorrect; processes move randomly between queues.

Solution

1. Step 1: Recall process movement rules in multilevel queue

   In multilevel queue scheduling, processes are assigned to a queue and remain there permanently.

2. Step 2: Compare with the given statement

   The statement says processes move between queues if waiting too long, which is false behavior for this scheduling type.

3. Final Answer:

   This is incorrect; processes do not move between queues. -> Option A

4. Quick Check:

   No process movement between queues [OK]

Hint: Processes stay fixed in their queue [OK]

Common Mistakes:

• Confusing with multilevel feedback queue
• Assuming aging causes queue changes
• Believing processes move randomly

5. In a multilevel queue scheduling system with three queues: System (highest priority), Interactive (medium priority), and Batch (lowest priority), how should CPU time be allocated if the System queue is always busy?

hard

A. System queue gets all CPU time; other queues wait until it is empty.

B. CPU time is shared equally among all queues regardless of priority.

C. Batch queue gets CPU time first to clear long jobs quickly.

D. Interactive queue preempts System queue when interactive tasks arrive.

Solution

1. Step 1: Understand priority handling in multilevel queue

   The CPU always serves the highest priority queue first until it is empty or blocked.

2. Step 2: Apply to given queues

   Since the System queue is highest priority and always busy, it will get all CPU time, causing other queues to wait.

3. Final Answer:

   System queue gets all CPU time; other queues wait until it is empty. -> Option A

4. Quick Check:

   Highest priority queue dominates CPU time [OK]

Hint: Highest priority queue runs exclusively if always busy [OK]

Common Mistakes:

• Assuming equal CPU sharing despite priority
• Thinking lower priority queues can preempt higher ones
• Believing batch jobs get priority to clear faster