Summary
Highlights
Scheduling is essential for multitasking operating systems to give the appearance of multiple tasks executing simultaneously. This applies to multiple threads within a single program (e.g., games) and multiple users in a multi-user environment. The scheduler manages which processes execute next and for how long. Processes move through states: ready queue, running, blocked (if awaiting input), or suspended (if time runs out).
First Come First Serve (FCFS) schedules processes in the strict order they arrive, similar to a supermarket queue. If a process takes a long time, all subsequent processes must wait until it finishes or leaves the CPU.
Shortest Job First (SJF) prioritizes the process that requires the shortest execution time. For this to work, the scheduler needs to know the estimated execution time of each process beforehand. Processes run until completion or exit the CPU.
Round Robin allocates a fixed amount of time, called a 'time slice' or 'quantum,' to each process. If a process doesn't complete within its time slice, it is suspended and moved to the back of the ready queue. This ensures fair allocation of CPU time among processes.
Shortest Remaining Time (SRT) is a preemptive algorithm similar to Shortest Job First. It can suspend a currently running process if a new process arrives with a shorter remaining execution time. This allows for more responsive handling of urgent tasks.
Processes can be blocked while running if they require data from slow devices like hard disks. While blocked, other processes can run. Once the required data is received, the blocked process generates an interrupt to signal the scheduler that it's ready to rejoin the queue.
Multi-Level Feedback Queues (MLFQ) use multiple ready queues, differentiating processes based on their CPU and I/O needs. Preferences are given to processes with short CPU bursts or high I/O bursts. Processes can be demoted to lower-priority queues if they use too much CPU time or promoted to higher-priority queues if they are I/O bound or interactive. MLFQ also prevents starvation by promoting processes that have waited too long in low-priority queues. Different queues can use different scheduling algorithms.
A summary table is provided, listing the five discussed scheduling algorithms (First Come First Serve, Shortest Job First, Round Robin, Shortest Remaining Time, and Multi-Level Feedback Queues) with brief descriptions and whether they are preemptive or non-preemptive.