Pre emptive vs Non pre emptive Scheduling

Definition

Scheduling Mode determines how OS decides when to take CPU away from running process and give it to another.

Preemptive Scheduling: OS can forcibly take CPU from running process Non-Preemptive Scheduling: Process keeps CPU until it voluntarily gives it up

Non-Preemptive Scheduling

Also called Cooperative Scheduling or Run-to-Completion scheduling.

How It Works

Once a process gets CPU, it runs until one of these happens:

1. Process calls exit() and terminates
2. Process makes system call that blocks (I/O request)
3. Process voluntarily yields CPU (rare)

OS cannot interrupt running process

Diagram

Process A:          Process B:          Process C:
████████ (running)
         (waits for I/O or terminates)
                    ████████ (runs until done)
                             (waits or terminates)
                                       ████████ (runs)

Characteristics

• Simple: Easier to implement
• Predictable: Same sequence always happens
• No Context Switching Overhead: Less CPU wasted
• Poor Responsiveness: Long-running process blocks others

When is CPU Given to Next Process?

1. I/O Request: Current process blocked, ready queue processed
2. Termination: Process finishes, next process selected
3. Voluntary Yield: Process calls sched_yield() (rare)

Real-World Issues

Process A: Calculating complex math (10 seconds)
         ↓
Process B: Waiting for user to press key (needs responsiveness!)
         ↓
User presses key after 1 second
         ↓
System doesn't respond for 9 more seconds
User frustrated!

Examples

• Old Operating Systems: DOS, Windows 3.1, Mac OS 9
• Embedded Systems: Simple devices with limited processes
• Cooperative Multitasking: Old application servers

Preemptive Scheduling

Also called Time-Sliced Scheduling or Multitasking.

How It Works

OS uses timer interrupt to take CPU from process periodically.

Timer Interrupt (every millisecond):
  1. CPU context (save registers)
  2. Run scheduler
  3. Select next process
  4. Load context of next process

OS can forcibly interrupt running process

Diagram

Time:  0ms     10ms    20ms    30ms    40ms    50ms
       │       │       │       │       │       │
Proc A █████
              █████
                    █████
                          █████
                                █████
Proc B           █████
                      █████
                            █████
                                  █████
Proc C                 █████
                             █████
                                   █████

       ↑       ↑       ↑       ↑       ↑       ↑
     Timer   Timer   Timer   Timer   Timer   Timer
     Int     Int     Int     Int     Int     Int

Characteristics

• Complex: Harder to implement (need timer hardware)
• Responsive: User input handled quickly
• Fair: All processes get CPU time
• Context Switch Overhead: Wasted CPU time
• Unpredictable: Order varies (depends on algorithm)

When is CPU Given to Next Process?

1. Timer Interrupt: Periodic interruption (time quantum expired)
2. I/O Request: Process needs I/O
3. Termination: Process finishes
4. Higher Priority Event: More important process needs CPU

Real-World Benefit

Same Scenario (preemptive):

Process A: Calculating complex math (10 seconds)
Process B: Waiting for user input

Time=1ms: Timer interrupt, Switch to Process B
Time=2ms: User presses key, Process B runs immediately!
User sees response within milliseconds!

Examples

• Modern Operating Systems: Windows (since NT), Linux, macOS, Unix
• Real-Time Systems: Critical systems needing quick response
• Interactive Systems: Desktop computers, servers
• Mobile OS: iOS, Android (with modifications)

Comparison Table

Scheduling Algorithm Compatibility

Works with Non-Preemptive

• FCFS (First Come First Served)
• SJF (Shortest Job First)
• Cooperative Multitasking

Works with Preemptive

• Round Robin (RR)
• Priority Scheduling
• Shortest Remaining Time (SRTF)
• Multilevel Feedback Queue (MLFQ)

Time Quantum (Time Slice)

In Preemptive Scheduling: How long each process runs before being interrupted

Typical Values

• Too Small (1ms):
  • Pros: Fair, responsive
  • Cons: Excessive context switching overhead
• Too Large (100ms):
  • Pros: Less context switching
  • Cons: Feels unresponsive to user
• Optimal (10-100ms):
  • Windows: 15-20ms
  • Linux: Depends on runnable processes
  • User perceives responsiveness

Effect on User Experience

Time Quantum = 1ms:        Time Quantum = 100ms:
Process A: 1ms             Process A: 100ms
Process B: 1ms             Process B: 100ms
Process C: 1ms             Process C: 100ms
Results:                   Results:
- Very responsive          - Long delays possible
- Lots of switching        - Less overhead
- Smooth transitions       - Visible freezes

Context Switching Overhead

What Happens During Context Switch

1. Save Context (0.5-1 microsecond)

   • CPU registers (16-256 registers)
   • Program counter
   • Memory management info

2. Run Scheduler (1-10 microseconds)

   • Select next process
   • Update scheduling structures

3. Load Context (0.5-1 microsecond)

   • Load registers from PCB
   • Jump to program counter

4. Cache Misses (10-100 microseconds)

   • New process brings different memory
   • CPU cache becomes invalid
   • Must reload from memory (slow!)

Total Context Switch Time: 10-100 microseconds (modern CPU)

Context Switch Overhead Percentage

Scenario 1: Time Quantum = 1ms, Context Switch = 10 microseconds
Useful work: 990 microseconds
Overhead: 10/1000 = 1%
Acceptable!

Scenario 2: Time Quantum = 10 microseconds, Context Switch = 10 microseconds
Useful work: 0 microseconds
Overhead: 10/10 = 100%
Disaster! (all time wasted switching)

Conclusion: Can't make time quantum too small

When to Use Each Mode

Use Non-Preemptive When

1. Embedded Systems: Limited processes, known behavior
2. Batch Processing: Jobs run independently
3. Predictability Critical: Real-time hard deadlines with predictable processes
4. Low Resource Devices: Limited memory, can’t afford scheduler overhead

Use Preemptive When

1. Interactive Systems: Desktop, server, mobile
2. Multi-User Systems: Multiple users need responsive system
3. General-Purpose OS: Windows, Linux, macOS
4. Safety-Critical Real-Time: Need immediate response to events
5. Fairness Important: All processes should get fair CPU time

Example Scenarios

Scenario 1: Bank ATM (Non-Preemptive Better)

Process 1: Calculate interest (5 seconds)
Process 2: Process withdrawal (requires user response)

Non-Preemptive: Process 1 runs, finishes, then Process 2 runs (total 10 sec)
Preemptive: Interrupts constantly, context switching overhead (could be 15 sec)

Conclusion: Non-preemptive better here (no user involved)

Scenario 2: Desktop Operating System (Preemptive Better)

Process 1: Video rendering (long-running)
Process 2: Text editor (user typing)

Non-Preemptive: User types key, editor waits for video process to finish (unresponsive!)
Preemptive: Timer interrupt brings editor to foreground, user sees response immediately!

Conclusion: Preemptive much better (multiple users)

Summary

Non-preemptive scheduling is simple but unresponsive. Process keeps CPU until it gives up (by blocking or terminating). Modern systems use preemptive scheduling where OS timer forcibly takes CPU to ensure fairness and responsiveness. Key trade-off: context switching overhead vs. responsiveness. Most modern OSes (Windows, Linux, macOS) use preemptive scheduling with time quantums around 10-20 milliseconds.