Operating system scheduling algorithms decide which process gets the CPU and for how long. This cheat sheet helps students compare common scheduling methods and compute key performance measures. It is useful for solving exam problems, reading Gantt charts, and understanding how an operating system balances speed, fairness, and responsiveness.
The core ideas include arrival time, burst time, completion time, turnaround time, waiting time, and response time. FCFS runs jobs in arrival order, SJF chooses the shortest job, priority scheduling chooses the most important job, and round robin gives each process a time quantum. Important formulas include turnaround time = completion time - arrival time and waiting time = turnaround time - burst time.
Good scheduling reduces average waiting time while avoiding starvation and excessive context switching.
Key Facts
- Turnaround time = completion time - arrival time.
- Waiting time = turnaround time - burst time.
- Response time = first start time - arrival time.
- Average waiting time = total waiting time for all processes / number of processes.
- Average turnaround time = total turnaround time for all processes / number of processes.
- CPU utilization = busy CPU time / total elapsed time x 100%.
- In round robin scheduling, a process runs for at most one time quantum before moving to the back of the ready queue if it is not finished.
- Shortest Job First is optimal for minimizing average waiting time when all burst times are known and processes are available at the same time.
Vocabulary
- Process
- A program in execution that needs CPU time, memory, and operating system resources.
- Ready Queue
- The list of processes that are loaded in memory and waiting to use the CPU.
- Burst Time
- The amount of CPU time a process needs to complete its current CPU work.
- Time Quantum
- The maximum time slice a process may run before being preempted in round robin scheduling.
- Preemption
- The act of interrupting a running process so another process can use the CPU.
- Starvation
- A condition where a process waits for a very long time because other processes keep being chosen first.
Common Mistakes to Avoid
- Confusing waiting time with turnaround time is wrong because turnaround time includes both waiting and running, while waiting time excludes CPU burst time.
- Ignoring arrival times is wrong because a process cannot be scheduled before it has entered the ready queue.
- Using the wrong priority direction is wrong because some systems treat smaller priority numbers as higher priority, while others treat larger numbers as higher priority.
- Forgetting context switching effects is wrong when the problem includes a context switch cost, because that extra time increases total elapsed time and can affect completion times.
- Choosing too large or too small a round robin quantum is wrong because a very large quantum acts like FCFS, while a very small quantum causes many context switches.
Practice Questions
- 1 Processes P1, P2, and P3 arrive at time 0 with burst times 6, 2, and 4. Using nonpreemptive SJF, find the average waiting time.
- 2 Processes P1, P2, and P3 have arrival times 0, 1, and 2 and burst times 5, 3, and 1. Using FCFS, find each completion time and the average turnaround time.
- 3 Using round robin with time quantum 2, schedule P1 and P2 if both arrive at time 0 and have burst times 5 and 3. Find the completion time of each process.
- 4 Explain why round robin is often better for interactive systems than FCFS, even if it may have more context switches.
Understanding Operating System Scheduling Algorithms
A process does not spend its whole life waiting for the CPU. It may run briefly, request a file from storage, wait for keyboard input, or send data over a network. While it waits for an input or output event, it is blocked and cannot be chosen.
When it becomes ready again, it joins the ready queue. The scheduler makes its decision from this queue. A dispatcher then performs the switch to the chosen process.
This switch saves the old process state and loads the new one. Saving registers, program position, and memory information takes time.
That time is called context switching overhead. It does useful work for the operating system, but it does not advance the program a student is measuring.
The main difference between scheduling policies is how much they know and whether they can interrupt a running process. Non-preemptive FCFS lets a process keep the CPU until it finishes or blocks. This can create the convoy effect.
One long job at the front makes many short jobs wait behind it. Preemptive versions of shortest job scheduling can stop a longer task when a newly arrived task needs less remaining CPU time. This often improves short task performance, though it causes more switches.
Real systems cannot know an exact future burst time. They estimate it from earlier behavior. Priority values have a similar problem.
A low priority process can wait for a very long time if higher priority work keeps arriving. Aging gradually raises the priority of a waiting process to reduce this risk.
Round robin is common in time-sharing systems because users notice delay before a program first reacts. A text editor, web browser, or terminal feels better when it gets a short chance to run quickly. The time quantum needs careful choice.
A very large quantum makes round robin behave much like FCFS. A very small quantum gives each process frequent turns, but the machine spends too much time switching states. On a Gantt chart, mark every arrival before choosing the next process.
If no process has arrived, draw an idle period. For each completed process, track when it first received CPU time separately from when it finally finished. These two moments describe different user experiences.
Exam questions often make hidden assumptions that change the answer. Check whether all processes arrive at time zero, whether lower or higher priority numbers win, and whether a tie is broken by arrival order or process number. For preemptive questions, check the queue again whenever a new process arrives.
For round robin, add processes that arrive during a time slice in the stated order before selecting the next turn. Keep a clear timeline rather than trying to calculate values mentally. CPU utilization can fall even when the scheduler is sensible, especially when every process is waiting for input or output.
A scheduler cannot keep the CPU busy if no ready work exists. In real operating systems, scheduling is usually a combination of policies for interactive programs, background services, and urgent system tasks rather than one simple rule.