Information Technology Reference
In-Depth Information
Starvation and Sample Bias
Systems that might suffer from starvation require extra care when being measured.
Suppose you want to compare FIFO and SJF experimentally. You set up two computers,
one running each scheduler, and send them the same sequence of tasks. After some
period you stop and report the average response time of completed tasks. If some tasks
are starved, however, the set of completed tasks will be different for the two policies.
Worse, we will have excluded the longest tasks from the results for SJF, skewing the
average response time even further. Put another way, if you want to manipulate statistics
to prove a point, this is a good trick to use! We leave the solution to this issue to the
problem set at end of the chapter.
pessimal for variance in response time. By doing the shortest tasks as quickly
as possible, SJF necessarily does longer tasks as slowly as possible (among poli-
cies that are work conserving). In other words, there is a fundamental tradeoff
between improving average response time and the variance in average response
time.
Worse, SJF can suffer from starvation and frequent context switches. If
enough short tasks arrive, long tasks may never complete. Whenever a task
is put on the ready queue that is shorter than the remaining time left on the
currently scheduled task, the scheduler will preempt it. If this keeps happening
indefinitely, the long task will never finish.
Suppose a supermarket manager reads a portion of this textbook and decides
to implement shortest job first to reduce average waiting times. The manager
tells herself: who cares about variance! A benefit is that there would no longer
be any need for express lanes | if someone has only a few items, they are
immediately whisked to the front of the line, interrupting anyone shopping for
eighteen kids. Of course, the wait times of the customers with full baskets
skyrockets, so they might decide instead to go to the supermarket down the
street, hurting profit margins.
Customers could also try to game the system: if you have a lot of items to
purchase, simply go through the line with one item at a time | you will always
be whisked to the front, at least until everyone else figures out the same dodge.
Exercises
1. For shortest job first, if the scheduler assigns a task to the processor, and
no other task becomes schedulable in the meantime, will the scheduler
ever preempt the current task? Why or why not?
2. Devise a workload where FIFO is pessimal | it does the worst possible
