Minimum Average Waiting Time

Computer Science Level 1

A web server receives several requests from across the globe. It processes different kinds of requests which take different amounts of time.

The server runs on a single-threaded process, and thus the requests cannot be processed parallelly. As a result, the clients must wait sometime before the requests are responded to. (The waiting time is the processing time, plus the extra waiting time the request incurs before the scheduler picks it.)

The management decides to minimize the average waiting time of the requests received per day.

Keeping in mind that the requests that will arrive in future cannot be predicted, the scheduler was so engineered as to pick the request waiting which requires the least time to process.

Is this the optimal strategy?

Yes No

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

R Mathe
May 26, 2018

Let t 0 , t 1 , … , t n − 1 t_{0},t_{1},\ldots,t_{n-1} denote the n ∈ N + n\in\mathbb{N}^{+} processes in the order of their processing. Request i i therefore has to wait T i = ∑ j < i t j ⏟ prev. req. + t i T_{i}=\underbrace{\sum_{j<i}t_{j}}_{\text{prev. req.}}+t_{i} for it to be processed. The average waiting time is thus:

[ t ] r c l T ‾ = 1 n ∑ i < n T i = 1 n ∑ i < n ∑ j ≤ i t j = ∑ j < n 1 n ∑ j ≤ i < n t j = ∑ j < n n − j n t j = ∑ j < n ( 1 − j n ) t j \begin{array}{c}[t]{rcl} \overline{T} &= &\frac{1}{n}\sum_{i<n}T_{i}\\ &= &\frac{1}{n}\sum_{i<n}\sum_{j\leq i}t_{j}\\ &= &\sum_{j<n}\frac{1}{n}\sum_{j\leq i<n}t_{j}\\ &= &\sum_{j<n}\frac{n-j}{n}t_{j}\\ &= &\sum_{j<n}(1-\frac{j}{n})t_{j}\\ \end{array}

So for the average waiting time, the processing times are weighted and summed. The j j -th request is weighted 1 − j n 1-\frac{j}{n} . Clearly to minimise this expression, it is necessary and sufficient that the weights decrease as the processing times increase. Since the weights ( 1 − j n ) j < n (1-\frac{j}{n})_{j<n} form a strict antitone sequence, it is necessary and sufficient that the times ( t j ) j < n (t_{j})_{j<n} form a monotone sequence. Hence it is necessary and sufficient to prioritise the requests from shortest to longest processing times.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

What would have been perhaps nicer would be to state more solutions to prevent 50-50. Eg force one to choose the optimal strategy amongst:

  1. prioritise the shorter processes
  2. prioritise the longer processes
  3. prioritise the processes nearest to the average and work outwards
  4. prioritise the processes farthest from the average and work inwards
  5. prioritise the processes nearest to the median and work outwards
  6. prioritise the processes farthest from the median and work inwards
  7. impossible to tell: it depends on the distribution of the processing times
  8. impossible to tell: it depends on the actual values of the processing times
  9. first come first serve

R Mathe - 3 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...