Information Technology Reference
In-Depth Information
FIFO and memcached
Although you may think that FIFO is too simple to be useful, there are some important
cases where it is exactly the right choice for the workload. One such example is mem-
cached. Many web services, such as Facebook, store their user data in a database.
The database provides flexible and consistent lookups, such as, which friends need to
be notified of a particular update to a user's Facebook wall. In order to improve per-
formance, Facebook and other systems put a cache called memcached in front of the
database, so that if a user posts two items to her Facebook wall, the system only needs
to do the database lookup the friend list once.
The system first checks whether the
information is cached, and if so uses that copy.
Because almost all requests are for small amounts of data, memcached is designed
to reply to requests in FIFO order. This minimizes overhead, as there is no need to time
slice between requests. Because tasks are equal in size, this minimizes both average
response time and the variance in response time, and it even maximizes throughput.
Win-win!
(In general, we won't know, so this isn't meant as a practical policy! Rather,
we use it as a thought experiment; later on, we'll see how to approximate SJF
in practice.) If we always schedule the task that has the least remaining work
to do, that will minimize average response time. (For this reason, some call SJF
shortest-remaining-time-first or SRTF.)
To see that SJF is optimal, consider a hypothetical alternative policy that
is not SJF, but that we think might be optimal. At some point this alternative
will run a task that is longer than something else in the queue; after all, it is
not SJF! If we now switch the order of tasks, keeping everything the same, but
doing the shorter task first, we will reduce the average response time.
Thus,
SJF must be optimal.
Figure 7.1 illustrates SJF on the same example we used for FIFO. If a long
task is the first to arrive, it will be scheduled (if we are work-conserving). When
a short task arrives a bit later, the scheduler will preempt the current task, and
start the shorter one. The remaining short tasks will be processed in order of
arrival, followed by finishing the long task.
What counts as \shortest" is the remaining time left on the task, not its
original length. If we are one nanosecond away from finishing an hour long
task, we will minimize average response time by staying with that task, rather
than preempting it for a minute long task that just arrived on the ready queue.
Of course, if they both arrive at about the same time, doing the minute long
task first will dramatically improve average response time.
Does SJF have any other downsides (other than being impossible to imple-
ment because it requires knowledge of the future)?
It turns out that SJF is
