- 2068 Bhadra · 4+4 marks
Preemptive vs non-preemptive; real-time scheduling
Short answer
Non-preemptive scheduling lets a process hold CPU until it blocks or finishes; preemptive can forcibly take CPU away for shorter response. Real-time scheduling uses preemptive priority to meet deadlines: Rate Monotonic gives highest priority to shortest period, Earliest Deadline First runs task with nearest deadline, schedulable up to 100% CPU.
Describe the difference between preemptive and non-preemptive scheduling algorithm. Explain about scheduling in real time.
Preemptive vs non-preemptive scheduling
In non-preemptive scheduling, once the CPU is given to a process it keeps it until it terminates or blocks for I/O; the OS cannot take the CPU away. In preemptive scheduling, the OS can forcibly take the CPU from a running process (when its time slice expires or a higher-priority process arrives) and give it to another.
| Basis | Preemptive | Non-preemptive |
|---|---|---|
| CPU release | OS can take the CPU away at any time | Only on termination or voluntary wait |
| Response time | Good for interactive use | Poor; a long job delays others (convoy effect) |
| Overhead | More context switches | Less overhead |
| Shared data | Needs synchronization (race conditions) | Simpler; no races caused by preemption |
| Starvation | Possible for low-priority processes (preemptive priority) or long jobs (SRTF) | Possible for long or low-priority jobs in SJF and non-preemptive priority; none in FCFS |
| Algorithms | Round robin, SRTF, preemptive priority | FCFS, SJF, non-preemptive priority |
| Hardware | Needs a timer interrupt | No timer needed |
Scheduling in real time
A real-time system must produce results within given deadlines. Tasks may be periodic (repeating every period P with execution time E) or aperiodic/sporadic. Real-time systems are hard (a missed deadline is a failure) or soft (a miss only lowers quality).
Real-time scheduling algorithms can be static (priorities fixed before run time) or dynamic:
- Rate Monotonic (RM): static; the task with the shortest period gets the highest priority; preemptive. A task set is guaranteed schedulable if CPU utilisation U = Σ(Eᵢ/Pᵢ) ≤ n(2^(1/n) − 1) (about 69% for large n).
- Earliest Deadline First (EDF): dynamic; the task with the nearest absolute deadline runs first. Schedulable if U ≤ 1 on one CPU.
- Least Laxity First: runs the task with the smallest slack time.
Real-time scheduling should be preemptive and priority based, with small and bounded interrupt latency and dispatch time. The scheduler may also use admission control (accepting a task only if its deadline can be guaranteed).
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Real-time scheduling; two-processor numerical · Operating System, chapter 2
- Preemptive vs non-preemptive; process states · Operating System, chapter 2
- Rate Monotonic real-time schedule · Operating System, chapter 2
- RR, preemptive priority, preemptive SJF · Operating System, chapter 2
- Preemptive priority and SRTF Gantt · Operating System, chapter 2
- Disk scheduling: FCFS, SSF, SCAN at 53 · Operating System, chapter 6 · asked 3×
- Non-preemptive priority scheduling (10, 5, 7 ms) · Embedded System, chapter 6 · asked 2×
- Preemptive priority scheduling (4, 6, 5 ms) · Embedded System, chapter 6
- Non-preemptive SJF with P4 arriving · Embedded System, chapter 6 · asked 2×
- Preemptive priority scheduling with P4 (6 ms) · Embedded System, chapter 6 · asked 2×