Mastering Process Scheduling: From FCFS to Multilevel Feedback Queues

Prerequisite Knowledge

Difference between Non‑Preemptive and Preemptive Scheduling

Non‑Preemptive Scheduling : Once a process starts executing, the operating system will not allocate the CPU to another process until the running process voluntarily releases it.

Preemptive Scheduling : The OS can forcibly pause a running process and assign the CPU to another process, even if the original process has not completed.

Common Process Scheduling Algorithms

First‑Come‑First‑Served (FCFS) Scheduling

Non‑Preemptive (FCFS)

Processes are queued in the order they arrive; the earliest arrival is executed first until it finishes or blocks, then the next process is selected.

Drawback : If a long job is followed by many short jobs, the short jobs must wait a long time, which is unfavorable for short‑job response.

Shortest Job First (SJF) Scheduling

Non‑Preemptive (SJF)

Jobs with the shortest execution time are prioritized, improving overall system throughput.

Drawback : Long jobs may suffer starvation when many short jobs are present.

Highest Response Ratio Next (HRRN) Scheduling

Non‑Preemptive (HRRN)

The algorithm balances short and long jobs by calculating a response ratio for each job before scheduling.

If waiting times are equal, shorter service time yields a higher response ratio, so short jobs are prioritized.

If service times are equal, longer waiting time yields a higher response ratio, so long jobs are prioritized.

Drawback : The response ratio must be recomputed each time, adding overhead.

Round‑Robin (RR) Scheduling

Preemptive (RR)

CPU time is divided into equal time slices; each process runs for one slice before the next process gets a turn, ensuring fairness.

Time slice: a fixed duration allocated to a process during which it may execute.

If the time slice is too short, frequent context switches increase system overhead.

If the time slice is too long, short jobs experience long response times.

Typical time slice values are 20 ms–50 ms.

Priority Scheduling

Both preemptive and non‑preemptive variants exist.

Processes are scheduled based on their priority level.

Priorities are often adjusted dynamically: long‑running processes may have their priority lowered, while processes that have waited long may have their priority raised.

Non‑Preemptive : When a higher‑priority process appears, it is scheduled after the current process finishes.

Preemptive : When a higher‑priority process appears, the current process is suspended and the higher‑priority process runs immediately.

Drawback : Low‑priority processes can suffer starvation.

Multilevel Feedback Queue Scheduling

Preemptive (Multilevel Feedback Queue)

Multiple queues are arranged from high to low priority; higher‑priority queues have shorter time slices.

Feedback : When a new process enters a higher‑priority queue, it preempts the currently running process.

Within each queue, processes are scheduled using Round‑Robin.

New processes start in the highest‑priority queue; if they do not finish within the allotted time slice, they are demoted to the next lower‑priority queue.

When the high‑priority queue becomes empty, the scheduler selects processes from the next lower queue.

If a process arrives in a higher‑priority queue, the currently running process is paused and placed at the end of its own queue.

This algorithm balances the needs of both long and short jobs, providing reasonable response times for all.