Service Time Estimation

operating-systems scheduling

Definition

Service Time Estimation

Service time estimation is the process of predicting the length of the next CPU burst for a process. This is required for strategies like SPN, SRT, and HRRN.

Mechanism: Exponential Averaging

Since the future behaviour of a process cannot be known with certainty, the OS uses a weighted average of past bursts to predict the next one. Let $T_n$ be the actual length of the $n$-th burst and $S_{n+1}$ be the predicted length for the next burst:

$$S_{n+1}=\alpha T_n+(1-\alpha )S_n$$

• $T_n$: The actual length of the most recent burst.
• $S_n$: The previous estimate.
• $\alpha$: The weighting factor ($0<\alpha <1$).
  • If $\alpha$ is close to 1, the estimate responds quickly to recent changes in behaviour.
  • If $\alpha$ is close to 0, the estimate is stable and ignores transient spikes.

Importance

Accurate estimation is crucial because:

• Fairness: Overestimating a burst might unfairly delay a short process.
• Starvation: Underestimating might allow a CPU-intensive process to monopolise the processor if the algorithm prioritises shorter bursts.