Scheduling criteria (turnaround time, waiting time, throughput) in Operating Systems - Full Explanation

Introduction

Imagine you have many tasks to do, but only one person to do them. How do you decide which task to do first so that everything finishes quickly and fairly? Scheduling criteria help us measure how well we manage these tasks in a computer system.

Explanation

Turnaround Time

Turnaround time is the total time taken from when a task arrives until it is fully completed. It includes the time the task waits and the time it actually runs. This helps us understand how long a user waits to get their job done.

Turnaround time measures the full duration a task spends in the system from start to finish.

Waiting Time

Waiting time is the total time a task spends waiting in the queue before it gets the chance to run. It does not include the running time. This shows how long a task is delayed before execution.

Waiting time focuses only on the delay before a task starts running.

Throughput

Throughput is the number of tasks completed in a given amount of time. Higher throughput means more tasks are finished quickly. It helps measure the efficiency of the system in handling many tasks.

Throughput measures how many tasks the system completes over time.

Real World Analogy

Imagine a busy coffee shop with many customers placing orders. Turnaround time is how long each customer waits from ordering to receiving their coffee. Waiting time is how long they stand in line before their order is taken. Throughput is how many customers get served in an hour.

Turnaround Time → Total time a customer spends from ordering to getting their coffee

Waiting Time → Time a customer waits in line before placing their order

Throughput → Number of customers served in one hour

Diagram

Diagram

┌───────────────┐
│   Task Arrives│
└──────┬────────┘
       │
       ▼
┌───────────────┐
│  Waiting Time │
│ (in queue)    │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│  Running Time │
│ (execution)   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│Turnaround Time│
│(Waiting + Run)│
└───────────────┘

Throughput: Number of tasks completed per unit time → ↑

This diagram shows the flow of a task through waiting and running stages, illustrating turnaround time and waiting time, with throughput as tasks completed over time.

Key Facts

Turnaround Time → Total time from task arrival to completion including waiting and running.

Waiting Time → Total time a task spends waiting in the queue before execution.

Throughput → Number of tasks completed per unit time.

Common Confusions

Thinking turnaround time and waiting time are the same.

Thinking turnaround time and waiting time are the same. Turnaround time includes both waiting and running time, while waiting time only counts the delay before running.

Assuming higher throughput always means shorter waiting time.

Assuming higher throughput always means shorter waiting time. High throughput means more tasks finish over time, but some tasks may still wait longer depending on scheduling.

Summary

Turnaround time measures the full duration a task spends in the system from arrival to completion.

Waiting time counts only the delay before a task starts running, excluding execution time.

Throughput shows how many tasks the system completes in a given time, indicating efficiency.

Practice

1. Which scheduling criterion measures the total time taken from the arrival of a process to its completion?

easy

A. Turnaround time

B. Waiting time

C. Throughput

D. Response time

Solution

1. Step 1: Understand the definition of turnaround time

   Turnaround time is the total time from when a process arrives until it finishes execution.

2. Step 2: Compare with other criteria

   Waiting time is only the time a process waits before starting, throughput is number of processes completed per time, and response time is time until first response.

3. Final Answer:

   Turnaround time -> Option A

4. Quick Check:

   Turnaround time = total process duration [OK]

Hint: Turnaround = arrival to finish total time [OK]

Common Mistakes:

• Confusing waiting time with turnaround time
• Mixing throughput with time durations
• Thinking response time equals turnaround time

2. Which of the following correctly defines waiting time in process scheduling?

easy

A. Number of processes completed per unit time

B. Time from process arrival to completion

C. Time a process spends in the ready queue before execution

D. Time taken by CPU to execute the process

Solution

1. Step 1: Define waiting time

   Waiting time is the time a process spends waiting in the ready queue before it starts running on the CPU.

2. Step 2: Eliminate other options

   Time from process arrival to completion describes turnaround time, C describes throughput, and D is CPU burst time, not waiting time.

3. Final Answer:

   Time a process spends in the ready queue before execution -> Option C

4. Quick Check:

   Waiting time = time before execution [OK]

Hint: Waiting time = time before process runs [OK]

Common Mistakes:

• Confusing waiting time with turnaround time
• Thinking waiting time includes execution time
• Mixing throughput with waiting time

3. Consider three processes with the following completion times (in seconds): P1=10, P2=15, P3=20. If all arrived at time 0, what is the throughput if the total time observed is 20 seconds?

medium

A. 0.20 processes per second

B. 0.15 processes per second

C. 0.10 processes per second

D. 0.25 processes per second

Solution

1. Step 1: Calculate total processes completed

   All three processes (P1, P2, P3) completed within 20 seconds, so total completed = 3.

2. Step 2: Calculate throughput

   Throughput = number of processes completed / total time = 3 / 20 = 0.15 processes per second.

3. Final Answer:

   0.15 processes per second -> Option B

4. Quick Check:

   Throughput = 3/20 = 0.15 [OK]

Hint: Throughput = completed tasks ÷ total time [OK]

Common Mistakes:

• Dividing total time by number of processes instead of reverse
• Counting incomplete processes
• Using average completion time instead of total time

4. A scheduler reports the following for a process: Arrival time = 0, Start time = 5, Completion time = 12. The waiting time is incorrectly calculated as 7 seconds. What is the correct waiting time?

medium

A. 5 seconds

B. 7 seconds

C. 12 seconds

D. 0 seconds

Solution

1. Step 1: Understand waiting time formula

   Waiting time = Start time - Arrival time = 5 - 0 = 5 seconds.

2. Step 2: Identify error in reported waiting time

   The reported waiting time of 7 seconds is incorrect because it does not match the formula.

3. Final Answer:

   5 seconds -> Option A

4. Quick Check:

   Waiting time = start - arrival = 5 [OK]

Hint: Waiting time = start time minus arrival time [OK]

Common Mistakes:

• Using completion time instead of start time
• Adding instead of subtracting times
• Confusing waiting time with turnaround time

5. A system runs 4 processes with arrival times and burst times as follows:
P1: arrival=0, burst=4
P2: arrival=1, burst=3
P3: arrival=2, burst=1
P4: arrival=3, burst=3
If the scheduler uses First-Come-First-Serve (FCFS), what is the average turnaround time?

hard

A. 3.5 seconds

B. 4.5 seconds

C. 5.0 seconds

D. 6.0 seconds

Solution

1. Step 1: Calculate completion times using FCFS

   Process order by arrival: P1(0), P2(1), P3(2), P4(3).
   P1 completes at 0+4=4,
   P2 starts at 4, completes at 4+3=7,
   P3 starts at 7, completes at 7+1=8,
   P4 starts at 8, completes at 8+3=11.

2. Step 2: Calculate turnaround times

   Turnaround = completion - arrival:
   P1: 4-0=4,
   P2: 7-1=6,
   P3: 8-2=6,
   P4: 11-3=8.
   Average turnaround = (4+6+6+8)/4 = 24/4 = 6.0 seconds.

3. Final Answer:

   6.0 seconds -> Option D

4. Quick Check:

   Average turnaround = 24/4 = 6.0 [OK]

Hint: Turnaround = completion - arrival; average = sum/number [OK]

Common Mistakes:

• Calculating turnaround as burst time only
• Ignoring arrival times in scheduling order
• Mixing waiting time with turnaround time