Scheduling Criteria

Definition

Scheduling Criteria are the metrics/measurements used to evaluate and compare scheduling algorithms. Different criteria have different importance based on system type. A good scheduling algorithm balances multiple criteria appropriately.

Types of Scheduling Criteria

1. CPU Utilization

Definition: Percentage of time CPU is busy (executing processes)

Formula: CPU Utilization = (Busy Time / Total Time) × 100%

Ideal Value: 80-90% (too low = wasting CPU, too high = system bottleneck)

Example:

In 1 second:
- CPU busy: 800ms
- CPU idle: 200ms
- Utilization = 800/1000 = 80%

Why Important?

  • CPU is expensive resource
  • Want to keep it busy (don’t want idle time)
  • Low utilization = wasted money

Trade-off:

  • High CPU utilization may mean longer wait times for users

2. Throughput

Definition: Number of processes completed per unit time

Formula: Throughput = Number of Processes Completed / Total Time

Unit: Processes per hour, or processes per second

Example:

In 1 hour:
- Processes completed: 50
- Throughput = 50/1 hour = 50 processes/hour

Why Important?

  • Measure of system productivity
  • How many jobs finished
  • More jobs = more useful system

Difference from Utilization:

  • Utilization: CPU is busy?
  • Throughput: How many jobs finished?

Trade-off:

  • High throughput may mean longer job execution time (batch process)

3. Turnaround Time

Definition: Time from job submission to job completion

Formula: Turnaround Time = Completion Time - Arrival Time

Unit: Milliseconds or seconds

Example:

Job submitted: 10:00 AM
Job completes: 10:30 AM
Turnaround time = 30 minutes

What’s Included:

  • Waiting time in ready queue
  • Time executing on CPU
  • Time waiting for I/O
  • Time waiting for resources

Why Important?

  • User’s perspective: How long did my job take?
  • Want to minimize this

Real-World Example:

Batch Processing:
Job arrives: 8:00 AM
Job starts: 8:15 AM (waited 15 min)
Job runs: 20 minutes
Job waits for I/O: 10 minutes
Job completes: 8:45 AM
Turnaround time = 45 minutes

4. Response Time

Definition: Time from when user submits request until first response appears

Formula: Response Time = Time of First Response - Time of Request

Unit: Milliseconds (for interactive systems)

Example:

User presses key: 10:00:00.000
Character appears: 10:00:00.050
Response time = 50 milliseconds

What’s Included:

  • Time waiting in queue
  • Time to context switch and start process
  • Time to execute first part of process
  • Does NOT include full completion

Why Important?

  • Interactive systems: User perceives system as responsive
  • User satisfaction depends heavily on response time
  • 50ms = feels instant
  • 100ms = still feels instant
  • 500ms = noticeably slow
  • 2000ms = feels very slow

Real-World Example:

Web Server Scenario:
User clicks link: 1:00:00.000
Server receives request: 1:00:00.001
Server processes request: 1:00:00.050
Web browser gets response: 1:00:00.051
User sees page starting to render: 1:00:00.100
Response time = 100 milliseconds (user-perceived)

vs.

Turnaround time = full page load = maybe 2 seconds

5. Waiting Time

Definition: Total time process spends in ready queue, waiting for CPU

Formula: Waiting Time = Turnaround Time - Actual Execution Time

Unit: Milliseconds or seconds

Example:

Job turnaround time: 100 seconds
Job actual execution: 30 seconds
Waiting time = 100 - 30 = 70 seconds
(spent 70 sec waiting, 30 sec running)

What’s Included:

  • Time in ready queue waiting for CPU
  • Does NOT include I/O waiting time
  • Only CPU scheduling waiting

Why Important?

  • Want to minimize waiting
  • Scheduling algorithm directly affects waiting time
  • Better scheduling = shorter waiting times

Trade-off:

  • FCFS minimizes context switches but increases waiting time
  • Round Robin decreases waiting time but increases context switches

6. Fairness

Definition: All processes get fair share of CPU time

Measurement:

  • No process starved (completely denied CPU)
  • No process gets disproportionately more CPU
  • Some variance acceptable (priority-based)

Example of Unfairness:

FCFS Schedule:
Process 1: 50 seconds (long-running)
Process 2: Gets to run only after Process 1 (unfair to Process 2)

Round Robin Schedule:
Process 1: 10ms CPU time
Process 2: 10ms CPU time
Process 3: 10ms CPU time
(much fairer)

Why Important?

  • All users expect reasonable service
  • Starvation (complete denial of CPU) unacceptable
  • Some fairness necessary for user satisfaction

Trade-off:

  • Maximum fairness (equal time) may not maximize throughput
  • Priority systems deliberately unfair (important process gets more)

