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.