To solve CPU scheduling algorithm problems in Operating Systems, we must understand definitions of non-preemptive scheduling and preemptive scheduling.
Scheduling algorithms determine CPU allocation switches between processes. Operating systems implement scheduling mechanisms based on non-preemptive or preemptive principles.
Non-preemptive Scheduling: Once a process receives CPU allocation, it retains exclusive control until execution completes or it voluntarily yields CPU control.
Preemptive Scheduling: Allows suspending an active process. Higher priority incoming processes can interrupt and claim CPU control from currently running processes at any time without warning.
1. First-In, First-Out (FIFO) / FCFS Scheduling Algorithm
CPU is allocated to the earliest process requesting CPU in the ready queue. Follows strict non-preemptive scheduling.
- Turnaround Time: P1=24, P2=26, P3=28
- Average Turnaround Time: (24 + 26 + 28)/3 = 26
- Waiting Time: P1=0, P2=23, P3=24
- Average Waiting Time: (0 + 23 + 24)/3 = 15.67
2. Round Robin (RR) Scheduling Algorithm
The scheduler allocates CPU time slices (quantums) cyclically across all ready processes. This is a preemptive scheduling algorithm: when a process consumes its allotted time quantum, the OS preempts the CPU and assigns it to the next process. Unfinished processes return to the tail of the ready queue.
- Turnaround Time: P1=30, P2=6, P3=8
- Average Turnaround Time: (30 + 6 + 8)/3 = 14.67
- Waiting Time: P1=6, P2=3, P3=5
- Average Waiting Time: (6 + 3 + 5)/3 = 4.67
3. Priority Scheduling Algorithm
The process with highest priority is allocated CPU first. Can be implemented as non-preemptive or preemptive. Preemptive priority scheduling yields CPU when higher priority processes arrive in ready queue.
-
Non-preemptive Case
* Turnaround Time: P1=24, P2=26, P3=28
* Average Turnaround Time: (24 + 26 + 28)/3 = 26
* Waiting Time: P1=0, P2=23, P3=25
* Average Waiting Time: (0 + 23 + 25)/3 = 16 -
Preemptive Case:
* Turnaround Time: P1=30, P2=3, P3=5
* Average Turnaround Time: (30 + 3 + 5)/3 = 12.67
* Waiting Time: P1=6, P2=0, P3=2
* Average Waiting Time: (6 + 0 + 2)/3 = 2
4. Shortest-Job-First (SJF) Scheduling Algorithm
Priority $p$ is assigned as inverse of required execution time $t$: $p = 1/t$. CPU is assigned to the process requiring shortest execution burst time. Can be non-preemptive or preemptive (Shortest-Remaining-Time-First / SRTF).
-
Non-preemptive Case
* Turnaround Time: P1=6, P2=19, P3=10, P4=5
* Average Turnaround Time: (6 + 19 + 10 + 5)/4 = 10
* Waiting Time: P1=0, P2=11, P3=6, P4=3
* Average Waiting Time: (0 + 11 + 6 + 3)/4 = 5 -
Preemptive Case:
* Turnaround Time: P1=8, P2=19, P3=10, P4=2
* Average Turnaround Time: (8 + 19 + 10 + 2)/4 = 9.75
* Waiting Time: P1=2, P2=11, P3=6, P4=0
* Average Waiting Time: (2 + 11 + 6 + 0)/4 = 4.75