Scheduling Criteria by System Type

Interactive Systems (Desktop/Server)

Priority (most to least important):

  1. Response Time (most important!)
  2. Fairness
  3. Turnaround Time
  4. Waiting Time
  5. CPU Utilization
  6. Throughput

Reasoning: Users want immediate response, all should get fair chance

Batch Systems (Non-Interactive)

Priority (most to least important):

  1. Throughput (most important!)
  2. Turnaround Time
  3. CPU Utilization
  4. Response Time (not important - no users)
  5. Fairness
  6. Waiting Time

Reasoning: Maximize jobs finished, don’t care about user perception

Real-Time Systems

Priority (most to least important):

  1. Meeting Deadlines (most important!)
  2. Predictability
  3. Response Time
  4. Fairness (lower priority)

Reasoning: Must meet hard deadlines, predictability critical

Optimizing vs. Criteria

Can We Optimize All Criteria?

No! Criteria often conflict.

Examples:

Conflict 1: Utilization vs. Response Time

To maximize response time (GOOD):
- Interrupt often = many context switches = waste CPU cycles
- Utilization decreases

To maximize utilization (GOOD):
- Reduce context switches = longer time without response
- Response time increases

Conflict 2: Fairness vs. Throughput

To maximize fairness (GOOD):
- Give equal time to all = everyone waits longer
- Turnaround time increases = throughput might decrease

To maximize throughput (GOOD):
- Batch similar jobs = unfair to some processes
- Some processes might starve

Conflict 3: Turnaround Time vs. Response Time

Minimize turnaround:
- Complete jobs as fast as possible
- But user might wait long before first response

Minimize response time:
- Respond to user quickly
- But take longer to complete entire job

Solutions

Different Algorithms for Different Systems:

  • FCFS: Good for batch, bad for interactive
  • Round Robin: Good for interactive, okay for batch
  • Priority: Good for real-time, can be unfair
  • Multilevel Feedback Queue: Compromise between all

Metrics to Measure Criteria

1. For CPU Utilization

measurement = (Total CPU Busy Time) / (Total Time)

2. For Throughput

measurement = (Number of Completed Processes) / (Total Time)

3. For Turnaround Time

measurement = Average(Completion Time - Arrival Time)
for all processes

4. For Response Time

measurement = Average(First Response Time - Request Time)
for all processes

5. For Waiting Time

measurement = Average(Time in Ready Queue)
for all processes

6. For Fairness

Can be measured as:
- Standard deviation of CPU time per process
- Max waiting time - Min waiting time (should be small)
- Check for starvation (any process getting 0 CPU)

Real-World Example

System: Web Server with 3 users

User A: Submits database query (expected 10 sec CPU)
User B: Submits document generation (expected 5 sec CPU)
User C: Submits search (expected 2 sec CPU)

FCFS Scheduling:
Time 0-10s: User A runs (turnaround=10s, response=10s) ← POOR response!
Time 10-15s: User B runs (turnaround=15s, response=15s) ← POOR response!
Time 15-17s: User C runs (turnaround=17s, response=17s) ← POOR response!

Metrics:
- CPU Utilization: 100% ✓
- Throughput: 3 jobs / 17s = 0.176 jobs/s
- Avg Turnaround: (10+15+17)/3 = 14s (not great)
- Avg Response: (10+15+17)/3 = 14s (very poor!)
- Avg Waiting: varies by job
- Fairness: User C had to wait 15s (unfair!)

---

Round Robin (time quantum = 2s):
Time 0-2s: User A runs (2s CPU)
Time 2-4s: User B runs (2s CPU)
Time 4-6s: User C runs (2s CPU) ← response = 4s (much better!)
Time 6-8s: User A runs (2s CPU more)
Time 8-10s: User B runs (2s CPU more)
Time 10-11s: User A runs (1s, done)
Time 11-13s: User C runs (1s more, done)
Time 13-17s: User B runs (remaining time)

Metrics:
- CPU Utilization: 100% ✓
- Throughput: Same 3 jobs / 17s
- Avg Response: (2+2+4)/3 = 2.67s ✓ (much better!)
- Avg Turnaround: (11+17+13)/3 = 13.67s (slightly better)
- Fairness: Much better (all get turns)

Conclusion: Round Robin better for interactive system!

Summary

Scheduling criteria measure quality of scheduling algorithms. Different criteria suit different system types. Key criteria: CPU utilization, throughput, turnaround time, response time, waiting time, and fairness. Most criteria conflict, so choosing appropriate algorithm depends on system priority. Interactive systems prioritize response time and fairness. Batch systems prioritize throughput. Real-time systems prioritize meeting deadlines.